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

   1 /*
   2  * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
   3  * This program and the accompanying materials are made available under the
   4  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   5  * and is available at http://www.eclipse.org/legal/epl-v10.html
   6  */
   7 package org.opendaylight.yangtools.yang.parser.impl;
   8
   9 import static com.google.common.base.Preconditions.checkNotNull;
  10 import static org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils.fillAugmentTarget;
  11 import static org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils.findBaseIdentity;
  12 import static org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils.findModuleFromContext;
  13 import static org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils.findSchemaNode;
  14 import static org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils.findSchemaNodeInModule;
  15 import static org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils.processAugmentation;
  16 import static org.opendaylight.yangtools.yang.parser.builder.impl.TypeUtils.resolveType;
  17 import static org.opendaylight.yangtools.yang.parser.builder.impl.TypeUtils.resolveTypeUnion;
  18 import com.google.common.base.Optional;
  19 import com.google.common.base.Preconditions;
  20 import com.google.common.collect.HashBiMap;
  21 import com.google.common.io.ByteSource;
  22 import java.io.File;
  23 import java.io.IOException;
  24 import java.io.InputStream;
  25 import java.net.URI;
  26 import java.util.ArrayList;
  27 import java.util.Collection;
  28 import java.util.Collections;
  29 import java.util.Date;
  30 import java.util.HashMap;
  31 import java.util.HashSet;
  32 import java.util.LinkedHashMap;
  33 import java.util.LinkedHashSet;
  34 import java.util.List;
  35 import java.util.Map;
  36 import java.util.Set;
  37 import java.util.TreeMap;
  38 import javax.annotation.concurrent.Immutable;
  39 import org.antlr.v4.runtime.ANTLRInputStream;
  40 import org.antlr.v4.runtime.CommonTokenStream;
  41 import org.antlr.v4.runtime.tree.ParseTree;
  42 import org.antlr.v4.runtime.tree.ParseTreeWalker;
  43 import org.opendaylight.yangtools.antlrv4.code.gen.YangLexer;
  44 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser;
  45 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser.YangContext;
  46 import org.opendaylight.yangtools.yang.common.QName;
  47 import org.opendaylight.yangtools.yang.common.QNameModule;
  48 import org.opendaylight.yangtools.yang.model.api.ChoiceCaseNode;
  49 import org.opendaylight.yangtools.yang.model.api.ChoiceSchemaNode;
  50 import org.opendaylight.yangtools.yang.model.api.ContainerSchemaNode;
  51 import org.opendaylight.yangtools.yang.model.api.DataSchemaNode;
  52 import org.opendaylight.yangtools.yang.model.api.ExtensionDefinition;
  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.ModuleIdentifier;
  56 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  57 import org.opendaylight.yangtools.yang.model.api.SchemaContext;
  58 import org.opendaylight.yangtools.yang.model.api.SchemaNode;
  59 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  60 import org.opendaylight.yangtools.yang.model.parser.api.YangContextParser;
  61 import org.opendaylight.yangtools.yang.model.parser.api.YangSyntaxErrorException;
  62 import org.opendaylight.yangtools.yang.parser.builder.api.AugmentationSchemaBuilder;
  63 import org.opendaylight.yangtools.yang.parser.builder.api.AugmentationTargetBuilder;
  64 import org.opendaylight.yangtools.yang.parser.builder.api.Builder;
  65 import org.opendaylight.yangtools.yang.parser.builder.api.DataNodeContainerBuilder;
  66 import org.opendaylight.yangtools.yang.parser.builder.api.DataSchemaNodeBuilder;
  67 import org.opendaylight.yangtools.yang.parser.builder.api.ExtensionBuilder;
  68 import org.opendaylight.yangtools.yang.parser.builder.api.GroupingBuilder;
  69 import org.opendaylight.yangtools.yang.parser.builder.api.SchemaNodeBuilder;
  70 import org.opendaylight.yangtools.yang.parser.builder.api.TypeAwareBuilder;
  71 import org.opendaylight.yangtools.yang.parser.builder.api.UnknownSchemaNodeBuilder;
  72 import org.opendaylight.yangtools.yang.parser.builder.api.UsesNodeBuilder;
  73 import org.opendaylight.yangtools.yang.parser.builder.impl.BuilderUtils;
  74 import org.opendaylight.yangtools.yang.parser.builder.impl.ChoiceBuilder;
  75 import org.opendaylight.yangtools.yang.parser.builder.impl.ChoiceCaseBuilder;
  76 import org.opendaylight.yangtools.yang.parser.builder.impl.GroupingUtils;
  77 import org.opendaylight.yangtools.yang.parser.builder.impl.IdentitySchemaNodeBuilder;
  78 import org.opendaylight.yangtools.yang.parser.builder.impl.IdentityrefTypeBuilder;
  79 import org.opendaylight.yangtools.yang.parser.builder.impl.ModuleBuilder;
  80 import org.opendaylight.yangtools.yang.parser.builder.impl.ModuleImpl;
  81 import org.opendaylight.yangtools.yang.parser.builder.impl.UnionTypeBuilder;
  82 import org.opendaylight.yangtools.yang.parser.builder.util.Comparators;
  83 import org.opendaylight.yangtools.yang.parser.util.ModuleDependencySort;
  84 import org.opendaylight.yangtools.yang.parser.util.NamedByteArrayInputStream;
  85 import org.opendaylight.yangtools.yang.parser.util.NamedFileInputStream;
  86 import org.opendaylight.yangtools.yang.parser.util.NamedInputStream;
  87 import org.opendaylight.yangtools.yang.parser.util.YangParseException;
  88 import org.slf4j.Logger;
  89 import org.slf4j.LoggerFactory;
  90
  91 @Immutable
  92 public final class YangParserImpl implements YangContextParser {
  93     private static final Logger LOG = LoggerFactory.getLogger(YangParserImpl.class);
  94     private static final YangParserImpl INSTANCE = new YangParserImpl();
  95
  96     public static YangParserImpl getInstance() {
  97         return INSTANCE;
  98     }
  99
 100     @Override
 101     @Deprecated
 102     public Set<Module> parseYangModels(final File yangFile, final File directory) {
 103         try {
 104             return parseFile(yangFile, directory).getModules();
 105         } catch (IOException | YangSyntaxErrorException e) {
 106             throw new YangParseException("Failed to parse yang data", e);
 107         }
 108     }
 109
 110     @Override
 111     public SchemaContext parseFile(final File yangFile, final File directory) throws IOException, YangSyntaxErrorException {
 112         Preconditions.checkState(yangFile.exists(), yangFile + " does not exists");
 113         Preconditions.checkState(directory.exists(), directory + " does not exists");
 114         Preconditions.checkState(directory.isDirectory(), directory + " is not a directory");
 115
 116         final String yangFileName = yangFile.getName();
 117         final String[] fileList = checkNotNull(directory.list(), directory + " not found or is not a directory");
 118
 119         Map<ByteSource, File> sourceToFile = new LinkedHashMap<>();
 120         ByteSource mainFileSource = BuilderUtils.fileToByteSource(yangFile);
 121         sourceToFile.put(mainFileSource, yangFile);
 122
 123         for (String fileName : fileList) {
 124             if (fileName.equals(yangFileName)) {
 125                 continue;
 126             }
 127             File dependency = new File(directory, fileName);
 128             if (dependency.isFile()) {
 129                 sourceToFile.put(BuilderUtils.fileToByteSource(dependency), dependency);
 130             }
 131         }
 132
 133         Map<ByteSource, ModuleBuilder> sourceToBuilder = parseSourcesToBuilders(sourceToFile.keySet(), null);
 134         ModuleBuilder main = sourceToBuilder.get(mainFileSource);
 135
 136         List<ModuleBuilder> moduleBuilders = new ArrayList<>();
 137         moduleBuilders.add(main);
 138         filterImports(main, new ArrayList<>(sourceToBuilder.values()), moduleBuilders);
 139         Collection<ModuleBuilder> resolved = resolveSubmodules(moduleBuilders);
 140
 141         // module builders sorted by dependencies
 142         List<ModuleBuilder> sortedBuilders = ModuleDependencySort.sort(resolved);
 143         LinkedHashMap<URI, TreeMap<Date, ModuleBuilder>> modules = resolveModulesWithImports(sortedBuilders, null);
 144         Collection<Module> unsorted = build(modules).values();
 145         Set<Module> result = new LinkedHashSet<>(
 146                 ModuleDependencySort.sort(unsorted.toArray(new Module[unsorted.size()])));
 147         return resolveSchemaContext(result);
 148     }
 149
 150     @Override
 151     @Deprecated
 152     public Set<Module> parseYangModels(final List<File> yangFiles) {
 153         return parseFiles(yangFiles).getModules();
 154     }
 155
 156     @Override
 157     public SchemaContext parseFiles(final Collection<File> yangFiles) {
 158         Collection<Module> unsorted = parseYangModelsMapped(yangFiles).values();
 159         Set<Module> sorted = new LinkedHashSet<>(
 160                 ModuleDependencySort.sort(unsorted.toArray(new Module[unsorted.size()])));
 161         return resolveSchemaContext(sorted);
 162     }
 163
 164     @Override
 165     @Deprecated
 166     public Set<Module> parseYangModels(final List<File> yangFiles, final SchemaContext context) {
 167         try {
 168             return parseFiles(yangFiles, context).getModules();
 169         } catch (IOException | YangSyntaxErrorException e) {
 170             throw new YangParseException("Failed to parse yang data", e);
 171         }
 172     }
 173
 174     @Override
 175     public SchemaContext parseFiles(final Collection<File> yangFiles, final SchemaContext context) throws IOException,
 176     YangSyntaxErrorException {
 177         if (yangFiles == null) {
 178             return resolveSchemaContext(Collections.<Module> emptySet());
 179         }
 180
 181         Collection<ByteSource> sources = BuilderUtils.filesToByteSources(yangFiles);
 182         return parseSources(sources, context);
 183     }
 184
 185     @Override
 186     @Deprecated
 187     public Set<Module> parseYangModelsFromStreams(final List<InputStream> yangModelStreams) {
 188         try {
 189             Collection<ByteSource> sources = BuilderUtils.streamsToByteSources(yangModelStreams);
 190             return parseSources(sources).getModules();
 191         } catch (IOException | YangSyntaxErrorException e) {
 192             throw new YangParseException("Failed to parse yang data", e);
 193         }
 194     }
 195
 196     @Override
 197     public SchemaContext parseSources(final Collection<ByteSource> sources) throws IOException,YangSyntaxErrorException {
 198         return assembleContext(parseYangModelSources(sources, null).values());
 199     }
 200
 201     @Override
 202     @Deprecated
 203     public Set<Module> parseYangModelsFromStreams(final List<InputStream> yangModelStreams, final SchemaContext context) {
 204         try {
 205             Collection<ByteSource> sources = BuilderUtils.streamsToByteSources(yangModelStreams);
 206             return parseSources(sources, context).getModules();
 207         } catch (IOException | YangSyntaxErrorException e) {
 208             throw new YangParseException("Failed to parse yang data", e);
 209         }
 210     }
 211
 212     @Override
 213     public SchemaContext parseSources(final Collection<ByteSource> sources, final SchemaContext context)
 214             throws IOException, YangSyntaxErrorException {
 215         if (sources == null) {
 216             return resolveSchemaContext(Collections.<Module> emptySet());
 217         }
 218
 219         final List<ModuleBuilder> sorted = resolveModuleBuilders(sources, context);
 220         final Map<URI, TreeMap<Date, ModuleBuilder>> modules = resolveModulesWithImports(sorted, context);
 221
 222         final Set<Module> unsorted = new LinkedHashSet<>(build(modules).values());
 223         if (context != null) {
 224             for (Module m : context.getModules()) {
 225                 if (!unsorted.contains(m)) {
 226                     unsorted.add(m);
 227                 }
 228             }
 229         }
 230         Set<Module> result = new LinkedHashSet<>(
 231                 ModuleDependencySort.sort(unsorted.toArray(new Module[unsorted.size()])));
 232         return resolveSchemaContext(result);
 233     }
 234
 235     private static LinkedHashMap<URI, TreeMap<Date, ModuleBuilder>> resolveModulesWithImports(final List<ModuleBuilder> sorted,
 236             final SchemaContext context) {
 237         final LinkedHashMap<URI, TreeMap<Date, ModuleBuilder>> modules = orderModules(sorted);
 238         for (ModuleBuilder module : sorted) {
 239             if (module != null) {
 240                 for (ModuleImport imp : module.getImports().values()) {
 241                     String prefix = imp.getPrefix();
 242                     ModuleBuilder targetModule = BuilderUtils.findModuleFromBuilders(imp, sorted);
 243                     if (targetModule == null) {
 244                         Module result = findModuleFromContext(context, module, prefix, 0);
 245                         targetModule = new ModuleBuilder(result);
 246                         TreeMap<Date, ModuleBuilder> map = modules.get(targetModule.getNamespace());
 247                         if (map == null) {
 248                             map = new TreeMap<>();
 249                             map.put(targetModule.getRevision(), targetModule);
 250                             modules.put(targetModule.getNamespace(), map);
 251                         } else {
 252                             map.put(targetModule.getRevision(), targetModule);
 253                         }
 254                     }
 255                     module.addImportedModule(prefix, targetModule);
 256                 }
 257             }
 258         }
 259         return modules;
 260     }
 261
 262     @Override
 263     public Map<File, Module> parseYangModelsMapped(final Collection<File> yangFiles) {
 264         if (yangFiles == null || yangFiles.isEmpty()) {
 265             return Collections.emptyMap();
 266         }
 267
 268         Map<ByteSource, File> byteSourceToFile = new HashMap<>();
 269         for (final File file : yangFiles) {
 270             ByteSource source = new ByteSource() {
 271                 @Override
 272                 public InputStream openStream() throws IOException {
 273                     return new NamedFileInputStream(file, file.getPath());
 274                 }
 275             };
 276             byteSourceToFile.put(source, file);
 277         }
 278
 279         Map<ByteSource, Module> byteSourceToModule;
 280         try {
 281             byteSourceToModule = parseYangModelSources(byteSourceToFile.keySet(), null);
 282         } catch (IOException | YangSyntaxErrorException e) {
 283             throw new YangParseException("Failed to parse yang data", e);
 284         }
 285         Map<File, Module> result = new LinkedHashMap<>();
 286         for (Map.Entry<ByteSource, Module> entry : byteSourceToModule.entrySet()) {
 287             result.put(byteSourceToFile.get(entry.getKey()), entry.getValue());
 288         }
 289         return result;
 290     }
 291
 292     @Override
 293     public Map<InputStream, Module> parseYangModelsFromStreamsMapped(final Collection<InputStream> yangModelStreams) {
 294         if (yangModelStreams == null || yangModelStreams.isEmpty()) {
 295             return Collections.emptyMap();
 296         }
 297
 298         Map<ByteSource, InputStream> sourceToStream = new HashMap<>();
 299         for (final InputStream stream : yangModelStreams) {
 300             ByteSource source = new ByteSource() {
 301                 @Override
 302                 public InputStream openStream() throws IOException {
 303                     return NamedByteArrayInputStream.create(stream);
 304                 }
 305             };
 306             sourceToStream.put(source, stream);
 307         }
 308
 309         Map<ByteSource, Module> sourceToModule;
 310         try {
 311             sourceToModule = parseYangModelSources(sourceToStream.keySet(), null);
 312         } catch (IOException | YangSyntaxErrorException e) {
 313             throw new YangParseException("Failed to parse yang data", e);
 314         }
 315         Map<InputStream, Module> result = new LinkedHashMap<>();
 316         for (Map.Entry<ByteSource, Module> entry : sourceToModule.entrySet()) {
 317             result.put(sourceToStream.get(entry.getKey()), entry.getValue());
 318         }
 319         return result;
 320     }
 321
 322     @Override
 323     public SchemaContext resolveSchemaContext(final Set<Module> modules) {
 324         // after merging parse method with this one, add support for getting
 325         // submodule sources.
 326         Map<ModuleIdentifier, String> identifiersToSources = new HashMap<>();
 327         for (Module module : modules) {
 328             ModuleImpl moduleImpl = (ModuleImpl) module;
 329             identifiersToSources.put(module, moduleImpl.getSource());
 330         }
 331         return new SchemaContextImpl(modules, identifiersToSources);
 332     }
 333
 334     public Collection<Module> buildModules(final Collection<ModuleBuilder> builders) {
 335         Collection<ModuleBuilder> unsorted = resolveSubmodules(builders);
 336         List<ModuleBuilder> sorted = ModuleDependencySort.sort(unsorted);
 337         Map<URI, TreeMap<Date, ModuleBuilder>> modules = resolveModulesWithImports(sorted, null);
 338         Map<ModuleBuilder, Module> builderToModule = build(modules);
 339         return builderToModule.values();
 340     }
 341
 342     public SchemaContext assembleContext(final Collection<Module> modules) {
 343         final Set<Module> sorted = new LinkedHashSet<>(
 344                 ModuleDependencySort.sort(modules.toArray(new Module[modules.size()])));
 345         return resolveSchemaContext(sorted);
 346     }
 347
 348     private Map<ByteSource, Module> parseYangModelSources(final Collection<ByteSource> sources, final SchemaContext context) throws IOException, YangSyntaxErrorException {
 349         if (sources == null || sources.isEmpty()) {
 350             return Collections.emptyMap();
 351         }
 352
 353         Map<ByteSource, ModuleBuilder> sourceToBuilder = resolveSources(sources, context);
 354         // sort and check for duplicates
 355         List<ModuleBuilder> sorted = ModuleDependencySort.sort(sourceToBuilder.values());
 356         Map<URI, TreeMap<Date, ModuleBuilder>> modules = resolveModulesWithImports(sorted, null);
 357         Map<ModuleBuilder, Module> builderToModule = build(modules);
 358         Map<ModuleBuilder, ByteSource> builderToSource = HashBiMap.create(sourceToBuilder).inverse();
 359         sorted = ModuleDependencySort.sort(builderToModule.keySet());
 360
 361         Map<ByteSource, Module> result = new LinkedHashMap<>();
 362         for (ModuleBuilder moduleBuilder : sorted) {
 363             Module value = checkNotNull(builderToModule.get(moduleBuilder), "Cannot get module for %s", moduleBuilder);
 364             result.put(builderToSource.get(moduleBuilder), value);
 365         }
 366
 367         return result;
 368     }
 369
 370     /**
 371      * Parse streams and resolve submodules.
 372      *
 373      * @param streams
 374      *            collection of streams to parse
 375      * @return map, where key is source stream and value is module builder
 376      *         parsed from stream
 377      * @throws YangSyntaxErrorException
 378      */
 379     // TODO: remove ByteSource result after removing YangModelParser
 380     private Map<ByteSource, ModuleBuilder> resolveSources(final Collection<ByteSource> streams, final SchemaContext context) throws IOException, YangSyntaxErrorException {
 381         Map<ByteSource, ModuleBuilder> builders = parseSourcesToBuilders(streams, context);
 382         return resolveSubmodules(builders);
 383     }
 384
 385     private Map<ByteSource, ModuleBuilder> parseSourcesToBuilders(final Collection<ByteSource> sources,
 386             final SchemaContext context) throws IOException, YangSyntaxErrorException {
 387         final ParseTreeWalker walker = new ParseTreeWalker();
 388         final Map<ByteSource, ParseTree> sourceToTree = parseYangSources(sources);
 389         final Map<ByteSource, ModuleBuilder> sourceToBuilder = new LinkedHashMap<>();
 390
 391         // validate yang
 392         new YangModelBasicValidator(walker).validate(sourceToTree.values());
 393
 394         Map<String, TreeMap<Date, URI>> namespaceContext = BuilderUtils.createYangNamespaceContext(
 395                 sourceToTree.values(), Optional.fromNullable(context));
 396         YangParserListenerImpl yangModelParser;
 397         for (Map.Entry<ByteSource, ParseTree> entry : sourceToTree.entrySet()) {
 398             ByteSource source = entry.getKey();
 399             String path = null; // TODO refactor to Optional
 400             // TODO refactor so that path can be retrieved without opening
 401             // stream: NamedInputStream -> NamedByteSource ?
 402             try (InputStream stream = source.openStream()) {
 403                 if (stream instanceof NamedInputStream) {
 404                     path = stream.toString();
 405                 }
 406             }
 407             yangModelParser = new YangParserListenerImpl(namespaceContext, path);
 408             walker.walk(yangModelParser, entry.getValue());
 409             ModuleBuilder moduleBuilder = yangModelParser.getModuleBuilder();
 410             moduleBuilder.setSource(source);
 411             sourceToBuilder.put(source, moduleBuilder);
 412         }
 413         return sourceToBuilder;
 414     }
 415
 416     private Map<ByteSource, ModuleBuilder> resolveSubmodules(final Map<ByteSource, ModuleBuilder> builders) {
 417         Map<ByteSource, ModuleBuilder> modules = new HashMap<>();
 418         Map<String, TreeMap<Date, ModuleBuilder>> submodules = new HashMap<>();
 419         for (Map.Entry<ByteSource, ModuleBuilder> entry : builders.entrySet()) {
 420             ModuleBuilder builder = entry.getValue();
 421             if (builder.isSubmodule()) {
 422                 String submoduleName = builder.getName();
 423                 TreeMap<Date, ModuleBuilder> map = submodules.get(submoduleName);
 424                 if (map == null) {
 425                     map = new TreeMap<>();
 426                     map.put(builder.getRevision(), builder);
 427                     submodules.put(submoduleName, map);
 428                 } else {
 429                     map.put(builder.getRevision(), builder);
 430                 }
 431             } else {
 432                 modules.put(entry.getKey(), builder);
 433             }
 434         }
 435
 436         for (ModuleBuilder module : modules.values()) {
 437             resolveSubmodules(module, submodules);
 438         }
 439
 440         return modules;
 441     }
 442
 443     private Collection<ModuleBuilder> resolveSubmodules(final Collection<ModuleBuilder> builders) {
 444         Collection<ModuleBuilder> modules = new HashSet<>();
 445         Map<String, TreeMap<Date, ModuleBuilder>> submodules = new HashMap<>();
 446         for (ModuleBuilder builder : builders) {
 447             if (builder.isSubmodule()) {
 448                 String submoduleName = builder.getName();
 449                 TreeMap<Date, ModuleBuilder> map = submodules.get(submoduleName);
 450                 if (map == null) {
 451                     map = new TreeMap<>();
 452                     map.put(builder.getRevision(), builder);
 453                     submodules.put(submoduleName, map);
 454                 } else {
 455                     map.put(builder.getRevision(), builder);
 456                 }
 457             } else {
 458                 modules.add(builder);
 459             }
 460         }
 461
 462         for (ModuleBuilder module : modules) {
 463             resolveSubmodules(module, submodules);
 464         }
 465
 466         return modules;
 467     }
 468
 469     /**
 470      * Traverse collection of builders, find builders representing submodule and
 471      * add this submodule to its parent module.
 472      *
 473      * @param module
 474      *            current module
 475      * @param submodules
 476      *            collection all loaded submodules
 477      * @return collection of module builders with resolved submodules
 478      */
 479     private void resolveSubmodules(final ModuleBuilder module,
 480             final Map<String, TreeMap<Date, ModuleBuilder>> submodules) {
 481         Map<String, Date> includes = module.getIncludedModules();
 482         for (Map.Entry<String, Date> entry : includes.entrySet()) {
 483             TreeMap<Date, ModuleBuilder> subs = submodules.get(entry.getKey());
 484             if (subs == null) {
 485                 throw new YangParseException("Failed to find references submodule " + entry.getKey() + " in module "
 486                         + module.getName());
 487             }
 488             Date rev = entry.getValue();
 489             ModuleBuilder submodule;
 490             if (rev == null) {
 491                 submodule = subs.lastEntry().getValue();
 492             } else {
 493                 submodule = subs.get(rev);
 494                 // FIXME an exception should be thrown after issue with
 495                 // submodule's revisions and namespaces will be resolved
 496                 if (submodule == null) {
 497                     submodule = subs.lastEntry().getValue();
 498                 }
 499             }
 500
 501             if (submodule.getIncludedModules().size() > 0) {
 502                 resolveSubmodules(submodule, submodules);
 503             }
 504             addSubmoduleToModule(submodule, module);
 505         }
 506     }
 507
 508     private void addSubmoduleToModule(final ModuleBuilder submodule, final ModuleBuilder module) {
 509         module.addSubmodule(submodule);
 510         submodule.setParent(module);
 511         module.getDirtyNodes().addAll(submodule.getDirtyNodes());
 512         module.getImports().putAll(submodule.getImports());
 513         module.getAugments().addAll(submodule.getAugments());
 514         module.getAugmentBuilders().addAll(submodule.getAugmentBuilders());
 515         module.getAllAugments().addAll(submodule.getAllAugments());
 516         module.getChildNodeBuilders().addAll(submodule.getChildNodeBuilders());
 517         module.getChildNodes().putAll(submodule.getChildNodes());
 518         module.getGroupings().addAll(submodule.getGroupings());
 519         module.getGroupingBuilders().addAll(submodule.getGroupingBuilders());
 520         module.getTypeDefinitions().addAll(submodule.getTypeDefinitions());
 521         module.getTypeDefinitionBuilders().addAll(submodule.getTypeDefinitionBuilders());
 522         module.getUsesNodes().addAll(submodule.getUsesNodes());
 523         module.getUsesNodeBuilders().addAll(submodule.getUsesNodeBuilders());
 524         module.getAllGroupings().addAll(submodule.getAllGroupings());
 525         module.getAllUsesNodes().addAll(submodule.getAllUsesNodes());
 526         module.getRpcs().addAll(submodule.getRpcs());
 527         module.getAddedRpcs().addAll(submodule.getAddedRpcs());
 528         module.getNotifications().addAll(submodule.getNotifications());
 529         module.getAddedNotifications().addAll(submodule.getAddedNotifications());
 530         module.getIdentities().addAll(submodule.getIdentities());
 531         module.getAddedIdentities().addAll(submodule.getAddedIdentities());
 532         module.getFeatures().addAll(submodule.getFeatures());
 533         module.getAddedFeatures().addAll(submodule.getAddedFeatures());
 534         module.getDeviations().addAll(submodule.getDeviations());
 535         module.getDeviationBuilders().addAll(submodule.getDeviationBuilders());
 536         module.getExtensions().addAll(submodule.getExtensions());
 537         module.getAddedExtensions().addAll(submodule.getAddedExtensions());
 538         module.getUnknownNodes().addAll(submodule.getUnknownNodes());
 539         module.getAllUnknownNodes().addAll(submodule.getAllUnknownNodes());
 540     }
 541
 542     private List<ModuleBuilder> resolveModuleBuilders(final Collection<ByteSource> yangFileStreams,
 543             final SchemaContext context) throws IOException, YangSyntaxErrorException {
 544         Map<ByteSource, ModuleBuilder> parsedBuilders = resolveSources(yangFileStreams, context);
 545         ModuleBuilder[] builders = new ModuleBuilder[parsedBuilders.size()];
 546         parsedBuilders.values().toArray(builders);
 547
 548         // module dependency graph sorted
 549         List<ModuleBuilder> sorted;
 550         if (context == null) {
 551             sorted = ModuleDependencySort.sort(builders);
 552         } else {
 553             sorted = ModuleDependencySort.sortWithContext(context, builders);
 554         }
 555         return sorted;
 556     }
 557
 558     /**
 559      * Order modules by namespace and revision.
 560      *
 561      * @param modules
 562      *            topologically sorted modules
 563      * @return modules ordered by namespace and revision
 564      */
 565     private static LinkedHashMap<URI, TreeMap<Date, ModuleBuilder>> orderModules(final List<ModuleBuilder> modules) {
 566         final LinkedHashMap<URI, TreeMap<Date, ModuleBuilder>> result = new LinkedHashMap<>();
 567         for (final ModuleBuilder builder : modules) {
 568             if (builder == null) {
 569                 continue;
 570             }
 571
 572             URI ns = builder.getNamespace();
 573             Date rev = builder.getRevision();
 574             if (rev == null) {
 575                 rev = new Date(0);
 576             }
 577
 578             TreeMap<Date, ModuleBuilder> builderByRevision = result.get(ns);
 579             if (builderByRevision == null) {
 580                 builderByRevision = new TreeMap<>();
 581                 builderByRevision.put(rev, builder);
 582                 result.put(ns, builderByRevision);
 583             } else {
 584                 builderByRevision.put(rev, builder);
 585             }
 586
 587         }
 588         return result;
 589     }
 590
 591     /**
 592      * Find {@code main} dependencies from {@code other} and add them to
 593      * {@code filtered}.
 594      *
 595      * @param main
 596      *            main yang module
 597      * @param other
 598      *            all loaded modules
 599      * @param filtered
 600      *            collection to fill up
 601      */
 602     private void filterImports(final ModuleBuilder main, final Collection<ModuleBuilder> other,
 603             final Collection<ModuleBuilder> filtered) {
 604         Map<String, ModuleImport> imports = main.getImports();
 605
 606         // if this is submodule, add parent to filtered and pick its imports
 607         if (main.isSubmodule()) {
 608             TreeMap<Date, ModuleBuilder> dependencies = new TreeMap<>();
 609             for (ModuleBuilder mb : other) {
 610                 if (mb.getName().equals(main.getBelongsTo())) {
 611                     dependencies.put(mb.getRevision(), mb);
 612                 }
 613             }
 614             ModuleBuilder parent = dependencies.get(dependencies.firstKey());
 615             filtered.add(parent);
 616             imports.putAll(parent.getImports());
 617         }
 618
 619         for (ModuleImport mi : imports.values()) {
 620             for (ModuleBuilder builder : other) {
 621                 if (mi.getModuleName().equals(builder.getModuleName())) {
 622                     if (mi.getRevision() == null) {
 623                         if (!filtered.contains(builder)) {
 624                             filtered.add(builder);
 625                             filterImports(builder, other, filtered);
 626                         }
 627                     } else {
 628                         if (mi.getRevision().equals(builder.getRevision())) {
 629                             if (!filtered.contains(builder)) {
 630                                 filtered.add(builder);
 631                                 filterImports(builder, other, filtered);
 632                             }
 633                         }
 634                     }
 635                 }
 636             }
 637         }
 638     }
 639
 640     private Map<ByteSource, ParseTree> parseYangSources(final Collection<ByteSource> sources) throws IOException, YangSyntaxErrorException {
 641         final Map<ByteSource, ParseTree> trees = new HashMap<>();
 642         for (ByteSource source : sources) {
 643             try (InputStream stream = source.openStream()) {
 644                 trees.put(source, parseYangSource(stream));
 645             }
 646         }
 647         return trees;
 648     }
 649
 650     public static YangContext parseYangSource(final InputStream stream) throws IOException, YangSyntaxErrorException {
 651         final YangLexer lexer = new YangLexer(new ANTLRInputStream(stream));
 652         final CommonTokenStream tokens = new CommonTokenStream(lexer);
 653         final YangParser parser = new YangParser(tokens);
 654         parser.removeErrorListeners();
 655
 656         final YangErrorListener errorListener = new YangErrorListener();
 657         parser.addErrorListener(errorListener);
 658
 659         final YangContext result = parser.yang();
 660         errorListener.validate();
 661
 662         return result;
 663     }
 664
 665     /**
 666      * Mini parser: This parsing context does not validate full YANG module,
 667      * only parses header up to the revisions and imports.
 668      *
 669      * @see org.opendaylight.yangtools.yang.parser.impl.util.YangModelDependencyInfo
 670      */
 671     public static YangContext parseStreamWithoutErrorListeners(final InputStream yangStream) {
 672         YangContext result = null;
 673         try {
 674             final ANTLRInputStream input = new ANTLRInputStream(yangStream);
 675             final YangLexer lexer = new YangLexer(input);
 676             final CommonTokenStream tokens = new CommonTokenStream(lexer);
 677             final YangParser parser = new YangParser(tokens);
 678             parser.removeErrorListeners();
 679             result = parser.yang();
 680         } catch (IOException e) {
 681             LOG.warn("Exception while reading yang file: " + yangStream, e);
 682         }
 683         return result;
 684     }
 685
 686     /**
 687      * Creates builder-to-module map based on given modules. Method first
 688      * resolve unresolved type references, instantiate groupings through uses
 689      * statements and perform augmentation.
 690      *
 691      * Node resolving must be performed in following order:
 692      * <ol>
 693      * <li>
 694      * unresolved type references</li>
 695      * <li>
 696      * uses in groupings</li>
 697      * <li>
 698      * uses in other nodes</li>
 699      * <li>
 700      * augments</li>
 701      * </ol>
 702      *
 703      * @param modules
 704      *            all loaded modules
 705      * @return modules mapped on their builders
 706      */
 707     private Map<ModuleBuilder, Module> build(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
 708         resolveDirtyNodes(modules);
 709         resolveAugmentsTargetPath(modules);
 710         resolveUsesTargetGrouping(modules);
 711         resolveUsesForGroupings(modules);
 712         resolveUsesForNodes(modules);
 713         resolveAugments(modules);
 714         resolveIdentities(modules);
 715         checkChoiceCasesForDuplicityQNames(modules);
 716
 717         // build
 718         final Map<ModuleBuilder, Module> result = new LinkedHashMap<>();
 719         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 720             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 721                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 722                 final Module module = moduleBuilder.build();
 723                 result.put(moduleBuilder, module);
 724             }
 725         }
 726         return result;
 727     }
 728
 729     /**
 730      * Resolve all unresolved type references.
 731      *
 732      * @param modules
 733      *            all loaded modules
 734      */
 735     private void resolveDirtyNodes(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
 736         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 737             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 738                 final ModuleBuilder module = childEntry.getValue();
 739                 resolveUnknownNodes(modules, module);
 740                 resolveDirtyNodes(modules, module);
 741             }
 742         }
 743     }
 744
 745     /**
 746      * Search for dirty nodes (node which contains UnknownType) and resolve
 747      * unknown types.
 748      *
 749      * @param modules
 750      *            all available modules
 751      * @param module
 752      *            current module
 753      */
 754     private void resolveDirtyNodes(final Map<URI, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 755         final Set<TypeAwareBuilder> dirtyNodes = module.getDirtyNodes();
 756         if (!dirtyNodes.isEmpty()) {
 757             for (TypeAwareBuilder nodeToResolve : dirtyNodes) {
 758                 if (nodeToResolve instanceof UnionTypeBuilder) {
 759                     // special handling for union types
 760                     resolveTypeUnion((UnionTypeBuilder) nodeToResolve, modules, module);
 761                 } else if (nodeToResolve.getTypedef() instanceof IdentityrefTypeBuilder) {
 762                     // special handling for identityref types
 763                     IdentityrefTypeBuilder idref = (IdentityrefTypeBuilder) nodeToResolve.getTypedef();
 764                     IdentitySchemaNodeBuilder identity = findBaseIdentity(module, idref.getBaseString(),
 765                             idref.getLine());
 766                     if (identity == null) {
 767                         throw new YangParseException(module.getName(), idref.getLine(), "Failed to find base identity");
 768                     }
 769                     idref.setBaseIdentity(identity);
 770                     nodeToResolve.setType(idref.build());
 771                 } else {
 772                     resolveType(nodeToResolve, modules, module);
 773                 }
 774             }
 775         }
 776     }
 777
 778     /**
 779      * Traverse through augmentations of modules and fix their child nodes
 780      * schema path.
 781      *
 782      * @param modules
 783      *            all loaded modules
 784      */
 785     private void resolveAugmentsTargetPath(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
 786         // collect augments from all loaded modules
 787         final List<AugmentationSchemaBuilder> allAugments = new ArrayList<>();
 788         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 789             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 790                 allAugments.addAll(inner.getValue().getAllAugments());
 791             }
 792         }
 793
 794         for (AugmentationSchemaBuilder augment : allAugments) {
 795             setCorrectAugmentTargetPath(augment);
 796         }
 797     }
 798
 799     /**
 800      * Find augment target and set correct schema path for all its child nodes.
 801      *
 802      * @param augment
 803      *            augment to resolve
 804      */
 805     private void setCorrectAugmentTargetPath(final AugmentationSchemaBuilder augment) {
 806         Builder parent = augment.getParent();
 807         final SchemaPath targetNodeSchemaPath;
 808
 809         if (parent instanceof UsesNodeBuilder) {
 810             targetNodeSchemaPath = findUsesAugmentTargetNodePath(((UsesNodeBuilder) parent).getParent(), augment);
 811         } else {
 812             targetNodeSchemaPath = augment.getTargetPath();
 813         }
 814
 815         for (DataSchemaNodeBuilder childNode : augment.getChildNodeBuilders()) {
 816             correctPathForAugmentNodes(childNode, targetNodeSchemaPath);
 817         }
 818     }
 819
 820     private SchemaPath findUsesAugmentTargetNodePath(DataNodeContainerBuilder usesParent,
 821             AugmentationSchemaBuilder augment) {
 822         QName parentQName = usesParent.getQName();
 823         final QNameModule qnm;
 824         if (parentQName == null) {
 825             ModuleBuilder m = BuilderUtils.getParentModule(usesParent);
 826             qnm = m.getQNameModule();
 827         } else {
 828             qnm = parentQName.getModule();
 829         }
 830
 831         SchemaPath path = usesParent.getPath();
 832         for (QName qname : augment.getTargetPath().getPathFromRoot()) {
 833             path = path.createChild(QName.create(qnm, qname.getLocalName()));
 834         }
 835
 836         return path;
 837     }
 838
 839     /**
 840      * Set new schema path to node and all its child nodes based on given parent
 841      * path. This method do not change the namespace.
 842      *
 843      * @param node
 844      *            node which schema path should be updated
 845      * @param parentPath
 846      *            schema path of parent node
 847      */
 848     private void correctPathForAugmentNodes(final DataSchemaNodeBuilder node, final SchemaPath parentPath) {
 849         SchemaPath newPath = parentPath.createChild(node.getQName());
 850         node.setPath(newPath);
 851         if (node instanceof DataNodeContainerBuilder) {
 852             for (DataSchemaNodeBuilder child : ((DataNodeContainerBuilder) node).getChildNodeBuilders()) {
 853                 correctPathForAugmentNodes(child, node.getPath());
 854             }
 855         }
 856         if (node instanceof ChoiceBuilder) {
 857             for (ChoiceCaseBuilder child : ((ChoiceBuilder) node).getCases()) {
 858                 correctPathForAugmentNodes(child, node.getPath());
 859             }
 860         }
 861     }
 862
 863     /**
 864      * Check augments for mandatory nodes. If the target node is in another
 865      * module, then nodes added by the augmentation MUST NOT be mandatory nodes.
 866      * If mandatory node is found, throw an exception.
 867      *
 868      * @param augments
 869      *            augments to check
 870      */
 871     private void checkAugmentMandatoryNodes(final Collection<AugmentationSchemaBuilder> augments) {
 872         for (AugmentationSchemaBuilder augment : augments) {
 873             URI augmentTargetNs = augment.getTargetPath().getPathFromRoot().iterator().next().getNamespace();
 874             Date augmentTargetRev = augment.getTargetPath().getPathFromRoot().iterator().next().getRevision();
 875             ModuleBuilder module = BuilderUtils.getParentModule(augment);
 876
 877             if (augmentTargetNs.equals(module.getNamespace()) && augmentTargetRev.equals(module.getRevision())) {
 878                 continue;
 879             }
 880
 881             for (DataSchemaNodeBuilder childNode : augment.getChildNodeBuilders()) {
 882                 if (childNode.getConstraints().isMandatory()) {
 883                     throw new YangParseException(augment.getModuleName(), augment.getLine(),
 884                             "Error in augment parsing: cannot augment mandatory node "
 885                                     + childNode.getQName().getLocalName());
 886                 }
 887             }
 888         }
 889     }
 890
 891     /**
 892      * Go through all augment definitions and resolve them.
 893      *
 894      * @param modules
 895      *            all loaded modules topologically sorted (based on dependencies
 896      *            between each other)
 897      */
 898     private void resolveAugments(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
 899         List<ModuleBuilder> all = new ArrayList<>();
 900         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 901             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 902                 all.add(inner.getValue());
 903             }
 904         }
 905
 906         for (ModuleBuilder mb : all) {
 907             if (mb != null) {
 908                 List<AugmentationSchemaBuilder> augments = mb.getAllAugments();
 909                 checkAugmentMandatoryNodes(augments);
 910                 Collections.sort(augments, Comparators.AUGMENT_BUILDER_COMP);
 911                 for (AugmentationSchemaBuilder augment : augments) {
 912                     if (!(augment.isResolved())) {
 913                         boolean resolved = resolveAugment(augment, mb, modules);
 914                         if (!resolved) {
 915                             throw new YangParseException(augment.getModuleName(), augment.getLine(),
 916                                     "Error in augment parsing: failed to find augment target: " + augment);
 917                         }
 918                     }
 919                 }
 920             }
 921         }
 922     }
 923
 924     /**
 925      * Perform augmentation defined under uses statement.
 926      *
 927      * @param augment
 928      *            augment to resolve
 929      * @param module
 930      *            current module
 931      * @param modules
 932      *            all loaded modules
 933      * @return true if augment process succeed
 934      */
 935     private boolean resolveUsesAugment(final AugmentationSchemaBuilder augment, final ModuleBuilder module,
 936             final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
 937         if (augment.isResolved()) {
 938             return true;
 939         }
 940
 941         UsesNodeBuilder usesNode = (UsesNodeBuilder) augment.getParent();
 942         DataNodeContainerBuilder parentNode = usesNode.getParent();
 943         Optional<SchemaNodeBuilder> potentialTargetNode;
 944         SchemaPath resolvedTargetPath = findUsesAugmentTargetNodePath(parentNode, augment);
 945         if (parentNode instanceof ModuleBuilder && resolvedTargetPath.isAbsolute()) {
 946             // Uses is directly used in module body, we lookup
 947             // We lookup in data namespace to find correct augmentation target
 948             potentialTargetNode = findSchemaNodeInModule(resolvedTargetPath, (ModuleBuilder) parentNode);
 949         } else {
 950             // Uses is used in local context (be it data namespace or grouping
 951             // namespace,
 952             // since all nodes via uses are imported to localName, it is safe to
 953             // to proceed only with local names.
 954             //
 955             // Conflicting elements in other namespaces are still not present
 956             // since resolveUsesAugment occurs before augmenting from external
 957             // modules.
 958             potentialTargetNode = Optional.<SchemaNodeBuilder> fromNullable(findSchemaNode(augment.getTargetPath()
 959                     .getPathFromRoot(), (SchemaNodeBuilder) parentNode));
 960         }
 961
 962         if (potentialTargetNode.isPresent()) {
 963             SchemaNodeBuilder targetNode = potentialTargetNode.get();
 964             if (targetNode instanceof AugmentationTargetBuilder) {
 965                 fillAugmentTarget(augment, targetNode);
 966                 ((AugmentationTargetBuilder) targetNode).addAugmentation(augment);
 967                 augment.setResolved(true);
 968                 return true;
 969             } else {
 970                 LOG.warn(
 971                         "Error in module {} at line {}: Unsupported augment target: {}. Augmentation process skipped.",
 972                         module.getName(), augment.getLine(), potentialTargetNode);
 973                 augment.setResolved(true);
 974                 augment.setUnsupportedTarget(true);
 975                 return true;
 976             }
 977         } else {
 978             throw new YangParseException(module.getName(), augment.getLine(), String.format(
 979                     "Failed to resolve augment in uses. Invalid augment target path: %s", augment.getTargetPath()));
 980         }
 981
 982     }
 983
 984     /**
 985      * Find augment target module and perform augmentation.
 986      *
 987      * @param augment
 988      *            augment to resolve
 989      * @param module
 990      *            current module
 991      * @param modules
 992      *            all loaded modules
 993      * @return true if augment process succeed
 994      */
 995     private boolean resolveAugment(final AugmentationSchemaBuilder augment, final ModuleBuilder module,
 996             final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
 997         if (augment.isResolved()) {
 998             return true;
 999         }
1000
1001         QName targetModuleName = augment.getTargetPath().getPathFromRoot().iterator().next();
1002         ModuleBuilder targetModule = BuilderUtils.findModule(targetModuleName, modules);
1003         if (targetModule == null) {
1004             throw new YangParseException(module.getModuleName(), augment.getLine(), "Failed to resolve augment "
1005                     + augment);
1006         }
1007
1008         return processAugmentation(augment, targetModule);
1009     }
1010
1011     /**
1012      * Go through identity statements defined in current module and resolve
1013      * their 'base' statement.
1014      *
1015      * @param modules
1016      *            all loaded modules
1017      */
1018     private void resolveIdentities(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1019         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
1020             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
1021                 ModuleBuilder module = inner.getValue();
1022                 final Set<IdentitySchemaNodeBuilder> identities = module.getAddedIdentities();
1023                 for (IdentitySchemaNodeBuilder identity : identities) {
1024                     resolveIdentity(module, identity);
1025                 }
1026             }
1027         }
1028     }
1029
1030     private void resolveIdentity(final ModuleBuilder module,
1031             final IdentitySchemaNodeBuilder identity) {
1032         final String baseIdentityName = identity.getBaseIdentityName();
1033         if (baseIdentityName != null) {
1034             IdentitySchemaNodeBuilder result = null;
1035             if (baseIdentityName.contains(":")) {
1036                 final int line = identity.getLine();
1037                 String[] splittedBase = baseIdentityName.split(":");
1038                 if (splittedBase.length > 2) {
1039                     throw new YangParseException(module.getName(), line,
1040                             "Failed to parse identityref base: "
1041                                     + baseIdentityName);
1042                 }
1043                 String prefix = splittedBase[0];
1044                 String name = splittedBase[1];
1045
1046                 if (prefix.equals(module.getPrefix())
1047                         && name.equals(identity.getQName().getLocalName())) {
1048                     throw new YangParseException(module.getName(),
1049                             identity.getLine(),
1050                             "Failed to parse base, identity name equals base identity name: "
1051                                     + baseIdentityName);
1052                 }
1053
1054                 ModuleBuilder dependentModule = BuilderUtils.getModuleByPrefix(
1055                         module, prefix);
1056                 result = BuilderUtils.findIdentity(
1057                         dependentModule.getAddedIdentities(), name);
1058             } else {
1059                 if (baseIdentityName.equals(identity.getQName().getLocalName())) {
1060                     throw new YangParseException(module.getName(),
1061                             identity.getLine(),
1062                             "Failed to parse base, identity name equals base identity name: "
1063                                     + baseIdentityName);
1064                 }
1065                 result = BuilderUtils.findIdentity(module.getAddedIdentities(),
1066                         baseIdentityName);
1067             }
1068             identity.setBaseIdentity(result);
1069         }
1070     }
1071
1072     /**
1073      * Find and add reference of uses target grouping.
1074      *
1075      * @param modules
1076      *            all loaded modules
1077      */
1078     private void resolveUsesTargetGrouping(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1079         final List<UsesNodeBuilder> allUses = new ArrayList<>();
1080         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
1081             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
1082                 allUses.addAll(inner.getValue().getAllUsesNodes());
1083             }
1084         }
1085         for (UsesNodeBuilder usesNode : allUses) {
1086             ModuleBuilder module = BuilderUtils.getParentModule(usesNode);
1087             final GroupingBuilder targetGroupingBuilder = GroupingUtils.getTargetGroupingFromModules(usesNode, modules,
1088                     module);
1089             usesNode.setGrouping(targetGroupingBuilder);
1090         }
1091     }
1092
1093     /**
1094      * Resolve uses statements defined in groupings.
1095      *
1096      * @param modules
1097      *            all loaded modules
1098      */
1099     private void resolveUsesForGroupings(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1100         final Set<GroupingBuilder> allGroupings = new HashSet<>();
1101         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
1102             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
1103                 ModuleBuilder module = inner.getValue();
1104                 allGroupings.addAll(module.getAllGroupings());
1105             }
1106         }
1107         final List<GroupingBuilder> sorted = GroupingSort.sort(allGroupings);
1108         for (GroupingBuilder gb : sorted) {
1109             List<UsesNodeBuilder> usesNodes = new ArrayList<>(GroupingSort.getAllUsesNodes(gb));
1110             Collections.sort(usesNodes, new GroupingUtils.UsesComparator());
1111             for (UsesNodeBuilder usesNode : usesNodes) {
1112                 resolveUses(usesNode, modules);
1113             }
1114         }
1115     }
1116
1117     /**
1118      * Resolve uses statements.
1119      *
1120      * @param modules
1121      *            all loaded modules
1122      */
1123     private void resolveUsesForNodes(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1124         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
1125             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
1126                 ModuleBuilder module = inner.getValue();
1127                 List<UsesNodeBuilder> usesNodes = module.getAllUsesNodes();
1128                 Collections.sort(usesNodes, new GroupingUtils.UsesComparator());
1129                 for (UsesNodeBuilder usesNode : usesNodes) {
1130                     resolveUses(usesNode, modules);
1131                 }
1132             }
1133         }
1134     }
1135
1136     /**
1137      * Find target grouping and copy its child nodes to current location with
1138      * new namespace.
1139      *
1140      * @param usesNode
1141      *            uses node to resolve
1142      * @param modules
1143      *            all loaded modules
1144      */
1145     private void resolveUses(final UsesNodeBuilder usesNode, final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1146         if (!usesNode.isResolved()) {
1147             DataNodeContainerBuilder parent = usesNode.getParent();
1148             ModuleBuilder module = BuilderUtils.getParentModule(parent);
1149             GroupingBuilder target = GroupingUtils.getTargetGroupingFromModules(usesNode, modules, module);
1150
1151             int index = nodeAfterUsesIndex(usesNode);
1152             List<DataSchemaNodeBuilder> targetNodes = target.instantiateChildNodes(parent);
1153             for (DataSchemaNodeBuilder targetNode : targetNodes) {
1154                 parent.addChildNode(index++, targetNode);
1155             }
1156             parent.getTypeDefinitionBuilders().addAll(target.instantiateTypedefs(parent));
1157             parent.getGroupingBuilders().addAll(target.instantiateGroupings(parent));
1158             parent.getUnknownNodes().addAll(target.instantiateUnknownNodes(parent));
1159             usesNode.setResolved(true);
1160             for (AugmentationSchemaBuilder augment : usesNode.getAugmentations()) {
1161                 resolveUsesAugment(augment, module, modules);
1162             }
1163
1164             GroupingUtils.performRefine(usesNode);
1165         }
1166     }
1167
1168     private int nodeAfterUsesIndex(final UsesNodeBuilder usesNode) {
1169         DataNodeContainerBuilder parent = usesNode.getParent();
1170         int usesLine = usesNode.getLine();
1171
1172         List<DataSchemaNodeBuilder> childNodes = parent.getChildNodeBuilders();
1173         if (childNodes.isEmpty()) {
1174             return 0;
1175         }
1176
1177         DataSchemaNodeBuilder nextNodeAfterUses = null;
1178         for (DataSchemaNodeBuilder childNode : childNodes) {
1179             if (!(childNode.isAddedByUses()) && !(childNode.isAugmenting())) {
1180                 if (childNode.getLine() > usesLine) {
1181                     nextNodeAfterUses = childNode;
1182                     break;
1183                 }
1184             }
1185         }
1186
1187         // uses is declared after child nodes
1188         if (nextNodeAfterUses == null) {
1189             return childNodes.size();
1190         }
1191
1192         return parent.getChildNodeBuilders().indexOf(nextNodeAfterUses);
1193     }
1194
1195     /**
1196      * Try to find extension describing this unknown node and assign it to
1197      * unknown node builder.
1198      *
1199      * @param modules
1200      *            all loaded modules
1201      * @param module
1202      *            current module
1203      */
1204     private void resolveUnknownNodes(final Map<URI, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
1205         for (UnknownSchemaNodeBuilder usnb : module.getAllUnknownNodes()) {
1206             QName nodeType = usnb.getNodeType();
1207             String localName = usnb.getNodeType().getLocalName();
1208             ModuleBuilder dependentModule = BuilderUtils.findModule(nodeType, modules);
1209
1210             if (dependentModule == null) {
1211                 LOG.warn(
1212                         "Error in module {} at line {}: Failed to resolve node {}: no such extension definition found.",
1213                         module.getName(), usnb.getLine(), usnb);
1214                 continue;
1215             }
1216
1217             ExtensionBuilder extBuilder = findExtBuilder(localName, dependentModule.getAddedExtensions());
1218             if (extBuilder == null) {
1219                 ExtensionDefinition extDef = findExtDef(localName, dependentModule.getExtensions());
1220                 if (extDef == null) {
1221                     LOG.warn(
1222                             "Error in module {} at line {}: Failed to resolve node {}: no such extension definition found.",
1223                             module.getName(), usnb.getLine(), usnb);
1224                 } else {
1225                     usnb.setExtensionDefinition(extDef);
1226                 }
1227             } else {
1228                 usnb.setExtensionBuilder(extBuilder);
1229             }
1230         }
1231     }
1232
1233     private ExtensionBuilder findExtBuilder(final String name, final Collection<ExtensionBuilder> extensions) {
1234         for (ExtensionBuilder extension : extensions) {
1235             if (extension.getQName().getLocalName().equals(name)) {
1236                 return extension;
1237             }
1238         }
1239         return null;
1240     }
1241
1242     private ExtensionDefinition findExtDef(final String name, final Collection<ExtensionDefinition> extensions) {
1243         for (ExtensionDefinition extension : extensions) {
1244             if (extension.getQName().getLocalName().equals(name)) {
1245                 return extension;
1246             }
1247         }
1248         return null;
1249     }
1250
1251
1252     /**
1253      * Traverse through modules and check if choice has choice cases with the
1254      * same qname.
1255      *
1256      * @param modules
1257      *            all loaded modules
1258      */
1259     private void checkChoiceCasesForDuplicityQNames(final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1260         for (Map.Entry<URI, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
1261             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
1262                 final ModuleBuilder moduleBuilder = childEntry.getValue();
1263                 final Module module = moduleBuilder.build();
1264                 final List<ChoiceSchemaNode> allChoicesFromModule = getChoicesFrom(module);
1265
1266                 for (ChoiceSchemaNode choiceNode : allChoicesFromModule) {
1267                     findDuplicityNodesIn(choiceNode, module, moduleBuilder, modules);
1268                 }
1269             }
1270         }
1271     }
1272
1273     private void findDuplicityNodesIn(final ChoiceSchemaNode choiceNode, final Module module, final ModuleBuilder moduleBuilder,
1274             final Map<URI, TreeMap<Date, ModuleBuilder>> modules) {
1275         final Set<QName> duplicityTestSet = new HashSet<QName>();
1276
1277         for (ChoiceCaseNode choiceCaseNode : choiceNode.getCases()) {
1278
1279             for (DataSchemaNode childSchemaNode : choiceCaseNode.getChildNodes()) {
1280                 if (!duplicityTestSet.add(childSchemaNode.getQName())) {
1281                     final Optional<SchemaNodeBuilder> schemaNodeBuilder = BuilderUtils.findSchemaNodeInModule(childSchemaNode.getPath(), moduleBuilder);
1282                     final String nameOfSchemaNode = childSchemaNode.getQName().getLocalName();
1283                     int lineOfSchemaNode = 0;
1284
1285                     if (schemaNodeBuilder.isPresent()) {
1286                         lineOfSchemaNode = schemaNodeBuilder.get().getLine();
1287                     }
1288                     throw new YangParseException(module.getName(), lineOfSchemaNode,
1289                             String.format("Choice has two nodes case with same qnames - %s", nameOfSchemaNode));
1290                 }
1291             }
1292         }
1293     }
1294
1295     private List<ChoiceSchemaNode> getChoicesFrom(final Module module) {
1296         final List<ChoiceSchemaNode> allChoices = new ArrayList<ChoiceSchemaNode>();
1297
1298         for (DataSchemaNode dataSchemaNode : module.getChildNodes()) {
1299             findChoicesIn(dataSchemaNode, allChoices);
1300         }
1301         return allChoices;
1302     }
1303
1304     private void findChoicesIn(final SchemaNode schemaNode, final Collection<ChoiceSchemaNode> choiceNodes) {
1305         if (schemaNode instanceof ContainerSchemaNode) {
1306             final ContainerSchemaNode contSchemaNode = (ContainerSchemaNode) schemaNode;
1307             for (DataSchemaNode dataSchemaNode : contSchemaNode.getChildNodes()) {
1308                 findChoicesIn(dataSchemaNode, choiceNodes);
1309             }
1310         } else if (schemaNode instanceof ListSchemaNode) {
1311             final ListSchemaNode listSchemaNode = (ListSchemaNode) schemaNode;
1312             for (DataSchemaNode dataSchemaNode : listSchemaNode.getChildNodes()) {
1313                 findChoicesIn(dataSchemaNode, choiceNodes);
1314             }
1315         } else if (schemaNode instanceof ChoiceSchemaNode) {
1316             choiceNodes.add((ChoiceSchemaNode) schemaNode);
1317         }
1318     }
1319
1320 }