Source code: javax/ide/extension/spi/DependencyTree.java

   package javax.ide.extension.spi;
   
   import java.io.IOException;
   import java.io.InputStream;
   
   import java.util.ArrayList;
   import java.util.Collection;
   import java.util.Collections;
   import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  import java.util.logging.Level;
  
  import java.util.logging.Logger;
  import javax.ide.extension.ElementEndContext;
  import javax.ide.extension.ElementStartContext;
  import javax.ide.extension.ElementVisitor;
  import javax.ide.extension.Extension;
  import javax.ide.extension.ExtensionDependency;
  import javax.ide.extension.ExtensionHook;
  
  import javax.ide.util.Version;
  import javax.xml.parsers.ParserConfigurationException;
  
  import org.xml.sax.InputSource;
  import org.xml.sax.SAXException;
  
  /**
   * DependencyTree is responsible for determining dependencies between extensions
   * and providing a load order that satisfies those dependencies.
   */
  public final class DependencyTree 
  {
    private static final String SOURCE = "source";
  
    private final Map _sourcesByExtension;
    private final Map _extensionsById = new HashMap();
    
    private List _topologicalExtensionList;
    private final Map _unsatisfiedDependencies = new HashMap();
    private final List _cycles = new ArrayList();
  
    private DependencyTree( List failedSources, Map sourcesByExtension )
    {
      _sourcesByExtension = sourcesByExtension;
      removeDuplicates();
      
      for ( Iterator i = _sourcesByExtension.keySet().iterator(); i.hasNext(); )
      {
        Extension extension = (Extension) i.next();
        _extensionsById.put( extension.getID(), extension );
      }
      
      // Now create a topological sort of the extensions. We must try the
      // sort from all vertices because we may have multiple disconnected
      // graph fragments. However, this is not as inefficient as it seems, since
      // we remember which vertices we've already visited.
      
      TopoSortState state = new TopoSortState();
      for ( Iterator i = _sourcesByExtension.keySet().iterator(); i.hasNext(); )
      {
        Extension thisExt = (Extension) i.next();
        if ( state.isUnvisited( thisExt ) )
        {
          topologicalSort( state, thisExt );
        }
      }
      
      _topologicalExtensionList = state.getTopoList();
  
    }
  
    /**
     * Build a dependency tree for the specified collection of extension 
     * sources.
     * 
     * @param extensionSources a collection of 
     *    javax.ide.extension.spi.ExtensionSource.
     * @return an instance of DependencyTree.
     */
    public static DependencyTree buildTree( Collection extensionSources, 
      EnabledExtensionLookup lookup, Logger logger, 
      DefaultElementContext initialContext )
    {
      SAXManifestParser minimalParser = new SAXManifestParser( initialContext );
      ((DefaultElementContext)minimalParser.getContext()).setMessageReporter( logger );
      MinimalExtensionVisitor visitor = new MinimalExtensionVisitor();
      
      minimalParser.getContext().registerChildVisitor(
        ExtensionVisitor.ELEMENT, visitor
      );
      
      List failedSources = new ArrayList();
      
      for ( Iterator i = extensionSources.iterator(); i.hasNext(); )
      {
       ExtensionSource source = (ExtensionSource) i.next();
       minimalParser.getContext().getScopeData().put( SOURCE, source );
       InputStream inputStream = null;
       try
       {
         // TODO handle encoding... Always a pain in the butt with xml. We need
         // to partially read the xml stream to figure out which encoding to use.
         
         inputStream = source.getInputStream();
       
         InputSource inputSource = new InputSource( inputStream );
         inputSource.setSystemId( source.getManifestURI().toString() );
         minimalParser.parse( inputSource );
       }
       catch ( ParserConfigurationException pce )
       {
         throw new IllegalStateException( "JAXP is misconfigured" ); // , pce );
       }
       catch ( SAXException saxe )
       {
         minimalParser.getContext().getLogger().log(
           Level.SEVERE,
           "Failed to process extension source "+ source.getName()+": "+saxe.getLocalizedMessage(),
           new LocatorImpl( source.getManifestURI().toString() )
         );
         failedSources.add( source );
       }
       catch ( IOException ioe )
       {
         minimalParser.getContext().getLogger().log(
           Level.SEVERE,
           "Failed to process extension source "+ source.getName()+": "+ioe.getLocalizedMessage(),
           new LocatorImpl( source.getManifestURI().toString() )
         );
         failedSources.add( source );
       }
       finally
       {
         try
         {
           if ( inputStream != null )
             inputStream.close();
         }
         catch ( IOException ioe )
         {
           minimalParser.getContext().getLogger().log( 
             Level.SEVERE, 
             "Exception closing stream",
             ioe
           );
         }
       }
     }
     
     Map sbe = visitor.getSourcesByExtension();
     for ( Iterator i = sbe.keySet().iterator(); i.hasNext(); )
     {
       Extension e = (Extension) i.next();
       if ( !lookup.isExtensionEnabled( e ) )
       {
         i.remove();
       }
     }
     
     return new DependencyTree( failedSources, sbe );
   }
   
   /**
    * Resolve duplicate extension ids. If two or more extensions are present 
    * with the same id but different versions, we discard the older versions.
    * If two or more extensions have the same version, we "arbitrarily" pick
    * only one.
    */
   private void removeDuplicates()
   {
     Map latestExtensionById = new HashMap();
     List extensionsToRemove = new ArrayList();
     
     for ( Iterator i = _sourcesByExtension.keySet().iterator(); i.hasNext(); )
     {
       Extension extension = (Extension) i.next();
       Extension latest = 
         (Extension) latestExtensionById.get( extension.getID() );
       if ( latest == null ) 
       {
         latestExtensionById.put( extension.getID(), extension );
       }
       // Do we have a later version?
       else if ( extension.getVersion().compareTo( latest.getVersion() ) > 0 )
       {
         // Remember the older extension. We will need to remove it from the map
         // later.
         extensionsToRemove.add( latest );
         latestExtensionById.put( extension.getID(), extension );
       }
       else
       {
         // Else, the extension version is <= the latest one, so we skip it.
         extensionsToRemove.add( extension );
       }
     }
     
     // Now remove all extensions in the list of duplicates we've built.
     for ( Iterator i = extensionsToRemove.iterator(); i.hasNext(); )
     {
       Extension extension = (Extension) i.next();
       _sourcesByExtension.remove( extension );
     }
   }
   
   /**
    * The state of a topological sort. Primarily avoids passing lots of 
    * parameters around...
    */
   private class TopoSortState
   {
     private Map _stateByExtension = new HashMap();
     private Set _unsatisfied = new HashSet();
     private List _currentlyVisiting = new ArrayList();
     private List _topoList = new ArrayList();
     
     public List getTopoList()
     {
       return _topoList;
     }
     
     public boolean isVisiting( Extension extension )
     {
       return _stateByExtension.get( extension ) == STATE_VISITING;
     }
     
     public boolean isVisited( Extension extension )
     {
       return _stateByExtension.get( extension ) == STATE_VISITED;
     }
     
     public boolean isUnvisited( Extension extension )
     {
       Object o = _stateByExtension.get( extension );
       return o == null || o == STATE_NOT_VISITED;
     }
     
     
     public void addUnsatisfied( Extension extension )
     {
       _unsatisfied.add( extension );
     }
     
     public boolean isUnsatisfied( Extension extension )
     {
       return _unsatisfied.contains( extension );
     }
     
     public void startVisiting( Extension extension )
     {
       _currentlyVisiting.add( extension );
       _stateByExtension.put( extension, STATE_VISITING );
     }
     
     public void endVisiting( Extension extension )
     {
       _currentlyVisiting.remove( extension );
       _stateByExtension.put( extension, STATE_VISITED );
     }
     
     public void markUnsatisfiedChain()
     {
       for ( Iterator i = _currentlyVisiting.iterator(); i.hasNext(); )
       {
         addUnsatisfied( (Extension) i.next() );
       }
     }
     
     public void markCycleChain( Extension current )
     {
       ArrayList al = new ArrayList();
       al.addAll( _currentlyVisiting );
       al.add( current );
       _cycles.add( al );
     }
     
     public void addToTopo( Extension extension )
     {
       _topoList.add( extension );
     }
   }
   
   /**
    * Topologically sort the set of extensions in _sourcesByExtension based on
    * their dependencies. This algorithm detects cycles, but does not abort
    * on the detection of them. Instead, it discards cyclic dependencies for
    * the purposes of topo sorts (we should probably signal some kind of error
    * condition so that it can be reported)
    * 
    * @param stateByExtension a map of STATE_ constants by extension. Indicate
    *    the current "color" of this vertex in the algorithm.
    * @param topo the current topological value. 
    * @param topoByExtension assigned topological values for visited vertices.
    * @param vertex the current vertex (extension).
    */
   private void topologicalSort( TopoSortState state, Extension ext )
   {
 
     try
     {
       state.startVisiting( ext );
       for ( Iterator i = ext.getDependencies().iterator(); i.hasNext(); )
       {
         ExtensionDependency dep = (ExtensionDependency) i.next();
         Extension depExt = (Extension) _extensionsById.get( dep.getID() );
         
         if ( depExt == null || 
              state.isUnsatisfied( depExt ) ||
              !isVersionSatisfied( dep, depExt )  )
         {
           // We hit an unsatisfied dependency.
           state.markUnsatisfiedChain();
           List unsat = (List) _unsatisfiedDependencies.get( ext );
           if ( unsat == null )
           {
             unsat = new ArrayList();
             _unsatisfiedDependencies.put( ext, unsat );
           }
           unsat.add( dep );
         }
         // Follow to extensions which this one depends on even if they are not
         // satisfied (by version). This means if we have
         //   A 1.0 requires B 1.1 requires C 1.2
         // but the installed versions are:
         //   A 1.0
         //   B 1.5
         //   C 1.2
         // we still process (and load) C, but not B.
         if ( depExt != null )
         {
           if ( state.isVisiting( depExt ) )
           {
             // We hit a cycle. 
             state.markCycleChain( depExt );
           }           
           if ( state.isUnvisited( depExt ) )
           {
             topologicalSort( state, depExt );
           }
         }
       }
     }
     finally
     {
       if ( !state.isUnsatisfied( ext ) )
       {
         state.addToTopo( ext );
       }    
       state.endVisiting( ext );
     }
   }
   
   /**
    * Get an extension which satisfies the specified dependency. 
    * 
    * @param dep the dependency to satisfy.
    * @return the extension satisfying this dependency, or null if no 
    *    extension was found satisfying the dependency.
    */
   private boolean isVersionSatisfied( ExtensionDependency dep, Extension ext )
   {
     if ( ext != null )
     {
       // Check minimum version.
       if ( dep.getMinimumVersion() != null && 
         dep.getMinimumVersion().compareTo( ext.getVersion() ) > 0 )
       {
         return false;
       }
       
       // Check maximum version.
       if ( dep.getMaximumVersion() != null && 
         dep.getMaximumVersion().compareTo( ext.getVersion() ) < 0 )
       {
         return false;
       }
     }
     
     return true;
   }
   
   /**
    * Get the list of extension ids, sorted in order of the topological sort of
    * their dependency graph.<p>
    * 
    * This list will not contain the ids of extensions which have unsatisfied
    * dependencies. To get a list of unsatisfied dependencies, call 
    * {@link #getUnsatisfiedExtensions()}.<p>
    * 
    * This list may contain extensions whose dependencies are not entirely 
    * satisfied because the dependency graph contained cycles. To get a list
    * of all identified cycles in the dependency graph, call 
    * getCycles().<p>
    * 
    * IDE implementations should generally process the manifests of extensions
    * in the order the extensions are returned by this method.
    * 
    * @return the set of all extension ids retrieved from processed sources.
    */
   public List getSortedExtensionIDs()
   {
     ArrayList idList = new ArrayList( _topologicalExtensionList.size() );
     for ( Iterator i = _topologicalExtensionList.iterator(); i.hasNext(); )
     {
       Extension ext = (Extension) i.next();
       idList.add( ext.getID() );
     }
     
     return Collections.unmodifiableList( idList );
   }
   
   /**
    * Get the resolved version of the specified extension id.
    * 
    * @param id the id of an extension.
    * @return the resolved version of the extension.
    */
   public Version getResolvedVersion( String id )
   {
     Extension ext = (Extension) _extensionsById.get( id );
     return ext.getVersion();
   }
   
   /**
    * Get cycles in the dependency graph. This method returns a collection of 
    * Lists, one for each identified cycle in the graph. Each list entry consists
    * of Extension instances for each extension in the cycle, starting at some
    * arbitrary extension and ending with the second encountered instance of 
    * some extension.
    * 
    * @return a collection of lists.
    */
   public Collection getCycles()
   {
     return _cycles;
   }
   
   /**
    * Get a collection of extensions with unsatisfied dependencies. 
    * 
    * @return a collection of Extensions which have one or more unsatisfied
    *    dependencies.
    */
   public Collection getUnsatisfiedExtensions()
   {
     return Collections.unmodifiableCollection( _unsatisfiedDependencies.keySet() );
   }
   
   /**
    * Get the set of unsatisfied dependencies for the specified extension.
    * 
    * @param unsatisfied an unsatisfied Extension. Must be in the set of 
    *    extensions returned by getUnsatisfiedExtensions(). Must not be null.
    * @return a collection of ExtensionDependency instances, one for each
    *    dependency of this extension that was missing.
    */
   public Collection getUnsatisfiedDependencies( Extension unsatisfied )
   {
     if ( unsatisfied == null )
     {
       throw new NullPointerException( "unsatisfied is null" );
     }
     Collection result = (Collection) _unsatisfiedDependencies.get( unsatisfied );
     if ( result == null )
     {
       throw new IllegalArgumentException( 
         "Not in the list of unsatisfied extensions: " + unsatisfied );
     }
     
     return Collections.unmodifiableCollection( result );
   }
   
   
   
   /**
    * Get the source of an extension. If there is more than one extension with
    * the same id, this returns the most recent version of the extension.
    * 
    * @param id the id of an extension. Must not be null, must be a known
    *    extension.
    * @return the source of the most recent version of the specified extension.
    */
   public ExtensionSource getSource( String id )
   {
     if ( id == null )
     {
       throw new NullPointerException( "id is null" );
     }
     
     Extension extension = (Extension) _extensionsById.get( id );
     if ( extension == null )
     {
       throw new IllegalArgumentException( "Unknown extension id " + id );
     }
     
     return (ExtensionSource) _sourcesByExtension.get( extension );
   }
   
 
   
   /**
    * A minimal visitor which just processes the id, version, esdk-version and
    * dependencies of an extension.
    */
   private static class MinimalExtensionVisitor extends BaseExtensionVisitor
   {
     private final Map _sourcesByExtension = new HashMap();
     private ElementVisitor _dependenciesVisitor = new DependenciesVisitor();
     
     public Map getSourcesByExtension()
     {
       return _sourcesByExtension;
     }
     
     public void start( ElementStartContext start )
     {
       DefaultExtension ext = processExtension( start );
       if ( ext != null )
       {
         start.registerChildVisitor( DependenciesVisitor.ELEMENT, 
           _dependenciesVisitor );
       }
     }
     
     public void end( ElementEndContext end )
     {
       ExtensionSource source = 
         (ExtensionSource) end.getScopeData().get( SOURCE );
       Extension extension = 
         (Extension) end.getScopeData().get( ExtensionHook.KEY_EXTENSION );
       if ( extension != null )
       {
         _sourcesByExtension.put( extension, source );
       }
     }
   }
   
   // Vertex states for topologicalSort(). Should really be an enum.
   private Object STATE_NOT_VISITED = "notvisited";
   private Object STATE_VISITING = "visiting";
   private Object STATE_VISITED = "visited";
   
   
   /**
    * Mechanism used by this class to look up whether an extension is 
    * enabled.
    */
   public static interface EnabledExtensionLookup
   {
     public boolean isExtensionEnabled( Extension e );
   }
 }