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