package org.simantics.scl.compiler.internal.codegen.analysis;

import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
import org.simantics.scl.compiler.common.names.Name;
import org.simantics.scl.compiler.common.names.Names;
import org.simantics.scl.compiler.constants.SCLConstant;
import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;
import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
import org.simantics.scl.compiler.internal.codegen.references.Val;
import org.simantics.scl.compiler.internal.codegen.references.ValRef;
import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;
import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;
import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;
import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;

import gnu.trove.map.hash.THashMap;
import gnu.trove.set.hash.THashSet;

public abstract class StatementBrowser {

    THashSet<SSABlock> visited;
    THashMap<SSABlock,SSAStatement> loopPos;
    SSAStatement fromStatement;
    SSABlock fromBlock;
    
    boolean stopBrowse = false;
    
    protected void stopBrowse() {
        stopBrowse = true;
    }
    
    public boolean isStopped() {
        return stopBrowse;
    }
    
    /**
     * Browses all statements that are potentially executed
     * between from and to.
     */
    public void browseBetween(SSAStatement from, SSAStatement to) {
        SSABlock toBlock = to.getParent();
        if(from.getParent() == toBlock) {
            for(SSAStatement cur = from.getNext(); cur != to; cur = cur.getNext()) {
                if(cur == null)
                    dominationError();
                visitStatement(cur);
                if(stopBrowse)
                    return;
            }
        }
        else {
            for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
                visitStatement(cur);
                if(stopBrowse)
                    return;
            }

            visited = new THashSet<SSABlock>();            
            fromStatement = from;
            fromBlock = from.getParent();
            
            loopPos = new THashMap<SSABlock,SSAStatement>();
            loopPos.put(toBlock, to);

            browsePredecessors(toBlock);            
        }
    }
    
    private void browseBetweenRec(SSAStatement to) {
        SSABlock toBlock = to.getParent();
        if(fromBlock == toBlock) {
            for(SSAStatement cur = fromStatement.getNext(); cur != to; cur = cur.getNext()) {
                if(cur == null)
                    dominationError();
                visitStatement(cur);
                if(stopBrowse)
                    return;
            }
        }
        else {
            for(SSAStatement cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
                visitStatement(cur);
                if(stopBrowse)
                    return;
            }
            loopPos.put(toBlock, to);
            browsePredecessors(to.getParent());            
        }
    }
    
    private void browsePredecessors(SSABlock block) {
        for(ContRef contRef = block.getOccurrence(); contRef != null; contRef = contRef.getNext()) {
            browse(contRef.getParent().getParent());
            if(stopBrowse)
                return;
        }
    }    
    
    private void browse(SSABlock block) {
        if(!visited.add(block))
            return;
        if(block == fromBlock) {
            for(SSAStatement cur = fromStatement.getNext(); cur != null; cur = cur.getNext()) {
                visitStatement(cur);
                if(stopBrowse)
                    return;
            }
            return;
        }
        if(loopPos.contains(block)) {
            handleLoop(block, loopPos.get(block));
            return;
        }
        for(SSAStatement cur = block.getFirstStatement(); cur != null; cur = cur.getNext()) {
            visitStatement(cur);
            if(stopBrowse)
                return;
        }
        browsePredecessors(block);
        if(stopBrowse)
            return;
        if(block.getPrev() == null) {
            SSAFunction function = block.getParent();
            if(function == fromBlock.getParent())
                dominationError();
            Val functionTarget = function.getTarget();
            if(functionTarget instanceof BoundVar)
                browseFunction((BoundVar)functionTarget, function.getArity());
            else
                dominationError();
        }
    }
    
    private static void dominationError() {
        throw new InternalCompilerError("Statement 'from' does not dominate the statement 'to'.");
    }

    protected void browseFunction(BoundVar function, int arity) {
        for(ValRef cur = function.getOccurrence(); cur != null; cur = cur.getNext()) {
            ValRefBinder binder = cur.getParent();
            if(binder instanceof LetApply)
                browseApply((LetApply)binder, cur, arity);
            else
                unanalyzedBrowse();
            if(stopBrowse)
                return;
        }
    }
    
    private static boolean callsOnlyOnce(Name name, int arity) {
        if(name == Names.Prelude_build)
            return arity == 1;
        else
            return false;
    }
    
    protected void browseApply(LetApply apply, ValRef functionRef, int arity) {
        ValRef applyFunctionRef = apply.getFunction(); 
        if(applyFunctionRef == functionRef) {
            if(apply.getParameters().length == arity)
                browseBetweenRec(apply);
            else
                unanalyzedBrowse();
        }
        else {
            Val applyFunction = applyFunctionRef.getBinding();
            if(!(applyFunction instanceof SCLConstant)) {
                unanalyzedBrowse();
                return;
            }
            Name name = ((SCLConstant)applyFunction).getName();
            if(callsOnlyOnce(name, arity))
                browseBetweenRec(apply);
            else
                unanalyzedBrowse();
        }
    }
    
    protected void unanalyzedBrowse() {
    }

    protected void visitStatement(SSAStatement statement) {        
    }
    
    protected void handleLoop(SSABlock block, SSAStatement recursiveStatement) {
        for(SSAStatement cur = recursiveStatement; cur != null; cur = cur.getNext()) {
            visitStatement(cur);
            if(stopBrowse)
                return;
        }
    }
    
    public boolean doesAlwaysReach() {
        for(SSABlock block : visited)
            for(SSABlock successor : block.getExit().getSuccessors())
                if(!visited.contains(successor))
                    return false;
        return true;
    }
    
}