gerrit.o-ran-sc Code Review - smo/teiv.git/blob

   1 /*
   2  *  ============LICENSE_START=======================================================
   3  *  Copyright (C) 2024 Ericsson
   4  *  Modifications Copyright (C) 2024 OpenInfra Foundation Europe
   5  *  ================================================================================
   6  *  Licensed under the Apache License, Version 2.0 (the "License");
   7  *  you may not use this file except in compliance with the License.
   8  *  You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  *  Unless required by applicable law or agreed to in writing, software
  13  *  distributed under the License is distributed on an "AS IS" BASIS,
  14  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  *  See the License for the specific language governing permissions and
  16  *  limitations under the License.
  17  *
  18  *  SPDX-License-Identifier: Apache-2.0
  19  *  ============LICENSE_END=========================================================
  20  */
  21 package org.oran.smo.yangtools.parser.model.resolvers;
  22
  23 import java.util.Arrays;
  24 import java.util.Collections;
  25 import java.util.HashSet;
  26 import java.util.List;
  27 import java.util.Objects;
  28 import java.util.Set;
  29 import java.util.stream.Collectors;
  30
  31 import org.oran.smo.yangtools.parser.ParserExecutionContext;
  32 import org.oran.smo.yangtools.parser.findings.Finding;
  33 import org.oran.smo.yangtools.parser.findings.ParserFindingType;
  34 import org.oran.smo.yangtools.parser.model.schema.Schema;
  35 import org.oran.smo.yangtools.parser.model.statements.AbstractStatement;
  36 import org.oran.smo.yangtools.parser.model.statements.ExtensionStatement;
  37 import org.oran.smo.yangtools.parser.model.statements.StatementFactory;
  38 import org.oran.smo.yangtools.parser.model.statements.StatementModuleAndName;
  39 import org.oran.smo.yangtools.parser.model.statements.ExtensionStatement.MaxCardinality;
  40 import org.oran.smo.yangtools.parser.model.statements.yang.CY;
  41 import org.oran.smo.yangtools.parser.model.statements.yang.YDeviate;
  42 import org.oran.smo.yangtools.parser.model.statements.yang.YDeviate.DeviateType;
  43 import org.oran.smo.yangtools.parser.model.statements.yang.YDeviation;
  44 import org.oran.smo.yangtools.parser.model.statements.yang.YMaxElements;
  45 import org.oran.smo.yangtools.parser.model.statements.yang.YMinElements;
  46 import org.oran.smo.yangtools.parser.model.statements.yang.YType;
  47 import org.oran.smo.yangtools.parser.model.util.StringHelper;
  48 import org.oran.smo.yangtools.parser.util.QNameHelper;
  49
  50 /**
  51  * Resolves 'deviation' statements.
  52  *
  53  * @author Mark Hollmann
  54  */
  55 public abstract class DeviationResolver {
  56
  57     /*
  58      * A note on how properties and statements are handled. Some properties for data nodes *always* exist,
  59      * even though their corresponding statements may not be listed in the YAM. For example, a data node
  60      * will always have a 'config' property, which may or may not be explicitly set by means of a statement
  61      * in the YAM. Technically, those properties cannot be ADDED or DELETED vi a deviate, only REPLACED.
  62      * This is not clear in the spec; but was clarified as part of a discussion on the netmod mailing list:
  63      * <p/>
  64      * "I think that config, mandatory, type, max-elements, min-elements cannot be added or
  65      *  deleted, only replaced, because they always exist."
  66      * <p/>
  67      * However, most YAM designers are not aware of this, and will use a deviate add/remove for these
  68      * properties. To avoid noise we are lenient in the code and will allow any of deviate
  69      * add/replace/remove for these properties.
  70      */
  71     private static final Set<StatementModuleAndName> PROPERTIES_THAT_ALWAYS_EXIST = new HashSet<>(Arrays.asList(
  72             CY.STMT_CONFIG, CY.STMT_MANDATORY, CY.STMT_TYPE, CY.STMT_MAX_ELEMENTS, CY.STMT_MIN_ELEMENTS));
  73
  74     /**
  75      * Resolves all deviates by applying the deviate operation against the respective target nodes.
  76      */
  77     public static void resolveDeviates(final ParserExecutionContext context, final Schema schema) {
  78
  79         @SuppressWarnings("unchecked") final List<YDeviation> allDeviations = (List<YDeviation>) Helper
  80                 .findStatementsAtModuleRootInSchema(CY.STMT_DEVIATION, schema);
  81
  82         /*
  83          * This is done in a certain order, to facilitate multiple deviations affecting
  84          * each other. E.g., a deviation may replace a property added by another deviation.
  85          */
  86         for (final YDeviation deviation : allDeviations) {
  87             resolveDeviation(context, deviation, YDeviate.DeviateType.ADD, schema);
  88         }
  89         for (final YDeviation deviation : allDeviations) {
  90             resolveDeviation(context, deviation, YDeviate.DeviateType.REPLACE, schema);
  91         }
  92         for (final YDeviation deviation : allDeviations) {
  93             resolveDeviation(context, deviation, YDeviate.DeviateType.DELETE, schema);
  94         }
  95         for (final YDeviation deviation : allDeviations) {
  96             resolveDeviation(context, deviation, YDeviate.DeviateType.NOT_SUPPORTED, schema);
  97         }
  98     }
  99
 100     private static void resolveDeviation(final ParserExecutionContext context, final YDeviation deviation,
 101             final DeviateType deviateTypeToProcess, final Schema schema) {
 102
 103         final String deviationTargetNode = deviation.getDeviationTargetNode();
 104         if (deviationTargetNode.isEmpty() || !deviationTargetNode.startsWith("/")) {
 105             /*
 106              * Pointless trying to resolve the path. No point issuing a finding either, a
 107              * P015_INVALID_SYNTAX_IN_DOCUMENT would have been issued already.
 108              */
 109             return;
 110         }
 111
 112         final AbstractStatement deviationTarget = findTargetSchemaNode(context, deviation, schema);
 113         if (deviationTarget == null) {
 114             /*
 115              * It is possible that the deviation is trying to remove parts of the tree that
 116              * have already been removed by a different deviation. If that's the case, we
 117              * simply continue.
 118              */
 119             if (deviateTypeToProcess == DeviateType.NOT_SUPPORTED && deviationRefersToPreviouslyRemovedSchemaNode(context,
 120                     deviation, schema)) {
 121                 /* do nothing */
 122             } else {
 123                 context.addFinding(new Finding(deviation, ParserFindingType.P054_UNRESOLVABLE_PATH,
 124                         "Path to schema node '" + deviation
 125                                 .getDeviationTargetNode() + "', part of 'deviation' statement, cannot be resolved."));
 126             }
 127
 128             return;
 129         }
 130
 131         for (final YDeviate deviate : deviation.getDeviates()) {
 132             if (deviateTypeToProcess == deviate.getDeviateType()) {
 133                 handleDeviate(context, deviate, deviationTarget);
 134             }
 135         }
 136     }
 137
 138     private static void handleDeviate(final ParserExecutionContext context, final YDeviate deviate,
 139             final AbstractStatement deviationTarget) {
 140
 141         if (deviate.getDeviateType() == DeviateType.ADD || deviate.getDeviateType() == DeviateType.REPLACE) {
 142             /*
 143              * Run a check first to see whether the statements underneath the 'deviate add/replace' are
 144              * actually allowed as children of the statement that is the target of the deviation. The RFC
 145              * says that handling of extensions is not defined; we assume that any extension listed under
 146              * a deviate add/replace is meant to be handled such.
 147              */
 148             final List<String> statementsAllowedAsChild = deviationTarget.getStatementsAllowedAsChild();
 149             boolean illegalChildFound = false;
 150
 151             for (final AbstractStatement childOfDeviate : deviate.getChildStatements()) {
 152                 if (!childOfDeviate.isExtension() && !statementsAllowedAsChild.contains(childOfDeviate.getDomElement()
 153                         .getName())) {
 154                     illegalChildFound = true;
 155                     context.addFinding(new Finding(childOfDeviate, ParserFindingType.P018_ILLEGAL_CHILD_STATEMENT,
 156                             "Statement '" + childOfDeviate
 157                                     .getStatementName() + "' not a valid child statement of deviated statement '" + deviationTarget
 158                                             .getStatementName()));
 159                 }
 160                 if (childOfDeviate.isExtension() && !((ExtensionStatement) childOfDeviate).canBeChildOf(deviationTarget
 161                         .getStatementModuleAndName())) {
 162                     illegalChildFound = true;
 163                     context.addFinding(new Finding(childOfDeviate, ParserFindingType.P018_ILLEGAL_CHILD_STATEMENT,
 164                             "Extension '" + childOfDeviate
 165                                     .getStatementName() + "' not a valid child statement of deviated statement '" + deviationTarget
 166                                             .getStatementName()));
 167                 }
 168             }
 169
 170             if (illegalChildFound) {
 171                 addDeviateInfo(deviate, "'deviate' has not been applied due to findings.");
 172                 return;
 173             }
 174         }
 175
 176         /*
 177          * Now manipulate the tree in accordance with the deviate operation.
 178          */
 179         switch (deviate.getDeviateType()) {
 180             case NOT_SUPPORTED:
 181                 handleDeviateNotSupported(deviationTarget, deviate);
 182                 break;
 183             case ADD:
 184                 handleDeviateAdd(context, deviationTarget, deviate);
 185                 break;
 186             case DELETE:
 187                 handleDeviateDelete(context, deviationTarget, deviate);
 188                 break;
 189             case REPLACE:
 190                 handleDeviateReplace(context, deviationTarget, deviate);
 191                 break;
 192         }
 193
 194         addDeviateInfo(deviate, "'deviate' has been applied.");
 195     }
 196
 197     private static void handleDeviateDelete(final ParserExecutionContext context, final AbstractStatement deviationTarget,
 198             final YDeviate deviate) {
 199         /*
 200          * From the RFC:
 201          *
 202          * The argument "delete" deletes properties from the target node. The
 203          * properties to delete are identified by substatements to the "delete"
 204          * statement. The substatement’s keyword MUST match a corresponding
 205          * keyword in the target node, and the argument’s string MUST be equal
 206          * to the corresponding keyword’s argument string in the target node.
 207          */
 208
 209         /*
 210          * So we need to get the child statements of the "deviate delete" statement,
 211          * and try to match these up against the child statements of the deviated statement.
 212          * "Match up" means the statement type must be the exact same, and the statements
 213          * value must be the exact same.
 214          */
 215         for (final AbstractStatement childOfDeviate : deviate.getChildStatements()) {
 216             deleteStatementFromUnderDeviatedStatement(context, deviationTarget, childOfDeviate, deviate);
 217         }
 218     }
 219
 220     private static void deleteStatementFromUnderDeviatedStatement(final ParserExecutionContext context,
 221             final AbstractStatement deviationTarget, final AbstractStatement statementToDelete, final YDeviate deviate) {
 222
 223         boolean matchFound = false;
 224         final List<? extends AbstractStatement> statementsOfTypeUnderDeviationTarget = deviationTarget.getChildren(
 225                 statementToDelete.getStatementModuleAndName());
 226
 227         for (final AbstractStatement childOfDeviationTarget : statementsOfTypeUnderDeviationTarget) {
 228             if (statementValuesAreSame(statementToDelete, childOfDeviationTarget)) {
 229                 /*
 230                  * We do a check first to see how many instances of the statement would be left after we delete the statement.
 231                  * If 0, and the statement is mandatory, that's a finding. We ignore extensions, as extensions (by definition)
 232                  * can never be mandatory.
 233                  */
 234                 final int newOccurenceCount = statementsOfTypeUnderDeviationTarget.size() - 1;
 235                 if (newOccurenceCount == 0 && !statementToDelete.isExtension()) {
 236                     final String statementName = statementToDelete.getDomElement().getName();
 237                     if (deviationTarget.getMandatorySingleChildStatementNames().contains(statementName) || deviationTarget
 238                             .getMandatoryMultipleChildStatementNames().contains(statementName)) {
 239                         context.addFinding(new Finding(statementToDelete,
 240                                 ParserFindingType.P166_DEVIATE_RESULTS_IN_CHILD_CARDINALITY_VIOLATION,
 241                                 "Cannot 'deviate delete' this statement as at least a single '" + statementToDelete
 242                                         .getStatementName() + "' statement is required under deviated statement '" + deviationTarget
 243                                                 .getStatementName() + "'."));
 244                         return;
 245                     }
 246                 }
 247
 248                 if (statementHasBeenAddedInByDeviateAdd(childOfDeviationTarget)) {
 249                     context.addFinding(new Finding(statementToDelete,
 250                             ParserFindingType.P165_DEVIATE_DELETE_OF_DEVIATED_STATEMENT, "Deletes a '" + statementToDelete
 251                                     .getStatementName() + "' statement that was previously added by a separate 'deviate add' operation."));
 252                 } else if (statementHasBeenAddedInByDeviateReplace(childOfDeviationTarget)) {
 253                     context.addFinding(new Finding(statementToDelete,
 254                             ParserFindingType.P165_DEVIATE_DELETE_OF_DEVIATED_STATEMENT, "Deletes a '" + statementToDelete
 255                                     .getStatementName() + "' statement that was previously replaced by a separate 'deviate replace' operation."));
 256                 }
 257
 258                 addDeviationHistory(deviationTarget, DeviationHistory.delete(childOfDeviationTarget, statementToDelete));
 259                 addDeviateInfo(deviationTarget, "statement " + childOfDeviationTarget.getDomElement()
 260                         .getNameValue() + " in " + StringHelper.getModuleLineString(
 261                                 childOfDeviationTarget) + " deleted by 'deviate delete' in " + StringHelper
 262                                         .getModuleLineString(statementToDelete));
 263
 264                 deviationTarget.removeChild(childOfDeviationTarget);
 265
 266                 matchFound = true;
 267                 break;
 268             }
 269         }
 270
 271         if (!matchFound) {
 272             context.addFinding(new Finding(statementToDelete, ParserFindingType.P161_INVALID_DEVIATE_OPERATION,
 273                     "Cannot 'deviate delete' this statement as the statement does not exist under the deviated statement."));
 274         }
 275     }
 276
 277     private static boolean statementValuesAreSame(final AbstractStatement statement1, final AbstractStatement statement2) {
 278         final String value1 = statement1.getDomElement().getValue();
 279         final String value2 = statement2.getDomElement().getValue();
 280         return Objects.equals(value1, value2);
 281     }
 282
 283     private static void handleDeviateAdd(final ParserExecutionContext context, final AbstractStatement deviationTarget,
 284             final YDeviate deviate) {
 285         /*
 286          * From the RFC:
 287          *
 288          * "The argument "add" adds properties to the target node. The
 289          * properties to add are identified by substatements to the "deviate"
 290          * statement. If a property can only appear once, the property MUST NOT
 291          * exist in the target node."
 292          */
 293
 294         /*
 295          * The following can only exists once, hence MUST NOT already exist under the deviated schema node.
 296          */
 297         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_CONFIG);
 298         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MANDATORY);
 299         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MAX_ELEMENTS);
 300         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MIN_ELEMENTS);
 301         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_TYPE);
 302         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_UNITS);
 303         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_DEFAULT);
 304         /*
 305          * The following can exist more than once, hence there can be statements under the deviated statement already.
 306          */
 307         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MUST);
 308         addUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_UNIQUE);
 309
 310         /*
 311          * Also make sure to deviate-in extensions. No special handling applies to these, as the
 312          * RFC stipulates this to be extension-specific.
 313          */
 314         handleDeviateAddForExtensions(context, deviationTarget, deviate);
 315     }
 316
 317     private static void handleDeviateAddForExtensions(final ParserExecutionContext context,
 318             final AbstractStatement deviatedStatement, final YDeviate deviate) {
 319         /*
 320          * For extensions we don't know upfront what the exact module/statement names are.
 321          * We must figure these out first, before we start adding these:
 322          */
 323         final Set<StatementModuleAndName> extensionModulesAndNames = deviate.getExtensionChildStatements().stream().map(
 324                 ext -> ext.getStatementModuleAndName()).collect(Collectors.toSet());
 325
 326         extensionModulesAndNames.forEach(sman -> addUnderDeviatedStatement(context, deviatedStatement, deviate, sman));
 327     }
 328
 329     /**
 330      * Given a statement type, verifies that the deviated statement does not already have as child this
 331      * statement, and assuming that this is not the case, adds it / them.
 332      * <p>
 333      * Note: Will gracefully handle a 'deviate add' of properties, i.e. allow these, although according
 334      * to RFC these should only ever be replaced.
 335      */
 336     private static <T extends AbstractStatement> void addUnderDeviatedStatement(final ParserExecutionContext context,
 337             final AbstractStatement deviationTarget, final YDeviate deviate, final StatementModuleAndName soughtChildType) {
 338
 339         /*
 340          * Get the instances of the statement type.
 341          */
 342         final List<T> statementsOfTypeUnderDeviate = deviate.getChildren(soughtChildType);
 343         final List<T> statementsOfTypeUnderTargetStatement = deviationTarget.getChildren(soughtChildType);
 344
 345         if (statementsOfTypeUnderDeviate.isEmpty()) {
 346             return;
 347         }
 348
 349         /*
 350          * Figure out whether there can be multiple instances of the statement under the target.
 351          */
 352         final AbstractStatement oneChildUnderDeviate = deviate.getChild(soughtChildType);
 353         boolean canHaveMultiple;
 354
 355         if (oneChildUnderDeviate.isExtension()) {
 356             canHaveMultiple = ((ExtensionStatement) oneChildUnderDeviate)
 357                     .getMaxCardinalityUnderParent() == MaxCardinality.MULTIPLE;
 358         } else {
 359             final String coreStatementName = soughtChildType.getStatementName();
 360             canHaveMultiple = deviationTarget.getMandatoryMultipleChildStatementNames().contains(
 361                     coreStatementName) || deviationTarget.getOptionalMultipleChildStatementNames().contains(
 362                             coreStatementName);
 363         }
 364
 365         if (!statementsOfTypeUnderTargetStatement.isEmpty() && !canHaveMultiple) {
 366             /*
 367              * A statement of this type already exists under the target, and there cannot be more than one.
 368              */
 369             for (final AbstractStatement statementUnderDeviate : statementsOfTypeUnderDeviate) {
 370                 context.addFinding(new Finding(statementUnderDeviate, ParserFindingType.P161_INVALID_DEVIATE_OPERATION,
 371                         "Cannot 'deviate add' statement '" + statementUnderDeviate
 372                                 .getStatementName() + "' as it already exists under the deviated statement. Use a 'deviate replace' instead."));
 373             }
 374             return;
 375         }
 376
 377         /*
 378          * Check whether the max cardinality would be violated by adding the statements.
 379          */
 380         final int newCount = statementsOfTypeUnderDeviate.size() + statementsOfTypeUnderTargetStatement.size();
 381         if (newCount > 1 && !canHaveMultiple) {
 382             context.addFinding(new Finding(statementsOfTypeUnderDeviate.get(0),
 383                     ParserFindingType.P166_DEVIATE_RESULTS_IN_CHILD_CARDINALITY_VIOLATION,
 384                     "Cannot 'deviate add' this statement as at most one '" + statementsOfTypeUnderDeviate.get(0)
 385                             .getStatementName() + "' statement is allowed under under '" + deviationTarget
 386                                     .getStatementName() + "'."));
 387             return;
 388         }
 389
 390         /*
 391          * Good - either a statement of this type does not already exist under the deviation target, or
 392          * this fact doesn't matter. Then simply clone it so that it ends up under the deviated statement.
 393          *
 394          * Really, cloning is not necessary - we could simply move the statement. However, if there is
 395          * downstream tooling that visualizes the schema it would be nice to retain the original content
 396          * of the deviation so that a user can see it. Also useful for debugging.
 397          */
 398         for (final T statementUnderDeviate : statementsOfTypeUnderDeviate) {
 399             final T clonedStatementPlacedUnderDeviationTarget = StatementFactory.cloneYangStatement(statementUnderDeviate,
 400                     deviationTarget);
 401             clonedStatementPlacedUnderDeviationTarget.cloneFrom(statementUnderDeviate);
 402
 403             addDeviationHistory(clonedStatementPlacedUnderDeviationTarget, DeviationHistory.add(statementUnderDeviate));
 404             addDeviateInfo(clonedStatementPlacedUnderDeviationTarget,
 405                     "statement added by 'deviate add' in module " + StringHelper.getModuleLineString(
 406                             statementUnderDeviate));
 407         }
 408     }
 409
 410     private static void handleDeviateReplace(final ParserExecutionContext context, final AbstractStatement deviationTarget,
 411             final YDeviate deviate) {
 412         /*
 413          * From the RFC:
 414          *
 415          * The argument "replace" replaces properties of the target node. The
 416          * properties to replace are identified by substatements to the
 417          * "deviate" statement. The properties to replace MUST exist in the
 418          * target node.
 419          */
 420
 421         /*
 422          * Before we do the actual replacement, we check for shrinking of boundaries.
 423          */
 424         checkForNarrowedMinMaxElements(context, deviationTarget.getChild(CY.STMT_MIN_ELEMENTS), deviate.getMinElements(),
 425                 deviationTarget.getChild(CY.STMT_MAX_ELEMENTS), deviate.getMaxElements());
 426         /*
 427          * ...and check for data type replacements...
 428          */
 429         checkForReplacedDataType(context, deviationTarget.getChild(CY.STMT_TYPE), deviate.getType());
 430
 431         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_CONFIG);
 432         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_DEFAULT);
 433         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MANDATORY);
 434         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MAX_ELEMENTS);
 435         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MIN_ELEMENTS);
 436         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_MUST);
 437         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_TYPE);
 438         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_UNIQUE);
 439         replaceUnderDeviatedStatement(context, deviationTarget, deviate, CY.STMT_UNITS);
 440
 441         handleReplaceDeviateForExtensions(context, deviationTarget, deviate);
 442     }
 443
 444     private static void handleReplaceDeviateForExtensions(final ParserExecutionContext context,
 445             final AbstractStatement deviatedStatement, final YDeviate deviate) {
 446         /*
 447          * For extensions we don't know upfront what the exact module/statement names are.
 448          * We must figure these out first, before we start replacing these:
 449          */
 450         final Set<StatementModuleAndName> extensionModulesAndNames = deviate.getExtensionChildStatements().stream().map(
 451                 ext -> ext.getStatementModuleAndName()).collect(Collectors.toSet());
 452
 453         extensionModulesAndNames.forEach(sman -> replaceUnderDeviatedStatement(context, deviatedStatement, deviate, sman));
 454     }
 455
 456     private static void checkForReplacedDataType(final ParserExecutionContext context, final YType oldType,
 457             final YType newType) {
 458
 459         if (newType == null) {
 460             return;
 461         }
 462
 463         final Set<String> oldDataTypes = new HashSet<>();
 464         final Set<String> newDataTypes = new HashSet<>();
 465
 466         collectDataTypes(oldDataTypes, oldType);
 467         collectDataTypes(newDataTypes, newType);
 468
 469         if (!oldDataTypes.equals(newDataTypes)) {
 470             context.addFinding(new Finding(newType, ParserFindingType.P057_DATA_TYPE_CHANGED,
 471                     "Data type has changed from " + oldDataTypes.toString() + " to " + newDataTypes.toString() + "."));
 472         }
 473     }
 474
 475     private static void collectDataTypes(final Set<String> dataTypes, final YType type) {
 476         if (type.getDataType().equals("union")) {
 477             for (final YType unionMemberType : type.getTypes()) {
 478                 collectDataTypes(dataTypes, unionMemberType);
 479             }
 480         } else {
 481             dataTypes.add(type.getDataType());
 482         }
 483     }
 484
 485     private static void checkForNarrowedMinMaxElements(final ParserExecutionContext context,
 486             final YMinElements oldMinElements, final YMinElements newMinElements, final YMaxElements oldMaxElements,
 487             final YMaxElements newMaxElements) {
 488
 489         final long oldMinValue = oldMinElements == null ? 0L : oldMinElements.getMinValue();
 490         final long newMinValue = newMinElements == null ? 0L : newMinElements.getMinValue();
 491
 492         if (newMinValue > oldMinValue) {
 493             context.addFinding(new Finding(newMinElements, ParserFindingType.P056_CONSTRAINT_NARROWED,
 494                     "Replacement raises min-elements boundary from '" + oldMinValue + "' to '" + newMinValue + "'."));
 495         }
 496
 497         final boolean oldMaxIsUnbounded = oldMaxElements == null ? true : oldMaxElements.isUnbounded();
 498         final boolean newMaxIsUnbounded = newMaxElements == null ? true : newMaxElements.isUnbounded();
 499         final long oldMaxValue = oldMaxIsUnbounded ? 0L : oldMaxElements.getMaxValue();
 500         final long newMaxValue = newMaxIsUnbounded ? 0L : newMaxElements.getMaxValue();
 501
 502         if (oldMaxIsUnbounded && !newMaxIsUnbounded) {
 503             context.addFinding(new Finding(newMaxElements, ParserFindingType.P056_CONSTRAINT_NARROWED,
 504                     "Replacement lowers max-elements boundary from 'unbounded' to '" + newMaxValue + "'."));
 505         } else if (!oldMaxIsUnbounded && !newMaxIsUnbounded && newMaxValue < oldMaxValue) {
 506             context.addFinding(new Finding(newMaxElements, ParserFindingType.P056_CONSTRAINT_NARROWED,
 507                     "Replacement lowers max-elements boundary from '" + oldMaxValue + "' to '" + newMaxValue + "'."));
 508         }
 509     }
 510
 511     /**
 512      * Given a statement type, verifies that the deviated statement *does* have as child this
 513      * statement, and assuming that this is the case, removes the original child and replaces
 514      * it with the deviate's child. Note: exception is made for properties that *always* exist.
 515      */
 516     @SuppressWarnings("unchecked")
 517     private static <T extends AbstractStatement> void replaceUnderDeviatedStatement(final ParserExecutionContext context,
 518             final AbstractStatement deviationTarget, final YDeviate deviate, final StatementModuleAndName soughtChildType) {
 519
 520         /*
 521          * Establish whether an instance of the supplied class exists under the "deviate" and/or under the deviated statement.
 522          */
 523         final List<T> statementsOfTypeUnderDeviate = deviate.getChildren(soughtChildType);
 524         final List<T> statementsOfTypeUnderDeviationTarget = deviationTarget.getChildren(soughtChildType);
 525
 526         if (statementsOfTypeUnderDeviate.isEmpty()) {
 527             return;
 528         }
 529
 530         final StatementModuleAndName statementModuleAndName = statementsOfTypeUnderDeviate.get(0)
 531                 .getStatementModuleAndName();
 532
 533         if (statementsOfTypeUnderDeviationTarget.isEmpty() && !PROPERTIES_THAT_ALWAYS_EXIST.contains(
 534                 statementModuleAndName)) {
 535             context.addFinding(new Finding(statementsOfTypeUnderDeviate.get(0),
 536                     ParserFindingType.P161_INVALID_DEVIATE_OPERATION,
 537                     "Cannot 'deviate replace' statement '" + statementsOfTypeUnderDeviate.get(0)
 538                             .getStatementName() + "' as it does not exist under the deviated statement."));
 539             return;
 540         }
 541
 542         /*
 543          * Check whether cardinality would be violated by doing the replace.
 544          */
 545         final int newOccurencesOfStatementType = statementsOfTypeUnderDeviate.size();
 546         if (statementModuleAndName.isYangCoreStatement() && newOccurencesOfStatementType > 1) {
 547             if (!deviationTarget.getMandatoryMultipleChildStatementNames().contains(statementModuleAndName
 548                     .getStatementName()) && !deviationTarget.getOptionalMultipleChildStatementNames().contains(
 549                             statementModuleAndName.getStatementName())) {
 550                 context.addFinding(new Finding(statementsOfTypeUnderDeviate.get(0),
 551                         ParserFindingType.P166_DEVIATE_RESULTS_IN_CHILD_CARDINALITY_VIOLATION,
 552                         "Cannot 'deviate replace' this statement as at most one '" + statementModuleAndName
 553                                 .getStatementName() + "' statement is allowed under '" + deviationTarget
 554                                         .getStatementName() + "'."));
 555                 return;
 556             }
 557         }
 558
 559         /*
 560          * Exists in both, so remove the original statement(s), and add the statements under deviate. We do a
 561          * quick check first, though, to see whether the statements that are being replaced likewise have been
 562          * deviated-in previously.
 563          */
 564         boolean replacingPreviouslyReplaced = false;
 565         boolean replacingPreviouslyAdded = false;
 566
 567         for (final T oneReplacedStatement : statementsOfTypeUnderDeviationTarget) {
 568             if (statementHasBeenAddedInByDeviateReplace(oneReplacedStatement)) {
 569                 replacingPreviouslyReplaced = true;
 570             } else if (statementHasBeenAddedInByDeviateAdd(oneReplacedStatement)) {
 571                 replacingPreviouslyAdded = true;
 572             }
 573
 574             addDeviateInfo(deviationTarget, "Previous statement/property " + oneReplacedStatement.getDomElement()
 575                     .getNameValue() + " in " + StringHelper.getModuleLineString(
 576                             deviationTarget) + " replaced by 'deviate replace' in " + StringHelper.getModuleLineString(
 577                                     deviate));
 578         }
 579
 580         deviationTarget.removeChildren(statementsOfTypeUnderDeviationTarget);
 581
 582         for (final T statementUnderDeviate : statementsOfTypeUnderDeviate) {
 583
 584             if (replacingPreviouslyReplaced) {
 585                 context.addFinding(new Finding(statementUnderDeviate,
 586                         ParserFindingType.P163_AMBIGUOUS_DEVIATE_REPLACE_OF_SAME_STATEMENT,
 587                         "Replaces another '" + statementUnderDeviate
 588                                 .getStatementName() + "' statement that has replaced the original statement by a separate 'deviate replace' operation."));
 589             } else if (replacingPreviouslyAdded) {
 590                 context.addFinding(new Finding(statementUnderDeviate,
 591                         ParserFindingType.P164_DEVIATE_REPLACE_OF_DEVIATE_ADDED_STATEMENT,
 592                         "Replaces another '" + statementUnderDeviate
 593                                 .getStatementName() + "' statement that has been previously added by a separate 'deviate add' operation."));
 594             }
 595
 596             final T clonedStatementPlacedUnderDeviationTarget = StatementFactory.cloneYangStatement(statementUnderDeviate,
 597                     deviationTarget);
 598             clonedStatementPlacedUnderDeviationTarget.cloneFrom(statementUnderDeviate);
 599
 600             addDeviationHistory(clonedStatementPlacedUnderDeviationTarget, DeviationHistory.replace(
 601                     (List<AbstractStatement>) statementsOfTypeUnderDeviationTarget, statementUnderDeviate));
 602             addDeviateInfo(clonedStatementPlacedUnderDeviationTarget,
 603                     "Replacement for previous statement or (possibly implicit) property, replaced by 'deviate replace' in " + StringHelper
 604                             .getModuleLineString(statementUnderDeviate));
 605         }
 606     }
 607
 608     private static void handleDeviateNotSupported(final AbstractStatement deviationTarget, final YDeviate deviate) {
 609
 610         /*
 611          * We add some additional information to the parent that will help the user to make sense of
 612          * what has happened. We also keep a record of the statement that we have removed. This is useful
 613          * later on if there is another statement referring to the deleted statement, because then we can
 614          * be smart about it and not issue findings.
 615          */
 616         addDeviationHistory(deviationTarget.getParentStatement(), DeviationHistory.notSupported(deviationTarget, deviate));
 617         addDeviateInfo(deviationTarget.getParentStatement(), "Statement " + deviationTarget.getDomElement()
 618                 .getNameValue() + " in " + StringHelper.getModuleLineString(
 619                         deviationTarget) + " marked as 'not-supported' by deviation in " + StringHelper.getModuleLineString(
 620                                 deviate) + " and thus removed.");
 621
 622         /*
 623          * That's easy - the schema node (the found statement) is not supported, so simply remove it.
 624          */
 625         deviationTarget.getParentStatement().removeChild(deviationTarget);
 626     }
 627
 628     /**
 629      * Finds the schema node that is being deviated.
 630      */
 631     private static AbstractStatement findTargetSchemaNode(final ParserExecutionContext context, final YDeviation deviation,
 632             final Schema schema) {
 633
 634         final AbstractStatement targetSchemaNode = Helper.findSchemaNode(context, deviation, deviation
 635                 .getDeviationTargetNode(), schema);
 636         if (targetSchemaNode == null) {
 637             return null;
 638         }
 639
 640         /*
 641          * Check whether they both sit inside the very same module
 642          */
 643         if (deviation.getDomElement().getYangModel() == targetSchemaNode.getDomElement().getYangModel()) {
 644             context.addFinding(new Finding(deviation, ParserFindingType.P162_DEVIATION_TARGET_NODE_IN_SAME_MODULE,
 645                     "Both 'deviation' and it's target node sit in the same (sub-)module."));
 646         }
 647
 648         return targetSchemaNode;
 649     }
 650
 651     /**
 652      * We try to figure out whether a 'deviate not-supported' refers to something in the
 653      * tree that has previously been removed. That's a bit involved, but well possible...
 654      */
 655     private static boolean deviationRefersToPreviouslyRemovedSchemaNode(final ParserExecutionContext context,
 656             final YDeviation deviation, final Schema schema) {
 657
 658         final String deviationTargetNode = deviation.getDeviationTargetNode();
 659         if (deviationTargetNode.isEmpty() || !deviationTargetNode.startsWith("/")) {
 660             /*
 661              * Pointless trying to resolve the path. No point issuing a finding either, a
 662              * P015_INVALID_SYNTAX_IN_DOCUMENT would have been issued already.
 663              */
 664             return false;
 665         }
 666
 667         /*
 668          * We split the path, and get the starting point for navigation.
 669          */
 670         final String[] identifierParts = Helper.getIdentifierParts(true, deviationTargetNode);
 671         AbstractStatement traversalStatement = Helper.findStartingSchemaNode(context, deviation, true, identifierParts[0],
 672                 schema);
 673         if (traversalStatement == null) {
 674             return false;
 675         }
 676
 677         /*
 678          * Go down the tree until we get stuck...
 679          */
 680         for (final String possiblyPrefixedIdentifier : identifierParts) {
 681             final AbstractStatement foundChildStatement = Helper.findChildSchemaNode(context, traversalStatement,
 682                     possiblyPrefixedIdentifier, deviation);
 683             if (foundChildStatement == null) {
 684                 /*
 685                  * OK, so this is the point where we could not follow the path anymore. We extract the
 686                  * identifier that we were actually looking for, and check whether such an identifier
 687                  * has been marked as previously not-supported.
 688                  */
 689                 final String unprefixedIdentifierSought = QNameHelper.extractName(possiblyPrefixedIdentifier);
 690
 691                 final List<DeviationHistory> removedStatementsHistory = getDeviationHistory(traversalStatement).stream()
 692                         .filter(dh -> dh.deviateType == DeviateType.NOT_SUPPORTED).collect(Collectors.toList());
 693                 for (final DeviationHistory history : removedStatementsHistory) {
 694                     if (unprefixedIdentifierSought.equals(history.deviatedStatements.get(0).getStatementIdentifier())) {
 695                         return true;
 696                     }
 697                 }
 698
 699                 /*
 700                  * There is nothing in the history, so truly not found.
 701                  */
 702                 return false;
 703             }
 704
 705             traversalStatement = foundChildStatement;
 706         }
 707
 708         /*
 709          * We really should never ever be getting here.
 710          */
 711         return false;
 712     }
 713
 714     private static final String DEVIATION_INFO = "DEVIATION_INFO";
 715
 716     private static void addDeviateInfo(final AbstractStatement statement, final String info) {
 717         Helper.addAppDataListInfo(statement, DEVIATION_INFO, info);
 718     }
 719
 720     public static List<String> getDeviationInfosForStatement(final AbstractStatement statement) {
 721         return Helper.getAppDataListInfo(statement, DEVIATION_INFO);
 722     }
 723
 724     private static final String DEVIATION_HISTORY = "DEVIATION_HISTORY";
 725
 726     private static void addDeviationHistory(final AbstractStatement onStatement, final DeviationHistory deviationHistory) {
 727         Helper.addAppDataListInfo(onStatement, DEVIATION_HISTORY, deviationHistory);
 728     }
 729
 730     public static List<DeviationHistory> getDeviationHistory(final AbstractStatement onStatement) {
 731         return Helper.getAppDataListInfo(onStatement, DEVIATION_HISTORY);
 732     }
 733
 734     private static boolean statementHasBeenAddedInByDeviateAdd(final AbstractStatement statement) {
 735         final List<DeviationHistory> deviationHistory = getDeviationHistory(statement);
 736         return deviationHistory.size() > 0 && deviationHistory.get(0).deviateType == DeviateType.ADD;
 737     }
 738
 739     private static boolean statementHasBeenAddedInByDeviateReplace(final AbstractStatement statement) {
 740         final List<DeviationHistory> deviationHistory = getDeviationHistory(statement);
 741         return deviationHistory.size() > 0 && deviationHistory.get(0).deviateType == DeviateType.REPLACE;
 742     }
 743
 744     public static class DeviationHistory {
 745
 746         static DeviationHistory notSupported(final AbstractStatement notSupportedChild, final YDeviate yDeviate) {
 747             return new DeviationHistory(YDeviate.DeviateType.NOT_SUPPORTED, Collections.singletonList(notSupportedChild),
 748                     yDeviate);
 749         }
 750
 751         static DeviationHistory delete(final AbstractStatement deletedChild, final AbstractStatement deviatingStatement) {
 752             return new DeviationHistory(YDeviate.DeviateType.DELETE, Collections.singletonList(deletedChild),
 753                     deviatingStatement);
 754         }
 755
 756         static DeviationHistory add(final AbstractStatement deviatingStatement) {
 757             return new DeviationHistory(YDeviate.DeviateType.ADD, Collections.<AbstractStatement> emptyList(),
 758                     deviatingStatement);
 759         }
 760
 761         static DeviationHistory replace(final List<AbstractStatement> replacedStatements,
 762                 final AbstractStatement deviatingStatement) {
 763             return new DeviationHistory(YDeviate.DeviateType.REPLACE, replacedStatements, deviatingStatement);
 764         }
 765
 766         /**
 767          * The type of deviation applied.
 768          */
 769         public final YDeviate.DeviateType deviateType;
 770
 771         /**
 772          * The statement that was deviated. This will be:
 773          * <p>
 774          * not-supported: The single statement (which will be a data node) that was removed.
 775          * delete: The single statement (typically a property) that was removed.
 776          * add: empty, no content.
 777          * replace: The statements (0..n) that were replaced.
 778          *
 779          * that were added, removed, or were changed. If the statements were
 780          * removed, the statement will not have a parent anymore.
 781          */
 782         public final List<AbstractStatement> deviatedStatements;
 783
 784         /**
 785          * The statement that performed the deviation, i.e. the 'deviate' statement itself,
 786          * or a child statement of 'deviate'.
 787          */
 788         public final AbstractStatement deviatingStatement;
 789
 790         private DeviationHistory(final DeviateType deviateType, final List<AbstractStatement> deviatedStatements,
 791                 final AbstractStatement deviatingStatement) {
 792             this.deviateType = deviateType;
 793             this.deviatedStatements = deviatedStatements;
 794             this.deviatingStatement = deviatingStatement;
 795         }
 796     }
 797 }