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