model/yang-model-util/src/main/java/org/opendaylight/yangtools/yang/model/util/SchemaInferenceStack.java

   1 /*
   2  * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.model.util;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verify;
  12 import static com.google.common.base.Verify.verifyNotNull;
  13 import static java.util.Objects.requireNonNull;
  14
  15 import com.google.common.annotations.Beta;
  16 import com.google.common.annotations.VisibleForTesting;
  17 import com.google.common.base.MoreObjects;
  18 import com.google.common.base.VerifyException;
  19 import com.google.common.collect.Collections2;
  20 import com.google.common.collect.ImmutableList;
  21 import com.google.common.collect.Iterables;
  22 import java.util.ArrayDeque;
  23 import java.util.Collection;
  24 import java.util.List;
  25 import java.util.NoSuchElementException;
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.eclipse.jdt.annotation.Nullable;
  28 import org.opendaylight.yangtools.concepts.Mutable;
  29 import org.opendaylight.yangtools.rfc8040.model.api.YangDataEffectiveStatement;
  30 import org.opendaylight.yangtools.yang.common.QName;
  31 import org.opendaylight.yangtools.yang.common.QNameModule;
  32 import org.opendaylight.yangtools.yang.common.UnresolvedQName.Unqualified;
  33 import org.opendaylight.yangtools.yang.common.YangDataName;
  34 import org.opendaylight.yangtools.yang.model.api.EffectiveModelContext;
  35 import org.opendaylight.yangtools.yang.model.api.EffectiveStatementInference;
  36 import org.opendaylight.yangtools.yang.model.api.LeafSchemaNode;
  37 import org.opendaylight.yangtools.yang.model.api.PathExpression;
  38 import org.opendaylight.yangtools.yang.model.api.PathExpression.DerefSteps;
  39 import org.opendaylight.yangtools.yang.model.api.PathExpression.LocationPathSteps;
  40 import org.opendaylight.yangtools.yang.model.api.SchemaTreeInference;
  41 import org.opendaylight.yangtools.yang.model.api.Status;
  42 import org.opendaylight.yangtools.yang.model.api.TypeAware;
  43 import org.opendaylight.yangtools.yang.model.api.TypeDefinition;
  44 import org.opendaylight.yangtools.yang.model.api.TypedDataSchemaNode;
  45 import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement;
  46 import org.opendaylight.yangtools.yang.model.api.stmt.CaseEffectiveStatement;
  47 import org.opendaylight.yangtools.yang.model.api.stmt.ChoiceEffectiveStatement;
  48 import org.opendaylight.yangtools.yang.model.api.stmt.DataTreeAwareEffectiveStatement;
  49 import org.opendaylight.yangtools.yang.model.api.stmt.DataTreeEffectiveStatement;
  50 import org.opendaylight.yangtools.yang.model.api.stmt.GroupingEffectiveStatement;
  51 import org.opendaylight.yangtools.yang.model.api.stmt.ModuleEffectiveStatement;
  52 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaNodeIdentifier;
  53 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaNodeIdentifier.Absolute;
  54 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeAwareEffectiveStatement;
  55 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeEffectiveStatement;
  56 import org.opendaylight.yangtools.yang.model.api.stmt.StatusEffectiveStatement;
  57 import org.opendaylight.yangtools.yang.model.api.stmt.TypedefAwareEffectiveStatement;
  58 import org.opendaylight.yangtools.yang.model.api.stmt.TypedefEffectiveStatement;
  59 import org.opendaylight.yangtools.yang.model.api.type.InstanceIdentifierTypeDefinition;
  60 import org.opendaylight.yangtools.yang.model.api.type.LeafrefTypeDefinition;
  61 import org.opendaylight.yangtools.yang.model.spi.AbstractEffectiveStatementInference;
  62 import org.opendaylight.yangtools.yang.model.spi.DefaultSchemaTreeInference;
  63 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath;
  64 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.AxisStep;
  65 import org.opendaylight.yangtools.yang.xpath.api.YangLocationPath.QNameStep;
  66 import org.slf4j.LoggerFactory;
  67
  68 /**
  69  * A state tracking utility for walking {@link EffectiveModelContext}'s contents along schema/grouping namespaces. This
  70  * is conceptually a stack, tracking {@link EffectiveStatement}s encountered along traversal.
  71  *
  72  * <p>
  73  * This class is designed for single-threaded uses and does not make any guarantees around concurrent access.
  74  */
  75 @Beta
  76 public final class SchemaInferenceStack implements Mutable, LeafrefResolver {
  77     /**
  78      * Semantic binding of {@link EffectiveStatementInference} produced by {@link SchemaInferenceStack}. Sequence of
  79      * {@link #statementPath()} is implementation-specific.
  80      */
  81     @Beta
  82     public static final class Inference extends AbstractEffectiveStatementInference<EffectiveStatement<?, ?>> {
  83         private final ArrayDeque<EffectiveStatement<?, ?>> deque;
  84         private final ModuleEffectiveStatement currentModule;
  85         private final int groupingDepth;
  86         private final boolean clean;
  87
  88         Inference(final @NonNull EffectiveModelContext modelContext, final ArrayDeque<EffectiveStatement<?, ?>> deque,
  89                 final ModuleEffectiveStatement currentModule, final int groupingDepth, final boolean clean) {
  90             super(modelContext);
  91             this.deque = requireNonNull(deque);
  92             this.currentModule = currentModule;
  93             this.groupingDepth = groupingDepth;
  94             this.clean = clean;
  95         }
  96
  97         /**
  98          * Create a new {@link Inference} backed by an effective model.
  99          *
 100          * @param modelContext {@link EffectiveModelContext} to which the inference is attached
 101          * @return A new @link Inference}
 102          * @throws NullPointerException if {@code modelContext} is {@code null}
 103          */
 104         public static @NonNull Inference of(final EffectiveModelContext modelContext) {
 105             return new Inference(modelContext, new ArrayDeque<>(), null, 0, true);
 106         }
 107
 108         /**
 109          * Create a new {@link Inference} backed by an effective model and set up to point and specified data tree node.
 110          *
 111          * @param modelContext {@link EffectiveModelContext} to which the inference is attached
 112          * @param qnames Data tree path qnames
 113          * @return A new @link Inference}
 114          * @throws NullPointerException if any argument is {@code null} or path contains a {@code null} element
 115          * @throws IllegalArgumentException if a path element cannot be found
 116          */
 117         public static @NonNull Inference ofDataTreePath(final EffectiveModelContext modelContext,
 118                 final QName... qnames) {
 119             return qnames.length == 0 ? of(modelContext)
 120                 : SchemaInferenceStack.ofDataTreePath(modelContext, qnames).toInference();
 121         }
 122
 123         @Override
 124         public List<EffectiveStatement<?, ?>> statementPath() {
 125             return ImmutableList.copyOf(deque);
 126         }
 127
 128         /**
 129          * Return {@code true} if this inference is empty. This is a more efficient alternative to
 130          * {@code statementPath().isEmpty()}.
 131          *
 132          * @return {@code true} if {@link #statementPath()} returns an empty list
 133          */
 134         public boolean isEmpty() {
 135             return deque.isEmpty();
 136         }
 137
 138         /**
 139          * Convert this inference into a {@link SchemaInferenceStack}.
 140          *
 141          * @return A new stack
 142          */
 143         public @NonNull SchemaInferenceStack toSchemaInferenceStack() {
 144             return new SchemaInferenceStack(modelContext(), deque, currentModule, groupingDepth, clean);
 145         }
 146     }
 147
 148     private static final String VERIFY_DEFAULT_SCHEMA_TREE_INFERENCE_PROP =
 149         "org.opendaylight.yangtools.yang.model.util.SchemaInferenceStack.verifyDefaultSchemaTreeInference";
 150     private static final boolean VERIFY_DEFAULT_SCHEMA_TREE_INFERENCE =
 151         Boolean.getBoolean(VERIFY_DEFAULT_SCHEMA_TREE_INFERENCE_PROP);
 152
 153     static {
 154         if (VERIFY_DEFAULT_SCHEMA_TREE_INFERENCE) {
 155             LoggerFactory.getLogger(SchemaInferenceStack.class)
 156                 .info("SchemaTreeStack.ofInference(DefaultSchemaTreeInference) argument is being verified");
 157         }
 158     }
 159
 160     private final @NonNull EffectiveModelContext modelContext;
 161     private final ArrayDeque<EffectiveStatement<?, ?>> deque;
 162
 163     private @Nullable ModuleEffectiveStatement currentModule;
 164     private int groupingDepth;
 165
 166     // True if there were only steps along grouping and schema tree, hence it is consistent with SchemaNodeIdentifier
 167     // False if we have evidence of a data tree lookup succeeding
 168     private boolean clean;
 169
 170     private SchemaInferenceStack(final EffectiveModelContext effectiveModel, final int expectedSize) {
 171         deque = new ArrayDeque<>(expectedSize);
 172         modelContext = requireNonNull(effectiveModel);
 173         clean = true;
 174     }
 175
 176     private SchemaInferenceStack(final SchemaInferenceStack source) {
 177         deque = source.deque.clone();
 178         modelContext = source.modelContext;
 179         currentModule = source.currentModule;
 180         groupingDepth = source.groupingDepth;
 181         clean = source.clean;
 182     }
 183
 184     private SchemaInferenceStack(final EffectiveModelContext modelContext,
 185             final ArrayDeque<EffectiveStatement<?, ?>> deque, final ModuleEffectiveStatement currentModule,
 186             final int groupingDepth, final boolean clean) {
 187         this.modelContext = requireNonNull(modelContext);
 188         this.deque = deque.clone();
 189         this.currentModule = currentModule;
 190         this.groupingDepth = groupingDepth;
 191         this.clean = clean;
 192     }
 193
 194     private SchemaInferenceStack(final EffectiveModelContext effectiveModel) {
 195         modelContext = requireNonNull(effectiveModel);
 196         deque = new ArrayDeque<>();
 197         clean = true;
 198     }
 199
 200     /**
 201      * Create a new empty stack backed by an effective model.
 202      *
 203      * @param effectiveModel EffectiveModelContext to which this stack is attached
 204      * @return A new stack
 205      * @throws NullPointerException if {@code effectiveModel} is {@code null}
 206      */
 207     public static @NonNull SchemaInferenceStack of(final EffectiveModelContext effectiveModel) {
 208         return new SchemaInferenceStack(effectiveModel);
 209     }
 210
 211     /**
 212      * Create a new stack backed by an effective model, pointing to specified schema node identified by
 213      * {@link Absolute}.
 214      *
 215      * @param effectiveModel EffectiveModelContext to which this stack is attached
 216      * @return A new stack
 217      * @throws NullPointerException if {@code effectiveModel} is {@code null}
 218      * @throws IllegalArgumentException if {@code path} cannot be resolved in the effective model
 219      */
 220     public static @NonNull SchemaInferenceStack of(final EffectiveModelContext effectiveModel, final Absolute path) {
 221         final var ret = new SchemaInferenceStack(effectiveModel);
 222         path.getNodeIdentifiers().forEach(ret::enterSchemaTree);
 223         return ret;
 224     }
 225
 226     /**
 227      * Create a new stack from an {@link EffectiveStatementInference}.
 228      *
 229      * @param inference Inference to use for initialization
 230      * @return A new stack
 231      * @throws NullPointerException if {@code inference} is {@code null}
 232      * @throws IllegalArgumentException if {@code inference} implementation is not supported
 233      */
 234     public static @NonNull SchemaInferenceStack ofInference(final EffectiveStatementInference inference) {
 235         if (inference.statementPath().isEmpty()) {
 236             return new SchemaInferenceStack(inference.modelContext());
 237         } else if (inference instanceof SchemaTreeInference sti) {
 238             return ofInference(sti);
 239         } else if (inference instanceof Inference inf) {
 240             return inf.toSchemaInferenceStack();
 241         } else {
 242             throw new IllegalArgumentException("Unsupported Inference " + inference);
 243         }
 244     }
 245
 246     /**
 247      * Create a new stack from an {@link SchemaTreeInference}.
 248      *
 249      * @param inference SchemaTreeInference to use for initialization
 250      * @return A new stack
 251      * @throws NullPointerException if {@code inference} is {@code null}
 252      * @throws IllegalArgumentException if {@code inference} cannot be resolved to a valid stack
 253      */
 254     public static @NonNull SchemaInferenceStack ofInference(final SchemaTreeInference inference) {
 255         return inference instanceof DefaultSchemaTreeInference dsti ? ofInference(dsti)
 256             : of(inference.modelContext(), inference.toSchemaNodeIdentifier());
 257     }
 258
 259     /**
 260      * Create a new stack from an {@link DefaultSchemaTreeInference}. The argument is nominally trusted to be an
 261      * accurate representation of the schema tree.
 262      *
 263      * <p>
 264      * Run-time verification of {@code inference} can be enabled by setting the
 265      * {@value #VERIFY_DEFAULT_SCHEMA_TREE_INFERENCE_PROP} system property to {@code true}.
 266      *
 267      * @param inference DefaultSchemaTreeInference to use for initialization
 268      * @return A new stack
 269      * @throws NullPointerException if {@code inference} is {@code null}
 270      * @throws IllegalArgumentException if {@code inference} refers to a missing module or when verification is enabled
 271      *                                  and it does not match its context's schema tree
 272      */
 273     public static @NonNull SchemaInferenceStack ofInference(final DefaultSchemaTreeInference inference) {
 274         return VERIFY_DEFAULT_SCHEMA_TREE_INFERENCE ? ofUntrusted(inference) : ofTrusted(inference);
 275     }
 276
 277     private static @NonNull SchemaInferenceStack ofTrusted(final DefaultSchemaTreeInference inference) {
 278         final var path = inference.statementPath();
 279         final var ret = new SchemaInferenceStack(inference.modelContext(), path.size());
 280         ret.currentModule = ret.getModule(path.get(0).argument());
 281         ret.deque.addAll(path);
 282         return ret;
 283     }
 284
 285     @VisibleForTesting
 286     static @NonNull SchemaInferenceStack ofUntrusted(final DefaultSchemaTreeInference inference) {
 287         final var ret = of(inference.modelContext(), inference.toSchemaNodeIdentifier());
 288         if (!Iterables.elementsEqual(ret.deque, inference.statementPath())) {
 289             throw new IllegalArgumentException("Provided " + inference + " is not consistent with resolved path "
 290                 + ret.toSchemaTreeInference());
 291         }
 292         return ret;
 293     }
 294
 295     /**
 296      * Create a new stack backed by an effective model and set up to point and specified data tree node.
 297      *
 298      * @param effectiveModel EffectiveModelContext to which this stack is attached
 299      * @return A new stack
 300      * @throws NullPointerException if any argument is {@code null} or path contains a {@code null} element
 301      * @throws IllegalArgumentException if a path element cannot be found
 302      */
 303     public static @NonNull SchemaInferenceStack ofDataTreePath(final EffectiveModelContext effectiveModel,
 304             final QName... path) {
 305         final var ret = new SchemaInferenceStack(effectiveModel);
 306         for (var qname : path) {
 307             ret.enterDataTree(qname);
 308         }
 309         return ret;
 310     }
 311
 312     /**
 313      * Return the {@link EffectiveModelContext} this stack operates on.
 314      *
 315      * @return the {@link EffectiveModelContext} this stack operates on
 316      */
 317     public @NonNull EffectiveModelContext modelContext() {
 318         return modelContext;
 319     }
 320
 321     /**
 322      * Create a deep copy of this object.
 323      *
 324      * @return An isolated copy of this object
 325      */
 326     public @NonNull SchemaInferenceStack copy() {
 327         return new SchemaInferenceStack(this);
 328     }
 329
 330     /**
 331      * Check if this stack is empty.
 332      *
 333      * @return {@code true} if this stack has not entered any node
 334      */
 335     public boolean isEmpty() {
 336         return deque.isEmpty();
 337     }
 338
 339     /**
 340      * Return the statement at the top of the stack.
 341      *
 342      * @return Top statement
 343      * @throws IllegalStateException if the stack is empty
 344      */
 345     public @NonNull EffectiveStatement<?, ?> currentStatement() {
 346         return checkNonNullState(deque.peekLast());
 347     }
 348
 349     /**
 350      * Return current module the stack has entered.
 351      *
 352      * @return Current module
 353      * @throws IllegalStateException if the stack is empty
 354      */
 355     public @NonNull ModuleEffectiveStatement currentModule() {
 356         return checkNonNullState(currentModule);
 357     }
 358
 359     /**
 360      * Check if the stack is in instantiated context. This indicates the stack is non-empty and there are only schema
 361      * tree statements in the stack.
 362      *
 363      * @return {@code false} if the stack is empty or contains a statement which is not a
 364      *         {@link SchemaTreeEffectiveStatement}, {@code true} otherwise.
 365      */
 366     public boolean inInstantiatedContext() {
 367         return groupingDepth == 0 && !deque.isEmpty()
 368             && deque.stream().allMatch(SchemaTreeEffectiveStatement.class::isInstance);
 369     }
 370
 371     /**
 372      * Check if the stack is in a {@code grouping} context.
 373      *
 374      * @return {@code false} if the stack contains a grouping.
 375      */
 376     public boolean inGrouping() {
 377         return groupingDepth != 0;
 378     }
 379
 380     /**
 381      * Return the effective {@code status} of the {@link #currentStatement()}, if present. This method operates on
 382      * the effective view of the model and therefore does not reflect status the declaration hierarchy. Most notably
 383      * this YANG snippet:
 384      * <pre>
 385      * {@code
 386      *   module foo {
 387      *     grouping foo {
 388      *       status obsolete;
 389      *       leaf bar { type string; }
 390      *     }
 391      *
 392      *     container foo {
 393      *       status deprecated;
 394      *       uses bar;
 395      *     }
 396      *
 397      *     uses foo;
 398      *   }
 399      * }
 400      * </pre>
 401      * will cause this method to report the status of {@code leaf bar} as:
 402      * <ul>
 403      *   <li>{@link Status#OBSOLETE} at its original declaration site in {@code grouping foo}</li>
 404      *   <li>{@link Status#DEPRECATED} at its instantiation in {@code container foo}</li>
 405      *   <li>{@link Status#CURRENT} at its instantiation in {@code module foo}</li>
 406      * </ul>
 407      *
 408      * @return {@link Status#CURRENT} if {@link #isEmpty()}, or the status of current statement as implied by its direct
 409      *         and its ancestors' substaments.
 410      */
 411     public @NonNull Status effectiveStatus() {
 412         final var it = reconstructDeque().descendingIterator();
 413         while (it.hasNext()) {
 414             final var optStatus = it.next().findFirstEffectiveSubstatementArgument(StatusEffectiveStatement.class);
 415             if (optStatus.isPresent()) {
 416                 return optStatus.orElseThrow();
 417             }
 418         }
 419         return Status.CURRENT;
 420     }
 421
 422     /**
 423      * Reset this stack to empty state.
 424      */
 425     public void clear() {
 426         deque.clear();
 427         currentModule = null;
 428         groupingDepth = 0;
 429         clean = true;
 430     }
 431
 432     /**
 433      * Lookup a {@code choice} by its node identifier and push it to the stack. This step is very similar to
 434      * {@link #enterSchemaTree(QName)}, except it handles the use case where traversal ignores actual {@code case}
 435      * intermediate schema tree children.
 436      *
 437      * @param nodeIdentifier Node identifier of the choice to enter
 438      * @return Resolved choice
 439      * @throws NullPointerException if {@code nodeIdentifier} is {@code null}
 440      * @throws IllegalArgumentException if the corresponding choice cannot be found
 441      */
 442     public @NonNull ChoiceEffectiveStatement enterChoice(final QName nodeIdentifier) {
 443         final var nodeId = requireNonNull(nodeIdentifier);
 444         final var parent = deque.peekLast();
 445         if (parent instanceof ChoiceEffectiveStatement choice) {
 446             return enterChoice(choice, nodeId);
 447         }
 448
 449         // Fall back to schema tree lookup. Note if it results in non-choice, we rewind before reporting an error
 450         final var result = enterSchemaTree(nodeId);
 451         if (result instanceof ChoiceEffectiveStatement choice) {
 452             return choice;
 453         }
 454         exit();
 455
 456         if (parent != null) {
 457             throw notPresent(parent, "Choice", nodeId);
 458         }
 459         throw new IllegalArgumentException("Choice " + nodeId + " not present");
 460     }
 461
 462     // choice -> choice transition, we have to deal with intermediate case nodes
 463     private @NonNull ChoiceEffectiveStatement enterChoice(final @NonNull ChoiceEffectiveStatement parent,
 464             final @NonNull QName nodeIdentifier) {
 465         for (var stmt : parent.effectiveSubstatements()) {
 466             if (stmt instanceof CaseEffectiveStatement caze) {
 467                 final var optMatch = caze.findSchemaTreeNode(nodeIdentifier)
 468                     .filter(ChoiceEffectiveStatement.class::isInstance)
 469                     .map(ChoiceEffectiveStatement.class::cast);
 470                 if (optMatch.isPresent()) {
 471                     final var match = optMatch.orElseThrow();
 472                     deque.addLast(match);
 473                     clean = false;
 474                     return match;
 475                 }
 476             }
 477         }
 478         throw notPresent(parent, "Choice", nodeIdentifier);
 479     }
 480
 481     /**
 482      * Lookup a {@code grouping} by its node identifier and push it to the stack.
 483      *
 484      * @param nodeIdentifier Node identifier of the grouping to enter
 485      * @return Resolved grouping
 486      * @throws NullPointerException if {@code nodeIdentifier} is {@code null}
 487      * @throws IllegalArgumentException if the corresponding grouping cannot be found
 488      */
 489     public @NonNull GroupingEffectiveStatement enterGrouping(final QName nodeIdentifier) {
 490         return pushGrouping(requireNonNull(nodeIdentifier));
 491     }
 492
 493     /**
 494      * Lookup a {@code schema tree} child by its node identifier and push it to the stack.
 495      *
 496      * @param nodeIdentifier Node identifier of the schema tree child to enter
 497      * @return Resolved schema tree child
 498      * @throws NullPointerException if {@code nodeIdentifier} is {@code null}
 499      * @throws IllegalArgumentException if the corresponding child cannot be found
 500      */
 501     public @NonNull SchemaTreeEffectiveStatement<?> enterSchemaTree(final QName nodeIdentifier) {
 502         return pushSchema(requireNonNull(nodeIdentifier));
 503     }
 504
 505     /**
 506      * Lookup a {@code schema tree} node by its schema node identifier and push it to the stack.
 507      *
 508      * @param nodeIdentifier Schema node identifier of the schema tree node to enter
 509      * @return Resolved schema tree node
 510      * @throws NullPointerException if {@code nodeIdentifier} is {@code null}
 511      * @throws IllegalArgumentException if the corresponding node cannot be found
 512      */
 513     public @NonNull SchemaTreeEffectiveStatement<?> enterSchemaTree(final SchemaNodeIdentifier nodeIdentifier) {
 514         if (nodeIdentifier instanceof Absolute) {
 515             clear();
 516         }
 517
 518         final var it = nodeIdentifier.getNodeIdentifiers().iterator();
 519         SchemaTreeEffectiveStatement<?> ret;
 520         do {
 521             ret = enterSchemaTree(it.next());
 522         } while (it.hasNext());
 523
 524         return ret;
 525     }
 526
 527     /**
 528      * Lookup a {@code schema tree} child by its node identifier and push it to the stack.
 529      *
 530      * @param nodeIdentifier Node identifier of the date tree child to enter
 531      * @return Resolved date tree child
 532      * @throws NullPointerException if {@code nodeIdentifier} is {@code null}
 533      * @throws IllegalArgumentException if the corresponding child cannot be found
 534      */
 535     public @NonNull DataTreeEffectiveStatement<?> enterDataTree(final QName nodeIdentifier) {
 536         return pushData(requireNonNull(nodeIdentifier));
 537     }
 538
 539     /**
 540      * Lookup a {@code typedef} by its node identifier and push it to the stack.
 541      *
 542      * @param nodeIdentifier Node identifier of the typedef to enter
 543      * @return Resolved typedef
 544      * @throws NullPointerException if {@code nodeIdentifier} is {@code null}
 545      * @throws IllegalArgumentException if the corresponding typedef cannot be found
 546      */
 547     public @NonNull TypedefEffectiveStatement enterTypedef(final QName nodeIdentifier) {
 548         return pushTypedef(requireNonNull(nodeIdentifier));
 549     }
 550
 551     /**
 552      * Lookup a {@code rc:yang-data} by the module namespace where it is defined and its template name.
 553      *
 554      * @param name Template name
 555      * @return Resolved yang-data
 556      * @throws NullPointerException if any argument is {@code null}
 557      * @throws IllegalArgumentException if the corresponding yang-data cannot be found
 558      * @throws IllegalStateException if this stack is not empty
 559      */
 560     public @NonNull YangDataEffectiveStatement enterYangData(final YangDataName name) {
 561         if (!isEmpty()) {
 562             throw new IllegalStateException("Cannot lookup yang-data in a non-empty stack");
 563         }
 564
 565         final var checkedName = requireNonNull(name);
 566         final var namespace = name.module();
 567         final var module = modelContext.getModuleStatements().get(namespace);
 568         if (module == null) {
 569             throw new IllegalArgumentException("Module for " + namespace + " not found");
 570         }
 571
 572         final var ret = module.streamEffectiveSubstatements(YangDataEffectiveStatement.class)
 573             .filter(stmt -> checkedName.equals(stmt.argument()))
 574             .findFirst()
 575             .orElseThrow(
 576                 () -> new IllegalArgumentException("yang-data " + checkedName.name() + " not present in " + namespace));
 577         deque.addLast(ret);
 578         currentModule = module;
 579         return ret;
 580     }
 581
 582     /**
 583      * Pop the current statement from the stack.
 584      *
 585      * @return Previous statement
 586      * @throws NoSuchElementException if this stack is empty
 587      */
 588     public @NonNull EffectiveStatement<?, ?> exit() {
 589         final var prev = deque.removeLast();
 590         if (prev instanceof GroupingEffectiveStatement) {
 591             --groupingDepth;
 592         }
 593         if (deque.isEmpty()) {
 594             currentModule = null;
 595             clean = true;
 596         }
 597         return prev;
 598     }
 599
 600     /**
 601      * Pop the current statement from the stack, asserting it is a {@link DataTreeEffectiveStatement} and that
 602      * subsequent {@link #enterDataTree(QName)} will find it again.
 603      *
 604      * @return Previous statement
 605      * @throws NoSuchElementException if this stack is empty
 606      * @throws IllegalStateException if current statement is not a DataTreeEffectiveStatement or if its parent is not
 607      *                               a {@link DataTreeAwareEffectiveStatement}
 608      */
 609     public @NonNull DataTreeEffectiveStatement<?> exitToDataTree() {
 610         final var child = exit();
 611         if (!(child instanceof DataTreeEffectiveStatement<?> ret)) {
 612             throw new IllegalStateException("Unexpected current " + child);
 613         }
 614
 615         var parent = deque.peekLast();
 616         while (parent instanceof ChoiceEffectiveStatement || parent instanceof CaseEffectiveStatement) {
 617             deque.pollLast();
 618             parent = deque.peekLast();
 619         }
 620
 621         if (parent == null || parent instanceof DataTreeAwareEffectiveStatement) {
 622             return ret;
 623         }
 624         throw new IllegalStateException("Unexpected parent " + parent);
 625     }
 626
 627     @Override
 628     public TypeDefinition<?> resolveLeafref(final LeafrefTypeDefinition type) {
 629         final var tmp = copy();
 630
 631         var current = type;
 632         while (true) {
 633             final var resolved = tmp.resolvePathExpression(current.getPathStatement());
 634             if (!(resolved instanceof TypeAware typeAware)) {
 635                 throw new IllegalStateException("Unexpected result " + resolved + " resultion of " + type);
 636             }
 637
 638             final var result = typeAware.getType();
 639             if (result instanceof LeafrefTypeDefinition leafref) {
 640                 if (result == type) {
 641                     throw new IllegalArgumentException(
 642                         "Resolution of " + type + " loops back onto itself via " + current);
 643                 }
 644                 current = leafref;
 645             } else {
 646                 return result;
 647             }
 648         }
 649     }
 650
 651     /**
 652      * Resolve a {@link PathExpression}.
 653      *
 654      * <p>
 655      * Note if this method throws, this stack may be in an undefined state.
 656      *
 657      * @param path Requested path
 658      * @return Resolved schema tree child
 659      * @throws NullPointerException if {@code path} is {@code null}
 660      * @throws IllegalArgumentException if the target node cannot be found
 661      * @throws VerifyException if path expression is invalid
 662      */
 663     public @NonNull EffectiveStatement<?, ?> resolvePathExpression(final PathExpression path) {
 664         final var steps = path.getSteps();
 665         if (steps instanceof LocationPathSteps location) {
 666             return resolveLocationPath(location.getLocationPath());
 667         } else if (steps instanceof DerefSteps deref) {
 668             return resolveDeref(deref);
 669         } else {
 670             throw new VerifyException("Unhandled steps " + steps);
 671         }
 672     }
 673
 674     private @NonNull EffectiveStatement<?, ?> resolveDeref(final DerefSteps deref) {
 675         final var leafRefSchemaNode = currentStatement();
 676         final var derefArg = deref.getDerefArgument();
 677         final var derefStmt = resolveLocationPath(derefArg);
 678         if (derefStmt == null) {
 679             // FIXME: dead code?
 680             throw new IllegalArgumentException(
 681                 "Cannot find deref(" + derefArg + ") target node in context of %s" + leafRefSchemaNode);
 682         }
 683         if (!(derefStmt instanceof TypedDataSchemaNode typed)) {
 684             throw new IllegalArgumentException(
 685                 "deref(" + derefArg + ") resolved to non-typed " + derefStmt + " in context of " + leafRefSchemaNode);
 686         }
 687
 688         // We have a deref() target, decide what to do about it
 689         final var targetType = typed.getType();
 690         if (targetType instanceof InstanceIdentifierTypeDefinition) {
 691             // Static inference breaks down, we cannot determine where this points to
 692             // FIXME: dedicated exception, users can recover from it, derive from IAE
 693             throw new UnsupportedOperationException("Cannot infer instance-identifier reference " + targetType);
 694         }
 695
 696         // deref() is defined only for instance-identifier and leafref types, handle the latter
 697         if (!(targetType instanceof LeafrefTypeDefinition leafref)) {
 698             throw new IllegalArgumentException("Illegal target type " + targetType);
 699         }
 700
 701         final var dereferencedLeafRefPath = leafref.getPathStatement();
 702         final var derefNode = resolvePathExpression(dereferencedLeafRefPath);
 703         // FIXME: revisit these checks
 704         checkArgument(derefStmt != null, "Can not find target node of dereferenced node %s", derefStmt);
 705         checkArgument(derefNode instanceof LeafSchemaNode, "Unexpected %s reference in %s", deref,
 706                 dereferencedLeafRefPath);
 707         return resolveLocationPath(deref.getRelativePath());
 708     }
 709
 710     private @NonNull EffectiveStatement<?, ?> resolveLocationPath(final YangLocationPath path) {
 711         // get the default namespace before we clear and loose our deque
 712         final var defaultNamespace = deque.isEmpty() ? null : ((QName) deque.peekLast().argument()).getModule();
 713         if (path.isAbsolute()) {
 714             clear();
 715         }
 716
 717         EffectiveStatement<?, ?> current = null;
 718         for (var step : path.getSteps()) {
 719             final var axis = step.getAxis();
 720             switch (axis) {
 721                 case PARENT -> {
 722                     verify(step instanceof AxisStep, "Unexpected parent step %s", step);
 723                     try {
 724                         current = exitToDataTree();
 725                     } catch (IllegalStateException | NoSuchElementException e) {
 726                         throw new IllegalArgumentException("Illegal parent access in " + path, e);
 727                     }
 728                 }
 729                 case CHILD -> {
 730                     if (step instanceof QNameStep qnameStep) {
 731                         current = enterChild(qnameStep, defaultNamespace);
 732                     } else {
 733                         throw new VerifyException("Unexpected child step " + step);
 734                     }
 735                 }
 736                 default -> throw new VerifyException("Unexpected step " + step);
 737             }
 738         }
 739
 740         return verifyNotNull(current);
 741     }
 742
 743     private @NonNull EffectiveStatement<?, ?> enterChild(final QNameStep step, final QNameModule defaultNamespace) {
 744         final var toResolve = step.getQName();
 745         final QName qname;
 746         if (toResolve instanceof QName qnameToResolve) {
 747             qname = qnameToResolve;
 748         } else if (toResolve instanceof Unqualified unqual) {
 749             if (defaultNamespace == null) {
 750                 throw new IllegalArgumentException("Can not find target module of step " + step);
 751             }
 752             qname = unqual.bindTo(defaultNamespace);
 753         } else {
 754             throw new VerifyException("Unexpected child step QName " + toResolve);
 755         }
 756         return enterDataTree(qname);
 757     }
 758
 759     /**
 760      * Return an {@link Inference} equivalent of current state.
 761      *
 762      * @return An {@link Inference}
 763      */
 764     public @NonNull Inference toInference() {
 765         return new Inference(modelContext, deque.clone(), currentModule, groupingDepth, clean);
 766     }
 767
 768     /**
 769      * Return an {@link SchemaTreeInference} equivalent of current state.
 770      *
 771      * @return An {@link SchemaTreeInference}
 772      * @throws IllegalStateException if current state cannot be converted to a {@link SchemaTreeInference}
 773      */
 774     public @NonNull SchemaTreeInference toSchemaTreeInference() {
 775         checkInInstantiatedContext();
 776         return DefaultSchemaTreeInference.unsafeOf(modelContext, reconstructDeque().stream()
 777             .map(stmt -> (SchemaTreeEffectiveStatement<?>) stmt)
 778             .collect(ImmutableList.toImmutableList()));
 779     }
 780
 781     private ArrayDeque<EffectiveStatement<?, ?>> reconstructDeque() {
 782         return clean ? deque : reconstructSchemaInferenceStack().deque;
 783     }
 784
 785     /**
 786      * Convert current state into an absolute schema node identifier.
 787      *
 788      * @return Absolute schema node identifier representing current state
 789      * @throws IllegalStateException if current state is not instantiated
 790      */
 791     public @NonNull Absolute toSchemaNodeIdentifier() {
 792         checkInInstantiatedContext();
 793         return Absolute.of(simplePathFromRoot());
 794     }
 795
 796     private void checkInInstantiatedContext() {
 797         if (!inInstantiatedContext()) {
 798             throw new IllegalStateException("Cannot convert uninstantiated context " + this);
 799         }
 800     }
 801
 802     @Override
 803     public String toString() {
 804         return MoreObjects.toStringHelper(this).add("path", deque).toString();
 805     }
 806
 807     private @NonNull GroupingEffectiveStatement pushGrouping(final @NonNull QName nodeIdentifier) {
 808         final var parent = deque.peekLast();
 809         return parent != null ? pushGrouping(parent, nodeIdentifier) : pushFirstGrouping(nodeIdentifier);
 810     }
 811
 812     private @NonNull GroupingEffectiveStatement pushGrouping(final @NonNull EffectiveStatement<?, ?> parent,
 813             final @NonNull QName nodeIdentifier) {
 814         final var ret = parent.streamEffectiveSubstatements(GroupingEffectiveStatement.class)
 815             .filter(stmt -> nodeIdentifier.equals(stmt.argument()))
 816             .findFirst()
 817             .orElseThrow(() -> notPresent(parent, "Grouping", nodeIdentifier));
 818         deque.addLast(ret);
 819         ++groupingDepth;
 820         return ret;
 821     }
 822
 823     private @NonNull GroupingEffectiveStatement pushFirstGrouping(final @NonNull QName nodeIdentifier) {
 824         final var module = getModule(nodeIdentifier);
 825         final var ret = pushGrouping(module, nodeIdentifier);
 826         currentModule = module;
 827         return ret;
 828     }
 829
 830     private @NonNull SchemaTreeEffectiveStatement<?> pushSchema(final @NonNull QName nodeIdentifier) {
 831         final var parent = deque.peekLast();
 832         return parent != null ? pushSchema(parent, nodeIdentifier) : pushFirstSchema(nodeIdentifier);
 833     }
 834
 835     private @NonNull SchemaTreeEffectiveStatement<?> pushSchema(final EffectiveStatement<?, ?> parent,
 836             final @NonNull QName nodeIdentifier) {
 837         if (parent instanceof SchemaTreeAwareEffectiveStatement<?, ?> schemaTreeParent) {
 838             return pushSchema(schemaTreeParent, nodeIdentifier);
 839         }
 840         throw new IllegalStateException("Cannot descend schema tree at " + parent);
 841     }
 842
 843     private @NonNull SchemaTreeEffectiveStatement<?> pushSchema(
 844             final @NonNull SchemaTreeAwareEffectiveStatement<?, ?> parent, final @NonNull QName nodeIdentifier) {
 845         final var ret = parent.findSchemaTreeNode(nodeIdentifier)
 846             .orElseThrow(() -> notPresent(parent, "Schema tree child ", nodeIdentifier));
 847         deque.addLast(ret);
 848         return ret;
 849     }
 850
 851     private @NonNull SchemaTreeEffectiveStatement<?> pushFirstSchema(final @NonNull QName nodeIdentifier) {
 852         final var module = getModule(nodeIdentifier);
 853         final var ret = pushSchema(module, nodeIdentifier);
 854         currentModule = module;
 855         return ret;
 856     }
 857
 858     private @NonNull DataTreeEffectiveStatement<?> pushData(final @NonNull QName nodeIdentifier) {
 859         final var parent = deque.peekLast();
 860         return parent != null ? pushData(parent, nodeIdentifier) : pushFirstData(nodeIdentifier);
 861     }
 862
 863     private @NonNull DataTreeEffectiveStatement<?> pushData(final EffectiveStatement<?, ?> parent,
 864             final @NonNull QName nodeIdentifier) {
 865         if (parent instanceof DataTreeAwareEffectiveStatement<?, ?> dataTreeParent) {
 866             return pushData(dataTreeParent, nodeIdentifier);
 867         }
 868         throw new IllegalStateException("Cannot descend data tree at " + parent);
 869     }
 870
 871     private @NonNull DataTreeEffectiveStatement<?> pushData(final @NonNull DataTreeAwareEffectiveStatement<?, ?> parent,
 872             final @NonNull QName nodeIdentifier) {
 873         final var ret = parent.findDataTreeNode(nodeIdentifier)
 874             .orElseThrow(() -> notPresent(parent, "Data tree child", nodeIdentifier));
 875         deque.addLast(ret);
 876         clean = false;
 877         return ret;
 878     }
 879
 880     private @NonNull DataTreeEffectiveStatement<?> pushFirstData(final @NonNull QName nodeIdentifier) {
 881         final var module = getModule(nodeIdentifier);
 882         final var ret = pushData(module, nodeIdentifier);
 883         currentModule = module;
 884         return ret;
 885     }
 886
 887     private @NonNull TypedefEffectiveStatement pushTypedef(final @NonNull QName nodeIdentifier) {
 888         final var parent = deque.peekLast();
 889         return parent != null ? pushTypedef(parent, nodeIdentifier) : pushFirstTypedef(nodeIdentifier);
 890     }
 891
 892     private @NonNull TypedefEffectiveStatement pushTypedef(final @NonNull EffectiveStatement<?, ?> parent,
 893             final @NonNull QName nodeIdentifier) {
 894         if (parent instanceof TypedefAwareEffectiveStatement<?, ?> aware) {
 895             final var ret = aware.findTypedef(nodeIdentifier)
 896                 .orElseThrow(() -> notPresent(parent, "Typedef", nodeIdentifier));
 897             deque.addLast(ret);
 898             return ret;
 899         }
 900         throw notPresent(parent, "Typedef", nodeIdentifier);
 901     }
 902
 903     private @NonNull TypedefEffectiveStatement pushFirstTypedef(final @NonNull QName nodeIdentifier) {
 904         final var module = getModule(nodeIdentifier);
 905         final var ret = pushTypedef(module, nodeIdentifier);
 906         currentModule = module;
 907         return ret;
 908     }
 909
 910     private @NonNull ModuleEffectiveStatement getModule(final @NonNull QName nodeIdentifier) {
 911         final var module = modelContext.getModuleStatements().get(nodeIdentifier.getModule());
 912         if (module == null) {
 913             throw new IllegalArgumentException("Module for " + nodeIdentifier + " not found");
 914         }
 915         return module;
 916     }
 917
 918     // Unified access to queue iteration for addressing purposes. Since we keep 'logical' steps as executed by user
 919     // at this point, conversion to SchemaNodeIdentifier may be needed. We dispatch based on 'clean'.
 920     private Collection<QName> simplePathFromRoot() {
 921         return clean ? qnames() : reconstructQNames();
 922     }
 923
 924     private Collection<QName> qnames() {
 925         return Collections2.transform(deque, stmt -> {
 926             if (stmt.argument() instanceof QName qname) {
 927                 return qname;
 928             }
 929             throw new VerifyException("Unexpected statement " + stmt);
 930         });
 931     }
 932
 933     // So there are some data tree steps in the stack... we essentially need to convert a data tree item into a series
 934     // of schema tree items. This means at least N searches, but after they are done, we get an opportunity to set the
 935     // clean flag.
 936     private Collection<QName> reconstructQNames() {
 937         return reconstructSchemaInferenceStack().qnames();
 938     }
 939
 940     private SchemaInferenceStack reconstructSchemaInferenceStack() {
 941         // Let's walk all statements and decipher them into a temporary stack
 942         final var tmp = new SchemaInferenceStack(modelContext, deque.size());
 943         for (var stmt : deque) {
 944             // Order of checks is significant
 945             if (stmt instanceof DataTreeEffectiveStatement<?> dataTree) {
 946                 tmp.resolveDataTreeSteps(dataTree.argument());
 947             } else if (stmt instanceof ChoiceEffectiveStatement choice) {
 948                 tmp.resolveChoiceSteps(choice.argument());
 949             } else if (stmt instanceof SchemaTreeEffectiveStatement<?> schemaTree) {
 950                 tmp.enterSchemaTree(schemaTree.argument());
 951             } else if (stmt instanceof GroupingEffectiveStatement grouping) {
 952                 tmp.enterGrouping(grouping.argument());
 953             } else if (stmt instanceof TypedefEffectiveStatement typedef) {
 954                 tmp.enterTypedef(typedef.argument());
 955             } else {
 956                 throw new VerifyException("Unexpected statement " + stmt);
 957             }
 958         }
 959
 960         // if the sizes match, we did not jump through hoops. let's remember that for future.
 961         if (deque.size() == tmp.deque.size()) {
 962             clean = true;
 963             return this;
 964         }
 965         return tmp;
 966     }
 967
 968     private void resolveChoiceSteps(final @NonNull QName nodeIdentifier) {
 969         final var parent = deque.peekLast();
 970         if (parent instanceof ChoiceEffectiveStatement choice) {
 971             resolveChoiceSteps(choice, nodeIdentifier);
 972         } else {
 973             enterSchemaTree(nodeIdentifier);
 974         }
 975     }
 976
 977     private void resolveChoiceSteps(final @NonNull ChoiceEffectiveStatement parent,
 978             final @NonNull QName nodeIdentifier) {
 979         for (var stmt : parent.effectiveSubstatements()) {
 980             if (stmt instanceof CaseEffectiveStatement caze) {
 981                 if (caze.findSchemaTreeNode(nodeIdentifier).orElse(null) instanceof ChoiceEffectiveStatement found) {
 982                     deque.addLast(caze);
 983                     deque.addLast(found);
 984                     return;
 985                 }
 986             }
 987         }
 988         throw new VerifyException("Failed to resolve " + nodeIdentifier + " in " + parent);
 989     }
 990
 991     private void resolveDataTreeSteps(final @NonNull QName nodeIdentifier) {
 992         final var parent = deque.peekLast();
 993         if (parent == null) {
 994             final var module = getModule(nodeIdentifier);
 995             resolveDataTreeSteps(module, nodeIdentifier);
 996             currentModule = module;
 997         } else if (parent instanceof SchemaTreeAwareEffectiveStatement<?, ?> schemaTreeParent) {
 998             resolveDataTreeSteps(schemaTreeParent, nodeIdentifier);
 999         } else {
1000             throw new VerifyException("Unexpected parent " + parent);
1001         }
1002     }
1003
1004     private void resolveDataTreeSteps(final @NonNull SchemaTreeAwareEffectiveStatement<?, ?> parent,
1005             final @NonNull QName nodeIdentifier) {
1006         // The algebra of identifiers in 'schema tree versus data tree':
1007         // - data tree parents are always schema tree parents
1008         // - data tree children are always schema tree children
1009
1010         // that implies that a data tree parent must satisfy schema tree queries with data tree children,
1011         // so a successful lookup of 'data tree parent -> child' and 'schema tree parent -> child' has to be the same
1012         // for a direct lookup.
1013         final var found = parent.findSchemaTreeNode(nodeIdentifier).orElse(null);
1014         if (found instanceof DataTreeEffectiveStatement) {
1015             // ... and it did, we are done
1016             deque.addLast(found);
1017             return;
1018         }
1019
1020         // Alright, so now it's down to filtering choice/case statements. For that we keep some globally-reused state
1021         // and employ a recursive match.
1022         final var match = new ArrayDeque<EffectiveStatement<QName, ?>>();
1023         for (var stmt : parent.effectiveSubstatements()) {
1024             if (stmt instanceof ChoiceEffectiveStatement choice && searchChoice(match, choice, nodeIdentifier)) {
1025                 deque.addAll(match);
1026                 return;
1027             }
1028         }
1029
1030         throw new VerifyException("Failed to resolve " + nodeIdentifier + " in " + parent);
1031     }
1032
1033     private static boolean searchCase(final @NonNull ArrayDeque<EffectiveStatement<QName, ?>> result,
1034             final @NonNull CaseEffectiveStatement parent, final @NonNull QName nodeIdentifier) {
1035         result.addLast(parent);
1036         for (var stmt : parent.effectiveSubstatements()) {
1037             if (stmt instanceof DataTreeEffectiveStatement<?> dataTree && nodeIdentifier.equals(stmt.argument())) {
1038                 result.addLast(dataTree);
1039                 return true;
1040             }
1041             if (stmt instanceof ChoiceEffectiveStatement choice && searchChoice(result, choice, nodeIdentifier)) {
1042                 return true;
1043             }
1044         }
1045         result.removeLast();
1046         return false;
1047     }
1048
1049     private static boolean searchChoice(final @NonNull ArrayDeque<EffectiveStatement<QName, ?>> result,
1050             final @NonNull ChoiceEffectiveStatement parent, final @NonNull QName nodeIdentifier) {
1051         result.addLast(parent);
1052         for (var stmt : parent.effectiveSubstatements()) {
1053             if (stmt instanceof CaseEffectiveStatement caze && searchCase(result, caze, nodeIdentifier)) {
1054                 return true;
1055             }
1056         }
1057         result.removeLast();
1058         return false;
1059     }
1060
1061     private static <T> @NonNull T checkNonNullState(final @Nullable T obj) {
1062         if (obj == null) {
1063             throw new IllegalStateException("Cannot execute on empty stack");
1064         }
1065         return obj;
1066     }
1067
1068     private static @NonNull IllegalArgumentException notPresent(final @NonNull EffectiveStatement<?, ?> parent,
1069             final @NonNull String name, final QName nodeIdentifier) {
1070         return new IllegalArgumentException(name + " " + nodeIdentifier + " not present in " + describeParent(parent));
1071     }
1072
1073     private static @NonNull String describeParent(final @NonNull EffectiveStatement<?, ?> parent) {
1074         // Add just enough information to be useful without being overly-verbose. Note we want to expose namespace
1075         // information, so that we understand what revisions we are dealing with
1076         if (parent instanceof SchemaTreeEffectiveStatement) {
1077             return "schema parent " + parent.argument();
1078         } else if (parent instanceof GroupingEffectiveStatement) {
1079             return "grouping " + parent.argument();
1080         } else if (parent instanceof ModuleEffectiveStatement module) {
1081             return "module " + module.argument().bindTo(module.localQNameModule());
1082         } else {
1083             // Shorthand for QNames, should provide enough context
1084             final var arg = parent.argument();
1085             return "parent " + (arg instanceof QName qname ? qname : parent);
1086         }
1087     }
1088 }