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