001: package net.sf.saxon.expr;
002:
003: import net.sf.saxon.Configuration;
004: import net.sf.saxon.Controller;
005: import net.sf.saxon.event.SequenceOutputter;
006: import net.sf.saxon.instruct.*;
007: import net.sf.saxon.om.*;
008: import net.sf.saxon.sort.SortExpression;
009: import net.sf.saxon.trace.InstructionInfoProvider;
010: import net.sf.saxon.trans.DynamicError;
011: import net.sf.saxon.trans.XPathException;
012: import net.sf.saxon.type.AnyItemType;
013: import net.sf.saxon.type.Type;
014: import net.sf.saxon.type.TypeHierarchy;
015: import net.sf.saxon.value.*;
016:
017: import javax.xml.transform.SourceLocator;
018: import java.util.Iterator;
019: import java.util.List;
020:
021: /**
022: * This class, ExpressionTool, contains a number of useful static methods
023: * for manipulating expressions. Most importantly, it provides the factory
024: * method make() for constructing a new expression
025: */
026:
027: public class ExpressionTool {
028: private ExpressionTool() {
029: }
030:
031: /**
032: * Parse an expression. This performs the basic analysis of the expression against the
033: * grammar, it binds variable references and function calls to variable definitions and
034: * function definitions, and it performs context-independent expression rewriting for
035: * optimization purposes.
036: *
037: * @exception net.sf.saxon.trans.XPathException if the expression contains a static error
038: * @param expression The expression (as a character string)
039: * @param env An object giving information about the compile-time
040: * context of the expression
041: * @param terminator The token that marks the end of this expression; typically
042: * Tokenizer.EOF, but may for example be a right curly brace
043: * @param lineNumber the line number of the start of the expression
044: * @return an object of type Expression
045: */
046:
047: public static Expression make(String expression, StaticContext env,
048: int start, int terminator, int lineNumber)
049: throws XPathException {
050: ExpressionParser parser = new ExpressionParser();
051: if (terminator == -1) {
052: terminator = Token.EOF;
053: }
054: Expression exp = parser.parse(expression, start, terminator,
055: lineNumber, env);
056: exp = exp.simplify(env);
057: makeParentReferences(exp);
058: return exp;
059: }
060:
061: /**
062: * Copy location information (currently the line number and parent) from one expression
063: * to another
064: */
065:
066: public static void copyLocationInfo(Expression from, Expression to) {
067: if (from instanceof ComputedExpression
068: && to instanceof ComputedExpression) {
069: ((ComputedExpression) to)
070: .setLocationId(((ComputedExpression) from)
071: .getLocationId());
072: }
073: }
074:
075: /**
076: * Establish the links from subexpressions to their parent expressions,
077: * by means of a recursive tree walk.
078: */
079:
080: public static void makeParentReferences(Expression top) {
081: // This costly method is now unnecessary; we are setting the parent expression
082: // as the tree is built. But it can be put back in if needed.
083: // if (top==null) {
084: // return;
085: // }
086: // for (Iterator children = top.iterateSubExpressions(); children.hasNext();) {
087: // Expression child = (Expression)children.next();
088: // if (child instanceof ComputedExpression) {
089: // ((ComputedExpression)child).setParentExpression((ComputedExpression)top);
090: // makeParentReferences(child);
091: // }
092: // }
093: }
094:
095: /**
096: * Get location information for an expression in the form of a SourceLocator
097: */
098:
099: public static SourceLocator getLocator(Expression exp) {
100: if (exp instanceof ComputedExpression) {
101: return (ComputedExpression) exp;
102: } else {
103: return null;
104: }
105: }
106:
107: /**
108: * Determine whether an expression is a repeatedly-evaluated subexpression
109: * of a parent expression. For example, the predicate in a filter expression is
110: * a repeatedly-evaluated subexpression of the filter expression.
111: */
112:
113: public static boolean isRepeatedSubexpression(Expression parent,
114: Expression child, StaticContext env) {
115: if (parent instanceof PathExpression) {
116: return child == ((PathExpression) parent)
117: .getStepExpression();
118: }
119: if (parent instanceof FilterExpression) {
120: final TypeHierarchy th = env.getNamePool()
121: .getTypeHierarchy();
122: return child == ((FilterExpression) parent).getFilter()
123: && !th.isSubType(child.getItemType(th),
124: Type.NUMBER_TYPE);
125: }
126: if (parent instanceof ForExpression) {
127: return child == ((ForExpression) parent).getAction();
128: }
129: if (parent instanceof QuantifiedExpression) {
130: return child == ((QuantifiedExpression) parent).getAction();
131: }
132: if (parent instanceof SimpleMappingExpression) {
133: return child == ((SimpleMappingExpression) parent)
134: .getStepExpression();
135: }
136: if (parent instanceof SortExpression) {
137: return ((SortExpression) parent).isSortKey(child);
138: }
139: // if (parent instanceof TupleSorter) {
140: // return ((TupleSorter)parent).isSortKey(child);
141: // }
142: if (parent instanceof AnalyzeString) {
143: return child == ((AnalyzeString) parent)
144: .getMatchingExpression()
145: || child == ((AnalyzeString) parent)
146: .getNonMatchingExpression();
147: }
148: if (parent instanceof ForEach) {
149: return child == ((ForEach) parent).getActionExpression();
150: }
151: if (parent instanceof ForEachGroup) {
152: return child == ((ForEachGroup) parent)
153: .getActionExpression();
154: }
155: if (parent instanceof While) {
156: return child == ((While) parent).getActionExpression();
157: }
158: if (parent instanceof GeneralComparison) {
159: return child == ((GeneralComparison) parent).getOperands()[1];
160: }
161: if (parent instanceof GeneralComparison10) {
162: Expression[] ops = ((GeneralComparison10) parent)
163: .getOperands();
164: return child == ops[0] || child == ops[1];
165: }
166: return false;
167: }
168:
169: /**
170: * Remove unwanted sorting from an expression, at compile time
171: */
172:
173: public static Expression unsorted(Optimizer opt, Expression exp,
174: boolean eliminateDuplicates) throws XPathException {
175: if (exp instanceof Value)
176: return exp; // fast exit
177: PromotionOffer offer = new PromotionOffer(opt);
178: offer.action = PromotionOffer.UNORDERED;
179: offer.mustEliminateDuplicates = eliminateDuplicates;
180: Expression exp2 = exp.promote(offer);
181: if (exp2 != exp) {
182: if (exp2 instanceof ComputedExpression) {
183: ((ComputedExpression) exp2).setParentExpression(exp
184: .getParentExpression());
185: }
186: return exp2;
187: }
188: return exp;
189: }
190:
191: /**
192: * Remove unwanted sorting from an expression, at compile time, if and only if it is known
193: * that the result of the expression will be homogeneous (all nodes, or all atomic values).
194: * This is done when we need the effective boolean value of a sequence: the EBV of a
195: * homogenous sequence does not depend on its order, but this is not true when atomic
196: * values and nodes are mixed: (N, AV) is true, but (AV, N) is an error.
197: */
198:
199: public static Expression unsortedIfHomogeneous(Optimizer opt,
200: Expression exp, boolean eliminateDuplicates)
201: throws XPathException {
202: if (exp instanceof Value) {
203: return exp; // fast exit
204: }
205: if (exp.getItemType(opt.getConfiguration().getNamePool()
206: .getTypeHierarchy()) instanceof AnyItemType) {
207: return exp;
208: } else {
209: PromotionOffer offer = new PromotionOffer(opt);
210: offer.action = PromotionOffer.UNORDERED;
211: offer.mustEliminateDuplicates = eliminateDuplicates;
212: return exp.promote(offer);
213: }
214: }
215:
216: /**
217: * Do lazy evaluation of an expression. This will return a value, which may optionally
218: * be a SequenceIntent, which is a wrapper around an iterator over the value of the expression.
219: *
220: * @param context the run-time evaluation context for the expression. If
221: * the expression is not evaluated immediately, then parts of the
222: * context on which the expression depends need to be saved as part of
223: * the Closure
224: * @param ref an indication of how the value will be used. The value 1 indicates that the value
225: * is only expected to be used once, so that there is no need to keep it in memory. A small value >1
226: * indicates multiple references, so the value will be saved when first evaluated. The special value
227: * FILTERED indicates a reference within a loop of the form $x[predicate], indicating that the value
228: * should be saved in a way that permits indexing.
229: * @exception XPathException if any error occurs in evaluating the
230: * expression
231: * @return a value: either the actual value obtained by evaluating the
232: * expression, or a Closure containing all the information needed to
233: * evaluate it later
234: */
235:
236: public static ValueRepresentation lazyEvaluate(Expression exp,
237: XPathContext context, int ref) throws XPathException {
238: // this sequence of tests rearranged 7 Apr 2005 because opt017 was failing. In 8.4 the test for a LazyExpression
239: // had been commented out - don't know why.
240: if (exp instanceof Value) {
241: return (Value) exp;
242:
243: } else if (exp instanceof VariableReference) {
244: return ((VariableReference) exp).evaluateVariable(context);
245:
246: } else if ((exp.getDependencies() & (StaticProperty.DEPENDS_ON_POSITION
247: | StaticProperty.DEPENDS_ON_LAST
248: | StaticProperty.DEPENDS_ON_CURRENT_ITEM
249: | StaticProperty.DEPENDS_ON_CURRENT_GROUP | StaticProperty.DEPENDS_ON_REGEX_GROUP)) != 0) {
250: // we can't save these values in the closure, so we evaluate
251: // the expression now if they are needed
252: return eagerEvaluate(exp, context);
253:
254: } else if (exp instanceof LazyExpression) {
255: // A LazyExpression is always evaluated lazily (if at all possible) to
256: // prevent spurious errors (see opt017)
257: return Closure.make((LazyExpression) exp, context,
258: (ref == 1 ? 10 : ref));
259:
260: } else if (!Cardinality.allowsMany(exp.getCardinality())) {
261: // singleton expressions are always evaluated eagerly
262: return eagerEvaluate(exp, context);
263:
264: } else {
265: // create a Closure, a wrapper for the expression and its context
266: return Closure.make((ComputedExpression) exp, context, ref);
267: }
268:
269: }
270:
271: /**
272: * Evaluate an expression now; lazy evaluation is not permitted in this case
273: * @param exp the expression to be evaluated
274: * @param context the run-time evaluation context
275: * @exception net.sf.saxon.trans.XPathException if any dynamic error occurs evaluating the
276: * expression
277: * @return the result of evaluating the expression
278: */
279:
280: public static Value eagerEvaluate(Expression exp,
281: XPathContext context) throws XPathException {
282: if (exp instanceof Value && !(exp instanceof Closure)) {
283: return (Value) exp;
284: }
285: if (exp instanceof VariableReference) {
286: ValueRepresentation v = ((VariableReference) exp)
287: .evaluateVariable(context);
288: if (v instanceof Closure) {
289: return SequenceExtent.makeSequenceExtent(((Closure) v)
290: .iterate(context));
291: } else if (v instanceof Value) {
292: return (Value) v;
293: } else if (v instanceof NodeInfo) {
294: return new SingletonNode((NodeInfo) v);
295: }
296: }
297: int m = exp.getImplementationMethod();
298: if ((m & Expression.ITERATE_METHOD) != 0) {
299: SequenceIterator iterator = exp.iterate(context);
300: if (iterator instanceof EmptyIterator) {
301: return EmptySequence.getInstance();
302: } else if (iterator instanceof SingletonIterator) {
303: Item item = ((SingletonIterator) iterator).getValue();
304: return Value.asValue(item);
305: }
306: Value extent = SequenceExtent.makeSequenceExtent(iterator);
307: int len = extent.getLength();
308: if (len == 0) {
309: return EmptySequence.getInstance();
310: } else if (len == 1) {
311: return Value.asValue(extent.itemAt(0));
312: } else {
313: return extent;
314: }
315:
316: } else if ((m & Expression.EVALUATE_METHOD) != 0) {
317: Item item = exp.evaluateItem(context);
318: return Value.asValue(item);
319:
320: } else {
321: // Use PROCESS_METHOD
322: Controller controller = context.getController();
323: XPathContext c2 = context.newMinorContext();
324: c2.setOrigin((InstructionInfoProvider) exp);
325: SequenceOutputter seq = new SequenceOutputter();
326: seq.setPipelineConfiguration(controller
327: .makePipelineConfiguration());
328: c2.setTemporaryReceiver(seq);
329: seq.open();
330: exp.process(c2);
331: seq.close();
332: return Value.asValue(seq.getSequence());
333: }
334: }
335:
336: public static boolean markTailFunctionCalls(Expression exp) {
337: if (exp instanceof ComputedExpression) {
338: return ((ComputedExpression) exp).markTailFunctionCalls();
339: } else {
340: return false;
341: }
342: }
343:
344: /**
345: * Construct indent string, for diagnostic output
346: *
347: * @param level the indentation level (the number of spaces to return)
348: * @return a string of "level*2" spaces
349: */
350:
351: public static String indent(int level) {
352: String s = "";
353: for (int i = 0; i < level; i++) {
354: s += " ";
355: }
356: return s;
357: }
358:
359: /**
360: * Allocate slot numbers to range variables
361: * @param exp the expression whose range variables need to have slot numbers assigned
362: * @param nextFree the next slot number that is available for allocation
363: * @param frame a SlotManager object that is used to track the mapping of slot numbers
364: * to variable names for debugging purposes. May be null.
365: * @return the next unallocated slot number.
366: */
367:
368: public static int allocateSlots(Expression exp, int nextFree,
369: SlotManager frame) {
370: if (exp instanceof Assignation) {
371: ((Assignation) exp).setSlotNumber(nextFree);
372: int count = ((Assignation) exp).getRequiredSlots();
373: nextFree += count;
374: if (frame != null) {
375: frame.allocateSlotNumber(((Assignation) exp)
376: .getVariableFingerprint());
377: if (count == 2) {
378: frame.allocateSlotNumber(((ForExpression) exp)
379: .getPositionVariableNameCode()
380: & NamePool.FP_MASK);
381: }
382: }
383: }
384: for (Iterator children = exp.iterateSubExpressions(); children
385: .hasNext();) {
386: Expression child = (Expression) children.next();
387: nextFree = allocateSlots(child, nextFree, frame);
388: }
389: return nextFree;
390:
391: // Note, we allocate a distinct slot to each range variable, even if the
392: // scopes don't overlap. This isn't strictly necessary, but might help
393: // debugging.
394: }
395:
396: /**
397: * Determine the effective boolean value of a sequence, given an iterator over the sequence
398: * @param iterator An iterator over the sequence whose effective boolean value is required
399: * @return the effective boolean value
400: * @throws XPathException if a dynamic error occurs
401: */
402: public static boolean effectiveBooleanValue(
403: SequenceIterator iterator) throws XPathException {
404: Item first = iterator.next();
405: if (first == null) {
406: return false;
407: }
408: if (first instanceof NodeInfo) {
409: return true;
410: } else {
411: if (first instanceof BooleanValue) {
412: if (iterator.next() != null) {
413: ebvError("sequence of two or more items starting with an atomic value");
414: }
415: return ((BooleanValue) first).getBooleanValue();
416: } else if (first instanceof StringValue
417: && !(first instanceof AnyURIValue)) {
418: if (iterator.next() != null) {
419: ebvError("sequence of two or more items starting with an atomic value");
420: }
421: return (first.getStringValueCS().length() != 0);
422: } else if (first instanceof NumericValue) {
423: if (iterator.next() != null) {
424: ebvError("sequence of two or more items starting with an atomic value");
425: }
426: // first==first is a test for NaN
427: return (!(first.equals(DoubleValue.ZERO)) && first
428: .equals(first));
429: } else {
430: ebvError("sequence starting with an atomic value other than a boolean, number, or string");
431: return false;
432: }
433: }
434: }
435:
436: public static void ebvError(String reason) throws XPathException {
437: DynamicError err = new DynamicError(
438: "Effective boolean value is not defined for a "
439: + reason);
440: err.setErrorCode("FORG0006");
441: err.setIsTypeError(true);
442: throw err;
443: }
444:
445: /**
446: * Determine whether an expression depends on any one of a set of variables
447: * @param e the expression being tested
448: * @param bindingList the set of variables being tested
449: * @return true if the expression depends on one of the given variables
450: */
451:
452: public static boolean dependsOnVariable(Expression e,
453: Binding[] bindingList) {
454: if (e instanceof VariableReference) {
455: for (int i = 0; i < bindingList.length; i++) {
456: if (((VariableReference) e).getBinding() == bindingList[i]) {
457: return true;
458: }
459: }
460: return false;
461: } else {
462: for (Iterator children = e.iterateSubExpressions(); children
463: .hasNext();) {
464: Expression child = (Expression) children.next();
465: if (dependsOnVariable(child, bindingList)) {
466: return true;
467: }
468: }
469: return false;
470: }
471: }
472:
473: /**
474: * Gather a list of all the variable bindings on which a given expression depends
475: * @param e the expression being tested
476: * @param list a list to which the bindings are to be added. The items in this list must
477: * implement {@link Binding}
478: */
479:
480: public static void gatherReferencedVariables(Expression e, List list) {
481: if (e instanceof VariableReference) {
482: Binding binding = ((VariableReference) e).getBinding();
483: if (!list.contains(binding)) {
484: list.add(binding);
485: }
486: } else {
487: for (Iterator children = e.iterateSubExpressions(); children
488: .hasNext();) {
489: Expression child = (Expression) children.next();
490: gatherReferencedVariables(child, list);
491: }
492: }
493: }
494:
495: /**
496: * Determine whether an expression contains a call on the function with a given fingerprint
497: * @param exp The expression being tested
498: * @param fp The fingerprint of the name of the function
499: * @return true if the expression contains a call on the function
500: */
501:
502: public static boolean callsFunction(Expression exp, int fp) {
503: if (exp instanceof FunctionCall
504: && (((FunctionCall) exp).getFunctionNameCode() & NamePool.FP_MASK) == fp) {
505: return true;
506: }
507: Iterator iter = exp.iterateSubExpressions();
508: while (iter.hasNext()) {
509: Expression e = (Expression) iter.next();
510: if (callsFunction(e, fp)) {
511: return true;
512: }
513: }
514: return false;
515: }
516:
517: /**
518: * Gather a list of all the user-defined functions which a given expression calls directly
519: * @param e the expression being tested
520: * @param list a list of the functions that are called. The items in this list must
521: * be objects of class {@link UserFunction}
522: */
523:
524: public static void gatherCalledFunctions(Expression e, List list) {
525: if (e instanceof UserFunctionCall) {
526: UserFunction function = ((UserFunctionCall) e)
527: .getFunction();
528: if (!list.contains(function)) {
529: list.add(function);
530: }
531: } else {
532: for (Iterator children = e.iterateSubExpressions(); children
533: .hasNext();) {
534: Expression child = (Expression) children.next();
535: gatherCalledFunctions(child, list);
536: }
537: }
538: }
539:
540: /**
541: * Resolve calls to the current() function within an expression
542: */
543:
544: public static Expression resolveCallsToCurrentFunction(
545: Expression exp, Configuration config) throws XPathException {
546: int current = config.getNamePool().getFingerprint(
547: NamespaceConstant.FN, "current");
548: if (current == -1) {
549: return exp;
550: // if the name fn:current is not in the name pool, then the expression can't contain any calls to it!
551: }
552: if (callsFunction(exp, current)) {
553: RangeVariableDeclaration decl = new RangeVariableDeclaration();
554: decl.setNameCode(config.getNamePool()
555: .allocate("saxon", NamespaceConstant.SAXON,
556: "current" + exp.hashCode()));
557: decl.setVariableName("saxon:current");
558: decl.setRequiredType(SequenceType.SINGLE_ITEM);
559: LetExpression let = new LetExpression();
560: let.setSequence(new ContextItemExpression());
561: let.setVariableDeclaration(decl);
562: PromotionOffer offer = new PromotionOffer(config
563: .getOptimizer());
564: offer.action = PromotionOffer.REPLACE_CURRENT;
565: offer.containingExpression = let;
566: exp = exp.promote(offer);
567: let.setAction(exp);
568: return let;
569: } else {
570: return exp;
571: }
572: }
573:
574: /**
575: * Determine whether it is possible to rearrange an expression so that all references to a given
576: * variable are replaced by a reference to ".". This is true of there are no references to the variable
577: * within a filter predicate or on the rhs of a "/" operator.
578: */
579:
580: public static boolean isVariableReplaceableByDot(Expression exp,
581: Binding[] binding) {
582: if (exp instanceof ComputedExpression) {
583: if (exp instanceof FilterExpression) {
584: Expression start = ((FilterExpression) exp)
585: .getBaseExpression();
586: Expression filter = ((FilterExpression) exp)
587: .getFilter();
588: return isVariableReplaceableByDot(start, binding)
589: && !dependsOnVariable(filter, binding);
590: } else if (exp instanceof PathExpression) {
591: Expression start = ((PathExpression) exp)
592: .getFirstStep();
593: Expression rest = ((PathExpression) exp)
594: .getRemainingSteps();
595: return isVariableReplaceableByDot(start, binding)
596: && !dependsOnVariable(rest, binding);
597: } else {
598: Iterator iter = exp.iterateSubExpressions();
599: while (iter.hasNext()) {
600: Expression sub = (Expression) iter.next();
601: if (!isVariableReplaceableByDot(sub, binding)) {
602: return false;
603: }
604: }
605: return true;
606: }
607: } else {
608: return true;
609: }
610: }
611: }
612:
613: //
614: // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
615: // you may not use this file except in compliance with the License. You may obtain a copy of the
616: // License at http://www.mozilla.org/MPL/
617: //
618: // Software distributed under the License is distributed on an "AS IS" basis,
619: // WITHOUT WARRANTY OF ANY KIND, either express or implied.
620: // See the License for the specific language governing rights and limitations under the License.
621: //
622: // The Original Code is: all this file.
623: //
624: // The Initial Developer of the Original Code is Michael H. Kay.
625: //
626: // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
627: //
628: // Contributor(s): none.
629: //
|