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