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

   1 /*
   2  * Copyright (c) 2014 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.yangtools.yang.parser.repo;
   9
  10 import com.google.common.base.MoreObjects;
  11 import com.google.common.collect.ArrayListMultimap;
  12 import com.google.common.collect.ImmutableList;
  13 import com.google.common.collect.ImmutableMultimap;
  14 import com.google.common.collect.Multimap;
  15 import java.util.ArrayList;
  16 import java.util.Collection;
  17 import java.util.HashMap;
  18 import java.util.Iterator;
  19 import java.util.Map;
  20 import java.util.Map.Entry;
  21 import java.util.Optional;
  22 import java.util.Set;
  23 import org.opendaylight.yangtools.yang.common.Revision;
  24 import org.opendaylight.yangtools.yang.common.UnresolvedQName.Unqualified;
  25 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  26 import org.opendaylight.yangtools.yang.model.api.stmt.ImportEffectiveStatement;
  27 import org.opendaylight.yangtools.yang.model.repo.api.SourceIdentifier;
  28 import org.opendaylight.yangtools.yang.parser.api.YangParserConfiguration;
  29 import org.opendaylight.yangtools.yang.parser.rfc7950.repo.YangModelDependencyInfo;
  30 import org.slf4j.Logger;
  31 import org.slf4j.LoggerFactory;
  32
  33 /**
  34  * Inter-module dependency resolved. Given a set of schema source identifiers and their
  35  * corresponding dependency information, the {@link #create(Map)} method creates a
  36  * a view of how consistent the dependencies are. In particular, this detects whether
  37  * any imports are unsatisfied.
  38  */
  39 // FIXME: improve this class to track and expose how wildcard imports were resolved.
  40 //        That information will allow us to track "damage" to dependency resolution
  41 //        as new models are added to a schema context.
  42 abstract class DependencyResolver {
  43     private static final Logger LOG = LoggerFactory.getLogger(DependencyResolver.class);
  44     private final ImmutableList<SourceIdentifier> resolvedSources;
  45     private final ImmutableList<SourceIdentifier> unresolvedSources;
  46     private final ImmutableMultimap<SourceIdentifier, ModuleImport> unsatisfiedImports;
  47
  48     protected DependencyResolver(final Map<SourceIdentifier, YangModelDependencyInfo> depInfo) {
  49         final Collection<SourceIdentifier> resolved = new ArrayList<>(depInfo.size());
  50         final Collection<SourceIdentifier> pending = new ArrayList<>(depInfo.keySet());
  51         final Map<SourceIdentifier, BelongsToDependency> submodules = new HashMap<>();
  52
  53         boolean progress;
  54         do {
  55             progress = false;
  56
  57             final Iterator<SourceIdentifier> it = pending.iterator();
  58             while (it.hasNext()) {
  59                 final SourceIdentifier id = it.next();
  60                 final YangModelDependencyInfo dep = depInfo.get(id);
  61
  62                 boolean okay = true;
  63
  64                 final Set<ModuleImport> dependencies = dep.getDependencies();
  65
  66                 // in case of submodule, remember belongs to
  67                 if (dep instanceof YangModelDependencyInfo.SubmoduleDependencyInfo) {
  68                     final var parent = ((YangModelDependencyInfo.SubmoduleDependencyInfo) dep).getParentModule();
  69                     submodules.put(id, new BelongsToDependency(parent));
  70                 }
  71
  72                 for (final ModuleImport mi : dependencies) {
  73                     if (!isKnown(resolved, mi)) {
  74                         LOG.debug("Source {} is missing import {}", id, mi);
  75                         okay = false;
  76                         break;
  77                     }
  78                 }
  79
  80                 if (okay) {
  81                     LOG.debug("Resolved source {}", id);
  82                     resolved.add(id);
  83                     it.remove();
  84                     progress = true;
  85                 }
  86             }
  87         } while (progress);
  88
  89         /// Additional check only for belongs-to statement
  90         for (final Entry<SourceIdentifier, BelongsToDependency> submodule : submodules.entrySet()) {
  91             final BelongsToDependency belongs = submodule.getValue();
  92             final SourceIdentifier sourceIdentifier = submodule.getKey();
  93             if (!isKnown(resolved, belongs)) {
  94                 LOG.debug("Source {} is missing parent {}", sourceIdentifier, belongs);
  95                 pending.add(sourceIdentifier);
  96                 resolved.remove(sourceIdentifier);
  97             }
  98         }
  99
 100         final Multimap<SourceIdentifier, ModuleImport> imports = ArrayListMultimap.create();
 101         for (final SourceIdentifier id : pending) {
 102             final YangModelDependencyInfo dep = depInfo.get(id);
 103             for (final ModuleImport mi : dep.getDependencies()) {
 104                 if (!isKnown(pending, mi) && !isKnown(resolved, mi)) {
 105                     imports.put(id, mi);
 106                 }
 107             }
 108         }
 109
 110         this.resolvedSources = ImmutableList.copyOf(resolved);
 111         this.unresolvedSources = ImmutableList.copyOf(pending);
 112         this.unsatisfiedImports = ImmutableMultimap.copyOf(imports);
 113     }
 114
 115     protected abstract boolean isKnown(Collection<SourceIdentifier> haystack, ModuleImport mi);
 116
 117     abstract YangParserConfiguration parserConfig();
 118
 119     /**
 120      * Collection of sources which have been resolved.
 121      */
 122     Collection<SourceIdentifier> getResolvedSources() {
 123         return resolvedSources;
 124     }
 125
 126     /**
 127      * Collection of sources which have not been resolved due to missing dependencies.
 128      */
 129     Collection<SourceIdentifier> getUnresolvedSources() {
 130         return unresolvedSources;
 131     }
 132
 133     /**
 134      * Detailed information about which imports were missing. The key in the map
 135      * is the source identifier of module which was issuing an import, the values
 136      * are imports which were unsatisfied.
 137      *
 138      * <p>
 139      * Note that this map contains only imports which are missing from the reactor,
 140      * not transitive failures.
 141      *
 142      * <p>
 143      * Examples:
 144      * <ul><li>
 145      * If A imports B, B imports C, and both A and B are in the reactor, only B->C
 146      * will be reported.
 147      * </li><li>
 148      * If A imports B and C, B imports C, and both A and B are in the reactor,
 149      * A->C and B->C will be reported.
 150      * </li></ul>
 151      */
 152     Multimap<SourceIdentifier, ModuleImport> getUnsatisfiedImports() {
 153         return unsatisfiedImports;
 154     }
 155
 156     private static class BelongsToDependency implements ModuleImport {
 157         private final Unqualified parent;
 158
 159         BelongsToDependency(final Unqualified parent) {
 160             this.parent = parent;
 161         }
 162
 163         @Override
 164         public Unqualified getModuleName() {
 165             return parent;
 166         }
 167
 168         @Override
 169         public Optional<Revision> getRevision() {
 170             return Optional.empty();
 171         }
 172
 173         @Override
 174         public Optional<String> getDescription() {
 175             return Optional.empty();
 176         }
 177
 178         @Override
 179         public Optional<String> getReference() {
 180             return Optional.empty();
 181         }
 182
 183         @Override
 184         public String getPrefix() {
 185             throw new UnsupportedOperationException();
 186         }
 187
 188         @Override
 189         public String toString() {
 190             return MoreObjects.toStringHelper(this).add("parent", parent).toString();
 191         }
 192
 193         @Override
 194         public ImportEffectiveStatement asEffectiveStatement() {
 195             throw new UnsupportedOperationException();
 196         }
 197     }
 198 }