reconstructor.js

// Reconstructor - Convert optimized 3AC back to C-like code

class Reconstructor {
    constructor() {}

    reconstruct(instructions) {
        try {
            // step 1: inline single-use temporaries
            const inlined = this.inlineTemporaries(instructions);
            // step 2: pattern-match control flow structures
            const cCode = this.buildCCode(inlined);
            return cCode;
        } catch (e) {
            return '// Reconstruction error: ' + e.message + '\n// Showing raw translation:\n' +
                this.rawTranslation(instructions);
        }
    }

    // inline temporary variables used only once
    inlineTemporaries(instructions) {
        const usageCount = {};
        const defMap = {};

        // count usages and map definitions
        for (let i = 0; i < instructions.length; i++) {
            const instr = instructions[i];
            if (instr.result && this.isTemp(instr.result)) {
                defMap[instr.result] = i;
            }
            if (instr.arg1 && this.isTemp(instr.arg1)) {
                usageCount[instr.arg1] = (usageCount[instr.arg1] || 0) + 1;
            }
            if (instr.arg2 && this.isTemp(instr.arg2)) {
                usageCount[instr.arg2] = (usageCount[instr.arg2] || 0) + 1;
            }
        }

        // find temps used exactly once -> inline them
        const inlineMap = {};
        for (const [tmpName, count] of Object.entries(usageCount)) {
            if (count === 1 && defMap[tmpName] !== undefined) {
                const defInstr = instructions[defMap[tmpName]];
                if (defInstr.type === 'binary') {
                    inlineMap[tmpName] = `(${this.resolveInline(defInstr.arg1, inlineMap)} ${defInstr.op} ${this.resolveInline(defInstr.arg2, inlineMap)})`;
                } else if (defInstr.type === 'unary') {
                    inlineMap[tmpName] = `(${defInstr.op}${this.resolveInline(defInstr.arg1, inlineMap)})`;
                } else if (defInstr.type === 'assign') {
                    inlineMap[tmpName] = this.resolveInline(defInstr.arg1, inlineMap);
                }
            }
        }

        // rebuild instructions without inlined temps
        const result = [];
        for (let i = 0; i < instructions.length; i++) {
            const instr = instructions[i];
            // skip temp definitions that were inlined
            if (instr.result && this.isTemp(instr.result) && inlineMap[instr.result]) {
                continue;
            }
            // resolve inlined references
            const resolved = { ...instr };
            if (resolved.arg1) resolved.arg1 = this.resolveInline(resolved.arg1, inlineMap);
            if (resolved.arg2) resolved.arg2 = this.resolveInline(resolved.arg2, inlineMap);
            result.push(resolved);
        }

        return result;
    }

    resolveInline(value, inlineMap) {
        if (value && inlineMap[value]) return inlineMap[value];
        return value;
    }

    isTemp(name) {
        return typeof name === 'string' && /^t\d+$/.test(name);
    }

    buildCCode(instructions) {
        const lines = [];
        let indent = 0;
        const pad = () => '    '.repeat(indent);
        let i = 0;

        while (i < instructions.length) {
            const instr = instructions[i];

            switch (instr.type) {
                case 'func_begin':
                    lines.push(`${pad()}int ${instr.name}(${(instr.params || []).map(p => p.dataType + ' ' + p.name).join(', ')}) {`);
                    indent++;
                    break;

                case 'func_end':
                    indent = Math.max(0, indent - 1);
                    lines.push(`${pad()}}`);
                    break;

                case 'declare':
                    lines.push(`${pad()}int ${instr.result};`);
                    break;

                case 'assign':
                    lines.push(`${pad()}${instr.result} = ${instr.arg1};`);
                    break;

                case 'binary':
                    lines.push(`${pad()}${instr.result} = ${instr.arg1} ${instr.op} ${instr.arg2};`);
                    break;

                case 'unary':
                    lines.push(`${pad()}${instr.result} = ${instr.op}${instr.arg1};`);
                    break;

                case 'param':
                    // accumulate params for the upcoming call
                    break;

                case 'call': {
                    // gather previous params
                    const params = [];
                    for (let j = i - 1; j >= 0 && instructions[j].type === 'param'; j--) {
                        params.unshift(instructions[j].arg1);
                    }
                    if (instr.result) {
                        lines.push(`${pad()}${instr.result} = ${instr.name}(${params.join(', ')});`);
                    } else {
                        lines.push(`${pad()}${instr.name}(${params.join(', ')});`);
                    }
                    break;
                }

                case 'return':
                    if (instr.arg1) {
                        lines.push(`${pad()}return ${instr.arg1};`);
                    } else {
                        lines.push(`${pad()}return;`);
                    }
                    break;

                case 'label': {
                    // try to detect while loop pattern: label -> ... -> if_false_goto -> ... -> goto [back] -> endLabel
                    const whileResult = this.tryMatchWhile(instructions, i);
                    if (whileResult) {
                        lines.push(`${pad()}while (${whileResult.condition}) {`);
                        indent++;
                        const bodyLines = this.buildCCode(whileResult.bodyInstructions);
                        lines.push(...bodyLines.split('\n').map(l => pad() + l.trim()).filter(l => l.trim()));
                        indent--;
                        lines.push(`${pad()}}`);
                        i = whileResult.endIndex;
                        break;
                    }
                    // otherwise just emit label as comment
                    lines.push(`${pad()}// ${instr.label}:`);
                    break;
                }

                case 'goto':
                    lines.push(`${pad()}goto ${instr.label};`);
                    break;

                case 'if_false_goto': {
                    // try to match if/else pattern
                    const ifResult = this.tryMatchIf(instructions, i);
                    if (ifResult) {
                        lines.push(`${pad()}if (${ifResult.condition}) {`);
                        indent++;
                        const thenLines = this.buildCCode(ifResult.thenInstructions);
                        lines.push(...thenLines.split('\n').map(l => pad() + l.trim()).filter(l => l.trim()));
                        indent--;
                        if (ifResult.elseInstructions && ifResult.elseInstructions.length > 0) {
                            lines.push(`${pad()}} else {`);
                            indent++;
                            const elseLines = this.buildCCode(ifResult.elseInstructions);
                            lines.push(...elseLines.split('\n').map(l => pad() + l.trim()).filter(l => l.trim()));
                            indent--;
                        }
                        lines.push(`${pad()}}`);
                        i = ifResult.endIndex;
                        break;
                    }
                    lines.push(`${pad()}if (!${instr.arg1}) goto ${instr.label};`);
                    break;
                }

                case 'if_goto':
                    lines.push(`${pad()}if (${instr.arg1}) goto ${instr.label};`);
                    break;

                case 'array_access':
                    lines.push(`${pad()}${instr.result} = ${instr.arg1}[${instr.arg2}];`);
                    break;

                default:
                    break;
            }
            i++;
        }

        return lines.join('\n');
    }

    // try to match while(cond) { body } pattern from labels/gotos
    tryMatchWhile(instructions, labelIndex) {
        const startLabel = instructions[labelIndex].label;

        // find if_false_goto after the label
        let condIndex = -1;
        for (let j = labelIndex + 1; j < instructions.length; j++) {
            const instr = instructions[j];
            if (instr.type === 'if_false_goto') {
                condIndex = j;
                break;
            }
            // if we hit another label or control flow first, not a while
            if (instr.type === 'label' || instr.type === 'goto') return null;
            // allow binary/unary/assign before the condition
            if (!['binary','unary','assign','declare'].includes(instr.type)) return null;
        }
        if (condIndex === -1) return null;

        const endLabel = instructions[condIndex].label;

        // find the goto back to startLabel, followed by endLabel
        let gotoIndex = -1;
        for (let j = condIndex + 1; j < instructions.length; j++) {
            if (instructions[j].type === 'goto' && instructions[j].label === startLabel) {
                gotoIndex = j;
                break;
            }
        }
        if (gotoIndex === -1) return null;

        // verify endLabel follows the goto
        if (gotoIndex + 1 < instructions.length &&
            instructions[gotoIndex + 1].type === 'label' &&
            instructions[gotoIndex + 1].label === endLabel) {

            const condition = instructions[condIndex].arg1;
            const bodyInstructions = instructions.slice(condIndex + 1, gotoIndex);

            return {
                condition,
                bodyInstructions,
                endIndex: gotoIndex + 1
            };
        }

        return null;
    }

    // try to match if/else pattern
    tryMatchIf(instructions, ifFalseIndex) {
        const instr = instructions[ifFalseIndex];
        const falseLabel = instr.label;
        const condition = instr.arg1;

        // find the target label
        let falseLabelIndex = -1;
        for (let j = ifFalseIndex + 1; j < instructions.length; j++) {
            if (instructions[j].type === 'label' && instructions[j].label === falseLabel) {
                falseLabelIndex = j;
                break;
            }
        }
        if (falseLabelIndex === -1) return null;

        // check if there's a goto just before the falseLabel (if-else pattern)
        const beforeFalseLabel = instructions[falseLabelIndex - 1];
        if (beforeFalseLabel && beforeFalseLabel.type === 'goto') {
            // if-else pattern
            const endLabel = beforeFalseLabel.label;
            let endLabelIndex = -1;
            for (let j = falseLabelIndex + 1; j < instructions.length; j++) {
                if (instructions[j].type === 'label' && instructions[j].label === endLabel) {
                    endLabelIndex = j;
                    break;
                }
            }

            const thenInstructions = instructions.slice(ifFalseIndex + 1, falseLabelIndex - 1);
            const elseInstructions = endLabelIndex !== -1
                ? instructions.slice(falseLabelIndex + 1, endLabelIndex)
                : instructions.slice(falseLabelIndex + 1);

            return {
                condition,
                thenInstructions,
                elseInstructions,
                endIndex: endLabelIndex !== -1 ? endLabelIndex : falseLabelIndex
            };
        }

        // simple if (no else)
        const thenInstructions = instructions.slice(ifFalseIndex + 1, falseLabelIndex);
        return {
            condition,
            thenInstructions,
            elseInstructions: null,
            endIndex: falseLabelIndex
        };
    }

    rawTranslation(instructions) {
        return instructions.map(instr => {
            switch (instr.type) {
                case 'func_begin': return `// function ${instr.name}`;
                case 'func_end': return '';
                case 'assign': return `${instr.result} = ${instr.arg1};`;
                case 'binary': return `${instr.result} = ${instr.arg1} ${instr.op} ${instr.arg2};`;
                case 'unary': return `${instr.result} = ${instr.op}${instr.arg1};`;
                case 'return': return instr.arg1 ? `return ${instr.arg1};` : 'return;';
                case 'param': return `// param ${instr.arg1}`;
                case 'call': return instr.result ? `${instr.result} = ${instr.name}(...);` : `${instr.name}(...);`;
                case 'label': return `${instr.label}:`;
                case 'goto': return `goto ${instr.label};`;
                case 'if_false_goto': return `if (!${instr.arg1}) goto ${instr.label};`;
                default: return `// ${JSON.stringify(instr)}`;
            }
        }).join('\n');
    }
}