yang/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.Maps;
  15 import com.google.common.collect.Multimap;
  16 import java.util.ArrayList;
  17 import java.util.Collection;
  18 import java.util.Date;
  19 import java.util.Iterator;
  20 import java.util.Map;
  21 import java.util.Map.Entry;
  22 import java.util.Set;
  23 import org.opendaylight.yangtools.concepts.SemVer;
  24 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  25 import org.opendaylight.yangtools.yang.model.repo.api.SourceIdentifier;
  26 import org.opendaylight.yangtools.yang.parser.impl.util.YangModelDependencyInfo;
  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  */
  40 abstract class DependencyResolver {
  41     private static final Logger LOG = LoggerFactory.getLogger(DependencyResolver.class);
  42     private final Collection<SourceIdentifier> resolvedSources;
  43     private final Collection<SourceIdentifier> unresolvedSources;
  44     private final Multimap<SourceIdentifier, ModuleImport> unsatisfiedImports;
  45
  46     protected DependencyResolver(final Map<SourceIdentifier, YangModelDependencyInfo> depInfo) {
  47         final Collection<SourceIdentifier> resolved = new ArrayList<>(depInfo.size());
  48         final Collection<SourceIdentifier> pending = new ArrayList<>(depInfo.keySet());
  49         final Map<SourceIdentifier, BelongsToDependency> submodules = Maps.newHashMap();
  50
  51         boolean progress;
  52         do {
  53             progress = false;
  54
  55             final Iterator<SourceIdentifier> it = pending.iterator();
  56             while (it.hasNext()) {
  57                 final SourceIdentifier id = it.next();
  58                 final YangModelDependencyInfo dep = depInfo.get(id);
  59
  60                 boolean okay = true;
  61
  62                 final Set<ModuleImport> dependencies = dep.getDependencies();
  63
  64                 // in case of submodule, remember belongs to
  65                 if (dep instanceof YangModelDependencyInfo.SubmoduleDependencyInfo) {
  66                     final String parent = ((YangModelDependencyInfo.SubmoduleDependencyInfo) dep).getParentModule();
  67                     submodules.put(id, new BelongsToDependency(parent));
  68                 }
  69
  70                 for (final ModuleImport mi : dependencies) {
  71                     if (!isKnown(resolved, mi)) {
  72                         LOG.debug("Source {} is missing import {}", id, mi);
  73                         okay = false;
  74                         break;
  75                     }
  76                 }
  77
  78                 if (okay) {
  79                     LOG.debug("Resolved source {}", id);
  80                     resolved.add(id);
  81                     it.remove();
  82                     progress = true;
  83                 }
  84             }
  85         } while (progress);
  86
  87         /// Additional check only for belongs-to statement
  88         for (final Entry<SourceIdentifier, BelongsToDependency> submodule : submodules.entrySet()) {
  89             final BelongsToDependency belongs = submodule.getValue();
  90             final SourceIdentifier sourceIdentifier = submodule.getKey();
  91             if (!isKnown(resolved, belongs)) {
  92                 LOG.debug("Source {} is missing parent {}", sourceIdentifier, belongs);
  93                 pending.add(sourceIdentifier);
  94                 resolved.remove(sourceIdentifier);
  95             }
  96         }
  97
  98         final Multimap<SourceIdentifier, ModuleImport> imports = ArrayListMultimap.create();
  99         for (final SourceIdentifier id : pending) {
 100             final YangModelDependencyInfo dep = depInfo.get(id);
 101             for (final ModuleImport mi : dep.getDependencies()) {
 102                 if (!isKnown(pending, mi) && !isKnown(resolved, mi)) {
 103                     imports.put(id, mi);
 104                 }
 105             }
 106         }
 107
 108         this.resolvedSources = ImmutableList.copyOf(resolved);
 109         this.unresolvedSources = ImmutableList.copyOf(pending);
 110         this.unsatisfiedImports = ImmutableMultimap.copyOf(imports);
 111     }
 112
 113     abstract protected boolean isKnown(final Collection<SourceIdentifier> haystack, final ModuleImport mi);
 114
 115     /**
 116      * Collection of sources which have been resolved.
 117      *
 118      * @return
 119      */
 120     Collection<SourceIdentifier> getResolvedSources() {
 121         return resolvedSources;
 122     }
 123
 124     /**
 125      * Collection of sources which have not been resolved due to missing dependencies.
 126      *
 127      * @return
 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      * Note that this map contains only imports which are missing from the reactor,
 139      * not transitive failures.
 140      *
 141      * Examples:
 142      *
 143      * If A imports B, B imports C, and both A and B are in the reactor, only B->C
 144      * will be reported.
 145      *
 146      * If A imports B and C, B imports C, and both A and B are in the reactor,
 147      * A->C and B->C will be reported.
 148      *
 149      * @return
 150      */
 151     Multimap<SourceIdentifier, ModuleImport> getUnsatisfiedImports() {
 152         return unsatisfiedImports;
 153     }
 154
 155     private static class BelongsToDependency implements ModuleImport {
 156         private final String parent;
 157
 158         public BelongsToDependency(final String parent) {
 159             this.parent = parent;
 160         }
 161
 162         @Override
 163         public String getModuleName() {
 164             return parent;
 165         }
 166
 167         @Override
 168         public Date getRevision() {
 169             return null;
 170         }
 171
 172         @Override
 173         public String getPrefix() {
 174             return null;
 175         }
 176
 177         @Override
 178         public SemVer getSemanticVersion() {
 179             return null;
 180         }
 181
 182         @Override
 183         public String toString() {
 184             return MoreObjects.toStringHelper(this)
 185                     .add("parent", parent)
 186                     .toString();
 187         }
 188     }
 189 }