Stack


1   /*
2    * ProGuard -- shrinking, optimization, obfuscation, and preverification
3    *             of Java bytecode.
4    *
5    * Copyright (c) 2002-2007 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   */
21  package proguard.evaluation;
22  
23  import proguard.evaluation.value.*;
24  
25  /**
26   * This class represents an operand stack that contains <code>Value</code>
27   * objects.
28   *
29   * @author Eric Lafortune
30   */
31  public class Stack
32  {
33      private static final TopValue TOP_VALUE = new TopValue();
34  
35  
36      protected Value[] values;
37      protected int     currentSize;
38      protected int     actualMaxSize;
39  
40  
41      /**
42       * Creates a new Stack with a given maximum size, accounting for the double
43       * space required by Category 2 values.
44       */
45      public Stack(int maxSize)
46      {
47          values = new Value[maxSize];
48      }
49  
50  
51      /**
52       * Creates a Stack that is a copy of the given Stack.
53       */
54      public Stack(Stack stack)
55      {
56          // Create the values array.
57          this(stack.values.length);
58  
59          // Copy the stack contents.
60          copy(stack);
61      }
62  
63  
64      /**
65       * Returns the actual maximum stack size that was required for all stack
66       * operations, accounting for the double space required by Category 2 values.
67       */
68      public int getActualMaxSize()
69      {
70          return actualMaxSize;
71      }
72  
73  
74      /**
75       * Resets this Stack, so that it can be reused.
76       */
77      public void reset(int maxSize)
78      {
79          // Is the values array large enough?
80          if (maxSize > values.length)
81          {
82              // Create a new one.
83              values = new Value[maxSize];
84          }
85  
86          // Clear the sizes.
87          clear();
88  
89          actualMaxSize = 0;
90      }
91  
92  
93      /**
94       * Copies the values of the given Stack into this Stack.
95       */
96      public void copy(Stack other)
97      {
98          // Is the values array large enough?
99          if (other.values.length > values.length)
100         {
101             // Create a new one.
102             values = new Value[other.values.length];
103         }
104 
105         // Copy the stack contents.
106         System.arraycopy(other.values, 0, this.values, 0, other.currentSize);
107 
108         // Copy the sizes.
109         currentSize   = other.currentSize;
110         actualMaxSize = other.actualMaxSize;
111     }
112 
113 
114     /**
115      * Generalizes the values of this Stack with the values of the given Stack.
116      * The stacks must have the same current sizes.
117      * @return whether the generalization has made any difference.
118      */
119     public boolean generalize(Stack other)
120     {
121         if (this.currentSize != other.currentSize)
122         {
123             throw new IllegalArgumentException  ("Stacks have different current sizes ["+this.currentSize+"] and ["+other.currentSize+"]");
124         }
125 
126         boolean changed = false;
127 
128         // Generalize the stack values.
129         for (int index = 0; index < currentSize; index++)
130         {
131             Value thisValue  = this.values[index];
132 
133             if (thisValue != null)
134             {
135                 Value newValue = null;
136 
137                 Value otherValue = other.values[index];
138 
139                 if (otherValue != null)
140                 {
141                     newValue = thisValue.generalize(otherValue);
142                 }
143 
144                 changed = changed || !thisValue.equals(newValue);
145 
146                 values[index] = newValue;
147             }
148         }
149 
150         // Check if the other stack extends beyond this one.
151         if (this.actualMaxSize < other.actualMaxSize)
152         {
153             this.actualMaxSize = other.actualMaxSize;
154         }
155 
156         return changed;
157     }
158 
159 
160     /**
161      * Clears the stack.
162      */
163     public void clear()
164     {
165         // Clear the stack contents.
166         for (int index = 0; index < currentSize; index++)
167         {
168             values[index] = null;
169         }
170 
171         currentSize = 0;
172     }
173 
174 
175     /**
176      * Returns the number of elements currently on the stack, accounting for the
177      * double space required by Category 2 values.
178      */
179     public int size()
180     {
181         return currentSize;
182     }
183 
184 
185     /**
186      * Gets the specified Value from the stack, without disturbing it.
187      * @param index the index of the stack element, counting from the bottom
188      *              of the stack.
189      * @return the value at the specified position.
190      */
191     public Value getBottom(int index)
192     {
193         return values[index];
194     }
195 
196 
197     /**
198      * Sets the specified Value on the stack, without disturbing it.
199      * @param index the index of the stack element, counting from the bottom
200      *              of the stack.
201      * @param value the value to set.
202      */
203     public void setBottom(int index, Value value)
204     {
205         values[index] = value;
206     }
207 
208 
209     /**
210      * Gets the specified Value from the stack, without disturbing it.
211      * @param index the index of the stack element, counting from the top
212      *              of the stack.
213      * @return the value at the specified position.
214      */
215     public Value getTop(int index)
216     {
217         return values[currentSize - index - 1];
218     }
219 
220 
221     /**
222      * Sets the specified Value on the stack, without disturbing it.
223      * @param index the index of the stack element, counting from the top
224      *              of the stack.
225      * @param value the value to set.
226      */
227     public void setTop(int index, Value value)
228     {
229         values[currentSize - index - 1] = value;
230     }
231 
232 
233     /**
234      * Removes the specified Value from the stack.
235      * @param index the index of the stack element, counting from the top
236      *              of the stack.
237      */
238     public void removeTop(int index)
239     {
240         System.arraycopy(values, currentSize - index,
241                          values, currentSize - index - 1,
242                          index);
243         currentSize--;
244     }
245 
246 
247     /**
248      * Pushes the given Value onto the stack.
249      */
250     public void push(Value value)
251     {
252         // Account for the extra space required by Category 2 values.
253         if (value.isCategory2())
254         {
255             values[currentSize++] = TOP_VALUE;
256         }
257 
258         // Push the value.
259         values[currentSize++] = value;
260 
261         // Update the maximum actual size;
262         if (actualMaxSize < currentSize)
263         {
264             actualMaxSize = currentSize;
265         }
266     }
267 
268 
269     /**
270      * Pops the top Value from the stack.
271      */
272     public Value pop()
273     {
274         Value value = values[--currentSize];
275 
276         values[currentSize] = null;
277 
278         // Account for the extra space required by Category 2 values.
279         if (value.isCategory2())
280         {
281             values[--currentSize] = null;
282         }
283 
284         return value;
285     }
286 
287 
288     // Pop methods that provide convenient casts to the expected value types.
289 
290     /**
291      * Pops the top IntegerValue from the stack.
292      */
293     public IntegerValue ipop()
294     {
295         return pop().integerValue();
296     }
297 
298 
299     /**
300      * Pops the top LongValue from the stack.
301      */
302     public LongValue lpop()
303     {
304         return pop().longValue();
305     }
306 
307 
308     /**
309      * Pops the top FloatValue from the stack.
310      */
311     public FloatValue fpop()
312     {
313         return pop().floatValue();
314     }
315 
316 
317     /**
318      * Pops the top DoubleValue from the stack.
319      */
320     public DoubleValue dpop()
321     {
322         return pop().doubleValue();
323     }
324 
325 
326     /**
327      * Pops the top ReferenceValue from the stack.
328      */
329     public ReferenceValue apop()
330     {
331         return pop().referenceValue();
332     }
333 
334 
335     /**
336      * Pops the top InstructionOffsetValue from the stack.
337      */
338     public InstructionOffsetValue opop()
339     {
340         return pop().instructionOffsetValue();
341     }
342 
343 
344     /**
345      * Pops the top category 1 value from the stack.
346      */
347     public void pop1()
348     {
349         values[--currentSize] = null;
350     }
351 
352 
353     /**
354      * Pops the top category 2 value from the stack (or alternatively, two
355      * Category 1 stack elements).
356      */
357     public void pop2()
358     {
359         values[--currentSize] = null;
360         values[--currentSize] = null;
361     }
362 
363 
364     /**
365      * Duplicates the top Category 1 value.
366      */
367     public void dup()
368     {
369         values[currentSize] = values[currentSize - 1].category1Value();
370 
371         currentSize++;
372 
373         // Update the maximum actual size;
374         if (actualMaxSize < currentSize)
375         {
376             actualMaxSize = currentSize;
377         }
378     }
379 
380 
381     /**
382      * Duplicates the top Category 1 value, one Category 1 element down the
383      * stack.
384      */
385     public void dup_x1()
386     {
387         values[currentSize]     = values[currentSize - 1].category1Value();
388         values[currentSize - 1] = values[currentSize - 2].category1Value();
389         values[currentSize - 2] = values[currentSize    ];
390 
391         currentSize++;
392 
393         // Update the maximum actual size;
394         if (actualMaxSize < currentSize)
395         {
396             actualMaxSize = currentSize;
397         }
398     }
399 
400 
401     /**
402      * Duplicates the top Category 1 value, two Category 1 elements (or one
403      * Category 2 element) down the stack.
404      */
405     public void dup_x2()
406     {
407         values[currentSize]     = values[currentSize - 1].category1Value();
408         values[currentSize - 1] = values[currentSize - 2];
409         values[currentSize - 2] = values[currentSize - 3];
410         values[currentSize - 3] = values[currentSize    ];
411 
412         currentSize++;
413 
414         // Update the maximum actual size;
415         if (actualMaxSize < currentSize)
416         {
417             actualMaxSize = currentSize;
418         }
419     }
420 
421     /**
422      * Duplicates the top Category 2 value (or alternatively, the equivalent
423      * Category 1 stack elements).
424      */
425     public void dup2()
426     {
427         values[currentSize    ] = values[currentSize - 2];
428         values[currentSize + 1] = values[currentSize - 1];
429 
430         currentSize += 2;
431 
432         // Update the maximum actual size;
433         if (actualMaxSize < currentSize)
434         {
435             actualMaxSize = currentSize;
436         }
437     }
438 
439 
440     /**
441      * Duplicates the top Category 2 value, one Category 1 element down the
442      * stack (or alternatively, the equivalent Category 1 stack values).
443      */
444     public void dup2_x1()
445     {
446         values[currentSize + 1] = values[currentSize - 1];
447         values[currentSize    ] = values[currentSize - 2];
448         values[currentSize - 1] = values[currentSize - 3];
449         values[currentSize - 2] = values[currentSize + 1];
450         values[currentSize - 3] = values[currentSize    ];
451 
452         currentSize += 2;
453 
454         // Update the maximum actual size;
455         if (actualMaxSize < currentSize)
456         {
457             actualMaxSize = currentSize;
458         }
459     }
460 
461 
462     /**
463      * Duplicates the top Category 2 value, one Category 2 stack element down
464      * the stack (or alternatively, the equivalent Category 1 stack values).
465      */
466     public void dup2_x2()
467     {
468         values[currentSize + 1] = values[currentSize - 1];
469         values[currentSize    ] = values[currentSize - 2];
470         values[currentSize - 1] = values[currentSize - 3];
471         values[currentSize - 2] = values[currentSize - 4];
472         values[currentSize - 3] = values[currentSize + 1];
473         values[currentSize - 4] = values[currentSize    ];
474 
475         currentSize += 2;
476 
477         // Update the maximum actual size;
478         if (actualMaxSize < currentSize)
479         {
480             actualMaxSize = currentSize;
481         }
482     }
483 
484 
485     /**
486      * Swaps the top two Category 1 values.
487      */
488     public void swap()
489     {
490         Value value1 = values[currentSize - 1].category1Value();
491         Value value2 = values[currentSize - 2].category1Value();
492 
493         values[currentSize - 1] = value2;
494         values[currentSize - 2] = value1;
495     }
496 
497 
498     // Implementations for Object.
499 
500     public boolean equals(Object   object)
501     {
502         if (object == null ||
503             this.getClass() != object.getClass())
504         {
505             return false;
506         }
507 
508         Stack other = (Stack)object;
509 
510         if (this.currentSize != other.currentSize)
511         {
512             return false;
513         }
514 
515         for (int index = 0; index < currentSize; index++)
516         {
517             Value thisValue  = this.values[index];
518             Value otherValue = other.values[index];
519             if (thisValue == null ? otherValue != null :
520                                     !thisValue.equals(otherValue))
521             {
522                 return false;
523             }
524         }
525 
526         return true;
527     }
528 
529 
530     public int hashCode()
531     {
532         int hashCode = currentSize;
533 
534         for (int index = 0; index < currentSize; index++)
535         {
536             Value value = values[index];
537             if (value != null)
538             {
539                 hashCode ^= value.hashCode();
540             }
541         }
542 
543         return hashCode;
544     }
545 
546 
547     public String   toString()
548     {
549         StringBuffer   buffer = new StringBuffer  ();
550 
551         for (int index = 0; index < currentSize; index++)
552         {
553             Value value = values[index];
554             buffer = buffer.append('[')
555                            .append(value == null ? "empty" : value.toString())
556                            .append(']');
557         }
558 
559         return buffer.toString();
560     }
561 }
562
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags