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