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
  47         public abstract class RdpPattern
  48         {
  49                 internal bool nullableComputed;
  50                 internal bool isNullable;
  51                 Hashtable patternPool;
  52
  53                 internal string debug ()
  54                 {
  55                         return RdpUtil.DebugRdpPattern (this, new Hashtable ());
  56                 }
  57
  58                 public abstract RelaxngPatternType PatternType { get; }
  59
  60                 public abstract RdpContentType ContentType { get; }
  61
  62                 private Hashtable setupTable (Type type, RdpPattern p)
  63                 {
  64                         if (patternPool == null) // could be null for RdpElement etc.
  65                                 patternPool = new Hashtable ();
  66
  67                         Hashtable typePool = (Hashtable) patternPool [type];
  68                         if (typePool == null) {
  69                                 typePool = new Hashtable ();
  70                                 patternPool [type] = typePool;
  71                         }
  72                         Hashtable pTable = (Hashtable) typePool [p];
  73                         if (pTable == null) {
  74                                 pTable = new Hashtable ();
  75                                 typePool [p] = pTable;
  76                         }
  77                         return pTable;
  78                 }
  79
  80                 internal RdpFlip MakeFlip (RdpBinaryFunction func, RdpPattern p)
  81                 {
  82                         // Though this method takes function argument, all
  83                         // p1 callers have different pattern types, so we don't
  84                         // have to distinguish tables by func.
  85
  86                         Hashtable table = patternPool [func] as Hashtable;
  87                         if (table == null) {
  88                                 table = new Hashtable ();
  89                                 patternPool [func] = table;
  90                         }
  91                         RdpFlip f = table [p] as RdpFlip;
  92                         if (f != null)
  93                                 return f;
  94                         f = new RdpFlip (func, p);
  95                         table [p] = f;
  96                         return f;
  97                 }
  98
  99                 public RdpChoice MakeChoice (RdpPattern p1, RdpPattern p2)
 100                 {
 101                         Hashtable p1Table = setupTable (typeof (RdpChoice), p1);
 102                         if (p1Table [p2] == null) {
 103                                 RdpChoice c = new RdpChoice (p1, p2);
 104                                 c.setInternTable (this.patternPool);
 105                                 p1Table [p2] = c;
 106                         }
 107                         return (RdpChoice) p1Table [p2];
 108                 }
 109
 110                 public RdpPattern MakeGroup (RdpPattern p1, RdpPattern p2)
 111                 {
 112                         Hashtable p1Table = setupTable (typeof (RdpGroup), p1);
 113                         if (p1Table [p2] == null) {
 114                                 RdpGroup g = new RdpGroup (p1, p2);
 115                                 g.setInternTable (this.patternPool);
 116                                 p1Table [p2] = g;
 117                         }
 118                         return (RdpGroup) p1Table [p2];
 119                 }
 120
 121                 public RdpInterleave MakeInterleave (RdpPattern p1, RdpPattern p2)
 122                 {
 123                         Hashtable p1Table = setupTable (typeof (RdpInterleave), p1);
 124                         if (p1Table [p2] == null) {
 125                                 RdpInterleave i = new RdpInterleave (p1, p2);
 126                                 i.setInternTable (this.patternPool);
 127                                 p1Table [p2] = i;
 128                         }
 129                         return (RdpInterleave) p1Table [p2];
 130                 }
 131
 132                 public RdpAfter MakeAfter (RdpPattern p1, RdpPattern p2)
 133                 {
 134                         Hashtable p1Table = setupTable (typeof (RdpAfter), p1);
 135                         if (p1Table [p2] == null) {
 136                                 RdpAfter a = new RdpAfter (p1, p2);
 137                                 a.setInternTable (this.patternPool);
 138                                 p1Table [p2] = a;
 139                         }
 140                         return (RdpAfter) p1Table [p2];
 141                 }
 142
 143                 public RdpOneOrMore MakeOneOrMore (RdpPattern p)
 144                 {
 145                         Hashtable pTable = (Hashtable) patternPool [typeof (RdpOneOrMore)];
 146                         if (pTable == null) {
 147                                 pTable = new Hashtable ();
 148                                 patternPool [typeof (RdpOneOrMore)] = pTable;
 149                         }
 150                         if (pTable [p] == null) {
 151                                 RdpOneOrMore oom = new RdpOneOrMore (p);
 152                                 oom.setInternTable (patternPool);
 153                                 pTable [p] = oom;
 154                         }
 155                         return (RdpOneOrMore) pTable [p];
 156                 }
 157
 158                 internal void setInternTable (Hashtable ht)
 159                 {
 160                         if (this.patternPool != null)
 161                                 return;
 162                         this.patternPool = ht;
 163
 164                         Hashtable pt = ht [GetType ()] as Hashtable;
 165                         if (pt == null) {
 166                                 pt = new Hashtable ();
 167                                 ht [GetType ()] = pt;
 168                         }
 169
 170                         RdpAbstractSingleContent single =
 171                                 this as RdpAbstractSingleContent;
 172                         if (single != null) {
 173                                 if (pt [single.Child] == null) {
 174                                         pt [single.Child] = this;
 175                                         single.Child.setInternTable (ht);
 176                                 }
 177                                 return;
 178                         }
 179
 180                         RdpAbstractBinary binary =
 181                                 this as RdpAbstractBinary;
 182                         if (binary != null) {
 183                                 Hashtable lTable = setupTable (GetType (), binary.LValue);
 184                                 if (lTable [binary.RValue] == null) {
 185                                         lTable [binary.RValue] = this;
 186                                         binary.LValue.setInternTable (ht);
 187                                         binary.RValue.setInternTable (ht);
 188                                 }
 189                                 return;
 190                         }
 191
 192                         // For rest patterns, only check recursively, without pooling.
 193                         RdpAttribute attr = this as RdpAttribute;
 194                         if (attr != null) {
 195                                 attr.Children.setInternTable (ht);
 196                                 return;
 197                         }
 198                         RdpElement el = this as RdpElement;
 199                         if (el != null) {
 200                                 el.Children.setInternTable (ht);
 201                                 return;
 202                         }
 203                         RdpDataExcept dex= this as RdpDataExcept;
 204                         if (dex != null) {
 205                                 dex.Except.setInternTable (ht);
 206                                 return;
 207                         }
 208
 209                         switch (PatternType) {
 210                         case RelaxngPatternType.Empty:
 211                         case RelaxngPatternType.NotAllowed:
 212                         case RelaxngPatternType.Text:
 213                         case RelaxngPatternType.Data:
 214                         case RelaxngPatternType.Value:
 215                                 return;
 216                         }
 217
 218 #if REPLACE_IN_ADVANCE
 219                         throw new InvalidOperationException ();
 220 #endif
 221                 }
 222
 223                 internal abstract void MarkReachableDefs ();
 224
 225                 internal abstract void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept);
 226
 227                 // This method is to detect text pattern inside interleave child.
 228                 internal abstract bool ContainsText ();
 229
 230                 internal virtual RdpPattern ExpandRef (Hashtable defs)
 231                 {
 232                         return this;
 233                 }
 234
 235                 internal virtual RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 236                 {
 237                         return this;
 238                 }
 239
 240                 public abstract bool Nullable { get; }
 241
 242                 // fills QName collection
 243                 public void GetLabels (LabelList elements, LabelList attributes)
 244                 {
 245                         GetLabels (elements, attributes, false);
 246                 }
 247
 248                 public abstract void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass);
 249
 250                 internal void AddNameLabel (LabelList names, RdpNameClass nc)
 251                 {
 252                         RdpName name = nc as RdpName;
 253                         if (name != null) {
 254                                 XmlQualifiedName qname = new XmlQualifiedName (
 255                                         name.LocalName, name.NamespaceURI);
 256                                 names [qname] = qname;
 257                                 return;
 258                         }
 259                         RdpNameClassChoice choice = nc as RdpNameClassChoice;
 260                         if (choice != null) {
 261                                 AddNameLabel (names, choice.LValue);
 262                                 AddNameLabel (names, choice.RValue);
 263                                 return;
 264                         }
 265                         // For NsName and AnyName, do nothing.
 266                 }
 267
 268                 #region Derivative
 269                 public virtual RdpPattern TextDeriv (string s, XmlReader reader)
 270                 {
 271                         // This is an extension to JJC algorithm.
 272                         // Whitespace text are allowed except for Data and Value
 273                         // (their TextDeriv are overridden)
 274                         return Util.IsWhitespace (s) ? this : RdpNotAllowed.Instance;
 275                 }
 276
 277 /*
 278                 public RdpPattern ChildDeriv (RdpChildNode child)
 279                 {
 280                         RdpTextChild tc = child as RdpTextChild;
 281 //                      RdpElementChild ec = child as RdpElementChild;
 282                         if (tc != null) {
 283                                 return TextDeriv (tc.Text);
 284                         } else {
 285                                 // complex stuff;-(
 286                                 return StartTagOpenDeriv (ec.LocalName, ec.NamespaceURI)
 287                                                 .AttsDeriv (ec.Attributes)
 288                                                 .StartTagCloseDeriv ()
 289                                         .ChildrenDeriv (ec.ChildNodes)
 290                                         .EndTagDeriv ();
 291                         }
 292                 }
 293 */
 294
 295                 public RdpPattern ListDeriv (string [] list, int index, XmlReader reader)
 296                 {
 297                         return listDerivInternal (list, 0, reader);
 298                 }
 299
 300                 private RdpPattern listDerivInternal (string [] list, int start, XmlReader reader)
 301                 {
 302                         if (list.Length <= start)
 303                                 return this;
 304                         else
 305                                 return this.TextDeriv (list [start], reader).listDerivInternal (list, start + 1, reader);
 306                 }
 307
 308                 // Choice(this, p)
 309                 public virtual RdpPattern Choice (RdpPattern p)
 310                 {
 311                         if (p is RdpNotAllowed)
 312                                 return this;
 313                         else if (this is RdpNotAllowed)
 314                                 return p;
 315                         else
 316                                 return MakeChoice (this, p);
 317                 }
 318
 319                 // Group(this, p)
 320                 public virtual RdpPattern Group (RdpPattern p)
 321                 {
 322                         if (p is RdpNotAllowed || this is RdpNotAllowed)
 323                                 return RdpNotAllowed.Instance;
 324                         else if (p is RdpEmpty)
 325                                 return this;
 326                         else if (this is RdpEmpty)
 327                                 return p;
 328                         else
 329                                 return MakeGroup (this, p);
 330                 }
 331
 332                 // Interleave(this, p)
 333                 public virtual RdpPattern Interleave (RdpPattern p)
 334                 {
 335                         if (p is RdpNotAllowed || this is RdpNotAllowed)
 336                                 return RdpNotAllowed.Instance;
 337                         else if (p is RdpEmpty)
 338                                 return this;
 339                         else if (this is RdpEmpty)
 340                                 return p;
 341                         else
 342                                 return MakeInterleave (this, p);
 343                 }
 344
 345                 // After(this, p)
 346                 public virtual RdpPattern After (RdpPattern p)
 347                 {
 348                         if (this is RdpNotAllowed || p is RdpNotAllowed)
 349                                 return RdpNotAllowed.Instance;
 350                         else
 351                                 return MakeAfter (this, p);
 352                 }
 353
 354
 355                 // applyAfter((f, p1=this), p2)
 356                 public virtual RdpPattern ApplyAfter (RdpApplyAfterHandler h)
 357                 {
 358                         return RdpNotAllowed.Instance;
 359                 }
 360
 361                 // startTagOpenDeriv (this, qname)
 362                 // startTagOpenDeriv _ qn = NotAllowed (default)
 363                 public virtual RdpPattern StartTagOpenDeriv (string name, string ns)
 364                 {
 365                         return RdpNotAllowed.Instance;
 366                 }
 367
 368                 // attDeriv(ctx, this, att)
 369                 // attDeriv _ _ _ = NotAllowed
 370                 public virtual RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
 371                 {
 372                         return RdpNotAllowed.Instance;
 373                 }
 374
 375                 public bool ValueMatch (string s, XmlReader reader)
 376                 {
 377                         return TextDeriv (s, reader).Nullable;
 378                 }
 379
 380                 public virtual RdpPattern StartTagCloseDeriv ()
 381                 {
 382                         return this;
 383                 }
 384
 385                 /*
 386                 public RdpPattern ChildrenDeriv (RdpChildNodes children)
 387                 {
 388                         return childrenDerivInternal (children, 0);
 389                 }
 390
 391                 RdpPattern childrenDerivInternal (RdpChildNodes children, int start)
 392                 {
 393                         if (children.Count == 0) {
 394                                 // childrenDeriv cx p []
 395                                 RdpChildNodes c = new RdpChildNodes ();
 396                                 c.Add (new RdpTextChild (String.Empty));
 397                                 return ChildrenDeriv (c);
 398                         } else if (children.Count == 1 && children [0] is RdpTextChild) {
 399                                 // childrenDeriv cx p [(TextNode s)]
 400                                 RdpTextChild tc = children [0] as RdpTextChild;
 401                                 RdpPattern p1 = ChildDeriv (tc);
 402                                 return RdpUtil.Whitespace (tc.Text) ?
 403                                         RdpUtil.Choice (this, p1) : p1;
 404                         } else
 405                                 // childrenDeriv cx p children
 406                                 return stripChildrenDerivInternal (children, start);
 407                 }
 408
 409                 RdpPattern stripChildrenDerivInternal (RdpChildNodes children, int start)
 410                 {
 411                         if (children.Count == start)
 412                                 return this;
 413                         else {
 414                                 RdpChildNode firstChild =
 415                                         children [start] as RdpChildNode;
 416                                 RdpPattern p =
 417                                         (firstChild.IsNonWhitespaceText) ?
 418                                         this : ChildDeriv (firstChild);
 419                                 return p.childrenDerivInternal (children, start + 1);
 420                         }
 421                 }
 422                 */
 423
 424                 public RdpPattern OneOrMore ()
 425                 {
 426                         if (PatternType == RelaxngPatternType.NotAllowed)
 427                                 return RdpNotAllowed.Instance;
 428                         else
 429                                 return MakeOneOrMore (this);
 430                 }
 431
 432                 public virtual RdpPattern EndTagDeriv ()
 433                 {
 434                         return RdpNotAllowed.Instance;
 435                 }
 436                 #endregion
 437         }
 438
 439         // Empty
 440         public class RdpEmpty : RdpPattern
 441         {
 442                 public RdpEmpty () {}
 443                 static RdpEmpty ()
 444                 {
 445                         instance = new RdpEmpty ();
 446                 }
 447
 448                 public override bool Nullable {
 449                         get { return true; }
 450                 }
 451
 452                 static RdpEmpty instance;
 453                 public static RdpEmpty Instance {
 454                         get { return instance; }
 455                 }
 456
 457                 public override RelaxngPatternType PatternType {
 458                         get { return RelaxngPatternType.Empty; }
 459                 }
 460
 461                 public override RdpContentType ContentType {
 462                         get { return RdpContentType.Empty; }
 463                 }
 464
 465                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 466                 {
 467                         // do nothing
 468                 }
 469
 470                 internal override void MarkReachableDefs ()
 471                 {
 472                         // do nothing
 473                 }
 474
 475                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 476                 {
 477                         if (dataExcept)
 478                                 throw new RelaxngException ("empty cannot appear under except of a data pattern.");
 479                 }
 480
 481                 internal override bool ContainsText()
 482                 {
 483                         return false;
 484                 }
 485         }
 486
 487         // NotAllowed
 488         public class RdpNotAllowed : RdpPattern
 489         {
 490                 public RdpNotAllowed () {}
 491                 static RdpNotAllowed ()
 492                 {
 493                         instance = new RdpNotAllowed ();
 494                 }
 495
 496                 static RdpNotAllowed instance;
 497                 public static RdpNotAllowed Instance {
 498                         get { return instance; }
 499                 }
 500
 501                 public override bool Nullable {
 502                         get { return false; }
 503                 }
 504
 505                 public override RdpPattern ApplyAfter (RdpApplyAfterHandler h)
 506                 {
 507                         return RdpNotAllowed.Instance;
 508                 }
 509
 510                 public override RelaxngPatternType PatternType {
 511                         get { return RelaxngPatternType.NotAllowed; }
 512                 }
 513
 514                 public override RdpContentType ContentType {
 515                         get { return RdpContentType.Empty; }
 516                 }
 517
 518                 internal override void MarkReachableDefs ()
 519                 {
 520                         // do nothing
 521                 }
 522
 523                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 524                 {
 525                         // do nothing
 526                 }
 527
 528                 internal override bool ContainsText()
 529                 {
 530                         return false;
 531                 }
 532
 533                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 534                 {
 535                         // FIXME: Supposed to clear something here?
 536                 }
 537         }
 538
 539         // Text
 540         public class RdpText : RdpPattern
 541         {
 542                 static RdpText instance;
 543                 public static RdpText Instance {
 544                         get { return instance; }
 545                 }
 546
 547                 public RdpText () {}
 548                 static RdpText ()
 549                 {
 550                         instance = new RdpText ();
 551                 }
 552
 553                 public override bool Nullable {
 554                         get { return true; }
 555                 }
 556
 557                 public override RelaxngPatternType PatternType {
 558                         get { return RelaxngPatternType.Text; }
 559                 }
 560
 561                 public override RdpContentType ContentType {
 562                         get { return RdpContentType.Complex; }
 563                 }
 564
 565                 public override RdpPattern TextDeriv (string s, XmlReader reader)
 566                 {
 567                         return this;
 568                 }
 569
 570                 internal override void MarkReachableDefs ()
 571                 {
 572                         // do nothing
 573                 }
 574
 575                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 576                 {
 577                         if (list)
 578                                 throw new RelaxngException ("text is not allowed under a list.");
 579                         if (dataExcept)
 580                                 throw new RelaxngException ("text is not allowed under except of a list.");
 581                 }
 582
 583                 internal override bool ContainsText()
 584                 {
 585                         return true;
 586                 }
 587
 588                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 589                 {
 590                         // do nothing
 591                 }
 592         }
 593
 594         // AbstractBinary
 595         public abstract class RdpAbstractBinary : RdpPattern
 596         {
 597                 public RdpAbstractBinary (RdpPattern l, RdpPattern r)
 598                 {
 599                         this.l = l;
 600                         this.r = r;
 601                 }
 602
 603                 RdpPattern l;
 604                 public RdpPattern LValue {
 605                         get { return l; }
 606                         set { l = value; }
 607                 }
 608
 609                 RdpPattern r;
 610                 public RdpPattern RValue {
 611                         get { return r; }
 612                         set { r = value; }
 613                 }
 614
 615                 RdpContentType computedContentType = RdpContentType.Invalid;
 616                 public override RdpContentType ContentType {
 617                         get {
 618                                 if (computedContentType == RdpContentType.Invalid) {
 619                                         if (l.ContentType == RdpContentType.Empty)
 620                                                 computedContentType = r.ContentType;
 621                                         else if (r.ContentType == RdpContentType.Empty)
 622                                                 computedContentType = l.ContentType;
 623                                         else if ((l.ContentType & RdpContentType.Simple) != 0 || ((r.ContentType & RdpContentType.Simple) != 0))
 624                                                 throw new RelaxngException ("The content type of this group is invalid.");
 625                                         else
 626                                                 computedContentType = RdpContentType.Complex;
 627                                 }
 628                                 return computedContentType;
 629                         }
 630                 }
 631
 632                 bool expanded;
 633                 internal override RdpPattern ExpandRef (Hashtable defs)
 634                 {
 635                         if (!expanded) {
 636                                 l = l.ExpandRef (defs);
 637                                 r = r.ExpandRef (defs);
 638                         }
 639                         return this;
 640                 }
 641
 642                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 643                 {
 644                         if (visited.Contains (this))
 645                                 return this;
 646                         visited.Add (this, this);
 647
 648                         if (LValue.PatternType == RelaxngPatternType.NotAllowed ||
 649                                 RValue.PatternType == RelaxngPatternType.NotAllowed) {
 650                                 result = true;
 651                                 return RdpNotAllowed.Instance;
 652                         } else if (LValue.PatternType == RelaxngPatternType.Empty) {
 653                                 result = true;
 654                                 return RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 655                         } else if (RValue.PatternType == RelaxngPatternType.Empty) {
 656                                 result = true;
 657                                 return LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 658                         } else {
 659                                 LValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 660                                 RValue = RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 661                                 return this;
 662                         }
 663                 }
 664
 665                 internal override void MarkReachableDefs ()
 666                 {
 667                         l.MarkReachableDefs ();
 668                         r.MarkReachableDefs ();
 669                 }
 670
 671                 internal override bool ContainsText()
 672                 {
 673                         return l.ContainsText () || r.ContainsText ();
 674                 }
 675
 676                 // 7.3 (group/interleave attribute names) and
 677                 // part of 7.4 (interleave element names)
 678                 // FIXME: Actually it should be done against the correct
 679                 // simplified grammar, expanding all refs.
 680                 internal void CheckNameOverlap (bool checkElements)
 681                 {
 682                         if (RdpUtil.NamesOverlap (LValue, RValue, checkElements))
 683                                 throw new RelaxngException ("Duplicate attributes inside a group or an interleave is not allowed.");
 684                         return;
 685                 }
 686         }
 687
 688         // Choice
 689         public class RdpChoice : RdpAbstractBinary
 690         {
 691                 public RdpChoice (RdpPattern l, RdpPattern r) : base (l, r)
 692                 {
 693                 }
 694
 695                 public override bool Nullable {
 696                         get {
 697                                 if (!nullableComputed) {
 698                                         isNullable =
 699                                                 LValue.Nullable || RValue.Nullable;
 700                                         nullableComputed = true;
 701                                 }
 702                                 return isNullable;
 703                         }
 704                 }
 705
 706                 public override RelaxngPatternType PatternType {
 707                         get { return RelaxngPatternType.Choice; }
 708                 }
 709
 710                 RdpContentType computedContentType = RdpContentType.Invalid;
 711                 public override RdpContentType ContentType {
 712                         get {
 713                                 if (computedContentType == RdpContentType.Invalid) {
 714                                         if (LValue.ContentType == RdpContentType.Simple ||
 715                                                 RValue.ContentType == RdpContentType.Simple)
 716                                                 computedContentType = RdpContentType.Simple;
 717                                         else
 718                                                 computedContentType = base.ContentType;
 719                                 }
 720                                 return computedContentType;
 721                         }
 722                 }
 723
 724                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 725                 {
 726                         LValue.GetLabels (elements, attributes, collectNameClass);
 727                         RValue.GetLabels (elements, attributes, collectNameClass);
 728                 }
 729
 730
 731                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 732                 {
 733                         if (visited.Contains (this))
 734                                 return this;
 735                         visited.Add (this, this);
 736
 737                         if (LValue.PatternType == RelaxngPatternType.NotAllowed &&
 738                                 RValue.PatternType == RelaxngPatternType.NotAllowed) {
 739                                 result = true;
 740                                 return RdpNotAllowed.Instance;
 741                         } else if (LValue.PatternType == RelaxngPatternType.NotAllowed) {
 742                                 result = true;
 743                                 return RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 744                         } else if (RValue.PatternType == RelaxngPatternType.NotAllowed) {
 745                                 result = true;
 746                                 return LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 747                         } else if (LValue.PatternType == RelaxngPatternType.Empty &&
 748                                 RValue.PatternType == RelaxngPatternType.Empty) {
 749                                 result = true;
 750                                 return RdpEmpty.Instance;
 751                         } else if (RValue.PatternType == RelaxngPatternType.Empty) {
 752                                 result = true;
 753                                 RValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 754                                 LValue = RdpEmpty.Instance;
 755                                 return this;
 756                         } else {
 757                                 LValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 758                                 RValue = RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 759                                 return this;
 760                         }
 761                 }
 762
 763                 public override RdpPattern TextDeriv (string s, XmlReader reader)
 764                 {
 765                         return LValue.TextDeriv (s, reader).Choice (RValue.TextDeriv (s, reader));
 766                 }
 767
 768                 public override RdpPattern ApplyAfter (RdpApplyAfterHandler handler)
 769                 {
 770 //                      return handler (LValue).Choice (handler (RValue));
 771                         return LValue.ApplyAfter (handler).Choice (RValue.ApplyAfter (handler));
 772                 }
 773
 774                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
 775                 {
 776 #if UseStatic
 777                         return RdpUtil.Choice (
 778                                 RdpUtil.StartTagOpenDeriv (LValue, qname),
 779                                 RdpUtil.StartTagOpenDeriv (RValue, qname));
 780 #else
 781                         RdpPattern lDeriv = LValue.StartTagOpenDeriv (name, ns);
 782                         return lDeriv.Choice (RValue.StartTagOpenDeriv (name, ns));
 783 #endif
 784                 }
 785
 786                 // attDeriv cx (Choice p1 p2) att =
 787                 //  choice (attDeriv cx p1 att) (attDeriv cx p2 att)
 788                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
 789                 {
 790                         return LValue.AttDeriv (name, ns, value, reader)
 791                                 .Choice (RValue.AttDeriv (name, ns, value, reader));
 792                 }
 793
 794                 // startTagCloseDeriv (Choice p1 p2) =
 795                 //  choice (startTagCloseDeriv p1) (startTagCloseDeriv p2)
 796                 public override RdpPattern StartTagCloseDeriv ()
 797                 {
 798                         return LValue.StartTagCloseDeriv ()
 799                                 .Choice (RValue.StartTagCloseDeriv ());
 800                 }
 801
 802                 public override RdpPattern EndTagDeriv ()
 803                 {
 804                         return LValue.EndTagDeriv ().Choice (RValue.EndTagDeriv ());
 805                 }
 806
 807                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 808                 {
 809                         LValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, list, dataExcept);
 810                         RValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, list, dataExcept);
 811                 }
 812         }
 813
 814         // Interleave
 815         public class RdpInterleave : RdpAbstractBinary
 816         {
 817                 public RdpInterleave (RdpPattern l, RdpPattern r) : base (l, r)
 818                 {
 819                 }
 820
 821                 public override bool Nullable {
 822                         get {
 823                                 if (!nullableComputed) {
 824                                         isNullable =
 825                                                 LValue.Nullable && RValue.Nullable;
 826                                         nullableComputed = true;
 827                                 }
 828                                 return isNullable;
 829                         }
 830                 }
 831
 832                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 833                 {
 834                         LValue.GetLabels (elements, attributes, collectNameClass);
 835                         RValue.GetLabels (elements, attributes, collectNameClass);
 836                 }
 837
 838                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
 839                 {
 840                         if (visited.Contains (this))
 841                                 return this;
 842                         visited.Add (this, this);
 843
 844                         if (LValue.PatternType == RelaxngPatternType.NotAllowed ||
 845                                 RValue.PatternType == RelaxngPatternType.NotAllowed) {
 846                                 result = true;
 847                                 return RdpNotAllowed.Instance;
 848                         } else {
 849                                 LValue = LValue.ReduceEmptyAndNotAllowed (ref result, visited);
 850                                 RValue = RValue.ReduceEmptyAndNotAllowed (ref result, visited);
 851                                 return this;
 852                         }
 853                 }
 854
 855                 public override RdpPattern TextDeriv (string s, XmlReader reader)
 856                 {
 857                         return LValue.TextDeriv (s, reader).Interleave (RValue)
 858                                 .Choice (LValue.Interleave (RValue.TextDeriv (s, reader)));
 859                 }
 860
 861                 // => choice (applyAfter (flip interleave p2) (startTagOpenDeriv p1 qn)) (applyAfter (interleave p1) (startTagOpenDeriv p2 qn)
 862                 // => p1.startTagOpenDeriv(qn).applyAfter (flip interleave p2).choice (p2.startTagOpenDeriv(qn).applyAfter (interleave p1) )
 863                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
 864                 {
 865                         RdpPattern handledL = LValue.StartTagOpenDeriv (name, ns);
 866                         RdpPattern handledR = RValue.StartTagOpenDeriv (name, ns);
 867                         RdpFlip flipL = MakeFlip (RdpUtil.InterleaveFunction, RValue);
 868                         RdpPattern choiceL = handledL.ApplyAfter (new RdpApplyAfterHandler (flipL.Apply));
 869                         RdpPattern choiceR = handledR.ApplyAfter (new RdpApplyAfterHandler (LValue.Interleave));
 870                         return choiceL.Choice (choiceR);
 871                 }
 872
 873                 // attDeriv cx (Interleave p1 p2) att =
 874                 //  choice (interleave (attDeriv cx p1 att) p2)
 875                 //         (interleave p1 (attDeriv cx p2 att))
 876                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
 877                 {
 878                         return LValue.AttDeriv (name, ns, value, reader)
 879                                 .Interleave (RValue)
 880                                 .Choice (LValue.Interleave (
 881                                         RValue.AttDeriv (name, ns, value, reader)));
 882                 }
 883
 884                 // startTagCloseDeriv (Interleave p1 p2) =
 885                 //  interleave (startTagCloseDeriv p1) (startTagCloseDeriv p2)
 886                 public override RdpPattern StartTagCloseDeriv ()
 887                 {
 888                         return LValue.StartTagCloseDeriv ()
 889                                 .Interleave (RValue.StartTagCloseDeriv ());
 890                 }
 891
 892                 /*
 893                 // FIXME: This is not specified in James Clark's algorithm, so
 894                 // this may raise unstable behaviour!!
 895                 // I think this is right but not confident.
 896
 897                 // ... then I reminded to include it.
 898                 public override RdpPattern EndTagDeriv ()
 899                 {
 900                         return LValue.Nullable ? RValue : RdpNotAllowed.Instance;
 901                 }
 902                 */
 903
 904                 public override RelaxngPatternType PatternType {
 905                         get { return RelaxngPatternType.Interleave; }
 906                 }
 907
 908                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
 909                 {
 910                         if (list)
 911                                 throw new RelaxngException ("interleave is not allowed under a list.");
 912                         if (dataExcept)
 913                                 throw new RelaxngException ("interleave is not allowed under except of a data.");
 914
 915                         // 7.1
 916                         LValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMore, list, dataExcept);
 917                         RValue.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMore, list, dataExcept);
 918
 919                         // unique name analysis - 7.3 and part of 7.4
 920                         CheckNameOverlap (true);
 921
 922                         // (2) text/text prohibited
 923                         if (LValue.ContainsText () && RValue.ContainsText ())
 924                                 throw new RelaxngException ("Both branches of the interleave contains a text pattern.");
 925                 }
 926         }
 927
 928         // Group
 929         public class RdpGroup : RdpAbstractBinary
 930         {
 931                 public RdpGroup (RdpPattern l, RdpPattern r) : base (l, r)
 932                 {
 933                 }
 934
 935                 public override bool Nullable {
 936                         get {
 937                                 if (!nullableComputed) {
 938                                         isNullable =
 939                                                 LValue.Nullable && RValue.Nullable;
 940                                         nullableComputed = true;
 941                                 }
 942                                 return isNullable;
 943                         }
 944                 }
 945
 946                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
 947                 {
 948                         LValue.GetLabels (elements, attributes, collectNameClass);
 949                         if (LValue.Nullable)
 950                                 RValue.GetLabels (elements, attributes, collectNameClass);
 951                         else
 952                                 RValue.GetLabels (null, attributes, collectNameClass);
 953                 }
 954
 955                 public override RdpPattern TextDeriv (string s, XmlReader reader)
 956                 {
 957                         RdpPattern p = LValue.TextDeriv (s, reader).Group (RValue);
 958                         return LValue.Nullable ?
 959                                 p.Choice (RValue.TextDeriv(s, reader)) : p;
 960                 }
 961
 962                 // startTagOpenDeriv (Group p1 p2) qn =
 963                 //  let x = applyAfter (flip group p2) (startTagOpenDeriv p1 qn)
 964                 //  in if nullable p1 then
 965                 //       choice x (startTagOpenDeriv p2 qn)
 966                 //     else
 967                 //       x
 968                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
 969                 {
 970                         RdpPattern handled = LValue.StartTagOpenDeriv (name, ns);
 971                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, RValue);
 972                         RdpPattern x = handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
 973                         if (LValue.Nullable)
 974                                 return x.Choice (RValue.StartTagOpenDeriv (name, ns));
 975                         else
 976                                 return x;
 977                 }
 978
 979                 // attDeriv cx (Group p1 p2) att =
 980                 //  choice (group (attDeriv cx p1 att) p2)
 981                 //         (group p1 (attDeriv cx p2 att))
 982                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
 983                 {
 984                         return LValue.AttDeriv (name, ns, value, reader).Group (RValue)
 985                                 .Choice (LValue.Group (
 986                                         RValue.AttDeriv (name, ns, value, reader)));
 987                 }
 988
 989                 // startTagCloseDeriv (Group p1 p2) =
 990                 //  group (startTagCloseDeriv p1) (startTagCloseDeriv p2)
 991                 public override RdpPattern StartTagCloseDeriv ()
 992                 {
 993                         return LValue.StartTagCloseDeriv ()
 994                                 .Group (RValue.StartTagCloseDeriv ());
 995                 }
 996
 997                 public override RelaxngPatternType PatternType {
 998                         get { return RelaxngPatternType.Group; }
 999                 }
1000
1001                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1002                 {
1003                         if (dataExcept)
1004                                 throw new RelaxngException ("interleave is not allowed under except of a data.");
1005
1006                         LValue.CheckConstraints (attribute, oneOrMore, oneOrMore, oneOrMoreInterleave, list, dataExcept);
1007                         RValue.CheckConstraints (attribute, oneOrMore, oneOrMore, oneOrMoreInterleave, list, dataExcept);
1008
1009                         // 7.3
1010                         CheckNameOverlap (false);
1011                 }
1012         }
1013
1014         public abstract class RdpAbstractSingleContent : RdpPattern
1015         {
1016                 RdpPattern child;
1017                 bool isExpanded;
1018
1019                 internal override RdpPattern ExpandRef (Hashtable defs)
1020                 {
1021                         if (!isExpanded)
1022                                 child = child.ExpandRef (defs);
1023                         return this;
1024                 }
1025
1026                 public RdpAbstractSingleContent (RdpPattern p)
1027                 {
1028                         this.child = p;
1029                 }
1030
1031                 public RdpPattern Child {
1032                         get { return child; }
1033                         set { child = value; }
1034                 }
1035
1036                 internal override void MarkReachableDefs ()
1037                 {
1038                         child.MarkReachableDefs ();
1039                 }
1040
1041                 internal override bool ContainsText()
1042                 {
1043                         return child.ContainsText ();
1044                 }
1045         }
1046
1047         // OneOrMore
1048         public class RdpOneOrMore : RdpAbstractSingleContent
1049         {
1050                 public RdpOneOrMore (RdpPattern p) : base (p)
1051                 {
1052                 }
1053
1054                 public override RelaxngPatternType PatternType {
1055                         get { return RelaxngPatternType.OneOrMore; }
1056                 }
1057
1058                 public override RdpContentType ContentType {
1059                         get {
1060                                 if (Child.ContentType == RdpContentType.Simple)
1061                                         throw new RelaxngException ("Invalid content type was found.");
1062                                 return Child.ContentType;
1063                         }
1064                 }
1065
1066                 public override bool Nullable {
1067                         get { return Child.Nullable; }
1068                 }
1069
1070                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1071                 {
1072                         Child.GetLabels (elements, attributes, collectNameClass);
1073                 }
1074
1075                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1076                 {
1077                         if (visited.Contains (this))
1078                                 return this;
1079                         visited.Add (this, this);
1080
1081                         if (Child.PatternType == RelaxngPatternType.NotAllowed) {
1082                                 result = true;
1083                                 return RdpNotAllowed.Instance;
1084                         } else if (Child.PatternType == RelaxngPatternType.Empty)
1085                                 return RdpEmpty.Instance;
1086                         else {
1087                                 Child = Child.ReduceEmptyAndNotAllowed (ref result, visited);
1088                                 return this;
1089                         }
1090                 }
1091
1092                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1093                 {
1094                         return Child.TextDeriv (s, reader).Group (Choice (RdpEmpty.Instance));
1095                 }
1096
1097                 // attDeriv cx (OneOrMore p) att =
1098                 //  group (attDeriv cx p att) (choice (OneOrMore p) Empty)
1099                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1100                 {
1101 #if UseStatic
1102                         return RdpUtil.Group (
1103                                 RdpUtil.AttDeriv (ctx, children, att),
1104                                 RdpUtil.Choice (RdpUtil.OneOrMore (children), RdpEmpty.Instance));
1105 #else
1106                         return Child.AttDeriv (name, ns, value, reader)
1107                                 .Group (Choice (RdpEmpty.Instance));
1108 #endif
1109                 }
1110
1111                 // startTagOpenDeriv (OneOrMore p) qn =
1112                 //  applyAfter (flip group (choice (OneOrMore p) Empty))
1113                 //             (startTagOpenDeriv p qn)
1114                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
1115                 {
1116                         RdpPattern rest = RdpEmpty.Instance.Choice (Child.OneOrMore ());
1117                         RdpPattern handled = Child.StartTagOpenDeriv (name, ns);
1118                         RdpFlip f = MakeFlip (RdpUtil.GroupFunction, rest);
1119                         return handled.ApplyAfter (new RdpApplyAfterHandler (f.Apply));
1120                 }
1121
1122                 // startTagCloseDeriv (OneOrMore p) =
1123                 //  oneOrMore (startTagCloseDeriv p)
1124                 public override RdpPattern StartTagCloseDeriv ()
1125                 {
1126 #if UseStatic
1127                         return RdpUtil.OneOrMore (
1128                                 RdpUtil.StartTagCloseDeriv (children));
1129 #else
1130                         return Child.StartTagCloseDeriv ().OneOrMore ();
1131 #endif
1132                 }
1133
1134                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1135                 {
1136                         if (dataExcept)
1137                                 throw new RelaxngException ("oneOrMore is not allowed under except of a data.");
1138                         this.Child.CheckConstraints (attribute, true, oneOrMoreGroup, oneOrMoreInterleave, list, dataExcept);
1139                 }
1140         }
1141
1142         // List
1143         public class RdpList : RdpAbstractSingleContent
1144         {
1145                 public RdpList (RdpPattern p) : base (p)
1146                 {
1147                 }
1148
1149                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1150                 {
1151                         if (visited.Contains (this))
1152                                 return this;
1153                         visited.Add (this, this);
1154
1155                         if (Child.PatternType == RelaxngPatternType.NotAllowed) {
1156                                 result = true;
1157                                 return RdpNotAllowed.Instance;
1158                         } else {
1159                                 Child = Child.ReduceEmptyAndNotAllowed (ref result, visited);
1160                                 return this;
1161                         }
1162                 }
1163
1164 /*
1165                 // This is not written in James Clark's derivative algorithm
1166                 // ( http://www.thaiopensource.com/relaxng/derivative.html ),
1167                 // but it looks required.
1168                 public override bool Nullable {
1169                         get { return this.Child.Nullable; }
1170                 }
1171
1172                 // ... but it also causes different error:
1173                 // <list><group><data .../><data .../></group></list>
1174 */
1175                 public override bool Nullable {
1176                         get { return false; }
1177                 }
1178
1179                 public override RelaxngPatternType PatternType {
1180                         get { return RelaxngPatternType.List; }
1181                 }
1182
1183                 public override RdpContentType ContentType {
1184                         get { return RdpContentType.Simple; }
1185                 }
1186
1187                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1188                 {
1189                         Child.GetLabels (elements, attributes, collectNameClass);
1190                 }
1191
1192                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1193                 {
1194                         RdpPattern p = Child.ListDeriv (Util.NormalizeWhitespace (s).Split (RdpUtil.WhitespaceChars), 0, reader);
1195                         if (p.Nullable)
1196                                 return RdpEmpty.Instance;
1197                         else
1198                                 return RdpNotAllowed.Instance;
1199                 }
1200
1201                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1202                 {
1203                         if (list)
1204                                 throw new RelaxngException ("list is not allowed uner another list.");
1205                         if (dataExcept)
1206                                 throw new RelaxngException ("list is not allowed under except of a data.");
1207                         this.Child.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, true, dataExcept);
1208                 }
1209         }
1210
1211         // Data
1212         public class RdpData : RdpPattern
1213         {
1214                 public RdpData (RdpDatatype dt)
1215                 {
1216                         this.dt = dt;
1217                 }
1218
1219                 RdpDatatype dt;
1220                 public RdpDatatype Datatype {
1221                         get { return dt; }
1222                 }
1223
1224                 // This is not written in James Clark's derivative algorithm
1225                 // ( http://www.thaiopensource.com/relaxng/derivative.html ),
1226                 // but it looks required.
1227                 public override bool Nullable {
1228                         get {
1229                                 if (dt.NamespaceURI.Length == 0)
1230                                         return true;
1231                                 return false;
1232                         }
1233                 }
1234
1235                 public override RelaxngPatternType PatternType {
1236                         get { return RelaxngPatternType.Data; }
1237                 }
1238
1239                 public override RdpContentType ContentType {
1240                         get { return RdpContentType.Simple; }
1241                 }
1242
1243                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1244                 {
1245                         // do nothing.
1246                 }
1247
1248                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1249                 {
1250                         if (dt.IsAllowed (s, reader))
1251                                 return RdpEmpty.Instance;
1252                         else
1253                                 return RdpNotAllowed.Instance;
1254                 }
1255
1256                 internal override void MarkReachableDefs ()
1257                 {
1258                         // do nothing
1259                 }
1260
1261                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1262                 {
1263                         // do nothing
1264                 }
1265
1266                 internal override bool ContainsText()
1267                 {
1268                         return false;
1269                 }
1270         }
1271
1272         // DataExcept
1273         public class RdpDataExcept : RdpData
1274         {
1275                 public RdpDataExcept (RdpDatatype dt, RdpPattern except)
1276                         : base (dt)
1277                 {
1278                         this.except = except;
1279                 }
1280
1281                 RdpPattern except;
1282                 public RdpPattern Except {
1283                         get { return except; }
1284                         set { except = value; }
1285                 }
1286
1287                 public override RelaxngPatternType PatternType {
1288                         get { return RelaxngPatternType.DataExcept; }
1289                 }
1290
1291                 public override RdpContentType ContentType {
1292                         get {
1293                                 RdpContentType c = except.ContentType; // conformance required for except pattern.
1294                                 return RdpContentType.Simple;
1295                         }
1296                 }
1297
1298                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1299                 {
1300                         if (visited.Contains (this))
1301                                 return this;
1302                         visited.Add (this, this);
1303
1304                         if (except.PatternType == RelaxngPatternType.NotAllowed) {
1305                                 result = true;
1306                                 return new RdpData (this.Datatype);
1307                         } else {
1308                                 except = except.ReduceEmptyAndNotAllowed (ref result, visited);
1309                                 return this;
1310                         }
1311                 }
1312
1313                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1314                 {
1315                         if (Datatype.IsAllowed (s, reader) && !except.TextDeriv (s, reader).Nullable)
1316                                 return RdpEmpty.Instance;
1317                         else
1318                                 return RdpNotAllowed.Instance;
1319                 }
1320
1321                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1322                 {
1323                         this.except.CheckConstraints (attribute, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, list, true);
1324                 }
1325
1326                 internal override bool ContainsText()
1327                 {
1328                         return except.ContainsText ();
1329                 }
1330         }
1331
1332         // Value
1333         public class RdpValue : RdpPattern
1334         {
1335                 public RdpValue (RdpDatatype dt, string value)
1336                 {
1337                         this.dt = dt;
1338                         this.value = value;
1339                 }
1340
1341                 RdpDatatype dt;
1342                 public RdpDatatype Datatype {
1343                         get { return dt; }
1344                 }
1345
1346                 string value;
1347                 public string Value {
1348                         get { return value; }
1349                 }
1350
1351                 // This is not written in James Clark's derivative algorithm
1352                 // ( http://www.thaiopensource.com/relaxng/derivative.html ),
1353                 // but it looks required.
1354                 public override bool Nullable {
1355                         get {
1356                                 if (dt.NamespaceURI.Length == 0 && value.Length == 0)
1357                                         return true;
1358                                 return false;
1359                         }
1360                 }
1361
1362                 public override RelaxngPatternType PatternType {
1363                         get { return RelaxngPatternType.Value; }
1364                 }
1365
1366                 public override RdpContentType ContentType {
1367                         get { return RdpContentType.Simple; }
1368                 }
1369
1370                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1371                 {
1372                         // do nothing
1373                 }
1374
1375                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1376                 {
1377                         if (dt.IsTypeEqual (value, s, reader))
1378                                 return RdpEmpty.Instance;
1379                         else
1380                                 return RdpNotAllowed.Instance;
1381                 }
1382
1383                 internal override void MarkReachableDefs ()
1384                 {
1385                         // do nothing
1386                 }
1387
1388                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1389                 {
1390                         // nothing to be checked
1391                 }
1392
1393                 internal override bool ContainsText()
1394                 {
1395                         return false;
1396                 }
1397         }
1398
1399         // Attribute
1400         public class RdpAttribute : RdpPattern
1401         {
1402                 public RdpAttribute (RdpNameClass nameClass, RdpPattern p)
1403                 {
1404                         this.nameClass = nameClass;
1405                         this.children = p;
1406                 }
1407
1408                 RdpNameClass nameClass;
1409                 public RdpNameClass NameClass {
1410                         get { return nameClass; }
1411                 }
1412
1413                 RdpPattern children;
1414                 public RdpPattern Children {
1415                         get { return children; }
1416                         set { children = value; }
1417                 }
1418
1419                 public override bool Nullable {
1420                         get { return false; }
1421                 }
1422
1423                 public override RelaxngPatternType PatternType {
1424                         get { return RelaxngPatternType.Attribute; }
1425                 }
1426
1427                 public override RdpContentType ContentType {
1428                         get { return RdpContentType.Empty; }
1429                 }
1430
1431                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1432                 {
1433                         if (attributes != null) {
1434                                 if (collectNameClass)
1435                                         attributes [NameClass] = NameClass;
1436                                 else
1437                                         AddNameLabel (attributes, NameClass);
1438                         }
1439                 }
1440
1441                 bool isExpanded;
1442                 internal override RdpPattern ExpandRef (Hashtable defs)
1443                 {
1444                         if (!isExpanded) {
1445                                 isExpanded = true;
1446                                 children = children.ExpandRef (defs);
1447                         }
1448                         return this;
1449                 }
1450
1451                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1452                 {
1453                         if (visited.Contains (this))
1454                                 return this;
1455                         visited.Add (this, this);
1456
1457                         if (children.PatternType == RelaxngPatternType.NotAllowed) {
1458                                 result = true;
1459                                 return RdpNotAllowed.Instance;
1460                         } else {
1461                                 children = children.ReduceEmptyAndNotAllowed (ref result, visited);
1462                                 return this;
1463                         }
1464                 }
1465
1466                 // attDeriv cx (Attribute nc p) (AttributeNode qn s) =
1467                 //  if contains nc qn && valueMatch cx p s then Empty else NotAllowed
1468                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1469                 {
1470                         // If value is null, then does not check ValueMatch.
1471 #if UseStatic
1472                         if (RdpUtil.Contains (this.nameClass, att.QName)
1473                                 && (value == null || RdpUtil.ValueMatch (ctx, this.children, att.Value)))
1474                                 return RdpEmpty.Instance;
1475                         else
1476                                 return RdpNotAllowed.Instance;
1477 #else
1478                         if (nameClass.Contains (name, ns) &&
1479                                 (value == null || children.ValueMatch (value, reader)))
1480                                 return RdpEmpty.Instance;
1481                         else
1482                                 return RdpNotAllowed.Instance;
1483 #endif
1484                 }
1485
1486                 // startTagCloseDeriv (Attribute _ _) = NotAllowed
1487                 public override RdpPattern StartTagCloseDeriv ()
1488                 {
1489                         return RdpNotAllowed.Instance;
1490                 }
1491
1492                 internal override void MarkReachableDefs ()
1493                 {
1494                         children.MarkReachableDefs ();
1495                 }
1496
1497                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1498                 {
1499                         // 7.1.1 and 7.1.2
1500                         if (attribute || oneOrMoreGroup || oneOrMoreInterleave || list || dataExcept)
1501                                 throw new RelaxngException ("Not allowed attribute occurence was specified in the pattern.");
1502
1503                         // latter part of 7.3
1504                         if (!oneOrMore && NameClass.HasInfiniteName)
1505                                 throw new RelaxngException ("Attributes that has an infinite name class must be repeatable.");
1506
1507                         this.Children.CheckConstraints (true, oneOrMore, false, false, false, false);
1508                 }
1509
1510                 internal override bool ContainsText()
1511                 {
1512                         // This method is to detect text pattern inside interleave child.
1513                         // return children.ContainsText ();
1514                         return false;
1515                 }
1516         }
1517
1518         // Element
1519         public class RdpElement : RdpPattern
1520         {
1521                 public RdpElement (RdpNameClass nameClass, RdpPattern p)
1522                 {
1523                         this.nameClass = nameClass;
1524                         this.children = p;
1525                 }
1526
1527                 RdpNameClass nameClass;
1528                 public RdpNameClass NameClass {
1529                         get { return nameClass; }
1530                 }
1531
1532                 RdpPattern children;
1533                 public RdpPattern Children {
1534                         get { return children; }
1535                         set { children = value; }
1536                 }
1537
1538                 public override bool Nullable {
1539                         get { return false; }
1540                 }
1541
1542                 public override RelaxngPatternType PatternType {
1543                         get { return RelaxngPatternType.Element; }
1544                 }
1545
1546                 bool contentTypeCheckDone;
1547                 public override RdpContentType ContentType {
1548                         get {
1549                                 if (!contentTypeCheckDone) {
1550                                         contentTypeCheckDone = true;
1551                                         RdpContentType ct = children.ContentType; // conformance required.
1552                                 }
1553                                 return RdpContentType.Complex;
1554                         }
1555                 }
1556
1557                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1558                 {
1559                         if (elements != null) {
1560                                 if (collectNameClass)
1561                                         elements [NameClass] = NameClass;
1562                                 else
1563                                         AddNameLabel (elements, NameClass);
1564                         }
1565                 }
1566
1567
1568                 bool isExpanded;
1569                 short expanding; // FIXME: It is totally not required, but there is
1570                 // some bugs in simplification and without it it causes infinite loop.
1571                 internal override RdpPattern ExpandRef (Hashtable defs)
1572                 {
1573                         if (!isExpanded) {
1574                                 isExpanded = true;
1575                                 if (expanding == 100)
1576                                         throw new RelaxngException (String.Format ("Invalid recursion was found. Name is {0}", nameClass));
1577                                 expanding++;
1578                                 children = children.ExpandRef (defs);
1579                                 expanding--;
1580                         }
1581                         return this;
1582                 }
1583
1584                 internal override RdpPattern ReduceEmptyAndNotAllowed (ref bool result, Hashtable visited)
1585                 {
1586                         if (visited.Contains (this))
1587                                 return this;
1588                         visited.Add (this, this);
1589
1590                         children = children.ReduceEmptyAndNotAllowed (ref result, visited);
1591                         return this;
1592                 }
1593
1594                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
1595                 {
1596 #if UseStatic
1597                         if (RdpUtil.Contains (this.nameClass, qname))
1598                                 return RdpUtil.After (this.Children, RdpEmpty.Instance);
1599                         else
1600                                 return RdpNotAllowed.Instance;
1601 #else
1602                         return nameClass.Contains (name, ns) ?
1603                                 children.After (RdpEmpty.Instance) :
1604                                 RdpNotAllowed.Instance;
1605 #endif
1606                 }
1607
1608                 internal override void MarkReachableDefs ()
1609                 {
1610                         children.MarkReachableDefs ();
1611                 }
1612
1613                 bool constraintsChecked;
1614                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1615                 {
1616                         if (constraintsChecked)
1617                                 return;
1618                         constraintsChecked = true;
1619                         if (attribute || list || dataExcept)
1620                                 throw new RelaxngException ("Not allowed element occurence was specified in the pattern.");
1621                         this.Children.CheckConstraints (false, oneOrMore, oneOrMoreGroup, oneOrMoreInterleave, false, false);
1622                 }
1623
1624                 internal override bool ContainsText()
1625                 {
1626                         return children.ContainsText ();
1627                 }
1628         }
1629
1630         // After
1631         public class RdpAfter : RdpAbstractBinary
1632         {
1633                 public RdpAfter (RdpPattern l, RdpPattern r) : base (l, r)
1634                 {
1635                 }
1636
1637                 public override bool Nullable {
1638                         get { return false; }
1639                 }
1640
1641                 public override void GetLabels (LabelList elements, LabelList attributes, bool collectNameClass)
1642                 {
1643                         LValue.GetLabels (elements, attributes, collectNameClass);
1644                 }
1645
1646                 public override RdpPattern TextDeriv (string s, XmlReader reader)
1647                 {
1648                         return LValue.TextDeriv (s, reader).After (RValue);
1649                 }
1650
1651                 // startTagOpenDeriv (After p1 p2) qn =
1652                 //   applyAfter (flip after p2) (startTagOpenDeriv p1 qn)
1653                 public override RdpPattern StartTagOpenDeriv (string name, string ns)
1654                 {
1655                         RdpPattern handled = LValue.StartTagOpenDeriv (name, ns);
1656                         RdpFlip f = MakeFlip (RdpUtil.AfterFunction, RValue);
1657                         return handled.ApplyAfter (new RdpApplyAfterHandler (
1658                                 f.Apply));
1659                 }
1660
1661                 public override RdpPattern ApplyAfter (RdpApplyAfterHandler handler)
1662                 {
1663                         return LValue.After (handler (RValue));
1664                 }
1665
1666                 // attDeriv cx (After p1 p2) att =
1667                 //  after (attDeriv cx p1 att) p2
1668                 public override RdpPattern AttDeriv (string name, string ns, string value, XmlReader reader)
1669                 {
1670                         return LValue.AttDeriv (name, ns, value, reader).After (RValue);
1671                 }
1672
1673                 public override RdpPattern StartTagCloseDeriv ()
1674                 {
1675                         return LValue.StartTagCloseDeriv ().After (RValue);
1676                 }
1677
1678                 public override RdpPattern EndTagDeriv ()
1679                 {
1680                         return LValue.Nullable ? RValue : RdpNotAllowed.Instance;
1681                 }
1682
1683                 public override RelaxngPatternType PatternType {
1684                         get { return RelaxngPatternType.After; }
1685                 }
1686
1687                 internal override void MarkReachableDefs ()
1688                 {
1689                         throw new InvalidOperationException ();
1690                 }
1691
1692                 internal override void CheckConstraints (bool attribute, bool oneOrMore, bool oneOrMoreGroup, bool oneOrMoreInterleave, bool list, bool dataExcept)
1693                 {
1694                         throw new InvalidOperationException ();
1695                 }
1696
1697                 internal override bool ContainsText ()
1698                 {
1699                         throw new InvalidOperationException ();
1700                 }
1701         }
1702 }
1703