xpath/axes/NodeSequence.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the  "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id: NodeSequence.java 469367 2006-10-31 04:41:08Z minchau $
 */
package org.apache.xpath.axes;

import java.util.Vector;

import org.apache.xml.dtm.DTM;
import org.apache.xml.dtm.DTMFilter;
import org.apache.xml.dtm.DTMIterator;
import org.apache.xml.dtm.DTMManager;
import org.apache.xml.utils.NodeVector;
import org.apache.xpath.NodeSetDTM;
import org.apache.xpath.XPathContext;
import org.apache.xpath.objects.XObject;

/**
 * This class is the dynamic wrapper for a Xalan DTMIterator instance, and
 * provides random access capabilities.
 */
public class NodeSequence extends XObject
  implements DTMIterator, Cloneable, PathComponent
{
    static final long serialVersionUID = 3866261934726581044L;
  /** The index of the last node in the iteration. */
  protected int m_last = -1;

  /**
   * The index of the next node to be fetched.  Useful if this
   * is a cached iterator, and is being used as random access
   * NodeList.
   */
  protected int m_next = 0;

  /**
   * A cache of a list of nodes obtained from the iterator so far.
   * This list is appended to until the iterator is exhausted and
   * the cache is complete.
   * <p>
   * Multiple NodeSequence objects may share the same cache.
   */
  private IteratorCache m_cache;

  /**
   * If this iterator needs to cache nodes that are fetched, they
   * are stored in the Vector in the generic object.
   */
  protected NodeVector getVector() {
      NodeVector nv = (m_cache != null) ?  m_cache.getVector() : null;
      return nv;
  }

  /**
   * Get the cache (if any) of nodes obtained from
   * the iterator so far. Note that the cache keeps
   * growing until the iterator is walked to exhaustion,
   * at which point the cache is "complete".
   */
  private IteratorCache getCache() {
      return m_cache;
  }

  /**
   * Set the vector where nodes will be cached.
   */
  protected void SetVector(NodeVector v)
  {
  	setObject(v);
  }


  /**
   * If the iterator needs to cache nodes as they are fetched,
   * then this method returns true.
   */
  public boolean hasCache()
  {
    final NodeVector nv = getVector();
  	return (nv != null);
  }

  /**
   * If this NodeSequence has a cache, and that cache is
   * fully populated then this method returns true, otherwise
   * if there is no cache or it is not complete it returns false.
   */
  private boolean cacheComplete() {
      final boolean complete;
      if (m_cache != null) {
          complete = m_cache.isComplete();
      } else {
          complete = false;
      }
      return complete;
  }

  /**
   * If this NodeSequence has a cache, mark that it is complete.
   * This method should be called after the iterator is exhausted.
   */
  private void markCacheComplete() {
      NodeVector nv = getVector();
      if (nv != null) {
          m_cache.setCacheComplete(true);
      }
  }


  /**
   * The functional iterator that fetches nodes.
   */
  protected DTMIterator m_iter;

  /**
   * Set the functional iterator that fetches nodes.
   * @param iter The iterator that is to be contained.
   */
  public final void setIter(DTMIterator iter)
  {
  	m_iter = iter;
  }

  /**
   * Get the functional iterator that fetches nodes.
   * @return The contained iterator.
   */
  public final DTMIterator getContainedIter()
  {
  	return m_iter;
  }

  /**
   * The DTMManager to use if we're using a NodeVector only.
   * We may well want to do away with this, and store it in the NodeVector.
   */
  protected DTMManager m_dtmMgr;

  // ==== Constructors ====

  /**
   * Create a new NodeSequence from a (already cloned) iterator.
   *
   * @param iter Cloned (not static) DTMIterator.
   * @param context The initial context node.
   * @param xctxt The execution context.
   * @param shouldCacheNodes True if this sequence can random access.
   */
  private NodeSequence(DTMIterator iter, int context, XPathContext xctxt, boolean shouldCacheNodes)
  {
  	setIter(iter);
  	setRoot(context, xctxt);
  	setShouldCacheNodes(shouldCacheNodes);
  }

  /**
   * Create a new NodeSequence from a (already cloned) iterator.
   *
   * @param nodeVector
   */
  public NodeSequence(Object nodeVector)
  {
  	super(nodeVector);
    if (nodeVector instanceof NodeVector) {
        SetVector((NodeVector) nodeVector);
    }
  	if(null != nodeVector)
  	{
  		assertion(nodeVector instanceof NodeVector,
  			"Must have a NodeVector as the object for NodeSequence!");
  		if(nodeVector instanceof DTMIterator)
  		{
  			setIter((DTMIterator)nodeVector);
  			m_last = ((DTMIterator)nodeVector).getLength();
  		}

  	}
  }

  /**
   * Construct an empty XNodeSet object.  This is used to create a mutable
   * nodeset to which random nodes may be added.
   */
  private NodeSequence(DTMManager dtmMgr)
  {
    super(new NodeVector());
    m_last = 0;
    m_dtmMgr = dtmMgr;
  }


  /**
   * Create a new NodeSequence in an invalid (null) state.
   */
  public NodeSequence()
  {
      return;
  }


  /**
   * @see DTMIterator#getDTM(int)
   */
  public DTM getDTM(int nodeHandle)
  {
  	DTMManager mgr = getDTMManager();
  	if(null != mgr)
    	return getDTMManager().getDTM(nodeHandle);
    else
    {
    	assertion(false, "Can not get a DTM Unless a DTMManager has been set!");
    	return null;
    }
  }

  /**
   * @see DTMIterator#getDTMManager()
   */
  public DTMManager getDTMManager()
  {
    return m_dtmMgr;
  }

  /**
   * @see DTMIterator#getRoot()
   */
  public int getRoot()
  {
  	if(null != m_iter)
    	return m_iter.getRoot();
  	else
  	{
  		// NodeSetDTM will call this, and so it's not a good thing to throw
  		// an assertion here.
  		// assertion(false, "Can not get the root from a non-iterated NodeSequence!");
  		return DTM.NULL;
  	}
  }

  /**
   * @see DTMIterator#setRoot(int, Object)
   */
  public void setRoot(int nodeHandle, Object environment)
  {
  	if(null != m_iter)
  	{
  		XPathContext xctxt = (XPathContext)environment;
  		m_dtmMgr = xctxt.getDTMManager();
  		m_iter.setRoot(nodeHandle, environment);
  		if(!m_iter.isDocOrdered())
  		{
  			if(!hasCache())
  				setShouldCacheNodes(true);
  			runTo(-1);
  			m_next=0;
  		}
  	}
  	else
  		assertion(false, "Can not setRoot on a non-iterated NodeSequence!");
  }

  /**
   * @see DTMIterator#reset()
   */
  public void reset()
  {
  	m_next = 0;
  	// not resetting the iterator on purpose!!!
  }

  /**
   * @see DTMIterator#getWhatToShow()
   */
  public int getWhatToShow()
  {
    return hasCache() ? (DTMFilter.SHOW_ALL & ~DTMFilter.SHOW_ENTITY_REFERENCE)
    	: m_iter.getWhatToShow();
  }

  /**
   * @see DTMIterator#getExpandEntityReferences()
   */
  public boolean getExpandEntityReferences()
  {
  	if(null != m_iter)
  		return m_iter.getExpandEntityReferences();
  	else
    	return true;
  }

  /**
   * @see DTMIterator#nextNode()
   */
  public int nextNode()
  {
    // If the cache is on, and the node has already been found, then
    // just return from the list.
    NodeVector vec = getVector();
    if (null != vec)
    {
        // There is a cache
    	if(m_next < vec.size())
    	{
            // The node is in the cache, so just return it.
			int next = vec.elementAt(m_next);
	    	m_next++;
	    	return next;
    	}
    	else if(cacheComplete() || (-1 != m_last) || (null == m_iter))
    	{
    		m_next++;
    		return DTM.NULL;
    	}
    }

  if (null == m_iter)
    return DTM.NULL;

 	int next = m_iter.nextNode();
    if(DTM.NULL != next)
    {
    	if(hasCache())
    	{
    		if(m_iter.isDocOrdered())
    	    {
    			getVector().addElement(next);
    			m_next++;
    		}
    		else
    		{
    			int insertIndex = addNodeInDocOrder(next);
    			if(insertIndex >= 0)
    				m_next++;
    		}
    	}
    	else
    		m_next++;
    }
    else
    {
        // We have exhausted the iterator, and if there is a cache
        // it must have all nodes in it by now, so let the cache
        // know that it is complete.
        markCacheComplete();

    	m_last = m_next;
    	m_next++;
    }

    return next;
  }

  /**
   * @see DTMIterator#previousNode()
   */
  public int previousNode()
  {
  	if(hasCache())
  	{
  		if(m_next <= 0)
  			return DTM.NULL;
  		else
  		{
  			m_next--;
  			return item(m_next);
  		}
  	}
  	else
  	{
	    int n = m_iter.previousNode();
	    m_next = m_iter.getCurrentPos();
	    return m_next;
  	}
  }

  /**
   * @see DTMIterator#detach()
   */
  public void detach()
  {
  	if(null != m_iter)
  		m_iter.detach();
  	super.detach();
  }

  /**
   * Calling this with a value of false will cause the nodeset
   * to be cached.
   * @see DTMIterator#allowDetachToRelease(boolean)
   */
  public void allowDetachToRelease(boolean allowRelease)
  {
  	if((false == allowRelease) && !hasCache())
  	{
  		setShouldCacheNodes(true);
  	}

  	if(null != m_iter)
  		m_iter.allowDetachToRelease(allowRelease);
  	super.allowDetachToRelease(allowRelease);
  }

  /**
   * @see DTMIterator#getCurrentNode()
   */
  public int getCurrentNode()
  {
  	if(hasCache())
  	{
  		int currentIndex = m_next-1;
  		NodeVector vec = getVector();
  		if((currentIndex >= 0) && (currentIndex < vec.size()))
  			return vec.elementAt(currentIndex);
  		else
  			return DTM.NULL;
  	}

  	if(null != m_iter)
  	{
    	return m_iter.getCurrentNode();
  	}
  	else
  		return DTM.NULL;
  }

  /**
   * @see DTMIterator#isFresh()
   */
  public boolean isFresh()
  {
    return (0 == m_next);
  }

  /**
   * @see DTMIterator#setShouldCacheNodes(boolean)
   */
  public void setShouldCacheNodes(boolean b)
  {
    if (b)
    {
      if(!hasCache())
      {
        SetVector(new NodeVector());
      }
//	  else
//	    getVector().RemoveAllNoClear();  // Is this good?
    }
    else
      SetVector(null);
  }

  /**
   * @see DTMIterator#isMutable()
   */
  public boolean isMutable()
  {
    return hasCache(); // though may be surprising if it also has an iterator!
  }

  /**
   * @see DTMIterator#getCurrentPos()
   */
  public int getCurrentPos()
  {
    return m_next;
  }

  /**
   * @see DTMIterator#runTo(int)
   */
  public void runTo(int index)
  {
    int n;

    if (-1 == index)
    {
      int pos = m_next;
      while (DTM.NULL != (n = nextNode()));
      m_next = pos;
    }
    else if(m_next == index)
    {
      return;
    }
    else if(hasCache() && m_next < getVector().size())
    {
      m_next = index;
    }
    else if((null == getVector()) && (index < m_next))
    {
      while ((m_next >= index) && DTM.NULL != (n = previousNode()));
    }
    else
    {
      while ((m_next < index) && DTM.NULL != (n = nextNode()));
    }

  }

  /**
   * @see DTMIterator#setCurrentPos(int)
   */
  public void setCurrentPos(int i)
  {
  	runTo(i);
  }

  /**
   * @see DTMIterator#item(int)
   */
  public int item(int index)
  {
  	setCurrentPos(index);
  	int n = nextNode();
  	m_next = index;
  	return n;
  }

  /**
   * @see DTMIterator#setItem(int, int)
   */
  public void setItem(int node, int index)
  {
  	NodeVector vec = getVector();
  	if(null != vec)
  	{
        int oldNode = vec.elementAt(index);
        if (oldNode != node && m_cache.useCount() > 1) {
            /* If we are going to set the node at the given index
             * to a different value, and the cache is shared
             * (has a use count greater than 1)
             * then make a copy of the cache and use it
             * so we don't overwrite the value for other
             * users of the cache.
             */
            IteratorCache newCache = new IteratorCache();
            final NodeVector nv;
            try {
                nv = (NodeVector) vec.clone();
            } catch (CloneNotSupportedException e) {
                // This should never happen
                e.printStackTrace();
                RuntimeException rte = new RuntimeException(e.getMessage());
                throw rte;
            }
            newCache.setVector(nv);
            newCache.setCacheComplete(true);
            m_cache = newCache;
            vec = nv;

            // Keep our superclass informed of the current NodeVector
            super.setObject(nv);

            /* When we get to here the new cache has
             * a use count of 1 and when setting a
             * bunch of values on the same NodeSequence,
             * such as when sorting, we will keep setting
             * values in that same copy which has a use count of 1.
             */
        }
  		vec.setElementAt(node, index);
  		m_last = vec.size();
  	}
  	else
  		m_iter.setItem(node, index);
  }

  /**
   * @see DTMIterator#getLength()
   */
  public int getLength()
  {
    IteratorCache cache = getCache();

  	if(cache != null)
  	{
        // Nodes from the iterator are cached
        if (cache.isComplete()) {
            // All of the nodes from the iterator are cached
            // so just return the number of nodes in the cache
            NodeVector nv = cache.getVector();
            return nv.size();
        }

        // If this NodeSequence wraps a mutable nodeset, then
        // m_last will not reflect the size of the nodeset if
        // it has been mutated...
        if (m_iter instanceof NodeSetDTM)
        {
            return m_iter.getLength();
        }

	  	if(-1 == m_last)
	  	{
	  		int pos = m_next;
	  		runTo(-1);
	  		m_next = pos;
	  	}
	    return m_last;
  	}
  	else
  	{
  		return (-1 == m_last) ? (m_last = m_iter.getLength()) : m_last;
  	}
  }

  /**
   * Note: Not a deep clone.
   * @see DTMIterator#cloneWithReset()
   */
  public DTMIterator cloneWithReset() throws CloneNotSupportedException
  {
  	NodeSequence seq = (NodeSequence)super.clone();
    seq.m_next = 0;
    if (m_cache != null) {
        // In making this clone of an iterator we are making
        // another NodeSequence object it has a reference
        // to the same IteratorCache object as the original
        // so we need to remember that more than one
        // NodeSequence object shares the cache.
        m_cache.increaseUseCount();
    }

    return seq;
  }

  /**
   * Get a clone of this iterator, but don't reset the iteration in the
   * process, so that it may be used from the current position.
   * Note: Not a deep clone.
   *
   * @return A clone of this object.
   *
   * @throws CloneNotSupportedException
   */
  public Object clone() throws CloneNotSupportedException
  {
          NodeSequence clone = (NodeSequence) super.clone();
          if (null != m_iter) clone.m_iter = (DTMIterator) m_iter.clone();
          if (m_cache != null) {
              // In making this clone of an iterator we are making
              // another NodeSequence object it has a reference
              // to the same IteratorCache object as the original
              // so we need to remember that more than one
              // NodeSequence object shares the cache.
              m_cache.increaseUseCount();
          }

          return clone;
  }


  /**
   * @see DTMIterator#isDocOrdered()
   */
  public boolean isDocOrdered()
  {
  	if(null != m_iter)
  		return m_iter.isDocOrdered();
  	else
    	return true; // can't be sure?
  }

  /**
   * @see DTMIterator#getAxis()
   */
  public int getAxis()
  {
  	if(null != m_iter)
    	return m_iter.getAxis();
    else
    {
    	assertion(false, "Can not getAxis from a non-iterated node sequence!");
    	return 0;
    }
  }

  /**
   * @see PathComponent#getAnalysisBits()
   */
  public int getAnalysisBits()
  {
  	if((null != m_iter) && (m_iter instanceof PathComponent))
    	return ((PathComponent)m_iter).getAnalysisBits();
    else
    	return 0;
  }

  /**
   * @see org.apache.xpath.Expression#fixupVariables(Vector, int)
   */
  public void fixupVariables(Vector vars, int globalsSize)
  {
  	super.fixupVariables(vars, globalsSize);
  }

  /**
   * Add the node into a vector of nodes where it should occur in
   * document order.
   * @param node The node to be added.
   * @return insertIndex.
   * @throws RuntimeException thrown if this NodeSetDTM is not of
   * a mutable type.
   */
   protected int addNodeInDocOrder(int node)
   {
      assertion(hasCache(), "addNodeInDocOrder must be done on a mutable sequence!");

      int insertIndex = -1;

      NodeVector vec = getVector();

      // This needs to do a binary search, but a binary search
      // is somewhat tough because the sequence test involves
      // two nodes.
      int size = vec.size(), i;

      for (i = size - 1; i >= 0; i--)
      {
        int child = vec.elementAt(i);

        if (child == node)
        {
          i = -2; // Duplicate, suppress insert

          break;
        }

        DTM dtm = m_dtmMgr.getDTM(node);
        if (!dtm.isNodeAfter(node, child))
        {
          break;
        }
      }

      if (i != -2)
      {
        insertIndex = i + 1;

        vec.insertElementAt(node, insertIndex);
      }

      // checkDups();
      return insertIndex;
    } // end addNodeInDocOrder(Vector v, Object obj)

   /**
    * It used to be that many locations in the code simply
    * did an assignment to this.m_obj directly, rather than
    * calling the setObject(Object) method. The problem is
    * that our super-class would be updated on what the
    * cache associated with this NodeSequence, but
    * we wouldn't know ourselves.
    * <p>
    * All setting of m_obj is done through setObject() now,
    * and this method over-rides the super-class method.
    * So now we are in the loop have an opportunity
    * to update some caching information.
    *
    */
   protected void setObject(Object obj) {
       if (obj instanceof NodeVector) {
           // Keep our superclass informed of the current NodeVector
           // ... if we don't the smoketest fails (don't know why).
           super.setObject(obj);

           // A copy of the code of what SetVector() would do.
           NodeVector v = (NodeVector)obj;
           if (m_cache != null) {
               m_cache.setVector(v);
           } else if (v!=null) {
               m_cache = new IteratorCache();
               m_cache.setVector(v);
           }
       } else if (obj instanceof IteratorCache) {
           IteratorCache cache = (IteratorCache) obj;
           m_cache = cache;
           m_cache.increaseUseCount();

           // Keep our superclass informed of the current NodeVector
           super.setObject(cache.getVector());
       } else {
           super.setObject(obj);
       }

   }

   /**
    * Each NodeSequence object has an iterator which is "walked".
    * As an iterator is walked one obtains nodes from it.
    * As those nodes are obtained they may be cached, making
    * the next walking of a copy or clone of the iterator faster.
    * This field (m_cache) is a reference to such a cache,
    * which is populated as the iterator is walked.
    * <p>
    * Note that multiple NodeSequence objects may hold a
    * reference to the same cache, and also
    * (and this is important) the same iterator.
    * The iterator and its cache may be shared among
    * many NodeSequence objects.
    * <p>
    * If one of the NodeSequence objects walks ahead
    * of the others it fills in the cache.
    * As the others NodeSequence objects catch up they
    * get their values from
    * the cache rather than the iterator itself, so
    * the iterator is only ever walked once and everyone
    * benefits from the cache.
    * <p>
    * At some point the cache may be
    * complete due to walking to the end of one of
    * the copies of the iterator, and the cache is
    * then marked as "complete".
    * and the cache will have no more nodes added to it.
    * <p>
    * Its use-count is the number of NodeSequence objects that use it.
    */
   private final static class IteratorCache {
       /**
        * A list of nodes already obtained from the iterator.
        * As the iterator is walked the nodes obtained from
        * it are appended to this list.
        * <p>
        * Both an iterator and its corresponding cache can
        * be shared by multiple NodeSequence objects.
        * <p>
        * For example, consider three NodeSequence objects
        * ns1, ns2 and ns3 doing such sharing, and the
        * nodes to be obtaind from the iterator being
        * the sequence { 33, 11, 44, 22, 55 }.
        * <p>
        * If ns3.nextNode() is called 3 times the the
        * underlying iterator will have walked through
        * 33, 11, 55 and these three nodes will have been put
        * in the cache.
        * <p>
        * If ns2.nextNode() is called 2 times it will return
        * 33 and 11 from the cache, leaving the iterator alone.
        * <p>
        * If ns1.nextNode() is called 6 times it will return
        * 33 and 11 from the cache, then get 44, 22, 55 from
        * the iterator, and appending 44, 22, 55 to the cache.
        * On the sixth call it is found that the iterator is
        * exhausted and the cache is marked complete.
        * <p>
        * Should ns2 or ns3 have nextNode() called they will
        * know that the cache is complete, and they will
        * obtain all subsequent nodes from the cache.
        * <p>
        * Note that the underlying iterator, though shared
        * is only ever walked once.
        */
        private NodeVector m_vec2;

        /**
         * true if the associated iterator is exhausted and
         * all nodes obtained from it are in the cache.
         */
        private boolean m_isComplete2;

        private int m_useCount2;

        IteratorCache() {
            m_vec2 = null;
            m_isComplete2 = false;
            m_useCount2 = 1;
            return;
        }

        /**
         * Returns count of how many NodeSequence objects share this
         * IteratorCache object.
         */
        private int useCount() {
            return m_useCount2;
        }

        /**
         * This method is called when yet another
         * NodeSequence object uses, or shares
         * this same cache.
         *
         */
        private void increaseUseCount() {
            if (m_vec2 != null)
                m_useCount2++;

        }

        /**
         * Sets the NodeVector that holds the
         * growing list of nodes as they are appended
         * to the cached list.
         */
        private void setVector(NodeVector nv) {
            m_vec2 = nv;
            m_useCount2 = 1;
        }

        /**
         * Get the cached list of nodes obtained from
         * the iterator so far.
         */
        private NodeVector getVector() {
            return m_vec2;
        }

        /**
         * Call this method with 'true' if the
         * iterator is exhausted and the cached list
         * is complete, or no longer growing.
         */
        private void setCacheComplete(boolean b) {
            m_isComplete2 = b;

        }

        /**
         * Returns true if no cache is complete
         * and immutable.
         */
        private boolean isComplete() {
            return m_isComplete2;
        }
    }

    /**
     * Get the cached list of nodes appended with
     * values obtained from the iterator as
     * a NodeSequence is walked when its
     * nextNode() method is called.
     */
    protected IteratorCache getIteratorCache() {
        return m_cache;
    }
}