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.collect.ImmutableList;
  11 import com.google.common.collect.ImmutableMultimap;
  12 import com.google.common.collect.Sets;
  13 import java.util.Collection;
  14 import java.util.HashMap;
  15 import java.util.Map;
  16 import org.opendaylight.yangtools.yang.model.api.source.SourceDependency;
  17 import org.opendaylight.yangtools.yang.model.api.source.SourceIdentifier;
  18 import org.opendaylight.yangtools.yang.model.spi.source.SourceInfo;
  19 import org.opendaylight.yangtools.yang.model.spi.source.SourceInfo.Submodule;
  20 import org.opendaylight.yangtools.yang.parser.api.YangParserConfiguration;
  21 import org.slf4j.Logger;
  22 import org.slf4j.LoggerFactory;
  23
  24 /**
  25  * Inter-module dependency resolved. Given a set of schema source identifiers and their
  26  * corresponding dependency information, the {@link #create(Map)} method creates a
  27  * a view of how consistent the dependencies are. In particular, this detects whether
  28  * any imports are unsatisfied.
  29  */
  30 // FIXME: improve this class to track and expose how wildcard imports were resolved.
  31 //        That information will allow us to track "damage" to dependency resolution
  32 //        as new models are added to a schema context.
  33 abstract class DependencyResolver {
  34     private static final Logger LOG = LoggerFactory.getLogger(DependencyResolver.class);
  35
  36     private final ImmutableList<SourceIdentifier> resolvedSources;
  37     private final ImmutableList<SourceIdentifier> unresolvedSources;
  38     private final ImmutableMultimap<SourceIdentifier, SourceDependency> unsatisfiedImports;
  39
  40     protected DependencyResolver(final Map<SourceIdentifier, SourceInfo> depInfo) {
  41         final var resolved = Sets.<SourceIdentifier>newHashSetWithExpectedSize(depInfo.size());
  42         final var pending = new HashMap<>(depInfo);
  43
  44         boolean progress;
  45         do {
  46             progress = false;
  47
  48             final var it = pending.values().iterator();
  49             while (it.hasNext()) {
  50                 final var dep = it.next();
  51                 if (tryResolve(resolved, dep)) {
  52                     final var sourceId = dep.sourceId();
  53                     LOG.debug("Resolved source {}", sourceId);
  54                     resolved.add(sourceId);
  55                     it.remove();
  56                     progress = true;
  57                 }
  58             }
  59         } while (progress);
  60
  61         resolvedSources = ImmutableList.copyOf(resolved);
  62         unresolvedSources = ImmutableList.copyOf(pending.keySet());
  63
  64         final var unstatisfied = ImmutableMultimap.<SourceIdentifier, SourceDependency>builder();
  65         for (var info : pending.values()) {
  66             for (var dep : info.imports()) {
  67                 if (!isKnown(depInfo.keySet(), dep)) {
  68                     unstatisfied.put(info.sourceId(), dep);
  69                 }
  70             }
  71             for (var dep : info.includes()) {
  72                 if (!isKnown(depInfo.keySet(), dep)) {
  73                     unstatisfied.put(info.sourceId(), dep);
  74                 }
  75             }
  76             if (info instanceof Submodule submodule) {
  77                 final var dep = submodule.belongsTo();
  78                 if (!isKnown(depInfo.keySet(), dep)) {
  79                     unstatisfied.put(info.sourceId(), dep);
  80                 }
  81             }
  82         }
  83         unsatisfiedImports = unstatisfied.build();
  84     }
  85
  86     /**
  87      * Collection of sources which have been resolved.
  88      */
  89     final ImmutableList<SourceIdentifier> resolvedSources() {
  90         return resolvedSources;
  91     }
  92
  93     /**
  94      * Collection of sources which have not been resolved due to missing dependencies.
  95      */
  96     final ImmutableList<SourceIdentifier> unresolvedSources() {
  97         return unresolvedSources;
  98     }
  99
 100     /**
 101      * Detailed information about which imports were missing. The key in the map is the source identifier of module
 102      * which was issuing an import, the values are imports which were unsatisfied.
 103      *
 104      * <p>
 105      * Note that this map contains only imports which are missing from the reactor, not transitive failures. Examples:
 106      * <ul>
 107      *   <li>if A imports B, B imports C, and both A and B are in the reactor, only B->C will be reported</li>
 108      *   <li>if A imports B and C, B imports C, and both A and B are in the reactor, A->C and B->C will be reported</li>
 109      * </ul>
 110      */
 111     final ImmutableMultimap<SourceIdentifier, SourceDependency> unsatisfiedImports() {
 112         return unsatisfiedImports;
 113     }
 114
 115     private boolean tryResolve(final Collection<SourceIdentifier> resolved, final SourceInfo info) {
 116         for (var dep : info.imports()) {
 117             if (!isKnown(resolved, dep)) {
 118                 LOG.debug("Source {} is missing import {}", info.sourceId(), dep);
 119                 return false;
 120             }
 121         }
 122         for (var dep : info.includes()) {
 123             if (!isKnown(resolved, dep)) {
 124                 LOG.debug("Source {} is missing include {}", info.sourceId(), dep);
 125                 return false;
 126             }
 127         }
 128         if (info instanceof Submodule submodule) {
 129             final var dep = submodule.belongsTo();
 130             if (!isKnown(resolved, dep)) {
 131                 LOG.debug("Source {} is missing belongs-to {}", info.sourceId(), dep);
 132                 return false;
 133             }
 134         }
 135         return true;
 136     }
 137
 138     abstract boolean isKnown(Collection<SourceIdentifier> haystack, SourceDependency dependency);
 139
 140     abstract YangParserConfiguration parserConfig();
 141 }