about summary refs log tree commit diff
path: root/src/librustc_data_structures
AgeCommit message (Collapse)AuthorLines
2016-10-25Add AccumulateVec, a potentially stack-allocated vector.Mark-Simulacrum-0/+163
AccumulateVec is generic over the Array trait, which is currently only implemented for [T; 8].
2016-10-22Auto merge of #37294 - nikomatsakis:issue-37154, r=nikomatsakisbors-15/+46
remove keys w/ skolemized regions from proj cache when popping skolemized regions This addresses #37154 (a regression). The projection cache was incorrectly caching the results for skolemized regions -- when we pop skolemized regions, we are supposed to drop cache keys for them (just as we remove those skolemized regions from the region inference graph). This is because those skolemized region numbers will be reused later with different meaning (and we have determined that the old ones don't leak out in any meaningful way). I did a *somewhat* aggressive fix here of only removing keys that mention the skolemized regions. One could imagine just removing all keys added since we started the skolemization (as indeed I did in my initial commit). This more aggressive fix required fixing a latent bug in `TypeFlags`, as an aside. I believe the more aggressive fix is correct; clearly there can be entries that are unrelated to the skoelemized region, and it's a shame to remove them. My one concern was that it *is* possible I believe to have some region variables that are created and related to skolemized regions, and maybe some of them could end up in the cache. However, that seems harmless enough to me-- those relations will be removed, and couldn't have impacted how trait resolution proceeded anyway (iow, the cache entry is not wrong, though it is kind of useless). r? @pnkfelix cc @arielb1
2016-10-22Rollup merge of #37286 - srinivasreddy:graph, r=nrcGuillaume Gomez-2/+2
run rustfmt on graph folder
2016-10-21only remove keys that mention skolemized regionsNiko Matsakis-3/+7
2016-10-21when pop skol, also remove from proj cacheNiko Matsakis-15/+42
2016-10-19Rollup merge of #37288 - srinivasreddy:snapshot_map, r=eddybGuillaume Gomez-8/+9
run rustfmt on snapshot_map
2016-10-19Rollup merge of #37287 - srinivasreddy:unify, r=eddybGuillaume Gomez-8/+6
run rustfmt on unify folder
2016-10-20run rustfmt on snapshot_mapSrinivas Reddy Thatiparthy-8/+9
2016-10-20run rustfmt on unify folderSrinivas Reddy Thatiparthy-8/+6
2016-10-20run rustfmt on graph folderSrinivas Reddy Thatiparthy-2/+2
2016-10-20run rustfmt on control_flow_graph folderSrinivas Reddy Thatiparthy-89/+48
2016-10-19Rollup merge of #37233 - michaelwoerister:blake2-for-ich, r=nikomatsakisEduard-Mihai Burtescu-0/+287
ICH: Use 128-bit Blake2b hash instead of 64-bit SipHash for incr. comp. fingerprints This PR makes incr. comp. hashes 128 bits wide in order to push collision probability below a threshold that we need to worry about. It also replaces SipHash, which has been mentioned multiple times as not being built for fingerprinting, with the [BLAKE2b hash function](https://blake2.net/), an improved version of the BLAKE sha-3 finalist. I was worried that using a cryptographic hash function would make ICH computation noticeably slower, but after doing some performance tests, I'm not any more. Most of the time BLAKE2b is actually faster than using two SipHashes (in order to get 128 bits): ``` SipHash libcore: 0.199 seconds libstd: 0.090 seconds BLAKE2b libcore: 0.162 seconds libstd: 0.078 seconds ``` If someone can prove that something like MetroHash128 provides a comparably low collision probability as BLAKE2, I'm happy to switch. But for now we are at least not taking a performance hit. I also suggest that we throw out the sha-256 implementation in the compiler and replace it with BLAKE2, since our sha-256 implementation is two to three times slower than the BLAKE2 implementation in this PR (cc @alexcrichton @eddyb @brson) r? @nikomatsakis (although there's not much incr. comp. specific in here, so feel free to re-assign)
2016-10-17Set stalled=false when encountering an errorJonas Schievink-0/+1
2016-10-17ICH: Use 128-bit Blake2b hash instead of 64-bit SipHash for incr. comp. ↵Michael Woerister-0/+287
fingerprints.
2016-10-17Don't process cycles when stalledJonas Schievink-0/+10
This improves the `inflate-0.1.0` benchmark by about 10% for me.
2016-10-10Move IdxSetBuf and BitSlice to rustc_data_structuresWesley Wiser-0/+300
Resolves a FIXME
2016-09-25Add support for the Haiku operating system on x86 and x86_64 machinesNiels Sascha Reedijk-0/+21
* Hand rebased from Niels original work on 1.9.0
2016-09-11Documentation of what does for each typeathulappadan-0/+1
2016-09-01ICH: Adapt to changes in the MetaItem AST representation.Michael Woerister-0/+6
2016-08-29incr.comp.: Move lock files out of directory being lockedMichael Woerister-20/+35
2016-08-29Implement copy-on-write scheme for managing the incremental compilation cache.Michael Woerister-0/+2
2016-08-29Add some features to flock.Michael Woerister-21/+105
2016-08-29Move `flock.rs` from librustdoc to librustc_data_structures.Michael Woerister-0/+241
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
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 15:56:21 +0000