2 // Mono.Xml.DTDAutomata
5 // Atsushi Enomoto (ginga@kit.hi-ho.ne.jp)
7 // (C)2003 Atsushi Enomoto
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:
19 // The above copyright notice and this permission notice shall be
20 // included in all copies or substantial portions of the Software.
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.
32 using System.Collections;
36 using System.Xml.Schema;
37 using Mono.Xml.Schema;
42 internal class DTDAutomataFactory
44 public DTDAutomataFactory (DTDObjectModel root)
50 Hashtable choiceTable = new Hashtable ();
51 Hashtable sequenceTable = new Hashtable ();
53 public DTDChoiceAutomata Choice (DTDAutomata left, DTDAutomata right)
55 Hashtable rightPool = choiceTable [left] as Hashtable;
56 if (rightPool == null) {
57 rightPool = new Hashtable ();
58 choiceTable [left] = rightPool;
60 DTDChoiceAutomata result = rightPool [right] as DTDChoiceAutomata;
62 result = new DTDChoiceAutomata (root, left, right);
63 rightPool [right] = result;
68 public DTDSequenceAutomata Sequence (DTDAutomata left, DTDAutomata right)
70 Hashtable rightPool = sequenceTable [left] as Hashtable;
71 if (rightPool == null) {
72 rightPool = new Hashtable ();
73 sequenceTable [left] = rightPool;
75 DTDSequenceAutomata result = rightPool [right] as DTDSequenceAutomata;
77 result = new DTDSequenceAutomata (root, left, right);
78 rightPool [right] = result;
84 internal abstract class DTDAutomata
86 public DTDAutomata (DTDObjectModel root)
91 private DTDObjectModel root;
93 public DTDObjectModel Root {
97 public DTDAutomata MakeChoice (DTDAutomata other)
99 if (this == Root.Invalid)
101 if (other == Root.Invalid)
103 if (this == Root.Empty && other == Root.Empty)
105 if (this == Root.Any && other == Root.Any)
107 else if (other == Root.Empty)
108 return Root.Factory.Choice (other, this);
110 return Root.Factory.Choice (this, other);
113 public DTDAutomata MakeSequence (DTDAutomata other)
115 if (this == Root.Invalid || other == Root.Invalid)
117 if (this == Root.Empty)
119 if (other == Root.Empty)
122 return Root.Factory.Sequence (this, other);
125 public abstract DTDAutomata TryStartElement (string name);
126 public virtual DTDAutomata TryEndElement ()
131 public virtual bool Emptiable {
132 get { return false; }
136 internal class DTDElementAutomata : DTDAutomata
138 public DTDElementAutomata (DTDObjectModel root, string name)
150 public override DTDAutomata TryStartElement (string name)
159 internal class DTDChoiceAutomata : DTDAutomata
161 public DTDChoiceAutomata (DTDObjectModel root,
162 DTDAutomata left, DTDAutomata right)
169 private DTDAutomata left;
170 private DTDAutomata right;
172 public DTDAutomata Left {
176 public DTDAutomata Right {
177 get { return right; }
180 public override DTDAutomata TryStartElement (string name)
182 return left.TryStartElement (name).MakeChoice (
183 right.TryStartElement (name));
186 public override DTDAutomata TryEndElement ()
188 return left.TryEndElement ().MakeChoice (right.TryEndElement ());
191 bool hasComputedEmptiable;
192 bool cachedEmptiable;
193 public override bool Emptiable {
195 if (!hasComputedEmptiable) {
196 cachedEmptiable = left.Emptiable ||
198 hasComputedEmptiable = true;
200 return cachedEmptiable;
205 internal class DTDSequenceAutomata : DTDAutomata
207 public DTDSequenceAutomata (DTDObjectModel root,
208 DTDAutomata left, DTDAutomata right)
215 private DTDAutomata left;
216 private DTDAutomata right;
218 public DTDAutomata Left {
222 public DTDAutomata Right {
223 get { return right; }
226 public override DTDAutomata TryStartElement (string name)
228 DTDAutomata afterL = left.TryStartElement (name);
229 DTDAutomata afterR = right.TryStartElement (name);
230 if (afterL == Root.Invalid)
231 return (left.Emptiable) ? afterR : afterL;
233 DTDAutomata whenLeftConsumed = afterL.MakeSequence (right);
235 return afterR.MakeChoice (whenLeftConsumed);
237 return whenLeftConsumed;
240 public override DTDAutomata TryEndElement ()
242 return left.Emptiable ? right : Root.Invalid;
245 bool hasComputedEmptiable;
246 bool cachedEmptiable;
247 public override bool Emptiable {
249 if (!hasComputedEmptiable) {
250 cachedEmptiable = left.Emptiable &&
252 hasComputedEmptiable = true;
254 return cachedEmptiable;
259 internal class DTDOneOrMoreAutomata : DTDAutomata
261 public DTDOneOrMoreAutomata (DTDObjectModel root,
262 DTDAutomata children)
265 this.children = children;
268 private DTDAutomata children;
270 public DTDAutomata Children {
271 get { return children; }
274 public override DTDAutomata TryStartElement (string name)
276 DTDAutomata afterC = children.TryStartElement (name);
277 if (afterC != Root.Invalid)
278 return afterC.MakeSequence (
279 Root.Empty.MakeChoice (this));
284 public override DTDAutomata TryEndElement ()
286 return Emptiable ? children.TryEndElement () : Root.Invalid;
290 internal class DTDEmptyAutomata : DTDAutomata
292 public DTDEmptyAutomata (DTDObjectModel root)
297 public override DTDAutomata TryEndElement ()
302 public override DTDAutomata TryStartElement (string name)
307 public override bool Emptiable {
312 internal class DTDAnyAutomata : DTDAutomata
314 public DTDAnyAutomata (DTDObjectModel root)
319 public override DTDAutomata TryEndElement ()
324 public override DTDAutomata TryStartElement (string name)
329 public override bool Emptiable {
334 internal class DTDInvalidAutomata : DTDAutomata
336 public DTDInvalidAutomata (DTDObjectModel root)
341 public override DTDAutomata TryEndElement ()
346 public override DTDAutomata TryStartElement (string name)