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