# Copyright (c) 2009 ActiveState Software Inc.
# See http://www.activestate.com/activepython/license/ for licensing
# information.

"""
    pypm.client.dependency
    ~~~~~~~~~~~~~~~~~~~~~~

    This module contains package dependency related functionality
"""

import operator
from textwrap import dedent
import pkg_resources
import logging
from collections import deque, namedtuple, defaultdict

from pypm.common.repository import RepoPackage
from pypm.client.base import PyPMFeature
from pypm.client import error
from pypm.client.store import InstalledPackage
from pypm.client.version import sort_packages_by_version

LOG = logging.getLogger(__name__)


#
# Dependency management
#

class Dependency(PyPMFeature):
    
    # An virtual package is a package associated with a single extra
    # (from setuptools' extras, that is). The need for them is based on the fact
    # that we can no longer treat packages as distinct entities, for both the
    # install and uninstall operation needs to take into account the extras as
    # well. 
    VirtualPackage = namedtuple('VirtualPackage', 'pkg extra')
    
    def get_dependencies(self, package, extras):
        """Return *all* dependencies for the given package
        
        Although conceptually the dependencies are listed recursively, this
        implementation is based on queue.
        
        Note that results will include all dependencies, not just the ones that
        are not yet installed. The caller is responsible for pruning the ones
        already installed.
        """
        queue = deque()     # items waiting to be processed
        consumed = set()    # items already processed
        results = []        # processed results
        
        def queue_add(item):
            """Add to ``queue`` if not already ``consumed`` or in ``results``"""
            if not (item in queue or item in consumed):
                queue.append(item)
                
        def add_to_queue(p, extras):
            """Add the given package and its extras list to queue"""
            queue_add(self.VirtualPackage(p, ''))  # the default requirements
            for e in extras or []:
                queue_add(self.VirtualPackage(p, e))
                
        def add_to_results(pkg):
            """Add to the results list keeping it unique"""
            for p in results:
                if p.canonical_name == pkg.canonical_name:
                    if p == pkg:
                        return # already added
                    else:
                        raise ValueError, (
                            '"%s" indirectly depends on multiple versions of '
                            '"%s" (%s; %s). Whereas PyPM can only install a '
                            'single version.' % (
                                package.canonical_name, pkg.canonical_name,
                                p.full_version, pkg.full_version))
            results.append(pkg)
                
        add_to_queue(package, extras)
        while queue:
            pkg, e = queue.popleft()
            add_to_results(pkg)
            
            for req in pkg.install_requires[e]:
                req = pkg_resources.Requirement.parse(req)
                # FIXME: http://twitter.com/sridhr/status/6247132653
                add_to_queue(
                    self._find_requirement_in_repo((pkg, e), req), req.extras)
                    
        return results
    
    def get_removable_dependents(self, ipkg):
        """Return installed packages depending on ``ipkg``"""
        assert type(ipkg) is InstalledPackage
        
        # A matrix of VirtualPackage. vp_matrix[a][b] is True if b depends on a
        vp_matrix = defaultdict(lambda: defaultdict(bool))
        ipkglist = self.pypmenv.installed_store.find_all_packages()
        ipkgmap = {}
        queue = deque()
        
        for p in ipkglist:
            ipkgmap[p.canonical_name] = p
            queue.append(self.VirtualPackage(p, '')) # 1. add actual package
            
        # Build the reverse-depends matrix (vp_matrix)
        while queue:
            dvp = queue.popleft()
            for reqs in dvp.pkg.install_requires[dvp.extra]:
                req = pkg_resources.Requirement.parse(reqs)
                reqp = ipkgmap[req.project_name.lower()]
                for e in self._normalize_extras(req.extras):
                    vp = self.VirtualPackage(reqp, e)
                    vp_matrix[vp][dvp] = True
                    if vp.extra:
                        queue.append(vp) # 2. add virtual package
                    
        results = []
        # Traverse all the dependents of ``ipkg`` using vp_matrix
        queue = deque()
        queue.append(self.VirtualPackage(ipkg, ''))
        while queue:
            vp = queue.popleft()
            if vp.extra == '':
                # add only an ctual package, not the virtual 'extra' thingy
                results.append(vp.pkg)
            vp_dependents = vp_matrix[vp].keys()
            for dvp in vp_matrix[vp].keys():
                queue.append(dvp)
                    
        return results
        
    def _find_requirement_in_repo(self, (pkg, e), req):
        """Find the best matching package (in repo) for the given requirement.
        
        (pkg, e) was the package that was requesting ``req``.
        
        We return the best matching package satisfying ``req``
        """
        try:
            return self.pypmenv.repo_store.find_requirement(req)
        except error.NoPackageAvailable:
            pkgname = '%s[%s]' % (pkg.name, e) if e else pkg.name
            raise error.DependencyNotFound(pkgname, req)
        
    def _normalize_extras(self, extras):
        """Return a tuple of extras including the empty/default extra"""
        extras = tuple(extras or ())
        assert '' not in extras
        return ('',) + extras
