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