1 //------------------------------------------------------------
2 // Copyright (c) Microsoft Corporation. All rights reserved.
3 //------------------------------------------------------------
4 namespace System.ServiceModel.Dispatcher
7 using System.Collections;
8 using System.Collections.Generic;
9 using System.Collections.ObjectModel;
11 using System.ServiceModel.Channels;
12 using System.ServiceModel.Diagnostics;
14 using System.Xml.XPath;
17 internal enum QueryCompilerFlags
20 InverseQuery = 0x00000001
23 internal struct FilterResult
25 QueryProcessor processor;
28 internal FilterResult(QueryProcessor processor)
30 this.processor = processor;
31 this.result = this.processor.Result;
34 internal FilterResult(bool result)
36 this.processor = null;
41 internal ICollection<MessageFilter> Matches
45 return this.processor.ResultSet;
49 internal QueryProcessor Processor
53 return this.processor;
65 internal MessageFilter GetSingleMatch()
67 Collection<MessageFilter> matches = processor.MatchList;
69 switch (matches.Count)
72 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new MultipleFilterMatchesException(SR.GetString(SR.FilterMultipleMatches), null, matches));
87 // XPathResult.GetResultAsString and XPathResult.GetResultAsBoolean,
88 // drive knowledge of TResult into the engine.
89 internal class QueryResult<TResult> : IEnumerable<KeyValuePair<MessageQuery, TResult>>
95 internal QueryResult(QueryMatcher matcher, Message message, bool evalBody)
97 this.matcher = matcher;
98 this.message = message;
99 this.evalBody = evalBody;
102 public TResult GetSingleResult()
104 QueryProcessor processor = this.matcher.CreateProcessor();
109 processor.Eval(this.matcher.RootOpcode, this.message, this.evalBody);
111 catch (XPathNavigatorException e)
113 throw TraceUtility.ThrowHelperError(e.Process(this.matcher.RootOpcode), this.message);
115 catch (NavigatorInvalidBodyAccessException e)
117 throw TraceUtility.ThrowHelperError(e.Process(this.matcher.RootOpcode), this.message);
123 this.message.Close();
126 result = processor.QueryResult;
127 this.matcher.ReleaseProcessor(processor);
130 if (typeof(TResult) == typeof(XPathResult) || typeof(TResult) == typeof(object))
132 return (TResult)(object)result;
134 else if (typeof(TResult) == typeof(string))
136 return (TResult)(object)result.GetResultAsString();
138 else if (typeof(TResult) == typeof(bool))
140 return (TResult)(object)result.GetResultAsBoolean();
144 throw Fx.AssertAndThrowFatal("unsupported type");
148 public IEnumerator<KeyValuePair<MessageQuery, TResult>> GetEnumerator()
150 QueryProcessor processor = this.matcher.CreateProcessor();
151 Collection<KeyValuePair<MessageQuery, XPathResult>> results =
152 new Collection<KeyValuePair<MessageQuery, XPathResult>>();
153 processor.ResultSet = results;
157 processor.Eval(this.matcher.RootOpcode, this.message, this.evalBody);
159 if (typeof(TResult) == typeof(XPathResult))
161 return (IEnumerator<KeyValuePair<MessageQuery, TResult>>)(object)results.GetEnumerator();
163 else if (typeof(TResult) == typeof(string) ||
164 typeof(TResult) == typeof(bool) ||
165 typeof(TResult) == typeof(object))
167 Collection<KeyValuePair<MessageQuery, TResult>> typedResults =
168 new Collection<KeyValuePair<MessageQuery, TResult>>();
170 foreach (var result in results)
172 if (typeof(TResult) == typeof(string))
175 new KeyValuePair<MessageQuery, TResult>(
176 result.Key, (TResult)(object)result.Value.GetResultAsString()));
178 else if (typeof(TResult) == typeof(bool))
181 new KeyValuePair<MessageQuery, TResult>(
182 result.Key, (TResult)(object)result.Value.GetResultAsBoolean()));
186 typedResults.Add(new KeyValuePair<MessageQuery, TResult>(
187 result.Key, (TResult)(object)result.Value));
191 return (IEnumerator<KeyValuePair<MessageQuery, TResult>>)typedResults.GetEnumerator();
195 throw Fx.AssertAndThrowFatal("unsupported type");
198 catch (XPathNavigatorException e)
200 throw TraceUtility.ThrowHelperError(e.Process(this.matcher.RootOpcode), this.message);
202 catch (NavigatorInvalidBodyAccessException e)
204 throw TraceUtility.ThrowHelperError(e.Process(this.matcher.RootOpcode), this.message);
210 this.message.Close();
213 this.matcher.ReleaseProcessor(processor);
217 IEnumerator IEnumerable.GetEnumerator()
219 return this.GetEnumerator();
226 internal abstract class QueryMatcher
228 static IFunctionLibrary[] defaultFunctionLibs; // The set of function libraries that our XPath compiler will link to
229 static XPathNavigator fxCompiler; // fx compiler
231 protected int maxNodes; // Maximum # of nodes that we will process while performing any individual match
232 protected Opcode query; // root opcode - this is where query evaluation starts
233 protected int subExprVars; // the number of subexpr node sequences the processing context must hold
236 protected WeakReference processorPool;
238 internal class QueryProcessorPool
240 QueryProcessor processor;
242 internal QueryProcessorPool()
246 internal QueryProcessor Pop()
248 QueryProcessor p = this.processor;
251 this.processor = (QueryProcessor)p.next;
258 internal void Push(QueryProcessor p)
260 p.next = this.processor;
265 static QueryMatcher()
267 QueryMatcher.defaultFunctionLibs = new IFunctionLibrary[] { new XPathFunctionLibrary() };
269 // For some incomprehensible reason, the Framework XPath compiler requires an instance of an XPath navigator
270 // to compile an xpath. This compiler uses a dummy xml document to create a navigator
271 XmlDocument doc = new XmlDocument();
273 QueryMatcher.fxCompiler = doc.CreateNavigator();
276 internal QueryMatcher()
278 this.maxNodes = int.MaxValue;
280 this.processorPool = new WeakReference(null);
281 this.subExprVars = 0;
284 internal QueryMatcher(QueryMatcher matcher)
286 this.processorPool = new WeakReference(null);
287 this.maxNodes = matcher.maxNodes;
288 this.query = matcher.query;
289 this.subExprVars = matcher.subExprVars;
292 internal bool IsCompiled
296 return (null != this.query);
300 internal int NodeQuota
304 return this.maxNodes;
308 Fx.Assert(value > 0, "");
309 this.maxNodes = value;
313 internal Opcode RootOpcode
321 internal int SubExprVarCount
325 return this.subExprVars;
330 /// Compile the given filter to run on an external (fx) xpath engine
332 internal static OpcodeBlock CompileForExternalEngine(string expression, XmlNamespaceManager namespaces, object item, bool match)
335 XPathExpression xpathExpr = QueryMatcher.fxCompiler.Compile(expression);
337 // Fx will bind prefixes and functions here.
338 if (namespaces != null)
340 // There's a bug in System.Xml.XPath. If we pass an XsltContext to SetContext it won't throw if there's
341 // an undefined prefix.
342 if (namespaces is XsltContext)
344 // Lex the xpath to find all prefixes used
345 XPathLexer lexer = new XPathLexer(expression, false);
346 while (lexer.MoveNext())
348 string prefix = lexer.Token.Prefix;
350 if (prefix.Length > 0 && namespaces.LookupNamespace(prefix) == null)
352 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new XsltException(SR.GetString(SR.FilterUndefinedPrefix, prefix)));
357 xpathExpr.SetContext(namespaces);
361 // FORCE the function to COMPILE - they won't bind namespaces unless we check the return type
363 if (XPathResultType.Error == xpathExpr.ReturnType)
365 // This should never be reached. The above property should throw if there's an error
366 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new XPathException(SR.GetString(SR.FilterCouldNotCompile, expression)));
369 OpcodeBlock codeBlock = new OpcodeBlock();
370 SingleFxEngineResultOpcode op;
374 op = new QuerySingleFxEngineResultOpcode();
378 op = new MatchSingleFxEngineResultOpcode();
381 op.XPath = xpathExpr;
384 codeBlock.Append(op);
389 /// Compile the given filter for evaluation using the internal engine.
391 /// <param name="flags">Caller customizes optimizations via the flags parameter</param>
392 /// <param name="returnType">Every xpath expression has a return type</param>
393 /// <returns>The opcode block we execute to evaluate</returns>
394 internal static OpcodeBlock CompileForInternalEngine(XPathMessageFilter filter, QueryCompilerFlags flags, IFunctionLibrary[] functionLibs, out ValueDataType returnType)
396 return QueryMatcher.CompileForInternalEngine(filter.XPath.Trim(), filter.namespaces, flags, functionLibs, out returnType);
399 internal static OpcodeBlock CompileForInternalEngine(string xpath, XmlNamespaceManager nsManager, QueryCompilerFlags flags, IFunctionLibrary[] functionLibs, out ValueDataType returnType)
401 OpcodeBlock codeBlock;
403 returnType = ValueDataType.None;
404 if (0 == xpath.Length)
406 // 0 length XPaths always match
407 codeBlock = new OpcodeBlock();
408 codeBlock.Append(new PushBooleanOpcode(true)); // Always match by pushing true on the eval stack
412 // Try to parse the xpath. Bind to default function libraries
413 // The parser returns an expression tree
414 XPathParser parser = new XPathParser(xpath, nsManager, functionLibs);
415 XPathExpr parseTree = parser.Parse();
417 if (null == parseTree)
419 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new QueryCompileException(QueryCompileError.CouldNotParseExpression));
422 returnType = parseTree.ReturnType;
424 // Compile the expression tree
425 XPathCompiler compiler = new XPathCompiler(flags);
427 codeBlock = compiler.Compile(parseTree);
433 internal static OpcodeBlock CompileForInternalEngine(string xpath, XmlNamespaceManager ns, QueryCompilerFlags flags, out ValueDataType returnType)
435 return QueryMatcher.CompileForInternalEngine(xpath, ns, flags, QueryMatcher.defaultFunctionLibs, out returnType);
438 internal SeekableXPathNavigator CreateMessageNavigator(Message message, bool matchBody)
440 SeekableXPathNavigator nav = message.GetNavigator(matchBody, this.maxNodes);
442 // Position the navigator at the root element
443 // This allows a caller to run relative XPaths on message
449 /// Checks the context pool for a generic navigator first. If none is available, creates a new one
451 internal SeekableXPathNavigator CreateSeekableNavigator(XPathNavigator navigator)
453 return new GenericSeekableNavigator(navigator);
456 internal SeekableXPathNavigator CreateSafeNavigator(SeekableXPathNavigator navigator)
458 INodeCounter counter = navigator as INodeCounter;
461 counter.CounterMarker = this.maxNodes;
462 counter.MaxCounter = this.maxNodes;
466 navigator = new SafeSeekableNavigator(navigator, this.maxNodes);
472 /// Checks the context pool for a processor first. If none is available, creates a new one
474 internal QueryProcessor CreateProcessor()
476 QueryProcessor p = null;
478 lock (this.processorPool)
480 QueryProcessorPool pool = this.processorPool.Target as QueryProcessorPool;
493 p = new QueryProcessor(this);
500 internal FilterResult Match(MessageBuffer messageBuffer, ICollection<MessageFilter> matches)
502 Message message = messageBuffer.CreateMessage();
506 result = this.Match(message, true, matches);
516 internal FilterResult Match(Message message, bool matchBody, ICollection<MessageFilter> matches)
518 QueryProcessor processor = this.CreateProcessor();
519 processor.MatchSet = matches;
520 processor.EnsureFilterCollection();
523 processor.Eval(this.query, message, matchBody);
525 catch (XPathNavigatorException e)
527 throw TraceUtility.ThrowHelperError(e.Process(this.query), message);
529 catch (NavigatorInvalidBodyAccessException e)
531 throw TraceUtility.ThrowHelperError(e.Process(this.query), message);
534 return new FilterResult(processor);
537 internal QueryResult<TResult> Evaluate<TResult>(MessageBuffer messageBuffer)
539 Message message = messageBuffer.CreateMessage();
540 return this.Evaluate<TResult>(message, true);
543 internal QueryResult<TResult> Evaluate<TResult>(Message message, bool matchBody)
545 return new QueryResult<TResult>(this, message, matchBody);
549 /// Execute matches over the given seekable navigator. If the navigator is not safe, wrap it with one that is
551 internal FilterResult Match(SeekableXPathNavigator navigator, ICollection<MessageFilter> matches)
553 // If the matcher places restrictions on the # of nodes we will inspect, and the navigator passed does
554 // not do any nodecounting itself, we must make that navigator safe by wrapping it
555 if (this.maxNodes < int.MaxValue)
557 navigator = this.CreateSafeNavigator(navigator);
560 QueryProcessor processor = this.CreateProcessor();
561 processor.MatchSet = matches;
562 processor.EnsureFilterCollection();
565 processor.Eval(this.query, navigator);
567 catch (XPathNavigatorException e)
569 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(this.query));
571 catch (NavigatorInvalidBodyAccessException e)
573 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(this.query));
576 return new FilterResult(processor);
580 /// Execute matches over the given navigator by wrapping it with a Seekable Navigator
582 internal FilterResult Match(XPathNavigator navigator, ICollection<MessageFilter> matches)
584 SeekableXPathNavigator nav = this.CreateSeekableNavigator(navigator);
585 return this.Match(nav, matches);
589 /// Release the given processor and place it back in the context pool
591 internal void ReleaseProcessor(QueryProcessor processor)
593 if (!processor.ReleaseRef())
598 lock (this.processorPool)
600 QueryProcessorPool pool = this.processorPool.Target as QueryProcessorPool;
603 pool = new QueryProcessorPool();
604 this.processorPool.Target = pool;
606 pool.Push(processor);
610 internal void ReleaseResult(FilterResult result)
612 if (null != result.Processor)
614 result.Processor.MatchSet = null;
615 this.ReleaseProcessor(result.Processor);
622 internal virtual void Trim()
624 if (this.query != null)
631 internal enum XPathFilterFlags
634 AlwaysMatch = 0x01, // filter always matches
635 IsFxFilter = 0x02, // filter is matched using the framework engine
639 /// A matcher used to evalute single XPath expressions
641 internal class XPathQueryMatcher : QueryMatcher
643 XPathFilterFlags flags;
645 static PushBooleanOpcode matchAlwaysFilter; // used for compiling xpaths that always match - i.e. xpath.Length == 0
646 static OpcodeBlock rootFilter; // used for compiling "/"
648 static XPathQueryMatcher()
650 XPathQueryMatcher.matchAlwaysFilter = new PushBooleanOpcode(true); //dummy
652 ValueDataType returnType;
653 XPathQueryMatcher.rootFilter = QueryMatcher.CompileForInternalEngine("/", null, QueryCompilerFlags.None, out returnType);
654 XPathQueryMatcher.rootFilter.Append(new MatchResultOpcode());
657 internal XPathQueryMatcher(bool match)
660 this.flags = XPathFilterFlags.None;
664 internal XPathFilterMatcher(XPathFilterMatcher matcher)
667 this.flags = matcher.flags;
670 internal bool IsAlwaysMatch
674 return (0 != (this.flags & XPathFilterFlags.AlwaysMatch));
678 internal bool IsFxFilter
682 return (0 != (this.flags & XPathFilterFlags.IsFxFilter));
687 /// If the xpath is an empty string, there is nothing to compile and the filter always matches
688 /// If not, try to compile the filter for execution within the filter engine's own query processor
689 /// If that query processor cannot accept the filter (it doesn't fall within the class of xpaths it can handle),
690 /// then revert to the fall-back solution - the slower Fx engine
692 internal void Compile(string expression, XmlNamespaceManager namespaces)
694 if (null == this.query)
696 // Try to compile for the internal engine first
699 this.CompileForInternal(expression, namespaces);
701 catch (QueryCompileException)
704 if (null == this.query)
706 // Try for an external engine that might work..
707 this.CompileForExternal(expression, namespaces);
713 /// Compile this xpath to run on an external (fx) xpath engine
715 internal void CompileForExternal(string xpath, XmlNamespaceManager names)
717 Opcode op = QueryMatcher.CompileForExternalEngine(xpath, names, null, this.match).First;
719 this.flags |= XPathFilterFlags.IsFxFilter;
723 /// Compile for the internal engine with default flags
724 /// By defalt, we compile an xpath to run stand alone, with standard optimizations
726 internal void CompileForInternal(string xpath, XmlNamespaceManager names)
729 xpath = xpath.Trim();
731 if (0 == xpath.Length)
733 // Empty xpaths always match. Same for xpaths that refer to the root only
734 // We will evaluate such filters with minimal overhead. However, we
735 // don't want a null value for this.query, so we stick a dummy value in there
736 this.query = XPathQueryMatcher.matchAlwaysFilter;
737 this.flags |= (XPathFilterFlags.AlwaysMatch);
739 else if (1 == xpath.Length && '/' == xpath[0])
741 this.query = XPathQueryMatcher.rootFilter.First;
742 this.flags |= (XPathFilterFlags.AlwaysMatch);
746 ValueDataType returnType;
747 OpcodeBlock codeBlock = QueryMatcher.CompileForInternalEngine(xpath, names, QueryCompilerFlags.None, out returnType);
748 // Inject a final opcode that will place the query result on the query context
749 // This query is now ready for execution STAND ALONE
752 codeBlock.Append(new MatchResultOpcode());
756 codeBlock.Append(new QueryResultOpcode());
759 this.query = codeBlock.First;
762 this.flags &= ~XPathFilterFlags.IsFxFilter;
765 internal FilterResult Match(MessageBuffer messageBuffer)
767 Message message = messageBuffer.CreateMessage();
772 result = this.Match(message, true);
781 internal FilterResult Match(Message message, bool matchBody)
783 if (this.IsAlwaysMatch)
785 // No need to do any expensive query evaluation if we know that the query will always match
786 return new FilterResult(true);
789 return base.Match(message, matchBody, null);
792 internal FilterResult Match(SeekableXPathNavigator navigator)
794 if (this.IsAlwaysMatch)
796 // No need to do any expensive query evaluation if we know that the query will always match
797 return new FilterResult(true);
800 // Is it a filter that we will evaluate using the framework engine?
801 // We can evaluate that without having to allocate a query processor
804 return new FilterResult(this.MatchFx(navigator));
807 return base.Match(navigator, null);
810 internal FilterResult Match(XPathNavigator navigator)
812 Fx.Assert(null != this.query, "");
813 if (this.IsAlwaysMatch)
815 return new FilterResult(true);
817 // Is it a filter that we will evaluate using the framework engine?
818 // We can evaluate that without having to allocate a query processor
821 return new FilterResult(this.MatchFx(navigator));
824 return base.Match(navigator, null);
828 /// Evaluates the filter over infosets surfaced via the given navigator by using the Fx engine
829 /// We assume that the filter was pre-compiled using the framework engine
831 internal bool MatchFx(XPathNavigator navigator)
833 INodeCounter counter = navigator as INodeCounter;
836 navigator = new SafeSeekableNavigator(new GenericSeekableNavigator(navigator), this.NodeQuota);
840 counter.CounterMarker = this.NodeQuota;
841 counter.MaxCounter = this.NodeQuota;
843 Fx.Assert(null != this.query && OpcodeID.MatchSingleFx == this.query.ID, "");
846 return ((MatchSingleFxEngineResultOpcode)this.query).Match(navigator);
848 catch (XPathNavigatorException e)
850 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(this.query));
852 catch (NavigatorInvalidBodyAccessException e)
854 throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(this.query));
859 internal class InverseQueryMatcher : QueryMatcher
861 SubExprEliminator elim;
862 Dictionary<object, Opcode> lastLookup;
865 internal InverseQueryMatcher(bool match)
868 this.elim = new SubExprEliminator();
869 this.lastLookup = new Dictionary<object, Opcode>();
873 internal void Add(string expression, XmlNamespaceManager names, object item, bool forceExternal)
875 Fx.Assert(null != item, "");
877 // Compile the new filter
879 bool compiled = false;
880 OpcodeBlock codeBlock = new OpcodeBlock();
882 codeBlock.Append(new NoOpOpcode(OpcodeID.QueryTree));
887 ValueDataType returnType = ValueDataType.None;
889 // Try to compile and merge the compiled query into the query tree
890 codeBlock.Append(QueryMatcher.CompileForInternalEngine(expression, names, QueryCompilerFlags.InverseQuery, out returnType));
892 MultipleResultOpcode opcode;
896 opcode = new QueryMultipleResultOpcode();
900 opcode = new MatchMultipleResultOpcode();
903 opcode.AddItem(item);
904 codeBlock.Append(opcode);
907 // Perform SubExpression Elimination
908 codeBlock = new OpcodeBlock(this.elim.Add(item, codeBlock.First));
909 this.subExprVars = this.elim.VariableCount;
911 catch (QueryCompileException)
913 // If the filter couldn't be compiled, we drop down to the framework engine
919 codeBlock.Append(QueryMatcher.CompileForExternalEngine(expression, names, item, this.match));
922 // Merge the compiled query into the query tree
923 QueryTreeBuilder builder = new QueryTreeBuilder();
924 this.query = builder.Build(this.query, codeBlock);
925 // To de-merge this filter from the tree, we'll have to walk backwards up the tree... so we
926 // have to remember the last opcode that is executed on behalf of this filter
927 this.lastLookup[item] = builder.LastOpcode;
930 internal void Clear()
932 foreach (object item in this.lastLookup.Keys)
934 this.Remove(this.lastLookup[item], item);
935 this.elim.Remove(item);
937 this.subExprVars = this.elim.VariableCount;
938 this.lastLookup.Clear();
941 internal void Remove(object item)
943 Fx.Assert(this.lastLookup.ContainsKey(item), "");
945 this.Remove(this.lastLookup[item], item);
946 this.lastLookup.Remove(item);
948 // Remove filter from subexpr eliminator
949 this.elim.Remove(item);
950 this.subExprVars = this.elim.VariableCount;
953 void Remove(Opcode opcode, object item)
955 MultipleResultOpcode multiOpcode = opcode as MultipleResultOpcode;
957 if (multiOpcode != null)
959 multiOpcode.RemoveItem(item);
967 internal override void Trim()