1 //------------------------------------------------------------ 2 // Copyright (c) Microsoft Corporation. All rights reserved. 3 //------------------------------------------------------------ 4 namespace System.ServiceModel.Dispatcher 5 { 6 using System.Runtime; 7 using System.Xml.XPath; 8 9 /// <summary> 10 /// This structure contains the criteria used to select a set of nodes from a context node 11 /// 12 /// Selectors select nodes with particular a relationship to a context node. Candidate nodes are first identified by 13 /// traversing away from the context node along an axis of traversal. The attribute axis, for example, identifies all 14 /// attributes of a given context node as candidates for selection. 15 /// 16 /// The candidate nodeset identified by axis traversal is then refined by applying node tests. 17 /// A nodeType test constructs a new nodeset by selecting only those nodes of a given type from source candidate set 18 /// A qname test further refines this nodeset by selecting only those that match a given qname 19 /// </summary> 20 class NodeSelectCriteria 21 { 22 protected QueryAxis axis; 23 protected NodeQName qname; 24 protected NodeQNameType qnameType; 25 protected QueryNodeType type; 26 NodeSelectCriteria(QueryAxisType axis, NodeQName qname, QueryNodeType nodeType)27 internal NodeSelectCriteria(QueryAxisType axis, NodeQName qname, QueryNodeType nodeType) 28 { 29 this.axis = QueryDataModel.GetAxis(axis); 30 this.qname = qname; 31 this.qnameType = qname.GetQNameType(); 32 this.type = nodeType; 33 } 34 35 internal QueryAxis Axis 36 { 37 get 38 { 39 return this.axis; 40 } 41 } 42 43 internal bool IsCompressable 44 { 45 get 46 { 47 // PERF, Microsoft, weaken guard? 48 return QueryAxisType.Self == this.axis.Type || QueryAxisType.Child == this.axis.Type; 49 //return ((QueryAxisType.Self == this.axis.Type) || ((this.axis.Type != QueryAxisType.DescendantOrSelf || this.axis.Type != QueryAxisType.Descendant)&& 0 != ((QueryNodeType.Element | QueryNodeType.Root) & this.type))); 50 } 51 } 52 53 internal NodeQName QName 54 { 55 get 56 { 57 return this.qname; 58 } 59 } 60 61 internal QueryNodeType Type 62 { 63 get 64 { 65 return this.type; 66 } 67 } 68 69 #if NO Create(QueryAxisType axis, NodeQName qname, QueryNodeType nodeType)70 internal static NodeSelectCriteria Create(QueryAxisType axis, NodeQName qname, QueryNodeType nodeType) 71 { 72 return new NodeSelectCriteria(axis, qname, nodeType); 73 } 74 #endif Equals(NodeSelectCriteria criteria)75 public bool Equals(NodeSelectCriteria criteria) 76 { 77 return (this.axis.Type == criteria.axis.Type && this.type == criteria.type && this.qname.Equals(criteria.qname)); 78 } 79 #if NO Match(SeekableXPathNavigator node)80 internal bool Match(SeekableXPathNavigator node) 81 { 82 return (this.MatchType(node) && this.MatchQName(node)); 83 } 84 #endif MatchType(SeekableXPathNavigator node)85 internal bool MatchType(SeekableXPathNavigator node) 86 { 87 QueryNodeType nodeType; 88 switch (node.NodeType) 89 { 90 default: 91 return false; 92 93 case XPathNodeType.Root: 94 nodeType = QueryNodeType.Root; 95 break; 96 97 case XPathNodeType.Attribute: 98 nodeType = QueryNodeType.Attribute; 99 break; 100 101 case XPathNodeType.Element: 102 nodeType = QueryNodeType.Element; 103 break; 104 105 case XPathNodeType.Comment: 106 nodeType = QueryNodeType.Comment; 107 break; 108 109 case XPathNodeType.Text: 110 case XPathNodeType.Whitespace: 111 case XPathNodeType.SignificantWhitespace: 112 nodeType = QueryNodeType.Text; 113 break; 114 115 case XPathNodeType.ProcessingInstruction: 116 nodeType = QueryNodeType.Processing; 117 break; 118 } 119 120 return (nodeType == (this.type & nodeType)); 121 } 122 MatchQName(SeekableXPathNavigator node)123 internal bool MatchQName(SeekableXPathNavigator node) 124 { 125 // Is this a standard qname test.. with known names and namespaces 126 switch (this.qnameType & NodeQNameType.Standard) 127 { 128 default: 129 break; 130 131 case NodeQNameType.Name: 132 // Selection criteria did not specify a namespace. Then, if the node supplies a namespace, we know 133 // that the criteria cannot possibly match 134 return (0 == node.NamespaceURI.Length && this.qname.EqualsName(node.LocalName)); 135 136 case NodeQNameType.Standard: 137 string str = node.LocalName; 138 if (this.qname.name.Length == str.Length && this.qname.name == str) 139 { 140 str = node.NamespaceURI; 141 return (this.qname.ns.Length == str.Length && this.qname.ns == str); 142 } 143 return false; 144 } 145 146 if (NodeQNameType.Empty == this.qnameType) 147 { 148 return true; 149 } 150 151 // Maybe a wildcard 152 switch (this.qnameType & NodeQNameType.Wildcard) 153 { 154 default: 155 break; 156 157 case NodeQNameType.NameWildcard: 158 return this.qname.EqualsNamespace(node.NamespaceURI); 159 160 case NodeQNameType.Wildcard: 161 return true; 162 } 163 164 return false; 165 } 166 Select(SeekableXPathNavigator contextNode, NodeSequence destSequence)167 internal void Select(SeekableXPathNavigator contextNode, NodeSequence destSequence) 168 { 169 switch (this.type) 170 { 171 default: 172 if (QueryAxisType.Self == this.axis.Type) 173 { 174 if (this.MatchType(contextNode) && this.MatchQName(contextNode)) 175 { 176 destSequence.Add(contextNode); 177 } 178 } 179 else if (QueryAxisType.Descendant == this.axis.Type) 180 { 181 SelectDescendants(contextNode, destSequence); 182 } 183 else if (QueryAxisType.DescendantOrSelf == this.axis.Type) 184 { 185 destSequence.Add(contextNode); 186 SelectDescendants(contextNode, destSequence); 187 } 188 else if (QueryAxisType.Child == this.axis.Type) 189 { 190 // Select children of arbitrary type off the context node 191 if (contextNode.MoveToFirstChild()) 192 { 193 do 194 { 195 // Select the node if its type and qname matches 196 if (this.MatchType(contextNode) && this.MatchQName(contextNode)) 197 { 198 destSequence.Add(contextNode); 199 } 200 } 201 while (contextNode.MoveToNext()); 202 } 203 204 } 205 else if (QueryAxisType.Attribute == this.axis.Type) 206 { 207 if (contextNode.MoveToFirstAttribute()) 208 { 209 do 210 { 211 // Select the node if its type and qname matches 212 if (this.MatchType(contextNode) && this.MatchQName(contextNode)) 213 { 214 destSequence.Add(contextNode); 215 // you can't have multiple instances of an attibute with the same qname 216 // Stop once one was found 217 // UNLESS WE HAVE A WILDCARD OFCOURSE! 218 if (0 == (this.qnameType & NodeQNameType.Wildcard)) 219 { 220 break; 221 } 222 } 223 } 224 while (contextNode.MoveToNextAttribute()); 225 } 226 227 } 228 else 229 { 230 throw DiagnosticUtility.ExceptionUtility.ThrowHelperCritical(new QueryProcessingException(QueryProcessingError.Unexpected)); 231 } 232 break; 233 234 case QueryNodeType.Attribute: 235 // Select attributes off the context Node 236 if (contextNode.MoveToFirstAttribute()) 237 { 238 do 239 { 240 if (this.MatchQName(contextNode)) 241 { 242 destSequence.Add(contextNode); 243 // you can't have multiple instances of an attibute with the same qname 244 // Stop once one was found 245 // UNLESS WE HAVE A WILDCARD OFCOURSE! 246 if (0 == (this.qnameType & NodeQNameType.Wildcard)) 247 { 248 break; 249 } 250 } 251 } 252 while (contextNode.MoveToNextAttribute()); 253 } 254 break; 255 256 case QueryNodeType.ChildNodes: 257 if (QueryAxisType.Descendant == this.axis.Type) 258 { 259 // Select descendants of arbitrary type off the context node 260 SelectDescendants(contextNode, destSequence); 261 } 262 else 263 { 264 // Select children of arbitrary type off the context node 265 if (contextNode.MoveToFirstChild()) 266 { 267 do 268 { 269 // Select the node if its type and qname matches 270 if (this.MatchType(contextNode) && this.MatchQName(contextNode)) 271 { 272 destSequence.Add(contextNode); 273 } 274 } 275 while (contextNode.MoveToNext()); 276 } 277 } 278 break; 279 280 case QueryNodeType.Element: 281 if (QueryAxisType.Descendant == this.axis.Type) 282 { 283 // Select descendants of arbitrary type off the context node 284 SelectDescendants(contextNode, destSequence); 285 } 286 else if (QueryAxisType.DescendantOrSelf == this.axis.Type) 287 { 288 destSequence.Add(contextNode); 289 SelectDescendants(contextNode, destSequence); 290 } 291 else if (contextNode.MoveToFirstChild()) 292 { 293 do 294 { 295 // Children could have non element nodes in line 296 // Select the node if it is an element and the qname matches 297 if (XPathNodeType.Element == contextNode.NodeType && this.MatchQName(contextNode)) 298 { 299 destSequence.Add(contextNode); 300 } 301 } 302 while (contextNode.MoveToNext()); 303 } 304 break; 305 306 case QueryNodeType.Root: 307 contextNode.MoveToRoot(); 308 destSequence.Add(contextNode); 309 break; 310 311 case QueryNodeType.Text: 312 // Select child text nodes 313 if (contextNode.MoveToFirstChild()) 314 { 315 do 316 { 317 // Select the node if its type matches 318 // Can't just do a comparison to XPathNodeType.Text since whitespace nodes 319 // count as text 320 if (this.MatchType(contextNode)) 321 { 322 destSequence.Add(contextNode); 323 } 324 } 325 while (contextNode.MoveToNext()); 326 } 327 break; 328 } 329 } 330 Select(SeekableXPathNavigator contextNode, NodeSequence destSequence, SelectOpcode next)331 internal Opcode Select(SeekableXPathNavigator contextNode, NodeSequence destSequence, SelectOpcode next) 332 { 333 Opcode returnOpcode = next.Next; 334 335 switch (this.type) 336 { 337 default: 338 if (QueryAxisType.Self == this.axis.Type) 339 { 340 if (this.MatchType(contextNode) && this.MatchQName(contextNode)) 341 { 342 long position = contextNode.CurrentPosition; 343 returnOpcode = next.Eval(destSequence, contextNode); 344 contextNode.CurrentPosition = position; 345 } 346 } 347 else 348 { 349 throw DiagnosticUtility.ExceptionUtility.ThrowHelperCritical(new QueryProcessingException(QueryProcessingError.Unexpected)); 350 } 351 352 break; 353 354 case QueryNodeType.ChildNodes: 355 // Select children of arbitrary type off the context node 356 if (contextNode.MoveToFirstChild()) 357 { 358 do 359 { 360 // Select the node if its type and qname matches 361 if (this.MatchType(contextNode) && this.MatchQName(contextNode)) 362 { 363 destSequence.Add(contextNode); 364 } 365 } 366 while (contextNode.MoveToNext()); 367 } 368 break; 369 370 case QueryNodeType.Element: 371 // Select child elements 372 if (contextNode.MoveToFirstChild()) 373 { 374 do 375 { 376 // Children could have non element nodes in line 377 // Select the node if it is an element and the qname matches 378 if (XPathNodeType.Element == contextNode.NodeType && this.MatchQName(contextNode)) 379 { 380 long position = contextNode.CurrentPosition; 381 returnOpcode = next.Eval(destSequence, contextNode); 382 contextNode.CurrentPosition = position; 383 } 384 } while (contextNode.MoveToNext()); 385 } 386 387 break; 388 389 case QueryNodeType.Root: 390 contextNode.MoveToRoot(); 391 returnOpcode = next.Eval(destSequence, contextNode); 392 break; 393 } 394 395 return returnOpcode; 396 } 397 SelectDescendants(SeekableXPathNavigator contextNode, NodeSequence destSequence)398 void SelectDescendants(SeekableXPathNavigator contextNode, NodeSequence destSequence) 399 { 400 int level = 1; 401 if (!contextNode.MoveToFirstChild()) 402 { 403 return; 404 } 405 while (level > 0) 406 { 407 // Don't need type check. All child nodes allowed. 408 if (this.MatchQName(contextNode)) 409 { 410 destSequence.Add(contextNode); 411 } 412 413 if (contextNode.MoveToFirstChild()) 414 { 415 ++level; 416 } 417 else if (contextNode.MoveToNext()) 418 { 419 420 } 421 else 422 { 423 while (level > 0) 424 { 425 contextNode.MoveToParent(); 426 --level; 427 428 if (contextNode.MoveToNext()) 429 { 430 break; 431 } 432 } 433 } 434 } 435 } 436 437 #if DEBUG_FILTER ToString()438 public override string ToString() 439 { 440 return string.Format("{0}, {1}:{2}", this.type, this.qname.ns, this.qname.name); 441 } 442 #endif 443 444 } 445 446 // General purpose selector 447 // Pops all parameters from the value stack 448 internal class SelectOpcode : Opcode 449 { 450 protected NodeSelectCriteria criteria; 451 SelectOpcode(NodeSelectCriteria criteria)452 internal SelectOpcode(NodeSelectCriteria criteria) 453 : this(OpcodeID.Select, criteria) 454 { 455 } 456 SelectOpcode(OpcodeID id, NodeSelectCriteria criteria)457 internal SelectOpcode(OpcodeID id, NodeSelectCriteria criteria) 458 : this(id, criteria, OpcodeFlags.None) 459 { 460 } 461 SelectOpcode(OpcodeID id, NodeSelectCriteria criteria, OpcodeFlags flags)462 internal SelectOpcode(OpcodeID id, NodeSelectCriteria criteria, OpcodeFlags flags) 463 : base(id) 464 { 465 this.criteria = criteria; 466 this.flags |= (flags | OpcodeFlags.Select); 467 if (criteria.IsCompressable && (0 == (this.flags & OpcodeFlags.InitialSelect))) 468 { 469 this.flags |= OpcodeFlags.CompressableSelect; 470 } 471 } 472 473 internal NodeSelectCriteria Criteria 474 { 475 get 476 { 477 return this.criteria; 478 } 479 } 480 Equals(Opcode op)481 internal override bool Equals(Opcode op) 482 { 483 if (base.Equals(op)) 484 { 485 return this.criteria.Equals(((SelectOpcode)op).criteria); 486 } 487 488 return false; 489 } 490 Eval(ProcessingContext context)491 internal override Opcode Eval(ProcessingContext context) 492 { 493 StackFrame topFrame = context.TopSequenceArg; 494 SeekableXPathNavigator node = null; 495 Value[] sequences = context.Sequences; 496 497 for (int i = topFrame.basePtr; i <= topFrame.endPtr; ++i) 498 { 499 // Each NodeSequence will generate a new one, but only if the source FilterSequence isn't empty 500 // If the source FilterSequence is empty, release it and replace it with an empty sequence 501 NodeSequence sourceSeq = sequences[i].Sequence; 502 int sourceSeqCount = sourceSeq.Count; 503 if (sourceSeqCount == 0) 504 { 505 context.ReplaceSequenceAt(i, NodeSequence.Empty); 506 context.ReleaseSequence(sourceSeq); 507 } 508 else 509 { 510 NodeSequenceItem[] items = sourceSeq.Items; 511 if (sourceSeq.CanReuse(context)) 512 { 513 node = items[0].GetNavigator(); 514 sourceSeq.Clear(); 515 sourceSeq.StartNodeset(); 516 517 this.criteria.Select(node, sourceSeq); 518 519 sourceSeq.StopNodeset(); 520 } 521 else 522 { 523 NodeSequence newSeq = null; 524 for (int item = 0; item < sourceSeqCount; ++item) 525 { 526 node = items[item].GetNavigator(); 527 Fx.Assert(null != node, ""); 528 if (null == newSeq) 529 { 530 newSeq = context.CreateSequence(); 531 } 532 newSeq.StartNodeset(); 533 this.criteria.Select(node, newSeq); 534 newSeq.StopNodeset(); 535 } 536 context.ReplaceSequenceAt(i, (null != newSeq) ? newSeq : NodeSequence.Empty); 537 context.ReleaseSequence(sourceSeq); 538 } 539 } 540 } 541 542 return this.next; 543 } 544 Eval(NodeSequence sequence, SeekableXPathNavigator node)545 internal override Opcode Eval(NodeSequence sequence, SeekableXPathNavigator node) 546 { 547 if (this.next == null || 0 == (this.next.Flags & OpcodeFlags.CompressableSelect)) 548 { 549 // The next opcode is not a compressible select. Complete the select operation and return the next opcode 550 sequence.StartNodeset(); 551 this.criteria.Select(node, sequence); 552 sequence.StopNodeset(); 553 return this.next; 554 } 555 556 return this.criteria.Select(node, sequence, (SelectOpcode)this.next); 557 } 558 559 #if DEBUG_FILTER ToString()560 public override string ToString() 561 { 562 return string.Format("{0} {1}", base.ToString(), this.criteria.ToString()); 563 } 564 #endif 565 } 566 567 internal class InitialSelectOpcode : SelectOpcode 568 { InitialSelectOpcode(NodeSelectCriteria criteria)569 internal InitialSelectOpcode(NodeSelectCriteria criteria) 570 : base(OpcodeID.InitialSelect, criteria, OpcodeFlags.InitialSelect) 571 { 572 } 573 Eval(ProcessingContext context)574 internal override Opcode Eval(ProcessingContext context) 575 { 576 StackFrame topFrame = context.TopSequenceArg; 577 Value[] sequences = context.Sequences; 578 579 bool wasInUse = context.SequenceStackInUse; 580 context.PushSequenceFrame(); 581 for (int i = topFrame.basePtr; i <= topFrame.endPtr; ++i) 582 { 583 NodeSequence sourceSeq = sequences[i].Sequence; 584 int count = sourceSeq.Count; 585 if (count == 0) 586 { 587 // Empty sequence. 588 // Since there are no nodes in the sequence, we will track this sequence also 589 // using an empty sequence 590 if (!wasInUse) 591 context.PushSequence(NodeSequence.Empty); 592 } 593 else 594 { 595 NodeSequenceItem[] items = sourceSeq.Items; 596 for (int item = 0; item < sourceSeq.Count; ++item) 597 { 598 SeekableXPathNavigator node = items[item].GetNavigator(); 599 Fx.Assert(null != node, ""); 600 601 NodeSequence newSeq = context.CreateSequence(); 602 newSeq.StartNodeset(); 603 604 this.criteria.Select(node, newSeq); 605 606 newSeq.StopNodeset(); 607 608 context.PushSequence(newSeq); 609 } 610 } 611 } 612 return this.next; 613 } 614 } 615 616 internal class SelectRootOpcode : Opcode 617 { SelectRootOpcode()618 internal SelectRootOpcode() 619 : base(OpcodeID.SelectRoot) 620 { 621 } 622 Eval(ProcessingContext context)623 internal override Opcode Eval(ProcessingContext context) 624 { 625 // The query processor object also serves as the query document root 626 int iterationCount = context.IterationCount; 627 Opcode returnOpcode = this.next; 628 629 // A root is always an initial step 630 context.PushSequenceFrame(); 631 NodeSequence seq = context.CreateSequence(); 632 if (this.next != null && 0 != (this.next.Flags & OpcodeFlags.CompressableSelect)) 633 { 634 SeekableXPathNavigator node = context.Processor.ContextNode; 635 node.MoveToRoot(); 636 returnOpcode = this.next.Eval(seq, node); 637 while (returnOpcode != null && 0 != (returnOpcode.Flags & OpcodeFlags.CompressableSelect)) 638 { 639 returnOpcode = returnOpcode.Next; 640 } 641 } 642 else 643 { 644 // Roots do not have any qnames.. 645 seq.StartNodeset(); 646 SeekableXPathNavigator node = context.Processor.ContextNode; 647 node.MoveToRoot(); 648 seq.Add(node); 649 seq.StopNodeset(); 650 } 651 652 if (seq.Count == 0) 653 { 654 context.ReleaseSequence(seq); 655 seq = NodeSequence.Empty; 656 } 657 658 for (int i = 0; i < iterationCount; ++i) 659 { 660 context.PushSequence(seq); 661 } 662 if (iterationCount > 1) 663 seq.refCount += iterationCount - 1; 664 665 return returnOpcode; 666 } 667 } 668 } 669