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