1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu)
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the Free
9 * Software Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21package proguard.evaluation;
22
23import proguard.evaluation.value.Value;
24
25/**
26 * This Stack saves additional information with stack elements, to keep track
27 * of their origins.
28 * <p>
29 * The stack stores a given producer Value along with each Value it stores.
30 * It then generalizes a given collected Value with the producer Value
31 * of each Value it loads. The producer Value and the initial collected Value
32 * can be set. The generalized collected Value can be retrieved, either taking
33 * into account dup/swap instructions as proper instructions or ignoring them.
34 *
35 * @author Eric Lafortune
36 */
37public class TracedStack extends Stack
38{
39    private Value producerValue;
40    private Stack producerStack;
41    private Stack actualProducerStack;
42
43
44    /**
45     * Creates a new TracedStack with a given maximum size.
46     */
47    public TracedStack(int maxSize)
48    {
49        super(maxSize);
50
51        producerStack       = new Stack(maxSize);
52        actualProducerStack = new Stack(maxSize);
53    }
54
55
56    /**
57     * Creates a new TracedStack that is a copy of the given TracedStack.
58     */
59    public TracedStack(TracedStack tracedStack)
60    {
61        super(tracedStack);
62
63        producerStack       = new Stack(tracedStack.producerStack);
64        actualProducerStack = new Stack(tracedStack.actualProducerStack);
65    }
66
67
68    /**
69     * Sets the Value that will be stored along with all push and pop
70     * instructions.
71     */
72    public void setProducerValue(Value producerValue)
73    {
74        this.producerValue = producerValue;
75    }
76
77
78    /**
79     * Gets the specified producer Value from the stack, without disturbing it.
80     * @param index the index of the stack element, counting from the bottom
81     *              of the stack.
82     * @return the producer value at the specified position.
83     */
84    public Value getBottomProducerValue(int index)
85    {
86        return producerStack.getBottom(index);
87    }
88
89
90    /**
91     * Gets the specified actual producer Value from the stack, ignoring
92     * dup/swap instructions, without disturbing it.
93     * @param index the index of the stack element, counting from the bottom
94     *              of the stack.
95     * @return the producer value at the specified position.
96     */
97    public Value getBottomActualProducerValue(int index)
98    {
99        return actualProducerStack.getBottom(index);
100    }
101
102
103    /**
104     * Gets the specified producer Value from the stack, without disturbing it.
105     * @param index the index of the stack element, counting from the top
106     *              of the stack.
107     * @return the producer value at the specified position.
108     */
109    public Value getTopProducerValue(int index)
110    {
111        return producerStack.getTop(index);
112    }
113
114
115    /**
116     * Gets the specified actual producer Value from the stack, ignoring
117     * dup/swap instructions, without disturbing it.
118     * @param index the index of the stack element, counting from the top
119     *              of the stack.
120     * @return the producer value at the specified position.
121     */
122    public Value getTopActualProducerValue(int index)
123    {
124        return actualProducerStack.getTop(index);
125    }
126
127
128    // Implementations for Stack.
129
130    public void reset(int size)
131    {
132        super.reset(size);
133
134        producerStack.reset(size);
135        actualProducerStack.reset(size);
136    }
137
138    public void copy(TracedStack other)
139    {
140        super.copy(other);
141
142        producerStack.copy(other.producerStack);
143        actualProducerStack.copy(other.actualProducerStack);
144    }
145
146    public boolean generalize(TracedStack other)
147    {
148        return
149            super.generalize(other) |
150            producerStack.generalize(other.producerStack) |
151            actualProducerStack.generalize(other.actualProducerStack);
152    }
153
154    public void clear()
155    {
156        super.clear();
157
158        producerStack.clear();
159        actualProducerStack.clear();
160    }
161
162    public void removeTop(int index)
163    {
164        super.removeTop(index);
165
166        producerStack.removeTop(index);
167        actualProducerStack.removeTop(index);
168    }
169
170    public void push(Value value)
171    {
172        super.push(value);
173
174        producerPush();
175
176        // Account for the extra space required by Category 2 values.
177        if (value.isCategory2())
178        {
179            producerPush();
180        }
181    }
182
183    public Value pop()
184    {
185        Value value = super.pop();
186
187        producerPop();
188
189        // Account for the extra space required by Category 2 values.
190        if (value.isCategory2())
191        {
192            producerPop();
193        }
194
195        return value;
196    }
197
198    public void pop1()
199    {
200        super.pop1();
201
202        producerPop();
203    }
204
205    public void pop2()
206    {
207        super.pop2();
208
209        producerPop();
210        producerPop();
211    }
212
213    public void dup()
214    {
215        super.dup();
216
217        producerStack.pop();
218        producerStack.push(producerValue);
219        producerStack.push(producerValue);
220
221        actualProducerStack.dup();
222    }
223
224    public void dup_x1()
225    {
226        super.dup_x1();
227
228        producerStack.pop();
229        producerStack.pop();
230        producerStack.push(producerValue);
231        producerStack.push(producerValue);
232        producerStack.push(producerValue);
233
234        actualProducerStack.dup_x1();
235    }
236
237    public void dup_x2()
238    {
239        super.dup_x2();
240
241        producerStack.pop();
242        producerStack.pop();
243        producerStack.pop();
244        producerStack.push(producerValue);
245        producerStack.push(producerValue);
246        producerStack.push(producerValue);
247        producerStack.push(producerValue);
248
249        actualProducerStack.dup_x2();
250    }
251
252    public void dup2()
253    {
254        super.dup2();
255
256        producerStack.pop();
257        producerStack.pop();
258        producerStack.push(producerValue);
259        producerStack.push(producerValue);
260        producerStack.push(producerValue);
261        producerStack.push(producerValue);
262
263        actualProducerStack.dup2();
264    }
265
266    public void dup2_x1()
267    {
268        super.dup2_x1();
269
270        producerStack.pop();
271        producerStack.pop();
272        producerStack.pop();
273        producerStack.push(producerValue);
274        producerStack.push(producerValue);
275        producerStack.push(producerValue);
276        producerStack.push(producerValue);
277        producerStack.push(producerValue);
278
279        actualProducerStack.dup2_x1();
280    }
281
282    public void dup2_x2()
283    {
284        super.dup2_x2();
285
286        producerStack.pop();
287        producerStack.pop();
288        producerStack.pop();
289        producerStack.pop();
290        producerStack.push(producerValue);
291        producerStack.push(producerValue);
292        producerStack.push(producerValue);
293        producerStack.push(producerValue);
294        producerStack.push(producerValue);
295        producerStack.push(producerValue);
296
297        actualProducerStack.dup2_x2();
298    }
299
300    public void swap()
301    {
302        super.swap();
303
304        producerStack.pop();
305        producerStack.pop();
306        producerStack.push(producerValue);
307        producerStack.push(producerValue);
308
309        actualProducerStack.swap();
310    }
311
312
313    // Implementations for Object.
314
315    public boolean equals(Object object)
316    {
317        if (object == null ||
318            this.getClass() != object.getClass())
319        {
320            return false;
321        }
322
323        TracedStack other = (TracedStack)object;
324
325        return super.equals(object) &&
326               this.producerStack.equals(other.producerStack) &&
327               this.actualProducerStack.equals(other.actualProducerStack);
328    }
329
330
331    public int hashCode()
332    {
333        return super.hashCode()         ^
334               producerStack.hashCode() ^
335               actualProducerStack.hashCode();
336    }
337
338
339    public String toString()
340    {
341        StringBuffer buffer = new StringBuffer();
342
343        for (int index = 0; index < this.size(); index++)
344        {
345            Value value               = this.values[index];
346            Value producerValue       = producerStack.getBottom(index);
347            Value actualProducerValue = actualProducerStack.getBottom(index);
348            buffer = buffer.append('[')
349                           .append(producerValue == null ? "empty:" :
350                                                           producerValue.equals(actualProducerValue) ? producerValue.toString() :
351                                                                                                       producerValue.toString() + actualProducerValue.toString())
352                           .append(value         == null ? "empty"  : value.toString())
353                           .append(']');
354        }
355
356        return buffer.toString();
357    }
358
359
360    // Small utility methods.
361
362    private void producerPush()
363    {
364        producerStack.push(producerValue);
365        actualProducerStack.push(producerValue);
366    }
367
368
369    private void producerPop()
370    {
371        producerStack.pop();
372        actualProducerStack.pop();
373    }
374}
375