[commit: Cabal] master: documentation for backjumping (652b610)

[Ian Lynagh]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/Cabal

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/652b610a18a1dd320e2718203e665ed7a941f5c2

>---------------------------------------------------------------

commit 652b610a18a1dd320e2718203e665ed7a941f5c2
Author: Andres Loeh <andres at well-typed.com>
Date:   Tue Jun 21 09:45:47 2011 +0000

    documentation for backjumping

>---------------------------------------------------------------

 .../Client/Dependency/Modular/Explore.hs           |   31 ++++++++++++++++++--
 1 files changed, 28 insertions(+), 3 deletions(-)

diff --git a/cabal-install/Distribution/Client/Dependency/Modular/Explore.hs b/cabal-install/Distribution/Client/Dependency/Modular/Explore.hs
index 5be31c7..b9dc52e 100644
--- a/cabal-install/Distribution/Client/Dependency/Modular/Explore.hs
+++ b/cabal-install/Distribution/Client/Dependency/Modular/Explore.hs
@@ -15,6 +15,10 @@ import Distribution.Client.Dependency.Modular.PSQ as P
 import Distribution.Client.Dependency.Modular.Tree
 
 -- | Backjumping.
+--
+-- A tree traversal that tries to propagate conflict sets
+-- up the tree from the leaves, and thereby cut branches.
+-- All the tricky things are done in the function 'combine'.
 backjump :: Tree a -> Tree (Maybe (ConflictSet QPN))
 backjump = snd . cata go
   where
@@ -32,9 +36,30 @@ backjump = snd . cata go
         c          = case cs of []    -> Nothing
                                 d : _ -> d
 
--- | TODO: This needs documentation. It's a horribly tricky function, mainly w.r.t.
--- laziness.
-combine :: Var QPN -> [(a, (Maybe (ConflictSet QPN), b))] -> ConflictSet QPN -> (Maybe (ConflictSet QPN), [(a, b)])
+-- | The 'combine' function is at the heart of backjumping. It takes
+-- the variable we're currently considering, and a list of children
+-- annotated with their respective conflict sets, and an accumulator
+-- for the result conflict set. It returns a combined conflict set
+-- for the parent node, and a (potentially shortened) list of children
+-- with the annotations removed.
+--
+-- It is *essential* that we produce the results as early as possible.
+-- In particular, we have to produce the list of children prior to
+-- traversing the entire list -- otherwise we lose the desired behaviour
+-- of being able to traverse the tree from left to right incrementally.
+--
+-- We can shorten the list of children if we find an individual conflict
+-- set that does not contain the current variable. In this case, we can
+-- just lift the conflict set to the current level, because the current
+-- level cannot possibly have contributed to this conflict, so no other
+-- choice at the current level would avoid the conflict.
+--
+-- If any of the children might contain a successful solution
+-- (indicated by Nothing), then Nothing will be the combined
+-- conflict set. If all children contain conflict sets, we can
+-- take the union as the combined conflict set.
+combine :: Var QPN -> [(a, (Maybe (ConflictSet QPN), b))] ->
+           ConflictSet QPN -> (Maybe (ConflictSet QPN), [(a, b)])
 combine _   []                      c = (Just c, [])
 combine var ((k, (     d, v)) : xs) c = (\ ~(e, ys) -> (e, (k, v) : ys)) $
                                         case d of