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