View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   https://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.bcel.verifier.structurals;
20  
21  import java.util.ArrayList;
22  import java.util.BitSet;
23  import java.util.HashMap;
24  import java.util.HashSet;
25  import java.util.List;
26  import java.util.Map;
27  import java.util.Set;
28  
29  import org.apache.bcel.generic.ASTORE;
30  import org.apache.bcel.generic.ATHROW;
31  import org.apache.bcel.generic.BranchInstruction;
32  import org.apache.bcel.generic.CodeExceptionGen;
33  import org.apache.bcel.generic.GotoInstruction;
34  import org.apache.bcel.generic.IndexedInstruction;
35  import org.apache.bcel.generic.Instruction;
36  import org.apache.bcel.generic.InstructionHandle;
37  import org.apache.bcel.generic.JsrInstruction;
38  import org.apache.bcel.generic.LocalVariableInstruction;
39  import org.apache.bcel.generic.MethodGen;
40  import org.apache.bcel.generic.RET;
41  import org.apache.bcel.generic.ReturnInstruction;
42  import org.apache.bcel.generic.Select;
43  import org.apache.bcel.verifier.exc.AssertionViolatedException;
44  import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
45  
46  /**
47   * Instances of this class contain information about the subroutines found in a code array of a method. This
48   * implementation considers the top-level (the instructions reachable without a JSR or JSR_W starting off from the first
49   * instruction in a code array of a method) being a special subroutine; see getTopLevel() for that. Please note that the
50   * definition of subroutines in the Java Virtual Machine Specification, Second Edition is somewhat incomplete.
51   * Therefore, JustIce uses an own, more rigid notion. Basically, a subroutine is a piece of code that starts at the
52   * target of a JSR of JSR_W instruction and ends at a corresponding RET instruction. Note also that the control flow of
53   * a subroutine may be complex and non-linear; and that subroutines may be nested. JustIce also mandates subroutines not
54   * to be protected by exception handling code (for the sake of control flow predictability). To understand JustIce's
55   * notion of subroutines, please read
56   *
57   * TODO: refer to the paper.
58   *
59   * @see #getTopLevel()
60   */
61  public class Subroutines {
62      // Node coloring constants
63      private enum ColourConstants {
64          WHITE, GRAY, BLACK
65      }
66  
67      /**
68       * This inner class implements the Subroutine interface.
69       */
70      private final class SubroutineImpl implements Subroutine {
71  
72          /**
73           * UNSET, a symbol for an uninitialized localVariable field. This is used for the "top-level" Subroutine; for example no
74           * subroutine.
75           */
76          private static final int UNSET = -1;
77  
78          private final SubroutineImpl[] EMPTY_ARRAY = {};
79  
80          /**
81           * The Local Variable slot where the first instruction of this subroutine (an ASTORE) stores the JsrInstruction's
82           * ReturnAddress in and the RET of this subroutine operates on.
83           */
84          private int localVariable = UNSET;
85  
86          /** The instructions that belong to this subroutine. */
87          private final Set<InstructionHandle> instructions = new HashSet<>(); // Elements: InstructionHandle
88  
89          /**
90           * The JSR or JSR_W instructions that define this subroutine by targeting it.
91           */
92          private final Set<InstructionHandle> theJSRs = new HashSet<>();
93  
94          /**
95           * The RET instruction that leaves this subroutine.
96           */
97          private InstructionHandle theRET;
98  
99          /**
100          * Constructs a new instance.
101          */
102         SubroutineImpl() {
103             // empty
104         }
105 
106         /**
107          * Adds a new JSR or JSR_W that has this subroutine as its target.
108          */
109         public void addEnteringJsrInstruction(final InstructionHandle jsrInst) {
110             if (jsrInst == null || !(jsrInst.getInstruction() instanceof JsrInstruction)) {
111                 throw new AssertionViolatedException("Expecting JsrInstruction InstructionHandle.");
112             }
113             if (localVariable == UNSET) {
114                 throw new AssertionViolatedException("Set the localVariable first.");
115             }
116             // Something is wrong when an ASTORE is targeted that does not operate on the same local variable than the rest of the
117             // JsrInstruction-targets and the RET.
118             // (We don't know out leader here so we cannot check if we're really targeted!)
119             if (localVariable != ((ASTORE) ((JsrInstruction) jsrInst.getInstruction()).getTarget().getInstruction()).getIndex()) {
120                 throw new AssertionViolatedException("Setting a wrong JsrInstruction.");
121             }
122             theJSRs.add(jsrInst);
123         }
124 
125         /*
126          * Adds an instruction to this subroutine. All instructions must have been added before invoking setLeavingRET().
127          *
128          * @see #setLeavingRET
129          */
130         void addInstruction(final InstructionHandle ih) {
131             if (theRET != null) {
132                 throw new AssertionViolatedException("All instructions must have been added before invoking setLeavingRET().");
133             }
134             instructions.add(ih);
135         }
136 
137         /*
138          * Refer to the Subroutine interface for documentation.
139          */
140         @Override
141         public boolean contains(final InstructionHandle inst) {
142             return instructions.contains(inst);
143         }
144 
145         /*
146          * Satisfies Subroutine.getAccessedLocalIndices().
147          */
148         @Override
149         public int[] getAccessedLocalsIndices() {
150             // TODO: Implement caching.
151             final Set<Integer> acc = new HashSet<>();
152             if (theRET == null && this != getTopLevel()) {
153                 throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals.");
154             }
155             {
156                 for (final InstructionHandle ih : instructions) {
157                     // RET is not a LocalVariableInstruction in the current version of BCEL.
158                     if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET) {
159                         final int idx = ((IndexedInstruction) ih.getInstruction()).getIndex();
160                         acc.add(Integer.valueOf(idx));
161                         // LONG? DOUBLE?.
162                         try {
163                             // LocalVariableInstruction instances are typed without the need to look into
164                             // the constant pool.
165                             if (ih.getInstruction() instanceof LocalVariableInstruction) {
166                                 final int s = ((LocalVariableInstruction) ih.getInstruction()).getType(null).getSize();
167                                 if (s == 2) {
168                                     acc.add(Integer.valueOf(idx + 1));
169                                 }
170                             }
171                         } catch (final RuntimeException re) {
172                             throw new AssertionViolatedException("BCEL did not like NULL as a ConstantPoolGen object.", re);
173                         }
174                     }
175                 }
176             }
177 
178             {
179                 final int[] ret = new int[acc.size()];
180                 int j = -1;
181                 for (final Integer accessedLocal : acc) {
182                     j++;
183                     ret[j] = accessedLocal.intValue();
184                 }
185                 return ret;
186             }
187         }
188 
189         /*
190          * Refer to the Subroutine interface for documentation.
191          */
192         @Override
193         public InstructionHandle[] getEnteringJsrInstructions() {
194             if (this == getTopLevel()) {
195                 throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine.");
196             }
197             return theJSRs.toArray(InstructionHandle.EMPTY_ARRAY);
198         }
199 
200         /*
201          * Refer to the Subroutine interface for documentation.
202          */
203         @Override
204         public InstructionHandle[] getInstructions() {
205             return instructions.toArray(InstructionHandle.EMPTY_ARRAY);
206         }
207 
208         /*
209          * Refer to the Subroutine interface for documentation.
210          */
211         @Override
212         public InstructionHandle getLeavingRET() {
213             if (this == getTopLevel()) {
214                 throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine.");
215             }
216             return theRET;
217         }
218 
219         /* Satisfies Subroutine.getRecursivelyAccessedLocalsIndices(). */
220         @Override
221         public int[] getRecursivelyAccessedLocalsIndices() {
222             final Set<Integer> s = new HashSet<>();
223             final int[] lvs = getAccessedLocalsIndices();
224             for (final int lv : lvs) {
225                 s.add(Integer.valueOf(lv));
226             }
227             getRecursivelyAccessedLocalsIndicesHelper(s, subSubs(), new HashSet<>());
228             final int[] ret = new int[s.size()];
229             int j = -1;
230             for (final Integer index : s) {
231                 j++;
232                 ret[j] = index.intValue();
233             }
234             return ret;
235         }
236 
237         /**
238          * Gets the recursively accessed local variable indexes and adds them to the supplied set.
239          * <p>
240          * A recursive helper method for getRecursivelyAccessedLocalsIndices(). Every subroutine is visited at most
241          * once: since the computed set is a plain union, re-exploring an already visited subroutine cannot add
242          * anything, but doing so once per call path made this helper exponential in the depth of the JSR call graph
243          * (and made it recurse forever on a cyclic one).
244          * </p>
245          *
246          * @see #getRecursivelyAccessedLocalsIndices()
247          */
248         private void getRecursivelyAccessedLocalsIndicesHelper(final Set<Integer> set, final Subroutine[] subs, final Set<Subroutine> visited) {
249             for (final Subroutine sub : subs) {
250                 if (!visited.add(sub)) {
251                     continue;
252                 }
253                 final int[] lvs = sub.getAccessedLocalsIndices();
254                 for (final int lv : lvs) {
255                     set.add(Integer.valueOf(lv));
256                 }
257                 if (sub.subSubs().length != 0) {
258                     getRecursivelyAccessedLocalsIndicesHelper(set, sub.subSubs(), visited);
259                 }
260             }
261         }
262 
263         /**
264          * Sets the leaving RET instruction. Must be invoked after all instructions are added. Must not be invoked for top-level
265          * 'subroutine'.
266          */
267         void setLeavingRET() {
268             if (localVariable == UNSET) {
269                 throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first.");
270             }
271             InstructionHandle ret = null;
272             for (final InstructionHandle actual : instructions) {
273                 if (actual.getInstruction() instanceof RET) {
274                     if (ret != null) {
275                         throw new StructuralCodeConstraintException("Subroutine with more than one RET detected: '" + ret + "' and '" + actual + "'.");
276                     }
277                     ret = actual;
278                 }
279             }
280             if (ret == null) {
281                 throw new StructuralCodeConstraintException("Subroutine without a RET detected.");
282             }
283             if (((RET) ret.getInstruction()).getIndex() != localVariable) {
284                 throw new StructuralCodeConstraintException(
285                     "Subroutine uses '" + ret + "' which does not match the correct local variable '" + localVariable + "'.");
286             }
287             theRET = ret;
288         }
289 
290         /*
291          * Sets the local variable slot the ASTORE that is targeted by the JsrInstructions of this subroutine operates on. This
292          * subroutine's RET operates on that same local variable slot, of course.
293          */
294         void setLocalVariable(final int i) {
295             if (localVariable != UNSET) {
296                 throw new AssertionViolatedException("localVariable set twice.");
297             }
298             localVariable = i;
299         }
300 
301         /*
302          * Satisfies Subroutine.subSubs().
303          */
304         @Override
305         public Subroutine[] subSubs() {
306             final Set<Subroutine> h = new HashSet<>();
307 
308             for (final InstructionHandle ih : instructions) {
309                 final Instruction inst = ih.getInstruction();
310                 if (inst instanceof JsrInstruction) {
311                     final InstructionHandle targ = ((JsrInstruction) inst).getTarget();
312                     h.add(getSubroutine(targ));
313                 }
314             }
315             return h.toArray(EMPTY_ARRAY);
316         }
317 
318         /**
319          * Returns a String representation of this object, merely for debugging purposes. (Internal) Warning: Verbosity on a
320          * problematic subroutine may cause stack overflow errors due to recursive subSubs() calls. Don't use this, then.
321          */
322         @Override
323         public String toString() {
324             final StringBuilder ret = new StringBuilder();
325             ret.append("Subroutine: Local variable is '").append(localVariable);
326             ret.append("', JSRs are '").append(theJSRs);
327             ret.append("', RET is '").append(theRET);
328             ret.append("', Instructions: '").append(instructions).append("'.");
329 
330             ret.append(" Accessed local variable slots: '");
331             int[] alv = getAccessedLocalsIndices();
332             for (final int element : alv) {
333                 ret.append(element);
334                 ret.append(" ");
335             }
336             ret.append("'.");
337 
338             ret.append(" Recursively (via subsub...routines) accessed local variable slots: '");
339             alv = getRecursivelyAccessedLocalsIndices();
340             for (final int element : alv) {
341                 ret.append(element);
342                 ret.append(" ");
343             }
344             ret.append("'.");
345 
346             return ret.toString();
347         }
348 
349     } // end Inner Class SubrouteImpl
350 
351     /**
352      * Gets the successors of a given InstructionHandle <strong>in the same subroutine</strong>. That
353      * means, a RET does not have any successors as defined here. A JsrInstruction has its physical successor as its
354      * successor (opposed to its target) as defined here.
355      */
356     private static InstructionHandle[] getSuccessors(final InstructionHandle instruction) {
357         final InstructionHandle[] single = new InstructionHandle[1];
358 
359         final Instruction inst = instruction.getInstruction();
360 
361         // Terminates method normally.
362         // Terminates method abnormally, because JustIce mandates
363         // subroutines not to be protected by exception handlers.
364         if (inst instanceof RET || inst instanceof ReturnInstruction || inst instanceof ATHROW) {
365             return InstructionHandle.EMPTY_ARRAY;
366         }
367 
368         // See method comment.
369         if (inst instanceof JsrInstruction) {
370             single[0] = instruction.getNext();
371             return single;
372         }
373 
374         if (inst instanceof GotoInstruction) {
375             single[0] = ((GotoInstruction) inst).getTarget();
376             return single;
377         }
378 
379         if (inst instanceof BranchInstruction) {
380             if (inst instanceof Select) {
381                 // BCEL's getTargets() returns only the non-default targets,
382                 // thanks to Eli Tilevich for reporting.
383                 final InstructionHandle[] matchTargets = ((Select) inst).getTargets();
384                 final InstructionHandle[] ret = new InstructionHandle[matchTargets.length + 1];
385                 ret[0] = ((Select) inst).getTarget();
386                 System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
387                 return ret;
388             }
389             final InstructionHandle[] pair = new InstructionHandle[2];
390             pair[0] = instruction.getNext();
391             pair[1] = ((BranchInstruction) inst).getTarget();
392             return pair;
393         }
394 
395         // default case: Fall through.
396         single[0] = instruction.getNext();
397         return single;
398     }
399 
400     private static StructuralCodeConstraintException recursiveCallException(final Subroutine sub2) {
401         // Don't use toString() here because of possibly infinite recursive subSubs() calls then.
402         final SubroutineImpl si = (SubroutineImpl) sub2;
403         return new StructuralCodeConstraintException("Subroutine with local variable '" + si.localVariable + "', JSRs '" + si.theJSRs + "', RET '"
404             + si.theRET + "' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call?"
405             + " JustIce's clean definition of a subroutine forbids both.");
406     }
407 
408     /**
409      * The map containing the subroutines found. Key: InstructionHandle of the leader of the subroutine. Elements:
410      * SubroutineImpl objects.
411      */
412     private final Map<InstructionHandle, Subroutine> subroutines = new HashMap<>();
413 
414     /**
415      * This is referring to a special subroutine, namely the top level. This is not really a subroutine but we use it to
416      * distinguish between top level instructions and unreachable instructions.
417      */
418     // CHECKSTYLE:OFF
419     public final Subroutine TOPLEVEL; // TODO can this be made private?
420     // CHECKSTYLE:ON
421 
422     /**
423      * Constructs a new instance.
424      *
425      * @param mg A MethodGen object representing method to create the Subroutine objects of. Assumes that JustIce strict
426      *        checks are needed.
427      */
428     public Subroutines(final MethodGen mg) {
429         this(mg, true);
430     }
431 
432     /**
433      * Constructs a new instance.
434      *
435      * @param mg A MethodGen object representing method to create the Subroutine objects of.
436      * @param enableJustIceCheck whether to enable additional JustIce checks.
437      * @since 6.0
438      */
439     public Subroutines(final MethodGen mg, final boolean enableJustIceCheck) {
440         final InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
441         final CodeExceptionGen[] handlers = mg.getExceptionHandlers();
442 
443         // Define our "Toplevel" fake subroutine.
444         TOPLEVEL = new SubroutineImpl();
445 
446         // Calculate "real" subroutines.
447         final Set<InstructionHandle> subLeaders = new HashSet<>(); // Elements: InstructionHandle
448         for (final InstructionHandle element : all) {
449             final Instruction inst = element.getInstruction();
450             if (inst instanceof JsrInstruction) {
451                 subLeaders.add(((JsrInstruction) inst).getTarget());
452             }
453         }
454 
455         // Build up the database.
456         for (final InstructionHandle astore : subLeaders) {
457             final SubroutineImpl sr = new SubroutineImpl();
458             sr.setLocalVariable(((ASTORE) astore.getInstruction()).getIndex());
459             subroutines.put(astore, sr);
460         }
461 
462         // Fake it a bit. We want a virtual "TopLevel" subroutine.
463         subroutines.put(all[0], TOPLEVEL);
464         subLeaders.add(all[0]);
465 
466         // Tell the subroutines about their JsrInstructions.
467         // Note that there cannot be a JSR targeting the top-level
468         // since "Jsr 0" is disallowed in Pass 3a.
469         // Instructions shared by a subroutine and the toplevel are
470         // disallowed and checked below, after the BFS.
471         for (final InstructionHandle element : all) {
472             final Instruction inst = element.getInstruction();
473             if (inst instanceof JsrInstruction) {
474                 final InstructionHandle leader = ((JsrInstruction) inst).getTarget();
475                 ((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(element);
476             }
477         }
478 
479         // Now do a BFS from every subroutine leader to find all the
480         // instructions that belong to a subroutine.
481         // we don't want to assign an instruction to two or more Subroutine objects.
482         final Set<InstructionHandle> instructionsAssigned = new HashSet<>();
483 
484         // Graph coloring. Key: InstructionHandle, Value: ColourConstants enum.
485         final Map<InstructionHandle, ColourConstants> colors = new HashMap<>();
486 
487         final List<InstructionHandle> qList = new ArrayList<>();
488         for (final InstructionHandle actual : subLeaders) {
489             // Do some BFS with "actual" as the root of the graph.
490             // Init colors: an instruction absent from the map is WHITE. Explicitly coloring every
491             // instruction WHITE on every round would make this initialization quadratic in the
492             // method size.
493             colors.clear();
494             colors.put(actual, ColourConstants.GRAY);
495             // Init Queue
496 
497             qList.clear();
498             qList.add(actual); // add(Obj) adds to the end, remove(0) removes from the start.
499 
500             /*
501              * BFS ALGORITHM MODIFICATION: Start out with multiple "root" nodes, as exception handlers are starting points of
502              * top-level code, too. [why top-level? TODO: Refer to the special JustIce notion of subroutines.]
503              */
504             if (actual == all[0]) {
505                 for (final CodeExceptionGen handler : handlers) {
506                     colors.put(handler.getHandlerPC(), ColourConstants.GRAY);
507                     qList.add(handler.getHandlerPC());
508                 }
509             }
510             /* CONTINUE NORMAL BFS ALGORITHM */
511 
512             // Loop until Queue is empty
513             while (!qList.isEmpty()) {
514                 final InstructionHandle u = qList.remove(0);
515                 final InstructionHandle[] successors = getSuccessors(u);
516                 for (final InstructionHandle successor : successors) {
517                     if (successor != null && colors.get(successor) == null) { // absent from the map means WHITE
518                         colors.put(successor, ColourConstants.GRAY);
519                         qList.add(successor);
520                     }
521                 }
522                 colors.put(u, ColourConstants.BLACK);
523             }
524             // BFS ended above. Only instructions visited by this BFS round are in the color map,
525             // so this scan is proportional to the round, not to the whole method.
526             for (final Map.Entry<InstructionHandle, ColourConstants> entry : colors.entrySet()) {
527                 if (entry.getValue() == ColourConstants.BLACK) {
528                     final InstructionHandle element = entry.getKey();
529                     ((SubroutineImpl) (actual == all[0] ? getTopLevel() : getSubroutine(actual))).addInstruction(element);
530                     if (instructionsAssigned.contains(element)) {
531                         throw new StructuralCodeConstraintException(
532                             "Instruction '" + element + "' is part of more than one subroutine (or of the top level and a subroutine).");
533                     }
534                     instructionsAssigned.add(element);
535                 }
536             }
537             if (actual != all[0]) { // If we don't deal with the top-level 'subroutine'
538                 ((SubroutineImpl) getSubroutine(actual)).setLeavingRET();
539             }
540         }
541 
542         if (enableJustIceCheck && handlers.length > 0) {
543             // Now make sure no instruction of a Subroutine is protected by exception handling code
544             // as is mandated by JustIces notion of subroutines.
545             // The handler coverage of every instruction is computed once, with a difference array
546             // over instruction list indices. Walking every handler's protected range and, per
547             // protected instruction, every subroutine would let a crafted method (thousands of
548             // handlers over large ranges) keep this constructor busy nearly forever.
549             final Map<InstructionHandle, Integer> instructionIndexes = new HashMap<>();
550             for (int i = 0; i < all.length; i++) {
551                 instructionIndexes.put(all[i], Integer.valueOf(i));
552             }
553             final int[] coverageDelta = new int[all.length + 1];
554             for (final CodeExceptionGen handler : handlers) {
555                 // Note the inclusive/inclusive notation of "generic API" exception handlers!
556                 final Integer startIndex = instructionIndexes.get(handler.getStartPC());
557                 final Integer endIndex = instructionIndexes.get(handler.getEndPC());
558                 if (startIndex == null || endIndex == null || startIndex.intValue() > endIndex.intValue()) {
559                     throw new StructuralCodeConstraintException("Exception handler '" + handler + "' does not protect a valid instruction range.");
560                 }
561                 coverageDelta[startIndex.intValue()]++;
562                 coverageDelta[endIndex.intValue() + 1]--;
563             }
564             final boolean[] isProtected = new boolean[all.length];
565             int covered = 0;
566             for (int i = 0; i < all.length; i++) {
567                 covered += coverageDelta[i];
568                 isProtected[i] = covered > 0;
569             }
570             for (final Subroutine sub : subroutines.values()) {
571                 if (sub == subroutines.get(all[0])) {
572                     continue;
573                 }
574                 for (final InstructionHandle protectedIh : sub.getInstructions()) {
575                     final Integer index = instructionIndexes.get(protectedIh);
576                     if (index != null && isProtected[index.intValue()]) {
577                         // Only the error message needs the offending handler; this scan runs at most once.
578                         for (final CodeExceptionGen handler : handlers) {
579                             final int startIndex = instructionIndexes.get(handler.getStartPC()).intValue();
580                             final int endIndex = instructionIndexes.get(handler.getEndPC()).intValue();
581                             if (startIndex <= index.intValue() && index.intValue() <= endIndex) {
582                                 throw new StructuralCodeConstraintException("Subroutine instruction '" + protectedIh
583                                     + "' is protected by an exception handler, '" + handler
584                                     + "'. This is forbidden by the JustIce verifier due to its clear definition of subroutines.");
585                             }
586                         }
587                     }
588                 }
589             }
590         }
591 
592         // Now make sure no subroutine is calling a subroutine
593         // that uses the same local variable for the RET as themselves
594         // (recursively).
595         // This includes that subroutines may not call themselves
596         // recursively, even not through intermediate calls to other
597         // subroutines.
598         noRecursiveCalls(getTopLevel());
599 
600     }
601 
602     /**
603      * Gets the Subroutine object associated with the given leader (that is, the first instruction of the subroutine).
604      * You must not use this to get the top-level instructions modeled as a Subroutine object.
605      *
606      * @param leader The leader instruction handle.
607      * @return The Subroutine object.
608      * @see #getTopLevel()
609      */
610     public Subroutine getSubroutine(final InstructionHandle leader) {
611         final Subroutine ret = subroutines.get(leader);
612 
613         if (ret == null) {
614             throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine.");
615         }
616 
617         if (ret == TOPLEVEL) {
618             throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel().");
619         }
620 
621         return ret;
622     }
623 
624     /**
625      * Gets the Subroutine object representing the top-level code.
626      *
627      * For easy handling, the piece of code that is <strong>not</strong> a subroutine, the top-level, is also modeled as a Subroutine
628      * object. It is a special Subroutine object where <B>you must not invoke getEnteringJsrInstructions() or
629      * getLeavingRET()</B>.
630      *
631      * @return The top-level Subroutine.
632      * @see Subroutine#getEnteringJsrInstructions()
633      * @see Subroutine#getLeavingRET()
634      */
635     public Subroutine getTopLevel() {
636         return TOPLEVEL;
637     }
638 
639     /**
640      * This utility method makes sure that no subroutine is calling a subroutine that uses the same local
641      * variable for the RET as themselves (recursively). This includes that subroutines may not call themselves recursively,
642      * even not through intermediate calls to other subroutines.
643      *
644      * Every subroutine is fully validated exactly once, memoizing the RET local variable indices used anywhere in its
645      * call subtree. The former implementation re-explored a subroutine once per call path, which is exponential in the
646      * number of subroutines for a layered JSR call graph.
647      *
648      * @throws StructuralCodeConstraintException Thrown if the above constraint is not satisfied.
649      */
650     private void noRecursiveCalls(final Subroutine sub) {
651         noRecursiveCalls(sub, new BitSet(), new HashMap<>(), new HashMap<>());
652     }
653 
654     /**
655      * The recursive helper for {@link #noRecursiveCalls(Subroutine)}.
656      *
657      * @param sub the subroutine whose callees are validated.
658      * @param pathLocals compact ids (see {@code localIds}) of the RET local variables used by the subroutines on the current call path.
659      * @param validated maps every fully validated subroutine to the compact ids of the RET local variables used by it and its entire call subtree.
660      * @param localIds maps a RET local variable index to a compact id so the bit sets stay small.
661      * @return the compact ids of the RET local variables used by {@code sub}'s callees and their call subtrees.
662      * @throws StructuralCodeConstraintException Thrown if a subroutine calls a subroutine using the same RET local variable.
663      */
664     private BitSet noRecursiveCalls(final Subroutine sub, final BitSet pathLocals, final Map<Subroutine, BitSet> validated,
665         final Map<Integer, Integer> localIds) {
666         final BitSet subtreeLocals = new BitSet();
667 
668         for (final Subroutine sub2 : sub.subSubs()) {
669             final Integer index = Integer.valueOf(((RET) sub2.getLeavingRET().getInstruction()).getIndex());
670             final int localId = localIds.computeIfAbsent(index, k -> Integer.valueOf(localIds.size())).intValue();
671 
672             BitSet childLocals = validated.get(sub2);
673             if (childLocals == null) {
674                 if (pathLocals.get(localId)) {
675                     // sub2 uses a RET local variable also used by a subroutine on the current call path;
676                     // this also covers (possibly indirect) recursive calls.
677                     throw recursiveCallException(sub2);
678                 }
679                 pathLocals.set(localId);
680                 childLocals = noRecursiveCalls(sub2, pathLocals, validated, localIds);
681                 pathLocals.clear(localId);
682                 childLocals.set(localId);
683                 validated.put(sub2, childLocals);
684             } else if (childLocals.intersects(pathLocals)) {
685                 // A subroutine in sub2's (already validated) call subtree uses a RET local variable also
686                 // used by a subroutine on the current call path.
687                 throw recursiveCallException(sub2);
688             }
689             subtreeLocals.or(childLocals);
690         }
691         return subtreeLocals;
692     }
693 
694     /**
695      * Returns the subroutine object associated with the given instruction. This is a costly operation, you should consider
696      * using getSubroutine(InstructionHandle). Returns 'null' if the given InstructionHandle lies in so-called 'dead code',
697      * for example code that can never be executed.
698      *
699      * @param any The instruction handle.
700      * @return The Subroutine object or null.
701      * @see #getSubroutine(InstructionHandle)
702      * @see #getTopLevel()
703      */
704     public Subroutine subroutineOf(final InstructionHandle any) {
705         for (final Subroutine s : subroutines.values()) {
706             if (s.contains(any)) {
707                 return s;
708             }
709         }
710         System.err.println("DEBUG: Please verify '" + any.toString(true) + "' lies in dead code.");
711         return null;
712         // throw new AssertionViolatedException("No subroutine for InstructionHandle found (DEAD CODE?).");
713     }
714 
715     /**
716      * Returns a String representation of this object; merely for debugging purposes.
717      */
718     @Override
719     public String toString() {
720         return "---\n" + subroutines + "\n---\n";
721     }
722 }