summaryrefslogtreecommitdiff
path: root/compiler/utils/Digraph.hs
Commit message (Collapse)AuthorAgeFilesLines
* Add Outputable instance for NodeMatthew Pickering2017-05-111-0/+3
| | | | | | | | | | Reviewers: austin, bgamari Reviewed By: bgamari Subscribers: rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3564
* Replace Digraph's Node type synonym with a data typeMatthew Pickering2017-04-041-14/+16
| | | | | | | | | | | | | This refactoring makes it more obvious when we are constructing a Node for the digraph rather than a less useful 3-tuple. Reviewers: austin, goldfire, bgamari, simonmar, dfeuer Reviewed By: dfeuer Subscribers: rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3414
* Typos in comments (and in a test)Gabor Greif2017-01-091-3/+3
|
* Typos in comments only [ci skip]Gabor Greif2016-11-281-3/+3
|
* Provide Uniquable version of SCCBartosz Nitka2016-06-231-22/+105
| | | | | | | | | | | | | | | | | | | | | | | | | | | We want to remove the `Ord Unique` instance because there's no way to implement it in deterministic way and it's too easy to use by accident. We sometimes compute SCC for datatypes whose Ord instance is implemented in terms of Unique. The Ord constraint on SCC is just an artifact of some internal data structures. We can have an alternative implementation with a data structure that uses Uniquable instead. This does exactly that and I'm pleased that I didn't have to introduce any duplication to do that. Test Plan: ./validate I looked at performance tests and it's a tiny bit better. Reviewers: bgamari, simonmar, ezyang, austin, goldfire Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2359 GHC Trac Issues: #4012
* Document SCC determinismBartosz Nitka2016-05-111-0/+15
| | | | | | | | | | | | | | | | | | | | | | I've documented the guarantees that stronglyConnCompFromEdgedVertices provides and commented on the call sites to explain why they are OK from determinism standpoint. I've changed the functions to nonDetUFM versions, so that it's explicit they could introduce nondeterminism. I haven't defined container (VarSet, NameSet) specific versions, so that we have less functions to worry about. Test Plan: this is mostly just documentation, it should have no runtime effect Reviewers: bgamari, simonmar, austin, simonpj Reviewed By: simonpj Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2194 GHC Trac Issues: #4012
* Remove orphan Functor instance of Data.Graph.SCCÖmer Sinan Ağacan2015-11-171-10/+1
| | | | | | | | | | Reviewers: bgamari, austin Reviewed By: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1481
* Make stronglyConnCompFromEdgedVertices deterministicBartosz Nitka2015-10-221-18/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This makes it so the result of computing SCC's depends on the order the nodes were passed to it, but not on the order on the user provided key type. The key type is usually `Unique` which is known to be nondeterministic. Test Plan: `text` and `aeson` become deterministic after this ./validate Compare compile time for `text`: ``` $ cabal get text && cd text* && cabal sandbox init && cabal install --dependencies-only && time cabal build real 0m59.459s user 0m57.862s sys 0m1.185s $ cabal clean && time cabal build real 1m0.037s user 0m58.350s sys 0m1.199s $ cabal clean && time cabal build real 0m57.634s user 0m56.118s sys 0m1.202s $ cabal get text && cd text* && cabal sandbox init && cabal install --dependencies-only && time cabal build real 0m59.867s user 0m58.176s sys 0m1.188s $ cabal clean && time cabal build real 1m0.157s user 0m58.622s sys 0m1.177s $ cabal clean && time cabal build real 1m0.950s user 0m59.397s sys 0m1.083s ``` Reviewers: ezyang, simonmar, austin, bgamari Reviewed By: simonmar, bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1268 GHC Trac Issues: #4012
* Remove graphFromVerticesAndAdjacencyBartosz Nitka2015-09-211-19/+1
| | | | | | | | It's not used anywhere. Reviewed By: austin Differential Revision: https://phabricator.haskell.org/D1266
* Refactor Digraph to use Data.Graph when possibleEdward Z. Yang2015-03-091-263/+45
| | | | | | | | | | | | | | Summary: This just rewrites the IntGraph data type. Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D708
* Revert "Refactor Digraph to use Data.Graph when possible"Edward Z. Yang2015-03-091-36/+264
| | | | | | | This breaks the build with GHC 7.6 bootstrapping, since the Functor SCC instance is not available. This reverts commit c439af5f5baa2c8af3434652554135230edbf5c3.
* Refactor Digraph to use Data.Graph when possibleEdward Z. Yang2015-03-091-264/+36
| | | | | | | | | | | | | | Summary: This just rewrites the IntGraph data type. Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D708
* compiler: de-lhs utils/Austin Seipp2014-12-031-0/+652
Signed-off-by: Austin Seipp <austin@well-typed.com>
View Lorry Controller Status