about summary refs log tree commit diff
path: root/src/librustc_data_structures
AgeCommit message (Collapse)AuthorLines
2016-05-18identify inputs of `MetaData(X)` nodesNiko Matsakis-4/+10
Generate a second hash file that contains the metadata for an X node.
2016-05-16Auto merge of #33491 - arielb1:obligation-jungle, r=nikomatsakisbors-411/+641
Replace the obligation forest with a graph In the presence of caching, arbitrary nodes in the obligation forest can be merged, which makes it a general graph. Handle it as such, using cycle-detection algorithms in the processing. I should do performance measurements sometime. This was pretty much written as a proof-of-concept. Please help me write this in a less-ugly way. I should also add comments explaining what is going on. r? @nikomatsakis
2016-05-13address review commentsAriel Ben-Yehuda-56/+81
2016-05-13add cycle-reporting logicAriel Ben-Yehuda-81/+111
Fixes #33344
2016-05-13rewrite obligation forest. cycles still handled incorrectly.Ariel Ben-Yehuda-370/+545
2016-05-11Plumb inference obligations through selectionMasood Malekghassemi-0/+8
2016-04-28Make the codegen unit partitioner also emit item declarations.Michael Woerister-11/+22
2016-04-03Use a BitVector instead of Vec<bool> for recording cleanup blocksJames Miller-1/+26
Also adds a FromIterator impl for BitVector to allow construction of a BitVector from an iterator yeilding bools.
2016-03-30Add some standard traversal iterators for MIRJames Miller-0/+1
Adds Preorder, Postorder and Reverse Postorder traversal iterators. Also makes trans/mir use Reverse Postorder traversal for blocks.
2016-03-21Auto merge of #32062 - Marwes:unification_table_for_eq_relations, r=nikomatsakisbors-9/+12
Improve time complexity of equality relations This PR adds a `UnificationTable` to the `TypeVariableTable` type which is used store information about variable equality instead of just storing them in a vector for later processing. By using a `UnificationTable` equality relations can be resolved in O(n) (for all realistic values of n) rather than O(n!) which can give massive speedups in certain cases (see combine as an example). Link to combine: https://github.com/Marwes/combine
2016-03-21Improve time complexity of equality relationsMarkus Westerlind-9/+12
This PR adds a `UnificationTable` to the `TypeVariableTable` type which is used store information about variable equality instead of just storing them in a vector for later processing. By using a `UnificationTable` equality relations can be resolved in O(n) (for all realistic values of n) rather than O(n!) which can give massive speedups in certain cases (see combine as an example). Link to combine: https://github.com/Marwes/combine
2016-03-14Move specialization graph walks to iterators; make associated typeAaron Turon-3/+1
projection sensitive to "mode" (most importantly, trans vs middle). This commit introduces several pieces of iteration infrastructure in the specialization graph data structure, as well as various helpers for finding the definition of a given item, given its kind and name. In addition, associated type projection is now *mode-sensitive*, with three possible modes: - **Topmost**. This means that projection is only possible if there is a non-`default` definition of the associated type directly on the selected impl. This mode is a bit of a hack: it's used during early coherence checking before we have built the specialization graph (and therefore before we can walk up the specialization parents to find other definitions). Eventually, this should be replaced with a less "staged" construction of the specialization graph. - **AnyFinal**. Projection succeeds for any non-`default` associated type definition, even if it is defined by a parent impl. Used throughout typechecking. - **Any**. Projection always succeeds. Used by trans. The lasting distinction here is between `AnyFinal` and `Any` -- we wish to treat `default` associated types opaquely for typechecking purposes. In addition to the above, the commit includes a few other minor review fixes.
2016-03-05adopt new header style to sidestep rust-lang-nursery/rustfmt#836Niko Matsakis-15/+9
2016-03-05apply rustfmt to librustc_data_structures, correcting ↵Niko Matsakis-355/+444
rust-lang-nursery/rustfmt#836
2016-02-23[MIR] Change SimplifyCfg pass to use bitvecSimonas Kazlauskas-0/+79
BitVector is much more space efficient.
2016-02-18Remove unnecessary explicit lifetime bounds.Corey Farwell-12/+12
These explicit lifetimes can be ommitted because of lifetime elision rules. Instances were found using rust-clippy.
2016-02-14rustc: Ensure FNV hashing is inlined across cratesAlex Crichton-0/+4
Right now the primary hashing algorithm of the compiler isn't actually inlined across crates, meaning that it may be missing out on some crucial optimizations in a few places (perhaps unrolling smaller loops, etc). This commit made the hashing function disappear from a profiled version of the compiler, but that's likely because it was just inlined elsewhere. When compiling winapi, however, this decreased compile time from 18.3 to 17.8 seconds (a 3% improvement).
2016-02-11bootstrap: Add a bunch of Cargo.toml filesAlex Crichton-0/+13
These describe the structure of all our crate dependencies.
2016-02-05Auto merge of #31349 - nikomatsakis:issue-31157-obligation-forest-cache, ↵bors-96/+191
r=aturon Have the `ObligationForest` keep some per-tree state (or type `T`) and have it give a mutable reference for use when processing obligations. In this case, it will be a hashmap. This obviously affects the work that @soltanmm has been doing on snapshotting. I partly want to toss this out there for discussion. Fixes #31157. (The test in question goes to approx. 30s instead of 5 minutes for me.) cc #30977. cc @aturon @arielb1 @soltanmm r? @aturon who reviewed original `ObligationForest`
2016-02-01Add a notion of "per-tree" stateNiko Matsakis-96/+191
2016-01-26Auto merge of #31120 - alexcrichton:attribute-deny-warnings, r=brsonbors-0/+1
This commit removes the `-D warnings` flag being passed through the makefiles to all crates to instead be a crate attribute. We want these attributes always applied for all our standard builds, and this is more amenable to Cargo-based builds as well. Note that all `deny(warnings)` attributes are gated with a `cfg(stage0)` attribute currently to match the same semantics we have today
2016-01-26Auto merge of #31081 - alexcrichton:stabilize-hasher, r=aturonbors-7/+5
This commit implements the stabilization of the custom hasher support intended for 1.7 but left out due to some last-minute questions that needed some decisions. A summary of the actions done in this PR are: Stable * `std::hash::BuildHasher` * `BuildHasher::Hasher` * `BuildHasher::build_hasher` * `std::hash::BuildHasherDefault` * `HashMap::with_hasher` * `HashMap::with_capacity_and_hasher` * `HashSet::with_hasher` * `HashSet::with_capacity_and_hasher` * `std::collections::hash_map::RandomState` * `RandomState::new` Deprecated * `std::collections::hash_state` * `std::collections::hash_state::HashState` - this trait was also moved into `std::hash` with a reexport here to ensure that we can have a blanket impl to prevent immediate breakage on nightly. Note that this is unstable in both location. * `HashMap::with_hash_state` - renamed * `HashMap::with_capacity_and_hash_state` - renamed * `HashSet::with_hash_state` - renamed * `HashSet::with_capacity_and_hash_state` - renamed Closes #27713
2016-01-26std: Stabilize custom hasher support in HashMapAlex Crichton-7/+5
This commit implements the stabilization of the custom hasher support intended for 1.7 but left out due to some last-minute questions that needed some decisions. A summary of the actions done in this PR are: Stable * `std::hash::BuildHasher` * `BuildHasher::Hasher` * `BuildHasher::build_hasher` * `std::hash::BuildHasherDefault` * `HashMap::with_hasher` * `HashMap::with_capacity_and_hasher` * `HashSet::with_hasher` * `HashSet::with_capacity_and_hasher` * `std::collections::hash_map::RandomState` * `RandomState::new` Deprecated * `std::collections::hash_state` * `std::collections::hash_state::HashState` - this trait was also moved into `std::hash` with a reexport here to ensure that we can have a blanket impl to prevent immediate breakage on nightly. Note that this is unstable in both location. * `HashMap::with_hash_state` - renamed * `HashMap::with_capacity_and_hash_state` - renamed * `HashSet::with_hash_state` - renamed * `HashSet::with_capacity_and_hash_state` - renamed Closes #27713
2016-01-24mk: Move from `-D warnings` to `#![deny(warnings)]`Alex Crichton-0/+1
This commit removes the `-D warnings` flag being passed through the makefiles to all crates to instead be a crate attribute. We want these attributes always applied for all our standard builds, and this is more amenable to Cargo-based builds as well. Note that all `deny(warnings)` attributes are gated with a `cfg(stage0)` attribute currently to match the same semantics we have today
2016-01-21[MIR] Promote temps to alloca on multi-assignmentSimonas Kazlauskas-2/+4
Fixes #31002
2016-01-16Document `ObligationForest` better.Niko Matsakis-49/+178
2016-01-16Pacify tidy.Niko Matsakis-57/+85
2016-01-16Permit coinductive match only for purely OIBIT backtraces.Niko Matsakis-0/+1
Better safe than sorry.
2016-01-14implement the obligation forest data structure and add some unit testsNiko Matsakis-1/+626
2016-01-06Fix tidy errorsNiko Matsakis-0/+10
2016-01-05Introduce the DepGraph and DepTracking map abstractions,Niko Matsakis-3/+49
along with a README explaining how they are to be used
2015-12-21Register new snapshotsAlex Crichton-3/+0
Lots of cruft to remove!
2015-12-12fix dropck performance regressionAriel Ben-Yehuda-3/+18
Turns out that calling `resolve_type_variables_if_possible` in a O(n^2) loop is a bad idea. Now we just resolve each copy of the region variable to its lowest name each time (we resolve the region variable to its lowest name, rather than to its unify-table name to avoid the risk of the unify-table name changing infinitely many times. That may be not a problem in practice, but I am not sure of it).
2015-12-10Add TupleSlice trait to rustc_data_structures.Michael Woerister-0/+61
2015-11-25Remove all uses of `#[staged_api]`Vadim Petrochenkov-1/+1
2015-09-06move fnv hashing support into librustc_data_structuresNiko Matsakis-0/+55
2015-09-06add a few accessors to GraphNiko Matsakis-0/+10
2015-08-23Fix panic in docs for librustc_data_structuresManish Goregaokar-1/+1
2015-08-21move the reverse into the iteratorNiko Matsakis-2/+2
2015-08-21missed one reference to "best"Niko Matsakis-4/+5
2015-08-21rename `best_upper_bound` to `postdom_upper_bound`Niko Matsakis-8/+8
2015-08-21remove use of swap_remove and compress the list as we go insteadNiko Matsakis-13/+12
2015-08-21nits from pnkfelixNiko Matsakis-45/+75
2015-08-21add final test case, correct one of the others (both versions producedNiko Matsakis-4/+22
same result)
2015-08-21add test cases suggested by pnkfelixNiko Matsakis-0/+82
2015-08-21clarify diagonal arrowsNiko Matsakis-0/+3
2015-08-18implement transitive relation type that can compute transitiveNiko Matsakis-0/+464
closures, upper bounds, and other fun things
2015-08-18remove unused importNiko Matsakis-1/+0
2015-08-18reorder imports to respect the alphabet, only one of the single mostNiko Matsakis-2/+2
important inventions of all time
2015-08-18generalize bitvector code into a bitmatrix; write some unit tests, butNiko Matsakis-9/+176
probably not enough. This code is so simple, what could possibly go wrong?
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-24 06:03:04 +0000