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

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