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

   1 /*
   2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.parser.impl;
   9
  10 import static org.opendaylight.yangtools.yang.parser.util.ParserUtils.*;
  11 import static org.opendaylight.yangtools.yang.parser.util.TypeUtils.*;
  12
  13 import java.io.File;
  14 import java.io.FileInputStream;
  15 import java.io.FileNotFoundException;
  16 import java.io.IOException;
  17 import java.io.InputStream;
  18 import java.net.URI;
  19 import java.util.ArrayList;
  20 import java.util.Collections;
  21 import java.util.Date;
  22 import java.util.HashMap;
  23 import java.util.HashSet;
  24 import java.util.LinkedHashMap;
  25 import java.util.List;
  26 import java.util.Map;
  27 import java.util.Map.Entry;
  28 import java.util.Set;
  29 import java.util.TreeMap;
  30
  31 import org.antlr.v4.runtime.ANTLRInputStream;
  32 import org.antlr.v4.runtime.CommonTokenStream;
  33 import org.antlr.v4.runtime.tree.ParseTree;
  34 import org.antlr.v4.runtime.tree.ParseTreeWalker;
  35 import org.opendaylight.yangtools.antlrv4.code.gen.YangLexer;
  36 import org.opendaylight.yangtools.antlrv4.code.gen.YangParser;
  37 import org.opendaylight.yangtools.yang.common.QName;
  38 import org.opendaylight.yangtools.yang.model.api.AnyXmlSchemaNode;
  39 import org.opendaylight.yangtools.yang.model.api.ChoiceNode;
  40 import org.opendaylight.yangtools.yang.model.api.ContainerSchemaNode;
  41 import org.opendaylight.yangtools.yang.model.api.DataNodeContainer;
  42 import org.opendaylight.yangtools.yang.model.api.DataSchemaNode;
  43 import org.opendaylight.yangtools.yang.model.api.GroupingDefinition;
  44 import org.opendaylight.yangtools.yang.model.api.IdentitySchemaNode;
  45 import org.opendaylight.yangtools.yang.model.api.LeafListSchemaNode;
  46 import org.opendaylight.yangtools.yang.model.api.LeafSchemaNode;
  47 import org.opendaylight.yangtools.yang.model.api.ListSchemaNode;
  48 import org.opendaylight.yangtools.yang.model.api.Module;
  49 import org.opendaylight.yangtools.yang.model.api.SchemaContext;
  50 import org.opendaylight.yangtools.yang.model.api.SchemaNode;
  51 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  52 import org.opendaylight.yangtools.yang.model.api.TypeDefinition;
  53 import org.opendaylight.yangtools.yang.model.api.UnknownSchemaNode;
  54 import org.opendaylight.yangtools.yang.model.parser.api.YangModelParser;
  55 import org.opendaylight.yangtools.yang.model.util.ExtendedType;
  56 import org.opendaylight.yangtools.yang.model.util.IdentityrefType;
  57 import org.opendaylight.yangtools.yang.parser.builder.api.AugmentationSchemaBuilder;
  58 import org.opendaylight.yangtools.yang.parser.builder.api.Builder;
  59 import org.opendaylight.yangtools.yang.parser.builder.api.DataNodeContainerBuilder;
  60 import org.opendaylight.yangtools.yang.parser.builder.api.DataSchemaNodeBuilder;
  61 import org.opendaylight.yangtools.yang.parser.builder.api.GroupingBuilder;
  62 import org.opendaylight.yangtools.yang.parser.builder.api.GroupingMember;
  63 import org.opendaylight.yangtools.yang.parser.builder.api.SchemaNodeBuilder;
  64 import org.opendaylight.yangtools.yang.parser.builder.api.TypeAwareBuilder;
  65 import org.opendaylight.yangtools.yang.parser.builder.api.TypeDefinitionBuilder;
  66 import org.opendaylight.yangtools.yang.parser.builder.api.UsesNodeBuilder;
  67 import org.opendaylight.yangtools.yang.parser.builder.impl.DeviationBuilder;
  68 import org.opendaylight.yangtools.yang.parser.builder.impl.IdentitySchemaNodeBuilder;
  69 import org.opendaylight.yangtools.yang.parser.builder.impl.IdentityrefTypeBuilder;
  70 import org.opendaylight.yangtools.yang.parser.builder.impl.ModuleBuilder;
  71 import org.opendaylight.yangtools.yang.parser.builder.impl.UnionTypeBuilder;
  72 import org.opendaylight.yangtools.yang.parser.builder.impl.UnknownSchemaNodeBuilder;
  73 import org.opendaylight.yangtools.yang.parser.util.GroupingUtils;
  74 import org.opendaylight.yangtools.yang.parser.util.ModuleDependencySort;
  75 import org.opendaylight.yangtools.yang.parser.util.ParserUtils;
  76 import org.opendaylight.yangtools.yang.parser.util.YangParseException;
  77 import org.opendaylight.yangtools.yang.validator.YangModelBasicValidator;
  78 import org.slf4j.Logger;
  79 import org.slf4j.LoggerFactory;
  80
  81 import com.google.common.collect.Lists;
  82 import com.google.common.collect.Maps;
  83 import com.google.common.collect.Sets;
  84
  85 public final class YangParserImpl implements YangModelParser {
  86     private static final Logger LOG = LoggerFactory.getLogger(YangParserImpl.class);
  87
  88     @Override
  89     public Set<Module> parseYangModels(final List<File> yangFiles) {
  90         return Sets.newLinkedHashSet(parseYangModelsMapped(yangFiles).values());
  91     }
  92
  93     @Override
  94     public Set<Module> parseYangModels(final List<File> yangFiles, final SchemaContext context) {
  95         // TODO
  96         throw new YangParseException("Not yet implemented");
  97         // if (yangFiles != null) {
  98         // final Map<InputStream, File> inputStreams = Maps.newHashMap();
  99         //
 100         // for (final File yangFile : yangFiles) {
 101         // try {
 102         // inputStreams.put(new FileInputStream(yangFile), yangFile);
 103         // } catch (FileNotFoundException e) {
 104         // LOG.warn("Exception while reading yang file: " + yangFile.getName(),
 105         // e);
 106         // }
 107         // }
 108         //
 109         // Map<ModuleBuilder, InputStream> builderToStreamMap =
 110         // Maps.newHashMap();
 111         //
 112         // final Map<String, TreeMap<Date, ModuleBuilder>> modules =
 113         // resolveModuleBuilders(
 114         // Lists.newArrayList(inputStreams.keySet()), builderToStreamMap);
 115         //
 116         // for (InputStream is : inputStreams.keySet()) {
 117         // try {
 118         // is.close();
 119         // } catch (IOException e) {
 120         // LOG.debug("Failed to close stream.");
 121         // }
 122         // }
 123         //
 124         // return new LinkedHashSet<Module>(buildWithContext(modules,
 125         // context).values());
 126         // }
 127         // return Collections.emptySet();
 128     }
 129
 130     @Override
 131     public Set<Module> parseYangModelsFromStreams(final List<InputStream> yangModelStreams) {
 132         return Sets.newHashSet(parseYangModelsFromStreamsMapped(yangModelStreams).values());
 133     }
 134
 135     @Override
 136     public Set<Module> parseYangModelsFromStreams(final List<InputStream> yangModelStreams, SchemaContext context) {
 137         // TODO
 138         throw new YangParseException("Not yet implemented");
 139         // if (yangModelStreams != null) {
 140         // Map<ModuleBuilder, InputStream> builderToStreamMap =
 141         // Maps.newHashMap();
 142         // final Map<String, TreeMap<Date, ModuleBuilder>> modules =
 143         // resolveModuleBuildersWithContext(
 144         // yangModelStreams, builderToStreamMap, context);
 145         // return new LinkedHashSet<Module>(buildWithContext(modules,
 146         // context).values());
 147         // }
 148         // return Collections.emptySet();
 149     }
 150
 151     @Override
 152     public Map<File, Module> parseYangModelsMapped(List<File> yangFiles) {
 153         if (yangFiles != null) {
 154             final Map<InputStream, File> inputStreams = Maps.newHashMap();
 155
 156             for (final File yangFile : yangFiles) {
 157                 try {
 158                     inputStreams.put(new FileInputStream(yangFile), yangFile);
 159                 } catch (FileNotFoundException e) {
 160                     LOG.warn("Exception while reading yang file: " + yangFile.getName(), e);
 161                 }
 162             }
 163
 164             Map<ModuleBuilder, InputStream> builderToStreamMap = Maps.newHashMap();
 165             final Map<String, TreeMap<Date, ModuleBuilder>> modules = resolveModuleBuilders(
 166                     Lists.newArrayList(inputStreams.keySet()), builderToStreamMap);
 167
 168             for (InputStream is : inputStreams.keySet()) {
 169                 try {
 170                     is.close();
 171                 } catch (IOException e) {
 172                     LOG.debug("Failed to close stream.");
 173                 }
 174             }
 175
 176             Map<File, Module> retVal = Maps.newLinkedHashMap();
 177             Map<ModuleBuilder, Module> builderToModuleMap = build(modules);
 178
 179             for (Entry<ModuleBuilder, Module> builderToModule : builderToModuleMap.entrySet()) {
 180                 retVal.put(inputStreams.get(builderToStreamMap.get(builderToModule.getKey())),
 181                         builderToModule.getValue());
 182             }
 183
 184             return retVal;
 185         }
 186         return Collections.emptyMap();
 187     }
 188
 189     @Override
 190     public Map<InputStream, Module> parseYangModelsFromStreamsMapped(final List<InputStream> yangModelStreams) {
 191         Map<ModuleBuilder, InputStream> builderToStreamMap = Maps.newHashMap();
 192
 193         final Map<String, TreeMap<Date, ModuleBuilder>> modules = resolveModuleBuilders(yangModelStreams,
 194                 builderToStreamMap);
 195         Map<InputStream, Module> retVal = Maps.newLinkedHashMap();
 196         Map<ModuleBuilder, Module> builderToModuleMap = build(modules);
 197
 198         for (Entry<ModuleBuilder, Module> builderToModule : builderToModuleMap.entrySet()) {
 199             retVal.put(builderToStreamMap.get(builderToModule.getKey()), builderToModule.getValue());
 200         }
 201         return retVal;
 202     }
 203
 204     @Override
 205     public SchemaContext resolveSchemaContext(final Set<Module> modules) {
 206         return new SchemaContextImpl(modules);
 207     }
 208
 209     private ModuleBuilder[] parseModuleBuilders(List<InputStream> inputStreams,
 210             Map<ModuleBuilder, InputStream> streamToBuilderMap) {
 211
 212         final ParseTreeWalker walker = new ParseTreeWalker();
 213         final List<ParseTree> trees = parseStreams(inputStreams);
 214         final ModuleBuilder[] builders = new ModuleBuilder[trees.size()];
 215
 216         // validate yang
 217         new YangModelBasicValidator(walker).validate(trees);
 218
 219         YangParserListenerImpl yangModelParser = null;
 220         for (int i = 0; i < trees.size(); i++) {
 221             yangModelParser = new YangParserListenerImpl();
 222             walker.walk(yangModelParser, trees.get(i));
 223             ModuleBuilder moduleBuilder = yangModelParser.getModuleBuilder();
 224
 225             // We expect the order of trees and streams has to be the same
 226             streamToBuilderMap.put(moduleBuilder, inputStreams.get(i));
 227             builders[i] = moduleBuilder;
 228         }
 229         return builders;
 230     }
 231
 232     private Map<String, TreeMap<Date, ModuleBuilder>> resolveModuleBuilders(final List<InputStream> yangFileStreams,
 233             Map<ModuleBuilder, InputStream> streamToBuilderMap) {
 234         return resolveModuleBuildersWithContext(yangFileStreams, streamToBuilderMap, null);
 235     }
 236
 237     private Map<String, TreeMap<Date, ModuleBuilder>> resolveModuleBuildersWithContext(
 238             final List<InputStream> yangFileStreams, final Map<ModuleBuilder, InputStream> streamToBuilderMap,
 239             final SchemaContext context) {
 240         final ModuleBuilder[] builders = parseModuleBuilders(yangFileStreams, streamToBuilderMap);
 241
 242         // Linked Hash Map MUST be used because Linked Hash Map preserves ORDER
 243         // of items stored in map.
 244         final LinkedHashMap<String, TreeMap<Date, ModuleBuilder>> modules = new LinkedHashMap<String, TreeMap<Date, ModuleBuilder>>();
 245
 246         // module dependency graph sorted
 247         List<ModuleBuilder> sorted = null;
 248         if (context == null) {
 249             sorted = ModuleDependencySort.sort(builders);
 250         } else {
 251             sorted = ModuleDependencySort.sortWithContext(context, builders);
 252         }
 253
 254         for (final ModuleBuilder builder : sorted) {
 255             if (builder == null) {
 256                 continue;
 257             }
 258             final String builderName = builder.getName();
 259             Date builderRevision = builder.getRevision();
 260             if (builderRevision == null) {
 261                 builderRevision = new Date(0L);
 262             }
 263             TreeMap<Date, ModuleBuilder> builderByRevision = modules.get(builderName);
 264             if (builderByRevision == null) {
 265                 builderByRevision = new TreeMap<Date, ModuleBuilder>();
 266             }
 267             builderByRevision.put(builderRevision, builder);
 268             modules.put(builderName, builderByRevision);
 269         }
 270         return modules;
 271     }
 272
 273     private List<ParseTree> parseStreams(final List<InputStream> yangStreams) {
 274         final List<ParseTree> trees = new ArrayList<ParseTree>();
 275         for (InputStream yangStream : yangStreams) {
 276             trees.add(parseStream(yangStream));
 277         }
 278         return trees;
 279     }
 280
 281     private ParseTree parseStream(final InputStream yangStream) {
 282         ParseTree result = null;
 283         try {
 284             final ANTLRInputStream input = new ANTLRInputStream(yangStream);
 285             final YangLexer lexer = new YangLexer(input);
 286             final CommonTokenStream tokens = new CommonTokenStream(lexer);
 287             final YangParser parser = new YangParser(tokens);
 288             parser.removeErrorListeners();
 289             parser.addErrorListener(new YangErrorListener());
 290
 291             result = parser.yang();
 292         } catch (IOException e) {
 293             LOG.warn("Exception while reading yang file: " + yangStream, e);
 294         }
 295         return result;
 296     }
 297
 298     private Map<ModuleBuilder, Module> build(final Map<String, TreeMap<Date, ModuleBuilder>> modules) {
 299         // fix unresolved nodes
 300         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 301             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 302                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 303                 fixUnresolvedNodes(modules, moduleBuilder);
 304             }
 305         }
 306         resolveAugments(modules);
 307         finishResolvingUses(modules);
 308         resolveDeviations(modules);
 309
 310         // build
 311         final Map<ModuleBuilder, Module> result = new LinkedHashMap<ModuleBuilder, Module>();
 312         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 313             final Map<Date, Module> modulesByRevision = new HashMap<Date, Module>();
 314             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 315                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 316                 final Module module = moduleBuilder.build();
 317                 modulesByRevision.put(childEntry.getKey(), module);
 318                 result.put(moduleBuilder, module);
 319             }
 320         }
 321         return result;
 322     }
 323
 324     private Map<ModuleBuilder, Module> buildWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 325             SchemaContext context) {
 326         // fix unresolved nodes
 327         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 328             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 329                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 330                 fixUnresolvedNodesWithContext(modules, moduleBuilder, context);
 331             }
 332         }
 333         resolveAugmentsWithContext(modules, context);
 334         resolveDeviationsWithContext(modules, context);
 335
 336         // build
 337         final Map<ModuleBuilder, Module> result = new LinkedHashMap<ModuleBuilder, Module>();
 338         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 339             final Map<Date, Module> modulesByRevision = new HashMap<Date, Module>();
 340             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 341                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 342                 final Module module = moduleBuilder.build();
 343                 modulesByRevision.put(childEntry.getKey(), module);
 344                 result.put(moduleBuilder, module);
 345             }
 346         }
 347         return result;
 348     }
 349
 350     private void fixUnresolvedNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder builder) {
 351         resolveDirtyNodes(modules, builder);
 352         resolveIdentities(modules, builder);
 353         resolveUsesNodes(modules, builder);
 354         resolveUnknownNodes(modules, builder);
 355     }
 356
 357     private void fixUnresolvedNodesWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 358             final ModuleBuilder builder, final SchemaContext context) {
 359         resolveDirtyNodesWithContext(modules, builder, context);
 360         resolveIdentitiesWithContext(modules, builder, context);
 361         resolveUsesNodesWithContext(modules, builder, context);
 362         resolveUnknownNodesWithContext(modules, builder, context);
 363     }
 364
 365     /**
 366      * Search for dirty nodes (node which contains UnknownType) and resolve
 367      * unknown types.
 368      *
 369      * @param modules
 370      *            all available modules
 371      * @param module
 372      *            current module
 373      */
 374     private void resolveDirtyNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 375         final Set<TypeAwareBuilder> dirtyNodes = module.getDirtyNodes();
 376         if (!dirtyNodes.isEmpty()) {
 377             for (TypeAwareBuilder nodeToResolve : dirtyNodes) {
 378                 if (nodeToResolve instanceof UnionTypeBuilder) {
 379                     // special handling for union types
 380                     resolveTypeUnion((UnionTypeBuilder) nodeToResolve, modules, module);
 381                 } else if (nodeToResolve.getTypedef() instanceof IdentityrefTypeBuilder) {
 382                     // special handling for identityref types
 383                     IdentityrefTypeBuilder idref = (IdentityrefTypeBuilder) nodeToResolve.getTypedef();
 384                     nodeToResolve.setType(new IdentityrefType(findFullQName(modules, module, idref), idref.getPath()));
 385                 } else {
 386                     resolveType(nodeToResolve, modules, module);
 387                 }
 388             }
 389         }
 390     }
 391
 392     private void resolveDirtyNodesWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 393             final ModuleBuilder module, SchemaContext context) {
 394         final Set<TypeAwareBuilder> dirtyNodes = module.getDirtyNodes();
 395         if (!dirtyNodes.isEmpty()) {
 396             for (TypeAwareBuilder nodeToResolve : dirtyNodes) {
 397                 if (nodeToResolve instanceof UnionTypeBuilder) {
 398                     // special handling for union types
 399                     resolveTypeUnionWithContext((UnionTypeBuilder) nodeToResolve, modules, module, context);
 400                 } else if (nodeToResolve.getTypedef() instanceof IdentityrefTypeBuilder) {
 401                     // special handling for identityref types
 402                     IdentityrefTypeBuilder idref = (IdentityrefTypeBuilder) nodeToResolve.getTypedef();
 403                     nodeToResolve.setType(new IdentityrefType(findFullQName(modules, module, idref), idref.getPath()));
 404                 } else {
 405                     resolveTypeWithContext(nodeToResolve, modules, module, context);
 406                 }
 407             }
 408         }
 409     }
 410
 411     /**
 412      * Go through all augment definitions and perform augmentation. It is
 413      * expected that modules are already sorted by their dependencies.
 414      *
 415      * @param modules
 416      *            all loaded modules
 417      */
 418     private void resolveAugments(final Map<String, TreeMap<Date, ModuleBuilder>> modules) {
 419         // collect augments from all loaded modules
 420         final List<AugmentationSchemaBuilder> allAugments = new ArrayList<>();
 421         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 422             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 423                 allAugments.addAll(inner.getValue().getAllAugments());
 424             }
 425         }
 426
 427         for (int i = 0; i < allAugments.size(); i++) {
 428             // pick one augment
 429             final AugmentationSchemaBuilder augment = allAugments.get(i);
 430             // create collection of others
 431             List<AugmentationSchemaBuilder> others = new ArrayList<>(allAugments);
 432             others.remove(augment);
 433
 434             // try to resolve it
 435             boolean resolved = resolveAugment(modules, augment);
 436             // while not resolved
 437             int j = 0;
 438             while (!(resolved) && j < others.size()) {
 439                 // try to resolve next augment
 440                 resolveAugment(modules, others.get(j));
 441                 // then try to resolve first again
 442                 resolved = resolveAugment(modules, augment);
 443                 j++;
 444
 445             }
 446
 447             if (!resolved) {
 448                 throw new YangParseException(augment.getModuleName(), augment.getLine(),
 449                         "Error in augment parsing: failed to find augment target");
 450             }
 451         }
 452     }
 453
 454     /**
 455      * Search for augment target and perform augmentation.
 456      *
 457      * @param modules
 458      *            all loaded modules
 459      * @param augmentBuilder
 460      *            augment to resolve
 461      * @return true if target node found, false otherwise
 462      */
 463     private boolean resolveAugment(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 464             final AugmentationSchemaBuilder augmentBuilder) {
 465         if (augmentBuilder.isResolved()) {
 466             return true;
 467         }
 468
 469         int line = augmentBuilder.getLine();
 470         ModuleBuilder module = getParentModule(augmentBuilder);
 471         List<QName> path = augmentBuilder.getTargetPath().getPath();
 472         Builder augmentParent = augmentBuilder.getParent();
 473         boolean isUsesAugment = false;
 474
 475         Builder firstNodeParent = null;
 476         if (augmentParent instanceof ModuleBuilder) {
 477             // if augment is defined under module, parent of first node is
 478             // target module
 479             final QName firstNameInPath = path.get(0);
 480             String prefix = firstNameInPath.getPrefix();
 481             if (prefix == null) {
 482                 prefix = module.getPrefix();
 483             }
 484             firstNodeParent = findDependentModuleBuilder(modules, module, prefix, line);
 485         } else if (augmentParent instanceof UsesNodeBuilder) {
 486             // if augment is defined under uses, parent of first node is uses
 487             // parent
 488             isUsesAugment = true;
 489             firstNodeParent = augmentParent.getParent();
 490         } else {
 491             // augment can be defined only under module or uses
 492             throw new YangParseException(augmentBuilder.getModuleName(), line,
 493                     "Failed to parse augment: Unresolved parent of augment: " + augmentParent);
 494         }
 495
 496         return processAugmentation(augmentBuilder, firstNodeParent, path, isUsesAugment);
 497     }
 498
 499     /**
 500      * Go through all augment definitions and resolve them. This method works in
 501      * same way as {@link #resolveAugments(Map)} except that if target node is
 502      * not found in loaded modules, it search for target node in given context.
 503      *
 504      * @param modules
 505      *            all loaded modules
 506      * @param context
 507      *            SchemaContext containing already resolved modules
 508      */
 509     private void resolveAugmentsWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 510             final SchemaContext context) {
 511         // collect augments from all loaded modules
 512         final List<AugmentationSchemaBuilder> allAugments = new ArrayList<>();
 513         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 514             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 515                 allAugments.addAll(inner.getValue().getAllAugments());
 516             }
 517         }
 518
 519         for (int i = 0; i < allAugments.size(); i++) {
 520             // pick augment from list
 521             final AugmentationSchemaBuilder augment = allAugments.get(i);
 522             // try to resolve it
 523             boolean resolved = resolveAugmentWithContext(modules, augment, context);
 524             // while not resolved
 525             int j = i + 1;
 526             while (!(resolved) && j < allAugments.size()) {
 527                 // try to resolve next augment
 528                 resolveAugmentWithContext(modules, allAugments.get(j), context);
 529                 // then try to resolve first again
 530                 resolved = resolveAugmentWithContext(modules, augment, context);
 531                 j++;
 532             }
 533
 534             if (!resolved) {
 535                 throw new YangParseException(augment.getModuleName(), augment.getLine(),
 536                         "Error in augment parsing: failed to find augment target");
 537             }
 538         }
 539     }
 540
 541     /**
 542      * Search for augment target and perform augmentation.
 543      *
 544      * @param modules
 545      *            all loaded modules
 546      * @param augmentBuilder
 547      *            augment to resolve
 548      * @param context
 549      *            SchemaContext containing already resolved modules
 550      * @return true if target node found, false otherwise
 551      */
 552     private boolean resolveAugmentWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 553             final AugmentationSchemaBuilder augmentBuilder, final SchemaContext context) {
 554         if (augmentBuilder.isResolved()) {
 555             return true;
 556         }
 557         int line = augmentBuilder.getLine();
 558         ModuleBuilder module = getParentModule(augmentBuilder);
 559         List<QName> path = augmentBuilder.getTargetPath().getPath();
 560         final QName firstNameInPath = path.get(0);
 561         String prefix = firstNameInPath.getPrefix();
 562         if (prefix == null) {
 563             prefix = module.getPrefix();
 564         }
 565         Builder augmentParent = augmentBuilder.getParent();
 566         Builder currentParent = null;
 567         boolean isUsesAugment = false;
 568
 569         if (augmentParent instanceof ModuleBuilder) {
 570             // if augment is defined under module, first parent is target module
 571             currentParent = findDependentModuleBuilder(modules, module, prefix, line);
 572         } else if (augmentParent instanceof UsesNodeBuilder) {
 573             // if augment is defined under uses, first parent is uses parent
 574             isUsesAugment = true;
 575             currentParent = augmentParent.getParent();
 576         } else {
 577             // augment can be defined only under module or uses
 578             throw new YangParseException(augmentBuilder.getModuleName(), augmentBuilder.getLine(),
 579                     "Error in augment parsing: Unresolved parent of augment: " + augmentParent);
 580         }
 581
 582         if (currentParent == null) {
 583             return processAugmentationOnContext(augmentBuilder, path, module, prefix, context);
 584         } else {
 585             return processAugmentation(augmentBuilder, currentParent, path, isUsesAugment);
 586         }
 587     }
 588
 589     /**
 590      * Go through identity statements defined in current module and resolve
 591      * their 'base' statement if present.
 592      *
 593      * @param modules
 594      *            all modules
 595      * @param module
 596      *            module being resolved
 597      */
 598     private void resolveIdentities(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 599         final Set<IdentitySchemaNodeBuilder> identities = module.getIdentities();
 600         for (IdentitySchemaNodeBuilder identity : identities) {
 601             final String baseIdentityName = identity.getBaseIdentityName();
 602             if (baseIdentityName != null) {
 603                 String baseIdentityPrefix = null;
 604                 String baseIdentityLocalName = null;
 605                 if (baseIdentityName.contains(":")) {
 606                     final String[] splitted = baseIdentityName.split(":");
 607                     baseIdentityPrefix = splitted[0];
 608                     baseIdentityLocalName = splitted[1];
 609                 } else {
 610                     baseIdentityPrefix = module.getPrefix();
 611                     baseIdentityLocalName = baseIdentityName;
 612                 }
 613                 final ModuleBuilder dependentModule = findDependentModuleBuilder(modules, module, baseIdentityPrefix,
 614                         identity.getLine());
 615
 616                 final Set<IdentitySchemaNodeBuilder> dependentModuleIdentities = dependentModule.getIdentities();
 617                 for (IdentitySchemaNodeBuilder idBuilder : dependentModuleIdentities) {
 618                     if (idBuilder.getQName().getLocalName().equals(baseIdentityLocalName)) {
 619                         identity.setBaseIdentity(idBuilder);
 620                     }
 621                 }
 622             }
 623         }
 624     }
 625
 626     /**
 627      * Go through identity statements defined in current module and resolve
 628      * their 'base' statement. Method tries to find base identity in given
 629      * modules. If base identity is not found, method will search it in context.
 630      *
 631      * @param modules
 632      *            all loaded modules
 633      * @param module
 634      *            current module
 635      * @param context
 636      *            SchemaContext containing already resolved modules
 637      */
 638     private void resolveIdentitiesWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 639             final ModuleBuilder module, final SchemaContext context) {
 640         final Set<IdentitySchemaNodeBuilder> identities = module.getIdentities();
 641         for (IdentitySchemaNodeBuilder identity : identities) {
 642             final String baseIdentityName = identity.getBaseIdentityName();
 643             if (baseIdentityName != null) {
 644                 String baseIdentityPrefix = null;
 645                 String baseIdentityLocalName = null;
 646                 if (baseIdentityName.contains(":")) {
 647                     final String[] splitted = baseIdentityName.split(":");
 648                     baseIdentityPrefix = splitted[0];
 649                     baseIdentityLocalName = splitted[1];
 650                 } else {
 651                     baseIdentityPrefix = module.getPrefix();
 652                     baseIdentityLocalName = baseIdentityName;
 653                 }
 654                 final ModuleBuilder dependentModuleBuilder = findDependentModuleBuilder(modules, module,
 655                         baseIdentityPrefix, identity.getLine());
 656
 657                 if (dependentModuleBuilder == null) {
 658                     final Module dependentModule = findModuleFromContext(context, module, baseIdentityPrefix,
 659                             identity.getLine());
 660                     final Set<IdentitySchemaNode> dependentModuleIdentities = dependentModule.getIdentities();
 661                     for (IdentitySchemaNode idNode : dependentModuleIdentities) {
 662                         if (idNode.getQName().getLocalName().equals(baseIdentityLocalName)) {
 663                             identity.setBaseIdentity(idNode);
 664                         }
 665                     }
 666                 } else {
 667                     final Set<IdentitySchemaNodeBuilder> dependentModuleIdentities = dependentModuleBuilder
 668                             .getIdentities();
 669                     for (IdentitySchemaNodeBuilder idBuilder : dependentModuleIdentities) {
 670                         if (idBuilder.getQName().getLocalName().equals(baseIdentityLocalName)) {
 671                             identity.setBaseIdentity(idBuilder);
 672                         }
 673                     }
 674                 }
 675             }
 676         }
 677     }
 678
 679     /**
 680      * Go through uses statements defined in current module and resolve their
 681      * refine statements.
 682      *
 683      * @param modules
 684      *            all modules
 685      * @param module
 686      *            module being resolved
 687      */
 688     private void resolveUsesNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 689         final List<UsesNodeBuilder> allModuleUses = module.getAllUsesNodes();
 690         List<UsesNodeBuilder> collection = new ArrayList<>(module.getAllUsesNodes());
 691         boolean usesDataLoaded = module.allUsesLoadDone();
 692         while (!usesDataLoaded) {
 693             for (UsesNodeBuilder usesNode : collection) {
 694                 if (!usesNode.isLoadDone()) {
 695                     final GroupingBuilder targetGrouping = GroupingUtils.getTargetGroupingFromModules(usesNode,
 696                             modules, module);
 697                     usesNode.setGroupingPath(targetGrouping.getPath());
 698                     // load uses target nodes in uses
 699                     GroupingUtils.loadTargetGroupingData(usesNode, targetGrouping);
 700                 }
 701             }
 702             collection = new ArrayList<>(module.getAllUsesNodes());
 703             usesDataLoaded = module.allUsesLoadDone();
 704         }
 705
 706         for (UsesNodeBuilder usesNode : allModuleUses) {
 707             final GroupingBuilder targetGrouping = GroupingUtils
 708                     .getTargetGroupingFromModules(usesNode, modules, module);
 709             // load uses target uses nodes in uses
 710             GroupingUtils.loadTargetGroupingUses(usesNode, targetGrouping);
 711         }
 712     }
 713
 714     private void finishResolvingUses(final Map<String, TreeMap<Date, ModuleBuilder>> modules) {
 715         final List<UsesNodeBuilder> alluses = new ArrayList<>();
 716         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 717             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 718                 alluses.addAll(inner.getValue().getAllUsesNodes());
 719             }
 720         }
 721         for (UsesNodeBuilder usesNode : alluses) {
 722             ParserUtils.processUsesNode(usesNode);
 723         }
 724         for (UsesNodeBuilder usesNode : alluses) {
 725             ParserUtils.performRefine(usesNode);
 726             ParserUtils.updateUsesParent(usesNode, usesNode.getParent());
 727         }
 728         for (UsesNodeBuilder usesNode : alluses) {
 729             ParserUtils.fixUsesNodesPath(usesNode);
 730         }
 731     }
 732
 733     /**
 734      * Tries to search target grouping in given modules and resolve refine
 735      * nodes. If grouping is not found in modules, method tries to find it in
 736      * modules from context.
 737      *
 738      * @param modules
 739      *            all loaded modules
 740      * @param module
 741      *            current module
 742      * @param context
 743      *            SchemaContext containing already resolved modules
 744      */
 745     private void resolveUsesNodesWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 746             final ModuleBuilder module, final SchemaContext context) {
 747         final List<UsesNodeBuilder> allModuleUses = module.getAllUsesNodes();
 748         for (UsesNodeBuilder usesNode : allModuleUses) {
 749             // process uses operation
 750             final GroupingBuilder targetGrouping = GroupingUtils
 751                     .getTargetGroupingFromModules(usesNode, modules, module);
 752             if (targetGrouping == null) {
 753                 // TODO implement
 754             } else {
 755                 usesNode.setGroupingPath(targetGrouping.getPath());
 756                 GroupingUtils.loadTargetGroupingData(usesNode, targetGrouping);
 757             }
 758         }
 759         for (UsesNodeBuilder usesNode : allModuleUses) {
 760             final GroupingBuilder targetGrouping = GroupingUtils
 761                     .getTargetGroupingFromModules(usesNode, modules, module);
 762             if (targetGrouping == null) {
 763                 // TODO implement
 764             } else {
 765                 GroupingUtils.loadTargetGroupingUses(usesNode, targetGrouping);
 766             }
 767         }
 768     }
 769
 770     // TODO use in implementation
 771     private void processUsesNode(final UsesNodeBuilder usesNode, final GroupingDefinition targetGrouping) {
 772         final String moduleName = usesNode.getModuleName();
 773         final int line = usesNode.getLine();
 774         DataNodeContainerBuilder parent = usesNode.getParent();
 775         URI namespace = null;
 776         Date revision = null;
 777         String prefix = null;
 778         if (parent instanceof ModuleBuilder) {
 779             ModuleBuilder m = (ModuleBuilder) parent;
 780             namespace = m.getNamespace();
 781             revision = m.getRevision();
 782             prefix = m.getPrefix();
 783         } else {
 784             QName parentQName = parent.getQName();
 785             namespace = parentQName.getNamespace();
 786             revision = parentQName.getRevision();
 787             prefix = parentQName.getPrefix();
 788         }
 789         SchemaPath parentPath = parent.getPath();
 790
 791         final Set<DataSchemaNodeBuilder> newChildren = new HashSet<>();
 792         for (DataSchemaNode child : targetGrouping.getChildNodes()) {
 793             if (child != null) {
 794                 DataSchemaNodeBuilder newChild = null;
 795                 QName newQName = new QName(namespace, revision, prefix, child.getQName().getLocalName());
 796                 if (child instanceof AnyXmlSchemaNode) {
 797                     newChild = createAnyXml((AnyXmlSchemaNode) child, newQName, moduleName, line);
 798                 } else if (child instanceof ChoiceNode) {
 799                     newChild = createChoice((ChoiceNode) child, newQName, moduleName, line);
 800                 } else if (child instanceof ContainerSchemaNode) {
 801                     newChild = createContainer((ContainerSchemaNode) child, newQName, moduleName, line);
 802                 } else if (child instanceof LeafListSchemaNode) {
 803                     newChild = createLeafList((LeafListSchemaNode) child, newQName, moduleName, line);
 804                 } else if (child instanceof LeafSchemaNode) {
 805                     newChild = createLeafBuilder((LeafSchemaNode) child, newQName, moduleName, line);
 806                 } else if (child instanceof ListSchemaNode) {
 807                     newChild = createList((ListSchemaNode) child, newQName, moduleName, line);
 808                 }
 809
 810                 if (newChild == null) {
 811                     throw new YangParseException(moduleName, line,
 812                             "Unknown member of target grouping while resolving uses node.");
 813                 }
 814                 if (newChild instanceof GroupingMember) {
 815                     ((GroupingMember) newChild).setAddedByUses(true);
 816                 }
 817
 818                 newChild.setPath(createSchemaPath(parentPath, newQName));
 819                 newChildren.add(newChild);
 820             }
 821         }
 822         usesNode.getFinalChildren().addAll(newChildren);
 823
 824         final Set<GroupingBuilder> newGroupings = new HashSet<>();
 825         for (GroupingDefinition g : targetGrouping.getGroupings()) {
 826             QName newQName = new QName(namespace, revision, prefix, g.getQName().getLocalName());
 827             GroupingBuilder newGrouping = createGrouping(g, newQName, moduleName, line);
 828             newGrouping.setAddedByUses(true);
 829             newGrouping.setPath(createSchemaPath(parentPath, newQName));
 830             newGroupings.add(newGrouping);
 831         }
 832         usesNode.getFinalGroupings().addAll(newGroupings);
 833
 834         final Set<TypeDefinitionBuilder> newTypedefs = new HashSet<>();
 835         for (TypeDefinition<?> td : targetGrouping.getTypeDefinitions()) {
 836             QName newQName = new QName(namespace, revision, prefix, td.getQName().getLocalName());
 837             TypeDefinitionBuilder newType = createTypedef((ExtendedType) td, newQName, moduleName, line);
 838             newType.setAddedByUses(true);
 839             newType.setPath(createSchemaPath(parentPath, newQName));
 840             newTypedefs.add(newType);
 841         }
 842         usesNode.getFinalTypedefs().addAll(newTypedefs);
 843
 844         final List<UnknownSchemaNodeBuilder> newUnknownNodes = new ArrayList<>();
 845         for (UnknownSchemaNode un : targetGrouping.getUnknownSchemaNodes()) {
 846             QName newQName = new QName(namespace, revision, prefix, un.getQName().getLocalName());
 847             UnknownSchemaNodeBuilder newNode = createUnknownSchemaNode(un, newQName, moduleName, line);
 848             newNode.setAddedByUses(true);
 849             newNode.setPath(createSchemaPath(parentPath, newQName));
 850             newUnknownNodes.add(newNode);
 851         }
 852         usesNode.getFinalUnknownNodes().addAll(newUnknownNodes);
 853     }
 854
 855     private void resolveUnknownNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 856         for (UnknownSchemaNodeBuilder usnb : module.getAllUnknownNodes()) {
 857             QName nodeType = usnb.getNodeType();
 858             if (nodeType.getNamespace() == null || nodeType.getRevision() == null) {
 859                 try {
 860                     ModuleBuilder dependentModule = findDependentModuleBuilder(modules, module, nodeType.getPrefix(),
 861                             usnb.getLine());
 862                     QName newNodeType = new QName(dependentModule.getNamespace(), dependentModule.getRevision(),
 863                             nodeType.getPrefix(), nodeType.getLocalName());
 864                     usnb.setNodeType(newNodeType);
 865                 } catch (YangParseException e) {
 866                     LOG.debug(module.getName(), usnb.getLine(), "Failed to find unknown node type: " + nodeType);
 867                 }
 868             }
 869         }
 870     }
 871
 872     private void resolveUnknownNodesWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 873             final ModuleBuilder module, final SchemaContext context) {
 874         for (UnknownSchemaNodeBuilder unknownNodeBuilder : module.getAllUnknownNodes()) {
 875             QName nodeType = unknownNodeBuilder.getNodeType();
 876             if (nodeType.getNamespace() == null || nodeType.getRevision() == null) {
 877                 try {
 878                     ModuleBuilder dependentModuleBuilder = findDependentModuleBuilder(modules, module,
 879                             nodeType.getPrefix(), unknownNodeBuilder.getLine());
 880
 881                     QName newNodeType = null;
 882                     if (dependentModuleBuilder == null) {
 883                         Module dependentModule = findModuleFromContext(context, module, nodeType.getPrefix(),
 884                                 unknownNodeBuilder.getLine());
 885                         newNodeType = new QName(dependentModule.getNamespace(), dependentModule.getRevision(),
 886                                 nodeType.getPrefix(), nodeType.getLocalName());
 887                     } else {
 888                         newNodeType = new QName(dependentModuleBuilder.getNamespace(),
 889                                 dependentModuleBuilder.getRevision(), nodeType.getPrefix(), nodeType.getLocalName());
 890                     }
 891
 892                     unknownNodeBuilder.setNodeType(newNodeType);
 893                 } catch (YangParseException e) {
 894                     LOG.debug(module.getName(), unknownNodeBuilder.getLine(), "Failed to find unknown node type: "
 895                             + nodeType);
 896                 }
 897             }
 898         }
 899     }
 900
 901     /**
 902      * Traverse through modules and resolve their deviation statements.
 903      *
 904      * @param modules
 905      *            all loaded modules
 906      */
 907     private void resolveDeviations(final Map<String, TreeMap<Date, ModuleBuilder>> modules) {
 908         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 909             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 910                 ModuleBuilder b = inner.getValue();
 911                 resolveDeviation(modules, b);
 912             }
 913         }
 914     }
 915
 916     /**
 917      * Traverse through module and resolve its deviation statements.
 918      *
 919      * @param modules
 920      *            all loaded modules
 921      * @param module
 922      *            module in which resolve deviations
 923      */
 924     private void resolveDeviation(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 925         for (DeviationBuilder dev : module.getDeviations()) {
 926             int line = dev.getLine();
 927             SchemaPath targetPath = dev.getTargetPath();
 928             List<QName> path = targetPath.getPath();
 929             QName q0 = path.get(0);
 930             String prefix = q0.getPrefix();
 931             if (prefix == null) {
 932                 prefix = module.getPrefix();
 933             }
 934
 935             ModuleBuilder dependentModuleBuilder = findDependentModuleBuilder(modules, module, prefix, line);
 936             processDeviation(dev, dependentModuleBuilder, path, module);
 937         }
 938     }
 939
 940     /**
 941      * Traverse through modules and resolve their deviation statements with
 942      * given context.
 943      *
 944      * @param modules
 945      *            all loaded modules
 946      * @param context
 947      *            already resolved context
 948      */
 949     private void resolveDeviationsWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 950             final SchemaContext context) {
 951         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 952             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 953                 ModuleBuilder b = inner.getValue();
 954                 resolveDeviationWithContext(modules, b, context);
 955             }
 956         }
 957     }
 958
 959     /**
 960      * Traverse through module and resolve its deviation statements with given
 961      * context.
 962      *
 963      * @param modules
 964      *            all loaded modules
 965      * @param module
 966      *            module in which resolve deviations
 967      * @param context
 968      *            already resolved context
 969      */
 970     private void resolveDeviationWithContext(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 971             final ModuleBuilder module, final SchemaContext context) {
 972         for (DeviationBuilder dev : module.getDeviations()) {
 973             int line = dev.getLine();
 974             SchemaPath targetPath = dev.getTargetPath();
 975             List<QName> path = targetPath.getPath();
 976             QName q0 = path.get(0);
 977             String prefix = q0.getPrefix();
 978             if (prefix == null) {
 979                 prefix = module.getPrefix();
 980             }
 981             String name = null;
 982
 983             ModuleBuilder dependentModuleBuilder = findDependentModuleBuilder(modules, module, prefix, line);
 984             if (dependentModuleBuilder == null) {
 985                 Module dependentModule = findModuleFromContext(context, module, prefix, line);
 986                 Object currentParent = dependentModule;
 987
 988                 for (int i = 0; i < path.size(); i++) {
 989                     if (currentParent == null) {
 990                         throw new YangParseException(module.getName(), line, "Failed to find deviation target.");
 991                     }
 992                     QName q = path.get(i);
 993                     name = q.getLocalName();
 994                     if (currentParent instanceof DataNodeContainer) {
 995                         currentParent = ((DataNodeContainer) currentParent).getDataChildByName(name);
 996                     }
 997                 }
 998
 999                 if (currentParent == null) {
1000                     throw new YangParseException(module.getName(), line, "Failed to find deviation target.");
1001                 }
1002                 if (currentParent instanceof SchemaNode) {
1003                     dev.setTargetPath(((SchemaNode) currentParent).getPath());
1004                 }
1005
1006             } else {
1007                 processDeviation(dev, dependentModuleBuilder, path, module);
1008             }
1009         }
1010     }
1011
1012     /**
1013      * Correct deviation target path in deviation builder.
1014      *
1015      * @param dev
1016      *            deviation
1017      * @param dependentModuleBuilder
1018      *            module containing deviation target
1019      * @param path
1020      *            current deviation target path
1021      * @param module
1022      *            current module
1023      */
1024     private void processDeviation(final DeviationBuilder dev, final ModuleBuilder dependentModuleBuilder,
1025             final List<QName> path, final ModuleBuilder module) {
1026         final int line = dev.getLine();
1027         Builder currentParent = dependentModuleBuilder;
1028
1029         for (int i = 0; i < path.size(); i++) {
1030             if (currentParent == null) {
1031                 throw new YangParseException(module.getName(), line, "Failed to find deviation target.");
1032             }
1033             QName q = path.get(i);
1034             String name = q.getLocalName();
1035             if (currentParent instanceof DataNodeContainerBuilder) {
1036                 currentParent = ((DataNodeContainerBuilder) currentParent).getDataChildByName(name);
1037             }
1038         }
1039
1040         if (currentParent == null || !(currentParent instanceof SchemaNodeBuilder)) {
1041             throw new YangParseException(module.getName(), line, "Failed to find deviation target.");
1042         }
1043         dev.setTargetPath(((SchemaNodeBuilder) currentParent).getPath());
1044     }
1045
1046 }