1/*
2 * Javassist, a Java-bytecode translator toolkit.
3 * Copyright (C) 1999-2007 Shigeru Chiba, and others. All Rights Reserved.
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License.  Alternatively, the contents of this file may be used under
8 * the terms of the GNU Lesser General Public License Version 2.1 or later.
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 */
15package javassist.bytecode.analysis;
16
17import java.util.HashMap;
18import java.util.Iterator;
19import java.util.Map;
20
21import javassist.CtClass;
22
23/**
24 * MultiType represents an unresolved type. Whenever two <literal>Type</literal>
25 * instances are merged, if they share more than one super type (either an
26 * interface or a superclass), then a <literal>MultiType</literal> is used to
27 * represent the possible super types. The goal of a <literal>MultiType</literal>
28 * is to reduce the set of possible types down to a single resolved type. This
29 * is done by eliminating non-assignable types from the typeset when the
30 * <literal>MultiType</literal> is passed as an argument to
31 * {@link Type#isAssignableFrom(Type)}, as well as removing non-intersecting
32 * types during a merge.
33 *
34 * Note: Currently the <litera>MultiType</literal> instance is reused as much
35 * as possible so that updates are visible from all frames. In addition, all
36 * <literal>MultiType</literal> merge paths are also updated. This is somewhat
37 * hackish, but it appears to handle most scenarios.
38 *
39 * @author Jason T. Greene
40 */
41
42/* TODO - A better, but more involved, approach would be to track the instruction
43 * offset that resulted in the creation of this type, and
44 * whenever the typeset changes, to force a merge on that position. This
45 * would require creating a new MultiType instance every time the typeset
46 * changes, and somehow communicating assignment changes to the Analyzer
47 */
48public class MultiType extends Type {
49    private Map interfaces;
50    private Type resolved;
51    private Type potentialClass;
52    private MultiType mergeSource;
53    private boolean changed = false;
54
55    public MultiType(Map interfaces) {
56        this(interfaces, null);
57    }
58
59    public MultiType(Map interfaces, Type potentialClass) {
60        super(null);
61        this.interfaces = interfaces;
62        this.potentialClass = potentialClass;
63    }
64
65    /**
66     * Gets the class that corresponds with this type. If this information
67     * is not yet known, java.lang.Object will be returned.
68     */
69    public CtClass getCtClass() {
70        if (resolved != null)
71            return resolved.getCtClass();
72
73        return Type.OBJECT.getCtClass();
74    }
75
76    /**
77     * Always returns null since this type is never used for an array.
78     */
79    public Type getComponent() {
80        return null;
81    }
82
83    /**
84     * Always returns 1, since this type is a reference.
85     */
86    public int getSize() {
87        return 1;
88    }
89
90    /**
91     * Always reutnrs false since this type is never used for an array
92     */
93    public boolean isArray() {
94        return false;
95    }
96
97    /**
98     * Returns true if the internal state has changed.
99     */
100    boolean popChanged() {
101        boolean changed = this.changed;
102        this.changed = false;
103        return changed;
104    }
105
106    public boolean isAssignableFrom(Type type) {
107        throw new UnsupportedOperationException("Not implemented");
108    }
109
110    public boolean isAssignableTo(Type type) {
111        if (resolved != null)
112            return type.isAssignableFrom(resolved);
113
114        if (Type.OBJECT.equals(type))
115            return true;
116
117        if (potentialClass != null && !type.isAssignableFrom(potentialClass))
118            potentialClass = null;
119
120        Map map = mergeMultiAndSingle(this, type);
121
122        if (map.size() == 1 && potentialClass == null) {
123            // Update previous merge paths to the same resolved type
124            resolved = Type.get((CtClass)map.values().iterator().next());
125            propogateResolved();
126
127            return true;
128        }
129
130        // Keep all previous merge paths up to date
131        if (map.size() >= 1) {
132            interfaces = map;
133            propogateState();
134
135            return true;
136        }
137
138        if (potentialClass != null) {
139            resolved = potentialClass;
140            propogateResolved();
141
142            return true;
143        }
144
145        return false;
146    }
147
148    private void propogateState() {
149        MultiType source = mergeSource;
150        while (source != null) {
151            source.interfaces = interfaces;
152            source.potentialClass = potentialClass;
153            source = source.mergeSource;
154        }
155    }
156
157    private void propogateResolved() {
158        MultiType source = mergeSource;
159        while (source != null) {
160            source.resolved = resolved;
161            source = source.mergeSource;
162        }
163    }
164
165    /**
166     * Always returns true, since this type is always a reference.
167     *
168     * @return true
169     */
170    public boolean isReference() {
171       return true;
172    }
173
174    private Map getAllMultiInterfaces(MultiType type) {
175        Map map = new HashMap();
176
177        Iterator iter = type.interfaces.values().iterator();
178        while (iter.hasNext()) {
179            CtClass intf = (CtClass)iter.next();
180            map.put(intf.getName(), intf);
181            getAllInterfaces(intf, map);
182        }
183
184        return map;
185    }
186
187
188    private Map mergeMultiInterfaces(MultiType type1, MultiType type2) {
189        Map map1 = getAllMultiInterfaces(type1);
190        Map map2 = getAllMultiInterfaces(type2);
191
192        return findCommonInterfaces(map1, map2);
193    }
194
195    private Map mergeMultiAndSingle(MultiType multi, Type single) {
196        Map map1 = getAllMultiInterfaces(multi);
197        Map map2 = getAllInterfaces(single.getCtClass(), null);
198
199        return findCommonInterfaces(map1, map2);
200    }
201
202    private boolean inMergeSource(MultiType source) {
203        while (source != null) {
204            if (source == this)
205                return true;
206
207            source = source.mergeSource;
208        }
209
210        return false;
211    }
212
213    public Type merge(Type type) {
214        if (this == type)
215            return this;
216
217        if (type == UNINIT)
218            return this;
219
220        if (type == BOGUS)
221            return BOGUS;
222
223        if (type == null)
224            return this;
225
226        if (resolved != null)
227            return resolved.merge(type);
228
229        if (potentialClass != null) {
230            Type mergePotential = potentialClass.merge(type);
231            if (! mergePotential.equals(potentialClass) || mergePotential.popChanged()) {
232                potentialClass = Type.OBJECT.equals(mergePotential) ? null : mergePotential;
233                changed = true;
234            }
235        }
236
237        Map merged;
238
239        if (type instanceof MultiType) {
240            MultiType multi = (MultiType)type;
241
242            if (multi.resolved != null) {
243                merged = mergeMultiAndSingle(this, multi.resolved);
244            } else {
245                merged = mergeMultiInterfaces(multi, this);
246                if (! inMergeSource(multi))
247                    mergeSource = multi;
248            }
249        } else {
250            merged = mergeMultiAndSingle(this, type);
251        }
252
253        // Keep all previous merge paths up to date
254        if (merged.size() > 1 || (merged.size() == 1 && potentialClass != null)) {
255            // Check for changes
256            if (merged.size() != interfaces.size()) {
257                changed = true;
258            } else if (changed == false){
259                Iterator iter = merged.keySet().iterator();
260                while (iter.hasNext())
261                    if (! interfaces.containsKey(iter.next()))
262                        changed = true;
263            }
264
265            interfaces = merged;
266            propogateState();
267
268            return this;
269        }
270
271        if (merged.size() == 1) {
272            resolved = Type.get((CtClass) merged.values().iterator().next());
273        } else if (potentialClass != null){
274            resolved = potentialClass;
275        } else {
276            resolved = OBJECT;
277        }
278
279        propogateResolved();
280
281        return resolved;
282    }
283
284    public boolean equals(Object o) {
285        if (! (o instanceof MultiType))
286            return false;
287
288        MultiType multi = (MultiType) o;
289        if (resolved != null)
290            return resolved.equals(multi.resolved);
291        else if (multi.resolved != null)
292            return false;
293
294        return interfaces.keySet().equals(multi.interfaces.keySet());
295    }
296
297    public String toString() {
298        if (resolved != null)
299            return resolved.toString();
300
301        StringBuffer buffer = new StringBuffer("{");
302        Iterator iter = interfaces.keySet().iterator();
303        while (iter.hasNext()) {
304            buffer.append(iter.next());
305            buffer.append(", ");
306        }
307        buffer.setLength(buffer.length() - 2);
308        if (potentialClass != null)
309            buffer.append(", *").append(potentialClass.toString());
310        buffer.append("}");
311        return buffer.toString();
312    }
313}
314