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

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