yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/impl/YangParserImpl.java

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