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