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
  31 using System;
  32 using System.Collections;
  33 using System.Text;
  34 using System.Xml;
  35 #if !NET_2_1
  36 using System.Xml.Schema;
  37 using Mono.Xml.Schema;
  38 #endif
  39
  40 namespace Mono.Xml
  41 {
  42         internal class DTDAutomataFactory
  43         {
  44                 public DTDAutomataFactory (DTDObjectModel root)
  45                 {
  46                         this.root = root;
  47                 }
  48
  49                 DTDObjectModel root;
  50                 Hashtable choiceTable = new Hashtable ();
  51                 Hashtable sequenceTable = new Hashtable ();
  52
  53                 public DTDChoiceAutomata Choice (DTDAutomata left, DTDAutomata right)
  54                 {
  55                         Hashtable rightPool = choiceTable [left] as Hashtable;
  56                         if (rightPool == null) {
  57                                 rightPool = new Hashtable ();
  58                                 choiceTable [left] = rightPool;
  59                         }
  60                         DTDChoiceAutomata result = rightPool [right] as DTDChoiceAutomata;
  61                         if (result == null) {
  62                                 result = new DTDChoiceAutomata (root, left, right);
  63                                 rightPool [right] = result;
  64                         }
  65                         return result;
  66                 }
  67
  68                 public DTDSequenceAutomata Sequence (DTDAutomata left, DTDAutomata right)
  69                 {
  70                         Hashtable rightPool = sequenceTable [left] as Hashtable;
  71                         if (rightPool == null) {
  72                                 rightPool = new Hashtable ();
  73                                 sequenceTable [left] = rightPool;
  74                         }
  75                         DTDSequenceAutomata result = rightPool [right] as DTDSequenceAutomata;
  76                         if (result == null) {
  77                                 result = new DTDSequenceAutomata (root, left, right);
  78                                 rightPool [right] = result;
  79                         }
  80                         return result;
  81                 }
  82         }
  83
  84         internal abstract class DTDAutomata
  85         {
  86                 public DTDAutomata (DTDObjectModel root)
  87                 {
  88                         this.root = root;
  89                 }
  90
  91                 private DTDObjectModel root;
  92
  93                 public DTDObjectModel Root {
  94                         get { return root; }
  95                 }
  96
  97                 public DTDAutomata MakeChoice (DTDAutomata other)
  98                 {
  99                         if (this == Root.Invalid)
 100                                 return other;
 101                         if (other == Root.Invalid)
 102                                 return this;
 103                         if (this == Root.Empty && other == Root.Empty)
 104                                 return this;
 105                         if (this == Root.Any && other == Root.Any)
 106                                 return this;
 107                         else if (other == Root.Empty)
 108                                 return Root.Factory.Choice (other, this);
 109                         else
 110                                 return Root.Factory.Choice (this, other);
 111                 }
 112
 113                 public DTDAutomata MakeSequence (DTDAutomata other)
 114                 {
 115                         if (this == Root.Invalid || other == Root.Invalid)
 116                                 return Root.Invalid;
 117                         if (this == Root.Empty)
 118                                 return other;
 119                         if (other == Root.Empty)
 120                                 return this;
 121                         else
 122                                 return Root.Factory.Sequence (this, other);
 123                 }
 124
 125                 public abstract DTDAutomata TryStartElement (string name);
 126                 public virtual DTDAutomata TryEndElement ()
 127                 {
 128                         return Root.Invalid;
 129                 }
 130
 131                 public virtual bool Emptiable {
 132                         get { return false; }
 133                 }
 134         }
 135
 136         internal class DTDElementAutomata : DTDAutomata
 137         {
 138                 public DTDElementAutomata (DTDObjectModel root, string name)
 139                         : base (root)
 140                 {
 141                         this.name = name;
 142                 }
 143
 144                 private string name;
 145
 146                 public string Name {
 147                         get { return name; }
 148                 }
 149
 150                 public override DTDAutomata TryStartElement (string name)
 151                 {
 152                         if (name == Name)
 153                                 return Root.Empty;
 154                         else
 155                                 return Root.Invalid;
 156                 }
 157         }
 158
 159         internal class DTDChoiceAutomata : DTDAutomata
 160         {
 161                 public DTDChoiceAutomata (DTDObjectModel root,
 162                         DTDAutomata left, DTDAutomata right)
 163                         : base (root)
 164                 {
 165                         this.left = left;
 166                         this.right = right;
 167                 }
 168
 169                 private DTDAutomata left;
 170                 private DTDAutomata right;
 171
 172                 public DTDAutomata Left {
 173                         get { return left; }
 174                 }
 175
 176                 public DTDAutomata Right {
 177                         get { return right; }
 178                 }
 179
 180                 public override DTDAutomata TryStartElement (string name)
 181                 {
 182                         return left.TryStartElement (name).MakeChoice (
 183                                 right.TryStartElement (name));
 184                 }
 185
 186                 public override DTDAutomata TryEndElement ()
 187                 {
 188                         return left.TryEndElement ().MakeChoice (right.TryEndElement ());
 189                 }
 190
 191                 bool hasComputedEmptiable;
 192                 bool cachedEmptiable;
 193                 public override bool Emptiable {
 194                         get {
 195                                 if (!hasComputedEmptiable) {
 196                                         cachedEmptiable = left.Emptiable ||
 197                                                 right.Emptiable;
 198                                         hasComputedEmptiable = true;
 199                                 }
 200                                 return cachedEmptiable;
 201                         }
 202                 }
 203         }
 204
 205         internal class DTDSequenceAutomata : DTDAutomata
 206         {
 207                 public DTDSequenceAutomata (DTDObjectModel root,
 208                         DTDAutomata left, DTDAutomata right)
 209                         : base (root)
 210                 {
 211                         this.left = left;
 212                         this.right = right;
 213                 }
 214
 215                 private DTDAutomata left;
 216                 private DTDAutomata right;
 217
 218                 public DTDAutomata Left {
 219                         get { return left; }
 220                 }
 221
 222                 public DTDAutomata Right {
 223                         get { return right; }
 224                 }
 225
 226                 public override DTDAutomata TryStartElement (string name)
 227                 {
 228                         DTDAutomata afterL = left.TryStartElement (name);
 229                         DTDAutomata afterR = right.TryStartElement (name);
 230                         if (afterL == Root.Invalid)
 231                                 return (left.Emptiable) ? afterR : afterL;
 232                         // else
 233                         DTDAutomata whenLeftConsumed = afterL.MakeSequence (right);
 234                         if (left.Emptiable)
 235                                 return afterR.MakeChoice (whenLeftConsumed);
 236                         else
 237                                 return whenLeftConsumed;
 238                 }
 239
 240                 public override DTDAutomata TryEndElement ()
 241                 {
 242                         return left.Emptiable ? right : Root.Invalid;
 243                 }
 244
 245                 bool hasComputedEmptiable;
 246                 bool cachedEmptiable;
 247                 public override bool Emptiable {
 248                         get {
 249                                 if (!hasComputedEmptiable) {
 250                                         cachedEmptiable = left.Emptiable &&
 251                                                 right.Emptiable;
 252                                         hasComputedEmptiable = true;
 253                                 }
 254                                 return cachedEmptiable;
 255                         }
 256                 }
 257         }
 258
 259         internal class DTDOneOrMoreAutomata : DTDAutomata
 260         {
 261                 public DTDOneOrMoreAutomata (DTDObjectModel root,
 262                         DTDAutomata children)
 263                         : base (root)
 264                 {
 265                         this.children = children;
 266                 }
 267
 268                 private DTDAutomata children;
 269
 270                 public DTDAutomata Children {
 271                         get { return children; }
 272                 }
 273
 274                 public override DTDAutomata TryStartElement (string name)
 275                 {
 276                         DTDAutomata afterC = children.TryStartElement (name);
 277                         if (afterC != Root.Invalid)
 278                                 return afterC.MakeSequence (
 279                                         Root.Empty.MakeChoice (this));
 280                         else
 281                                 return Root.Invalid;
 282                 }
 283
 284                 public override DTDAutomata TryEndElement ()
 285                 {
 286                         return Emptiable ? children.TryEndElement () : Root.Invalid;
 287                 }
 288         }
 289
 290         internal class DTDEmptyAutomata : DTDAutomata
 291         {
 292                 public DTDEmptyAutomata (DTDObjectModel root)
 293                         : base (root)
 294                 {
 295                 }
 296
 297                 public override DTDAutomata TryEndElement ()
 298                 {
 299                         return this;
 300                 }
 301
 302                 public override DTDAutomata TryStartElement (string name)
 303                 {
 304                         return Root.Invalid;
 305                 }
 306
 307                 public override bool Emptiable {
 308                         get { return true; }
 309                 }
 310         }
 311
 312         internal class DTDAnyAutomata : DTDAutomata
 313         {
 314                 public DTDAnyAutomata (DTDObjectModel root)
 315                         : base (root)
 316                 {
 317                 }
 318
 319                 public override DTDAutomata TryEndElement ()
 320                 {
 321                         return this;
 322                 }
 323
 324                 public override DTDAutomata TryStartElement (string name)
 325                 {
 326                         return this;
 327                 }
 328
 329                 public override bool Emptiable {
 330                         get { return true; }
 331                 }
 332         }
 333
 334         internal class DTDInvalidAutomata : DTDAutomata
 335         {
 336                 public DTDInvalidAutomata (DTDObjectModel root)
 337                         : base (root)
 338                 {
 339                 }
 340
 341                 public override DTDAutomata TryEndElement ()
 342                 {
 343                         return this;
 344                 }
 345
 346                 public override DTDAutomata TryStartElement (string name)
 347                 {
 348                         return this;
 349                 }
 350         }
 351 }