yang/yang-data-impl/src/main/java/org/opendaylight/yangtools/yang/data/impl/leafref/LeafRefValidatation.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.Iterables;
  11 import java.util.ArrayList;
  12 import java.util.Collection;
  13 import java.util.HashMap;
  14 import java.util.HashSet;
  15 import java.util.Iterator;
  16 import java.util.List;
  17 import java.util.Map;
  18 import java.util.Map.Entry;
  19 import java.util.Optional;
  20 import java.util.Set;
  21 import org.opendaylight.yangtools.yang.common.QName;
  22 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  23 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
  24 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  25 import org.opendaylight.yangtools.yang.data.api.schema.AugmentationNode;
  26 import org.opendaylight.yangtools.yang.data.api.schema.ChoiceNode;
  27 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild;
  28 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode;
  29 import org.opendaylight.yangtools.yang.data.api.schema.LeafNode;
  30 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetNode;
  31 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  32 import org.opendaylight.yangtools.yang.data.api.schema.MapNode;
  33 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  34 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
  35 import org.opendaylight.yangtools.yang.data.api.schema.UnkeyedListEntryNode;
  36 import org.opendaylight.yangtools.yang.data.api.schema.ValueNode;
  37 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidate;
  38 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidateNode;
  39 import org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType;
  40 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  41 import org.slf4j.Logger;
  42 import org.slf4j.LoggerFactory;
  43
  44 public final class LeafRefValidatation {
  45
  46     private static final Logger LOG = LoggerFactory.getLogger(LeafRefValidatation.class);
  47     private static final String FAILED = " -> FAILED";
  48     private static final String SUCCESS = " -> OK";
  49
  50     private final Set<LeafRefContext> validatedLeafRefCtx = new HashSet<>();
  51     private final List<String> errorsMessages = new ArrayList<>();
  52     private final DataTreeCandidate tree;
  53
  54     private LeafRefValidatation(final DataTreeCandidate tree) {
  55         this.tree = tree;
  56     }
  57
  58     public static void validate(final DataTreeCandidate tree, final LeafRefContext rootLeafRefCtx)
  59             throws LeafRefDataValidationFailedException {
  60         new LeafRefValidatation(tree).validate0(rootLeafRefCtx);
  61     }
  62
  63     private void validate0(final LeafRefContext rootLeafRefCtx) throws LeafRefDataValidationFailedException {
  64         for (final DataTreeCandidateNode dataTreeCandidateNode : tree.getRootNode().getChildNodes()) {
  65             if (dataTreeCandidateNode.getModificationType() != ModificationType.UNMODIFIED) {
  66                 final PathArgument identifier = dataTreeCandidateNode.getIdentifier();
  67                 final QName childQName = identifier.getNodeType();
  68
  69                 final LeafRefContext referencedByCtx = rootLeafRefCtx.getReferencedChildByName(childQName);
  70                 final LeafRefContext referencingCtx = rootLeafRefCtx.getReferencingChildByName(childQName);
  71                 if (referencedByCtx != null || referencingCtx != null) {
  72                     final YangInstanceIdentifier yangInstanceIdentifier = YangInstanceIdentifier
  73                             .create(dataTreeCandidateNode.getIdentifier());
  74                     validateNode(dataTreeCandidateNode, referencedByCtx, referencingCtx, yangInstanceIdentifier);
  75                 }
  76             }
  77         }
  78
  79         if (!errorsMessages.isEmpty()) {
  80             final StringBuilder message = new StringBuilder();
  81             int errCount = 0;
  82             for (final String errorMessage : errorsMessages) {
  83                 message.append(errorMessage);
  84                 errCount++;
  85             }
  86             throw new LeafRefDataValidationFailedException(message.toString(), errCount);
  87         }
  88     }
  89
  90     private void validateNode(final DataTreeCandidateNode node, final LeafRefContext referencedByCtx,
  91         final LeafRefContext referencingCtx, final YangInstanceIdentifier current) {
  92
  93         if (node.getModificationType() == ModificationType.WRITE && node.getDataAfter().isPresent()) {
  94             final Optional<NormalizedNode<?, ?>> dataAfter = node.getDataAfter();
  95             final NormalizedNode<?, ?> normalizedNode = dataAfter.get();
  96             validateNodeData(normalizedNode, referencedByCtx, referencingCtx,
  97                     node.getModificationType(), current);
  98             return;
  99         }
 100
 101         if (node.getModificationType() == ModificationType.DELETE && referencedByCtx != null) {
 102             final Optional<NormalizedNode<?, ?>> dataBefor = node.getDataBefore();
 103             final NormalizedNode<?, ?> normalizedNode = dataBefor.get();
 104             validateNodeData(normalizedNode, referencedByCtx, null,
 105                     node.getModificationType(), current);
 106             return;
 107         }
 108
 109         final Collection<DataTreeCandidateNode> childNodes = node.getChildNodes();
 110         for (final DataTreeCandidateNode childNode : childNodes) {
 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                     final YangInstanceIdentifier childYangInstanceIdentifier = current.node(childNode.getIdentifier());
 117                     validateNode(childNode, childReferencedByCtx,childReferencingCtx, childYangInstanceIdentifier);
 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().get();
 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().get();
 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
 163         if (node instanceof LeafNode) {
 164             final LeafNode<?> leaf = (LeafNode<?>) node;
 165
 166             if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 167                 validateLeafRefTargetNodeData(leaf, referencedByCtx, modificationType);
 168             }
 169             if (referencingCtx != null && referencingCtx.isReferencing()) {
 170                 validateLeafRefNodeData(leaf, referencingCtx, modificationType, current);
 171             }
 172
 173             return;
 174         }
 175
 176         if (node instanceof LeafSetNode) {
 177             if (referencedByCtx == null && referencingCtx == null) {
 178                 return;
 179             }
 180
 181             final LeafSetNode<?> leafSet = (LeafSetNode<?>) node;
 182             for (final NormalizedNode<?, ?> leafSetEntry : leafSet.getValue()) {
 183                 if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 184                     validateLeafRefTargetNodeData(leafSetEntry, referencedByCtx, modificationType);
 185                 }
 186                 if (referencingCtx != null && referencingCtx.isReferencing()) {
 187                     validateLeafRefNodeData(leafSetEntry, referencingCtx, modificationType, current);
 188                 }
 189             }
 190
 191             return;
 192         }
 193
 194         if (node instanceof ChoiceNode) {
 195             final ChoiceNode choice = (ChoiceNode) node;
 196             for (final DataContainerChild<? extends PathArgument, ?> dataContainerChild : choice.getValue()) {
 197                 final QName qname = dataContainerChild.getNodeType();
 198
 199                 final LeafRefContext childReferencedByCtx;
 200                 if (referencedByCtx != null) {
 201                     childReferencedByCtx = findReferencedByCtxUnderChoice(referencedByCtx, qname);
 202                 } else {
 203                     childReferencedByCtx = null;
 204                 }
 205
 206                 final LeafRefContext childReferencingCtx;
 207                 if (referencingCtx != null) {
 208                     childReferencingCtx = findReferencingCtxUnderChoice(referencingCtx, qname);
 209                 } else {
 210                     childReferencingCtx = null;
 211                 }
 212
 213                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 214                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 215                             .node(dataContainerChild.getIdentifier());
 216                     validateNodeData(dataContainerChild, childReferencedByCtx,
 217                             childReferencingCtx, modificationType, childYangInstanceIdentifier);
 218                 }
 219             }
 220         } else if (node instanceof DataContainerNode) {
 221             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 222
 223             for (final DataContainerChild<? extends PathArgument, ?> child : dataContainerNode.getValue()) {
 224                 if (child instanceof AugmentationNode) {
 225                     validateNodeData(child, referencedByCtx, referencingCtx, modificationType, current
 226                         .node(child.getIdentifier()));
 227                     return;
 228                 }
 229
 230                 final QName qname = child.getNodeType();
 231                 final LeafRefContext childReferencedByCtx;
 232                 if (referencedByCtx != null) {
 233                     childReferencedByCtx = referencedByCtx.getReferencedChildByName(qname);
 234                 } else {
 235                     childReferencedByCtx = null;
 236                 }
 237
 238                 final LeafRefContext childReferencingCtx;
 239                 if (referencingCtx != null) {
 240                     childReferencingCtx = referencingCtx.getReferencingChildByName(qname);
 241                 } else {
 242                     childReferencingCtx = null;
 243                 }
 244
 245                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 246                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 247                             .node(child.getIdentifier());
 248                     validateNodeData(child, childReferencedByCtx,
 249                             childReferencingCtx, modificationType, childYangInstanceIdentifier);
 250                 }
 251             }
 252         } else if (node instanceof MapNode) {
 253             final MapNode map = (MapNode) node;
 254
 255             for (final MapEntryNode mapEntry : map.getValue()) {
 256                 final YangInstanceIdentifier mapEntryYangInstanceIdentifier = current.node(mapEntry.getIdentifier());
 257                 for (final DataContainerChild<? extends PathArgument, ?> mapEntryNode : mapEntry.getValue()) {
 258                     if (mapEntryNode instanceof AugmentationNode) {
 259                         validateNodeData(mapEntryNode, referencedByCtx, referencingCtx, modificationType, current
 260                             .node(mapEntryNode.getIdentifier()));
 261                         return;
 262                     }
 263
 264                     final QName qname = mapEntryNode.getNodeType();
 265                     final LeafRefContext childReferencedByCtx;
 266                     if (referencedByCtx != null) {
 267                         childReferencedByCtx = referencedByCtx.getReferencedChildByName(qname);
 268                     } else {
 269                         childReferencedByCtx = null;
 270                     }
 271
 272                     final LeafRefContext childReferencingCtx;
 273                     if (referencingCtx != null) {
 274                         childReferencingCtx = referencingCtx.getReferencingChildByName(qname);
 275                     } else {
 276                         childReferencingCtx = null;
 277                     }
 278
 279                     if (childReferencedByCtx != null || childReferencingCtx != null) {
 280                         validateNodeData(mapEntryNode, childReferencedByCtx, childReferencingCtx, modificationType,
 281                                 mapEntryYangInstanceIdentifier.node(mapEntryNode.getIdentifier()));
 282                     }
 283                 }
 284             }
 285         }
 286         // FIXME: check UnkeyedListNode case
 287     }
 288
 289     private static LeafRefContext findReferencingCtxUnderChoice(
 290             final LeafRefContext referencingCtx, final QName qname) {
 291
 292         for (final LeafRefContext child : referencingCtx.getReferencingChilds().values()) {
 293             final LeafRefContext referencingChildByName = child.getReferencingChildByName(qname);
 294             if (referencingChildByName != null) {
 295                 return referencingChildByName;
 296             }
 297         }
 298
 299         return null;
 300     }
 301
 302     private static LeafRefContext findReferencedByCtxUnderChoice(
 303             final LeafRefContext referencedByCtx, final QName qname) {
 304
 305         for (final LeafRefContext child : referencedByCtx.getReferencedByChilds().values()) {
 306             final LeafRefContext referencedByChildByName = child.getReferencedChildByName(qname);
 307             if (referencedByChildByName != null) {
 308                 return referencedByChildByName;
 309             }
 310         }
 311
 312         return null;
 313     }
 314
 315     private void validateLeafRefTargetNodeData(final NormalizedNode<?, ?> leaf, final LeafRefContext
 316             referencedByCtx, final ModificationType modificationType) {
 317         final Map<LeafRefContext, Set<?>> leafRefsValues = new HashMap<>();
 318         if (validatedLeafRefCtx.contains(referencedByCtx)) {
 319             leafRefTargetNodeDataLog(leaf, referencedByCtx, modificationType, leafRefsValues, null);
 320             return;
 321         }
 322
 323         final Map<QName, LeafRefContext> allReferencedByLeafRefCtxs = referencedByCtx.getAllReferencedByLeafRefCtxs();
 324         for (final LeafRefContext leafRefContext : allReferencedByLeafRefCtxs.values()) {
 325             if (leafRefContext.isReferencing()) {
 326                 final Set<Object> values = new HashSet<>();
 327
 328                 final SchemaPath leafRefNodeSchemaPath = leafRefContext.getCurrentNodePath();
 329                 final LeafRefPath leafRefNodePath = LeafRefUtils.schemaPathToLeafRefPath(leafRefNodeSchemaPath,
 330                                 leafRefContext.getLeafRefContextModule());
 331                 final Iterable<QNameWithPredicate> pathFromRoot = leafRefNodePath.getPathFromRoot();
 332                 addValues(values, tree.getRootNode().getDataAfter(), pathFromRoot, null, QNameWithPredicate.ROOT);
 333                 leafRefsValues.put(leafRefContext, values);
 334             }
 335         }
 336
 337         if (!leafRefsValues.isEmpty()) {
 338             final Set<Object> leafRefTargetNodeValues = new HashSet<>();
 339             final SchemaPath nodeSchemaPath = referencedByCtx.getCurrentNodePath();
 340             final LeafRefPath nodePath = LeafRefUtils.schemaPathToLeafRefPath(nodeSchemaPath, referencedByCtx
 341                     .getLeafRefContextModule());
 342             addValues(leafRefTargetNodeValues, tree.getRootNode().getDataAfter(), nodePath.getPathFromRoot(), null,
 343                     QNameWithPredicate.ROOT);
 344             leafRefTargetNodeDataLog(leaf, referencedByCtx, modificationType, leafRefsValues,
 345                     leafRefTargetNodeValues);
 346         } else {
 347             leafRefTargetNodeDataLog(leaf, referencedByCtx, modificationType, null, null);
 348         }
 349         validatedLeafRefCtx.add(referencedByCtx);
 350     }
 351
 352     private void leafRefTargetNodeDataLog(final NormalizedNode<?, ?> leaf, final LeafRefContext referencedByCtx,
 353             final ModificationType modificationType, final Map<LeafRefContext, Set<?>> leafRefsValues,
 354             final Set<Object> leafRefTargetNodeValues) {
 355
 356         if (leafRefsValues != null && !leafRefsValues.isEmpty()) {
 357             final Set<Entry<LeafRefContext, Set<?>>> entrySet = leafRefsValues.entrySet();
 358             LOG.debug("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}]",
 359                     modificationType, referencedByCtx.getNodeName(), leaf.getValue());
 360             for (final Entry<LeafRefContext, Set<?>> entry : entrySet) {
 361                 final LeafRefContext leafRefContext = entry.getKey();
 362                 final Set<?> leafRefValuesSet = entry.getValue();
 363                 for (final Object leafRefsValue : leafRefValuesSet) {
 364                     if (leafRefTargetNodeValues != null && !leafRefTargetNodeValues.contains(leafRefsValue)) {
 365                         LOG.debug("Invalid leafref value [{}] allowed values {} by validation of leafref TARGET node: "
 366                                 + "{} path of invalid LEAFREF node: {} leafRef target path: {} {}", leafRefsValue,
 367                                 leafRefTargetNodeValues, leaf.getNodeType(), leafRefContext.getCurrentNodePath(),
 368                                 leafRefContext.getAbsoluteLeafRefTargetPath(), FAILED);
 369                         errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s by validation "
 370                                         + "of leafref TARGET node: %s path of invalid LEAFREF node: %s leafRef target "
 371                                         + "path: %s %s", leafRefsValue, leafRefTargetNodeValues, leaf.getNodeType(),
 372                                 leafRefContext.getCurrentNodePath(), leafRefContext.getAbsoluteLeafRefTargetPath(),
 373                                 FAILED));
 374                     } else {
 375                         LOG.debug("Valid leafref value [{}] {}", leafRefsValue, SUCCESS);
 376                     }
 377                 }
 378             }
 379         } else if (leafRefsValues != null) {
 380             LOG.debug("Operation [{}] validate data of leafref TARGET node: name[{}] = value[{}] "
 381                     + "-> SKIP: Already validated", modificationType, referencedByCtx.getNodeName(), leaf.getValue());
 382         }
 383     }
 384
 385     private void validateLeafRefNodeData(final NormalizedNode<?, ?> leaf, final LeafRefContext referencingCtx,
 386             final ModificationType modificationType, final YangInstanceIdentifier current) {
 387         final HashSet<Object> values = new HashSet<>();
 388         final LeafRefPath targetPath = referencingCtx.getAbsoluteLeafRefTargetPath();
 389         final Iterable<QNameWithPredicate> pathFromRoot = targetPath.getPathFromRoot();
 390
 391         addValues(values, tree.getRootNode().getDataAfter(), pathFromRoot, current, QNameWithPredicate.ROOT);
 392
 393         if (!values.contains(leaf.getValue())) {
 394             LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}",
 395                     modificationType, referencingCtx.getNodeName(), leaf.getValue(), FAILED);
 396             LOG.debug("Invalid leafref value [{}] allowed values {} of LEAFREF node: {} leafRef target path: {}",
 397                     leaf.getValue(), values, leaf.getNodeType(), referencingCtx.getAbsoluteLeafRefTargetPath());
 398             errorsMessages.add(String.format("Invalid leafref value [%s] allowed values %s of LEAFREF node: %s "
 399                             + "leafRef target path: %s", leaf.getValue(), values, leaf.getNodeType(), referencingCtx
 400                     .getAbsoluteLeafRefTargetPath()));
 401         } else {
 402             LOG.debug("Operation [{}] validate data of LEAFREF node: name[{}] = value[{}] {}", modificationType,
 403                     referencingCtx.getNodeName(), leaf.getValue(), SUCCESS);
 404         }
 405     }
 406
 407     private void addValues(final Set<Object> values, final Optional<? extends NormalizedNode<?, ?>> optDataNode,
 408             final Iterable<QNameWithPredicate> path, final YangInstanceIdentifier current,
 409             final QNameWithPredicate previousQName) {
 410
 411         if (!optDataNode.isPresent()) {
 412             return;
 413         }
 414         final NormalizedNode<?, ?> node = optDataNode.get();
 415         if (node instanceof ValueNode) {
 416             values.add(node.getValue());
 417             return;
 418         }
 419         if (node instanceof LeafSetNode<?>) {
 420             for (final NormalizedNode<?, ?> entry : ((LeafSetNode<?>) node).getValue()) {
 421                 values.add(entry.getValue());
 422             }
 423             return;
 424         }
 425
 426         final Iterator<QNameWithPredicate> iterator = path.iterator();
 427         if (!iterator.hasNext()) {
 428             return;
 429         }
 430         final QNameWithPredicate qnameWithPredicate = iterator.next();
 431         final QName qName = qnameWithPredicate.getQName();
 432         final PathArgument pathArgument = new NodeIdentifier(qName);
 433
 434         if (node instanceof DataContainerNode) {
 435             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 436             final Optional<DataContainerChild<? extends PathArgument, ?>> child = dataContainerNode
 437                     .getChild(pathArgument);
 438
 439             if (child.isPresent()) {
 440                 addValues(values, child, nextLevel(path), current, qnameWithPredicate);
 441             } else {
 442                 for (final ChoiceNode choiceNode : getChoiceNodes(dataContainerNode)) {
 443                     addValues(values, Optional.of(choiceNode), path, current,
 444                             qnameWithPredicate);
 445                 }
 446             }
 447
 448         } else if (node instanceof MapNode) {
 449             final MapNode map = (MapNode) node;
 450             final List<QNamePredicate> qNamePredicates = previousQName.getQNamePredicates();
 451             if (qNamePredicates.isEmpty() || current == null) {
 452                 final Iterable<MapEntryNode> value = map.getValue();
 453                 for (final MapEntryNode mapEntryNode : value) {
 454                     final Optional<DataContainerChild<? extends PathArgument, ?>> child = mapEntryNode
 455                             .getChild(pathArgument);
 456
 457                     if (child.isPresent()) {
 458                         addValues(values, child, nextLevel(path), current, qnameWithPredicate);
 459                     } else {
 460                         for (final ChoiceNode choiceNode : getChoiceNodes(mapEntryNode)) {
 461                             addValues(values, Optional.of(choiceNode), path, current, qnameWithPredicate);
 462                         }
 463                     }
 464                 }
 465             } else {
 466                 final Map<QName, Set<?>> keyValues = new HashMap<>();
 467
 468                 final Iterator<QNamePredicate> predicates = qNamePredicates.iterator();
 469                 while (predicates.hasNext()) {
 470                     final QNamePredicate predicate = predicates.next();
 471                     final QName identifier = predicate.getIdentifier();
 472                     final LeafRefPath predicatePathKeyExpression = predicate
 473                             .getPathKeyExpression();
 474
 475                     final Set<?> pathKeyExprValues = getPathKeyExpressionValues(
 476                             predicatePathKeyExpression, current);
 477
 478                     keyValues.put(identifier, pathKeyExprValues);
 479                 }
 480
 481                 for (final MapEntryNode mapEntryNode : map.getValue()) {
 482                     if (isMatchingPredicate(mapEntryNode, keyValues)) {
 483                         final Optional<DataContainerChild<? extends PathArgument, ?>> child = mapEntryNode
 484                                 .getChild(pathArgument);
 485
 486                         if (child.isPresent()) {
 487                             addValues(values, child, nextLevel(path), current, qnameWithPredicate);
 488                         } else {
 489                             for (final ChoiceNode choiceNode : getChoiceNodes(mapEntryNode)) {
 490                                 addValues(values, Optional.of(choiceNode),  path, current, qnameWithPredicate);
 491                             }
 492                         }
 493                     }
 494                 }
 495             }
 496         }
 497     }
 498
 499     private static Iterable<ChoiceNode> getChoiceNodes(final DataContainerNode<?> dataContainerNode) {
 500         final List<ChoiceNode> choiceNodes = new ArrayList<>();
 501         for (final DataContainerChild<? extends PathArgument, ?> child : dataContainerNode.getValue()) {
 502             if (child instanceof ChoiceNode) {
 503                 choiceNodes.add((ChoiceNode) child);
 504             }
 505         }
 506         return choiceNodes;
 507     }
 508
 509     private static boolean isMatchingPredicate(final MapEntryNode mapEntryNode,
 510             final Map<QName, Set<?>> allowedKeyValues) {
 511         for (final Entry<QName, Object> entryKeyValue : mapEntryNode.getIdentifier().getKeyValues().entrySet()) {
 512             final Set<?> allowedValues = allowedKeyValues.get(entryKeyValue.getKey());
 513             if (allowedValues != null && !allowedValues.contains(entryKeyValue.getValue())) {
 514                 return false;
 515             }
 516         }
 517
 518         return true;
 519     }
 520
 521     private Set<?> getPathKeyExpressionValues(final LeafRefPath predicatePathKeyExpression,
 522             final YangInstanceIdentifier current) {
 523
 524         final Optional<NormalizedNode<?, ?>> parent = findParentNode(tree.getRootNode().getDataAfter(), current);
 525         final Iterable<QNameWithPredicate> predicatePathExpr = predicatePathKeyExpression.getPathFromRoot();
 526         final Iterable<QNameWithPredicate> predicatePath = nextLevel(predicatePathExpr);
 527
 528         final Set<Object> values = new HashSet<>();
 529         // FIXME: this null check does not look right
 530         if (parent != null) {
 531             addValues(values, parent, predicatePath, null, QNameWithPredicate.ROOT);
 532         }
 533
 534         return values;
 535     }
 536
 537     private static Optional<NormalizedNode<?, ?>> findParentNode(
 538             final Optional<NormalizedNode<?, ?>> root, final YangInstanceIdentifier path) {
 539         Optional<NormalizedNode<?, ?>> currentNode = root;
 540         final Iterator<PathArgument> pathIterator = path.getPathArguments().iterator();
 541         while (pathIterator.hasNext()) {
 542             final PathArgument childPathArgument = pathIterator.next();
 543             if (pathIterator.hasNext() && currentNode.isPresent()) {
 544                 currentNode = NormalizedNodes.getDirectChild(currentNode.get(), childPathArgument);
 545             } else {
 546                 return currentNode;
 547             }
 548         }
 549         return Optional.empty();
 550     }
 551
 552     private static Iterable<QNameWithPredicate> nextLevel(final Iterable<QNameWithPredicate> path) {
 553         return Iterables.skip(path, 1);
 554     }
 555 }