001    /*
002     $Id: CompileStack.java 4352 2006-12-13 15:58:48Z blackdrag $
003    
004     Copyright 2003 (C) James Strachan and Bob Mcwhirter. All Rights Reserved.
005    
006     Redistribution and use of this software and associated documentation
007     ("Software"), with or without modification, are permitted provided
008     that the following conditions are met:
009    
010     1. Redistributions of source code must retain copyright
011        statements and notices.  Redistributions must also contain a
012        copy of this document.
013    
014     2. Redistributions in binary form must reproduce the
015        above copyright notice, this list of conditions and the
016        following disclaimer in the documentation and/or other
017        materials provided with the distribution.
018    
019     3. The name "groovy" must not be used to endorse or promote
020        products derived from this Software without prior written
021        permission of The Codehaus.  For written permission,
022        please contact info@codehaus.org.
023    
024     4. Products derived from this Software may not be called "groovy"
025        nor may "groovy" appear in their names without prior written
026        permission of The Codehaus. "groovy" is a registered
027        trademark of The Codehaus.
028    
029     5. Due credit should be given to The Codehaus -
030        http://groovy.codehaus.org/
031    
032     THIS SOFTWARE IS PROVIDED BY THE CODEHAUS AND CONTRIBUTORS
033     ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
034     NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
035     FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
036     THE CODEHAUS OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
037     INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
038     (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
039     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
040     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
041     STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
042     ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
043     OF THE POSSIBILITY OF SUCH DAMAGE.
044    
045     */
046    
047    package org.codehaus.groovy.classgen;
048    
049    import java.util.ArrayList;
050    import java.util.Collections;
051    import java.util.HashMap;
052    import java.util.Iterator;
053    import java.util.LinkedList;
054    import java.util.List;
055    import java.util.ListIterator;
056    
057    import org.codehaus.groovy.GroovyBugError;
058    import org.codehaus.groovy.ast.ClassHelper;
059    import org.codehaus.groovy.ast.ClassNode;
060    import org.codehaus.groovy.ast.Parameter;
061    import org.codehaus.groovy.ast.VariableScope;
062    import org.objectweb.asm.Label;
063    import org.objectweb.asm.MethodVisitor;
064    import org.objectweb.asm.Opcodes;
065    
066    /**
067     * This class is a helper for AsmClassGenerator. It manages
068     * different aspects of the code of a code block like 
069     * handling labels, defining variables, and scopes. 
070     * After a MethodNode is visited clear should be called, for 
071     * initialization the method init should be used.
072     * <p> 
073     * Some Notes:
074     * <ul>
075     * <li> every push method will require a later pop call
076     * <li> method parameters may define a category 2 variable, so
077     *      don't ignore the type stored in the variable object
078     * <li> the index of the variable may not be as assumed when
079     *      the variable is a parameter of a method because the 
080     *      parameter may be used in a closure, so don't ignore
081     *      the stored variable index
082     * <li> the names of temporary variables can be ignored. The names
083     *      are only used for debugging and do not conflict with each 
084     *      other or normal variables. For accessing the index of the
085     *      variable must be used.
086     * </ul>
087     * 
088     * 
089     * @see org.codehaus.groovy.classgen.AsmClassGenerator
090     * @author Jochen Theodorou
091     */
092    public class CompileStack implements Opcodes {
093        /**
094         * @TODO remove optimization of this.foo -> this.@foo
095         * 
096         */
097        
098        // state flag
099        private boolean clear=true;
100        // current scope
101        private VariableScope scope;
102        // current label for continue
103        private Label continueLabel;
104        // current label for break
105        private Label breakLabel;
106        // available variables on stack
107        private HashMap stackVariables = new HashMap();
108        // index of the last variable on stack
109        private int currentVariableIndex = 1;
110        // index for the next variable on stack
111        private int nextVariableIndex = 1;
112        // currently temporary variables in use
113        private LinkedList temporaryVariables = new LinkedList();
114        // overall used variables for a method/constructor
115        private LinkedList usedVariables = new LinkedList();
116        // map containing named labels of parenting blocks
117        private HashMap superBlockNamedLabels = new HashMap();
118        // map containing named labels of current block
119        private HashMap currentBlockNamedLabels = new HashMap();
120        // list containing runnables representing a finally block
121        // such a block is created by synchronized or finally and
122        // must be called for break/continue/return
123        private LinkedList finallyBlocks = new LinkedList();
124        // a list of blocks already visiting. 
125        private List visitedBlocks = new LinkedList();
126        
127        private Label thisStartLabel, thisEndLabel;
128    
129        // current class index
130        private int currentClassIndex , currentMetaClassIndex;
131        
132        private MethodVisitor mv;
133        private BytecodeHelper helper;
134        
135        // helper to handle different stack based variables    
136        private LinkedList stateStack = new LinkedList();
137        
138        // defines the first variable index useable after
139        // all parameters of a method 
140        private int localVariableOffset;
141        // this is used to store the goals for a "break foo" call
142        // in a loop where foo is a label.
143            private HashMap namedLoopBreakLabel = new HashMap();
144            //this is used to store the goals for a "continue foo" call
145        // in a loop where foo is a label.
146            private HashMap namedLoopContinueLabel = new HashMap();
147        private String className;
148            
149        private class StateStackElement {
150            VariableScope _scope;
151            Label _continueLabel;
152            Label _breakLabel;
153            Label _finallyLabel;
154            int _lastVariableIndex;
155            int _nextVariableIndex;
156            HashMap _stackVariables;
157            LinkedList _temporaryVariables = new LinkedList();
158            LinkedList _usedVariables = new LinkedList();
159            HashMap _superBlockNamedLabels;
160            HashMap _currentBlockNamedLabels;
161            LinkedList _finallyBlocks;
162            
163            StateStackElement() {
164                _scope = CompileStack.this.scope;
165                _continueLabel = CompileStack.this.continueLabel;
166                _breakLabel = CompileStack.this.breakLabel;
167                _lastVariableIndex = CompileStack.this.currentVariableIndex;
168                _stackVariables = CompileStack.this.stackVariables;
169                _temporaryVariables = CompileStack.this.temporaryVariables;
170                _nextVariableIndex = nextVariableIndex;
171                _superBlockNamedLabels = superBlockNamedLabels;
172                _currentBlockNamedLabels = currentBlockNamedLabels;
173                _finallyBlocks = finallyBlocks;
174            }
175        }
176        
177        private void pushState() {
178            stateStack.add(new StateStackElement());
179            stackVariables = new HashMap(stackVariables);
180            finallyBlocks = new LinkedList(finallyBlocks);
181        }
182        
183        private void popState() {
184            if (stateStack.size()==0) {
185                 throw new GroovyBugError("Tried to do a pop on the compile stack without push.");
186            }
187            StateStackElement element = (StateStackElement) stateStack.removeLast();
188            scope = element._scope;
189            continueLabel = element._continueLabel;
190            breakLabel = element._breakLabel;
191            currentVariableIndex = element._lastVariableIndex;
192            stackVariables = element._stackVariables;
193            nextVariableIndex = element._nextVariableIndex;
194            finallyBlocks = element._finallyBlocks;
195        }
196        
197        public Label getContinueLabel() {
198            return continueLabel;
199        }
200    
201        public Label getBreakLabel() {
202            return breakLabel;
203        }
204    
205        public void removeVar(int tempIndex) {
206            for (Iterator iter = temporaryVariables.iterator(); iter.hasNext();) {
207                Variable element = (Variable) iter.next();
208                if (element.getIndex()==tempIndex) {
209                    iter.remove();
210                    return;
211                }
212            }
213            throw new GroovyBugError("CompileStack#removeVar: tried to remove a temporary variable with a non existent index");
214        }
215    
216        private void setEndLabels(){
217            Label endLabel = new Label();
218            mv.visitLabel(endLabel);
219            for (Iterator iter = stackVariables.values().iterator(); iter.hasNext();) {
220                Variable var = (Variable) iter.next();
221                var.setEndLabel(endLabel);
222            }
223            thisEndLabel = endLabel;
224        }
225        
226        public void pop() {
227            setEndLabels();
228            popState();
229        }
230    
231        public VariableScope getScope() {
232            return scope;
233        }
234    
235        /**
236         * creates a temporary variable. 
237         * 
238         * @param var defines type and name
239         * @param store defines if the toplevel argument of the stack should be stored
240         * @return the index used for this temporary variable
241         */
242        public int defineTemporaryVariable(org.codehaus.groovy.ast.Variable var, boolean store) {
243            return defineTemporaryVariable(var.getName(), var.getType(),store);
244        }
245    
246        public Variable getVariable(String variableName ) {
247            return getVariable(variableName,true);
248        }
249        
250        public Variable getVariable(String variableName, boolean mustExist) {
251            if (variableName.equals("this")) return Variable.THIS_VARIABLE;
252            if (variableName.equals("super")) return Variable.SUPER_VARIABLE;
253            Variable v = (Variable) stackVariables.get(variableName);
254            if (v==null && mustExist)  throw new GroovyBugError("tried to get a variable with the name "+variableName+" as stack variable, but a variable with this name was not created");
255            return v;
256        }
257    
258        /**
259         * creates a temporary variable. 
260         * 
261         * @param name defines type and name
262         * @param store defines if the toplevel argument of the stack should be stored
263         * @return the index used for this temporary variable
264         */
265        public int defineTemporaryVariable(String name,boolean store) {
266            return defineTemporaryVariable(name, ClassHelper.DYNAMIC_TYPE,store);
267        }
268    
269        /**
270         * creates a temporary variable. 
271         * 
272         * @param name defines the name
273         * @param node defines the node
274         * @param store defines if the toplevel argument of the stack should be stored 
275         * @return the index used for this temporary variable
276         */
277        public int defineTemporaryVariable(String name, ClassNode node, boolean store) {
278            Variable answer = defineVar(name,node,false);
279            temporaryVariables.add(answer);
280            usedVariables.removeLast();
281            
282            if (store) mv.visitVarInsn(ASTORE, currentVariableIndex);
283            
284            return answer.getIndex();
285        }
286        
287        private void resetVariableIndex(boolean isStatic) {
288            if (!isStatic) {
289                currentVariableIndex=1;
290                nextVariableIndex=1;
291            } else {
292                currentVariableIndex=0;
293                nextVariableIndex=0;
294            }
295        }
296      
297        /**
298         * Clears the state of the class. This method should be called 
299         * after a MethodNode is visited. Note that a call to init will
300         * fail if clear is not called before
301         */
302        public void clear() {
303            if (stateStack.size()>1) {
304                int size = stateStack.size()-1;
305                throw new GroovyBugError("the compile stack contains "+size+" more push instruction"+(size==1?"":"s")+" than pops.");
306            }
307            clear = true;
308            // br experiment with local var table so debuggers can retrieve variable names
309            if (true) {//AsmClassGenerator.CREATE_DEBUG_INFO) {
310                if (thisEndLabel==null) setEndLabels();
311                
312                if (!scope.isInStaticContext()) {
313                    // write "this"
314                    mv.visitLocalVariable("this", className, null, thisStartLabel, thisEndLabel, 0);
315                }
316               
317                for (Iterator iterator = usedVariables.iterator(); iterator.hasNext();) {
318                    Variable v = (Variable) iterator.next();
319                    String type = BytecodeHelper.getTypeDescription(v.getType());
320                    Label start = v.getStartLabel();
321                    Label end = v.getEndLabel();
322                    mv.visitLocalVariable(v.getName(), type, null, start, end, v.getIndex());
323                }
324            }
325            pop();
326            stackVariables.clear();
327            usedVariables.clear();
328            scope = null;
329            mv=null;
330            resetVariableIndex(false);
331            superBlockNamedLabels.clear();
332            currentBlockNamedLabels.clear();
333            namedLoopBreakLabel.clear();
334            namedLoopContinueLabel.clear();
335            continueLabel=null;
336            breakLabel=null;
337            helper = null;
338            thisStartLabel=null;
339            thisEndLabel=null;
340        }
341        
342        /**
343         * initializes this class for a MethodNode. This method will
344         * automatically define varibales for the method parameters
345         * and will create references if needed. the created variables
346         * can be get by getVariable
347         * 
348         */
349        protected void init(VariableScope el, Parameter[] parameters, MethodVisitor mv, ClassNode cn) {
350            if (!clear) throw new GroovyBugError("CompileStack#init called without calling clear before");
351            clear=false;
352            pushVariableScope(el);
353            this.mv = mv;
354            this.helper = new BytecodeHelper(mv);
355            defineMethodVariables(parameters,el.isInStaticContext());
356            this.className = BytecodeHelper.getTypeDescription(cn);
357            currentClassIndex = -1; currentMetaClassIndex = -1;
358        }
359    
360        /**
361         * Causes the statestack to add an element and sets
362         * the given scope as new current variable scope. Creates 
363         * a element for the state stack so pop has to be called later
364         */
365        protected void pushVariableScope(VariableScope el) {
366            pushState();
367            scope = el;
368            superBlockNamedLabels = new HashMap(superBlockNamedLabels);
369            superBlockNamedLabels.putAll(currentBlockNamedLabels);
370            currentBlockNamedLabels = new HashMap();
371        }
372        
373        /**
374         * Should be called when decending into a loop that defines
375         * also a scope. Calls pushVariableScope and prepares labels 
376         * for a loop structure. Creates a element for the state stack
377         * so pop has to be called later 
378         */
379        protected void pushLoop(VariableScope el, String labelName) {
380            pushVariableScope(el);
381            initLoopLabels(labelName);
382        }
383    
384        private void initLoopLabels(String labelName) {
385            continueLabel = new Label();
386            breakLabel = new Label();
387            if (labelName!=null) {
388                    namedLoopBreakLabel.put(labelName,breakLabel);
389                    namedLoopContinueLabel.put(labelName,continueLabel);
390            }
391        }
392        
393        /**
394         * Should be called when decending into a loop that does 
395         * not define a scope. Creates a element for the state stack
396         * so pop has to be called later
397         */
398        protected void pushLoop(String labelName) {
399            pushState();
400            initLoopLabels(labelName);
401        }
402        
403        /**
404         * Used for <code>break foo</code> inside a loop to end the
405         * execution of the marked loop. This method will return the
406         * break label of the loop if there is one found for the name.
407         * If not, the current break label is returned.
408         */
409        protected Label getNamedBreakLabel(String name) {
410            Label label = getBreakLabel();
411            Label endLabel = null;
412            if (name!=null) endLabel = (Label) namedLoopBreakLabel.get(name);
413            if (endLabel!=null) label = endLabel;
414            return label;
415        }
416        
417        /**
418         * Used for <code>continue foo</code> inside a loop to continue
419         * the execution of the marked loop. This method will return 
420         * the break label of the loop if there is one found for the 
421         * name. If not, getLabel is used.
422         */
423        protected Label getNamedContinueLabel(String name) {
424            Label label = getLabel(name);
425            Label endLabel = null;
426            if (name!=null) endLabel = (Label) namedLoopContinueLabel.get(name);
427            if (endLabel!=null) label = endLabel;
428            return label;
429        }    
430        
431        /**
432         * Creates a new break label and a element for the state stack
433         * so pop has to be called later
434         */
435        protected Label pushSwitch(){
436            pushState();
437            breakLabel = new Label();
438            return breakLabel;
439        }
440        
441        /**
442         * because a boolean Expression may not be evaluated completly
443         * it is important to keep the registers clean
444         */
445        protected void pushBooleanExpression(){
446            pushState();
447        }
448        
449        private Variable defineVar(String name, ClassNode type, boolean methodParameterUsedInClosure) {
450            makeNextVariableID(type);
451            int index = currentVariableIndex;
452            if (methodParameterUsedInClosure) {
453                index = localVariableOffset++;
454            }
455            Variable answer = new Variable(index, type, name);
456            usedVariables.add(answer);
457            answer.setHolder(methodParameterUsedInClosure);
458            return answer;
459        }
460        
461        private void makeLocalVariablesOffset(Parameter[] paras,boolean isInStaticContext) {
462            resetVariableIndex(isInStaticContext);
463            
464            for (int i = 0; i < paras.length; i++) {
465                makeNextVariableID(paras[i].getType());
466            }
467            localVariableOffset = nextVariableIndex;
468            
469            resetVariableIndex(isInStaticContext);
470        }
471        
472        private void defineMethodVariables(Parameter[] paras,boolean isInStaticContext) {
473            Label startLabel  = new Label();
474            thisStartLabel = startLabel;
475            mv.visitLabel(startLabel);
476            
477            makeLocalVariablesOffset(paras,isInStaticContext);      
478            
479            boolean hasHolder = false;
480            for (int i = 0; i < paras.length; i++) {
481                String name = paras[i].getName();
482                Variable answer;
483                if (paras[i].isClosureSharedVariable()) {
484                    answer = defineVar(name, ClassHelper.getWrapper(paras[i].getType()), true);
485                    ClassNode type = paras[i].getType();
486                    helper.load(type,currentVariableIndex);
487                    helper.box(type);
488                    createReference(answer);
489                    hasHolder = true;
490                } else {
491                    answer = defineVar(name,paras[i].getType(),false);
492                }
493                answer.setStartLabel(startLabel);
494                stackVariables.put(name, answer);
495            }
496            
497            if (hasHolder) {
498                nextVariableIndex = localVariableOffset;
499            }
500        }
501    
502        private void createReference(Variable reference) {
503            mv.visitTypeInsn(NEW, "groovy/lang/Reference");
504            mv.visitInsn(DUP_X1);
505            mv.visitInsn(SWAP);
506            mv.visitMethodInsn(INVOKESPECIAL, "groovy/lang/Reference", "<init>", "(Ljava/lang/Object;)V");
507            mv.visitVarInsn(ASTORE, reference.getIndex());
508        }
509        
510        /**
511         * Defines a new Variable using an AST variable.
512         * @param initFromStack if true the last element of the 
513         *                      stack will be used to initilize
514         *                      the new variable. If false null
515         *                      will be used.
516         */
517        public Variable defineVariable(org.codehaus.groovy.ast.Variable v, boolean initFromStack) {
518            String name = v.getName();
519            Variable answer = defineVar(name,v.getType(),false);
520            if (v.isClosureSharedVariable()) answer.setHolder(true);
521            stackVariables.put(name, answer);
522            
523            Label startLabel  = new Label();
524            answer.setStartLabel(startLabel);
525            if (answer.isHolder())  {
526                if (!initFromStack) mv.visitInsn(ACONST_NULL);
527                createReference(answer);
528            } else {
529                if (!initFromStack) mv.visitInsn(ACONST_NULL);
530                mv.visitVarInsn(ASTORE, currentVariableIndex);            
531            } 
532            mv.visitLabel(startLabel);
533            return answer;
534        }
535    
536        /**
537         * Returns true if a varibale is already defined
538         */
539        public boolean containsVariable(String name) {
540            return stackVariables.containsKey(name);
541        }
542        
543        /**
544         * Calculates the index of the next free register stores ir
545         * and sets the current variable index to the old value
546         */
547        private void makeNextVariableID(ClassNode type) {
548            currentVariableIndex = nextVariableIndex;
549            if (type==ClassHelper.long_TYPE || type==ClassHelper.double_TYPE) {
550                nextVariableIndex++;
551            }
552            nextVariableIndex++;
553        }
554        
555        /**
556         * Returns the label for the given name 
557         */
558        public Label getLabel(String name) {
559            if (name==null) return null;
560            Label l = (Label) superBlockNamedLabels.get(name);
561            if (l==null) l = createLocalLabel(name);
562            return l;
563        }
564        
565        /**
566         * creates a new named label
567         */
568        public Label createLocalLabel(String name) {
569            Label l = (Label) currentBlockNamedLabels.get(name);
570            if (l==null) {
571                l = new Label();
572                currentBlockNamedLabels.put(name,l);
573            }
574            return l;
575        }
576        
577        public int getCurrentClassIndex(){
578            return currentClassIndex;
579        }
580        
581        public void setCurrentClassIndex(int index){
582            currentClassIndex=index;
583        }
584        
585        public int getCurrentMetaClassIndex(){
586            return currentMetaClassIndex;
587        }
588        
589        public void setCurrentMetaClassIndex(int index){
590            currentMetaClassIndex=index;
591        }
592    
593        public void applyFinallyBlocks(Label label, boolean isBreakLabel) {
594            // first find the state defining the label. That is the state
595            // directly after the state not knowing this label. If no state
596            // in the list knows that label, then the defining state is the
597            // current state.
598            StateStackElement result = null;
599            for (ListIterator iter = stateStack.listIterator(stateStack.size()); iter.hasPrevious();) {
600                StateStackElement element = (StateStackElement) iter.previous();
601                if (!element._currentBlockNamedLabels.values().contains(label)) {
602                    if (isBreakLabel && element._breakLabel != label) {
603                        result = element;
604                        break;
605                    }
606                    if (!isBreakLabel && element._continueLabel != label) {
607                        result = element;
608                        break;
609                    }
610                }
611            }
612            
613            List blocksToRemove;
614            if (result==null) {
615                // all Blocks do know the label, so use all finally blocks
616                blocksToRemove = Collections.EMPTY_LIST;
617            } else {
618                blocksToRemove = result._finallyBlocks;
619            }
620            
621            ArrayList blocks = new ArrayList(finallyBlocks);
622            blocks.removeAll(blocksToRemove);
623            applyFinallyBlocks(blocks);
624        }
625    
626        private void applyFinallyBlocks(List blocks) {
627            for (Iterator iter = blocks.iterator(); iter.hasNext();) {
628                Runnable block = (Runnable) iter.next();
629                if (visitedBlocks.contains(block)) continue;
630                visitedBlocks.add(block);
631                block.run();
632            }     
633        }
634        
635        public void applyFinallyBlocks() {
636            applyFinallyBlocks(finallyBlocks); 
637        }
638    
639        public boolean hasFinallyBlocks() {
640            return !finallyBlocks.isEmpty();
641        }
642    
643        public void pushFinallyBlock(Runnable block) {
644            finallyBlocks.addFirst(block);
645            pushState();
646        }
647    
648        public void popFinallyBlock() {
649            popState();
650            finallyBlocks.removeFirst();
651        }
652    }