StructuredBlock


1   /* StructuredBlock Copyright (C) 1998-2002 Jochen Hoenicke.
2    *
3    * This program is free software; you can redistribute it and/or modify
4    * it under the terms of the GNU Lesser General Public License as published by
5    * the Free Software Foundation; either version 2, or (at your option)
6    * any later version.
7    *
8    * This program is distributed in the hope that it will be useful,
9    * but WITHOUT ANY WARRANTY; without even the implied warranty of
10   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   * GNU General Public License for more details.
12   *
13   * You should have received a copy of the GNU Lesser General Public License
14   * along with this program; see the file COPYING.LESSER.  If not, write to
15   * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
16   *
17   * $Id: StructuredBlock.java.in,v 4.3.2.2 2002/05/28 17:34:09 hoenicke Exp $
18   */
19  
20  package jode.flow;
21  import jode.AssertError;
22  import jode.GlobalOptions;
23  import jode.decompiler.TabbedPrintWriter;
24  import jode.decompiler.LocalInfo;
25  import jode.decompiler.Declarable;
26  import jode.decompiler.ClassAnalyzer;
27  import jode.util.SimpleSet;
28  
29  import java.util.Collections  ;
30  import java.util.Iterator  ;
31  import java.util.Set  ;
32  
33  /**
34   * A structured block is the building block of the source programm.
35   * For every program construct like if, while, try, or blocks there is
36   * a corresponding structured block.
37   *
38   * Some of these Block are only intermediate representation, that get
39   * converted to another block later.
40   *
41   * Every block has to handle the local variables that it contains.
42   * This is done by the in/out vectors and the local variable structure
43   * themself.  Every local variable used in this structured block is
44   * either in or out.
45   *
46   * There are following types of structured blocks: 
47   * <ul>
48   * <li>if-then-(else)-block  (IfThenElseBlock)
49   * <li>(do)-while/for-block  (LoopBlock)
50   * <li>switch-block          (SwitchBlock)
51   * <li>try-catch-block       (CatchBlock)
52   * <li>try-finally-block     (FinallyBlock)
53   * <li>synchronized-block    (SynchronizedBlock)
54   * <li>one-instruction       (InstructionBlock)
55   * <li>empty-block           (EmptyBlock)
56   * <li>multi-blocks-block    (SequentialBlock)
57   * </ul>
58   */
59  
60  public abstract class StructuredBlock {
61      /* Invariants:
62       * in.intersection(out) = empty
63       * outer != null => flowBlock = outer.flowBlock
64       * outer == null => flowBlock.block = this
65       * jump  == null => outer != null
66       * either getNextBlock() != null 
67       *     or getNextFlowBlock() != null or outer == null
68       * either outer.getNextBlock(this) != null 
69       *     or outer.getNextFlowBlock(this) != null
70       */
71  
72      /**
73       * The Set containing all Declarables that are used in this
74       * block. 
75       */
76      Set used;
77  
78      /**
79       * The Set containing all Declarables we must declare.
80       * The analyzation is done in makeDeclaration
81       */
82      Set declare;
83      Set done;
84  
85      /**
86       * The surrounding structured block.  If this is the outermost
87       * block in a flow block, outer is null.  */
88      StructuredBlock outer;
89  
90  //     /**
91  //      * The surrounding non sequential block.  This is the same as if
92  //      * you would repeatedly get outer until you reach a non sequential
93  //      * block.  This is field is only valid, if the outer block is a
94  //      * sequential block.
95  //      */
96  //     StructuredBlock realOuter;
97  
98      /**
99       * The flow block in which this structured block lies.  */
100     FlowBlock flowBlock;
101     
102     /** 
103      * The jump that follows on this block, or null if there is no
104      * jump, but the control flows normal (only allowed if
105      * getNextBlock != null).  
106      */
107     Jump jump;
108 
109     /**
110      * Returns the block where the control will normally flow to, when
111      * this block is finished.
112      */
113     public StructuredBlock getNextBlock() {
114         if (jump != null)
115             return null;
116         if (outer != null)
117             return outer.getNextBlock(this);
118         return null;
119     }
120 
121     public void setJump(Jump jump) {
122         this.jump = jump;
123         jump.prev = this;
124     }
125 
126     /**
127      * Returns the flow block where the control will normally flow to,
128      * when this block is finished.
129      * @return null, if the control flows into a non empty structured
130      * block or if this is the outermost block.
131      */
132     public FlowBlock getNextFlowBlock() {
133         if (jump != null)
134             return jump.destination;
135         if (outer != null)
136             return outer.getNextFlowBlock(this);
137         return null;
138     }
139 
140     /**
141      * Returns the block where the control will normally flow to, when
142      * the given sub block is finished. (This is overwritten by
143      * SequentialBlock and SwitchBlock).  If this isn't called with a
144      * direct sub block, the behaviour is undefined, so take care.
145      * @return null, if the control flows to another FlowBlock.  */
146     public StructuredBlock getNextBlock(StructuredBlock subBlock) {
147         return getNextBlock();
148     }
149 
150     public FlowBlock getNextFlowBlock(StructuredBlock subBlock) {
151         return getNextFlowBlock();
152     }
153 
154     /**
155      * Tells if this block is empty and only changes control flow.
156      */
157     public boolean isEmpty() {
158         return false;
159     }
160 
161     /**
162      * Tells if the sub block is the single exit point of the current block.
163      * @param subBlock the sub block.
164      * @return true, if the sub block is the single exit point of the
165      * current block.  
166      */
167     public boolean isSingleExit(StructuredBlock subBlock) {
168     return false;
169     }
170 
171     /**
172      * Replaces the given sub block with a new block.
173      * @param oldBlock the old sub block.
174      * @param newBlock the new sub block.
175      * @return false, if oldBlock wasn't a direct sub block.
176      */
177     public boolean replaceSubBlock(StructuredBlock oldBlock, 
178                                    StructuredBlock newBlock) {
179         return false;
180     }
181 
182     /**
183      * Returns all sub block of this structured block.
184      */
185     public StructuredBlock[] getSubBlocks() {
186         return new StructuredBlock[0];
187     }
188 
189     /**
190      * Returns if this block contains the given block.
191      * @param child the block which should be contained by this block.
192      * @return false, if child is null, or is not contained in this block.
193      */
194     public boolean contains(StructuredBlock child) {
195         while (child != this && child != null)
196             child = child.outer;
197         return (child == this);
198     }
199 
200     /** 
201      * Removes the jump.  This does not update the successors vector
202      * of the flow block, you have to do it yourself.  */
203     public final void removeJump() {
204         if (jump != null) {
205             jump.prev = null;
206             jump = null;
207         }
208     }
209 
210     /**
211      * This will move the definitions of sb and childs to this block,
212      * but only descend to sub and not further.  It is assumed that
213      * sub will become a sub block of this block, but may not yet.  
214      *
215      * @param sb The structured block that should be replaced.  
216      * @param sub The uppermost sub block of structured block, that
217      * will be moved to this block (may be this).  
218      */
219     void moveDefinitions(StructuredBlock from, StructuredBlock sub) {
220     }
221 
222     /**
223      * This function replaces sb with this block.  It copies outer and
224      * from sb, and updates the outer block, so it knows that sb was
225      * replaced.  You have to replace sb.outer or mustn't use sb
226      * anymore.  <p>
227      * It will also move the definitions of sb and childs to this block,
228      * but only descend to sub and not further.  It is assumed that
229      * sub will become a sub block of this block.
230      * @param sb The structured block that should be replaced.  
231      * @param sub  The uppermost sub block of structured block, 
232      *      that will be moved to this block (may be this).
233      */
234     public void replace(StructuredBlock sb) {
235         outer = sb.outer;
236         setFlowBlock(sb.flowBlock);
237         if (outer != null) {
238             outer.replaceSubBlock(sb, this);
239         } else {
240             flowBlock.block = this;
241         }
242     }
243 
244     /**
245      * This function swaps the jump with another block.
246      * @param block The block whose jump is swapped.
247      */
248     public void swapJump(StructuredBlock block) {
249         Jump tmp = block.jump;
250         block.jump = jump;
251         jump = tmp;
252         
253         jump.prev = this;
254         block.jump.prev = block;
255     }
256 
257     /**
258      * This function moves the jump to this block.  
259      * The jump field of the previous owner is cleared afterwards.  
260      * If the given jump is null, nothing bad happens.
261      * @param jump The jump that should be moved, may be null.
262      */
263     public void moveJump(Jump jump) {
264         if (this.jump != null)
265             throw new AssertError("overriding with moveJump()");
266         this.jump = jump;
267         if (jump != null) {
268             jump.prev.jump = null;
269             jump.prev = this;
270         }
271     }
272 
273     /**
274      * This function copies the jump to this block.  
275      * If the given jump is null, nothing bad happens.
276      * @param jump The jump that should be moved, may be null.
277      */
278     public void copyJump(Jump jump) {
279         if (this.jump != null)
280             throw new AssertError("overriding with moveJump()");
281         if (jump != null) {
282         this.jump = new Jump(jump);
283         this.jump.prev = this;
284         }
285     }
286 
287     /**
288      * Appends a block to this block.
289      * @return the new combined block.
290      */
291     public StructuredBlock appendBlock(StructuredBlock block) {
292         if (block instanceof EmptyBlock) {
293             moveJump(block.jump);
294             return this;
295         } else {
296             SequentialBlock sequBlock = new SequentialBlock();
297             sequBlock.replace(this);
298             sequBlock.setFirst(this);
299             sequBlock.setSecond(block);
300             return sequBlock;
301         }
302     }
303 
304     /**
305      * Prepends a block to this block.
306      * @return the new combined block.
307      */
308     public StructuredBlock prependBlock(StructuredBlock block) {
309     SequentialBlock sequBlock = new SequentialBlock();
310     sequBlock.replace(this);
311     sequBlock.setFirst(block);
312     sequBlock.setSecond(this);
313     return sequBlock;
314     }
315 
316     /**
317      * Removes this block, or replaces it with an EmptyBlock.
318      */
319     public final void removeBlock() {
320 
321         if (outer instanceof SequentialBlock) {
322             if (outer.getSubBlocks()[1] == this) {
323                 if (jump != null)
324                     outer.getSubBlocks()[0].moveJump(jump);
325                 outer.getSubBlocks()[0].replace(outer);
326             } else
327                 outer.getSubBlocks()[1].replace(outer);
328             return;
329         }
330 
331         EmptyBlock eb = new EmptyBlock();
332         eb.moveJump(jump);
333         eb.replace(this);
334     }
335 
336     /**
337      * Determines if there is a path, that flows through the end
338      * of this block.  If there is such a path, it is forbidden to
339      * change the control flow in after this block and this method
340      * returns false.
341      * @return true, if the jump may be safely changed.
342      */
343     public boolean flowMayBeChanged() {
344     return jump != null || jumpMayBeChanged();
345     }
346 
347     public boolean jumpMayBeChanged() {
348     return false;
349     }
350 
351     public Set getDeclarables() {
352     return Collections.EMPTY_SET;
353     }
354 
355     /**
356      * Propagate the used set.  Initially the used block contains the
357      * local that are used in some expression directly in this block.
358      * This will extend the set, so that a variable is used if it is
359      * used in at least two sub blocks.
360      *
361      * @return all locals that are used in this block or in some sub
362      * block (this is <i>not</i> the used set).  */
363     public Set propagateUsage() {
364     used = new SimpleSet();
365     used.addAll(getDeclarables());
366         StructuredBlock[] subs = getSubBlocks();
367         Set allUse = new SimpleSet();
368     allUse.addAll(used);
369         for (int i=0; i<subs.length; i++) {
370             Set childUse = subs[i].propagateUsage();
371             /* All variables used in more than one sub blocks, are
372              * used in this block, too.  
373              */
374         Set intersection = new SimpleSet();
375         intersection.addAll(childUse);
376         intersection.retainAll(allUse);
377         used.addAll(intersection);
378         allUse.addAll(childUse);
379         }
380         return allUse;
381     }
382 
383     /** 
384      * This is called after the analysis is completely done.  It
385      * will remove all PUSH/stack_i expressions, (if the bytecode
386      * is correct). <p>
387      * The default implementation merges the stack after each sub block.
388      * This may not be, what you want. <p>
389      *
390      * @param initialStack the stackmap at begin of the block
391      * @return the stack after the block has executed.
392      * @throw RuntimeException if something did get wrong.
393      */
394     public VariableStack mapStackToLocal(VariableStack stack) {
395     StructuredBlock[] subBlocks = getSubBlocks();
396     VariableStack after;
397     if (subBlocks.length == 0)
398         after = stack;
399     else {
400         after = null;
401         for (int i=0; i< subBlocks.length; i++) {
402         after = VariableStack.merge
403             (after, subBlocks[i].mapStackToLocal(stack));
404         }
405     }
406     if (jump != null) {
407         /* assert(after != null) */
408         jump.stackMap = after;
409         return null;
410     }
411     return after;
412     }
413 
414     /** 
415      * This is called after mapStackToLocal to do the stack to local
416      * transformation.
417      */
418     public void removePush() {
419     StructuredBlock[] subBlocks = getSubBlocks();
420     for (int i=0; i< subBlocks.length; i++)
421         subBlocks[i].removePush();
422     }
423 
424     /** 
425      * This method should remove local variables that are only written
426      * and read one time directly after another.  <br>
427      *
428      * This is especially important for stack locals, that are created
429      * when there are unusual swap or dup instructions, but also makes
430      * inlined functions more pretty (but not that close to the
431      * bytecode).  
432      */
433     public void removeOnetimeLocals() {
434     StructuredBlock[] subBlocks = getSubBlocks();
435     for (int i=0; i< subBlocks.length; i++)
436         subBlocks[i].removeOnetimeLocals();
437     }
438 
439     /**
440      * Make the declarations, i.e. initialize the declare variable
441      * to correct values.  This will declare every variable that
442      * is marked as used, but not done.<br>
443      *
444      * This will now also combine locals, that use the same slot, have
445      * compatible types and are declared in the same block. <br>
446      *
447      * @param done The set of the already declare variables.
448      */
449     public void makeDeclaration(Set done) {
450     this.done = new SimpleSet();
451     this.done.addAll(done);
452 
453     declare = new SimpleSet();
454     Iterator   iter = used.iterator();
455     next_used:
456     while (iter.hasNext()) {
457         Declarable declarable = (Declarable) iter.next();
458 
459         // Check if this is already declared.
460         if (done.contains(declarable))
461         continue next_used;
462 
463         if (declarable instanceof LocalInfo) {
464         LocalInfo local = (LocalInfo) declarable;
465 
466         /* First generate the names for the locals, since this may
467          * also change their types, if they are in the local
468          * variable table.
469          */
470         String   localName = local.guessName();
471         
472         // Merge with all locals in this block, that use the same 
473         // slot and have compatible types and names.
474         Iterator   doneIter = done.iterator();
475         while (doneIter.hasNext()) {
476             Declarable previous = (Declarable) doneIter.next();
477             if (!(previous instanceof LocalInfo))
478             continue;
479             LocalInfo prevLocal = (LocalInfo) previous;
480             /* We  only merge locals living in the same
481              * method and having the same slot.
482              *
483              * We don't want to merge variables, whose names
484              * are not generated by us and differ.  And we
485              * don't want to merge special locals that have a
486              * constant expression, e.g. this.
487              */
488             if (prevLocal.getMethodAnalyzer()
489             == local.getMethodAnalyzer()
490             && prevLocal.getSlot() == local.getSlot()
491             && prevLocal.getType().isOfType(local.getType())
492             && (prevLocal.isNameGenerated() 
493                 || local.isNameGenerated()
494                 || localName.equals(prevLocal.getName()))
495             && !prevLocal.isFinal() 
496             && !local.isFinal()
497             && prevLocal.getExpression() == null
498             && local.getExpression() == null) {
499             local.combineWith(prevLocal);
500             continue next_used;
501             }
502         }
503         }
504         
505         if (declarable.getName() != null) {
506         Iterator   doneIter = done.iterator();
507         while (doneIter.hasNext()) {
508             Declarable previous = (Declarable) doneIter.next();
509             if (declarable.getName().equals(previous.getName())) {
510             /* A name conflict happened. */
511             declarable.makeNameUnique();
512             break;
513             }
514         }
515         }
516         done.add(declarable);
517         declare.add(declarable);
518         if (declarable instanceof ClassAnalyzer)
519         ((ClassAnalyzer) declarable).makeDeclaration(done);
520     }
521         StructuredBlock[] subs = getSubBlocks();
522     for (int i=0; i<subs.length; i++)
523         subs[i].makeDeclaration(done);
524         /* remove the variables again, since we leave the scope.
525          */
526         done.removeAll(declare);
527     }
528 
529     public void checkConsistent() {
530         StructuredBlock[] subs = getSubBlocks();
531         for (int i=0; i<subs.length; i++) {
532             if (subs[i].outer != this ||
533                 subs[i].flowBlock != flowBlock) {
534                 throw new AssertError("Inconsistency");
535             }
536             subs[i].checkConsistent();
537         }
538         if (jump != null && jump.destination != null) {
539             Jump jumps = (Jump) flowBlock.getJumps(jump.destination);
540             for (; jumps != jump; jumps = jumps.next) {
541                 if (jumps == null)
542                     throw new AssertError("Inconsistency");
543             }
544         }
545     }
546 
547     /**
548      * Set the flow block of this block and all sub blocks.
549      * @param flowBlock the new flow block
550      */
551     public void setFlowBlock(FlowBlock flowBlock) {
552         if (this.flowBlock != flowBlock) {
553             this.flowBlock = flowBlock;
554             StructuredBlock[] subs = getSubBlocks();
555             for (int i=0; i<subs.length; i++) {
556                 if (subs[i] != null)
557                     subs[i].setFlowBlock(flowBlock);
558             }
559         }
560     }
561 
562     /**
563      * Tells if this block needs braces when used in a if or while block.
564      * @return true if this block should be sorrounded by braces.
565      */
566     public boolean needsBraces() {
567         return true;
568     }
569 
570     /**
571      * Fill all in variables into the given VariableSet.
572      * @param in The VariableSet, the in variables should be stored to.
573      */
574     public void fillInGenSet(Set in, Set gen) {
575         /* overwritten by InstructionContainer */
576     }
577 
578     /**
579      * Add all the successors of this block and all subblocks to the
580      * flow block.
581      * @param succs The vector, the successors should be stored to.
582      */
583     public void fillSuccessors() {
584         if (jump != null)
585             flowBlock.addSuccessor(jump);
586         StructuredBlock[] subs = getSubBlocks();
587         for (int i=0; i<subs.length; i++) {
588             subs[i].fillSuccessors();
589         }
590     }
591 
592     /**
593      * Print the source code for this structured block.  This handles
594      * everything that is unique for all structured blocks and calls
595      * dumpInstruction afterwards.
596      * @param writer The tabbed print writer, where we print to.
597      */
598     public void dumpSource(TabbedPrintWriter writer)
599         throws java.io.IOException  
600     {
601     if ((GlobalOptions.debuggingFlags
602          & GlobalOptions.DEBUG_LOCALS) != 0) {
603         if (declare != null)
604         writer.println("declaring: "+declare);
605         if (done != null)
606         writer.println("done: "+done);
607         writer.println("using: "+used);
608     }
609 
610     if (declare != null) {
611         Iterator   iter = declare.iterator();
612         while (iter.hasNext()) {
613         Declarable decl = (Declarable) iter.next();
614         decl.dumpDeclaration(writer);
615         writer.println(";");
616         }
617     }
618         dumpInstruction(writer);
619 
620         if (jump != null)
621             jump.dumpSource(writer);
622     }
623 
624     /**
625      * Print the instruction expressing this structured block.
626      * @param writer The tabbed print writer, where we print to.
627      */
628     public abstract void dumpInstruction(TabbedPrintWriter writer)
629         throws java.io.IOException  ;
630 
631     public String   toString() {
632         try {
633             java.io.StringWriter   strw = new java.io.StringWriter  ();
634             jode.decompiler.TabbedPrintWriter writer = 
635                 new jode.decompiler.TabbedPrintWriter(strw);
636             writer.println(super.toString());
637             writer.tab();
638             dumpSource(writer);
639             return strw.toString();
640         } catch (java.io.IOException   ex) {
641             return super.toString();
642         }
643     }
644 
645     public void simplify() {
646     StructuredBlock[] subs = getSubBlocks();
647     for (int i=0; i < subs.length; i++)
648         subs[i].simplify();
649     }
650 
651     /**
652      * Do simple transformation on the structuredBlock.
653      * @return true, if some transformation was done.
654      */
655     public boolean doTransformations() {
656         return false;
657     }
658 }
659 
660
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags