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