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
9 http://www.apache.org/licenses/LICENSE-2.0
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 ==================================================================== */
18 package org
.apache
.poi
.hssf
.record
.formula
;
20 import java
.util
.ArrayList
;
21 import java
.util
.List
;
22 import java
.util
.Stack
;
24 import org
.apache
.poi
.hssf
.record
.RecordInputStream
;
25 import org
.apache
.poi
.hssf
.usermodel
.HSSFWorkbook
;
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).
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.
41 * @author Jason Height (jheight at chariot dot net dot au)
43 public abstract class Ptg
implements Cloneable
{
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
51 *we keep this method in case we wish to change the way we parse
52 *It needs a getPrecedence in OperationsPtg
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();
58 java.util.ListIterator i = infixPtgs.listIterator();
61 boolean weHaveABracket = false;
64 if (p instanceof OperationPtg) {
65 if (p instanceof ParenthesisPtg) {
66 if (!weHaveABracket) {
68 weHaveABracket = true;
70 o = (OperationPtg) operands.pop();
71 while (!(o instanceof ParenthesisPtg)) {
74 weHaveABracket = false;
78 while (!operands.isEmpty() && ((OperationPtg) operands.peek()).getPrecedence() >= ((OperationPtg) p).getPrecedence() ) { //TODO handle ^ since it is right associative
79 retval.add(operands.pop());
87 while (!operands.isEmpty()) {
88 if (operands.peek() instanceof ParenthesisPtg ){
91 retval.add(operands.pop());
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.
102 public static Ptg
[] readTokens(int size
, RecordInputStream in
) {
103 Stack temp
= createParsedExpressionTokens((short)size
, in
);
104 return toPtgArray(temp
);
108 * @deprecated - use readTokens()
110 public static Stack
createParsedExpressionTokens(short size
, RecordInputStream in
)
112 Stack stack
= new Stack();
114 List arrayPtgs
= null;
117 Ptg ptg
= Ptg
.createPtg( in
);
118 if (ptg
instanceof ArrayPtg
) {
119 if (arrayPtgs
== null)
120 arrayPtgs
= new ArrayList(5);
123 } else pos
+= ptg
.getSize();
127 throw new RuntimeException("Ptg array size mismatch");
129 if (arrayPtgs
!= null) {
130 for (int i
=0;i
<arrayPtgs
.size();i
++) {
131 ArrayPtg p
= (ArrayPtg
)arrayPtgs
.get(i
);
132 p
.readTokenValues(in
);
138 public static Ptg
createPtg(RecordInputStream in
) {
139 byte id
= in
.readByte();
142 return createBasePtg(id
, in
);
145 Ptg retval
= createClassifiedPtg(id
, in
);
148 retval
.setClass(CLASS_ARRAY
);
149 } else if (id
> 0x40) {
150 retval
.setClass(CLASS_VALUE
);
152 retval
.setClass(CLASS_REF
);
158 private static Ptg
createClassifiedPtg(byte id
, RecordInputStream in
) {
160 int baseId
= id
& 0x1F | 0x20;
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
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
183 throw new UnsupportedOperationException(" Unknown Ptg in Formula: 0x"+
184 Integer
.toHexString(id
) + " (" + ( int ) id
+ ")");
187 private static Ptg
createBasePtg(byte id
, RecordInputStream in
) {
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
213 case StringPtg
.sid
: return new StringPtg(in
); // 0x17
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
221 throw new RuntimeException("Unexpected base token id (" + id
+ ")");
227 public static int getEncodedSize(Stack ptgs
) {
228 return getEncodedSize(toPtgArray(ptgs
));
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.
234 public final Ptg
copy() {
235 // TODO - all base tokens are logically immutable, but AttrPtg needs some clean-up
236 if (this instanceof ValueOperatorPtg
) {
239 if (this instanceof ScalarConstantPtg
) {
242 return (Ptg
) clone();
245 protected Object
clone() {
247 return super.clone();
248 } catch (CloneNotSupportedException e
) {
249 throw new RuntimeException(e
);
252 private static Ptg
[] toPtgArray(List l
) {
253 Ptg
[] result
= new Ptg
[l
.size()];
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
]);
264 // TODO - several duplicates of this code should be refactored here
265 public static int getEncodedSize(Ptg
[] ptgs
) {
267 for (int i
= 0; i
< ptgs
.length
; i
++) {
268 result
+= ptgs
[i
].getSize();
273 * Writes the ptgs to the data buffer, starting at the specified offset.
276 * The 2 byte encode length field is <b>not</b> written by this method.
277 * @return number of bytes written
279 public static int serializePtgs(Ptg
[] ptgs
, byte[] data
, int offset
) {
280 return serializePtgStack(createStack(ptgs
), data
, offset
);
284 * @deprecated use serializePtgs()
286 public static int serializePtgStack(Stack expression
, byte[] array
, int offset
) {
289 if (expression
!= null)
290 size
= expression
.size();
292 List arrayPtgs
= null;
294 for (int k
= 0; k
< size
; k
++) {
295 Ptg ptg
= ( Ptg
) expression
.get(k
);
297 ptg
.writeBytes(array
, pos
+ offset
);
298 if (ptg
instanceof ArrayPtg
) {
299 if (arrayPtgs
== null)
300 arrayPtgs
= new ArrayList(5);
303 } else pos
+= ptg
.getSize();
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
);
315 * @return the encoded length of this Ptg, including the initial Ptg type identifier byte.
317 public abstract int getSize();
320 * @return the encoded length of this Ptg, not including the initial Ptg type identifier byte.
322 // public abstract int getDataSize();
324 public final byte [] getBytes()
326 int size
= getSize();
327 byte[] bytes
= new byte[ size
];
329 writeBytes(bytes
, 0);
332 /** write this Ptg to a byte array*/
333 public abstract void writeBytes(byte [] array
, int offset
);
336 * return a string representation of this token alone
338 public abstract String
toFormulaString(HSSFWorkbook book
);
340 * dump a debug representation (hexdump) to a string
342 public final String
toDebugString() {
343 byte[] ba
= new byte[getSize()];
347 retval
= org
.apache
.poi
.util
.HexDump
.dump(ba
,0,0);
348 } catch (Exception e
) {
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
358 public String
toString(){
359 return this.getClass().toString();
362 public static final byte CLASS_REF
= 0x00;
363 public static final byte CLASS_VALUE
= 0x20;
364 public static final byte CLASS_ARRAY
= 0x40;
366 private byte ptgClass
= CLASS_REF
; //base ptg
368 public final void setClass(byte thePtgClass
) {
370 throw new RuntimeException("setClass should not be called on a base token");
372 ptgClass
= thePtgClass
;
376 * @return the 'operand class' (REF/VALUE/ARRAY) for this Ptg
378 public final byte getPtgClass() {
382 public abstract byte getDefaultOperandClass();
385 * @return <code>false</code> if this token is classified as 'reference', 'value', or 'array'
387 public abstract boolean isBaseToken();