From dde3e63c454fe72ddb7e7b9689baf2618e6d1e67 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Mon, 26 Oct 2020 15:17:55 +0100 Subject: [PATCH] Add LazyDOMQueryResult Rehost the evaluation logic into a dedicated iterator class. This does not make iteration lazy, but sets the stage by giving the state being passed around a place to live. JIRA: MDSAL-610 Change-Id: Ic23eb38d7e5a6bd1cf1b7637dec88eff552520d7 Signed-off-by: Robert Varga --- .../dom/spi/query/DOMQueryEvaluator.java | 75 +---------- .../dom/spi/query/LazyDOMQueryResult.java | 34 +++++ .../spi/query/LazyDOMQueryResultIterator.java | 116 ++++++++++++++++++ 3 files changed, 153 insertions(+), 72 deletions(-) create mode 100644 dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResult.java create mode 100644 dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResultIterator.java diff --git a/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/DOMQueryEvaluator.java b/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/DOMQueryEvaluator.java index 7cb1b95a87..a28737f128 100644 --- a/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/DOMQueryEvaluator.java +++ b/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/DOMQueryEvaluator.java @@ -7,24 +7,13 @@ */ package org.opendaylight.mdsal.dom.spi.query; -import static com.google.common.base.Preconditions.checkArgument; - import java.util.AbstractMap.SimpleImmutableEntry; -import java.util.ArrayDeque; -import java.util.ArrayList; -import java.util.Deque; -import java.util.List; -import java.util.Map.Entry; import java.util.Optional; import org.eclipse.jdt.annotation.NonNullByDefault; import org.opendaylight.mdsal.dom.api.query.DOMQuery; -import org.opendaylight.mdsal.dom.api.query.DOMQueryPredicate; import org.opendaylight.mdsal.dom.api.query.DOMQueryResult; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; -import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument; -import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode; -import org.opendaylight.yangtools.yang.data.api.schema.MapNode; import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes; @@ -45,7 +34,7 @@ public final class DOMQueryEvaluator { */ public static DOMQueryResult evaluateOn(final DOMQuery query, final NormalizedNode queryRoot) { final YangInstanceIdentifier path = query.getSelect(); - return path.isEmpty() ? evalSingle(queryRoot, query) : evalPath(queryRoot, query); + return path.isEmpty() ? evalSingle(query, queryRoot) : new LazyDOMQueryResult(query, queryRoot); } /** @@ -70,66 +59,8 @@ public final class DOMQueryEvaluator { return evaluateOn(query, evalRoot); } - private static DOMQueryResult evalSingle(final NormalizedNode data, final DOMQuery query) { - return matches(data, query) ? DOMQueryResult.of() + private static DOMQueryResult evalSingle(final DOMQuery query, final NormalizedNode data) { + return LazyDOMQueryResultIterator.matches(data, query) ? DOMQueryResult.of() : DOMQueryResult.of(new SimpleImmutableEntry<>(query.getRoot(), data)); } - - private static DOMQueryResult evalPath(final NormalizedNode queryRoot, final DOMQuery query) { - // FIXME: this is eager evaluation, we should be doing lazy traversal - final List>> result = new ArrayList<>(); - evalPath(result, new ArrayDeque<>(query.getRoot().getPathArguments()), - new ArrayDeque<>(query.getSelect().getPathArguments()), queryRoot, query); - return DOMQueryResult.of(result); - } - - private static void evalPath(final List>> result, - final Deque path, final ArrayDeque remaining, - final NormalizedNode data, final DOMQuery query) { - final PathArgument next = remaining.poll(); - if (next == null) { - if (matches(data, query)) { - result.add(new SimpleImmutableEntry<>(YangInstanceIdentifier.create(path), data)); - } - return; - } - - if (data instanceof MapNode && next instanceof NodeIdentifier) { - checkArgument(data.getIdentifier().equals(next), "Unexpected step %s", next); - for (MapEntryNode child : ((MapNode) data).getValue()) { - evalChild(result, path, remaining, query, child); - } - } else { - NormalizedNodes.getDirectChild(data, next).ifPresent( - child -> evalChild(result, path, remaining, query, child)); - } - remaining.push(next); - } - - private static void evalChild(final List>> result, - final Deque path, final ArrayDeque remaining, final DOMQuery query, - final NormalizedNode child) { - path.addLast(child.getIdentifier()); - evalPath(result, path, remaining, child, query); - path.removeLast(); - } - - private static boolean matches(final NormalizedNode data, final DOMQuery query) { - for (DOMQueryPredicate pred : query.getPredicates()) { - // Okay, now we need to deal with predicates, but do it in a smart fashion, so we do not end up iterating - // all over the place. Typically we will be matching just a leaf. - final YangInstanceIdentifier path = pred.getPath(); - final Optional> node; - if (path.coerceParent().isEmpty()) { - node = NormalizedNodes.getDirectChild(data, path.getLastPathArgument()); - } else { - node = NormalizedNodes.findNode(data, path); - } - - if (!pred.test(node.orElse(null))) { - return false; - } - } - return true; - } } diff --git a/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResult.java b/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResult.java new file mode 100644 index 0000000000..91894ec9a9 --- /dev/null +++ b/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResult.java @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.mdsal.dom.spi.query; + +import static java.util.Objects.requireNonNull; + +import java.util.Iterator; +import java.util.Map.Entry; +import org.eclipse.jdt.annotation.NonNullByDefault; +import org.opendaylight.mdsal.dom.api.query.DOMQuery; +import org.opendaylight.mdsal.dom.api.query.DOMQueryResult; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; +import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; + +@NonNullByDefault +final class LazyDOMQueryResult implements DOMQueryResult { + private final NormalizedNode queryRoot; + private final DOMQuery query; + + LazyDOMQueryResult(final DOMQuery query, final NormalizedNode queryRoot) { + this.query = requireNonNull(query); + this.queryRoot = requireNonNull(queryRoot); + } + + @Override + public Iterator>> iterator() { + return new LazyDOMQueryResultIterator(query, queryRoot); + } +} diff --git a/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResultIterator.java b/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResultIterator.java new file mode 100644 index 0000000000..4c2e02fa5d --- /dev/null +++ b/dom/mdsal-dom-spi/src/main/java/org/opendaylight/mdsal/dom/spi/query/LazyDOMQueryResultIterator.java @@ -0,0 +1,116 @@ +/* + * Copyright (c) 2020 PANTHEON.tech, s.r.o. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.mdsal.dom.spi.query; + +import static com.google.common.base.Preconditions.checkArgument; +import static java.util.Objects.requireNonNull; + +import java.util.AbstractMap.SimpleImmutableEntry; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.Map.Entry; +import java.util.Optional; +import org.eclipse.jdt.annotation.NonNullByDefault; +import org.opendaylight.mdsal.dom.api.query.DOMQuery; +import org.opendaylight.mdsal.dom.api.query.DOMQueryPredicate; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument; +import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode; +import org.opendaylight.yangtools.yang.data.api.schema.MapNode; +import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; +import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes; + +@NonNullByDefault +final class LazyDOMQueryResultIterator implements Iterator>> { + // Current data item + private final ArrayDeque> currentData = new ArrayDeque<>(); + // Absolute path from root of current data item + private final ArrayDeque currentPath; + // Steps remaining in the select part of the query + private final ArrayDeque selectSteps; + // The query which needs to be executed + private final DOMQuery query; + + // FIXME: MDSAL-610: this needs to be eliminated + private final Iterator>> iter; + + LazyDOMQueryResultIterator(final DOMQuery query, final NormalizedNode queryRoot) { + this.query = requireNonNull(query); + currentPath = new ArrayDeque<>(query.getRoot().getPathArguments()); + selectSteps = new ArrayDeque<>(query.getSelect().getPathArguments()); + currentData.push(queryRoot); + + // FIXME: MDSAL-610: this is a recursive algo, filling provided list. Turn it around into a state mutator. + final List>> result = new ArrayList<>(); + evalPath(result); + this.iter = result.iterator(); + currentPath.clear(); + selectSteps.clear(); + } + + @Override + public boolean hasNext() { + return iter.hasNext(); + } + + @Override + public Entry> next() { + return iter.next(); + } + + private void evalPath(final List>> result) { + final NormalizedNode data = currentData.pop(); + final PathArgument next = selectSteps.poll(); + if (next == null) { + if (matches(data, query)) { + result.add(new SimpleImmutableEntry<>(YangInstanceIdentifier.create(currentPath), data)); + } + return; + } + + if (data instanceof MapNode && next instanceof NodeIdentifier) { + checkArgument(data.getIdentifier().equals(next), "Unexpected step %s", next); + for (MapEntryNode child : ((MapNode) data).getValue()) { + evalChild(result, child); + } + } else { + NormalizedNodes.getDirectChild(data, next).ifPresent(child -> evalChild(result, child)); + } + selectSteps.push(next); + } + + private void evalChild(final List>> result, + final NormalizedNode child) { + currentPath.addLast(child.getIdentifier()); + currentData.push(child); + evalPath(result); + currentPath.removeLast(); + } + + static boolean matches(final NormalizedNode data, final DOMQuery query) { + for (DOMQueryPredicate pred : query.getPredicates()) { + // Okay, now we need to deal with predicates, but do it in a smart fashion, so we do not end up iterating + // all over the place. Typically we will be matching just a leaf. + final YangInstanceIdentifier path = pred.getPath(); + final Optional> node; + if (path.coerceParent().isEmpty()) { + node = NormalizedNodes.getDirectChild(data, path.getLastPathArgument()); + } else { + node = NormalizedNodes.findNode(data, path); + } + + if (!pred.test(node.orElse(null))) { + return false; + } + } + return true; + } +} -- 2.36.6