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