From 52e49d63e73b995ea10bbeefb62df9c6101b44c3 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Wed, 18 Nov 2020 15:41:30 +0100 Subject: [PATCH] Add UniqueValidation This is a simplement implementation with a stateless external enforcer, similar to what MinMaxElementsValidation does. The test suite is split out of If3b94a085be034de28e341ac900142b021cd2a88 and adapted a bit. JIRA: YANGTOOLS-1177 Change-Id: I3914497981db0281ab8f32dee12a102ce729022e Signed-off-by: Peter Kajsa Signed-off-by: Robert Varga --- .../src/main/java/module-info.java | 1 + .../tree/UniqueConstraintException.java | 44 +++ .../src/main/java/module-info.java | 3 + ...ractNodeContainerModificationStrategy.java | 48 ++-- .../data/impl/schema/tree/BinaryValue.java | 49 ++++ .../schema/tree/ListModificationStrategy.java | 18 +- .../tree/ModificationApplyOperation.java | 31 +- .../tree/SchemaAwareApplyOperation.java | 2 +- .../impl/schema/tree/UniqueValidation.java | 144 ++++++++++ .../impl/schema/tree/UniqueValidator.java | 188 ++++++++++++ .../data/impl/schema/tree/UniqueValues.java | 94 ++++++ .../schema/tree/UniqueConstraintTest.java | 268 ++++++++++++++++++ .../src/test/resources/yt570.yang | 82 ++++++ 13 files changed, 922 insertions(+), 50 deletions(-) create mode 100644 yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/UniqueConstraintException.java create mode 100644 yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/BinaryValue.java create mode 100644 yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidation.java create mode 100644 yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidator.java create mode 100644 yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValues.java create mode 100644 yang/yang-data-impl/src/test/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueConstraintTest.java create mode 100644 yang/yang-data-impl/src/test/resources/yt570.yang diff --git a/yang/yang-data-api/src/main/java/module-info.java b/yang/yang-data-api/src/main/java/module-info.java index cbe3cafd57..c13d04f6af 100644 --- a/yang/yang-data-api/src/main/java/module-info.java +++ b/yang/yang-data-api/src/main/java/module-info.java @@ -21,4 +21,5 @@ module org.opendaylight.yangtools.yang.data.api { // Annotations requires static transitive org.eclipse.jdt.annotation; + requires static com.github.spotbugs.annotations; } diff --git a/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/UniqueConstraintException.java b/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/UniqueConstraintException.java new file mode 100644 index 0000000000..48cbe7c058 --- /dev/null +++ b/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/UniqueConstraintException.java @@ -0,0 +1,44 @@ +/* + * 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.yangtools.yang.data.api.schema.tree; + +import static java.util.Objects.requireNonNull; + +import com.google.common.annotations.Beta; +import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; +import java.util.Collections; +import java.util.Map; +import org.eclipse.jdt.annotation.NonNullByDefault; +import org.eclipse.jdt.annotation.Nullable; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; +import org.opendaylight.yangtools.yang.model.api.stmt.SchemaNodeIdentifier.Descendant; + +/** + * Exception thrown when a {@code unique} statement restrictions are violated. + * + * @author Robert Varga + */ +@Beta +@NonNullByDefault +public class UniqueConstraintException extends DataValidationFailedException { + private static final long serialVersionUID = 1L; + + // Note: this cannot be an ImmutableMap because we must support null values + @SuppressFBWarnings(value = "SE_BAD_FIELD", justification = "Best effort on serialization") + private final Map values; + + public UniqueConstraintException(final YangInstanceIdentifier path, final Map values, + final String message) { + super(path, message); + this.values = requireNonNull(values); + } + + public final Map values() { + return Collections.unmodifiableMap(values); + } +} diff --git a/yang/yang-data-impl/src/main/java/module-info.java b/yang/yang-data-impl/src/main/java/module-info.java index 7901619c0a..6935fffe47 100644 --- a/yang/yang-data-impl/src/main/java/module-info.java +++ b/yang/yang-data-impl/src/main/java/module-info.java @@ -26,11 +26,14 @@ module org.opendaylight.yangtools.yang.data.impl { requires org.opendaylight.yangtools.util; requires org.opendaylight.yangtools.rfc7952.data.util; requires org.opendaylight.yangtools.rfc8528.data.util; + requires org.opendaylight.yangtools.yang.common; + requires org.opendaylight.yangtools.yang.model.api; requires org.opendaylight.yangtools.yang.model.util; requires org.slf4j; // Annotations requires static transitive org.eclipse.jdt.annotation; + requires static com.github.spotbugs.annotations; requires static org.osgi.service.component.annotations; requires static javax.inject; requires static metainf.services; diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractNodeContainerModificationStrategy.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractNodeContainerModificationStrategy.java index 342745b735..50ef3b0b7e 100644 --- a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractNodeContainerModificationStrategy.java +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/AbstractNodeContainerModificationStrategy.java @@ -172,20 +172,18 @@ abstract class AbstractNodeContainerModificationStrategy } /* - * This is where things get interesting. The user has performed a write and - * then she applied some more modifications to it. So we need to make sense - * of that an apply the operations on top of the written value. We could have - * done it during the write, but this operation is potentially expensive, so - * we have left it out of the fast path. + * This is where things get interesting. The user has performed a write and then she applied some more + * modifications to it. So we need to make sense of that and apply the operations on top of the written value. * - * As it turns out, once we materialize the written data, we can share the - * code path with the subtree change. So let's create an unsealed TreeNode - * and run the common parts on it -- which end with the node being sealed. + * We could have done it during the write, but this operation is potentially expensive, so we have left it out + * of the fast path. * - * FIXME: this code needs to be moved out from the prepare() path and into - * the read() and seal() paths. Merging of writes needs to be charged - * to the code which originated this, not to the code which is - * attempting to make it visible. + * As it turns out, once we materialize the written data, we can share the code path with the subtree change. So + * let's create an unsealed TreeNode and run the common parts on it -- which end with the node being sealed. + * + * FIXME: this code needs to be moved out from the prepare() path and into the read() and seal() paths. Merging + * of writes needs to be charged to the code which originated this, not to the code which is attempting + * to make it visible. */ final MutableTreeNode mutable = newValueMeta.mutable(); mutable.setSubtreeVersion(version); @@ -274,12 +272,10 @@ abstract class AbstractNodeContainerModificationStrategy case TOUCH: mergeChildrenIntoModification(modification, children, version); - // We record empty merge value, since real children merges - // are already expanded. This is needed to satisfy non-null for merge - // original merge value can not be used since it mean different - // order of operation - parent changes are always resolved before - // children ones, and having node in TOUCH means children was modified - // before. + // We record empty merge value, since real children merges are already expanded. This is needed to + // satisfy non-null for merge original merge value can not be used since it mean different order of + // operation - parent changes are always resolved before children ones, and having node in TOUCH means + // children was modified before. modification.updateValue(LogicalOperation.MERGE, support.createEmptyValue(value)); return; case MERGE: @@ -320,9 +316,11 @@ abstract class AbstractNodeContainerModificationStrategy @Override protected TreeNode applyTouch(final ModifiedNode modification, final TreeNode currentMeta, final Version version) { /* - * The user may have issued an empty merge operation. In this case we do not perform - * a data tree mutation, do not pass GO, and do not collect useless garbage. It - * also means the ModificationType is UNMODIFIED. + * The user may have issued an empty merge operation. In this case we: + * - do not perform a data tree mutation + * - do not pass GO, and + * - do not collect useless garbage. + * It also means the ModificationType is UNMODIFIED. */ final Collection children = modification.getChildren(); if (!children.isEmpty()) { @@ -333,12 +331,12 @@ abstract class AbstractNodeContainerModificationStrategy final TreeNode ret = mutateChildren(newMeta, dataBuilder, version, children); /* - * It is possible that the only modifications under this node were empty merges, - * which were turned into UNMODIFIED. If that is the case, we can turn this operation - * into UNMODIFIED, too, potentially cascading it up to root. This has the benefit - * of speeding up any users, who can skip processing child nodes. + * It is possible that the only modifications under this node were empty merges, which were turned into + * UNMODIFIED. If that is the case, we can turn this operation into UNMODIFIED, too, potentially cascading + * it up to root. This has the benefit of speeding up any users, who can skip processing child nodes. * * In order to do that, though, we have to check all child operations are UNMODIFIED. + * * Let's do precisely that, stopping as soon we find a different result. */ for (final ModifiedNode child : children) { diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/BinaryValue.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/BinaryValue.java new file mode 100644 index 0000000000..088d0b65b2 --- /dev/null +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/BinaryValue.java @@ -0,0 +1,49 @@ +/* + * 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.yangtools.yang.data.impl.schema.tree; + +import static java.util.Objects.requireNonNull; + +import java.util.Arrays; +import java.util.Base64; +import org.opendaylight.yangtools.concepts.Immutable; + +final class BinaryValue implements Immutable { + private final byte[] value; + + private BinaryValue(final byte[] value) { + this.value = requireNonNull(value); + } + + static Object wrap(final Object value) { + return value instanceof byte[] ? new BinaryValue((byte[]) value) : value; + } + + static Object wrapToString(final Object value) { + return value instanceof byte[] ? toString((byte[]) value) : value; + } + + @Override + public int hashCode() { + return Arrays.hashCode(value); + } + + @Override + public boolean equals(final Object obj) { + return obj == this || obj instanceof BinaryValue && Arrays.equals(value, ((BinaryValue) obj).value); + } + + @Override + public String toString() { + return toString(value); + } + + private static String toString(final byte[] value) { + return Base64.getEncoder().encodeToString(value); + } +} diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ListModificationStrategy.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ListModificationStrategy.java index 84e2d7d490..c8018ae90b 100644 --- a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ListModificationStrategy.java +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/ListModificationStrategy.java @@ -75,22 +75,20 @@ final class ListModificationStrategy extends SchemaAwareApplyOperation - * Operation is composite - operation on top level node consists of - * suboperations on child nodes. This allows to walk operation hierarchy and + * An operation responsible for applying {@link ModifiedNode} on tree. The operation is a hierachical composite - + * the operation on top level node consists of suboperations on child nodes. This allows to walk operation hierarchy and * invoke suboperations independently. * *

* Implementation notes *

    - *
  • - * Implementations MUST expose all nested suboperations which operates on child - * nodes expose via {@link #getChild(PathArgument)} method. - *
  • Same suboperations SHOULD be used when invoked via - * {@link #apply(ModifiedNode, Optional, Version)} if applicable. + *
  • Implementations MUST expose all nested suboperations which operates on child nodes expose via + * {@link #getChild(PathArgument)} method.
    • + *
  • Same suboperations SHOULD be used when invoked via {@link #apply(ModifiedNode, Optional, Version)}, + * if applicable.
    • + *
  • There are exactly two base implementations: + *
      + *
    • {@link SchemaAwareApplyOperation}, which serves as the base class for stateful mutators -- directly + * impacting the layout and transitions of the {@link TreeNode} hierarchy. + *
    • {@link AbstractValidation}, which serves as the base class for stateless checks, which work purely on top + * of the {@link TreeNode} hierarchy. These are always overlaid on top of some other + * {@link ModificationApplyOperation}, ultimately leading to a {@link SchemaAwareApplyOperation}. + *
    + * This allows baseline invocations from {@link OperationWithModification} to be bimorphic in the first line of + * dispatch. + *
    • *
- * - *

- * Hierarchical composite operation which is responsible for applying - * modification on particular subtree and creating updated subtree */ abstract class ModificationApplyOperation implements StoreTreeNode { /** diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/SchemaAwareApplyOperation.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/SchemaAwareApplyOperation.java index ae8440ce84..9531d837ac 100644 --- a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/SchemaAwareApplyOperation.java +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/SchemaAwareApplyOperation.java @@ -104,7 +104,7 @@ abstract class SchemaAwareApplyOperation extends Modificat op = MapModificationStrategy.of(schemaNode, treeConfig); } - return MinMaxElementsValidation.from(op); + return UniqueValidation.of(schemaNode, treeConfig, MinMaxElementsValidation.from(op)); } protected static void checkNotConflicting(final ModificationPath path, final TreeNode original, diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidation.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidation.java new file mode 100644 index 0000000000..b308a194b5 --- /dev/null +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidation.java @@ -0,0 +1,144 @@ +/* + * 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.yangtools.yang.data.impl.schema.tree; + +import static com.google.common.base.Preconditions.checkState; +import static com.google.common.base.Verify.verify; + +import com.google.common.base.MoreObjects.ToStringHelper; +import com.google.common.base.Stopwatch; +import com.google.common.collect.HashMultimap; +import com.google.common.collect.ImmutableList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.NonNullByDefault; +import org.eclipse.jdt.annotation.Nullable; +import org.opendaylight.yangtools.yang.common.QName; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier; +import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode; +import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; +import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodeContainer; +import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeConfiguration; +import org.opendaylight.yangtools.yang.data.api.schema.tree.UniqueConstraintException; +import org.opendaylight.yangtools.yang.model.api.DataNodeContainer; +import org.opendaylight.yangtools.yang.model.api.DataSchemaNode; +import org.opendaylight.yangtools.yang.model.api.ListSchemaNode; +import org.opendaylight.yangtools.yang.model.api.TypedDataSchemaNode; +import org.opendaylight.yangtools.yang.model.api.stmt.SchemaNodeIdentifier.Descendant; +import org.opendaylight.yangtools.yang.model.api.stmt.UniqueEffectiveStatement; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * A {@link AbstractValidation} which ensures a particular {@code list} node complies with its {@code unique} + * constraints. + */ +final class UniqueValidation extends AbstractValidation { + private static final Logger LOG = LoggerFactory.getLogger(UniqueValidation.class); + + private final @NonNull ImmutableList> validators; + + private UniqueValidation(final ModificationApplyOperation delegate, final List> validators) { + super(delegate); + this.validators = ImmutableList.copyOf(validators); + } + + static ModificationApplyOperation of(final ListSchemaNode schema, final DataTreeConfiguration treeConfig, + final ModificationApplyOperation delegate) { + final Collection uniques = schema.getUniqueConstraints(); + if (!treeConfig.isUniqueIndexEnabled() || uniques.isEmpty()) { + return delegate; + } + + final Stopwatch sw = Stopwatch.createStarted(); + final Map> paths = new HashMap<>(); + final List> validators = uniques.stream() + .map(unique -> UniqueValidator.of(unique.argument().stream() + .map(descendant -> paths.computeIfAbsent(descendant, key -> toDescendantPath(schema, key))) + .collect(ImmutableList.toImmutableList()))) + .collect(ImmutableList.toImmutableList()); + LOG.debug("Constructed {} validators in {}", validators.size(), sw); + + return validators.isEmpty() ? delegate : new UniqueValidation(delegate, validators); + } + + @Override + void enforceOnData(final NormalizedNode data) { + enforceOnData(data, (message, values) -> new IllegalArgumentException(message)); + } + + @Override + void enforceOnData(final ModificationPath path, final NormalizedNode data) + throws UniqueConstraintException { + enforceOnData(data, (message, values) -> new UniqueConstraintException(path.toInstanceIdentifier(), values, + message)); + } + + private void enforceOnData(final NormalizedNode data, + final ExceptionSupplier exceptionSupplier) throws T { + final Stopwatch sw = Stopwatch.createStarted(); + verify(data instanceof NormalizedNodeContainer, "Unexpected data %s", data); + final var children = ((NormalizedNodeContainer) data).getValue(); + final var collected = HashMultimap., Object>create(validators.size(), children.size()); + for (NormalizedNode child : children) { + verify(child instanceof DataContainerNode, "Unexpected child %s", child); + final DataContainerNode cont = (DataContainerNode) child; + + final Map, Object> valueCache = new HashMap<>(); + for (UniqueValidator validator : validators) { + final Object values = validator.extractValues(valueCache, cont); + final Object masked = BinaryValue.wrap(values); + if (!collected.put(validator, masked)) { + final Map index = validator.indexValues(values); + throw exceptionSupplier.get(cont.getIdentifier() + + " violates unique constraint on " + masked + " of " + index.keySet(), index); + } + } + } + + LOG.trace("Enforced {} validators in {}", validators.size(), sw); + } + + @Override + ToStringHelper addToStringAttributes(final ToStringHelper helper) { + return super.addToStringAttributes(helper.add("validators", validators)); + } + + private static ImmutableList toDescendantPath(final ListSchemaNode parent, + final Descendant descendant) { + final List qnames = descendant.getNodeIdentifiers(); + final ImmutableList.Builder builder = ImmutableList.builderWithExpectedSize(qnames.size()); + final Iterator it = descendant.getNodeIdentifiers().iterator(); + DataNodeContainer current = parent; + while (true) { + final QName qname = it.next(); + final DataSchemaNode next = current.findDataChildByName(qname) + .orElseThrow(() -> new IllegalStateException("Cannot find component " + qname + " of " + descendant)); + builder.add(NodeIdentifier.create(qname)); + if (!it.hasNext()) { + checkState(next instanceof TypedDataSchemaNode, "Unexpected schema %s for %s", next, descendant); + final ImmutableList ret = builder.build(); + LOG.trace("Resolved {} to {}", descendant, ret); + return ret; + } + + checkState(next instanceof DataNodeContainer, "Unexpected non-container %s for %s", next, descendant); + current = (DataNodeContainer) next; + } + } + + @FunctionalInterface + @NonNullByDefault + interface ExceptionSupplier { + T get(String message, Map values); + } +} diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidator.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidator.java new file mode 100644 index 0000000000..b7aeae1624 --- /dev/null +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValidator.java @@ -0,0 +1,188 @@ +/* + * 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.yangtools.yang.data.impl.schema.tree; + +import static com.google.common.base.Preconditions.checkState; +import static com.google.common.base.Verify.verify; +import static java.util.Objects.requireNonNull; + +import com.google.common.base.MoreObjects; +import com.google.common.collect.Collections2; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Maps; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; +import org.opendaylight.yangtools.concepts.Immutable; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier; +import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild; +import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode; +import org.opendaylight.yangtools.yang.data.api.schema.LeafNode; +import org.opendaylight.yangtools.yang.model.api.stmt.SchemaNodeIdentifier.Descendant; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * A validator for a single {@code unique} constraint. This class is further specialized for single- and + * multiple-constraint implementations. + * + *

+ * The basic idea is that for each list entry there is a corresponding value vector of one or more values, each + * corresponding to one component of the {@code unique} constraint. + */ +abstract class UniqueValidator implements Immutable { + private static final class One extends UniqueValidator { + One(final List path) { + super(encodePath(path)); + } + + @Override + Object extractValues(final Map, Object> valueCache, final DataContainerNode data) { + return extractValue(valueCache, data, decodePath(descendants)); + } + + @Override + Map indexValues(final Object values) { + return Collections.singletonMap(decodeDescendant(descendants), values); + } + } + + private static final class Many extends UniqueValidator> { + Many(final List> descendantPaths) { + super(descendantPaths.stream().map(UniqueValidator::encodePath).collect(ImmutableSet.toImmutableSet())); + } + + @Override + UniqueValues extractValues(final Map, Object> valueCache, + final DataContainerNode data) { + return descendants.stream() + .map(obj -> extractValue(valueCache, data, decodePath(obj))) + .collect(UniqueValues.COLLECTOR); + } + + @Override + Map indexValues(final Object values) { + final Map index = Maps.newHashMapWithExpectedSize(descendants.size()); + final Iterator it = ((UniqueValues) values).iterator(); + for (Object obj : descendants) { + verify(index.put(decodeDescendant(obj), it.next()) == null); + } + return index; + } + } + + private static final Logger LOG = LoggerFactory.getLogger(UniqueValidator.class); + + final @NonNull T descendants; + + UniqueValidator(final T descendants) { + this.descendants = requireNonNull(descendants); + } + + static UniqueValidator of(final List> descendants) { + return descendants.size() == 1 ? new One(descendants.get(0)) : new Many(descendants); + } + + /** + * Extract a value vector from a particular child. + * + * @param valueCache Cache of descendants already looked up + * @param data Root data node + * @return Value vector + */ + abstract @Nullable Object extractValues(Map, Object> valueCache, + DataContainerNode data); + + /** + * Index a value vector by associating each value with its corresponding {@link Descendant}. + * + * @param values Value vector + * @return Map of Descandant/value relations + */ + abstract Map indexValues(Object values); + + /** + * Encode a path for storage. Single-element paths are squashed to their only element. The inverse operation is + * {@link #decodePath(Object)}. + * + * @param path Path to encode + * @return Encoded path. + */ + static final Object encodePath(final List path) { + return path.size() == 1 ? path.get(0) : ImmutableList.copyOf(path); + } + + /** + * Decode a path from storage. This is the inverse operation to {@link #encodePath(List)}. + * + * @param obj Encoded path + * @return Decoded path + */ + static final @NonNull ImmutableList decodePath(final Object obj) { + return obj instanceof NodeIdentifier ? ImmutableList.of((NodeIdentifier) obj) + : (ImmutableList) obj; + } + + static final @NonNull Descendant decodeDescendant(final Object obj) { + return Descendant.of(Collections2.transform(decodePath(obj), NodeIdentifier::getNodeType)); + } + + /** + * Extract the value for a single descendant. + * + * @param valueCache Cache of descendants already looked up + * @param data Root data node + * @param path Descendant path + * @return Value for the descendant + */ + static final @Nullable Object extractValue(final Map, Object> valueCache, + final DataContainerNode data, final List path) { + return valueCache.computeIfAbsent(path, key -> extractValue(data, key)); + } + + /** + * Extract the value for a single descendant. + * + * @param data Root data node + * @param path Descendant path + * @return Value for the descendant + */ + private static @Nullable Object extractValue(final DataContainerNode data, final List path) { + DataContainerNode current = data; + final Iterator it = path.iterator(); + while (true) { + final NodeIdentifier step = it.next(); + final Optional> optNext = current.getChild(step); + if (optNext.isEmpty()) { + return null; + } + + final DataContainerChild next = optNext.orElseThrow(); + if (!it.hasNext()) { + checkState(next instanceof LeafNode, "Unexpected node %s at %s", next, path); + final Object value = next.getValue(); + LOG.trace("Resolved {} to value {}", path, value); + return value; + } + + checkState(next instanceof DataContainerNode, "Unexpected node %s in %s", next, path); + current = (DataContainerNode) next; + } + } + + @Override + public final String toString() { + return MoreObjects.toStringHelper(this).add("paths", descendants).toString(); + } +} diff --git a/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValues.java b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValues.java new file mode 100644 index 0000000000..46ac64d1d3 --- /dev/null +++ b/yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueValues.java @@ -0,0 +1,94 @@ +/* + * 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.yangtools.yang.data.impl.schema.tree; + +import static com.google.common.base.Verify.verify; +import static java.util.Objects.requireNonNull; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Iterator; +import java.util.NoSuchElementException; +import java.util.stream.Collector; +import org.opendaylight.yangtools.concepts.Immutable; + +/** + * A vector of values associated with a unique constraint. This is almost an {@link ArrayList}, except it is + * unmodifiable. + */ +final class UniqueValues implements Immutable, Iterable { + static final Collector COLLECTOR = Collector.of(ArrayList::new, ArrayList::add, + (left, right) -> { + left.addAll(right); + return left; + }, + list -> new UniqueValues(list.toArray())); + + private final Object[] objects; + private final int hashCode; + + private UniqueValues(final Object[] objects) { + verify(objects.length != 0); + this.objects = objects; + this.hashCode = Arrays.deepHashCode(objects); + } + + @Override + public Iterator iterator() { + return new Itr(objects); + } + + @Override + public int hashCode() { + return hashCode; + } + + @Override + public boolean equals(final Object obj) { + return this == obj || obj instanceof UniqueValues && Arrays.deepEquals(objects, ((UniqueValues) obj).objects); + } + + @Override + public String toString() { + return toString(objects); + } + + private static String toString(final Object[] objects) { + final StringBuilder sb = new StringBuilder(); + sb.append('[').append(BinaryValue.wrapToString(objects[0])); + for (int i = 1; i < objects.length; ++i) { + sb.append(", ").append(BinaryValue.wrapToString(objects[i])); + } + return sb.append(']').toString(); + } + + private static final class Itr implements Iterator { + private final Object[] objects; + + private int offset = 0; + + Itr(final Object[] objects) { + this.objects = requireNonNull(objects); + } + + @Override + public boolean hasNext() { + return offset < objects.length; + } + + @Override + public Object next() { + int local = offset; + if (local >= objects.length) { + throw new NoSuchElementException(); + } + offset = local + 1; + return objects[local]; + } + } +} diff --git a/yang/yang-data-impl/src/test/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueConstraintTest.java b/yang/yang-data-impl/src/test/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueConstraintTest.java new file mode 100644 index 0000000000..4db997ad8b --- /dev/null +++ b/yang/yang-data-impl/src/test/java/org/opendaylight/yangtools/yang/data/impl/schema/tree/UniqueConstraintTest.java @@ -0,0 +1,268 @@ +/* + * Copyright (c) 2016 Cisco Systems, Inc. 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.yangtools.yang.data.impl.schema.tree; + +import static org.hamcrest.CoreMatchers.containsString; +import static org.hamcrest.CoreMatchers.startsWith; +import static org.hamcrest.MatcherAssert.assertThat; +import static org.junit.Assert.assertThrows; + +import org.junit.BeforeClass; +import org.junit.Test; +import org.opendaylight.yangtools.yang.common.QName; +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.NodeIdentifierWithPredicates; +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.tree.DataTreeCandidate; +import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeConfiguration; +import org.opendaylight.yangtools.yang.data.api.schema.tree.DataValidationFailedException; +import org.opendaylight.yangtools.yang.data.api.schema.tree.TreeType; +import org.opendaylight.yangtools.yang.data.api.schema.tree.UniqueConstraintException; +import org.opendaylight.yangtools.yang.data.impl.schema.Builders; +import org.opendaylight.yangtools.yang.data.impl.schema.ImmutableNodes; +import org.opendaylight.yangtools.yang.model.api.EffectiveModelContext; +import org.opendaylight.yangtools.yang.parser.spi.meta.ReactorException; + +public class UniqueConstraintTest { + private static final String NS = "foo"; + private static final String REV = "2016-05-17"; + private static final QName TASK_CONTAINER = QName.create(NS, REV, "task-container"); + private static final QName TASK = QName.create(NS, REV, "task"); + private static final QName TASK_ID = QName.create(NS, REV, "task-id"); + private static final QName MY_LEAF_1 = QName.create(NS, REV, "my-leaf-1"); + private static final QName MY_LEAF_2 = QName.create(NS, REV, "my-leaf-2"); + private static final QName MY_LEAF_3 = QName.create(NS, REV, "my-leaf-3"); + private static final QName MY_CONTAINER = QName.create(NS, REV, "my-container"); + + private static EffectiveModelContext TEST_MODEL; + + @BeforeClass + public static void beforeClass() { + TEST_MODEL = TestModel.createTestContext("/yt570.yang"); + } + + @Test + public void switchEntriesTest() throws ReactorException, DataValidationFailedException { + final InMemoryDataTree inMemoryDataTree = initDataTree(TEST_MODEL, true); + writeMapEntry(inMemoryDataTree, "1", "l1", "l2", "l3"); + writeMapEntry(inMemoryDataTree, "2", "l2", "l3", "l4"); + + final InMemoryDataTreeModification modificationTree = inMemoryDataTree.takeSnapshot().newModification(); + + final MapEntryNode mapEntry1 = createMapEntry("1", "l2", "l3", "l4"); + final MapEntryNode mapEntry2 = createMapEntry("2", "l1", "l2", "l3"); + + //switch values of map entries + modificationTree.write( + YangInstanceIdentifier.of(TASK_CONTAINER).node(TASK) + .node(NodeIdentifierWithPredicates.of(TASK, TASK_ID, "1")), mapEntry1); + modificationTree.write( + YangInstanceIdentifier.of(TASK_CONTAINER).node(TASK) + .node(NodeIdentifierWithPredicates.of(TASK, TASK_ID, "2")), mapEntry2); + + modificationTree.ready(); + inMemoryDataTree.validate(modificationTree); + final DataTreeCandidate prepare = inMemoryDataTree.prepare(modificationTree); + inMemoryDataTree.commit(prepare); + } + + @Test + public void mapTest() throws ReactorException, DataValidationFailedException { + final InMemoryDataTree inMemoryDataTree = emptyDataTree(TEST_MODEL, true); + + + verifyExceptionMessage(assertThrows(IllegalArgumentException.class, () -> writeMap(inMemoryDataTree, true)), + "(foo?revision=2016-05-17)task[{(foo?revision=2016-05-17)task-id=", + "}] violates unique constraint on [l2, l1] of ", + "(foo?revision=2016-05-17)my-leaf-1", + "(foo?revision=2016-05-17)my-leaf-2]"); + + writeMap(inMemoryDataTree, false); + verifyExceptionMessage(assertThrows(UniqueConstraintException.class, + () -> writeMapEntry(inMemoryDataTree, "4", "l1", "l2", "l30")), + "(foo?revision=2016-05-17)task[{(foo?revision=2016-05-17)task-id=", + "}] violates unique constraint on [l2, l1] of ", + "(foo?revision=2016-05-17)my-leaf-1", + "(foo?revision=2016-05-17)my-leaf-2"); + } + + @Test + public void mapEntryTest() throws ReactorException, DataValidationFailedException { + final InMemoryDataTree inMemoryDataTree = initDataTree(TEST_MODEL, true); + writeAndRemoveMapEntries(inMemoryDataTree, true); + writeAndRemoveMapEntries(inMemoryDataTree, false); + } + + private static void writeAndRemoveMapEntries(final InMemoryDataTree inMemoryDataTree, final boolean clear) + throws DataValidationFailedException { + writeMapEntry(inMemoryDataTree, "1", "l1", "l2", "l3"); + writeMapEntry(inMemoryDataTree, "2", "l2", "l3", "l4"); + writeMapEntry(inMemoryDataTree, "3", "l3", "l4", "l5"); + writeMapEntry(inMemoryDataTree, "2", "l2", "l3", "l6"); + writeMapEntry(inMemoryDataTree, "10", "l2", "l10", "l4"); + verifyExceptionMessage(assertThrows(UniqueConstraintException.class, + () -> writeMapEntry(inMemoryDataTree, "4", "l1", "l5", "l3")), + "(foo?revision=2016-05-17)task[{(foo?revision=2016-05-17)task-id=", + "}] violates unique constraint on [l1, l3] of ", + "(foo?revision=2016-05-17)my-container, my-leaf-3", + "(foo?revision=2016-05-17)my-leaf-1"); + writeMapEntry(inMemoryDataTree, "4", "l4", "l5", "l6"); + verifyExceptionMessage(assertThrows(UniqueConstraintException.class, + () -> writeMapEntry(inMemoryDataTree, "5", "l3", "l4", "l7")), + "(foo?revision=2016-05-17)task[{(foo?revision=2016-05-17)task-id=", + "}] violates unique constraint on [l4, l3] of ", + "(foo?revision=2016-05-17)my-leaf-1", + "(foo?revision=2016-05-17)my-leaf-2"); + removeMapEntry(inMemoryDataTree, taskEntryKey("3")); + writeMapEntry(inMemoryDataTree, "5", "l3", "l4", "l7"); + writeMapEntry(inMemoryDataTree, "5", "l3", "l4", "l7"); + verifyExceptionMessage(assertThrows(UniqueConstraintException.class, + () -> writeMapEntry(inMemoryDataTree, "6", "l3", "l4", "l11")), + "(foo?revision=2016-05-17)task[{(foo?revision=2016-05-17)task-id=", + "}] violates unique constraint on [l4, l3] of ", + "(foo?revision=2016-05-17)my-leaf-1", + "(foo?revision=2016-05-17)my-leaf-2"); + + if (clear) { + removeMapEntry(inMemoryDataTree, taskEntryKey("1")); + removeMapEntry(inMemoryDataTree, taskEntryKey("2")); + removeMapEntry(inMemoryDataTree, taskEntryKey("4")); + removeMapEntry(inMemoryDataTree, taskEntryKey("5")); + removeMapEntry(inMemoryDataTree, taskEntryKey("10")); + } + } + + private static void verifyExceptionMessage(final Exception ex, final String expectedStart, + final String... expectedLeaves) { + verifyExceptionMessage(expectedStart, ex.getMessage(), expectedLeaves); + } + + private static void verifyExceptionMessage(final String expectedStart, final String message, + final String... leafs) { + assertThat(message, startsWith(expectedStart)); + for (final String leaf : leafs) { + assertThat(message, containsString(leaf)); + } + } + + private static void writeMap(final InMemoryDataTree inMemoryDataTree, final boolean withUniqueViolation) + throws DataValidationFailedException { + final MapNode taskNode = Builders + .mapBuilder() + .withNodeIdentifier(new NodeIdentifier(TASK)) + .withChild(createMapEntry("1", "l1", "l2", "l3")) + .withChild(createMapEntry("2", "l2", "l3", "l4")) + .withChild( + withUniqueViolation ? createMapEntry("3", "l1", "l2", "l10") : createMapEntry("3", "l3", "l4", + "l5")).build(); + + final InMemoryDataTreeModification modificationTree = inMemoryDataTree.takeSnapshot().newModification(); + modificationTree.write(YangInstanceIdentifier.of(TASK_CONTAINER).node(TASK), taskNode); + modificationTree.ready(); + inMemoryDataTree.validate(modificationTree); + final DataTreeCandidate prepare = inMemoryDataTree.prepare(modificationTree); + inMemoryDataTree.commit(prepare); + } + + private static void writeMapEntry(final InMemoryDataTree inMemoryDataTree, final Object taskIdValue, + final Object myLeaf1Value, final Object myLeaf2Value, final Object myLeaf3Value) + throws DataValidationFailedException { + final MapEntryNode taskEntryNode = Builders + .mapEntryBuilder() + .withNodeIdentifier(NodeIdentifierWithPredicates.of(TASK, TASK_ID, taskIdValue)) + .withChild(ImmutableNodes.leafNode(TASK_ID, taskIdValue)) + .withChild(ImmutableNodes.leafNode(MY_LEAF_1, myLeaf1Value)) + .withChild(ImmutableNodes.leafNode(MY_LEAF_2, myLeaf2Value)) + .withChild( + Builders.containerBuilder().withNodeIdentifier(new NodeIdentifier(MY_CONTAINER)) + .withChild(ImmutableNodes.leafNode(MY_LEAF_3, myLeaf3Value)).build()).build(); + + final InMemoryDataTreeModification modificationTree = inMemoryDataTree.takeSnapshot().newModification(); + modificationTree.write( + YangInstanceIdentifier.of(TASK_CONTAINER).node(TASK) + .node(NodeIdentifierWithPredicates.of(TASK, TASK_ID, taskIdValue)), + taskEntryNode); + modificationTree.ready(); + inMemoryDataTree.validate(modificationTree); + final DataTreeCandidate prepare = inMemoryDataTree.prepare(modificationTree); + inMemoryDataTree.commit(prepare); + } + + private static void removeMapEntry(final InMemoryDataTree inMemoryDataTree, + final NodeIdentifierWithPredicates mapEntryKey) throws DataValidationFailedException { + final InMemoryDataTreeModification modificationTree = inMemoryDataTree.takeSnapshot().newModification(); + modificationTree.delete(YangInstanceIdentifier.of(TASK_CONTAINER).node(TASK).node(mapEntryKey)); + modificationTree.ready(); + inMemoryDataTree.validate(modificationTree); + final DataTreeCandidate prepare = inMemoryDataTree.prepare(modificationTree); + inMemoryDataTree.commit(prepare); + } + + private static MapEntryNode createMapEntry(final Object taskIdValue, final Object myLeaf1Value, + final Object myLeaf2Value, final Object myLeaf3Value) throws DataValidationFailedException { + return Builders + .mapEntryBuilder() + .withNodeIdentifier(NodeIdentifierWithPredicates.of(TASK, TASK_ID, taskIdValue)) + .withChild(ImmutableNodes.leafNode(TASK_ID, taskIdValue)) + .withChild(ImmutableNodes.leafNode(MY_LEAF_1, myLeaf1Value)) + .withChild(ImmutableNodes.leafNode(MY_LEAF_2, myLeaf2Value)) + .withChild( + Builders.containerBuilder().withNodeIdentifier(new NodeIdentifier(MY_CONTAINER)) + .withChild(ImmutableNodes.leafNode(MY_LEAF_3, myLeaf3Value)).build()).build(); + } + + private static NodeIdentifierWithPredicates taskEntryKey(final String taskId) { + return NodeIdentifierWithPredicates.of(TASK, TASK_ID, taskId); + } + + @Test + public void disabledUniqueIndexTest() throws ReactorException, DataValidationFailedException { + final InMemoryDataTree inMemoryDataTree = initDataTree(TEST_MODEL, false); + + writeMapEntry(inMemoryDataTree, "1", "l1", "l2", "l3"); + writeMapEntry(inMemoryDataTree, "2", "l2", "l3", "l4"); + writeMapEntry(inMemoryDataTree, "3", "l3", "l4", "l5"); + writeMapEntry(inMemoryDataTree, "2", "l2", "l3", "l6"); + writeMapEntry(inMemoryDataTree, "10", "l2", "l10", "l4"); + writeMapEntry(inMemoryDataTree, "4", "l1", "l5", "l3"); + writeMapEntry(inMemoryDataTree, "4", "l4", "l5", "l6"); + writeMapEntry(inMemoryDataTree, "5", "l3", "l4", "l7"); + removeMapEntry(inMemoryDataTree, taskEntryKey("3")); + writeMapEntry(inMemoryDataTree, "5", "l3", "l4", "l7"); + writeMapEntry(inMemoryDataTree, "5", "l3", "l4", "l7"); + writeMapEntry(inMemoryDataTree, "6", "l3", "l4", "l7"); + } + + private static InMemoryDataTree initDataTree(final EffectiveModelContext schemaContext, final boolean uniqueIndex) + throws DataValidationFailedException { + final InMemoryDataTree inMemoryDataTree = (InMemoryDataTree) new InMemoryDataTreeFactory().create( + new DataTreeConfiguration.Builder(TreeType.CONFIGURATION).setUniqueIndexes(uniqueIndex).build()); + inMemoryDataTree.setEffectiveModelContext(schemaContext); + + final MapNode taskNode = Builders.mapBuilder().withNodeIdentifier(new NodeIdentifier(TASK)).build(); + final InMemoryDataTreeModification modificationTree = inMemoryDataTree.takeSnapshot().newModification(); + modificationTree.write(YangInstanceIdentifier.of(TASK_CONTAINER).node(TASK), taskNode); + modificationTree.ready(); + + inMemoryDataTree.validate(modificationTree); + final DataTreeCandidate prepare = inMemoryDataTree.prepare(modificationTree); + inMemoryDataTree.commit(prepare); + return inMemoryDataTree; + } + + private static InMemoryDataTree emptyDataTree(final EffectiveModelContext schemaContext, final boolean uniqueIndex) + throws DataValidationFailedException { + final InMemoryDataTree inMemoryDataTree = (InMemoryDataTree) new InMemoryDataTreeFactory().create( + new DataTreeConfiguration.Builder(TreeType.CONFIGURATION).setUniqueIndexes(uniqueIndex).build()); + inMemoryDataTree.setEffectiveModelContext(schemaContext); + + return inMemoryDataTree; + } +} diff --git a/yang/yang-data-impl/src/test/resources/yt570.yang b/yang/yang-data-impl/src/test/resources/yt570.yang new file mode 100644 index 0000000000..a1ee7fc9c6 --- /dev/null +++ b/yang/yang-data-impl/src/test/resources/yt570.yang @@ -0,0 +1,82 @@ +module foo { + yang-version 1; + namespace "foo"; + prefix foo; + + revision 2016-05-17 { + description "test"; + } + + container task-container { + list task { + key "task-id"; + unique "my-leaf-1 my-leaf-2"; + unique "my-leaf-1 my-container/my-leaf-3"; + + leaf task-id { + type string; + } + leaf my-leaf-1 { + type string; + } + leaf my-leaf-2 { + type string; + } + container my-container { + leaf my-leaf-3 { + type string; + } + } + } + } + + list inside-list { + list inner { + leaf inner-leaf { + type string; + } + } + + unique "inner/inner-leaf"; + } + + list cross-list { + key "k"; + leaf k { + type string; + } + list one { + key "one"; + leaf one { + type string; + } + leaf one-leaf { + type string; + } + } + + list two { + key "two"; + leaf two { + type string; + } + leaf two-leaf { + type string; + } + } + + unique "one/one-leaf two/two-leaf"; + } + + list nested-list { + list one { + list two { + leaf two-leaf { + type string; + } + } + } + + unique "one/two/two-leaf"; + } +} -- 2.36.6