/*
 * Copyright 2005 by Oracle USA
 * 500 Oracle Parkway, Redwood Shores, California, 94065, U.S.A.
 * All rights reserved.
 */
package javax.ide.extension.spi;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;

import java.net.URI;

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.ElementContext;
import javax.ide.extension.ElementStartContext;
import javax.ide.extension.ElementVisitor;
import javax.ide.extension.Extension;
import javax.ide.extension.ExtensionDependency;
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 = ExtensionVisitor.KEY_EXTENSION_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();

  DependencyTree( List failedSources, Map sourcesByExtension )
  {
    _sourcesByExtension = sourcesByExtension;
    removeDuplicates( sourcesByExtension );
    
    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();

  }
  
  public static Map<Extension,ExtensionSource> loadMinimal( 
    DefaultElementContext initialContext,
    Collection<ExtensionSource> extensionSources, 
    List<ExtensionSource> failedSources,
    Logger logger ) 
  {
    SAXManifestParser minimalParser = new SAXManifestParser( initialContext );
    ((DefaultElementContext)minimalParser.getContext()).setMessageReporter( logger );
    MinimalExtensionVisitor visitor = new MinimalExtensionVisitor();
    
    minimalParser.getContext().registerChildVisitor(
      ExtensionVisitor.ELEMENT, visitor
    );
    
    for ( Iterator i = extensionSources.iterator(); i.hasNext(); )
    {
      ExtensionSource source = (ExtensionSource) i.next();
      minimalParser.getContext().getScopeData().put( SOURCE, source );
      InputStream inputStream = null;
      try
      { 
        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: "+saxe.getLocalizedMessage(),
          new LocatorImpl( source.getManifestURI().toString() )
        );
        failedSources.add( source );
      }
      catch ( FileNotFoundException fnf )
      {
        fnf.printStackTrace();
        minimalParser.getContext().getLogger().log(
          Level.SEVERE,
          source.getName()+" does not contain an extension manifest.",
          new LocatorImpl( source.getManifestURI().toString() )
        );        
      }
      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
          );
        }
      }
    }
    
    return visitor.getSourcesByExtension();
  }

  /**
   * 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 )
  {
    List<ExtensionSource> failedSources = new ArrayList<ExtensionSource>();
    Map sbe = loadMinimal( initialContext, extensionSources, failedSources, logger );
    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.
   */
  public static void removeDuplicates( Map sourcesByExtension )
  {
    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 extension( ElementContext context, Extension extension )
    {
      ExtensionSource source = 
        (ExtensionSource) context.getScopeData().get( SOURCE );
      if ( extension != null )
      {
        _sourcesByExtension.put( extension, source );
      }
    }
    
    public void addToClasspath( ElementContext context, Extension extension, 
      URI classpathEntry )
    {
      // NO-OP
    }
  }
  
  // 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 );
  }
}