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