<commit_before>-----------------------------------------------------------------------------
-- |
-- Module      :  Hackage.DepGraph
-- Copyright   :  (c) <NAME> 2008
-- License     :  BSD-like
--
-- Maintainer  :  <EMAIL>
-- Stability   :  provisional
-- Portability :  portable
--
-- Package dependency graph
--
-----------------------------------------------------------------------------
module Hackage.DepGraph (
  DepGraph, ResolvedPackage(..),
  fromList, toList,
  empty,
  ready,
  removeCompleted,
  removeFailed
  ) where

import Hackage.Types
import Distribution.Package (PackageIdentifier, Package(..), PackageFixedDeps(..))

import Data.List (partition, intersect)
import Control.Exception (assert)

data ResolvedPackage = ResolvedPackage PkgInfo FlagAssignment [PackageIdentifier]
  deriving Show

instance Package ResolvedPackage where
   packageId (ResolvedPackage p _ _) = packageId p

instance PackageFixedDeps ResolvedPackage where
   depends (ResolvedPackage _ _ d) = d

-- | A package dependency graph
--
-- * Invariant: the graph is acyclic
--
newtype DepGraph = DepGraph [ResolvedPackage]

-- | Build a dependency graph from a set of resolved packages.
--
-- * The dependencies must not by cyclic.
--
fromList :: [ResolvedPackage] -> DepGraph
fromList = DepGraph

toList :: DepGraph -> [ResolvedPackage]
toList (DepGraph g) = g

-- | Is the graph empty?
empty :: DepGraph -> Bool
empty (DepGraph g) = null g


-- | The next package, meaning a package which has no dependencies.
--
-- * The graph must be non-empty.
--
ready :: DepGraph -> ResolvedPackage
ready (DepGraph pkgs) =
  case [ pkg | pkg@(ResolvedPackage _ _ []) <- pkgs ] of
    []      -> error $ "DepGraph.head: internal error: no nodes with 0-outdegree\n"
                    ++ unlines (map show pkgs)
    (pkg:_) -> pkg


-- | Remove a package from the graph, getting back an updated graph.
--
-- * The package must exist in the graph.
-- * The package must have had no dependent packages.
--
removeCompleted :: PackageIdentifier -> DepGraph -> DepGraph
removeCompleted pkgid (DepGraph pkgs) =
  case partition isCompleted pkgs of
    ([_pkg], pkgs') -> DepGraph [ ResolvedPackage pkg fs (filter (/=pkgid) deps)
                                | ResolvedPackage pkg fs deps <- pkgs' ]
    _               -> error "DepGraph.removeCompleted: no such package"
  where isCompleted = (==pkgid) . packageId

-- | Remove a package and all the packages that depend on it from the graph.
--
-- You get back an updated graph and a list of packages that were removed
-- (the given package will be first in that list).
--
-- * The package must exist in the graph.
--
removeFailed :: PackageIdentifier -> DepGraph -> (DepGraph, [ResolvedPackage])
removeFailed pkgid (DepGraph pkgs0) =
  case partition ((==pkgid) . packageId) pkgs0 of
    ([pkg], pkgs') -> case remove [pkg] [pkgid] pkgs' of
                        result -> assert (packageId p == pkgid) result
                          where (_,p:_) = result
    _              -> error "DepGraph.removeFailed: no such package"

  where<commit_msg>Take nub by package id when making a dep graph and give more detailed error messages for internal error conditions. Fixes a problem where installing a set of packages where several depended on the same package would give us a ResolvedDependency list containing multiple copies of that package. The DepGraph was expecting unique packages. Resolving package deps and generating install plans needs more thought and better specified invariants.<commit_after>-----------------------------------------------------------------------------
-- |
-- Module      :  Hackage.DepGraph
-- Copyright   :  (c) <NAME> 2008
-- License     :  BSD-like
--
-- Maintainer  :  <EMAIL>
-- Stability   :  provisional
-- Portability :  portable
--
-- Package dependency graph
--
-----------------------------------------------------------------------------
module Hackage.DepGraph (
  DepGraph, ResolvedPackage(..),
  fromList, toList,
  empty,
  ready,
  removeCompleted,
  removeFailed
  ) where

import Hackage.Types
import Distribution.Package
         ( PackageIdentifier, showPackageId, Package(..), PackageFixedDeps(..) )
import Distribution.Simple.Utils
         ( intercalate, equating )

import Data.List
         ( partition, intersect, nubBy )
import Control.Exception
         ( assert )

data ResolvedPackage = ResolvedPackage PkgInfo FlagAssignment [PackageIdentifier]
  deriving Show

instance Package ResolvedPackage where
   packageId (ResolvedPackage p _ _) = packageId p

instance PackageFixedDeps ResolvedPackage where
   depends (ResolvedPackage _ _ d) = d

-- | A package dependency graph
--
-- * Invariant: the graph is acyclic
--
newtype DepGraph = DepGraph [ResolvedPackage]

-- | Build a dependency graph from a set of resolved packages.
--
-- * The dependencies must not by cyclic.
--
fromList :: [ResolvedPackage] -> DepGraph
fromList = DepGraph . nubBy (equating packageId)

toList :: DepGraph -> [ResolvedPackage]
toList (DepGraph g) = g

-- | Is the graph empty?
empty :: DepGraph -> Bool
empty (DepGraph g) = null g


-- | The next package, meaning a package which has no dependencies.
--
-- * The graph must be non-empty.
--
ready :: DepGraph -> ResolvedPackage
ready (DepGraph pkgs) =
  case [ pkg | pkg@(ResolvedPackage _ _ []) <- pkgs ] of
    []      -> error $ "DepGraph.head: internal error: no nodes with 0-outdegree\n"
                    ++ unlines (map show pkgs)
    (pkg:_) -> pkg


-- | Remove a package from the graph, getting back an updated graph.
--
-- * The package must exist in the graph.
-- * The package must have had no dependent packages.
--
removeCompleted :: PackageIdentifier -> DepGraph -> DepGraph
removeCompleted pkgid (DepGraph pkgs) =
  case partition isCompleted pkgs of
    ([_pkg], pkgs') -> DepGraph [ ResolvedPackage pkg fs (filter (/=pkgid) deps)
                                | ResolvedPackage pkg fs deps <- pkgs' ]
    _               -> error $ "DepGraph.removeCompleted: no such package "
                            ++ showPackageId pkgid
                            ++ "\nin DepGraph: "
                            ++ intercalate ", "
                                 (map (showPackageId . packageId) pkgs)

  where isCompleted = (==pkgid) . packageId

-- | Remove a package and all the packages that depend on it from the graph.
--
-- You get back an updated graph and a list of packages that were removed
-- (the given package will be first in that list).
--
-- * The package must exist in the graph.
--
removeFailed :: PackageIdentifier -> DepGraph -> (DepGraph, [ResolvedPackage])
removeFailed pkgid (DepGraph pkgs0) =
  case partition ((==pkgid) . packageId) pkgs0 of
    ([pkg], pkgs') -> case remove [pkg] [pkgid] pkgs' of
                        result -> assert (packageId p == pkgid) result
                          where (_,p:_) = result
    ((_:_),_)      -> error $ "DepGraph.removeFailed: internal error multiple instances of "
                           ++ showPackageId pkgid
    _              -> error $ "DepGraph.removeFailed: no such package "
                           ++ showPackageId pkgid

  where
{'fraction_non_alphanumeric': 0.13928471640122939, 'fraction_numerical': 0.0019558535903883767, 'mean_word_length': 2.2734339277549154, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6591999', 'n_tokens_mistral': 1966, 'n_tokens_neox': 1880, 'n_words': 705}