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