KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xerces > impl > xs > models > CMBuilder


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.apache.xerces.impl.xs.models;
18
19 import org.apache.xerces.impl.dtd.models.CMNode;
20 import org.apache.xerces.impl.xs.SchemaSymbols;
21 import org.apache.xerces.impl.xs.XSComplexTypeDecl;
22 import org.apache.xerces.impl.xs.XSDeclarationPool;
23 import org.apache.xerces.impl.xs.XSElementDecl;
24 import org.apache.xerces.impl.xs.XSModelGroupImpl;
25 import org.apache.xerces.impl.xs.XSParticleDecl;
26
27 /**
28  * This class constructs content models for a given grammar.
29  *
30  * @xerces.internal
31  *
32  * @author Elena Litani, IBM
33  * @author Sandy Gao, IBM
34  *
35  * @version $Id: CMBuilder.java,v 1.23 2004/10/06 15:14:52 mrglavas Exp $
36  */
37 public class CMBuilder {
38
39     // REVISIT: should update the decl pool to cache XSCM objects too
40 private XSDeclarationPool fDeclPool = null;
41
42     // It never changes, so a static member is good enough
43 private static XSEmptyCM fEmptyCM = new XSEmptyCM();
44
45     // needed for DFA construction
46 private int fLeafCount;
47     // needed for UPA
48 private int fParticleCount;
49     //Factory to create Bin, Uni, Leaf nodes
50 private CMNodeFactory fNodeFactory ;
51
52     public CMBuilder(CMNodeFactory nodeFactory) {
53         fDeclPool = null;
54         fNodeFactory = nodeFactory ;
55     }
56
57     public void setDeclPool(XSDeclarationPool declPool) {
58         fDeclPool = declPool;
59     }
60
61     /**
62      * Get content model for the a given type
63      *
64      * @param typeDecl get content model for which complex type
65      * @return a content model validator
66      */
67     public XSCMValidator getContentModel(XSComplexTypeDecl typeDecl) {
68
69         // for complex type with empty or simple content,
70 // there is no content model validator
71 short contentType = typeDecl.getContentType();
72         if (contentType == XSComplexTypeDecl.CONTENTTYPE_SIMPLE ||
73             contentType == XSComplexTypeDecl.CONTENTTYPE_EMPTY) {
74             return null;
75         }
76
77         XSParticleDecl particle = (XSParticleDecl)typeDecl.getParticle();
78
79         // if the content is element only or mixed, but no particle
80 // is defined, return the empty content model
81 if (particle == null)
82             return fEmptyCM;
83
84         // if the content model contains "all" model group,
85 // we create an "all" content model, otherwise a DFA content model
86 XSCMValidator cmValidator = null;
87         if (particle.fType == XSParticleDecl.PARTICLE_MODELGROUP &&
88             ((XSModelGroupImpl)particle.fValue).fCompositor == XSModelGroupImpl.MODELGROUP_ALL) {
89             cmValidator = createAllCM(particle);
90         }
91         else {
92             cmValidator = createDFACM(particle);
93         }
94
95         //now we are throught building content model and have passed sucessfully of the nodecount check
96 //if set by the application
97 fNodeFactory.resetNodeCount() ;
98
99         // if the validator returned is null, it means there is nothing in
100 // the content model, so we return the empty content model.
101 if (cmValidator == null)
102             cmValidator = fEmptyCM;
103
104         return cmValidator;
105     }
106
107     XSCMValidator createAllCM(XSParticleDecl particle) {
108         if (particle.fMaxOccurs == 0)
109             return null;
110
111         // get the model group, and add all children of it to the content model
112 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue;
113         // create an all content model. the parameter indicates whether
114 // the <all> itself is optional
115 XSAllCM allContent = new XSAllCM(particle.fMinOccurs == 0, group.fParticleCount);
116         for (int i = 0; i < group.fParticleCount; i++) {
117             // add the element decl to the all content model
118 allContent.addElement((XSElementDecl)group.fParticles[i].fValue,
119             group.fParticles[i].fMinOccurs == 0);
120         }
121         return allContent;
122     }
123
124     XSCMValidator createDFACM(XSParticleDecl particle) {
125         fLeafCount = 0;
126         fParticleCount = 0;
127         // convert particle tree to CM tree
128 CMNode node = buildSyntaxTree(particle);
129         if (node == null)
130             return null;
131         // build DFA content model from the CM tree
132 return new XSDFACM(node, fLeafCount);
133     }
134
135     // 1. convert particle tree to CM tree:
136 // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+
137 // a{n, m} -> a, a, ..., a?, a?, ...
138 // 3. convert model groups (a, b, c, ...) or (a | b | c | ...) to
139 // binary tree: (((a,b),c),...) or (((a|b)|c)|...)
140 // 4. make sure each leaf node (XSCMLeaf) has a distinct position
141 private CMNode buildSyntaxTree(XSParticleDecl particle) {
142
143         int maxOccurs = particle.fMaxOccurs;
144         int minOccurs = particle.fMinOccurs;
145         short type = particle.fType;
146         CMNode nodeRet = null;
147
148         if ((type == XSParticleDecl.PARTICLE_WILDCARD) ||
149             (type == XSParticleDecl.PARTICLE_ELEMENT)) {
150             // (task 1) element and wildcard particles should be converted to
151 // leaf nodes
152 // REVISIT: Make a clone of the leaf particle, so that if there
153 // are two references to the same group, we have two different
154 // leaf particles for the same element or wildcard decl.
155 // This is useful for checking UPA.
156 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++);
157             // (task 2) expand occurrence values
158 nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs);
159         }
160         else if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
161             // (task 1,3) convert model groups to binary trees
162 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue;
163             CMNode temp = null;
164             // when the model group is a choice of more than one particles, but
165 // only one of the particle is not empty, (for example
166 // <choice>
167 // <sequence/>
168 // <element name="e"/>
169 // </choice>
170 // ) we can't not return that one particle ("e"). instead, we should
171 // treat such particle as optional ("e?").
172 // the following boolean variable is true when there are at least
173 // 2 non-empty children.
174 boolean twoChildren = false;
175             for (int i = 0; i < group.fParticleCount; i++) {
176                 // first convert each child to a CM tree
177 temp = buildSyntaxTree(group.fParticles[i]);
178                 // then combine them using binary operation
179 if (temp != null) {
180                     if (nodeRet == null) {
181                         nodeRet = temp;
182                     }
183                     else {
184                         nodeRet = fNodeFactory.getCMBinOpNode(group.fCompositor, nodeRet, temp);
185                         // record the fact that there are at least 2 children
186 twoChildren = true;
187                     }
188                 }
189             }
190             // (task 2) expand occurrence values
191 if (nodeRet != null) {
192                 // when the group is "choice", there is only one non-empty
193 // child, and the group had more than one children, we need
194 // to create a zero-or-one (optional) node for the non-empty
195 // particle.
196 if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE &&
197                     !twoChildren && group.fParticleCount > 1) {
198                     nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet);
199                 }
200                 nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs);
201             }
202         }
203
204         return nodeRet;
205     }
206
207     // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+
208 // a{n, m} -> a, a, ..., a?, a?, ...
209 // 4. make sure each leaf node (XSCMLeaf) has a distinct position
210 private CMNode expandContentModel(CMNode node,
211                                       int minOccurs, int maxOccurs) {
212
213         CMNode nodeRet = null;
214
215         if (minOccurs==1 && maxOccurs==1) {
216             nodeRet = node;
217         }
218         else if (minOccurs==0 && maxOccurs==1) {
219             //zero or one
220 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, node);
221         }
222         else if (minOccurs == 0 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) {
223             //zero or more
224 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, node);
225         }
226         else if (minOccurs == 1 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) {
227             //one or more
228 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, node);
229         }
230         else if (maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
231             // => a,a,..,a+
232 // create a+ node first, then put minOccurs-1 a's in front of it
233 // for the first time "node" is used, we don't need to make a copy
234 // and for other references to node, we make copies
235 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, node);
236             // (task 4) we need to call copyNode here, so that we append
237 // an entire new copy of the node (a subtree). this is to ensure
238 // all leaf nodes have distinct position
239 // we know that minOccurs > 1
240 nodeRet = fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE,
241                                                   multiNodes(node, minOccurs-1, true), nodeRet);
242         }
243         else {
244             // {n,m} => a,a,a,...(a),(a),...
245 // first n a's, then m-n a?'s.
246 // copyNode is called, for the same reason as above
247 if (minOccurs > 0) {
248                 nodeRet = multiNodes(node, minOccurs, false);
249             }
250             if (maxOccurs > minOccurs) {
251                 node = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, node);
252                 if (nodeRet == null) {
253                     nodeRet = multiNodes(node, maxOccurs-minOccurs, false);
254                 }
255                 else {
256                     nodeRet = fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE,
257                                                           nodeRet, multiNodes(node, maxOccurs-minOccurs, true));
258                 }
259             }
260         }
261
262         return nodeRet;
263     }
264
265     private CMNode multiNodes(CMNode node, int num, boolean copyFirst) {
266         if (num == 0) {
267             return null;
268         }
269         if (num == 1) {
270             return copyFirst ? copyNode(node) : node;
271         }
272         int num1 = num/2;
273         return fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE,
274                                            multiNodes(node, num1, copyFirst),
275                                            multiNodes(node, num-num1, true));
276     }
277
278     // 4. make sure each leaf node (XSCMLeaf) has a distinct position
279 private CMNode copyNode(CMNode node) {
280         int type = node.type();
281         // for choice or sequence, copy the two subtrees, and combine them
282 if (type == XSModelGroupImpl.MODELGROUP_CHOICE ||
283             type == XSModelGroupImpl.MODELGROUP_SEQUENCE) {
284             XSCMBinOp bin = (XSCMBinOp)node;
285             node = fNodeFactory.getCMBinOpNode(type, copyNode(bin.getLeft()),
286                                  copyNode(bin.getRight()));
287         }
288         // for ?+*, copy the subtree, and put it in a new ?+* node
289 else if (type == XSParticleDecl.PARTICLE_ZERO_OR_MORE ||
290                  type == XSParticleDecl.PARTICLE_ONE_OR_MORE ||
291                  type == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
292             XSCMUniOp uni = (XSCMUniOp)node;
293             node = fNodeFactory.getCMUniOpNode(type, copyNode(uni.getChild()));
294         }
295         // for element/wildcard (leaf), make a new leaf node,
296 // with a distinct position
297 else if (type == XSParticleDecl.PARTICLE_ELEMENT ||
298                  type == XSParticleDecl.PARTICLE_WILDCARD) {
299             XSCMLeaf leaf = (XSCMLeaf)node;
300             node = fNodeFactory.getCMLeafNode(leaf.type(), leaf.getLeaf(), leaf.getParticleId(), fLeafCount++);
301         }
302
303         return node;
304     }
305 }
306
Popular Tags