mcs/class/System.XML/System.Xml/DTDAutomata.cs

   1 //
   2 // Mono.Xml.DTDAutomata
   3 //
   4 // Author:
   5 //      Atsushi Enomoto (ginga@kit.hi-ho.ne.jp)
   6 //
   7 //      (C)2003 Atsushi Enomoto
   8 //
   9
  10 //
  11 // Permission is hereby granted, free of charge, to any person obtaining
  12 // a copy of this software and associated documentation files (the
  13 // "Software"), to deal in the Software without restriction, including
  14 // without limitation the rights to use, copy, modify, merge, publish,
  15 // distribute, sublicense, and/or sell copies of the Software, and to
  16 // permit persons to whom the Software is furnished to do so, subject to
  17 // the following conditions:
  18 //
  19 // The above copyright notice and this permission notice shall be
  20 // included in all copies or substantial portions of the Software.
  21 //
  22 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  23 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  24 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  25 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  26 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  27 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  29 //
  30 using System;
  31 using System.Collections;
  32 using System.Text;
  33 using System.Xml;
  34 using System.Xml.Schema;
  35 using Mono.Xml.Schema;
  36
  37 namespace Mono.Xml
  38 {
  39         internal class DTDAutomataFactory
  40         {
  41                 public DTDAutomataFactory (DTDObjectModel root)
  42                 {
  43                         this.root = root;
  44                 }
  45
  46                 DTDObjectModel root;
  47                 Hashtable choiceTable = new Hashtable ();
  48                 Hashtable sequenceTable = new Hashtable ();
  49
  50                 public DTDChoiceAutomata Choice (DTDAutomata left, DTDAutomata right)
  51                 {
  52                         Hashtable rightPool = choiceTable [left] as Hashtable;
  53                         if (rightPool == null) {
  54                                 rightPool = new Hashtable ();
  55                                 choiceTable [left] = rightPool;
  56                         }
  57                         DTDChoiceAutomata result = rightPool [right] as DTDChoiceAutomata;
  58                         if (result == null) {
  59                                 result = new DTDChoiceAutomata (root, left, right);
  60                                 rightPool [right] = result;
  61                         }
  62                         return result;
  63                 }
  64
  65                 public DTDSequenceAutomata Sequence (DTDAutomata left, DTDAutomata right)
  66                 {
  67                         Hashtable rightPool = sequenceTable [left] as Hashtable;
  68                         if (rightPool == null) {
  69                                 rightPool = new Hashtable ();
  70                                 sequenceTable [left] = rightPool;
  71                         }
  72                         DTDSequenceAutomata result = rightPool [right] as DTDSequenceAutomata;
  73                         if (result == null) {
  74                                 result = new DTDSequenceAutomata (root, left, right);
  75                                 rightPool [right] = result;
  76                         }
  77                         return result;
  78                 }
  79         }
  80
  81         internal abstract class DTDAutomata
  82         {
  83                 public DTDAutomata (DTDObjectModel root)
  84                 {
  85                         this.root = root;
  86                 }
  87
  88                 private DTDObjectModel root;
  89
  90                 public DTDObjectModel Root {
  91                         get { return root; }
  92                 }
  93
  94                 public DTDAutomata MakeChoice (DTDAutomata other)
  95                 {
  96                         if (this == Root.Invalid)
  97                                 return other;
  98                         if (other == Root.Invalid)
  99                                 return this;
 100                         if (this == Root.Empty && other == Root.Empty)
 101                                 return this;
 102                         if (this == Root.Any && other == Root.Any)
 103                                 return this;
 104                         else if (other == Root.Empty)
 105                                 return Root.Factory.Choice (other, this);
 106                         else
 107                                 return Root.Factory.Choice (this, other);
 108                 }
 109
 110                 public DTDAutomata MakeSequence (DTDAutomata other)
 111                 {
 112                         if (this == Root.Invalid || other == Root.Invalid)
 113                                 return Root.Invalid;
 114                         if (this == Root.Empty)
 115                                 return other;
 116                         if (other == Root.Empty)
 117                                 return this;
 118                         else
 119                                 return Root.Factory.Sequence (this, other);
 120                 }
 121
 122                 public abstract DTDAutomata TryStartElement (string name);
 123                 public virtual DTDAutomata TryEndElement ()
 124                 {
 125                         return Root.Invalid;
 126                 }
 127
 128                 public virtual bool Emptiable {
 129                         get { return false; }
 130                 }
 131         }
 132
 133         internal class DTDElementAutomata : DTDAutomata
 134         {
 135                 public DTDElementAutomata (DTDObjectModel root, string name)
 136                         : base (root)
 137                 {
 138                         this.name = name;
 139                 }
 140
 141                 private string name;
 142
 143                 public string Name {
 144                         get { return name; }
 145                 }
 146
 147                 public override DTDAutomata TryStartElement (string name)
 148                 {
 149                         if (name == Name)
 150                                 return Root.Empty;
 151                         else
 152                                 return Root.Invalid;
 153                 }
 154         }
 155
 156         internal class DTDChoiceAutomata : DTDAutomata
 157         {
 158                 public DTDChoiceAutomata (DTDObjectModel root,
 159                         DTDAutomata left, DTDAutomata right)
 160                         : base (root)
 161                 {
 162                         this.left = left;
 163                         this.right = right;
 164                 }
 165
 166                 private DTDAutomata left;
 167                 private DTDAutomata right;
 168
 169                 public DTDAutomata Left {
 170                         get { return left; }
 171                 }
 172
 173                 public DTDAutomata Right {
 174                         get { return right; }
 175                 }
 176
 177                 public override DTDAutomata TryStartElement (string name)
 178                 {
 179                         return left.TryStartElement (name).MakeChoice (
 180                                 right.TryStartElement (name));
 181                 }
 182
 183                 public override DTDAutomata TryEndElement ()
 184                 {
 185                         return left.TryEndElement ().MakeChoice (right.TryEndElement ());
 186                 }
 187
 188                 bool hasComputedEmptiable;
 189                 bool cachedEmptiable;
 190                 public override bool Emptiable {
 191                         get {
 192                                 if (!hasComputedEmptiable) {
 193                                         cachedEmptiable = left.Emptiable ||
 194                                                 right.Emptiable;
 195                                         hasComputedEmptiable = true;
 196                                 }
 197                                 return cachedEmptiable;
 198                         }
 199                 }
 200         }
 201
 202         internal class DTDSequenceAutomata : DTDAutomata
 203         {
 204                 public DTDSequenceAutomata (DTDObjectModel root,
 205                         DTDAutomata left, DTDAutomata right)
 206                         : base (root)
 207                 {
 208                         this.left = left;
 209                         this.right = right;
 210                 }
 211
 212                 private DTDAutomata left;
 213                 private DTDAutomata right;
 214
 215                 public DTDAutomata Left {
 216                         get { return left; }
 217                 }
 218
 219                 public DTDAutomata Right {
 220                         get { return right; }
 221                 }
 222
 223                 public override DTDAutomata TryStartElement (string name)
 224                 {
 225                         DTDAutomata afterL = left.TryStartElement (name);
 226                         DTDAutomata afterR = right.TryStartElement (name);
 227                         if (afterL == Root.Invalid)
 228                                 return (left.Emptiable) ? afterR : afterL;
 229                         // else
 230                         DTDAutomata whenLeftConsumed = afterL.MakeSequence (right);
 231                         if (left.Emptiable)
 232                                 return afterR.MakeChoice (whenLeftConsumed);
 233                         else
 234                                 return whenLeftConsumed;
 235                 }
 236
 237                 public override DTDAutomata TryEndElement ()
 238                 {
 239                         return left.Emptiable ? right : Root.Invalid;
 240                 }
 241
 242                 bool hasComputedEmptiable;
 243                 bool cachedEmptiable;
 244                 public override bool Emptiable {
 245                         get {
 246                                 if (!hasComputedEmptiable) {
 247                                         cachedEmptiable = left.Emptiable &&
 248                                                 right.Emptiable;
 249                                         hasComputedEmptiable = true;
 250                                 }
 251                                 return cachedEmptiable;
 252                         }
 253                 }
 254         }
 255
 256         internal class DTDOneOrMoreAutomata : DTDAutomata
 257         {
 258                 public DTDOneOrMoreAutomata (DTDObjectModel root,
 259                         DTDAutomata children)
 260                         : base (root)
 261                 {
 262                         this.children = children;
 263                 }
 264
 265                 private DTDAutomata children;
 266
 267                 public DTDAutomata Children {
 268                         get { return children; }
 269                 }
 270
 271                 public override DTDAutomata TryStartElement (string name)
 272                 {
 273                         DTDAutomata afterC = children.TryStartElement (name);
 274                         if (afterC != Root.Invalid)
 275                                 return afterC.MakeSequence (
 276                                         Root.Empty.MakeChoice (this));
 277                         else
 278                                 return Root.Invalid;
 279                 }
 280
 281                 public override DTDAutomata TryEndElement ()
 282                 {
 283                         return Emptiable ? children.TryEndElement () : Root.Invalid;
 284                 }
 285         }
 286
 287         internal class DTDEmptyAutomata : DTDAutomata
 288         {
 289                 public DTDEmptyAutomata (DTDObjectModel root)
 290                         : base (root)
 291                 {
 292                 }
 293
 294                 public override DTDAutomata TryEndElement ()
 295                 {
 296                         return this;
 297                 }
 298
 299                 public override DTDAutomata TryStartElement (string name)
 300                 {
 301                         return Root.Invalid;
 302                 }
 303
 304                 public override bool Emptiable {
 305                         get { return true; }
 306                 }
 307         }
 308
 309         internal class DTDAnyAutomata : DTDAutomata
 310         {
 311                 public DTDAnyAutomata (DTDObjectModel root)
 312                         : base (root)
 313                 {
 314                 }
 315
 316                 public override DTDAutomata TryEndElement ()
 317                 {
 318                         return this;
 319                 }
 320
 321                 public override DTDAutomata TryStartElement (string name)
 322                 {
 323                         return this;
 324                 }
 325
 326                 public override bool Emptiable {
 327                         get { return true; }
 328                 }
 329         }
 330
 331         internal class DTDInvalidAutomata : DTDAutomata
 332         {
 333                 public DTDInvalidAutomata (DTDObjectModel root)
 334                         : base (root)
 335                 {
 336                 }
 337
 338                 public override DTDAutomata TryEndElement ()
 339                 {
 340                         return this;
 341                 }
 342
 343                 public override DTDAutomata TryStartElement (string name)
 344                 {
 345                         return this;
 346                 }
 347         }
 348 }