KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 2001-2004 The Apache Software Foundation. All rights
6  * reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Apache Software Foundation (http://www.apache.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Xerces" and "Apache Software Foundation" must
28  * not be used to endorse or promote products derived from this
29  * software without prior written permission. For written
30  * permission, please contact apache@apache.org.
31  *
32  * 5. Products derived from this software may not be called "Apache",
33  * nor may "Apache" appear in their name, without prior written
34  * permission of the Apache Software Foundation.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This software consists of voluntary contributions made by many
51  * individuals on behalf of the Apache Software Foundation and was
52  * originally based on software copyright (c) 2001, International
53  * Business Machines, Inc., http://www.apache.org. For more
54  * information on the Apache Software Foundation, please see
55  * <http://www.apache.org/>.
56  */
57
58 package com.sun.org.apache.xerces.internal.impl.xs.models;
59
60 import com.sun.org.apache.xerces.internal.impl.dtd.models.CMNode;
61 import com.sun.org.apache.xerces.internal.impl.xs.SchemaSymbols;
62 import com.sun.org.apache.xerces.internal.impl.xs.XSComplexTypeDecl;
63 import com.sun.org.apache.xerces.internal.impl.xs.XSDeclarationPool;
64 import com.sun.org.apache.xerces.internal.impl.xs.XSElementDecl;
65 import com.sun.org.apache.xerces.internal.impl.xs.XSModelGroupImpl;
66 import com.sun.org.apache.xerces.internal.impl.xs.XSParticleDecl;
67
68 /**
69  * This class constructs content models for a given grammar.
70  *
71  * @author Elena Litani, IBM
72  * @author Sandy Gao, IBM
73  *
74  * @version $Id: CMBuilder.java,v 1.21 2004/02/03 17:27:45 sandygao Exp $
75  */
76 public class CMBuilder {
77
78     // REVISIT: should update the decl pool to cache XSCM objects too
79 private XSDeclarationPool fDeclPool = null;
80
81     // It never changes, so a static member is good enough
82 private static XSEmptyCM fEmptyCM = new XSEmptyCM();
83
84     // needed for DFA construction
85 private int fLeafCount;
86     // needed for UPA
87 private int fParticleCount;
88     //Factory to create Bin, Uni, Leaf nodes
89 private CMNodeFactory fNodeFactory ;
90
91     public CMBuilder(CMNodeFactory nodeFactory) {
92         fDeclPool = null;
93         fNodeFactory = nodeFactory ;
94     }
95
96     public void setDeclPool(XSDeclarationPool declPool) {
97         fDeclPool = declPool;
98     }
99
100     /**
101      * Get content model for the a given type
102      *
103      * @param typeDecl get content model for which complex type
104      * @return a content model validator
105      */
106     public XSCMValidator getContentModel(XSComplexTypeDecl typeDecl) {
107
108         // for complex type with empty or simple content,
109 // there is no content model validator
110 short contentType = typeDecl.getContentType();
111         if (contentType == XSComplexTypeDecl.CONTENTTYPE_SIMPLE ||
112             contentType == XSComplexTypeDecl.CONTENTTYPE_EMPTY) {
113             return null;
114         }
115
116         XSParticleDecl particle = (XSParticleDecl)typeDecl.getParticle();
117
118         // if the content is element only or mixed, but no particle
119 // is defined, return the empty content model
120 if (particle == null)
121             return fEmptyCM;
122
123         // if the content model contains "all" model group,
124 // we create an "all" content model, otherwise a DFA content model
125 XSCMValidator cmValidator = null;
126         if (particle.fType == XSParticleDecl.PARTICLE_MODELGROUP &&
127             ((XSModelGroupImpl)particle.fValue).fCompositor == XSModelGroupImpl.MODELGROUP_ALL) {
128             cmValidator = createAllCM(particle);
129         }
130         else {
131             cmValidator = createDFACM(particle);
132         }
133
134         //now we are throught building content model and have passed sucessfully of the nodecount check
135 //if set by the application
136 fNodeFactory.resetNodeCount() ;
137
138         // if the validator returned is null, it means there is nothing in
139 // the content model, so we return the empty content model.
140 if (cmValidator == null)
141             cmValidator = fEmptyCM;
142
143         return cmValidator;
144     }
145
146     XSCMValidator createAllCM(XSParticleDecl particle) {
147         if (particle.fMaxOccurs == 0)
148             return null;
149
150         // get the model group, and add all children of it to the content model
151 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue;
152         // create an all content model. the parameter indicates whether
153 // the <all> itself is optional
154 XSAllCM allContent = new XSAllCM(particle.fMinOccurs == 0, group.fParticleCount);
155         for (int i = 0; i < group.fParticleCount; i++) {
156             // add the element decl to the all content model
157 allContent.addElement((XSElementDecl)group.fParticles[i].fValue,
158             group.fParticles[i].fMinOccurs == 0);
159         }
160         return allContent;
161     }
162
163     XSCMValidator createDFACM(XSParticleDecl particle) {
164         fLeafCount = 0;
165         fParticleCount = 0;
166         // convert particle tree to CM tree
167 CMNode node = buildSyntaxTree(particle);
168         if (node == null)
169             return null;
170         // build DFA content model from the CM tree
171 return new XSDFACM(node, fLeafCount);
172     }
173
174     // 1. convert particle tree to CM tree:
175 // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+
176 // a{n, m} -> a, a, ..., a?, a?, ...
177 // 3. convert model groups (a, b, c, ...) or (a | b | c | ...) to
178 // binary tree: (((a,b),c),...) or (((a|b)|c)|...)
179 // 4. make sure each leaf node (XSCMLeaf) has a distinct position
180 private CMNode buildSyntaxTree(XSParticleDecl particle) {
181
182         int maxOccurs = particle.fMaxOccurs;
183         int minOccurs = particle.fMinOccurs;
184         short type = particle.fType;
185         CMNode nodeRet = null;
186
187         if ((type == XSParticleDecl.PARTICLE_WILDCARD) ||
188             (type == XSParticleDecl.PARTICLE_ELEMENT)) {
189             // (task 1) element and wildcard particles should be converted to
190 // leaf nodes
191 // REVISIT: Make a clone of the leaf particle, so that if there
192 // are two references to the same group, we have two different
193 // leaf particles for the same element or wildcard decl.
194 // This is useful for checking UPA.
195 nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++);
196             // (task 2) expand occurrence values
197 nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs);
198         }
199         else if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
200             // (task 1,3) convert model groups to binary trees
201 XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue;
202             CMNode temp = null;
203             // when the model group is a choice of more than one particles, but
204 // only one of the particle is not empty, (for example
205 // <choice>
206 // <sequence/>
207 // <element name="e"/>
208 // </choice>
209 // ) we can't not return that one particle ("e"). instead, we should
210 // treat such particle as optional ("e?").
211 // the following boolean variable is true when there are at least
212 // 2 non-empty children.
213 boolean twoChildren = false;
214             for (int i = 0; i < group.fParticleCount; i++) {
215                 // first convert each child to a CM tree
216 temp = buildSyntaxTree(group.fParticles[i]);
217                 // then combine them using binary operation
218 if (temp != null) {
219                     if (nodeRet == null) {
220                         nodeRet = temp;
221                     }
222                     else {
223                         nodeRet = fNodeFactory.getCMBinOpNode(group.fCompositor, nodeRet, temp);
224                         // record the fact that there are at least 2 children
225 twoChildren = true;
226                     }
227                 }
228             }
229             // (task 2) expand occurrence values
230 if (nodeRet != null) {
231                 // when the group is "choice", there is only one non-empty
232 // child, and the group had more than one children, we need
233 // to create a zero-or-one (optional) node for the non-empty
234 // particle.
235 if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE &&
236                     !twoChildren && group.fParticleCount > 1) {
237                     nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet);
238                 }
239                 nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs);
240             }
241         }
242
243         return nodeRet;
244     }
245
246     // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+
247 // a{n, m} -> a, a, ..., a?, a?, ...
248 // 4. make sure each leaf node (XSCMLeaf) has a distinct position
249 private CMNode expandContentModel(CMNode node,
250                                       int minOccurs, int maxOccurs) {
251
252         CMNode nodeRet = null;
253
254         if (minOccurs==1 && maxOccurs==1) {
255             nodeRet = node;
256         }
257         else if (minOccurs==0 && maxOccurs==1) {
258             //zero or one
259 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, node);
260         }
261         else if (minOccurs == 0 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) {
262             //zero or more
263 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, node);
264         }
265         else if (minOccurs == 1 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) {
266             //one or more
267 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, node);
268         }
269         else if (maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
270             // => a,a,..,a+
271 // create a+ node first, then put minOccurs-1 a's in front of it
272 // for the first time "node" is used, we don't need to make a copy
273 // and for other references to node, we make copies
274 nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, node);
275             // (task 4) we need to call copyNode here, so that we append
276 // an entire new copy of the node (a subtree). this is to ensure
277 // all leaf nodes have distinct position
278 // we know that minOccurs > 1
279 nodeRet = fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE,
280                                                   multiNodes(node, minOccurs-1, true), nodeRet);
281         }
282         else {
283             // {n,m} => a,a,a,...(a),(a),...
284 // first n a's, then m-n a?'s.
285 // copyNode is called, for the same reason as above
286 if (minOccurs > 0) {
287                 nodeRet = multiNodes(node, minOccurs, false);
288             }
289             if (maxOccurs > minOccurs) {
290                 node = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, node);
291                 if (nodeRet == null) {
292                     nodeRet = multiNodes(node, maxOccurs-minOccurs, false);
293                 }
294                 else {
295                     nodeRet = fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE,
296                                                           nodeRet, multiNodes(node, maxOccurs-minOccurs, true));
297                 }
298             }
299         }
300
301         return nodeRet;
302     }
303
304     private CMNode multiNodes(CMNode node, int num, boolean copyFirst) {
305         if (num == 0) {
306             return null;
307         }
308         if (num == 1) {
309             return copyFirst ? copyNode(node) : node;
310         }
311         int num1 = num/2;
312         return fNodeFactory.getCMBinOpNode(XSModelGroupImpl.MODELGROUP_SEQUENCE,
313                                            multiNodes(node, num1, copyFirst),
314                                            multiNodes(node, num-num1, true));
315     }
316
317     // 4. make sure each leaf node (XSCMLeaf) has a distinct position
318 private CMNode copyNode(CMNode node) {
319         int type = node.type();
320         // for choice or sequence, copy the two subtrees, and combine them
321 if (type == XSModelGroupImpl.MODELGROUP_CHOICE ||
322             type == XSModelGroupImpl.MODELGROUP_SEQUENCE) {
323             XSCMBinOp bin = (XSCMBinOp)node;
324             node = fNodeFactory.getCMBinOpNode(type, copyNode(bin.getLeft()),
325                                  copyNode(bin.getRight()));
326         }
327         // for ?+*, copy the subtree, and put it in a new ?+* node
328 else if (type == XSParticleDecl.PARTICLE_ZERO_OR_MORE ||
329                  type == XSParticleDecl.PARTICLE_ONE_OR_MORE ||
330                  type == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
331             XSCMUniOp uni = (XSCMUniOp)node;
332             node = fNodeFactory.getCMUniOpNode(type, copyNode(uni.getChild()));
333         }
334         // for element/wildcard (leaf), make a new leaf node,
335 // with a distinct position
336 else if (type == XSParticleDecl.PARTICLE_ELEMENT ||
337                  type == XSParticleDecl.PARTICLE_WILDCARD) {
338             XSCMLeaf leaf = (XSCMLeaf)node;
339             node = fNodeFactory.getCMLeafNode(leaf.type(), leaf.getLeaf(), leaf.getParticleId(), fLeafCount++);
340         }
341
342         return node;
343     }
344 }
345
Popular Tags