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      */
  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
  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
  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 
 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
 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      */
 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")
 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      */
 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")
 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 
 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 {
 347         OneSubGroup() {}
 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