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