0001: /*
0002: * Copyright 1999-2004 The Apache Software Foundation.
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: /*
0017: * $Id: WalkerFactory.java,v 1.30 2005/01/23 01:02:11 mcnamara Exp $
0018: */
0019: package org.apache.xpath.axes;
0020:
0021: import org.apache.xalan.res.XSLMessages;
0022: import org.apache.xml.dtm.Axis;
0023: import org.apache.xml.dtm.DTMFilter;
0024: import org.apache.xml.dtm.DTMIterator;
0025: import org.apache.xpath.Expression;
0026: import org.apache.xpath.compiler.Compiler;
0027: import org.apache.xpath.compiler.FunctionTable;
0028: import org.apache.xpath.compiler.OpCodes;
0029: import org.apache.xpath.objects.XNumber;
0030: import org.apache.xpath.patterns.ContextMatchStepPattern;
0031: import org.apache.xpath.patterns.FunctionPattern;
0032: import org.apache.xpath.patterns.NodeTest;
0033: import org.apache.xpath.patterns.StepPattern;
0034: import org.apache.xpath.res.XPATHErrorResources;
0035:
0036: /**
0037: * This class is both a factory for XPath location path expressions,
0038: * which are built from the opcode map output, and an analysis engine
0039: * for the location path expressions in order to provide optimization hints.
0040: */
0041: public class WalkerFactory {
0042:
0043: /**
0044: * This method is for building an array of possible levels
0045: * where the target element(s) could be found for a match.
0046: * @param lpi The owning location path iterator.
0047: * @param compiler non-null reference to compiler object that has processed
0048: * the XPath operations into an opcode map.
0049: * @param stepOpCodePos The opcode position for the step.
0050: *
0051: * @return non-null AxesWalker derivative.
0052: *
0053: * @throws javax.xml.transform.TransformerException
0054: * @xsl.usage advanced
0055: */
0056: static AxesWalker loadOneWalker(WalkingIterator lpi,
0057: Compiler compiler, int stepOpCodePos)
0058: throws javax.xml.transform.TransformerException {
0059:
0060: AxesWalker firstWalker = null;
0061: int stepType = compiler.getOp(stepOpCodePos);
0062:
0063: if (stepType != OpCodes.ENDOP) {
0064:
0065: // m_axesWalkers = new AxesWalker[1];
0066: // As we unwind from the recursion, create the iterators.
0067: firstWalker = createDefaultWalker(compiler, stepType, lpi,
0068: 0);
0069:
0070: firstWalker.init(compiler, stepOpCodePos, stepType);
0071: }
0072:
0073: return firstWalker;
0074: }
0075:
0076: /**
0077: * This method is for building an array of possible levels
0078: * where the target element(s) could be found for a match.
0079: * @param lpi The owning location path iterator object.
0080: * @param compiler non-null reference to compiler object that has processed
0081: * the XPath operations into an opcode map.
0082: * @param stepOpCodePos The opcode position for the step.
0083: * @param stepIndex The top-level step index withing the iterator.
0084: *
0085: * @return non-null AxesWalker derivative.
0086: *
0087: * @throws javax.xml.transform.TransformerException
0088: * @xsl.usage advanced
0089: */
0090: static AxesWalker loadWalkers(WalkingIterator lpi,
0091: Compiler compiler, int stepOpCodePos, int stepIndex)
0092: throws javax.xml.transform.TransformerException {
0093:
0094: int stepType;
0095: AxesWalker firstWalker = null;
0096: AxesWalker walker, prevWalker = null;
0097:
0098: int analysis = analyze(compiler, stepOpCodePos, stepIndex);
0099:
0100: while (OpCodes.ENDOP != (stepType = compiler
0101: .getOp(stepOpCodePos))) {
0102: walker = createDefaultWalker(compiler, stepOpCodePos, lpi,
0103: analysis);
0104:
0105: walker.init(compiler, stepOpCodePos, stepType);
0106: walker.exprSetParent(lpi);
0107:
0108: // walker.setAnalysis(analysis);
0109: if (null == firstWalker) {
0110: firstWalker = walker;
0111: } else {
0112: prevWalker.setNextWalker(walker);
0113: walker.setPrevWalker(prevWalker);
0114: }
0115:
0116: prevWalker = walker;
0117: stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
0118:
0119: if (stepOpCodePos < 0)
0120: break;
0121: }
0122:
0123: return firstWalker;
0124: }
0125:
0126: public static boolean isSet(int analysis, int bits) {
0127: return (0 != (analysis & bits));
0128: }
0129:
0130: public static void diagnoseIterator(String name, int analysis,
0131: Compiler compiler) {
0132: System.out.println(compiler.toString() + ", " + name + ", "
0133: + Integer.toBinaryString(analysis) + ", "
0134: + getAnalysisString(analysis));
0135: }
0136:
0137: /**
0138: * Create a new LocPathIterator iterator. The exact type of iterator
0139: * returned is based on an analysis of the XPath operations.
0140: *
0141: * @param compiler non-null reference to compiler object that has processed
0142: * the XPath operations into an opcode map.
0143: * @param opPos The position of the operation code for this itterator.
0144: *
0145: * @return non-null reference to a LocPathIterator or derivative.
0146: *
0147: * @throws javax.xml.transform.TransformerException
0148: */
0149: public static DTMIterator newDTMIterator(Compiler compiler,
0150: int opPos, boolean isTopLevel)
0151: throws javax.xml.transform.TransformerException {
0152:
0153: int firstStepPos = compiler.getFirstChildPos(opPos);
0154: int analysis = analyze(compiler, firstStepPos, 0);
0155: boolean isOneStep = isOneStep(analysis);
0156: DTMIterator iter;
0157:
0158: // Is the iteration a one-step attribute pattern (i.e. select="@foo")?
0159: if (isOneStep && walksSelfOnly(analysis) && isWild(analysis)
0160: && !hasPredicate(analysis)) {
0161: if (DEBUG_ITERATOR_CREATION)
0162: diagnoseIterator("SelfIteratorNoPredicate", analysis,
0163: compiler);
0164:
0165: // Then use a simple iteration of the attributes, with node test
0166: // and predicate testing.
0167: iter = new SelfIteratorNoPredicate(compiler, opPos,
0168: analysis);
0169: }
0170: // Is the iteration exactly one child step?
0171: else if (walksChildrenOnly(analysis) && isOneStep) {
0172:
0173: // Does the pattern specify *any* child with no predicate? (i.e. select="child::node()".
0174: if (isWild(analysis) && !hasPredicate(analysis)) {
0175: if (DEBUG_ITERATOR_CREATION)
0176: diagnoseIterator("ChildIterator", analysis,
0177: compiler);
0178:
0179: // Use simple child iteration without any test.
0180: iter = new ChildIterator(compiler, opPos, analysis);
0181: } else {
0182: if (DEBUG_ITERATOR_CREATION)
0183: diagnoseIterator("ChildTestIterator", analysis,
0184: compiler);
0185:
0186: // Else use simple node test iteration with predicate test.
0187: iter = new ChildTestIterator(compiler, opPos, analysis);
0188: }
0189: }
0190: // Is the iteration a one-step attribute pattern (i.e. select="@foo")?
0191: else if (isOneStep && walksAttributes(analysis)) {
0192: if (DEBUG_ITERATOR_CREATION)
0193: diagnoseIterator("AttributeIterator", analysis,
0194: compiler);
0195:
0196: // Then use a simple iteration of the attributes, with node test
0197: // and predicate testing.
0198: iter = new AttributeIterator(compiler, opPos, analysis);
0199: } else if (isOneStep && !walksFilteredList(analysis)) {
0200: if (!walksNamespaces(analysis)
0201: && (walksInDocOrder(analysis) || isSet(analysis,
0202: BIT_PARENT))) {
0203: if (false || DEBUG_ITERATOR_CREATION)
0204: diagnoseIterator("OneStepIteratorForward",
0205: analysis, compiler);
0206:
0207: // Then use a simple iteration of the attributes, with node test
0208: // and predicate testing.
0209: iter = new OneStepIteratorForward(compiler, opPos,
0210: analysis);
0211: } else {
0212: if (false || DEBUG_ITERATOR_CREATION)
0213: diagnoseIterator("OneStepIterator", analysis,
0214: compiler);
0215:
0216: // Then use a simple iteration of the attributes, with node test
0217: // and predicate testing.
0218: iter = new OneStepIterator(compiler, opPos, analysis);
0219: }
0220: }
0221:
0222: // Analysis of "//center":
0223: // bits: 1001000000001010000000000000011
0224: // count: 3
0225: // root
0226: // child:node()
0227: // BIT_DESCENDANT_OR_SELF
0228: // It's highly possible that we should have a seperate bit set for
0229: // "//foo" patterns.
0230: // For at least the time being, we can't optimize patterns like
0231: // "//table[3]", because this has to be analyzed as
0232: // "/descendant-or-self::node()/table[3]" in order for the indexes
0233: // to work right.
0234: else if (isOptimizableForDescendantIterator(compiler,
0235: firstStepPos, 0)
0236: // && getStepCount(analysis) <= 3
0237: // && walksDescendants(analysis)
0238: // && walksSubtreeOnlyFromRootOrContext(analysis)
0239: ) {
0240: if (DEBUG_ITERATOR_CREATION)
0241: diagnoseIterator("DescendantIterator", analysis,
0242: compiler);
0243:
0244: iter = new DescendantIterator(compiler, opPos, analysis);
0245: } else {
0246: if (isNaturalDocOrder(compiler, firstStepPos, 0, analysis)) {
0247: if (false || DEBUG_ITERATOR_CREATION) {
0248: diagnoseIterator("WalkingIterator", analysis,
0249: compiler);
0250: }
0251:
0252: iter = new WalkingIterator(compiler, opPos, analysis,
0253: true);
0254: } else {
0255: // if (DEBUG_ITERATOR_CREATION)
0256: // diagnoseIterator("MatchPatternIterator", analysis, compiler);
0257: //
0258: // return new MatchPatternIterator(compiler, opPos, analysis);
0259: if (DEBUG_ITERATOR_CREATION)
0260: diagnoseIterator("WalkingIteratorSorted", analysis,
0261: compiler);
0262:
0263: iter = new WalkingIteratorSorted(compiler, opPos,
0264: analysis, true);
0265: }
0266: }
0267: if (iter instanceof LocPathIterator)
0268: ((LocPathIterator) iter).setIsTopLevel(isTopLevel);
0269:
0270: return iter;
0271: }
0272:
0273: /**
0274: * Special purpose function to see if we can optimize the pattern for
0275: * a DescendantIterator.
0276: *
0277: * @param compiler non-null reference to compiler object that has processed
0278: * the XPath operations into an opcode map.
0279: * @param stepOpCodePos The opcode position for the step.
0280: *
0281: * @return 32 bits as an integer that give information about the location
0282: * path as a whole.
0283: *
0284: * @throws javax.xml.transform.TransformerException
0285: */
0286: public static int getAxisFromStep(Compiler compiler,
0287: int stepOpCodePos)
0288: throws javax.xml.transform.TransformerException {
0289:
0290: int stepType = compiler.getOp(stepOpCodePos);
0291:
0292: switch (stepType) {
0293: case OpCodes.FROM_FOLLOWING:
0294: return Axis.FOLLOWING;
0295: case OpCodes.FROM_FOLLOWING_SIBLINGS:
0296: return Axis.FOLLOWINGSIBLING;
0297: case OpCodes.FROM_PRECEDING:
0298: return Axis.PRECEDING;
0299: case OpCodes.FROM_PRECEDING_SIBLINGS:
0300: return Axis.PRECEDINGSIBLING;
0301: case OpCodes.FROM_PARENT:
0302: return Axis.PARENT;
0303: case OpCodes.FROM_NAMESPACE:
0304: return Axis.NAMESPACE;
0305: case OpCodes.FROM_ANCESTORS:
0306: return Axis.ANCESTOR;
0307: case OpCodes.FROM_ANCESTORS_OR_SELF:
0308: return Axis.ANCESTORORSELF;
0309: case OpCodes.FROM_ATTRIBUTES:
0310: return Axis.ATTRIBUTE;
0311: case OpCodes.FROM_ROOT:
0312: return Axis.ROOT;
0313: case OpCodes.FROM_CHILDREN:
0314: return Axis.CHILD;
0315: case OpCodes.FROM_DESCENDANTS_OR_SELF:
0316: return Axis.DESCENDANTORSELF;
0317: case OpCodes.FROM_DESCENDANTS:
0318: return Axis.DESCENDANT;
0319: case OpCodes.FROM_SELF:
0320: return Axis.SELF;
0321: case OpCodes.OP_EXTFUNCTION:
0322: case OpCodes.OP_FUNCTION:
0323: case OpCodes.OP_GROUP:
0324: case OpCodes.OP_VARIABLE:
0325: return Axis.FILTEREDLIST;
0326: }
0327:
0328: throw new RuntimeException(XSLMessages.createXPATHMessage(
0329: XPATHErrorResources.ER_NULL_ERROR_HANDLER,
0330: new Object[] { Integer.toString(stepType) })); //"Programmer's assertion: unknown opcode: "
0331: //+ stepType);
0332: }
0333:
0334: /**
0335: * Get a corresponding BIT_XXX from an axis.
0336: * @param axis One of Axis.ANCESTOR, etc.
0337: * @return One of BIT_ANCESTOR, etc.
0338: */
0339: static public int getAnalysisBitFromAxes(int axis) {
0340: switch (axis) // Generate new traverser
0341: {
0342: case Axis.ANCESTOR:
0343: return BIT_ANCESTOR;
0344: case Axis.ANCESTORORSELF:
0345: return BIT_ANCESTOR_OR_SELF;
0346: case Axis.ATTRIBUTE:
0347: return BIT_ATTRIBUTE;
0348: case Axis.CHILD:
0349: return BIT_CHILD;
0350: case Axis.DESCENDANT:
0351: return BIT_DESCENDANT;
0352: case Axis.DESCENDANTORSELF:
0353: return BIT_DESCENDANT_OR_SELF;
0354: case Axis.FOLLOWING:
0355: return BIT_FOLLOWING;
0356: case Axis.FOLLOWINGSIBLING:
0357: return BIT_FOLLOWING_SIBLING;
0358: case Axis.NAMESPACE:
0359: case Axis.NAMESPACEDECLS:
0360: return BIT_NAMESPACE;
0361: case Axis.PARENT:
0362: return BIT_PARENT;
0363: case Axis.PRECEDING:
0364: return BIT_PRECEDING;
0365: case Axis.PRECEDINGSIBLING:
0366: return BIT_PRECEDING_SIBLING;
0367: case Axis.SELF:
0368: return BIT_SELF;
0369: case Axis.ALLFROMNODE:
0370: return BIT_DESCENDANT_OR_SELF;
0371: // case Axis.PRECEDINGANDANCESTOR :
0372: case Axis.DESCENDANTSFROMROOT:
0373: case Axis.ALL:
0374: case Axis.DESCENDANTSORSELFFROMROOT:
0375: return BIT_ANY_DESCENDANT_FROM_ROOT;
0376: case Axis.ROOT:
0377: return BIT_ROOT;
0378: case Axis.FILTEREDLIST:
0379: return BIT_FILTER;
0380: default:
0381: return BIT_FILTER;
0382: }
0383: }
0384:
0385: static boolean functionProximateOrContainsProximate(
0386: Compiler compiler, int opPos) {
0387: int endFunc = opPos + compiler.getOp(opPos + 1) - 1;
0388: opPos = compiler.getFirstChildPos(opPos);
0389: int funcID = compiler.getOp(opPos);
0390: // System.out.println("funcID: "+funcID);
0391: // System.out.println("opPos: "+opPos);
0392: // System.out.println("endFunc: "+endFunc);
0393: switch (funcID) {
0394: case FunctionTable.FUNC_LAST:
0395: case FunctionTable.FUNC_POSITION:
0396: return true;
0397: default:
0398: opPos++;
0399: int i = 0;
0400: for (int p = opPos; p < endFunc; p = compiler
0401: .getNextOpPos(p), i++) {
0402: int innerExprOpPos = p + 2;
0403: int argOp = compiler.getOp(innerExprOpPos);
0404: boolean prox = isProximateInnerExpr(compiler,
0405: innerExprOpPos);
0406: if (prox)
0407: return true;
0408: }
0409:
0410: }
0411: return false;
0412: }
0413:
0414: static boolean isProximateInnerExpr(Compiler compiler, int opPos) {
0415: int op = compiler.getOp(opPos);
0416: int innerExprOpPos = opPos + 2;
0417: switch (op) {
0418: case OpCodes.OP_ARGUMENT:
0419: if (isProximateInnerExpr(compiler, innerExprOpPos))
0420: return true;
0421: break;
0422: case OpCodes.OP_VARIABLE:
0423: case OpCodes.OP_NUMBERLIT:
0424: case OpCodes.OP_LITERAL:
0425: case OpCodes.OP_LOCATIONPATH:
0426: break; // OK
0427: case OpCodes.OP_FUNCTION:
0428: boolean isProx = functionProximateOrContainsProximate(
0429: compiler, opPos);
0430: if (isProx)
0431: return true;
0432: break;
0433: case OpCodes.OP_GT:
0434: case OpCodes.OP_GTE:
0435: case OpCodes.OP_LT:
0436: case OpCodes.OP_LTE:
0437: case OpCodes.OP_EQUALS:
0438: int leftPos = compiler.getFirstChildPos(op);
0439: int rightPos = compiler.getNextOpPos(leftPos);
0440: isProx = isProximateInnerExpr(compiler, leftPos);
0441: if (isProx)
0442: return true;
0443: isProx = isProximateInnerExpr(compiler, rightPos);
0444: if (isProx)
0445: return true;
0446: break;
0447: default:
0448: return true; // be conservative...
0449: }
0450: return false;
0451: }
0452:
0453: /**
0454: * Tell if the predicates need to have proximity knowledge.
0455: */
0456: public static boolean mightBeProximate(Compiler compiler,
0457: int opPos, int stepType)
0458: throws javax.xml.transform.TransformerException {
0459:
0460: boolean mightBeProximate = false;
0461: int argLen;
0462:
0463: switch (stepType) {
0464: case OpCodes.OP_VARIABLE:
0465: case OpCodes.OP_EXTFUNCTION:
0466: case OpCodes.OP_FUNCTION:
0467: case OpCodes.OP_GROUP:
0468: argLen = compiler.getArgLength(opPos);
0469: break;
0470: default:
0471: argLen = compiler.getArgLengthOfStep(opPos);
0472: }
0473:
0474: int predPos = compiler.getFirstPredicateOpPos(opPos);
0475: int count = 0;
0476:
0477: while (OpCodes.OP_PREDICATE == compiler.getOp(predPos)) {
0478: count++;
0479:
0480: int innerExprOpPos = predPos + 2;
0481: int predOp = compiler.getOp(innerExprOpPos);
0482:
0483: switch (predOp) {
0484: case OpCodes.OP_VARIABLE:
0485: return true; // Would need more smarts to tell if this could be a number or not!
0486: case OpCodes.OP_LOCATIONPATH:
0487: // OK.
0488: break;
0489: case OpCodes.OP_NUMBER:
0490: case OpCodes.OP_NUMBERLIT:
0491: return true; // that's all she wrote!
0492: case OpCodes.OP_FUNCTION:
0493: boolean isProx = functionProximateOrContainsProximate(
0494: compiler, innerExprOpPos);
0495: if (isProx)
0496: return true;
0497: break;
0498: case OpCodes.OP_GT:
0499: case OpCodes.OP_GTE:
0500: case OpCodes.OP_LT:
0501: case OpCodes.OP_LTE:
0502: case OpCodes.OP_EQUALS:
0503: int leftPos = compiler.getFirstChildPos(innerExprOpPos);
0504: int rightPos = compiler.getNextOpPos(leftPos);
0505: isProx = isProximateInnerExpr(compiler, leftPos);
0506: if (isProx)
0507: return true;
0508: isProx = isProximateInnerExpr(compiler, rightPos);
0509: if (isProx)
0510: return true;
0511: break;
0512: default:
0513: return true; // be conservative...
0514: }
0515:
0516: predPos = compiler.getNextOpPos(predPos);
0517: }
0518:
0519: return mightBeProximate;
0520: }
0521:
0522: /**
0523: * Special purpose function to see if we can optimize the pattern for
0524: * a DescendantIterator.
0525: *
0526: * @param compiler non-null reference to compiler object that has processed
0527: * the XPath operations into an opcode map.
0528: * @param stepOpCodePos The opcode position for the step.
0529: * @param stepIndex The top-level step index withing the iterator.
0530: *
0531: * @return 32 bits as an integer that give information about the location
0532: * path as a whole.
0533: *
0534: * @throws javax.xml.transform.TransformerException
0535: */
0536: private static boolean isOptimizableForDescendantIterator(
0537: Compiler compiler, int stepOpCodePos, int stepIndex)
0538: throws javax.xml.transform.TransformerException {
0539:
0540: int stepType;
0541: int stepCount = 0;
0542: boolean foundDorDS = false;
0543: boolean foundSelf = false;
0544: boolean foundDS = false;
0545:
0546: int nodeTestType = OpCodes.NODETYPE_NODE;
0547:
0548: while (OpCodes.ENDOP != (stepType = compiler
0549: .getOp(stepOpCodePos))) {
0550: // The DescendantIterator can only do one node test. If there's more
0551: // than one, use another iterator.
0552: if (nodeTestType != OpCodes.NODETYPE_NODE
0553: && nodeTestType != OpCodes.NODETYPE_ROOT)
0554: return false;
0555:
0556: stepCount++;
0557: if (stepCount > 3)
0558: return false;
0559:
0560: boolean mightBeProximate = mightBeProximate(compiler,
0561: stepOpCodePos, stepType);
0562: if (mightBeProximate)
0563: return false;
0564:
0565: switch (stepType) {
0566: case OpCodes.FROM_FOLLOWING:
0567: case OpCodes.FROM_FOLLOWING_SIBLINGS:
0568: case OpCodes.FROM_PRECEDING:
0569: case OpCodes.FROM_PRECEDING_SIBLINGS:
0570: case OpCodes.FROM_PARENT:
0571: case OpCodes.OP_VARIABLE:
0572: case OpCodes.OP_EXTFUNCTION:
0573: case OpCodes.OP_FUNCTION:
0574: case OpCodes.OP_GROUP:
0575: case OpCodes.FROM_NAMESPACE:
0576: case OpCodes.FROM_ANCESTORS:
0577: case OpCodes.FROM_ANCESTORS_OR_SELF:
0578: case OpCodes.FROM_ATTRIBUTES:
0579: case OpCodes.MATCH_ATTRIBUTE:
0580: case OpCodes.MATCH_ANY_ANCESTOR:
0581: case OpCodes.MATCH_IMMEDIATE_ANCESTOR:
0582: return false;
0583: case OpCodes.FROM_ROOT:
0584: if (1 != stepCount)
0585: return false;
0586: break;
0587: case OpCodes.FROM_CHILDREN:
0588: if (!foundDS && !(foundDorDS && foundSelf))
0589: return false;
0590: break;
0591: case OpCodes.FROM_DESCENDANTS_OR_SELF:
0592: foundDS = true;
0593: case OpCodes.FROM_DESCENDANTS:
0594: if (3 == stepCount)
0595: return false;
0596: foundDorDS = true;
0597: break;
0598: case OpCodes.FROM_SELF:
0599: if (1 != stepCount)
0600: return false;
0601: foundSelf = true;
0602: break;
0603: default:
0604: throw new RuntimeException(
0605: XSLMessages
0606: .createXPATHMessage(
0607: XPATHErrorResources.ER_NULL_ERROR_HANDLER,
0608: new Object[] { Integer
0609: .toString(stepType) })); //"Programmer's assertion: unknown opcode: "
0610: // + stepType);
0611: }
0612:
0613: nodeTestType = compiler.getStepTestType(stepOpCodePos);
0614:
0615: int nextStepOpCodePos = compiler
0616: .getNextStepPos(stepOpCodePos);
0617:
0618: if (nextStepOpCodePos < 0)
0619: break;
0620:
0621: if (OpCodes.ENDOP != compiler.getOp(nextStepOpCodePos)) {
0622: if (compiler.countPredicates(stepOpCodePos) > 0) {
0623: return false;
0624: }
0625: }
0626:
0627: stepOpCodePos = nextStepOpCodePos;
0628: }
0629:
0630: return true;
0631: }
0632:
0633: /**
0634: * Analyze the location path and return 32 bits that give information about
0635: * the location path as a whole. See the BIT_XXX constants for meaning about
0636: * each of the bits.
0637: *
0638: * @param compiler non-null reference to compiler object that has processed
0639: * the XPath operations into an opcode map.
0640: * @param stepOpCodePos The opcode position for the step.
0641: * @param stepIndex The top-level step index withing the iterator.
0642: *
0643: * @return 32 bits as an integer that give information about the location
0644: * path as a whole.
0645: *
0646: * @throws javax.xml.transform.TransformerException
0647: */
0648: private static int analyze(Compiler compiler, int stepOpCodePos,
0649: int stepIndex)
0650: throws javax.xml.transform.TransformerException {
0651:
0652: int stepType;
0653: int stepCount = 0;
0654: int analysisResult = 0x00000000; // 32 bits of analysis
0655:
0656: while (OpCodes.ENDOP != (stepType = compiler
0657: .getOp(stepOpCodePos))) {
0658: stepCount++;
0659:
0660: // String namespace = compiler.getStepNS(stepOpCodePos);
0661: // boolean isNSWild = (null != namespace)
0662: // ? namespace.equals(NodeTest.WILD) : false;
0663: // String localname = compiler.getStepLocalName(stepOpCodePos);
0664: // boolean isWild = (null != localname) ? localname.equals(NodeTest.WILD) : false;
0665: boolean predAnalysis = analyzePredicate(compiler,
0666: stepOpCodePos, stepType);
0667:
0668: if (predAnalysis)
0669: analysisResult |= BIT_PREDICATE;
0670:
0671: switch (stepType) {
0672: case OpCodes.OP_VARIABLE:
0673: case OpCodes.OP_EXTFUNCTION:
0674: case OpCodes.OP_FUNCTION:
0675: case OpCodes.OP_GROUP:
0676: analysisResult |= BIT_FILTER;
0677: break;
0678: case OpCodes.FROM_ROOT:
0679: analysisResult |= BIT_ROOT;
0680: break;
0681: case OpCodes.FROM_ANCESTORS:
0682: analysisResult |= BIT_ANCESTOR;
0683: break;
0684: case OpCodes.FROM_ANCESTORS_OR_SELF:
0685: analysisResult |= BIT_ANCESTOR_OR_SELF;
0686: break;
0687: case OpCodes.FROM_ATTRIBUTES:
0688: analysisResult |= BIT_ATTRIBUTE;
0689: break;
0690: case OpCodes.FROM_NAMESPACE:
0691: analysisResult |= BIT_NAMESPACE;
0692: break;
0693: case OpCodes.FROM_CHILDREN:
0694: analysisResult |= BIT_CHILD;
0695: break;
0696: case OpCodes.FROM_DESCENDANTS:
0697: analysisResult |= BIT_DESCENDANT;
0698: break;
0699: case OpCodes.FROM_DESCENDANTS_OR_SELF:
0700:
0701: // Use a special bit to to make sure we get the right analysis of "//foo".
0702: if (2 == stepCount && BIT_ROOT == analysisResult) {
0703: analysisResult |= BIT_ANY_DESCENDANT_FROM_ROOT;
0704: }
0705:
0706: analysisResult |= BIT_DESCENDANT_OR_SELF;
0707: break;
0708: case OpCodes.FROM_FOLLOWING:
0709: analysisResult |= BIT_FOLLOWING;
0710: break;
0711: case OpCodes.FROM_FOLLOWING_SIBLINGS:
0712: analysisResult |= BIT_FOLLOWING_SIBLING;
0713: break;
0714: case OpCodes.FROM_PRECEDING:
0715: analysisResult |= BIT_PRECEDING;
0716: break;
0717: case OpCodes.FROM_PRECEDING_SIBLINGS:
0718: analysisResult |= BIT_PRECEDING_SIBLING;
0719: break;
0720: case OpCodes.FROM_PARENT:
0721: analysisResult |= BIT_PARENT;
0722: break;
0723: case OpCodes.FROM_SELF:
0724: analysisResult |= BIT_SELF;
0725: break;
0726: case OpCodes.MATCH_ATTRIBUTE:
0727: analysisResult |= (BIT_MATCH_PATTERN | BIT_ATTRIBUTE);
0728: break;
0729: case OpCodes.MATCH_ANY_ANCESTOR:
0730: analysisResult |= (BIT_MATCH_PATTERN | BIT_ANCESTOR);
0731: break;
0732: case OpCodes.MATCH_IMMEDIATE_ANCESTOR:
0733: analysisResult |= (BIT_MATCH_PATTERN | BIT_PARENT);
0734: break;
0735: default:
0736: throw new RuntimeException(
0737: XSLMessages
0738: .createXPATHMessage(
0739: XPATHErrorResources.ER_NULL_ERROR_HANDLER,
0740: new Object[] { Integer
0741: .toString(stepType) })); //"Programmer's assertion: unknown opcode: "
0742: //+ stepType);
0743: }
0744:
0745: if (OpCodes.NODETYPE_NODE == compiler
0746: .getOp(stepOpCodePos + 3)) // child::node()
0747: {
0748: analysisResult |= BIT_NODETEST_ANY;
0749: }
0750:
0751: stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
0752:
0753: if (stepOpCodePos < 0)
0754: break;
0755: }
0756:
0757: analysisResult |= (stepCount & BITS_COUNT);
0758:
0759: return analysisResult;
0760: }
0761:
0762: /**
0763: * Tell if the given axis goes downword. Bogus name, if you can think of
0764: * a better one, please do tell. This really has to do with inverting
0765: * attribute axis.
0766: * @param axis One of Axis.XXX.
0767: * @return true if the axis is not a child axis and does not go up from
0768: * the axis root.
0769: */
0770: public static boolean isDownwardAxisOfMany(int axis) {
0771: return ((Axis.DESCENDANTORSELF == axis)
0772: || (Axis.DESCENDANT == axis)
0773: || (Axis.FOLLOWING == axis)
0774: // || (Axis.FOLLOWINGSIBLING == axis)
0775: || (Axis.PRECEDING == axis)
0776: // || (Axis.PRECEDINGSIBLING == axis)
0777: );
0778: }
0779:
0780: /**
0781: * Read a <a href="http://www.w3.org/TR/xpath#location-paths">LocationPath</a>
0782: * as a generalized match pattern. What this means is that the LocationPath
0783: * is read backwards, as a test on a given node, to see if it matches the
0784: * criteria of the selection, and ends up at the context node. Essentially,
0785: * this is a backwards query from a given node, to find the context node.
0786: * <p>So, the selection "foo/daz[2]" is, in non-abreviated expanded syntax,
0787: * "self::node()/following-sibling::foo/child::daz[position()=2]".
0788: * Taking this as a match pattern for a probable node, it works out to
0789: * "self::daz/parent::foo[child::daz[position()=2 and isPrevStepNode()]
0790: * precedingSibling::node()[isContextNodeOfLocationPath()]", adding magic
0791: * isPrevStepNode and isContextNodeOfLocationPath operations. Predicates in
0792: * the location path have to be executed by the following step,
0793: * because they have to know the context of their execution.
0794: *
0795: * @param mpi The MatchPatternIterator to which the steps will be attached.
0796: * @param compiler The compiler that holds the syntax tree/op map to
0797: * construct from.
0798: * @param stepOpCodePos The current op code position within the opmap.
0799: * @param stepIndex The top-level step index withing the iterator.
0800: *
0801: * @return A StepPattern object, which may contain relative StepPatterns.
0802: *
0803: * @throws javax.xml.transform.TransformerException
0804: */
0805: static StepPattern loadSteps(MatchPatternIterator mpi,
0806: Compiler compiler, int stepOpCodePos, int stepIndex)
0807: throws javax.xml.transform.TransformerException {
0808: if (DEBUG_PATTERN_CREATION) {
0809: System.out.println("================");
0810: System.out.println("loadSteps for: "
0811: + compiler.getPatternString());
0812: }
0813: int stepType;
0814: StepPattern step = null;
0815: StepPattern firstStep = null, prevStep = null;
0816: int analysis = analyze(compiler, stepOpCodePos, stepIndex);
0817:
0818: while (OpCodes.ENDOP != (stepType = compiler
0819: .getOp(stepOpCodePos))) {
0820: step = createDefaultStepPattern(compiler, stepOpCodePos,
0821: mpi, analysis, firstStep, prevStep);
0822:
0823: if (null == firstStep) {
0824: firstStep = step;
0825: } else {
0826:
0827: //prevStep.setNextWalker(step);
0828: step.setRelativePathPattern(prevStep);
0829: }
0830:
0831: prevStep = step;
0832: stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
0833:
0834: if (stepOpCodePos < 0)
0835: break;
0836: }
0837:
0838: int axis = Axis.SELF;
0839: int paxis = Axis.SELF;
0840: StepPattern tail = step;
0841: for (StepPattern pat = step; null != pat; pat = pat
0842: .getRelativePathPattern()) {
0843: int nextAxis = pat.getAxis();
0844: //int nextPaxis = pat.getPredicateAxis();
0845: pat.setAxis(axis);
0846:
0847: // The predicate axis can't be moved!!! Test Axes103
0848: // pat.setPredicateAxis(paxis);
0849:
0850: // If we have an attribute or namespace axis that went up, then
0851: // it won't find the attribute in the inverse, since the select-to-match
0852: // axes are not invertable (an element is a parent of an attribute, but
0853: // and attribute is not a child of an element).
0854: // If we don't do the magic below, then "@*/ancestor-or-self::*" gets
0855: // inverted for match to "self::*/descendant-or-self::@*/parent::node()",
0856: // which obviously won't work.
0857: // So we will rewrite this as:
0858: // "self::*/descendant-or-self::*/attribute::*/parent::node()"
0859: // Child has to be rewritten a little differently:
0860: // select: "@*/parent::*"
0861: // inverted match: "self::*/child::@*/parent::node()"
0862: // rewrite: "self::*/attribute::*/parent::node()"
0863: // Axes that go down in the select, do not have to have special treatment
0864: // in the rewrite. The following inverted match will still not select
0865: // anything.
0866: // select: "@*/child::*"
0867: // inverted match: "self::*/parent::@*/parent::node()"
0868: // Lovely business, this.
0869: // -sb
0870: int whatToShow = pat.getWhatToShow();
0871: if (whatToShow == DTMFilter.SHOW_ATTRIBUTE
0872: || whatToShow == DTMFilter.SHOW_NAMESPACE) {
0873: int newAxis = (whatToShow == DTMFilter.SHOW_ATTRIBUTE) ? Axis.ATTRIBUTE
0874: : Axis.NAMESPACE;
0875: if (isDownwardAxisOfMany(axis)) {
0876: StepPattern attrPat = new StepPattern(whatToShow,
0877: pat.getNamespace(), pat.getLocalName(),
0878: //newAxis, pat.getPredicateAxis);
0879: newAxis, 0); // don't care about the predicate axis
0880: XNumber score = pat.getStaticScore();
0881: pat.setNamespace(null);
0882: pat.setLocalName(NodeTest.WILD);
0883: attrPat.setPredicates(pat.getPredicates());
0884: pat.setPredicates(null);
0885: pat.setWhatToShow(DTMFilter.SHOW_ELEMENT);
0886: StepPattern rel = pat.getRelativePathPattern();
0887: pat.setRelativePathPattern(attrPat);
0888: attrPat.setRelativePathPattern(rel);
0889: attrPat.setStaticScore(score);
0890:
0891: // This is needed to inverse a following pattern, because of the
0892: // wacky Xalan rules for following from an attribute. See axes108.
0893: // By these rules, following from an attribute is not strictly
0894: // inverseable.
0895: if (Axis.PRECEDING == pat.getAxis())
0896: pat.setAxis(Axis.PRECEDINGANDANCESTOR);
0897:
0898: else if (Axis.DESCENDANT == pat.getAxis())
0899: pat.setAxis(Axis.DESCENDANTORSELF);
0900:
0901: pat = attrPat;
0902: } else if (Axis.CHILD == pat.getAxis()) {
0903: // In this case just change the axis.
0904: // pat.setWhatToShow(whatToShow);
0905: pat.setAxis(Axis.ATTRIBUTE);
0906: }
0907: }
0908: axis = nextAxis;
0909: //paxis = nextPaxis;
0910: tail = pat;
0911: }
0912:
0913: if (axis < Axis.ALL) {
0914: StepPattern selfPattern = new ContextMatchStepPattern(axis,
0915: paxis);
0916: // We need to keep the new nodetest from affecting the score...
0917: XNumber score = tail.getStaticScore();
0918: tail.setRelativePathPattern(selfPattern);
0919: tail.setStaticScore(score);
0920: selfPattern.setStaticScore(score);
0921: }
0922:
0923: if (DEBUG_PATTERN_CREATION) {
0924: System.out
0925: .println("Done loading steps: " + step.toString());
0926:
0927: System.out.println("");
0928: }
0929: return step; // start from last pattern?? //firstStep;
0930: }
0931:
0932: /**
0933: * Create a StepPattern that is contained within a LocationPath.
0934: *
0935: *
0936: * @param compiler The compiler that holds the syntax tree/op map to
0937: * construct from.
0938: * @param stepOpCodePos The current op code position within the opmap.
0939: * @param mpi The MatchPatternIterator to which the steps will be attached.
0940: * @param analysis 32 bits of analysis, from which the type of AxesWalker
0941: * may be influenced.
0942: * @param tail The step that is the first step analyzed, but the last
0943: * step in the relative match linked list, i.e. the tail.
0944: * May be null.
0945: * @param head The step that is the current head of the relative
0946: * match step linked list.
0947: * May be null.
0948: *
0949: * @return the head of the list.
0950: *
0951: * @throws javax.xml.transform.TransformerException
0952: */
0953: private static StepPattern createDefaultStepPattern(
0954: Compiler compiler, int opPos, MatchPatternIterator mpi,
0955: int analysis, StepPattern tail, StepPattern head)
0956: throws javax.xml.transform.TransformerException {
0957:
0958: int stepType = compiler.getOp(opPos);
0959: boolean simpleInit = false;
0960: int totalNumberWalkers = (analysis & BITS_COUNT);
0961: boolean prevIsOneStepDown = true;
0962: int firstStepPos = compiler.getFirstChildPos(opPos);
0963:
0964: int whatToShow = compiler.getWhatToShow(opPos);
0965: StepPattern ai = null;
0966: int axis, predicateAxis;
0967:
0968: switch (stepType) {
0969: case OpCodes.OP_VARIABLE:
0970: case OpCodes.OP_EXTFUNCTION:
0971: case OpCodes.OP_FUNCTION:
0972: case OpCodes.OP_GROUP:
0973: prevIsOneStepDown = false;
0974:
0975: Expression expr;
0976:
0977: switch (stepType) {
0978: case OpCodes.OP_VARIABLE:
0979: case OpCodes.OP_EXTFUNCTION:
0980: case OpCodes.OP_FUNCTION:
0981: case OpCodes.OP_GROUP:
0982: expr = compiler.compile(opPos);
0983: break;
0984: default:
0985: expr = compiler.compile(opPos + 2);
0986: }
0987:
0988: axis = Axis.FILTEREDLIST;
0989: predicateAxis = Axis.FILTEREDLIST;
0990: ai = new FunctionPattern(expr, axis, predicateAxis);
0991: simpleInit = true;
0992: break;
0993: case OpCodes.FROM_ROOT:
0994: whatToShow = DTMFilter.SHOW_DOCUMENT
0995: | DTMFilter.SHOW_DOCUMENT_FRAGMENT;
0996:
0997: axis = Axis.ROOT;
0998: predicateAxis = Axis.ROOT;
0999: ai = new StepPattern(DTMFilter.SHOW_DOCUMENT
1000: | DTMFilter.SHOW_DOCUMENT_FRAGMENT, axis,
1001: predicateAxis);
1002: break;
1003: case OpCodes.FROM_ATTRIBUTES:
1004: whatToShow = DTMFilter.SHOW_ATTRIBUTE;
1005: axis = Axis.PARENT;
1006: predicateAxis = Axis.ATTRIBUTE;
1007: // ai = new StepPattern(whatToShow, Axis.SELF, Axis.SELF);
1008: break;
1009: case OpCodes.FROM_NAMESPACE:
1010: whatToShow = DTMFilter.SHOW_NAMESPACE;
1011: axis = Axis.PARENT;
1012: predicateAxis = Axis.NAMESPACE;
1013: // ai = new StepPattern(whatToShow, axis, predicateAxis);
1014: break;
1015: case OpCodes.FROM_ANCESTORS:
1016: axis = Axis.DESCENDANT;
1017: predicateAxis = Axis.ANCESTOR;
1018: break;
1019: case OpCodes.FROM_CHILDREN:
1020: axis = Axis.PARENT;
1021: predicateAxis = Axis.CHILD;
1022: break;
1023: case OpCodes.FROM_ANCESTORS_OR_SELF:
1024: axis = Axis.DESCENDANTORSELF;
1025: predicateAxis = Axis.ANCESTORORSELF;
1026: break;
1027: case OpCodes.FROM_SELF:
1028: axis = Axis.SELF;
1029: predicateAxis = Axis.SELF;
1030: break;
1031: case OpCodes.FROM_PARENT:
1032: axis = Axis.CHILD;
1033: predicateAxis = Axis.PARENT;
1034: break;
1035: case OpCodes.FROM_PRECEDING_SIBLINGS:
1036: axis = Axis.FOLLOWINGSIBLING;
1037: predicateAxis = Axis.PRECEDINGSIBLING;
1038: break;
1039: case OpCodes.FROM_PRECEDING:
1040: axis = Axis.FOLLOWING;
1041: predicateAxis = Axis.PRECEDING;
1042: break;
1043: case OpCodes.FROM_FOLLOWING_SIBLINGS:
1044: axis = Axis.PRECEDINGSIBLING;
1045: predicateAxis = Axis.FOLLOWINGSIBLING;
1046: break;
1047: case OpCodes.FROM_FOLLOWING:
1048: axis = Axis.PRECEDING;
1049: predicateAxis = Axis.FOLLOWING;
1050: break;
1051: case OpCodes.FROM_DESCENDANTS_OR_SELF:
1052: axis = Axis.ANCESTORORSELF;
1053: predicateAxis = Axis.DESCENDANTORSELF;
1054: break;
1055: case OpCodes.FROM_DESCENDANTS:
1056: axis = Axis.ANCESTOR;
1057: predicateAxis = Axis.DESCENDANT;
1058: break;
1059: default:
1060: throw new RuntimeException(XSLMessages.createXPATHMessage(
1061: XPATHErrorResources.ER_NULL_ERROR_HANDLER,
1062: new Object[] { Integer.toString(stepType) })); //"Programmer's assertion: unknown opcode: "
1063: //+ stepType);
1064: }
1065: if (null == ai) {
1066: whatToShow = compiler.getWhatToShow(opPos); // %REVIEW%
1067: ai = new StepPattern(whatToShow, compiler.getStepNS(opPos),
1068: compiler.getStepLocalName(opPos), axis,
1069: predicateAxis);
1070: }
1071:
1072: if (false || DEBUG_PATTERN_CREATION) {
1073: System.out.print("new step: " + ai);
1074: System.out.print(", axis: " + Axis.getNames(ai.getAxis()));
1075: System.out.print(", predAxis: "
1076: + Axis.getNames(ai.getAxis()));
1077: System.out.print(", what: ");
1078: System.out.print(" ");
1079: ai.debugWhatToShow(ai.getWhatToShow());
1080: }
1081:
1082: int argLen = compiler.getFirstPredicateOpPos(opPos);
1083:
1084: ai.setPredicates(compiler.getCompiledPredicates(argLen));
1085:
1086: return ai;
1087: }
1088:
1089: /**
1090: * Analyze a step and give information about it's predicates. Right now this
1091: * just returns true or false if the step has a predicate.
1092: *
1093: * @param compiler non-null reference to compiler object that has processed
1094: * the XPath operations into an opcode map.
1095: * @param opPos The opcode position for the step.
1096: * @param stepType The type of step, one of OP_GROUP, etc.
1097: *
1098: * @return true if step has a predicate.
1099: *
1100: * @throws javax.xml.transform.TransformerException
1101: */
1102: static boolean analyzePredicate(Compiler compiler, int opPos,
1103: int stepType)
1104: throws javax.xml.transform.TransformerException {
1105:
1106: int argLen;
1107:
1108: switch (stepType) {
1109: case OpCodes.OP_VARIABLE:
1110: case OpCodes.OP_EXTFUNCTION:
1111: case OpCodes.OP_FUNCTION:
1112: case OpCodes.OP_GROUP:
1113: argLen = compiler.getArgLength(opPos);
1114: break;
1115: default:
1116: argLen = compiler.getArgLengthOfStep(opPos);
1117: }
1118:
1119: int pos = compiler.getFirstPredicateOpPos(opPos);
1120: int nPredicates = compiler.countPredicates(pos);
1121:
1122: return (nPredicates > 0) ? true : false;
1123: }
1124:
1125: /**
1126: * Create the proper Walker from the axes type.
1127: *
1128: * @param compiler non-null reference to compiler object that has processed
1129: * the XPath operations into an opcode map.
1130: * @param opPos The opcode position for the step.
1131: * @param lpi The owning location path iterator.
1132: * @param analysis 32 bits of analysis, from which the type of AxesWalker
1133: * may be influenced.
1134: *
1135: * @return non-null reference to AxesWalker derivative.
1136: * @throws RuntimeException if the input is bad.
1137: */
1138: private static AxesWalker createDefaultWalker(Compiler compiler,
1139: int opPos, WalkingIterator lpi, int analysis) {
1140:
1141: AxesWalker ai = null;
1142: int stepType = compiler.getOp(opPos);
1143:
1144: /*
1145: System.out.println("0: "+compiler.getOp(opPos));
1146: System.out.println("1: "+compiler.getOp(opPos+1));
1147: System.out.println("2: "+compiler.getOp(opPos+2));
1148: System.out.println("3: "+compiler.getOp(opPos+3));
1149: System.out.println("4: "+compiler.getOp(opPos+4));
1150: System.out.println("5: "+compiler.getOp(opPos+5));
1151: */
1152: boolean simpleInit = false;
1153: int totalNumberWalkers = (analysis & BITS_COUNT);
1154: boolean prevIsOneStepDown = true;
1155:
1156: switch (stepType) {
1157: case OpCodes.OP_VARIABLE:
1158: case OpCodes.OP_EXTFUNCTION:
1159: case OpCodes.OP_FUNCTION:
1160: case OpCodes.OP_GROUP:
1161: prevIsOneStepDown = false;
1162:
1163: if (DEBUG_WALKER_CREATION)
1164: System.out.println("new walker: FilterExprWalker: "
1165: + analysis + ", " + compiler.toString());
1166:
1167: ai = new FilterExprWalker(lpi);
1168: simpleInit = true;
1169: break;
1170: case OpCodes.FROM_ROOT:
1171: ai = new AxesWalker(lpi, Axis.ROOT);
1172: break;
1173: case OpCodes.FROM_ANCESTORS:
1174: prevIsOneStepDown = false;
1175: ai = new ReverseAxesWalker(lpi, Axis.ANCESTOR);
1176: break;
1177: case OpCodes.FROM_ANCESTORS_OR_SELF:
1178: prevIsOneStepDown = false;
1179: ai = new ReverseAxesWalker(lpi, Axis.ANCESTORORSELF);
1180: break;
1181: case OpCodes.FROM_ATTRIBUTES:
1182: ai = new AxesWalker(lpi, Axis.ATTRIBUTE);
1183: break;
1184: case OpCodes.FROM_NAMESPACE:
1185: ai = new AxesWalker(lpi, Axis.NAMESPACE);
1186: break;
1187: case OpCodes.FROM_CHILDREN:
1188: ai = new AxesWalker(lpi, Axis.CHILD);
1189: break;
1190: case OpCodes.FROM_DESCENDANTS:
1191: prevIsOneStepDown = false;
1192: ai = new AxesWalker(lpi, Axis.DESCENDANT);
1193: break;
1194: case OpCodes.FROM_DESCENDANTS_OR_SELF:
1195: prevIsOneStepDown = false;
1196: ai = new AxesWalker(lpi, Axis.DESCENDANTORSELF);
1197: break;
1198: case OpCodes.FROM_FOLLOWING:
1199: prevIsOneStepDown = false;
1200: ai = new AxesWalker(lpi, Axis.FOLLOWING);
1201: break;
1202: case OpCodes.FROM_FOLLOWING_SIBLINGS:
1203: prevIsOneStepDown = false;
1204: ai = new AxesWalker(lpi, Axis.FOLLOWINGSIBLING);
1205: break;
1206: case OpCodes.FROM_PRECEDING:
1207: prevIsOneStepDown = false;
1208: ai = new ReverseAxesWalker(lpi, Axis.PRECEDING);
1209: break;
1210: case OpCodes.FROM_PRECEDING_SIBLINGS:
1211: prevIsOneStepDown = false;
1212: ai = new ReverseAxesWalker(lpi, Axis.PRECEDINGSIBLING);
1213: break;
1214: case OpCodes.FROM_PARENT:
1215: prevIsOneStepDown = false;
1216: ai = new ReverseAxesWalker(lpi, Axis.PARENT);
1217: break;
1218: case OpCodes.FROM_SELF:
1219: ai = new AxesWalker(lpi, Axis.SELF);
1220: break;
1221: default:
1222: throw new RuntimeException(XSLMessages.createXPATHMessage(
1223: XPATHErrorResources.ER_NULL_ERROR_HANDLER,
1224: new Object[] { Integer.toString(stepType) })); //"Programmer's assertion: unknown opcode: "
1225: //+ stepType);
1226: }
1227:
1228: if (simpleInit) {
1229: ai.initNodeTest(DTMFilter.SHOW_ALL);
1230: } else {
1231: int whatToShow = compiler.getWhatToShow(opPos);
1232:
1233: /*
1234: System.out.print("construct: ");
1235: NodeTest.debugWhatToShow(whatToShow);
1236: System.out.println("or stuff: "+(whatToShow & (DTMFilter.SHOW_ATTRIBUTE
1237: | DTMFilter.SHOW_ELEMENT
1238: | DTMFilter.SHOW_PROCESSING_INSTRUCTION)));
1239: */
1240: if ((0 == (whatToShow & (DTMFilter.SHOW_ATTRIBUTE
1241: | DTMFilter.SHOW_NAMESPACE | DTMFilter.SHOW_ELEMENT | DTMFilter.SHOW_PROCESSING_INSTRUCTION)))
1242: || (whatToShow == DTMFilter.SHOW_ALL))
1243: ai.initNodeTest(whatToShow);
1244: else {
1245: ai.initNodeTest(whatToShow, compiler.getStepNS(opPos),
1246: compiler.getStepLocalName(opPos));
1247: }
1248: }
1249:
1250: return ai;
1251: }
1252:
1253: public static String getAnalysisString(int analysis) {
1254: StringBuffer buf = new StringBuffer();
1255: buf.append("count: " + getStepCount(analysis) + " ");
1256: if ((analysis & BIT_NODETEST_ANY) != 0) {
1257: buf.append("NTANY|");
1258: }
1259: if ((analysis & BIT_PREDICATE) != 0) {
1260: buf.append("PRED|");
1261: }
1262: if ((analysis & BIT_ANCESTOR) != 0) {
1263: buf.append("ANC|");
1264: }
1265: if ((analysis & BIT_ANCESTOR_OR_SELF) != 0) {
1266: buf.append("ANCOS|");
1267: }
1268: if ((analysis & BIT_ATTRIBUTE) != 0) {
1269: buf.append("ATTR|");
1270: }
1271: if ((analysis & BIT_CHILD) != 0) {
1272: buf.append("CH|");
1273: }
1274: if ((analysis & BIT_DESCENDANT) != 0) {
1275: buf.append("DESC|");
1276: }
1277: if ((analysis & BIT_DESCENDANT_OR_SELF) != 0) {
1278: buf.append("DESCOS|");
1279: }
1280: if ((analysis & BIT_FOLLOWING) != 0) {
1281: buf.append("FOL|");
1282: }
1283: if ((analysis & BIT_FOLLOWING_SIBLING) != 0) {
1284: buf.append("FOLS|");
1285: }
1286: if ((analysis & BIT_NAMESPACE) != 0) {
1287: buf.append("NS|");
1288: }
1289: if ((analysis & BIT_PARENT) != 0) {
1290: buf.append("P|");
1291: }
1292: if ((analysis & BIT_PRECEDING) != 0) {
1293: buf.append("PREC|");
1294: }
1295: if ((analysis & BIT_PRECEDING_SIBLING) != 0) {
1296: buf.append("PRECS|");
1297: }
1298: if ((analysis & BIT_SELF) != 0) {
1299: buf.append(".|");
1300: }
1301: if ((analysis & BIT_FILTER) != 0) {
1302: buf.append("FLT|");
1303: }
1304: if ((analysis & BIT_ROOT) != 0) {
1305: buf.append("R|");
1306: }
1307: return buf.toString();
1308: }
1309:
1310: /** Set to true for diagnostics about walker creation */
1311: static final boolean DEBUG_PATTERN_CREATION = false;
1312:
1313: /** Set to true for diagnostics about walker creation */
1314: static final boolean DEBUG_WALKER_CREATION = false;
1315:
1316: /** Set to true for diagnostics about iterator creation */
1317: static final boolean DEBUG_ITERATOR_CREATION = false;
1318:
1319: public static boolean hasPredicate(int analysis) {
1320: return (0 != (analysis & BIT_PREDICATE));
1321: }
1322:
1323: public static boolean isWild(int analysis) {
1324: return (0 != (analysis & BIT_NODETEST_ANY));
1325: }
1326:
1327: public static boolean walksAncestors(int analysis) {
1328: return isSet(analysis, BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF);
1329: }
1330:
1331: public static boolean walksAttributes(int analysis) {
1332: return (0 != (analysis & BIT_ATTRIBUTE));
1333: }
1334:
1335: public static boolean walksNamespaces(int analysis) {
1336: return (0 != (analysis & BIT_NAMESPACE));
1337: }
1338:
1339: public static boolean walksChildren(int analysis) {
1340: return (0 != (analysis & BIT_CHILD));
1341: }
1342:
1343: public static boolean walksDescendants(int analysis) {
1344: return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF);
1345: }
1346:
1347: public static boolean walksSubtree(int analysis) {
1348: return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF
1349: | BIT_CHILD);
1350: }
1351:
1352: public static boolean walksSubtreeOnlyMaybeAbsolute(int analysis) {
1353: return walksSubtree(analysis) && !walksExtraNodes(analysis)
1354: && !walksUp(analysis) && !walksSideways(analysis);
1355: }
1356:
1357: public static boolean walksSubtreeOnly(int analysis) {
1358: return walksSubtreeOnlyMaybeAbsolute(analysis)
1359: && !isAbsolute(analysis);
1360: }
1361:
1362: public static boolean walksFilteredList(int analysis) {
1363: return isSet(analysis, BIT_FILTER);
1364: }
1365:
1366: public static boolean walksSubtreeOnlyFromRootOrContext(int analysis) {
1367: return walksSubtree(analysis) && !walksExtraNodes(analysis)
1368: && !walksUp(analysis) && !walksSideways(analysis)
1369: && !isSet(analysis, BIT_FILTER);
1370: }
1371:
1372: public static boolean walksInDocOrder(int analysis) {
1373: return (walksSubtreeOnlyMaybeAbsolute(analysis)
1374: || walksExtraNodesOnly(analysis) || walksFollowingOnlyMaybeAbsolute(analysis))
1375: && !isSet(analysis, BIT_FILTER);
1376: }
1377:
1378: public static boolean walksFollowingOnlyMaybeAbsolute(int analysis) {
1379: return isSet(analysis, BIT_SELF | BIT_FOLLOWING_SIBLING
1380: | BIT_FOLLOWING)
1381: && !walksSubtree(analysis)
1382: && !walksUp(analysis)
1383: && !walksSideways(analysis);
1384: }
1385:
1386: public static boolean walksUp(int analysis) {
1387: return isSet(analysis, BIT_PARENT | BIT_ANCESTOR
1388: | BIT_ANCESTOR_OR_SELF);
1389: }
1390:
1391: public static boolean walksSideways(int analysis) {
1392: return isSet(analysis, BIT_FOLLOWING | BIT_FOLLOWING_SIBLING
1393: | BIT_PRECEDING | BIT_PRECEDING_SIBLING);
1394: }
1395:
1396: public static boolean walksExtraNodes(int analysis) {
1397: return isSet(analysis, BIT_NAMESPACE | BIT_ATTRIBUTE);
1398: }
1399:
1400: public static boolean walksExtraNodesOnly(int analysis) {
1401: return walksExtraNodes(analysis) && !isSet(analysis, BIT_SELF)
1402: && !walksSubtree(analysis) && !walksUp(analysis)
1403: && !walksSideways(analysis) && !isAbsolute(analysis);
1404: }
1405:
1406: public static boolean isAbsolute(int analysis) {
1407: return isSet(analysis, BIT_ROOT | BIT_FILTER);
1408: }
1409:
1410: public static boolean walksChildrenOnly(int analysis) {
1411: return walksChildren(analysis) && !isSet(analysis, BIT_SELF)
1412: && !walksExtraNodes(analysis)
1413: && !walksDescendants(analysis) && !walksUp(analysis)
1414: && !walksSideways(analysis)
1415: && (!isAbsolute(analysis) || isSet(analysis, BIT_ROOT));
1416: }
1417:
1418: public static boolean walksChildrenAndExtraAndSelfOnly(int analysis) {
1419: return walksChildren(analysis) && !walksDescendants(analysis)
1420: && !walksUp(analysis) && !walksSideways(analysis)
1421: && (!isAbsolute(analysis) || isSet(analysis, BIT_ROOT));
1422: }
1423:
1424: public static boolean walksDescendantsAndExtraAndSelfOnly(
1425: int analysis) {
1426: return !walksChildren(analysis) && walksDescendants(analysis)
1427: && !walksUp(analysis) && !walksSideways(analysis)
1428: && (!isAbsolute(analysis) || isSet(analysis, BIT_ROOT));
1429: }
1430:
1431: public static boolean walksSelfOnly(int analysis) {
1432: return isSet(analysis, BIT_SELF) && !walksSubtree(analysis)
1433: && !walksUp(analysis) && !walksSideways(analysis)
1434: && !isAbsolute(analysis);
1435: }
1436:
1437: public static boolean walksUpOnly(int analysis) {
1438: return !walksSubtree(analysis) && walksUp(analysis)
1439: && !walksSideways(analysis) && !isAbsolute(analysis);
1440: }
1441:
1442: public static boolean walksDownOnly(int analysis) {
1443: return walksSubtree(analysis) && !walksUp(analysis)
1444: && !walksSideways(analysis) && !isAbsolute(analysis);
1445: }
1446:
1447: public static boolean walksDownExtraOnly(int analysis) {
1448: return walksSubtree(analysis) && walksExtraNodes(analysis)
1449: && !walksUp(analysis) && !walksSideways(analysis)
1450: && !isAbsolute(analysis);
1451: }
1452:
1453: public static boolean canSkipSubtrees(int analysis) {
1454: return isSet(analysis, BIT_CHILD) | walksSideways(analysis);
1455: }
1456:
1457: public static boolean canCrissCross(int analysis) {
1458: // This could be done faster. Coded for clarity.
1459: if (walksSelfOnly(analysis))
1460: return false;
1461: else if (walksDownOnly(analysis) && !canSkipSubtrees(analysis))
1462: return false;
1463: else if (walksChildrenAndExtraAndSelfOnly(analysis))
1464: return false;
1465: else if (walksDescendantsAndExtraAndSelfOnly(analysis))
1466: return false;
1467: else if (walksUpOnly(analysis))
1468: return false;
1469: else if (walksExtraNodesOnly(analysis))
1470: return false;
1471: else if (walksSubtree(analysis)
1472: && (walksSideways(analysis) || walksUp(analysis) || canSkipSubtrees(analysis)))
1473: return true;
1474: else
1475: return false;
1476: }
1477:
1478: /**
1479: * Tell if the pattern can be 'walked' with the iteration steps in natural
1480: * document order, without duplicates.
1481: *
1482: * @param analysis The general analysis of the pattern.
1483: *
1484: * @return true if the walk can be done in natural order.
1485: *
1486: * @throws javax.xml.transform.TransformerException
1487: */
1488: static public boolean isNaturalDocOrder(int analysis) {
1489: if (canCrissCross(analysis) || isSet(analysis, BIT_NAMESPACE)
1490: || walksFilteredList(analysis))
1491: return false;
1492:
1493: if (walksInDocOrder(analysis))
1494: return true;
1495:
1496: return false;
1497: }
1498:
1499: /**
1500: * Tell if the pattern can be 'walked' with the iteration steps in natural
1501: * document order, without duplicates.
1502: *
1503: * @param compiler non-null reference to compiler object that has processed
1504: * the XPath operations into an opcode map.
1505: * @param stepOpCodePos The opcode position for the step.
1506: * @param stepIndex The top-level step index withing the iterator.
1507: * @param analysis The general analysis of the pattern.
1508: *
1509: * @return true if the walk can be done in natural order.
1510: *
1511: * @throws javax.xml.transform.TransformerException
1512: */
1513: private static boolean isNaturalDocOrder(Compiler compiler,
1514: int stepOpCodePos, int stepIndex, int analysis)
1515: throws javax.xml.transform.TransformerException {
1516: if (canCrissCross(analysis))
1517: return false;
1518:
1519: // Namespaces can present some problems, so just punt if we're looking for
1520: // these.
1521: if (isSet(analysis, BIT_NAMESPACE))
1522: return false;
1523:
1524: // The following, preceding, following-sibling, and preceding sibling can
1525: // be found in doc order if we get to this point, but if they occur
1526: // together, they produce
1527: // duplicates, so it's better for us to eliminate this case so we don't
1528: // have to check for duplicates during runtime if we're using a
1529: // WalkingIterator.
1530: if (isSet(analysis, BIT_FOLLOWING | BIT_FOLLOWING_SIBLING)
1531: && isSet(analysis, BIT_PRECEDING
1532: | BIT_PRECEDING_SIBLING))
1533: return false;
1534:
1535: // OK, now we have to check for select="@*/axis::*" patterns, which
1536: // can also cause duplicates to happen. But select="axis*/@::*" patterns
1537: // are OK, as are select="@foo/axis::*" patterns.
1538: // Unfortunately, we can't do this just via the analysis bits.
1539:
1540: int stepType;
1541: int stepCount = 0;
1542: boolean foundWildAttribute = false;
1543:
1544: // Steps that can traverse anything other than down a
1545: // subtree or that can produce duplicates when used in
1546: // combonation are counted with this variable.
1547: int potentialDuplicateMakingStepCount = 0;
1548:
1549: while (OpCodes.ENDOP != (stepType = compiler
1550: .getOp(stepOpCodePos))) {
1551: stepCount++;
1552:
1553: switch (stepType) {
1554: case OpCodes.FROM_ATTRIBUTES:
1555: case OpCodes.MATCH_ATTRIBUTE:
1556: if (foundWildAttribute) // Maybe not needed, but be safe.
1557: return false;
1558:
1559: // This doesn't seem to work as a test for wild card. Hmph.
1560: // int nodeTestType = compiler.getStepTestType(stepOpCodePos);
1561:
1562: String localName = compiler
1563: .getStepLocalName(stepOpCodePos);
1564: // System.err.println("localName: "+localName);
1565: if (localName.equals("*")) {
1566: foundWildAttribute = true;
1567: }
1568: break;
1569: case OpCodes.FROM_FOLLOWING:
1570: case OpCodes.FROM_FOLLOWING_SIBLINGS:
1571: case OpCodes.FROM_PRECEDING:
1572: case OpCodes.FROM_PRECEDING_SIBLINGS:
1573: case OpCodes.FROM_PARENT:
1574: case OpCodes.OP_VARIABLE:
1575: case OpCodes.OP_EXTFUNCTION:
1576: case OpCodes.OP_FUNCTION:
1577: case OpCodes.OP_GROUP:
1578: case OpCodes.FROM_NAMESPACE:
1579: case OpCodes.FROM_ANCESTORS:
1580: case OpCodes.FROM_ANCESTORS_OR_SELF:
1581: case OpCodes.MATCH_ANY_ANCESTOR:
1582: case OpCodes.MATCH_IMMEDIATE_ANCESTOR:
1583: case OpCodes.FROM_DESCENDANTS_OR_SELF:
1584: case OpCodes.FROM_DESCENDANTS:
1585: if (potentialDuplicateMakingStepCount > 0)
1586: return false;
1587: potentialDuplicateMakingStepCount++;
1588: case OpCodes.FROM_ROOT:
1589: case OpCodes.FROM_CHILDREN:
1590: case OpCodes.FROM_SELF:
1591: if (foundWildAttribute)
1592: return false;
1593: break;
1594: default:
1595: throw new RuntimeException(
1596: XSLMessages
1597: .createXPATHMessage(
1598: XPATHErrorResources.ER_NULL_ERROR_HANDLER,
1599: new Object[] { Integer
1600: .toString(stepType) })); //"Programmer's assertion: unknown opcode: "
1601: // + stepType);
1602: }
1603:
1604: int nextStepOpCodePos = compiler
1605: .getNextStepPos(stepOpCodePos);
1606:
1607: if (nextStepOpCodePos < 0)
1608: break;
1609:
1610: stepOpCodePos = nextStepOpCodePos;
1611: }
1612:
1613: return true;
1614: }
1615:
1616: public static boolean isOneStep(int analysis) {
1617: return (analysis & BITS_COUNT) == 0x00000001;
1618: }
1619:
1620: public static int getStepCount(int analysis) {
1621: return (analysis & BITS_COUNT);
1622: }
1623:
1624: /**
1625: * First 8 bits are the number of top-level location steps. Hopefully
1626: * there will never be more that 255 location steps!!!
1627: */
1628: public static final int BITS_COUNT = 0x000000FF;
1629:
1630: /** 4 bits are reserved for future use. */
1631: public static final int BITS_RESERVED = 0x00000F00;
1632:
1633: /** Bit is on if the expression contains a top-level predicate. */
1634: public static final int BIT_PREDICATE = (0x00001000);
1635:
1636: /** Bit is on if any of the walkers contain an ancestor step. */
1637: public static final int BIT_ANCESTOR = (0x00001000 << 1);
1638:
1639: /** Bit is on if any of the walkers contain an ancestor-or-self step. */
1640: public static final int BIT_ANCESTOR_OR_SELF = (0x00001000 << 2);
1641:
1642: /** Bit is on if any of the walkers contain an attribute step. */
1643: public static final int BIT_ATTRIBUTE = (0x00001000 << 3);
1644:
1645: /** Bit is on if any of the walkers contain a child step. */
1646: public static final int BIT_CHILD = (0x00001000 << 4);
1647:
1648: /** Bit is on if any of the walkers contain a descendant step. */
1649: public static final int BIT_DESCENDANT = (0x00001000 << 5);
1650:
1651: /** Bit is on if any of the walkers contain a descendant-or-self step. */
1652: public static final int BIT_DESCENDANT_OR_SELF = (0x00001000 << 6);
1653:
1654: /** Bit is on if any of the walkers contain a following step. */
1655: public static final int BIT_FOLLOWING = (0x00001000 << 7);
1656:
1657: /** Bit is on if any of the walkers contain a following-sibiling step. */
1658: public static final int BIT_FOLLOWING_SIBLING = (0x00001000 << 8);
1659:
1660: /** Bit is on if any of the walkers contain a namespace step. */
1661: public static final int BIT_NAMESPACE = (0x00001000 << 9);
1662:
1663: /** Bit is on if any of the walkers contain a parent step. */
1664: public static final int BIT_PARENT = (0x00001000 << 10);
1665:
1666: /** Bit is on if any of the walkers contain a preceding step. */
1667: public static final int BIT_PRECEDING = (0x00001000 << 11);
1668:
1669: /** Bit is on if any of the walkers contain a preceding-sibling step. */
1670: public static final int BIT_PRECEDING_SIBLING = (0x00001000 << 12);
1671:
1672: /** Bit is on if any of the walkers contain a self step. */
1673: public static final int BIT_SELF = (0x00001000 << 13);
1674:
1675: /**
1676: * Bit is on if any of the walkers contain a filter (i.e. id(), extension
1677: * function, etc.) step.
1678: */
1679: public static final int BIT_FILTER = (0x00001000 << 14);
1680:
1681: /** Bit is on if any of the walkers contain a root step. */
1682: public static final int BIT_ROOT = (0x00001000 << 15);
1683:
1684: /**
1685: * If any of these bits are on, the expression may likely traverse outside
1686: * the given subtree.
1687: */
1688: public static final int BITMASK_TRAVERSES_OUTSIDE_SUBTREE = (BIT_NAMESPACE // ??
1689: | BIT_PRECEDING_SIBLING
1690: | BIT_PRECEDING
1691: | BIT_FOLLOWING_SIBLING | BIT_FOLLOWING | BIT_PARENT // except parent of attrs.
1692: | BIT_ANCESTOR_OR_SELF | BIT_ANCESTOR | BIT_FILTER | BIT_ROOT);
1693:
1694: /**
1695: * Bit is on if any of the walkers can go backwards in document
1696: * order from the context node.
1697: */
1698: public static final int BIT_BACKWARDS_SELF = (0x00001000 << 16);
1699:
1700: /** Found "//foo" pattern */
1701: public static final int BIT_ANY_DESCENDANT_FROM_ROOT = (0x00001000 << 17);
1702:
1703: /**
1704: * Bit is on if any of the walkers contain an node() test. This is
1705: * really only useful if the count is 1.
1706: */
1707: public static final int BIT_NODETEST_ANY = (0x00001000 << 18);
1708:
1709: // can't go higher than 18!
1710:
1711: /** Bit is on if the expression is a match pattern. */
1712: public static final int BIT_MATCH_PATTERN = (0x00001000 << 19);
1713: }
|