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    }