]> git.lizzy.rs Git - rust.git/commit
Speed up `nearest_common_ancestor()`.
authorNicholas Nethercote <nnethercote@mozilla.com>
Fri, 20 Apr 2018 10:28:28 +0000 (20:28 +1000)
committerNicholas Nethercote <nnethercote@mozilla.com>
Fri, 20 Apr 2018 10:28:28 +0000 (20:28 +1000)
commitcccd51cd6e8861ba2640834c11fa67f83fa7698f
treef6fd65c6c116aad4755423e0db710054d1b242b0
parent144c0d5519dff9eca7bacd6191856ef57dbb7e0f
Speed up `nearest_common_ancestor()`.

`nearest_common_ancestor()` uses an algorithm that requires computing
the full scope chain for both scopes, which is expensive because each
element involves a hash table lookup, and then looking for a common
tail.

This patch changes `nearest_common_ancestor()` to use a different
algorithm, which starts at the given scopes and works outwards (i.e. up
the scope tree) until a common ancestor is found. This is much faster
because in most cases the common ancestor is found well before the end
of the scope chains. Also, the use of a SmallVec avoids the need for any
allocation most of the time.
src/librustc/middle/region.rs