001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 */ 018package org.apache.bcel.verifier.structurals; 019 020import java.util.ArrayList; 021import java.util.HashMap; 022import java.util.HashSet; 023import java.util.List; 024import java.util.Map; 025import java.util.Set; 026 027import org.apache.bcel.generic.ASTORE; 028import org.apache.bcel.generic.ATHROW; 029import org.apache.bcel.generic.BranchInstruction; 030import org.apache.bcel.generic.CodeExceptionGen; 031import org.apache.bcel.generic.GotoInstruction; 032import org.apache.bcel.generic.IndexedInstruction; 033import org.apache.bcel.generic.Instruction; 034import org.apache.bcel.generic.InstructionHandle; 035import org.apache.bcel.generic.JsrInstruction; 036import org.apache.bcel.generic.LocalVariableInstruction; 037import org.apache.bcel.generic.MethodGen; 038import org.apache.bcel.generic.RET; 039import org.apache.bcel.generic.ReturnInstruction; 040import org.apache.bcel.generic.Select; 041import org.apache.bcel.verifier.exc.AssertionViolatedException; 042import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; 043 044/** 045 * Instances of this class contain information about the subroutines found in a code array of a method. This 046 * implementation considers the top-level (the instructions reachable without a JSR or JSR_W starting off from the first 047 * instruction in a code array of a method) being a special subroutine; see getTopLevel() for that. Please note that the 048 * definition of subroutines in the Java Virtual Machine Specification, Second Edition is somewhat incomplete. 049 * Therefore, JustIce uses an own, more rigid notion. Basically, a subroutine is a piece of code that starts at the 050 * target of a JSR of JSR_W instruction and ends at a corresponding RET instruction. Note also that the control flow of 051 * a subroutine may be complex and non-linear; and that subroutines may be nested. JustIce also mandates subroutines not 052 * to be protected by exception handling code (for the sake of control flow predictability). To understand JustIce's 053 * notion of subroutines, please read 054 * 055 * TODO: refer to the paper. 056 * 057 * @see #getTopLevel() 058 */ 059public class Subroutines { 060 // Node coloring constants 061 private enum ColourConstants { 062 WHITE, GRAY, BLACK 063 } 064 065 /** 066 * This inner class implements the Subroutine interface. 067 */ 068 private class SubroutineImpl implements Subroutine { 069 /** 070 * UNSET, a symbol for an uninitialized localVariable field. This is used for the "top-level" Subroutine; i.e. no 071 * subroutine. 072 */ 073 private static final int UNSET = -1; 074 075 private final SubroutineImpl[] EMPTY_ARRAY = {}; 076 077 /** 078 * The Local Variable slot where the first instruction of this subroutine (an ASTORE) stores the JsrInstruction's 079 * ReturnAddress in and the RET of this subroutine operates on. 080 */ 081 private int localVariable = UNSET; 082 083 /** The instructions that belong to this subroutine. */ 084 private final Set<InstructionHandle> instructions = new HashSet<>(); // Elements: InstructionHandle 085 086 /** 087 * The JSR or JSR_W instructions that define this subroutine by targeting it. 088 */ 089 private final Set<InstructionHandle> theJSRs = new HashSet<>(); 090 091 /** 092 * The RET instruction that leaves this subroutine. 093 */ 094 private InstructionHandle theRET; 095 096 /** 097 * The default constructor. 098 */ 099 public SubroutineImpl() { 100 } 101 102 /** 103 * A recursive helper method for getRecursivelyAccessedLocalsIndices(). 104 * 105 * @see #getRecursivelyAccessedLocalsIndices() 106 */ 107 private void _getRecursivelyAccessedLocalsIndicesHelper(final Set<Integer> set, final Subroutine[] subs) { 108 for (final Subroutine sub : subs) { 109 final int[] lvs = sub.getAccessedLocalsIndices(); 110 for (final int lv : lvs) { 111 set.add(Integer.valueOf(lv)); 112 } 113 if (sub.subSubs().length != 0) { 114 _getRecursivelyAccessedLocalsIndicesHelper(set, sub.subSubs()); 115 } 116 } 117 } 118 119 /** 120 * Adds a new JSR or JSR_W that has this subroutine as its target. 121 */ 122 public void addEnteringJsrInstruction(final InstructionHandle jsrInst) { 123 if (jsrInst == null || !(jsrInst.getInstruction() instanceof JsrInstruction)) { 124 throw new AssertionViolatedException("Expecting JsrInstruction InstructionHandle."); 125 } 126 if (localVariable == UNSET) { 127 throw new AssertionViolatedException("Set the localVariable first!"); 128 } 129 // Something is wrong when an ASTORE is targeted that does not operate on the same local variable than the rest of the 130 // JsrInstruction-targets and the RET. 131 // (We don't know out leader here so we cannot check if we're really targeted!) 132 if (localVariable != ((ASTORE) ((JsrInstruction) jsrInst.getInstruction()).getTarget().getInstruction()).getIndex()) { 133 throw new AssertionViolatedException("Setting a wrong JsrInstruction."); 134 } 135 theJSRs.add(jsrInst); 136 } 137 138 /* 139 * Adds an instruction to this subroutine. All instructions must have been added before invoking setLeavingRET(). 140 * 141 * @see #setLeavingRET 142 */ 143 void addInstruction(final InstructionHandle ih) { 144 if (theRET != null) { 145 throw new AssertionViolatedException("All instructions must have been added before invoking setLeavingRET()."); 146 } 147 instructions.add(ih); 148 } 149 150 /* 151 * Refer to the Subroutine interface for documentation. 152 */ 153 @Override 154 public boolean contains(final InstructionHandle inst) { 155 return instructions.contains(inst); 156 } 157 158 /* 159 * Satisfies Subroutine.getAccessedLocalIndices(). 160 */ 161 @Override 162 public int[] getAccessedLocalsIndices() { 163 // TODO: Implement caching. 164 final Set<Integer> acc = new HashSet<>(); 165 if (theRET == null && this != getTopLevel()) { 166 throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals."); 167 } 168 { 169 for (final InstructionHandle ih : instructions) { 170 // RET is not a LocalVariableInstruction in the current version of BCEL. 171 if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET) { 172 final int idx = ((IndexedInstruction) ih.getInstruction()).getIndex(); 173 acc.add(Integer.valueOf(idx)); 174 // LONG? DOUBLE?. 175 try { 176 // LocalVariableInstruction instances are typed without the need to look into 177 // the constant pool. 178 if (ih.getInstruction() instanceof LocalVariableInstruction) { 179 final int s = ((LocalVariableInstruction) ih.getInstruction()).getType(null).getSize(); 180 if (s == 2) { 181 acc.add(Integer.valueOf(idx + 1)); 182 } 183 } 184 } catch (final RuntimeException re) { 185 throw new AssertionViolatedException("BCEL did not like NULL as a ConstantPoolGen object.", re); 186 } 187 } 188 } 189 } 190 191 { 192 final int[] ret = new int[acc.size()]; 193 int j = -1; 194 for (final Integer accessedLocal : acc) { 195 j++; 196 ret[j] = accessedLocal.intValue(); 197 } 198 return ret; 199 } 200 } 201 202 /* 203 * Refer to the Subroutine interface for documentation. 204 */ 205 @Override 206 public InstructionHandle[] getEnteringJsrInstructions() { 207 if (this == getTopLevel()) { 208 throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine."); 209 } 210 return theJSRs.toArray(InstructionHandle.EMPTY_ARRAY); 211 } 212 213 /* 214 * Refer to the Subroutine interface for documentation. 215 */ 216 @Override 217 public InstructionHandle[] getInstructions() { 218 return instructions.toArray(InstructionHandle.EMPTY_ARRAY); 219 } 220 221 /* 222 * Refer to the Subroutine interface for documentation. 223 */ 224 @Override 225 public InstructionHandle getLeavingRET() { 226 if (this == getTopLevel()) { 227 throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine."); 228 } 229 return theRET; 230 } 231 232 /* Satisfies Subroutine.getRecursivelyAccessedLocalsIndices(). */ 233 @Override 234 public int[] getRecursivelyAccessedLocalsIndices() { 235 final Set<Integer> s = new HashSet<>(); 236 final int[] lvs = getAccessedLocalsIndices(); 237 for (final int lv : lvs) { 238 s.add(Integer.valueOf(lv)); 239 } 240 _getRecursivelyAccessedLocalsIndicesHelper(s, this.subSubs()); 241 final int[] ret = new int[s.size()]; 242 int j = -1; 243 for (final Integer index : s) { 244 j++; 245 ret[j] = index.intValue(); 246 } 247 return ret; 248 } 249 250 /** 251 * Sets the leaving RET instruction. Must be invoked after all instructions are added. Must not be invoked for top-level 252 * 'subroutine'. 253 */ 254 void setLeavingRET() { 255 if (localVariable == UNSET) { 256 throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first."); 257 } 258 InstructionHandle ret = null; 259 for (final InstructionHandle actual : instructions) { 260 if (actual.getInstruction() instanceof RET) { 261 if (ret != null) { 262 throw new StructuralCodeConstraintException("Subroutine with more then one RET detected: '" + ret + "' and '" + actual + "'."); 263 } 264 ret = actual; 265 } 266 } 267 if (ret == null) { 268 throw new StructuralCodeConstraintException("Subroutine without a RET detected."); 269 } 270 if (((RET) ret.getInstruction()).getIndex() != localVariable) { 271 throw new StructuralCodeConstraintException( 272 "Subroutine uses '" + ret + "' which does not match the correct local variable '" + localVariable + "'."); 273 } 274 theRET = ret; 275 } 276 277 /* 278 * Sets the local variable slot the ASTORE that is targeted by the JsrInstructions of this subroutine operates on. This 279 * subroutine's RET operates on that same local variable slot, of course. 280 */ 281 void setLocalVariable(final int i) { 282 if (localVariable != UNSET) { 283 throw new AssertionViolatedException("localVariable set twice."); 284 } 285 localVariable = i; 286 } 287 288 /* 289 * Satisfies Subroutine.subSubs(). 290 */ 291 @Override 292 public Subroutine[] subSubs() { 293 final Set<Subroutine> h = new HashSet<>(); 294 295 for (final InstructionHandle ih : instructions) { 296 final Instruction inst = ih.getInstruction(); 297 if (inst instanceof JsrInstruction) { 298 final InstructionHandle targ = ((JsrInstruction) inst).getTarget(); 299 h.add(getSubroutine(targ)); 300 } 301 } 302 return h.toArray(EMPTY_ARRAY); 303 } 304 305 /** 306 * Returns a String representation of this object, merely for debugging purposes. (Internal) Warning: Verbosity on a 307 * problematic subroutine may cause stack overflow errors due to recursive subSubs() calls. Don't use this, then. 308 */ 309 @Override 310 public String toString() { 311 final StringBuilder ret = new StringBuilder(); 312 ret.append("Subroutine: Local variable is '").append(localVariable); 313 ret.append("', JSRs are '").append(theJSRs); 314 ret.append("', RET is '").append(theRET); 315 ret.append("', Instructions: '").append(instructions).append("'."); 316 317 ret.append(" Accessed local variable slots: '"); 318 int[] alv = getAccessedLocalsIndices(); 319 for (final int element : alv) { 320 ret.append(element); 321 ret.append(" "); 322 } 323 ret.append("'."); 324 325 ret.append(" Recursively (via subsub...routines) accessed local variable slots: '"); 326 alv = getRecursivelyAccessedLocalsIndices(); 327 for (final int element : alv) { 328 ret.append(element); 329 ret.append(" "); 330 } 331 ret.append("'."); 332 333 return ret.toString(); 334 } 335 336 }// end Inner Class SubrouteImpl 337 338 /** 339 * A utility method that calculates the successors of a given InstructionHandle <B>in the same subroutine</B>. That 340 * means, a RET does not have any successors as defined here. A JsrInstruction has its physical successor as its 341 * successor (opposed to its target) as defined here. 342 */ 343 private static InstructionHandle[] getSuccessors(final InstructionHandle instruction) { 344 final InstructionHandle[] single = new InstructionHandle[1]; 345 346 final Instruction inst = instruction.getInstruction(); 347 348 // Terminates method normally. 349 // Terminates method abnormally, because JustIce mandates 350 // subroutines not to be protected by exception handlers. 351 if (inst instanceof RET || inst instanceof ReturnInstruction || inst instanceof ATHROW) { 352 return InstructionHandle.EMPTY_ARRAY; 353 } 354 355 // See method comment. 356 if (inst instanceof JsrInstruction) { 357 single[0] = instruction.getNext(); 358 return single; 359 } 360 361 if (inst instanceof GotoInstruction) { 362 single[0] = ((GotoInstruction) inst).getTarget(); 363 return single; 364 } 365 366 if (inst instanceof BranchInstruction) { 367 if (inst instanceof Select) { 368 // BCEL's getTargets() returns only the non-default targets, 369 // thanks to Eli Tilevich for reporting. 370 final InstructionHandle[] matchTargets = ((Select) inst).getTargets(); 371 final InstructionHandle[] ret = new InstructionHandle[matchTargets.length + 1]; 372 ret[0] = ((Select) inst).getTarget(); 373 System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length); 374 return ret; 375 } 376 final InstructionHandle[] pair = new InstructionHandle[2]; 377 pair[0] = instruction.getNext(); 378 pair[1] = ((BranchInstruction) inst).getTarget(); 379 return pair; 380 } 381 382 // default case: Fall through. 383 single[0] = instruction.getNext(); 384 return single; 385 } 386 387 /** 388 * The map containing the subroutines found. Key: InstructionHandle of the leader of the subroutine. Elements: 389 * SubroutineImpl objects. 390 */ 391 private final Map<InstructionHandle, Subroutine> subroutines = new HashMap<>(); 392 393 /** 394 * This is referring to a special subroutine, namely the top level. This is not really a subroutine but we use it to 395 * distinguish between top level instructions and unreachable instructions. 396 */ 397 // CHECKSTYLE:OFF 398 public final Subroutine TOPLEVEL; // TODO can this be made private? 399 // CHECKSTYLE:ON 400 401 /** 402 * Constructor. 403 * 404 * @param mg A MethodGen object representing method to create the Subroutine objects of. Assumes that JustIce strict 405 * checks are needed. 406 */ 407 public Subroutines(final MethodGen mg) { 408 this(mg, true); 409 } 410 411 /** 412 * Constructor. 413 * 414 * @param mg A MethodGen object representing method to create the Subroutine objects of. 415 * @param enableJustIceCheck whether to enable additional JustIce checks 416 * @since 6.0 417 */ 418 public Subroutines(final MethodGen mg, final boolean enableJustIceCheck) { 419 final InstructionHandle[] all = mg.getInstructionList().getInstructionHandles(); 420 final CodeExceptionGen[] handlers = mg.getExceptionHandlers(); 421 422 // Define our "Toplevel" fake subroutine. 423 TOPLEVEL = new SubroutineImpl(); 424 425 // Calculate "real" subroutines. 426 final Set<InstructionHandle> sub_leaders = new HashSet<>(); // Elements: InstructionHandle 427 for (final InstructionHandle element : all) { 428 final Instruction inst = element.getInstruction(); 429 if (inst instanceof JsrInstruction) { 430 sub_leaders.add(((JsrInstruction) inst).getTarget()); 431 } 432 } 433 434 // Build up the database. 435 for (final InstructionHandle astore : sub_leaders) { 436 final SubroutineImpl sr = new SubroutineImpl(); 437 sr.setLocalVariable(((ASTORE) astore.getInstruction()).getIndex()); 438 subroutines.put(astore, sr); 439 } 440 441 // Fake it a bit. We want a virtual "TopLevel" subroutine. 442 subroutines.put(all[0], TOPLEVEL); 443 sub_leaders.add(all[0]); 444 445 // Tell the subroutines about their JsrInstructions. 446 // Note that there cannot be a JSR targeting the top-level 447 // since "Jsr 0" is disallowed in Pass 3a. 448 // Instructions shared by a subroutine and the toplevel are 449 // disallowed and checked below, after the BFS. 450 for (final InstructionHandle element : all) { 451 final Instruction inst = element.getInstruction(); 452 if (inst instanceof JsrInstruction) { 453 final InstructionHandle leader = ((JsrInstruction) inst).getTarget(); 454 ((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(element); 455 } 456 } 457 458 // Now do a BFS from every subroutine leader to find all the 459 // instructions that belong to a subroutine. 460 // we don't want to assign an instruction to two or more Subroutine objects. 461 final Set<InstructionHandle> instructions_assigned = new HashSet<>(); 462 463 // Graph coloring. Key: InstructionHandle, Value: ColourConstants enum . 464 final Map<InstructionHandle, ColourConstants> colors = new HashMap<>(); 465 466 final List<InstructionHandle> qList = new ArrayList<>(); 467 for (final InstructionHandle actual : sub_leaders) { 468 // Do some BFS with "actual" as the root of the graph. 469 // Init colors 470 for (final InstructionHandle element : all) { 471 colors.put(element, ColourConstants.WHITE); 472 } 473 colors.put(actual, ColourConstants.GRAY); 474 // Init Queue 475 476 qList.clear(); 477 qList.add(actual); // add(Obj) adds to the end, remove(0) removes from the start. 478 479 /* 480 * BFS ALGORITHM MODIFICATION: Start out with multiple "root" nodes, as exception handlers are starting points of 481 * top-level code, too. [why top-level? TODO: Refer to the special JustIce notion of subroutines.] 482 */ 483 if (actual == all[0]) { 484 for (final CodeExceptionGen handler : handlers) { 485 colors.put(handler.getHandlerPC(), ColourConstants.GRAY); 486 qList.add(handler.getHandlerPC()); 487 } 488 } 489 /* CONTINUE NORMAL BFS ALGORITHM */ 490 491 // Loop until Queue is empty 492 while (!qList.isEmpty()) { 493 final InstructionHandle u = qList.remove(0); 494 final InstructionHandle[] successors = getSuccessors(u); 495 for (final InstructionHandle successor : successors) { 496 if (colors.get(successor) == ColourConstants.WHITE) { 497 colors.put(successor, ColourConstants.GRAY); 498 qList.add(successor); 499 } 500 } 501 colors.put(u, ColourConstants.BLACK); 502 } 503 // BFS ended above. 504 for (final InstructionHandle element : all) { 505 if (colors.get(element) == ColourConstants.BLACK) { 506 ((SubroutineImpl) (actual == all[0] ? getTopLevel() : getSubroutine(actual))).addInstruction(element); 507 if (instructions_assigned.contains(element)) { 508 throw new StructuralCodeConstraintException( 509 "Instruction '" + element + "' is part of more than one subroutine (or of the top level and a subroutine)."); 510 } 511 instructions_assigned.add(element); 512 } 513 } 514 if (actual != all[0]) {// If we don't deal with the top-level 'subroutine' 515 ((SubroutineImpl) getSubroutine(actual)).setLeavingRET(); 516 } 517 } 518 519 if (enableJustIceCheck) { 520 // Now make sure no instruction of a Subroutine is protected by exception handling code 521 // as is mandated by JustIces notion of subroutines. 522 for (final CodeExceptionGen handler : handlers) { 523 InstructionHandle _protected = handler.getStartPC(); 524 while (_protected != handler.getEndPC().getNext()) { 525 // Note the inclusive/inclusive notation of "generic API" exception handlers! 526 for (final Subroutine sub : subroutines.values()) { 527 if (sub != subroutines.get(all[0]) && sub.contains(_protected)) { 528 throw new StructuralCodeConstraintException("Subroutine instruction '" + _protected + "' is protected by an exception handler, '" 529 + handler + "'. This is forbidden by the JustIce verifier due to its clear definition of subroutines."); 530 } 531 } 532 _protected = _protected.getNext(); 533 } 534 } 535 } 536 537 // Now make sure no subroutine is calling a subroutine 538 // that uses the same local variable for the RET as themselves 539 // (recursively). 540 // This includes that subroutines may not call themselves 541 // recursively, even not through intermediate calls to other 542 // subroutines. 543 noRecursiveCalls(getTopLevel(), new HashSet<>()); 544 545 } 546 547 /** 548 * Returns the Subroutine object associated with the given leader (that is, the first instruction of the subroutine). 549 * You must not use this to get the top-level instructions modeled as a Subroutine object. 550 * 551 * @see #getTopLevel() 552 */ 553 public Subroutine getSubroutine(final InstructionHandle leader) { 554 final Subroutine ret = subroutines.get(leader); 555 556 if (ret == null) { 557 throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine."); 558 } 559 560 if (ret == TOPLEVEL) { 561 throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel()."); 562 } 563 564 return ret; 565 } 566 567 /** 568 * For easy handling, the piece of code that is <B>not</B> a subroutine, the top-level, is also modeled as a Subroutine 569 * object. It is a special Subroutine object where <B>you must not invoke getEnteringJsrInstructions() or 570 * getLeavingRET()</B>. 571 * 572 * @see Subroutine#getEnteringJsrInstructions() 573 * @see Subroutine#getLeavingRET() 574 */ 575 public Subroutine getTopLevel() { 576 return TOPLEVEL; 577 } 578 579 /** 580 * This (recursive) utility method makes sure that no subroutine is calling a subroutine that uses the same local 581 * variable for the RET as themselves (recursively). This includes that subroutines may not call themselves recursively, 582 * even not through intermediate calls to other subroutines. 583 * 584 * @throws StructuralCodeConstraintException if the above constraint is not satisfied. 585 */ 586 private void noRecursiveCalls(final Subroutine sub, final Set<Integer> set) { 587 final Subroutine[] subs = sub.subSubs(); 588 589 for (final Subroutine sub2 : subs) { 590 final int index = ((RET) sub2.getLeavingRET().getInstruction()).getIndex(); 591 592 if (!set.add(Integer.valueOf(index))) { 593 // Don't use toString() here because of possibly infinite recursive subSubs() calls then. 594 final SubroutineImpl si = (SubroutineImpl) sub2; 595 throw new StructuralCodeConstraintException("Subroutine with local variable '" + si.localVariable + "', JSRs '" + si.theJSRs + "', RET '" 596 + si.theRET + "' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call?" 597 + " JustIce's clean definition of a subroutine forbids both."); 598 } 599 600 noRecursiveCalls(sub2, set); 601 602 set.remove(Integer.valueOf(index)); 603 } 604 } 605 606 /** 607 * Returns the subroutine object associated with the given instruction. This is a costly operation, you should consider 608 * using getSubroutine(InstructionHandle). Returns 'null' if the given InstructionHandle lies in so-called 'dead code', 609 * i.e. code that can never be executed. 610 * 611 * @see #getSubroutine(InstructionHandle) 612 * @see #getTopLevel() 613 */ 614 public Subroutine subroutineOf(final InstructionHandle any) { 615 for (final Subroutine s : subroutines.values()) { 616 if (s.contains(any)) { 617 return s; 618 } 619 } 620 System.err.println("DEBUG: Please verify '" + any.toString(true) + "' lies in dead code."); 621 return null; 622 // throw new AssertionViolatedException("No subroutine for InstructionHandle found (DEAD CODE?)."); 623 } 624 625 /** 626 * Returns a String representation of this object; merely for debugging puposes. 627 */ 628 @Override 629 public String toString() { 630 return "---\n" + subroutines + "\n---\n"; 631 } 632}