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