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