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