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