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 }