summary refs log tree commit diff
path: root/src/librustc_data_structures
AgeCommit message (Collapse)AuthorLines
2016-08-09generalize BitMatrix to be NxM and not just NxNNiko Matsakis-17/+69
2016-08-09isolate predecessor computationNiko Matsakis-18/+50
The new `Predecessors` type computes a set of interesting targets and their HIR predecessors, and discards everything in between.
2016-07-02Auto merge of #34605 - arielb1:bug-in-the-jungle, r=eddybbors-8/+67
fail obligations that depend on erroring obligations Fix a bug where an obligation that depend on an erroring obligation would be regarded as successful, leading to global cache pollution and random lossage. Fixes #33723. Fixes #34503. r? @eddyb since @nikomatsakis is on vacation beta-nominating because of the massive lossage potential (e.g. with `Copy` this could lead to random memory leaks), plus this is a regression.
2016-07-02fail obligations that depend on erroring obligationsAriel Ben-Yehuda-8/+67
Fix a bug where an obligation that depend on an erroring obligation would be regarded as successful, leading to global cache pollution and random lossage. Fixes #33723. Fixes #34503.
2016-06-28refactor rustc_metadata to use CamelCase names and IndexVecAriel Ben-Yehuda-0/+6
2016-06-23add control flow graph and algorithms. add dominator to mirScott A Carr-1/+830
2016-06-14Auto merge of #34221 - srinivasreddy:rm_redundant, r=alexcrichtonbors-15/+1
remove redundant test case in bitvector.rs `bitvec_iter_works_2` does exactly same as `bitvec_iter_works_1`, so i removed it.
2016-06-11Add additional test cases to test all arities of tuple; And remove type ↵Srinivas Reddy Thatiparthy-8/+18
suffix - i32 on integers
2016-06-11remove redundant test caseSrinivas Reddy Thatiparthy-15/+1
2016-06-09make the basic_blocks field privateAriel Ben-Yehuda-1/+20
2016-06-09introduce the type-safe IdxVec and use it instead of loose indexesAriel Ben-Yehuda-0/+210
2016-06-05Auto merge of #33999 - scottcarr:master, r=nikomatsakisbors-1/+1
generate fewer basic blocks for variant switches CC #33567 Adds a new field to TestKind::Switch that tracks the variants that are actually matched against. The other candidates target a common "otherwise" block.
2016-06-01switch to BitVector, simplify target_block logicScott A Carr-1/+1
clarify comments and panic message
2016-05-31add a snapshottable hashmapNiko Matsakis-0/+189
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
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-01 05:23:54 +0000