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.base.Optional;
  11 import com.google.common.collect.Iterables;
  12 import java.util.Collection;
  13 import java.util.HashMap;
  14 import java.util.HashSet;
  15 import java.util.Iterator;
  16 import java.util.LinkedList;
  17 import java.util.List;
  18 import java.util.Map;
  19 import java.util.Map.Entry;
  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.NodeIdentifierWithPredicates;
  24 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  25 import org.opendaylight.yangtools.yang.data.api.schema.ChoiceNode;
  26 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild;
  27 import org.opendaylight.yangtools.yang.data.api.schema.DataContainerNode;
  28 import org.opendaylight.yangtools.yang.data.api.schema.LeafNode;
  29 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetEntryNode;
  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.tree.DataTreeCandidate;
  37 import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeCandidateNode;
  38 import org.opendaylight.yangtools.yang.data.api.schema.tree.ModificationType;
  39 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  40 import org.slf4j.Logger;
  41 import org.slf4j.LoggerFactory;
  42
  43 public class LeafRefValidatation {
  44
  45     private static final Logger LOG = LoggerFactory.getLogger(LeafRefValidatation.class);
  46     private static final String NEW_LINE = System.getProperty("line.separator");
  47     private static final String FAILED = " -> FAILED";
  48     private static final String SUCCESS = " -> OK";
  49
  50     private final DataTreeCandidate tree;
  51     private final List<String> errorsMessages =  new LinkedList<>();
  52     private final Set<LeafRefContext> validatedLeafRefCtx =  new HashSet<>();
  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     private void validate0(final LeafRefContext rootLeafRefCtx)
  63             throws LeafRefDataValidationFailedException {
  64
  65         final DataTreeCandidateNode rootNode = tree.getRootNode();
  66
  67         final Collection<DataTreeCandidateNode> childNodes = rootNode.getChildNodes();
  68         for (final DataTreeCandidateNode dataTreeCandidateNode : childNodes) {
  69
  70             final ModificationType modificationType = dataTreeCandidateNode
  71                     .getModificationType();
  72             if (modificationType != ModificationType.UNMODIFIED) {
  73
  74                 final PathArgument identifier = dataTreeCandidateNode.getIdentifier();
  75                 final QName childQName = identifier.getNodeType();
  76
  77                 final LeafRefContext referencedByCtx = rootLeafRefCtx
  78                         .getReferencedChildByName(childQName);
  79                 final LeafRefContext referencingCtx = rootLeafRefCtx
  80                         .getReferencingChildByName(childQName);
  81                 if (referencedByCtx != null || referencingCtx != null) {
  82                     final YangInstanceIdentifier yangInstanceIdentifier = YangInstanceIdentifier
  83                             .create(dataTreeCandidateNode.getIdentifier());
  84                     validateNode(dataTreeCandidateNode, referencedByCtx,
  85                             referencingCtx, yangInstanceIdentifier);
  86                 }
  87             }
  88
  89         }
  90
  91         if (!errorsMessages.isEmpty()) {
  92             final StringBuilder message = new StringBuilder();
  93             int errCount = 0;
  94             for (final String errorMessage : errorsMessages) {
  95                 message.append(errorMessage);
  96                 errCount++;
  97             }
  98             throw new LeafRefDataValidationFailedException(message.toString(),
  99                     errCount);
 100         }
 101
 102     }
 103
 104     private void validateNode(final DataTreeCandidateNode node,
 105             final LeafRefContext referencedByCtx, final LeafRefContext referencingCtx,
 106             final YangInstanceIdentifier current) {
 107
 108         if ((node.getModificationType() == ModificationType.WRITE)
 109                 && node.getDataAfter().isPresent()) {
 110             final Optional<NormalizedNode<?, ?>> dataAfter = node.getDataAfter();
 111             final NormalizedNode<?, ?> normalizedNode = dataAfter.get();
 112             validateNodeData(normalizedNode, referencedByCtx, referencingCtx,
 113                     node.getModificationType(), current);
 114             return;
 115         }
 116
 117         if (node.getModificationType() == ModificationType.DELETE
 118                 && referencedByCtx != null) {
 119             final Optional<NormalizedNode<?, ?>> dataBefor = node.getDataBefore();
 120             final NormalizedNode<?, ?> normalizedNode = dataBefor.get();
 121             validateNodeData(normalizedNode, referencedByCtx, null,
 122                     node.getModificationType(), current);
 123             return;
 124         }
 125
 126         final Collection<DataTreeCandidateNode> childNodes = node.getChildNodes();
 127         for (final DataTreeCandidateNode childNode : childNodes) {
 128             final ModificationType modificationType = childNode.getModificationType();
 129
 130             if (modificationType != ModificationType.UNMODIFIED) {
 131
 132                 final LeafRefContext childReferencedByCtx = getReferencedByCtxChild(
 133                         referencedByCtx, childNode);
 134                 final LeafRefContext childReferencingCtx = getReferencingCtxChild(
 135                         referencingCtx, childNode);
 136
 137                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 138                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 139                             .node(childNode.getIdentifier());
 140                     validateNode(childNode, childReferencedByCtx,
 141                             childReferencingCtx, childYangInstanceIdentifier);
 142                 }
 143             }
 144
 145         }
 146
 147     }
 148
 149     private static LeafRefContext getReferencingCtxChild(
 150             final LeafRefContext referencingCtx, final DataTreeCandidateNode childNode) {
 151
 152         LeafRefContext childReferencingCtx = null;
 153         if (referencingCtx != null) {
 154             final PathArgument identifier = childNode.getIdentifier();
 155             final QName childQName = identifier.getNodeType();
 156
 157             childReferencingCtx = referencingCtx
 158                     .getReferencingChildByName(childQName);
 159
 160             if (childReferencingCtx == null) {
 161                 final NormalizedNode<?, ?> data = childNode.getDataAfter().get();
 162                 if (data instanceof MapEntryNode
 163                         || data instanceof UnkeyedListEntryNode) {
 164                     childReferencingCtx = referencingCtx;
 165                 }
 166             }
 167         }
 168
 169         return childReferencingCtx;
 170     }
 171
 172     private static LeafRefContext getReferencedByCtxChild(
 173             final LeafRefContext referencedByCtx, final DataTreeCandidateNode childNode) {
 174
 175         LeafRefContext childReferencedByCtx = null;
 176         if (referencedByCtx != null) {
 177             final PathArgument identifier = childNode.getIdentifier();
 178             final QName childQName = identifier.getNodeType();
 179
 180             childReferencedByCtx = referencedByCtx
 181                     .getReferencedChildByName(childQName);
 182             if (childReferencedByCtx == null) {
 183                 final NormalizedNode<?, ?> data = childNode.getDataAfter().get();
 184                 if (data instanceof MapEntryNode
 185                         || data instanceof UnkeyedListEntryNode) {
 186                     childReferencedByCtx = referencedByCtx;
 187                 }
 188             }
 189         }
 190
 191         return childReferencedByCtx;
 192     }
 193
 194     private void validateNodeData(final NormalizedNode<?, ?> node,
 195             final LeafRefContext referencedByCtx, final LeafRefContext referencingCtx,
 196             final ModificationType modificationType, final YangInstanceIdentifier current) {
 197
 198         if (node instanceof LeafNode) {
 199             final LeafNode<?> leaf = (LeafNode<?>) node;
 200
 201             if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 202                 validateLeafRefTargetNodeData(leaf, referencedByCtx,
 203                         modificationType);
 204             }
 205             if (referencingCtx != null && referencingCtx.isReferencing()) {
 206                 validateLeafRefNodeData(leaf, referencingCtx, modificationType,
 207                         current);
 208             }
 209
 210             return;
 211         }
 212
 213         if (node instanceof LeafSetNode) {
 214             final LeafSetNode<?> leafSet = (LeafSetNode<?>) node;
 215
 216             if (referencedByCtx == null && referencingCtx == null) {
 217                 return;
 218             }
 219
 220             final Iterable<? extends NormalizedNode<?, ?>> leafSetEntries = leafSet
 221                     .getValue();
 222             for (final NormalizedNode<?, ?> leafSetEntry : leafSetEntries) {
 223                 if (referencedByCtx != null && referencedByCtx.isReferenced()) {
 224                     validateLeafRefTargetNodeData(leafSetEntry,
 225                             referencedByCtx, modificationType);
 226                 }
 227                 if (referencingCtx != null && referencingCtx.isReferencing()) {
 228                     validateLeafRefNodeData(leafSetEntry, referencingCtx,
 229                             modificationType, current);
 230                 }
 231             }
 232
 233             return;
 234         }
 235
 236         if (node instanceof ChoiceNode) {
 237             final ChoiceNode choice = (ChoiceNode) node;
 238             final Iterable<DataContainerChild<? extends PathArgument, ?>> childs = choice
 239                     .getValue();
 240             for (final DataContainerChild<? extends PathArgument, ?> dataContainerChild : childs) {
 241                 final QName qname = dataContainerChild.getNodeType();
 242
 243                 LeafRefContext childReferencedByCtx = null;
 244                 LeafRefContext childReferencingCtx = null;
 245                 if (referencedByCtx != null) {
 246                     childReferencedByCtx = findReferencedByCtxUnderChoice(
 247                             referencedByCtx, qname);
 248                 }
 249                 if (referencingCtx != null) {
 250                     childReferencingCtx = findReferencingCtxUnderChoice(
 251                             referencingCtx, qname);
 252                 }
 253                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 254                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 255                             .node(dataContainerChild.getIdentifier());
 256                     validateNodeData(dataContainerChild, childReferencedByCtx,
 257                             childReferencingCtx, modificationType,
 258                             childYangInstanceIdentifier);
 259                 }
 260             }
 261         } else if (node instanceof DataContainerNode) {
 262             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 263             final Iterable<DataContainerChild<? extends PathArgument, ?>> dataContainerChilds = dataContainerNode
 264                     .getValue();
 265
 266             for (final DataContainerChild<? extends PathArgument, ?> dataContainerChild : dataContainerChilds) {
 267                 final QName qname = dataContainerChild.getNodeType();
 268
 269                 LeafRefContext childReferencedByCtx = null;
 270                 LeafRefContext childReferencingCtx = null;
 271                 if (referencedByCtx != null) {
 272                     childReferencedByCtx = referencedByCtx
 273                             .getReferencedChildByName(qname);
 274                 }
 275                 if (referencingCtx != null) {
 276                     childReferencingCtx = referencingCtx
 277                             .getReferencingChildByName(qname);
 278                 }
 279                 if (childReferencedByCtx != null || childReferencingCtx != null) {
 280                     final YangInstanceIdentifier childYangInstanceIdentifier = current
 281                             .node(dataContainerChild.getIdentifier());
 282                     validateNodeData(dataContainerChild, childReferencedByCtx,
 283                             childReferencingCtx, modificationType,
 284                             childYangInstanceIdentifier);
 285                 }
 286             }
 287         } else if (node instanceof MapNode) {
 288             final MapNode map = (MapNode) node;
 289             final Iterable<MapEntryNode> mapEntries = map.getValue();
 290             for (final MapEntryNode mapEntry : mapEntries) {
 291                 final Iterable<DataContainerChild<? extends PathArgument, ?>> mapEntryNodes = mapEntry
 292                         .getValue();
 293                 final YangInstanceIdentifier mapEntryYangInstanceIdentifier = current
 294                         .node(mapEntry.getIdentifier());
 295                 for (final DataContainerChild<? extends PathArgument, ?> mapEntryNode : mapEntryNodes) {
 296                     final QName qname = mapEntryNode.getNodeType();
 297
 298                     LeafRefContext childReferencedByCtx = null;
 299                     LeafRefContext childReferencingCtx = null;
 300                     if (referencedByCtx != null) {
 301                         childReferencedByCtx = referencedByCtx
 302                                 .getReferencedChildByName(qname);
 303                     }
 304                     if (referencingCtx != null) {
 305                         childReferencingCtx = referencingCtx
 306                                 .getReferencingChildByName(qname);
 307                     }
 308                     if (childReferencedByCtx != null
 309                             || childReferencingCtx != null) {
 310                         final YangInstanceIdentifier mapEntryNodeYangInstanceIdentifier = mapEntryYangInstanceIdentifier
 311                                 .node(mapEntryNode.getIdentifier());
 312                         validateNodeData(mapEntryNode, childReferencedByCtx,
 313                                 childReferencingCtx, modificationType,
 314                                 mapEntryNodeYangInstanceIdentifier);
 315                     }
 316                 }
 317             }
 318
 319         }
 320         // FIXME if(node instance of UnkeyedListNode ...
 321     }
 322
 323     private static LeafRefContext findReferencingCtxUnderChoice(
 324             final LeafRefContext referencingCtx, final QName qname) {
 325
 326         final Map<QName, LeafRefContext> referencingChilds = referencingCtx
 327                 .getReferencingChilds();
 328         final Set<Entry<QName, LeafRefContext>> childs = referencingChilds.entrySet();
 329         for (final Entry<QName, LeafRefContext> child : childs) {
 330             final LeafRefContext referencingChildByName = child.getValue()
 331                     .getReferencingChildByName(qname);
 332             if (referencingChildByName != null) {
 333                 return referencingChildByName;
 334             }
 335         }
 336
 337         return null;
 338     }
 339
 340     private static LeafRefContext findReferencedByCtxUnderChoice(
 341             final LeafRefContext referencedByCtx, final QName qname) {
 342
 343         final Map<QName, LeafRefContext> referencedByChilds = referencedByCtx
 344                 .getReferencedByChilds();
 345         final Set<Entry<QName, LeafRefContext>> childs = referencedByChilds
 346                 .entrySet();
 347         for (final Entry<QName, LeafRefContext> child : childs) {
 348             final LeafRefContext referencedByChildByName = child.getValue()
 349                     .getReferencedChildByName(qname);
 350             if (referencedByChildByName != null) {
 351                 return referencedByChildByName;
 352             }
 353         }
 354
 355         return null;
 356     }
 357
 358     @SuppressWarnings("rawtypes")
 359     private void validateLeafRefTargetNodeData(final NormalizedNode<?, ?> leaf,
 360             final LeafRefContext referencedByCtx, final ModificationType modificationType) {
 361
 362         final StringBuilder header_log = new StringBuilder();
 363         final StringBuilder log = new StringBuilder();
 364         header_log.append("Operation [" + modificationType
 365                 + "] validate data of leafref TARGET node: name["
 366                 + referencedByCtx.getNodeName() + "] = value["
 367                 + leaf.getValue() + "]");
 368
 369         if (validatedLeafRefCtx.contains(referencedByCtx)) {
 370             header_log.append(" -> SKIP: Already validated");
 371             LOG.debug(header_log.toString());
 372             return;
 373         }
 374
 375         final Map<QName, LeafRefContext> allReferencedByLeafRefCtxs = referencedByCtx
 376                 .getAllReferencedByLeafRefCtxs();
 377
 378         final Map<LeafRefContext, Set> leafRefsValues = new HashMap<>();
 379         final Collection<LeafRefContext> leafrefs = allReferencedByLeafRefCtxs
 380                 .values();
 381         for (final LeafRefContext leafRefContext : leafrefs) {
 382             if (leafRefContext.isReferencing()) {
 383                 final Set<Object> values = new HashSet<>();
 384
 385                 final SchemaPath leafRefNodeSchemaPath = leafRefContext
 386                         .getCurrentNodePath();
 387                 final LeafRefPath leafRefNodePath = LeafRefUtils
 388                         .schemaPathToLeafRefPath(leafRefNodeSchemaPath,
 389                                 leafRefContext.getLeafRefContextModule());
 390                 final Iterable<QNameWithPredicate> pathFromRoot = leafRefNodePath
 391                         .getPathFromRoot();
 392                 addValues(values, tree.getRootNode().getDataAfter(),
 393                         pathFromRoot, null, QNameWithPredicate.ROOT);
 394                 leafRefsValues.put(leafRefContext, values);
 395             }
 396         }
 397
 398         final Set<Object> leafRefTargetNodeValues = new HashSet<>();
 399         final SchemaPath nodeSchemaPath = referencedByCtx.getCurrentNodePath();
 400         final LeafRefPath nodePath = LeafRefUtils.schemaPathToLeafRefPath(
 401                 nodeSchemaPath, referencedByCtx.getLeafRefContextModule());
 402         addValues(leafRefTargetNodeValues, tree.getRootNode().getDataAfter(),
 403                 nodePath.getPathFromRoot(), null, QNameWithPredicate.ROOT);
 404
 405         boolean valid = true;
 406         final Set<Entry<LeafRefContext, Set>> entrySet = leafRefsValues
 407                 .entrySet();
 408         for (final Entry<LeafRefContext, Set> entry : entrySet) {
 409             final LeafRefContext leafRefContext = entry.getKey();
 410             final Set leafRefValuesSet = entry.getValue();
 411             for (final Object leafRefsValue : leafRefValuesSet) {
 412                 if (!leafRefTargetNodeValues.contains(leafRefsValue)) {
 413
 414                     final StringBuilder sb = createInvalidTargetMessage(leaf,
 415                             leafRefTargetNodeValues, leafRefContext,
 416                             leafRefsValue);
 417                     log.append(NEW_LINE);
 418                     log.append(sb.toString());
 419                     log.append(FAILED);
 420
 421                     sb.append(NEW_LINE);
 422                     errorsMessages.add(sb.toString());
 423
 424                     valid = false;
 425                 } else {
 426                     log.append(NEW_LINE);
 427                     log.append("Valid leafref value [");
 428                     log.append(leafRefsValue);
 429                     log.append("]");
 430                     log.append(SUCCESS);
 431                 }
 432             }
 433         }
 434
 435         header_log.append(valid ? SUCCESS : FAILED);
 436         LOG.debug(header_log.append(log.toString()).toString());
 437
 438         validatedLeafRefCtx.add(referencedByCtx);
 439     }
 440
 441     private static StringBuilder createInvalidTargetMessage(final NormalizedNode<?, ?> leaf,
 442             final Set<?> leafRefTargetNodeValues, final LeafRefContext leafRefContext,
 443             final Object leafRefsValue) {
 444         final StringBuilder sb = new StringBuilder();
 445         sb.append("Invalid leafref value [");
 446         sb.append(leafRefsValue);
 447         sb.append("] allowed values ");
 448         sb.append(leafRefTargetNodeValues);
 449         sb.append(" by validation of leafref TARGET node: ");
 450         sb.append(leaf.getNodeType());
 451         sb.append(" path of invalid LEAFREF node: ");
 452         sb.append(leafRefContext.getCurrentNodePath());
 453         sb.append(" leafRef target path: ");
 454         sb.append(leafRefContext.getAbsoluteLeafRefTargetPath());
 455         return sb;
 456     }
 457
 458     private void validateLeafRefNodeData(final NormalizedNode<?, ?> leaf,
 459             final LeafRefContext referencingCtx, final ModificationType modificationType,
 460             final YangInstanceIdentifier current) {
 461
 462         final StringBuilder headerLog = new StringBuilder();
 463         final StringBuilder log = new StringBuilder();
 464
 465         headerLog.append("Operation [");
 466         headerLog.append(modificationType);
 467         headerLog.append("] validate data of LEAFREF node: name[");
 468         headerLog.append(referencingCtx.getNodeName());
 469         headerLog.append("] = value[");
 470         headerLog.append(leaf.getValue());
 471         headerLog.append(']');
 472
 473         final HashSet<Object> values = new HashSet<>();
 474         final LeafRefPath targetPath = referencingCtx.getAbsoluteLeafRefTargetPath();
 475         final Iterable<QNameWithPredicate> pathFromRoot = targetPath
 476                 .getPathFromRoot();
 477
 478         addValues(values, tree.getRootNode().getDataAfter(), pathFromRoot,
 479                 current, QNameWithPredicate.ROOT);
 480
 481         if (!values.contains(leaf.getValue())) {
 482             final StringBuilder sb = createInvalidLeafRefMessage(leaf,
 483                     referencingCtx, values);
 484             errorsMessages.add(sb.toString());
 485
 486             headerLog.append(FAILED);
 487             log.append(sb.toString());
 488         } else {
 489             headerLog.append(SUCCESS);
 490         }
 491
 492         LOG.debug(headerLog.toString());
 493         if (log.length() != 0) {
 494             LOG.debug(log.toString());
 495         }
 496     }
 497
 498     private static StringBuilder createInvalidLeafRefMessage(
 499             final NormalizedNode<?, ?> leaf, final LeafRefContext referencingCtx,
 500             final Set<?> values) {
 501         final StringBuilder sb = new StringBuilder();
 502         sb.append("Invalid leafref value [");
 503         sb.append(leaf.getValue());
 504         sb.append("] allowed values ");
 505         sb.append(values);
 506         sb.append(" of LEAFREF node: ");
 507         sb.append(leaf.getNodeType());
 508         sb.append(" leafRef target path: ");
 509         sb.append(referencingCtx.getAbsoluteLeafRefTargetPath());
 510         sb.append(NEW_LINE);
 511         return sb;
 512     }
 513
 514     private void addValues(final Set<Object> values,
 515             final Optional<? extends NormalizedNode<?, ?>> optDataNode,
 516             final Iterable<QNameWithPredicate> path, final YangInstanceIdentifier current,
 517             final QNameWithPredicate previousQName) {
 518
 519         if (!optDataNode.isPresent()) {
 520             return;
 521         }
 522         final NormalizedNode<?, ?> node = optDataNode.get();
 523
 524         if (node instanceof LeafNode || node instanceof LeafSetEntryNode) {
 525             values.add(node.getValue());
 526             return;
 527         } else if (node instanceof LeafSetNode<?>) {
 528             final LeafSetNode<?> leafSetNode = (LeafSetNode<?>) node;
 529             final Iterable<? extends NormalizedNode<?, ?>> entries = leafSetNode
 530                     .getValue();
 531             for (final NormalizedNode<?, ?> entry : entries) {
 532                 values.add(entry.getValue());
 533             }
 534             return;
 535         }
 536
 537         final Iterator<QNameWithPredicate> iterator = path.iterator();
 538         if (!iterator.hasNext()) {
 539             return;
 540         }
 541         final QNameWithPredicate qnameWithPredicate = iterator.next();
 542         final QName qName = qnameWithPredicate.getQName();
 543         final PathArgument pathArgument = toPathArgument(qName);
 544
 545         if (node instanceof DataContainerNode) {
 546             final DataContainerNode<?> dataContainerNode = (DataContainerNode<?>) node;
 547             final Optional<DataContainerChild<? extends PathArgument, ?>> child = dataContainerNode
 548                     .getChild(pathArgument);
 549
 550             if (child.isPresent()) {
 551                 addValues(values, child, nextLevel(path), current,
 552                         qnameWithPredicate);
 553             } else {
 554                 final Iterable<ChoiceNode> choiceNodes = getChoiceNodes(dataContainerNode);
 555                 for (final ChoiceNode choiceNode : choiceNodes) {
 556                     addValues(values, Optional.of(choiceNode), path, current,
 557                             qnameWithPredicate);
 558                 }
 559             }
 560
 561         } else if (node instanceof MapNode) {
 562             final MapNode map = (MapNode) node;
 563             final List<QNamePredicate> qNamePredicates = previousQName
 564                     .getQNamePredicates();
 565             if (qNamePredicates.isEmpty() || current == null) {
 566                 final Iterable<MapEntryNode> value = map.getValue();
 567                 for (final MapEntryNode mapEntryNode : value) {
 568                     final Optional<DataContainerChild<? extends PathArgument, ?>> child = mapEntryNode
 569                             .getChild(pathArgument);
 570
 571                     if (child.isPresent()) {
 572                         addValues(values, child, nextLevel(path), current,
 573                                 qnameWithPredicate);
 574                     } else {
 575                         final Iterable<ChoiceNode> choiceNodes = getChoiceNodes(mapEntryNode);
 576                         for (final ChoiceNode choiceNode : choiceNodes) {
 577                             addValues(values, Optional.of(choiceNode), path,
 578                                     current, qnameWithPredicate);
 579                         }
 580                     }
 581                 }
 582             } else {
 583                 final Map<QName, Set<?>> keyValues = new HashMap<>();
 584
 585                 final Iterator<QNamePredicate> predicates = qNamePredicates
 586                         .iterator();
 587                 while (predicates.hasNext()) {
 588                     final QNamePredicate predicate = predicates.next();
 589                     final QName identifier = predicate.getIdentifier();
 590                     final LeafRefPath predicatePathKeyExpression = predicate
 591                             .getPathKeyExpression();
 592
 593                     final Set<?> pathKeyExprValues = getPathKeyExpressionValues(
 594                             predicatePathKeyExpression, current);
 595
 596                     keyValues.put(identifier, pathKeyExprValues);
 597                 }
 598
 599                 final Iterable<MapEntryNode> mapEntryNodes = map.getValue();
 600                 for (final MapEntryNode mapEntryNode : mapEntryNodes) {
 601                     if (isMatchingPredicate(mapEntryNode, keyValues)) {
 602                         final Optional<DataContainerChild<? extends PathArgument, ?>> child = mapEntryNode
 603                                 .getChild(pathArgument);
 604
 605                         if (child.isPresent()) {
 606                             addValues(values, child, nextLevel(path), current,
 607                                     qnameWithPredicate);
 608                         } else {
 609                             final Iterable<ChoiceNode> choiceNodes = getChoiceNodes(mapEntryNode);
 610                             for (final ChoiceNode choiceNode : choiceNodes) {
 611                                 addValues(values, Optional.of(choiceNode),
 612                                         path, current, qnameWithPredicate);
 613                             }
 614                         }
 615                     }
 616                 }
 617
 618             }
 619         }
 620     }
 621
 622     private static Iterable<ChoiceNode> getChoiceNodes(final DataContainerNode<?> dataContainerNode) {
 623
 624         final LinkedList<ChoiceNode> choiceNodes = new LinkedList<ChoiceNode>();
 625
 626         final Iterable<DataContainerChild<? extends PathArgument, ?>> childs = dataContainerNode
 627                 .getValue();
 628         for (final DataContainerChild<? extends PathArgument, ?> child : childs) {
 629             if (child instanceof ChoiceNode) {
 630                 choiceNodes.add((ChoiceNode) child);
 631             }
 632         }
 633         return choiceNodes;
 634     }
 635
 636     private static boolean isMatchingPredicate(final MapEntryNode mapEntryNode,
 637             final Map<QName, Set<?>> allowedKeyValues) {
 638
 639         final NodeIdentifierWithPredicates identifier = mapEntryNode.getIdentifier();
 640         final Map<QName, Object> entryKeyValues = identifier.getKeyValues();
 641
 642         final Set<Entry<QName, Object>> entryKeyValueSet = entryKeyValues.entrySet();
 643         for (final Entry<QName, Object> entryKeyValue : entryKeyValueSet) {
 644             final QName key = entryKeyValue.getKey();
 645             final Object value = entryKeyValue.getValue();
 646
 647             final Set<?> allowedValues = allowedKeyValues.get(key);
 648             if (allowedValues != null && !allowedValues.contains(value)) {
 649                 return false;
 650             }
 651
 652         }
 653
 654         return true;
 655     }
 656
 657     private Set<?> getPathKeyExpressionValues(
 658             final LeafRefPath predicatePathKeyExpression,
 659             final YangInstanceIdentifier current) {
 660
 661         final Optional<NormalizedNode<?, ?>> parent = findParentNode(tree
 662                 .getRootNode().getDataAfter(), current);
 663
 664         final Iterable<QNameWithPredicate> predicatePathExpr = predicatePathKeyExpression
 665                 .getPathFromRoot();
 666         final Iterable<QNameWithPredicate> predicatePath = nextLevel(predicatePathExpr);
 667
 668         final Set<Object> values = new HashSet<>();
 669         if (parent != null) {
 670             addValues(values, parent, predicatePath, null,
 671                     QNameWithPredicate.ROOT);
 672         }
 673
 674         return values;
 675     }
 676
 677     private static Optional<NormalizedNode<?, ?>> findParentNode(
 678             final Optional<NormalizedNode<?, ?>> root, final YangInstanceIdentifier path) {
 679         Optional<NormalizedNode<?, ?>> currentNode = root;
 680         final Iterator<PathArgument> pathIterator = path.getPathArguments()
 681                 .iterator();
 682         while (pathIterator.hasNext()) {
 683             final PathArgument childPathArgument = pathIterator.next();
 684             if (pathIterator.hasNext() && currentNode.isPresent()) {
 685                 currentNode = NormalizedNodes.getDirectChild(currentNode.get(),
 686                         childPathArgument);
 687             } else {
 688                 return currentNode;
 689             }
 690         }
 691         return Optional.absent();
 692     }
 693
 694     private static Iterable<QNameWithPredicate> nextLevel(final Iterable<QNameWithPredicate> path) {
 695         return Iterables.skip(path, 1);
 696     }
 697
 698     private static PathArgument toPathArgument(final QName qName) {
 699         return YangInstanceIdentifier.of(qName).getLastPathArgument();
 700     }
 701 }