module FlatCurry.NormalizeLet ( normalizeLet ) where

import Data.SCC          ( scc )
import FlatCurry.Goodies ( allVars )
import FlatCurry.Types

--- Normalize all let expressions occurring in an expression
--- by transforming each let expression into a hierarchical let expression
--- according to the dependencies of the bindings.
--- For instance,
---
---     let { x = f y ; y = g z} in e
---
--- is transformed into
---
---     let { y = g z} in let { x = f y} in e
---
normalizeLet :: Expr -> Expr
normalizeLet exp = case exp of
  Var _         -> exp
  Lit _         -> exp
  Comb ct qf es -> Comb ct qf (map normalizeLet es)
  Let bs e      -> foldr Let e (sortLetBindings bs)
  Free vs e     -> Free vs (normalizeLet e)
  Or e1 e2      -> Or (normalizeLet e1) (normalizeLet e2)
  Case ct be bs -> Case ct (normalizeLet be)
                        (map (\ (Branch p e) -> Branch p (normalizeLet e)) bs)
  Typed e t     -> Typed (normalizeLet e) t

-- Sort a list of let bindings into strongly connected compontents
-- sorted by the dependencies of the defined variables.
sortLetBindings :: [(Int,Expr)] -> [[(Int,Expr)]]
sortLetBindings bs = scc definedBy usedIn bs
 where
  definedBy (v,_) = [v]

  usedIn (_,e) = filter (`elem` map fst bs) (allVars e)