1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one
3  * or more contributor license agreements. See the NOTICE file
4  * distributed with this work for additional information
5  * regarding copyright ownership. The ASF licenses this file
6  * to you under the Apache License, Version 2.0 (the  "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  *     http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18 /*
19  * $Id: AxesWalker.java 513117 2007-03-01 03:28:52Z minchau $
20  */
21 package org.apache.xpath.axes;
22 
23 import java.util.Vector;
24 
25 import org.apache.xalan.res.XSLMessages;
26 import org.apache.xml.dtm.DTM;
27 import org.apache.xml.dtm.DTMAxisTraverser;
28 import org.apache.xml.dtm.DTMIterator;
29 import org.apache.xpath.Expression;
30 import org.apache.xpath.ExpressionOwner;
31 import org.apache.xpath.XPathContext;
32 import org.apache.xpath.XPathVisitor;
33 import org.apache.xpath.compiler.Compiler;
34 import org.apache.xpath.res.XPATHErrorResources;
35 
36 /**
37  * Serves as common interface for axes Walkers, and stores common
38  * state variables.
39  */
40 public class AxesWalker extends PredicatedNodeTest
41         implements Cloneable, PathComponent, ExpressionOwner
42 {
43     static final long serialVersionUID = -2966031951306601247L;
44 
45   /**
46    * Construct an AxesWalker using a LocPathIterator.
47    *
48    * @param locPathIterator non-null reference to the parent iterator.
49    */
AxesWalker(LocPathIterator locPathIterator, int axis)50   public AxesWalker(LocPathIterator locPathIterator, int axis)
51   {
52     super( locPathIterator );
53     m_axis = axis;
54   }
55 
wi()56   public final WalkingIterator wi()
57   {
58     return (WalkingIterator)m_lpi;
59   }
60 
61   /**
62    * Initialize an AxesWalker during the parse of the XPath expression.
63    *
64    * @param compiler The Compiler object that has information about this
65    *                 walker in the op map.
66    * @param opPos The op code position of this location step.
67    * @param stepType  The type of location step.
68    *
69    * @throws javax.xml.transform.TransformerException
70    */
init(Compiler compiler, int opPos, int stepType)71   public void init(Compiler compiler, int opPos, int stepType)
72           throws javax.xml.transform.TransformerException
73   {
74 
75     initPredicateInfo(compiler, opPos);
76 
77     // int testType = compiler.getOp(nodeTestOpPos);
78   }
79 
80   /**
81    * Get a cloned AxesWalker.
82    *
83    * @return A new AxesWalker that can be used without mutating this one.
84    *
85    * @throws CloneNotSupportedException
86    */
clone()87   public Object clone() throws CloneNotSupportedException
88   {
89     // Do not access the location path itterator during this operation!
90 
91     AxesWalker clone = (AxesWalker) super.clone();
92 
93     //clone.setCurrentNode(clone.m_root);
94 
95     // clone.m_isFresh = true;
96 
97     return clone;
98   }
99 
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    */
cloneDeep(WalkingIterator cloneOwner, Vector cloneList)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    */
findClone(AxesWalker key, Vector cloneList)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    */
detach()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    */
getRoot()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    */
getAnalysisBits()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    */
setRoot(int root)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    */
getCurrentNode()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    */
setNextWalker(AxesWalker walker)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    */
getNextWalker()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    */
setPrevWalker(AxesWalker walker)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    */
getPrevWalker()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    */
returnNextNode(int n)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    */
getNextNode()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    */
nextNode()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    */
getLastPos(XPathContext xctxt)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    */
setDefaultDTM(DTM dtm)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    */
getDTM(int node)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    */
isDocOrdered()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    */
getAxis()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    */
callVisitors(ExpressionOwner owner, XPathVisitor visitor)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    */
getExpression()535   public Expression getExpression()
536   {
537     return m_nextWalker;
538   }
539 
540   /**
541    * @see ExpressionOwner#setExpression(Expression)
542    */
setExpression(Expression exp)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      */
deepEquals(Expression expr)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 }
591