libcore/luni/src/main/java/org/apache/xpath/axes/UnionPathIterator.java

   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: UnionPathIterator.java 469314 2006-10-30 23:31:59Z minchau $
  20  */
  21 package org.apache.xpath.axes;
  22
  23 import org.apache.xml.dtm.Axis;
  24 import org.apache.xml.dtm.DTM;
  25 import org.apache.xml.dtm.DTMIterator;
  26 import org.apache.xpath.Expression;
  27 import org.apache.xpath.ExpressionOwner;
  28 import org.apache.xpath.XPathVisitor;
  29 import org.apache.xpath.compiler.Compiler;
  30 import org.apache.xpath.compiler.OpCodes;
  31 import org.apache.xpath.compiler.OpMap;
  32
  33 /**
  34  * This class extends NodeSetDTM, which implements DTMIterator,
  35  * and fetches nodes one at a time in document order based on a XPath
  36  * <a href="http://www.w3.org/TR/xpath#NT-UnionExpr">UnionExpr</a>.
  37  * As each node is iterated via nextNode(), the node is also stored
  38  * in the NodeVector, so that previousNode() can easily be done.
  39  * @xsl.usage advanced
  40  */
  41 public class UnionPathIterator extends LocPathIterator
  42         implements Cloneable, DTMIterator, java.io.Serializable, PathComponent
  43 {
  44     static final long serialVersionUID = -3910351546843826781L;
  45
  46   /**
  47    * Constructor to create an instance which you can add location paths to.
  48    */
  49   public UnionPathIterator()
  50   {
  51
  52     super();
  53
  54     // m_mutable = false;
  55     // m_cacheNodes = false;
  56     m_iterators = null;
  57     m_exprs = null;
  58   }
  59
  60   /**
  61    * Initialize the context values for this expression
  62    * after it is cloned.
  63    *
  64    * @param context The XPath runtime context for this
  65    * transformation.
  66    */
  67   public void setRoot(int context, Object environment)
  68   {
  69     super.setRoot(context, environment);
  70
  71     try
  72     {
  73       if (null != m_exprs)
  74       {
  75         int n = m_exprs.length;
  76         DTMIterator newIters[] = new DTMIterator[n];
  77
  78         for (int i = 0; i < n; i++)
  79         {
  80           DTMIterator iter = m_exprs[i].asIterator(m_execContext, context);
  81           newIters[i] = iter;
  82           iter.nextNode();
  83         }
  84         m_iterators = newIters;
  85       }
  86     }
  87     catch(Exception e)
  88     {
  89       throw new org.apache.xml.utils.WrappedRuntimeException(e);
  90     }
  91   }
  92
  93   /**
  94    * Add an iterator to the union list.
  95    *
  96    * @param expr non-null reference to a location path iterator.
  97    */
  98   public void addIterator(DTMIterator expr)
  99   {
 100
 101     // Increase array size by only 1 at a time.  Fix this
 102     // if it looks to be a problem.
 103     if (null == m_iterators)
 104     {
 105       m_iterators = new DTMIterator[1];
 106       m_iterators[0] = expr;
 107     }
 108     else
 109     {
 110       DTMIterator[] exprs = m_iterators;
 111       int len = m_iterators.length;
 112
 113       m_iterators = new DTMIterator[len + 1];
 114
 115       System.arraycopy(exprs, 0, m_iterators, 0, len);
 116
 117       m_iterators[len] = expr;
 118     }
 119     expr.nextNode();
 120     if(expr instanceof Expression)
 121         ((Expression)expr).exprSetParent(this);
 122   }
 123
 124   /**
 125    *  Detaches the iterator from the set which it iterated over, releasing
 126    * any computational resources and placing the iterator in the INVALID
 127    * state. After<code>detach</code> has been invoked, calls to
 128    * <code>nextNode</code> or<code>previousNode</code> will raise the
 129    * exception INVALID_STATE_ERR.
 130    */
 131   public void detach()
 132   {
 133           if(m_allowDetach && null != m_iterators){
 134                   int n = m_iterators.length;
 135                   for(int i = 0; i < n; i++)
 136                   {
 137                           m_iterators[i].detach();
 138                   }
 139                   m_iterators = null;
 140           }
 141   }
 142
 143
 144   /**
 145    * Create a UnionPathIterator object, including creation
 146    * of location path iterators from the opcode list, and call back
 147    * into the Compiler to create predicate expressions.
 148    *
 149    * @param compiler The Compiler which is creating
 150    * this expression.
 151    * @param opPos The position of this iterator in the
 152    * opcode list from the compiler.
 153    *
 154    * @throws javax.xml.transform.TransformerException
 155    */
 156   public UnionPathIterator(Compiler compiler, int opPos)
 157           throws javax.xml.transform.TransformerException
 158   {
 159
 160     super();
 161
 162     opPos = OpMap.getFirstChildPos(opPos);
 163
 164     loadLocationPaths(compiler, opPos, 0);
 165   }
 166
 167   /**
 168    * This will return an iterator capable of handling the union of paths given.
 169    *
 170    * @param compiler The Compiler which is creating
 171    * this expression.
 172    * @param opPos The position of this iterator in the
 173    * opcode list from the compiler.
 174    *
 175    * @return Object that is derived from LocPathIterator.
 176    *
 177    * @throws javax.xml.transform.TransformerException
 178    */
 179   public static LocPathIterator createUnionIterator(Compiler compiler, int opPos)
 180           throws javax.xml.transform.TransformerException
 181   {
 182         // For the moment, I'm going to first create a full UnionPathIterator, and
 183         // then see if I can reduce it to a UnionChildIterator.  It would obviously
 184         // be more effecient to just test for the conditions for a UnionChildIterator,
 185         // and then create that directly.
 186         UnionPathIterator upi = new UnionPathIterator(compiler, opPos);
 187         int nPaths = upi.m_exprs.length;
 188         boolean isAllChildIterators = true;
 189         for(int i = 0; i < nPaths; i++)
 190         {
 191                 LocPathIterator lpi = upi.m_exprs[i];
 192
 193                 if(lpi.getAxis() != Axis.CHILD)
 194                 {
 195                         isAllChildIterators = false;
 196                         break;
 197                 }
 198                 else
 199                 {
 200                         // check for positional predicates or position function, which won't work.
 201                         if(HasPositionalPredChecker.check(lpi))
 202                         {
 203                                 isAllChildIterators = false;
 204                                 break;
 205                         }
 206                 }
 207         }
 208         if(isAllChildIterators)
 209         {
 210                 UnionChildIterator uci = new UnionChildIterator();
 211
 212                 for(int i = 0; i < nPaths; i++)
 213                 {
 214                         PredicatedNodeTest lpi = upi.m_exprs[i];
 215                         // I could strip the lpi down to a pure PredicatedNodeTest, but
 216                         // I don't think it's worth it.  Note that the test can be used
 217                         // as a static object... so it doesn't have to be cloned.
 218                         uci.addNodeTest(lpi);
 219                 }
 220                 return uci;
 221
 222         }
 223         else
 224                 return upi;
 225   }
 226
 227   /**
 228    * Get the analysis bits for this walker, as defined in the WalkerFactory.
 229    * @return One of WalkerFactory#BIT_DESCENDANT, etc.
 230    */
 231   public int getAnalysisBits()
 232   {
 233     int bits = 0;
 234
 235     if (m_exprs != null)
 236     {
 237       int n = m_exprs.length;
 238
 239       for (int i = 0; i < n; i++)
 240       {
 241         int bit = m_exprs[i].getAnalysisBits();
 242         bits |= bit;
 243       }
 244     }
 245
 246     return bits;
 247   }
 248
 249   /**
 250    * Read the object from a serialization stream.
 251    *
 252    * @param stream Input stream to read from
 253    *
 254    * @throws java.io.IOException
 255    * @throws javax.xml.transform.TransformerException
 256    */
 257   private void readObject(java.io.ObjectInputStream stream)
 258           throws java.io.IOException, javax.xml.transform.TransformerException
 259   {
 260     try
 261     {
 262       stream.defaultReadObject();
 263       m_clones =  new IteratorPool(this);
 264     }
 265     catch (ClassNotFoundException cnfe)
 266     {
 267       throw new javax.xml.transform.TransformerException(cnfe);
 268     }
 269   }
 270
 271   /**
 272    * Get a cloned LocPathIterator that holds the same
 273    * position as this iterator.
 274    *
 275    * @return A clone of this iterator that holds the same node position.
 276    *
 277    * @throws CloneNotSupportedException
 278    */
 279   public Object clone() throws CloneNotSupportedException
 280   {
 281
 282     UnionPathIterator clone = (UnionPathIterator) super.clone();
 283     if (m_iterators != null)
 284     {
 285       int n = m_iterators.length;
 286
 287       clone.m_iterators = new DTMIterator[n];
 288
 289       for (int i = 0; i < n; i++)
 290       {
 291         clone.m_iterators[i] = (DTMIterator)m_iterators[i].clone();
 292       }
 293     }
 294
 295     return clone;
 296   }
 297
 298
 299   /**
 300    * Create a new location path iterator.
 301    *
 302    * @param compiler The Compiler which is creating
 303    * this expression.
 304    * @param opPos The position of this iterator in the
 305    *
 306    * @return New location path iterator.
 307    *
 308    * @throws javax.xml.transform.TransformerException
 309    */
 310   protected LocPathIterator createDTMIterator(
 311           Compiler compiler, int opPos) throws javax.xml.transform.TransformerException
 312   {
 313     LocPathIterator lpi = (LocPathIterator)WalkerFactory.newDTMIterator(compiler, opPos,
 314                                       (compiler.getLocationPathDepth() <= 0));
 315     return lpi;
 316   }
 317
 318   /**
 319    * Initialize the location path iterators.  Recursive.
 320    *
 321    * @param compiler The Compiler which is creating
 322    * this expression.
 323    * @param opPos The position of this iterator in the
 324    * opcode list from the compiler.
 325    * @param count The insert position of the iterator.
 326    *
 327    * @throws javax.xml.transform.TransformerException
 328    */
 329   protected void loadLocationPaths(Compiler compiler, int opPos, int count)
 330           throws javax.xml.transform.TransformerException
 331   {
 332
 333     // TODO: Handle unwrapped FilterExpr
 334     int steptype = compiler.getOp(opPos);
 335
 336     if (steptype == OpCodes.OP_LOCATIONPATH)
 337     {
 338       loadLocationPaths(compiler, compiler.getNextOpPos(opPos), count + 1);
 339
 340       m_exprs[count] = createDTMIterator(compiler, opPos);
 341       m_exprs[count].exprSetParent(this);
 342     }
 343     else
 344     {
 345
 346       // Have to check for unwrapped functions, which the LocPathIterator
 347       // doesn't handle.
 348       switch (steptype)
 349       {
 350       case OpCodes.OP_VARIABLE :
 351       case OpCodes.OP_EXTFUNCTION :
 352       case OpCodes.OP_FUNCTION :
 353       case OpCodes.OP_GROUP :
 354         loadLocationPaths(compiler, compiler.getNextOpPos(opPos), count + 1);
 355
 356         WalkingIterator iter =
 357           new WalkingIterator(compiler.getNamespaceContext());
 358         iter.exprSetParent(this);
 359
 360         if(compiler.getLocationPathDepth() <= 0)
 361           iter.setIsTopLevel(true);
 362
 363         iter.m_firstWalker = new org.apache.xpath.axes.FilterExprWalker(iter);
 364
 365         iter.m_firstWalker.init(compiler, opPos, steptype);
 366
 367         m_exprs[count] = iter;
 368         break;
 369       default :
 370         m_exprs = new LocPathIterator[count];
 371       }
 372     }
 373   }
 374
 375   /**
 376    *  Returns the next node in the set and advances the position of the
 377    * iterator in the set. After a DTMIterator is created, the first call
 378    * to nextNode() returns the first node in the set.
 379    * @return  The next <code>Node</code> in the set being iterated over, or
 380    *   <code>null</code> if there are no more members in that set.
 381    */
 382   public int nextNode()
 383   {
 384         if(m_foundLast)
 385                 return DTM.NULL;
 386
 387     // Loop through the iterators getting the current fetched
 388     // node, and get the earliest occuring in document order
 389     int earliestNode = DTM.NULL;
 390
 391     if (null != m_iterators)
 392     {
 393       int n = m_iterators.length;
 394       int iteratorUsed = -1;
 395
 396       for (int i = 0; i < n; i++)
 397       {
 398         int node = m_iterators[i].getCurrentNode();
 399
 400         if (DTM.NULL == node)
 401           continue;
 402         else if (DTM.NULL == earliestNode)
 403         {
 404           iteratorUsed = i;
 405           earliestNode = node;
 406         }
 407         else
 408         {
 409           if (node == earliestNode)
 410           {
 411
 412             // Found a duplicate, so skip past it.
 413             m_iterators[i].nextNode();
 414           }
 415           else
 416           {
 417             DTM dtm = getDTM(node);
 418
 419             if (dtm.isNodeAfter(node, earliestNode))
 420             {
 421               iteratorUsed = i;
 422               earliestNode = node;
 423             }
 424           }
 425         }
 426       }
 427
 428       if (DTM.NULL != earliestNode)
 429       {
 430         m_iterators[iteratorUsed].nextNode();
 431
 432         incrementCurrentPos();
 433       }
 434       else
 435         m_foundLast = true;
 436     }
 437
 438     m_lastFetched = earliestNode;
 439
 440     return earliestNode;
 441   }
 442
 443   /**
 444    * This function is used to fixup variables from QNames to stack frame
 445    * indexes at stylesheet build time.
 446    * @param vars List of QNames that correspond to variables.  This list
 447    * should be searched backwards for the first qualified name that
 448    * corresponds to the variable reference qname.  The position of the
 449    * QName in the vector from the start of the vector will be its position
 450    * in the stack frame (but variables above the globalsTop value will need
 451    * to be offset to the current stack frame).
 452    */
 453   public void fixupVariables(java.util.Vector vars, int globalsSize)
 454   {
 455     for (int i = 0; i < m_exprs.length; i++)
 456     {
 457       m_exprs[i].fixupVariables(vars, globalsSize);
 458     }
 459
 460   }
 461
 462   /**
 463    * The location path iterators, one for each
 464    * <a href="http://www.w3.org/TR/xpath#NT-LocationPath">location
 465    * path</a> contained in the union expression.
 466    * @serial
 467    */
 468   protected LocPathIterator[] m_exprs;
 469
 470
 471   /**
 472    * The location path iterators, one for each
 473    * <a href="http://www.w3.org/TR/xpath#NT-LocationPath">location
 474    * path</a> contained in the union expression.
 475    * @serial
 476    */
 477   protected DTMIterator[] m_iterators;
 478
 479   /**
 480    * Returns the axis being iterated, if it is known.
 481    *
 482    * @return Axis.CHILD, etc., or -1 if the axis is not known or is of multiple
 483    * types.
 484    */
 485   public int getAxis()
 486   {
 487     // Could be smarter.
 488     return -1;
 489   }
 490
 491   class iterOwner implements ExpressionOwner
 492   {
 493         int m_index;
 494
 495         iterOwner(int index)
 496         {
 497                 m_index = index;
 498         }
 499
 500     /**
 501      * @see ExpressionOwner#getExpression()
 502      */
 503     public Expression getExpression()
 504     {
 505       return m_exprs[m_index];
 506     }
 507
 508     /**
 509      * @see ExpressionOwner#setExpression(Expression)
 510      */
 511     public void setExpression(Expression exp)
 512     {
 513
 514         if(!(exp instanceof LocPathIterator))
 515         {
 516                 // Yuck.  Need FilterExprIter.  Or make it so m_exprs can be just
 517                 // plain expressions?
 518                 WalkingIterator wi = new WalkingIterator(getPrefixResolver());
 519                 FilterExprWalker few = new FilterExprWalker(wi);
 520                 wi.setFirstWalker(few);
 521                 few.setInnerExpression(exp);
 522                 wi.exprSetParent(UnionPathIterator.this);
 523                 few.exprSetParent(wi);
 524                 exp.exprSetParent(few);
 525                 exp = wi;
 526         }
 527         else
 528                 exp.exprSetParent(UnionPathIterator.this);
 529         m_exprs[m_index] = (LocPathIterator)exp;
 530     }
 531
 532   }
 533
 534   /**
 535    * @see org.apache.xpath.XPathVisitable#callVisitors(ExpressionOwner, XPathVisitor)
 536    */
 537   public void callVisitors(ExpressionOwner owner, XPathVisitor visitor)
 538   {
 539                 if(visitor.visitUnionPath(owner, this))
 540                 {
 541                         if(null != m_exprs)
 542                         {
 543                                 int n = m_exprs.length;
 544                                 for(int i = 0; i < n; i++)
 545                                 {
 546                                         m_exprs[i].callVisitors(new iterOwner(i), visitor);
 547                                 }
 548                         }
 549                 }
 550   }
 551
 552     /**
 553      * @see Expression#deepEquals(Expression)
 554      */
 555     public boolean deepEquals(Expression expr)
 556     {
 557       if (!super.deepEquals(expr))
 558             return false;
 559
 560       UnionPathIterator upi = (UnionPathIterator) expr;
 561
 562       if (null != m_exprs)
 563       {
 564         int n = m_exprs.length;
 565
 566         if((null == upi.m_exprs) || (upi.m_exprs.length != n))
 567                 return false;
 568
 569         for (int i = 0; i < n; i++)
 570         {
 571           if(!m_exprs[i].deepEquals(upi.m_exprs[i]))
 572                 return false;
 573         }
 574       }
 575       else if (null != upi.m_exprs)
 576       {
 577           return false;
 578       }
 579
 580       return true;
 581     }
 582
 583
 584 }