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