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.
31 using System
.Collections
;
34 using System
.Xml
.Schema
;
35 using Mono
.Xml
.Schema
;
39 internal class DTDAutomataFactory
41 public DTDAutomataFactory (DTDObjectModel root
)
47 Hashtable choiceTable
= new Hashtable ();
48 Hashtable sequenceTable
= new Hashtable ();
50 public DTDChoiceAutomata
Choice (DTDAutomata left
, DTDAutomata right
)
52 Hashtable rightPool
= choiceTable
[left
] as Hashtable
;
53 if (rightPool
== null) {
54 rightPool
= new Hashtable ();
55 choiceTable
[left
] = rightPool
;
57 DTDChoiceAutomata result
= rightPool
[right
] as DTDChoiceAutomata
;
59 result
= new DTDChoiceAutomata (root
, left
, right
);
60 rightPool
[right
] = result
;
65 public DTDSequenceAutomata
Sequence (DTDAutomata left
, DTDAutomata right
)
67 Hashtable rightPool
= sequenceTable
[left
] as Hashtable
;
68 if (rightPool
== null) {
69 rightPool
= new Hashtable ();
70 sequenceTable
[left
] = rightPool
;
72 DTDSequenceAutomata result
= rightPool
[right
] as DTDSequenceAutomata
;
74 result
= new DTDSequenceAutomata (root
, left
, right
);
75 rightPool
[right
] = result
;
81 internal abstract class DTDAutomata
83 public DTDAutomata (DTDObjectModel root
)
88 private DTDObjectModel root
;
90 public DTDObjectModel Root
{
94 public DTDAutomata
MakeChoice (DTDAutomata other
)
96 if (this == Root
.Invalid
)
98 if (other
== Root
.Invalid
)
100 if (this == Root
.Empty
&& other
== Root
.Empty
)
102 if (this == Root
.Any
&& other
== Root
.Any
)
104 else if (other
== Root
.Empty
)
105 return Root
.Factory
.Choice (other
, this);
107 return Root
.Factory
.Choice (this, other
);
110 public DTDAutomata
MakeSequence (DTDAutomata other
)
112 if (this == Root
.Invalid
|| other
== Root
.Invalid
)
114 if (this == Root
.Empty
)
116 if (other
== Root
.Empty
)
119 return Root
.Factory
.Sequence (this, other
);
122 public abstract DTDAutomata
TryStartElement (string name
);
123 public virtual DTDAutomata
TryEndElement ()
128 public virtual bool Emptiable
{
129 get { return false; }
133 internal class DTDElementAutomata
: DTDAutomata
135 public DTDElementAutomata (DTDObjectModel root
, string name
)
147 public override DTDAutomata
TryStartElement (string name
)
156 internal class DTDChoiceAutomata
: DTDAutomata
158 public DTDChoiceAutomata (DTDObjectModel root
,
159 DTDAutomata left
, DTDAutomata right
)
166 private DTDAutomata left
;
167 private DTDAutomata right
;
169 public DTDAutomata Left
{
173 public DTDAutomata Right
{
174 get { return right; }
177 public override DTDAutomata
TryStartElement (string name
)
179 return left
.TryStartElement (name
).MakeChoice (
180 right
.TryStartElement (name
));
183 public override DTDAutomata
TryEndElement ()
185 return left
.TryEndElement ().MakeChoice (right
.TryEndElement ());
188 bool hasComputedEmptiable
;
189 bool cachedEmptiable
;
190 public override bool Emptiable
{
192 if (!hasComputedEmptiable
) {
193 cachedEmptiable
= left
.Emptiable
||
195 hasComputedEmptiable
= true;
197 return cachedEmptiable
;
202 internal class DTDSequenceAutomata
: DTDAutomata
204 public DTDSequenceAutomata (DTDObjectModel root
,
205 DTDAutomata left
, DTDAutomata right
)
212 private DTDAutomata left
;
213 private DTDAutomata right
;
215 public DTDAutomata Left
{
219 public DTDAutomata Right
{
220 get { return right; }
223 public override DTDAutomata
TryStartElement (string name
)
225 DTDAutomata afterL
= left
.TryStartElement (name
);
226 DTDAutomata afterR
= right
.TryStartElement (name
);
227 if (afterL
== Root
.Invalid
)
228 return (left
.Emptiable
) ? afterR
: afterL
;
230 DTDAutomata whenLeftConsumed
= afterL
.MakeSequence (right
);
232 return afterR
.MakeChoice (whenLeftConsumed
);
234 return whenLeftConsumed
;
237 public override DTDAutomata
TryEndElement ()
239 return left
.Emptiable
? right
: Root
.Invalid
;
242 bool hasComputedEmptiable
;
243 bool cachedEmptiable
;
244 public override bool Emptiable
{
246 if (!hasComputedEmptiable
) {
247 cachedEmptiable
= left
.Emptiable
&&
249 hasComputedEmptiable
= true;
251 return cachedEmptiable
;
256 internal class DTDOneOrMoreAutomata
: DTDAutomata
258 public DTDOneOrMoreAutomata (DTDObjectModel root
,
259 DTDAutomata children
)
262 this.children
= children
;
265 private DTDAutomata children
;
267 public DTDAutomata Children
{
268 get { return children; }
271 public override DTDAutomata
TryStartElement (string name
)
273 DTDAutomata afterC
= children
.TryStartElement (name
);
274 if (afterC
!= Root
.Invalid
)
275 return afterC
.MakeSequence (
276 Root
.Empty
.MakeChoice (this));
281 public override DTDAutomata
TryEndElement ()
283 return Emptiable
? children
.TryEndElement () : Root
.Invalid
;
287 internal class DTDEmptyAutomata
: DTDAutomata
289 public DTDEmptyAutomata (DTDObjectModel root
)
294 public override DTDAutomata
TryEndElement ()
299 public override DTDAutomata
TryStartElement (string name
)
304 public override bool Emptiable
{
309 internal class DTDAnyAutomata
: DTDAutomata
311 public DTDAnyAutomata (DTDObjectModel root
)
316 public override DTDAutomata
TryEndElement ()
321 public override DTDAutomata
TryStartElement (string name
)
326 public override bool Emptiable
{
331 internal class DTDInvalidAutomata
: DTDAutomata
333 public DTDInvalidAutomata (DTDObjectModel root
)
338 public override DTDAutomata
TryEndElement ()
343 public override DTDAutomata
TryStartElement (string name
)