src/java/org/apache/poi/hssf/record/formula/Ptg.java

   1 /* ====================================================================
   2    Licensed to the Apache Software Foundation (ASF) under one or more
   3    contributor license agreements.  See the NOTICE file distributed with
   4    this work for additional information regarding copyright ownership.
   5    The ASF licenses this file to You under the Apache License, Version 2.0
   6    (the "License"); you may not use this file except in compliance with
   7    the License.  You may obtain a copy of the License at
   8
   9        http://www.apache.org/licenses/LICENSE-2.0
  10
  11    Unless required by applicable law or agreed to in writing, software
  12    distributed under the License is distributed on an "AS IS" BASIS,
  13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14    See the License for the specific language governing permissions and
  15    limitations under the License.
  16 ==================================================================== */
  17
  18 package org.apache.poi.hssf.record.formula;
  19
  20 import java.util.ArrayList;
  21 import java.util.List;
  22 import java.util.Stack;
  23
  24 import org.apache.poi.hssf.record.RecordInputStream;
  25 import org.apache.poi.hssf.usermodel.HSSFWorkbook;
  26
  27 /**
  28  * <tt>Ptg</tt> represents a syntactic token in a formula.  'PTG' is an acronym for
  29  * '<b>p</b>arse <b>t</b>hin<b>g</b>'.  Originally, the name referred to the single
  30  * byte identifier at the start of the token, but in POI, <tt>Ptg</tt> encapsulates
  31  * the whole formula token (initial byte + value data).
  32  * <p/>
  33  *
  34  * <tt>Ptg</tt>s are logically arranged in a tree representing the structure of the
  35  * parsed formula.  However, in BIFF files <tt>Ptg</tt>s are written/read in
  36  * <em>Reverse-Polish Notation</em> order. The RPN ordering also simplifies formula
  37  * evaluation logic, so POI mostly accesses <tt>Ptg</tt>s in the same way.
  38  *
  39  * @author  andy
  40  * @author avik
  41  * @author Jason Height (jheight at chariot dot net dot au)
  42  */
  43 public abstract class Ptg implements Cloneable {
  44
  45         /* convert infix order ptg list to rpn order ptg list
  46          * @return List ptgs in RPN order
  47          * @param infixPtgs List of ptgs in infix order
  48          */
  49
  50         /* DO NOT REMOVE
  51          *we keep this method in case we wish to change the way we parse
  52          *It needs a getPrecedence in OperationsPtg
  53
  54         public static List ptgsToRpn(List infixPtgs) {
  55                 java.util.Stack operands = new java.util.Stack();
  56                 java.util.List retval = new java.util.Stack();
  57
  58                 java.util.ListIterator i = infixPtgs.listIterator();
  59                 Object p;
  60                 OperationPtg o ;
  61                 boolean weHaveABracket = false;
  62                 while (i.hasNext()) {
  63                         p=i.next();
  64                         if (p instanceof OperationPtg) {
  65                                 if (p instanceof ParenthesisPtg) {
  66                                         if (!weHaveABracket) {
  67                                                 operands.push(p);
  68                                                 weHaveABracket = true;
  69                                         } else {
  70                                                 o = (OperationPtg) operands.pop();
  71                                                 while (!(o instanceof ParenthesisPtg)) {
  72                                                         retval.add(o);
  73                                                 }
  74                                                 weHaveABracket = false;
  75                                         }
  76                                 } else {
  77
  78                                         while  (!operands.isEmpty() && ((OperationPtg) operands.peek()).getPrecedence() >= ((OperationPtg) p).getPrecedence() ) { //TODO handle ^ since it is right associative
  79                                                 retval.add(operands.pop());
  80                                         }
  81                                         operands.push(p);
  82                                 }
  83                         } else {
  84                                 retval.add(p);
  85                         }
  86                 }
  87                 while (!operands.isEmpty()) {
  88                         if (operands.peek() instanceof ParenthesisPtg ){
  89                                 //throw some error
  90                         } else {
  91                                 retval.add(operands.pop());
  92                         }
  93                 }
  94                 return retval;
  95         }
  96         */
  97
  98         /**
  99          * Reads <tt>size</tt> bytes of the input stream, to create an array of <tt>Ptg</tt>s.
 100          * Extra data (beyond <tt>size</tt>) may be read if and <tt>ArrayPtg</tt>s are present.
 101          */
 102         public static Ptg[] readTokens(int size, RecordInputStream in) {
 103                 Stack temp = createParsedExpressionTokens((short)size, in);
 104                 return toPtgArray(temp);
 105         }
 106
 107         /**
 108          * @deprecated - use readTokens()
 109          */
 110         public static Stack createParsedExpressionTokens(short size, RecordInputStream in)
 111         {
 112                 Stack stack = new Stack();
 113                 int pos = 0;
 114                 List arrayPtgs = null;
 115                 while ( pos < size )
 116                 {
 117                         Ptg ptg = Ptg.createPtg( in );
 118                         if (ptg instanceof ArrayPtg) {
 119                                 if (arrayPtgs == null)
 120                                         arrayPtgs = new ArrayList(5);
 121                                 arrayPtgs.add(ptg);
 122                                 pos += 8;
 123                         } else pos += ptg.getSize();
 124                         stack.push( ptg );
 125                 }
 126                 if(pos != size) {
 127                         throw new RuntimeException("Ptg array size mismatch");
 128                 }
 129                 if (arrayPtgs != null) {
 130                         for (int i=0;i<arrayPtgs.size();i++) {
 131                                 ArrayPtg p = (ArrayPtg)arrayPtgs.get(i);
 132                                 p.readTokenValues(in);
 133                         }
 134                 }
 135                 return stack;
 136         }
 137
 138         public static Ptg createPtg(RecordInputStream in) {
 139                 byte id = in.readByte();
 140
 141                 if (id < 0x20) {
 142                         return createBasePtg(id, in);
 143                 }
 144
 145                 Ptg  retval = createClassifiedPtg(id, in);
 146
 147                 if (id > 0x60) {
 148                         retval.setClass(CLASS_ARRAY);
 149                 } else if (id > 0x40) {
 150                         retval.setClass(CLASS_VALUE);
 151                 } else {
 152                         retval.setClass(CLASS_REF);
 153                 }
 154
 155            return retval;
 156         }
 157
 158         private static Ptg createClassifiedPtg(byte id, RecordInputStream in) {
 159
 160                 int baseId = id & 0x1F | 0x20;
 161
 162                 switch (baseId) {
 163                         case ArrayPtg.sid:     return new ArrayPtg(in);    // 0x20, 0x40, 0x60
 164                          case FuncPtg.sid:     return new FuncPtg(in);     // 0x21, 0x41, 0x61
 165                          case FuncVarPtg.sid:  return new FuncVarPtg(in);  // 0x22, 0x42, 0x62
 166                          case NamePtg.sid:     return new NamePtg(in);     // 0x23, 0x43, 0x63
 167                          case RefPtg.sid:      return new RefPtg(in);      // 0x24, 0x44, 0x64
 168                          case AreaPtg.sid:     return new AreaPtg(in);     // 0x25, 0x45, 0x65
 169                          case MemAreaPtg.sid:  return new MemAreaPtg(in);  // 0x26, 0x46, 0x66
 170                          case MemErrPtg.sid:   return new MemErrPtg(in);   // 0x27, 0x47, 0x67
 171                          case MemFuncPtg.sid:  return new MemFuncPtg(in);  // 0x29, 0x49, 0x69
 172                          case RefErrorPtg.sid: return  new RefErrorPtg(in);// 0x2a, 0x4a, 0x6a
 173                          case AreaErrPtg.sid:  return new AreaErrPtg(in);  // 0x2b, 0x4b, 0x6b
 174                          case RefNPtg.sid:     return new RefNPtg(in);     // 0x2c, 0x4c, 0x6c
 175                          case AreaNPtg.sid:    return new AreaNPtg(in);    // 0x2d, 0x4d, 0x6d
 176
 177                          case NameXPtg.sid:    return new NameXPtg(in);    // 0x39, 0x49, 0x79
 178                          case Ref3DPtg.sid:    return  new Ref3DPtg(in);   // 0x3a, 0x5a, 0x7a
 179                          case Area3DPtg.sid:   return new Area3DPtg(in);   // 0x3b, 0x5b, 0x7b
 180                          case DeletedRef3DPtg.sid:  return new DeletedRef3DPtg(in);   // 0x3c, 0x5c, 0x7c
 181                          case DeletedArea3DPtg.sid: return  new DeletedArea3DPtg(in); // 0x3d, 0x5d, 0x7d
 182                 }
 183                 throw new UnsupportedOperationException(" Unknown Ptg in Formula: 0x"+
 184                                    Integer.toHexString(id) + " (" + ( int ) id + ")");
 185         }
 186
 187         private static Ptg createBasePtg(byte id, RecordInputStream in) {
 188                 switch(id) {
 189                         case 0x00:                return new UnknownPtg(); // TODO - not a real Ptg
 190                         case ExpPtg.sid:          return new ExpPtg(in);          // 0x01
 191                         case TblPtg.sid:          return new TblPtg(in);          // 0x02
 192                         case AddPtg.sid:          return AddPtg.instance;         // 0x03
 193                         case SubtractPtg.sid:     return SubtractPtg.instance;    // 0x04
 194                         case MultiplyPtg.sid:     return MultiplyPtg.instance;    // 0x05
 195                         case DividePtg.sid:       return DividePtg.instance;      // 0x06
 196                         case PowerPtg.sid:        return PowerPtg.instance;       // 0x07
 197                         case ConcatPtg.sid:       return ConcatPtg.instance;      // 0x08
 198                         case LessThanPtg.sid:     return LessThanPtg.instance;    // 0x09
 199                         case LessEqualPtg.sid:    return LessEqualPtg.instance;   // 0x0a
 200                         case EqualPtg.sid:        return EqualPtg.instance;       // 0x0b
 201                         case GreaterEqualPtg.sid: return GreaterEqualPtg.instance;// 0x0c
 202                         case GreaterThanPtg.sid:  return GreaterThanPtg.instance; // 0x0d
 203                         case NotEqualPtg.sid:     return NotEqualPtg.instance;    // 0x0e
 204                         case IntersectionPtg.sid: return IntersectionPtg.instance;// 0x0f
 205                         case UnionPtg.sid:        return UnionPtg.instance;       // 0x10
 206                         case RangePtg.sid:        return RangePtg.instance;       // 0x11
 207                         case UnaryPlusPtg.sid:    return UnaryPlusPtg.instance;   // 0x12
 208                         case UnaryMinusPtg.sid:   return UnaryMinusPtg.instance;  // 0x13
 209                         case PercentPtg.sid:      return PercentPtg.instance;     // 0x14
 210                         case ParenthesisPtg.sid:  return ParenthesisPtg.instance; // 0x15
 211                         case MissingArgPtg.sid:   return MissingArgPtg.instance;  // 0x16
 212
 213                         case StringPtg.sid:       return new StringPtg(in);       // 0x17
 214                         case AttrPtg.sid:
 215                         case 0x1a:        return new AttrPtg(in); // 0x19
 216                         case ErrPtg.sid:          return new ErrPtg(in);          // 0x1c
 217                         case BoolPtg.sid:         return new BoolPtg(in);         // 0x1d
 218                         case IntPtg.sid:          return new IntPtg(in);          // 0x1e
 219                         case NumberPtg.sid:       return new NumberPtg(in);       // 0x1f
 220                 }
 221                 throw new RuntimeException("Unexpected base token id (" + id + ")");
 222         }
 223         /**
 224          *
 225          *
 226          */
 227         public static int getEncodedSize(Stack ptgs) {
 228                 return getEncodedSize(toPtgArray(ptgs));
 229         }
 230         /**
 231          * @return a distinct copy of this <tt>Ptg</tt> if the class is mutable, or the same instance
 232          * if the class is immutable.
 233          */
 234         public final Ptg copy() {
 235                 // TODO - all base tokens are logically immutable, but AttrPtg needs some clean-up
 236                 if (this instanceof ValueOperatorPtg) {
 237                         return this;
 238                 }
 239                 if (this instanceof ScalarConstantPtg) {
 240                         return this;
 241                 }
 242                 return (Ptg) clone();
 243         }
 244
 245         protected Object clone() {
 246                 try {
 247                         return super.clone();
 248                 } catch (CloneNotSupportedException e) {
 249                         throw new RuntimeException(e);
 250                 }
 251         }
 252         private static Ptg[] toPtgArray(List l) {
 253                 Ptg[] result = new Ptg[l.size()];
 254                 l.toArray(result);
 255                 return result;
 256         }
 257         private static Stack createStack(Ptg[] formulaTokens) {
 258                 Stack result = new Stack();
 259                 for (int i = 0; i < formulaTokens.length; i++) {
 260                         result.add(formulaTokens[i]);
 261                 }
 262                 return result;
 263         }
 264         // TODO - several duplicates of this code should be refactored here
 265         public static int getEncodedSize(Ptg[] ptgs) {
 266                 int result = 0;
 267                 for (int i = 0; i < ptgs.length; i++) {
 268                         result += ptgs[i].getSize();
 269                 }
 270                 return result;
 271         }
 272         /**
 273          * Writes the ptgs to the data buffer, starting at the specified offset.
 274          *
 275          * <br/>
 276          * The 2 byte encode length field is <b>not</b> written by this method.
 277          * @return number of bytes written
 278          */
 279         public static int serializePtgs(Ptg[] ptgs, byte[] data, int offset) {
 280                 return serializePtgStack(createStack(ptgs), data, offset);
 281         }
 282
 283         /**
 284          * @deprecated use serializePtgs()
 285          */
 286         public static int serializePtgStack(Stack expression, byte[] array, int offset) {
 287                 int pos = 0;
 288                 int size = 0;
 289                 if (expression != null)
 290                         size = expression.size();
 291
 292                 List arrayPtgs = null;
 293
 294                 for (int k = 0; k < size; k++) {
 295                         Ptg ptg = ( Ptg ) expression.get(k);
 296
 297                         ptg.writeBytes(array, pos + offset);
 298                         if (ptg instanceof ArrayPtg) {
 299                           if (arrayPtgs == null)
 300                                   arrayPtgs = new ArrayList(5);
 301                           arrayPtgs.add(ptg);
 302                           pos += 8;
 303                         } else pos += ptg.getSize();
 304                 }
 305                 if (arrayPtgs != null) {
 306                         for (int i=0;i<arrayPtgs.size();i++) {
 307                                 ArrayPtg p = (ArrayPtg)arrayPtgs.get(i);
 308                                 pos += p.writeTokenValueBytes(array, pos + offset);
 309                         }
 310                 }
 311                 return pos;
 312         }
 313
 314         /**
 315          * @return the encoded length of this Ptg, including the initial Ptg type identifier byte.
 316          */
 317         public abstract int getSize();
 318
 319         /**
 320          * @return the encoded length of this Ptg, not including the initial Ptg type identifier byte.
 321          */
 322 //    public abstract int getDataSize();
 323
 324         public final byte [] getBytes()
 325         {
 326                 int    size  = getSize();
 327                 byte[] bytes = new byte[ size ];
 328
 329                 writeBytes(bytes, 0);
 330                 return bytes;
 331         }
 332         /** write this Ptg to a byte array*/
 333         public abstract void writeBytes(byte [] array, int offset);
 334
 335         /**
 336          * return a string representation of this token alone
 337          */
 338         public abstract String toFormulaString(HSSFWorkbook book);
 339         /**
 340          * dump a debug representation (hexdump) to a string
 341          */
 342         public final String toDebugString() {
 343                 byte[] ba = new byte[getSize()];
 344                 String retval=null;
 345                 writeBytes(ba,0);
 346                 try {
 347                         retval = org.apache.poi.util.HexDump.dump(ba,0,0);
 348                 } catch (Exception e) {
 349                         e.printStackTrace();
 350                 }
 351                 return retval;
 352         }
 353
 354         /** Overridden toString method to ensure object hash is not printed.
 355          * This helps get rid of gratuitous diffs when comparing two dumps
 356          * Subclasses may output more relevant information by overriding this method
 357          **/
 358         public String toString(){
 359                 return this.getClass().toString();
 360         }
 361
 362         public static final byte CLASS_REF = 0x00;
 363         public static final byte CLASS_VALUE = 0x20;
 364         public static final byte CLASS_ARRAY = 0x40;
 365
 366         private byte ptgClass = CLASS_REF; //base ptg
 367
 368         public final void setClass(byte thePtgClass) {
 369                 if (isBaseToken()) {
 370                         throw new RuntimeException("setClass should not be called on a base token");
 371                 }
 372                 ptgClass = thePtgClass;
 373         }
 374
 375         /**
 376          *  @return the 'operand class' (REF/VALUE/ARRAY) for this Ptg
 377          */
 378         public final byte getPtgClass() {
 379                 return ptgClass;
 380         }
 381
 382         public abstract byte getDefaultOperandClass();
 383
 384         /**
 385          * @return <code>false</code> if this token is classified as 'reference', 'value', or 'array'
 386          */
 387         public abstract boolean isBaseToken();
 388 }