package org.jruby.ir;

   import java.util.ArrayList;

   import java.util.HashMap;

   import java.util.List;

   import java.util.Map;

   import java.util.Set;

   import java.util.SortedSet;

   import java.util.TreeSet;

  import org.jruby.RubyModule;

  import org.jruby.exceptions.Unrescuable;

  import org.jruby.ir.dataflow.DataFlowProblem;

  import org.jruby.ir.instructions.CallBase;

  import org.jruby.ir.instructions.CopyInstr;

  import org.jruby.ir.instructions.GetGlobalVariableInstr;

  import org.jruby.ir.instructions.Instr;

  import org.jruby.ir.instructions.PutGlobalVarInstr;

  import org.jruby.ir.instructions.ReceiveSelfInstr;

  import org.jruby.ir.instructions.ResultInstr;

  import org.jruby.ir.instructions.Specializeable;

  import org.jruby.ir.instructions.ThreadPollInstr;

  import org.jruby.ir.operands.CurrentScope;

  import org.jruby.ir.operands.GlobalVariable;

  import org.jruby.ir.operands.Label;

  import org.jruby.ir.operands.LocalVariable;

  import org.jruby.ir.operands.Operand;

  import org.jruby.ir.operands.ScopeModule;

  import org.jruby.ir.operands.Self;

  import org.jruby.ir.operands.TemporaryVariable;

  import org.jruby.ir.operands.Variable;

  import org.jruby.ir.operands.WrappedIRClosure;

  import org.jruby.ir.passes.CompilerPass;

  import org.jruby.ir.representations.BasicBlock;

  import org.jruby.ir.representations.CFG;

  import org.jruby.ir.representations.CFGLinearizer;

  import org.jruby.ir.transformations.inlining.CFGInliner;

  import org.jruby.parser.StaticScope;

  import org.jruby.util.log.Logger;

  import org.jruby.util.log.LoggerFactory;

  public abstract class IRScope {

      private static final Logger LOG = LoggerFactory.getLogger("IRScope");

      private static Integer globalScopeCount = 0;

    

      private int scopeId;

    

      private String name;

    

      private final String fileName;

    

      private final int lineNumber;

    

      private IRScope lexicalParent;

    

      private StaticScope staticScope;
    
    

      private RubyModule containerModule; 
    
    

      private List<Instr> instrList; 

    

     private CFG cfg;

    

     private List<IRClosure> nestedClosures;

    

     private Set<Variable> definedLocalVars;

    

     private Set<Variable> usedLocalVars;

    

     private boolean hasUnusedImplicitBlockArg;

    

     private TemporaryVariable currentModuleVar;

     private TemporaryVariable currentScopeVar;

    

     private Map<String, DataFlowProblem> dfProbs;

     private Instr[] linearizedInstrArray;

     private List<BasicBlock> linearizedBBList;

     protected int temporaryVariableIndex;

    

     private Map<String, Integer> nextVarIndex;

     // Index values to guarantee we don't assign same internal index twice

     private int nextClosureIndex;

     // List of all scopes this scope contains lexically.  This is not used

     // for execution, but is used during dry-runs for debugging.

     List<IRScope> lexicalChildren; 

     protected static class LocalVariableAllocator {

         public int nextSlot;

         public Map<String, LocalVariable> varMap;

         public LocalVariableAllocator() {

             varMap = new HashMap<String, LocalVariable>();

             nextSlot = 0;

         }

         public final LocalVariable getVariable(String name) {

             return varMap.get(name);

         }

         public final void putVariable(String name, LocalVariable var) {

             varMap.put(name, var);

             nextSlot++;

         }

     }

     LocalVariableAllocator localVars;

     LocalVariableAllocator evalScopeVars;

     /* *****************************************************************************************************

      * Does this execution scope (applicable only to methods) receive a block and use it in such a way that

      * all of the caller's local variables need to be materialized into a heap binding?

      * Ex: 

      *    def foo(&b)

      *      eval 'puts a', b

      *    end

      *  

      *    def bar

      *      a = 1

      *      foo {} # prints out '1'

      *    end

      *

      * Here, 'foo' can access all of bar's variables because it captures the caller's closure.

      *

      * There are 2 scenarios when this can happen (even this is conservative -- but, good enough for now)

      * 1. This method receives an explicit block argument (in this case, the block can be stored, passed around,

      *    eval'ed against, called, etc.).  

      *    CAVEAT: This is conservative ... it may not actually be stored & passed around, evaled, called, ...

      * 2. This method has a 'super' call (ZSuper AST node -- ZSuperInstr IR instruction)

      *    In this case, the parent (in the inheritance hierarchy) can access the block and store it, etc.  So, in reality,

      *    rather than assume that the parent will always do this, we can query the parent, if we can precisely identify

      *    the parent method (which in the face of Ruby's dynamic hierarchy, we cannot).  So, be pessimistic.

      *

      * This logic was extracted from an email thread on the JRuby mailing list -- Yehuda Katz & Charles Nutter

      * contributed this analysis above.

      * ********************************************************************************************************/

     private boolean canCaptureCallersBinding;

     /* ****************************************************************************

      * Does this scope define code, i.e. does it (or anybody in the downward call chain)

      * do class_eval, module_eval? In the absence of any other information, we default

      * to yes -- which basically leads to pessimistic but safe optimizations.  But, for

      * library and internal methods, this might be false.

      * **************************************************************************** */

     private boolean canModifyCode;

     /* ****************************************************************************

      * Does this scope require a binding to be materialized?

      * Yes if any of the following holds true:

      * - calls 'Proc.new'

      * - calls 'eval'

      * - calls 'call' (could be a call on a stored block which could be local!)

      * - calls 'send' and we cannot resolve the message (method name) that is being sent!

      * - calls methods that can access the caller's binding

      * - calls a method which we cannot resolve now!

      * - has a call whose closure requires a binding

      * **************************************************************************** */

     private boolean bindingHasEscaped;

    

     private boolean usesEval;

    

     private boolean usesBackrefOrLastline;

    

     private boolean usesZSuper;

    

     private boolean hasLoops;

    

     private int threadPollInstrsCount;

    

     private boolean hasExplicitCallProtocol;

    

     private boolean relinearizeCFG;

     private IRManager manager;

     // Used by cloning code

     protected IRScope(IRScope s, IRScope lexicalParent) {

         this.lexicalParent = lexicalParent;

         this.manager = s.manager;

         this.fileName = s.fileName;

         this.lineNumber = s.lineNumber;

         this.staticScope = s.staticScope;

         this.threadPollInstrsCount = s.threadPollInstrsCount;

         this.nextClosureIndex = s.nextClosureIndex;

         this.temporaryVariableIndex = s.temporaryVariableIndex;

         this.hasLoops = s.hasLoops;

         this.hasUnusedImplicitBlockArg = s.hasUnusedImplicitBlockArg;

         this.instrList = null;

         this.nestedClosures = new ArrayList<IRClosure>();

         this.dfProbs = new HashMap<String, DataFlowProblem>();

         this.nextVarIndex = new HashMap<String, Integer>(); // SSS FIXME: clone!

         this.cfg = null;

         this.linearizedInstrArray = null;

         this.linearizedBBList = null;

         this.canModifyCode = s.canModifyCode;

         this.canCaptureCallersBinding = s.canCaptureCallersBinding;

         this.bindingHasEscaped = s.bindingHasEscaped;

         this.usesEval = s.usesEval;

         this.usesBackrefOrLastline = s.usesBackrefOrLastline;

         this.usesZSuper = s.usesZSuper;

         this.hasExplicitCallProtocol = s.hasExplicitCallProtocol;

         this.localVars = new LocalVariableAllocator(); // SSS FIXME: clone!

         this.localVars.nextSlot = s.localVars.nextSlot;

         this.relinearizeCFG = false;

         setupLexicalContainment();

     }

     public IRScope(IRManager manager, IRScope lexicalParent, String name, 

             String fileName, int lineNumber, StaticScope staticScope) {

         this.manager = manager;

         this.lexicalParent = lexicalParent;        

         this.name = name;

         this.fileName = fileName;

         this.lineNumber = lineNumber;

         this.staticScope = staticScope;

         this.threadPollInstrsCount = 0;

         this.nextClosureIndex = 0;

         this.temporaryVariableIndex = -1;

         this.instrList = new ArrayList<Instr>();

         this.nestedClosures = new ArrayList<IRClosure>();

         this.dfProbs = new HashMap<String, DataFlowProblem>();

         this.nextVarIndex = new HashMap<String, Integer>();

         this.cfg = null;

         this.linearizedInstrArray = null;

         this.linearizedBBList = null;

         this.hasLoops = false;

         this.hasUnusedImplicitBlockArg = false;

         // These flags are true by default!

         this.canModifyCode = true;

         this.canCaptureCallersBinding = true;

         this.bindingHasEscaped = true;

         this.usesEval = true;

         this.usesBackrefOrLastline = true;

         this.usesZSuper = true;

         this.hasExplicitCallProtocol = false;

         this.localVars = new LocalVariableAllocator();

         synchronized(globalScopeCount) { this.scopeId = globalScopeCount++; }

         this.relinearizeCFG = false;

         setupLexicalContainment();

     }

     private final void setupLexicalContainment() {

         if (manager.isDryRun()) {

             lexicalChildren = new ArrayList<IRScope>();

             if (lexicalParent != null) lexicalParent.addChildScope(this);

         }        

     }

     @Override

     public int hashCode() {

         return scopeId;

     }

     protected void addChildScope(IRScope scope) {

         lexicalChildren.add(scope);

     }

     public List<IRScope> getLexicalScopes() {

         return lexicalChildren;

     }

     public void addClosure(IRClosure c) {

         nestedClosures.add(c);

     }

     public Instr getLastInstr() {

         return instrList.get(instrList.size() - 1);

     }

     public void addInstr(Instr i) {

         if (i instanceof ThreadPollInstr) threadPollInstrsCount++;

         instrList.add(i);

     }

     public LocalVariable getNewFlipStateVariable() {

         return getLocalVariable("%flip_" + allocateNextPrefixedName("%flip"), 0);

     }

     public void initFlipStateVariable(Variable v, Operand initState) {

         // Add it to the beginning

         instrList.add(0, new CopyInstr(v, initState));

     }

     public boolean isForLoopBody() {

         return false;

     }

     public Label getNewLabel(String prefix) {

         return new Label(prefix + "_" + allocateNextPrefixedName(prefix));

     }

     public Label getNewLabel() {

         return getNewLabel("LBL");

     }    

     public List<IRClosure> getClosures() {

         return nestedClosures;

     }

     public IRManager getManager() {

         return manager;

     }
    
    

     public IRScope getLexicalParent() {

         return lexicalParent;

     }

     public StaticScope getStaticScope() {

         return staticScope;

     }    

     public IRMethod getNearestMethod() {

         IRScope current = this;

         while (current != null && !(current instanceof IRMethod)) {

             current = current.getLexicalParent();

         }

         return (IRMethod) current;

     }

     public IRScope getNearestFlipVariableScope() {

         IRScope current = this;

         while (current != null && !current.isFlipScope()) {

             current = current.getLexicalParent();

         }

         return current;

     }

     public IRScope getNearestTopLocalVariableScope() {

         IRScope current = this;

         while (current != null && !current.isTopLocalVariableScope()) {

             current = current.getLexicalParent();

         }

         return current;

     }
    
    

     public IRScope getNearestModuleReferencingScope() {

         IRScope current = this;

         while (!(current instanceof IRModuleBody)) {

             // When eval'ing, we dont have a lexical view of what module we are nested in

             // because binding_eval, class_eval, module_eval, instance_eval can switch

             // around the lexical scope for evaluation to be something else.            

             if (current == null || current instanceof IREvalScript) return null;

             current = current.getLexicalParent();

         }

         return current;

     }

     public String getName() {

         return name;

     }

     public void setName(String name) { // This is for IRClosure ;(

         this.name = name;

     }

     public String getFileName() {

         return fileName;

     }

     public int getLineNumber() {

         return lineNumber;

     }

    

     public IRScope getTopLevelScope() {

         IRScope current = this;

         for (; current != null && !current.isScriptScope(); current = current.getLexicalParent()) {}

         return current;

     }

     public boolean isNestedInClosure(IRClosure closure) {

         for (IRScope s = this; s != null && !s.isTopLocalVariableScope(); s = s.getLexicalParent()) {

             if (s == closure) return true;

         }

         return false;

     }

     public void setHasLoopsFlag(boolean f) {

         hasLoops = true;

     }

     public boolean hasLoops() {

         return hasLoops;

     }

     public boolean hasExplicitCallProtocol() {

         return hasExplicitCallProtocol;

     }

     public void setExplicitCallProtocolFlag(boolean flag) {

         this.hasExplicitCallProtocol = flag;

     }

     public void setCodeModificationFlag(boolean f) { 

         canModifyCode = f;

     }

     public boolean modifiesCode() { 

         return canModifyCode;

     }

     public boolean bindingHasEscaped() {

         return bindingHasEscaped;

     }

     public boolean usesBackrefOrLastline() {

         return usesBackrefOrLastline;

     }

     public boolean usesEval() {

         return usesEval;

     }

     public boolean usesZSuper() {

         return usesZSuper;

     }

     public boolean canCaptureCallersBinding() {

         return canCaptureCallersBinding;

     }

     public CFG buildCFG() {

         cfg = new CFG(this);

         cfg.build(instrList);

         // Clear out instruction list after CFG has been built.

         this.instrList = null;  

         return cfg;

     }

     protected void setCFG(CFG cfg) {

        this.cfg = cfg;

     }

     public CFG getCFG() {

         return cfg;

     }

     private void setupLabelPCs(HashMap<Label, Integer> labelIPCMap) {

         for (BasicBlock b: linearizedBBList) {

             Label l = b.getLabel();

             l.setTargetPC(labelIPCMap.get(l));

         }

     }

     private Instr[] prepareInstructionsForInterpretation() {

         checkRelinearization();

         if (linearizedInstrArray != null) return linearizedInstrArray; // Already prepared

         try {

             buildLinearization(); // FIXME: compiler passes should have done this

             depends(linearization());

         } catch (RuntimeException e) {

             LOG.error("Error linearizing cfg: ", e);

             CFG c = cfg();

             LOG.error("\nGraph:\n" + c.toStringGraph());

             LOG.error("\nInstructions:\n" + c.toStringInstrs());

             throw e;

         }

         // Set up IPCs

         HashMap<Label, Integer> labelIPCMap = new HashMap<Label, Integer>();

         List<Instr> newInstrs = new ArrayList<Instr>();

         int ipc = 0;

         for (BasicBlock b: linearizedBBList) {

             labelIPCMap.put(b.getLabel(), ipc);

             List<Instr> bbInstrs = b.getInstrs();

             int bbInstrsLength = bbInstrs.size();

             for (int i = 0; i < bbInstrsLength; i++) {

                 Instr instr = bbInstrs.get(i);

                 if (instr instanceof Specializeable) {

                     instr = ((Specializeable) instr).specializeForInterpretation();

                     bbInstrs.set(i, instr);

                 }

                 if (!(instr instanceof ReceiveSelfInstr)) {

                     newInstrs.add(instr);

                     ipc++;

                 }

             }

         }

         // Set up label PCs

         setupLabelPCs(labelIPCMap);

         // Exit BB ipc

         cfg().getExitBB().getLabel().setTargetPC(ipc + 1);

         linearizedInstrArray = newInstrs.toArray(new Instr[newInstrs.size()]);

         return linearizedInstrArray;

     }

     private void runCompilerPasses() {

         // SSS FIXME: Why is this again?  Document this weirdness!

         // Forcibly clear out the shared eval-scope variable allocator each time this method executes

         initEvalScopeVariableAllocator(true); 

         // SSS FIXME: We should configure different optimization levels

         // and run different kinds of analysis depending on time budget.  Accordingly, we need to set

         // IR levels/states (basic, optimized, etc.) and the

         // ENEBO: If we use a MT optimization mechanism we cannot mutate CFG

         // while another thread is using it.  This may need to happen on a clone()

         // and we may need to update the method to return the new method.  Also,

         // if this scope is held in multiple locations how do we update all references?

         for (CompilerPass pass: getManager().getCompilerPasses(this)) {

             pass.run(this);

         }

     }

    

     public synchronized Instr[] prepareForInterpretation() {

         checkRelinearization();

         if (linearizedInstrArray != null) return linearizedInstrArray;

         // Build CFG and run compiler passes, if necessary

         if (getCFG() == null) runCompilerPasses();

         // Linearize CFG, etc.

         return prepareInstructionsForInterpretation();

     }

     /* SSS FIXME: Do we need to synchronize on this?  Cache this info in a scope field? */
    

     public Tuple<Instr[], Map<Integer,Label[]>> prepareForCompilation() {

         // Build CFG and run compiler passes, if necessary

         if (getCFG() == null) runCompilerPasses();

         try {

             buildLinearization(); // FIXME: compiler passes should have done this

             depends(linearization());

         } catch (RuntimeException e) {

             LOG.error("Error linearizing cfg: ", e);

             CFG c = cfg();

             LOG.error("\nGraph:\n" + c.toStringGraph());

             LOG.error("\nInstructions:\n" + c.toStringInstrs());

             throw e;

         }

         // Set up IPCs

         // FIXME: Would be nice to collapse duplicate labels; for now, using Label[]

         HashMap<Integer, Label[]> ipcLabelMap = new HashMap<Integer, Label[]>();

         HashMap<Label, Integer>   labelIPCMap = new HashMap<Label, Integer>();

         List<Instr> newInstrs = new ArrayList<Instr>();

         int ipc = 0;

         for (BasicBlock b : linearizedBBList) {

             Label l = b.getLabel();

             labelIPCMap.put(l, ipc);

             ipcLabelMap.put(ipc, catLabels(ipcLabelMap.get(ipc), l));

             for (Instr i : b.getInstrs()) {

                 if (!(i instanceof ReceiveSelfInstr)) {

                     newInstrs.add(i);

                     ipc++;

                 }

             }

         }

         // Set up label PCs

         setupLabelPCs(labelIPCMap);

         return new Tuple<Instr[], Map<Integer,Label[]>>(newInstrs.toArray(new Instr[newInstrs.size()]), ipcLabelMap);

     }

     private List<Object[]> buildJVMExceptionTable() {

         List<Object[]> etEntries = new ArrayList<Object[]>();

         for (BasicBlock b: linearizedBBList) {

             // We need handlers for:

             // - RaiseException (Ruby exceptions -- handled by rescues),

             // - Unrescuable    (JRuby exceptions -- handled by ensures),

             // - Throwable      (JRuby/Java exceptions -- handled by rescues)

             // in that order since Throwable < Unrescuable and Throwable < RaiseException

             BasicBlock rBB = cfg().getRescuerBBFor(b);

             BasicBlock eBB = cfg().getEnsurerBBFor(b);

             if ((eBB != null) && (rBB == eBB || rBB == null)) {

                 // 1. same rescue and ensure handler ==> just spit out one entry with a Throwable class

                 // 2. only ensure handler            ==> just spit out one entry with a Throwable class

                 //

                 // The rescue handler knows whether to unwrap or not.  But for now, the rescue handler

                 // has to process its recv_exception instruction as

                 //    e = (e instanceof RaiseException) ? unwrap(e) : e;

                 int start = b.getLabel().getTargetPC();

                 int end   = start + b.instrCount();

                 etEntries.add(new Object[] {start, end, eBB.getLabel().getTargetPC(), Throwable.class});

             } else if (rBB != null) {

                 int start = b.getLabel().getTargetPC();