mcs/class/Commons.Xml.Relaxng/Commons.Xml.Relaxng.Derivative/RdpPatterns.cs

   1 //
   2 // Commons.Xml.Relaxng.Derivative.RdpPatterns.cs
   3 //
   4 // Author:
   5 //      Atsushi Enomoto <ginga@kit.hi-ho.ne.jp>
   6 //
   7 // 2003 Atsushi Enomoto "No rights reserved."
   8 //
   9 // Copyright (c) 2004 Novell Inc.
  10 // All rights reserved
  11 //
  12
  13 //
  14 // Permission is hereby granted, free of charge, to any person obtaining
  15 // a copy of this software and associated documentation files (the
  16 // "Software"), to deal in the Software without restriction, including
  17 // without limitation the rights to use, copy, modify, merge, publish,
  18 // distribute, sublicense, and/or sell copies of the Software, and to
  19 // permit persons to whom the Software is furnished to do so, subject to
  20 // the following conditions:
  21 //
  22 // The above copyright notice and this permission notice shall be
  23 // included in all copies or substantial portions of the Software.
  24 //
  25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  32 //
  33
  34 using System;
  35 using System.Collections;
  36 using System.Xml;
  37 using Commons.Xml.Relaxng;
  38
  39 using LabelList = System.Collections.Hashtable;
  40
  41
  42 namespace Commons.Xml.Relaxng.Derivative
  43 {
  44         public delegate RdpPattern RdpApplyAfterHandler (RdpPattern p);
  45
  46         // abstract Pattern. Note that in README the classes in this namespace
  47         // is explicitly written as not for public use (and hidden in monodoc
  48         // for now).
  49         public abstract class RdpPattern
  50         {
  51                 internal bool nullableComputed;
  52                 internal bool isNullable;
  53                 Hashtable patternPool;
  54
  55                 internal string debug ()
  56                 {
  57                         return RdpUtil.DebugRdpPattern (this, new Hashtable ());
  58                 }
  59
  60                 public abstract RelaxngPatternType PatternType { get; }
  61
  62                 public abstract RdpContentType ContentType { get; }
  63
  64                 private Hashtable setupTable (Type type, RdpPattern p)
  65                 {
  66                         if (patternPool == null) // could be null for RdpElement etc.
  67                                 patternPool = new Hashtable ();
  68
  69                         Hashtable typePool = (Hashtable) patternPool [type];
  70                         if (typePool == null) {
  71                                 typePool = new Hashtable ();
  72                                 patternPool [type] = typePool;
  73                         }
  74                         Hashtable pTable = (Hashtable) typePool [p];
  75                         if (pTable == null) {
  76                                 pTable = new Hashtable ();
  77                                 typePool [p] = pTable;
  78                         }
  79                         return pTable;
  80                 }
  81
  82                 internal RdpFlip MakeFlip (RdpBinaryFunction func, RdpPattern p)
  83                 {
  84                         if (patternPool == null) // could be null for RdpElement etc.
  85                                 patternPool = new Hashtable ();
  86
  87                         // Though this method takes function argument, all
  88                         // p1 callers have different pattern types, so we don't
  89                         // have to distinguish tables by func.
  90
  91                         Hashtable table = patternPool [func] as Hashtable;
  92                         if (table == null) {
  93                                 table = new Hashtable ();
  94                                 patternPool [func] = table;
  95                         }
  96                         RdpFlip f = table [p] as RdpFlip;
  97                         if (f != null)
  98                                 return f;
  99                         f = new RdpFlip (func, p);
 100                         table [p] = f;
 101                         return f;
 102                 }
 103
 104                 public RdpChoice MakeChoiceLeaf (RdpPattern p)
 105                 {
 106                         if (patternPool == null) // could be null for RdpElement etc.
 107                                 patternPool = new Hashtable ();
 108                         Hashtable leaves = (Hashtable) patternPool [typeof (RdpEmpty)];
 109                         if (leaves == null) {
 110                                 leaves = new Hashtable ();
 111                                 patternPool [typeof (RdpEmpty)] = leaves;
 112                         }
 113                         RdpChoice leaf = leaves [p] as RdpChoice;
 114                         if (leaf == null) {
 115                                 leaf = new RdpChoice (RdpEmpty.Instance, p);
 116                                 leaf.setInternTable (patternPool);
 117                                 leaves [p] = leaf;
 118                         }
 119                         return leaf;
 120                 }
 121
 122                 public RdpPattern MakeChoice (RdpPattern p1, RdpPattern p2)
 123                 {
 124                         if (p1.PatternType == RelaxngPatternType.NotAllowed)
 125                                 return p2;
 126                         if (p2.PatternType == RelaxngPatternType.NotAllowed)
 127                                 return p1;
 128                         if (p1 == p2)
 129                                 return p1;
 130                         // choice-leaves support
 131                         if (p1.PatternType == RelaxngPatternType.Empty)
 132                                 return MakeChoiceLeaf (p2);
 133                         if (p2.PatternType == RelaxngPatternType.Empty)
 134                                 return MakeChoiceLeaf (p1);
 135
 136                         if (p1.GetHashCode () > p2.GetHashCode ()) {
 137                                 RdpPattern tmp = p1;
 138                                 p1 = p2;
 139                                 p2 = tmp;
 140                         }
 141
 142                         Hashtable p1Table = setupTable (typeof (RdpChoice), p1);
 143                         if (p1Table [p2] == null) {
 144                                 RdpChoice c = new RdpChoice (p1, p2);
 145                                 c.setInternTable (this.patternPool);
 146                                 p1Table [p2] = c;
 147                         }
 148                         return (RdpChoice) p1Table [p2];
 149                 }
 150
 151                 public RdpPattern MakeGroup (RdpPattern p1, RdpPattern p2)
 152                 {
 153                         if (p1.PatternType == RelaxngPatternType.Empty)
 154                                 return p2;
 155
 156                         Hashtable p1Table = setupTable (typeof (RdpGroup), p1);
 157                         if (p1Table [p2] == null) {
 158                                 RdpGroup g = new RdpGroup (p1, p2);
 159                                 g.setInternTable (this.patternPool);
 160                                 p1Table [p2] = g;
 161                         }
 162                         return (RdpGroup) p1Table [p2];
 163                 }
 164
 165                 public RdpInterleave MakeInterleave (RdpPattern p1, RdpPattern p2)
 166                 {
 167                         if (p1.GetHashCode () > p2.GetHashCode ()) {
 168                                 RdpPattern tmp = p1;
 169                                 p1 = p2;
 170                                 p2 = tmp;
 171                         }
 172
 173                         Hashtable p1Table = setupTable (typeof (RdpInterleave), p1);
 174                         if (p1Table [p2] == null) {
 175                                 RdpInterleave i = new RdpInterleave (p1, p2);
 176                                 i.setInternTable (this.patternPool);
 177                                 p1Table [p2] = i;
 178                         }
 179                         return (RdpInterleave) p1Table [p2];
 180                 }
 181
 182                 public RdpAfter MakeAfter (RdpPattern p1, RdpPattern p2)
 183                 {
 184                         Hashtable p1Table = setupTable (typeof (RdpAfter), p1);
 185                         if (p1Table [p2] == null) {
 186                                 RdpAfter a = new RdpAfter (p1, p2);
 187                                 a.setInternTable (this.patternPool);
 188                                 p1Table [p2] = a;
 189                         }
 190                         return (RdpAfter) p1Table [p2];
 191                 }
 192
 193                 public RdpOneOrMore MakeOneOrMore (RdpPattern p)
 194                 {
 195                         if (patternPool == null) // could be null for RdpElement etc.
 196                                 patternPool = new Hashtable ();
 197
 198                         Hashtable pTable = (Hashtable) patternPool [typeof (RdpOneOrMore)];
 199                         if (pTable == null) {
 200                                 pTable = new Hashtable ();
 201                                 patternPool [typeof (RdpOneOrMore)] = pTable;
 202                         }
 203                         if (pTable [p] == null) {
 204                                 RdpOneOrMore oom = new RdpOneOrMore (p);
 205                                 oom.setInternTable (patternPool);
 206                                 pTable [p] = oom;
 207                         }
 208                         return (RdpOneOrMore) pTable [p];
 209                 }
 210
 211                 internal void setInternTable (Hashtable ht)
 212                 {
 213                         if (this.patternPool != null)
 214                                 return;
 215                         this.patternPool = ht;
 216
 217                         Hashtable pt = ht [GetType ()] as Hashtable;
 218                         if (pt == null) {
 219                                 pt = new Hashtable ();
 220                                 ht [GetType ()] = pt;
 221                         }
 222
 223                         RdpAbstractSingleContent single =
 224                                 this as RdpAbstractSingleContent;
 225                         if (single != null) {
 226                                 if (pt [single.Child] == null) {
 227                                         pt [single.Child] = this;
 228                                         single.Child.setInternTable (ht);
 229                                 }
 230                                 return;
 231                         }
 232
 233                         RdpAbstractBinary binary =
 234                                 this as RdpAbstractBinary;
 235                         if (binary != null) {
 236                                 Hashtable lTable = setupTable (GetType (), binary.LValue);
 237                                 if (lTable [binary.RValue] == null) {
 238                                         lTable [binary.RValue] = this;
 239                                         binary.LValue.setInternTable (ht);
 240                                         binary.RValue.setInternTable (ht);
 241                                 }
 242                                 return;
 243                         }
 244
 245                         // For rest patterns, only check recursively, without pooling.
 246                         RdpAttribute attr = this as RdpAttribute;
 247                         if (attr != null) {
 248                                 attr.Children.setInternTable (ht);
 249                                 return;
 250                         }
 251                         RdpElement el = this as RdpElement;
 252                         if (el != null) {
 253                                 el.Children.setInternTable (ht);
 254                                 return;
 255                         }
 256                         RdpDataExcept dex= this as RdpDataExcept;
 257                         if (dex != null) {
 258                                 dex.Except.setInternTable (ht);
 259                                 return;
 260                         }
 261
 262                         switch (PatternType) {
 263                         case RelaxngPatternType.Empty:
 264                         case RelaxngPatternType.NotAllowed:
 265                         case RelaxngPatternType.Text:
 266                         case RelaxngPatternType.Data:
 267                         case RelaxngPatternType.Value:
 268                                 return;
 269                         }
 270
 271 #if REPLACE_IN_ADVANCE
 272                         throw new InvalidOperationException ();
 273 #endif
 274                 }
 275
 276                 internal abstract void MarkReachableDefs ();
 277
 278                 internal abstract void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept);
 279
 280                 // This method is to detect text pattern inside interleave child.
 281                 internal abstract bool ContainsText ();
 282
 283                 internal virtual RdpPattern ExpandRef (Hashtable defs)
 284                 {
 285                         return this;
 286                 }
 287
 288                 internal virtual RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 289                 {
 290                         return this;
 291                 }
 292
 293                 public abstract bool Nullable { get; }
 294
 295                 internal virtual bool IsTextValueDependent {
 296                         get { return false; }
 297                 }
 298
 299                 internal virtual bool IsContextDependent {
 300                         get { return false; }
 301                 }
 302
 303                 // fills QName collection
 304                 public void GetLabels (LabelList elements, LabelList attributes)
 305                 {
 306                         GetLabels (elements, attributes, false);
 307                 }
 308
 309                 public abstract void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass);
 310
 311                 internal void AddNameLabel (LabelList names, RdpNameClass nc)
 312                 {
 313                         RdpName name = nc as RdpName;
 314                         if (name != null) {
 315                                 XmlQualifiedName qname = new XmlQualifiedName (
 316                                         name.LocalName, name.NamespaceURI);
 317                                 names [qname] = qname;
 318                                 return;
 319                         }
 320                         RdpNameClassChoice choice = nc as RdpNameClassChoice;
 321                         if (choice != null) {
 322                                 AddNameLabel (names, choice.LValue);
 323                                 AddNameLabel (names, choice.RValue);
 324                                 return;
 325                         }
 326                         // For NsName and AnyName, do nothing.
 327                 }
 328
 329                 #region Derivative
 330                 public virtual RdpPattern TextDeriv (string s, XmlReader reader)
 331                 {
 332                         return RdpNotAllowed.Instance;
 333                 }
 334
 335                 internal virtual RdpPattern TextDeriv (string s, XmlReader reader, MemoizationStore memo)
 336                 {
 337                         return TextDeriv (s, reader);
 338                 }
 339
 340                 internal virtual RdpPattern EmptyTextDeriv (MemoizationStore memo)
 341                 {
 342                         return TextDeriv (String.Empty, null, memo);
 343                 }
 344
 345                 internal virtual RdpPattern TextOnlyDeriv ()
 346                 {
 347                         return this;
 348                 }
 349
 350                 internal virtual RdpPattern TextOnlyDeriv (MemoizationStore store)
 351                 {
 352                         return this;
 353                 }
 354
 355                 internal virtual RdpPattern MixedTextDeriv ()
 356                 {
 357                         return RdpNotAllowed.Instance;
 358                 }
 359
 360                 internal virtual RdpPattern MixedTextDeriv (MemoizationStore memo)
 361                 {
 362                         return RdpNotAllowed.Instance;
 363                 }
 364
 365                 public RdpPattern ListDeriv (string [] list, int index, XmlReader reader)
 366                 {
 367                         return listDerivInternal (list, 0, reader);
 368                 }
 369
 370                 private RdpPattern listDerivInternal (string [] list, int start, XmlReader reader)
 371                 {
 372                         if (list.Length <= start)
 373                                 return this;
 374                         else if (list [start].Length == 0)
 375                                 return listDerivInternal (list, start + 1, reader);
 376                         else
 377                                 return this.TextDeriv (list [start].Trim (RdpUtil.WhitespaceChars), reader).listDerivInternal (list, start + 1, reader);
 378                 }
 379
 380                 // Choice(this, p)
 381                 public virtual RdpPattern Choice (RdpPattern p)
 382                 {
 383                         if (p is RdpNotAllowed)
 384                                 return this;
 385                         else if (this is RdpNotAllowed)
 386                                 return p;
 387                         else
 388                                 return MakeChoice (this, p);
 389                 }
 390
 391                 // Group(this, p)
 392                 public virtual RdpPattern Group (RdpPattern p)
 393                 {
 394                         if (p is RdpNotAllowed || this is RdpNotAllowed)
 395                                 return RdpNotAllowed.Instance;
 396                         else if (p is RdpEmpty)
 397                                 return this;
 398                         else if (this is RdpEmpty)
 399                                 return p;
 400                         else
 401                                 return MakeGroup (this, p);
 402                 }
 403
 404                 // Interleave(this, p)
 405                 public virtual RdpPattern Interleave (RdpPattern p)
 406                 {
 407                         if (p is RdpNotAllowed || this is RdpNotAllowed)
 408                                 return RdpNotAllowed.Instance;
 409                         else if (p is RdpEmpty)
 410                                 return this;
 411                         else if (this is RdpEmpty)
 412                                 return p;
 413                         else
 414                                 return MakeInterleave (this, p);
 415                 }
 416
 417                 // After(this, p)
 418                 public virtual RdpPattern After (RdpPattern p)
 419                 {
 420                         if (this is RdpNotAllowed || p is RdpNotAllowed)
 421                                 return RdpNotAllowed.Instance;
 422                         else
 423                                 return MakeAfter (this, p);
 424                 }
 425
 426
 427                 // applyAfter((f, p1=this), p2)
 428                 public virtual RdpPattern ApplyAfter (RdpApplyAfterHandler h)
 429                 {
 430                         throw new Exception ("INTERNAL ERROR: should not happen. This is " + this);
 431                 }
 432
 433                 // startTagOpenDeriv (this, qname)
 434                 // startTagOpenDeriv _ qn = NotAllowed (default)
 435                 public virtual RdpPattern StartTagOpenDeriv (string name, string ns)
 436                 {
 437                         return RdpNotAllowed.Instance;
 438                 }
 439
 440                 internal virtual RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
 441                 {
 442                         return StartTagOpenDeriv (name, ns);
 443                 }
 444
 445                 // attDeriv(ctx, this, att)
 446                 // attDeriv _ _ _ = NotAllowed
 447                 public virtual RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
 448                 {
 449                         return RdpNotAllowed.Instance;
 450                 }
 451
 452                 public virtual RdpPattern StartAttDeriv (string name, string ns)
 453                 {
 454                         return RdpNotAllowed.Instance;
 455                 }
 456
 457                 internal virtual RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
 458                 {
 459                         return StartAttDeriv (name, ns);
 460                 }
 461
 462                 public virtual RdpPattern EndAttDeriv ()
 463                 {
 464                         return RdpNotAllowed.Instance;
 465                 }
 466
 467                 internal virtual RdpPattern EndAttDeriv (MemoizationStore memo)
 468                 {
 469                         return EndAttDeriv ();
 470                 }
 471
 472                 public bool ValueMatch (string s, XmlReader reader)
 473                 {
 474                         return Nullable && Util.IsWhitespace (s) ||
 475                                 TextDeriv (s, reader).Nullable;
 476                 }
 477
 478                 public virtual RdpPattern StartTagCloseDeriv ()
 479                 {
 480                         return this;
 481                 }
 482
 483                 internal virtual RdpPattern StartTagCloseDeriv (MemoizationStore memo)
 484                 {
 485                         return StartTagCloseDeriv ();
 486                 }
 487
 488                 public RdpPattern OneOrMore ()
 489                 {
 490                         if (PatternType == RelaxngPatternType.NotAllowed)
 491                                 return RdpNotAllowed.Instance;
 492                         else
 493                                 return MakeOneOrMore (this);
 494                 }
 495
 496                 public virtual RdpPattern EndTagDeriv ()
 497                 {
 498                         return RdpNotAllowed.Instance;
 499                 }
 500
 501                 internal virtual RdpPattern EndTagDeriv (MemoizationStore memo)
 502                 {
 503                         return EndTagDeriv ();
 504                 }
 505                 #endregion
 506         }
 507
 508         // Empty
 509         public class RdpEmpty : RdpPattern
 510         {
 511                 public RdpEmpty () {}
 512                 static RdpEmpty ()
 513                 {
 514                         instance = new RdpEmpty ();
 515                 }
 516
 517                 public override bool Nullable {
 518                         get { return true; }
 519                 }
 520
 521                 internal override bool IsTextValueDependent {
 522                         get { return false; }
 523                 }
 524
 525                 internal override bool IsContextDependent {
 526                         get { return false; }
 527                 }
 528
 529                 static RdpEmpty instance;
 530                 public static RdpEmpty Instance {
 531                         get { return instance; }
 532                 }
 533
 534                 public override RelaxngPatternType PatternType {
 535                         get { return RelaxngPatternType.Empty; }
 536                 }
 537
 538                 public override RdpContentType ContentType {
 539                         get { return RdpContentType.Empty; }
 540                 }
 541
 542                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 543                 {
 544                         // do nothing
 545                 }
 546
 547                 internal override void MarkReachableDefs ()
 548                 {
 549                         // do nothing
 550                 }
 551
 552                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 553                 {
 554                         if (dataExcept)
 555                                 throw new RelaxngException ("empty cannot appear under except of a data pattern.");
 556                 }
 557
 558                 internal override bool ContainsText()
 559                 {
 560                         return false;
 561                 }
 562         }
 563
 564         // NotAllowed
 565         public class RdpNotAllowed : RdpPattern
 566         {
 567                 public RdpNotAllowed () {}
 568                 static RdpNotAllowed ()
 569                 {
 570                         instance = new RdpNotAllowed ();
 571                 }
 572
 573                 static RdpNotAllowed instance;
 574                 public static RdpNotAllowed Instance {
 575                         get { return instance; }
 576                 }
 577
 578                 public override bool Nullable {
 579                         get { return false; }
 580                 }
 581
 582                 internal override bool IsTextValueDependent {
 583                         get { return false; }
 584                 }
 585
 586                 internal override bool IsContextDependent {
 587                         get { return false; }
 588                 }
 589
 590                 public override RdpPattern ApplyAfter (RdpApplyAfterHandler h)
 591                 {
 592                         return RdpNotAllowed.Instance;
 593                 }
 594
 595                 public override RelaxngPatternType PatternType {
 596                         get { return RelaxngPatternType.NotAllowed; }
 597                 }
 598
 599                 public override RdpContentType ContentType {
 600                         get { return RdpContentType.Empty; }
 601                 }
 602
 603                 internal override void MarkReachableDefs ()
 604                 {
 605                         // do nothing
 606                 }
 607
 608                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 609                 {
 610                         // do nothing
 611                 }
 612
 613                 internal override bool ContainsText()
 614                 {
 615                         return false;
 616                 }
 617
 618                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 619                 {
 620                         // FIXME: Supposed to clear something here?
 621                 }
 622         }
 623
 624         // Text
 625         public class RdpText : RdpPattern
 626         {
 627                 static RdpText instance;
 628                 public static RdpText Instance {
 629                         get { return instance; }
 630                 }
 631
 632                 public RdpText () {}
 633                 static RdpText ()
 634                 {
 635                         instance = new RdpText ();
 636                 }
 637
 638                 public override bool Nullable {
 639                         get { return true; }
 640                 }
 641
 642                 internal override bool IsTextValueDependent {
 643                         get { return false; }
 644                 }
 645
 646                 internal override bool IsContextDependent {
 647                         get { return false; }
 648                 }
 649
 650                 public override RelaxngPatternType PatternType {
 651                         get { return RelaxngPatternType.Text; }
 652                 }
 653
 654                 public override RdpContentType ContentType {
 655                         get { return RdpContentType.Complex; }
 656                 }
 657
 658                 public override RdpPattern TextDeriv (string s, XmlReader reader)
 659                 {
 660                         return this;
 661                 }
 662
 663                 internal override RdpPattern EmptyTextDeriv (MemoizationStore memo)
 664                 {
 665                         return this;
 666                 }
 667
 668                 internal override RdpPattern MixedTextDeriv ()
 669                 {
 670                         return this;
 671                 }
 672
 673                 internal override RdpPattern MixedTextDeriv (MemoizationStore memo)
 674                 {
 675                         return this;
 676                 }
 677
 678                 internal override void MarkReachableDefs ()
 679                 {
 680                         // do nothing
 681                 }
 682
 683                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 684                 {
 685                         if (list)
 686                                 throw new RelaxngException ("text is not allowed under a list.");
 687                         if (dataExcept)
 688                                 throw new RelaxngException ("text is not allowed under except of a list.");
 689                 }
 690
 691                 internal override bool ContainsText()
 692                 {
 693                         return true;
 694                 }
 695
 696                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 697                 {
 698                         // do nothing
 699                 }
 700         }
 701
 702         // AbstractBinary
 703         public abstract class RdpAbstractBinary : RdpPattern
 704         {
 705                 public RdpAbstractBinary (RdpPattern l, RdpPattern r)
 706                 {
 707                         this.l = l;
 708                         this.r = r;
 709                 }
 710
 711                 RdpPattern l;
 712                 public RdpPattern LValue {
 713                         get { return l; }
 714                         set { l = value; }
 715                 }
 716
 717                 RdpPattern r;
 718                 public RdpPattern RValue {
 719                         get { return r; }
 720                         set { r = value; }
 721                 }
 722
 723                 RdpContentType computedContentType = RdpContentType.Invalid;
 724                 public override RdpContentType ContentType {
 725                         get {
 726                                 if (computedContentType == RdpContentType.Invalid) {
 727                                         if (l.ContentType == RdpContentType.Empty)
 728                                                 computedContentType = r.ContentType;
 729                                         else if (r.ContentType == RdpContentType.Empty)
 730                                                 computedContentType = l.ContentType;
 731                                         else if ((l.ContentType & RdpContentType.Simple) != 0 || ((r.ContentType & RdpContentType.Simple) != 0))
 732                                                 throw new RelaxngException ("The content type of this group is invalid.");
 733                                         else
 734                                                 computedContentType = RdpContentType.Complex;
 735                                 }
 736                                 return computedContentType;
 737                         }
 738                 }
 739
 740                 bool expanded;
 741                 internal override RdpPattern ExpandRef (Hashtable defs)
 742                 {
 743                         if (!expanded) {
 744                                 l = l.ExpandRef (defs);
 745                                 r = r.ExpandRef (defs);
 746                         }
 747                         return this;
 748                 }
 749
 750                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 751                 {
 752                         if (visited.Contains (this))
 753                                 return this;
 754                         visited.Add (this, this);
 755
 756                         if (LValue.PatternType == RelaxngPatternType.NotAllowed ||
 757                                 RValue.PatternType == RelaxngPatternType.NotAllowed) {
 758                                 result = true;
 759                                 return RdpNotAllowed.Instance;
 760                         } else if (LValue.PatternType == RelaxngPatternType.Empty) {
 761                                 result = true;
 762                                 return RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 763                         } else if (RValue.PatternType == RelaxngPatternType.Empty) {
 764                                 result = true;
 765                                 return LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 766                         } else {
 767                                 LValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 768                                 RValue = RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 769                                 return this;
 770                         }
 771                 }
 772
 773                 internal override void MarkReachableDefs ()
 774                 {
 775                         l.MarkReachableDefs ();
 776                         r.MarkReachableDefs ();
 777                 }
 778
 779                 internal override bool ContainsText()
 780                 {
 781                         return l.ContainsText () || r.ContainsText ();
 782                 }
 783
 784                 // 7.3 (group/interleave attribute names) and
 785                 // part of 7.4 (interleave element names)
 786                 // FIXME: Actually it should be done against the correct
 787                 // simplified grammar, expanding all refs.
 788                 internal void CheckNameOverlap (bool checkElements)
 789                 {
 790                         if (RdpUtil.NamesOverlap (LValue, RValue, checkElements))
 791                                 throw new RelaxngException ("Duplicate attributes inside a group or an interleave is not allowed.");
 792                         return;
 793                 }
 794         }
 795
 796         // Choice
 797         public class RdpChoice : RdpAbstractBinary
 798         {
 799                 public RdpChoice (RdpPattern l, RdpPattern r) : base (l, r)
 800                 {
 801                 }
 802
 803                 public override bool Nullable {
 804                         get {
 805                                 if (!nullableComputed) {
 806                                         isNullable =
 807                                                 LValue.Nullable || RValue.Nullable;
 808                                         nullableComputed = true;
 809                                 }
 810                                 return isNullable;
 811                         }
 812                 }
 813
 814                 bool isTextValueDependentComputed;
 815                 bool isTextValueDependent;
 816
 817                 internal override bool IsTextValueDependent {
 818                         get {
 819                                 if (!isTextValueDependentComputed) {
 820                                         isTextValueDependent = LValue.IsTextValueDependent || RValue.IsTextValueDependent;
 821                                         isTextValueDependentComputed = true;
 822                                 }
 823                                 return isTextValueDependent;
 824                         }
 825                 }
 826
 827                 bool isContextDependentComputed;
 828                 bool isContextDependent;
 829
 830                 internal override bool IsContextDependent {
 831                         get {
 832                                 if (!isContextDependentComputed) {
 833                                         isContextDependent = LValue.IsContextDependent || RValue.IsContextDependent;
 834                                         isContextDependentComputed = true;
 835                                 }
 836                                 return isContextDependent;
 837                         }
 838                 }
 839
 840                 public override RelaxngPatternType PatternType {
 841                         get { return RelaxngPatternType.Choice; }
 842                 }
 843
 844                 RdpContentType computedContentType = RdpContentType.Invalid;
 845                 public override RdpContentType ContentType {
 846                         get {
 847                                 if (computedContentType == RdpContentType.Invalid) {
 848                                         if (LValue.ContentType == RdpContentType.Simple ||
 849                                                 RValue.ContentType == RdpContentType.Simple)
 850                                                 computedContentType = RdpContentType.Simple;
 851                                         else
 852                                                 computedContentType = base.ContentType;
 853                                 }
 854                                 return computedContentType;
 855                         }
 856                 }
 857
 858                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 859                 {
 860                         LValue.GetLabels (elements, attributes, collectNameClass);
 861                         RValue.GetLabels (elements, attributes, collectNameClass);
 862                 }
 863
 864
 865                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 866                 {
 867                         if (visited.Contains (this))
 868                                 return this;
 869                         visited.Add (this, this);
 870
 871                         if (LValue.PatternType == RelaxngPatternType.NotAllowed &&
 872                                 RValue.PatternType == RelaxngPatternType.NotAllowed) {
 873                                 result = true;
 874                                 return RdpNotAllowed.Instance;
 875                         } else if (LValue.PatternType == RelaxngPatternType.NotAllowed) {
 876                                 result = true;
 877                                 return RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 878                         } else if (RValue.PatternType == RelaxngPatternType.NotAllowed) {
 879                                 result = true;
 880                                 return LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 881                         } else if (LValue.PatternType == RelaxngPatternType.Empty &&
 882                                 RValue.PatternType == RelaxngPatternType.Empty) {
 883                                 result = true;
 884                                 return RdpEmpty.Instance;
 885                         } else if (RValue.PatternType == RelaxngPatternType.Empty) {
 886                                 result = true;
 887                                 RValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 888                                 LValue = RdpEmpty.Instance;
 889                                 return this;
 890                         } else {
 891                                 LValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 892                                 RValue = RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 893                                 return this;
 894                         }
 895                 }
 896
 897                 public override RdpPattern TextDeriv (string s, XmlReader reader)
 898                 {
 899                         return LValue.TextDeriv (s, reader).Choice (RValue.TextDeriv (s, reader));
 900                 }
 901
 902                 internal override RdpPattern TextDeriv (string s, XmlReader reader, MemoizationStore memo)
 903                 {
 904                         return memo.TextDeriv (LValue, s, reader).Choice (memo.TextDeriv (RValue, s, reader));
 905                 }
 906
 907                 internal override RdpPattern EmptyTextDeriv (MemoizationStore memo)
 908                 {
 909                         return memo.EmptyTextDeriv (LValue)
 910                                 .Choice (memo.EmptyTextDeriv (RValue));
 911                 }
 912
 913                 internal override RdpPattern TextOnlyDeriv ()
 914                 {
 915                         return LValue.TextOnlyDeriv ().Choice (
 916                                 RValue.TextOnlyDeriv ());
 917                 }
 918
 919                 internal override RdpPattern TextOnlyDeriv (MemoizationStore memo)
 920                 {
 921                         return memo.TextOnlyDeriv (LValue).Choice (
 922                                 memo.TextOnlyDeriv (RValue));
 923                 }
 924
 925                 internal override RdpPattern MixedTextDeriv ()
 926                 {
 927                         return LValue.MixedTextDeriv ().Choice (
 928                                 RValue.MixedTextDeriv ());
 929                 }
 930
 931                 internal override RdpPattern MixedTextDeriv (MemoizationStore memo)
 932                 {
 933                         return memo.MixedTextDeriv (LValue).Choice (
 934                                 memo.MixedTextDeriv (RValue));
 935                 }
 936
 937                 public override RdpPattern ApplyAfter (RdpApplyAfterHandler handler)
 938                 {
 939 //                      return handler (LValue).Choice (handler (RValue));
 940                         return LValue.ApplyAfter (handler).Choice (RValue.ApplyAfter (handler));
 941                 }
 942
 943                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
 944                 {
 945 #if UseStatic
 946                         return RdpUtil.Choice (
 947                                 RdpUtil.StartTagOpenDeriv (LValue, qname),
 948                                 RdpUtil.StartTagOpenDeriv (RValue, qname));
 949 #else
 950                         RdpPattern lDeriv = LValue.StartTagOpenDeriv (name, ns);
 951                         return lDeriv.Choice (RValue.StartTagOpenDeriv (name, ns));
 952 #endif
 953                 }
 954
 955                 internal override RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
 956                 {
 957                         RdpPattern lDeriv = memo.StartTagOpenDeriv (LValue, name, ns);
 958                         return lDeriv.Choice (memo.StartTagOpenDeriv (RValue, name, ns));
 959                 }
 960
 961                 // attDeriv cx (Choice p1 p2) att =
 962                 //  choice (attDeriv cx p1 att) (attDeriv cx p2 att)
 963                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
 964                 {
 965                         return LValue.AttDeriv (name, ns, value, reader)
 966                                 .Choice (RValue.AttDeriv (name, ns, value, reader));
 967                 }
 968
 969                 public override RdpPattern StartAttDeriv (string name, string ns)
 970                 {
 971                         RdpPattern lDeriv = LValue.StartAttDeriv (name, ns);
 972                         return lDeriv.Choice (RValue.StartAttDeriv (name, ns));
 973                 }
 974
 975                 internal override RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
 976                 {
 977                         return memo.StartAttDeriv (LValue, name, ns)
 978                                 .Choice (memo.StartAttDeriv (RValue, name, ns));
 979                 }
 980
 981                 public override RdpPattern EndAttDeriv ()
 982                 {
 983                         return LValue.EndAttDeriv ().Choice (RValue.EndAttDeriv ());
 984                 }
 985
 986                 internal override RdpPattern EndAttDeriv (MemoizationStore memo)
 987                 {
 988                         return memo.EndAttDeriv (LValue).Choice (memo.EndAttDeriv (RValue));
 989                 }
 990
 991                 // startTagCloseDeriv (Choice p1 p2) =
 992                 //  choice (startTagCloseDeriv p1) (startTagCloseDeriv p2)
 993                 public override RdpPattern StartTagCloseDeriv ()
 994                 {
 995                         return LValue.StartTagCloseDeriv ()
 996                                 .Choice (RValue.StartTagCloseDeriv ());
 997                 }
 998
 999                 internal override RdpPattern StartTagCloseDeriv (MemoizationStore memo)
1000                 {
1001                         return memo.StartTagCloseDeriv (LValue)
1002                                 .Choice (memo.StartTagCloseDeriv (RValue));
1003                 }
1004
1005                 public override RdpPattern EndTagDeriv ()
1006                 {
1007                         return LValue.EndTagDeriv ().Choice (RValue.EndTagDeriv ());
1008                 }
1009
1010                 internal override RdpPattern EndTagDeriv (MemoizationStore memo)
1011                 {
1012                         return memo.EndTagDeriv (LValue).Choice (memo.EndTagDeriv (RValue));
1013                 }
1014
1015                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1016                 {
1017                         LValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, list, dataExcept);
1018                         RValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, list, dataExcept);
1019                 }
1020         }
1021
1022         // Interleave
1023         public class RdpInterleave : RdpAbstractBinary
1024         {
1025                 public RdpInterleave (RdpPattern l, RdpPattern r) : base (l, r)
1026                 {
1027                 }
1028
1029                 public override bool Nullable {
1030                         get {
1031                                 if (!nullableComputed) {
1032                                         isNullable =
1033                                                 LValue.Nullable && RValue.Nullable;
1034                                         nullableComputed = true;
1035                                 }
1036                                 return isNullable;
1037                         }
1038                 }
1039
1040                 internal override bool IsTextValueDependent {
1041                         get { return LValue.IsTextValueDependent || RValue.IsTextValueDependent; }
1042                 }
1043
1044                 internal override bool IsContextDependent {
1045                         get { return LValue.IsContextDependent || RValue.IsContextDependent; }
1046                 }
1047
1048                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1049                 {
1050                         LValue.GetLabels (elements, attributes, collectNameClass);
1051                         RValue.GetLabels (elements, attributes, collectNameClass);
1052                 }
1053
1054                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1055                 {
1056                         if (visited.Contains (this))
1057                                 return this;
1058                         visited.Add (this, this);
1059
1060                         if (LValue.PatternType == RelaxngPatternType.NotAllowed ||
1061                                 RValue.PatternType == RelaxngPatternType.NotAllowed) {
1062                                 result = true;
1063                                 return RdpNotAllowed.Instance;
1064                         } else {
1065                                 LValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
1066                                 RValue = RValue.ReduceEmptyAndNotAllowed (ref result, visited);
1067                                 return this;
1068                         }
1069                 }
1070
1071                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1072                 {
1073                         return LValue.TextDeriv (s, reader).Interleave (RValue)
1074                                 .Choice (LValue.Interleave (RValue.TextDeriv (s, reader)));
1075                 }
1076
1077                 internal override RdpPattern TextDeriv (string s, XmlReader reader, MemoizationStore memo)
1078                 {
1079                         return memo.TextDeriv (LValue, s, reader).Interleave (RValue)
1080                                 .Choice (LValue.Interleave (memo.TextDeriv (RValue, s, reader)));
1081                 }
1082
1083                 internal override RdpPattern EmptyTextDeriv (MemoizationStore memo)
1084                 {
1085                         return memo.EmptyTextDeriv (LValue).Interleave (RValue)
1086                                 .Choice (LValue.Interleave (memo.EmptyTextDeriv (RValue)));
1087                 }
1088
1089                 internal override RdpPattern TextOnlyDeriv ()
1090                 {
1091                         return LValue.TextOnlyDeriv ().Interleave (
1092                                 RValue.TextOnlyDeriv ());
1093                 }
1094
1095                 internal override RdpPattern TextOnlyDeriv (MemoizationStore memo)
1096                 {
1097                         return memo.TextOnlyDeriv (LValue).Interleave (
1098                                 memo.TextOnlyDeriv (RValue));
1099                 }
1100
1101                 internal override RdpPattern MixedTextDeriv ()
1102                 {
1103                         return LValue.MixedTextDeriv ().Interleave (RValue).Choice (
1104                                 LValue.Interleave (RValue.MixedTextDeriv ()));
1105                 }
1106
1107                 internal override RdpPattern MixedTextDeriv (MemoizationStore memo)
1108                 {
1109                         return memo.MixedTextDeriv (LValue).Interleave (RValue).Choice (
1110                                 LValue.Interleave (memo.MixedTextDeriv (RValue)));
1111                 }
1112
1113                 // => choice (applyAfter (flip interleave p2) (startTagOpenDeriv p1 qn)) (applyAfter (interleave p1) (startTagOpenDeriv p2 qn)
1114                 // => p1.startTagOpenDeriv(qn).applyAfter (flip interleave p2).choice (p2.startTagOpenDeriv(qn).applyAfter (interleave p1) )
1115                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
1116                 {
1117                         RdpPattern handledL = LValue.StartTagOpenDeriv (name, ns);
1118                         RdpPattern handledR = RValue.StartTagOpenDeriv (name, ns);
1119                         RdpFlip flipL = MakeFlip (RdpUtil.InterleaveFunction, RValue);
1120                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
1121                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Interleave));
1122                         return choiceL.Choice (choiceR);
1123                 }
1124
1125                 internal override RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
1126                 {
1127                         RdpPattern handledL = memo.StartTagOpenDeriv (LValue, name, ns);
1128                         RdpPattern handledR = memo.StartTagOpenDeriv (RValue, name, ns);
1129                         RdpFlip flipL = MakeFlip (RdpUtil.InterleaveFunction, RValue);
1130                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
1131                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Interleave));
1132                         return choiceL.Choice (choiceR);
1133                 }
1134
1135                 // attDeriv cx (Interleave p1 p2) att =
1136                 //  choice (interleave (attDeriv cx p1 att) p2)
1137                 //         (interleave p1 (attDeriv cx p2 att))
1138                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1139                 {
1140                         return LValue.AttDeriv (name, ns, value, reader)
1141                                 .Interleave (RValue)
1142                                 .Choice (LValue.Interleave (
1143                                         RValue.AttDeriv (name, ns, value, reader)));
1144                 }
1145
1146                 public override RdpPattern StartAttDeriv (string name, string ns)
1147                 {
1148                         RdpPattern handledL = LValue.StartAttDeriv (name, ns);
1149                         RdpPattern handledR = RValue.StartAttDeriv (name, ns);
1150                         RdpFlip flipL = MakeFlip (RdpUtil.InterleaveFunction, RValue);
1151                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
1152                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Interleave));
1153                         return choiceL.Choice (choiceR);
1154                 }
1155
1156                 internal override RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
1157                 {
1158                         RdpPattern handledL = memo.StartAttDeriv (LValue, name, ns);
1159                         RdpPattern handledR = memo.StartAttDeriv (RValue, name, ns);
1160                         RdpFlip flipL = MakeFlip (RdpUtil.InterleaveFunction, RValue);
1161                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
1162                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Interleave));
1163                         return choiceL.Choice (choiceR);
1164                 }
1165
1166                 // startTagCloseDeriv (Interleave p1 p2) =
1167                 //  interleave (startTagCloseDeriv p1) (startTagCloseDeriv p2)
1168                 public override RdpPattern StartTagCloseDeriv ()
1169                 {
1170                         return LValue.StartTagCloseDeriv ()
1171                                 .Interleave (RValue.StartTagCloseDeriv ());
1172                 }
1173
1174                 internal override RdpPattern StartTagCloseDeriv (MemoizationStore memo)
1175                 {
1176                         return memo.StartTagCloseDeriv (LValue)
1177                                 .Interleave (memo.StartTagCloseDeriv (RValue));
1178                 }
1179
1180                 public override RelaxngPatternType PatternType {
1181                         get { return RelaxngPatternType.Interleave; }
1182                 }
1183
1184                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1185                 {
1186                         if (list)
1187                                 throw new RelaxngException ("interleave is not allowed under a list.");
1188                         if (dataExcept)
1189                                 throw new RelaxngException ("interleave is not allowed under except of a data.");
1190
1191                         // 7.1
1192                         LValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMore, list, dataExcept);
1193                         RValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMore, list, dataExcept);
1194
1195                         // unique name analysis - 7.3 and part of 7.4
1196                         CheckNameOverlap (true);
1197
1198                         // (2) text/text prohibited
1199                         if (LValue.ContainsText () && RValue.ContainsText ())
1200                                 throw new RelaxngException ("Both branches of the interleave contains a text pattern.");
1201                 }
1202         }
1203
1204         // Group
1205         public class RdpGroup : RdpAbstractBinary
1206         {
1207                 public RdpGroup (RdpPattern l, RdpPattern r) : base (l, r)
1208                 {
1209                 }
1210
1211                 public override bool Nullable {
1212                         get {
1213                                 if (!nullableComputed) {
1214                                         isNullable =
1215                                                 LValue.Nullable && RValue.Nullable;
1216                                         nullableComputed = true;
1217                                 }
1218                                 return isNullable;
1219                         }
1220                 }
1221
1222                 internal override bool IsTextValueDependent {
1223                         get { return LValue.IsTextValueDependent || (LValue.Nullable ? RValue.IsTextValueDependent : false); }
1224                 }
1225
1226                 internal override bool IsContextDependent {
1227                         get { return LValue.IsContextDependent || (LValue.Nullable ? RValue.IsContextDependent : false); }
1228                 }
1229
1230                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1231                 {
1232                         LValue.GetLabels (elements, attributes, collectNameClass);
1233                         if (LValue.Nullable)
1234                                 RValue.GetLabels (elements, attributes, collectNameClass);
1235                         else
1236                                 RValue.GetLabels (null, attributes, collectNameClass);
1237                 }
1238
1239                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1240                 {
1241                         RdpPattern p = LValue.TextDeriv (s, reader);
1242                         p = (p.PatternType == RelaxngPatternType.NotAllowed) ?
1243                                 p : p.Group (RValue);
1244                         return LValue.Nullable ?
1245                                 p.Choice (RValue.TextDeriv (s, reader)) : p;
1246                 }
1247
1248                 internal override RdpPattern TextDeriv (string s, XmlReader reader, MemoizationStore memo)
1249                 {
1250                         RdpPattern p = memo.TextDeriv (LValue, s, reader);
1251                         p = (p.PatternType == RelaxngPatternType.NotAllowed) ?
1252                                 p : p.Group (RValue);
1253                         return LValue.Nullable ?
1254                                 p.Choice (memo.TextDeriv (RValue, s, reader)) : p;
1255                 }
1256
1257                 internal override RdpPattern EmptyTextDeriv (MemoizationStore memo)
1258                 {
1259                         RdpPattern p = memo.EmptyTextDeriv (LValue);
1260                         p = p.PatternType == RelaxngPatternType.NotAllowed ?
1261                                 p : p.Group (RValue);
1262                         return LValue.Nullable ?
1263                                 p.Choice (memo.EmptyTextDeriv (RValue)) : p;
1264                 }
1265
1266                 internal override RdpPattern TextOnlyDeriv ()
1267                 {
1268                         RdpPattern p = LValue.TextOnlyDeriv ();
1269                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1270                                 p : p.Group (RValue.TextOnlyDeriv ());
1271                 }
1272
1273                 internal override RdpPattern TextOnlyDeriv (MemoizationStore memo)
1274                 {
1275                         RdpPattern p = memo.TextOnlyDeriv (LValue);
1276                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1277                                 p : p.Group (memo.TextOnlyDeriv (RValue));
1278                 }
1279
1280                 internal override RdpPattern MixedTextDeriv ()
1281                 {
1282                         RdpPattern p = LValue.MixedTextDeriv ().Group (RValue);
1283                         return LValue.Nullable ?
1284                                 p.Choice (RValue.MixedTextDeriv ()) : p;
1285                 }
1286
1287                 internal override RdpPattern MixedTextDeriv (MemoizationStore memo)
1288                 {
1289                         RdpPattern p = memo.MixedTextDeriv (LValue).Group (RValue);
1290                         return LValue.Nullable ?
1291                                 p.Choice (memo.MixedTextDeriv (RValue)) : p;
1292                 }
1293
1294                 // startTagOpenDeriv (Group p1 p2) qn =
1295                 //  let x = applyAfter (flip group p2) (startTagOpenDeriv p1 qn)
1296                 //  in if nullable p1 then
1297                 //       choice x (startTagOpenDeriv p2 qn)
1298                 //     else
1299                 //       x
1300                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
1301                 {
1302                         RdpPattern handled = LValue.StartTagOpenDeriv (name, ns);
1303                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, RValue);
1304                         RdpPattern x = handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1305                         if (LValue.Nullable)
1306                                 return x.Choice (RValue.StartTagOpenDeriv (name, ns));
1307                         else
1308                                 return x;
1309                 }
1310
1311                 internal override RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
1312                 {
1313                         RdpPattern handled = memo.StartTagOpenDeriv (LValue, name, ns);
1314                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, RValue);
1315                         RdpPattern x = handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1316                         if (LValue.Nullable)
1317                                 return x.Choice (memo.StartTagOpenDeriv (RValue, name, ns));
1318                         else
1319                                 return x;
1320                 }
1321
1322                 // attDeriv cx (Group p1 p2) att =
1323                 //  choice (group (attDeriv cx p1 att) p2)
1324                 //         (group p1 (attDeriv cx p2 att))
1325                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1326                 {
1327                         return LValue.AttDeriv (name, ns, value, reader).Group (RValue)
1328                                 .Choice (LValue.Group (
1329                                         RValue.AttDeriv (name, ns, value, reader)));
1330                 }
1331
1332                 // startAttDeriv (group p1 p2) == startAttDeriv (interleave p1 p2)
1333                 public override RdpPattern StartAttDeriv (string name, string ns)
1334                 {
1335                         RdpPattern handledL = LValue.StartAttDeriv (name, ns);
1336                         RdpPattern handledR = RValue.StartAttDeriv (name, ns);
1337                         RdpFlip flipL = MakeFlip (RdpUtil.GroupFunction, RValue);
1338                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
1339                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Group));
1340                         return choiceL.Choice (choiceR);
1341                 }
1342
1343                 internal override RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
1344                 {
1345                         RdpPattern handledL = memo.StartAttDeriv (LValue, name, ns);
1346                         RdpPattern handledR = memo.StartAttDeriv (RValue, name, ns);
1347                         RdpFlip flipL = MakeFlip (RdpUtil.GroupFunction, RValue);
1348                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
1349                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Group));
1350                         return choiceL.Choice (choiceR);
1351                 }
1352
1353                 // startTagCloseDeriv (Group p1 p2) =
1354                 //  group (startTagCloseDeriv p1) (startTagCloseDeriv p2)
1355                 public override RdpPattern StartTagCloseDeriv ()
1356                 {
1357                         RdpPattern p = LValue.StartTagCloseDeriv ();
1358                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1359                                 p : p.Group (RValue.StartTagCloseDeriv ());
1360                 }
1361
1362                 internal override RdpPattern StartTagCloseDeriv (MemoizationStore memo)
1363                 {
1364                         RdpPattern p = memo.StartTagCloseDeriv (LValue);
1365                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1366                                 p : p.Group (memo.StartTagCloseDeriv (RValue));
1367                 }
1368
1369                 public override RelaxngPatternType PatternType {
1370                         get { return RelaxngPatternType.Group; }
1371                 }
1372
1373                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1374                 {
1375                         if (dataExcept)
1376                                 throw new RelaxngException ("interleave is not allowed under except of a data.");
1377
1378                         LValue.CheckConstraints (attribute, oneOrMore, oneOrMore, oneOrMoreInterleave, list, dataExcept);
1379                         RValue.CheckConstraints (attribute, oneOrMore, oneOrMore, oneOrMoreInterleave, list, dataExcept);
1380
1381                         // 7.3
1382                         CheckNameOverlap (false);
1383                 }
1384         }
1385
1386         public abstract class RdpAbstractSingleContent : RdpPattern
1387         {
1388                 RdpPattern child;
1389                 bool isExpanded;
1390
1391                 internal override RdpPattern ExpandRef (Hashtable defs)
1392                 {
1393                         if (!isExpanded)
1394                                 child = child.ExpandRef (defs);
1395                         return this;
1396                 }
1397
1398                 public RdpAbstractSingleContent (RdpPattern p)
1399                 {
1400                         this.child = p;
1401                 }
1402
1403                 public RdpPattern Child {
1404                         get { return child; }
1405                         set { child = value; }
1406                 }
1407
1408                 internal override void MarkReachableDefs ()
1409                 {
1410                         child.MarkReachableDefs ();
1411                 }
1412
1413                 internal override bool ContainsText()
1414                 {
1415                         return child.ContainsText ();
1416                 }
1417         }
1418
1419         // OneOrMore
1420         public class RdpOneOrMore : RdpAbstractSingleContent
1421         {
1422                 public RdpOneOrMore (RdpPattern p) : base (p)
1423                 {
1424                 }
1425
1426                 public override RelaxngPatternType PatternType {
1427                         get { return RelaxngPatternType.OneOrMore; }
1428                 }
1429
1430                 public override RdpContentType ContentType {
1431                         get {
1432                                 if (Child.ContentType == RdpContentType.Simple)
1433                                         throw new RelaxngException ("Invalid content type was found.");
1434                                 return Child.ContentType;
1435                         }
1436                 }
1437
1438                 public override bool Nullable {
1439                         get { return Child.Nullable; }
1440                 }
1441
1442                 internal override bool IsTextValueDependent {
1443                         get { return Child.IsTextValueDependent; }
1444                 }
1445
1446                 internal override bool IsContextDependent {
1447                         get { return Child.IsContextDependent; }
1448                 }
1449
1450                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1451                 {
1452                         Child.GetLabels (elements, attributes, collectNameClass);
1453                 }
1454
1455                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1456                 {
1457                         if (visited.Contains (this))
1458                                 return this;
1459                         visited.Add (this, this);
1460
1461                         if (Child.PatternType == RelaxngPatternType.NotAllowed) {
1462                                 result = true;
1463                                 return RdpNotAllowed.Instance;
1464                         } else if (Child.PatternType == RelaxngPatternType.Empty)
1465                                 return RdpEmpty.Instance;
1466                         else {
1467                                 Child = Child.ReduceEmptyAndNotAllowed (ref result, visited);
1468                                 return this;
1469                         }
1470                 }
1471
1472                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1473                 {
1474                         RdpPattern p = Child.TextDeriv (s, reader);
1475                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1476                                 p : p.Group (this.Choice (RdpEmpty.Instance));
1477                 }
1478
1479                 internal override RdpPattern TextDeriv (string s, XmlReader reader, MemoizationStore memo)
1480                 {
1481                         RdpPattern p = memo.TextDeriv (Child, s, reader);
1482                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1483                                 p : p.Group (this.Choice (RdpEmpty.Instance));
1484                 }
1485
1486                 internal override RdpPattern EmptyTextDeriv (MemoizationStore memo)
1487                 {
1488                         RdpPattern p = memo.EmptyTextDeriv (Child);
1489                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1490                                 p : p.Group (this.Choice (RdpEmpty.Instance));
1491                 }
1492
1493                 internal override RdpPattern TextOnlyDeriv ()
1494                 {
1495                         return Child.TextOnlyDeriv ().OneOrMore ();
1496                 }
1497
1498                 internal override RdpPattern TextOnlyDeriv (MemoizationStore memo)
1499                 {
1500                         return memo.TextOnlyDeriv (Child).OneOrMore ();
1501                 }
1502
1503                 internal override RdpPattern MixedTextDeriv ()
1504                 {
1505                         RdpPattern p = Child.MixedTextDeriv ();
1506                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1507                                 p : p.Group (this.Choice (RdpEmpty.Instance));
1508                 }
1509
1510                 internal override RdpPattern MixedTextDeriv (MemoizationStore memo)
1511                 {
1512                         RdpPattern p = memo.MixedTextDeriv (Child);
1513                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1514                                 p : p.Group (this.Choice (RdpEmpty.Instance));
1515                 }
1516
1517                 // attDeriv cx (OneOrMore p) att =
1518                 //  group (attDeriv cx p att) (choice (OneOrMore p) Empty)
1519                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1520                 {
1521                         RdpPattern p = Child.AttDeriv (name, ns, value, reader);
1522                         return p.PatternType == RelaxngPatternType.NotAllowed ?
1523                                 p : p.Group (Choice (RdpEmpty.Instance));
1524                 }
1525
1526                 // startTagOpenDeriv (OneOrMore p) qn =
1527                 //  applyAfter (flip group (choice (OneOrMore p) Empty))
1528                 //             (startTagOpenDeriv p qn)
1529                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
1530                 {
1531                         RdpPattern rest = RdpEmpty.Instance.Choice (Child.OneOrMore ());
1532                         RdpPattern handled = Child.StartTagOpenDeriv (name, ns);
1533                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, rest);
1534                         return handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1535                 }
1536
1537                 internal override RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
1538                 {
1539                         RdpPattern rest = RdpEmpty.Instance.Choice (Child.OneOrMore ());
1540                         RdpPattern handled = memo.StartTagOpenDeriv (Child, name, ns);
1541                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, rest);
1542                         return handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1543                 }
1544
1545                 public override RdpPattern StartAttDeriv (string name, string ns)
1546                 {
1547                         RdpPattern rest = RdpEmpty.Instance.Choice (Child.OneOrMore ());
1548                         RdpPattern handled = Child.StartAttDeriv (name, ns);
1549                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, rest);
1550                         return handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1551                 }
1552
1553                 internal override RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
1554                 {
1555                         RdpPattern rest = RdpEmpty.Instance.Choice (Child.OneOrMore ());
1556                         RdpPattern handled = memo.StartAttDeriv (Child, name, ns);
1557                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, rest);
1558                         return handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1559                 }
1560
1561                 // startTagCloseDeriv (OneOrMore p) =
1562                 //  oneOrMore (startTagCloseDeriv p)
1563                 public override RdpPattern StartTagCloseDeriv ()
1564                 {
1565 #if UseStatic
1566                         return RdpUtil.OneOrMore (
1567                                 RdpUtil.StartTagCloseDeriv (children));
1568 #else
1569                         return Child.StartTagCloseDeriv ().OneOrMore ();
1570 #endif
1571                 }
1572
1573                 internal override RdpPattern StartTagCloseDeriv (MemoizationStore memo)
1574                 {
1575                         return memo.StartTagCloseDeriv (Child).OneOrMore ();
1576                 }
1577
1578                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1579                 {
1580                         if (dataExcept)
1581                                 throw new RelaxngException ("oneOrMore is not allowed under except of a data.");
1582                         this.Child.CheckConstraints (attribute, true, oneOrMoreGroup, oneOrMoreInterleave, list, dataExcept);
1583                 }
1584         }
1585
1586         // List
1587         public class RdpList : RdpAbstractSingleContent
1588         {
1589                 public RdpList (RdpPattern p) : base (p)
1590                 {
1591                 }
1592
1593                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1594                 {
1595                         if (visited.Contains (this))
1596                                 return this;
1597                         visited.Add (this, this);
1598
1599                         if (Child.PatternType == RelaxngPatternType.NotAllowed) {
1600                                 result = true;
1601                                 return RdpNotAllowed.Instance;
1602                         } else {
1603                                 Child = Child.ReduceEmptyAndNotAllowed (ref result, visited);
1604                                 return this;
1605                         }
1606                 }
1607
1608                 public override bool Nullable {
1609                         get { return false; }
1610                 }
1611
1612                 internal override bool IsTextValueDependent {
1613                         get { return true; }
1614                 }
1615
1616                 internal override bool IsContextDependent {
1617                         get { return Child.IsContextDependent; }
1618                 }
1619
1620                 public override RelaxngPatternType PatternType {
1621                         get { return RelaxngPatternType.List; }
1622                 }
1623
1624                 public override RdpContentType ContentType {
1625                         get { return RdpContentType.Simple; }
1626                 }
1627
1628                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1629                 {
1630                         Child.GetLabels (elements, attributes, collectNameClass);
1631                 }
1632
1633                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1634                 {
1635                         s = Util.NormalizeWhitespace (s);
1636
1637                         RdpPattern p = Child.ListDeriv (s.Split (RdpUtil.WhitespaceChars), 0, reader);
1638                         if (p.Nullable)
1639                                 return RdpEmpty.Instance;
1640                         else
1641                                 return RdpNotAllowed.Instance;
1642                 }
1643
1644                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1645                 {
1646                         if (list)
1647                                 throw new RelaxngException ("list is not allowed uner another list.");
1648                         if (dataExcept)
1649                                 throw new RelaxngException ("list is not allowed under except of a data.");
1650                         this.Child.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, true, dataExcept);
1651                 }
1652         }
1653
1654         // Data
1655         public class RdpData : RdpPattern
1656         {
1657                 public RdpData (RdpDatatype dt)
1658                 {
1659                         this.dt = dt;
1660                 }
1661
1662                 RdpDatatype dt;
1663                 public RdpDatatype Datatype {
1664                         get { return dt; }
1665                 }
1666
1667                 public override bool Nullable {
1668                         get { return false; }
1669                 }
1670
1671                 internal override bool IsTextValueDependent {
1672                         get { return true; }
1673                 }
1674
1675                 internal override bool IsContextDependent {
1676                         get { return dt.IsContextDependent; }
1677                 }
1678
1679                 public override RelaxngPatternType PatternType {
1680                         get { return RelaxngPatternType.Data; }
1681                 }
1682
1683                 public override RdpContentType ContentType {
1684                         get { return RdpContentType.Simple; }
1685                 }
1686
1687                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1688                 {
1689                         // do nothing.
1690                 }
1691
1692                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1693                 {
1694                         if (dt.IsAllowed (s, reader))
1695                                 return RdpEmpty.Instance;
1696                         else
1697                                 return RdpNotAllowed.Instance;
1698                 }
1699
1700                 internal override void MarkReachableDefs ()
1701                 {
1702                         // do nothing
1703                 }
1704
1705                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1706                 {
1707                         // do nothing
1708                 }
1709
1710                 internal override bool ContainsText()
1711                 {
1712                         return false;
1713                 }
1714         }
1715
1716         // DataExcept
1717         public class RdpDataExcept : RdpData
1718         {
1719                 public RdpDataExcept (RdpDatatype dt, RdpPattern except)
1720                         : base (dt)
1721                 {
1722                         this.except = except;
1723                 }
1724
1725                 RdpPattern except;
1726                 public RdpPattern Except {
1727                         get { return except; }
1728                         set { except = value; }
1729                 }
1730
1731                 public override RelaxngPatternType PatternType {
1732                         get { return RelaxngPatternType.DataExcept; }
1733                 }
1734
1735                 public override RdpContentType ContentType {
1736                         get {
1737                                 RdpContentType c = except.ContentType; // conformance required for except pattern.
1738                                 return RdpContentType.Simple;
1739                         }
1740                 }
1741
1742                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1743                 {
1744                         if (visited.Contains (this))
1745                                 return this;
1746                         visited.Add (this, this);
1747
1748                         if (except.PatternType == RelaxngPatternType.NotAllowed) {
1749                                 result = true;
1750                                 return new RdpData (this.Datatype);
1751                         } else {
1752                                 except = except.ReduceEmptyAndNotAllowed (ref result, visited);
1753                                 return this;
1754                         }
1755                 }
1756
1757                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1758                 {
1759                         if (Datatype.IsAllowed (s, reader) && !except.TextDeriv (s, reader).Nullable)
1760                                 return RdpEmpty.Instance;
1761                         else
1762                                 return RdpNotAllowed.Instance;
1763                 }
1764
1765                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1766                 {
1767                         this.except.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, list, true);
1768                 }
1769
1770                 internal override bool ContainsText()
1771                 {
1772                         return except.ContainsText ();
1773                 }
1774         }
1775
1776         // Value
1777         public class RdpValue : RdpPattern
1778         {
1779                 public RdpValue (RdpDatatype dt, string value)
1780                 {
1781                         this.dt = dt;
1782                         this.value = value;
1783                 }
1784
1785                 RdpDatatype dt;
1786                 public RdpDatatype Datatype {
1787                         get { return dt; }
1788                 }
1789
1790                 string value;
1791                 public string Value {
1792                         get { return value; }
1793                 }
1794
1795                 public override bool Nullable {
1796                         get { return false; }
1797                 }
1798
1799                 internal override bool IsTextValueDependent {
1800                         get { return true; }
1801                 }
1802
1803                 internal override bool IsContextDependent {
1804                         get { return dt.IsContextDependent; }
1805                 }
1806
1807                 public override RelaxngPatternType PatternType {
1808                         get { return RelaxngPatternType.Value; }
1809                 }
1810
1811                 public override RdpContentType ContentType {
1812                         get { return RdpContentType.Simple; }
1813                 }
1814
1815                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1816                 {
1817                         // do nothing
1818                 }
1819
1820                 string cachedValue;
1821                 RdpPattern cachedPattern;
1822
1823                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1824                 {
1825                         if (s == cachedValue && !IsContextDependent)
1826                                 return cachedPattern;
1827                         cachedPattern = TextDerivCore (s, reader);
1828                         cachedValue = s;
1829                         return cachedPattern;
1830                 }
1831
1832                 RdpPattern TextDerivCore (string s, XmlReader reader)
1833                 {
1834                         if (dt.IsTypeEqual (value, s, reader))
1835                                 return RdpEmpty.Instance;
1836                         else
1837                                 return RdpNotAllowed.Instance;
1838                 }
1839
1840                 internal override void MarkReachableDefs ()
1841                 {
1842                         // do nothing
1843                 }
1844
1845                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1846                 {
1847                         // nothing to be checked
1848                 }
1849
1850                 internal override bool ContainsText()
1851                 {
1852                         return false;
1853                 }
1854         }
1855
1856         // Attribute
1857         public class RdpAttribute : RdpPattern
1858         {
1859                 public RdpAttribute (RdpNameClass nameClass, RdpPattern p)
1860                 {
1861                         this.nameClass = nameClass;
1862                         this.children = p;
1863                 }
1864
1865                 RdpNameClass nameClass;
1866                 public RdpNameClass NameClass {
1867                         get { return nameClass; }
1868                 }
1869
1870                 RdpPattern children;
1871                 public RdpPattern Children {
1872                         get { return children; }
1873                         set { children = value; }
1874                 }
1875
1876                 public override bool Nullable {
1877                         get { return false; }
1878                 }
1879
1880                 internal override bool IsTextValueDependent {
1881                         get { return false; }
1882                 }
1883
1884                 internal override bool IsContextDependent {
1885                         get { return false; }
1886                 }
1887
1888                 public override RelaxngPatternType PatternType {
1889                         get { return RelaxngPatternType.Attribute; }
1890                 }
1891
1892                 public override RdpContentType ContentType {
1893                         get { return RdpContentType.Empty; }
1894                 }
1895
1896                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1897                 {
1898                         if (attributes != null) {
1899                                 if (collectNameClass)
1900                                         attributes [NameClass] = NameClass;
1901                                 else
1902                                         AddNameLabel (attributes, NameClass);
1903                         }
1904                 }
1905
1906                 bool isExpanded;
1907                 internal override RdpPattern ExpandRef (Hashtable defs)
1908                 {
1909                         if (!isExpanded) {
1910                                 isExpanded = true;
1911                                 children = children.ExpandRef (defs);
1912                         }
1913                         return this;
1914                 }
1915
1916                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1917                 {
1918                         if (visited.Contains (this))
1919                                 return this;
1920                         visited.Add (this, this);
1921
1922                         if (children.PatternType == RelaxngPatternType.NotAllowed) {
1923                                 result = true;
1924                                 return RdpNotAllowed.Instance;
1925                         } else {
1926                                 children = children.ReduceEmptyAndNotAllowed (ref result, visited);
1927                                 return this;
1928                         }
1929                 }
1930
1931                 // attDeriv cx (Attribute nc p) (AttributeNode qn s) =
1932                 //  if contains nc qn && valueMatch cx p s then Empty else NotAllowed
1933                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1934                 {
1935                         // If value is null, then does not check ValueMatch.
1936 #if UseStatic
1937                         if (RdpUtil.Contains (this.nameClass, att.QName)
1938                                 && (value == null || RdpUtil.ValueMatch (ctx, this.children, att.Value)))
1939                                 return RdpEmpty.Instance;
1940                         else
1941                                 return RdpNotAllowed.Instance;
1942 #else
1943                         if (nameClass.Contains (name, ns) &&
1944                                 (value == null || children.ValueMatch (value, reader)))
1945                                 return RdpEmpty.Instance;
1946                         else
1947                                 return RdpNotAllowed.Instance;
1948 #endif
1949                 }
1950
1951                 public override RdpPattern StartAttDeriv (string name, string ns)
1952                 {
1953                         return nameClass.Contains (name, ns) ?
1954                                 children.After (RdpEmpty.Instance) : RdpNotAllowed.Instance;
1955                 }
1956
1957                 internal override RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
1958                 {
1959                         return nameClass.Contains (name, ns) ?
1960                                 children.After (RdpEmpty.Instance) : RdpNotAllowed.Instance;
1961                 }
1962
1963                 // startTagCloseDeriv (Attribute _ _) = NotAllowed
1964                 public override RdpPattern StartTagCloseDeriv ()
1965                 {
1966                         return RdpNotAllowed.Instance;
1967                 }
1968
1969                 internal override RdpPattern StartTagCloseDeriv (MemoizationStore memo)
1970                 {
1971                         return RdpNotAllowed.Instance;
1972                 }
1973
1974                 internal override void MarkReachableDefs ()
1975                 {
1976                         children.MarkReachableDefs ();
1977                 }
1978
1979                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1980                 {
1981                         // 7.1.1 and 7.1.2
1982                         if (attribute || oneOrMoreGroup || oneOrMoreInterleave || list || dataExcept)
1983                                 throw new RelaxngException ("Not allowed attribute occurence was specified in the pattern.");
1984
1985                         // latter part of 7.3
1986                         if (!oneOrMore && NameClass.HasInfiniteName)
1987                                 throw new RelaxngException ("Attributes that has an infinite name class must be repeatable.");
1988
1989                         this.Children.CheckConstraints (true, oneOrMore, false, false, false, false);
1990                 }
1991
1992                 internal override bool ContainsText()
1993                 {
1994                         // This method is to detect text pattern inside interleave child.
1995                         // return children.ContainsText ();
1996                         return false;
1997                 }
1998         }
1999
2000         // Element
2001         public class RdpElement : RdpPattern
2002         {
2003                 public RdpElement (RdpNameClass nameClass, RdpPattern p)
2004                 {
2005                         this.nameClass = nameClass;
2006                         this.children = p;
2007                 }
2008
2009                 RdpNameClass nameClass;
2010                 public RdpNameClass NameClass {
2011                         get { return nameClass; }
2012                 }
2013
2014                 RdpPattern children;
2015                 public RdpPattern Children {
2016                         get { return children; }
2017                         set { children = value; }
2018                 }
2019
2020                 public override bool Nullable {
2021                         get { return false; }
2022                 }
2023
2024                 internal override bool IsTextValueDependent {
2025                         get { return false; }
2026                 }
2027
2028                 internal override bool IsContextDependent {
2029                         get { return false; }
2030                 }
2031
2032                 public override RelaxngPatternType PatternType {
2033                         get { return RelaxngPatternType.Element; }
2034                 }
2035
2036                 bool contentTypeCheckDone;
2037                 public override RdpContentType ContentType {
2038                         get {
2039                                 if (!contentTypeCheckDone) {
2040                                         contentTypeCheckDone = true;
2041                                         RdpContentType ct = children.ContentType; // conformance required.
2042                                 }
2043                                 return RdpContentType.Complex;
2044                         }
2045                 }
2046
2047                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
2048                 {
2049                         if (elements != null) {
2050                                 if (collectNameClass)
2051                                         elements [NameClass] = NameClass;
2052                                 else
2053                                         AddNameLabel (elements, NameClass);
2054                         }
2055                 }
2056
2057
2058                 bool isExpanded;
2059                 short expanding; // FIXME: It is totally not required, but there is
2060                 // some bugs in simplification and without it it causes infinite loop.
2061                 internal override RdpPattern ExpandRef (Hashtable defs)
2062                 {
2063                         if (!isExpanded) {
2064                                 isExpanded = true;
2065                                 if (expanding == 100)
2066                                         throw new RelaxngException (String.Format ("Invalid recursion was found. Name is {0}", nameClass));
2067                                 expanding++;
2068                                 children = children.ExpandRef (defs);
2069                                 expanding--;
2070                         }
2071                         return this;
2072                 }
2073
2074                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
2075                 {
2076                         if (visited.Contains (this))
2077                                 return this;
2078                         visited.Add (this, this);
2079
2080                         children = children.ReduceEmptyAndNotAllowed (ref result, visited);
2081                         return this;
2082                 }
2083
2084                 internal override RdpPattern TextOnlyDeriv ()
2085                 {
2086                         return RdpNotAllowed.Instance;
2087                 }
2088
2089                 internal override RdpPattern TextOnlyDeriv (MemoizationStore memo)
2090                 {
2091                         return RdpNotAllowed.Instance;
2092                 }
2093
2094                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
2095                 {
2096 #if UseStatic
2097                         if (RdpUtil.Contains (this.nameClass, qname))
2098                                 return RdpUtil.After (this.Children, RdpEmpty.Instance);
2099                         else
2100                                 return RdpNotAllowed.Instance;
2101 #else
2102                         return nameClass.Contains (name, ns) ?
2103                                 children.After (RdpEmpty.Instance) :
2104                                 RdpNotAllowed.Instance;
2105 #endif
2106                 }
2107
2108                 internal override RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
2109                 {
2110                         return nameClass.Contains (name, ns) ?
2111                                 children.After (RdpEmpty.Instance) :
2112                                 RdpNotAllowed.Instance;
2113                 }
2114
2115                 internal override void MarkReachableDefs ()
2116                 {
2117                         children.MarkReachableDefs ();
2118                 }
2119
2120                 bool constraintsChecked;
2121                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
2122                 {
2123                         if (constraintsChecked)
2124                                 return;
2125                         constraintsChecked = true;
2126                         if (attribute || list || dataExcept)
2127                                 throw new RelaxngException ("Not allowed element occurence was specified in the pattern.");
2128                         this.Children.CheckConstraints (false, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, false, false);
2129                 }
2130
2131                 internal override bool ContainsText()
2132                 {
2133                         return children.ContainsText ();
2134                 }
2135         }
2136
2137         // After
2138         public class RdpAfter : RdpAbstractBinary
2139         {
2140                 public RdpAfter (RdpPattern l, RdpPattern r) : base (l, r)
2141                 {
2142                 }
2143
2144                 public override bool Nullable {
2145                         get { return false; }
2146                 }
2147
2148                 internal override bool IsTextValueDependent {
2149                         get { return LValue.IsTextValueDependent; }
2150                 }
2151
2152                 internal override bool IsContextDependent {
2153                         get { return LValue.IsContextDependent; }
2154                 }
2155
2156                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
2157                 {
2158                         LValue.GetLabels (elements, attributes, collectNameClass);
2159                 }
2160
2161                 public override RdpPattern TextDeriv (string s, XmlReader reader)
2162                 {
2163                         return LValue.TextDeriv (s, reader).After (RValue);
2164                 }
2165
2166                 internal override RdpPattern TextDeriv (string s, XmlReader reader, MemoizationStore memo)
2167                 {
2168                         return memo.TextDeriv (LValue, s, reader).After (RValue);
2169                 }
2170
2171                 internal override RdpPattern EmptyTextDeriv (MemoizationStore memo)
2172                 {
2173                         return memo.EmptyTextDeriv (LValue).After (RValue);
2174                 }
2175
2176                 internal override RdpPattern TextOnlyDeriv ()
2177                 {
2178                         return LValue.TextOnlyDeriv ().After (RValue);
2179                 }
2180
2181                 internal override RdpPattern TextOnlyDeriv (MemoizationStore memo)
2182                 {
2183                         return memo.TextOnlyDeriv (LValue).After (RValue);
2184                 }
2185
2186                 internal override RdpPattern MixedTextDeriv ()
2187                 {
2188                         return LValue.MixedTextDeriv ().After (RValue);
2189                 }
2190
2191                 internal override RdpPattern MixedTextDeriv (MemoizationStore memo)
2192                 {
2193                         return memo.MixedTextDeriv (LValue).After (RValue);
2194                 }
2195
2196                 // startTagOpenDeriv (After p1 p2) qn =
2197                 //   applyAfter (flip after p2) (startTagOpenDeriv p1 qn)
2198                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
2199                 {
2200                         RdpPattern handled = LValue.StartTagOpenDeriv (name, ns);
2201                         RdpFlip f = MakeFlip (RdpUtil.AfterFunction, RValue);
2202                         return handled.ApplyAfter (new RdpApplyAfterHandler (
2203                                 f.Apply));
2204                 }
2205
2206                 internal override RdpPattern StartTagOpenDeriv (string name, string ns, MemoizationStore memo)
2207                 {
2208                         RdpPattern handled = memo.StartTagOpenDeriv (LValue, name, ns);
2209                         RdpFlip f = MakeFlip (RdpUtil.AfterFunction, RValue);
2210                         return handled.ApplyAfter (new RdpApplyAfterHandler (
2211                                 f.Apply));
2212                 }
2213
2214                 public override RdpPattern ApplyAfter (RdpApplyAfterHandler handler)
2215                 {
2216                         return LValue.After (handler (RValue));
2217                 }
2218
2219                 // attDeriv cx (After p1 p2) att =
2220                 //  after (attDeriv cx p1 att) p2
2221                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
2222                 {
2223                         return LValue.AttDeriv (name, ns, value, reader).After (RValue);
2224                 }
2225
2226                 public override RdpPattern StartAttDeriv (string name, string ns)
2227                 {
2228                         RdpPattern handled = LValue.StartAttDeriv (name, ns);
2229                         RdpFlip f = MakeFlip (RdpUtil.AfterFunction, RValue);
2230                         return handled.ApplyAfter (new RdpApplyAfterHandler (
2231                                 f.Apply));
2232                 }
2233
2234                 internal override RdpPattern StartAttDeriv (string name, string ns, MemoizationStore memo)
2235                 {
2236                         RdpPattern handled = memo.StartAttDeriv (LValue, name, ns);
2237                         RdpFlip f = MakeFlip (RdpUtil.AfterFunction, RValue);
2238                         return handled.ApplyAfter (new RdpApplyAfterHandler (
2239                                 f.Apply));
2240                 }
2241
2242                 public override RdpPattern EndAttDeriv ()
2243                 {
2244                         return LValue.Nullable ? RValue : RdpNotAllowed.Instance;
2245                 }
2246
2247                 public override RdpPattern StartTagCloseDeriv ()
2248                 {
2249                         return LValue.StartTagCloseDeriv ().After (RValue);
2250                 }
2251
2252                 internal override RdpPattern StartTagCloseDeriv (MemoizationStore memo)
2253                 {
2254                         return memo.StartTagCloseDeriv (LValue).After (RValue);
2255                 }
2256
2257                 public override RdpPattern EndTagDeriv ()
2258                 {
2259                         return LValue.Nullable ? RValue : RdpNotAllowed.Instance;
2260                 }
2261
2262                 public override RelaxngPatternType PatternType {
2263                         get { return RelaxngPatternType.After; }
2264                 }
2265
2266                 internal override void MarkReachableDefs ()
2267                 {
2268                         throw new InvalidOperationException ();
2269                 }
2270
2271                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
2272                 {
2273                         throw new InvalidOperationException ();
2274                 }
2275
2276                 internal override bool ContainsText ()
2277                 {
2278                         throw new InvalidOperationException ();
2279                 }
2280         }
2281 }
2282