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