001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: AxesWalker.java 513117 2007-03-01 03:28:52Z minchau $
020 */
021 package org.apache.xpath.axes;
022
023 import java.util.Vector;
024
025 import org.apache.xalan.res.XSLMessages;
026 import org.apache.xml.dtm.DTM;
027 import org.apache.xml.dtm.DTMAxisTraverser;
028 import org.apache.xml.dtm.DTMIterator;
029 import org.apache.xpath.Expression;
030 import org.apache.xpath.ExpressionOwner;
031 import org.apache.xpath.XPathContext;
032 import org.apache.xpath.XPathVisitor;
033 import org.apache.xpath.compiler.Compiler;
034 import org.apache.xpath.res.XPATHErrorResources;
035
036 /**
037 * Serves as common interface for axes Walkers, and stores common
038 * state variables.
039 */
040 public class AxesWalker extends PredicatedNodeTest
041 implements Cloneable, PathComponent, ExpressionOwner
042 {
043 static final long serialVersionUID = -2966031951306601247L;
044
045 /**
046 * Construct an AxesWalker using a LocPathIterator.
047 *
048 * @param locPathIterator non-null reference to the parent iterator.
049 */
050 public AxesWalker(LocPathIterator locPathIterator, int axis)
051 {
052 super( locPathIterator );
053 m_axis = axis;
054 }
055
056 public final WalkingIterator wi()
057 {
058 return (WalkingIterator)m_lpi;
059 }
060
061 /**
062 * Initialize an AxesWalker during the parse of the XPath expression.
063 *
064 * @param compiler The Compiler object that has information about this
065 * walker in the op map.
066 * @param opPos The op code position of this location step.
067 * @param stepType The type of location step.
068 *
069 * @throws javax.xml.transform.TransformerException
070 */
071 public void init(Compiler compiler, int opPos, int stepType)
072 throws javax.xml.transform.TransformerException
073 {
074
075 initPredicateInfo(compiler, opPos);
076
077 // int testType = compiler.getOp(nodeTestOpPos);
078 }
079
080 /**
081 * Get a cloned AxesWalker.
082 *
083 * @return A new AxesWalker that can be used without mutating this one.
084 *
085 * @throws CloneNotSupportedException
086 */
087 public Object clone() throws CloneNotSupportedException
088 {
089 // Do not access the location path itterator during this operation!
090
091 AxesWalker clone = (AxesWalker) super.clone();
092
093 //clone.setCurrentNode(clone.m_root);
094
095 // clone.m_isFresh = true;
096
097 return clone;
098 }
099
100 /**
101 * Do a deep clone of this walker, including next and previous walkers.
102 * If the this AxesWalker is on the clone list, don't clone but
103 * return the already cloned version.
104 *
105 * @param cloneOwner non-null reference to the cloned location path
106 * iterator to which this clone will be added.
107 * @param cloneList non-null vector of sources in odd elements, and the
108 * corresponding clones in even vectors.
109 *
110 * @return non-null clone, which may be a new clone, or may be a clone
111 * contained on the cloneList.
112 */
113 AxesWalker cloneDeep(WalkingIterator cloneOwner, Vector cloneList)
114 throws CloneNotSupportedException
115 {
116 AxesWalker clone = findClone(this, cloneList);
117 if(null != clone)
118 return clone;
119 clone = (AxesWalker)this.clone();
120 clone.setLocPathIterator(cloneOwner);
121 if(null != cloneList)
122 {
123 cloneList.addElement(this);
124 cloneList.addElement(clone);
125 }
126
127 if(wi().m_lastUsedWalker == this)
128 cloneOwner.m_lastUsedWalker = clone;
129
130 if(null != m_nextWalker)
131 clone.m_nextWalker = m_nextWalker.cloneDeep(cloneOwner, cloneList);
132
133 // If you don't check for the cloneList here, you'll go into an
134 // recursive infinate loop.
135 if(null != cloneList)
136 {
137 if(null != m_prevWalker)
138 clone.m_prevWalker = m_prevWalker.cloneDeep(cloneOwner, cloneList);
139 }
140 else
141 {
142 if(null != m_nextWalker)
143 clone.m_nextWalker.m_prevWalker = clone;
144 }
145 return clone;
146 }
147
148 /**
149 * Find a clone that corresponds to the key argument.
150 *
151 * @param key The original AxesWalker for which there may be a clone.
152 * @param cloneList vector of sources in odd elements, and the
153 * corresponding clones in even vectors, may be null.
154 *
155 * @return A clone that corresponds to the key, or null if key not found.
156 */
157 static AxesWalker findClone(AxesWalker key, Vector cloneList)
158 {
159 if(null != cloneList)
160 {
161 // First, look for clone on list.
162 int n = cloneList.size();
163 for (int i = 0; i < n; i+=2)
164 {
165 if(key == cloneList.elementAt(i))
166 return (AxesWalker)cloneList.elementAt(i+1);
167 }
168 }
169 return null;
170 }
171
172 /**
173 * Detaches the walker from the set which it iterated over, releasing
174 * any computational resources and placing the iterator in the INVALID
175 * state.
176 */
177 public void detach()
178 {
179 m_currentNode = DTM.NULL;
180 m_dtm = null;
181 m_traverser = null;
182 m_isFresh = true;
183 m_root = DTM.NULL;
184 }
185
186 //=============== TreeWalker Implementation ===============
187
188 /**
189 * The root node of the TreeWalker, as specified in setRoot(int root).
190 * Note that this may actually be below the current node.
191 *
192 * @return The context node of the step.
193 */
194 public int getRoot()
195 {
196 return m_root;
197 }
198
199 /**
200 * Get the analysis bits for this walker, as defined in the WalkerFactory.
201 * @return One of WalkerFactory#BIT_DESCENDANT, etc.
202 */
203 public int getAnalysisBits()
204 {
205 int axis = getAxis();
206 int bit = WalkerFactory.getAnalysisBitFromAxes(axis);
207 return bit;
208 }
209
210 /**
211 * Set the root node of the TreeWalker.
212 * (Not part of the DOM2 TreeWalker interface).
213 *
214 * @param root The context node of this step.
215 */
216 public void setRoot(int root)
217 {
218 // %OPT% Get this directly from the lpi.
219 XPathContext xctxt = wi().getXPathContext();
220 m_dtm = xctxt.getDTM(root);
221 m_traverser = m_dtm.getAxisTraverser(m_axis);
222 m_isFresh = true;
223 m_foundLast = false;
224 m_root = root;
225 m_currentNode = root;
226
227 if (DTM.NULL == root)
228 {
229 throw new RuntimeException(
230 XSLMessages.createXPATHMessage(XPATHErrorResources.ER_SETTING_WALKER_ROOT_TO_NULL, null)); //"\n !!!! Error! Setting the root of a walker to null!!!");
231 }
232
233 resetProximityPositions();
234 }
235
236 /**
237 * The node at which the TreeWalker is currently positioned.
238 * <br> The value must not be null. Alterations to the DOM tree may cause
239 * the current node to no longer be accepted by the TreeWalker's
240 * associated filter. currentNode may also be explicitly set to any node,
241 * whether or not it is within the subtree specified by the root node or
242 * would be accepted by the filter and whatToShow flags. Further
243 * traversal occurs relative to currentNode even if it is not part of the
244 * current view by applying the filters in the requested direction (not
245 * changing currentNode where no traversal is possible).
246 *
247 * @return The node at which the TreeWalker is currently positioned, only null
248 * if setRoot has not yet been called.
249 */
250 public final int getCurrentNode()
251 {
252 return m_currentNode;
253 }
254
255 /**
256 * Set the next walker in the location step chain.
257 *
258 *
259 * @param walker Reference to AxesWalker derivative, or may be null.
260 */
261 public void setNextWalker(AxesWalker walker)
262 {
263 m_nextWalker = walker;
264 }
265
266 /**
267 * Get the next walker in the location step chain.
268 *
269 *
270 * @return Reference to AxesWalker derivative, or null.
271 */
272 public AxesWalker getNextWalker()
273 {
274 return m_nextWalker;
275 }
276
277 /**
278 * Set or clear the previous walker reference in the location step chain.
279 *
280 *
281 * @param walker Reference to previous walker reference in the location
282 * step chain, or null.
283 */
284 public void setPrevWalker(AxesWalker walker)
285 {
286 m_prevWalker = walker;
287 }
288
289 /**
290 * Get the previous walker reference in the location step chain.
291 *
292 *
293 * @return Reference to previous walker reference in the location
294 * step chain, or null.
295 */
296 public AxesWalker getPrevWalker()
297 {
298 return m_prevWalker;
299 }
300
301 /**
302 * This is simply a way to bottle-neck the return of the next node, for
303 * diagnostic purposes.
304 *
305 * @param n Node to return, or null.
306 *
307 * @return The argument.
308 */
309 private int returnNextNode(int n)
310 {
311
312 return n;
313 }
314
315 /**
316 * Get the next node in document order on the axes.
317 *
318 * @return the next node in document order on the axes, or null.
319 */
320 protected int getNextNode()
321 {
322 if (m_foundLast)
323 return DTM.NULL;
324
325 if (m_isFresh)
326 {
327 m_currentNode = m_traverser.first(m_root);
328 m_isFresh = false;
329 }
330 // I shouldn't have to do this the check for current node, I think.
331 // numbering\numbering24.xsl fails if I don't do this. I think
332 // it occurs as the walkers are backing up. -sb
333 else if(DTM.NULL != m_currentNode)
334 {
335 m_currentNode = m_traverser.next(m_root, m_currentNode);
336 }
337
338 if (DTM.NULL == m_currentNode)
339 this.m_foundLast = true;
340
341 return m_currentNode;
342 }
343
344 /**
345 * Moves the <code>TreeWalker</code> to the next visible node in document
346 * order relative to the current node, and returns the new node. If the
347 * current node has no next node, or if the search for nextNode attempts
348 * to step upward from the TreeWalker's root node, returns
349 * <code>null</code> , and retains the current node.
350 * @return The new node, or <code>null</code> if the current node has no
351 * next node in the TreeWalker's logical view.
352 */
353 public int nextNode()
354 {
355 int nextNode = DTM.NULL;
356 AxesWalker walker = wi().getLastUsedWalker();
357
358 while (true)
359 {
360 if (null == walker)
361 break;
362
363 nextNode = walker.getNextNode();
364
365 if (DTM.NULL == nextNode)
366 {
367
368 walker = walker.m_prevWalker;
369 }
370 else
371 {
372 if (walker.acceptNode(nextNode) != DTMIterator.FILTER_ACCEPT)
373 {
374 continue;
375 }
376
377 if (null == walker.m_nextWalker)
378 {
379 wi().setLastUsedWalker(walker);
380
381 // return walker.returnNextNode(nextNode);
382 break;
383 }
384 else
385 {
386 AxesWalker prev = walker;
387
388 walker = walker.m_nextWalker;
389
390 walker.setRoot(nextNode);
391
392 walker.m_prevWalker = prev;
393
394 continue;
395 }
396 } // if(null != nextNode)
397 } // while(null != walker)
398
399 return nextNode;
400 }
401
402 //============= End TreeWalker Implementation =============
403
404 /**
405 * Get the index of the last node that can be itterated to.
406 *
407 *
408 * @param xctxt XPath runtime context.
409 *
410 * @return the index of the last node that can be itterated to.
411 */
412 public int getLastPos(XPathContext xctxt)
413 {
414
415 int pos = getProximityPosition();
416
417 AxesWalker walker;
418
419 try
420 {
421 walker = (AxesWalker) clone();
422 }
423 catch (CloneNotSupportedException cnse)
424 {
425 return -1;
426 }
427
428 walker.setPredicateCount(m_predicateIndex);
429 walker.setNextWalker(null);
430 walker.setPrevWalker(null);
431
432 WalkingIterator lpi = wi();
433 AxesWalker savedWalker = lpi.getLastUsedWalker();
434
435 try
436 {
437 lpi.setLastUsedWalker(walker);
438
439 int next;
440
441 while (DTM.NULL != (next = walker.nextNode()))
442 {
443 pos++;
444 }
445
446 // TODO: Should probably save this in the iterator.
447 }
448 finally
449 {
450 lpi.setLastUsedWalker(savedWalker);
451 }
452
453 // System.out.println("pos: "+pos);
454 return pos;
455 }
456
457 //============= State Data =============
458
459 /**
460 * The DTM for the root. This can not be used, or must be changed,
461 * for the filter walker, or any walker that can have nodes
462 * from multiple documents.
463 * Never, ever, access this value without going through getDTM(int node).
464 */
465 private DTM m_dtm;
466
467 /**
468 * Set the DTM for this walker.
469 *
470 * @param dtm Non-null reference to a DTM.
471 */
472 public void setDefaultDTM(DTM dtm)
473 {
474 m_dtm = dtm;
475 }
476
477 /**
478 * Get the DTM for this walker.
479 *
480 * @return Non-null reference to a DTM.
481 */
482 public DTM getDTM(int node)
483 {
484 //
485 return wi().getXPathContext().getDTM(node);
486 }
487
488 /**
489 * Returns true if all the nodes in the iteration well be returned in document
490 * order.
491 * Warning: This can only be called after setRoot has been called!
492 *
493 * @return true as a default.
494 */
495 public boolean isDocOrdered()
496 {
497 return true;
498 }
499
500 /**
501 * Returns the axis being iterated, if it is known.
502 *
503 * @return Axis.CHILD, etc., or -1 if the axis is not known or is of multiple
504 * types.
505 */
506 public int getAxis()
507 {
508 return m_axis;
509 }
510
511 /**
512 * This will traverse the heararchy, calling the visitor for
513 * each member. If the called visitor method returns
514 * false, the subtree should not be called.
515 *
516 * @param owner The owner of the visitor, where that path may be
517 * rewritten if needed.
518 * @param visitor The visitor whose appropriate method will be called.
519 */
520 public void callVisitors(ExpressionOwner owner, XPathVisitor visitor)
521 {
522 if(visitor.visitStep(owner, this))
523 {
524 callPredicateVisitors(visitor);
525 if(null != m_nextWalker)
526 {
527 m_nextWalker.callVisitors(this, visitor);
528 }
529 }
530 }
531
532 /**
533 * @see ExpressionOwner#getExpression()
534 */
535 public Expression getExpression()
536 {
537 return m_nextWalker;
538 }
539
540 /**
541 * @see ExpressionOwner#setExpression(Expression)
542 */
543 public void setExpression(Expression exp)
544 {
545 exp.exprSetParent(this);
546 m_nextWalker = (AxesWalker)exp;
547 }
548
549 /**
550 * @see Expression#deepEquals(Expression)
551 */
552 public boolean deepEquals(Expression expr)
553 {
554 if (!super.deepEquals(expr))
555 return false;
556
557 AxesWalker walker = (AxesWalker)expr;
558 if(this.m_axis != walker.m_axis)
559 return false;
560
561 return true;
562 }
563
564 /**
565 * The root node of the TreeWalker, as specified when it was created.
566 */
567 transient int m_root = DTM.NULL;
568
569 /**
570 * The node at which the TreeWalker is currently positioned.
571 */
572 private transient int m_currentNode = DTM.NULL;
573
574 /** True if an itteration has not begun. */
575 transient boolean m_isFresh;
576
577 /** The next walker in the location step chain.
578 * @serial */
579 protected AxesWalker m_nextWalker;
580
581 /** The previous walker in the location step chain, or null.
582 * @serial */
583 AxesWalker m_prevWalker;
584
585 /** The traversal axis from where the nodes will be filtered. */
586 protected int m_axis = -1;
587
588 /** The DTM inner traversal class, that corresponds to the super axis. */
589 protected DTMAxisTraverser m_traverser;
590 }