{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998
-}{-# LANGUAGE CPP #-}moduleVarSet(-- * Var, Id and TyVar set typesVarSet ,IdSet ,TyVarSet ,CoVarSet ,TyCoVarSet ,-- ** Manipulating these setsemptyVarSet ,unitVarSet ,mkVarSet ,extendVarSet ,extendVarSetList ,elemVarSet ,subVarSet ,unionVarSet ,unionVarSets ,mapUnionVarSet ,intersectVarSet ,intersectsVarSet ,disjointVarSet ,isEmptyVarSet ,delVarSet ,delVarSetList ,delVarSetByKey ,minusVarSet ,filterVarSet ,mapVarSet ,anyVarSet ,allVarSet ,transCloVarSet ,fixVarSet ,lookupVarSet_Directly ,lookupVarSet ,lookupVarSetByName ,sizeVarSet ,seqVarSet ,elemVarSetByKey ,partitionVarSet ,pluralVarSet ,pprVarSet ,-- * Deterministic Var set typesDVarSet ,DIdSet ,DTyVarSet ,DTyCoVarSet ,-- ** Manipulating these setsemptyDVarSet ,unitDVarSet ,mkDVarSet ,extendDVarSet ,extendDVarSetList ,elemDVarSet ,dVarSetElems ,subDVarSet ,unionDVarSet ,unionDVarSets ,mapUnionDVarSet ,intersectDVarSet ,dVarSetIntersectVarSet ,intersectsDVarSet ,disjointDVarSet ,isEmptyDVarSet ,delDVarSet ,delDVarSetList ,minusDVarSet ,foldDVarSet ,filterDVarSet ,mapDVarSet ,dVarSetMinusVarSet ,anyDVarSet ,allDVarSet ,transCloDVarSet ,sizeDVarSet ,seqDVarSet ,partitionDVarSet ,dVarSetToVarSet ,)where#include "HsVersions.h"
importGhcPrelude importVar (Var ,TyVar ,CoVar ,TyCoVar ,Id )importUnique importName (Name )importUniqSet importUniqDSet importUniqFM (disjointUFM ,pluralUFM ,pprUFM )importUniqDFM (disjointUDFM ,udfmToUfm ,anyUDFM ,allUDFM )importOutputable (SDoc )-- | A non-deterministic Variable Set---- A non-deterministic set of variables.-- See Note [Deterministic UniqFM] in UniqDFM for explanation why it's not-- deterministic and why it matters. Use DVarSet if the set eventually-- gets converted into a list or folded over in a way where the order-- changes the generated code, for example when abstracting variables.typeVarSet =UniqSet Var -- | Identifier SettypeIdSet =UniqSet Id -- | Type Variable SettypeTyVarSet =UniqSet TyVar -- | Coercion Variable SettypeCoVarSet =UniqSet CoVar -- | Type or Coercion Variable SettypeTyCoVarSet =UniqSet TyCoVar emptyVarSet::VarSet intersectVarSet::VarSet ->VarSet ->VarSet unionVarSet::VarSet ->VarSet ->VarSet unionVarSets::[VarSet ]->VarSet mapUnionVarSet::(a ->VarSet )->[a ]->VarSet -- ^ map the function over the list, and union the resultsunitVarSet::Var ->VarSet extendVarSet::VarSet ->Var ->VarSet extendVarSetList::VarSet ->[Var ]->VarSet elemVarSet::Var ->VarSet ->BooldelVarSet::VarSet ->Var ->VarSet delVarSetList::VarSet ->[Var ]->VarSet minusVarSet::VarSet ->VarSet ->VarSet isEmptyVarSet::VarSet ->BoolmkVarSet::[Var ]->VarSet lookupVarSet_Directly::VarSet ->Unique ->MaybeVar lookupVarSet::VarSet ->Var ->MaybeVar -- Returns the set element, which may be-- (==) to the argument, but not the same aslookupVarSetByName::VarSet ->Name ->MaybeVar sizeVarSet::VarSet ->IntfilterVarSet::(Var ->Bool)->VarSet ->VarSet delVarSetByKey::VarSet ->Unique ->VarSet elemVarSetByKey::Unique ->VarSet ->BoolpartitionVarSet::(Var ->Bool)->VarSet ->(VarSet ,VarSet )emptyVarSet =emptyUniqSet unitVarSet =unitUniqSet extendVarSet =addOneToUniqSet extendVarSetList =addListToUniqSet intersectVarSet =intersectUniqSets intersectsVarSet::VarSet ->VarSet ->Bool-- True if non-empty intersectiondisjointVarSet::VarSet ->VarSet ->Bool-- True if empty intersectionsubVarSet::VarSet ->VarSet ->Bool-- True if first arg is subset of second-- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty;-- ditto disjointVarSet, subVarSetunionVarSet =unionUniqSets unionVarSets =unionManyUniqSets elemVarSet =elementOfUniqSet minusVarSet =minusUniqSet delVarSet =delOneFromUniqSet delVarSetList =delListFromUniqSet isEmptyVarSet =isEmptyUniqSet mkVarSet =mkUniqSet lookupVarSet_Directly =lookupUniqSet_Directly lookupVarSet =lookupUniqSet lookupVarSetByName =lookupUniqSet sizeVarSet =sizeUniqSet filterVarSet =filterUniqSet delVarSetByKey =delOneFromUniqSet_Directly elemVarSetByKey =elemUniqSet_Directly partitionVarSet =partitionUniqSet mapUnionVarSet get_set xs =foldr(unionVarSet .get_set )emptyVarSet xs -- See comments with type signaturesintersectsVarSet s1 s2 =not(s1 `disjointVarSet `s2 )disjointVarSet s1 s2 =disjointUFM (getUniqSet s1 )(getUniqSet s2 )subVarSet s1 s2 =isEmptyVarSet (s1 `minusVarSet `s2 )anyVarSet::(Var ->Bool)->VarSet ->BoolanyVarSet =uniqSetAny allVarSet::(Var ->Bool)->VarSet ->BoolallVarSet =uniqSetAll mapVarSet::Uniquable b =>(a ->b )->UniqSet a ->UniqSet b mapVarSet =mapUniqSet fixVarSet::(VarSet ->VarSet )-- Map the current set to a new set->VarSet ->VarSet -- (fixVarSet f s) repeatedly applies f to the set s,-- until it reaches a fixed point.fixVarSet fn vars |new_vars `subVarSet `vars =vars |otherwise=fixVarSet fn new_vars wherenew_vars =fn vars transCloVarSet::(VarSet ->VarSet )-- Map some variables in the set to-- extra variables that should be in it->VarSet ->VarSet -- (transCloVarSet f s) repeatedly applies f to new candidates, adding any-- new variables to s that it finds thereby, until it reaches a fixed point.---- The function fn could be (Var -> VarSet), but we use (VarSet -> VarSet)-- for efficiency, so that the test can be batched up.-- It's essential that fn will work fine if given new candidates-- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2-- Use fixVarSet if the function needs to see the whole set all at oncetransCloVarSet fn seeds =go seeds seeds wherego::VarSet -- Accumulating result->VarSet -- Work-list; un-processed subset of accumulating result->VarSet -- Specification: go acc vs = acc `union` transClo fn vsgo acc candidates |isEmptyVarSet new_vs =acc |otherwise=go (acc `unionVarSet `new_vs )new_vs wherenew_vs =fn candidates `minusVarSet `acc seqVarSet::VarSet ->()seqVarSet s =sizeVarSet s `seq`()-- | Determines the pluralisation suffix appropriate for the length of a set-- in the same way that plural from Outputable does for lists.pluralVarSet::VarSet ->SDoc pluralVarSet =pluralUFM .getUniqSet -- | Pretty-print a non-deterministic set.-- The order of variables is non-deterministic and for pretty-printing that-- shouldn't be a problem.-- Having this function helps contain the non-determinism created with-- nonDetEltsUFM.-- Passing a list to the pretty-printing function allows the caller-- to decide on the order of Vars (eg. toposort them) without them having-- to use nonDetEltsUFM at the call site. This prevents from let-binding-- non-deterministically ordered lists and reusing them where determinism-- matters.pprVarSet::VarSet -- ^ The things to be pretty printed->([Var ]->SDoc )-- ^ The pretty printing function to use on the-- elements->SDoc -- ^ 'SDoc' where the things have been pretty-- printedpprVarSet =pprUFM .getUniqSet -- Deterministic VarSet-- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need-- DVarSet.-- | Deterministic Variable SettypeDVarSet =UniqDSet Var -- | Deterministic Identifier SettypeDIdSet =UniqDSet Id -- | Deterministic Type Variable SettypeDTyVarSet =UniqDSet TyVar -- | Deterministic Type or Coercion Variable SettypeDTyCoVarSet =UniqDSet TyCoVar emptyDVarSet::DVarSet emptyDVarSet =emptyUniqDSet unitDVarSet::Var ->DVarSet unitDVarSet =unitUniqDSet mkDVarSet::[Var ]->DVarSet mkDVarSet =mkUniqDSet -- The new element always goes to the right of existing ones.extendDVarSet::DVarSet ->Var ->DVarSet extendDVarSet =addOneToUniqDSet elemDVarSet::Var ->DVarSet ->BoolelemDVarSet =elementOfUniqDSet dVarSetElems::DVarSet ->[Var ]dVarSetElems =uniqDSetToList subDVarSet::DVarSet ->DVarSet ->BoolsubDVarSet s1 s2 =isEmptyDVarSet (s1 `minusDVarSet `s2 )unionDVarSet::DVarSet ->DVarSet ->DVarSet unionDVarSet =unionUniqDSets unionDVarSets::[DVarSet ]->DVarSet unionDVarSets =unionManyUniqDSets -- | Map the function over the list, and union the resultsmapUnionDVarSet::(a ->DVarSet )->[a ]->DVarSet mapUnionDVarSet get_set xs =foldr(unionDVarSet .get_set )emptyDVarSet xs intersectDVarSet::DVarSet ->DVarSet ->DVarSet intersectDVarSet =intersectUniqDSets dVarSetIntersectVarSet::DVarSet ->VarSet ->DVarSet dVarSetIntersectVarSet =uniqDSetIntersectUniqSet -- | True if empty intersectiondisjointDVarSet::DVarSet ->DVarSet ->BooldisjointDVarSet s1 s2 =disjointUDFM (getUniqDSet s1 )(getUniqDSet s2 )-- | True if non-empty intersectionintersectsDVarSet::DVarSet ->DVarSet ->BoolintersectsDVarSet s1 s2 =not(s1 `disjointDVarSet `s2 )isEmptyDVarSet::DVarSet ->BoolisEmptyDVarSet =isEmptyUniqDSet delDVarSet::DVarSet ->Var ->DVarSet delDVarSet =delOneFromUniqDSet minusDVarSet::DVarSet ->DVarSet ->DVarSet minusDVarSet =minusUniqDSet dVarSetMinusVarSet::DVarSet ->VarSet ->DVarSet dVarSetMinusVarSet =uniqDSetMinusUniqSet foldDVarSet::(Var ->a ->a )->a ->DVarSet ->a foldDVarSet =foldUniqDSet anyDVarSet::(Var ->Bool)->DVarSet ->BoolanyDVarSet p =anyUDFM p .getUniqDSet allDVarSet::(Var ->Bool)->DVarSet ->BoolallDVarSet p =allUDFM p .getUniqDSet mapDVarSet::Uniquable b =>(a ->b )->UniqDSet a ->UniqDSet b mapDVarSet =mapUniqDSet filterDVarSet::(Var ->Bool)->DVarSet ->DVarSet filterDVarSet =filterUniqDSet sizeDVarSet::DVarSet ->IntsizeDVarSet =sizeUniqDSet -- | Partition DVarSet according to the predicate givenpartitionDVarSet::(Var ->Bool)->DVarSet ->(DVarSet ,DVarSet )partitionDVarSet =partitionUniqDSet -- | Delete a list of variables from DVarSetdelDVarSetList::DVarSet ->[Var ]->DVarSet delDVarSetList =delListFromUniqDSet seqDVarSet::DVarSet ->()seqDVarSet s =sizeDVarSet s `seq`()-- | Add a list of variables to DVarSetextendDVarSetList::DVarSet ->[Var ]->DVarSet extendDVarSetList =addListToUniqDSet -- | Convert a DVarSet to a VarSet by forgeting the order of insertiondVarSetToVarSet::DVarSet ->VarSet dVarSetToVarSet =unsafeUFMToUniqSet .udfmToUfm .getUniqDSet -- | transCloVarSet for DVarSettransCloDVarSet::(DVarSet ->DVarSet )-- Map some variables in the set to-- extra variables that should be in it->DVarSet ->DVarSet -- (transCloDVarSet f s) repeatedly applies f to new candidates, adding any-- new variables to s that it finds thereby, until it reaches a fixed point.---- The function fn could be (Var -> DVarSet), but we use (DVarSet -> DVarSet)-- for efficiency, so that the test can be batched up.-- It's essential that fn will work fine if given new candidates-- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2transCloDVarSet fn seeds =go seeds seeds wherego::DVarSet -- Accumulating result->DVarSet -- Work-list; un-processed subset of accumulating result->DVarSet -- Specification: go acc vs = acc `union` transClo fn vsgo acc candidates |isEmptyDVarSet new_vs =acc |otherwise=go (acc `unionDVarSet `new_vs )new_vs wherenew_vs =fn candidates `minusDVarSet `acc