walkerfactory.java

来自「java jdk 1.4的源码」· Java 代码 · 共 1,871 行 · 第 1/5 页

/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 1999 The Apache Software Foundation.  All rights 
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:  
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Xalan" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written 
 *    permission, please contact [e-mail].
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation and was
 * originally based on software copyright (c) 1999, Lotus
 * Development Corporation., http://www.lotus.com.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */
package org.apache.xpath.axes;

import org.apache.xpath.compiler.OpCodes;
import org.apache.xpath.compiler.Compiler;
import org.apache.xpath.compiler.FunctionTable;
import org.apache.xpath.patterns.NodeTest;
import org.apache.xpath.patterns.StepPattern;
import org.apache.xpath.patterns.ContextMatchStepPattern;
import org.apache.xpath.patterns.FunctionPattern;
import org.apache.xpath.Expression;
import org.apache.xpath.objects.XNumber;
import org.apache.xalan.res.XSLMessages;
import org.apache.xpath.res.XPATHErrorResources;

import org.apache.xml.dtm.DTMFilter;
import org.apache.xml.dtm.DTMIterator;
import org.apache.xml.dtm.Axis;

/**
 * This class is both a factory for XPath location path expressions,
 * which are built from the opcode map output, and an analysis engine
 * for the location path expressions in order to provide optimization hints.
 */
public class WalkerFactory
{

  /**
   * <meta name="usage" content="advanced"/>
   * This method is for building an array of possible levels
   * where the target element(s) could be found for a match.
   * @param xpath The xpath that is executing.
   * @param context The current source tree context node.
   *
   * @param lpi The owning location path iterator.
   * @param compiler non-null reference to compiler object that has processed
   *                 the XPath operations into an opcode map.
   * @param stepOpCodePos The opcode position for the step.
   *
   * @return non-null AxesWalker derivative.
   *
   * @throws javax.xml.transform.TransformerException
   */
  static AxesWalker loadOneWalker(
          WalkingIterator lpi, Compiler compiler, int stepOpCodePos)
            throws javax.xml.transform.TransformerException
  {

    AxesWalker firstWalker = null;
    int stepType = compiler.getOp(stepOpCodePos);

    if (stepType != OpCodes.ENDOP)
    {

      // m_axesWalkers = new AxesWalker[1];
      // As we unwind from the recursion, create the iterators.
      firstWalker = createDefaultWalker(compiler, stepType, lpi, 0);

      firstWalker.init(compiler, stepOpCodePos, stepType);
    }

    return firstWalker;
  }

  /**
   * <meta name="usage" content="advanced"/>
   * This method is for building an array of possible levels
   * where the target element(s) could be found for a match.
   * @param xpath The xpath that is executing.
   * @param context The current source tree context node.
   *
   * @param lpi The owning location path iterator object.
   * @param compiler non-null reference to compiler object that has processed
   *                 the XPath operations into an opcode map.
   * @param stepOpCodePos The opcode position for the step.
   * @param stepIndex The top-level step index withing the iterator.
   *
   * @return non-null AxesWalker derivative.
   *
   * @throws javax.xml.transform.TransformerException
   */
  static AxesWalker loadWalkers(
          WalkingIterator lpi, Compiler compiler, int stepOpCodePos, int stepIndex)
            throws javax.xml.transform.TransformerException
  {

    int stepType;
    AxesWalker firstWalker = null;
    AxesWalker walker, prevWalker = null;

    int analysis = analyze(compiler, stepOpCodePos, stepIndex);

    while (OpCodes.ENDOP != (stepType = compiler.getOp(stepOpCodePos)))
    {
      walker = createDefaultWalker(compiler, stepOpCodePos, lpi, analysis);

      walker.init(compiler, stepOpCodePos, stepType);
      walker.exprSetParent(lpi);

      // walker.setAnalysis(analysis);
      if (null == firstWalker)
      {
        firstWalker = walker;
      }
      else
      {
        prevWalker.setNextWalker(walker);
        walker.setPrevWalker(prevWalker);
      }

      prevWalker = walker;
      stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);

      if (stepOpCodePos < 0)
        break;
    }

    return firstWalker;
  }
  
  public static boolean isSet(int analysis, int bits)
  {
    return (0 != (analysis & bits));
  }
  
  public static void diagnoseIterator(String name, int analysis, Compiler compiler)
  {
    System.out.println(compiler.toString()+", "+name+", "
                             + Integer.toBinaryString(analysis) + ", "
                             + getAnalysisString(analysis));
  }

  /**
   * Create a new LocPathIterator iterator.  The exact type of iterator
   * returned is based on an analysis of the XPath operations.
   *
   * @param compiler non-null reference to compiler object that has processed
   *                 the XPath operations into an opcode map.
   * @param opPos The position of the operation code for this itterator.
   *
   * @return non-null reference to a LocPathIterator or derivative.
   *
   * @throws javax.xml.transform.TransformerException
   */
  public static DTMIterator newDTMIterator(
          Compiler compiler, int opPos,
          boolean isTopLevel)
            throws javax.xml.transform.TransformerException
  {

    int firstStepPos = compiler.getFirstChildPos(opPos);
    int analysis = analyze(compiler, firstStepPos, 0);
    boolean isOneStep = isOneStep(analysis);
    DTMIterator iter;

    // Is the iteration a one-step attribute pattern (i.e. select="@foo")?
    if (isOneStep && walksSelfOnly(analysis) && 
        isWild(analysis) && !hasPredicate(analysis))
    {
      if (DEBUG_ITERATOR_CREATION)
        diagnoseIterator("SelfIteratorNoPredicate", analysis, compiler);

      // Then use a simple iteration of the attributes, with node test 
      // and predicate testing.
      iter = new SelfIteratorNoPredicate(compiler, opPos, analysis);
    }
    // Is the iteration exactly one child step?
    else if (walksChildrenOnly(analysis) && isOneStep)
    {

      // Does the pattern specify *any* child with no predicate? (i.e. select="child::node()".
      if (isWild(analysis) && !hasPredicate(analysis))
      {
        if (DEBUG_ITERATOR_CREATION)
          diagnoseIterator("ChildIterator", analysis, compiler);

        // Use simple child iteration without any test.
        iter = new ChildIterator(compiler, opPos, analysis);
      }
      else
      {
        if (DEBUG_ITERATOR_CREATION)
          diagnoseIterator("ChildTestIterator", analysis, compiler);

        // Else use simple node test iteration with predicate test.
        iter = new ChildTestIterator(compiler, opPos, analysis);
      }
    }
    // Is the iteration a one-step attribute pattern (i.e. select="@foo")?
    else if (isOneStep && walksAttributes(analysis))
    {
      if (DEBUG_ITERATOR_CREATION)
        diagnoseIterator("AttributeIterator", analysis, compiler);

      // Then use a simple iteration of the attributes, with node test 
      // and predicate testing.
      iter = new AttributeIterator(compiler, opPos, analysis);
    }
    else if(isOneStep && !walksFilteredList(analysis))
    {
      if( !walksNamespaces(analysis) 
      && (walksInDocOrder(analysis) || isSet(analysis, BIT_PARENT)))
      {
        if (false || DEBUG_ITERATOR_CREATION)
          diagnoseIterator("OneStepIteratorForward", analysis, compiler);
  
        // Then use a simple iteration of the attributes, with node test 
        // and predicate testing.
        iter = new OneStepIteratorForward(compiler, opPos, analysis);
      }
      else
      {
        if (false || DEBUG_ITERATOR_CREATION)
          diagnoseIterator("OneStepIterator", analysis, compiler);
  
        // Then use a simple iteration of the attributes, with node test 
        // and predicate testing.
        iter = new OneStepIterator(compiler, opPos, analysis);
      }
    }

    // Analysis of "//center":
    // bits: 1001000000001010000000000000011
    // count: 3
    // root
    // child:node()
    // BIT_DESCENDANT_OR_SELF
    // It's highly possible that we should have a seperate bit set for 
    // "//foo" patterns.
    // For at least the time being, we can't optimize patterns like 
    // "//table[3]", because this has to be analyzed as 
    // "/descendant-or-self::node()/table[3]" in order for the indexes 
    // to work right.
    else if (isOptimizableForDescendantIterator(compiler, firstStepPos, 0)
              // && getStepCount(analysis) <= 3 
              // && walksDescendants(analysis) 
              // && walksSubtreeOnlyFromRootOrContext(analysis)
             )
    {
      if (DEBUG_ITERATOR_CREATION)
        diagnoseIterator("DescendantIterator", analysis, compiler);

      iter = new DescendantIterator(compiler, opPos, analysis);
    }
    else
    { 
      if(isNaturalDocOrder(compiler, firstStepPos, 0, analysis))
      {
        if (false || DEBUG_ITERATOR_CREATION)
        {
          diagnoseIterator("WalkingIterator", analysis, compiler);
        }
  
        iter = new WalkingIterator(compiler, opPos, analysis, true);
      }
      else
      {
//        if (DEBUG_ITERATOR_CREATION)
//          diagnoseIterator("MatchPatternIterator", analysis, compiler);
//
//        return new MatchPatternIterator(compiler, opPos, analysis);
        if (DEBUG_ITERATOR_CREATION)
          diagnoseIterator("WalkingIteratorSorted", analysis, compiler);

        iter = new WalkingIteratorSorted(compiler, opPos, analysis, true);
      }
    }
    if(iter instanceof LocPathIterator)
      ((LocPathIterator)iter).setIsTopLevel(isTopLevel);
      
    return iter;
  }
  
  /**
   * Special purpose function to see if we can optimize the pattern for 
   * a DescendantIterator.
   *
   * @param compiler non-null reference to compiler object that has processed
   *                 the XPath operations into an opcode map.
   * @param stepOpCodePos The opcode position for the step.
   * @param stepIndex The top-level step index withing the iterator.
   *
   * @return 32 bits as an integer that give information about the location
   * path as a whole.
   *
   * @throws javax.xml.transform.TransformerException
   */
  public static int getAxisFromStep(
          Compiler compiler, int stepOpCodePos)
            throws javax.xml.transform.TransformerException
  {

    int stepType = compiler.getOp(stepOpCodePos);

    switch (stepType)
    {
    case OpCodes.FROM_FOLLOWING :
      return Axis.FOLLOWING;
    case OpCodes.FROM_FOLLOWING_SIBLINGS :
      return Axis.FOLLOWINGSIBLING;
    case OpCodes.FROM_PRECEDING :
      return Axis.PRECEDING;
    case OpCodes.FROM_PRECEDING_SIBLINGS :
      return Axis.PRECEDINGSIBLING;
    case OpCodes.FROM_PARENT :
      return Axis.PARENT;
    case OpCodes.FROM_NAMESPACE :
      return Axis.NAMESPACE;
    case OpCodes.FROM_ANCESTORS :
      return Axis.ANCESTOR;
    case OpCodes.FROM_ANCESTORS_OR_SELF :
      return Axis.ANCESTORORSELF;
    case OpCodes.FROM_ATTRIBUTES :
      return Axis.ATTRIBUTE;
    case OpCodes.FROM_ROOT :
      return Axis.ROOT;
    case OpCodes.FROM_CHILDREN :
      return Axis.CHILD;
    case OpCodes.FROM_DESCENDANTS_OR_SELF :
      return Axis.DESCENDANTORSELF;