View Javadoc

1   /*
2    $Id: ExpressionStack.java,v 1.3 2004/04/30 09:57:46 cpoirier Exp $
3   
4    Copyright 2003 (C) James Strachan and Bob Mcwhirter. All Rights Reserved.
5   
6    Redistribution and use of this software and associated documentation
7    ("Software"), with or without modification, are permitted provided
8    that the following conditions are met:
9   
10   1. Redistributions of source code must retain copyright
11      statements and notices.  Redistributions must also contain a
12      copy of this document.
13  
14   2. Redistributions in binary form must reproduce the
15      above copyright notice, this list of conditions and the
16      following disclaimer in the documentation and/or other
17      materials provided with the distribution.
18  
19   3. The name "groovy" must not be used to endorse or promote
20      products derived from this Software without prior written
21      permission of The Codehaus.  For written permission,
22      please contact info@codehaus.org.
23  
24   4. Products derived from this Software may not be called "groovy"
25      nor may "groovy" appear in their names without prior written
26      permission of The Codehaus. "groovy" is a registered
27      trademark of The Codehaus.
28  
29   5. Due credit should be given to The Codehaus -
30      http://groovy.codehaus.org/
31  
32   THIS SOFTWARE IS PROVIDED BY THE CODEHAUS AND CONTRIBUTORS
33   ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
34   NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
35   FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
36   THE CODEHAUS OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
37   INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
38   (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
39   SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40   HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41   STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42   ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
43   OF THE POSSIBILITY OF SUCH DAMAGE.
44  
45   */
46  
47  package org.codehaus.groovy.syntax.parser;
48  
49  import java.util.ArrayList;
50  
51  import org.codehaus.groovy.control.CompilationFailedException;
52  import org.codehaus.groovy.syntax.*;
53  import org.codehaus.groovy.GroovyBugError;
54  
55  
56  
57  /***
58   *  A combination stack and helper class for parsing groovy expression.
59   *  <p>
60   *  Expressions are a little trickier to parse than the statements above.
61   *  As a result, we are now doing a hybrid LL/LR parse at the expression
62   *  level.
63   *
64   *  @author <a href="mailto:cpoirier@dreaming.org">Chris Poirier</a>
65   */
66  
67  public class ExpressionStack
68  {
69      private ArrayList stack  = new ArrayList();
70      private Parser    parser = null;
71      private int       open   = 0;
72  
73  
74      ExpressionStack( Parser context )
75      {
76          this.parser = context;
77      }
78  
79  
80  
81    //---------------------------------------------------------------------------
82    // PRIMARY OPERATIONS
83  
84  
85     /***
86      *  Returns true if the stack is empty.
87      */
88  
89      boolean isEmpty()
90      {
91          return stack.isEmpty();
92      }
93  
94  
95  
96     /***
97      *  Returns true if the stack is in a state that can be considered
98      *  a complete expression, provided lookahead is amenable, of course.
99      */
100 
101     public boolean isComplete()
102     {
103         return size() == 1 && topIsAnExpression();
104     }
105 
106 
107 
108    /***
109     *  Returns true if the stack can be completed without further shifts.
110     *  Used by Parser.la(ExpressionStack) to determine when ambiguous tokens
111     *  can't be read across a newline.  The algorithm will guess true if it
112     *  isn't sure.  If it returns false, you can rely on that analysis.
113     */
114 
115     public boolean canComplete()
116     {
117         //
118         // We can immediately return false if there is anything
119         // open or if the top is not an expression...
120 
121         if( open > 0 || !topIsAnExpression() )
122         {
123             return false;
124         }
125 
126 
127         //
128         // If it is complete, it can complete...
129 
130         if( size() == 1 )
131         {
132             return true;
133         }
134 
135 
136         //
137         // For everything else, we guess true.  It is most likely
138         // the case, because of the way the parser moves complex
139         // stuff off to LL routines and validates the ordering of
140         // nodes pushed on the stack, that if the top is an expression,
141         // and nothing is "open" (ie. unmatched parenthesis, early
142         // stage ternary operators), the stack can be reduced back
143         // to the root without further shifts.  Our guarantee is
144         // that our guess true might be wrong, but that we will only
145         // return false when we are sure, so, no harm done...
146 
147         return true;
148     }
149 
150 
151 
152    /***
153     *  Returns the number of elements in the stack.
154     */
155 
156     int size()
157     {
158         return stack.size();
159     }
160 
161 
162 
163    /***
164     *  Pushes a node onto the stack.
165     */
166 
167     void push( CSTNode node )
168     {
169         if( (node.isA(Types.LEFT_PARENTHESIS) || node.isA(Types.QUESTION)) && node.size() == 1 )
170         {
171             open++;
172         }
173 
174         stack.add( node );
175     }
176 
177 
178 
179    /***
180     *  Pops the node from the top of the stack.
181     */
182 
183     CSTNode pop()
184     {
185         CSTNode node = (CSTNode)stack.remove( stack.size() - 1 );
186 
187         if( (node.isA(Types.LEFT_PARENTHESIS) || node.isA(Types.QUESTION)) && node.size() == 1 )
188         {
189             open--;
190         }
191 
192         return node;
193     }
194 
195 
196 
197    /***
198     *  Returns the top node from the stack without removing it.
199     */
200 
201     CSTNode top()
202     {
203         return top(0);
204     }
205 
206 
207 
208    /***
209     *  Returns some node from the stack.  <code>offset</code> is counted
210     *  from the top of the stack.
211     */
212 
213     CSTNode top( int offset )
214     {
215         if( offset < stack.size() )
216         {
217             return (CSTNode)stack.get( stack.size() - 1 - offset );
218         }
219         else
220         {
221             return Token.NULL;
222         }
223     }
224 
225 
226 
227 
228   //---------------------------------------------------------------------------
229   // PARSER OPERATIONS
230 
231 
232    /***
233     *  Shifts some number of (non-newline) tokens from the stream to the top
234     *  of the stack.  They are pushed in order.
235     */
236 
237     void shift( int count ) throws SyntaxException, CompilationFailedException
238     {
239         for( int i = 0; i < count; i++ )
240         {
241             push( parser.consume() );
242         }
243     }
244 
245 
246 
247    /***
248     *  Shifts a token from the stream to the top of the stack.
249     */
250 
251     void shift() throws SyntaxException, CompilationFailedException
252     {
253         push( parser.consume() );
254     }
255 
256 
257 
258    /***
259     *  Performs a reduce by taking some number of <code>CSTNode</code>s
260     *  from the top of the stack, and making one of them a
261     *  <code>Reduction</code> with the others as children, then pushes
262     *  that new node back onto the stack.
263     */
264 
265     void reduce( int count, int rootOffset, boolean mark )
266     {
267         if( count <= rootOffset || rootOffset < 0 || count > size() )
268         {
269             throw new GroovyBugError( "error in call to ExpressionStack.reduce(): count=" + count + ", rootOffset=" + rootOffset );
270         }
271 
272         CSTNode   root     = null;
273         CSTNode[] children = new CSTNode[count-1];
274 
275         for( int child = count - 2, element = 0; element < count; element++ )
276         {
277             if( element == rootOffset )
278             {
279                 root = pop();
280             }
281             else
282             {
283                 children[child--] = pop();
284             }
285         }
286 
287         root = root.asReduction();
288         for( int i = 0; i < children.length; i++ )
289         {
290             root.add( children[i] );
291         }
292 
293         if( mark )
294         {
295             root.markAsExpression();
296         }
297 
298         push( root );
299 
300     }
301 
302 
303 
304 
305   //---------------------------------------------------------------------------
306   // TESTS
307 
308 
309    /***
310     *  Return true if the stack is at the start of an expression.  True if
311     *  either the stack is empty or the top token is a left parenthesis.
312     */
313 
314     boolean atStartOfExpression()
315     {
316         return isEmpty() || (top().isA(Types.LEFT_PARENTHESIS) && !top().hasChildren());
317     }
318 
319 
320 
321    /***
322     *  Returns true if the top element of the stack is an operator.
323     */
324 
325     boolean topIsAnOperator( )
326     {
327         return ExpressionSupport.isAnOperator( top(), false );
328     }
329 
330 
331 
332    /***
333     *  Returns true if the element at the specified offset from the top
334     *  of the stack is an operator.
335     */
336 
337     boolean topIsAnOperator( int offset, boolean unknownReturns )
338     {
339         return ExpressionSupport.isAnOperator( top(offset), unknownReturns );
340     }
341 
342 
343 
344    /***
345     *  Returns true if the top element of the stack is a modifiable expression.
346     */
347 
348     boolean topIsAModifiableExpression()
349     {
350         return ExpressionSupport.isAModifiableExpression( top() );
351     }
352 
353 
354 
355    /***
356     *  Returns true if the top element of the stack is an expression.
357     */
358 
359     boolean topIsAnExpression( )
360     {
361         return top().isAnExpression();
362     }
363 
364 
365 
366   //---------------------------------------------------------------------------
367   // SUGAR
368 
369 
370    /***
371     *  Shifts if the specified flag is true, reports an error otherwise.
372     */
373 
374     void shiftIf( boolean flag, String error ) throws SyntaxException, CompilationFailedException
375     {
376         if( flag )
377         {
378             push( parser.consume() );
379         }
380         else
381         {
382             parser.error( error );
383         }
384     }
385 
386 
387 
388    /***
389     *  Shifts unless the specified flag is true, reports an error otherwise.
390     */
391 
392     void shiftUnless( boolean flag, String error ) throws SyntaxException, CompilationFailedException
393     {
394         if( flag )
395         {
396             parser.error( error );
397         }
398         else
399         {
400             push( parser.consume() );
401         }
402     }
403 
404 
405 
406    /***
407     *  Shifts if the top of the stack is an expression, reports an error
408     *  otherwise.
409     */
410 
411     void shiftIfTopIsAnExpression( String error ) throws SyntaxException, CompilationFailedException
412     {
413         shiftIf( ExpressionSupport.isAnExpression(top(), false), error );
414     }
415 
416 
417 
418    /***
419     *  Shifts if the top of the stack is a operator, reports an
420     *  error otherwise.
421     */
422 
423     void shiftIfTopIsAnOperator( String error ) throws SyntaxException, CompilationFailedException
424     {
425         shiftIf( ExpressionSupport.isAnOperator(top(), false), error );
426     }
427 
428 
429 
430    /***
431     *  Shifts unless the top of the stack is an expression, reports an
432     *  error otherwise.
433     */
434 
435     void shiftUnlessTopIsAnExpression( String error ) throws SyntaxException, CompilationFailedException
436     {
437         shiftUnless( ExpressionSupport.isAnExpression(top(), false), error );
438     }
439 
440 
441 
442    /***
443     *  Shifts unless the top of the stack is an operator, reports an
444     *  error otherwise.
445     */
446 
447     void shiftUnlessTopIsAnOperator( String error ) throws SyntaxException, CompilationFailedException
448     {
449         shiftUnless( ExpressionSupport.isAnOperator(top(), false), error );
450     }
451 
452 
453 
454 
455   //---------------------------------------------------------------------------
456   // OUTPUT
457 
458 
459    /***
460     *  Creates a string representation of the stack.
461     */
462 
463     public String toString( )
464     {
465         StringBuffer buffer = new StringBuffer();
466         String newline = System.getProperty( "line.separator", "\n" );
467         int count = stack.size();
468 
469         buffer.append( "ExpressionStack with " ).append( size() ).append( " elements" ).append( newline );
470         for( int i = count - 1; i >= 0; i-- )
471         {
472             buffer.append( top(i).toString() ).append( newline );
473         }
474 
475         return buffer.toString();
476     }
477 
478 }