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