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