]> git.lizzy.rs Git - rust.git/commit
Auto merge of #32062 - Marwes:unification_table_for_eq_relations, r=nikomatsakis
authorbors <bors@rust-lang.org>
Mon, 21 Mar 2016 23:00:08 +0000 (16:00 -0700)
committerbors <bors@rust-lang.org>
Mon, 21 Mar 2016 23:00:08 +0000 (16:00 -0700)
commit21922e1f48b263b39498cfeec79c1ca3f5886efe
tree091cf922ad764cc1bc19a2910b16d0abd82691e5
parent0168dc7c5904701983c280cb4fa0fb0c0fa692c5
parente00cdd73456a3258e317bf68f8fa3a26c9922deb
Auto merge of #32062 - Marwes:unification_table_for_eq_relations, r=nikomatsakis

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
src/librustc/middle/infer/freshen.rs
src/librustc/middle/infer/mod.rs