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;
019:
020: import org.apache.xerces.xs.XSConstants;
021: import org.apache.xerces.xs.XSObjectList;
022: import org.apache.xerces.xs.XSSimpleTypeDefinition;
023: import org.apache.xerces.xs.XSTypeDefinition;
024: import org.apache.xerces.xni.QName;
025: import java.util.Hashtable;
026: import java.util.Vector;
027:
028: /**
029: * To store and validate information about substitutionGroup
030: *
031: * @xerces.internal
032: *
033: * @author Sandy Gao, IBM
034: *
035: * @version $Id: SubstitutionGroupHandler.java 520257 2007-03-20 03:37:12Z mrglavas $
036: */
037: public class SubstitutionGroupHandler {
038:
039: private static final XSElementDecl[] EMPTY_GROUP = new XSElementDecl[0];
040:
041: // grammar resolver
042: XSGrammarBucket fGrammarBucket;
043:
044: /**
045: * Default constructor
046: */
047: public SubstitutionGroupHandler(XSGrammarBucket grammarBucket) {
048: fGrammarBucket = grammarBucket;
049: }
050:
051: // 3.9.4 Element Sequence Locally Valid (Particle) 2.3.3
052: // check whether one element decl matches an element with the given qname
053: public XSElementDecl getMatchingElemDecl(QName element,
054: XSElementDecl exemplar) {
055: if (element.localpart == exemplar.fName
056: && element.uri == exemplar.fTargetNamespace) {
057: return exemplar;
058: }
059:
060: // if the exemplar is not a global element decl, then it's not possible
061: // to be substituted by another element.
062: if (exemplar.fScope != XSConstants.SCOPE_GLOBAL) {
063: return null;
064: }
065:
066: // if the decl blocks substitution, return false
067: if ((exemplar.fBlock & XSConstants.DERIVATION_SUBSTITUTION) != 0) {
068: return null;
069: }
070:
071: // get grammar of the element
072: SchemaGrammar sGrammar = fGrammarBucket.getGrammar(element.uri);
073: if (sGrammar == null) {
074: return null;
075: }
076:
077: // get the decl for the element
078: XSElementDecl eDecl = sGrammar
079: .getGlobalElementDecl(element.localpart);
080: if (eDecl == null) {
081: return null;
082: }
083:
084: // and check by using substitutionGroup information
085: if (substitutionGroupOK(eDecl, exemplar, exemplar.fBlock)) {
086: return eDecl;
087: }
088:
089: return null;
090: }
091:
092: // 3.3.6 Substitution Group OK (Transitive)
093: // check whether element can substitute exemplar
094: protected boolean substitutionGroupOK(XSElementDecl element,
095: XSElementDecl exemplar, short blockingConstraint) {
096: // For an element declaration (call it D) to be validly substitutable for another element declaration (call it C) subject to a blocking constraint (a subset of {substitution, extension, restriction}, the value of a {disallowed substitutions}) one of the following must be true:
097: // 1. D and C are the same element declaration.
098: if (element == exemplar) {
099: return true;
100: }
101:
102: // 2 All of the following must be true:
103: // 2.1 The blocking constraint does not contain substitution.
104: if ((blockingConstraint & XSConstants.DERIVATION_SUBSTITUTION) != 0) {
105: return false;
106: }
107:
108: // 2.2 There is a chain of {substitution group affiliation}s from D to C, that is, either D's {substitution group affiliation} is C, or D's {substitution group affiliation}'s {substitution group affiliation} is C, or . . .
109: XSElementDecl subGroup = element.fSubGroup;
110: while (subGroup != null && subGroup != exemplar) {
111: subGroup = subGroup.fSubGroup;
112: }
113:
114: if (subGroup == null) {
115: return false;
116: }
117:
118: // 2.3 The set of all {derivation method}s involved in the derivation of D's {type definition} from C's {type definition} does not intersect with the union of the blocking constraint, C's {prohibited substitutions} (if C is complex, otherwise the empty set) and the {prohibited substitutions} (respectively the empty set) of any intermediate {type definition}s in the derivation of D's {type definition} from C's {type definition}.
119: // prepare the combination of {derivation method} and
120: // {disallowed substitution}
121: return typeDerivationOK(element.fType, exemplar.fType,
122: blockingConstraint);
123: }
124:
125: private boolean typeDerivationOK(XSTypeDefinition derived,
126: XSTypeDefinition base, short blockingConstraint) {
127:
128: short devMethod = 0, blockConstraint = blockingConstraint;
129:
130: // "derived" should be derived from "base"
131: // add derivation methods of derived types to devMethod;
132: // add block of base types to blockConstraint.
133: XSTypeDefinition type = derived;
134: while (type != base && type != SchemaGrammar.fAnyType) {
135: if (type.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
136: devMethod |= ((XSComplexTypeDecl) type).fDerivedBy;
137: } else {
138: devMethod |= XSConstants.DERIVATION_RESTRICTION;
139: }
140: type = type.getBaseType();
141: // type == null means the current type is anySimpleType,
142: // whose base type should be anyType
143: if (type == null) {
144: type = SchemaGrammar.fAnyType;
145: }
146: if (type.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
147: blockConstraint |= ((XSComplexTypeDecl) type).fBlock;
148: }
149: }
150: if (type != base) {
151: // If the base is a union, check if "derived" is allowed through any of the member types.
152: if (base.getTypeCategory() == XSTypeDefinition.SIMPLE_TYPE) {
153: XSSimpleTypeDefinition st = (XSSimpleTypeDefinition) base;
154: if (st.getVariety() == XSSimpleTypeDefinition.VARIETY_UNION) {
155: XSObjectList memberTypes = st.getMemberTypes();
156: final int length = memberTypes.getLength();
157: for (int i = 0; i < length; ++i) {
158: if (typeDerivationOK(derived,
159: (XSTypeDefinition) memberTypes.item(i),
160: blockingConstraint)) {
161: return true;
162: }
163: }
164: }
165: }
166: return false;
167: }
168: if ((devMethod & blockConstraint) != 0) {
169: return false;
170: }
171: return true;
172: }
173:
174: // check whether element is in exemplar's substitution group
175: public boolean inSubstitutionGroup(XSElementDecl element,
176: XSElementDecl exemplar) {
177: // [Definition:] Every element declaration (call this HEAD) in the {element declarations} of a schema defines a substitution group, a subset of those {element declarations}, as follows:
178: // Define PSG, the potential substitution group for HEAD, as follows:
179: // 1 The element declaration itself is in PSG;
180: // 2 PSG is closed with respect to {substitution group affiliation}, that is, if any element declaration in the {element declarations} has a {substitution group affiliation} in PSG, then it is also in PSG itself.
181: // HEAD's actual substitution group is then the set consisting of each member of PSG such that all of the following must be true:
182: // 1 Its {abstract} is false.
183: // 2 It is validly substitutable for HEAD subject to an empty blocking constraint, as defined in Substitution Group OK (Transitive) (3.3.6).
184: return substitutionGroupOK(element, exemplar, exemplar.fBlock);
185: }
186:
187: // to store substitution group information
188: // the key to the hashtable is an element decl, and the value is
189: // - a Vector, which contains all elements that has this element as their
190: // substitution group affilication
191: // - an array of OneSubGroup, which contains its substitution group before block.
192: Hashtable fSubGroupsB = new Hashtable();
193: private static final OneSubGroup[] EMPTY_VECTOR = new OneSubGroup[0];
194: // The real substitution groups (after "block")
195: Hashtable fSubGroups = new Hashtable();
196:
197: /**
198: * clear the internal registry of substitutionGroup information
199: */
200: public void reset() {
201: fSubGroupsB.clear();
202: fSubGroups.clear();
203: }
204:
205: /**
206: * add a list of substitution group information.
207: */
208: public void addSubstitutionGroup(XSElementDecl[] elements) {
209: XSElementDecl subHead, element;
210: Vector subGroup;
211: // for all elements with substitution group affiliation
212: for (int i = elements.length - 1; i >= 0; i--) {
213: element = elements[i];
214: subHead = element.fSubGroup;
215: // check whether this an entry for this element
216: subGroup = (Vector) fSubGroupsB.get(subHead);
217: if (subGroup == null) {
218: // if not, create a new one
219: subGroup = new Vector();
220: fSubGroupsB.put(subHead, subGroup);
221: }
222: // add to the vactor
223: subGroup.addElement(element);
224: }
225: }
226:
227: /**
228: * get all elements that can substitute the given element,
229: * according to the spec, we shouldn't consider the {block} constraints.
230: *
231: * from the spec, substitution group of a given element decl also contains
232: * the element itself. but the array returned from this method doesn't
233: * containt this element.
234: */
235: public XSElementDecl[] getSubstitutionGroup(XSElementDecl element) {
236: // If we already have sub group for this element, just return it.
237: Object subGroup = fSubGroups.get(element);
238: if (subGroup != null)
239: return (XSElementDecl[]) subGroup;
240:
241: if ((element.fBlock & XSConstants.DERIVATION_SUBSTITUTION) != 0) {
242: fSubGroups.put(element, EMPTY_GROUP);
243: return EMPTY_GROUP;
244: }
245:
246: // Otherwise, get all potential sub group elements
247: // (without considering "block" on this element
248: OneSubGroup[] groupB = getSubGroupB(element, new OneSubGroup());
249: int len = groupB.length, rlen = 0;
250: XSElementDecl[] ret = new XSElementDecl[len];
251: // For each of such elements, check whether the derivation methods
252: // overlap with "block". If not, add it to the sub group
253: for (int i = 0; i < len; i++) {
254: if ((element.fBlock & groupB[i].dMethod) == 0)
255: ret[rlen++] = groupB[i].sub;
256: }
257: // Resize the array if necessary
258: if (rlen < len) {
259: XSElementDecl[] ret1 = new XSElementDecl[rlen];
260: System.arraycopy(ret, 0, ret1, 0, rlen);
261: ret = ret1;
262: }
263: // Store the subgroup
264: fSubGroups.put(element, ret);
265:
266: return ret;
267: }
268:
269: // Get potential sub group element (without considering "block")
270: private OneSubGroup[] getSubGroupB(XSElementDecl element,
271: OneSubGroup methods) {
272: Object subGroup = fSubGroupsB.get(element);
273:
274: // substitution group for this one is empty
275: if (subGroup == null) {
276: fSubGroupsB.put(element, EMPTY_VECTOR);
277: return EMPTY_VECTOR;
278: }
279:
280: // we've already calculated the element, just return.
281: if (subGroup instanceof OneSubGroup[])
282: return (OneSubGroup[]) subGroup;
283:
284: // we only have the *direct* substitutions
285: Vector group = (Vector) subGroup, newGroup = new Vector();
286: OneSubGroup[] group1;
287: // then for each of the direct substitutions, get its substitution
288: // group, and combine the groups together.
289: short dMethod, bMethod, dSubMethod, bSubMethod;
290: for (int i = group.size() - 1, j; i >= 0; i--) {
291: // Check whether this element is blocked. If so, ignore it.
292: XSElementDecl sub = (XSElementDecl) group.elementAt(i);
293: if (!getDBMethods(sub.fType, element.fType, methods))
294: continue;
295: // Remember derivation methods and blocks from the types
296: dMethod = methods.dMethod;
297: bMethod = methods.bMethod;
298: // Add this one to potential group
299: newGroup.addElement(new OneSubGroup(sub, methods.dMethod,
300: methods.bMethod));
301: // Get potential group for this element
302: group1 = getSubGroupB(sub, methods);
303: for (j = group1.length - 1; j >= 0; j--) {
304: // For each of them, check whether it's blocked (by type)
305: dSubMethod = (short) (dMethod | group1[j].dMethod);
306: bSubMethod = (short) (bMethod | group1[j].bMethod);
307: // Ignore it if it's blocked
308: if ((dSubMethod & bSubMethod) != 0)
309: continue;
310: newGroup.addElement(new OneSubGroup(group1[j].sub,
311: dSubMethod, bSubMethod));
312: }
313: }
314: // Convert to an array
315: OneSubGroup[] ret = new OneSubGroup[newGroup.size()];
316: for (int i = newGroup.size() - 1; i >= 0; i--) {
317: ret[i] = (OneSubGroup) newGroup.elementAt(i);
318: }
319: // Store the potential sub group
320: fSubGroupsB.put(element, ret);
321:
322: return ret;
323: }
324:
325: private boolean getDBMethods(XSTypeDefinition typed,
326: XSTypeDefinition typeb, OneSubGroup methods) {
327: short dMethod = 0, bMethod = 0;
328: while (typed != typeb && typed != SchemaGrammar.fAnyType) {
329: if (typed.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE)
330: dMethod |= ((XSComplexTypeDecl) typed).fDerivedBy;
331: else
332: dMethod |= XSConstants.DERIVATION_RESTRICTION;
333: typed = typed.getBaseType();
334: // type == null means the current type is anySimpleType,
335: // whose base type should be anyType
336: if (typed == null)
337: typed = SchemaGrammar.fAnyType;
338: if (typed.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE)
339: bMethod |= ((XSComplexTypeDecl) typed).fBlock;
340: }
341: // No derivation relation, or blocked, return false
342: if (typed != typeb || (dMethod & bMethod) != 0)
343: return false;
344:
345: // Remember the derivation methods and blocks, return true.
346: methods.dMethod = dMethod;
347: methods.bMethod = bMethod;
348: return true;
349: }
350:
351: // Record the information about how one element substitute another one
352: private static final class OneSubGroup {
353: OneSubGroup() {
354: }
355:
356: OneSubGroup(XSElementDecl sub, short dMethod, short bMethod) {
357: this .sub = sub;
358: this .dMethod = dMethod;
359: this .bMethod = bMethod;
360: }
361:
362: // The element that substitutes another one
363: XSElementDecl sub;
364: // The combination of all derivation methods from sub's type to
365: // the head's type
366: short dMethod;
367: // The combination of {block} of the types in the derivation chain
368: // excluding sub's type
369: short bMethod;
370: }
371: } // class SubstitutionGroupHandler
|