opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/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.controller.yang.parser.impl;
   9
  10 import java.io.File;
  11 import java.io.FileInputStream;
  12 import java.io.FileNotFoundException;
  13 import java.io.IOException;
  14 import java.io.InputStream;
  15 import java.util.ArrayList;
  16 import java.util.Collections;
  17 import java.util.Date;
  18 import java.util.HashMap;
  19 import java.util.HashSet;
  20 import java.util.Iterator;
  21 import java.util.LinkedHashMap;
  22 import java.util.List;
  23 import java.util.Map;
  24 import java.util.Map.Entry;
  25 import java.util.NoSuchElementException;
  26 import java.util.Set;
  27 import java.util.TreeMap;
  28
  29 import org.antlr.v4.runtime.ANTLRInputStream;
  30 import org.antlr.v4.runtime.CommonTokenStream;
  31 import org.antlr.v4.runtime.tree.ParseTree;
  32 import org.antlr.v4.runtime.tree.ParseTreeWalker;
  33 import org.opendaylight.controller.antlrv4.code.gen.YangLexer;
  34 import org.opendaylight.controller.antlrv4.code.gen.YangParser;
  35 import org.opendaylight.controller.yang.common.QName;
  36 import org.opendaylight.controller.yang.model.api.Module;
  37 import org.opendaylight.controller.yang.model.api.ModuleImport;
  38 import org.opendaylight.controller.yang.model.api.SchemaContext;
  39 import org.opendaylight.controller.yang.model.api.SchemaPath;
  40 import org.opendaylight.controller.yang.model.api.TypeDefinition;
  41 import org.opendaylight.controller.yang.model.api.type.BinaryTypeDefinition;
  42 import org.opendaylight.controller.yang.model.api.type.DecimalTypeDefinition;
  43 import org.opendaylight.controller.yang.model.api.type.IntegerTypeDefinition;
  44 import org.opendaylight.controller.yang.model.api.type.StringTypeDefinition;
  45 import org.opendaylight.controller.yang.model.parser.api.YangModelParser;
  46 import org.opendaylight.controller.yang.model.util.ExtendedType;
  47 import org.opendaylight.controller.yang.model.util.IdentityrefType;
  48 import org.opendaylight.controller.yang.model.util.UnknownType;
  49 import org.opendaylight.controller.yang.parser.builder.api.AugmentationSchemaBuilder;
  50 import org.opendaylight.controller.yang.parser.builder.api.AugmentationTargetBuilder;
  51 import org.opendaylight.controller.yang.parser.builder.api.Builder;
  52 import org.opendaylight.controller.yang.parser.builder.api.DataNodeContainerBuilder;
  53 import org.opendaylight.controller.yang.parser.builder.api.DataSchemaNodeBuilder;
  54 import org.opendaylight.controller.yang.parser.builder.api.GroupingBuilder;
  55 import org.opendaylight.controller.yang.parser.builder.api.SchemaNodeBuilder;
  56 import org.opendaylight.controller.yang.parser.builder.api.TypeAwareBuilder;
  57 import org.opendaylight.controller.yang.parser.builder.api.TypeDefinitionBuilder;
  58 import org.opendaylight.controller.yang.parser.builder.api.UsesNodeBuilder;
  59 import org.opendaylight.controller.yang.parser.builder.impl.AnyXmlBuilder;
  60 import org.opendaylight.controller.yang.parser.builder.impl.ChoiceBuilder;
  61 import org.opendaylight.controller.yang.parser.builder.impl.ContainerSchemaNodeBuilder;
  62 import org.opendaylight.controller.yang.parser.builder.impl.IdentitySchemaNodeBuilder;
  63 import org.opendaylight.controller.yang.parser.builder.impl.IdentityrefTypeBuilder;
  64 import org.opendaylight.controller.yang.parser.builder.impl.LeafListSchemaNodeBuilder;
  65 import org.opendaylight.controller.yang.parser.builder.impl.LeafSchemaNodeBuilder;
  66 import org.opendaylight.controller.yang.parser.builder.impl.ListSchemaNodeBuilder;
  67 import org.opendaylight.controller.yang.parser.builder.impl.ModuleBuilder;
  68 import org.opendaylight.controller.yang.parser.builder.impl.RpcDefinitionBuilder;
  69 import org.opendaylight.controller.yang.parser.builder.impl.TypeDefinitionBuilderImpl;
  70 import org.opendaylight.controller.yang.parser.builder.impl.UnionTypeBuilder;
  71 import org.opendaylight.controller.yang.parser.builder.impl.UnknownSchemaNodeBuilder;
  72 import org.opendaylight.controller.yang.parser.util.ModuleDependencySort;
  73 import org.opendaylight.controller.yang.parser.util.ParserUtils;
  74 import org.opendaylight.controller.yang.parser.util.RefineHolder;
  75 import org.opendaylight.controller.yang.parser.util.TypeConstraints;
  76 import org.opendaylight.controller.yang.parser.util.YangParseException;
  77 import org.opendaylight.controller.yang.validator.YangModelBasicValidator;
  78 import org.slf4j.Logger;
  79 import org.slf4j.LoggerFactory;
  80
  81 import com.google.common.collect.Lists;
  82 import com.google.common.collect.Maps;
  83 import com.google.common.collect.Sets;
  84
  85 public final class YangParserImpl implements YangModelParser {
  86
  87     private static final Logger logger = LoggerFactory.getLogger(YangParserImpl.class);
  88
  89     @Override
  90     public Map<File, Module> parseYangModelsMapped(List<File> yangFiles) {
  91         if (yangFiles != null) {
  92             final Map<InputStream, File> inputStreams = Maps.newHashMap();
  93
  94             for (final File yangFile : yangFiles) {
  95                 try {
  96                     inputStreams.put(new FileInputStream(yangFile), yangFile);
  97                 } catch (FileNotFoundException e) {
  98                     logger.warn("Exception while reading yang file: " + yangFile.getName(), e);
  99                 }
 100             }
 101
 102             Map<ModuleBuilder, InputStream> builderToStreamMap = Maps.newHashMap();
 103
 104             final Map<String, TreeMap<Date, ModuleBuilder>> modules = resolveModuleBuilders(
 105                     Lists.newArrayList(inputStreams.keySet()), builderToStreamMap);
 106             // return new LinkedHashSet<Module>(build(modules).values());
 107
 108             Map<File, Module> retVal = Maps.newLinkedHashMap();
 109             Map<ModuleBuilder, Module> builderToModuleMap = build(modules);
 110
 111             for (Entry<ModuleBuilder, Module> builderToModule : builderToModuleMap.entrySet()) {
 112                 retVal.put(inputStreams.get(builderToStreamMap.get(builderToModule.getKey())),
 113                         builderToModule.getValue());
 114             }
 115
 116             return retVal;
 117         }
 118         return Collections.emptyMap();
 119     }
 120
 121     @Override
 122     public Set<Module> parseYangModels(final List<File> yangFiles) {
 123         return Sets.newLinkedHashSet(parseYangModelsMapped(yangFiles).values());
 124     }
 125
 126     @Override
 127     public Set<Module> parseYangModelsFromStreams(final List<InputStream> yangModelStreams) {
 128         return Sets.newHashSet(parseYangModelsFromStreamsMapped(yangModelStreams).values());
 129     }
 130
 131     @Override
 132     public Map<InputStream, Module> parseYangModelsFromStreamsMapped(final List<InputStream> yangModelStreams) {
 133         Map<ModuleBuilder, InputStream> builderToStreamMap = Maps.newHashMap();
 134
 135         final Map<String, TreeMap<Date, ModuleBuilder>> modules = resolveModuleBuilders(yangModelStreams,
 136                 builderToStreamMap);
 137         Map<InputStream, Module> retVal = Maps.newLinkedHashMap();
 138         Map<ModuleBuilder, Module> builderToModuleMap = build(modules);
 139
 140         for (Entry<ModuleBuilder, Module> builderToModule : builderToModuleMap.entrySet()) {
 141             retVal.put(builderToStreamMap.get(builderToModule.getKey()), builderToModule.getValue());
 142         }
 143         return retVal;
 144     }
 145
 146     @Override
 147     public SchemaContext resolveSchemaContext(final Set<Module> modules) {
 148         return new SchemaContextImpl(modules);
 149     }
 150
 151     private ModuleBuilder[] parseModuleBuilders(List<InputStream> inputStreams,
 152             Map<ModuleBuilder, InputStream> streamToBuilderMap) {
 153
 154         final ParseTreeWalker walker = new ParseTreeWalker();
 155         final List<ParseTree> trees = parseStreams(inputStreams);
 156         final ModuleBuilder[] builders = new ModuleBuilder[trees.size()];
 157
 158         // validate yang
 159         new YangModelBasicValidator(walker).validate(trees);
 160
 161         YangParserListenerImpl yangModelParser = null;
 162         for (int i = 0; i < trees.size(); i++) {
 163             yangModelParser = new YangParserListenerImpl();
 164             walker.walk(yangModelParser, trees.get(i));
 165             ModuleBuilder moduleBuilder = yangModelParser.getModuleBuilder();
 166
 167             // We expect the order of trees and streams has to be the same
 168             streamToBuilderMap.put(moduleBuilder, inputStreams.get(i));
 169             builders[i] = moduleBuilder;
 170         }
 171         return builders;
 172     }
 173
 174     private Map<String, TreeMap<Date, ModuleBuilder>> resolveModuleBuilders(final List<InputStream> yangFileStreams,
 175             Map<ModuleBuilder, InputStream> streamToBuilderMap) {
 176
 177         final ModuleBuilder[] builders = parseModuleBuilders(yangFileStreams, streamToBuilderMap);
 178
 179         // Linked Hash Map MUST be used because Linked Hash Map preserves ORDER
 180         // of items stored in map.
 181         final LinkedHashMap<String, TreeMap<Date, ModuleBuilder>> modules = new LinkedHashMap<String, TreeMap<Date, ModuleBuilder>>();
 182
 183         // module dependency graph sorted
 184         List<ModuleBuilder> sorted = ModuleDependencySort.sort(builders);
 185
 186         for (ModuleBuilder builder : sorted) {
 187             final String builderName = builder.getName();
 188             Date builderRevision = builder.getRevision();
 189             if (builderRevision == null) {
 190                 builderRevision = new Date(0L);
 191             }
 192             TreeMap<Date, ModuleBuilder> builderByRevision = modules.get(builderName);
 193             if (builderByRevision == null) {
 194                 builderByRevision = new TreeMap<Date, ModuleBuilder>();
 195             }
 196             builderByRevision.put(builderRevision, builder);
 197             modules.put(builderName, builderByRevision);
 198         }
 199         return modules;
 200     }
 201
 202     private List<ParseTree> parseStreams(final List<InputStream> yangStreams) {
 203         final List<ParseTree> trees = new ArrayList<ParseTree>();
 204         for (InputStream yangStream : yangStreams) {
 205             trees.add(parseStream(yangStream));
 206         }
 207         return trees;
 208     }
 209
 210     private ParseTree parseStream(final InputStream yangStream) {
 211         ParseTree result = null;
 212         try {
 213             final ANTLRInputStream input = new ANTLRInputStream(yangStream);
 214             final YangLexer lexer = new YangLexer(input);
 215             final CommonTokenStream tokens = new CommonTokenStream(lexer);
 216             final YangParser parser = new YangParser(tokens);
 217
 218             result = parser.yang();
 219         } catch (IOException e) {
 220             logger.warn("Exception while reading yang file: " + yangStream, e);
 221         }
 222         return result;
 223     }
 224
 225     private Map<ModuleBuilder, Module> build(final Map<String, TreeMap<Date, ModuleBuilder>> modules) {
 226         // fix unresolved nodes
 227         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 228             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 229                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 230                 fixUnresolvedNodes(modules, moduleBuilder);
 231             }
 232         }
 233         resolveAugments(modules);
 234
 235         // build
 236         // LinkedHashMap MUST be used otherwise the values will not maintain
 237         // order!
 238         // http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html
 239         final Map<ModuleBuilder, Module> result = new LinkedHashMap<ModuleBuilder, Module>();
 240         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 241             final Map<Date, Module> modulesByRevision = new HashMap<Date, Module>();
 242             for (Map.Entry<Date, ModuleBuilder> childEntry : entry.getValue().entrySet()) {
 243                 final ModuleBuilder moduleBuilder = childEntry.getValue();
 244                 final Module module = moduleBuilder.build();
 245                 modulesByRevision.put(childEntry.getKey(), module);
 246                 result.put(moduleBuilder, module);
 247             }
 248         }
 249         return result;
 250     }
 251
 252     private void fixUnresolvedNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder builder) {
 253         resolveDirtyNodes(modules, builder);
 254         resolveIdentities(modules, builder);
 255         resolveUsesRefines(modules, builder);
 256         resolveUnknownNodes(modules, builder);
 257     }
 258
 259     /**
 260      * Search for dirty nodes (node which contains UnknownType) and resolve
 261      * unknown types.
 262      *
 263      * @param modules
 264      *            all available modules
 265      * @param module
 266      *            current module
 267      */
 268     private void resolveDirtyNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 269         final Map<List<String>, TypeAwareBuilder> dirtyNodes = module.getDirtyNodes();
 270         if (!dirtyNodes.isEmpty()) {
 271             for (Map.Entry<List<String>, TypeAwareBuilder> entry : dirtyNodes.entrySet()) {
 272                 final TypeAwareBuilder nodeToResolve = entry.getValue();
 273
 274                 if (nodeToResolve instanceof UnionTypeBuilder) {
 275                     // special handling for union types
 276                     resolveTypeUnion((UnionTypeBuilder) nodeToResolve, modules, module);
 277                 } else if (nodeToResolve.getTypedef() instanceof IdentityrefTypeBuilder) {
 278                     // special handling for identityref types
 279                     IdentityrefTypeBuilder idref = (IdentityrefTypeBuilder) nodeToResolve.getTypedef();
 280                     nodeToResolve.setType(new IdentityrefType(findFullQName(modules, module, idref), idref.getPath()));
 281                 } else {
 282                     resolveType(nodeToResolve, modules, module);
 283                 }
 284             }
 285         }
 286     }
 287
 288     private void resolveType(final TypeAwareBuilder nodeToResolve,
 289             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder builder) {
 290         TypeDefinitionBuilder resolvedType = null;
 291         final int line = nodeToResolve.getLine();
 292         final TypeDefinition<?> nodeToResolveType = nodeToResolve.getType();
 293         final QName unknownTypeQName = nodeToResolveType.getBaseType().getQName();
 294         final ModuleBuilder dependentModule = findDependentModule(modules, builder, unknownTypeQName.getPrefix(), line);
 295
 296         final TypeDefinitionBuilder targetTypeBuilder = findTypeDefinitionBuilder(nodeToResolve.getPath(),
 297                 dependentModule, unknownTypeQName.getLocalName(), builder.getName(), line);
 298
 299         if (nodeToResolveType instanceof ExtendedType) {
 300             final ExtendedType extType = (ExtendedType) nodeToResolveType;
 301             final TypeDefinitionBuilder newType = extendedTypeWithNewBaseType(nodeToResolve, targetTypeBuilder,
 302                     extType, modules, builder);
 303             resolvedType = newType;
 304         } else {
 305             resolvedType = targetTypeBuilder;
 306         }
 307
 308         // validate constraints
 309         final TypeConstraints constraints = findConstraints(nodeToResolve, new TypeConstraints(builder.getName(),
 310                 nodeToResolve.getLine()), modules, builder);
 311         constraints.validateConstraints();
 312
 313         nodeToResolve.setTypedef(resolvedType);
 314     }
 315
 316     private void resolveTypeUnion(final UnionTypeBuilder union,
 317             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder builder) {
 318
 319         final List<TypeDefinition<?>> unionTypes = union.getTypes();
 320         final List<TypeDefinition<?>> toRemove = new ArrayList<TypeDefinition<?>>();
 321         for (TypeDefinition<?> unionType : unionTypes) {
 322             if (unionType instanceof UnknownType) {
 323                 final UnknownType ut = (UnknownType) unionType;
 324                 final ModuleBuilder dependentModule = findDependentModule(modules, builder, ut.getQName().getPrefix(),
 325                         union.getLine());
 326                 final TypeDefinitionBuilder resolvedType = findTypeDefinitionBuilder(union.getPath(), dependentModule,
 327                         ut.getQName().getLocalName(), builder.getName(), union.getLine());
 328                 union.setTypedef(resolvedType);
 329                 toRemove.add(ut);
 330             } else if (unionType instanceof ExtendedType) {
 331                 final ExtendedType extType = (ExtendedType) unionType;
 332                 TypeDefinition<?> extTypeBase = extType.getBaseType();
 333                 if (extTypeBase instanceof UnknownType) {
 334                     final UnknownType ut = (UnknownType) extTypeBase;
 335                     final ModuleBuilder dependentModule = findDependentModule(modules, builder, ut.getQName()
 336                             .getPrefix(), union.getLine());
 337                     final TypeDefinitionBuilder targetTypeBuilder = findTypeDefinitionBuilder(union.getPath(),
 338                             dependentModule, ut.getQName().getLocalName(), builder.getName(), union.getLine());
 339
 340                     final TypeDefinitionBuilder newType = extendedTypeWithNewBaseType(targetTypeBuilder,
 341                             targetTypeBuilder, extType, modules, builder);
 342
 343                     union.setTypedef(newType);
 344                     toRemove.add(extType);
 345                 }
 346             }
 347         }
 348         unionTypes.removeAll(toRemove);
 349     }
 350
 351     private TypeDefinitionBuilder extendedTypeWithNewBaseType(final TypeAwareBuilder nodeToResolve,
 352             final TypeDefinitionBuilder newBaseType, final ExtendedType oldExtendedType,
 353             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder builder) {
 354         final TypeConstraints constraints = findConstraints(nodeToResolve, new TypeConstraints(builder.getName(),
 355                 nodeToResolve.getLine()), modules, builder);
 356         final TypeDefinitionBuilderImpl newType = new TypeDefinitionBuilderImpl(oldExtendedType.getQName(),
 357                 nodeToResolve.getLine());
 358         newType.setTypedef(newBaseType);
 359         newType.setPath(oldExtendedType.getPath());
 360         newType.setDescription(oldExtendedType.getDescription());
 361         newType.setReference(oldExtendedType.getReference());
 362         newType.setStatus(oldExtendedType.getStatus());
 363         newType.setLengths(constraints.getLength());
 364         newType.setPatterns(constraints.getPatterns());
 365         newType.setRanges(constraints.getRange());
 366         newType.setFractionDigits(constraints.getFractionDigits());
 367         newType.setUnits(oldExtendedType.getUnits());
 368         newType.setDefaultValue(oldExtendedType.getDefaultValue());
 369         newType.setUnknownNodes(oldExtendedType.getUnknownSchemaNodes());
 370         return newType;
 371     }
 372
 373     private TypeConstraints findConstraints(final TypeAwareBuilder nodeToResolve, final TypeConstraints constraints,
 374             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder builder) {
 375
 376         // union type cannot be restricted
 377         if (nodeToResolve instanceof UnionTypeBuilder) {
 378             return constraints;
 379         }
 380
 381         if (nodeToResolve instanceof TypeDefinitionBuilder) {
 382             TypeDefinitionBuilder typedefToResolve = (TypeDefinitionBuilder) nodeToResolve;
 383             constraints.addFractionDigits(typedefToResolve.getFractionDigits());
 384             constraints.addLengths(typedefToResolve.getLengths());
 385             constraints.addPatterns(typedefToResolve.getPatterns());
 386             constraints.addRanges(typedefToResolve.getRanges());
 387         }
 388
 389         TypeDefinition<?> type = nodeToResolve.getType();
 390         if (type == null) {
 391             return findConstraints(nodeToResolve.getTypedef(), constraints, modules, builder);
 392         } else {
 393             if (type instanceof UnknownType) {
 394                 ModuleBuilder dependentModule = findDependentModule(modules, builder, type.getQName().getPrefix(),
 395                         nodeToResolve.getLine());
 396                 TypeDefinitionBuilder tdb = findTypeDefinitionBuilder(nodeToResolve.getPath(), dependentModule, type
 397                         .getQName().getLocalName(), builder.getName(), nodeToResolve.getLine());
 398                 return findConstraints(tdb, constraints, modules, dependentModule);
 399             } else if (type instanceof ExtendedType) {
 400                 ExtendedType extType = (ExtendedType) type;
 401                 constraints.addFractionDigits(extType.getFractionDigits());
 402                 constraints.addLengths(extType.getLengths());
 403                 constraints.addPatterns(extType.getPatterns());
 404                 constraints.addRanges(extType.getRanges());
 405
 406                 TypeDefinition<?> base = extType.getBaseType();
 407                 if (base instanceof UnknownType) {
 408                     ModuleBuilder dependentModule = findDependentModule(modules, builder, base.getQName().getPrefix(),
 409                             nodeToResolve.getLine());
 410                     TypeDefinitionBuilder tdb = findTypeDefinitionBuilder(nodeToResolve.getPath(), dependentModule,
 411                             base.getQName().getLocalName(), builder.getName(), nodeToResolve.getLine());
 412                     return findConstraints(tdb, constraints, modules, dependentModule);
 413                 } else {
 414                     // it has to be base yang type
 415                     mergeConstraints(type, constraints);
 416                     return constraints;
 417                 }
 418             } else {
 419                 // it is base yang type
 420                 mergeConstraints(type, constraints);
 421                 return constraints;
 422             }
 423         }
 424     }
 425
 426     /**
 427      * Search for type definition builder by name.
 428      *
 429      * @param dirtyNodeSchemaPath
 430      *            schema path of node which contains unresolved type
 431      * @param dependentModule
 432      *            module which should contains referenced type
 433      * @param typeName
 434      *            name of type definition
 435      * @param currentModuleName
 436      *            name of current module
 437      * @param line
 438      *            current line in yang model
 439      * @return
 440      */
 441     private TypeDefinitionBuilder findTypeDefinitionBuilder(SchemaPath dirtyNodeSchemaPath,
 442             final ModuleBuilder dependentModule, final String typeName, final String currentModuleName, final int line) {
 443         final List<QName> path = dirtyNodeSchemaPath.getPath();
 444         TypeDefinitionBuilder result = null;
 445
 446         Set<TypeDefinitionBuilder> typedefs = dependentModule.getModuleTypedefs();
 447         result = findTdb(typedefs, typeName);
 448
 449         if (result == null) {
 450             Builder currentNode = null;
 451             final List<String> currentPath = new ArrayList<String>();
 452             currentPath.add(dependentModule.getName());
 453
 454             for (int i = 0; i < path.size(); i++) {
 455                 QName qname = path.get(i);
 456                 currentPath.add(qname.getLocalName());
 457                 currentNode = dependentModule.getModuleNode(currentPath);
 458
 459                 if (currentNode instanceof RpcDefinitionBuilder) {
 460                     typedefs = ((RpcDefinitionBuilder) currentNode).getTypeDefinitions();
 461                 } else if (currentNode instanceof DataNodeContainerBuilder) {
 462                     typedefs = ((DataNodeContainerBuilder) currentNode).getTypeDefinitions();
 463                 } else {
 464                     typedefs = Collections.emptySet();
 465                 }
 466
 467                 result = findTdb(typedefs, typeName);
 468                 if (result != null) {
 469                     break;
 470                 }
 471             }
 472         }
 473
 474         if (result != null) {
 475             return result;
 476         }
 477         throw new YangParseException(currentModuleName, line, "Referenced type '" + typeName + "' not found.");
 478     }
 479
 480     private TypeDefinitionBuilder findTdb(Set<TypeDefinitionBuilder> types, String name) {
 481         for (TypeDefinitionBuilder td : types) {
 482             if (td.getQName().getLocalName().equals(name)) {
 483                 return td;
 484             }
 485         }
 486         return null;
 487     }
 488
 489     /**
 490      * Pull restriction from referenced type and add them to given constraints
 491      *
 492      * @param referencedType
 493      * @param constraints
 494      */
 495     private void mergeConstraints(final TypeDefinition<?> referencedType, final TypeConstraints constraints) {
 496
 497         if (referencedType instanceof DecimalTypeDefinition) {
 498             constraints.addRanges(((DecimalTypeDefinition) referencedType).getRangeStatements());
 499             constraints.addFractionDigits(((DecimalTypeDefinition) referencedType).getFractionDigits());
 500         } else if (referencedType instanceof IntegerTypeDefinition) {
 501             constraints.addRanges(((IntegerTypeDefinition) referencedType).getRangeStatements());
 502         } else if (referencedType instanceof StringTypeDefinition) {
 503             constraints.addPatterns(((StringTypeDefinition) referencedType).getPatterns());
 504             constraints.addLengths(((StringTypeDefinition) referencedType).getLengthStatements());
 505         } else if (referencedType instanceof BinaryTypeDefinition) {
 506             constraints.addLengths(((BinaryTypeDefinition) referencedType).getLengthConstraints());
 507         }
 508     }
 509
 510     /**
 511      * Go through all augment definitions and resolve them. This method also
 512      * finds augment target node and add child nodes to it.
 513      *
 514      * @param modules
 515      *            all available modules
 516      */
 517     private void resolveAugments(final Map<String, TreeMap<Date, ModuleBuilder>> modules) {
 518         final List<ModuleBuilder> allModulesList = new ArrayList<ModuleBuilder>();
 519         final Set<ModuleBuilder> allModulesSet = new HashSet<ModuleBuilder>();
 520         for (Map.Entry<String, TreeMap<Date, ModuleBuilder>> entry : modules.entrySet()) {
 521             for (Map.Entry<Date, ModuleBuilder> inner : entry.getValue().entrySet()) {
 522                 allModulesList.add(inner.getValue());
 523                 allModulesSet.add(inner.getValue());
 524             }
 525         }
 526
 527         for (int i = 0; i < allModulesList.size(); i++) {
 528             final ModuleBuilder module = allModulesList.get(i);
 529             // try to resolve augments in module
 530             resolveAugment(modules, module);
 531             // while all augments are not resolved
 532             final Iterator<ModuleBuilder> allModulesIterator = allModulesSet.iterator();
 533             while (!(module.getAugmentsResolved() == module.getAugments().size())) {
 534                 ModuleBuilder nextModule = null;
 535                 // try resolve other module augments
 536                 try {
 537                     nextModule = allModulesIterator.next();
 538                     resolveAugment(modules, nextModule);
 539                 } catch (NoSuchElementException e) {
 540                     throw new YangParseException("Failed to resolve augments in module '" + module.getName() + "'.", e);
 541                 }
 542                 // then try to resolve first module again
 543                 resolveAugment(modules, module);
 544             }
 545         }
 546     }
 547
 548     /**
 549      *
 550      * @param modules
 551      *            all available modules
 552      * @param module
 553      *            current module
 554      */
 555     private void resolveAugment(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 556         if (module.getAugmentsResolved() < module.getAugments().size()) {
 557             for (AugmentationSchemaBuilder augmentBuilder : module.getAugments()) {
 558
 559                 if (!augmentBuilder.isResolved()) {
 560                     final SchemaPath augmentTargetSchemaPath = augmentBuilder.getTargetPath();
 561                     final List<QName> path = augmentTargetSchemaPath.getPath();
 562
 563                     final QName qname = path.get(0);
 564                     String prefix = qname.getPrefix();
 565                     if (prefix == null) {
 566                         prefix = module.getPrefix();
 567                     }
 568
 569                     DataSchemaNodeBuilder currentParent = null;
 570                     final ModuleBuilder dependentModule = findDependentModule(modules, module, prefix,
 571                             augmentBuilder.getLine());
 572                     for (DataSchemaNodeBuilder child : dependentModule.getChildNodes()) {
 573                         final QName childQName = child.getQName();
 574                         if (childQName.getLocalName().equals(qname.getLocalName())) {
 575                             currentParent = child;
 576                             break;
 577                         }
 578                     }
 579
 580                     if (currentParent == null) {
 581                         continue;
 582                     }
 583
 584                     for (int i = 1; i < path.size(); i++) {
 585                         final QName currentQName = path.get(i);
 586                         DataSchemaNodeBuilder newParent = null;
 587                         for (DataSchemaNodeBuilder child : ((DataNodeContainerBuilder) currentParent).getChildNodes()) {
 588                             final QName childQName = child.getQName();
 589                             if (childQName.getLocalName().equals(currentQName.getLocalName())) {
 590                                 newParent = child;
 591                                 break;
 592                             }
 593                         }
 594                         if (newParent == null) {
 595                             break; // node not found, quit search
 596                         } else {
 597                             currentParent = newParent;
 598                         }
 599                     }
 600
 601                     final QName currentQName = currentParent.getQName();
 602                     final QName lastAugmentPathElement = path.get(path.size() - 1);
 603                     if (currentQName.getLocalName().equals(lastAugmentPathElement.getLocalName())) {
 604
 605                         if (currentParent instanceof ChoiceBuilder) {
 606                             ParserUtils.fillAugmentTarget(augmentBuilder, (ChoiceBuilder) currentParent);
 607                         } else {
 608                             ParserUtils.fillAugmentTarget(augmentBuilder, (DataNodeContainerBuilder) currentParent);
 609                         }
 610                         ((AugmentationTargetBuilder) currentParent).addAugmentation(augmentBuilder);
 611                         SchemaPath oldPath = currentParent.getPath();
 612                         augmentBuilder.setTargetPath(new SchemaPath(oldPath.getPath(), oldPath.isAbsolute()));
 613                         augmentBuilder.setResolved(true);
 614                         module.augmentResolved();
 615                     }
 616                 }
 617
 618             }
 619         }
 620     }
 621
 622     /**
 623      * Go through identity statements defined in current module and resolve
 624      * their 'base' statement if present.
 625      *
 626      * @param modules
 627      *            all modules
 628      * @param module
 629      *            module being resolved
 630      */
 631     private void resolveIdentities(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 632         final Set<IdentitySchemaNodeBuilder> identities = module.getIdentities();
 633         for (IdentitySchemaNodeBuilder identity : identities) {
 634             final String baseIdentityName = identity.getBaseIdentityName();
 635             if (baseIdentityName != null) {
 636                 String baseIdentityPrefix = null;
 637                 String baseIdentityLocalName = null;
 638                 if (baseIdentityName.contains(":")) {
 639                     final String[] splitted = baseIdentityName.split(":");
 640                     baseIdentityPrefix = splitted[0];
 641                     baseIdentityLocalName = splitted[1];
 642                 } else {
 643                     baseIdentityPrefix = module.getPrefix();
 644                     baseIdentityLocalName = baseIdentityName;
 645                 }
 646                 final ModuleBuilder dependentModule = findDependentModule(modules, module, baseIdentityPrefix,
 647                         identity.getLine());
 648
 649                 final Set<IdentitySchemaNodeBuilder> dependentModuleIdentities = dependentModule.getIdentities();
 650                 for (IdentitySchemaNodeBuilder idBuilder : dependentModuleIdentities) {
 651                     if (idBuilder.getQName().getLocalName().equals(baseIdentityLocalName)) {
 652                         identity.setBaseIdentity(idBuilder);
 653                     }
 654                 }
 655             }
 656         }
 657     }
 658
 659     /**
 660      * Go through uses statements defined in current module and resolve their
 661      * refine statements.
 662      *
 663      * @param modules
 664      *            all modules
 665      * @param module
 666      *            module being resolved
 667      */
 668     private void resolveUsesRefines(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 669         final Map<List<String>, UsesNodeBuilder> moduleUses = module.getUsesNodes();
 670         for (Map.Entry<List<String>, UsesNodeBuilder> entry : moduleUses.entrySet()) {
 671             final UsesNodeBuilder usesNode = entry.getValue();
 672             final int line = usesNode.getLine();
 673
 674             GroupingBuilder targetGrouping = getTargetGrouping(usesNode, modules, module);
 675             usesNode.setGroupingPath(targetGrouping.getPath());
 676
 677             for (RefineHolder refine : usesNode.getRefines()) {
 678                 SchemaNodeBuilder refineTarget = getRefineNodeBuilderCopy(targetGrouping, refine, modules, module);
 679                 ParserUtils.checkRefine(refineTarget, refine);
 680                 ParserUtils.refineDefault(refineTarget, refine, line);
 681                 if (refineTarget instanceof LeafSchemaNodeBuilder) {
 682                     final LeafSchemaNodeBuilder leaf = (LeafSchemaNodeBuilder) refineTarget;
 683                     ParserUtils.refineLeaf(leaf, refine, line);
 684                     usesNode.addRefineNode(leaf);
 685                 } else if (refineTarget instanceof ContainerSchemaNodeBuilder) {
 686                     final ContainerSchemaNodeBuilder container = (ContainerSchemaNodeBuilder) refineTarget;
 687                     ParserUtils.refineContainer(container, refine, line);
 688                     usesNode.addRefineNode(container);
 689                 } else if (refineTarget instanceof ListSchemaNodeBuilder) {
 690                     final ListSchemaNodeBuilder list = (ListSchemaNodeBuilder) refineTarget;
 691                     ParserUtils.refineList(list, refine, line);
 692                     usesNode.addRefineNode(list);
 693                 } else if (refineTarget instanceof LeafListSchemaNodeBuilder) {
 694                     final LeafListSchemaNodeBuilder leafList = (LeafListSchemaNodeBuilder) refineTarget;
 695                     ParserUtils.refineLeafList(leafList, refine, line);
 696                     usesNode.addRefineNode(leafList);
 697                 } else if (refineTarget instanceof ChoiceBuilder) {
 698                     final ChoiceBuilder choice = (ChoiceBuilder) refineTarget;
 699                     ParserUtils.refineChoice(choice, refine, line);
 700                     usesNode.addRefineNode(choice);
 701                 } else if (refineTarget instanceof AnyXmlBuilder) {
 702                     final AnyXmlBuilder anyXml = (AnyXmlBuilder) refineTarget;
 703                     ParserUtils.refineAnyxml(anyXml, refine, line);
 704                     usesNode.addRefineNode(anyXml);
 705                 } else if (refineTarget instanceof GroupingBuilder) {
 706                     usesNode.addRefineNode(refineTarget);
 707                 } else if (refineTarget instanceof TypeDefinitionBuilder) {
 708                     usesNode.addRefineNode(refineTarget);
 709                 }
 710             }
 711         }
 712     }
 713
 714     private GroupingBuilder getTargetGrouping(final UsesNodeBuilder usesBuilder,
 715             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 716         final int line = usesBuilder.getLine();
 717         String groupingString = usesBuilder.getGroupingName();
 718         String groupingPrefix;
 719         String groupingName;
 720
 721         if (groupingString.contains(":")) {
 722             String[] splitted = groupingString.split(":");
 723             if (splitted.length != 2 || groupingString.contains("/")) {
 724                 throw new YangParseException(module.getName(), line, "Invalid name of target grouping");
 725             }
 726             groupingPrefix = splitted[0];
 727             groupingName = splitted[1];
 728         } else {
 729             groupingPrefix = module.getPrefix();
 730             groupingName = groupingString;
 731         }
 732
 733         ModuleBuilder dependentModule = null;
 734         if (groupingPrefix.equals(module.getPrefix())) {
 735             dependentModule = module;
 736         } else {
 737             dependentModule = findDependentModule(modules, module, groupingPrefix, line);
 738         }
 739
 740         List<QName> path = usesBuilder.getPath().getPath();
 741         GroupingBuilder result = null;
 742         Set<GroupingBuilder> groupings = dependentModule.getModuleGroupings();
 743         result = findGrouping(groupings, groupingName);
 744
 745         if (result == null) {
 746             Builder currentNode = null;
 747             final List<String> currentPath = new ArrayList<String>();
 748             currentPath.add(dependentModule.getName());
 749
 750             for (int i = 0; i < path.size(); i++) {
 751                 QName qname = path.get(i);
 752                 currentPath.add(qname.getLocalName());
 753                 currentNode = dependentModule.getModuleNode(currentPath);
 754
 755                 if (currentNode instanceof RpcDefinitionBuilder) {
 756                     groupings = ((RpcDefinitionBuilder) currentNode).getGroupings();
 757                 } else if (currentNode instanceof DataNodeContainerBuilder) {
 758                     groupings = ((DataNodeContainerBuilder) currentNode).getGroupings();
 759                 } else {
 760                     groupings = Collections.emptySet();
 761                 }
 762
 763                 result = findGrouping(groupings, groupingName);
 764                 if (result != null) {
 765                     break;
 766                 }
 767             }
 768         }
 769
 770         if (result != null) {
 771             return result;
 772         }
 773         throw new YangParseException(module.getName(), line, "Referenced grouping '" + groupingName + "' not found.");
 774     }
 775
 776     private GroupingBuilder findGrouping(Set<GroupingBuilder> groupings, String name) {
 777         for (GroupingBuilder grouping : groupings) {
 778             if (grouping.getQName().getLocalName().equals(name)) {
 779                 return grouping;
 780             }
 781         }
 782         return null;
 783     }
 784
 785     /**
 786      * Find original builder of node to refine and return copy of this builder.
 787      * <p>
 788      * We must create and use a copy of builder to preserve original builder
 789      * state, because this object will be refined (modified) and later added to
 790      * {@link UsesNodeBuilder}.
 791      * </p>
 792      *
 793      * @param groupingPath
 794      *            path to grouping which contains node to refine
 795      * @param refine
 796      *            refine object containing informations about refine
 797      * @param modules
 798      *            all loaded modules
 799      * @param module
 800      *            current module
 801      * @return copy of node to be refined if it is present in grouping, null
 802      *         otherwise
 803      */
 804     private SchemaNodeBuilder getRefineNodeBuilderCopy(final GroupingBuilder targetGrouping, final RefineHolder refine,
 805             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 806         Builder result = null;
 807         final Builder lookedUpBuilder = findRefineTargetBuilder(targetGrouping, refine, modules, module);
 808         if (lookedUpBuilder instanceof LeafSchemaNodeBuilder) {
 809             result = ParserUtils.copyLeafBuilder((LeafSchemaNodeBuilder) lookedUpBuilder);
 810         } else if (lookedUpBuilder instanceof ContainerSchemaNodeBuilder) {
 811             result = ParserUtils.copyContainerBuilder((ContainerSchemaNodeBuilder) lookedUpBuilder);
 812         } else if (lookedUpBuilder instanceof ListSchemaNodeBuilder) {
 813             result = ParserUtils.copyListBuilder((ListSchemaNodeBuilder) lookedUpBuilder);
 814         } else if (lookedUpBuilder instanceof LeafListSchemaNodeBuilder) {
 815             result = ParserUtils.copyLeafListBuilder((LeafListSchemaNodeBuilder) lookedUpBuilder);
 816         } else if (lookedUpBuilder instanceof ChoiceBuilder) {
 817             result = ParserUtils.copyChoiceBuilder((ChoiceBuilder) lookedUpBuilder);
 818         } else if (lookedUpBuilder instanceof AnyXmlBuilder) {
 819             result = ParserUtils.copyAnyXmlBuilder((AnyXmlBuilder) lookedUpBuilder);
 820         } else if (lookedUpBuilder instanceof GroupingBuilder) {
 821             result = ParserUtils.copyGroupingBuilder((GroupingBuilder) lookedUpBuilder);
 822         } else if (lookedUpBuilder instanceof TypeDefinitionBuilder) {
 823             result = ParserUtils.copyTypedefBuilder((TypeDefinitionBuilderImpl) lookedUpBuilder);
 824         } else {
 825             throw new YangParseException(module.getName(), refine.getLine(), "Target '" + refine.getName()
 826                     + "' can not be refined");
 827         }
 828         return (SchemaNodeBuilder) result;
 829     }
 830
 831     /**
 832      * Find builder of refine node.
 833      *
 834      * @param groupingPath
 835      *            path to grouping which contains node to refine
 836      * @param refine
 837      *            object containing refine information
 838      * @param modules
 839      *            all loaded modules
 840      * @param module
 841      *            current module
 842      * @return Builder object of refine node if it is present in grouping, null
 843      *         otherwise
 844      */
 845     private Builder findRefineTargetBuilder(final GroupingBuilder builder, final RefineHolder refine,
 846             final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 847         final String refineNodeName = refine.getName();
 848         Builder result = builder.getChildNode(refineNodeName);
 849         if (result == null) {
 850             Set<GroupingBuilder> grps = builder.getGroupings();
 851             for (GroupingBuilder gr : grps) {
 852                 if (gr.getQName().getLocalName().equals(refineNodeName)) {
 853                     result = gr;
 854                     break;
 855                 }
 856             }
 857         }
 858         if (result == null) {
 859             Set<TypeDefinitionBuilder> typedefs = builder.getTypeDefinitions();
 860             for (TypeDefinitionBuilder typedef : typedefs) {
 861                 if (typedef.getQName().getLocalName().equals(refineNodeName)) {
 862                     result = typedef;
 863                     break;
 864                 }
 865             }
 866         }
 867         return result;
 868     }
 869
 870     private QName findFullQName(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module,
 871             final IdentityrefTypeBuilder idref) {
 872         QName result = null;
 873         String baseString = idref.getBaseString();
 874         if (baseString.contains(":")) {
 875             String[] splittedBase = baseString.split(":");
 876             if (splittedBase.length > 2) {
 877                 throw new YangParseException(module.getName(), idref.getLine(), "Failed to parse identityref base: "
 878                         + baseString);
 879             }
 880             String prefix = splittedBase[0];
 881             String name = splittedBase[1];
 882             ModuleBuilder dependentModule = findDependentModule(modules, module, prefix, idref.getLine());
 883             result = new QName(dependentModule.getNamespace(), dependentModule.getRevision(), prefix, name);
 884         } else {
 885             result = new QName(module.getNamespace(), module.getRevision(), module.getPrefix(), baseString);
 886         }
 887         return result;
 888     }
 889
 890     private void resolveUnknownNodes(final Map<String, TreeMap<Date, ModuleBuilder>> modules, final ModuleBuilder module) {
 891         for (UnknownSchemaNodeBuilder usnb : module.getUnknownNodes()) {
 892             QName nodeType = usnb.getNodeType();
 893             if (nodeType.getNamespace() == null || nodeType.getRevision() == null) {
 894                 try {
 895                     ModuleBuilder dependentModule = findDependentModule(modules, module, nodeType.getPrefix(),
 896                             usnb.getLine());
 897                     QName newNodeType = new QName(dependentModule.getNamespace(), dependentModule.getRevision(),
 898                             nodeType.getPrefix(), nodeType.getLocalName());
 899                     usnb.setNodeType(newNodeType);
 900                 } catch (YangParseException e) {
 901                     logger.debug(module.getName(), usnb.getLine(), "Failed to find unknown node type: " + nodeType);
 902                 }
 903             }
 904         }
 905     }
 906
 907     /**
 908      * Find dependent module based on given prefix
 909      *
 910      * @param modules
 911      *            all available modules
 912      * @param module
 913      *            current module
 914      * @param prefix
 915      *            target module prefix
 916      * @param line
 917      *            current line in yang model
 918      * @return
 919      */
 920     private ModuleBuilder findDependentModule(final Map<String, TreeMap<Date, ModuleBuilder>> modules,
 921             final ModuleBuilder module, final String prefix, final int line) {
 922         ModuleBuilder dependentModule = null;
 923         Date dependentModuleRevision = null;
 924
 925         if (prefix.equals(module.getPrefix())) {
 926             dependentModule = module;
 927         } else {
 928             final ModuleImport dependentModuleImport = ParserUtils.getModuleImport(module, prefix);
 929             if (dependentModuleImport == null) {
 930                 throw new YangParseException(module.getName(), line, "No import found with prefix '" + prefix + "'.");
 931             }
 932             final String dependentModuleName = dependentModuleImport.getModuleName();
 933             dependentModuleRevision = dependentModuleImport.getRevision();
 934
 935             final TreeMap<Date, ModuleBuilder> moduleBuildersByRevision = modules.get(dependentModuleName);
 936             if (moduleBuildersByRevision == null) {
 937                 throw new YangParseException(module.getName(), line, "Failed to find dependent module '"
 938                         + dependentModuleName + "'.");
 939             }
 940             if (dependentModuleRevision == null) {
 941                 dependentModule = moduleBuildersByRevision.lastEntry().getValue();
 942             } else {
 943                 dependentModule = moduleBuildersByRevision.get(dependentModuleRevision);
 944             }
 945         }
 946
 947         if (dependentModule == null) {
 948             throw new YangParseException(module.getName(), line, "Failed to find dependent module with prefix '"
 949                     + prefix + "' and revision '" + dependentModuleRevision + "'.");
 950         }
 951         return dependentModule;
 952     }
 953
 954 }