1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.rop.type;
18
19import com.android.dx.command.dexer.Main;
20import java.util.concurrent.ConcurrentHashMap;
21import java.util.concurrent.ConcurrentMap;
22
23/**
24 * Representation of a method descriptor. Instances of this class are
25 * generally interned and may be usefully compared with each other
26 * using {@code ==}.
27 */
28public final class Prototype implements Comparable<Prototype> {
29    /**
30     * Intern table for instances.
31     *
32     * <p>The initial capacity is based on a medium-size project.
33     */
34    private static final ConcurrentMap<String, Prototype> internTable =
35            new ConcurrentHashMap<>(10_000, 0.75f, Main.CONCURRENCY_LEVEL);
36
37    /** {@code non-null;} method descriptor */
38    private final String descriptor;
39
40    /** {@code non-null;} return type */
41    private final Type returnType;
42
43    /** {@code non-null;} list of parameter types */
44    private final StdTypeList parameterTypes;
45
46    /** {@code null-ok;} list of parameter frame types, if calculated */
47    private StdTypeList parameterFrameTypes;
48
49    /**
50     * Returns the unique instance corresponding to the
51     * given method descriptor. See vmspec-2 sec4.3.3 for details on the
52     * field descriptor syntax.
53     *
54     * @param descriptor {@code non-null;} the descriptor
55     * @return {@code non-null;} the corresponding instance
56     * @throws IllegalArgumentException thrown if the descriptor has
57     * invalid syntax
58     */
59    public static Prototype intern(String descriptor) {
60        if (descriptor == null) {
61            throw new NullPointerException("descriptor == null");
62        }
63
64        Prototype result = internTable.get(descriptor);
65        if (result != null) {
66            return result;
67        }
68
69        result = fromDescriptor(descriptor);
70        return putIntern(result);
71    }
72
73    /**
74     * Returns a prototype for a method descriptor.
75     *
76     * The {@code Prototype} returned will be the interned value if present,
77     * or a new instance otherwise. If a new instance is created, it is not
78     * placed in the intern table.
79     *
80     * @param descriptor {@code non-null;} the descriptor
81     * @return {@code non-null;} the corresponding instance
82     * @throws IllegalArgumentException thrown if the descriptor has
83     * invalid syntax
84     */
85    public static Prototype fromDescriptor(String descriptor) {
86        Prototype result = internTable.get(descriptor);
87        if (result != null) {
88            return result;
89        }
90
91        Type[] params = makeParameterArray(descriptor);
92        int paramCount = 0;
93        int at = 1;
94
95        for (;;) {
96            int startAt = at;
97            char c = descriptor.charAt(at);
98            if (c == ')') {
99                at++;
100                break;
101            }
102
103            // Skip array markers.
104            while (c == '[') {
105                at++;
106                c = descriptor.charAt(at);
107            }
108
109            if (c == 'L') {
110                // It looks like the start of a class name; find the end.
111                int endAt = descriptor.indexOf(';', at);
112                if (endAt == -1) {
113                    throw new IllegalArgumentException("bad descriptor");
114                }
115                at = endAt + 1;
116            } else {
117                at++;
118            }
119
120            params[paramCount] =
121                Type.intern(descriptor.substring(startAt, at));
122            paramCount++;
123        }
124
125        Type returnType = Type.internReturnType(descriptor.substring(at));
126        StdTypeList parameterTypes = new StdTypeList(paramCount);
127
128        for (int i = 0; i < paramCount; i++) {
129            parameterTypes.set(i, params[i]);
130        }
131
132        return new Prototype(descriptor, returnType, parameterTypes);
133    }
134
135    public static void clearInternTable() {
136        internTable.clear();
137    }
138
139    /**
140     * Helper for {@link #intern} which returns an empty array to
141     * populate with parsed parameter types, and which also ensures
142     * that there is a '(' at the start of the descriptor and a
143     * single ')' somewhere before the end.
144     *
145     * @param descriptor {@code non-null;} the descriptor string
146     * @return {@code non-null;} array large enough to hold all parsed parameter
147     * types, but which is likely actually larger than needed
148     */
149    private static Type[] makeParameterArray(String descriptor) {
150        int length = descriptor.length();
151
152        if (descriptor.charAt(0) != '(') {
153            throw new IllegalArgumentException("bad descriptor");
154        }
155
156        /*
157         * This is a cheesy way to establish an upper bound on the
158         * number of parameters: Just count capital letters.
159         */
160        int closeAt = 0;
161        int maxParams = 0;
162        for (int i = 1; i < length; i++) {
163            char c = descriptor.charAt(i);
164            if (c == ')') {
165                closeAt = i;
166                break;
167            }
168            if ((c >= 'A') && (c <= 'Z')) {
169                maxParams++;
170            }
171        }
172
173        if ((closeAt == 0) || (closeAt == (length - 1))) {
174            throw new IllegalArgumentException("bad descriptor");
175        }
176
177        if (descriptor.indexOf(')', closeAt + 1) != -1) {
178            throw new IllegalArgumentException("bad descriptor");
179        }
180
181        return new Type[maxParams];
182    }
183
184    /**
185     * Interns an instance, adding to the descriptor as necessary based
186     * on the given definer, name, and flags. For example, an init
187     * method has an uninitialized object of type {@code definer}
188     * as its first argument.
189     *
190     * @param descriptor {@code non-null;} the descriptor string
191     * @param definer {@code non-null;} class the method is defined on
192     * @param isStatic whether this is a static method
193     * @param isInit whether this is an init method
194     * @return {@code non-null;} the interned instance
195     */
196    public static Prototype intern(String descriptor, Type definer,
197            boolean isStatic, boolean isInit) {
198        Prototype base = intern(descriptor);
199
200        if (isStatic) {
201            return base;
202        }
203
204        if (isInit) {
205            definer = definer.asUninitialized(Integer.MAX_VALUE);
206        }
207
208        return base.withFirstParameter(definer);
209    }
210
211    /**
212     * Interns an instance which consists of the given number of
213     * {@code int}s along with the given return type
214     *
215     * @param returnType {@code non-null;} the return type
216     * @param count {@code > 0;} the number of elements in the prototype
217     * @return {@code non-null;} the interned instance
218     */
219    public static Prototype internInts(Type returnType, int count) {
220        // Make the descriptor...
221
222        StringBuffer sb = new StringBuffer(100);
223
224        sb.append('(');
225
226        for (int i = 0; i < count; i++) {
227            sb.append('I');
228        }
229
230        sb.append(')');
231        sb.append(returnType.getDescriptor());
232
233        // ...and intern it.
234        return intern(sb.toString());
235    }
236
237    /**
238     * Constructs an instance. This is a private constructor; use one
239     * of the public static methods to get instances.
240     *
241     * @param descriptor {@code non-null;} the descriptor string
242     */
243    private Prototype(String descriptor, Type returnType,
244            StdTypeList parameterTypes) {
245        if (descriptor == null) {
246            throw new NullPointerException("descriptor == null");
247        }
248
249        if (returnType == null) {
250            throw new NullPointerException("returnType == null");
251        }
252
253        if (parameterTypes == null) {
254            throw new NullPointerException("parameterTypes == null");
255        }
256
257        this.descriptor = descriptor;
258        this.returnType = returnType;
259        this.parameterTypes = parameterTypes;
260        this.parameterFrameTypes = null;
261    }
262
263    /** {@inheritDoc} */
264    @Override
265    public boolean equals(Object other) {
266        if (this == other) {
267            /*
268             * Since externally-visible instances are interned, this
269             * check helps weed out some easy cases.
270             */
271            return true;
272        }
273
274        if (!(other instanceof Prototype)) {
275            return false;
276        }
277
278        return descriptor.equals(((Prototype) other).descriptor);
279    }
280
281    /** {@inheritDoc} */
282    @Override
283    public int hashCode() {
284        return descriptor.hashCode();
285    }
286
287    /** {@inheritDoc} */
288    @Override
289    public int compareTo(Prototype other) {
290        if (this == other) {
291            return 0;
292        }
293
294        /*
295         * The return type is the major order, and then args in order,
296         * and then the shorter list comes first (similar to string
297         * sorting).
298         */
299
300        int result = returnType.compareTo(other.returnType);
301
302        if (result != 0) {
303            return result;
304        }
305
306        int thisSize = parameterTypes.size();
307        int otherSize = other.parameterTypes.size();
308        int size = Math.min(thisSize, otherSize);
309
310        for (int i = 0; i < size; i++) {
311            Type thisType = parameterTypes.get(i);
312            Type otherType = other.parameterTypes.get(i);
313
314            result = thisType.compareTo(otherType);
315
316            if (result != 0) {
317                return result;
318            }
319        }
320
321        if (thisSize < otherSize) {
322            return -1;
323        } else if (thisSize > otherSize) {
324            return 1;
325        } else {
326            return 0;
327        }
328    }
329
330    /** {@inheritDoc} */
331    @Override
332    public String toString() {
333        return descriptor;
334    }
335
336    /**
337     * Gets the descriptor string.
338     *
339     * @return {@code non-null;} the descriptor
340     */
341    public String getDescriptor() {
342        return descriptor;
343    }
344
345    /**
346     * Gets the return type.
347     *
348     * @return {@code non-null;} the return type
349     */
350    public Type getReturnType() {
351        return returnType;
352    }
353
354    /**
355     * Gets the list of parameter types.
356     *
357     * @return {@code non-null;} the list of parameter types
358     */
359    public StdTypeList getParameterTypes() {
360        return parameterTypes;
361    }
362
363    /**
364     * Gets the list of frame types corresponding to the list of parameter
365     * types. The difference between the two lists (if any) is that all
366     * "intlike" types (see {@link Type#isIntlike}) are replaced by
367     * {@link Type#INT}.
368     *
369     * @return {@code non-null;} the list of parameter frame types
370     */
371    public StdTypeList getParameterFrameTypes() {
372        if (parameterFrameTypes == null) {
373            int sz = parameterTypes.size();
374            StdTypeList list = new StdTypeList(sz);
375            boolean any = false;
376            for (int i = 0; i < sz; i++) {
377                Type one = parameterTypes.get(i);
378                if (one.isIntlike()) {
379                    any = true;
380                    one = Type.INT;
381                }
382                list.set(i, one);
383            }
384            parameterFrameTypes = any ? list : parameterTypes;
385        }
386
387        return parameterFrameTypes;
388    }
389
390    /**
391     * Returns a new interned instance, which is the same as this instance,
392     * except that it has an additional parameter prepended to the original's
393     * argument list.
394     *
395     * @param param {@code non-null;} the new first parameter
396     * @return {@code non-null;} an appropriately-constructed instance
397     */
398    public Prototype withFirstParameter(Type param) {
399        String newDesc = "(" + param.getDescriptor() + descriptor.substring(1);
400        StdTypeList newParams = parameterTypes.withFirst(param);
401
402        newParams.setImmutable();
403
404        Prototype result =
405            new Prototype(newDesc, returnType, newParams);
406
407        return putIntern(result);
408    }
409
410    /**
411     * Puts the given instance in the intern table if it's not already
412     * there. If a conflicting value is already in the table, then leave it.
413     * Return the interned value.
414     *
415     * @param desc {@code non-null;} instance to make interned
416     * @return {@code non-null;} the actual interned object
417     */
418    private static Prototype putIntern(Prototype desc) {
419        Prototype result = internTable.putIfAbsent(desc.getDescriptor(), desc);
420        return result != null ? result : desc;
421    }
422}
423