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