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