1 /*
2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
3 */
4 /*
5 * Copyright 2001-2005 The Apache Software Foundation.
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20 package com.sun.org.apache.xerces.internal.impl.xs;
21
22 import com.sun.org.apache.xerces.internal.xni.QName;
23 import com.sun.org.apache.xerces.internal.xs.XSConstants;
24 import com.sun.org.apache.xerces.internal.xs.XSObjectList;
25 import com.sun.org.apache.xerces.internal.xs.XSSimpleTypeDefinition;
26 import com.sun.org.apache.xerces.internal.xs.XSTypeDefinition;
27 import java.util.HashMap;
28 import java.util.Map;
29 import java.util.Vector;
30
31 /**
32 * To store and validate information about substitutionGroup
33 *
34 * @xerces.internal
35 *
36 * @author Sandy Gao, IBM
37 *
38 * @version $Id: SubstitutionGroupHandler.java,v 1.6 2010-11-01 04:39:55 joehw Exp $
39 */
40 public class SubstitutionGroupHandler {
41
42 private static final XSElementDecl[] EMPTY_GROUP = new XSElementDecl[0];
43
44 // grammar resolver
45 XSGrammarBucket fGrammarBucket;
46
47 /**
48 * Default constructor
49 */
50 public SubstitutionGroupHandler(XSGrammarBucket grammarBucket) {
51 fGrammarBucket = grammarBucket;
52 }
53
54 // 3.9.4 Element Sequence Locally Valid (Particle) 2.3.3
55 // check whether one element decl matches an element with the given qname
56 public XSElementDecl getMatchingElemDecl(QName element, XSElementDecl exemplar) {
57 if (element.localpart == exemplar.fName &&
58 element.uri == exemplar.fTargetNamespace) {
59 return exemplar;
60 }
61
62 // if the exemplar is not a global element decl, then it's not possible
63 // to be substituted by another element.
64 if (exemplar.fScope != XSConstants.SCOPE_GLOBAL)
65 return null;
66
67 // if the decl blocks substitution, return false
68 if ((exemplar.fBlock & XSConstants.DERIVATION_SUBSTITUTION) != 0)
69 return null;
70
71 // get grammar of the element
72 SchemaGrammar sGrammar = fGrammarBucket.getGrammar(element.uri);
73 if (sGrammar == null)
74 return null;
75
76 // get the decl for the element
77 XSElementDecl eDecl = sGrammar.getGlobalElementDecl(element.localpart);
78 if (eDecl == null)
79 return null;
80
81 // and check by using substitutionGroup information
82 if (substitutionGroupOK(eDecl, exemplar, exemplar.fBlock))
83 return eDecl;
84
85 return null;
86 }
87
88 // 3.3.6 Substitution Group OK (Transitive)
89 // check whether element can substitute exemplar
90 protected boolean substitutionGroupOK(XSElementDecl element, XSElementDecl exemplar, short blockingConstraint) {
91 // 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:
92 // 1. D and C are the same element declaration.
93 if (element == exemplar)
94 return true;
95
96 // 2 All of the following must be true:
97 // 2.1 The blocking constraint does not contain substitution.
98 if ((blockingConstraint & XSConstants.DERIVATION_SUBSTITUTION) != 0)
99 return false;
100
101 // 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 . . .
102 XSElementDecl subGroup = element.fSubGroup;
103 while (subGroup != null && subGroup != exemplar) {
104 subGroup = subGroup.fSubGroup;
105 }
106
107 if (subGroup == null)
108 return false;
109
110 // 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}.
111 // prepare the combination of {derivation method} and
112 // {disallowed substitution}
113 return typeDerivationOK(element.fType, exemplar.fType, blockingConstraint);
114 }
115 private boolean typeDerivationOK(XSTypeDefinition derived, XSTypeDefinition base, short blockingConstraint) {
116
117 short devMethod = 0, blockConstraint = blockingConstraint;
118
119 // "derived" should be derived from "base"
120 // add derivation methods of derived types to devMethod;
121 // add block of base types to blockConstraint.
122 XSTypeDefinition type = derived;
123 while (type != base && type != SchemaGrammar.fAnyType) {
124 if (type.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
125 devMethod |= ((XSComplexTypeDecl)type).fDerivedBy;
126 }
127 else {
128 devMethod |= XSConstants.DERIVATION_RESTRICTION;
129 }
130 type = type.getBaseType();
131 // type == null means the current type is anySimpleType,
132 // whose base type should be anyType
133 if (type == null) {
134 type = SchemaGrammar.fAnyType;
135 }
136 if (type.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
137 blockConstraint |= ((XSComplexTypeDecl)type).fBlock;
138 }
139 }
140 if (type != base) {
141 // If the base is a union, check if "derived" is allowed through any of the member types.
142 if (base.getTypeCategory() == XSTypeDefinition.SIMPLE_TYPE) {
143 XSSimpleTypeDefinition st = (XSSimpleTypeDefinition) base;
144 if (st.getVariety() == XSSimpleTypeDefinition.VARIETY_UNION) {
145 XSObjectList memberTypes = st.getMemberTypes();
146 final int length = memberTypes.getLength();
147 for (int i = 0; i < length; ++i) {
148 if (typeDerivationOK(derived, (XSTypeDefinition) memberTypes.item(i), blockingConstraint)) {
149 return true;
150 }
151 }
152 }
153 }
154 return false;
155 }
156 if ((devMethod & blockConstraint) != 0) {
157 return false;
158 }
159 return true;
160 }
161
162 // check whether element is in exemplar's substitution group
163 public boolean inSubstitutionGroup(XSElementDecl element, XSElementDecl exemplar) {
164 // [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:
165 // Define PSG, the potential substitution group for HEAD, as follows:
166 // 1 The element declaration itself is in PSG;
167 // 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.
168 // HEAD's actual substitution group is then the set consisting of each member of PSG such that all of the following must be true:
169 // 1 Its {abstract} is false.
170 // 2 It is validly substitutable for HEAD subject to an empty blocking constraint, as defined in Substitution Group OK (Transitive) (3.3.6).
171 return substitutionGroupOK(element, exemplar, exemplar.fBlock);
172 }
173
174 // to store substitution group information
175 // the key to the map is an element decl, and the value is
176 // - a Vector, which contains all elements that has this element as their
177 // substitution group affilication
178 // - an array of OneSubGroup, which contains its substitution group before block.
179 Map<XSElementDecl, Object> fSubGroupsB = new HashMap<>();
180 private static final OneSubGroup[] EMPTY_VECTOR = new OneSubGroup[0];
181 // The real substitution groups (after "block")
182 Map<XSElementDecl, XSElementDecl[]> fSubGroups = new HashMap<>();
183
184 /**
185 * clear the internal registry of substitutionGroup information
186 */
187 public void reset() {
188 fSubGroupsB.clear();
189 fSubGroups.clear();
190 }
191
192 /**
193 * add a list of substitution group information.
194 */
195 public void addSubstitutionGroup(XSElementDecl[] elements) {
196 XSElementDecl subHead, element;
197 Vector subGroup;
198 // for all elements with substitution group affiliation
199 for (int i = elements.length-1; i >= 0; i--) {
200 element = elements[i];
201 subHead = element.fSubGroup;
202 // check whether this an entry for this element
203 subGroup = (Vector)fSubGroupsB.get(subHead);
204 if (subGroup == null) {
205 // if not, create a new one
206 subGroup = new Vector();
207 fSubGroupsB.put(subHead, subGroup);
208 }
209 // add to the vactor
210 subGroup.addElement(element);
211 }
212 }
213
214 /**
215 * get all elements that can substitute the given element,
216 * according to the spec, we shouldn't consider the {block} constraints.
217 *
218 * from the spec, substitution group of a given element decl also contains
219 * the element itself. but the array returned from this method doesn't
220 * containt this element.
221 */
222 public XSElementDecl[] getSubstitutionGroup(XSElementDecl element) {
223 // If we already have sub group for this element, just return it.
224 XSElementDecl[] subGroup = fSubGroups.get(element);
225 if (subGroup != null)
226 return subGroup;
227
228 if ((element.fBlock & XSConstants.DERIVATION_SUBSTITUTION) != 0) {
229 fSubGroups.put(element, EMPTY_GROUP);
230 return EMPTY_GROUP;
231 }
232
233 // Otherwise, get all potential sub group elements
234 // (without considering "block" on this element
235 OneSubGroup[] groupB = getSubGroupB(element, new OneSubGroup());
236 int len = groupB.length, rlen = 0;
237 XSElementDecl[] ret = new XSElementDecl[len];
238 // For each of such elements, check whether the derivation methods
239 // overlap with "block". If not, add it to the sub group
240 for (int i = 0 ; i < len; i++) {
241 if ((element.fBlock & groupB[i].dMethod) == 0)
242 ret[rlen++] = groupB[i].sub;
243 }
244 // Resize the array if necessary
245 if (rlen < len) {
246 XSElementDecl[] ret1 = new XSElementDecl[rlen];
247 System.arraycopy(ret, 0, ret1, 0, rlen);
248 ret = ret1;
249 }
250 // Store the subgroup
251 fSubGroups.put(element, ret);
252
253 return ret;
254 }
255
256 // Get potential sub group element (without considering "block")
257 private OneSubGroup[] getSubGroupB(XSElementDecl element, OneSubGroup methods) {
258 Object subGroup = fSubGroupsB.get(element);
259
260 // substitution group for this one is empty
261 if (subGroup == null) {
262 fSubGroupsB.put(element, EMPTY_VECTOR);
263 return EMPTY_VECTOR;
264 }
265
266 // we've already calculated the element, just return.
267 if (subGroup instanceof OneSubGroup[])
268 return (OneSubGroup[])subGroup;
269
270 // we only have the *direct* substitutions
271 Vector group = (Vector)subGroup, newGroup = new Vector();
272 OneSubGroup[] group1;
273 // then for each of the direct substitutions, get its substitution
274 // group, and combine the groups together.
275 short dMethod, bMethod, dSubMethod, bSubMethod;
276 for (int i = group.size()-1, j; i >= 0; i--) {
277 // Check whether this element is blocked. If so, ignore it.
278 XSElementDecl sub = (XSElementDecl)group.elementAt(i);
279 if (!getDBMethods(sub.fType, element.fType, methods))
280 continue;
281 // Remember derivation methods and blocks from the types
282 dMethod = methods.dMethod;
283 bMethod = methods.bMethod;
284 // Add this one to potential group
285 newGroup.addElement(new OneSubGroup(sub, methods.dMethod, methods.bMethod));
286 // Get potential group for this element
287 group1 = getSubGroupB(sub, methods);
288 for (j = group1.length-1; j >= 0; j--) {
289 // For each of them, check whether it's blocked (by type)
290 dSubMethod = (short)(dMethod | group1[j].dMethod);
291 bSubMethod = (short)(bMethod | group1[j].bMethod);
292 // Ignore it if it's blocked
293 if ((dSubMethod & bSubMethod) != 0)
294 continue;
295 newGroup.addElement(new OneSubGroup(group1[j].sub, dSubMethod, bSubMethod));
296 }
297 }
298 // Convert to an array
299 OneSubGroup[] ret = new OneSubGroup[newGroup.size()];
300 for (int i = newGroup.size()-1; i >= 0; i--) {
301 ret[i] = (OneSubGroup)newGroup.elementAt(i);
302 }
303 // Store the potential sub group
304 fSubGroupsB.put(element, ret);
305
306 return ret;
307 }
308
309 private boolean getDBMethods(XSTypeDefinition typed, XSTypeDefinition typeb,
310 OneSubGroup methods) {
311 short dMethod = 0, bMethod = 0;
312 while (typed != typeb && typed != SchemaGrammar.fAnyType) {
313 if (typed.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE)
314 dMethod |= ((XSComplexTypeDecl)typed).fDerivedBy;
315 else
316 dMethod |= XSConstants.DERIVATION_RESTRICTION;
317 typed = typed.getBaseType();
318 // type == null means the current type is anySimpleType,
319 // whose base type should be anyType
320 if (typed == null)
321 typed = SchemaGrammar.fAnyType;
322 if (typed.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE)
323 bMethod |= ((XSComplexTypeDecl)typed).fBlock;
324 }
325 // No derivation relation, or blocked, return false
326 if (typed != typeb || (dMethod & bMethod) != 0)
327 return false;
328
329 // Remember the derivation methods and blocks, return true.
330 methods.dMethod = dMethod;
331 methods.bMethod = bMethod;
332 return true;
333 }
334
335 // Record the information about how one element substitute another one
336 private static final class OneSubGroup {
337 OneSubGroup() {}
338 OneSubGroup(XSElementDecl sub, short dMethod, short bMethod) {
339 this.sub = sub;
340 this.dMethod = dMethod;
341 this.bMethod = bMethod;
342 }
343 // The element that substitutes another one
344 XSElementDecl sub;
345 // The combination of all derivation methods from sub's type to
346 // the head's type
347 short dMethod;
348 // The combination of {block} of the types in the derivation chain
349 // excluding sub's type
350 short bMethod;
351 }
352 } // class SubstitutionGroupHandler