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