StringFormulaParser


1   /*********************************************************************
2   *
3   *      Copyright (C) 2002 Andrew Khan
4   *
5   * This library is free software; you can redistribute it and/or
6   * modify it under the terms of the GNU Lesser General Public
7   * License as published by the Free Software Foundation; either
8   * version 2.1 of the License, or (at your option) any later version.
9   *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  ***************************************************************************/
19  
20  package jxl.biff.formula;
21  
22  import java.util.ArrayList  ;
23  import java.util.Iterator  ;
24  import java.util.Stack  ;
25  import java.io.StringReader  ;
26  import java.io.IOException  ;
27  
28  import common.Assert;
29  import common.Logger;
30  
31  import jxl.Cell;
32  import jxl.WorkbookSettings;
33  import jxl.biff.WorkbookMethods;
34  
35  /**
36   * Parses a string formula into a parse tree
37   */
38  class StringFormulaParser implements Parser
39  {
40    /**
41     * The logger
42     */
43    private static Logger logger = Logger.getLogger(StringFormulaParser.class);
44  
45    /**
46     * The formula string passed to this object
47     */
48    private String   formula;
49  
50    /**
51     * The parsed formula string, as retrieved from the parse tree
52     */
53    private String   parsedFormula;
54  
55    /**
56     * The parse tree
57     */
58    private ParseItem root;
59  
60    /**
61     * The stack argument used when parsing a function in order to
62     * pass multiple arguments back to the calling method
63     */
64    private Stack   arguments;
65  
66    /**
67     * The workbook settings
68     */
69    private WorkbookSettings settings;
70  
71    /**
72     * A handle to the external sheet
73     */
74    private ExternalSheet externalSheet;
75  
76    /**
77     * A handle to the name table
78     */
79    private WorkbookMethods nameTable;
80  
81    /**
82     * Constructor
83     * @param f
84     * @param ws
85     */
86    public StringFormulaParser(String   f, ExternalSheet es, WorkbookMethods nt, 
87                               WorkbookSettings ws)
88    {
89      formula = f;
90      settings = ws;
91      externalSheet = es;
92      nameTable = nt;
93    }
94  
95    /**
96     * Parses the list of tokens
97     *
98     * @exception FormulaException
99     */
100   public void parse() throws FormulaException
101   {
102     ArrayList   tokens = getTokens();
103     
104     Iterator   i = tokens.iterator();
105     
106     root = parseCurrent(i);
107   }
108 
109   /**
110    * Recursively parses the token array.  Recursion is used in order
111    * to evaluate parentheses and function arguments
112    *
113    * @param i an iterator of tokens
114    * @return the root node of the current parse stack
115    * @exception FormulaException if an error occurs
116    */
117   private ParseItem parseCurrent(Iterator   i) throws FormulaException
118   {
119     Stack   stack = new Stack  ();
120     Stack   operators = new Stack  ();
121     Stack   args = null; // we usually don't need this
122 
123     boolean parenthesesClosed = false;
124     ParseItem lastParseItem = null;
125     
126     while (i.hasNext() && !parenthesesClosed)
127     {
128       ParseItem pi = (ParseItem) i.next();
129 
130       if (pi instanceof Operand)
131       {
132         handleOperand((Operand) pi, stack);
133       }
134       else if (pi instanceof StringFunction)
135       {
136         handleFunction((StringFunction) pi, i, stack);
137       }
138       else if (pi instanceof Operator)
139       {
140         Operator op = (Operator) pi;
141 
142         // See if the operator is a binary or unary operator
143         // It is a unary operator either if the stack is empty, or if
144         // the last thing off the stack was another operator
145         if (op instanceof StringOperator)
146         {
147           StringOperator sop = (StringOperator) op;
148           if (stack.isEmpty() || lastParseItem instanceof Operator)
149           {
150             op = sop.getUnaryOperator();
151           }
152           else
153           {
154             op = sop.getBinaryOperator();
155           }
156         }
157 
158         if (operators.empty())
159         {
160           // nothing much going on, so do nothing for the time being
161           operators.push(op);
162         }
163         else
164         {
165           Operator operator = (Operator) operators.peek();
166 
167           // If the latest operator has a higher precedence then add to the 
168           // operator stack and wait
169           if (op.getPrecedence() < operator.getPrecedence())
170           {
171             operators.push(op);
172           }
173           else
174           {
175             // The operator is a lower precedence so we can sort out
176             // some of the items on the stack
177             operators.pop(); // remove the operator from the stack
178             operator.getOperands(stack);
179             stack.push(operator);
180             operators.push(op);
181           }
182         }
183       }
184       else if (pi instanceof ArgumentSeparator)
185       {
186         // Clean up any remaining items on this stack
187         while (!operators.isEmpty())
188         {
189           Operator o = (Operator) operators.pop();
190           o.getOperands(stack);
191           stack.push(o);
192         }
193         
194         // Add it to the argument stack.  Create the argument stack
195         // if necessary.  Items will be stored on the argument stack in
196         // reverse order
197         if (args == null)
198         {
199           args = new Stack  ();
200         }
201 
202         args.push(stack.pop());
203         stack.clear();
204       }
205       else if (pi instanceof OpenParentheses)
206       {
207         ParseItem pi2 = parseCurrent(i);
208         Parenthesis p = new Parenthesis();
209         pi2.setParent(p);
210         p.add(pi2);
211         stack.push(p);
212       }
213       else if (pi instanceof CloseParentheses)
214       {
215         parenthesesClosed = true;
216       }
217       
218       lastParseItem = pi;
219     }
220     
221     while (!operators.isEmpty())
222     {
223       Operator o = (Operator) operators.pop();
224       o.getOperands(stack);
225       stack.push(o);
226     }
227 
228     ParseItem rt = !stack.empty()? (ParseItem) stack.pop():null;
229 
230     // if the agument stack is not null, then add it to that stack
231     // as well for good measure
232     if (args != null && rt != null)
233     {
234       args.push(rt);
235     }
236 
237     arguments = args;
238 
239     if (!stack.empty() || !operators.empty() )
240     {
241       logger.warn("Formula " + formula + 
242                   " has a non-empty parse stack");
243     }
244 
245     return rt;
246   }
247 
248   /**
249    * Gets the list of lexical tokens using the generated lexical analyzer
250    *
251    * @return the list of tokens
252    * @exception FormulaException if an error occurs
253    */
254   private ArrayList   getTokens() throws FormulaException
255   {
256     ArrayList   tokens = new ArrayList  ();
257 
258     StringReader   sr = new StringReader  (formula);
259     Yylex lex = new Yylex(sr);
260     lex.setExternalSheet(externalSheet);
261     lex.setNameTable(nameTable);
262     try
263     {
264       ParseItem pi = lex.yylex();
265       while (pi != null)
266       {
267         tokens.add(pi);
268         pi = lex.yylex();
269       }
270     }
271     catch (IOException   e)
272     {
273       logger.warn(e.toString());
274     }
275     catch (Error   e)
276     {
277       throw new FormulaException(FormulaException.lexicalError,
278                                  formula + " at char  " + lex.getPos());
279     }
280       
281     return tokens;
282   }
283 
284   /**
285    * Gets the formula as a string.  Uses the parse tree to do this, and
286    * does not simply return whatever string was passed in
287    */
288   public String   getFormula()
289   {
290     if (parsedFormula == null)
291     {
292       StringBuffer   sb = new StringBuffer  ();
293       root.getString(sb);
294       parsedFormula = sb.toString();
295     }
296 
297     return parsedFormula;
298   }
299 
300   /**
301    * Gets the bytes for the formula
302    *
303    * @return the bytes in RPN
304    */
305   public byte[] getBytes()
306   {
307     byte[] bytes = root.getBytes();
308     
309     if (root.isVolatile())
310     {
311       byte[] newBytes = new byte[bytes.length + 4];
312       System.arraycopy(bytes, 0, newBytes, 4, bytes.length);
313       newBytes[0] = Token.ATTRIBUTE.getCode();
314       newBytes[1] = (byte) 0x1;
315       bytes = newBytes;
316     }
317 
318     return bytes;
319   }
320 
321   /**
322    * Handles the case when parsing a string when a token is a function
323    *
324    * @param sf the string function
325    * @param i  the token iterator
326    * @param stack the parse tree stack
327    * @exception FormulaException if an error occurs
328    */
329   private void handleFunction(StringFunction sf, Iterator   i, 
330                               Stack   stack)
331     throws FormulaException
332   {
333     ParseItem pi2 = parseCurrent(i); 
334 
335     // If the function is unknown, then throw an error
336     if (sf.getFunction(settings) == Function.UNKNOWN)
337     {
338       throw new FormulaException(FormulaException.unrecognizedFunction);
339     }
340 
341     // First check for possible optimized functions and possible
342     // use of the Attribute token
343     if (sf.getFunction(settings) == Function.SUM && arguments == null)
344     {
345       // this is handled by an attribute
346       Attribute a = new Attribute(sf, settings);
347       a.add(pi2);
348       stack.push(a);
349       return;
350     }
351 
352     if (sf.getFunction(settings) == Function.IF)
353     {
354       // this is handled by an attribute
355       Attribute a = new Attribute(sf, settings);
356           
357       // Add in the if conditions as a var arg function in
358       // the correct order
359       VariableArgFunction vaf = new VariableArgFunction(settings);
360       int numargs = arguments.size();
361       for (int j = 0 ; j < numargs; j++)
362       {
363         ParseItem pi3 = (ParseItem) arguments.get(j);
364         vaf.add(pi3);
365       }
366           
367       a.setIfConditions(vaf);
368       stack.push(a);
369       return;
370     }
371 
372     // Function cannot be optimized.  See if it is a variable argument 
373     // function or not
374     if (sf.getFunction(settings).getNumArgs() == 0xff)
375     {
376       // If the arg stack has not been initialized, it means
377       // that there was only one argument, which is the
378       // returned parse item
379       if (arguments == null)
380       {
381         VariableArgFunction vaf = new VariableArgFunction
382           (sf.getFunction(settings), 1, settings);
383         vaf.add(pi2);
384         stack.push(vaf);
385       }
386       else
387       {
388         // Add the args to the function in the correct order
389         int numargs = arguments.size();
390         VariableArgFunction vaf = new VariableArgFunction
391           (sf.getFunction(settings), numargs, settings);
392         
393         ParseItem[] args = new ParseItem[numargs];
394         for (int j = 0 ; j < numargs; j++)
395         {
396           ParseItem pi3 = (ParseItem) arguments.pop();
397           args[numargs-j-1] = pi3;
398         }
399 
400         for (int j = 0 ; j < args.length ; j++)
401         {
402           vaf.add(args[j]);
403         }
404         stack.push(vaf);
405         arguments.clear();
406         arguments = null;
407       }
408       return;
409     }
410 
411     // Function is a standard built in function
412     BuiltInFunction bif = new BuiltInFunction(sf.getFunction(settings), 
413                                               settings);
414       
415     int numargs = sf.getFunction(settings).getNumArgs();
416     if (numargs == 1)
417     {
418       // only one item which is the returned ParseItem
419       bif.add(pi2);
420     }
421     else
422     {
423       if ((arguments == null && numargs != 0) ||
424           (arguments != null && numargs != arguments.size()))
425       {
426         throw new FormulaException(FormulaException.incorrectArguments);
427       }
428       // multiple arguments so go to the arguments stack.  
429       // Unlike the variable argument function, the args are
430       // stored in reverse order
431       for (int j = 0; j < numargs ; j++)
432       {
433         ParseItem pi3 = (ParseItem) arguments.get(j);
434         bif.add(pi3);
435       }
436     }
437     stack.push(bif);
438   }
439 
440   /**
441    * Default behaviour is to do nothing
442    *
443    * @param colAdjust the amount to add on to each relative cell reference
444    * @param rowAdjust the amount to add on to each relative row reference
445    */
446   public void adjustRelativeCellReferences(int colAdjust, int rowAdjust)
447   {
448     root.adjustRelativeCellReferences(colAdjust, rowAdjust);
449   }
450 
451   /**
452    * Called when a column is inserted on the specified sheet.  Tells
453    * the formula  parser to update all of its cell references beyond this
454    * column
455    *
456    * @param sheetIndex the sheet on which the column was inserted
457    * @param col the column number which was inserted
458    * @param currentSheet TRUE if this formula is on the sheet in which the
459    * column was inserted, FALSE otherwise
460    */
461   public void columnInserted(int sheetIndex, int col, boolean currentSheet)
462   {
463     root.columnInserted(sheetIndex, col, currentSheet);
464   }
465 
466 
467   /**
468    * Called when a column is inserted on the specified sheet.  Tells
469    * the formula  parser to update all of its cell references beyond this
470    * column
471    *
472    * @param sheetIndex the sheet on which the column was removed
473    * @param col the column number which was removed
474    * @param currentSheet TRUE if this formula is on the sheet in which the
475    * column was inserted, FALSE otherwise
476    */
477   public void columnRemoved(int sheetIndex, int col, boolean currentSheet)
478   {
479     root.columnRemoved(sheetIndex, col, currentSheet);
480   }
481 
482   /**
483    * Called when a column is inserted on the specified sheet.  Tells
484    * the formula  parser to update all of its cell references beyond this
485    * column
486    *
487    * @param sheetIndex the sheet on which the column was inserted
488    * @param row the column number which was inserted
489    * @param currentSheet TRUE if this formula is on the sheet in which the
490    * column was inserted, FALSE otherwise
491    */
492   public void rowInserted(int sheetIndex, int row, boolean currentSheet)
493   {
494     root.rowInserted(sheetIndex, row, currentSheet);
495   }
496 
497   /**
498    * Called when a column is inserted on the specified sheet.  Tells
499    * the formula  parser to update all of its cell references beyond this
500    * column
501    *
502    * @param sheetIndex the sheet on which the column was removed
503    * @param row the column number which was removed
504    * @param currentSheet TRUE if this formula is on the sheet in which the
505    * column was inserted, FALSE otherwise
506    */
507   public void rowRemoved(int sheetIndex, int row, boolean currentSheet)
508   {
509     root.rowRemoved(sheetIndex, row, currentSheet);
510   }
511 
512   /**
513    * Handles operands by pushing them onto the stack
514    *
515    * @param o operand
516    * @param stack stack
517    */
518   private void handleOperand(Operand o, Stack   stack)
519   {
520     if (!(o instanceof IntegerValue))
521     {
522       stack.push(o);
523       return;
524     }
525 
526     if (o instanceof IntegerValue)
527     {
528       IntegerValue iv = (IntegerValue) o;
529       if (!iv.isOutOfRange())
530       {
531         stack.push(iv);
532       }
533       else
534       {
535         // convert to a double
536         DoubleValue dv = new  DoubleValue(iv.getValue());
537         stack.push(dv);
538       }
539     }
540   }
541 
542 }
543
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags