001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-1999 Raja Vallee-Rai
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot;
027:
028: import soot.jimple.*;
029: import soot.util.*;
030: import java.util.*;
031:
032: /** Represents the class hierarchy. It is closely linked to a Scene,
033: * and must be recreated if the Scene changes.
034: *
035: * The general convention is that if a method name contains
036: * "Including", then it returns the non-strict result; otherwise,
037: * it does a strict query (e.g. strict superclass). */
038: public class Hierarchy {
039: // These two maps are not filled in the constructor.
040: HashMap<SootClass, List<SootClass>> classToSubclasses;
041: HashMap<SootClass, List<SootClass>> interfaceToSubinterfaces;
042:
043: HashMap<SootClass, List> classToDirSubclasses;
044: HashMap<SootClass, List> interfaceToDirSubinterfaces;
045:
046: // This holds the direct implementers.
047: HashMap<SootClass, List> interfaceToDirImplementers;
048:
049: int state;
050: Scene sc;
051:
052: /** Constructs a hierarchy from the current scene. */
053: public Hierarchy() {
054: this .sc = Scene.v();
055: state = sc.getState();
056:
057: // Well, this used to be describable by 'Duh'.
058: // Construct the subclasses hierarchy and the subinterfaces hierarchy.
059: {
060: Chain allClasses = sc.getClasses();
061:
062: classToSubclasses = new HashMap<SootClass, List<SootClass>>(
063: allClasses.size() * 2 + 1, 0.7f);
064: interfaceToSubinterfaces = new HashMap<SootClass, List<SootClass>>(
065: allClasses.size() * 2 + 1, 0.7f);
066:
067: classToDirSubclasses = new HashMap<SootClass, List>(
068: allClasses.size() * 2 + 1, 0.7f);
069: interfaceToDirSubinterfaces = new HashMap<SootClass, List>(
070: allClasses.size() * 2 + 1, 0.7f);
071: interfaceToDirImplementers = new HashMap<SootClass, List>(
072: allClasses.size() * 2 + 1, 0.7f);
073:
074: Iterator classesIt = allClasses.iterator();
075: while (classesIt.hasNext()) {
076: SootClass c = (SootClass) classesIt.next();
077: if (c.resolvingLevel() < SootClass.HIERARCHY)
078: continue;
079:
080: if (c.isInterface()) {
081: interfaceToDirSubinterfaces.put(c, new ArrayList());
082: interfaceToDirImplementers.put(c, new ArrayList());
083: } else
084: classToDirSubclasses.put(c, new ArrayList());
085: }
086:
087: classesIt = allClasses.iterator();
088: while (classesIt.hasNext()) {
089: SootClass c = (SootClass) classesIt.next();
090: if (c.resolvingLevel() < SootClass.HIERARCHY)
091: continue;
092:
093: if (c.hasSuperclass()) {
094: if (c.isInterface()) {
095: Iterator subIt = c.getInterfaces().iterator();
096:
097: while (subIt.hasNext()) {
098: SootClass i = (SootClass) subIt.next();
099: if (c.resolvingLevel() < SootClass.HIERARCHY)
100: continue;
101: List<SootClass> l = interfaceToDirSubinterfaces
102: .get(i);
103: l.add(c);
104: }
105: } else {
106: List<SootClass> l = classToDirSubclasses.get(c
107: .getSuperclass());
108: l.add(c);
109:
110: Iterator subIt = c.getInterfaces().iterator();
111:
112: while (subIt.hasNext()) {
113: SootClass i = (SootClass) subIt.next();
114: if (c.resolvingLevel() < SootClass.HIERARCHY)
115: continue;
116: l = interfaceToDirImplementers.get(i);
117: l.add(c);
118: }
119: }
120: }
121: }
122:
123: // Fill the directImplementers lists with subclasses.
124: {
125: classesIt = allClasses.iterator();
126: while (classesIt.hasNext()) {
127: SootClass c = (SootClass) classesIt.next();
128: if (c.resolvingLevel() < SootClass.HIERARCHY)
129: continue;
130: if (c.isInterface()) {
131: List<SootClass> imp = interfaceToDirImplementers
132: .get(c);
133: Set<SootClass> s = new ArraySet();
134:
135: Iterator<SootClass> impIt = imp.iterator();
136: while (impIt.hasNext()) {
137: SootClass c0 = impIt.next();
138: if (c.resolvingLevel() < SootClass.HIERARCHY)
139: continue;
140: s.addAll(getSubclassesOfIncluding(c0));
141: }
142:
143: imp.clear();
144: imp.addAll(s);
145: }
146: }
147: }
148:
149: classesIt = allClasses.iterator();
150: while (classesIt.hasNext()) {
151: SootClass c = (SootClass) classesIt.next();
152: if (c.resolvingLevel() < SootClass.HIERARCHY)
153: continue;
154:
155: if (c.isInterface()) {
156: interfaceToDirSubinterfaces
157: .put(
158: c,
159: Collections
160: .unmodifiableList(interfaceToDirSubinterfaces
161: .get(c)));
162: interfaceToDirImplementers
163: .put(
164: c,
165: Collections
166: .unmodifiableList(interfaceToDirImplementers
167: .get(c)));
168: } else
169: classToDirSubclasses.put(c, Collections
170: .unmodifiableList(classToDirSubclasses
171: .get(c)));
172: }
173: }
174: }
175:
176: private void checkState() {
177: if (state != sc.getState())
178: throw new ConcurrentModificationException(
179: "Scene changed for Hierarchy!");
180: }
181:
182: // This includes c in the list of subclasses.
183: /** Returns a list of subclasses of c, including itself. */
184: public List<SootClass> getSubclassesOfIncluding(SootClass c) {
185: c.checkLevel(SootClass.HIERARCHY);
186: if (c.isInterface())
187: throw new RuntimeException("class needed!");
188:
189: List<SootClass> l = new ArrayList<SootClass>();
190: l.addAll(getSubclassesOf(c));
191: l.add(c);
192:
193: return Collections.unmodifiableList(l);
194: }
195:
196: /** Returns a list of subclasses of c, excluding itself. */
197: public List<SootClass> getSubclassesOf(SootClass c) {
198: c.checkLevel(SootClass.HIERARCHY);
199: if (c.isInterface())
200: throw new RuntimeException("class needed!");
201:
202: checkState();
203:
204: // If already cached, return the value.
205: if (classToSubclasses.get(c) != null)
206: return classToSubclasses.get(c);
207:
208: // Otherwise, build up the hashmap.
209: List<SootClass> l = new ArrayList<SootClass>();
210:
211: ListIterator it = classToDirSubclasses.get(c).listIterator();
212: while (it.hasNext()) {
213: SootClass cls = (SootClass) it.next();
214: if (cls.resolvingLevel() < SootClass.HIERARCHY)
215: continue;
216: l.addAll(getSubclassesOfIncluding(cls));
217: }
218:
219: l = Collections.unmodifiableList(l);
220: classToSubclasses.put(c, l);
221:
222: return l;
223: }
224:
225: /** Returns a list of superclasses of c, including itself. */
226: public List<SootClass> getSuperclassesOfIncluding(SootClass c) {
227: c.checkLevel(SootClass.HIERARCHY);
228: List<SootClass> l = getSuperclassesOf(c);
229: ArrayList<SootClass> al = new ArrayList<SootClass>();
230: al.add(c);
231: al.addAll(l);
232: return Collections.unmodifiableList(al);
233: }
234:
235: /** Returns a list of strict superclasses of c, starting with c's parent. */
236: public List<SootClass> getSuperclassesOf(SootClass c) {
237: c.checkLevel(SootClass.HIERARCHY);
238: if (c.isInterface())
239: throw new RuntimeException("class needed!");
240:
241: checkState();
242:
243: ArrayList<SootClass> l = new ArrayList<SootClass>();
244: SootClass cl = c;
245:
246: while (cl.hasSuperclass()) {
247: l.add(cl.getSuperclass());
248: cl = cl.getSuperclass();
249: }
250:
251: return Collections.unmodifiableList(l);
252: }
253:
254: /** Returns a list of subinterfaces of c, including itself. */
255: public List<SootClass> getSubinterfacesOfIncluding(SootClass c) {
256: c.checkLevel(SootClass.HIERARCHY);
257: if (!c.isInterface())
258: throw new RuntimeException("interface needed!");
259:
260: List<SootClass> l = new ArrayList<SootClass>();
261: l.addAll(getSubinterfacesOf(c));
262: l.add(c);
263:
264: return Collections.unmodifiableList(l);
265: }
266:
267: /** Returns a list of subinterfaces of c, excluding itself. */
268: public List<SootClass> getSubinterfacesOf(SootClass c) {
269: c.checkLevel(SootClass.HIERARCHY);
270: if (!c.isInterface())
271: throw new RuntimeException("interface needed!");
272:
273: checkState();
274:
275: // If already cached, return the value.
276: if (interfaceToSubinterfaces.get(c) != null)
277: return interfaceToSubinterfaces.get(c);
278:
279: // Otherwise, build up the hashmap.
280: List<SootClass> l = new ArrayList<SootClass>();
281:
282: ListIterator it = interfaceToDirSubinterfaces.get(c)
283: .listIterator();
284: while (it.hasNext()) {
285: l
286: .addAll(getSubinterfacesOfIncluding((SootClass) it
287: .next()));
288: }
289:
290: interfaceToSubinterfaces
291: .put(c, Collections.unmodifiableList(l));
292:
293: return Collections.unmodifiableList(l);
294: }
295:
296: /** Returns a list of superinterfaces of c, excluding itself. */
297: public List getSuperinterfacesOf(SootClass c) {
298: throw new RuntimeException("Not implemented yet!");
299: }
300:
301: /** Returns a list of direct superclasses of c, excluding c. */
302: public List getDirectSuperclassesOf(SootClass c) {
303: throw new RuntimeException("Not implemented yet!");
304: }
305:
306: /** Returns a list of direct subclasses of c, excluding c. */
307: public List getDirectSubclassesOf(SootClass c) {
308: c.checkLevel(SootClass.HIERARCHY);
309: if (c.isInterface())
310: throw new RuntimeException("class needed!");
311:
312: checkState();
313:
314: return Collections
315: .unmodifiableList(classToDirSubclasses.get(c));
316: }
317:
318: // This includes c in the list of subclasses.
319: /** Returns a list of direct subclasses of c, including c. */
320: public List<SootClass> getDirectSubclassesOfIncluding(SootClass c) {
321: c.checkLevel(SootClass.HIERARCHY);
322: if (c.isInterface())
323: throw new RuntimeException("class needed!");
324:
325: checkState();
326:
327: List<SootClass> l = new ArrayList<SootClass>();
328: l.addAll(classToDirSubclasses.get(c));
329: l.add(c);
330:
331: return Collections.unmodifiableList(l);
332: }
333:
334: /** Returns a list of direct superinterfaces of c. */
335: public List getDirectSuperinterfacesOf(SootClass c) {
336: throw new RuntimeException("Not implemented yet!");
337: }
338:
339: /** Returns a list of direct subinterfaces of c. */
340: public List getDirectSubinterfacesOf(SootClass c) {
341: c.checkLevel(SootClass.HIERARCHY);
342: if (!c.isInterface())
343: throw new RuntimeException("interface needed!");
344:
345: checkState();
346:
347: return interfaceToDirSubinterfaces.get(c);
348: }
349:
350: /** Returns a list of direct subinterfaces of c, including itself. */
351: public List<SootClass> getDirectSubinterfacesOfIncluding(SootClass c) {
352: c.checkLevel(SootClass.HIERARCHY);
353: if (!c.isInterface())
354: throw new RuntimeException("interface needed!");
355:
356: checkState();
357:
358: List<SootClass> l = new ArrayList<SootClass>();
359: l.addAll(interfaceToDirSubinterfaces.get(c));
360: l.add(c);
361:
362: return Collections.unmodifiableList(l);
363: }
364:
365: /** Returns a list of direct implementers of c, excluding itself. */
366: public List getDirectImplementersOf(SootClass i) {
367: i.checkLevel(SootClass.HIERARCHY);
368: if (!i.isInterface())
369: throw new RuntimeException("interface needed; got " + i);
370:
371: checkState();
372:
373: return Collections.unmodifiableList(interfaceToDirImplementers
374: .get(i));
375: }
376:
377: /** Returns a list of implementers of c, excluding itself. */
378: public List<SootClass> getImplementersOf(SootClass i) {
379: i.checkLevel(SootClass.HIERARCHY);
380: if (!i.isInterface())
381: throw new RuntimeException("interface needed; got " + i);
382:
383: checkState();
384:
385: Iterator<SootClass> it = getSubinterfacesOfIncluding(i)
386: .iterator();
387: ArraySet set = new ArraySet();
388:
389: while (it.hasNext()) {
390: SootClass c = it.next();
391:
392: set.addAll(getDirectImplementersOf(c));
393: }
394:
395: ArrayList l = new ArrayList();
396: l.addAll(set);
397:
398: return Collections.unmodifiableList(l);
399: }
400:
401: /** Returns true if child is a subclass of possibleParent. */
402: public boolean isClassSubclassOf(SootClass child,
403: SootClass possibleParent) {
404: child.checkLevel(SootClass.HIERARCHY);
405: possibleParent.checkLevel(SootClass.HIERARCHY);
406: return getSuperclassesOf(child).contains(possibleParent);
407: }
408:
409: /** Returns true if child is, or is a subclass of, possibleParent. */
410: public boolean isClassSubclassOfIncluding(SootClass child,
411: SootClass possibleParent) {
412: child.checkLevel(SootClass.HIERARCHY);
413: possibleParent.checkLevel(SootClass.HIERARCHY);
414: return getSuperclassesOfIncluding(child).contains(
415: possibleParent);
416: }
417:
418: /** Returns true if child is a direct subclass of possibleParent. */
419: public boolean isClassDirectSubclassOf(SootClass c, SootClass c2) {
420: throw new RuntimeException("Not implemented yet!");
421: }
422:
423: /** Returns true if child is a superclass of possibleParent. */
424: public boolean isClassSuperclassOf(SootClass parent,
425: SootClass possibleChild) {
426: parent.checkLevel(SootClass.HIERARCHY);
427: possibleChild.checkLevel(SootClass.HIERARCHY);
428: return getSubclassesOf(parent).contains(possibleChild);
429: }
430:
431: /** Returns true if parent is, or is a superclass of, possibleChild. */
432: public boolean isClassSuperclassOfIncluding(SootClass parent,
433: SootClass possibleChild) {
434: parent.checkLevel(SootClass.HIERARCHY);
435: possibleChild.checkLevel(SootClass.HIERARCHY);
436: return getSubclassesOfIncluding(parent).contains(possibleChild);
437: }
438:
439: /** Returns true if child is a subinterface of possibleParent. */
440: public boolean isInterfaceSubinterfaceOf(SootClass child,
441: SootClass possibleParent) {
442: child.checkLevel(SootClass.HIERARCHY);
443: possibleParent.checkLevel(SootClass.HIERARCHY);
444: return getSubinterfacesOf(possibleParent).contains(child);
445: }
446:
447: /** Returns true if child is a direct subinterface of possibleParent. */
448: public boolean isInterfaceDirectSubinterfaceOf(SootClass child,
449: SootClass possibleParent) {
450: child.checkLevel(SootClass.HIERARCHY);
451: possibleParent.checkLevel(SootClass.HIERARCHY);
452: return getDirectSubinterfacesOf(possibleParent).contains(child);
453: }
454:
455: /** Returns the most specific type which is an ancestor of both c1 and c2. */
456: public SootClass getLeastCommonSuperclassOf(SootClass c1,
457: SootClass c2) {
458: c1.checkLevel(SootClass.HIERARCHY);
459: c2.checkLevel(SootClass.HIERARCHY);
460: throw new RuntimeException("Not implemented yet!");
461: }
462:
463: // Questions about method invocation.
464:
465: /** Returns true if the method m is visible from code in the class from. */
466: public boolean isVisible(SootClass from, SootMethod m) {
467: from.checkLevel(SootClass.HIERARCHY);
468: m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
469: if (m.isPublic())
470: return true;
471: if (m.isPrivate()) {
472: return from.equals(m.getDeclaringClass());
473: }
474: if (m.isProtected()) {
475: return isClassSubclassOfIncluding(from, m
476: .getDeclaringClass());
477: }
478: // m is package
479: return from.getJavaPackageName().equals(
480: m.getDeclaringClass().getJavaPackageName());
481: //|| isClassSubclassOfIncluding( from, m.getDeclaringClass() );
482: }
483:
484: /** Given an object of actual type C (o = new C()), returns the method which will be called
485: on an o.f() invocation. */
486: public SootMethod resolveConcreteDispatch(SootClass concreteType,
487: SootMethod m) {
488: concreteType.checkLevel(SootClass.HIERARCHY);
489: m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
490: checkState();
491:
492: if (concreteType.isInterface())
493: throw new RuntimeException("class needed!");
494:
495: Iterator<SootClass> it = getSuperclassesOfIncluding(
496: concreteType).iterator();
497: String methodSig = m.getSubSignature();
498:
499: while (it.hasNext()) {
500: SootClass c = it.next();
501: if (c.declaresMethod(methodSig) && isVisible(c, m)) {
502: return c.getMethod(methodSig);
503: }
504: }
505: throw new RuntimeException(
506: "could not resolve concrete dispatch!\nType: "
507: + concreteType + "\nMethod: " + m);
508: }
509:
510: /** Given a set of definite receiver types, returns a list of possible targets. */
511: public List resolveConcreteDispatch(List classes, SootMethod m) {
512: m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
513: checkState();
514:
515: ArraySet s = new ArraySet();
516: Iterator classesIt = classes.iterator();
517:
518: while (classesIt.hasNext()) {
519: Object cls = classesIt.next();
520: if (cls instanceof RefType)
521: s.add(resolveConcreteDispatch(((RefType) cls)
522: .getSootClass(), m));
523: else if (cls instanceof ArrayType) {
524: s.add(resolveConcreteDispatch((RefType
525: .v("java.lang.Object")).getSootClass(), m));
526: } else
527: throw new RuntimeException(
528: "Unable to resolve concrete dispatch of type "
529: + cls);
530: }
531:
532: List l = new ArrayList();
533: l.addAll(s);
534: return Collections.unmodifiableList(l);
535: }
536:
537: // what can get called for c & all its subclasses
538: /** Given an abstract dispatch to an object of type c and a method m, gives
539: * a list of possible receiver methods. */
540: public List resolveAbstractDispatch(SootClass c, SootMethod m) {
541: c.checkLevel(SootClass.HIERARCHY);
542: m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
543: checkState();
544:
545: Iterator<SootClass> classesIt = null;
546:
547: if (c.isInterface()) {
548: classesIt = getImplementersOf(c).iterator();
549: HashSet<SootClass> classes = new HashSet<SootClass>();
550: while (classesIt.hasNext())
551: classes.addAll(getSubclassesOfIncluding(classesIt
552: .next()));
553: classesIt = classes.iterator();
554: }
555:
556: else
557: classesIt = getSubclassesOfIncluding(c).iterator();
558:
559: ArraySet s = new ArraySet();
560:
561: while (classesIt.hasNext()) {
562: SootClass cl = classesIt.next();
563: if (Modifier.isAbstract(cl.getModifiers()))
564: continue;
565: s.add(resolveConcreteDispatch(cl, m));
566: }
567:
568: List l = new ArrayList();
569: l.addAll(s);
570: return Collections.unmodifiableList(l);
571: }
572:
573: // what can get called if you have a set of possible receiver types
574: /** Returns a list of possible targets for the given method and set of receiver types. */
575: public List resolveAbstractDispatch(List classes, SootMethod m) {
576: m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
577: ArraySet s = new ArraySet();
578: Iterator classesIt = classes.iterator();
579:
580: while (classesIt.hasNext())
581: s.addAll(resolveAbstractDispatch((SootClass) classesIt
582: .next(), m));
583:
584: List l = new ArrayList();
585: l.addAll(s);
586: return Collections.unmodifiableList(l);
587: }
588:
589: /** Returns the target for the given SpecialInvokeExpr. */
590: public SootMethod resolveSpecialDispatch(SpecialInvokeExpr ie,
591: SootMethod container) {
592: container.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
593: SootMethod target = ie.getMethod();
594: target.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
595:
596: /* This is a bizarre condition! Hopefully the implementation is correct.
597: See VM Spec, 2nd Edition, Chapter 6, in the definition of invokespecial. */
598: if (target.getName().equals("<init>") || target.isPrivate())
599: return target;
600: else if (isClassSubclassOf(target.getDeclaringClass(),
601: container.getDeclaringClass()))
602: return resolveConcreteDispatch(container
603: .getDeclaringClass(), target);
604: else
605: return target;
606: }
607: }
|