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