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