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

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