yang/yang-model-util/src/main/java/org/opendaylight/yangtools/yang/model/util/SchemaInferenceStack.java

   1 /*
   2  * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.model.util;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Preconditions.checkState;
  12 import static com.google.common.base.Verify.verify;
  13 import static java.util.Objects.requireNonNull;
  14
  15 import com.google.common.annotations.Beta;
  16 import com.google.common.base.MoreObjects;
  17 import com.google.common.base.VerifyException;
  18 import com.google.common.collect.ImmutableList;
  19 import com.google.common.collect.Iterators;
  20 import java.util.ArrayDeque;
  21 import java.util.Deque;
  22 import java.util.Iterator;
  23 import java.util.List;
  24 import java.util.NoSuchElementException;
  25 import java.util.Optional;
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.eclipse.jdt.annotation.Nullable;
  28 import org.opendaylight.yangtools.concepts.Mutable;
  29 import org.opendaylight.yangtools.yang.common.QName;
  30 import org.opendaylight.yangtools.yang.model.api.EffectiveModelContext;
  31 import org.opendaylight.yangtools.yang.model.api.EffectiveModelContextProvider;
  32 import org.opendaylight.yangtools.yang.model.api.EffectiveStatementInference;
  33 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  34 import org.opendaylight.yangtools.yang.model.api.SchemaTreeInference;
  35 import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement;
  36 import org.opendaylight.yangtools.yang.model.api.stmt.CaseEffectiveStatement;
  37 import org.opendaylight.yangtools.yang.model.api.stmt.ChoiceEffectiveStatement;
  38 import org.opendaylight.yangtools.yang.model.api.stmt.DataTreeAwareEffectiveStatement;
  39 import org.opendaylight.yangtools.yang.model.api.stmt.DataTreeEffectiveStatement;
  40 import org.opendaylight.yangtools.yang.model.api.stmt.GroupingEffectiveStatement;
  41 import org.opendaylight.yangtools.yang.model.api.stmt.ModuleEffectiveStatement;
  42 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaNodeIdentifier.Absolute;
  43 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeAwareEffectiveStatement;
  44 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeEffectiveStatement;
  45 import org.opendaylight.yangtools.yang.model.spi.AbstractEffectiveStatementInference;
  46 import org.opendaylight.yangtools.yang.model.spi.DefaultSchemaTreeInference;
  47
  48 /**
  49  * A state tracking utility for walking {@link EffectiveModelContext}'s contents along schema/grouping namespaces. This
  50  * is conceptually a stack, tracking {@link EffectiveStatement}s encountered along traversal.
  51  *
  52  * <p>
  53  * This is meant to be a replacement concept for the use of {@link SchemaPath} in various places, notably
  54  * in {@link SchemaContextUtil} methods.
  55  *
  56  * <p>
  57  * This class is designed for single-threaded uses and does not make any guarantees around concurrent access.
  58  */
  59 @Beta
  60 public final class SchemaInferenceStack implements Mutable, EffectiveModelContextProvider {
  61     /**
  62      * Semantic binding of {@link EffectiveStatementInference} produced by {@link SchemaInferenceStack}. Sequence of
  63      * {@link #statementPath()} is implementation-specific.
  64      */
  65     @Beta
  66     public static final class Inference extends AbstractEffectiveStatementInference<EffectiveStatement<?, ?>> {
  67         private final ArrayDeque<EffectiveStatement<?, ?>> deque;
  68         private final ModuleEffectiveStatement currentModule;
  69         private final int groupingDepth;
  70         private final boolean clean;
  71
  72         Inference(final @NonNull EffectiveModelContext modelContext, final ArrayDeque<EffectiveStatement<?, ?>> deque,
  73                 final ModuleEffectiveStatement currentModule, final int groupingDepth, final boolean clean) {
  74             super(modelContext);
  75             this.deque = requireNonNull(deque);
  76             this.currentModule = currentModule;
  77             this.groupingDepth = groupingDepth;
  78             this.clean = clean;
  79         }
  80
  81         @Override
  82         public List<EffectiveStatement<?, ?>> statementPath() {
  83             return ImmutableList.copyOf(deque.descendingIterator());
  84         }
  85
  86         /**
  87          * Convert this inference into a {@link SchemaInferenceStack}.
  88          *
  89          * @return A new stack
  90          */
  91         public @NonNull SchemaInferenceStack toSchemaInferenceStack() {
  92             return new SchemaInferenceStack(getEffectiveModelContext(), deque, currentModule, groupingDepth, clean);
  93         }
  94     }
  95
  96     private final @NonNull EffectiveModelContext effectiveModel;
  97     private final ArrayDeque<EffectiveStatement<?, ?>> deque;
  98
  99     private @Nullable ModuleEffectiveStatement currentModule;
 100     private int groupingDepth;
 101
 102     // True if there were only steps along grouping and schema tree, hence it is consistent with SchemaNodeIdentifier
 103     // False if we have evidence of a data tree lookup succeeding
 104     private boolean clean;
 105
 106     private SchemaInferenceStack(final EffectiveModelContext effectiveModel, final int expectedSize) {
 107         this.deque = new ArrayDeque<>(expectedSize);
 108         this.effectiveModel = requireNonNull(effectiveModel);
 109         this.clean = true;
 110     }
 111
 112     private SchemaInferenceStack(final SchemaInferenceStack source) {
 113         this.deque = source.deque.clone();
 114         this.effectiveModel = source.effectiveModel;
 115         this.currentModule = source.currentModule;
 116         this.groupingDepth = source.groupingDepth;
 117         this.clean = source.clean;
 118     }
 119
 120     private SchemaInferenceStack(final EffectiveModelContext effectiveModel,
 121             final ArrayDeque<EffectiveStatement<?, ?>> deque, final ModuleEffectiveStatement currentModule,
 122             final int groupingDepth, final boolean clean) {
 123         this.effectiveModel = requireNonNull(effectiveModel);
 124         this.deque = deque.clone();
 125         this.currentModule = currentModule;
 126         this.groupingDepth = groupingDepth;
 127         this.clean = clean;
 128     }
 129
 130     private SchemaInferenceStack(final EffectiveModelContext effectiveModel) {
 131         this.effectiveModel = requireNonNull(effectiveModel);
 132         this.deque = new ArrayDeque<>();
 133         this.clean = true;
 134     }
 135
 136     /**
 137      * Create a new empty stack backed by an effective model.
 138      *
 139      * @param effectiveModel EffectiveModelContext to which this stack is attached
 140      * @return A new stack
 141      * @throws NullPointerException if {@code effectiveModel} is null
 142      */
 143     public static @NonNull SchemaInferenceStack of(final EffectiveModelContext effectiveModel) {
 144         return new SchemaInferenceStack(effectiveModel);
 145     }
 146
 147     /**
 148      * Create a new stack backed by an effective model, pointing to specified schema node identified by
 149      * {@link Absolute}.
 150      *
 151      * @param effectiveModel EffectiveModelContext to which this stack is attached
 152      * @return A new stack
 153      * @throws NullPointerException if {@code effectiveModel} is null
 154      * @throws IllegalArgumentException if {@code path} cannot be resolved in the effective model
 155      */
 156     public static @NonNull SchemaInferenceStack of(final EffectiveModelContext effectiveModel, final Absolute path) {
 157         final SchemaInferenceStack ret = new SchemaInferenceStack(effectiveModel);
 158         path.getNodeIdentifiers().forEach(ret::enterSchemaTree);
 159         return ret;
 160     }
 161
 162     /**
 163      * Create a new stack from an {@link EffectiveStatementInference}.
 164      *
 165      * @param inference Inference to use for initialization
 166      * @return A new stack
 167      * @throws NullPointerException if {@code inference} is null
 168      * @throws IllegalArgumentException if {@code inference} implementation is not supported
 169      */
 170     public static @NonNull SchemaInferenceStack ofInference(final EffectiveStatementInference inference) {
 171         if (inference.statementPath().isEmpty()) {
 172             return new SchemaInferenceStack(inference.getEffectiveModelContext());
 173         } else if (inference instanceof SchemaTreeInference) {
 174             return ofInference((SchemaTreeInference) inference);
 175         } else if (inference instanceof Inference) {
 176             return ((Inference) inference).toSchemaInferenceStack();
 177         } else {
 178             throw new IllegalArgumentException("Unsupported Inference " + inference);
 179         }
 180     }
 181
 182     /**
 183      * Create a new stack from an {@link SchemaTreeInference}.
 184      *
 185      * @param inference SchemaTreeInference to use for initialization
 186      * @return A new stack
 187      * @throws NullPointerException if {@code inference} is null
 188      * @throws IllegalArgumentException if {@code inference} cannot be resolved to a valid stack
 189      */
 190     public static @NonNull SchemaInferenceStack ofInference(final SchemaTreeInference inference) {
 191         return of(inference.getEffectiveModelContext(), inference.toSchemaNodeIdentifier());
 192     }
 193
 194     /**
 195      * Create a new stack backed by an effective model, pointing to specified schema node identified by an absolute
 196      * {@link SchemaPath} and its {@link SchemaPath#getPathFromRoot()}.
 197      *
 198      * @param effectiveModel EffectiveModelContext to which this stack is attached
 199      * @return A new stack
 200      * @throws NullPointerException {@code effectiveModel} is null
 201      * @throws IllegalArgumentException if {@code path} cannot be resolved in the effective model or if it is not an
 202      *                                  absolute path.
 203      */
 204     @Deprecated
 205     public static @NonNull SchemaInferenceStack ofInstantiatedPath(final EffectiveModelContext effectiveModel,
 206             final SchemaPath path) {
 207         checkArgument(path.isAbsolute(), "Cannot operate on relative path %s", path);
 208         final SchemaInferenceStack ret = new SchemaInferenceStack(effectiveModel);
 209         path.getPathFromRoot().forEach(ret::enterSchemaTree);
 210         return ret;
 211     }
 212
 213     @Override
 214     public EffectiveModelContext getEffectiveModelContext() {
 215         return effectiveModel;
 216     }
 217
 218     /**
 219      * Create a deep copy of this object.
 220      *
 221      * @return An isolated copy of this object
 222      */
 223     public @NonNull SchemaInferenceStack copy() {
 224         return new SchemaInferenceStack(this);
 225     }
 226
 227     /**
 228      * Check if this stack is empty.
 229      *
 230      * @return True if this stack has not entered any node.
 231      */
 232     public boolean isEmpty() {
 233         return deque.isEmpty();
 234     }
 235
 236     /**
 237      * Return the statement at the top of the stack.
 238      *
 239      * @return Top statement
 240      * @throws IllegalStateException if the stack is empty
 241      */
 242     public @NonNull EffectiveStatement<?, ?> currentStatement() {
 243         return checkNonNullState(deque.peekFirst());
 244     }
 245
 246     /**
 247      * Return current module the stack has entered.
 248      *
 249      * @return Current module
 250      * @throws IllegalStateException if the stack is empty
 251      */
 252     public @NonNull ModuleEffectiveStatement currentModule() {
 253         return checkNonNullState(currentModule);
 254     }
 255
 256     /**
 257      * Check if the stack is in instantiated context. This indicates the stack is non-empty and there is no grouping
 258      * (or similar construct) present in the stack.
 259      *
 260      * @return False if the stack is empty or contains a grouping, true otherwise.
 261      */
 262     public boolean inInstantiatedContext() {
 263         return groupingDepth == 0 && !deque.isEmpty();
 264     }
 265
 266     /**
 267      * Reset this stack to empty state.
 268      */
 269     public void clear() {
 270         deque.clear();
 271         currentModule = null;
 272         groupingDepth = 0;
 273         clean = true;
 274     }
 275
 276     /**
 277      * Lookup a {@code choice} by its node identifier and push it to the stack. This step is very similar to
 278      * {@link #enterSchemaTree(QName)}, except it handles the use case where traversal ignores actual {@code case}
 279      * intermediate schema tree children.
 280      *
 281      * @param nodeIdentifier Node identifier of the grouping to enter
 282      * @return Resolved choice
 283      * @throws NullPointerException if {@code nodeIdentifier} is null
 284      * @throws IllegalArgumentException if the corresponding choice cannot be found
 285      */
 286     public @NonNull ChoiceEffectiveStatement enterChoice(final QName nodeIdentifier) {
 287         final EffectiveStatement<?, ?> parent = deque.peek();
 288         if (parent instanceof ChoiceEffectiveStatement) {
 289             return enterChoice((ChoiceEffectiveStatement) parent, nodeIdentifier);
 290         }
 291
 292         // Fall back to schema tree lookup. Note if it results in non-choice, we rewind before reporting an error
 293         final SchemaTreeEffectiveStatement<?> result = enterSchemaTree(nodeIdentifier);
 294         if (result instanceof ChoiceEffectiveStatement) {
 295             return (ChoiceEffectiveStatement) result;
 296         }
 297         exit();
 298         throw new IllegalArgumentException("Choice " + nodeIdentifier + " not present");
 299     }
 300
 301     // choice -> choice transition, we have to deal with intermediate case nodes
 302     private @NonNull ChoiceEffectiveStatement enterChoice(final ChoiceEffectiveStatement parent,
 303             final QName nodeIdentifier) {
 304         for (EffectiveStatement<?, ?> stmt : parent.effectiveSubstatements()) {
 305             if (stmt instanceof CaseEffectiveStatement) {
 306                 final Optional<ChoiceEffectiveStatement> optMatch = ((CaseEffectiveStatement) stmt)
 307                     .findSchemaTreeNode(nodeIdentifier)
 308                     .filter(ChoiceEffectiveStatement.class::isInstance)
 309                     .map(ChoiceEffectiveStatement.class::cast);
 310                 if (optMatch.isPresent()) {
 311                     final SchemaTreeEffectiveStatement<?> match = optMatch.orElseThrow();
 312                     deque.push(match);
 313                     clean = false;
 314                     return (ChoiceEffectiveStatement) match;
 315                 }
 316             }
 317         }
 318         throw new IllegalArgumentException("Choice " + nodeIdentifier + " not present");
 319     }
 320
 321     /**
 322      * Lookup a {@code grouping} by its node identifier and push it to the stack.
 323      *
 324      * @param nodeIdentifier Node identifier of the grouping to enter
 325      * @return Resolved grouping
 326      * @throws NullPointerException if {@code nodeIdentifier} is null
 327      * @throws IllegalArgumentException if the corresponding grouping cannot be found
 328      */
 329     public @NonNull GroupingEffectiveStatement enterGrouping(final QName nodeIdentifier) {
 330         return pushGrouping(requireNonNull(nodeIdentifier));
 331     }
 332
 333     /**
 334      * Lookup a {@code schema tree} child by its node identifier and push it to the stack.
 335      *
 336      * @param nodeIdentifier Node identifier of the schema tree child to enter
 337      * @return Resolved schema tree child
 338      * @throws NullPointerException if {@code nodeIdentifier} is null
 339      * @throws IllegalArgumentException if the corresponding child cannot be found
 340      */
 341     public @NonNull SchemaTreeEffectiveStatement<?> enterSchemaTree(final QName nodeIdentifier) {
 342         return pushSchema(requireNonNull(nodeIdentifier));
 343     }
 344
 345     /**
 346      * Lookup a {@code schema tree} child by its node identifier and push it to the stack.
 347      *
 348      * @param nodeIdentifier Node identifier of the date tree child to enter
 349      * @return Resolved date tree child
 350      * @throws NullPointerException if {@code nodeIdentifier} is null
 351      * @throws IllegalArgumentException if the corresponding child cannot be found
 352      */
 353     public @NonNull DataTreeEffectiveStatement<?> enterDataTree(final QName nodeIdentifier) {
 354         return pushData(requireNonNull(nodeIdentifier));
 355     }
 356
 357     /**
 358      * Pop the current statement from the stack.
 359      *
 360      * @return Previous statement
 361      * @throws NoSuchElementException if this stack is empty
 362      */
 363     public @NonNull EffectiveStatement<?, ?> exit() {
 364         final EffectiveStatement<?, ?> prev = deque.pop();
 365         if (prev instanceof GroupingEffectiveStatement) {
 366             --groupingDepth;
 367         }
 368         if (deque.isEmpty()) {
 369             currentModule = null;
 370             clean = true;
 371         }
 372         return prev;
 373     }
 374
 375     /**
 376      * Pop the current statement from the stack, asserting it is a {@link DataTreeEffectiveStatement} and that
 377      * subsequent {@link #enterDataTree(QName)} will find it again.
 378      *
 379      * @return Previous statement
 380      * @throws NoSuchElementException if this stack is empty
 381      * @throws IllegalStateException if current statement is not a DataTreeEffectiveStatement or if its parent is not
 382      *                               a {@link DataTreeAwareEffectiveStatement}
 383      */
 384     public @NonNull DataTreeEffectiveStatement<?> exitToDataTree() {
 385         final EffectiveStatement<?, ?> child = exit();
 386         checkState(child instanceof DataTreeEffectiveStatement, "Unexpected current %s", child);
 387         final EffectiveStatement<?, ?> parent = deque.peekFirst();
 388         checkState(parent == null || parent instanceof DataTreeAwareEffectiveStatement, "Unexpected parent %s", parent);
 389         return (DataTreeEffectiveStatement<?>) child;
 390     }
 391
 392     /**
 393      * Return an {@link Inference} equivalent of current state.
 394      *
 395      * @return An {@link Inference}
 396      */
 397     public @NonNull Inference toInference() {
 398         return new Inference(effectiveModel, deque.clone(), currentModule, groupingDepth, clean);
 399     }
 400
 401     /**
 402      * Return an {@link SchemaTreeInference} equivalent of current state.
 403      *
 404      * @return An {@link SchemaTreeInference}
 405      * @throws IllegalStateException if current state cannot be converted to a {@link SchemaTreeInference}
 406      */
 407     public @NonNull SchemaTreeInference toSchemaTreeInference() {
 408         return DefaultSchemaTreeInference.of(getEffectiveModelContext(), toSchemaNodeIdentifier());
 409     }
 410
 411     /**
 412      * Convert current state into an absolute schema node identifier.
 413      *
 414      * @return Absolute schema node identifier representing current state
 415      * @throws IllegalStateException if current state is not instantiated
 416      */
 417     public @NonNull Absolute toSchemaNodeIdentifier() {
 418         checkState(inInstantiatedContext(), "Cannot convert uninstantiated context %s", this);
 419         return Absolute.of(ImmutableList.<QName>builderWithExpectedSize(deque.size())
 420             .addAll(simplePathFromRoot())
 421             .build());
 422     }
 423
 424     /**
 425      * Convert current state into a SchemaPath.
 426      *
 427      * @return Absolute SchemaPath representing current state
 428      * @throws IllegalStateException if current state is not instantiated
 429      * @deprecated This method is meant only for interoperation with SchemaPath-based APIs.
 430      */
 431     @Deprecated
 432     public @NonNull SchemaPath toSchemaPath() {
 433         SchemaPath ret = SchemaPath.ROOT;
 434         final Iterator<QName> it = simplePathFromRoot();
 435         while (it.hasNext()) {
 436             ret = ret.createChild(it.next());
 437         }
 438         return ret;
 439     }
 440
 441     /**
 442      * Return an iterator along {@link SchemaPath#getPathFromRoot()}. This method is a faster equivalent of
 443      * {@code toSchemaPath().getPathFromRoot().iterator()}.
 444      *
 445      * @return An unmodifiable iterator
 446      */
 447     @Deprecated
 448     public @NonNull Iterator<QName> schemaPathIterator() {
 449         return Iterators.unmodifiableIterator(simplePathFromRoot());
 450     }
 451
 452     @Override
 453     public String toString() {
 454         return MoreObjects.toStringHelper(this).add("stack", deque).toString();
 455     }
 456
 457     private @NonNull GroupingEffectiveStatement pushGrouping(final @NonNull QName nodeIdentifier) {
 458         final EffectiveStatement<?, ?> parent = deque.peekFirst();
 459         return parent != null ? pushGrouping(parent, nodeIdentifier) : pushFirstGrouping(nodeIdentifier);
 460     }
 461
 462     private @NonNull GroupingEffectiveStatement pushGrouping(final @NonNull EffectiveStatement<?, ?> parent,
 463             final @NonNull QName nodeIdentifier) {
 464         final GroupingEffectiveStatement ret = parent.streamEffectiveSubstatements(GroupingEffectiveStatement.class)
 465             .filter(stmt -> nodeIdentifier.equals(stmt.argument()))
 466             .findFirst()
 467             .orElseThrow(() -> new IllegalArgumentException("Grouping " + nodeIdentifier + " not present"));
 468         deque.push(ret);
 469         ++groupingDepth;
 470         return ret;
 471     }
 472
 473     private @NonNull GroupingEffectiveStatement pushFirstGrouping(final @NonNull QName nodeIdentifier) {
 474         final ModuleEffectiveStatement module = getModule(nodeIdentifier);
 475         final GroupingEffectiveStatement ret = pushGrouping(module, nodeIdentifier);
 476         currentModule = module;
 477         return ret;
 478     }
 479
 480     private @NonNull SchemaTreeEffectiveStatement<?> pushSchema(final @NonNull QName nodeIdentifier) {
 481         final EffectiveStatement<?, ?> parent = deque.peekFirst();
 482         return parent != null ? pushSchema(parent, nodeIdentifier) : pushFirstSchema(nodeIdentifier);
 483     }
 484
 485     private @NonNull SchemaTreeEffectiveStatement<?> pushSchema(final EffectiveStatement<?, ?> parent,
 486             final @NonNull QName nodeIdentifier) {
 487         checkState(parent instanceof SchemaTreeAwareEffectiveStatement, "Cannot descend schema tree at %s", parent);
 488         return pushSchema((SchemaTreeAwareEffectiveStatement<?, ?>) parent, nodeIdentifier);
 489     }
 490
 491     private @NonNull SchemaTreeEffectiveStatement<?> pushSchema(
 492             final @NonNull SchemaTreeAwareEffectiveStatement<?, ?> parent, final @NonNull QName nodeIdentifier) {
 493         final SchemaTreeEffectiveStatement<?> ret = parent.findSchemaTreeNode(nodeIdentifier).orElseThrow(
 494             () -> new IllegalArgumentException("Schema tree child " + nodeIdentifier + " not present"));
 495         deque.push(ret);
 496         return ret;
 497     }
 498
 499     private @NonNull SchemaTreeEffectiveStatement<?> pushFirstSchema(final @NonNull QName nodeIdentifier) {
 500         final ModuleEffectiveStatement module = getModule(nodeIdentifier);
 501         final SchemaTreeEffectiveStatement<?> ret = pushSchema(module, nodeIdentifier);
 502         currentModule = module;
 503         return ret;
 504     }
 505
 506     private @NonNull DataTreeEffectiveStatement<?> pushData(final @NonNull QName nodeIdentifier) {
 507         final EffectiveStatement<?, ?> parent = deque.peekFirst();
 508         return parent != null ? pushData(parent, nodeIdentifier) : pushFirstData(nodeIdentifier);
 509     }
 510
 511     private @NonNull DataTreeEffectiveStatement<?> pushData(final EffectiveStatement<?, ?> parent,
 512             final @NonNull QName nodeIdentifier) {
 513         checkState(parent instanceof DataTreeAwareEffectiveStatement, "Cannot descend data tree at %s", parent);
 514         return pushData((DataTreeAwareEffectiveStatement<?, ?>) parent, nodeIdentifier);
 515     }
 516
 517     private @NonNull DataTreeEffectiveStatement<?> pushData(final @NonNull DataTreeAwareEffectiveStatement<?, ?> parent,
 518             final @NonNull QName nodeIdentifier) {
 519         final DataTreeEffectiveStatement<?> ret = parent.findDataTreeNode(nodeIdentifier).orElseThrow(
 520             () -> new IllegalArgumentException("Schema tree child " + nodeIdentifier + " not present"));
 521         deque.push(ret);
 522         clean = false;
 523         return ret;
 524     }
 525
 526     private @NonNull DataTreeEffectiveStatement<?> pushFirstData(final @NonNull QName nodeIdentifier) {
 527         final ModuleEffectiveStatement module = getModule(nodeIdentifier);
 528         final DataTreeEffectiveStatement<?> ret = pushData(module, nodeIdentifier);
 529         currentModule = module;
 530         return ret;
 531     }
 532
 533     private @NonNull ModuleEffectiveStatement getModule(final @NonNull QName nodeIdentifier) {
 534         final ModuleEffectiveStatement module = effectiveModel.getModuleStatements().get(nodeIdentifier.getModule());
 535         checkArgument(module != null, "Module for %s not found", nodeIdentifier);
 536         return module;
 537     }
 538
 539     // Unified access to queue iteration for addressing purposes. Since we keep 'logical' steps as executed by user
 540     // at this point, conversion to SchemaNodeIdentifier may be needed. We dispatch based on 'clean'.
 541     private Iterator<QName> simplePathFromRoot() {
 542         return clean ? iterateQNames() : reconstructQNames();
 543     }
 544
 545     private Iterator<QName> iterateQNames() {
 546         return Iterators.transform(deque.descendingIterator(), stmt -> {
 547             final Object argument = stmt.argument();
 548             verify(argument instanceof QName, "Unexpected statement %s", stmt);
 549             return (QName) argument;
 550         });
 551     }
 552
 553     // So there are some data tree steps in the stack... we essentially need to convert a data tree item into a series
 554     // of schema tree items. This means at least N searches, but after they are done, we get an opportunity to set the
 555     // clean flag.
 556     private Iterator<QName> reconstructQNames() {
 557         // Let's walk all statements and decipher them into a temporary stack
 558         final SchemaInferenceStack tmp = new SchemaInferenceStack(effectiveModel, deque.size());
 559         final Iterator<EffectiveStatement<?, ?>> it = deque.descendingIterator();
 560         while (it.hasNext()) {
 561             final EffectiveStatement<?, ?> stmt = it.next();
 562             // Order of checks is significant
 563             if (stmt instanceof DataTreeEffectiveStatement) {
 564                 tmp.resolveDataTreeSteps(((DataTreeEffectiveStatement<?>) stmt).argument());
 565             } else if (stmt instanceof ChoiceEffectiveStatement) {
 566                 tmp.resolveChoiceSteps(((ChoiceEffectiveStatement) stmt).argument());
 567             } else if (stmt instanceof SchemaTreeEffectiveStatement) {
 568                 tmp.enterSchemaTree(((SchemaTreeEffectiveStatement<?> )stmt).argument());
 569             } else if (stmt instanceof GroupingEffectiveStatement) {
 570                 tmp.enterGrouping(((GroupingEffectiveStatement) stmt).argument());
 571             } else {
 572                 throw new VerifyException("Unexpected statement " + stmt);
 573             }
 574         }
 575
 576         // if the sizes match, we did not jump through hoops. let's remember that for future.
 577         clean = deque.size() == tmp.deque.size();
 578         return tmp.iterateQNames();
 579     }
 580
 581     private void resolveChoiceSteps(final @NonNull QName nodeIdentifier) {
 582         final EffectiveStatement<?, ?> parent = deque.peekFirst();
 583         if (parent instanceof ChoiceEffectiveStatement) {
 584             resolveChoiceSteps((ChoiceEffectiveStatement) parent, nodeIdentifier);
 585         } else {
 586             enterSchemaTree(nodeIdentifier);
 587         }
 588     }
 589
 590     private void resolveChoiceSteps(final @NonNull ChoiceEffectiveStatement parent,
 591             final @NonNull QName nodeIdentifier) {
 592         for (EffectiveStatement<?, ?> stmt : parent.effectiveSubstatements()) {
 593             if (stmt instanceof CaseEffectiveStatement) {
 594                 final CaseEffectiveStatement caze = (CaseEffectiveStatement) stmt;
 595                 final SchemaTreeEffectiveStatement<?> found = caze.findSchemaTreeNode(nodeIdentifier).orElse(null);
 596                 if (found instanceof ChoiceEffectiveStatement) {
 597                     deque.push(caze);
 598                     deque.push(found);
 599                     return;
 600                 }
 601             }
 602         }
 603         throw new VerifyException("Failed to resolve " + nodeIdentifier + " in " + parent);
 604     }
 605
 606     private void resolveDataTreeSteps(final @NonNull QName nodeIdentifier) {
 607         final EffectiveStatement<?, ?> parent = deque.peekFirst();
 608         if (parent != null) {
 609             verify(parent instanceof SchemaTreeAwareEffectiveStatement, "Unexpected parent %s", parent);
 610             resolveDataTreeSteps((SchemaTreeAwareEffectiveStatement<?, ?>) parent, nodeIdentifier);
 611             return;
 612         }
 613
 614         final ModuleEffectiveStatement module = getModule(nodeIdentifier);
 615         resolveDataTreeSteps(module, nodeIdentifier);
 616         currentModule = module;
 617     }
 618
 619     private void resolveDataTreeSteps(final @NonNull SchemaTreeAwareEffectiveStatement<?, ?> parent,
 620             final @NonNull QName nodeIdentifier) {
 621         // The algebra of identifiers in 'schema tree versus data tree':
 622         // - data tree parents are always schema tree parents
 623         // - data tree children are always schema tree children
 624
 625         // that implies that a data tree parent must satisfy schema tree queries with data tree children,
 626         // so a successful lookup of 'data tree parent -> child' and 'schema tree parent -> child' has to be the same
 627         // for a direct lookup.
 628         final SchemaTreeEffectiveStatement<?> found = parent.findSchemaTreeNode(nodeIdentifier).orElse(null);
 629         if (found instanceof DataTreeEffectiveStatement) {
 630             // ... and it did, we are done
 631             deque.push(found);
 632             return;
 633         }
 634
 635         // Alright, so now it's down to filtering choice/case statements. For that we keep some globally-reused state
 636         // and employ a recursive match.
 637         final Deque<EffectiveStatement<QName, ?>> match = new ArrayDeque<>();
 638         for (EffectiveStatement<?, ?> stmt : parent.effectiveSubstatements()) {
 639             if (stmt instanceof ChoiceEffectiveStatement
 640                 && searchChoice(match, (ChoiceEffectiveStatement) stmt, nodeIdentifier)) {
 641                 match.descendingIterator().forEachRemaining(deque::push);
 642                 return;
 643             }
 644         }
 645
 646         throw new VerifyException("Failed to resolve " + nodeIdentifier + " in " + parent);
 647     }
 648
 649     private static boolean searchCase(final @NonNull Deque<EffectiveStatement<QName, ?>> result,
 650             final @NonNull CaseEffectiveStatement parent, final @NonNull QName nodeIdentifier) {
 651         result.push(parent);
 652         for (EffectiveStatement<?, ?> stmt : parent.effectiveSubstatements()) {
 653             if (stmt instanceof DataTreeEffectiveStatement && nodeIdentifier.equals(stmt.argument())) {
 654                 result.push((DataTreeEffectiveStatement<?>) stmt);
 655                 return true;
 656             }
 657             if (stmt instanceof ChoiceEffectiveStatement
 658                 && searchChoice(result, (ChoiceEffectiveStatement) stmt, nodeIdentifier)) {
 659                 return true;
 660             }
 661         }
 662         result.pop();
 663         return false;
 664     }
 665
 666     private static boolean searchChoice(final @NonNull Deque<EffectiveStatement<QName, ?>> result,
 667             final @NonNull ChoiceEffectiveStatement parent, final @NonNull QName nodeIdentifier) {
 668         result.push(parent);
 669         for (EffectiveStatement<?, ?> stmt : parent.effectiveSubstatements()) {
 670             if (stmt instanceof CaseEffectiveStatement
 671                 && searchCase(result, (CaseEffectiveStatement) stmt, nodeIdentifier)) {
 672                 return true;
 673             }
 674         }
 675         result.pop();
 676         return false;
 677     }
 678
 679     private static <T> @NonNull T checkNonNullState(final @Nullable T obj) {
 680         if (obj == null) {
 681             throw new IllegalStateException("Cannot execute on empty stack");
 682         }
 683         return obj;
 684     }
 685 }