{-# OPTIONS -cpp #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Distribution.Configuration
-- Copyright   :  Thomas Schilling, 2007
-- 
-- Maintainer  :  Isaac Jones <ijones@syntaxpolice.org>
-- Stability   :  alpha
-- Portability :  portable
--
-- Configurations

{- All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.

    * Redistributions in binary form must reproduce the above
      copyright notice, this list of conditions and the following
      disclaimer in the documentation and/or other materials provided
      with the distribution.

    * Neither the name of Isaac Jones nor the names of other
      contributors may be used to endorse or promote products derived
      from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -}

module Distribution.Configuration (
    Flag(..),
    ConfVar(..),
    Condition(..), parseCondition, simplifyCondition,
    CondTree(..), ppCondTree, mapTreeData,
    --satisfyFlags, 
    resolveWithFlags, ignoreConditions,
    DepTestRslt(..)
  ) where

import Distribution.Compat.ReadP as ReadP hiding ( char )
import qualified Distribution.Compat.ReadP as ReadP ( char )
import Distribution.Version 
    ( Version(..), VersionRange(..), withinRange
    , showVersionRange, parseVersionRange )

import Text.PrettyPrint.HughesPJ

import Data.Char ( isAlphaNum, toLower )
import Data.Maybe ( catMaybes, maybeToList )
import Data.Monoid

#ifdef DEBUG
import Data.List ( (\\) )
import Distribution.ParseUtils
#endif

------------------------------------------------------------------------------

-- | A flag can represent a feature to be included, or a way of linking
--   a target against its dependencies, or in fact whatever you can think of.
data Flag = MkFlag
    { flagName        :: String
    , flagDescription :: String
    , flagDefault     :: Bool
    }

instance Show Flag where show (MkFlag n _ _) = n

-- | A @ConfFlag@ represents an user-defined flag
data ConfFlag = ConfFlag String
    deriving Eq

-- | A @ConfVar@ represents the variable type used. 
data ConfVar = OS String 
             | Arch String 
             | Flag ConfFlag
             | Impl String VersionRange
               deriving Eq

instance Show ConfVar where
    show (OS n) = "os(" ++ n ++ ")"
    show (Arch n) = "arch(" ++ n ++ ")"
    show (Flag (ConfFlag f)) = "flag(" ++ f ++ ")"
    show (Impl c v) = "impl(" ++ c ++ " " ++ showVersionRange v ++ ")"

-- | A boolean expression parameterized over the variable type used.
data Condition c = Var c
                 | Lit Bool
                 | CNot (Condition c)
                 | COr (Condition c) (Condition c)
                 | CAnd (Condition c) (Condition c)
                   
instance Show c => Show (Condition c) where
    show c = render $ ppCond c

-- | Pretty print a @Condition@.
ppCond :: Show c => Condition c -> Doc
ppCond (Var x) = text (show x)
ppCond (Lit b) = text (show b)
ppCond (CNot c) = char '!' <> parens (ppCond c)
ppCond (COr c1 c2) = parens $ sep [ppCond c1, text "||" <+> ppCond c2]
ppCond (CAnd c1 c2) = parens $ sep [ppCond c1, text "&&" <+> ppCond c2]


-- | Simplify the condition and return its free variables.
simplifyCondition :: Condition c
                  -> (c -> Either d Bool)   -- ^ (partial) variable assignment
                  -> (Condition d, [d])
simplifyCondition cond i = fv . walk $ cond
  where
    walk cnd = case cnd of
      Var v   -> either Var Lit (i v)
      Lit b   -> Lit b
      CNot c  -> case walk c of
                   Lit True -> Lit False
                   Lit False -> Lit True
                   c' -> CNot c'
      COr c d -> case (walk c, walk d) of
                   (Lit False, d') -> d'
                   (Lit True, _)   -> Lit True
                   (c', Lit False) -> c'
                   (_, Lit True)   -> Lit True
                   (c',d')         -> COr c' d'
      CAnd c d -> case (walk c, walk d) of
                    (Lit False, _) -> Lit False
                    (Lit True, d') -> d'
                    (_, Lit False) -> Lit False
                    (c', Lit True) -> c'
                    (c',d')        -> CAnd c' d'
    -- gather free vars
    fv c = (c, fv' c)
    fv' c = case c of
      Var v     -> [v]
      Lit _      -> []
      CNot c'    -> fv' c'
      COr c1 c2  -> fv' c1 ++ fv' c2
      CAnd c1 c2 -> fv' c1 ++ fv' c2

-- | Simplify a configuration condition using the os and arch names.  Returns
--   the names of all the flags occurring in the condition.
simplifyWithSysParams :: String -> String -> (String, Version) -> Condition ConfVar ->  
                         (Condition ConfFlag, [String])
simplifyWithSysParams os arch (impl, implVer) cond = (cond', flags)
  where
    (cond', fvs) = simplifyCondition cond interp 
    interp (OS name)   = Right $ lcase name == lcase os
                              || lcase name `elem` osAliases (lcase os)
    interp (Arch name) = Right $ lcase name == lcase arch
    interp (Impl i vr) = Right $ lcase impl == lcase i
                              && implVer `withinRange` vr
    interp (Flag  f)   = Left f
    flags = [ fname | ConfFlag fname <- fvs ]

    --FIXME: use Distribution.System.OS type and alias list:
    osAliases "mingw32"  = ["windows"]
    osAliases "solaris2" = ["solaris"]
    osAliases _          = []
    lcase = map toLower

-- XXX: Add instances and check
--
-- prop_sC_idempotent cond a o = cond' == cond''
--   where
--     cond'  = simplifyCondition cond a o
--     cond'' = simplifyCondition cond' a o
--
-- prop_sC_noLits cond a o = isLit res || not (hasLits res)
--   where
--     res = simplifyCondition cond a o
--     hasLits (Lit _) = True
--     hasLits (CNot c) = hasLits c
--     hasLits (COr l r) = hasLits l || hasLits r
--     hasLits (CAnd l r) = hasLits l || hasLits r
--     hasLits _ = False
--

-- | Parse a configuration condition from a string.
parseCondition :: ReadP r (Condition ConfVar)
parseCondition = condOr
  where
    condOr   = sepBy1 condAnd (oper "||") >>= return . foldl1 COr
    condAnd  = sepBy1 cond (oper "&&")>>= return . foldl1 CAnd
    cond     = sp >> (lit +++ inparens condOr +++ notCond +++ osCond 
                      +++ archCond +++ flagCond +++ implCond )
    inparens   = between (ReadP.char '(' >> sp) (sp >> ReadP.char ')' >> sp)
    notCond  = ReadP.char '!' >> sp >> cond >>= return . CNot
    osCond   = string "os" >> sp >> inparens osIdent >>= return . Var. OS 
    archCond = string "arch" >> sp >> inparens archIdent >>= return . Var . Arch 
    flagCond = string "flag" >> sp >> inparens flagIdent >>= return . Var . Flag . ConfFlag
    implCond = string "impl" >> sp >> inparens implIdent >>= return . Var
    ident    = munch1 isIdentChar >>= return . map toLower
    lit      = ((string "true" <++ string "True") >> return (Lit True)) <++ 
               ((string "false" <++ string "False") >> return (Lit False))
    archIdent     = ident >>= return 
    osIdent       = ident >>= return 
    flagIdent     = ident
    isIdentChar c = isAlphaNum c || (c `elem` "_-")
    oper s        = sp >> string s >> sp
    sp            = skipSpaces
    implIdent     = do i <- ident
                       vr <- sp >> option AnyVersion parseVersionRange
                       return $ Impl i vr

------------------------------------------------------------------------------

data CondTree v c a = CondNode 
    { condTreeData        :: a
    , condTreeConstraints :: c
    , condTreeComponents  :: [( Condition v
                              , CondTree v c a
                              , Maybe (CondTree v c a))]
    }

mapCondTree :: (a -> b) -> (c -> d) -> (Condition v -> Condition w) 
            -> CondTree v c a -> CondTree w d b
mapCondTree fa fc fcnd (CondNode a c ifs) =
    CondNode (fa a) (fc c) (map g ifs)
  where
    g (cnd, t, me) = (fcnd cnd, mapCondTree fa fc fcnd t,
                           fmap (mapCondTree fa fc fcnd) me)

mapTreeConstrs :: (c -> d) -> CondTree v c a -> CondTree v d a
mapTreeConstrs f = mapCondTree id f id

mapTreeConds :: (Condition v -> Condition w) -> CondTree v c a -> CondTree w c a
mapTreeConds f = mapCondTree id id f

mapTreeData :: (a -> b) -> CondTree v c a -> CondTree v c b
mapTreeData f = mapCondTree f id id

instance (Show v, Show c) => Show (CondTree v c a) where
    show t = render $ ppCondTree t (text . show)

ppCondTree :: Show v => CondTree v c a -> (c -> Doc) -> Doc
ppCondTree (CondNode _dat cs ifs) ppD =
    (text "build-depends: " <+>
      ppD cs)
    $+$
    (vcat $ map ppIf ifs)
  where 
    ppIf (c,thenTree,mElseTree) = 
        ((text "if" <+> ppCond c <> colon) $$
          nest 2 (ppCondTree thenTree ppD))
        $+$ (maybe empty (\t -> text "else: " $$ nest 2 (ppCondTree t ppD))
                   mElseTree)

 
-- | Result of dependency test. Isomorphic to @Maybe d@ but renamed for
--   clarity.
data DepTestRslt d = DepOk | MissingDeps d 

instance Monoid d => Monoid (DepTestRslt d) where
    mempty = DepOk
    mappend DepOk x = x
    mappend x DepOk = x
    mappend (MissingDeps d) (MissingDeps d') = MissingDeps (d `mappend` d')


data BT a = BTN a | BTB (BT a) (BT a)  -- very simple binary tree


-- | Try to find a flag assignment that satisfies the constaints of all trees.
--
-- Returns either the missing dependencies, or a tuple containing the
-- resulting data, the associated dependencies, and the chosen flag
-- assignments.
--
-- In case of failure, the _smallest_ number of of missing dependencies is
-- returned. [XXX: Could also be specified with a function argument.]
--
-- XXX: The current algorithm is rather naive.  A better approach would be to:
--
-- * Rule out possible paths, by taking a look at the associated dependencies.
--
-- * Infer the required values for the conditions of these paths, and
--   calculate the required domains for the variables used in these
--   conditions.  Then picking a flag assignment would be linear (I guess).
--
-- This would require some sort of SAT solving, though, thus it's not
-- implemented unless we really need it.
--   
resolveWithFlags :: Monoid a =>
     [(String,[Bool])] 
        -- ^ Domain for each flag name, will be tested in order.
  -> String  -- ^ OS name, as returned by System.Info.os
  -> String  -- ^ arch name, as returned by System.Info.arch
  -> (String, Version) -- ^ Compiler name + version
  -> [CondTree ConfVar [d] a]    
  -> ([d] -> DepTestRslt [d])  -- ^ Dependency test function.
  -> (Either [d] -- missing dependencies
       ([a], [d], [(String, Bool)]))
resolveWithFlags dom os arch impl trees checkDeps =
    case try dom [] of
      Right r -> Right r
      Left dbt -> Left $ findShortest dbt
  where 
    -- Check dependencies only once; might avoid some duplicate efforts.
    preCheckedTrees = map ( mapTreeConstrs (\d -> (checkDeps d,d))
                          . mapTreeConds (fst . simplifyWithSysParams os arch impl) )
                        trees

    -- @try@ recursively tries all possible flag assignments in the domain and
    -- either succeeds or returns a binary tree with the missing dependencies
    -- encountered in each run.  Since the tree is constructed lazily, we
    -- avoid some computation overhead in the successful case.
    try [] flags = 
        let (depss, as) = unzip 
                         . map (simplifyCondTree (env flags)) 
                         $ preCheckedTrees
        in case mconcat depss of
             (DepOk, ds) -> Right (as, ds, flags)
             (MissingDeps mds, _) -> Left (BTN mds)
    try ((n, vals):rest) flags = 
        tryAll $ map (\v -> try rest ((n, v):flags)) vals

    tryAll = foldr mp mz

    -- special version of `mplus' for our local purposes
    mp (Left xs)   (Left ys)   = (Left (BTB xs ys))
    mp (Left _)    m@(Right _) = m
    mp m@(Right _) _           = m

    -- `mzero'
    mz = Left (BTN [])

    env flags flag@(ConfFlag n) = maybe (Left flag) Right . lookup n $ flags 

    -- for the error case we inspect our lazy tree of missing dependencies and
    -- pick the shortest list of missing dependencies
    findShortest (BTN x) = x
    findShortest (BTB lt rt) = 
        let l = findShortest lt
            r = findShortest rt
        in case (l,r) of
             ([], xs) -> xs  -- [] is too short
             (xs, []) -> xs
             ([x], _) -> [x] -- single elem is optimum
             (_, [x]) -> [x]
             (xs, ys) -> if lazyLengthCmp xs ys
                         then xs else ys 
    -- lazy variant of @\xs ys -> length xs <= length ys@
    lazyLengthCmp [] _ = True
    lazyLengthCmp _ [] = False
    lazyLengthCmp (_:xs) (_:ys) = lazyLengthCmp xs ys



simplifyCondTree :: (Monoid a, Monoid d) =>
                    (v -> Either v Bool) 
                 -> CondTree v d a 
                 -> (d, a)
simplifyCondTree env (CondNode a d ifs) =
    foldr mappend (d, a) $ catMaybes $ map simplifyIf ifs
  where
    simplifyIf (cnd, t, me) = 
        case simplifyCondition cnd env of
          (Lit True, _) -> Just $ simplifyCondTree env t
          (Lit False, _) -> fmap (simplifyCondTree env) me
          _ -> error $ "Environment not defined for all free vars" 

-- | Flatten a CondTree.  This will resolve the CondTree by taking all
--  possible paths into account.  Note that since branches represent exclusive
--  choices this may not result in a \"sane\" result.
ignoreConditions :: (Monoid a, Monoid c) => CondTree v c a -> (a, c)
ignoreConditions (CondNode a c ifs) = (a, c) `mappend` mconcat (concatMap f ifs)
  where f (_, t, me) = ignoreConditions t 
                       : maybeToList (fmap ignoreConditions me)

------------------------------------------------------------------------------
-- compatibility

#if (__GLASGOW_HASKELL__ && __GLASGOW_HASKELL__ <= 602)
-- This instance wasn't present in Data.Monoid in GHC 6.2
instance (Monoid a, Monoid b) => Monoid (a,b) where
	mempty = (mempty, mempty)
	(a1,b1) `mappend` (a2,b2) =
		(a1 `mappend` a2, b1 `mappend` b2)
#endif

------------------------------------------------------------------------------
-- Testing

#ifdef DEBUG

tstTree :: CondTree ConfVar [Int] String
tstTree = CondNode "A" [0] 
              [ (CNot (Var (Flag (ConfFlag "a"))), 
                 CondNode "B" [1] [],
                 Nothing)
              , (CAnd (Var (Flag (ConfFlag "b"))) (Var (Flag (ConfFlag "c"))),
                CondNode "C" [2] [],
                Just $ CondNode "D" [3] 
                         [ (Lit True,
                           CondNode "E" [4] [],
                           Just $ CondNode "F" [5] []) ])
                ]


test_simplify = simplifyWithSysParams i386 darwin ("ghc",Version [6,6] []) tstCond 
  where 
    tstCond = COr (CAnd (Var (Arch ppc)) (Var (OS darwin)))
                  (CAnd (Var (Flag (ConfFlag "debug"))) (Var (OS darwin)))
    [ppc,i386] = ["ppc","i386"]
    [darwin,windows] = ["darwin","windows"]



test_parseCondition = map (runP 1 "test" parseCondition) testConditions
  where
    testConditions = [ "os(darwin)"
                     , "arch(i386)"
                     , "!os(linux)"
                     , "! arch(ppc)"
                     , "os(windows) && arch(i386)"
                     , "os(windows) && arch(i386) && flag(debug)"
                     , "true && false || false && true"  -- should be same 
                     , "(true && false) || (false && true)"  -- as this
                     , "(os(darwin))"
                     , " ( os ( darwin ) ) "
                     , "true && !(false || os(plan9))"
                     , "flag( foo_bar )"
                     , "flag( foo_O_-_O_bar )"
                     , "impl ( ghc )"
                     , "impl( ghc >= 6.6.1 )"
                     ]

test_ppCondTree = render $ ppCondTree tstTree (text . show)
  

test_simpCondTree = simplifyCondTree env tstTree
  where
    env x = maybe (Left x) Right (lookup x flags)
    flags = [(mkFlag "a",False), (mkFlag "b",False), (mkFlag "c", True)] 
    mkFlag = Flag . ConfFlag

test_resolveWithFlags = resolveWithFlags dom "os" "arch" ("ghc",Version [6,6] []) [tstTree] check
  where
    dom = [("a", [False,True]), ("b", [True,False]), ("c", [True,False])]
    check ds = let missing = ds \\ avail in
               case missing of
                 [] -> DepOk
                 _ -> MissingDeps missing
    avail = [0,1,3,4]

test_ignoreConditions = ignoreConditions tstTree

#endif