KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > typing > TypeVariable


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-2000 Etienne Gagnon. All rights reserved.
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */

25
26
27 package soot.jimple.toolkits.typing;
28
29 import soot.*;
30 import soot.jimple.*;
31 import soot.util.*;
32 import java.util.*;
33
34 /** Represents a type variable. **/
35 class TypeVariable implements Comparable JavaDoc
36 {
37   private static final boolean DEBUG = false;
38
39   private final int id;
40   private final TypeResolver resolver;
41
42   private TypeVariable rep = this;
43   private int rank = 0;
44
45   private TypeNode approx;
46
47   private TypeNode type;
48   private TypeVariable array;
49   private TypeVariable element;
50   private int depth;
51
52   private List parents = Collections.unmodifiableList(new LinkedList());
53   private List children = Collections.unmodifiableList(new LinkedList());
54   private BitVector ancestors;
55   private BitVector indirectAncestors;
56
57   public TypeVariable(int id, TypeResolver resolver)
58   {
59     this.id = id;
60     this.resolver = resolver;
61   }
62
63   public TypeVariable(int id, TypeResolver resolver, TypeNode type)
64   {
65     this.id = id;
66     this.resolver = resolver;
67     this.type = type;
68     approx = type;
69     
70     for( Iterator parentIt = type.parents().iterator(); parentIt.hasNext(); ) {
71     
72         final TypeNode parent = (TypeNode) parentIt.next();
73     
74     addParent(resolver.typeVariable(parent));
75       }
76
77     if(type.hasElement())
78       {
79     element = resolver.typeVariable(type.element());
80     element.array = this;
81       }
82   }
83
84   public int hashCode()
85   {
86     if(rep != this)
87       {
88     return ecr().hashCode();
89       }
90    
91     return id;
92   }
93
94   public boolean equals(Object JavaDoc obj)
95   {
96     if(rep != this)
97       {
98     return ecr().equals(obj);
99       }
100
101     if(obj == null)
102       {
103     return false;
104       }
105
106     if(!obj.getClass().equals(getClass()))
107       {
108     return false;
109       }
110     
111     TypeVariable ecr = ((TypeVariable) obj).ecr();
112
113     if(ecr != this)
114       {
115     return false;
116       }
117     
118     return true;
119   }
120
121   public int compareTo(Object JavaDoc o)
122   {
123     if(rep != this)
124       {
125     return ecr().compareTo(o);
126       }
127
128     return id - ((TypeVariable) o).ecr().id;
129   }
130   
131   private TypeVariable ecr()
132   {
133     if(rep != this)
134       {
135     rep = rep.ecr();
136       }
137
138     return rep;
139   }
140
141   public TypeVariable union(TypeVariable var) throws TypeException
142   {
143     if(rep != this)
144       {
145     return ecr().union(var);
146       }
147
148     TypeVariable y = var.ecr();
149
150     if(this == y)
151       {
152     return this;
153       }
154     
155     if(rank > y.rank)
156       {
157     y.rep = this;
158
159     merge(y);
160     y.clear();
161
162     return this;
163       }
164
165     rep = y;
166     if(rank == y.rank)
167       {
168     y.rank++;
169       }
170
171     y.merge(this);
172     clear();
173
174     return y;
175   }
176
177   private void clear()
178   {
179     approx = null;
180     type = null;
181     element = null;
182     array = null;
183     parents = null;
184     children = null;
185     ancestors = null;
186     indirectAncestors = null;
187   }
188
189   private void merge(TypeVariable var) throws TypeException
190   {
191     if(depth != 0 || var.depth != 0)
192       {
193     throw new InternalTypingException();
194       }
195
196     // Merge types
197
if(type == null)
198       {
199     type = var.type;
200       }
201     else if(var.type != null)
202       {
203     error("Type Error(1): Attempt to merge two types.");
204       }
205
206     // Merge parents
207
{
208       Set set = new TreeSet(parents);
209       set.addAll(var.parents);
210       set.remove(this);
211       parents = Collections.unmodifiableList(new LinkedList(set));
212     }
213
214     // Merge children
215
{
216       Set set = new TreeSet(children);
217       set.addAll(var.children);
218       set.remove(this);
219       children = Collections.unmodifiableList(new LinkedList(set));
220     }
221   }
222
223   void validate() throws TypeException
224   {
225     if(rep != this)
226       {
227     ecr().validate();
228     return;
229       }
230     
231     // Validate relations.
232
if(type != null)
233       {
234     for(Iterator i = parents.iterator(); i.hasNext();)
235       {
236         TypeVariable parent = ((TypeVariable) i.next()).ecr();
237
238         if(parent.type != null)
239           {
240         if(!type.hasAncestor(parent.type))
241           {
242             if(DEBUG)
243               {
244             G.v().out.println(parent.type + " is not a parent of " + type);
245               }
246
247             error("Type Error(2): Parent type is not a valid ancestor.");
248           }
249           }
250       }
251
252     for(Iterator i = children.iterator(); i.hasNext();)
253       {
254         TypeVariable child = ((TypeVariable) i.next()).ecr();
255
256         if(child.type != null)
257           {
258         if(!type.hasDescendant(child.type))
259           {
260             if(DEBUG)
261               {
262             G.v().out.println(child.type + "(" + child + ") is not a child of " + type + "(" + this + ")");
263               }
264
265             error("Type Error(3): Child type is not a valid descendant.");
266           }
267           }
268       }
269       }
270   }
271   
272   public void removeIndirectRelations()
273   {
274     if(rep != this)
275       {
276     ecr().removeIndirectRelations();
277     return;
278       }
279     
280     if(indirectAncestors == null)
281       {
282     fixAncestors();
283       }
284
285     List parentsToRemove = new LinkedList();
286
287     for( Iterator parentIt = parents.iterator(); parentIt.hasNext(); ) {
288
289         final TypeVariable parent = (TypeVariable) parentIt.next();
290     if(indirectAncestors.get(parent.id()))
291       {
292         parentsToRemove.add(parent);
293       }
294       }
295
296     for( Iterator parentIt = parentsToRemove.iterator(); parentIt.hasNext(); ) {
297
298         final TypeVariable parent = (TypeVariable) parentIt.next();
299
300     removeParent(parent);
301       }
302   }
303   
304   private void fixAncestors()
305   {
306     BitVector ancestors = new BitVector(0);
307     BitVector indirectAncestors = new BitVector(0);
308     for(Iterator i = parents.iterator(); i.hasNext();)
309       {
310     TypeVariable parent = ((TypeVariable) i.next()).ecr();
311
312     if(parent.ancestors == null)
313       {
314         parent.fixAncestors();
315       }
316
317     ancestors.set(parent.id);
318     ancestors.or(parent.ancestors);
319     indirectAncestors.or(parent.ancestors);
320       }
321
322     this.ancestors = ancestors;
323     this.indirectAncestors = indirectAncestors;
324   }
325
326   public int id()
327   {
328     if(rep != this)
329       {
330     return ecr().id();
331       }
332
333     return id;
334   }
335
336   public void addParent(TypeVariable variable)
337   {
338     if(rep != this)
339       {
340     ecr().addParent(variable);
341     return;
342       }
343
344     TypeVariable var = variable.ecr();
345  
346     if(var == this)
347       {
348     return;
349       }
350
351     {
352       Set set = new TreeSet(parents);
353       set.add(var);
354       parents = Collections.unmodifiableList(new LinkedList(set));
355     }
356     
357     {
358       Set set = new TreeSet(var.children);
359       set.add(this);
360       var.children = Collections.unmodifiableList(new LinkedList(set));
361     }
362   }
363
364   public void removeParent(TypeVariable variable)
365   {
366     if(rep != this)
367       {
368     ecr().removeParent(variable);
369     return;
370       }
371
372     TypeVariable var = variable.ecr();
373  
374     {
375       Set set = new TreeSet(parents);
376       set.remove(var);
377       parents = Collections.unmodifiableList(new LinkedList(set));
378     }
379
380     {
381       Set set = new TreeSet(var.children);
382       set.remove(this);
383       var.children = Collections.unmodifiableList(new LinkedList(set));
384     }
385   }
386
387   public void addChild(TypeVariable variable)
388   {
389     if(rep != this)
390       {
391     ecr().addChild(variable);
392     return;
393       }
394
395     TypeVariable var = variable.ecr();
396  
397     if(var == this)
398       {
399     return;
400       }
401
402     {
403       Set set = new TreeSet(children);
404       set.add(var);
405       children = Collections.unmodifiableList(new LinkedList(set));
406     }
407
408     {
409       Set set = new TreeSet(var.parents);
410       set.add(this);
411       var.parents = Collections.unmodifiableList(new LinkedList(set));
412     }
413   }
414
415   public void removeChild(TypeVariable variable)
416   {
417     if(rep != this)
418       {
419     ecr().removeChild(variable);
420     return;
421       }
422
423     TypeVariable var = variable.ecr();
424  
425     {
426       Set set = new TreeSet(children);
427       set.remove(var);
428       children = Collections.unmodifiableList(new LinkedList(set));
429     }
430
431     {
432       Set set = new TreeSet(var.parents);
433       set.remove(this);
434       var.parents = Collections.unmodifiableList(new LinkedList(set));
435     }
436   }
437
438   public int depth()
439   {
440     if(rep != this)
441       {
442     return ecr().depth();
443       }
444
445     return depth;
446   }
447
448   public void makeElement()
449   {
450     if(rep != this)
451       {
452     ecr().makeElement();
453     return;
454       }
455
456     if(element == null)
457       {
458     element = resolver.typeVariable();
459     element.array = this;
460       }
461   }
462
463   public TypeVariable element()
464   {
465     if(rep != this)
466       {
467     return ecr().element();
468       }
469
470     return (element == null) ? null : element.ecr();
471   }
472
473   public TypeVariable array()
474   {
475     if(rep != this)
476       {
477     return ecr().array();
478       }
479
480     return (array == null) ? null : array.ecr();
481   }
482
483   public List parents()
484   {
485     if(rep != this)
486       {
487     return ecr().parents();
488       }
489     
490     return parents;
491   }
492
493   public List children()
494   {
495     if(rep != this)
496       {
497     return ecr().children();
498       }
499     
500     return children;
501   }
502
503   public TypeNode approx()
504   {
505     if(rep != this)
506       {
507     return ecr().approx();
508       }
509
510     return approx;
511   }
512
513   public TypeNode type()
514   {
515     if(rep != this)
516       {
517     return ecr().type();
518       }
519
520     return type;
521   }
522
523   static void error(String JavaDoc message) throws TypeException
524   {
525     try
526       {
527     throw new TypeException(message);
528       }
529     catch(TypeException e)
530       {
531     if(DEBUG)
532       {
533         e.printStackTrace();
534       }
535     throw e;
536       }
537   }
538
539   /** Computes approximative types. The work list must be
540    * initialized with all constant type variables. */

541   public static void computeApprox(TreeSet workList) throws TypeException
542   {
543     while(workList.size() > 0)
544       {
545     TypeVariable var = (TypeVariable) workList.first();
546     workList.remove(var);
547
548     var.fixApprox(workList);
549       }
550   }
551
552   private void fixApprox(TreeSet workList) throws TypeException
553   {
554     if(rep != this)
555       {
556     ecr().fixApprox(workList);
557     return;
558       }
559
560     if(type == null && approx != resolver.hierarchy().NULL)
561       {
562     TypeVariable element = element();
563     
564     if(element != null)
565       {
566         if(!approx.hasElement())
567           {
568         G.v().out.println("*** " + this + " ***");
569         
570         error("Type Error(4)");
571           }
572         
573         TypeNode temp = approx.element();
574         
575         if(element.approx == null)
576           {
577         element.approx = temp;
578         workList.add(element);
579           }
580         else
581           {
582         TypeNode type = element.approx.lca(temp);
583
584         if(type != element.approx)
585           {
586             element.approx = type;
587             workList.add(element);
588           }
589         else if(element.approx != resolver.hierarchy().INT)
590           {
591             type = approx.lca(element.approx.array());
592
593             if(type != approx)
594               {
595             approx = type;
596             workList.add(this);
597               }
598           }
599           }
600       }
601     
602     TypeVariable array = array();
603     
604     if(array != null &&
605        approx != resolver.hierarchy().NULL &&
606        approx != resolver.hierarchy().INT)
607       {
608         TypeNode temp = approx.array();
609         
610         if(array.approx == null)
611           {
612         array.approx = temp;
613         workList.add(array);
614           }
615         else
616           {
617         TypeNode type = array.approx.lca(temp);
618
619         if(type != array.approx)
620           {
621             array.approx = type;
622             workList.add(array);
623           }
624         else
625           {
626             type = approx.lca(array.approx.element());
627
628             if(type != approx)
629               {
630             approx = type;
631             workList.add(this);
632               }
633           }
634           }
635       }
636       }
637     
638     for(Iterator i = parents.iterator(); i.hasNext();)
639       {
640     TypeVariable parent = ((TypeVariable) i.next()).ecr();
641
642     if(parent.approx == null)
643       {
644         parent.approx = approx;
645         workList.add(parent);
646       }
647     else
648       {
649         TypeNode type = parent.approx.lca(approx);
650
651         if(type != parent.approx)
652           {
653         parent.approx = type;
654         workList.add(parent);
655           }
656       }
657       }
658
659     if(type != null)
660       {
661     approx = type;
662       }
663   }
664
665   public void fixDepth() throws TypeException
666   {
667     if(rep != this)
668       {
669     ecr().fixDepth();
670     return;
671       }
672
673     if(type != null)
674       {
675     if(type.type() instanceof ArrayType)
676       {
677         ArrayType at = (ArrayType) type.type();
678
679         depth = at.numDimensions;
680       }
681     else
682       {
683         depth = 0;
684       }
685       }
686     else
687       {
688     if(approx.type() instanceof ArrayType)
689       {
690         ArrayType at = (ArrayType) approx.type();
691
692         depth = at.numDimensions;
693       }
694     else
695       {
696         depth = 0;
697       }
698       }
699
700     // make sure array types have element type
701
if(depth == 0 && element() != null)
702       {
703     error("Type Error(11)");
704       }
705     else if(depth > 0 && element() == null)
706       {
707     makeElement();
708     TypeVariable element = element();
709     element.depth = depth - 1;
710
711     while(element.depth != 0)
712       {
713         element.makeElement();
714         element.element().depth = element.depth - 1;
715         element = element.element();
716       }
717       }
718   }
719
720   public void propagate()
721   {
722     if(rep != this)
723       {
724     ecr().propagate();
725       }
726
727     if(depth == 0)
728       {
729     return;
730       }
731
732     for(Iterator i = parents.iterator(); i.hasNext(); )
733       {
734     TypeVariable var = ((TypeVariable) i.next()).ecr();
735
736     if(var.depth() == depth)
737       {
738         element().addParent(var.element());
739       }
740     else if(var.depth() == 0)
741       {
742         if(var.type() == null) {
743           // hack for J2ME library, reported by Stephen Cheng
744
if (!G.v().isJ2ME) {
745         var.addChild(resolver.typeVariable(resolver.hierarchy().CLONEABLE));
746         var.addChild(resolver.typeVariable(resolver.hierarchy().SERIALIZABLE));
747           }
748         }
749       }
750     else
751       {
752         if(var.type() == null) {
753           // hack for J2ME library, reported by Stephen Cheng
754
if (!G.v().isJ2ME) {
755         var.addChild(resolver.typeVariable(ArrayType.v(RefType.v("java.lang.Cloneable"), var.depth())));
756         var.addChild(resolver.typeVariable(ArrayType.v(RefType.v("java.io.Serializable"), var.depth())));
757           }
758         }
759       }
760       }
761
762     for( Iterator varIt = parents.iterator(); varIt.hasNext(); ) {
763
764         final TypeVariable var = (TypeVariable) varIt.next();
765     removeParent(var);
766       }
767   }
768
769   public String JavaDoc toString()
770   {
771     if(rep != this)
772       {
773     return ecr().toString();
774       }
775     
776     StringBuffer JavaDoc s = new StringBuffer JavaDoc();
777     s.append(",[parents:");
778
779     {
780       boolean comma = false;
781       
782       for(Iterator i = parents.iterator(); i.hasNext(); )
783     {
784       if(comma)
785         {
786           s.append(",");
787         }
788       else
789         {
790           comma = true;
791         }
792       s.append(((TypeVariable) i.next()).id());
793     }
794     }
795     
796     s.append("],[children:");
797
798     {
799       boolean comma = false;
800       
801       for(Iterator i = children.iterator(); i.hasNext(); )
802     {
803       if(comma)
804         {
805           s.append(",");
806         }
807       else
808         {
809           comma = true;
810         }
811       s.append(((TypeVariable) i.next()).id());
812     }
813     }
814     
815     s.append("]");
816     return "[id:" + id + ",depth:" + depth + ((type != null) ? (",type:" + type) : "") + ",approx:" + approx + s +
817       (element == null ? "" : ",arrayof:" + element.id()) + "]";
818   }
819
820   public void fixParents()
821   {
822     if(rep != this)
823       {
824     ecr().fixParents();
825     return;
826       }
827
828     {
829       Set set = new TreeSet(parents);
830       parents = Collections.unmodifiableList(new LinkedList(set));
831     }
832   }
833
834   public void fixChildren()
835   {
836     if(rep != this)
837       {
838     ecr().fixChildren();
839     return;
840       }
841
842     {
843       Set set = new TreeSet(children);
844       children = Collections.unmodifiableList(new LinkedList(set));
845     }
846   }
847
848 }
849
Popular Tags