yang/yang-model-export/src/main/java/org/opendaylight/yangtools/yang/model/export/StatementPrefixResolver.java

   1 /*
   2  * Copyright (c) 2019 PANTHEON.tech, s.r.o. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.model.export;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static com.google.common.base.Verify.verify;
  12 import static java.util.Objects.requireNonNull;
  13
  14 import com.google.common.collect.ArrayListMultimap;
  15 import com.google.common.collect.HashMultimap;
  16 import com.google.common.collect.ImmutableMap;
  17 import com.google.common.collect.ImmutableMap.Builder;
  18 import com.google.common.collect.Maps;
  19 import com.google.common.collect.Multimap;
  20 import java.util.AbstractMap.SimpleImmutableEntry;
  21 import java.util.Collection;
  22 import java.util.HashMap;
  23 import java.util.Iterator;
  24 import java.util.Map;
  25 import java.util.Map.Entry;
  26 import java.util.Optional;
  27 import org.eclipse.jdt.annotation.Nullable;
  28 import org.opendaylight.yangtools.yang.common.QNameModule;
  29 import org.opendaylight.yangtools.yang.common.Revision;
  30 import org.opendaylight.yangtools.yang.common.YangConstants;
  31 import org.opendaylight.yangtools.yang.model.api.meta.DeclaredStatement;
  32 import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement;
  33 import org.opendaylight.yangtools.yang.model.api.stmt.ModuleEffectiveStatement;
  34 import org.opendaylight.yangtools.yang.model.api.stmt.ModuleEffectiveStatement.NameToEffectiveSubmoduleNamespace;
  35 import org.opendaylight.yangtools.yang.model.api.stmt.ModuleEffectiveStatement.QNameModuleToPrefixNamespace;
  36 import org.opendaylight.yangtools.yang.model.api.stmt.SubmoduleEffectiveStatement;
  37
  38 /**
  39  * Utility resolver to disambiguate imports.
  40  */
  41 final class StatementPrefixResolver {
  42     private static final class Conflict {
  43         private final Collection<Entry<DeclaredStatement<?>, String>> statements;
  44
  45         Conflict(final Collection<Entry<DeclaredStatement<?>, String>> entries) {
  46             statements = requireNonNull(entries);
  47         }
  48
  49         @Nullable String findPrefix(final DeclaredStatement<?> stmt) {
  50             return statements.stream().filter(entry -> contains(entry.getKey(), stmt)).findFirst().map(Entry::getValue)
  51                     .orElse(null);
  52         }
  53
  54         private static boolean contains(final DeclaredStatement<?> haystack, final DeclaredStatement<?> needle) {
  55             if (haystack == needle) {
  56                 return true;
  57             }
  58             for (DeclaredStatement<?> child : haystack.declaredSubstatements()) {
  59                 if (contains(child, needle)) {
  60                     return true;
  61                 }
  62             }
  63             return false;
  64         }
  65     }
  66
  67     private final Map<QNameModule, ?> lookup;
  68
  69     private StatementPrefixResolver(final Map<QNameModule, String> map) {
  70         lookup = ImmutableMap.copyOf(map);
  71     }
  72
  73     private StatementPrefixResolver(final ImmutableMap<QNameModule, ?> map) {
  74         lookup = requireNonNull(map);
  75     }
  76
  77     static StatementPrefixResolver forModule(final ModuleEffectiveStatement module) {
  78         final Map<QNameModule, String> imports = module.getAll(QNameModuleToPrefixNamespace.class);
  79         final Collection<SubmoduleEffectiveStatement> submodules = module.getAll(
  80             NameToEffectiveSubmoduleNamespace.class).values();
  81         if (submodules.isEmpty()) {
  82             // Simple: it's just the module
  83             return new StatementPrefixResolver(imports);
  84         }
  85
  86         // Stage one: check what everyone thinks about imports
  87         final Map<String, Multimap<QNameModule, EffectiveStatement<?, ?>>> prefixToNamespaces = new HashMap<>();
  88         indexPrefixes(prefixToNamespaces, imports, module);
  89         for (SubmoduleEffectiveStatement submodule : submodules) {
  90             indexPrefixes(prefixToNamespaces, submodule.getAll(QNameModuleToPrefixNamespace.class), submodule);
  91         }
  92
  93         // Stage two: see what QNameModule -> prefix mappings there are. We will need to understand this in step three
  94         final Multimap<QNameModule, String> namespaceToPrefixes = HashMultimap.create();
  95         for (Entry<String, Multimap<QNameModule, EffectiveStatement<?,?>>> entry : prefixToNamespaces.entrySet()) {
  96             for (QNameModule namespace : entry.getValue().keySet()) {
  97                 namespaceToPrefixes.put(namespace, entry.getKey());
  98             }
  99         }
 100
 101         // Stage three: resolve first order of conflicts, potentially completely resolving mappings...
 102         final Builder<QNameModule, Object> builder = ImmutableMap.builderWithExpectedSize(prefixToNamespaces.size());
 103
 104         // ... first resolve unambiguous mappings ...
 105         final Iterator<Entry<String, Multimap<QNameModule, EffectiveStatement<?, ?>>>> it =
 106                 prefixToNamespaces.entrySet().iterator();
 107         while (it.hasNext()) {
 108             final Entry<String, Multimap<QNameModule, EffectiveStatement<?, ?>>> entry = it.next();
 109             final Multimap<QNameModule, EffectiveStatement<?, ?>> modules = entry.getValue();
 110             if (modules.size() == 1) {
 111                 // Careful now: the namespace needs to be unambiguous
 112                 final QNameModule namespace = modules.keys().iterator().next();
 113                 if (namespaceToPrefixes.get(namespace).size() == 1) {
 114                     builder.put(namespace, entry.getKey());
 115                     it.remove();
 116                 }
 117             }
 118         }
 119
 120         // .. check for any remaining conflicts ...
 121         if (!prefixToNamespaces.isEmpty()) {
 122             final Multimap<QNameModule, Entry<DeclaredStatement<?>, String>> conflicts = ArrayListMultimap.create();
 123             for (Entry<String, Multimap<QNameModule, EffectiveStatement<?, ?>>> entry : prefixToNamespaces.entrySet()) {
 124                 for (Entry<QNameModule, EffectiveStatement<?, ?>> namespace : entry.getValue().entries()) {
 125                     conflicts.put(namespace.getKey(), new SimpleImmutableEntry<>(namespace.getValue().getDeclared(),
 126                             entry.getKey()));
 127                 }
 128             }
 129
 130             builder.putAll(Maps.transformValues(conflicts.asMap(), Conflict::new));
 131         }
 132
 133         return new StatementPrefixResolver(builder.build());
 134     }
 135
 136     static StatementPrefixResolver forSubmodule(final SubmoduleEffectiveStatement submodule) {
 137         return new StatementPrefixResolver(submodule.getAll(QNameModuleToPrefixNamespace.class));
 138     }
 139
 140     Optional<String> findPrefix(final DeclaredStatement<?> stmt) {
 141         final QNameModule module = stmt.statementDefinition().getStatementName().getModule();
 142         if (YangConstants.RFC6020_YIN_MODULE.equals(module)) {
 143             return Optional.empty();
 144         }
 145
 146         final Object obj = lookup.get(module);
 147         if (obj != null) {
 148             return decodeEntry(obj, stmt);
 149         }
 150         if (module.getRevision().isPresent()) {
 151             throw new IllegalArgumentException("Failed to find prefix for statement " + stmt);
 152         }
 153
 154         // FIXME: this is an artifact of commonly-bound statements in parser, which means a statement's name
 155         //        does not have a Revision. We'll need to find a solution to this which is acceptable. There
 156         //        are multiple ways of fixing this:
 157         //        - perhaps EffectiveModuleStatement should be giving us a statement-to-EffectiveModule map?
 158         //        - or DeclaredStatement should provide the prefix?
 159         //        The second one seems cleaner, as that means we would not have perform any lookup at all...
 160         Entry<QNameModule, ?> match = null;
 161         for (Entry<QNameModule, ?> entry : lookup.entrySet()) {
 162             final QNameModule ns = entry.getKey();
 163             if (module.equals(ns.withoutRevision()) && (match == null
 164                     || Revision.compare(match.getKey().getRevision(), ns.getRevision()) < 0)) {
 165                 match = entry;
 166             }
 167         }
 168
 169         return match == null ? null : decodeEntry(match.getValue(), stmt);
 170     }
 171
 172     private static Optional<String> decodeEntry(final Object entry, final DeclaredStatement<?> stmt) {
 173         if (entry instanceof String) {
 174             return Optional.of((String)entry);
 175         }
 176         verify(entry instanceof Conflict, "Unexpected entry %s", entry);
 177         final String prefix = ((Conflict) entry).findPrefix(stmt);
 178         checkArgument(prefix != null, "Failed to find prefix for statement %s", stmt);
 179         verify(!prefix.isEmpty(), "Empty prefix for statement %s", stmt);
 180         return Optional.of(prefix);
 181     }
 182
 183     private static void indexPrefixes(final Map<String, Multimap<QNameModule, EffectiveStatement<?, ?>>> map,
 184             final Map<QNameModule, String> imports, final EffectiveStatement<?, ?> stmt) {
 185         for (Entry<QNameModule, String> entry : imports.entrySet()) {
 186             map.computeIfAbsent(entry.getValue(), key -> ArrayListMultimap.create()).put(entry.getKey(), stmt);
 187         }
 188     }
 189 }