yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/impl/YangParserImpl.java

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