yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/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.impl.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.Consumer;
  25 import java.util.function.Predicate;
  26 import java.util.stream.Collectors;
  27 import java.util.stream.Stream;
  28 import org.opendaylight.yangtools.yang.common.QName;
  29 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  30 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
  31 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  32 import org.opendaylight.yangtools.yang.data.api.schema.AugmentationNode;
  33 import org.opendaylight.yangtools.yang.data.api.schema.ChoiceNode;
  34 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild;
  35 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode;
  36 import org.opendaylight.yangtools.yang.data.api.schema.LeafNode;
  37 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetNode;
  38 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  39 import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
  40 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  41 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
  42 import org.opendaylight.yangtools.yang.data.api.schema.UnkeyedListEntryNode;
  43 import org.opendaylight.yangtools.yang.data.api.schema.ValueNode;
  44 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidate;
  45 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidateNode;
  46 import org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType;
  47 import org.slf4j.Logger;
  48 import org.slf4j.LoggerFactory;
  49
  50 public final class LeafRefValidation {
  51     private static final Logger LOG = LoggerFactory.getLogger(LeafRefValidation.class);
  52     private static final String FAILED = " -> FAILED";
  53     private static final String SUCCESS = " -> OK";
  54
  55     private final Set<LeafRefContext> validatedLeafRefCtx = new HashSet<>();
  56     private final List<String> errorsMessages = new ArrayList<>();
  57     private final NormalizedNode<?, ?> root;
  58
  59     private LeafRefValidation(final NormalizedNode<?, ?> root) {
  60         this.root = root;
  61     }
  62
  63     public static void validate(final DataTreeCandidate tree, final LeafRefContext rootLeafRefCtx)
  64             throws LeafRefDataValidationFailedException {
  65         final Optional<NormalizedNode<?, ?>> root = tree.getRootNode().getDataAfter();
  66         if (root.isPresent()) {
  67             new LeafRefValidation(root.get()).validateChildren(rootLeafRefCtx, tree.getRootNode().getChildNodes());
  68         }
  69     }
  70
  71     private void validateChildren(final LeafRefContext rootLeafRefCtx, final Collection<DataTreeCandidateNode> children)
  72             throws LeafRefDataValidationFailedException {
  73         for (final DataTreeCandidateNode 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 (final String 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().get(), referencedByCtx, referencingCtx, node.getModificationType(),
 103                 current);
 104             return;
 105         }
 106
 107         if (node.getModificationType() == ModificationType.DELETE && referencedByCtx != null) {
 108             validateNodeData(node.getDataBefore().get(), referencedByCtx, null, node.getModificationType(), current);
 109             return;
 110         }
 111
 112         for (final DataTreeCandidateNode 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().get();
 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().get();
 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,
 172                 modificationType, 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.getValue()) {
 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.getValue()) {
 209             final QName qname = child.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.getValue()) {
 225             if (child instanceof AugmentationNode) {
 226                 validateNodeData(child, referencedByCtx, referencingCtx, modificationType, current.node(
 227                     child.getIdentifier()));
 228                 return;
 229             }
 230
 231             validateChildNodeData(child, referencedByCtx, referencingCtx, modificationType, current);
 232         }
 233     }
 234
 235     private void validateMapNodeData(final MapNode node, final LeafRefContext referencedByCtx,
 236             final LeafRefContext referencingCtx, final ModificationType modificationType,
 237             final YangInstanceIdentifier current) {
 238         for (final MapEntryNode mapEntry : node.getValue()) {
 239             final YangInstanceIdentifier mapEntryIdentifier = current.node(mapEntry.getIdentifier());
 240             for (final DataContainerChild<?, ?> child : mapEntry.getValue()) {
 241                 if (child instanceof AugmentationNode) {
 242                     validateNodeData(child, referencedByCtx, referencingCtx, modificationType, current.node(
 243                         child.getIdentifier()));
 244                     return;
 245                 }
 246
 247                 validateChildNodeData(child, referencedByCtx, referencingCtx, modificationType, mapEntryIdentifier);
 248             }
 249         }
 250     }
 251
 252     private void validateChildNodeData(final DataContainerChild<?, ?> child, final LeafRefContext referencedByCtx,
 253             final LeafRefContext referencingCtx, final ModificationType modificationType,
 254             final YangInstanceIdentifier current) {
 255         final QName qname = child.getNodeType();
 256         final LeafRefContext childReferencedByCtx = referencedByCtx == null ? null
 257                 : referencedByCtx.getReferencedChildByName(qname);
 258         final LeafRefContext childReferencingCtx = referencingCtx == null ? null
 259                 : referencingCtx.getReferencingChildByName(qname);
 260         if (childReferencedByCtx != null || childReferencingCtx != null) {
 261             validateNodeData(child, childReferencedByCtx, childReferencingCtx, modificationType, current.node(
 262                 child.getIdentifier()));
 263         }
 264     }
 265
 266     private static LeafRefContext findReferencingCtxUnderChoice(final LeafRefContext referencingCtx,
 267             final QName qname) {
 268         for (final LeafRefContext child : referencingCtx.getReferencingChilds().values()) {
 269             final LeafRefContext referencingChildByName = child.getReferencingChildByName(qname);
 270             if (referencingChildByName != null) {
 271                 return referencingChildByName;
 272             }
 273         }
 274         return null;
 275     }
 276
 277     private static LeafRefContext findReferencedByCtxUnderChoice(final LeafRefContext referencedByCtx,
 278             final QName qname) {
 279         for (final LeafRefContext child : referencedByCtx.getReferencedByChilds().values()) {
 280             final LeafRefContext referencedByChildByName = child.getReferencedChildByName(qname);
 281             if (referencedByChildByName != null) {
 282                 return referencedByChildByName;
 283             }
 284         }
 285         return null;
 286     }
 287
 288     private void validateLeafRefTargetNodeData(final NormalizedNode<?, ?> leaf, final LeafRefContext
 289             referencedByCtx, final ModificationType modificationType) {
 290         if (!validatedLeafRefCtx.add(referencedByCtx)) {
 291             LOG.trace("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}] -> SKIP: Already "
 292                     + "validated", modificationType, referencedByCtx.getNodeName(), leaf.getValue());
 293             return;
 294         }
 295
 296         LOG.trace("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}]", modificationType,
 297             referencedByCtx.getNodeName(), leaf.getValue());
 298         final Set<LeafRefContext> leafRefs = referencedByCtx.getAllReferencedByLeafRefCtxs().values().stream()
 299                 .filter(LeafRefContext::isReferencing).collect(Collectors.toSet());
 300         if (leafRefs.isEmpty()) {
 301             return;
 302         }
 303
 304         final Set<Object> leafRefTargetNodeValues = extractRootValues(referencedByCtx);
 305         leafRefs.forEach(leafRefContext -> {
 306             extractRootValues(leafRefContext).forEach(leafRefsValue -> {
 307                 if (leafRefTargetNodeValues.contains(leafRefsValue)) {
 308                     LOG.trace("Valid leafref value [{}] {}", leafRefsValue, SUCCESS);
 309                     return;
 310                 }
 311
 312                 LOG.debug("Invalid leafref value [{}] allowed values {} by validation of leafref TARGET node: {} path "
 313                         + "of invalid LEAFREF node: {} leafRef target path: {} {}", leafRefsValue,
 314                         leafRefTargetNodeValues, leaf.getNodeType(), leafRefContext.getCurrentNodePath(),
 315                         leafRefContext.getAbsoluteLeafRefTargetPath(), FAILED);
 316                 errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s by validation of leafref"
 317                         + " TARGET node: %s path of invalid LEAFREF node: %s leafRef target path: %s %s", leafRefsValue,
 318                         leafRefTargetNodeValues, leaf.getNodeType(), leafRefContext.getCurrentNodePath(),
 319                         leafRefContext.getAbsoluteLeafRefTargetPath(),
 320                         FAILED));
 321             });
 322         });
 323     }
 324
 325     private Set<Object> extractRootValues(final LeafRefContext context) {
 326         return computeValues(root, createPath(context.getLeafRefNodePath()), null);
 327     }
 328
 329     private void validateLeafRefNodeData(final NormalizedNode<?, ?> leaf, final LeafRefContext referencingCtx,
 330             final ModificationType modificationType, final YangInstanceIdentifier current) {
 331         final Set<Object> values = computeValues(root, createPath(referencingCtx.getAbsoluteLeafRefTargetPath()),
 332             current);
 333         if (values.contains(leaf.getValue())) {
 334             LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 335                 referencingCtx.getNodeName(), leaf.getValue(), SUCCESS);
 336             return;
 337         }
 338
 339         LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 340             referencingCtx.getNodeName(), leaf.getValue(), FAILED);
 341         LOG.debug("Invalid leafref value [{}] allowed values {} of LEAFREF node: {} leafRef target path: {}",
 342             leaf.getValue(), values, leaf.getNodeType(), referencingCtx.getAbsoluteLeafRefTargetPath());
 343         errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s of LEAFREF node: %s leafRef "
 344                 + "target path: %s", leaf.getValue(), values, leaf.getNodeType(),
 345                 referencingCtx.getAbsoluteLeafRefTargetPath()));
 346     }
 347
 348     private Set<Object> computeValues(final NormalizedNode<?, ?> node, final Deque<QNameWithPredicate> path,
 349             final YangInstanceIdentifier current) {
 350         final HashSet<Object> values = new HashSet<>();
 351         addValues(values, node, ImmutableList.of(), path, current);
 352         return values;
 353     }
 354
 355     private void addValues(final Set<Object> values, final NormalizedNode<?, ?> node,
 356             final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 357             final YangInstanceIdentifier current) {
 358         if (node instanceof ValueNode) {
 359             values.add(node.getValue());
 360             return;
 361         }
 362         if (node instanceof LeafSetNode<?>) {
 363             for (final NormalizedNode<?, ?> entry : ((LeafSetNode<?>) node).getValue()) {
 364                 values.add(entry.getValue());
 365             }
 366             return;
 367         }
 368
 369         final QNameWithPredicate next = path.peek();
 370         if (next == null) {
 371             return;
 372         }
 373
 374         final QName qname = next.getQName();
 375         final PathArgument pathArgument = new NodeIdentifier(qname);
 376         if (node instanceof DataContainerNode) {
 377             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 378             final Optional<DataContainerChild<?, ?>> child = dataContainerNode.getChild(pathArgument);
 379             if (child.isPresent()) {
 380                 addNextValues(values, child.get(), next.getQNamePredicates(), path, current);
 381             } else {
 382                 forEachChoice(dataContainerNode,
 383                     choice -> addValues(values, choice, next.getQNamePredicates(), path, current));
 384             }
 385         } else if (node instanceof MapNode) {
 386             Stream<MapEntryNode> entries = ((MapNode) node).getValue().stream();
 387             if (!nodePredicates.isEmpty() && current != null) {
 388                 entries = entries.filter(createMapEntryPredicate(nodePredicates, current));
 389             }
 390
 391             entries.forEach(mapEntryNode -> {
 392                 final Optional<DataContainerChild<?, ?>> child = mapEntryNode.getChild(pathArgument);
 393                 if (child.isPresent()) {
 394                     addNextValues(values, child.get(), next.getQNamePredicates(), path, current);
 395                 } else {
 396                     forEachChoice(mapEntryNode,
 397                         choice -> addValues(values, choice, next.getQNamePredicates(), path, current));
 398                 }
 399             });
 400         }
 401     }
 402
 403     private Predicate<MapEntryNode> createMapEntryPredicate(final List<QNamePredicate> nodePredicates,
 404             final YangInstanceIdentifier current) {
 405         final Map<QName, Set<?>> keyValues = new HashMap<>();
 406         for (QNamePredicate predicate : nodePredicates) {
 407             keyValues.put(predicate.getIdentifier(), getPathKeyExpressionValues(predicate.getPathKeyExpression(),
 408                 current));
 409         }
 410
 411         return mapEntry -> {
 412             for (final Entry<QName, Object> entryKeyValue : mapEntry.getIdentifier().getKeyValues().entrySet()) {
 413                 final Set<?> allowedValues = keyValues.get(entryKeyValue.getKey());
 414                 if (allowedValues != null && !allowedValues.contains(entryKeyValue.getValue())) {
 415                     return false;
 416                 }
 417             }
 418             return true;
 419         };
 420     }
 421
 422     private void addNextValues(final Set<Object> values, final NormalizedNode<?, ?> node,
 423             final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 424             final YangInstanceIdentifier current) {
 425         final QNameWithPredicate element = path.pop();
 426         try {
 427             addValues(values, node, nodePredicates, path, current);
 428         } finally {
 429             path.push(element);
 430         }
 431     }
 432
 433     private static void forEachChoice(final DataContainerNode<?> node, final Consumer<ChoiceNode> consumer) {
 434         for (final DataContainerChild<?, ?> child : node.getValue()) {
 435             if (child instanceof ChoiceNode) {
 436                 consumer.accept((ChoiceNode) child);
 437             }
 438         }
 439     }
 440
 441     private Set<?> getPathKeyExpressionValues(final LeafRefPath predicatePathKeyExpression,
 442             final YangInstanceIdentifier current) {
 443         return findParentNode(Optional.of(root), current).map(parent -> {
 444             final Deque<QNameWithPredicate> path = createPath(predicatePathKeyExpression);
 445             path.pollFirst();
 446             return computeValues(parent, path, null);
 447         }).orElse(ImmutableSet.of());
 448     }
 449
 450     private static Optional<NormalizedNode<?, ?>> findParentNode(
 451             final Optional<NormalizedNode<?, ?>> root, final YangInstanceIdentifier path) {
 452         Optional<NormalizedNode<?, ?>> currentNode = root;
 453         final Iterator<PathArgument> pathIterator = path.getPathArguments().iterator();
 454         while (pathIterator.hasNext()) {
 455             final PathArgument childPathArgument = pathIterator.next();
 456             if (pathIterator.hasNext() && currentNode.isPresent()) {
 457                 currentNode = NormalizedNodes.getDirectChild(currentNode.get(), childPathArgument);
 458             } else {
 459                 return currentNode;
 460             }
 461         }
 462         return Optional.empty();
 463     }
 464
 465     private static Deque<QNameWithPredicate> createPath(final LeafRefPath path) {
 466         final Deque<QNameWithPredicate> ret = new ArrayDeque<>();
 467         path.getPathTowardsRoot().forEach(ret::push);
 468         return ret;
 469     }
 470 }