module Shake.ImportQuery where
import qualified Data.Aeson as Aeson
import qualified Data.List as List
import qualified Data.Map as Map
import qualified Data.Maybe as Maybe
import qualified Data.Set as Set
import qualified Data.Text as Text
import qualified Data.Tree as Tree
import qualified System.FilePath as FilePath
import qualified System.Process as Process
import qualified Util.Num as Num
import qualified Util.Seq as Seq
import qualified Shake.HsDeps as HsDeps
import Global
type Graph = Map Module [Module]
type Module = Text
data CachedGraph = CachedGraph {
CachedGraph -> Graph
_graph :: Graph
, CachedGraph -> Map Module (Set Module)
_closures :: Map Module (Set Module)
} deriving (Int -> CachedGraph -> ShowS
[CachedGraph] -> ShowS
CachedGraph -> FilePath
(Int -> CachedGraph -> ShowS)
-> (CachedGraph -> FilePath)
-> ([CachedGraph] -> ShowS)
-> Show CachedGraph
forall a.
(Int -> a -> ShowS) -> (a -> FilePath) -> ([a] -> ShowS) -> Show a
showList :: [CachedGraph] -> ShowS
$cshowList :: [CachedGraph] -> ShowS
show :: CachedGraph -> FilePath
$cshow :: CachedGraph -> FilePath
showsPrec :: Int -> CachedGraph -> ShowS
$cshowsPrec :: Int -> CachedGraph -> ShowS
Show)
cachedGraph :: Graph -> CachedGraph
cachedGraph :: Graph -> CachedGraph
cachedGraph Graph
g = CachedGraph
{ _graph :: Graph
_graph = Graph
g
, _closures :: Map Module (Set Module)
_closures = (Module -> [Module] -> Set Module)
-> Graph -> Map Module (Set Module)
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.mapWithKey (\Module
m [Module]
_ -> Graph -> Module -> Set Module
closure Graph
g Module
m) Graph
g
}
loadCachedGraph :: IO CachedGraph
loadCachedGraph :: IO CachedGraph
loadCachedGraph = Graph -> CachedGraph
cachedGraph (Graph -> CachedGraph) -> IO Graph -> IO CachedGraph
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> IO Graph
loadGraph
addDep :: Graph -> Module -> Module -> Either [[Module]] (Tree.Tree Module)
addDep :: Graph -> Module -> Module -> Either [[Module]] (Tree Module)
addDep Graph
graph Module
parent Module
new
| Module -> Set Module -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member Module
new Set Module
oldClosure = [[Module]] -> Either [[Module]] (Tree Module)
forall a b. a -> Either a b
Left ([[Module]] -> Either [[Module]] (Tree Module))
-> [[Module]] -> Either [[Module]] (Tree Module)
forall a b. (a -> b) -> a -> b
$ Graph -> Module -> Module -> [[Module]]
paths Graph
graph Module
parent Module
new
| Bool
otherwise = Tree Module -> Either [[Module]] (Tree Module)
forall a b. b -> Either a b
Right (Tree Module -> Either [[Module]] (Tree Module))
-> Tree Module -> Either [[Module]] (Tree Module)
forall a b. (a -> b) -> a -> b
$ Set Module -> Tree Module -> Tree Module
trimTree Set Module
oldClosure (Tree Module -> Tree Module) -> Tree Module -> Tree Module
forall a b. (a -> b) -> a -> b
$ Graph -> Module -> Tree Module
closureTree Graph
graph Module
new
where oldClosure :: Set Module
oldClosure = Graph -> Module -> Set Module
closure Graph
graph Module
parent
rmDep :: CachedGraph -> Module -> Module -> [(Module, Set Module)]
rmDep :: CachedGraph -> Module -> Module -> [(Module, Set Module)]
rmDep CachedGraph
graph Module
parent Module
removed =
((Module, Set Module) -> Bool)
-> [(Module, Set Module)] -> [(Module, Set Module)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Set Module -> Set Module -> Bool
forall a. Eq a => a -> a -> Bool
/= Set Module
forall a. Monoid a => a
mempty) (Set Module -> Bool)
-> ((Module, Set Module) -> Set Module)
-> (Module, Set Module)
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Module, Set Module) -> Set Module
forall a b. (a, b) -> b
snd) ([(Module, Set Module)] -> [(Module, Set Module)])
-> ([Module] -> [(Module, Set Module)])
-> [Module]
-> [(Module, Set Module)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Module -> Set Module) -> [Module] -> [(Module, Set Module)]
forall a k. (a -> k) -> [a] -> [(a, k)]
Seq.key_on_snd Module -> Set Module
gone ([Module] -> [(Module, Set Module)])
-> [Module] -> [(Module, Set Module)]
forall a b. (a -> b) -> a -> b
$ Graph -> [Module]
forall k a. Map k a -> [k]
Map.keys (CachedGraph -> Graph
_graph CachedGraph
graph)
where
gone :: Module -> Set Module
gone Module
mod = Module -> Map Module (Set Module) -> Set Module
forall k a. (Ord k, Monoid a) => k -> Map k a -> a
get Module
mod (CachedGraph -> Map Module (Set Module)
_closures CachedGraph
graph) Set Module -> Set Module -> Set Module
forall a. Ord a => Set a -> Set a -> Set a
`Set.difference` Graph -> Module -> Set Module
closure Graph
without Module
mod
without :: Graph
without = ([Module] -> [Module]) -> Module -> Graph -> Graph
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
Map.adjust ((Module -> Bool) -> [Module] -> [Module]
forall a. (a -> Bool) -> [a] -> [a]
filter (Module -> Module -> Bool
forall a. Eq a => a -> a -> Bool
/=Module
removed)) Module
parent (CachedGraph -> Graph
_graph CachedGraph
graph)
findWeakLinks :: CachedGraph -> [(Int, ((Text, Text), [(Module, Set Module)]))]
findWeakLinks :: CachedGraph -> [(Int, ((Module, Module), [(Module, Set Module)]))]
findWeakLinks CachedGraph
graph = (Module -> [(Int, ((Module, Module), [(Module, Set Module)]))])
-> [Module] -> [(Int, ((Module, Module), [(Module, Set Module)]))]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Module -> [(Int, ((Module, Module), [(Module, Set Module)]))]
get ([Module] -> [(Int, ((Module, Module), [(Module, Set Module)]))])
-> [Module] -> [(Int, ((Module, Module), [(Module, Set Module)]))]
forall a b. (a -> b) -> a -> b
$ (Module -> Bool) -> [Module] -> [Module]
forall a. (a -> Bool) -> [a] -> [a]
filter Module -> Bool
wanted ([Module] -> [Module]) -> [Module] -> [Module]
forall a b. (a -> b) -> a -> b
$ Graph -> [Module]
forall k a. Map k a -> [k]
Map.keys (CachedGraph -> Graph
_graph CachedGraph
graph)
where
get :: Module -> [(Int, ((Module, Module), [(Module, Set Module)]))]
get Module
parent = (Module -> (Int, ((Module, Module), [(Module, Set Module)])))
-> [Module] -> [(Int, ((Module, Module), [(Module, Set Module)]))]
forall a b. (a -> b) -> [a] -> [b]
map (Module
-> Module -> (Int, ((Module, Module), [(Module, Set Module)]))
get1 Module
parent) (Module -> Graph -> [Module]
importsOf Module
parent (CachedGraph -> Graph
_graph CachedGraph
graph))
get1 :: Module
-> Module -> (Int, ((Module, Module), [(Module, Set Module)]))
get1 Module
parent Module
removed = ([(Module, Set Module)] -> Int
forall {a} {a}. [(a, Set a)] -> Int
scoreOf [(Module, Set Module)]
rms, ((Module
parent, Module
removed), [(Module, Set Module)]
rms))
where rms :: [(Module, Set Module)]
rms = CachedGraph -> Module -> Module -> [(Module, Set Module)]
rmDep CachedGraph
graph Module
parent Module
removed
scoreOf :: [(a, Set a)] -> Int
scoreOf = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
Num.sum ([Int] -> Int) -> ([(a, Set a)] -> [Int]) -> [(a, Set a)] -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, Set a) -> Int) -> [(a, Set a)] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Set a -> Int
forall a. Set a -> Int
Set.size (Set a -> Int) -> ((a, Set a) -> Set a) -> (a, Set a) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, Set a) -> Set a
forall a b. (a, b) -> b
snd)
wanted :: Module -> Bool
wanted Module
mod = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (Module -> Bool) -> [Module] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Module -> Module -> Bool
`Text.isSuffixOf` Module
mod) [Module
"_test", Module
"_profile"]
paths :: Graph -> Module -> Module -> [[Module]]
paths :: Graph -> Module -> Module -> [[Module]]
paths Graph
graph Module
from Module
to
| Module
from Module -> Module -> Bool
forall a. Eq a => a -> a -> Bool
== Module
to = [[Module
to]]
| Bool
otherwise = case Module -> Graph -> Maybe [Module]
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Module
from Graph
graph of
Maybe [Module]
Nothing -> []
Just [Module]
mods -> [Module
fromModule -> [Module] -> [Module]
forall a. a -> [a] -> [a]
:[Module]
path | Module
m <- [Module]
mods, [Module]
path <- Graph -> Module -> Module -> [[Module]]
paths Graph
graph Module
m Module
to]
closureTree :: Graph -> Module -> Tree.Tree Module
closureTree :: Graph -> Module -> Tree Module
closureTree Graph
graph Module
mod =
Module -> [Tree Module] -> Tree Module
forall a. a -> [Tree a] -> Tree a
Tree.Node Module
mod ((Module -> Tree Module) -> [Module] -> [Tree Module]
forall a b. (a -> b) -> [a] -> [b]
map (Graph -> Module -> Tree Module
closureTree Graph
graph) (Module -> Graph -> [Module]
importsOf Module
mod Graph
graph))
trimTree :: Set Module -> Tree.Tree Module -> Tree.Tree Module
trimTree :: Set Module -> Tree Module -> Tree Module
trimTree Set Module
seen = (Set Module, Tree Module) -> Tree Module
forall a b. (a, b) -> b
snd ((Set Module, Tree Module) -> Tree Module)
-> (Tree Module -> (Set Module, Tree Module))
-> Tree Module
-> Tree Module
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set Module -> Tree Module -> (Set Module, Tree Module)
forall {a}.
(Ord a, Semigroup a, IsString a) =>
Set a -> Tree a -> (Set a, Tree a)
go Set Module
seen
where
go :: Set a -> Tree a -> (Set a, Tree a)
go Set a
seen (Tree.Node a
mod [Tree a]
subs)
| a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
mod Set a
seen = (Set a
seen, a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Tree.Node (a
mod a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
"*") [])
| Bool
otherwise = a -> [Tree a] -> Tree a
forall a. a -> [Tree a] -> Tree a
Tree.Node a
mod ([Tree a] -> Tree a) -> (Set a, [Tree a]) -> (Set a, Tree a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
(Set a -> Tree a -> (Set a, Tree a))
-> Set a -> [Tree a] -> (Set a, [Tree a])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
List.mapAccumL Set a -> Tree a -> (Set a, Tree a)
go (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
mod Set a
seen) [Tree a]
subs
closureList :: Graph -> Module -> [Module]
closureList :: Graph -> Module -> [Module]
closureList Graph
graph = Tree Module -> [Module]
forall a. Tree a -> [a]
Tree.flatten (Tree Module -> [Module])
-> (Module -> Tree Module) -> Module -> [Module]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph -> Module -> Tree Module
closureTree Graph
graph
closure :: Graph -> Module -> Set Module
closure :: Graph -> Module -> Set Module
closure Graph
graph = Set Module -> Module -> Set Module
go Set Module
forall a. Set a
Set.empty
where
go :: Set Module -> Module -> Set Module
go Set Module
seen Module
mod
| Module
mod Module -> Set Module -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set Module
seen = Set Module
seen
| Bool
otherwise = (Set Module -> Module -> Set Module)
-> Set Module -> [Module] -> Set Module
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' Set Module -> Module -> Set Module
go (Module -> Set Module -> Set Module
forall a. Ord a => a -> Set a -> Set a
Set.insert Module
mod Set Module
seen) (Module -> Graph -> [Module]
importsOf Module
mod Graph
graph)
importsOf :: Module -> Graph -> [Module]
importsOf :: Module -> Graph -> [Module]
importsOf = Module -> Graph -> [Module]
forall k a. (Ord k, Monoid a) => k -> Map k a -> a
get
get :: (Ord k, Monoid a) => k -> Map k a -> a
get :: forall k a. (Ord k, Monoid a) => k -> Map k a -> a
get = a -> k -> Map k a -> a
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault a
forall a. Monoid a => a
mempty
cacheGraph :: IO ()
cacheGraph :: IO ()
cacheGraph = FilePath -> Graph -> IO ()
forall a. ToJSON a => FilePath -> a -> IO ()
Aeson.encodeFile FilePath
cacheFile (Graph -> IO ()) -> IO Graph -> IO ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IO Graph
generateGraph
loadGraph :: IO Graph
loadGraph :: IO Graph
loadGraph = Graph -> Maybe Graph -> Graph
forall a. a -> Maybe a -> a
fromMaybe (FilePath -> Graph
forall a. HasCallStack => FilePath -> a
error FilePath
"no parse") (Maybe Graph -> Graph) -> IO (Maybe Graph) -> IO Graph
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> FilePath -> IO (Maybe Graph)
forall a. FromJSON a => FilePath -> IO (Maybe a)
Aeson.decodeFileStrict' FilePath
cacheFile
cacheFile :: FilePath
cacheFile :: FilePath
cacheFile = FilePath
"build/imports.json"
generateGraph :: IO Graph
generateGraph :: IO Graph
generateGraph =
((Set FilePath, [Maybe (FilePath, [FilePath])]) -> Graph)
-> IO (Set FilePath, [Maybe (FilePath, [FilePath])]) -> IO Graph
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([(Module, [Module])] -> Graph
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(Module, [Module])] -> Graph)
-> ((Set FilePath, [Maybe (FilePath, [FilePath])])
-> [(Module, [Module])])
-> (Set FilePath, [Maybe (FilePath, [FilePath])])
-> Graph
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((FilePath, [FilePath]) -> (Module, [Module]))
-> [(FilePath, [FilePath])] -> [(Module, [Module])]
forall a b. (a -> b) -> [a] -> [b]
map ((FilePath -> Module)
-> ([FilePath] -> [Module])
-> (FilePath, [FilePath])
-> (Module, [Module])
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap FilePath -> Module
fileToModule ((FilePath -> Module) -> [FilePath] -> [Module]
forall a b. (a -> b) -> [a] -> [b]
map FilePath -> Module
fileToModule))
([(FilePath, [FilePath])] -> [(Module, [Module])])
-> ((Set FilePath, [Maybe (FilePath, [FilePath])])
-> [(FilePath, [FilePath])])
-> (Set FilePath, [Maybe (FilePath, [FilePath])])
-> [(Module, [Module])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Maybe (FilePath, [FilePath])] -> [(FilePath, [FilePath])]
forall a. [Maybe a] -> [a]
Maybe.catMaybes ([Maybe (FilePath, [FilePath])] -> [(FilePath, [FilePath])])
-> ((Set FilePath, [Maybe (FilePath, [FilePath])])
-> [Maybe (FilePath, [FilePath])])
-> (Set FilePath, [Maybe (FilePath, [FilePath])])
-> [(FilePath, [FilePath])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Set FilePath, [Maybe (FilePath, [FilePath])])
-> [Maybe (FilePath, [FilePath])]
forall a b. (a, b) -> b
snd) (IO (Set FilePath, [Maybe (FilePath, [FilePath])]) -> IO Graph)
-> IO (Set FilePath, [Maybe (FilePath, [FilePath])]) -> IO Graph
forall a b. (a -> b) -> a -> b
$
(Set FilePath
-> FilePath -> IO (Set FilePath, Maybe (FilePath, [FilePath])))
-> Set FilePath
-> [FilePath]
-> IO (Set FilePath, [Maybe (FilePath, [FilePath])])
forall (m :: * -> *) state x y.
Monad m =>
(state -> x -> m (state, y)) -> state -> [x] -> m (state, [y])
Seq.mapAccumLM Set FilePath
-> FilePath -> IO (Set FilePath, Maybe (FilePath, [FilePath]))
get Set FilePath
forall a. Set a
Set.empty ([FilePath] -> IO (Set FilePath, [Maybe (FilePath, [FilePath])]))
-> IO [FilePath]
-> IO (Set FilePath, [Maybe (FilePath, [FilePath])])
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IO [FilePath]
getAllHs
where
get :: Set FilePath
-> FilePath -> IO (Set FilePath, Maybe (FilePath, [FilePath]))
get Set FilePath
seen FilePath
fname
| FilePath -> Set FilePath -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member FilePath
fname Set FilePath
seen = (Set FilePath, Maybe (FilePath, [FilePath]))
-> IO (Set FilePath, Maybe (FilePath, [FilePath]))
forall (m :: * -> *) a. Monad m => a -> m a
return (Set FilePath
seen, Maybe (FilePath, [FilePath])
forall a. Maybe a
Nothing)
| Bool
otherwise = do
[FilePath]
deps <- Generated -> Maybe [FilePath] -> FilePath -> IO [FilePath]
HsDeps.importsOfIO Generated
generatedSrc (FilePath -> Maybe [FilePath]
cppFlags FilePath
fname) FilePath
fname
(Set FilePath, Maybe (FilePath, [FilePath]))
-> IO (Set FilePath, Maybe (FilePath, [FilePath]))
forall (m :: * -> *) a. Monad m => a -> m a
return (FilePath -> Set FilePath -> Set FilePath
forall a. Ord a => a -> Set a -> Set a
Set.insert FilePath
fname Set FilePath
seen, (FilePath, [FilePath]) -> Maybe (FilePath, [FilePath])
forall a. a -> Maybe a
Just (FilePath
fname, [FilePath]
deps))
getAllHs :: IO [FilePath]
getAllHs :: IO [FilePath]
getAllHs =
(FilePath -> Bool) -> [FilePath] -> [FilePath]
forall a. (a -> Bool) -> [a] -> [a]
filter FilePath -> Bool
isHs ([FilePath] -> [FilePath])
-> (FilePath -> [FilePath]) -> FilePath -> [FilePath]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FilePath -> [FilePath]
lines (FilePath -> [FilePath]) -> IO FilePath -> IO [FilePath]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
FilePath -> [FilePath] -> FilePath -> IO FilePath
Process.readProcess FilePath
"git" [FilePath
"ls-tree", FilePath
"--name-only", FilePath
"-r", FilePath
"HEAD"] FilePath
""
where isHs :: FilePath -> Bool
isHs FilePath
fn = (FilePath -> Bool) -> [FilePath] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (FilePath -> FilePath -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`List.isSuffixOf` FilePath
fn) [FilePath
".hs", FilePath
".hsc", FilePath
".chs"]
generatedSrc :: HsDeps.Generated
generatedSrc :: Generated
generatedSrc = HsDeps.Generated
{ _generatedHs :: Set FilePath
_generatedHs = [FilePath] -> Set FilePath
forall a. Ord a => [a] -> Set a
Set.fromList [FilePath
"Solkattu/All.hs"]
, _generatedExtensions :: [FilePath]
_generatedExtensions = [FilePath
".hsc", FilePath
".chs"]
}
cppFlags :: FilePath -> Maybe [String]
cppFlags :: FilePath -> Maybe [FilePath]
cppFlags FilePath
fn
| FilePath
fn FilePath -> Set FilePath -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set FilePath
cppInImports = [FilePath] -> Maybe [FilePath]
forall a. a -> Maybe a
Just
[ FilePath
"-Ibuild/debug"
, FilePath
"-DTESTING"
, FilePath
"-DBUILD_DIR=\"\""
, FilePath
"-DGHC_VERSION=90001"
]
| Bool
otherwise = Maybe [FilePath]
forall a. Maybe a
Nothing
fileToModule :: FilePath -> Module
fileToModule :: FilePath -> Module
fileToModule = FilePath -> Module
txt (FilePath -> Module) -> ShowS -> FilePath -> Module
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Char -> Char) -> ShowS
forall a b. (a -> b) -> [a] -> [b]
map Char -> Char
replace ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
FilePath.dropExtensions
where
replace :: Char -> Char
replace Char
'/' = Char
'.'
replace Char
c = Char
c
cppInImports :: Set.Set FilePath
cppInImports :: Set FilePath
cppInImports = [FilePath] -> Set FilePath
forall a. Ord a => [a] -> Set a
Set.fromList
[ FilePath
"App/Main.hs"
, FilePath
"Cmd/Repl.hs"
, FilePath
"Midi/MidiDriver.hs"
, FilePath
"App/LoadInstruments.hs"
]