yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/builder/impl/BuilderUtils.java

   1 /*
   2  * Copyright (c) 2013 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.parser.builder.impl;
   9
  10 import com.google.common.base.Function;
  11 import com.google.common.base.Optional;
  12 import com.google.common.base.Preconditions;
  13 import com.google.common.base.Splitter;
  14 import com.google.common.collect.Collections2;
  15 import com.google.common.collect.Iterables;
  16 import com.google.common.io.ByteSource;
  17 import com.google.common.io.ByteStreams;
  18 import java.io.File;
  19 import java.io.FileNotFoundException;
  20 import java.io.IOException;
  21 import java.io.InputStream;
  22 import java.net.URI;
  23 import java.util.ArrayList;
  24 import java.util.Collection;
  25 import java.util.Date;
  26 import java.util.HashMap;
  27 import java.util.HashSet;
  28 import java.util.Iterator;
  29 import java.util.LinkedHashSet;
  30 import java.util.List;
  31 import java.util.Map;
  32 import java.util.NavigableMap;
  33 import java.util.Set;
  34 import java.util.TreeMap;
  35 import org.antlr.v4.runtime.tree.ParseTree;
  36 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Belongs_to_stmtContext;
  37 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Module_header_stmtsContext;
  38 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Module_stmtContext;
  39 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Namespace_stmtContext;
  40 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Revision_stmtsContext;
  41 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Submodule_header_stmtsContext;
  42 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.Submodule_stmtContext;
  43 import org.opendaylight.yangtools.yang.common.QName;
  44 import org.opendaylight.yangtools.yang.model.api.AnyXmlSchemaNode;
  45 import org.opendaylight.yangtools.yang.model.api.ChoiceCaseNode;
  46 import org.opendaylight.yangtools.yang.model.api.ChoiceSchemaNode;
  47 import org.opendaylight.yangtools.yang.model.api.ContainerSchemaNode;
  48 import org.opendaylight.yangtools.yang.model.api.DataNodeContainer;
  49 import org.opendaylight.yangtools.yang.model.api.DataSchemaNode;
  50 import org.opendaylight.yangtools.yang.model.api.GroupingDefinition;
  51 import org.opendaylight.yangtools.yang.model.api.LeafListSchemaNode;
  52 import org.opendaylight.yangtools.yang.model.api.LeafSchemaNode;
  53 import org.opendaylight.yangtools.yang.model.api.ListSchemaNode;
  54 import org.opendaylight.yangtools.yang.model.api.Module;
  55 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  56 import org.opendaylight.yangtools.yang.model.api.SchemaContext;
  57 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  58 import org.opendaylight.yangtools.yang.model.api.TypeDefinition;
  59 import org.opendaylight.yangtools.yang.model.api.UnknownSchemaNode;
  60 import org.opendaylight.yangtools.yang.model.util.ExtendedType;
  61 import org.opendaylight.yangtools.yang.parser.builder.api.AugmentationSchemaBuilder;
  62 import org.opendaylight.yangtools.yang.parser.builder.api.AugmentationTargetBuilder;
  63 import org.opendaylight.yangtools.yang.parser.builder.api.Builder;
  64 import org.opendaylight.yangtools.yang.parser.builder.api.DataNodeContainerBuilder;
  65 import org.opendaylight.yangtools.yang.parser.builder.api.DataSchemaNodeBuilder;
  66 import org.opendaylight.yangtools.yang.parser.builder.api.GroupingBuilder;
  67 import org.opendaylight.yangtools.yang.parser.builder.api.GroupingMember;
  68 import org.opendaylight.yangtools.yang.parser.builder.api.SchemaNodeBuilder;
  69 import org.opendaylight.yangtools.yang.parser.builder.api.TypeDefinitionBuilder;
  70 import org.opendaylight.yangtools.yang.parser.builder.api.UnknownSchemaNodeBuilder;
  71 import org.opendaylight.yangtools.yang.parser.builder.api.UsesNodeBuilder;
  72 import org.opendaylight.yangtools.yang.parser.impl.ParserListenerUtils;
  73 import org.opendaylight.yangtools.yang.parser.impl.util.YangModelDependencyInfo;
  74 import org.opendaylight.yangtools.yang.parser.util.NamedByteArrayInputStream;
  75 import org.opendaylight.yangtools.yang.parser.util.NamedFileInputStream;
  76 import org.opendaylight.yangtools.yang.parser.util.YangParseException;
  77 import org.slf4j.Logger;
  78 import org.slf4j.LoggerFactory;
  79
  80 public final class BuilderUtils {
  81
  82     private static final Logger LOG = LoggerFactory.getLogger(BuilderUtils.class);
  83     private static final Splitter COLON_SPLITTER = Splitter.on(':');
  84     private static final Date NULL_DATE = new Date(0L);
  85     private static final String INPUT = "input";
  86     private static final String OUTPUT = "output";
  87     private static final String CHILD_NOT_FOUND_IN_NODE_STR = "Child {} not found in node {}";
  88
  89     private BuilderUtils() {
  90     }
  91
  92     public static Collection<ByteSource> streamsToByteSources(final Collection<InputStream> streams) throws IOException {
  93         Collection<ByteSource> result = new HashSet<>();
  94         for (InputStream stream : streams) {
  95             result.add(new ByteSourceImpl(stream));
  96         }
  97         return result;
  98     }
  99
 100     public static ByteSource fileToByteSource(final File file) {
 101         return new ByteSource() {
 102             @Override
 103             public InputStream openStream() throws IOException {
 104                 return new NamedFileInputStream(file, file.getAbsolutePath());
 105             }
 106         };
 107     }
 108
 109     public static Collection<ByteSource> filesToByteSources(final Collection<File> streams)
 110             throws FileNotFoundException {
 111         return Collections2.transform(streams, new Function<File, ByteSource>() {
 112             @Override
 113             public ByteSource apply(final File input) {
 114                 return new ByteSource() {
 115                     @Override
 116                     public InputStream openStream() throws IOException {
 117                         return new NamedFileInputStream(input, input.getAbsolutePath());
 118                     }
 119                 };
 120             }
 121         });
 122     }
 123
 124     /**
 125      * Find dependent module based on given prefix
 126      *
 127      * @param modules
 128      *            all available modules
 129      * @param module
 130      *            current module
 131      * @param prefix
 132      *            target module prefix
 133      * @param line
 134      *            current line in yang model
 135      * @return module builder if found, null otherwise
 136      */
 137     public static ModuleBuilder findModuleFromBuilders(final Map<String, NavigableMap<Date, ModuleBuilder>> modules,
 138             final ModuleBuilder module, final String prefix, final int line) {
 139         ModuleBuilder dependentModule;
 140         Date dependentModuleRevision;
 141
 142         if (prefix == null) {
 143             dependentModule = module;
 144         } else if (prefix.equals(module.getPrefix())) {
 145             dependentModule = module;
 146         } else {
 147             ModuleImport dependentModuleImport = module.getImport(prefix);
 148             if (dependentModuleImport == null) {
 149                 throw new YangParseException(module.getName(), line, "No import found with prefix '" + prefix + "'.");
 150             }
 151             String dependentModuleName = dependentModuleImport.getModuleName();
 152             dependentModuleRevision = dependentModuleImport.getRevision();
 153
 154             NavigableMap<Date, ModuleBuilder> moduleBuildersByRevision = modules.get(dependentModuleName);
 155             if (moduleBuildersByRevision == null) {
 156                 return null;
 157             }
 158             if (dependentModuleRevision == null) {
 159                 dependentModule = moduleBuildersByRevision.lastEntry().getValue();
 160             } else {
 161                 dependentModule = moduleBuildersByRevision.get(dependentModuleRevision);
 162             }
 163         }
 164         return dependentModule;
 165     }
 166
 167     public static ModuleBuilder findModuleFromBuilders(final ModuleImport imp, final Iterable<ModuleBuilder> modules) {
 168         String name = imp.getModuleName();
 169         Date revision = imp.getRevision();
 170         NavigableMap<Date, ModuleBuilder> map = new TreeMap<>();
 171         for (ModuleBuilder module : modules) {
 172             if (module != null && module.getName().equals(name)) {
 173                 map.put(module.getRevision(), module);
 174             }
 175         }
 176         if (map.isEmpty()) {
 177             return null;
 178         }
 179         if (revision == null) {
 180             return map.lastEntry().getValue();
 181         }
 182         return map.get(revision);
 183     }
 184
 185     /**
 186      * Find module from context based on prefix.
 187      *
 188      * @param context
 189      *            schema context
 190      * @param currentModule
 191      *            current module
 192      * @param prefix
 193      *            prefix used to reference dependent module
 194      * @param line
 195      *            current line in yang model
 196      * @return module based on import with given prefix if found in context,
 197      *         null otherwise
 198      * @throws YangParseException
 199      *             if no import found with given prefix
 200      */
 201     public static Module findModuleFromContext(final SchemaContext context, final ModuleBuilder currentModule,
 202             final String prefix, final int line) {
 203         NavigableMap<Date, Module> modulesByRevision = new TreeMap<>();
 204
 205         ModuleImport dependentModuleImport = currentModule.getImport(prefix);
 206         if (dependentModuleImport == null) {
 207             throw new YangParseException(currentModule.getName(), line, "No import found with prefix '" + prefix + "'.");
 208         }
 209         String dependentModuleName = dependentModuleImport.getModuleName();
 210         Date dependentModuleRevision = dependentModuleImport.getRevision();
 211
 212         for (Module contextModule : context.getModules()) {
 213             if (contextModule.getName().equals(dependentModuleName)) {
 214                 Date revision = contextModule.getRevision();
 215                 if (revision == null) {
 216                     revision = NULL_DATE;
 217                 }
 218                 modulesByRevision.put(revision, contextModule);
 219             }
 220         }
 221
 222         Module result;
 223         if (dependentModuleRevision == null) {
 224             result = modulesByRevision.get(modulesByRevision.firstKey());
 225         } else {
 226             result = modulesByRevision.get(dependentModuleRevision);
 227         }
 228         if (result == null) {
 229             throw new YangParseException(currentModule.getName(), line, "Module not found for prefix " + prefix);
 230         }
 231
 232         return result;
 233     }
 234
 235     /**
 236      * Add all augment's child nodes to given target.
 237      *
 238      * @param augment
 239      *            builder of augment statement
 240      * @param target
 241      *            augmentation target node
 242      */
 243     public static void fillAugmentTarget(final AugmentationSchemaBuilder augment, final Builder target) {
 244         if (target instanceof DataNodeContainerBuilder) {
 245             fillAugmentTarget(augment, (DataNodeContainerBuilder) target);
 246         } else if (target instanceof ChoiceBuilder) {
 247             fillAugmentTarget(augment, (ChoiceBuilder) target);
 248         } else {
 249             throw new YangParseException(
 250                     augment.getModuleName(),
 251                     augment.getLine(),
 252                     "Error in augment parsing: The target node MUST be either a container, list, choice, case, input, output, or notification node.");
 253         }
 254     }
 255
 256     /**
 257      * Add all augment's child nodes to given target.
 258      *
 259      * @param augment
 260      *            builder of augment statement
 261      * @param target
 262      *            augmentation target node
 263      */
 264     private static void fillAugmentTarget(final AugmentationSchemaBuilder augment, final DataNodeContainerBuilder target) {
 265         for (DataSchemaNodeBuilder child : augment.getChildNodeBuilders()) {
 266             DataSchemaNodeBuilder childCopy = CopyUtils.copy(child, target, false);
 267             if (augment.getParent() instanceof UsesNodeBuilder) {
 268                 setNodeAddedByUses(childCopy);
 269             }
 270             setNodeAugmenting(childCopy);
 271             try {
 272                 target.addChildNode(childCopy);
 273             } catch (YangParseException e) {
 274
 275                 // more descriptive message
 276                 throw new YangParseException(augment.getModuleName(), augment.getLine(),
 277                         "Failed to perform augmentation: " + e.getMessage());
 278             }
 279         }
 280     }
 281
 282     /**
 283      * Add all augment's child nodes to given target.
 284      *
 285      * @param augment
 286      *            builder of augment statement
 287      * @param target
 288      *            augmentation target choice node
 289      */
 290     private static void fillAugmentTarget(final AugmentationSchemaBuilder augment, final ChoiceBuilder target) {
 291         for (DataSchemaNodeBuilder builder : augment.getChildNodeBuilders()) {
 292             DataSchemaNodeBuilder childCopy = CopyUtils.copy(builder, target, false);
 293             if (augment.getParent() instanceof UsesNodeBuilder) {
 294                 setNodeAddedByUses(childCopy);
 295             }
 296             setNodeAugmenting(childCopy);
 297             target.addCase(childCopy);
 298         }
 299         for (UsesNodeBuilder usesNode : augment.getUsesNodeBuilders()) {
 300             if (usesNode != null) {
 301                 throw new YangParseException(augment.getModuleName(), augment.getLine(),
 302                         "Error in augment parsing: cannot augment choice with nodes from grouping");
 303             }
 304         }
 305     }
 306
 307     /**
 308      * Set augmenting flag to true for node and all its child nodes.
 309      *
 310      * @param node
 311      */
 312     private static void setNodeAugmenting(final DataSchemaNodeBuilder node) {
 313         node.setAugmenting(true);
 314         if (node instanceof DataNodeContainerBuilder) {
 315             DataNodeContainerBuilder dataNodeChild = (DataNodeContainerBuilder) node;
 316             for (DataSchemaNodeBuilder inner : dataNodeChild.getChildNodeBuilders()) {
 317                 setNodeAugmenting(inner);
 318             }
 319         } else if (node instanceof ChoiceBuilder) {
 320             ChoiceBuilder choiceChild = (ChoiceBuilder) node;
 321             for (ChoiceCaseBuilder inner : choiceChild.getCases()) {
 322                 setNodeAugmenting(inner);
 323             }
 324         }
 325     }
 326
 327     /**
 328      * Set addedByUses flag to true for node and all its child nodes.
 329      *
 330      * @param node grouping member node
 331      */
 332     public static void setNodeAddedByUses(final GroupingMember node) {
 333         node.setAddedByUses(true);
 334         if (node instanceof DataNodeContainerBuilder) {
 335             DataNodeContainerBuilder dataNodeChild = (DataNodeContainerBuilder) node;
 336             for (DataSchemaNodeBuilder inner : dataNodeChild.getChildNodeBuilders()) {
 337                 setNodeAddedByUses(inner);
 338             }
 339         } else if (node instanceof ChoiceBuilder) {
 340             ChoiceBuilder choiceChild = (ChoiceBuilder) node;
 341             for (ChoiceCaseBuilder inner : choiceChild.getCases()) {
 342                 setNodeAddedByUses(inner);
 343             }
 344         }
 345     }
 346
 347     /**
 348      * Find builder of schema node under parent builder (including under
 349      * AugmentationSchemaBuilder).
 350      *
 351      * @param path
 352      *            - path of target schema node builder
 353      * @param parent
 354      *            - base data node container builder under which the target
 355      *            schema node builder should be found
 356      * @return builder of schema node
 357      */
 358     public static SchemaNodeBuilder findTargetNode(final Iterable<QName> path,
 359             final DataNodeContainerBuilder parent) {
 360
 361         Preconditions.checkNotNull(parent);
 362         Preconditions.checkNotNull(path);
 363
 364         SchemaNodeBuilder foundNode = null;
 365
 366         final Iterator<QName> pathIterator = path.iterator();
 367         if (pathIterator.hasNext()) {
 368             String name = pathIterator.next().getLocalName();
 369             foundNode = parent.getDataChildByName(name);
 370             if (foundNode == null) {
 371                 foundNode = findUnknownNode(name, parent);
 372             }
 373         }
 374
 375         if (pathIterator.hasNext() && foundNode != null) {
 376             return findSchemaNode(Iterables.skip(path, 1), foundNode);
 377         } else {
 378             return foundNode;
 379         }
 380     }
 381
 382     public static SchemaNodeBuilder findSchemaNode(final Iterable<QName> path, final SchemaNodeBuilder parentNode) {
 383         SchemaNodeBuilder node = null;
 384         SchemaNodeBuilder parent = parentNode;
 385         int size = Iterables.size(path);
 386         int i = 0;
 387         for (QName qname : path) {
 388             String name = qname.getLocalName();
 389             if (parent instanceof DataNodeContainerBuilder) {
 390                 node = ((DataNodeContainerBuilder) parent).getDataChildByName(name);
 391                 if (node == null) {
 392                     node = findUnknownNode(name, parent);
 393                 }
 394             } else if (parent instanceof ChoiceBuilder) {
 395                 node = ((ChoiceBuilder) parent).getCaseNodeByName(name);
 396                 if (node == null) {
 397                     node = findUnknownNode(name, parent);
 398                 }
 399             } else if (parent instanceof RpcDefinitionBuilder) {
 400                 if (INPUT.equals(name)) {
 401                     node = ((RpcDefinitionBuilder) parent).getInput();
 402                 } else if (OUTPUT.equals(name)) {
 403                     node = ((RpcDefinitionBuilder) parent).getOutput();
 404                 } else {
 405                     if (node == null) {
 406                         node = findUnknownNode(name, parent);
 407                     }
 408                 }
 409             } else {
 410                 node = findUnknownNode(name, parent);
 411             }
 412
 413             if (i < size - 1) {
 414                 parent = node;
 415             }
 416             i = i + 1;
 417         }
 418
 419         return node;
 420     }
 421
 422     private static UnknownSchemaNodeBuilder findUnknownNode(final String name, final Builder parent) {
 423         for (UnknownSchemaNodeBuilder un : parent.getUnknownNodes()) {
 424             if (un.getQName().getLocalName().equals(name)) {
 425                 return un;
 426             }
 427         }
 428         return null;
 429     }
 430
 431     /**
 432      *
 433      * Find a builder for node in data namespace of YANG module.
 434      *
 435      * Search is performed on full QName equals, this means builders and schema
 436      * path MUST be resolved against imports and their namespaces.
 437      *
 438      * Search is done in data namespace, this means notification, rpc
 439      * definitions and top level data definitions are considered as top-level
 440      * items, from which it is possible to traverse.
 441      *
 442      *
 443      * @param schemaPath
 444      *            Schema Path to node
 445      * @param module
 446      *            ModuleBuilder to start lookup in
 447      * @return Node Builder if found, {@link Optional#absent()} otherwise.
 448      */
 449     public static Optional<SchemaNodeBuilder> findSchemaNodeInModule(final SchemaPath schemaPath,
 450             final ModuleBuilder module) {
 451         Iterator<QName> path = schemaPath.getPathFromRoot().iterator();
 452         Preconditions.checkArgument(path.hasNext(), "Schema Path must contain at least one element.");
 453         QName first = path.next();
 454         Optional<SchemaNodeBuilder> currentNode = getDataNamespaceChild(module, first);
 455
 456         while (currentNode.isPresent() && path.hasNext()) {
 457             SchemaNodeBuilder currentParent = currentNode.get();
 458             QName currentPath = path.next();
 459             currentNode = findDataChild(currentParent, currentPath);
 460             if (!currentNode.isPresent()) {
 461                 for (SchemaNodeBuilder un : currentParent.getUnknownNodes()) {
 462                     if (un.getQName().equals(currentPath)) {
 463                         currentNode = Optional.of(un);
 464                     }
 465                 }
 466             }
 467         }
 468         return currentNode;
 469     }
 470
 471     private static Optional<SchemaNodeBuilder> findDataChild(final SchemaNodeBuilder parent, final QName child) {
 472         if (parent instanceof DataNodeContainerBuilder) {
 473             return castOptional(SchemaNodeBuilder.class,
 474                     findDataChildInDataNodeContainer((DataNodeContainerBuilder) parent, child));
 475         } else if (parent instanceof ChoiceBuilder) {
 476             return castOptional(SchemaNodeBuilder.class, findCaseInChoice((ChoiceBuilder) parent, child));
 477         } else if (parent instanceof RpcDefinitionBuilder) {
 478             return castOptional(SchemaNodeBuilder.class, findContainerInRpc((RpcDefinitionBuilder) parent, child));
 479         } else {
 480             LOG.trace(CHILD_NOT_FOUND_IN_NODE_STR, child, parent);
 481             return Optional.absent();
 482         }
 483     }
 484
 485     /**
 486      * Casts optional from one argument to other.
 487      *
 488      * @param cls
 489      *            Class to be checked
 490      * @param optional
 491      *            Original value
 492      * @return Optional object with type argument casted as cls
 493      */
 494     private static <T> Optional<T> castOptional(final Class<T> cls, final Optional<?> optional) {
 495         if (optional.isPresent()) {
 496             Object value = optional.get();
 497             if (cls.isInstance(value)) {
 498                 @SuppressWarnings("unchecked")
 499                 // Actually checked by outer if
 500                 T casted = (T) value;
 501                 return Optional.of(casted);
 502             }
 503         }
 504         return Optional.absent();
 505     }
 506
 507     // FIXME: if rpc does not define input or output, this method creates it
 508     /**
 509      *
 510      * Gets input / output container from {@link RpcDefinitionBuilder} if QName
 511      * is input/output.
 512      *
 513      *
 514      * @param parent
 515      *            RPC Definition builder
 516      * @param child
 517      *            Child QName
 518      * @return Optional of input/output if defined and QName is input/output.
 519      *         Otherwise {@link Optional#absent()}.
 520      */
 521     private static Optional<ContainerSchemaNodeBuilder> findContainerInRpc(final RpcDefinitionBuilder parent,
 522             final QName child) {
 523         if (INPUT.equals(child.getLocalName())) {
 524             if (parent.getInput() == null) {
 525                 QName qname = QName.create(parent.getQName().getModule(), INPUT);
 526                 final ContainerSchemaNodeBuilder inputBuilder = new ContainerSchemaNodeBuilder(parent.getModuleName(),
 527                         parent.getLine(), qname, parent.getPath().createChild(qname));
 528                 inputBuilder.setParent(parent);
 529                 parent.setInput(inputBuilder);
 530                 return Optional.of(inputBuilder);
 531             }
 532             return Optional.of(parent.getInput());
 533         } else if (OUTPUT.equals(child.getLocalName())) {
 534             if (parent.getOutput() == null) {
 535                 QName qname = QName.create(parent.getQName().getModule(), OUTPUT);
 536                 final ContainerSchemaNodeBuilder outputBuilder = new ContainerSchemaNodeBuilder(parent.getModuleName(),
 537                         parent.getLine(), qname, parent.getPath().createChild(qname));
 538                 outputBuilder.setParent(parent);
 539                 parent.setOutput(outputBuilder);
 540                 return Optional.of(outputBuilder);
 541             }
 542             return Optional.of(parent.getOutput());
 543         }
 544         LOG.trace(CHILD_NOT_FOUND_IN_NODE_STR, child, parent);
 545         return Optional.absent();
 546     }
 547
 548     /**
 549      * Finds case by QName in {@link ChoiceBuilder}
 550      *
 551      *
 552      * @param parent
 553      *            DataNodeContainer in which lookup should be performed
 554      * @param child
 555      *            QName of child
 556      * @return Optional of child if found.
 557      */
 558
 559     private static Optional<ChoiceCaseBuilder> findCaseInChoice(final ChoiceBuilder parent, final QName child) {
 560         for (ChoiceCaseBuilder caze : parent.getCases()) {
 561             if (caze.getQName().equals(child)) {
 562                 return Optional.of(caze);
 563             }
 564         }
 565         LOG.trace(CHILD_NOT_FOUND_IN_NODE_STR, child, parent);
 566         return Optional.absent();
 567     }
 568
 569     /**
 570      * Finds direct child by QName in {@link DataNodeContainerBuilder}
 571      *
 572      *
 573      * @param parent
 574      *            DataNodeContainer in which lookup should be performed
 575      * @param child
 576      *            QName of child
 577      * @return Optional of child if found.
 578      */
 579     private static Optional<DataSchemaNodeBuilder> findDataChildInDataNodeContainer(final DataNodeContainerBuilder parent,
 580             final QName child) {
 581         for (DataSchemaNodeBuilder childNode : parent.getChildNodeBuilders()) {
 582             if (childNode.getQName().equals(child)) {
 583                 return Optional.of(childNode);
 584             }
 585         }
 586         LOG.trace(CHILD_NOT_FOUND_IN_NODE_STR, child, parent);
 587         return Optional.absent();
 588     }
 589
 590     /**
 591      *
 592      * Find a child builder for node in data namespace of YANG module.
 593      *
 594      * Search is performed on full QName equals, this means builders and schema
 595      * path MUST be resolved against imports and their namespaces.
 596      *
 597      * Search is done in data namespace, this means notification, rpc
 598      * definitions and top level data definitions are considered as top-level
 599      * items, from which it is possible to traverse.
 600      *
 601      *
 602      * @param child
 603      *            Child QName.
 604      * @param module
 605      *            ModuleBuilder to start lookup in
 606      * @return Node Builder if found, {@link Optional#absent()} otherwise.
 607      */
 608     private static Optional<SchemaNodeBuilder> getDataNamespaceChild(final ModuleBuilder module, final QName child) {
 609         /*
 610          * First we do lookup in data tree, if node is found we return it.
 611          */
 612         final Optional<SchemaNodeBuilder> dataTreeNode = getDataChildByQName(module, child);
 613         if (dataTreeNode.isPresent()) {
 614             return dataTreeNode;
 615         }
 616
 617         /*
 618          * We lookup in notifications
 619          */
 620         Set<NotificationBuilder> notifications = module.getAddedNotifications();
 621         for (NotificationBuilder notification : notifications) {
 622             if (notification.getQName().equals(child)) {
 623                 return Optional.<SchemaNodeBuilder> of(notification);
 624             }
 625         }
 626
 627         /*
 628          * We lookup in RPCs
 629          */
 630         Set<RpcDefinitionBuilder> rpcs = module.getAddedRpcs();
 631         for (RpcDefinitionBuilder rpc : rpcs) {
 632             if (rpc.getQName().equals(child)) {
 633                 return Optional.<SchemaNodeBuilder> of(rpc);
 634             }
 635         }
 636         LOG.trace("Child {} not found in data namespace of module {}", child, module);
 637         return Optional.absent();
 638     }
 639
 640     private static Optional<SchemaNodeBuilder> getDataChildByQName(final DataNodeContainerBuilder builder, final QName child) {
 641         for (DataSchemaNodeBuilder childNode : builder.getChildNodeBuilders()) {
 642             if (childNode.getQName().equals(child)) {
 643                 return Optional.<SchemaNodeBuilder> of(childNode);
 644             }
 645         }
 646         LOG.trace(CHILD_NOT_FOUND_IN_NODE_STR, child, builder);
 647         return Optional.absent();
 648     }
 649
 650     /**
 651      * Find augment target node and perform augmentation.
 652      *
 653      * @param augment
 654      *            augment builder to process
 655      * @param firstNodeParent
 656      *            parent of first node in path
 657      * @return true if augmentation process succeed, false otherwise
 658      */
 659     public static boolean processAugmentation(final AugmentationSchemaBuilder augment,
 660             final ModuleBuilder firstNodeParent) {
 661         Optional<SchemaNodeBuilder> potentialTargetNode = findSchemaNodeInModule(augment.getTargetPath(),
 662                 firstNodeParent);
 663         if (!potentialTargetNode.isPresent()) {
 664             return false;
 665         } else if (potentialTargetNode.get() instanceof UnknownSchemaNodeBuilder) {
 666             LOG.warn("Error in augment parsing: unsupported augment target: {}", potentialTargetNode.get());
 667             return true;
 668         }
 669         SchemaNodeBuilder targetNode = potentialTargetNode.get();
 670         fillAugmentTarget(augment, targetNode);
 671         Preconditions.checkState(targetNode instanceof AugmentationTargetBuilder,
 672                 "Node refered by augmentation must be valid augmentation target");
 673         ((AugmentationTargetBuilder) targetNode).addAugmentation(augment);
 674         augment.setResolved(true);
 675         return true;
 676     }
 677
 678     public static IdentitySchemaNodeBuilder findBaseIdentity(final ModuleBuilder module, final String baseString,
 679             final int line) {
 680
 681         // FIXME: optimize indexOf() away?
 682         if (baseString.indexOf(':') != -1) {
 683             final Iterator<String> it = COLON_SPLITTER.split(baseString).iterator();
 684             final String prefix = it.next();
 685             final String name = it.next();
 686
 687             if (it.hasNext()) {
 688                 throw new YangParseException(module.getName(), line, "Failed to parse identityref base: " + baseString);
 689             }
 690
 691             ModuleBuilder dependentModule = getModuleByPrefix(module, prefix);
 692             if (dependentModule == null) {
 693                 return null;
 694             }
 695
 696             return findIdentity(dependentModule.getAddedIdentities(), name);
 697         } else {
 698             return findIdentity(module.getAddedIdentities(), baseString);
 699         }
 700     }
 701
 702     public static IdentitySchemaNodeBuilder findIdentity(final Set<IdentitySchemaNodeBuilder> identities,
 703             final String name) {
 704         for (IdentitySchemaNodeBuilder identity : identities) {
 705             if (identity.getQName().getLocalName().equals(name)) {
 706                 return identity;
 707             }
 708         }
 709         return null;
 710     }
 711
 712     /**
 713      * Get module in which this node is defined.
 714      *
 715      * @param node node
 716      * @return builder of module where this node is defined
 717      */
 718     public static ModuleBuilder getParentModule(final Builder node) {
 719         if (node instanceof ModuleBuilder) {
 720             return (ModuleBuilder) node;
 721         }
 722         Builder parent = node.getParent();
 723         while (!(parent instanceof ModuleBuilder)) {
 724             parent = parent.getParent();
 725         }
 726         ModuleBuilder parentModule = (ModuleBuilder) parent;
 727         if (parentModule.isSubmodule()) {
 728             parentModule = parentModule.getParent();
 729         }
 730         return parentModule;
 731     }
 732
 733     public static Set<DataSchemaNodeBuilder> wrapChildNodes(final String moduleName, final int line,
 734             final Collection<DataSchemaNode> nodes, final SchemaPath parentPath, final QName parentQName) {
 735         Set<DataSchemaNodeBuilder> result = new LinkedHashSet<>(nodes.size());
 736
 737         for (DataSchemaNode node : nodes) {
 738             QName qname = QName.create(parentQName, node.getQName().getLocalName());
 739             DataSchemaNodeBuilder wrapped = wrapChildNode(moduleName, line, node, parentPath, qname);
 740             result.add(wrapped);
 741         }
 742         return result;
 743     }
 744
 745     public static DataSchemaNodeBuilder wrapChildNode(final String moduleName, final int line,
 746             final DataSchemaNode node, final SchemaPath parentPath, final QName qname) {
 747
 748         final SchemaPath schemaPath = parentPath.createChild(qname);
 749
 750         if (node instanceof AnyXmlSchemaNode) {
 751             return new AnyXmlBuilder(moduleName, line, qname, schemaPath, (AnyXmlSchemaNode) node);
 752         } else if (node instanceof ChoiceSchemaNode) {
 753             return new ChoiceBuilder(moduleName, line, qname, schemaPath, (ChoiceSchemaNode) node);
 754         } else if (node instanceof ContainerSchemaNode) {
 755             return new ContainerSchemaNodeBuilder(moduleName, line, qname, schemaPath, (ContainerSchemaNode) node);
 756         } else if (node instanceof LeafSchemaNode) {
 757             return new LeafSchemaNodeBuilder(moduleName, line, qname, schemaPath, (LeafSchemaNode) node);
 758         } else if (node instanceof LeafListSchemaNode) {
 759             return new LeafListSchemaNodeBuilder(moduleName, line, qname, schemaPath, (LeafListSchemaNode) node);
 760         } else if (node instanceof ListSchemaNode) {
 761             return new ListSchemaNodeBuilder(moduleName, line, qname, schemaPath, (ListSchemaNode) node);
 762         } else if (node instanceof ChoiceCaseNode) {
 763             return new ChoiceCaseBuilder(moduleName, line, qname, schemaPath, (ChoiceCaseNode) node);
 764         } else {
 765             throw new YangParseException(moduleName, line, "Failed to copy node: Unknown type of DataSchemaNode: "
 766                     + node);
 767         }
 768     }
 769
 770     public static Set<GroupingBuilder> wrapGroupings(final String moduleName, final int line,
 771             final Set<GroupingDefinition> nodes, final SchemaPath parentPath, final QName parentQName) {
 772         Set<GroupingBuilder> result = new HashSet<>();
 773         for (GroupingDefinition node : nodes) {
 774             QName qname = QName.create(parentQName, node.getQName().getLocalName());
 775             SchemaPath schemaPath = parentPath.createChild(qname);
 776             result.add(new GroupingBuilderImpl(moduleName, line, qname, schemaPath, node));
 777         }
 778         return result;
 779     }
 780
 781     public static Set<TypeDefinitionBuilder> wrapTypedefs(final String moduleName, final int line,
 782             final DataNodeContainer dataNode, final SchemaPath parentPath, final QName parentQName) {
 783         Set<TypeDefinition<?>> nodes = dataNode.getTypeDefinitions();
 784         Set<TypeDefinitionBuilder> result = new HashSet<>();
 785         for (TypeDefinition<?> node : nodes) {
 786             QName qname = QName.create(parentQName, node.getQName().getLocalName());
 787             SchemaPath schemaPath = parentPath.createChild(qname);
 788             result.add(new TypeDefinitionBuilderImpl(moduleName, line, qname, schemaPath, (ExtendedType) node));
 789         }
 790         return result;
 791     }
 792
 793     public static List<UnknownSchemaNodeBuilderImpl> wrapUnknownNodes(final String moduleName, final int line,
 794             final List<UnknownSchemaNode> nodes, final SchemaPath parentPath, final QName parentQName) {
 795         List<UnknownSchemaNodeBuilderImpl> result = new ArrayList<>();
 796         for (UnknownSchemaNode node : nodes) {
 797             QName qname = QName.create(parentQName, node.getQName().getLocalName());
 798             SchemaPath schemaPath = parentPath.createChild(qname);
 799             result.add(new UnknownSchemaNodeBuilderImpl(moduleName, line, qname, schemaPath, node));
 800         }
 801         return result;
 802     }
 803
 804     private static final class ByteSourceImpl extends ByteSource {
 805         private final String toString;
 806         private final byte[] data;
 807
 808         private ByteSourceImpl(final InputStream input) throws IOException {
 809             toString = input.toString();
 810             data = ByteStreams.toByteArray(input);
 811         }
 812
 813         @Override
 814         public InputStream openStream() throws IOException {
 815             return new NamedByteArrayInputStream(data, toString);
 816         }
 817     }
 818
 819     public static ModuleBuilder getModuleByPrefix(final ModuleBuilder module, final String prefix) {
 820         if (prefix == null || prefix.isEmpty() || prefix.equals(module.getPrefix())) {
 821             return module;
 822         } else {
 823             return module.getImportedModule(prefix);
 824         }
 825     }
 826
 827     public static ModuleBuilder findModule(final QName qname, final Map<URI, NavigableMap<Date, ModuleBuilder>> modules) {
 828         NavigableMap<Date, ModuleBuilder> map = modules.get(qname.getNamespace());
 829         if (map == null) {
 830             return null;
 831         }
 832         if (qname.getRevision() == null) {
 833             return map.lastEntry().getValue();
 834         }
 835         return map.get(qname.getRevision());
 836     }
 837
 838     public static Map<String, NavigableMap<Date, URI>> createYangNamespaceContext(
 839             final Collection<? extends ParseTree> modules, final Optional<SchemaContext> context) {
 840         Map<String, NavigableMap<Date, URI>> namespaceContext = new HashMap<>();
 841         Set<Submodule_stmtContext> submodules = new HashSet<>();
 842         // first read ParseTree collection and separate modules and submodules
 843         for (ParseTree module : modules) {
 844             for (int i = 0; i < module.getChildCount(); i++) {
 845                 ParseTree moduleTree = module.getChild(i);
 846                 if (moduleTree instanceof Submodule_stmtContext) {
 847                     // put submodule context to separate collection
 848                     submodules.add((Submodule_stmtContext) moduleTree);
 849                 } else if (moduleTree instanceof Module_stmtContext) {
 850                     // get name, revision and namespace from module
 851                     Module_stmtContext moduleCtx = (Module_stmtContext) moduleTree;
 852                     final String moduleName = ParserListenerUtils.stringFromNode(moduleCtx);
 853                     Date rev = null;
 854                     URI namespace = null;
 855                     for (int j = 0; j < moduleCtx.getChildCount(); j++) {
 856                         ParseTree moduleCtxChildTree = moduleCtx.getChild(j);
 857                         if (moduleCtxChildTree instanceof Revision_stmtsContext) {
 858                             String revisionDateStr = YangModelDependencyInfo
 859                                     .getLatestRevision((Revision_stmtsContext) moduleCtxChildTree);
 860                             if (revisionDateStr == null) {
 861                                 rev = new Date(0);
 862                             } else {
 863                                 rev = QName.parseRevision(revisionDateStr);
 864                             }
 865                         }
 866                         if (moduleCtxChildTree instanceof Module_header_stmtsContext) {
 867                             Module_header_stmtsContext headerCtx = (Module_header_stmtsContext) moduleCtxChildTree;
 868                             for (int k = 0; k < headerCtx.getChildCount(); k++) {
 869                                 ParseTree ctx = headerCtx.getChild(k);
 870                                 if (ctx instanceof Namespace_stmtContext) {
 871                                     final String namespaceStr = ParserListenerUtils.stringFromNode(ctx);
 872                                     namespace = URI.create(namespaceStr);
 873                                     break;
 874                                 }
 875                             }
 876                         }
 877                     }
 878                     // update namespaceContext
 879                     NavigableMap<Date, URI> revToNs = namespaceContext.get(moduleName);
 880                     if (revToNs == null) {
 881                         revToNs = new TreeMap<>();
 882                         revToNs.put(rev, namespace);
 883                         namespaceContext.put(moduleName, revToNs);
 884                     }
 885                     revToNs.put(rev, namespace);
 886                 }
 887             }
 888         }
 889         // after all ParseTree-s are parsed update namespaceContext with modules
 890         // from SchemaContext
 891         if (context.isPresent()) {
 892             for (Module module : context.get().getModules()) {
 893                 NavigableMap<Date, URI> revToNs = namespaceContext.get(module.getName());
 894                 if (revToNs == null) {
 895                     revToNs = new TreeMap<>();
 896                     revToNs.put(module.getRevision(), module.getNamespace());
 897                     namespaceContext.put(module.getName(), revToNs);
 898                 }
 899                 revToNs.put(module.getRevision(), module.getNamespace());
 900             }
 901         }
 902         // when all modules are processed, traverse submodules and update
 903         // namespaceContext with mapping for submodules
 904         for (Submodule_stmtContext submodule : submodules) {
 905             final String moduleName = ParserListenerUtils.stringFromNode(submodule);
 906             for (int i = 0; i < submodule.getChildCount(); i++) {
 907                 ParseTree subHeaderCtx = submodule.getChild(i);
 908                 if (subHeaderCtx instanceof Submodule_header_stmtsContext) {
 909                     for (int j = 0; j < subHeaderCtx.getChildCount(); j++) {
 910                         ParseTree belongsCtx = subHeaderCtx.getChild(j);
 911                         if (belongsCtx instanceof Belongs_to_stmtContext) {
 912                             final String belongsTo = ParserListenerUtils.stringFromNode(belongsCtx);
 913                             NavigableMap<Date, URI> ns = namespaceContext.get(belongsTo);
 914                             if (ns == null) {
 915                                 throw new YangParseException(moduleName, submodule.getStart().getLine(), String.format(
 916                                         "Unresolved belongs-to statement: %s", belongsTo));
 917                             }
 918                             // submodule get namespace and revision from module
 919                             NavigableMap<Date, URI> subNs = new TreeMap<>();
 920                             subNs.put(ns.firstKey(), ns.firstEntry().getValue());
 921                             namespaceContext.put(moduleName, subNs);
 922                         }
 923                     }
 924                 }
 925             }
 926         }
 927         return namespaceContext;
 928     }
 929
 930 }