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