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