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