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.Optional;
  11 import com.google.common.base.Preconditions;
  12 import com.google.common.collect.ArrayListMultimap;
  13 import com.google.common.collect.ImmutableMultimap;
  14 import com.google.common.collect.Multimap;
  15
  16 import java.util.ArrayList;
  17 import java.util.Collection;
  18 import java.util.Collections;
  19 import java.util.Iterator;
  20 import java.util.Map;
  21
  22 import org.opendaylight.yangtools.yang.common.QName;
  23 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  24 import org.opendaylight.yangtools.yang.model.repo.api.SourceIdentifier;
  25 import org.opendaylight.yangtools.yang.parser.impl.util.YangModelDependencyInfo;
  26 import org.slf4j.Logger;
  27 import org.slf4j.LoggerFactory;
  28
  29 /**
  30  * Inter-module dependency resolved. Given a set of schema source identifiers and their
  31  * corresponding dependency information, the {@link #create(Map)} method creates a
  32  * a view of how consistent the dependencies are. In particular, this detects whether
  33  * any imports are unsatisfied.
  34  *
  35  * FIXME: improve this class to track and expose how wildcard imports were resolved.
  36  *        That information will allow us to track "damage" to dependency resolution
  37  *        as new models are added to a schema context.
  38  */
  39 final class DependencyResolver {
  40     private static final Logger LOG = LoggerFactory.getLogger(DependencyResolver.class);
  41     private final Collection<SourceIdentifier> resolvedSources;
  42     private final Collection<SourceIdentifier> unresolvedSources;
  43     private final Multimap<SourceIdentifier, ModuleImport> unsatisfiedImports;
  44
  45     public DependencyResolver(final Collection<SourceIdentifier> resolvedSources,
  46             final Collection<SourceIdentifier> unresolvedSources, final Multimap<SourceIdentifier, ModuleImport> unsatisfiedImports) {
  47         this.resolvedSources = Preconditions.checkNotNull(resolvedSources);
  48         this.unresolvedSources = Preconditions.checkNotNull(unresolvedSources);
  49         this.unsatisfiedImports = Preconditions.checkNotNull(unsatisfiedImports);
  50     }
  51
  52     private static SourceIdentifier findWildcard(final Iterable<SourceIdentifier> haystack, final String needle) {
  53         for (SourceIdentifier r : haystack) {
  54             if (r.getName().equals(needle)) {
  55                 return r;
  56             }
  57         }
  58
  59         return null;
  60     }
  61
  62     private static boolean isKnown(final Collection<SourceIdentifier> haystack, final ModuleImport mi) {
  63         final String rev = mi.getRevision() != null ? QName.formattedRevision(mi.getRevision()) : null;
  64         final SourceIdentifier msi = SourceIdentifier.create(mi.getModuleName(), Optional.fromNullable(rev));
  65
  66         // Quick lookup
  67         if (haystack.contains(msi)) {
  68             return true;
  69         }
  70
  71         // Slow revision-less walk
  72         return rev == null && findWildcard(haystack, mi.getModuleName()) != null;
  73     }
  74
  75
  76
  77     public static final DependencyResolver create(final Map<SourceIdentifier, YangModelDependencyInfo> depInfo) {
  78         final Collection<SourceIdentifier> resolved = new ArrayList<>(depInfo.size());
  79         final Collection<SourceIdentifier> pending = new ArrayList<>(depInfo.keySet());
  80
  81         boolean progress;
  82         do {
  83             progress = false;
  84
  85             final Iterator<SourceIdentifier> it = pending.iterator();
  86             while (it.hasNext()) {
  87                 final SourceIdentifier id = it.next();
  88                 final YangModelDependencyInfo dep = depInfo.get(id);
  89
  90                 boolean okay = true;
  91                 for (ModuleImport mi : dep.getDependencies()) {
  92                     if (!isKnown(resolved, mi)) {
  93                         LOG.debug("Source {} is missing import {}", id, mi);
  94                         okay = false;
  95                         break;
  96                     }
  97                 }
  98
  99                 if (okay) {
 100                     LOG.debug("Resolved source {}", id);
 101                     resolved.add(id);
 102                     it.remove();
 103                     progress = true;
 104                 }
 105             }
 106         } while (progress);
 107
 108         if (!pending.isEmpty()) {
 109             final Multimap<SourceIdentifier, ModuleImport> imports = ArrayListMultimap.create();
 110             for (SourceIdentifier id : pending) {
 111                 final YangModelDependencyInfo dep = depInfo.get(id);
 112                 for (ModuleImport mi : dep.getDependencies()) {
 113                     if (!isKnown(pending, mi) && !isKnown(resolved, mi)) {
 114                         imports.put(id, mi);
 115                     }
 116                 }
 117             }
 118
 119             return new DependencyResolver(resolved, pending, imports);
 120         } else {
 121             return new DependencyResolver(resolved, Collections.<SourceIdentifier>emptyList(), ImmutableMultimap.<SourceIdentifier, ModuleImport>of());
 122         }
 123     }
 124
 125     /**
 126      * Collection of sources which have been resolved.
 127      *
 128      * @return
 129      */
 130     Collection<SourceIdentifier> getResolvedSources() {
 131         return resolvedSources;
 132     }
 133
 134     /**
 135      * Collection of sources which have not been resolved due to missing dependencies.
 136      *
 137      * @return
 138      */
 139     Collection<SourceIdentifier> getUnresolvedSources() {
 140         return unresolvedSources;
 141     }
 142
 143     /**
 144      * Detailed information about which imports were missing. The key in the map
 145      * is the source identifier of module which was issuing an import, the values
 146      * are imports which were unsatisfied.
 147      *
 148      * Note that this map contains only imports which are missing from the reactor,
 149      * not transitive failures.
 150      *
 151      * Examples:
 152      *
 153      * If A imports B, B imports C, and both A and B are in the reactor, only B->C
 154      * will be reported.
 155      *
 156      * If A imports B and C, B imports C, and both A and B are in the reactor,
 157      * A->C and B->C will be reported.
 158      *
 159      * @return
 160      */
 161     Multimap<SourceIdentifier, ModuleImport> getUnsatisfiedImports() {
 162         return unsatisfiedImports;
 163     }
 164 }