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