summaryrefslogtreecommitdiff
path: root/compiler/utils/UniqDFM.hs
Commit message (Collapse)AuthorAgeFilesLines
* Modules: Types (#13009)Sylvain Henry2020-03-291-420/+0
| | | | | | | Update Haddock submodule Metric Increase: haddock.compiler
* Fix typos, using Wikipedia list of common typosBrian Wignall2019-11-281-1/+1
|
* Add Foldable, Traversable instances for Uniq(D)FMSebastian Graf2019-08-131-0/+11
| | | | | The `UniqDFM` is deterministic, of course, while we provide an unsafe `NonDetUniqFM` wrapper for `UniqFM` to opt into nondeterministic instances.
* Use DeriveFunctor throughout the codebase (#15654)Krzysztof Gogolewski2019-06-121-4/+1
|
* Make `UniqDSet` a newtypeSebastian Graf2018-11-131-1/+7
| | | | | | | | | | | | | | | | | | | | Summary: This brings the situation of `UniqDSet` in line with `UniqSet`. @dfeuer said in D3146#92820 that he would do this, but probably never got around to it. Validated locally. Reviewers: AndreasK, mpickering, bgamari, dfeuer, simonpj Reviewed By: simonpj Subscribers: simonpj, rwbarton, carter, dfeuer GHC Trac Issues: #15879, #13114 Differential Revision: https://phabricator.haskell.org/D5313
* Finish fix for #14880.Tobias Dammers2018-10-281-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The real change that fixes the ticket is described in Note [Naughty quantification candidates] in TcMType. Fixing this required reworking candidateQTyVarsOfType, the function that extracts free variables as candidates for quantification. One consequence is that we now must be more careful when quantifying: any skolems around must be quantified manually, and quantifyTyVars will now only quantify over metavariables. This makes good sense, as skolems are generally user-written and are listed in the AST. As a bonus, we now have more control over the ordering of such skolems. Along the way, this commit fixes #15711 and refines the fix to #14552 (by accepted a program that was previously rejected, as we can now accept that program by zapping variables to Any). This commit also does a fair amount of rejiggering kind inference of datatypes. Notably, we now can skip the generalization step in kcTyClGroup for types with CUSKs, because we get the kind right the first time. This commit also thus fixes #15743 and #15592, which both concern datatype kind generalisation. (#15591 is also very relevant.) For this aspect of the commit, see Note [Required, Specified, and Inferred in types] in TcTyClsDecls. Test cases: dependent/should_fail/T14880{,-2}, dependent/should_fail/T15743[cd] dependent/should_compile/T15743{,e} ghci/scripts/T15743b polykinds/T15592 dependent/should_fail/T15591[bc] ghci/scripts/T15591
* Replace most occurences of foldl with foldl'.klebinger.andreas@gmx.at2018-08-211-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch adds foldl' to GhcPrelude and changes must occurences of foldl to foldl'. This leads to better performance especially for quick builds where GHC does not perform strictness analysis. It does change strictness behaviour when we use foldl' to turn a argument list into function applications. But this is only a drawback if code looks ONLY at the last argument but not at the first. And as the benchmarks show leads to fewer allocations in practice at O2. Compiler performance for Nofib: O2 Allocations: -1 s.d. ----- -0.0% +1 s.d. ----- -0.0% Average ----- -0.0% O2 Compile Time: -1 s.d. ----- -2.8% +1 s.d. ----- +1.3% Average ----- -0.8% O0 Allocations: -1 s.d. ----- -0.2% +1 s.d. ----- -0.1% Average ----- -0.2% Test Plan: ci Reviewers: goldfire, bgamari, simonmar, tdammers, monoidal Reviewed By: bgamari, monoidal Subscribers: tdammers, rwbarton, thomie, carter Differential Revision: https://phabricator.haskell.org/D4929
* compiler: introduce custom "GhcPrelude" PreludeHerbert Valerio Riedel2017-09-191-0/+2
| | | | | | | | | | | | | | | | | | This switches the compiler/ component to get compiled with -XNoImplicitPrelude and a `import GhcPrelude` is inserted in all modules. This is motivated by the upcoming "Prelude" re-export of `Semigroup((<>))` which would cause lots of name clashes in every modulewhich imports also `Outputable` Reviewers: austin, goldfire, bgamari, alanz, simonmar Reviewed By: bgamari Subscribers: goldfire, rwbarton, thomie, mpickering, bgamari Differential Revision: https://phabricator.haskell.org/D3989
* Add missing Semigroup instances to compilerHerbert Valerio Riedel2017-08-311-1/+5
| | | | | This is a pre-requisite for implementing the Semigroup/Monoid proposal. The instances have been introduced in a way to minimise warnings.
* Use intersect and minus instead of filterBartosz Nitka2017-04-171-1/+1
| | | | | | | | | | | | | | | These are asymptotically better and convey the intent a bit better. Test Plan: ./validate Reviewers: simonpj, bgamari, austin, goldfire Reviewed By: bgamari Subscribers: rwbarton, thomie, simonmar Differential Revision: https://phabricator.haskell.org/D3455
* Fix TcSimplify.decideQuantification for kind variablesSimon Peyton Jones2017-03-101-18/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | TcSimplify.decideQuantification was doing the Wrong Thing when "growing" the type variables to quantify over. We were trying to do this on a tyvar set where we'd split off the dependent type varaibles; and we just got it wrong. A kind variable wasn't being generalised properly, with confusing knock on consequences. All this led to Trac #13371 and Trac #13393. This commit tidies it all up: * The type TcDepVars is renamed as CandidateQTvs; and splitDepVarsOfType to candidateQTyVarsOfType * The code in TcSimplify.decideQuantification is simpler. It no longer does the tricky "grow" stuff over TcDepVars. Instead it use ordinary VarSets (thereby eliminating the nasty growThetaTyVarsDSet) and uses that to filter the result of candidateQTyVarsOfType. * I documented that candidateQTyVarsOfType returns the type variables in a good order in which to quantify, and rewrote it to use an accumulator pattern, so that we would predicatably get left-to-right ordering. In doing all this I also made UniqDFM behave a little more nicely: * When inserting an element that is there already, keep the old tag, while still overwriting with the new value. * This means that when doing udfmToList we get back elements in the order they were originally inserted, rather than in reverse order. It's not a big deal, but in a subsequent commit I use it to improve the order of type variables in inferred types. All this led to a lot of error message wibbles: - changing the order of quantified variables - changing the order in which instances are listed in GHCi - changing the tidying of variables in typechecker erors There's a submodule update for 'array' because one of its tests has an error-message change. I may not have associated all of them with the correct commit.
* Fix deprecation warnings from containersErik de Castro Lopo2017-01-301-2/+2
| | | | | | | | | | | | | | | The functions that were causing warnings were deprecated in containers 0.5 and GHC is already using containers 0.5.9.1. Test Plan: validate Reviewers: rwbarton, bgamari, hsyl20, austin, dfeuer Reviewed By: dfeuer Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D3036
* Remove ufmToListBartosz Nitka2016-06-301-2/+2
| | | | | | | This documents nondeterminism in code generation and removes the nondeterministic ufmToList function. In the future someone will have to use nonDetUFMToList (with proper explanation) or pprUFMWithKeys.
* Make UnitIdMap a deterministic mapBartosz Nitka2016-06-061-1/+6
| | | | | | | | | | | | | | | | | | | This impacts at least the order in which version macros are generated. It's pretty hard to track what kind of nondeterminism is benign and this should have no performance impact as the number of packages should be relatively small. Test Plan: ./validate Reviewers: simonmar, austin, bgamari, ezyang Reviewed By: ezyang Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2308 GHC Trac Issues: #4012
* Use UniqDFM for HomePackageTableBartosz Nitka2016-06-061-2/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This isn't strictly necessary for deterministic ABIs. The results of eltsHpt are consumed in two ways: 1) they determine the order of linking 2) if you track the data flow all the family instances get put in FamInstEnvs, so the nondeterministic order is forgotten. 3) same for VectInfo stuff 4) same for Annotations The problem is that I haven't found a nice way to do 2. in a local way and 1. is nice to have if we went for deterministic object files. Besides these maps are keyed on ModuleNames so they should be small relative to other things and the overhead should be negligible. As a bonus we also get more specific names. Test Plan: ./validate Reviewers: bgamari, austin, hvr, ezyang, simonmar Reviewed By: simonmar Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2300 GHC Trac Issues: #4012
* Make FieldLabelEnv a deterministic setBartosz Nitka2016-06-031-0/+4
| | | | | | | | | | | | | | | | | | This lets us kill fsEnvElts function which is nondeterministic. We also get better guarantees than just comments. We don't do lookups, but I believe a set is needed for deduplication. Test Plan: ./validate Reviewers: bgamari, mpickering, austin, simonmar Reviewed By: simonmar Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2297 GHC Trac Issues: #4012
* Remove 'deriving Typeable' statementsRyan Scott2016-05-241-3/+2
| | | | | | | | | | | | | | | | | Summary: Deriving `Typeable` has been a no-op since GHC 7.10, and now that we require 7.10+ to build GHC, we can remove all the redundant `deriving Typeable` statements in GHC. Test Plan: ./validate Reviewers: goldfire, austin, hvr, bgamari Reviewed By: austin, hvr, bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2260
* Make Arrow desugaring deterministicBartosz Nitka2016-05-241-1/+6
| | | | | | | | | | | | | | | | | | | This kills two instances of varSetElems that turned out to be nondeterministic. I've tried to untangle this before, but it's a bit hard with the fixDs in the middle. Fortunately I now have a test case that proves that we need determinism here. Test Plan: ./validate, new testcase Reviewers: simonpj, simonmar, austin, bgamari Reviewed By: bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2258 GHC Trac Issues: #4012
* Make inert_model and inert_eqs deterministic setsBartosz Nitka2016-05-181-1/+21
| | | | | | | | | | | | | | | | | | | | The order inert_model and intert_eqs fold affects the order that the typechecker looks at things. I've been able to experimentally confirm that the order of equalities and the order of the model matter for determinism. This is just a straigthforward replacement of nondeterministic VarEnv for deterministic DVarEnv. Test Plan: ./validate Reviewers: simonpj, goldfire, austin, bgamari, simonmar Reviewed By: simonmar Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2232 GHC Trac Issues: #4012
* Kill varEnvElts in specImportsBartosz Nitka2016-05-121-0/+32
| | | | | | | | | | | | | | | | | We need the order of specialized binds and rules to be deterministic, so we use a deterministic set here. Test Plan: ./validate Reviewers: simonmar, bgamari, austin, simonpj Reviewed By: simonpj Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2197 GHC Trac Issues: #4012
* Kill varSetElemsWellScoped in quantifyTyVarsBartosz Nitka2016-04-261-1/+11
| | | | | | | | | | | | | | | | | | | | | | | | varSetElemsWellScoped introduces unnecessary non-determinism in inferred type signatures. Removing this instance required changing the representation of TcDepVars to use deterministic sets. This is the last occurence of varSetElemsWellScoped, allowing me to finally remove it. Test Plan: ./validate I will update the expected outputs when commiting, some reordering of type variables in types is expected. Reviewers: goldfire, simonpj, austin, bgamari Reviewed By: simonpj Subscribers: thomie, simonmar Differential Revision: https://phabricator.haskell.org/D2135 GHC Trac Issues: #4012
* Replace calls to `ptext . sLit` with `text`Jan Stolarek2016-01-181-2/+1
| | | | | | | | | | | | | | | | | | | | Summary: In the past the canonical way for constructing an SDoc string literal was the composition `ptext . sLit`. But for some time now we have function `text` that does the same. Plus it has some rules that optimize its runtime behaviour. This patch takes all uses of `ptext . sLit` in the compiler and replaces them with calls to `text`. The main benefits of this patch are clener (shorter) code and less dependencies between module, because many modules now do not need to import `FastString`. I don't expect any performance benefits - we mostly use SDocs to report errors and it seems there is little to be gained here. Test Plan: ./validate Reviewers: bgamari, austin, goldfire, hvr, alanz Subscribers: goldfire, thomie, mpickering Differential Revision: https://phabricator.haskell.org/D1784
* Add kind equalities to GHC.Richard Eisenberg2015-12-111-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This implements the ideas originally put forward in "System FC with Explicit Kind Equality" (ICFP'13). There are several noteworthy changes with this patch: * We now have casts in types. These change the kind of a type. See new constructor `CastTy`. * All types and all constructors can be promoted. This includes GADT constructors. GADT pattern matches take place in type family equations. In Core, types can now be applied to coercions via the `CoercionTy` constructor. * Coercions can now be heterogeneous, relating types of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2` proves both that `t1` and `t2` are the same and also that `k1` and `k2` are the same. * The `Coercion` type has been significantly enhanced. The documentation in `docs/core-spec/core-spec.pdf` reflects the new reality. * The type of `*` is now `*`. No more `BOX`. * Users can write explicit kind variables in their code, anywhere they can write type variables. For backward compatibility, automatic inference of kind-variable binding is still permitted. * The new extension `TypeInType` turns on the new user-facing features. * Type families and synonyms are now promoted to kinds. This causes trouble with parsing `*`, leading to the somewhat awkward new `HsAppsTy` constructor for `HsType`. This is dispatched with in the renamer, where the kind `*` can be told apart from a type-level multiplication operator. Without `-XTypeInType` the old behavior persists. With `-XTypeInType`, you need to import `Data.Kind` to get `*`, also known as `Type`. * The kind-checking algorithms in TcHsType have been significantly rewritten to allow for enhanced kinds. * The new features are still quite experimental and may be in flux. * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203. * TODO: Update user manual. Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142. Updates Haddock submodule.
* Implement more deterministic operations and document themBartosz Nitka2015-12-021-0/+45
| | | | | | | | | | | | | | | | I will need them for the future determinism fixes. Test Plan: ./validate Reviewers: simonpj, goldfire, bgamari, austin, hvr, simonmar Reviewed By: simonpj, simonmar Subscribers: osa1, thomie Differential Revision: https://phabricator.haskell.org/D1537 GHC Trac Issues: #4012
* Add DVarSet - a deterministic set of VarsBartosz Nitka2015-11-211-8/+142
| | | | | | | | | | | | | | | | | | | | | | | This implements `DVarSet`, a deterministic set of Vars, with an interface very similar to `VarSet` with a couple of functions missing. I will need this in changes that follow, one of them will be about changing the type of the set of Vars that `RuleInfo` holds to make the free variable computation deterministic. Test Plan: ./validate I can add new tests if anyone wants me to. Reviewers: simonpj, simonmar, austin, bgamari Reviewed By: simonmar, bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1487 GHC Trac Issues: #4012
* Make type-class dictionary let binds deterministicBartosz Nitka2015-10-301-0/+118
When generating dictionary let binds in dsTcEvBinds we may end up generating them in arbitrary order according to Unique order. Consider: ``` let $dEq = GHC.Classes.$fEqInt in let $$dNum = GHC.Num.$fNumInt in ... ``` vs ``` let $dNum = GHC.Num.$fNumInt in let $dEq = GHC.Classes.$fEqInt in ... ``` The way this change fixes it is by using `UniqDFM` - a type of deterministic finite maps of things keyed on `Unique`s. This way when you pull out evidence variables corresponding to type-class dictionaries they are in deterministic order. Currently it's the order of insertion and the way it's implemented is by tagging the values with the time of insertion. Test Plan: I've added a new test case to reproduce the issue. ./validate Reviewers: ezyang, simonmar, austin, simonpj, bgamari Reviewed By: simonmar, simonpj, bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1396 GHC Trac Issues: #4012
View Lorry Controller Status