001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package org.apache.xerces.impl.xs.models;
019:
020: import org.apache.xerces.impl.dtd.models.CMNode;
021: import org.apache.xerces.impl.xs.SchemaSymbols;
022: import org.apache.xerces.impl.xs.XSComplexTypeDecl;
023: import org.apache.xerces.impl.xs.XSDeclarationPool;
024: import org.apache.xerces.impl.xs.XSElementDecl;
025: import org.apache.xerces.impl.xs.XSModelGroupImpl;
026: import org.apache.xerces.impl.xs.XSParticleDecl;
027:
028: /**
029: * This class constructs content models for a given grammar.
030: *
031: * @xerces.internal
032: *
033: * @author Elena Litani, IBM
034: * @author Sandy Gao, IBM
035: *
036: * @version $Id: CMBuilder.java 573322 2007-09-06 16:48:47Z peterjm $
037: */
038: public class CMBuilder {
039:
040: // REVISIT: should update the decl pool to cache XSCM objects too
041: private XSDeclarationPool fDeclPool = null;
042:
043: // It never changes, so a static member is good enough
044: private static final XSEmptyCM fEmptyCM = new XSEmptyCM();
045:
046: // needed for DFA construction
047: private int fLeafCount;
048: // needed for UPA
049: private int fParticleCount;
050: //Factory to create Bin, Uni, Leaf nodes
051: private final CMNodeFactory fNodeFactory;
052:
053: public CMBuilder(CMNodeFactory nodeFactory) {
054: fDeclPool = null;
055: fNodeFactory = nodeFactory;
056: }
057:
058: public void setDeclPool(XSDeclarationPool declPool) {
059: fDeclPool = declPool;
060: }
061:
062: /**
063: * Get content model for the a given type
064: *
065: * @param typeDecl get content model for which complex type
066: * @return a content model validator
067: */
068: public XSCMValidator getContentModel(XSComplexTypeDecl typeDecl,
069: boolean forUPA) {
070:
071: // for complex type with empty or simple content,
072: // there is no content model validator
073: short contentType = typeDecl.getContentType();
074: if (contentType == XSComplexTypeDecl.CONTENTTYPE_SIMPLE
075: || contentType == XSComplexTypeDecl.CONTENTTYPE_EMPTY) {
076: return null;
077: }
078:
079: XSParticleDecl particle = (XSParticleDecl) typeDecl
080: .getParticle();
081:
082: // if the content is element only or mixed, but no particle
083: // is defined, return the empty content model
084: if (particle == null)
085: return fEmptyCM;
086:
087: // if the content model contains "all" model group,
088: // we create an "all" content model, otherwise a DFA content model
089: XSCMValidator cmValidator = null;
090: if (particle.fType == XSParticleDecl.PARTICLE_MODELGROUP
091: && ((XSModelGroupImpl) particle.fValue).fCompositor == XSModelGroupImpl.MODELGROUP_ALL) {
092: cmValidator = createAllCM(particle);
093: } else {
094: cmValidator = createDFACM(particle, forUPA);
095: }
096:
097: //now we are throught building content model and have passed sucessfully of the nodecount check
098: //if set by the application
099: fNodeFactory.resetNodeCount();
100:
101: // if the validator returned is null, it means there is nothing in
102: // the content model, so we return the empty content model.
103: if (cmValidator == null)
104: cmValidator = fEmptyCM;
105:
106: return cmValidator;
107: }
108:
109: XSCMValidator createAllCM(XSParticleDecl particle) {
110: if (particle.fMaxOccurs == 0)
111: return null;
112:
113: // get the model group, and add all children of it to the content model
114: XSModelGroupImpl group = (XSModelGroupImpl) particle.fValue;
115: // create an all content model. the parameter indicates whether
116: // the <all> itself is optional
117: XSAllCM allContent = new XSAllCM(particle.fMinOccurs == 0,
118: group.fParticleCount);
119: for (int i = 0; i < group.fParticleCount; i++) {
120: // add the element decl to the all content model
121: allContent.addElement(
122: (XSElementDecl) group.fParticles[i].fValue,
123: group.fParticles[i].fMinOccurs == 0);
124: }
125: return allContent;
126: }
127:
128: XSCMValidator createDFACM(XSParticleDecl particle, boolean forUPA) {
129: fLeafCount = 0;
130: fParticleCount = 0;
131: // convert particle tree to CM tree
132: CMNode node = useRepeatingLeafNodes(particle) ? buildCompactSyntaxTree(particle)
133: : buildSyntaxTree(particle, forUPA);
134: if (node == null)
135: return null;
136: // build DFA content model from the CM tree
137: return new XSDFACM(node, fLeafCount);
138: }
139:
140: // 1. convert particle tree to CM tree:
141: // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+
142: // a{n, m} -> a, a, ..., a?, a?, ...
143: // 3. convert model groups (a, b, c, ...) or (a | b | c | ...) to
144: // binary tree: (((a,b),c),...) or (((a|b)|c)|...)
145: // 4. make sure each leaf node (XSCMLeaf) has a distinct position
146: private CMNode buildSyntaxTree(XSParticleDecl particle,
147: boolean forUPA) {
148:
149: int maxOccurs = particle.fMaxOccurs;
150: int minOccurs = particle.fMinOccurs;
151:
152: boolean compactedForUPA = false;
153: if (forUPA) {
154: // When doing UPA, we reduce the size of the minOccurs/maxOccurs values to make
155: // processing the DFA faster. For UPA the exact values don't matter.
156: if (minOccurs > 1) {
157: if (maxOccurs > minOccurs
158: || particle.getMaxOccursUnbounded()) {
159: minOccurs = 1;
160: compactedForUPA = true;
161: } else { // maxOccurs == minOccurs
162: minOccurs = 2;
163: compactedForUPA = true;
164: }
165: }
166: if (maxOccurs > 1) {
167: maxOccurs = 2;
168: compactedForUPA = true;
169: }
170: }
171:
172: short type = particle.fType;
173: CMNode nodeRet = null;
174:
175: if ((type == XSParticleDecl.PARTICLE_WILDCARD)
176: || (type == XSParticleDecl.PARTICLE_ELEMENT)) {
177: // (task 1) element and wildcard particles should be converted to
178: // leaf nodes
179: // REVISIT: Make a clone of the leaf particle, so that if there
180: // are two references to the same group, we have two different
181: // leaf particles for the same element or wildcard decl.
182: // This is useful for checking UPA.
183: nodeRet = fNodeFactory.getCMLeafNode(particle.fType,
184: particle.fValue, fParticleCount++, fLeafCount++);
185: // (task 2) expand occurrence values
186: nodeRet = expandContentModel(nodeRet, minOccurs, maxOccurs);
187: if (nodeRet != null) {
188: nodeRet.setIsCompactUPAModel(compactedForUPA);
189: }
190: } else if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
191: // (task 1,3) convert model groups to binary trees
192: XSModelGroupImpl group = (XSModelGroupImpl) particle.fValue;
193: CMNode temp = null;
194: // when the model group is a choice of more than one particles, but
195: // only one of the particle is not empty, (for example
196: // <choice>
197: // <sequence/>
198: // <element name="e"/>
199: // </choice>
200: // ) we can't not return that one particle ("e"). instead, we should
201: // treat such particle as optional ("e?").
202: // the following int variable keeps track of the number of non-empty children
203: int count = 0;
204: for (int i = 0; i < group.fParticleCount; i++) {
205: // first convert each child to a CM tree
206: temp = buildSyntaxTree(group.fParticles[i], forUPA);
207: // then combine them using binary operation
208: if (temp != null) {
209: compactedForUPA |= temp.isCompactedForUPA();
210: ++count;
211: if (nodeRet == null) {
212: nodeRet = temp;
213: } else {
214: nodeRet = fNodeFactory.getCMBinOpNode(
215: group.fCompositor, nodeRet, temp);
216: }
217: }
218: }
219: // (task 2) expand occurrence values
220: if (nodeRet != null) {
221: // when the group is "choice" and the group has one or more empty children,
222: // we need to create a zero-or-one (optional) node for the non-empty particles.
223: if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE
224: && count < group.fParticleCount) {
225: nodeRet = fNodeFactory.getCMUniOpNode(
226: XSParticleDecl.PARTICLE_ZERO_OR_ONE,
227: nodeRet);
228: }
229: nodeRet = expandContentModel(nodeRet, minOccurs,
230: maxOccurs);
231: nodeRet.setIsCompactUPAModel(compactedForUPA);
232: }
233: }
234:
235: return nodeRet;
236: }
237:
238: // 2. expand all occurrence values: a{n, unbounded} -> a, a, ..., a+
239: // a{n, m} -> a, a, ..., a?, a?, ...
240: // 4. make sure each leaf node (XSCMLeaf) has a distinct position
241: private CMNode expandContentModel(CMNode node, int minOccurs,
242: int maxOccurs) {
243:
244: CMNode nodeRet = null;
245:
246: if (minOccurs == 1 && maxOccurs == 1) {
247: nodeRet = node;
248: } else if (minOccurs == 0 && maxOccurs == 1) {
249: //zero or one
250: nodeRet = fNodeFactory.getCMUniOpNode(
251: XSParticleDecl.PARTICLE_ZERO_OR_ONE, node);
252: } else if (minOccurs == 0
253: && maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
254: //zero or more
255: nodeRet = fNodeFactory.getCMUniOpNode(
256: XSParticleDecl.PARTICLE_ZERO_OR_MORE, node);
257: } else if (minOccurs == 1
258: && maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
259: //one or more
260: nodeRet = fNodeFactory.getCMUniOpNode(
261: XSParticleDecl.PARTICLE_ONE_OR_MORE, node);
262: } else if (maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
263: // => a,a,..,a+
264: // create a+ node first, then put minOccurs-1 a's in front of it
265: // for the first time "node" is used, we don't need to make a copy
266: // and for other references to node, we make copies
267: nodeRet = fNodeFactory.getCMUniOpNode(
268: XSParticleDecl.PARTICLE_ONE_OR_MORE, node);
269: // (task 4) we need to call copyNode here, so that we append
270: // an entire new copy of the node (a subtree). this is to ensure
271: // all leaf nodes have distinct position
272: // we know that minOccurs > 1
273: nodeRet = fNodeFactory.getCMBinOpNode(
274: XSModelGroupImpl.MODELGROUP_SEQUENCE, multiNodes(
275: node, minOccurs - 1, true), nodeRet);
276: } else {
277: // {n,m} => a,a,a,...(a),(a),...
278: // first n a's, then m-n a?'s.
279: // copyNode is called, for the same reason as above
280: if (minOccurs > 0) {
281: nodeRet = multiNodes(node, minOccurs, false);
282: }
283: if (maxOccurs > minOccurs) {
284: node = fNodeFactory.getCMUniOpNode(
285: XSParticleDecl.PARTICLE_ZERO_OR_ONE, node);
286: if (nodeRet == null) {
287: nodeRet = multiNodes(node, maxOccurs - minOccurs,
288: false);
289: } else {
290: nodeRet = fNodeFactory.getCMBinOpNode(
291: XSModelGroupImpl.MODELGROUP_SEQUENCE,
292: nodeRet, multiNodes(node, maxOccurs
293: - minOccurs, true));
294: }
295: }
296: }
297:
298: return nodeRet;
299: }
300:
301: private CMNode multiNodes(CMNode node, int num, boolean copyFirst) {
302: if (num == 0) {
303: return null;
304: }
305: if (num == 1) {
306: return copyFirst ? copyNode(node) : node;
307: }
308: int num1 = num / 2;
309: return fNodeFactory.getCMBinOpNode(
310: XSModelGroupImpl.MODELGROUP_SEQUENCE, multiNodes(node,
311: num1, copyFirst), multiNodes(node, num - num1,
312: true));
313: }
314:
315: // 4. make sure each leaf node (XSCMLeaf) has a distinct position
316: private CMNode copyNode(CMNode node) {
317: int type = node.type();
318: // for choice or sequence, copy the two subtrees, and combine them
319: if (type == XSModelGroupImpl.MODELGROUP_CHOICE
320: || type == XSModelGroupImpl.MODELGROUP_SEQUENCE) {
321: XSCMBinOp bin = (XSCMBinOp) node;
322: node = fNodeFactory.getCMBinOpNode(type, copyNode(bin
323: .getLeft()), copyNode(bin.getRight()));
324: }
325: // for ?+*, copy the subtree, and put it in a new ?+* node
326: else if (type == XSParticleDecl.PARTICLE_ZERO_OR_MORE
327: || type == XSParticleDecl.PARTICLE_ONE_OR_MORE
328: || type == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
329: XSCMUniOp uni = (XSCMUniOp) node;
330: node = fNodeFactory.getCMUniOpNode(type, copyNode(uni
331: .getChild()));
332: }
333: // for element/wildcard (leaf), make a new leaf node,
334: // with a distinct position
335: else if (type == XSParticleDecl.PARTICLE_ELEMENT
336: || type == XSParticleDecl.PARTICLE_WILDCARD) {
337: XSCMLeaf leaf = (XSCMLeaf) node;
338: node = fNodeFactory.getCMLeafNode(leaf.type(), leaf
339: .getLeaf(), leaf.getParticleId(), fLeafCount++);
340: }
341:
342: return node;
343: }
344:
345: // A special version of buildSyntaxTree() which builds a compact syntax tree
346: // containing compound leaf nodes which carry occurence information. This method
347: // for building the syntax tree is chosen over buildSyntaxTree() when
348: // useRepeatingLeafNodes() returns true.
349: private CMNode buildCompactSyntaxTree(XSParticleDecl particle) {
350: int maxOccurs = particle.fMaxOccurs;
351: int minOccurs = particle.fMinOccurs;
352: short type = particle.fType;
353: CMNode nodeRet = null;
354:
355: if ((type == XSParticleDecl.PARTICLE_WILDCARD)
356: || (type == XSParticleDecl.PARTICLE_ELEMENT)) {
357: return buildCompactSyntaxTree2(particle, minOccurs,
358: maxOccurs);
359: } else if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
360: XSModelGroupImpl group = (XSModelGroupImpl) particle.fValue;
361: if (group.fParticleCount == 1
362: && (minOccurs != 1 || maxOccurs != 1)) {
363: return buildCompactSyntaxTree2(group.fParticles[0],
364: minOccurs, maxOccurs);
365: } else {
366: CMNode temp = null;
367:
368: // when the model group is a choice of more than one particles, but
369: // only one of the particle is not empty, (for example
370: // <choice>
371: // <sequence/>
372: // <element name="e"/>
373: // </choice>
374: // ) we can't not return that one particle ("e"). instead, we should
375: // treat such particle as optional ("e?").
376: // the following int variable keeps track of the number of non-empty children
377: int count = 0;
378: for (int i = 0; i < group.fParticleCount; i++) {
379: // first convert each child to a CM tree
380: temp = buildCompactSyntaxTree(group.fParticles[i]);
381: // then combine them using binary operation
382: if (temp != null) {
383: ++count;
384: if (nodeRet == null) {
385: nodeRet = temp;
386: } else {
387: nodeRet = fNodeFactory.getCMBinOpNode(
388: group.fCompositor, nodeRet, temp);
389: }
390: }
391: }
392: if (nodeRet != null) {
393: // when the group is "choice" and the group has one or more empty children,
394: // we need to create a zero-or-one (optional) node for the non-empty particles.
395: if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE
396: && count < group.fParticleCount) {
397: nodeRet = fNodeFactory.getCMUniOpNode(
398: XSParticleDecl.PARTICLE_ZERO_OR_ONE,
399: nodeRet);
400: }
401: }
402: }
403: }
404: return nodeRet;
405: }
406:
407: private CMNode buildCompactSyntaxTree2(XSParticleDecl particle,
408: int minOccurs, int maxOccurs) {
409: // Convert element and wildcard particles to leaf nodes. Wrap repeating particles in a CMUniOpNode.
410: CMNode nodeRet = null;
411: if (minOccurs == 1 && maxOccurs == 1) {
412: nodeRet = fNodeFactory.getCMLeafNode(particle.fType,
413: particle.fValue, fParticleCount++, fLeafCount++);
414: } else if (minOccurs == 0 && maxOccurs == 1) {
415: // zero or one
416: nodeRet = fNodeFactory.getCMLeafNode(particle.fType,
417: particle.fValue, fParticleCount++, fLeafCount++);
418: nodeRet = fNodeFactory.getCMUniOpNode(
419: XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet);
420: } else if (minOccurs == 0
421: && maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
422: // zero or more
423: nodeRet = fNodeFactory.getCMLeafNode(particle.fType,
424: particle.fValue, fParticleCount++, fLeafCount++);
425: nodeRet = fNodeFactory.getCMUniOpNode(
426: XSParticleDecl.PARTICLE_ZERO_OR_MORE, nodeRet);
427: } else if (minOccurs == 1
428: && maxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED) {
429: // one or more
430: nodeRet = fNodeFactory.getCMLeafNode(particle.fType,
431: particle.fValue, fParticleCount++, fLeafCount++);
432: nodeRet = fNodeFactory.getCMUniOpNode(
433: XSParticleDecl.PARTICLE_ONE_OR_MORE, nodeRet);
434: } else {
435: // {n,m}: Instead of expanding this out, create a compound leaf node which carries the
436: // occurence information and wrap it in the appropriate CMUniOpNode.
437: nodeRet = fNodeFactory.getCMRepeatingLeafNode(
438: particle.fType, particle.fValue, minOccurs,
439: maxOccurs, fParticleCount++, fLeafCount++);
440: if (minOccurs == 0) {
441: nodeRet = fNodeFactory.getCMUniOpNode(
442: XSParticleDecl.PARTICLE_ZERO_OR_MORE, nodeRet);
443: } else {
444: nodeRet = fNodeFactory.getCMUniOpNode(
445: XSParticleDecl.PARTICLE_ONE_OR_MORE, nodeRet);
446: }
447: }
448: return nodeRet;
449: }
450:
451: // This method checks if this particle can be transformed into a compact syntax
452: // tree containing compound leaf nodes which carry occurence information. Currently
453: // it returns true if each model group has minOccurs/maxOccurs == 1 or
454: // contains only one element/wildcard particle with minOccurs/maxOccurs == 1.
455: private boolean useRepeatingLeafNodes(XSParticleDecl particle) {
456: int maxOccurs = particle.fMaxOccurs;
457: int minOccurs = particle.fMinOccurs;
458: short type = particle.fType;
459:
460: if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
461: XSModelGroupImpl group = (XSModelGroupImpl) particle.fValue;
462: if (minOccurs != 1 || maxOccurs != 1) {
463: if (group.fParticleCount == 1) {
464: XSParticleDecl particle2 = (XSParticleDecl) group.fParticles[0];
465: short type2 = particle2.fType;
466: return ((type2 == XSParticleDecl.PARTICLE_ELEMENT || type2 == XSParticleDecl.PARTICLE_WILDCARD)
467: && particle2.fMinOccurs == 1 && particle2.fMaxOccurs == 1);
468: }
469: return (group.fParticleCount == 0);
470: }
471: for (int i = 0; i < group.fParticleCount; ++i) {
472: if (!useRepeatingLeafNodes(group.fParticles[i])) {
473: return false;
474: }
475: }
476: }
477: return true;
478: }
479: }
|