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