Do not force materialization when not needed
[yangtools.git] / yang / yang-parser-reactor / src / main / java / org / opendaylight / yangtools / yang / parser / stmt / reactor / InferredStatementContext.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.parser.stmt.reactor;
9
10 import static com.google.common.base.Verify.verify;
11 import static java.util.Objects.requireNonNull;
12
13 import com.google.common.base.VerifyException;
14 import com.google.common.collect.ImmutableList;
15 import com.google.common.collect.ImmutableSet;
16 import com.google.common.collect.Streams;
17 import java.util.ArrayList;
18 import java.util.Collection;
19 import java.util.HashMap;
20 import java.util.List;
21 import java.util.Map;
22 import java.util.Map.Entry;
23 import java.util.Objects;
24 import java.util.Optional;
25 import java.util.stream.Collectors;
26 import java.util.stream.Stream;
27 import org.eclipse.jdt.annotation.NonNull;
28 import org.eclipse.jdt.annotation.Nullable;
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.YangStmtMapping;
33 import org.opendaylight.yangtools.yang.model.api.meta.DeclaredStatement;
34 import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement;
35 import org.opendaylight.yangtools.yang.model.api.meta.StatementDefinition;
36 import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeEffectiveStatement;
37 import org.opendaylight.yangtools.yang.parser.spi.SchemaTreeNamespace;
38 import org.opendaylight.yangtools.yang.parser.spi.meta.CopyHistory;
39 import org.opendaylight.yangtools.yang.parser.spi.meta.CopyType;
40 import org.opendaylight.yangtools.yang.parser.spi.meta.InferenceException;
41 import org.opendaylight.yangtools.yang.parser.spi.meta.NamespaceBehaviour.OnDemandSchemaTreeStorageNode;
42 import org.opendaylight.yangtools.yang.parser.spi.meta.NamespaceBehaviour.StorageNodeType;
43 import org.opendaylight.yangtools.yang.parser.spi.meta.StatementFactory;
44 import org.opendaylight.yangtools.yang.parser.spi.meta.StmtContext;
45 import org.opendaylight.yangtools.yang.parser.spi.meta.StmtContextUtils;
46 import org.opendaylight.yangtools.yang.parser.spi.source.StatementSourceReference;
47 import org.slf4j.Logger;
48 import org.slf4j.LoggerFactory;
49
50 /**
51  * A statement which has been inferred to exist. Functionally it is equivalent to a SubstatementContext, but it is not
52  * backed by a declaration (and declared statements). It is backed by a prototype StatementContextBase and has only
53  * effective substatements, which are either transformed from that prototype or added by inference.
54  */
55 final class InferredStatementContext<A, D extends DeclaredStatement<A>, E extends EffectiveStatement<A, D>>
56         extends StatementContextBase<A, D, E> implements OnDemandSchemaTreeStorageNode {
57     private static final Logger LOG = LoggerFactory.getLogger(InferredStatementContext.class);
58
59     // Sentinel object for 'substatements'
60     private static final Object SWEPT_SUBSTATEMENTS = new Object();
61
62     private final @NonNull StatementContextBase<A, D, E> prototype;
63     private final @NonNull StatementContextBase<?, ?, ?> parent;
64     private final @NonNull StmtContext<A, D, E> originalCtx;
65     private final @NonNull CopyType childCopyType;
66     private final QNameModule targetModule;
67     private final A argument;
68
69     /**
70      * Effective substatements, lazily materialized. This field can have four states:
71      * <ul>
72      *   <li>it can be {@code null}, in which case no materialization has taken place</li>
73      *   <li>it can be a {@link HashMap}, in which case partial materialization has taken place</li>
74      *   <li>it can be a {@link List}, in which case full materialization has taken place</li>
75      *   <li>it can be {@link SWEPT_SUBSTATEMENTS}, in which case materialized state is no longer available</li>
76      * </ul>
77      */
78     private Object substatements;
79
80     private InferredStatementContext(final InferredStatementContext<A, D, E> original,
81             final StatementContextBase<?, ?, ?> parent) {
82         super(original);
83         this.parent = requireNonNull(parent);
84         this.childCopyType = original.childCopyType;
85         this.targetModule = original.targetModule;
86         this.prototype = original.prototype;
87         this.originalCtx = original.originalCtx;
88         this.argument = original.argument;
89         // Substatements are initialized here
90         this.substatements = ImmutableList.of();
91     }
92
93     InferredStatementContext(final StatementContextBase<?, ?, ?> parent, final StatementContextBase<A, D, E> prototype,
94             final CopyType myCopyType, final CopyType childCopyType, final QNameModule targetModule) {
95         super(prototype.definition(), CopyHistory.of(myCopyType, prototype.history()));
96         this.parent = requireNonNull(parent);
97         this.prototype = requireNonNull(prototype);
98         this.argument = targetModule == null ? prototype.argument()
99                 : prototype.definition().adaptArgumentValue(prototype, targetModule);
100         this.childCopyType = requireNonNull(childCopyType);
101         this.targetModule = targetModule;
102         this.originalCtx = prototype.getOriginalCtx().orElse(prototype);
103
104         // Mark prototype as blocking statement cleanup
105         prototype.incRef();
106     }
107
108     @Override
109     public Collection<? extends StatementContextBase<?, ?, ?>> mutableDeclaredSubstatements() {
110         return ImmutableList.of();
111     }
112
113     @Override
114     public Collection<? extends Mutable<?, ?, ?>> mutableEffectiveSubstatements() {
115         return mutableEffectiveSubstatements(ensureEffectiveSubstatements());
116     }
117
118     @Override
119     public Iterable<? extends StmtContext<?, ?, ?>> allSubstatements() {
120         // No need to concat with declared
121         return effectiveSubstatements();
122     }
123
124     @Override
125     public Stream<? extends StmtContext<?, ?, ?>> allSubstatementsStream() {
126         // No need to concat with declared
127         return effectiveSubstatements().stream();
128     }
129
130     @Override
131     public StatementSourceReference sourceReference() {
132         return originalCtx.sourceReference();
133     }
134
135     @Override
136     public String rawArgument() {
137         return originalCtx.rawArgument();
138     }
139
140     @Override
141     public Optional<StmtContext<A, D, E>> getOriginalCtx() {
142         return Optional.of(originalCtx);
143     }
144
145     @Override
146     public Optional<StmtContext<A, D, E>> getPreviousCopyCtx() {
147         return Optional.of(prototype);
148     }
149
150     @Override
151     public D declared() {
152         /*
153          * Share original instance of declared statement between all effective statements which have been copied or
154          * derived from this original declared statement.
155          */
156         return originalCtx.declared();
157     }
158
159     @Override
160     public void removeStatementFromEffectiveSubstatements(final StatementDefinition statementDef) {
161         substatements = removeStatementFromEffectiveSubstatements(ensureEffectiveSubstatements(), statementDef);
162     }
163
164     @Override
165     public void removeStatementFromEffectiveSubstatements(final StatementDefinition statementDef,
166             final String statementArg) {
167         substatements = removeStatementFromEffectiveSubstatements(ensureEffectiveSubstatements(), statementDef,
168             statementArg);
169     }
170
171     @Override
172     public void addEffectiveSubstatement(final Mutable<?, ?, ?> substatement) {
173         substatements = addEffectiveSubstatement(ensureEffectiveSubstatements(), substatement);
174     }
175
176     @Override
177     void addEffectiveSubstatementsImpl(final Collection<? extends Mutable<?, ?, ?>> statements) {
178         substatements = addEffectiveSubstatementsImpl(ensureEffectiveSubstatements(), statements);
179     }
180
181     @Override
182     InferredStatementContext<A, D, E> reparent(final StatementContextBase<?, ?, ?> newParent) {
183         return new InferredStatementContext<>(this, newParent);
184     }
185
186     @Override
187     E createEffective(final StatementFactory<A, D, E> factory) {
188         // If we have not materialized we do not have a difference in effective substatements, hence we can forward
189         // towards the source of the statement.
190         return substatements == null ? tryToReusePrototype(factory) : super.createEffective(factory);
191     }
192
193     private @NonNull E tryToReusePrototype(final StatementFactory<A, D, E> factory) {
194         final E origEffective = prototype.buildEffective();
195         final Collection<? extends @NonNull EffectiveStatement<?, ?>> origSubstatements =
196             origEffective.effectiveSubstatements();
197
198         // First check if we can reuse the entire prototype
199         if (!factory.canReuseCurrent(this, prototype, origSubstatements)) {
200             // FIXME: YANGTOOLS-1067: an incremental improvement here is that we reuse statements that are not affected
201             //                        by us changing parent. For example: if our SchemaPath changed, but the namespace
202             //                        remained the same, 'key' statement should get reused.
203             // Fall back to full instantiation
204             return super.createEffective(factory);
205         }
206
207         // No substatements to deal with, we can freely reuse the original
208         if (origSubstatements.isEmpty()) {
209             LOG.debug("Reusing empty: {}", origEffective);
210             substatements = ImmutableList.of();
211             prototype.decRef();
212             return origEffective;
213         }
214
215         // We can reuse this statement let's see if all the statements agree
216         final List<Entry<Mutable<?, ?, ?>, Mutable<?, ?, ?>>> declared = prototype.streamDeclared()
217             .filter(StmtContext::isSupportedByFeatures)
218             .map(sub -> effectiveCopy((ReactorStmtCtx<?, ?, ?>) sub))
219             .filter(Objects::nonNull)
220             .collect(Collectors.toUnmodifiableList());
221         final List<Entry<Mutable<?, ?, ?>, Mutable<?, ?, ?>>> effective = prototype.streamEffective()
222             .map(sub -> effectiveCopy((ReactorStmtCtx<?, ?, ?>) sub))
223             .filter(Objects::nonNull)
224             .collect(Collectors.toUnmodifiableList());
225
226         // We no longer need the prototype's substatements, but we may need to retain ours
227         prototype.decRef();
228         if (haveRef()) {
229             substatements = Streams.concat(declared.stream(), effective.stream())
230                 .map(Entry::getValue)
231                 .collect(ImmutableList.toImmutableList());
232         } else {
233             // This should immediately get swept anyway. Should we use a poison object?
234             substatements = List.of();
235         }
236
237         if (allReused(declared) && allReused(effective)) {
238             LOG.debug("Reusing after substatement check: {}", origEffective);
239             return origEffective;
240         }
241
242         // Values are the effective copies, hence this efficienly deals with recursion.
243         return factory.createEffective(this, declared.stream().map(Entry::getValue),
244             effective.stream().map(Entry::getValue));
245     }
246
247     private static boolean allReused(final List<Entry<Mutable<?, ?, ?>, Mutable<?, ?, ?>>> entries) {
248         for (Entry<Mutable<?, ?, ?>, Mutable<?, ?, ?>> entry : entries) {
249             if (entry.getKey() != entry.getValue()) {
250                 return false;
251             }
252         }
253         return true;
254     }
255
256     @Override
257     boolean hasEmptySubstatements() {
258         if (substatements == null) {
259             return prototype.hasEmptySubstatements();
260         }
261         return substatements instanceof HashMap ? false : ((List<?>) substatements).isEmpty();
262     }
263
264     @Override
265     public <X, Z extends EffectiveStatement<X, ?>> @NonNull Optional<X> findSubstatementArgument(
266             final @NonNull Class<Z> type) {
267         if (substatements instanceof List) {
268             return super.findSubstatementArgument(type);
269         }
270
271         final Optional<X> templateArg = prototype.findSubstatementArgument(type);
272         if (templateArg.isEmpty()) {
273             return templateArg;
274         }
275         if (SchemaTreeEffectiveStatement.class.isAssignableFrom(type)) {
276             // X is known to be QName
277             return (Optional<X>) templateArg.map(template -> ((QName) template).bindTo(targetModule));
278         }
279         return templateArg;
280     }
281
282     @Override
283     public boolean hasSubstatement(final @NonNull Class<? extends EffectiveStatement<?, ?>> type) {
284         return substatements instanceof List ? super.hasSubstatement(type)
285             // We do not allow deletion of partially-materialized statements, hence this is accurate
286             : prototype.hasSubstatement(type);
287     }
288
289     @Override
290     public <Y extends DeclaredStatement<QName>, Z extends SchemaTreeEffectiveStatement<Y>>
291             StmtContext<QName, Y, Z> requestSchemaTreeChild(final QName qname) {
292         if (substatements instanceof List) {
293             // We have performed materialization, hence we have triggered creation of all our schema tree child
294             // statements.
295             return null;
296         }
297
298         final QName templateQName = qname.bindTo(StmtContextUtils.getRootModuleQName(prototype));
299         LOG.debug("Materializing child {} from {}", qname, templateQName);
300
301         final StmtContext<?, ?, ?> template;
302         if (prototype instanceof InferredStatementContext) {
303             // Note: we need to access namespace here, as the target statement may have already been populated, in which
304             //       case we want to obtain the statement in local namespace storage.
305             template = (StmtContext) ((InferredStatementContext<?, ?, ?>) prototype).getFromNamespace(
306                 SchemaTreeNamespace.class, templateQName);
307         } else {
308             template = prototype.allSubstatementsStream()
309                 .filter(stmt -> stmt.producesEffective(SchemaTreeEffectiveStatement.class)
310                     && templateQName.equals(stmt.argument()))
311                 .findAny()
312                 .orElse(null);
313         }
314
315         if (template == null) {
316             // We do not have a template, this child does not exist. It may be added later, but that is someone else's
317             // responsibility.
318             LOG.debug("Child {} does not have a template", qname);
319             return null;
320         }
321
322         @SuppressWarnings("unchecked")
323         final Mutable<QName, Y, Z> ret = (Mutable<QName, Y, Z>) copySubstatement((Mutable<?, ?, ?>) template)
324             .orElseThrow(
325                 () -> new InferenceException(this, "Failed to materialize child %s template %s", qname, template));
326         ensureCompletedPhase(ret);
327         addMaterialized(template, ret);
328
329         LOG.debug("Child {} materialized", qname);
330         return ret;
331     }
332
333     // Instantiate this statement's effective substatements. Note this method has side-effects in namespaces and overall
334     // BuildGlobalContext, hence it must be called at most once.
335     private List<ReactorStmtCtx<?, ?, ?>> ensureEffectiveSubstatements() {
336         accessSubstatements();
337         return substatements instanceof List ? castEffective(substatements)
338             : initializeSubstatements(castMaterialized(substatements));
339     }
340
341     @Override
342     Iterable<ReactorStmtCtx<?, ?, ?>> effectiveChildrenToComplete() {
343         // When we have not initialized, there are no statements to catch up: we will catch up when we are copying
344         // from prototype (which is already at ModelProcessingPhase.EFFECTIVE_MODEL).
345         if (substatements == null) {
346             return ImmutableList.of();
347         }
348         accessSubstatements();
349         if (substatements instanceof HashMap) {
350             return castMaterialized(substatements).values();
351         } else {
352             return castEffective(substatements);
353         }
354     }
355
356     @Override
357     Stream<? extends StmtContext<?, ?, ?>> streamDeclared() {
358         return Stream.empty();
359     }
360
361     @Override
362     Stream<? extends StmtContext<?, ?, ?>> streamEffective() {
363         accessSubstatements();
364         return ensureEffectiveSubstatements().stream();
365     }
366
367     private void accessSubstatements() {
368         verify(substatements != SWEPT_SUBSTATEMENTS, "Attempted to access substatements of %s", this);
369     }
370
371     @Override
372     void markNoParentRef() {
373         final Object local = substatements;
374         if (local != null) {
375             markNoParentRef(castEffective(local));
376         }
377     }
378
379     @Override
380     int sweepSubstatements() {
381         final Object local = substatements;
382         substatements = SWEPT_SUBSTATEMENTS;
383         int count = 0;
384         if (local != null) {
385             final List<ReactorStmtCtx<?, ?, ?>> list = castEffective(local);
386             sweep(list);
387             count = countUnswept(list);
388         }
389         return count;
390     }
391
392     private List<ReactorStmtCtx<?, ?, ?>> initializeSubstatements(
393             final Map<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree) {
394         final Collection<? extends StatementContextBase<?, ?, ?>> declared = prototype.mutableDeclaredSubstatements();
395         final Collection<? extends Mutable<?, ?, ?>> effective = prototype.mutableEffectiveSubstatements();
396
397         final List<Mutable<?, ?, ?>> buffer = new ArrayList<>(declared.size() + effective.size());
398         for (final Mutable<?, ?, ?> stmtContext : declared) {
399             if (stmtContext.isSupportedByFeatures()) {
400                 copySubstatement(stmtContext, buffer, materializedSchemaTree);
401             }
402         }
403         for (final Mutable<?, ?, ?> stmtContext : effective) {
404             copySubstatement(stmtContext, buffer, materializedSchemaTree);
405         }
406
407         final List<ReactorStmtCtx<?, ?, ?>> ret = beforeAddEffectiveStatementUnsafe(ImmutableList.of(), buffer.size());
408         ret.addAll((Collection) buffer);
409         substatements = ret;
410
411         prototype.decRef();
412         return ret;
413     }
414
415     // Statement copy mess starts here
416     //
417     // FIXME: This is messy and is probably wrong in some corner case. Even if it is correct, the way how it is correct
418     //        relies on hard-coded maps. At the end of the day, the logic needs to be controlled by statement's
419     //        StatementSupport.
420     // FIXME: YANGTOOLS-652: this map looks very much like UsesStatementSupport.TOP_REUSED_DEF_SET
421     private static final ImmutableSet<YangStmtMapping> REUSED_DEF_SET = ImmutableSet.of(
422         YangStmtMapping.TYPE,
423         YangStmtMapping.TYPEDEF,
424         YangStmtMapping.USES);
425
426     private Map.Entry<Mutable<?, ?, ?>, Mutable<?, ?, ?>> effectiveCopy(final ReactorStmtCtx<?, ?, ?> stmt) {
427         // FIXME: YANGTOOLS-652: formerly known as "isReusedByUses"
428         if (REUSED_DEF_SET.contains(stmt.definition().getPublicView())) {
429             return Map.entry(stmt, stmt.replicaAsChildOf(this));
430         }
431
432         final ReactorStmtCtx<?, ?, ?> effective = stmt.asEffectiveChildOf(this, childCopyType, targetModule);
433         return effective == null ? null : Map.entry(stmt, effective);
434     }
435
436     private void copySubstatement(final Mutable<?, ?, ?> substatement, final Collection<Mutable<?, ?, ?>> buffer,
437             final Map<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree) {
438         final StatementDefinition def = substatement.publicDefinition();
439
440         // FIXME: YANGTOOLS-652: formerly known as "isReusedByUses"
441         if (REUSED_DEF_SET.contains(def)) {
442             LOG.trace("Reusing substatement {} for {}", substatement, this);
443             buffer.add(substatement.replicaAsChildOf(this));
444             return;
445         }
446
447         // Consult materialized substatements. We are in a copy operation and will end up throwing materialized
448         // statements away -- hence we do not perform Map.remove() to save ourselves a mutation operation.
449         //
450         // We could also perform a Map.containsKey() and perform a bulk add, but that would mean the statement order
451         // against parent would change -- and we certainly do not want that to happen.
452         final ReactorStmtCtx<?, ?, ?> materialized = findMaterialized(materializedSchemaTree, substatement);
453         if (materialized == null) {
454             copySubstatement(substatement).ifPresent(copy -> {
455                 ensureCompletedPhase(copy);
456                 buffer.add(copy);
457             });
458         } else {
459             buffer.add(materialized);
460         }
461     }
462
463     private Optional<? extends Mutable<?, ?, ?>> copySubstatement(final Mutable<?, ?, ?> substatement) {
464         // FIXME: YANGTOOLS-1195: this is not exactly what we want to do here, because we are dealing with two different
465         //                        requests: copy for inference purposes (this method), while we also copy for purposes
466         //                        of buildEffective() -- in which case we want to probably invoke asEffectiveChildOf()
467         //                        or similar
468         return substatement.copyAsChildOf(this, childCopyType, targetModule);
469     }
470
471     private void addMaterialized(final StmtContext<?, ?, ?> template, final Mutable<?, ?, ?> copy) {
472         final HashMap<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree;
473         if (substatements == null) {
474             // Lazy initialization of backing map. We do not expect this to be used often or multiple times -- each hit
475             // here means an inference along schema tree, such as deviate/augment. HashMap requires power-of-two and
476             // defaults to 0.75 load factor -- we therefore size it to 4, i.e. next two inserts will not cause a
477             // resizing operation.
478             materializedSchemaTree = new HashMap<>(4);
479             substatements = materializedSchemaTree;
480         } else {
481             verify(substatements instanceof HashMap, "Unexpected substatements %s", substatements);
482             materializedSchemaTree = castMaterialized(substatements);
483         }
484
485         final StmtContext<?, ?, ?> existing = materializedSchemaTree.put(template,
486             (StatementContextBase<?, ?, ?>) copy);
487         if (existing != null) {
488             throw new VerifyException(
489                 "Unexpected duplicate request for " + copy.argument() + " previous result was " + existing);
490         }
491     }
492
493     private static @Nullable ReactorStmtCtx<?, ?, ?> findMaterialized(
494             final Map<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> materializedSchemaTree,
495             final StmtContext<?, ?, ?> template) {
496         return materializedSchemaTree == null ? null : materializedSchemaTree.get(template);
497     }
498
499     @SuppressWarnings("unchecked")
500     private static List<ReactorStmtCtx<?, ?, ?>> castEffective(final Object substatements) {
501         return (List<ReactorStmtCtx<?, ?, ?>>) substatements;
502     }
503
504     @SuppressWarnings("unchecked")
505     private static HashMap<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>> castMaterialized(final Object substatements) {
506         return (HashMap<StmtContext<?, ?, ?>, ReactorStmtCtx<?, ?, ?>>) substatements;
507     }
508
509     // Statement copy mess ends here
510
511     /*
512      * KEEP THINGS ORGANIZED!
513      *
514      * below methods exist in the same form in SubstatementContext. If any adjustment is made here, make sure it is
515      * properly updated there.
516      */
517     @Override
518     @Deprecated
519     public Optional<SchemaPath> schemaPath() {
520         return substatementGetSchemaPath();
521     }
522
523     @Override
524     public A argument() {
525         return argument;
526     }
527
528     @Override
529     public StatementContextBase<?, ?, ?> getParentContext() {
530         return parent;
531     }
532
533     @Override
534     public StorageNodeType getStorageNodeType() {
535         return StorageNodeType.STATEMENT_LOCAL;
536     }
537
538     @Override
539     public StatementContextBase<?, ?, ?> getParentNamespaceStorage() {
540         return parent;
541     }
542
543     @Override
544     public RootStatementContext<?, ?, ?> getRoot() {
545         return parent.getRoot();
546     }
547
548     @Override
549     public EffectiveConfig effectiveConfig() {
550         return effectiveConfig(parent);
551     }
552
553     @Override
554     protected boolean isIgnoringIfFeatures() {
555         return isIgnoringIfFeatures(parent);
556     }
557
558     @Override
559     protected boolean isIgnoringConfig() {
560         return isIgnoringConfig(parent);
561     }
562
563     @Override
564     protected boolean isParentSupportedByFeatures() {
565         return parent.isSupportedByFeatures();
566     }
567 }