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
--- EOF ---