// Copyright (c) 2023, Compiler Explorer Authors
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//     * Redistributions of source code must retain the above copyright notice,
//       this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright
//       notice, this list of conditions and the following disclaimer in the
//       documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

import _ from 'underscore';

import {EdgeColor} from '../../../types/compilation/cfg.interfaces.js';
import {CompilationResult} from '../../../types/compilation/compilation.interfaces.js';
import type {ResultLineSource} from '../../../types/resultline/resultline.interfaces.js';
import {logger} from '../../logger.js';
import {BaseInstructionSetInfo, InstructionType} from '../instruction-sets/base.js';

export type Range = {
    start: number;
    end: number;
};

export type BBRange = {
    nameId: string;
    start: number;
    end: number;
    actionPos: number[];
};

export type CanonicalBB = {
    nameId: string;
    start: number;
    end: number;
};

export type Node = {
    id: string;
    label: string;
};

export type Edge = {
    from: string;
    to: string;
    arrows: string;
    color: EdgeColor;
};

export type AssemblyLine = {
    text: string;
    source?: ResultLineSource | undefined;
};

export class BaseCFGParser {
    static get key() {
        return 'base';
    }

    constructor(public readonly instructionSetInfo: BaseInstructionSetInfo) {}

    public filterData(assembly: AssemblyLine[]): AssemblyLine[] {
        const jmpLabelRegex = /\.L\d+:/;
        const isCode = (x: AssemblyLine) =>
            x?.text && (x.source !== null || jmpLabelRegex.test(x.text) || this.isFunctionName(x));
        return this.filterTextSection(assembly).map(_.clone).filter(isCode);
    }

    public splitToFunctions(asmArr: AssemblyLine[]): Range[] {
        if (asmArr.length === 0) return [];
        const result: Range[] = [];
        let cur = 1;
        const last = asmArr.length;
        const fnRange: Range = {start: 0, end: 0};
        while (cur !== last) {
            if (this.isFunctionEnd(asmArr[cur].text)) {
                fnRange.end = cur;
                if (fnRange.end > fnRange.start + 1) result.push(_.clone(fnRange));
                fnRange.start = cur;
            }
            ++cur;
        }

        fnRange.end = last;
        if (fnRange.end > fnRange.start + 1) result.push(_.clone(fnRange));
        return result;
    }

    protected getBbId(firstInst: string): string {
        return firstInst;
    }

    protected getBbFirstInstIdx(firstLine: number) {
        //inst is expected to be .L*: where * in 1,2,...
        return firstLine + 1;
    }

    protected splitToBasicBlocks(asmArr: AssemblyLine[], range: Range) {
        let cur = range.start;
        const last = range.end;
        if (cur === last) return [];
        const functionName = asmArr[cur].text;
        ++cur;

        let rangeBb: BBRange = {nameId: functionName, start: cur, end: 0, actionPos: []};
        const result: BBRange[] = [];

        const newRangeWith = (oldRange: BBRange, nameId: string, start: number) => ({
            nameId: nameId,
            start: start,
            actionPos: [],
            end: oldRange.end,
        });

        while (cur < last) {
            const inst = asmArr[cur].text;
            const prevInst = asmArr[cur - 1] ? asmArr[cur - 1].text : '';
            if (this.isBasicBlockEnd(inst, prevInst)) {
                rangeBb.end = cur;
                result.push(_.clone(rangeBb));
                rangeBb = newRangeWith(rangeBb, this.getBbId(inst), this.getBbFirstInstIdx(cur));
            } else if (this.instructionSetInfo.isJmpInstruction(inst)) {
                rangeBb.actionPos.push(cur);
            }
            ++cur;
        }

        rangeBb.end = last;
        result.push(_.clone(rangeBb));
        return result;
    }

    protected isFunctionName(line: AssemblyLine) {
        return line.text.trim().indexOf('.') !== 0 || line.text.startsWith('.omp_');
    }

    public async processFuncNames(code: AssemblyLine[], fullRes?: CompilationResult): Promise<AssemblyLine[]> {
        return code;
    }

    protected getAsmDirective(txt: string) {
        const pattern = /^\s*(\.[^ L]\S*)/;
        const match = txt.match(pattern);
        if (match !== null) {
            return match[1];
        }
        return null;
    }

    protected filterTextSection(data: AssemblyLine[]): AssemblyLine[] {
        let useCurrentSection = true;
        const result: AssemblyLine[] = [];
        for (const i in data) {
            const x = data[i];
            const directive = this.getAsmDirective(x.text);
            if (directive != null) {
                if (directive === '.text' || directive === '.data') {
                    useCurrentSection = directive === '.text';
                } else if (directive === '.section') {
                    // Only patttern match for now.
                    // Extracting section name would require adjusting demangling code
                    // as demangled name could contain various symbols including ','.
                    useCurrentSection = /\.section\s*"?\.text/.test(x.text);
                } else if (useCurrentSection) {
                    result.push(x);
                }
            } else if (useCurrentSection) {
                result.push(x);
            }
        }
        return result;
    }

    protected isFunctionEnd(x: string) {
        return x[0] !== ' ' && (x[0] !== '.' || x.startsWith('.omp_')) && x.includes(':');
    }

    protected isBasicBlockEnd(inst: string, prevInst: string) {
        return inst[0] === '.' || prevInst.includes(' ret');
    }

    protected extractJmpTargetName(inst: string) {
        return inst.match(/\.L\d+/) + ':';
    }

    protected extractNodeIdFromInst(inst: string) {
        return inst;
    }

    protected extractAltJmpTargetName(asmArr: AssemblyLine[], bbIdx: number, arrBB: CanonicalBB[]): string {
        const hasName = (asmArr: AssemblyLine[], cbb: CanonicalBB) => {
            const asm = asmArr[cbb.end];
            return asm ? this.isBasicBlockEnd(asm.text, '') : false;
        };

        const generateName = (name: string, suffix: number) => {
            const pos = name.indexOf(this.getLabelSeparator());
            if (pos === -1) return `${name + this.getLabelSeparator() + suffix}`;
            return name.substring(0, pos + 1) + suffix;
        };
        const bb = arrBB[bbIdx];
        if (hasName(asmArr, bb)) return asmArr[bb.end].text;
        const newBbName = generateName(bb.nameId, bb.end);
        arrBB[bbIdx + 1].nameId = newBbName;
        return newBbName;
    }

    protected getLabelSeparator() {
        return '@';
    }

    protected splitToCanonicalBasicBlock(basicBlock: BBRange): CanonicalBB[] {
        const actionPos = basicBlock.actionPos;
        let actPosSz = actionPos.length;
        if (actionPos[actPosSz - 1] + 1 === basicBlock.end) {
            --actPosSz;
        }

        if (actPosSz === 0)
            return [
                {
                    nameId: basicBlock.nameId,
                    start: basicBlock.start,
                    end: basicBlock.end,
                },
            ];
        if (actPosSz === 1)
            return [
                {nameId: basicBlock.nameId, start: basicBlock.start, end: actionPos[0] + 1},
                {
                    nameId: basicBlock.nameId + this.getLabelSeparator() + (actionPos[0] + 1),
                    start: actionPos[0] + 1,
                    end: basicBlock.end,
                },
            ];

        let cur = 0;
        const last = actPosSz;
        const blockName = basicBlock.nameId;
        let tmp: CanonicalBB = {nameId: blockName, start: basicBlock.start, end: actionPos[cur] + 1};
        const result: CanonicalBB[] = [];
        result.push(_.clone(tmp));
        while (cur !== last - 1) {
            tmp.nameId = blockName + this.getLabelSeparator() + (actionPos[cur] + 1);
            tmp.start = actionPos[cur] + 1;
            ++cur;
            tmp.end = actionPos[cur] + 1;
            result.push(_.clone(tmp));
        }

        tmp = {
            nameId: blockName + this.getLabelSeparator() + (actionPos[cur] + 1),
            start: actionPos[cur] + 1,
            end: basicBlock.end,
        };
        result.push(_.clone(tmp));

        return result;
    }

    protected concatInstructions(asmArr: AssemblyLine[], first: number, last: number) {
        return asmArr
            .slice(first, last)
            .map(x => x.text)
            .join('\n');
    }

    protected makeNodes(asms: AssemblyLine[], arrOfCanonicalBasicBlock: CanonicalBB[]): Node[] {
        return arrOfCanonicalBasicBlock.map(e => ({
            id: e.nameId,
            label: `${e.nameId}${e.nameId.includes(':') ? '' : ':'}\n${this.concatInstructions(asms, e.start, e.end)}`,
        }));
    }

    protected makeEdges(asmArr: AssemblyLine[], arrOfCanonicalBasicBlock: CanonicalBB[]) {
        const edges: Edge[] = [];

        const setEdge = (sourceNode: string, targetNode: string, color: EdgeColor) => ({
            from: sourceNode,
            to: targetNode,
            arrows: 'to',
            color: color,
        });

        /* note: x.end-1 possible values:
            jmp .L*, {jne,je,jg,...} .L*, ret/rep ret, call and any other instruction that doesn't change control flow
        */

        for (const [i, x] of arrOfCanonicalBasicBlock.entries()) {
            const lastInst = asmArr[x.end - 1].text;
            switch (this.instructionSetInfo.getInstructionType(lastInst)) {
                case InstructionType.jmp: {
                    //we have to deal only with jmp destination, jmp instruction are always taken.
                    //edge from jump inst
                    const targetNode = this.extractJmpTargetName(lastInst);
                    edges.push(setEdge(x.nameId, targetNode, 'blue'));
                    break;
                }
                case InstructionType.conditionalJmpInst: {
                    //deal with : branch taken, branch not taken
                    const targetNode1 = this.extractJmpTargetName(lastInst);
                    edges.push(setEdge(x.nameId, targetNode1, 'green'));
                    const targetNode2 = this.extractAltJmpTargetName(asmArr, i, arrOfCanonicalBasicBlock);
                    edges.push(setEdge(x.nameId, targetNode2, 'red'));
                    break;
                }
                case InstructionType.notRetInst: {
                    //precondition: lastInst is not last instruction in asmArr (but it is in canonical basic block)
                    //note : asmArr[x.end] expected to be .L*:(name of a basic block)
                    //       this .L*: has to be exactly after the last instruction in the current canonical basic block
                    if (asmArr[x.end]) {
                        const targetNode = this.extractNodeIdFromInst(asmArr[x.end].text);
                        edges.push(setEdge(x.nameId, targetNode, 'grey'));
                    }
                    break;
                }
                case InstructionType.retInst: {
                    break;
                }
            }
        }
        logger.debug(edges);
        return edges;
    }

    public generateFunctionCfg(code: AssemblyLine[], fn: Range) {
        // Split fn to basic blocks by compiler-given labels
        const basicBlocks = this.splitToBasicBlocks(code, fn);
        let arrOfCanonicalBasicBlock: CanonicalBB[] = [];
        for (const bb of basicBlocks) {
            // Split further, considering jump targets start new blocks
            const tmp = this.splitToCanonicalBasicBlock(bb);
            arrOfCanonicalBasicBlock = arrOfCanonicalBasicBlock.concat(tmp);
        }
        return {
            nodes: this.makeNodes(code, arrOfCanonicalBasicBlock),
            edges: this.makeEdges(code, arrOfCanonicalBasicBlock),
        };
    }

    public getFnName(code: AssemblyLine[], fn: Range) {
        return code[fn.start].text;
    }
}
