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.code;
18
19import com.android.dx.util.MutabilityControl;
20import com.android.dx.rop.cst.CstUtf8;
21
22/**
23 * Set of {@link RegisterSpec} instances, where a given register number
24 * may appear only once in the set.
25 */
26public final class RegisterSpecSet
27        extends MutabilityControl {
28    /** {@code non-null;} no-element instance */
29    public static final RegisterSpecSet EMPTY = new RegisterSpecSet(0);
30
31    /**
32     * {@code non-null;} array of register specs, where each element is
33     * {@code null} or is an instance whose {@code reg}
34     * matches the array index
35     */
36    private final RegisterSpec[] specs;
37
38    /** {@code >= -1;} size of the set or {@code -1} if not yet calculated */
39    private int size;
40
41    /**
42     * Constructs an instance. The instance is initially empty.
43     *
44     * @param maxSize {@code >= 0;} the maximum register number (exclusive) that
45     * may be represented in this instance
46     */
47    public RegisterSpecSet(int maxSize) {
48        super(maxSize != 0);
49
50        this.specs = new RegisterSpec[maxSize];
51        this.size = 0;
52    }
53
54    /** {@inheritDoc} */
55    @Override
56    public boolean equals(Object other) {
57        if (!(other instanceof RegisterSpecSet)) {
58            return false;
59        }
60
61        RegisterSpecSet otherSet = (RegisterSpecSet) other;
62        RegisterSpec[] otherSpecs = otherSet.specs;
63        int len = specs.length;
64
65        if ((len != otherSpecs.length) || (size() != otherSet.size())) {
66            return false;
67        }
68
69        for (int i = 0; i < len; i++) {
70            RegisterSpec s1 = specs[i];
71            RegisterSpec s2 = otherSpecs[i];
72
73            if (s1 == s2) {
74                continue;
75            }
76
77            if ((s1 == null) || !s1.equals(s2)) {
78                return false;
79            }
80        }
81
82        return true;
83    }
84
85    /** {@inheritDoc} */
86    @Override
87    public int hashCode() {
88        int len = specs.length;
89        int hash = 0;
90
91        for (int i = 0; i < len; i++) {
92            RegisterSpec spec = specs[i];
93            int oneHash = (spec == null) ? 0 : spec.hashCode();
94            hash = (hash * 31) + oneHash;
95        }
96
97        return hash;
98    }
99
100    /** {@inheritDoc} */
101    @Override
102    public String toString() {
103        int len = specs.length;
104        StringBuffer sb = new StringBuffer(len * 25);
105
106        sb.append('{');
107
108        boolean any = false;
109        for (int i = 0; i < len; i++) {
110            RegisterSpec spec = specs[i];
111            if (spec != null) {
112                if (any) {
113                    sb.append(", ");
114                } else {
115                    any = true;
116                }
117                sb.append(spec);
118            }
119        }
120
121        sb.append('}');
122        return sb.toString();
123    }
124
125    /**
126     * Gets the maximum number of registers that may be in this instance, which
127     * is also the maximum-plus-one of register numbers that may be
128     * represented.
129     *
130     * @return {@code >= 0;} the maximum size
131     */
132    public int getMaxSize() {
133        return specs.length;
134    }
135
136    /**
137     * Gets the current size of this instance.
138     *
139     * @return {@code >= 0;} the size
140     */
141    public int size() {
142        int result = size;
143
144        if (result < 0) {
145            int len = specs.length;
146
147            result = 0;
148            for (int i = 0; i < len; i++) {
149                if (specs[i] != null) {
150                    result++;
151                }
152            }
153
154            size = result;
155        }
156
157        return result;
158    }
159
160    /**
161     * Gets the element with the given register number, if any.
162     *
163     * @param reg {@code >= 0;} the desired register number
164     * @return {@code null-ok;} the element with the given register number or
165     * {@code null} if there is none
166     */
167    public RegisterSpec get(int reg) {
168        try {
169            return specs[reg];
170        } catch (ArrayIndexOutOfBoundsException ex) {
171            // Translate the exception.
172            throw new IllegalArgumentException("bogus reg");
173        }
174    }
175
176    /**
177     * Gets the element with the same register number as the given
178     * spec, if any. This is just a convenient shorthand for
179     * {@code get(spec.getReg())}.
180     *
181     * @param spec {@code non-null;} spec with the desired register number
182     * @return {@code null-ok;} the element with the matching register number or
183     * {@code null} if there is none
184     */
185    public RegisterSpec get(RegisterSpec spec) {
186        return get(spec.getReg());
187    }
188
189    /**
190     * Returns the spec in this set that's currently associated with a
191     * given local (type, name, and signature), or {@code null} if there is
192     * none. This ignores the register number of the given spec but
193     * matches on everything else.
194     *
195     * @param spec {@code non-null;} local to look for
196     * @return {@code null-ok;} first register found that matches, if any
197     */
198    public RegisterSpec findMatchingLocal(RegisterSpec spec) {
199        int length = specs.length;
200
201        for (int reg = 0; reg < length; reg++) {
202            RegisterSpec s = specs[reg];
203
204            if (s == null) {
205                continue;
206            }
207
208            if (spec.matchesVariable(s)) {
209                return s;
210            }
211        }
212
213        return null;
214    }
215
216    /**
217     * Returns the spec in this set that's currently associated with a given
218     * local (name and signature), or {@code null} if there is none.
219     *
220     * @param local {@code non-null;} local item to search for
221     * @return {@code null-ok;} first register found with matching name and signature
222     */
223    public RegisterSpec localItemToSpec(LocalItem local) {
224        int length = specs.length;
225
226        for (int reg = 0; reg < length; reg++) {
227            RegisterSpec spec = specs[reg];
228
229            if ((spec != null) && local.equals(spec.getLocalItem())) {
230                return spec;
231            }
232        }
233
234        return null;
235    }
236
237    /**
238     * Removes a spec from the set. Only the register number
239     * of the parameter is significant.
240     *
241     * @param toRemove {@code non-null;} register to remove.
242     */
243    public void remove(RegisterSpec toRemove) {
244        try {
245            specs[toRemove.getReg()] = null;
246            size = -1;
247        } catch (ArrayIndexOutOfBoundsException ex) {
248            // Translate the exception.
249            throw new IllegalArgumentException("bogus reg");
250        }
251    }
252
253    /**
254     * Puts the given spec into the set. If there is already an element in
255     * the set with the same register number, it is replaced. Additionally,
256     * if the previous element is for a category-2 register, then that
257     * previous element is nullified. Finally, if the given spec is for
258     * a category-2 register, then the immediately subsequent element
259     * is nullified.
260     *
261     * @param spec {@code non-null;} the register spec to put in the instance
262     */
263    public void put(RegisterSpec spec) {
264        throwIfImmutable();
265
266        if (spec == null) {
267            throw new NullPointerException("spec == null");
268        }
269
270        size = -1;
271
272        try {
273            int reg = spec.getReg();
274            specs[reg] = spec;
275
276            if (reg > 0) {
277                int prevReg = reg - 1;
278                RegisterSpec prevSpec = specs[prevReg];
279                if ((prevSpec != null) && (prevSpec.getCategory() == 2)) {
280                    specs[prevReg] = null;
281                }
282            }
283
284            if (spec.getCategory() == 2) {
285                specs[reg + 1] = null;
286            }
287        } catch (ArrayIndexOutOfBoundsException ex) {
288            // Translate the exception.
289            throw new IllegalArgumentException("spec.getReg() out of range");
290        }
291    }
292
293    /**
294     * Put the entire contents of the given set into this one.
295     *
296     * @param set {@code non-null;} the set to put into this instance
297     */
298    public void putAll(RegisterSpecSet set) {
299        int max = set.getMaxSize();
300
301        for (int i = 0; i < max; i++) {
302            RegisterSpec spec = set.get(i);
303            if (spec != null) {
304                put(spec);
305            }
306        }
307    }
308
309    /**
310     * Intersects this instance with the given one, modifying this
311     * instance. The intersection consists of the pairwise
312     * {@link RegisterSpec#intersect} of corresponding elements from
313     * this instance and the given one where both are non-null.
314     *
315     * @param other {@code non-null;} set to intersect with
316     * @param localPrimary whether local variables are primary to
317     * the intersection; if {@code true}, then the only non-null
318     * result elements occur when registers being intersected have
319     * equal names (or both have {@code null} names)
320     */
321    public void intersect(RegisterSpecSet other, boolean localPrimary) {
322        throwIfImmutable();
323
324        RegisterSpec[] otherSpecs = other.specs;
325        int thisLen = specs.length;
326        int len = Math.min(thisLen, otherSpecs.length);
327
328        size = -1;
329
330        for (int i = 0; i < len; i++) {
331            RegisterSpec spec = specs[i];
332
333            if (spec == null) {
334                continue;
335            }
336
337            RegisterSpec intersection =
338                spec.intersect(otherSpecs[i], localPrimary);
339            if (intersection != spec) {
340                specs[i] = intersection;
341            }
342        }
343
344        for (int i = len; i < thisLen; i++) {
345            specs[i] = null;
346        }
347    }
348
349    /**
350     * Returns an instance that is identical to this one, except that
351     * all register numbers are offset by the given amount. Mutability
352     * of the result is inherited from the original.
353     *
354     * @param delta the amount to offset the register numbers by
355     * @return {@code non-null;} an appropriately-constructed instance
356     */
357    public RegisterSpecSet withOffset(int delta) {
358        int len = specs.length;
359        RegisterSpecSet result = new RegisterSpecSet(len + delta);
360
361        for (int i = 0; i < len; i++) {
362            RegisterSpec spec = specs[i];
363            if (spec != null) {
364                result.put(spec.withOffset(delta));
365            }
366        }
367
368        result.size = size;
369
370        if (isImmutable()) {
371            result.setImmutable();
372        }
373
374        return result;
375    }
376
377    /**
378     * Makes and return a mutable copy of this instance.
379     *
380     * @return {@code non-null;} the mutable copy
381     */
382    public RegisterSpecSet mutableCopy() {
383        int len = specs.length;
384        RegisterSpecSet copy = new RegisterSpecSet(len);
385
386        for (int i = 0; i < len; i++) {
387            RegisterSpec spec = specs[i];
388            if (spec != null) {
389                copy.put(spec);
390            }
391        }
392
393        copy.size = size;
394
395        return copy;
396    }
397}
398