1 19 20 25 26 package soot; 27 28 import soot.jimple.*; 29 import soot.util.*; 30 import java.util.*; 31 32 38 public class Hierarchy 39 { 40 HashMap classToSubclasses; 42 HashMap interfaceToSubinterfaces; 43 44 HashMap classToDirSubclasses; 45 HashMap interfaceToDirSubinterfaces; 46 47 HashMap interfaceToDirImplementers; 49 50 int state; 51 Scene sc; 52 53 54 public Hierarchy() 55 { 56 this.sc = Scene.v(); 57 state = sc.getState(); 58 59 { 62 Chain allClasses = sc.getClasses(); 63 64 classToSubclasses = new HashMap(allClasses.size() * 2 + 1, 0.7f); 65 interfaceToSubinterfaces = new HashMap(allClasses.size() * 2 + 1, 0.7f); 66 67 classToDirSubclasses = new HashMap 68 (allClasses.size() * 2 + 1, 0.7f); 69 interfaceToDirSubinterfaces = new HashMap 70 (allClasses.size() * 2 + 1, 0.7f); 71 interfaceToDirImplementers = new HashMap 72 (allClasses.size() * 2 + 1, 0.7f); 73 74 Iterator classesIt = allClasses.iterator(); 75 while (classesIt.hasNext()) 76 { 77 SootClass c = (SootClass)classesIt.next(); 78 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 79 80 if (c.isInterface()) 81 { 82 interfaceToDirSubinterfaces.put(c, new ArrayList()); 83 interfaceToDirImplementers.put(c, new ArrayList()); 84 } 85 else 86 classToDirSubclasses.put(c, new ArrayList()); 87 } 88 89 classesIt = allClasses.iterator(); 90 while (classesIt.hasNext()) 91 { 92 SootClass c = (SootClass)classesIt.next(); 93 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 94 95 if (c.hasSuperclass()) 96 { 97 if (c.isInterface()) 98 { 99 Iterator subIt = c.getInterfaces().iterator(); 100 101 while (subIt.hasNext()) 102 { 103 SootClass i = (SootClass)subIt.next(); 104 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 105 List l = (List)interfaceToDirSubinterfaces.get(i); 106 l.add(c); 107 } 108 } 109 else 110 { 111 List l = (List)classToDirSubclasses.get(c.getSuperclass()); 112 l.add(c); 113 114 115 Iterator subIt = c.getInterfaces().iterator(); 116 117 while (subIt.hasNext()) 118 { 119 SootClass i = (SootClass)subIt.next(); 120 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 121 l = (List)interfaceToDirImplementers.get(i); 122 l.add(c); 123 } 124 } 125 } 126 } 127 128 { 130 classesIt = allClasses.iterator(); 131 while (classesIt.hasNext()) 132 { 133 SootClass c = (SootClass)classesIt.next(); 134 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 135 if (c.isInterface()) 136 { 137 List imp = (List)interfaceToDirImplementers.get(c); 138 Set s = new ArraySet(); 139 140 Iterator impIt = imp.iterator(); 141 while (impIt.hasNext()) 142 { 143 SootClass c0 = (SootClass)impIt.next(); 144 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 145 s.addAll(getSubclassesOfIncluding(c0)); 146 } 147 148 imp.clear(); imp.addAll(s); 149 } 150 } 151 } 152 153 classesIt = allClasses.iterator(); 154 while (classesIt.hasNext()) 155 { 156 SootClass c = (SootClass)classesIt.next(); 157 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue; 158 159 if (c.isInterface()) 160 { 161 interfaceToDirSubinterfaces.put(c, Collections.unmodifiableList 162 ((List)interfaceToDirSubinterfaces.get(c))); 163 interfaceToDirImplementers.put(c, Collections.unmodifiableList 164 ((List)interfaceToDirImplementers.get(c))); 165 } 166 else 167 classToDirSubclasses.put(c, Collections.unmodifiableList 168 ((List)classToDirSubclasses.get(c))); 169 } 170 } 171 } 172 173 private void checkState() 174 { 175 if (state != sc.getState()) 176 throw new ConcurrentModificationException("Scene changed for Hierarchy!"); 177 } 178 179 181 public List getSubclassesOfIncluding(SootClass c) 182 { 183 c.checkLevel(SootClass.HIERARCHY); 184 if (c.isInterface()) 185 throw new RuntimeException ("class needed!"); 186 187 List l = new ArrayList(); 188 l.addAll(getSubclassesOf(c)); 189 l.add(c); 190 191 return Collections.unmodifiableList(l); 192 } 193 194 195 public List getSubclassesOf(SootClass c) 196 { 197 c.checkLevel(SootClass.HIERARCHY); 198 if (c.isInterface()) 199 throw new RuntimeException ("class needed!"); 200 201 checkState(); 202 203 if (classToSubclasses.get(c) != null) 205 return (List)classToSubclasses.get(c); 206 207 List l = new ArrayList(); 209 210 ListIterator it = ((List)classToDirSubclasses.get(c)).listIterator(); 211 while (it.hasNext()) 212 { 213 SootClass cls = (SootClass) it.next(); 214 if( cls.resolvingLevel() < cls.HIERARCHY ) continue; 215 l.addAll(getSubclassesOfIncluding(cls)); 216 } 217 218 l = Collections.unmodifiableList(l); 219 classToSubclasses.put(c, l); 220 221 return l; 222 } 223 224 225 public List getSuperclassesOfIncluding(SootClass c) 226 { 227 c.checkLevel(SootClass.HIERARCHY); 228 List l = getSuperclassesOf(c); 229 ArrayList al = new ArrayList(); al.add(c); al.addAll(l); 230 return Collections.unmodifiableList(al); 231 } 232 233 234 public List getSuperclassesOf(SootClass c) 235 { 236 c.checkLevel(SootClass.HIERARCHY); 237 if (c.isInterface()) 238 throw new RuntimeException ("class needed!"); 239 240 checkState(); 241 242 ArrayList l = new ArrayList(); 243 SootClass cl = c; 244 245 while (cl.hasSuperclass()) 246 { 247 l.add(cl.getSuperclass()); 248 cl = cl.getSuperclass(); 249 } 250 251 return Collections.unmodifiableList(l); 252 } 253 254 255 public List getSubinterfacesOfIncluding(SootClass c) 256 { 257 c.checkLevel(SootClass.HIERARCHY); 258 if (!c.isInterface()) 259 throw new RuntimeException ("interface needed!"); 260 261 List l = new ArrayList(); 262 l.addAll(getSubinterfacesOf(c)); 263 l.add(c); 264 265 return Collections.unmodifiableList(l); 266 } 267 268 269 public List getSubinterfacesOf(SootClass c) 270 { 271 c.checkLevel(SootClass.HIERARCHY); 272 if (!c.isInterface()) 273 throw new RuntimeException ("interface needed!"); 274 275 checkState(); 276 277 if (interfaceToSubinterfaces.get(c) != null) 279 return (List)interfaceToSubinterfaces.get(c); 280 281 List l = new ArrayList(); 283 284 ListIterator it = ((List)interfaceToDirSubinterfaces.get(c)).listIterator(); 285 while (it.hasNext()) 286 { 287 l.addAll(getSubinterfacesOfIncluding((SootClass)it.next())); 288 } 289 290 interfaceToSubinterfaces.put(c, Collections.unmodifiableList(l)); 291 292 return Collections.unmodifiableList(l); 293 } 294 295 296 public List getSuperinterfacesOf(SootClass c) 297 { 298 throw new RuntimeException ("Not implemented yet!"); 299 } 300 301 302 public List getDirectSuperclassesOf(SootClass c) 303 { 304 throw new RuntimeException ("Not implemented yet!"); 305 } 306 307 308 public List getDirectSubclassesOf(SootClass c) 309 { 310 c.checkLevel(SootClass.HIERARCHY); 311 if (c.isInterface()) 312 throw new RuntimeException ("class needed!"); 313 314 checkState(); 315 316 return Collections.unmodifiableList((List)classToDirSubclasses.get(c)); 317 } 318 319 321 public List getDirectSubclassesOfIncluding(SootClass c) 322 { 323 c.checkLevel(SootClass.HIERARCHY); 324 if (c.isInterface()) 325 throw new RuntimeException ("class needed!"); 326 327 checkState(); 328 329 List l = new ArrayList(); 330 l.addAll((List)classToDirSubclasses.get(c)); 331 l.add(c); 332 333 return Collections.unmodifiableList(l); 334 } 335 336 337 public List getDirectSuperinterfacesOf(SootClass c) 338 { 339 throw new RuntimeException ("Not implemented yet!"); 340 } 341 342 343 public List getDirectSubinterfacesOf(SootClass c) 344 { 345 c.checkLevel(SootClass.HIERARCHY); 346 if (!c.isInterface()) 347 throw new RuntimeException ("interface needed!"); 348 349 checkState(); 350 351 return (List)interfaceToDirSubinterfaces.get(c); 352 } 353 354 355 public List getDirectSubinterfacesOfIncluding(SootClass c) 356 { 357 c.checkLevel(SootClass.HIERARCHY); 358 if (!c.isInterface()) 359 throw new RuntimeException ("interface needed!"); 360 361 checkState(); 362 363 List l = new ArrayList(); 364 l.addAll((List)interfaceToDirSubinterfaces.get(c)); 365 l.add(c); 366 367 return Collections.unmodifiableList(l); 368 } 369 370 371 public List getDirectImplementersOf(SootClass i) 372 { 373 i.checkLevel(SootClass.HIERARCHY); 374 if (!i.isInterface()) 375 throw new RuntimeException ("interface needed; got "+i); 376 377 checkState(); 378 379 return Collections.unmodifiableList((List)interfaceToDirImplementers.get(i)); 380 } 381 382 383 public List getImplementersOf(SootClass i) 384 { 385 i.checkLevel(SootClass.HIERARCHY); 386 if (!i.isInterface()) 387 throw new RuntimeException ("interface needed; got "+i); 388 389 checkState(); 390 391 Iterator it = getSubinterfacesOfIncluding(i).iterator(); 392 ArraySet set = new ArraySet(); 393 394 while (it.hasNext()) 395 { 396 SootClass c = (SootClass)it.next(); 397 398 set.addAll(getDirectImplementersOf(c)); 399 } 400 401 ArrayList l = new ArrayList(); 402 l.addAll(set); 403 404 return Collections.unmodifiableList(l); 405 } 406 407 408 public boolean isClassSubclassOf(SootClass child, SootClass possibleParent) 409 { 410 child.checkLevel(SootClass.HIERARCHY); 411 possibleParent.checkLevel(SootClass.HIERARCHY); 412 return getSuperclassesOf(child).contains(possibleParent); 413 } 414 415 416 public boolean isClassSubclassOfIncluding(SootClass child, SootClass possibleParent) 417 { 418 child.checkLevel(SootClass.HIERARCHY); 419 possibleParent.checkLevel(SootClass.HIERARCHY); 420 return getSuperclassesOfIncluding(child).contains(possibleParent); 421 } 422 423 424 public boolean isClassDirectSubclassOf(SootClass c, SootClass c2) 425 { 426 throw new RuntimeException ("Not implemented yet!"); 427 } 428 429 430 public boolean isClassSuperclassOf(SootClass parent, SootClass possibleChild) 431 { 432 parent.checkLevel(SootClass.HIERARCHY); 433 possibleChild.checkLevel(SootClass.HIERARCHY); 434 return getSubclassesOf(parent).contains(possibleChild); 435 } 436 437 438 public boolean isClassSuperclassOfIncluding(SootClass parent, SootClass possibleChild) 439 { 440 parent.checkLevel(SootClass.HIERARCHY); 441 possibleChild.checkLevel(SootClass.HIERARCHY); 442 return getSubclassesOfIncluding(parent).contains(possibleChild); 443 } 444 445 446 public boolean isInterfaceSubinterfaceOf(SootClass child, SootClass possibleParent) 447 { 448 child.checkLevel(SootClass.HIERARCHY); 449 possibleParent.checkLevel(SootClass.HIERARCHY); 450 return getSubinterfacesOf(possibleParent).contains(child); 451 } 452 453 454 public boolean isInterfaceDirectSubinterfaceOf(SootClass child, 455 SootClass possibleParent) 456 { 457 child.checkLevel(SootClass.HIERARCHY); 458 possibleParent.checkLevel(SootClass.HIERARCHY); 459 return getDirectSubinterfacesOf(possibleParent).contains(child); 460 } 461 462 463 public SootClass getLeastCommonSuperclassOf(SootClass c1, 464 SootClass c2) 465 { 466 c1.checkLevel(SootClass.HIERARCHY); 467 c2.checkLevel(SootClass.HIERARCHY); 468 throw new RuntimeException ("Not implemented yet!"); 469 } 470 471 473 474 private boolean isVisible( SootClass from, SootMethod m ) { 475 from.checkLevel(SootClass.HIERARCHY); 476 m.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 477 if( m.isPublic() ) return true; 478 if( m.isPrivate() ) { 479 return from.equals( m.getDeclaringClass() ); 480 } 481 if( m.isProtected() ) { 482 return isClassSubclassOfIncluding( from, m.getDeclaringClass() ); 483 } 484 return from.getJavaPackageName().equals( 486 m.getDeclaringClass().getJavaPackageName() ); 487 } 489 490 492 public SootMethod resolveConcreteDispatch(SootClass concreteType, SootMethod m) 493 { 494 concreteType.checkLevel(SootClass.HIERARCHY); 495 m.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 496 checkState(); 497 498 if (concreteType.isInterface()) 499 throw new RuntimeException ("class needed!"); 500 501 Iterator it = getSuperclassesOfIncluding(concreteType).iterator(); 502 String methodSig = m.getSubSignature(); 503 504 while (it.hasNext()) 505 { 506 SootClass c = (SootClass)it.next(); 507 if (c.declaresMethod(methodSig) 508 && isVisible( c, m ) 509 ) { 510 return c.getMethod(methodSig); 511 } 512 } 513 throw new RuntimeException ("could not resolve concrete dispatch!\nType: "+concreteType+"\nMethod: "+m); 514 } 515 516 517 public List resolveConcreteDispatch(List classes, SootMethod m) 518 { 519 m.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 520 checkState(); 521 522 ArraySet s = new ArraySet(); 523 Iterator classesIt = classes.iterator(); 524 525 while (classesIt.hasNext()) { 526 Object cls = classesIt.next(); 527 if (cls instanceof RefType) 528 s.add(resolveConcreteDispatch(((RefType)cls).getSootClass(), m)); 529 else if (cls instanceof ArrayType) { 530 s.add(resolveConcreteDispatch((RefType.v("java.lang.Object")).getSootClass(), m)); 531 } 532 else throw new RuntimeException ("Unable to resolve concrete dispatch of type "+ cls); 533 } 534 535 List l = new ArrayList(); l.addAll(s); 536 return Collections.unmodifiableList(l); 537 } 538 539 542 public List resolveAbstractDispatch(SootClass c, SootMethod m) 543 { 544 c.checkLevel(SootClass.HIERARCHY); 545 m.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 546 checkState(); 547 548 Iterator classesIt = null; 549 550 if (c.isInterface()) { 551 classesIt = getImplementersOf(c).iterator(); 552 HashSet classes = new HashSet(); 553 while (classesIt.hasNext()) 554 classes.addAll(getSubclassesOfIncluding((SootClass)classesIt.next())); 555 classesIt = classes.iterator(); 556 } 557 558 else 559 classesIt = getSubclassesOfIncluding(c).iterator(); 560 561 ArraySet s = new ArraySet(); 562 563 while (classesIt.hasNext()) { 564 SootClass cl = (SootClass) classesIt.next(); 565 if( Modifier.isAbstract( cl.getModifiers() ) ) continue; 566 s.add(resolveConcreteDispatch(cl, m)); 567 } 568 569 List l = new ArrayList(); l.addAll(s); 570 return Collections.unmodifiableList(l); 571 } 572 573 575 public List resolveAbstractDispatch(List classes, SootMethod m) 576 { 577 m.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 578 ArraySet s = new ArraySet(); 579 Iterator classesIt = classes.iterator(); 580 581 while (classesIt.hasNext()) 582 s.addAll(resolveAbstractDispatch((SootClass)classesIt.next(), m)); 583 584 List l = new ArrayList(); l.addAll(s); 585 return Collections.unmodifiableList(l); 586 } 587 588 589 public SootMethod resolveSpecialDispatch(SpecialInvokeExpr ie, SootMethod container) 590 { 591 container.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 592 SootMethod target = ie.getMethod(); 593 target.getDeclaringClass().checkLevel(SootClass.HIERARCHY); 594 595 597 if (target.getName().equals("<init>") || target.isPrivate()) 598 return target; 599 else if (isClassSubclassOf(target.getDeclaringClass(), container.getDeclaringClass())) 600 return resolveConcreteDispatch(container.getDeclaringClass(), target); 601 else 602 return target; 603 } 604 } 605 | Popular Tags |