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