2 * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved.
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
8 package org.opendaylight.yangtools.yang.parser.stmt.reactor;
10 import static com.google.common.base.Verify.verify;
11 import static java.util.Objects.requireNonNull;
13 import com.google.common.base.VerifyException;
14 import com.google.common.collect.ImmutableList;
15 import com.google.common.collect.Streams;
16 import java.util.ArrayList;
17 import java.util.Collection;
18 import java.util.HashMap;
19 import java.util.Iterator;
20 import java.util.List;
22 import java.util.Objects;
23 import java.util.Optional;
24 import java.util.stream.Collectors;
25 import java.util.stream.Stream;
26 import org.eclipse.jdt.annotation.NonNull;
27 import org.eclipse.jdt.annotation.Nullable;
28 import org.opendaylight.yangtools.concepts.Immutable;
29 import org.opendaylight.yangtools.yang.common.QName;
30 import org.opendaylight.yangtools.yang.common.QNameModule;
31 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
32 import org.opendaylight.yangtools.yang.model.api.meta.DeclaredStatement;
33 import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement;
34 import org.opendaylight.yangtools.yang.model.api.meta.StatementDefinition;
35 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeEffectiveStatement;
36 import org.opendaylight.yangtools.yang.parser.spi.SchemaTreeNamespace;
37 import org.opendaylight.yangtools.yang.parser.spi.meta.CopyType;
38 import org.opendaylight.yangtools.yang.parser.spi.meta.InferenceException;
39 import org.opendaylight.yangtools.yang.parser.spi.meta.NamespaceBehaviour.OnDemandSchemaTreeStorageNode;
40 import org.opendaylight.yangtools.yang.parser.spi.meta.NamespaceBehaviour.StorageNodeType;
41 import org.opendaylight.yangtools.yang.parser.spi.meta.StatementFactory;
42 import org.opendaylight.yangtools.yang.parser.spi.meta.StmtContext;
43 import org.opendaylight.yangtools.yang.parser.spi.meta.StmtContextUtils;
44 import org.opendaylight.yangtools.yang.parser.spi.source.StatementSourceReference;
45 import org.slf4j.Logger;
46 import org.slf4j.LoggerFactory;
49 * A statement which has been inferred to exist. Functionally it is equivalent to a SubstatementContext, but it is not
50 * backed by a declaration (and declared statements). It is backed by a prototype StatementContextBase and has only
51 * effective substatements, which are either transformed from that prototype or added by inference.
53 final class InferredStatementContext<A, D extends DeclaredStatement<A>, E extends EffectiveStatement<A, D>>
54 extends StatementContextBase<A, D, E> implements OnDemandSchemaTreeStorageNode {
55 // An effective copy view, with enough information to decide what to do next
56 private static final class EffectiveCopy implements Immutable {
58 private final ReactorStmtCtx<?, ?, ?> orig;
59 // Effective view, if the statement is to be reused it equals to orig
60 private final ReactorStmtCtx<?, ?, ?> copy;
62 EffectiveCopy(final ReactorStmtCtx<?, ?, ?> orig, final ReactorStmtCtx<?, ?, ?> copy) {
63 this.orig = requireNonNull(orig);
64 this.copy = requireNonNull(copy);
71 ReactorStmtCtx<?, ?, ?> toChildContext(final @NonNull InferredStatementContext<?, ?, ?> parent) {
72 return isReused() ? orig.replicaAsChildOf(parent) : copy;
75 ReactorStmtCtx<?, ?, ?> toReusedChild(final @NonNull InferredStatementContext<?, ?, ?> parent) {
76 verify(isReused(), "Attempted to discard copy %s", copy);
77 return orig.replicaAsChildOf(parent);
81 private static final Logger LOG = LoggerFactory.getLogger(InferredStatementContext.class);
83 // Sentinel objects for 'substatements', String is a good enough type
84 private static final @NonNull String REUSED_SUBSTATEMENTS = "reused";
85 private static final @NonNull String SWEPT_SUBSTATEMENTS = "swept";
87 private final @NonNull StatementContextBase<A, D, E> prototype;
88 private final @NonNull StatementContextBase<?, ?, ?> parent;
89 private final @NonNull StmtContext<A, D, E> originalCtx;
90 // TODO: consider encoding this in StatementContextBase fields, there should be plenty of room
91 private final @NonNull CopyType childCopyType;
92 private final QNameModule targetModule;
93 private final A argument;
96 * Effective substatements, lazily materialized. This field can have four states:
98 * <li>it can be {@code null}, in which case no materialization has taken place</li>
99 * <li>it can be a {@link HashMap}, in which case partial materialization has taken place</li>
100 * <li>it can be a {@link List}, in which case full materialization has taken place</li>
101 * <li>it can be {@link SWEPT_SUBSTATEMENTS}, in which case materialized state is no longer available</li>
104 private Object substatements;
106 private InferredStatementContext(final InferredStatementContext<A, D, E> original,
107 final StatementContextBase<?, ?, ?> parent) {
109 this.parent = requireNonNull(parent);
110 this.childCopyType = original.childCopyType;
111 this.targetModule = original.targetModule;
112 this.prototype = original.prototype;
113 this.originalCtx = original.originalCtx;
114 this.argument = original.argument;
115 // Substatements are initialized here
116 this.substatements = ImmutableList.of();
119 InferredStatementContext(final StatementContextBase<?, ?, ?> parent, final StatementContextBase<A, D, E> prototype,
120 final CopyType myCopyType, final CopyType childCopyType, final QNameModule targetModule) {
121 super(prototype, myCopyType);
122 this.parent = requireNonNull(parent);
123 this.prototype = requireNonNull(prototype);
124 this.argument = targetModule == null ? prototype.argument()
125 : prototype.definition().adaptArgumentValue(prototype, targetModule);
126 this.childCopyType = requireNonNull(childCopyType);
127 this.targetModule = targetModule;
128 this.originalCtx = prototype.getOriginalCtx().orElse(prototype);
130 // Mark prototype as blocking statement cleanup
135 public Collection<? extends StatementContextBase<?, ?, ?>> mutableDeclaredSubstatements() {
136 return ImmutableList.of();
140 public Collection<? extends Mutable<?, ?, ?>> mutableEffectiveSubstatements() {
141 return mutableEffectiveSubstatements(ensureEffectiveSubstatements());
145 public Iterable<? extends StmtContext<?, ?, ?>> allSubstatements() {
146 // No need to concat with declared
147 return effectiveSubstatements();
151 public Stream<? extends StmtContext<?, ?, ?>> allSubstatementsStream() {
152 // No need to concat with declared
153 return effectiveSubstatements().stream();
157 public StatementSourceReference sourceReference() {
158 return originalCtx.sourceReference();
162 public String rawArgument() {
163 return originalCtx.rawArgument();
167 public Optional<StmtContext<A, D, E>> getOriginalCtx() {
168 return Optional.of(originalCtx);
172 public Optional<StmtContext<A, D, E>> getPreviousCopyCtx() {
173 return Optional.of(prototype);
177 public D declared() {
179 * Share original instance of declared statement between all effective statements which have been copied or
180 * derived from this original declared statement.
182 return originalCtx.declared();
186 public void removeStatementFromEffectiveSubstatements(final StatementDefinition statementDef) {
187 substatements = removeStatementFromEffectiveSubstatements(ensureEffectiveSubstatements(), statementDef);
191 public void removeStatementFromEffectiveSubstatements(final StatementDefinition statementDef,
192 final String statementArg) {
193 substatements = removeStatementFromEffectiveSubstatements(ensureEffectiveSubstatements(), statementDef,
198 public void addEffectiveSubstatement(final Mutable<?, ?, ?> substatement) {
199 substatements = addEffectiveSubstatement(ensureEffectiveSubstatements(), substatement);
203 void addEffectiveSubstatementsImpl(final Collection<? extends Mutable<?, ?, ?>> statements) {
204 substatements = addEffectiveSubstatementsImpl(ensureEffectiveSubstatements(), statements);
208 InferredStatementContext<A, D, E> reparent(final StatementContextBase<?, ?, ?> newParent) {
209 return new InferredStatementContext<>(this, newParent);
213 E createEffective(final StatementFactory<A, D, E> factory) {
214 // If we have not materialized we do not have a difference in effective substatements, hence we can forward
215 // towards the source of the statement.
216 accessSubstatements();
217 return substatements == null ? tryToReusePrototype(factory) : super.createEffective(factory);
220 private @NonNull E tryToReusePrototype(final StatementFactory<A, D, E> factory) {
221 final E origEffective = prototype.buildEffective();
222 final Collection<? extends @NonNull EffectiveStatement<?, ?>> origSubstatements =
223 origEffective.effectiveSubstatements();
225 // First check if we can reuse the entire prototype
226 if (!factory.canReuseCurrent(this, prototype, origSubstatements)) {
227 // FIXME: YANGTOOLS-1214: deduplicate this return
228 return tryToReuseSubstatements(factory, origEffective);
231 // We can reuse this statement let's see if all statements agree...
232 // ... no substatements to deal with, we can freely reuse the original
233 if (origSubstatements.isEmpty()) {
234 LOG.debug("Reusing empty: {}", origEffective);
235 substatements = ImmutableList.of();
237 return origEffective;
240 // ... all are context independent, reuse the original
241 if (allSubstatementsContextIndependent()) {
242 LOG.debug("Reusing context-independent: {}", origEffective);
243 substatements = noRefs() ? REUSED_SUBSTATEMENTS : reusePrototypeReplicas();
245 return origEffective;
248 // ... copy-sensitive check
249 final List<EffectiveCopy> declCopy = prototype.streamDeclared()
250 .map(sub -> effectiveCopy((ReactorStmtCtx<?, ?, ?>) sub))
251 .filter(Objects::nonNull)
252 .collect(Collectors.toUnmodifiableList());
253 final List<EffectiveCopy> effCopy = prototype.streamEffective()
254 .map(sub -> effectiveCopy((ReactorStmtCtx<?, ?, ?>) sub))
255 .filter(Objects::nonNull)
256 .collect(Collectors.toUnmodifiableList());
258 // ... are any copy-sensitive?
259 if (allReused(declCopy) && allReused(effCopy)) {
260 LOG.debug("Reusing after substatement check: {}", origEffective);
261 substatements = noRefs() ? REUSED_SUBSTATEMENTS
262 : reusePrototypeReplicas(Streams.concat(declCopy.stream(), effCopy.stream())
263 .map(copy -> copy.toReusedChild(this)));
265 return origEffective;
268 // *sigh*, ok, heavy lifting through a shallow copy
269 final List<ReactorStmtCtx<?, ?, ?>> declared = declCopy.stream()
270 .map(copy -> copy.toChildContext(this))
271 .collect(ImmutableList.toImmutableList());
272 final List<ReactorStmtCtx<?, ?, ?>> effective = effCopy.stream()
273 .map(copy -> copy.toChildContext(this))
274 .collect(ImmutableList.toImmutableList());
275 substatements = declared.isEmpty() ? effective
276 : Streams.concat(declared.stream(), effective.stream()).collect(ImmutableList.toImmutableList());
279 // Values are the effective copies, hence this efficiently deals with recursion.
280 // FIXME: YANGTOOLS-1214: deduplicate this return
281 return factory.createEffective(this, declared.stream(), effective.stream());
284 private @NonNull E tryToReuseSubstatements(final StatementFactory<A, D, E> factory, final @NonNull E original) {
285 if (allSubstatementsContextIndependent()) {
286 LOG.debug("Reusing substatements of: {}", prototype);
287 substatements = noRefs() ? REUSED_SUBSTATEMENTS : reusePrototypeReplicas();
289 return factory.copyEffective(this, original);
292 // Fall back to full instantiation, which populates our substatements. Then check if we should be reusing
293 // the substatement list, as this operation turned out to not affect them.
294 final E effective = super.createEffective(factory);
295 // Since we have forced instantiation to deal with this case, we also need to reset the 'modified' flag
298 if (sameSubstatements(original.effectiveSubstatements(), effective)) {
299 LOG.debug("Reusing unchanged substatements of: {}", prototype);
300 return factory.copyEffective(this, original);
305 private List<ReactorStmtCtx<?, ?, ?>> reusePrototypeReplicas() {
306 return reusePrototypeReplicas(Streams.concat(prototype.streamDeclared(), prototype.streamEffective()));
309 private List<ReactorStmtCtx<?, ?, ?>> reusePrototypeReplicas(final Stream<StmtContext<?, ?, ?>> stream) {
312 final ReplicaStatementContext<?, ?, ?> ret = ((ReactorStmtCtx<?, ?, ?>) stmt).replicaAsChildOf(this);
313 ret.buildEffective();
316 .collect(Collectors.toUnmodifiableList());
319 private static boolean sameSubstatements(final Collection<?> original, final EffectiveStatement<?, ?> effective) {
320 final Collection<?> copied = effective.effectiveSubstatements();
321 if (copied != effective.effectiveSubstatements() || original.size() != copied.size()) {
322 // Do not bother if result is treating substatements as transient
326 final Iterator<?> oit = original.iterator();
327 final Iterator<?> cit = copied.iterator();
328 while (oit.hasNext()) {
329 verify(cit.hasNext());
330 // Identity comparison on purpose to side-step whatever equality there might be. We want to reuse instances
332 if (oit.next() != cit.next()) {
336 verify(!cit.hasNext());
340 private static boolean allReused(final List<EffectiveCopy> entries) {
341 return entries.stream().allMatch(EffectiveCopy::isReused);
345 ReactorStmtCtx<A, D, E> unmodifiedEffectiveSource() {
346 return isModified() ? this : prototype.unmodifiedEffectiveSource();
350 boolean hasEmptySubstatements() {
351 if (substatements == null) {
352 return prototype.hasEmptySubstatements();
354 return substatements instanceof HashMap ? false : ((List<?>) substatements).isEmpty();
358 boolean noSensitiveSubstatements() {
359 accessSubstatements();
360 if (substatements == null) {
361 // No difference, defer to prototype
362 return prototype.allSubstatementsContextIndependent();
364 if (substatements instanceof List) {
365 // Fully materialized, walk all statements
366 return noSensitiveSubstatements(castEffective(substatements));
369 // Partially-materialized. This case has three distinct outcomes:
370 // - prototype does not have a sensitive statement (1)
371 // - protype has a sensitive substatement, and
372 // - we have not marked is as unsupported (2)
373 // - we have marked it as unsupported (3)
375 // Determining the outcome between (2) and (3) is a bother, this check errs on the side of false negative side
376 // and treats (3) as (2) -- i.e. even if we marked a sensitive statement as unsupported, we still consider it
377 // as affecting the result.
378 return prototype.allSubstatementsContextIndependent()
379 && noSensitiveSubstatements(castMaterialized(substatements).values());
383 <X, Z extends EffectiveStatement<X, ?>> @NonNull Optional<X> findSubstatementArgumentImpl(
384 final @NonNull Class<Z> type) {
385 if (substatements instanceof List) {
386 return super.findSubstatementArgumentImpl(type);
389 final Optional<X> templateArg = prototype.findSubstatementArgument(type);
390 if (templateArg.isEmpty()) {
393 if (SchemaTreeEffectiveStatement.class.isAssignableFrom(type)) {
394 // X is known to be QName
395 return (Optional<X>) templateArg.map(template -> ((QName) template).bindTo(targetModule));
401 boolean hasSubstatementImpl(final @NonNull Class<? extends EffectiveStatement<?, ?>> type) {
402 return substatements instanceof List ? super.hasSubstatementImpl(type)
403 // We do not allow deletion of partially-materialized statements, hence this is accurate
404 : prototype.hasSubstatement(type);
408 public <Y extends DeclaredStatement<QName>, Z extends SchemaTreeEffectiveStatement<Y>>
409 StmtContext<QName, Y, Z> requestSchemaTreeChild(final QName qname) {
410 if (substatements instanceof List) {
411 // We have performed materialization, hence we have triggered creation of all our schema tree child
416 final QName templateQName = qname.bindTo(StmtContextUtils.getRootModuleQName(prototype));
417 LOG.debug("Materializing child {} from {}", qname, templateQName);
419 final StmtContext<?, ?, ?> template;
420 if (prototype instanceof InferredStatementContext) {
421 // Note: we need to access namespace here, as the target statement may have already been populated, in which
422 // case we want to obtain the statement in local namespace storage.
423 template = (StmtContext) ((InferredStatementContext<?, ?, ?>) prototype).getFromNamespace(
424 SchemaTreeNamespace.class, templateQName);
426 template = prototype.allSubstatementsStream()
427 .filter(stmt -> stmt.producesEffective(SchemaTreeEffectiveStatement.class)
428 && templateQName.equals(stmt.argument()))
433 if (template == null) {
434 // We do not have a template, this child does not exist. It may be added later, but that is someone else's
436 LOG.debug("Child {} does not have a template", qname);
440 @SuppressWarnings("unchecked")
441 final Mutable<QName, Y, Z> ret = (Mutable<QName, Y, Z>) copySubstatement((Mutable<?, ?, ?>) template)
443 () -> new InferenceException(this, "Failed to materialize child %s template %s", qname, template));
444 ensureCompletedPhase(ret);
445 addMaterialized(template, ret);
447 LOG.debug("Child {} materialized", qname);
451 // Instantiate this statement's effective substatements. Note this method has side-effects in namespaces and overall
452 // BuildGlobalContext, hence it must be called at most once.
453 private List<ReactorStmtCtx<?, ?, ?>> ensureEffectiveSubstatements() {
454 accessSubstatements();
455 return substatements instanceof List ? castEffective(substatements)
456 : initializeSubstatements(castMaterialized(substatements));
460 Iterable<ReactorStmtCtx<?, ?, ?>> effectiveChildrenToComplete() {
461 // When we have not initialized, there are no statements to catch up: we will catch up when we are copying
462 // from prototype (which is already at ModelProcessingPhase.EFFECTIVE_MODEL).
463 if (substatements == null) {
464 return ImmutableList.of();
466 accessSubstatements();
467 if (substatements instanceof HashMap) {
468 return castMaterialized(substatements).values();
470 return castEffective(substatements);
475 Stream<? extends @NonNull StmtContext<?, ?, ?>> streamDeclared() {
476 return Stream.empty();
480 Stream<? extends @NonNull StmtContext<?, ?, ?>> streamEffective() {
481 return ensureEffectiveSubstatements().stream().filter(StmtContext::isSupportedToBuildEffective);
484 private void accessSubstatements() {
485 if (substatements instanceof String) {
486 throw new VerifyException("Access to " + substatements + " substatements of " + this);
491 void markNoParentRef() {
492 final Object local = substatements;
494 markNoParentRef(castEffective(local));
499 int sweepSubstatements() {
500 final Object local = substatements;
501 substatements = SWEPT_SUBSTATEMENTS;
503 if (local instanceof List) {
504 final List<ReactorStmtCtx<?, ?, ?>> list = castEffective(local);
506 count = countUnswept(list);
511 private List<ReactorStmtCtx<?, ?, ?>> initializeSubstatements(
512 final Map<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree) {
513 final Collection<? extends StatementContextBase<?, ?, ?>> declared = prototype.mutableDeclaredSubstatements();
514 final Collection<? extends Mutable<?, ?, ?>> effective = prototype.mutableEffectiveSubstatements();
516 final List<Mutable<?, ?, ?>> buffer = new ArrayList<>(declared.size() + effective.size());
517 for (final Mutable<?, ?, ?> stmtContext : declared) {
518 if (stmtContext.isSupportedByFeatures()) {
519 copySubstatement(stmtContext, buffer, materializedSchemaTree);
522 for (final Mutable<?, ?, ?> stmtContext : effective) {
523 copySubstatement(stmtContext, buffer, materializedSchemaTree);
526 final List<ReactorStmtCtx<?, ?, ?>> ret = beforeAddEffectiveStatementUnsafe(ImmutableList.of(), buffer.size());
527 ret.addAll((Collection) buffer);
536 // Statement copy mess starts here. As it turns out, it's not that much of a mess, but it does make your head spin
537 // sometimes. Tread softly because you tread on my dreams.
540 private EffectiveCopy effectiveCopy(final ReactorStmtCtx<?, ?, ?> stmt) {
541 final ReactorStmtCtx<?, ?, ?> effective = stmt.asEffectiveChildOf(this, childCopyType, targetModule);
542 return effective == null ? null : new EffectiveCopy(stmt, effective);
545 private void copySubstatement(final Mutable<?, ?, ?> substatement, final Collection<Mutable<?, ?, ?>> buffer,
546 final Map<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree) {
547 // Consult materialized substatements. We are in a copy operation and will end up throwing materialized
548 // statements away -- hence we do not perform Map.remove() to save ourselves a mutation operation.
550 // We could also perform a Map.containsKey() and perform a bulk add, but that would mean the statement order
551 // against parent would change -- and we certainly do not want that to happen.
552 final ReactorStmtCtx<?, ?, ?> materialized = findMaterialized(materializedSchemaTree, substatement);
553 if (materialized == null) {
554 copySubstatement(substatement).ifPresent(copy -> {
555 ensureCompletedPhase(copy);
559 buffer.add(materialized);
563 private Optional<? extends Mutable<?, ?, ?>> copySubstatement(final Mutable<?, ?, ?> substatement) {
564 return substatement.copyAsChildOf(this, childCopyType, targetModule);
567 private void addMaterialized(final StmtContext<?, ?, ?> template, final Mutable<?, ?, ?> copy) {
568 final HashMap<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree;
569 if (substatements == null) {
570 // Lazy initialization of backing map. We do not expect this to be used often or multiple times -- each hit
571 // here means an inference along schema tree, such as deviate/augment. HashMap requires power-of-two and
572 // defaults to 0.75 load factor -- we therefore size it to 4, i.e. next two inserts will not cause a
573 // resizing operation.
574 materializedSchemaTree = new HashMap<>(4);
575 substatements = materializedSchemaTree;
578 verify(substatements instanceof HashMap, "Unexpected substatements %s", substatements);
579 materializedSchemaTree = castMaterialized(substatements);
582 final StmtContext<?, ?, ?> existing = materializedSchemaTree.put(template,
583 (StatementContextBase<?, ?, ?>) copy);
584 if (existing != null) {
585 throw new VerifyException(
586 "Unexpected duplicate request for " + copy.argument() + " previous result was " + existing);
590 private static @Nullable ReactorStmtCtx<?, ?, ?> findMaterialized(
591 final Map<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree,
592 final StmtContext<?, ?, ?> template) {
593 return materializedSchemaTree == null ? null : materializedSchemaTree.get(template);
596 @SuppressWarnings("unchecked")
597 private static List<ReactorStmtCtx<?, ?, ?>> castEffective(final Object substatements) {
598 return (List<ReactorStmtCtx<?, ?, ?>>) substatements;
601 @SuppressWarnings("unchecked")
602 private static HashMap<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> castMaterialized(final Object substatements) {
603 return (HashMap<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>>) substatements;
606 // Statement copy mess ends here
609 * KEEP THINGS ORGANIZED!
611 * below methods exist in the same form in SubstatementContext. If any adjustment is made here, make sure it is
612 * properly updated there.
616 public SchemaPath schemaPath() {
617 return substatementGetSchemaPath();
621 public A argument() {
626 public StatementContextBase<?, ?, ?> getParentContext() {
631 public StorageNodeType getStorageNodeType() {
632 return StorageNodeType.STATEMENT_LOCAL;
636 public StatementContextBase<?, ?, ?> getParentNamespaceStorage() {
641 public RootStatementContext<?, ?, ?> getRoot() {
642 return parent.getRoot();
646 public EffectiveConfig effectiveConfig() {
647 return effectiveConfig(parent);
651 protected boolean isIgnoringIfFeatures() {
652 return isIgnoringIfFeatures(parent);
656 protected boolean isIgnoringConfig() {
657 return isIgnoringConfig(parent);
661 protected boolean isParentSupportedByFeatures() {
662 return parent.isSupportedByFeatures();