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
 165         if (node instanceof LeafNode) {
 166             final LeafNode<?> leaf = (LeafNode<?>) node;
 167
 168             if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 169                 validateLeafRefTargetNodeData(leaf, referencedByCtx, modificationType);
 170             }
 171             if (referencingCtx != null && referencingCtx.isReferencing()) {
 172                 validateLeafRefNodeData(leaf, referencingCtx, modificationType, current);
 173             }
 174
 175             return;
 176         }
 177
 178         if (node instanceof LeafSetNode) {
 179             if (referencedByCtx == null && referencingCtx == null) {
 180                 return;
 181             }
 182
 183             final LeafSetNode<?> leafSet = (LeafSetNode<?>) node;
 184             for (final NormalizedNode<?, ?> leafSetEntry : leafSet.getValue()) {
 185                 if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 186                     validateLeafRefTargetNodeData(leafSetEntry, referencedByCtx, modificationType);
 187                 }
 188                 if (referencingCtx != null && referencingCtx.isReferencing()) {
 189                     validateLeafRefNodeData(leafSetEntry, referencingCtx, modificationType, current);
 190                 }
 191             }
 192
 193             return;
 194         }
 195
 196         if (node instanceof ChoiceNode) {
 197             final ChoiceNode choice = (ChoiceNode) node;
 198             for (final DataContainerChild<? extends PathArgument, ?> dataContainerChild : choice.getValue()) {
 199                 final QName qname = dataContainerChild.getNodeType();
 200
 201                 final LeafRefContext childReferencedByCtx;
 202                 if (referencedByCtx != null) {
 203                     childReferencedByCtx = findReferencedByCtxUnderChoice(referencedByCtx, qname);
 204                 } else {
 205                     childReferencedByCtx = null;
 206                 }
 207
 208                 final LeafRefContext childReferencingCtx;
 209                 if (referencingCtx != null) {
 210                     childReferencingCtx = findReferencingCtxUnderChoice(referencingCtx, qname);
 211                 } else {
 212                     childReferencingCtx = null;
 213                 }
 214
 215                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 216                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 217                             .node(dataContainerChild.getIdentifier());
 218                     validateNodeData(dataContainerChild, childReferencedByCtx,
 219                             childReferencingCtx, modificationType, childYangInstanceIdentifier);
 220                 }
 221             }
 222         } else if (node instanceof DataContainerNode) {
 223             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 224
 225             for (final DataContainerChild<? extends PathArgument, ?> child : dataContainerNode.getValue()) {
 226                 if (child instanceof AugmentationNode) {
 227                     validateNodeData(child, referencedByCtx, referencingCtx, modificationType, current
 228                         .node(child.getIdentifier()));
 229                     return;
 230                 }
 231
 232                 final QName qname = child.getNodeType();
 233                 final LeafRefContext childReferencedByCtx;
 234                 if (referencedByCtx != null) {
 235                     childReferencedByCtx = referencedByCtx.getReferencedChildByName(qname);
 236                 } else {
 237                     childReferencedByCtx = null;
 238                 }
 239
 240                 final LeafRefContext childReferencingCtx;
 241                 if (referencingCtx != null) {
 242                     childReferencingCtx = referencingCtx.getReferencingChildByName(qname);
 243                 } else {
 244                     childReferencingCtx = null;
 245                 }
 246
 247                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 248                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 249                             .node(child.getIdentifier());
 250                     validateNodeData(child, childReferencedByCtx,
 251                             childReferencingCtx, modificationType, childYangInstanceIdentifier);
 252                 }
 253             }
 254         } else if (node instanceof MapNode) {
 255             final MapNode map = (MapNode) node;
 256
 257             for (final MapEntryNode mapEntry : map.getValue()) {
 258                 final YangInstanceIdentifier mapEntryYangInstanceIdentifier = current.node(mapEntry.getIdentifier());
 259                 for (final DataContainerChild<? extends PathArgument, ?> mapEntryNode : mapEntry.getValue()) {
 260                     if (mapEntryNode instanceof AugmentationNode) {
 261                         validateNodeData(mapEntryNode, referencedByCtx, referencingCtx, modificationType, current
 262                             .node(mapEntryNode.getIdentifier()));
 263                         return;
 264                     }
 265
 266                     final QName qname = mapEntryNode.getNodeType();
 267                     final LeafRefContext childReferencedByCtx;
 268                     if (referencedByCtx != null) {
 269                         childReferencedByCtx = referencedByCtx.getReferencedChildByName(qname);
 270                     } else {
 271                         childReferencedByCtx = null;
 272                     }
 273
 274                     final LeafRefContext childReferencingCtx;
 275                     if (referencingCtx != null) {
 276                         childReferencingCtx = referencingCtx.getReferencingChildByName(qname);
 277                     } else {
 278                         childReferencingCtx = null;
 279                     }
 280
 281                     if (childReferencedByCtx != null || childReferencingCtx != null) {
 282                         validateNodeData(mapEntryNode, childReferencedByCtx, childReferencingCtx, modificationType,
 283                                 mapEntryYangInstanceIdentifier.node(mapEntryNode.getIdentifier()));
 284                     }
 285                 }
 286             }
 287         }
 288         // FIXME: check UnkeyedListNode case
 289     }
 290
 291     private static LeafRefContext findReferencingCtxUnderChoice(
 292             final LeafRefContext referencingCtx, final QName qname) {
 293
 294         for (final LeafRefContext child : referencingCtx.getReferencingChilds().values()) {
 295             final LeafRefContext referencingChildByName = child.getReferencingChildByName(qname);
 296             if (referencingChildByName != null) {
 297                 return referencingChildByName;
 298             }
 299         }
 300
 301         return null;
 302     }
 303
 304     private static LeafRefContext findReferencedByCtxUnderChoice(
 305             final LeafRefContext referencedByCtx, final QName qname) {
 306
 307         for (final LeafRefContext child : referencedByCtx.getReferencedByChilds().values()) {
 308             final LeafRefContext referencedByChildByName = child.getReferencedChildByName(qname);
 309             if (referencedByChildByName != null) {
 310                 return referencedByChildByName;
 311             }
 312         }
 313
 314         return null;
 315     }
 316
 317     private void validateLeafRefTargetNodeData(final NormalizedNode<?, ?> leaf, final LeafRefContext
 318             referencedByCtx, final ModificationType modificationType) {
 319         if (!validatedLeafRefCtx.add(referencedByCtx)) {
 320             LOG.trace("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}] -> SKIP: Already "
 321                     + "validated", modificationType, referencedByCtx.getNodeName(), leaf.getValue());
 322             return;
 323         }
 324
 325         LOG.trace("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}]", modificationType,
 326             referencedByCtx.getNodeName(), leaf.getValue());
 327         final Set<LeafRefContext> leafRefs = referencedByCtx.getAllReferencedByLeafRefCtxs().values().stream()
 328                 .filter(LeafRefContext::isReferencing).collect(Collectors.toSet());
 329         if (leafRefs.isEmpty()) {
 330             return;
 331         }
 332
 333         final Set<Object> leafRefTargetNodeValues = extractRootValues(referencedByCtx);
 334         leafRefs.forEach(leafRefContext -> {
 335             extractRootValues(leafRefContext).forEach(leafRefsValue -> {
 336                 if (leafRefTargetNodeValues.contains(leafRefsValue)) {
 337                     LOG.trace("Valid leafref value [{}] {}", leafRefsValue, SUCCESS);
 338                     return;
 339                 }
 340
 341                 LOG.debug("Invalid leafref value [{}] allowed values {} by validation of leafref TARGET node: {} path "
 342                         + "of invalid LEAFREF node: {} leafRef target path: {} {}", leafRefsValue,
 343                         leafRefTargetNodeValues, leaf.getNodeType(), leafRefContext.getCurrentNodePath(),
 344                         leafRefContext.getAbsoluteLeafRefTargetPath(), FAILED);
 345                 errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s by validation of leafref"
 346                         + " TARGET node: %s path of invalid LEAFREF node: %s leafRef target path: %s %s", leafRefsValue,
 347                         leafRefTargetNodeValues, leaf.getNodeType(), leafRefContext.getCurrentNodePath(),
 348                         leafRefContext.getAbsoluteLeafRefTargetPath(),
 349                         FAILED));
 350             });
 351         });
 352     }
 353
 354     private Set<Object> extractRootValues(final LeafRefContext context) {
 355         return computeValues(root, createPath(context.getLeafRefNodePath()), null);
 356     }
 357
 358     private void validateLeafRefNodeData(final NormalizedNode<?, ?> leaf, final LeafRefContext referencingCtx,
 359             final ModificationType modificationType, final YangInstanceIdentifier current) {
 360         final Set<Object> values = computeValues(root, createPath(referencingCtx.getAbsoluteLeafRefTargetPath()),
 361             current);
 362         if (values.contains(leaf.getValue())) {
 363             LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 364                 referencingCtx.getNodeName(), leaf.getValue(), SUCCESS);
 365             return;
 366         }
 367
 368         LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 369             referencingCtx.getNodeName(), leaf.getValue(), FAILED);
 370         LOG.debug("Invalid leafref value [{}] allowed values {} of LEAFREF node: {} leafRef target path: {}",
 371             leaf.getValue(), values, leaf.getNodeType(), referencingCtx.getAbsoluteLeafRefTargetPath());
 372         errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s of LEAFREF node: %s leafRef "
 373                 + "target path: %s", leaf.getValue(), values, leaf.getNodeType(),
 374                 referencingCtx.getAbsoluteLeafRefTargetPath()));
 375     }
 376
 377     private Set<Object> computeValues(final NormalizedNode<?, ?> node, final Deque<QNameWithPredicate> path,
 378             final YangInstanceIdentifier current) {
 379         final HashSet<Object> values = new HashSet<>();
 380         addValues(values, node, ImmutableList.of(), path, current);
 381         return values;
 382     }
 383
 384     private void addValues(final Set<Object> values, final NormalizedNode<?, ?> node,
 385             final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 386             final YangInstanceIdentifier current) {
 387         if (node instanceof ValueNode) {
 388             values.add(node.getValue());
 389             return;
 390         }
 391         if (node instanceof LeafSetNode<?>) {
 392             for (final NormalizedNode<?, ?> entry : ((LeafSetNode<?>) node).getValue()) {
 393                 values.add(entry.getValue());
 394             }
 395             return;
 396         }
 397
 398         final QNameWithPredicate next = path.peek();
 399         if (next == null) {
 400             return;
 401         }
 402
 403         final QName qname = next.getQName();
 404         final PathArgument pathArgument = new NodeIdentifier(qname);
 405         if (node instanceof DataContainerNode) {
 406             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 407             final Optional<DataContainerChild<?, ?>> child = dataContainerNode.getChild(pathArgument);
 408             if (child.isPresent()) {
 409                 addNextValues(values, child.get(), next.getQNamePredicates(), path, current);
 410             } else {
 411                 forEachChoice(dataContainerNode,
 412                     choice -> addValues(values, choice, next.getQNamePredicates(), path, current));
 413             }
 414         } else if (node instanceof MapNode) {
 415             Stream<MapEntryNode> entries = ((MapNode) node).getValue().stream();
 416             if (!nodePredicates.isEmpty() && current != null) {
 417                 entries = entries.filter(createMapEntryPredicate(nodePredicates, current));
 418             }
 419
 420             entries.forEach(mapEntryNode -> {
 421                 final Optional<DataContainerChild<?, ?>> child = mapEntryNode.getChild(pathArgument);
 422                 if (child.isPresent()) {
 423                     addNextValues(values, child.get(), next.getQNamePredicates(), path, current);
 424                 } else {
 425                     forEachChoice(mapEntryNode,
 426                         choice -> addValues(values, choice, next.getQNamePredicates(), path, current));
 427                 }
 428             });
 429         }
 430     }
 431
 432     private Predicate<MapEntryNode> createMapEntryPredicate(final List<QNamePredicate> nodePredicates,
 433             final YangInstanceIdentifier current) {
 434         final Map<QName, Set<?>> keyValues = new HashMap<>();
 435         for (QNamePredicate predicate : nodePredicates) {
 436             keyValues.put(predicate.getIdentifier(), getPathKeyExpressionValues(predicate.getPathKeyExpression(),
 437                 current));
 438         }
 439
 440         return mapEntry -> {
 441             for (final Entry<QName, Object> entryKeyValue : mapEntry.getIdentifier().getKeyValues().entrySet()) {
 442                 final Set<?> allowedValues = keyValues.get(entryKeyValue.getKey());
 443                 if (allowedValues != null && !allowedValues.contains(entryKeyValue.getValue())) {
 444                     return false;
 445                 }
 446             }
 447             return true;
 448         };
 449     }
 450
 451     private void addNextValues(final Set<Object> values, final NormalizedNode<?, ?> node,
 452             final List<QNamePredicate> nodePredicates, final Deque<QNameWithPredicate> path,
 453             final YangInstanceIdentifier current) {
 454         final QNameWithPredicate element = path.pop();
 455         try {
 456             addValues(values, node, nodePredicates, path, current);
 457         } finally {
 458             path.push(element);
 459         }
 460     }
 461
 462     private static void forEachChoice(final DataContainerNode<?> node, final Consumer<ChoiceNode> consumer) {
 463         for (final DataContainerChild<? extends PathArgument, ?> child : node.getValue()) {
 464             if (child instanceof ChoiceNode) {
 465                 consumer.accept((ChoiceNode) child);
 466             }
 467         }
 468     }
 469
 470     private Set<?> getPathKeyExpressionValues(final LeafRefPath predicatePathKeyExpression,
 471             final YangInstanceIdentifier current) {
 472         return findParentNode(Optional.of(root), current).map(parent -> {
 473             final Deque<QNameWithPredicate> path = createPath(predicatePathKeyExpression);
 474             path.pollFirst();
 475             return computeValues(parent, path, null);
 476         }).orElse(ImmutableSet.of());
 477     }
 478
 479     private static Optional<NormalizedNode<?, ?>> findParentNode(
 480             final Optional<NormalizedNode<?, ?>> root, final YangInstanceIdentifier path) {
 481         Optional<NormalizedNode<?, ?>> currentNode = root;
 482         final Iterator<PathArgument> pathIterator = path.getPathArguments().iterator();
 483         while (pathIterator.hasNext()) {
 484             final PathArgument childPathArgument = pathIterator.next();
 485             if (pathIterator.hasNext() && currentNode.isPresent()) {
 486                 currentNode = NormalizedNodes.getDirectChild(currentNode.get(), childPathArgument);
 487             } else {
 488                 return currentNode;
 489             }
 490         }
 491         return Optional.empty();
 492     }
 493
 494     private static Deque<QNameWithPredicate> createPath(final LeafRefPath path) {
 495         final Deque<QNameWithPredicate> ret = new ArrayDeque<>();
 496         path.getPathTowardsRoot().forEach(ret::push);
 497         return ret;
 498     }
 499 }