1 //------------------------------------------------------------------------------ 2 // <copyright file="ContentValidator.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // <owner current="true" primary="true">Microsoft</owner> 6 //------------------------------------------------------------------------------ 7 using System; 8 using System.Collections; 9 using System.Collections.Generic; 10 using System.Globalization; 11 using System.Text; 12 using System.Diagnostics; 13 14 namespace System.Xml.Schema { 15 16 #region ExceptionSymbolsPositions 17 18 /// <summary> 19 /// UPA violations will throw this exception 20 /// </summary> 21 class UpaException : Exception { 22 object particle1; 23 object particle2; UpaException(object particle1, object particle2)24 public UpaException(object particle1, object particle2) { 25 this.particle1 = particle1; 26 this.particle2 = particle2; 27 } 28 public object Particle1 { get { return particle1; } } 29 public object Particle2 { get { return particle2; } } 30 } 31 32 /// <summary> 33 /// SymbolsDictionary is a map between names that ContextValidator recognizes and symbols - int symbol[XmlQualifiedName name]. 34 /// There are two types of name - full names and wildcards (namespace is specified, local name is anythig). 35 /// Wildcard excludes all full names that would match by the namespace part. 36 /// SymbolsDictionry alwas recognizes all the symbols - the last one is a true wildcard - 37 /// both name and namespace can be anything that none of the other symbols matched. 38 /// </summary> 39 class SymbolsDictionary { 40 int last = 0; 41 Hashtable names; 42 Hashtable wildcards = null; 43 ArrayList particles; 44 object particleLast = null; 45 bool isUpaEnforced = true; 46 SymbolsDictionary()47 public SymbolsDictionary() { 48 names = new Hashtable(); 49 particles = new ArrayList(); 50 } 51 52 public int Count { 53 // last one is a "*:*" any wildcard 54 get { return last + 1; } 55 } 56 57 public int CountOfNames { 58 get { return names.Count; } 59 } 60 61 /// <summary> 62 /// True is particle can be deterministically attributed from the symbol and conversion to DFA is possible. 63 /// </summary> 64 public bool IsUpaEnforced { 65 get { return isUpaEnforced; } 66 set { isUpaEnforced = value; } 67 } 68 69 /// <summary> 70 /// Add name and return it's number 71 /// </summary> AddName(XmlQualifiedName name, object particle)72 public int AddName(XmlQualifiedName name, object particle) { 73 object lookup = names[name]; 74 if (lookup != null) { 75 int symbol = (int)lookup; 76 if (particles[symbol] != particle) { 77 isUpaEnforced = false; 78 } 79 return symbol; 80 } 81 else { 82 names.Add(name, last); 83 particles.Add(particle); 84 Debug.Assert(particles.Count == last + 1); 85 return last ++; 86 } 87 } 88 AddNamespaceList(NamespaceList list, object particle, bool allowLocal)89 public void AddNamespaceList(NamespaceList list, object particle, bool allowLocal) { 90 switch (list.Type) { 91 case NamespaceList.ListType.Any: 92 particleLast = particle; 93 break; 94 case NamespaceList.ListType.Other: 95 // Create a symbol for the excluded namespace, but don't set a particle for it. 96 AddWildcard(list.Excluded, null); 97 if (!allowLocal) { 98 AddWildcard(string.Empty, null); //##local is not allowed 99 } 100 break; 101 case NamespaceList.ListType.Set: 102 foreach(string wildcard in list.Enumerate) { 103 AddWildcard(wildcard, particle); 104 } 105 break; 106 } 107 } 108 AddWildcard(string wildcard, object particle)109 private void AddWildcard(string wildcard, object particle) { 110 if (wildcards == null) { 111 wildcards = new Hashtable(); 112 } 113 object lookup = wildcards[wildcard]; 114 if (lookup == null) { 115 wildcards.Add(wildcard, last); 116 particles.Add(particle); 117 Debug.Assert(particles.Count == last + 1); 118 last ++; 119 } 120 else if (particle != null) { 121 particles[(int)lookup] = particle; 122 } 123 } 124 GetNamespaceListSymbols(NamespaceList list)125 public ICollection GetNamespaceListSymbols(NamespaceList list) { 126 ArrayList match = new ArrayList(); 127 foreach(XmlQualifiedName name in names.Keys) { 128 if (name != XmlQualifiedName.Empty && list.Allows(name)) { 129 match.Add(names[name]); 130 } 131 } 132 if (wildcards != null) { 133 foreach(string wildcard in wildcards.Keys) { 134 if (list.Allows(wildcard)) { 135 match.Add(wildcards[wildcard]); 136 } 137 } 138 } 139 if (list.Type == NamespaceList.ListType.Any || list.Type == NamespaceList.ListType.Other) { 140 match.Add(last); // add wildcard 141 } 142 return match; 143 } 144 145 /// <summary> 146 /// Find the symbol for the given name. If neither names nor wilcards match it last (*.*) symbol will be returned 147 /// </summary> 148 public int this[XmlQualifiedName name] { 149 get { 150 object lookup = names[name]; 151 if (lookup != null) { 152 return (int)lookup; 153 } 154 if (wildcards != null) { 155 lookup = wildcards[name.Namespace]; 156 if (lookup != null) { 157 return (int)lookup; 158 } 159 } 160 return last; // true wildcard 161 } 162 } 163 164 /// <summary> 165 /// Check if a name exists in the symbol dictionary 166 /// </summary> Exists(XmlQualifiedName name)167 public bool Exists(XmlQualifiedName name) { 168 169 object lookup = names[name]; 170 if (lookup != null) { 171 return true; 172 } 173 return false; 174 } 175 176 /// <summary> 177 /// Return content processing mode for the symbol 178 /// </summary> GetParticle(int symbol)179 public object GetParticle(int symbol) { 180 return symbol == last ? particleLast : particles[symbol]; 181 } 182 183 /// <summary> 184 /// Output symbol's name 185 /// </summary> NameOf(int symbol)186 public string NameOf(int symbol) { 187 foreach (DictionaryEntry de in names) { 188 if ((int)de.Value == symbol) { 189 return ((XmlQualifiedName)de.Key).ToString(); 190 } 191 } 192 if (wildcards != null) { 193 foreach (DictionaryEntry de in wildcards) { 194 if ((int)de.Value == symbol) { 195 return (string)de.Key + ":*"; 196 } 197 } 198 } 199 return "##other:*"; 200 } 201 } 202 203 struct Position { 204 public int symbol; 205 public object particle; PositionSystem.Xml.Schema.Position206 public Position(int symbol, object particle) { 207 this.symbol = symbol; 208 this.particle = particle; 209 } 210 } 211 212 class Positions { 213 ArrayList positions = new ArrayList(); 214 Add(int symbol, object particle)215 public int Add(int symbol, object particle) { 216 return positions.Add(new Position(symbol, particle)); 217 } 218 219 public Position this[int pos] { 220 get { return (Position)positions[pos]; } 221 } 222 223 public int Count { 224 get { return positions.Count; } 225 } 226 } 227 #endregion 228 229 #region SystaxTree 230 /// <summary> 231 /// Base class for the systax tree nodes 232 /// </summary> 233 abstract class SyntaxTreeNode { 234 /// <summary> 235 /// Expand NamesapceListNode and RangeNode nodes. All other nodes 236 /// </summary> ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)237 public abstract void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions); 238 239 /// <summary> 240 /// Clone the syntaxTree. We need to pass symbolsByPosition because leaf nodes have to add themselves to it. 241 /// </summary> Clone(Positions positions)242 public abstract SyntaxTreeNode Clone(Positions positions); 243 244 /// <summary> 245 /// From a regular expression to a DFA 246 /// Compilers by Aho, Sethi, Ullman. 247 /// ISBN 0-201-10088-6, p135 248 /// Construct firstpos, lastpos and calculate followpos 249 /// </summary> ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)250 public abstract void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos); 251 252 /// <summary> 253 /// Returns nullable property that is being used by ConstructPos 254 /// </summary> 255 public abstract bool IsNullable { get; } 256 257 /// <summary> 258 /// Returns true if node is a range node 259 /// </summary> 260 public virtual bool IsRangeNode { 261 get { 262 return false; 263 } 264 } 265 266 /// <summary> 267 /// Print syntax tree 268 /// </summary> 269 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)270 public abstract void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions); 271 #endif 272 } 273 274 /// <summary> 275 /// Terminal of the syntax tree 276 /// </summary> 277 class LeafNode : SyntaxTreeNode { 278 int pos; 279 LeafNode(int pos)280 public LeafNode(int pos) { 281 this.pos = pos; 282 } 283 284 public int Pos { 285 get { return pos;} 286 set { pos = value; } 287 } 288 ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)289 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 290 // do nothing 291 } 292 Clone(Positions positions)293 public override SyntaxTreeNode Clone(Positions positions) { 294 return new LeafNode(positions.Add(positions[pos].symbol, positions[pos].particle)); 295 } 296 ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)297 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 298 firstpos.Set(pos); 299 lastpos.Set(pos); 300 } 301 302 public override bool IsNullable { 303 get { return false; } 304 } 305 306 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)307 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 308 bb.Append("\"" + symbols.NameOf(positions[pos].symbol) + "\""); 309 } 310 #endif 311 } 312 313 /// <summary> 314 /// Temporary node to represent NamespaceList. Will be expended as a choice of symbols 315 /// </summary> 316 class NamespaceListNode : SyntaxTreeNode { 317 protected NamespaceList namespaceList; 318 protected object particle; 319 NamespaceListNode(NamespaceList namespaceList, object particle)320 public NamespaceListNode(NamespaceList namespaceList, object particle) { 321 this.namespaceList = namespaceList; 322 this.particle = particle; 323 } 324 Clone(Positions positions)325 public override SyntaxTreeNode Clone(Positions positions) { 326 // NamespaceListNode nodes have to be removed prior to that 327 throw new InvalidOperationException(); 328 } 329 GetResolvedSymbols(SymbolsDictionary symbols)330 public virtual ICollection GetResolvedSymbols(SymbolsDictionary symbols) { 331 return symbols.GetNamespaceListSymbols(namespaceList); 332 } 333 ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)334 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 335 SyntaxTreeNode replacementNode = null; 336 foreach(int symbol in GetResolvedSymbols(symbols)) { 337 if (symbols.GetParticle(symbol) != particle) { 338 symbols.IsUpaEnforced = false; 339 } 340 LeafNode node = new LeafNode(positions.Add(symbol, particle)); 341 if (replacementNode == null) { 342 replacementNode = node; 343 } 344 else { 345 InteriorNode choice = new ChoiceNode(); 346 choice.LeftChild = replacementNode; 347 choice.RightChild = node; 348 replacementNode = choice; 349 } 350 } 351 if (parent.LeftChild == this) { 352 parent.LeftChild = replacementNode; 353 } 354 else { 355 parent.RightChild = replacementNode; 356 } 357 } 358 ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)359 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 360 // NamespaceListNode nodes have to be removed prior to that 361 throw new InvalidOperationException(); 362 } 363 364 public override bool IsNullable { 365 // NamespaceListNode nodes have to be removed prior to that 366 get { throw new InvalidOperationException(); } 367 } 368 369 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)370 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 371 bb.Append("[" + namespaceList.ToString() + "]"); 372 } 373 #endif 374 } 375 376 /// <summary> 377 /// Base class for all internal node. Note that only sequence and choice have right child 378 /// </summary> 379 abstract class InteriorNode : SyntaxTreeNode { 380 SyntaxTreeNode leftChild; 381 SyntaxTreeNode rightChild; 382 383 public SyntaxTreeNode LeftChild { 384 get { return leftChild;} 385 set { leftChild = value;} 386 } 387 388 public SyntaxTreeNode RightChild { 389 get { return rightChild;} 390 set { rightChild = value;} 391 } 392 Clone(Positions positions)393 public override SyntaxTreeNode Clone(Positions positions) { 394 InteriorNode other = (InteriorNode)this.MemberwiseClone(); 395 other.LeftChild = leftChild.Clone(positions); 396 if (rightChild != null) { 397 other.RightChild = rightChild.Clone(positions); 398 } 399 return other; 400 } 401 402 //no recursive version of expand tree for Sequence and Choice node ExpandTreeNoRecursive(InteriorNode parent, SymbolsDictionary symbols, Positions positions)403 protected void ExpandTreeNoRecursive(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 404 Stack<InteriorNode> nodeStack = new Stack<InteriorNode>(); 405 InteriorNode this_ = this; 406 while (true) { 407 if (this_.leftChild is ChoiceNode || this_.leftChild is SequenceNode) { 408 nodeStack.Push(this_); 409 this_ = (InteriorNode)this_.leftChild; 410 continue; 411 } 412 this_.leftChild.ExpandTree(this_, symbols, positions); 413 414 ProcessRight: 415 if (this_.rightChild != null) { 416 this_.rightChild.ExpandTree(this_, symbols, positions); 417 } 418 419 if (nodeStack.Count == 0) 420 break; 421 422 this_ = nodeStack.Pop(); 423 goto ProcessRight; 424 } 425 } 426 ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)427 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 428 leftChild.ExpandTree(this, symbols, positions); 429 if (rightChild != null) { 430 rightChild.ExpandTree(this, symbols, positions); 431 } 432 } 433 } 434 435 436 sealed class SequenceNode : InteriorNode { 437 438 struct SequenceConstructPosContext { 439 public SequenceNode this_; 440 public BitSet firstpos; 441 public BitSet lastpos; 442 public BitSet lastposLeft; 443 public BitSet firstposRight; 444 SequenceConstructPosContextSystem.Xml.Schema.SequenceNode.SequenceConstructPosContext445 public SequenceConstructPosContext(SequenceNode node, BitSet firstpos, BitSet lastpos) { 446 this_ = node; 447 this.firstpos = firstpos; 448 this.lastpos = lastpos; 449 450 lastposLeft = null; 451 firstposRight = null; 452 } 453 } 454 ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)455 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 456 457 Stack<SequenceConstructPosContext> contextStack = new Stack<SequenceConstructPosContext>(); 458 SequenceConstructPosContext context = new SequenceConstructPosContext(this, firstpos, lastpos); 459 460 while (true) { 461 SequenceNode this_ = context.this_; 462 context.lastposLeft = new BitSet(lastpos.Count); 463 if (this_.LeftChild is SequenceNode) { 464 contextStack.Push(context); 465 context = new SequenceConstructPosContext((SequenceNode)this_.LeftChild, context.firstpos, context.lastposLeft); 466 continue; 467 } 468 this_.LeftChild.ConstructPos(context.firstpos, context.lastposLeft, followpos); 469 470 ProcessRight: 471 context.firstposRight = new BitSet(firstpos.Count); 472 this_.RightChild.ConstructPos(context.firstposRight, context.lastpos, followpos); 473 474 if (this_.LeftChild.IsNullable && !this_.RightChild.IsRangeNode) { 475 context.firstpos.Or(context.firstposRight); 476 } 477 if (this_.RightChild.IsNullable) { 478 context.lastpos.Or(context.lastposLeft); 479 } 480 for (int pos = context.lastposLeft.NextSet(-1); pos != -1; pos = context.lastposLeft.NextSet(pos)) { 481 followpos[pos].Or(context.firstposRight); 482 } 483 if (this_.RightChild.IsRangeNode) { //firstpos is leftchild.firstpos as the or with firstposRight has not been done as it is a rangenode 484 ((LeafRangeNode)this_.RightChild).NextIteration = context.firstpos.Clone(); 485 } 486 487 if (contextStack.Count == 0) 488 break; 489 490 context = contextStack.Pop(); 491 this_ = context.this_; 492 goto ProcessRight; 493 } 494 } 495 496 public override bool IsNullable { 497 get { 498 SyntaxTreeNode n; 499 SequenceNode this_ = this; 500 do { 501 if (this_.RightChild.IsRangeNode && ((LeafRangeNode)this_.RightChild).Min == 0) 502 return true; 503 if (!this_.RightChild.IsNullable && !this_.RightChild.IsRangeNode) 504 return false; 505 n = this_.LeftChild; 506 this_ = n as SequenceNode; 507 } 508 while (this_ != null); 509 return n.IsNullable; 510 } 511 } 512 ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)513 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 514 ExpandTreeNoRecursive(parent, symbols, positions); 515 } 516 517 #if DEBUG WritePos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)518 internal static void WritePos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 519 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "FirstPos: "); 520 WriteBitSet(firstpos); 521 522 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "LastPos: "); 523 WriteBitSet(lastpos); 524 525 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Followpos: "); 526 for(int i =0; i < followpos.Length; i++) { 527 WriteBitSet(followpos[i]); 528 } 529 } WriteBitSet(BitSet curpos)530 internal static void WriteBitSet(BitSet curpos) { 531 int[] list = new int[curpos.Count]; 532 for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 533 list[pos] = 1; 534 } 535 for(int i = 0; i < list.Length; i++) { 536 Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, list[i] + " "); 537 } 538 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 539 } 540 541 Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)542 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 543 Stack<SequenceNode> nodeStack = new Stack<SequenceNode>(); 544 SequenceNode this_ = this; 545 546 while (true) { 547 bb.Append("("); 548 if (this_.LeftChild is SequenceNode) { 549 nodeStack.Push(this_); 550 this_ = (SequenceNode)this_.LeftChild; 551 continue; 552 } 553 this_.LeftChild.Dump(bb, symbols, positions); 554 555 ProcessRight: 556 bb.Append(", "); 557 this_.RightChild.Dump(bb, symbols, positions); 558 bb.Append(")"); 559 if (nodeStack.Count == 0) 560 break; 561 562 this_ = nodeStack.Pop(); 563 goto ProcessRight; 564 } 565 } 566 #endif 567 568 } 569 570 sealed class ChoiceNode : InteriorNode { 571 ConstructChildPos(SyntaxTreeNode child, BitSet firstpos, BitSet lastpos, BitSet[] followpos)572 private static void ConstructChildPos(SyntaxTreeNode child, BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 573 BitSet firstPosTemp = new BitSet(firstpos.Count); 574 BitSet lastPosTemp = new BitSet(lastpos.Count); 575 child.ConstructPos(firstPosTemp, lastPosTemp, followpos); 576 firstpos.Or(firstPosTemp); 577 lastpos.Or(lastPosTemp); 578 } 579 ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)580 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 581 582 BitSet firstPosTemp = new BitSet(firstpos.Count); 583 BitSet lastPosTemp = new BitSet(lastpos.Count); 584 SyntaxTreeNode n; 585 ChoiceNode this_ = this; 586 do { 587 ConstructChildPos(this_.RightChild, firstPosTemp, lastPosTemp, followpos); 588 n = this_.LeftChild; 589 this_ = n as ChoiceNode; 590 } while (this_ != null); 591 592 n.ConstructPos(firstpos, lastpos, followpos); 593 firstpos.Or(firstPosTemp); 594 lastpos.Or(lastPosTemp); 595 } 596 597 public override bool IsNullable { 598 get { 599 SyntaxTreeNode n; 600 ChoiceNode this_ = this; 601 do { 602 if (this_.RightChild.IsNullable) 603 return true; 604 n = this_.LeftChild; 605 this_ = n as ChoiceNode; 606 } 607 while (this_ != null); 608 return n.IsNullable; 609 } 610 } 611 ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)612 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 613 ExpandTreeNoRecursive(parent, symbols, positions); 614 } 615 616 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)617 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 618 Stack<ChoiceNode> nodeStack = new Stack<ChoiceNode>(); 619 ChoiceNode this_ = this; 620 621 while (true) { 622 bb.Append("("); 623 if (this_.LeftChild is ChoiceNode) { 624 nodeStack.Push(this_); 625 this_ = (ChoiceNode)this_.LeftChild; 626 continue; 627 } 628 this_.LeftChild.Dump(bb, symbols, positions); 629 630 ProcessRight: 631 bb.Append(" | "); 632 this_.RightChild.Dump(bb, symbols, positions); 633 bb.Append(")"); 634 if (nodeStack.Count == 0) 635 break; 636 637 this_ = nodeStack.Pop(); 638 goto ProcessRight; 639 } 640 } 641 #endif 642 } 643 644 sealed class PlusNode : InteriorNode { ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)645 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 646 LeftChild.ConstructPos(firstpos, lastpos, followpos); 647 for (int pos = lastpos.NextSet(-1); pos != -1; pos = lastpos.NextSet(pos)) { 648 followpos[pos].Or(firstpos); 649 } 650 } 651 652 public override bool IsNullable { 653 get { return LeftChild.IsNullable; } 654 } 655 656 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)657 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 658 LeftChild.Dump(bb, symbols, positions); 659 bb.Append("+"); 660 } 661 #endif 662 } 663 664 sealed class QmarkNode : InteriorNode { ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)665 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 666 LeftChild.ConstructPos(firstpos, lastpos, followpos); 667 } 668 669 public override bool IsNullable { 670 get { return true; } 671 } 672 673 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)674 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 675 LeftChild.Dump(bb, symbols, positions); 676 bb.Append("?"); 677 } 678 #endif 679 } 680 681 sealed class StarNode : InteriorNode { ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)682 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 683 LeftChild.ConstructPos(firstpos, lastpos, followpos); 684 for (int pos = lastpos.NextSet(-1); pos != -1; pos = lastpos.NextSet(pos)) { 685 followpos[pos].Or(firstpos); 686 } 687 } 688 689 public override bool IsNullable { 690 get { return true; } 691 } 692 693 #if DEBUG Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)694 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 695 LeftChild.Dump(bb, symbols, positions); 696 bb.Append("*"); 697 } 698 #endif 699 } 700 701 #if EXPANDRANGE 702 /// <summary> 703 /// Temporary node to occurance range. Will be expended to a sequence of terminals 704 /// </summary> 705 sealed class RangeNode : InteriorNode { 706 int min; 707 int max; 708 RangeNode(int min, int max)709 public RangeNode(int min, int max) { 710 this.min = min; 711 this.max = max; 712 } 713 714 public int Max { 715 get { return max;} 716 } 717 718 public int Min { 719 get { return min;} 720 } 721 Clone(Positions positions)722 public override SyntaxTreeNode Clone(Positions positions) { 723 // range nodes have to be removed prior to that 724 throw new InvalidOperationException(); 725 } 726 727 /// <summary> 728 /// Expand tree will replace a{min, max} using following algorithm. Bare in mind that this sequence will have at least two leaves 729 /// if min == 0 (max cannot be unbounded) 730 /// a?, ... a? 731 /// \__ __/ 732 /// max 733 /// else 734 /// if max == unbounded 735 /// a, ... a, a* 736 /// \__ __/ 737 /// min 738 /// else 739 /// a, ... a, a?, ... a? 740 /// \__ __/ \__ __/ 741 /// min max - min 742 /// </summary> ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)743 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 744 LeftChild.ExpandTree(this, symbols, positions); 745 SyntaxTreeNode replacementNode = null; 746 if (min == 0) { 747 Debug.Assert(max != int.MaxValue); 748 replacementNode = NewQmark(LeftChild); 749 for (int i = 0; i < max - 1; i ++) { 750 replacementNode = NewSequence(replacementNode, NewQmark(LeftChild.Clone(positions))); 751 } 752 } 753 else { 754 replacementNode = LeftChild; 755 for (int i = 0; i < min - 1; i ++) { 756 replacementNode = NewSequence(replacementNode, LeftChild.Clone(positions)); 757 } 758 if (max == int.MaxValue) { 759 replacementNode = NewSequence(replacementNode, NewStar(LeftChild.Clone(positions))); 760 } 761 else { 762 for (int i = 0; i < max - min; i ++) { 763 replacementNode = NewSequence(replacementNode, NewQmark(LeftChild.Clone(positions))); 764 } 765 } 766 } 767 if (parent.LeftChild == this) { 768 parent.LeftChild = replacementNode; 769 } 770 else { 771 parent.RightChild = replacementNode; 772 } 773 } 774 NewSequence(SyntaxTreeNode leftChild, SyntaxTreeNode rightChild)775 private SyntaxTreeNode NewSequence(SyntaxTreeNode leftChild, SyntaxTreeNode rightChild) { 776 InteriorNode sequence = new SequenceNode(); 777 sequence.LeftChild = leftChild; 778 sequence.RightChild = rightChild; 779 return sequence; 780 } 781 NewStar(SyntaxTreeNode leftChild)782 private SyntaxTreeNode NewStar(SyntaxTreeNode leftChild) { 783 InteriorNode star = new StarNode(); 784 star.LeftChild = leftChild; 785 return star; 786 } 787 NewQmark(SyntaxTreeNode leftChild)788 private SyntaxTreeNode NewQmark(SyntaxTreeNode leftChild) { 789 InteriorNode qmark = new QmarkNode(); 790 qmark.LeftChild = leftChild; 791 return qmark; 792 } 793 ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)794 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 795 throw new InvalidOperationException(); 796 } 797 798 public override bool IsNullable { 799 get { throw new InvalidOperationException(); } 800 } 801 Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions)802 public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 803 LeftChild.Dump(bb, symbols, positions); 804 bb.Append("{" + Convert.ToString(min, NumberFormatInfo.InvariantInfo) + ", " + Convert.ToString(max, NumberFormatInfo.InvariantInfo) + "}"); 805 } 806 807 } 808 #endif 809 810 811 /// <summary> 812 /// Using range node as one of the terminals 813 /// </summary> 814 sealed class LeafRangeNode : LeafNode { 815 decimal min; 816 decimal max; 817 BitSet nextIteration; 818 LeafRangeNode(decimal min, decimal max)819 public LeafRangeNode(decimal min, decimal max) : this(-1, min, max) {} 820 LeafRangeNode(int pos, decimal min, decimal max)821 public LeafRangeNode(int pos, decimal min, decimal max) : base(pos) { 822 this.min = min; 823 this.max = max; 824 } 825 826 public decimal Max { 827 get { return max;} 828 } 829 830 public decimal Min { 831 get { return min;} 832 } 833 834 public BitSet NextIteration { 835 get { 836 return nextIteration; 837 } 838 set { 839 nextIteration = value; 840 } 841 } 842 Clone(Positions positions)843 public override SyntaxTreeNode Clone(Positions positions) { 844 return new LeafRangeNode(this.Pos, this.min, this.max); 845 } 846 847 public override bool IsRangeNode { 848 get { 849 return true; 850 } 851 } 852 ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions)853 public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 854 Debug.Assert(parent is SequenceNode); 855 Debug.Assert(this == parent.RightChild); 856 //change the range node min to zero if left is nullable 857 if (parent.LeftChild.IsNullable) { 858 min = 0; 859 } 860 } 861 } 862 863 #endregion 864 865 #region ContentValidator 866 /// <summary> 867 /// Basic ContentValidator 868 /// </summary> 869 class ContentValidator { 870 XmlSchemaContentType contentType; 871 bool isOpen; //For XDR Content Models or ANY 872 bool isEmptiable; 873 874 public static readonly ContentValidator Empty = new ContentValidator(XmlSchemaContentType.Empty); 875 public static readonly ContentValidator TextOnly = new ContentValidator(XmlSchemaContentType.TextOnly, false, false); 876 public static readonly ContentValidator Mixed = new ContentValidator(XmlSchemaContentType.Mixed); 877 public static readonly ContentValidator Any = new ContentValidator(XmlSchemaContentType.Mixed, true, true); 878 ContentValidator(XmlSchemaContentType contentType)879 public ContentValidator(XmlSchemaContentType contentType) { 880 this.contentType = contentType; 881 this.isEmptiable = true; 882 } 883 ContentValidator(XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)884 protected ContentValidator(XmlSchemaContentType contentType, bool isOpen, bool isEmptiable) { 885 this.contentType = contentType; 886 this.isOpen = isOpen; 887 this.isEmptiable = isEmptiable; 888 } 889 890 public XmlSchemaContentType ContentType { 891 get { return contentType; } 892 } 893 894 public bool PreserveWhitespace { 895 get { return contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Mixed; } 896 } 897 898 public virtual bool IsEmptiable { 899 get { return isEmptiable; } 900 } 901 902 public bool IsOpen { 903 get { 904 if (contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Empty) 905 return false; 906 else 907 return isOpen; 908 } 909 set { isOpen = value; } 910 } 911 InitValidation(ValidationState context)912 public virtual void InitValidation(ValidationState context) { 913 // do nothin' 914 } 915 ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode)916 public virtual object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 917 if (contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Empty) { //Cannot have elements in TextOnly or Empty content 918 context.NeedValidateChildren = false; 919 } 920 errorCode = -1; 921 return null; 922 } 923 CompleteValidation(ValidationState context)924 public virtual bool CompleteValidation(ValidationState context) { 925 return true; 926 } 927 ExpectedElements(ValidationState context, bool isRequiredOnly)928 public virtual ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 929 return null; 930 } 931 ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet)932 public virtual ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet) { 933 return null; 934 } 935 AddParticleToExpected(XmlSchemaParticle p, XmlSchemaSet schemaSet, ArrayList particles)936 public static void AddParticleToExpected(XmlSchemaParticle p, XmlSchemaSet schemaSet, ArrayList particles) { 937 AddParticleToExpected(p, schemaSet, particles, false); 938 } 939 AddParticleToExpected(XmlSchemaParticle p, XmlSchemaSet schemaSet, ArrayList particles, bool global)940 public static void AddParticleToExpected(XmlSchemaParticle p, XmlSchemaSet schemaSet, ArrayList particles, bool global) { 941 if (!particles.Contains(p)) { 942 particles.Add(p); 943 } 944 //Only then it can be head of substitutionGrp, if it is, add its members 945 XmlSchemaElement elem = p as XmlSchemaElement; 946 if (elem != null && (global ||!elem.RefName.IsEmpty)) { 947 XmlSchemaObjectTable substitutionGroups = schemaSet.SubstitutionGroups; 948 XmlSchemaSubstitutionGroup grp = (XmlSchemaSubstitutionGroup)substitutionGroups[elem.QualifiedName]; 949 if (grp != null) { 950 //Grp members wil contain the head as well, so filter head as we added it already 951 for (int i = 0; i < grp.Members.Count; ++i) { 952 XmlSchemaElement member = (XmlSchemaElement)grp.Members[i]; 953 if (!elem.QualifiedName.Equals(member.QualifiedName) && !particles.Contains(member)) { //A member might have been directly present as an element in the content model 954 particles.Add(member); 955 } 956 } 957 } 958 } 959 } 960 } 961 962 sealed class ParticleContentValidator : ContentValidator { 963 SymbolsDictionary symbols; 964 Positions positions; 965 Stack stack; // parsing context 966 SyntaxTreeNode contentNode; // content model points to syntax tree 967 bool isPartial; // whether the closure applies to partial or the whole node that is on top of the stack 968 int minMaxNodesCount; 969 bool enableUpaCheck; 970 ParticleContentValidator(XmlSchemaContentType contentType)971 public ParticleContentValidator(XmlSchemaContentType contentType) : this(contentType, true) { 972 } 973 ParticleContentValidator(XmlSchemaContentType contentType, bool enableUpaCheck)974 public ParticleContentValidator(XmlSchemaContentType contentType, bool enableUpaCheck) : base(contentType) { 975 this.enableUpaCheck = enableUpaCheck; 976 } 977 InitValidation(ValidationState context)978 public override void InitValidation(ValidationState context) { 979 // ParticleContentValidator cannot be used during validation 980 throw new InvalidOperationException(); 981 } 982 ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode)983 public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 984 // ParticleContentValidator cannot be used during validation 985 throw new InvalidOperationException(); 986 } 987 CompleteValidation(ValidationState context)988 public override bool CompleteValidation(ValidationState context) { 989 // ParticleContentValidator cannot be used during validation 990 throw new InvalidOperationException(); 991 } 992 Start()993 public void Start() { 994 symbols = new SymbolsDictionary(); 995 positions = new Positions(); 996 stack = new Stack(); 997 } 998 OpenGroup()999 public void OpenGroup() { 1000 stack.Push(null); 1001 } 1002 CloseGroup()1003 public void CloseGroup() { 1004 SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 1005 if (node == null) { 1006 return; 1007 } 1008 if (stack.Count == 0) { 1009 contentNode = node; 1010 isPartial = false; 1011 } 1012 else { 1013 // some collapsing to do... 1014 InteriorNode inNode = (InteriorNode)stack.Pop(); 1015 if (inNode != null) { 1016 inNode.RightChild = node; 1017 node = inNode; 1018 isPartial = true; 1019 } 1020 else { 1021 isPartial = false; 1022 } 1023 stack.Push(node); 1024 } 1025 } 1026 Exists(XmlQualifiedName name)1027 public bool Exists(XmlQualifiedName name) { 1028 if (symbols.Exists(name)) { 1029 return true; 1030 } 1031 return false; 1032 } 1033 AddName(XmlQualifiedName name, object particle)1034 public void AddName(XmlQualifiedName name, object particle) { 1035 AddLeafNode(new LeafNode(positions.Add(symbols.AddName(name, particle), particle))); 1036 } 1037 AddNamespaceList(NamespaceList namespaceList, object particle)1038 public void AddNamespaceList(NamespaceList namespaceList, object particle) { 1039 symbols.AddNamespaceList(namespaceList, particle, false); 1040 AddLeafNode(new NamespaceListNode(namespaceList, particle)); 1041 } 1042 AddLeafNode(SyntaxTreeNode node)1043 private void AddLeafNode(SyntaxTreeNode node) { 1044 if (stack.Count > 0) { 1045 InteriorNode inNode = (InteriorNode)stack.Pop(); 1046 if (inNode != null) { 1047 inNode.RightChild = node; 1048 node = inNode; 1049 } 1050 } 1051 stack.Push( node ); 1052 isPartial = true; 1053 } 1054 AddChoice()1055 public void AddChoice() { 1056 SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 1057 InteriorNode choice = new ChoiceNode(); 1058 choice.LeftChild = node; 1059 stack.Push(choice); 1060 } 1061 AddSequence()1062 public void AddSequence() { 1063 SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 1064 InteriorNode sequence = new SequenceNode(); 1065 sequence.LeftChild = node; 1066 stack.Push(sequence); 1067 } 1068 AddStar()1069 public void AddStar() { 1070 Closure(new StarNode()); 1071 } 1072 AddPlus()1073 public void AddPlus() { 1074 Closure(new PlusNode()); 1075 } 1076 AddQMark()1077 public void AddQMark() { 1078 Closure(new QmarkNode()); 1079 } 1080 AddLeafRange(decimal min, decimal max)1081 public void AddLeafRange(decimal min, decimal max) { 1082 LeafRangeNode rNode = new LeafRangeNode(min, max); 1083 int pos = positions.Add(-2, rNode); 1084 rNode.Pos = pos; 1085 1086 InteriorNode sequence = new SequenceNode(); 1087 sequence.RightChild = rNode; 1088 Closure(sequence); 1089 minMaxNodesCount++; 1090 } 1091 1092 #if EXPANDRANGE AddRange(int min, int max)1093 public void AddRange(int min, int max) { 1094 Closure(new RangeNode(min, max)); 1095 } 1096 #endif Closure(InteriorNode node)1097 private void Closure(InteriorNode node) { 1098 if (stack.Count > 0) { 1099 SyntaxTreeNode topNode = (SyntaxTreeNode)stack.Pop(); 1100 InteriorNode inNode = topNode as InteriorNode; 1101 if (isPartial && inNode != null) { 1102 // need to reach in and wrap right hand side of element. 1103 // and n remains the same. 1104 node.LeftChild = inNode.RightChild; 1105 inNode.RightChild = node; 1106 } 1107 else { 1108 // wrap terminal or any node 1109 node.LeftChild = topNode; 1110 topNode = node; 1111 } 1112 stack.Push(topNode); 1113 } 1114 else if (contentNode != null) { //If there is content to wrap 1115 // wrap whole content 1116 node.LeftChild = contentNode; 1117 contentNode = node; 1118 } 1119 } 1120 Finish()1121 public ContentValidator Finish() { 1122 return Finish(true); 1123 } 1124 Finish(bool useDFA)1125 public ContentValidator Finish(bool useDFA) { 1126 Debug.Assert(ContentType == XmlSchemaContentType.ElementOnly || ContentType == XmlSchemaContentType.Mixed); 1127 if (contentNode == null) { 1128 if (ContentType == XmlSchemaContentType.Mixed) { 1129 string ctype = IsOpen ? "Any" : "TextOnly"; 1130 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "\t\t\tContentType: " + ctype); 1131 return IsOpen ? ContentValidator.Any : ContentValidator.TextOnly; 1132 } 1133 else { 1134 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "\t\t\tContent: EMPTY"); 1135 Debug.Assert(!IsOpen); 1136 return ContentValidator.Empty; 1137 } 1138 } 1139 1140 #if DEBUG 1141 StringBuilder bb = new StringBuilder(); 1142 contentNode.Dump(bb, symbols, positions); 1143 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "\t\t\tContent : " + bb.ToString()); 1144 #endif 1145 1146 // Add end marker 1147 InteriorNode contentRoot = new SequenceNode(); 1148 contentRoot.LeftChild = contentNode; 1149 LeafNode endMarker = new LeafNode(positions.Add(symbols.AddName(XmlQualifiedName.Empty, null), null)); 1150 contentRoot.RightChild = endMarker; 1151 1152 // Eliminate NamespaceListNode(s) and RangeNode(s) 1153 contentNode.ExpandTree(contentRoot, symbols, positions); 1154 1155 #if DEBUG 1156 bb = new StringBuilder(); 1157 contentRoot.LeftChild.Dump(bb, symbols, positions); 1158 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "\t\t\tExpended: " + bb.ToString()); 1159 #endif 1160 1161 // calculate followpos 1162 int symbolsCount = symbols.Count; 1163 int positionsCount = positions.Count; 1164 BitSet firstpos = new BitSet(positionsCount); 1165 BitSet lastpos = new BitSet(positionsCount); 1166 BitSet[] followpos = new BitSet[positionsCount]; 1167 for (int i = 0; i < positionsCount; i++) { 1168 followpos[i] = new BitSet(positionsCount); 1169 } 1170 contentRoot.ConstructPos(firstpos, lastpos, followpos); 1171 #if DEBUG 1172 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "firstpos, lastpos, followpos"); 1173 SequenceNode.WritePos(firstpos, lastpos, followpos); 1174 #endif 1175 if (minMaxNodesCount > 0) { //If the tree has any terminal range nodes 1176 BitSet positionsWithRangeTerminals; 1177 BitSet[] minMaxFollowPos = CalculateTotalFollowposForRangeNodes(firstpos, followpos, out positionsWithRangeTerminals); 1178 1179 if (enableUpaCheck) { 1180 CheckCMUPAWithLeafRangeNodes(GetApplicableMinMaxFollowPos(firstpos, positionsWithRangeTerminals, minMaxFollowPos)); 1181 for (int i = 0; i < positionsCount; i++) { 1182 CheckCMUPAWithLeafRangeNodes(GetApplicableMinMaxFollowPos(followpos[i], positionsWithRangeTerminals, minMaxFollowPos)); 1183 } 1184 } 1185 return new RangeContentValidator(firstpos, followpos, symbols, positions, endMarker.Pos, this.ContentType, contentRoot.LeftChild.IsNullable, positionsWithRangeTerminals, minMaxNodesCount); 1186 } 1187 else { 1188 int[][] transitionTable = null; 1189 // if each symbol has unique particle we are golden 1190 if (!symbols.IsUpaEnforced) { 1191 if (enableUpaCheck) { 1192 // multiple positions that match the same symbol have different particles, but they never follow the same position 1193 CheckUniqueParticleAttribution(firstpos, followpos); 1194 } 1195 } 1196 else if (useDFA) { 1197 // Can return null if the number of states reaches higher than 8192 / positionsCount 1198 transitionTable = BuildTransitionTable(firstpos, followpos, endMarker.Pos); 1199 } 1200 #if DEBUG 1201 bb = new StringBuilder(); 1202 Dump(bb, followpos, transitionTable); 1203 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, bb.ToString()); 1204 #endif 1205 if (transitionTable != null) { 1206 return new DfaContentValidator(transitionTable, symbols,this.ContentType, this.IsOpen, contentRoot.LeftChild.IsNullable); 1207 } else { 1208 return new NfaContentValidator(firstpos, followpos, symbols, positions, endMarker.Pos, this.ContentType, this.IsOpen, contentRoot.LeftChild.IsNullable); 1209 } 1210 } 1211 } 1212 CalculateTotalFollowposForRangeNodes(BitSet firstpos, BitSet[] followpos, out BitSet posWithRangeTerminals)1213 private BitSet[] CalculateTotalFollowposForRangeNodes(BitSet firstpos, BitSet[] followpos, out BitSet posWithRangeTerminals) { 1214 int positionsCount = positions.Count; //terminals 1215 posWithRangeTerminals = new BitSet(positionsCount); 1216 1217 //Compute followpos for each range node 1218 //For any range node that is surrounded by an outer range node, its follow positions will include those of the outer range node 1219 BitSet[] minmaxFollowPos = new BitSet[minMaxNodesCount]; 1220 int localMinMaxNodesCount = 0; 1221 1222 for (int i = positionsCount - 1; i >= 0; i--) { 1223 Position p = positions[i]; 1224 if (p.symbol == -2) { //P is a LeafRangeNode 1225 LeafRangeNode lrNode = p.particle as LeafRangeNode; 1226 Debug.Assert(lrNode != null); 1227 BitSet tempFollowPos = new BitSet(positionsCount); 1228 tempFollowPos.Clear(); 1229 tempFollowPos.Or(followpos[i]); //Add the followpos of the range node 1230 if (lrNode.Min != lrNode.Max) { //If they are the same, then followpos cannot include the firstpos 1231 tempFollowPos.Or(lrNode.NextIteration); //Add the nextIteration of the range node (this is the firstpos of its parent's leftChild) 1232 } 1233 1234 //For each position in the bitset, if it is a outer range node (pos > i), then add its followpos as well to the current node's followpos 1235 for (int pos = tempFollowPos.NextSet(-1); pos != -1; pos = tempFollowPos.NextSet(pos)) { 1236 if (pos > i) { 1237 Position p1 = positions[pos]; 1238 if (p1.symbol == -2) { 1239 LeafRangeNode lrNode1 = p1.particle as LeafRangeNode; 1240 Debug.Assert(lrNode1 != null); 1241 tempFollowPos.Or(minmaxFollowPos[lrNode1.Pos]); 1242 } 1243 } 1244 } 1245 //set the followpos built to the index in the BitSet[] 1246 minmaxFollowPos[localMinMaxNodesCount] = tempFollowPos; 1247 lrNode.Pos = localMinMaxNodesCount++; 1248 posWithRangeTerminals.Set(i); 1249 } 1250 } 1251 return minmaxFollowPos; 1252 } 1253 CheckCMUPAWithLeafRangeNodes(BitSet curpos)1254 private void CheckCMUPAWithLeafRangeNodes(BitSet curpos) { 1255 object[] symbolMatches = new object[symbols.Count]; 1256 for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 1257 Position currentPosition = positions[pos]; 1258 int symbol = currentPosition.symbol; 1259 if (symbol >= 0) { //its not a range position 1260 if (symbolMatches[symbol] != null) { 1261 throw new UpaException(symbolMatches[symbol], currentPosition.particle); 1262 } 1263 else { 1264 symbolMatches[symbol] = currentPosition.particle; 1265 } 1266 } 1267 } 1268 } 1269 1270 //For each position, this method calculates the additional follows of any range nodes that need to be added to its followpos 1271 //((ab?)2-4)c, Followpos of a is b as well as that of node R(2-4) = c GetApplicableMinMaxFollowPos(BitSet curpos, BitSet posWithRangeTerminals, BitSet[] minmaxFollowPos)1272 private BitSet GetApplicableMinMaxFollowPos(BitSet curpos, BitSet posWithRangeTerminals, BitSet[] minmaxFollowPos) { 1273 if (curpos.Intersects(posWithRangeTerminals)) { 1274 BitSet newSet = new BitSet(positions.Count); //Doing work again 1275 newSet.Or(curpos); 1276 newSet.And(posWithRangeTerminals); 1277 curpos = curpos.Clone(); 1278 for (int pos = newSet.NextSet(-1); pos != -1; pos = newSet.NextSet(pos)) { 1279 LeafRangeNode lrNode = positions[pos].particle as LeafRangeNode; 1280 curpos.Or(minmaxFollowPos[lrNode.Pos]); 1281 } 1282 } 1283 return curpos; 1284 } 1285 CheckUniqueParticleAttribution(BitSet firstpos, BitSet[] followpos)1286 private void CheckUniqueParticleAttribution(BitSet firstpos, BitSet[] followpos) { 1287 CheckUniqueParticleAttribution(firstpos); 1288 for (int i = 0; i < positions.Count; i++) { 1289 CheckUniqueParticleAttribution(followpos[i]); 1290 } 1291 } 1292 CheckUniqueParticleAttribution(BitSet curpos)1293 private void CheckUniqueParticleAttribution(BitSet curpos) { 1294 // particles will be attributed uniquely if the same symbol never poins to two different ones 1295 object[] particles = new object[symbols.Count]; 1296 for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 1297 // if position can follow 1298 int symbol = positions[pos].symbol; 1299 if (particles[symbol] == null) { 1300 // set particle for the symbol 1301 particles[symbol] = positions[pos].particle; 1302 } 1303 else if (particles[symbol] != positions[pos].particle) { 1304 throw new UpaException(particles[symbol], positions[pos].particle); 1305 } 1306 // two different position point to the same symbol and particle - that's OK 1307 } 1308 } 1309 1310 /// <summary> 1311 /// Algorithm 3.5 Construction of a DFA from a regular expression 1312 /// </summary> BuildTransitionTable(BitSet firstpos, BitSet[] followpos, int endMarkerPos)1313 private int[][] BuildTransitionTable(BitSet firstpos, BitSet[] followpos, int endMarkerPos) { 1314 const int TimeConstant = 8192; //(MaxStates * MaxPositions should be a constant) 1315 int positionsCount = positions.Count; 1316 int MaxStatesCount = TimeConstant / positionsCount; 1317 int symbolsCount = symbols.Count; 1318 1319 // transition table (Dtran in the book) 1320 ArrayList transitionTable = new ArrayList(); 1321 1322 // state lookup table (Dstate in the book) 1323 Hashtable stateTable = new Hashtable(); 1324 1325 // Add empty set that would signal an error 1326 stateTable.Add(new BitSet(positionsCount), -1); 1327 1328 // lists unmarked states 1329 Queue unmarked = new Queue(); 1330 1331 // initially, the only unmarked state in Dstates is firstpo(root) 1332 int state = 0; 1333 unmarked.Enqueue(firstpos); 1334 stateTable.Add(firstpos, 0); 1335 transitionTable.Add(new int[symbolsCount + 1]); 1336 1337 // while there is an umnarked state T in Dstates do begin 1338 while (unmarked.Count > 0) { 1339 BitSet statePosSet = (BitSet)unmarked.Dequeue(); // all positions that constitute DFA state 1340 Debug.Assert(state == (int)stateTable[statePosSet]); // just make sure that statePosSet is for correct state 1341 int[] transition = (int[])transitionTable[state]; 1342 if (statePosSet[endMarkerPos]) { 1343 transition[symbolsCount] = 1; // accepting 1344 } 1345 1346 // for each input symbol a do begin 1347 for (int symbol = 0; symbol < symbolsCount; symbol ++) { 1348 // let U be the set of positions that are in followpos(p) 1349 // for some position p in T 1350 // such that the symbol at position p is a 1351 BitSet newset = new BitSet(positionsCount); 1352 for (int pos = statePosSet.NextSet(-1); pos != -1; pos = statePosSet.NextSet(pos)) { 1353 if (symbol == positions[pos].symbol) { 1354 newset.Or(followpos[pos]); 1355 } 1356 } 1357 1358 // if U is not empty and is not in Dstates then 1359 // add U as an unmarked state to Dstates 1360 object lookup = stateTable[newset]; 1361 if (lookup != null) { 1362 transition[symbol] = (int)lookup; 1363 } 1364 else { 1365 // construct new state 1366 int newState = stateTable.Count - 1; 1367 if (newState >= MaxStatesCount) { 1368 return null; 1369 } 1370 unmarked.Enqueue(newset); 1371 stateTable.Add(newset, newState); 1372 transitionTable.Add(new int[symbolsCount + 1]); 1373 transition[symbol] = newState; 1374 } 1375 } 1376 state++; 1377 } 1378 // now convert transition table to array 1379 return (int[][])transitionTable.ToArray(typeof(int[])); 1380 } 1381 1382 #if DEBUG Dump(StringBuilder bb, BitSet[] followpos, int[][] transitionTable)1383 private void Dump(StringBuilder bb, BitSet[] followpos, int[][] transitionTable) { 1384 // Temporary printout 1385 bb.AppendLine("Positions"); 1386 for (int i = 0; i < positions.Count; i ++) { 1387 bb.AppendLine(i + " " + positions[i].symbol.ToString(NumberFormatInfo.InvariantInfo) + " " + symbols.NameOf(positions[i].symbol)); 1388 } 1389 bb.AppendLine("Followpos"); 1390 for (int i = 0; i < positions.Count; i++) { 1391 for (int j = 0; j < positions.Count; j++) { 1392 bb.Append(followpos[i][j] ? "X" : "O"); 1393 } 1394 bb.AppendLine(); 1395 } 1396 if (transitionTable != null) { 1397 // Temporary printout 1398 bb.AppendLine("Transitions"); 1399 for (int i = 0; i < transitionTable.Length; i++) { 1400 for (int j = 0; j < symbols.Count; j++) { 1401 if (transitionTable[i][j] == -1) { 1402 bb.Append(" x "); 1403 } 1404 else { 1405 bb.AppendFormat(" {0:000} ", transitionTable[i][j]); 1406 } 1407 } 1408 bb.AppendLine(transitionTable[i][symbols.Count] == 1 ? "+" : ""); 1409 } 1410 } 1411 } 1412 #endif 1413 } 1414 1415 /// <summary> 1416 /// Deterministic Finite Automata 1417 /// Compilers by Aho, Sethi, Ullman. 1418 /// ISBN 0-201-10088-6, pp. 115, 116, 140 1419 /// </summary> 1420 sealed class DfaContentValidator : ContentValidator { 1421 int[][] transitionTable; 1422 SymbolsDictionary symbols; 1423 1424 /// <summary> 1425 /// Algorithm 3.5 Construction of a DFA from a regular expression 1426 /// </summary> DfaContentValidator( int[][] transitionTable, SymbolsDictionary symbols, XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)1427 internal DfaContentValidator( 1428 int[][] transitionTable, SymbolsDictionary symbols, 1429 XmlSchemaContentType contentType, bool isOpen, bool isEmptiable) : base(contentType, isOpen, isEmptiable) { 1430 this.transitionTable = transitionTable; 1431 this.symbols = symbols; 1432 } 1433 InitValidation(ValidationState context)1434 public override void InitValidation(ValidationState context) { 1435 context.CurrentState.State = 0; 1436 context.HasMatched = transitionTable[0][symbols.Count] > 0; 1437 } 1438 1439 /// <summary> 1440 /// Algorithm 3.1 Simulating a DFA 1441 /// </summary> ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode)1442 public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 1443 int symbol = symbols[name]; 1444 int state = transitionTable[context.CurrentState.State][symbol]; 1445 errorCode = 0; 1446 if (state != -1) { 1447 context.CurrentState.State = state; 1448 context.HasMatched = transitionTable[context.CurrentState.State][symbols.Count] > 0; 1449 return symbols.GetParticle(symbol); // OK 1450 } 1451 if (IsOpen && context.HasMatched) { 1452 // XDR allows any well-formed contents after matched. 1453 return null; 1454 } 1455 context.NeedValidateChildren = false; 1456 errorCode = -1; 1457 return null; // will never be here 1458 } 1459 CompleteValidation(ValidationState context)1460 public override bool CompleteValidation(ValidationState context) { 1461 if (!context.HasMatched) { 1462 return false; 1463 } 1464 return true; 1465 } 1466 ExpectedElements(ValidationState context, bool isRequiredOnly)1467 public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 1468 ArrayList names = null; 1469 int[] transition = transitionTable[context.CurrentState.State]; 1470 if (transition != null) { 1471 for (int i = 0; i < transition.Length - 1; i ++) { 1472 if (transition[i] != -1) { 1473 if (names == null) { 1474 names = new ArrayList(); 1475 } 1476 XmlSchemaParticle p = (XmlSchemaParticle)symbols.GetParticle(i); 1477 if (p == null) { 1478 string s = symbols.NameOf(i); 1479 if (s.Length != 0) { 1480 names.Add(s); 1481 } 1482 } 1483 else { 1484 string s = p.NameString; 1485 if (!names.Contains(s)) { 1486 names.Add(s); 1487 } 1488 } 1489 } 1490 } 1491 } 1492 return names; 1493 } 1494 ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet)1495 public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet) { 1496 ArrayList particles = new ArrayList(); 1497 int[] transition = transitionTable[context.CurrentState.State]; 1498 if (transition != null) { 1499 for (int i = 0; i < transition.Length - 1; i ++) { 1500 if (transition[i] != -1) { 1501 XmlSchemaParticle p = (XmlSchemaParticle)symbols.GetParticle(i); 1502 if (p == null) { 1503 continue; 1504 } 1505 AddParticleToExpected(p, schemaSet, particles); 1506 } 1507 } 1508 } 1509 return particles; 1510 } 1511 } 1512 1513 /// <summary> 1514 /// Nondeterministic Finite Automata 1515 /// Compilers by Aho, Sethi, Ullman. 1516 /// ISBN 0-201-10088-6, pp. 126,140 1517 /// </summary> 1518 sealed class NfaContentValidator : ContentValidator { 1519 BitSet firstpos; 1520 BitSet[] followpos; 1521 SymbolsDictionary symbols; 1522 Positions positions; 1523 int endMarkerPos; 1524 NfaContentValidator( BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)1525 internal NfaContentValidator( 1526 BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, 1527 XmlSchemaContentType contentType, bool isOpen, bool isEmptiable) : base(contentType, isOpen, isEmptiable) { 1528 this.firstpos = firstpos; 1529 this.followpos = followpos; 1530 this.symbols = symbols; 1531 this.positions = positions; 1532 this.endMarkerPos = endMarkerPos; 1533 } 1534 InitValidation(ValidationState context)1535 public override void InitValidation(ValidationState context) { 1536 context.CurPos[0] = firstpos.Clone(); 1537 context.CurPos[1] = new BitSet(firstpos.Count); 1538 context.CurrentState.CurPosIndex = 0; 1539 } 1540 1541 /// <summary> 1542 /// Algorithm 3.4 Simulation of an NFA 1543 /// </summary> ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode)1544 public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 1545 BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 1546 int next = (context.CurrentState.CurPosIndex + 1) % 2; 1547 BitSet nextpos = context.CurPos[next]; 1548 nextpos.Clear(); 1549 int symbol = symbols[name]; 1550 object particle = null; 1551 errorCode = 0; 1552 for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 1553 // if position can follow 1554 if (symbol == positions[pos].symbol) { 1555 nextpos.Or(followpos[pos]); 1556 particle = positions[pos].particle; //Between element and wildcard, element will be in earlier pos than wildcard since we add the element nodes to the list of positions first 1557 break; // and then ExpandTree for the namespace nodes which adds the wildcards to the positions list 1558 } 1559 } 1560 if (!nextpos.IsEmpty) { 1561 context.CurrentState.CurPosIndex = next; 1562 return particle; 1563 } 1564 if (IsOpen && curpos[endMarkerPos]) { 1565 // XDR allows any well-formed contents after matched. 1566 return null; 1567 } 1568 context.NeedValidateChildren = false; 1569 errorCode = -1; 1570 return null; // will never be here 1571 1572 } 1573 1574 #if FINDUPA_PARTICLE FindUPAParticle(ref object originalParticle, object newParticle)1575 private bool FindUPAParticle(ref object originalParticle, object newParticle) { 1576 if (originalParticle == null) { 1577 originalParticle = newParticle; 1578 if (originalParticle is XmlSchemaElement) { //if the first particle is element, then break, otherwise try to find an element 1579 return true; 1580 } 1581 } 1582 else if (newParticle is XmlSchemaElement) { 1583 if (originalParticle is XmlSchemaAny) { //Weak wildcards, element takes precendence over any 1584 originalParticle = newParticle; 1585 return true; 1586 } 1587 } 1588 return false; 1589 } 1590 #endif 1591 CompleteValidation(ValidationState context)1592 public override bool CompleteValidation(ValidationState context) { 1593 if (!context.CurPos[context.CurrentState.CurPosIndex][endMarkerPos]) { 1594 return false; 1595 } 1596 return true; 1597 } 1598 ExpectedElements(ValidationState context, bool isRequiredOnly)1599 public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 1600 ArrayList names = null; 1601 BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 1602 for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 1603 if (names == null) { 1604 names = new ArrayList(); 1605 } 1606 XmlSchemaParticle p = (XmlSchemaParticle)positions[pos].particle; 1607 if (p == null) { 1608 string s = symbols.NameOf(positions[pos].symbol); 1609 if (s.Length != 0) { 1610 names.Add(s); 1611 } 1612 } 1613 else { 1614 string s = p.NameString; 1615 if (!names.Contains(s)) { 1616 names.Add(s); 1617 } 1618 } 1619 } 1620 return names; 1621 } 1622 ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet)1623 public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet) { 1624 ArrayList particles = new ArrayList(); 1625 BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 1626 for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 1627 XmlSchemaParticle p = (XmlSchemaParticle)positions[pos].particle; 1628 if (p == null) { 1629 continue; 1630 } 1631 else { 1632 AddParticleToExpected(p, schemaSet, particles); 1633 } 1634 } 1635 return particles; 1636 } 1637 } 1638 1639 internal struct RangePositionInfo { 1640 public BitSet curpos; 1641 public decimal[] rangeCounters; 1642 } 1643 1644 sealed class RangeContentValidator : ContentValidator { 1645 BitSet firstpos; 1646 BitSet[] followpos; 1647 BitSet positionsWithRangeTerminals; 1648 SymbolsDictionary symbols; 1649 Positions positions; 1650 int minMaxNodesCount; 1651 int endMarkerPos; 1652 RangeContentValidator( BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, XmlSchemaContentType contentType, bool isEmptiable, BitSet positionsWithRangeTerminals, int minmaxNodesCount)1653 internal RangeContentValidator( 1654 BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, XmlSchemaContentType contentType, bool isEmptiable, BitSet positionsWithRangeTerminals, int minmaxNodesCount) : base(contentType, false, isEmptiable) { 1655 this.firstpos = firstpos; 1656 this.followpos = followpos; 1657 this.symbols = symbols; 1658 this.positions = positions; 1659 this.positionsWithRangeTerminals = positionsWithRangeTerminals; 1660 this.minMaxNodesCount = minmaxNodesCount; 1661 this.endMarkerPos = endMarkerPos; 1662 } 1663 InitValidation(ValidationState context)1664 public override void InitValidation(ValidationState context) { 1665 int positionsCount = positions.Count; 1666 List<RangePositionInfo> runningPositions = context.RunningPositions; 1667 if (runningPositions != null) { 1668 Debug.Assert(minMaxNodesCount != 0); 1669 runningPositions.Clear(); 1670 } 1671 else { 1672 runningPositions = new List<RangePositionInfo>(); 1673 context.RunningPositions = runningPositions; 1674 } 1675 RangePositionInfo rposInfo = new RangePositionInfo(); 1676 rposInfo.curpos = firstpos.Clone(); 1677 1678 rposInfo.rangeCounters = new decimal[minMaxNodesCount]; 1679 runningPositions.Add(rposInfo); 1680 context.CurrentState.NumberOfRunningPos = 1; 1681 context.HasMatched = rposInfo.curpos.Get(endMarkerPos); 1682 } 1683 ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode)1684 public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 1685 errorCode = 0; 1686 int symbol = symbols[name]; 1687 bool hasSeenFinalPosition = false; 1688 List<RangePositionInfo> runningPositions = context.RunningPositions; 1689 int matchCount = context.CurrentState.NumberOfRunningPos; 1690 int k = 0; 1691 RangePositionInfo rposInfo; 1692 1693 int pos = -1; 1694 int firstMatchedIndex = -1; 1695 bool matched = false; 1696 1697 #if RANGE_DEBUG 1698 WriteRunningPositions("Current running positions to match", runningPositions, name, matchCount); 1699 #endif 1700 1701 while (k < matchCount) { //we are looking for the first match in the list of bitsets 1702 rposInfo = runningPositions[k]; 1703 BitSet curpos = rposInfo.curpos; 1704 for (int matchpos = curpos.NextSet(-1); matchpos != -1; matchpos = curpos.NextSet(matchpos)) { //In all sets, have to scan all positions because of Disabled UPA possibility 1705 if (symbol == positions[matchpos].symbol) { 1706 pos = matchpos; 1707 if (firstMatchedIndex == -1) { // get the first match for this symbol 1708 firstMatchedIndex = k; 1709 } 1710 matched = true; 1711 break; 1712 } 1713 } 1714 if (matched && positions[pos].particle is XmlSchemaElement) { //We found a match in the list, break at that bitset 1715 break; 1716 } 1717 else { 1718 k++; 1719 } 1720 } 1721 1722 if (k == matchCount && pos != -1) { // we did find a match but that was any and hence continued ahead for element 1723 k = firstMatchedIndex; 1724 } 1725 if (k < matchCount) { //There is a match 1726 if (k != 0) { //If the first bitset itself matched, then no need to remove anything 1727 #if RANGE_DEBUG 1728 WriteRunningPositions("Removing unmatched entries till the first match", runningPositions, XmlQualifiedName.Empty, k); 1729 #endif 1730 runningPositions.RemoveRange(0, k); //Delete entries from 0 to k-1 1731 } 1732 matchCount = matchCount - k; 1733 k = 0; // Since we re-sized the array 1734 while (k < matchCount) { 1735 rposInfo = runningPositions[k]; 1736 matched = rposInfo.curpos.Get(pos); //Look for the bitset that matches the same position as pos 1737 if (matched) { //If match found, get the follow positions of the current matched position 1738 #if RANGE_DEBUG 1739 Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Matched position: " + pos + " "); SequenceNode.WriteBitSet(rposInfo.curpos); 1740 Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Follow pos of Matched position: "); SequenceNode.WriteBitSet(followpos[pos]); 1741 #endif 1742 rposInfo.curpos = followpos[pos]; //Note that we are copying the same counters of the current position to that of the follow position 1743 runningPositions[k] = rposInfo; 1744 k++; 1745 } 1746 else { //Clear the current pos and get another position from the list to start matching 1747 matchCount--; 1748 if (matchCount > 0) { 1749 RangePositionInfo lastrpos = runningPositions[matchCount]; 1750 runningPositions[matchCount] = runningPositions[k]; 1751 runningPositions[k] = lastrpos; 1752 } 1753 } 1754 } 1755 } 1756 else { //There is no match 1757 matchCount = 0; 1758 } 1759 1760 if (matchCount > 0) { 1761 Debug.Assert(minMaxNodesCount > 0); 1762 if (matchCount >= 10000) { 1763 context.TooComplex = true; 1764 matchCount /= 2; 1765 } 1766 #if RANGE_DEBUG 1767 WriteRunningPositions("Matched positions to expand ", runningPositions, name, matchCount); 1768 #endif 1769 1770 for (k = matchCount - 1; k >= 0; k--) { 1771 int j = k; 1772 BitSet currentRunningPosition = runningPositions[k].curpos; 1773 hasSeenFinalPosition = hasSeenFinalPosition || currentRunningPosition.Get(endMarkerPos); //Accepting position reached if the current position BitSet contains the endPosition 1774 while (matchCount < 10000 && currentRunningPosition.Intersects(positionsWithRangeTerminals)) { 1775 //Now might add 2 more positions to followpos 1776 //1. nextIteration of the rangeNode, which is firstpos of its parent's leftChild 1777 //2. Followpos of the range node 1778 1779 BitSet countingPosition = currentRunningPosition.Clone(); 1780 countingPosition.And(positionsWithRangeTerminals); 1781 int cPos = countingPosition.NextSet(-1); //Get the first position where leaf range node appears 1782 LeafRangeNode lrNode = positions[cPos].particle as LeafRangeNode; //For a position with leaf range node, the particle is the node itself 1783 Debug.Assert(lrNode != null); 1784 1785 rposInfo = runningPositions[j]; 1786 if (matchCount + 2 >= runningPositions.Count) { 1787 runningPositions.Add(new RangePositionInfo()); 1788 runningPositions.Add(new RangePositionInfo()); 1789 } 1790 RangePositionInfo newRPosInfo = runningPositions[matchCount]; 1791 if (newRPosInfo.rangeCounters == null) { 1792 newRPosInfo.rangeCounters = new decimal[minMaxNodesCount]; 1793 } 1794 Array.Copy(rposInfo.rangeCounters, 0, newRPosInfo.rangeCounters, 0, rposInfo.rangeCounters.Length); 1795 decimal count = ++newRPosInfo.rangeCounters[lrNode.Pos]; 1796 1797 if (count == lrNode.Max) { 1798 newRPosInfo.curpos = followpos[cPos]; //since max has been reached, Get followposition of range node 1799 newRPosInfo.rangeCounters[lrNode.Pos] = 0; //reset counter 1800 runningPositions[matchCount] = newRPosInfo; 1801 j = matchCount++; 1802 } 1803 else if (count < lrNode.Min) { 1804 newRPosInfo.curpos = lrNode.NextIteration; 1805 runningPositions[matchCount] = newRPosInfo; 1806 matchCount++; 1807 break; 1808 } 1809 else { // min <= count < max 1810 newRPosInfo.curpos = lrNode.NextIteration; //set currentpos to firstpos of node which has the range 1811 runningPositions[matchCount] = newRPosInfo; 1812 j = matchCount + 1; 1813 newRPosInfo = runningPositions[j]; 1814 if (newRPosInfo.rangeCounters == null) { 1815 newRPosInfo.rangeCounters = new decimal[minMaxNodesCount]; 1816 } 1817 Array.Copy(rposInfo.rangeCounters, 0, newRPosInfo.rangeCounters, 0, rposInfo.rangeCounters.Length); 1818 newRPosInfo.curpos = followpos[cPos]; 1819 newRPosInfo.rangeCounters[lrNode.Pos] = 0; 1820 runningPositions[j] = newRPosInfo; 1821 matchCount += 2; 1822 } 1823 currentRunningPosition = runningPositions[j].curpos; 1824 hasSeenFinalPosition = hasSeenFinalPosition || currentRunningPosition.Get(endMarkerPos); 1825 } 1826 } 1827 context.HasMatched = hasSeenFinalPosition; 1828 context.CurrentState.NumberOfRunningPos = matchCount; 1829 return positions[pos].particle; 1830 } //matchcount > 0 1831 errorCode = -1; 1832 context.NeedValidateChildren = false; 1833 return null; 1834 } 1835 1836 #if RANGE_DEBUG WriteRunningPositions(string text, List<RangePositionInfo> runningPositions, XmlQualifiedName name, int length)1837 private void WriteRunningPositions(string text, List<RangePositionInfo> runningPositions, XmlQualifiedName name, int length) { 1838 int counter = 0; 1839 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 1840 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 1841 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, text + name.Name); 1842 while (counter < length) { 1843 BitSet curpos = runningPositions[counter].curpos; 1844 SequenceNode.WriteBitSet(curpos); 1845 for(int rcnt = 0; rcnt < runningPositions[counter].rangeCounters.Length; rcnt++) { 1846 Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "RangeCounter[" + rcnt + "]" + runningPositions[counter].rangeCounters[rcnt] + " "); 1847 } 1848 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 1849 Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 1850 counter++; 1851 } 1852 } 1853 #endif CompleteValidation(ValidationState context)1854 public override bool CompleteValidation(ValidationState context) { 1855 return context.HasMatched; 1856 } 1857 ExpectedElements(ValidationState context, bool isRequiredOnly)1858 public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 1859 ArrayList names = null; 1860 BitSet expectedPos; 1861 if (context.RunningPositions != null) { 1862 List<RangePositionInfo> runningPositions = context.RunningPositions; 1863 expectedPos = new BitSet(positions.Count); 1864 for (int i = context.CurrentState.NumberOfRunningPos - 1; i >=0; i--) { 1865 Debug.Assert(runningPositions[i].curpos != null); 1866 expectedPos.Or(runningPositions[i].curpos); 1867 } 1868 for (int pos = expectedPos.NextSet(-1); pos != -1; pos = expectedPos.NextSet(pos)) { 1869 if (names == null) { 1870 names = new ArrayList(); 1871 } 1872 int symbol = positions[pos].symbol; 1873 if (symbol >= 0) { //non range nodes 1874 XmlSchemaParticle p = positions[pos].particle as XmlSchemaParticle; 1875 if (p == null) { 1876 string s = symbols.NameOf(positions[pos].symbol); 1877 if (s.Length != 0) { 1878 names.Add(s); 1879 } 1880 } 1881 else { 1882 string s = p.NameString; 1883 if (!names.Contains(s)) { 1884 names.Add(s); 1885 } 1886 } 1887 } 1888 } 1889 } 1890 return names; 1891 } 1892 ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet)1893 public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet) { 1894 ArrayList particles = new ArrayList(); 1895 BitSet expectedPos; 1896 if (context.RunningPositions != null) { 1897 List<RangePositionInfo> runningPositions = context.RunningPositions; 1898 expectedPos = new BitSet(positions.Count); 1899 for (int i = context.CurrentState.NumberOfRunningPos - 1; i >=0; i--) { 1900 Debug.Assert(runningPositions[i].curpos != null); 1901 expectedPos.Or(runningPositions[i].curpos); 1902 } 1903 for (int pos = expectedPos.NextSet(-1); pos != -1; pos = expectedPos.NextSet(pos)) { 1904 int symbol = positions[pos].symbol; 1905 if (symbol >= 0) { //non range nodes 1906 XmlSchemaParticle p = positions[pos].particle as XmlSchemaParticle; 1907 if (p == null) { 1908 continue; 1909 } 1910 AddParticleToExpected(p, schemaSet, particles); 1911 } 1912 } 1913 } 1914 return particles; 1915 } 1916 } 1917 1918 sealed class AllElementsContentValidator : ContentValidator { 1919 Hashtable elements; // unique terminal names to positions in Bitset mapping 1920 object[] particles; 1921 BitSet isRequired; // required flags 1922 int countRequired = 0; 1923 AllElementsContentValidator(XmlSchemaContentType contentType, int size, bool isEmptiable)1924 public AllElementsContentValidator(XmlSchemaContentType contentType, int size, bool isEmptiable) : base(contentType, false, isEmptiable) { 1925 elements = new Hashtable(size); 1926 particles = new object[size]; 1927 isRequired = new BitSet(size); 1928 } 1929 AddElement(XmlQualifiedName name, object particle, bool isEmptiable)1930 public bool AddElement(XmlQualifiedName name, object particle, bool isEmptiable) { 1931 if (elements[name] != null) { 1932 return false; 1933 } 1934 int i = elements.Count; 1935 elements.Add(name, i); 1936 particles[i] = particle; 1937 if (!isEmptiable) { 1938 isRequired.Set(i); 1939 countRequired ++; 1940 } 1941 return true; 1942 } 1943 1944 public override bool IsEmptiable { 1945 get { return base.IsEmptiable || countRequired == 0; } 1946 } 1947 InitValidation(ValidationState context)1948 public override void InitValidation(ValidationState context) { 1949 Debug.Assert(elements.Count > 0); 1950 context.AllElementsSet = new BitSet(elements.Count); // 1951 context.CurrentState.AllElementsRequired = -1; // no elements at all 1952 } 1953 ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode)1954 public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 1955 object lookup = elements[name]; 1956 errorCode = 0; 1957 if (lookup == null) { 1958 context.NeedValidateChildren = false; 1959 return null; 1960 } 1961 int index = (int)lookup; 1962 if (context.AllElementsSet[index]) { 1963 errorCode = -2; 1964 return null; 1965 } 1966 if (context.CurrentState.AllElementsRequired == -1) { 1967 context.CurrentState.AllElementsRequired = 0; 1968 } 1969 context.AllElementsSet.Set(index); 1970 if (isRequired[index]) { 1971 context.CurrentState.AllElementsRequired++; 1972 } 1973 return particles[index]; 1974 } 1975 CompleteValidation(ValidationState context)1976 public override bool CompleteValidation(ValidationState context) { 1977 if (context.CurrentState.AllElementsRequired == countRequired || IsEmptiable && context.CurrentState.AllElementsRequired == -1) { 1978 return true; 1979 } 1980 return false; 1981 } 1982 ExpectedElements(ValidationState context, bool isRequiredOnly)1983 public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 1984 ArrayList names = null; 1985 foreach (DictionaryEntry entry in elements) { 1986 if (!context.AllElementsSet[(int)entry.Value] && (!isRequiredOnly || isRequired[(int)entry.Value])) { 1987 if (names == null) { 1988 names = new ArrayList(); 1989 } 1990 names.Add(entry.Key); 1991 } 1992 } 1993 return names; 1994 } 1995 ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet)1996 public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly, XmlSchemaSet schemaSet) { 1997 ArrayList expectedParticles = new ArrayList(); 1998 foreach (DictionaryEntry entry in elements) { 1999 if (!context.AllElementsSet[(int)entry.Value] && (!isRequiredOnly || isRequired[(int)entry.Value])) { 2000 AddParticleToExpected(this.particles[(int)entry.Value] as XmlSchemaParticle, schemaSet, expectedParticles); 2001 } 2002 } 2003 return expectedParticles; 2004 } 2005 } 2006 #endregion 2007 } 2008