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