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