data/yang-data-tree-ri/src/main/java/org/opendaylight/yangtools/yang/data/tree/leafref/LeafRefValidation.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. 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.data.tree.leafref;
   9
  10 import com.google.common.collect.ImmutableList;
  11 import com.google.common.collect.ImmutableSet;
  12 import java.util.ArrayDeque;
  13 import java.util.ArrayList;
  14 import java.util.Collection;
  15 import java.util.Deque;
  16 import java.util.HashMap;
  17 import java.util.HashSet;
  18 import java.util.Iterator;
  19 import java.util.List;
  20 import java.util.Map;
  21 import java.util.Map.Entry;
  22 import java.util.Optional;
  23 import java.util.Set;
  24 import java.util.function.Predicate;
  25 import java.util.stream.Collectors;
  26 import java.util.stream.Stream;
  27 import org.opendaylight.yangtools.yang.common.QName;
  28 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  29 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
  30 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  31 import org.opendaylight.yangtools.yang.data.api.schema.ChoiceNode;
  32 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild;
  33 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode;
  34 import org.opendaylight.yangtools.yang.data.api.schema.LeafNode;
  35 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetNode;
  36 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  37 import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
  38 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  39 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
  40 import org.opendaylight.yangtools.yang.data.api.schema.UnkeyedListEntryNode;
  41 import org.opendaylight.yangtools.yang.data.api.schema.ValueNode;
  42 import org.opendaylight.yangtools.yang.data.tree.api.DataTreeCandidate;
  43 import org.opendaylight.yangtools.yang.data.tree.api.DataTreeCandidateNode;
  44 import org.opendaylight.yangtools.yang.data.tree.api.ModificationType;
  45 import org.slf4j.Logger;
  46 import org.slf4j.LoggerFactory;
  47
  48 public final class LeafRefValidation {
  49     private static final Logger LOG = LoggerFactory.getLogger(LeafRefValidation.class);
  50     private static final String FAILED = " -> FAILED";
  51     private static final String SUCCESS = " -> OK";
  52
  53     private final Set<LeafRefContext> validatedLeafRefCtx = new HashSet<>();
  54     private final List<String> errorsMessages = new ArrayList<>();
  55     private final NormalizedNode root;
  56
  57     private LeafRefValidation(final NormalizedNode root) {
  58         this.root = root;
  59     }
  60
  61     public static void validate(final DataTreeCandidate tree, final LeafRefContext rootLeafRefCtx)
  62             throws LeafRefDataValidationFailedException {
  63         final var root = tree.getRootNode().getDataAfter();
  64         if (root.isPresent()) {
  65             new LeafRefValidation(root.orElseThrow())
  66                 .validateChildren(rootLeafRefCtx, tree.getRootNode().getChildNodes());
  67         }
  68     }
  69
  70     private void validateChildren(final LeafRefContext rootLeafRefCtx, final Collection<DataTreeCandidateNode> children)
  71             throws LeafRefDataValidationFailedException {
  72         for (var dataTreeCandidateNode : children) {
  73             if (dataTreeCandidateNode.getModificationType() != ModificationType.UNMODIFIED) {
  74                 final PathArgument identifier = dataTreeCandidateNode.getIdentifier();
  75                 final QName childQName = identifier.getNodeType();
  76
  77                 final LeafRefContext referencedByCtx = rootLeafRefCtx.getReferencedChildByName(childQName);
  78                 final LeafRefContext referencingCtx = rootLeafRefCtx.getReferencingChildByName(childQName);
  79                 if (referencedByCtx != null || referencingCtx != null) {
  80                     validateNode(dataTreeCandidateNode, referencedByCtx, referencingCtx,
  81                         YangInstanceIdentifier.create(identifier));
  82                 }
  83             }
  84         }
  85
  86         if (!errorsMessages.isEmpty()) {
  87             final StringBuilder message = new StringBuilder();
  88             int errCount = 0;
  89             for (var errorMessage : errorsMessages) {
  90                 message.append(errorMessage);
  91                 errCount++;
  92             }
  93             throw new LeafRefDataValidationFailedException(message.toString(), errCount);
  94         }
  95     }
  96
  97     private void validateNode(final DataTreeCandidateNode node, final LeafRefContext referencedByCtx,
  98         final LeafRefContext referencingCtx, final YangInstanceIdentifier current) {
  99
 100         if (node.getModificationType() == ModificationType.WRITE && node.getDataAfter().isPresent()) {
 101             validateNodeData(node.getDataAfter().orElseThrow(), referencedByCtx, referencingCtx,
 102                 node.getModificationType(), current);
 103             return;
 104         }
 105
 106         if (node.getModificationType() == ModificationType.DELETE && referencedByCtx != null) {
 107             validateNodeData(node.getDataBefore().orElseThrow(), referencedByCtx, null, node.getModificationType(),
 108                 current);
 109             return;
 110         }
 111
 112         for (var childNode : node.getChildNodes()) {
 113             if (childNode.getModificationType() != ModificationType.UNMODIFIED) {
 114                 final LeafRefContext childReferencedByCtx = getReferencedByCtxChild(referencedByCtx, childNode);
 115                 final LeafRefContext childReferencingCtx = getReferencingCtxChild(referencingCtx, childNode);
 116
 117                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 118                     validateNode(childNode, childReferencedByCtx,childReferencingCtx,
 119                         current.node(childNode.getIdentifier()));
 120                 }
 121             }
 122         }
 123     }
 124
 125     private static LeafRefContext getReferencingCtxChild(final LeafRefContext referencingCtx,
 126             final DataTreeCandidateNode childNode) {
 127         if (referencingCtx == null) {
 128             return null;
 129         }
 130
 131         final QName childQName = childNode.getIdentifier().getNodeType();
 132         LeafRefContext childReferencingCtx = referencingCtx.getReferencingChildByName(childQName);
 133         if (childReferencingCtx == null) {
 134             final NormalizedNode data = childNode.getDataAfter().orElseThrow();
 135             if (data instanceof MapEntryNode || data instanceof UnkeyedListEntryNode) {
 136                 childReferencingCtx = referencingCtx;
 137             }
 138         }
 139
 140         return childReferencingCtx;
 141     }
 142
 143     private static LeafRefContext getReferencedByCtxChild(final LeafRefContext referencedByCtx,
 144             final DataTreeCandidateNode childNode) {
 145         if (referencedByCtx == null) {
 146             return null;
 147         }
 148
 149         final QName childQName = childNode.getIdentifier().getNodeType();
 150         LeafRefContext childReferencedByCtx = referencedByCtx.getReferencedChildByName(childQName);
 151         if (childReferencedByCtx == null) {
 152             final NormalizedNode data = childNode.getDataAfter().orElseThrow();
 153             if (data instanceof MapEntryNode || data instanceof UnkeyedListEntryNode) {
 154                 childReferencedByCtx = referencedByCtx;
 155             }
 156         }
 157
 158         return childReferencedByCtx;
 159     }
 160
 161     private void validateNodeData(final NormalizedNode node, final LeafRefContext referencedByCtx,
 162             final LeafRefContext referencingCtx, final ModificationType modificationType,
 163             final YangInstanceIdentifier current) {
 164         if (node instanceof LeafNode) {
 165             validateLeafNodeData((LeafNode<?>) node, referencedByCtx, referencingCtx, modificationType, current);
 166         } else if (node instanceof LeafSetNode) {
 167             validateLeafSetNodeData((LeafSetNode<?>) node, referencedByCtx, referencingCtx, modificationType, current);
 168         } else if (node instanceof ChoiceNode) {
 169             validateChoiceNodeData((ChoiceNode) node, referencedByCtx, referencingCtx, modificationType, current);
 170         } else if (node instanceof DataContainerNode) {
 171             validateDataContainerNodeData((DataContainerNode) node, referencedByCtx, referencingCtx, modificationType,
 172                 current);
 173         } else if (node instanceof MapNode) {
 174             validateMapNodeData((MapNode) node, referencedByCtx, referencingCtx, modificationType, current);
 175         }
 176         // FIXME: check UnkeyedListNode case
 177     }
 178
 179     private void validateLeafNodeData(final LeafNode<?> node, final LeafRefContext referencedByCtx,
 180             final LeafRefContext referencingCtx, final ModificationType modificationType,
 181             final YangInstanceIdentifier current) {
 182         if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 183             validateLeafRefTargetNodeData(node, referencedByCtx, modificationType);
 184         }
 185         if (referencingCtx != null && referencingCtx.isReferencing()) {
 186             validateLeafRefNodeData(node, referencingCtx, modificationType, current);
 187         }
 188     }
 189
 190     private void validateLeafSetNodeData(final LeafSetNode<?> node, final LeafRefContext referencedByCtx,
 191             final LeafRefContext referencingCtx, final ModificationType modificationType,
 192             final YangInstanceIdentifier current) {
 193         if (referencedByCtx != null || referencingCtx != null) {
 194             for (final NormalizedNode leafSetEntry : node.body()) {
 195                 if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 196                     validateLeafRefTargetNodeData(leafSetEntry, referencedByCtx, modificationType);
 197                 }
 198                 if (referencingCtx != null && referencingCtx.isReferencing()) {
 199                     validateLeafRefNodeData(leafSetEntry, referencingCtx, modificationType, current);
 200                 }
 201             }
 202         }
 203     }
 204
 205     private void validateChoiceNodeData(final ChoiceNode node, final LeafRefContext referencedByCtx,
 206             final LeafRefContext referencingCtx, final ModificationType modificationType,
 207             final YangInstanceIdentifier current) {
 208         for (final DataContainerChild child : node.body()) {
 209             final QName qname = child.getIdentifier().getNodeType();
 210             final LeafRefContext childReferencedByCtx = referencedByCtx == null ? null
 211                     : findReferencedByCtxUnderChoice(referencedByCtx, qname);
 212             final LeafRefContext childReferencingCtx = referencingCtx == null ? null
 213                     : findReferencingCtxUnderChoice(referencingCtx, qname);
 214             if (childReferencedByCtx != null || childReferencingCtx != null) {
 215                 validateNodeData(child, childReferencedByCtx, childReferencingCtx, modificationType,
 216                     current.node(child.getIdentifier()));
 217             }
 218         }
 219     }
 220
 221     private void validateDataContainerNodeData(final DataContainerNode node, final LeafRefContext referencedByCtx,
 222             final LeafRefContext referencingCtx, final ModificationType modificationType,
 223             final YangInstanceIdentifier current) {
 224         for (final DataContainerChild child : node.body()) {
 225             validateChildNodeData(child, referencedByCtx, referencingCtx, modificationType, current);
 226         }
 227     }
 228
 229     private void validateMapNodeData(final MapNode node, final LeafRefContext referencedByCtx,
 230             final LeafRefContext referencingCtx, final ModificationType modificationType,
 231             final YangInstanceIdentifier current) {
 232         for (final MapEntryNode mapEntry : node.asMap().values()) {
 233             final YangInstanceIdentifier mapEntryIdentifier = current.node(mapEntry.getIdentifier());
 234             for (final DataContainerChild child : mapEntry.body()) {
 235                 validateChildNodeData(child, referencedByCtx, referencingCtx, modificationType, mapEntryIdentifier);
 236             }
 237         }
 238     }
 239
 240     private void validateChildNodeData(final DataContainerChild child, final LeafRefContext referencedByCtx,
 241             final LeafRefContext referencingCtx, final ModificationType modificationType,
 242             final YangInstanceIdentifier current) {
 243         final QName qname = child.getIdentifier().getNodeType();
 244         final LeafRefContext childReferencedByCtx = referencedByCtx == null ? null
 245                 : referencedByCtx.getReferencedChildByName(qname);
 246         final LeafRefContext childReferencingCtx = referencingCtx == null ? null
 247                 : referencingCtx.getReferencingChildByName(qname);
 248         if (childReferencedByCtx != null || childReferencingCtx != null) {
 249             validateNodeData(child, childReferencedByCtx, childReferencingCtx, modificationType, current.node(
 250                 child.getIdentifier()));
 251         }
 252     }
 253
 254     private static LeafRefContext findReferencingCtxUnderChoice(final LeafRefContext referencingCtx,
 255             final QName qname) {
 256         for (final LeafRefContext child : referencingCtx.getReferencingChilds().values()) {
 257             final LeafRefContext referencingChildByName = child.getReferencingChildByName(qname);
 258             if (referencingChildByName != null) {
 259                 return referencingChildByName;
 260             }
 261         }
 262         return null;
 263     }
 264
 265     private static LeafRefContext findReferencedByCtxUnderChoice(final LeafRefContext referencedByCtx,
 266             final QName qname) {
 267         for (final LeafRefContext child : referencedByCtx.getReferencedByChilds().values()) {
 268             final LeafRefContext referencedByChildByName = child.getReferencedChildByName(qname);
 269             if (referencedByChildByName != null) {
 270                 return referencedByChildByName;
 271             }
 272         }
 273         return null;
 274     }
 275
 276     private void validateLeafRefTargetNodeData(final NormalizedNode leaf, final LeafRefContext
 277             referencedByCtx, final ModificationType modificationType) {
 278         if (!validatedLeafRefCtx.add(referencedByCtx)) {
 279             LOG.trace("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}] -> SKIP: Already "
 280                     + "validated", modificationType, referencedByCtx.getNodeName(), leaf.body());
 281             return;
 282         }
 283
 284         LOG.trace("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}]", modificationType,
 285             referencedByCtx.getNodeName(), leaf.body());
 286         final Set<LeafRefContext> leafRefs = referencedByCtx.getAllReferencedByLeafRefCtxs().values().stream()
 287                 .filter(LeafRefContext::isReferencing).collect(Collectors.toSet());
 288         if (leafRefs.isEmpty()) {
 289             return;
 290         }
 291
 292         final Set<Object> leafRefTargetNodeValues = extractRootValues(referencedByCtx);
 293         leafRefs.forEach(leafRefContext -> {
 294             extractRootValues(leafRefContext).forEach(leafRefsValue -> {
 295                 if (leafRefTargetNodeValues.contains(leafRefsValue)) {
 296                     LOG.trace("Valid leafref value [{}] {}", leafRefsValue, SUCCESS);
 297                     return;
 298                 }
 299
 300                 LOG.debug("Invalid leafref value [{}] allowed values {} by validation of leafref TARGET node: {} path "
 301                         + "of invalid LEAFREF node: {} leafRef target path: {} {}", leafRefsValue,
 302                         leafRefTargetNodeValues, leaf.getIdentifier(), leafRefContext.getCurrentNodePath(),
 303                         leafRefContext.getAbsoluteLeafRefTargetPath(), FAILED);
 304                 errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s by validation of leafref"
 305                         + " TARGET node: %s path of invalid LEAFREF node: %s leafRef target path: %s %s", leafRefsValue,
 306                         leafRefTargetNodeValues, leaf.getIdentifier(), leafRefContext.getCurrentNodePath(),
 307                         leafRefContext.getAbsoluteLeafRefTargetPath(),
 308                         FAILED));
 309             });
 310         });
 311     }
 312
 313     private Set<Object> extractRootValues(final LeafRefContext context) {
 314         return computeValues(root, createPath(context.getLeafRefNodePath()), null);
 315     }
 316
 317     private void validateLeafRefNodeData(final NormalizedNode leaf, final LeafRefContext referencingCtx,
 318             final ModificationType modificationType, final YangInstanceIdentifier current) {
 319         final Set<Object> values = computeValues(root, createPath(referencingCtx.getAbsoluteLeafRefTargetPath()),
 320             current);
 321         if (values.contains(leaf.body())) {
 322             LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 323                 referencingCtx.getNodeName(), leaf.body(), SUCCESS);
 324             return;
 325         }
 326
 327         LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 328             referencingCtx.getNodeName(), leaf.body(), FAILED);
 329         LOG.debug("Invalid leafref value [{}] allowed values {} of LEAFREF node: {} leafRef target path: {}",
 330             leaf.body(), values, leaf.getIdentifier(), referencingCtx.getAbsoluteLeafRefTargetPath());
 331         errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s of LEAFREF node: %s leafRef "
 332                 + "target path: %s", leaf.body(), values, leaf.getIdentifier(),
 333                 referencingCtx.getAbsoluteLeafRefTargetPath()));
 334     }
 335
 336     private Set<Object> computeValues(final NormalizedNode node, final Deque<QNameWithPredicate> path,
 337             final YangInstanceIdentifier current) {
 338         final HashSet<Object> values = new HashSet<>();
 339         addValues(values, node, ImmutableList.of(), path, current);
 340         return values;
 341     }
 342
 343     private void addValues(final Set<Object> values, final NormalizedNode node,
 344             final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 345             final YangInstanceIdentifier current) {
 346         if (node instanceof ValueNode) {
 347             values.add(node.body());
 348             return;
 349         }
 350         if (node instanceof LeafSetNode<?>) {
 351             for (final NormalizedNode entry : ((LeafSetNode<?>) node).body()) {
 352                 values.add(entry.body());
 353             }
 354             return;
 355         }
 356
 357         final QNameWithPredicate next = path.peek();
 358         if (next == null) {
 359             return;
 360         }
 361
 362         final PathArgument pathArgument = new NodeIdentifier(next.getQName());
 363         if (node instanceof DataContainerNode) {
 364             processChildNode(values, (DataContainerNode) node, pathArgument, next.getQNamePredicates(), path, current);
 365         } else if (node instanceof MapNode) {
 366             Stream<MapEntryNode> entries = ((MapNode) node).body().stream();
 367             if (!nodePredicates.isEmpty() && current != null) {
 368                 entries = entries.filter(createMapEntryPredicate(nodePredicates, current));
 369             }
 370
 371             entries.forEach(entry -> processChildNode(values, entry, pathArgument, next.getQNamePredicates(), path,
 372                 current));
 373         }
 374     }
 375
 376     private void processChildNode(final Set<Object> values, final DataContainerNode parent,
 377             final PathArgument arg, final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 378             final YangInstanceIdentifier current) {
 379         final DataContainerChild child = parent.childByArg(arg);
 380         if (child == null) {
 381             // FIXME: YANGTOOLS-901. We have SchemaContext nearby, hence we should be able to cache how to get
 382             //        to the leaf with with specified QName, without having to iterate through Choices.
 383             //        That perhaps means we should not have QNameWithPredicates, but NodeIdentifierWithPredicates as
 384             //        the path specification.
 385             for (final DataContainerChild mixin : parent.body()) {
 386                 if (mixin instanceof ChoiceNode) {
 387                     addValues(values, mixin, nodePredicates, path, current);
 388                 }
 389             }
 390         } else {
 391             addNextValues(values, child, nodePredicates, path, current);
 392         }
 393     }
 394
 395     private Predicate<MapEntryNode> createMapEntryPredicate(final List<QNamePredicate> nodePredicates,
 396             final YangInstanceIdentifier current) {
 397         final Map<QName, Set<?>> keyValues = new HashMap<>();
 398         for (QNamePredicate predicate : nodePredicates) {
 399             keyValues.put(predicate.getIdentifier(), getPathKeyExpressionValues(predicate.getPathKeyExpression(),
 400                 current));
 401         }
 402
 403         return mapEntry -> {
 404             for (final Entry<QName, Object> entryKeyValue : mapEntry.getIdentifier().entrySet()) {
 405                 final Set<?> allowedValues = keyValues.get(entryKeyValue.getKey());
 406                 if (allowedValues != null && !allowedValues.contains(entryKeyValue.getValue())) {
 407                     return false;
 408                 }
 409             }
 410             return true;
 411         };
 412     }
 413
 414     private void addNextValues(final Set<Object> values, final NormalizedNode node,
 415             final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 416             final YangInstanceIdentifier current) {
 417         final QNameWithPredicate element = path.pop();
 418         try {
 419             addValues(values, node, nodePredicates, path, current);
 420         } finally {
 421             path.push(element);
 422         }
 423     }
 424
 425     private Set<?> getPathKeyExpressionValues(final LeafRefPath predicatePathKeyExpression,
 426             final YangInstanceIdentifier current) {
 427         return findParentNode(Optional.of(root), current).map(parent -> {
 428             final Deque<QNameWithPredicate> path = createPath(predicatePathKeyExpression);
 429             path.pollFirst();
 430             return computeValues(parent, path, null);
 431         }).orElse(ImmutableSet.of());
 432     }
 433
 434     private static Optional<NormalizedNode> findParentNode(
 435             final Optional<NormalizedNode> root, final YangInstanceIdentifier path) {
 436         Optional<NormalizedNode> currentNode = root;
 437         final Iterator<PathArgument> pathIterator = path.getPathArguments().iterator();
 438         while (pathIterator.hasNext()) {
 439             final PathArgument childPathArgument = pathIterator.next();
 440             if (pathIterator.hasNext() && currentNode.isPresent()) {
 441                 currentNode = NormalizedNodes.getDirectChild(currentNode.orElseThrow(), childPathArgument);
 442             } else {
 443                 return currentNode;
 444             }
 445         }
 446         return Optional.empty();
 447     }
 448
 449     private static Deque<QNameWithPredicate> createPath(final LeafRefPath path) {
 450         final Deque<QNameWithPredicate> ret = new ArrayDeque<>();
 451         path.getPathTowardsRoot().forEach(ret::push);
 452         return ret;
 453     }
 454 }