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