Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

14 files changed, 2851 insertions, 0 deletions

diff --git a/vendor/ena/.cargo-checksum.json b/vendor/ena/.cargo-checksum.json
new file mode 100644
index 000000000..246be2f1d
--- /dev/null
+++ b/vendor/ena/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"9cc278873c11103275c22c025d2170754767dc30ae109ddafd60b881b7d5a64b","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"0621878e61f0d0fda054bcbe02df75192c28bde1ecc8289cbd86aeba2dd72720","README.md":"c623c5a776782edc92b00e4934bd50b7754a861dc6cad02ee4c2a87f946a542f","measurements.txt":"b209f98f2bc696904a48829e86952f4f09b59e4e685f7c12087c59d05ed31829","src/bitvec.rs":"c6c66c348776ff480b7ff6e4a3e0f64554a4194266f614408b45b5e3c324ec0a","src/lib.rs":"9b94637cb53e882625d3fb714acac37bb5fe7762d2a583ad4fd43f276f849214","src/snapshot_vec.rs":"b9fce507e3eece42c742405aea870562f99fdea3a4e30a122cea64ef5634f197","src/undo_log.rs":"5c94971d95ae1dd2de04eae2ea1ec5b99c627fbe92b2ea40a4fa3c37d340e7b8","src/unify/backing_vec.rs":"97cc2cec917ad87bb59b9f08ab3e081758ab5632d4a2e35621ba68c175ab10e5","src/unify/mod.rs":"bffe4e412b7624cf67efb64e75ecb3f537050080c8aefa69e354c2d774906976","src/unify/tests.rs":"6ffe2de338f1c8014292fdc7e764451c7af3de344fd405a46b818447304bdd23","tests/external_undo_log.rs":"215645f44d90b22b6ff07f72157b285e9cc277b856c31a0b82526b1534bef240"},"package":"d7402b94a93c24e742487327a7cd839dc9d36fec9de9fb25b09f2dae459f36c3"}
\ No newline at end of file
diff --git a/vendor/ena/Cargo.toml b/vendor/ena/Cargo.toml
new file mode 100644
index 000000000..620558398
--- /dev/null
+++ b/vendor/ena/Cargo.toml
@@ -0,0 +1,37 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[package]
+name = "ena"
+version = "0.14.0"
+authors = ["Niko Matsakis <niko@alum.mit.edu>"]
+description = "Union-find, congruence closure, and other unification code. Based on code from rustc."
+homepage = "https://github.com/rust-lang-nursery/ena"
+readme = "README.md"
+keywords = ["unification", "union-find"]
+license = "MIT/Apache-2.0"
+repository = "https://github.com/rust-lang-nursery/ena"
+[dependencies.dogged]
+version = "0.2.0"
+optional = true
+
+[dependencies.log]
+version = "0.4"
+
+[dependencies.petgraph]
+version = "0.4.5"
+optional = true
+
+[features]
+bench = []
+congruence-closure = ["petgraph"]
+persistent = ["dogged"]
diff --git a/vendor/ena/LICENSE-APACHE b/vendor/ena/LICENSE-APACHE
new file mode 100644
index 000000000..16fe87b06
--- /dev/null
+++ b/vendor/ena/LICENSE-APACHE
@@ -0,0 +1,201 @@
+                              Apache License
+                        Version 2.0, January 2004
+                     http://www.apache.org/licenses/
+
+TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+1. Definitions.
+
+   "License" shall mean the terms and conditions for use, reproduction,
+   and distribution as defined by Sections 1 through 9 of this document.
+
+   "Licensor" shall mean the copyright owner or entity authorized by
+   the copyright owner that is granting the License.
+
+   "Legal Entity" shall mean the union of the acting entity and all
+   other entities that control, are controlled by, or are under common
+   control with that entity. For the purposes of this definition,
+   "control" means (i) the power, direct or indirect, to cause the
+   direction or management of such entity, whether by contract or
+   otherwise, or (ii) ownership of fifty percent (50%) or more of the
+   outstanding shares, or (iii) beneficial ownership of such entity.
+
+   "You" (or "Your") shall mean an individual or Legal Entity
+   exercising permissions granted by this License.
+
+   "Source" form shall mean the preferred form for making modifications,
+   including but not limited to software source code, documentation
+   source, and configuration files.
+
+   "Object" form shall mean any form resulting from mechanical
+   transformation or translation of a Source form, including but
+   not limited to compiled object code, generated documentation,
+   and conversions to other media types.
+
+   "Work" shall mean the work of authorship, whether in Source or
+   Object form, made available under the License, as indicated by a
+   copyright notice that is included in or attached to the work
+   (an example is provided in the Appendix below).
+
+   "Derivative Works" shall mean any work, whether in Source or Object
+   form, that is based on (or derived from) the Work and for which the
+   editorial revisions, annotations, elaborations, or other modifications
+   represent, as a whole, an original work of authorship. For the purposes
+   of this License, Derivative Works shall not include works that remain
+   separable from, or merely link (or bind by name) to the interfaces of,
+   the Work and Derivative Works thereof.
+
+   "Contribution" shall mean any work of authorship, including
+   the original version of the Work and any modifications or additions
+   to that Work or Derivative Works thereof, that is intentionally
+   submitted to Licensor for inclusion in the Work by the copyright owner
+   or by an individual or Legal Entity authorized to submit on behalf of
+   the copyright owner. For the purposes of this definition, "submitted"
+   means any form of electronic, verbal, or written communication sent
+   to the Licensor or its representatives, including but not limited to
+   communication on electronic mailing lists, source code control systems,
+   and issue tracking systems that are managed by, or on behalf of, the
+   Licensor for the purpose of discussing and improving the Work, but
+   excluding communication that is conspicuously marked or otherwise
+   designated in writing by the copyright owner as "Not a Contribution."
+
+   "Contributor" shall mean Licensor and any individual or Legal Entity
+   on behalf of whom a Contribution has been received by Licensor and
+   subsequently incorporated within the Work.
+
+2. Grant of Copyright License. Subject to the terms and conditions of
+   this License, each Contributor hereby grants to You a perpetual,
+   worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+   copyright license to reproduce, prepare Derivative Works of,
+   publicly display, publicly perform, sublicense, and distribute the
+   Work and such Derivative Works in Source or Object form.
+
+3. Grant of Patent License. Subject to the terms and conditions of
+   this License, each Contributor hereby grants to You a perpetual,
+   worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+   (except as stated in this section) patent license to make, have made,
+   use, offer to sell, sell, import, and otherwise transfer the Work,
+   where such license applies only to those patent claims licensable
+   by such Contributor that are necessarily infringed by their
+   Contribution(s) alone or by combination of their Contribution(s)
+   with the Work to which such Contribution(s) was submitted. If You
+   institute patent litigation against any entity (including a
+   cross-claim or counterclaim in a lawsuit) alleging that the Work
+   or a Contribution incorporated within the Work constitutes direct
+   or contributory patent infringement, then any patent licenses
+   granted to You under this License for that Work shall terminate
+   as of the date such litigation is filed.
+
+4. Redistribution. You may reproduce and distribute copies of the
+   Work or Derivative Works thereof in any medium, with or without
+   modifications, and in Source or Object form, provided that You
+   meet the following conditions:
+
+   (a) You must give any other recipients of the Work or
+       Derivative Works a copy of this License; and
+
+   (b) You must cause any modified files to carry prominent notices
+       stating that You changed the files; and
+
+   (c) You must retain, in the Source form of any Derivative Works
+       that You distribute, all copyright, patent, trademark, and
+       attribution notices from the Source form of the Work,
+       excluding those notices that do not pertain to any part of
+       the Derivative Works; and
+
+   (d) If the Work includes a "NOTICE" text file as part of its
+       distribution, then any Derivative Works that You distribute must
+       include a readable copy of the attribution notices contained
+       within such NOTICE file, excluding those notices that do not
+       pertain to any part of the Derivative Works, in at least one
+       of the following places: within a NOTICE text file distributed
+       as part of the Derivative Works; within the Source form or
+       documentation, if provided along with the Derivative Works; or,
+       within a display generated by the Derivative Works, if and
+       wherever such third-party notices normally appear. The contents
+       of the NOTICE file are for informational purposes only and
+       do not modify the License. You may add Your own attribution
+       notices within Derivative Works that You distribute, alongside
+       or as an addendum to the NOTICE text from the Work, provided
+       that such additional attribution notices cannot be construed
+       as modifying the License.
+
+   You may add Your own copyright statement to Your modifications and
+   may provide additional or different license terms and conditions
+   for use, reproduction, or distribution of Your modifications, or
+   for any such Derivative Works as a whole, provided Your use,
+   reproduction, and distribution of the Work otherwise complies with
+   the conditions stated in this License.
+
+5. Submission of Contributions. Unless You explicitly state otherwise,
+   any Contribution intentionally submitted for inclusion in the Work
+   by You to the Licensor shall be under the terms and conditions of
+   this License, without any additional terms or conditions.
+   Notwithstanding the above, nothing herein shall supersede or modify
+   the terms of any separate license agreement you may have executed
+   with Licensor regarding such Contributions.
+
+6. Trademarks. This License does not grant permission to use the trade
+   names, trademarks, service marks, or product names of the Licensor,
+   except as required for reasonable and customary use in describing the
+   origin of the Work and reproducing the content of the NOTICE file.
+
+7. Disclaimer of Warranty. Unless required by applicable law or
+   agreed to in writing, Licensor provides the Work (and each
+   Contributor provides its Contributions) on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+   implied, including, without limitation, any warranties or conditions
+   of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+   PARTICULAR PURPOSE. You are solely responsible for determining the
+   appropriateness of using or redistributing the Work and assume any
+   risks associated with Your exercise of permissions under this License.
+
+8. Limitation of Liability. In no event and under no legal theory,
+   whether in tort (including negligence), contract, or otherwise,
+   unless required by applicable law (such as deliberate and grossly
+   negligent acts) or agreed to in writing, shall any Contributor be
+   liable to You for damages, including any direct, indirect, special,
+   incidental, or consequential damages of any character arising as a
+   result of this License or out of the use or inability to use the
+   Work (including but not limited to damages for loss of goodwill,
+   work stoppage, computer failure or malfunction, or any and all
+   other commercial damages or losses), even if such Contributor
+   has been advised of the possibility of such damages.
+
+9. Accepting Warranty or Additional Liability. While redistributing
+   the Work or Derivative Works thereof, You may choose to offer,
+   and charge a fee for, acceptance of support, warranty, indemnity,
+   or other liability obligations and/or rights consistent with this
+   License. However, in accepting such obligations, You may act only
+   on Your own behalf and on Your sole responsibility, not on behalf
+   of any other Contributor, and only if You agree to indemnify,
+   defend, and hold each Contributor harmless for any liability
+   incurred by, or claims asserted against, such Contributor by reason
+   of your accepting any such warranty or additional liability.
+
+END OF TERMS AND CONDITIONS
+
+APPENDIX: How to apply the Apache License to your work.
+
+   To apply the Apache License to your work, attach the following
+   boilerplate notice, with the fields enclosed by brackets "[]"
+   replaced with your own identifying information. (Don't include
+   the brackets!)  The text should be enclosed in the appropriate
+   comment syntax for the file format. We also recommend that a
+   file or class name and description of purpose be included on the
+   same "printed page" as the copyright notice for easier
+   identification within third-party archives.
+
+Copyright [yyyy] [name of copyright owner]
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+	http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
diff --git a/vendor/ena/LICENSE-MIT b/vendor/ena/LICENSE-MIT
new file mode 100644
index 000000000..25597d583
--- /dev/null
+++ b/vendor/ena/LICENSE-MIT
@@ -0,0 +1,25 @@
+Copyright (c) 2010 The Rust Project Developers
+
+Permission is hereby granted, free of charge, to any
+person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the
+Software without restriction, including without
+limitation the rights to use, copy, modify, merge,
+publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software
+is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice
+shall be included in all copies or substantial portions
+of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
+ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
+SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
diff --git a/vendor/ena/README.md b/vendor/ena/README.md
new file mode 100644
index 000000000..afa6567c6
--- /dev/null
+++ b/vendor/ena/README.md
@@ -0,0 +1,22 @@
+[![Build Status](https://travis-ci.com/rust-lang-nursery/ena.svg?branch=master)](https://travis-ci.com/rust-lang-nursery/ena)
+
+An implementation of union-find in Rust; extracted from (and used by)
+rustc.
+
+### Name
+
+The name "ena" comes from the Greek word for "one".
+
+### Features
+
+By default, you just get the union-find implementation. You can also
+opt-in to the following experimental features:
+
+- `bench`: use to run benchmarks (`cargo bench --features bench`)
+
+### License
+
+Like rustc itself, this code is dual-licensed under the MIT and Apache
+licenses. Pull requests, comments, and other contributions are assumed
+to imply consent to those terms. Moreover, it is understood that any
+changes here may well be used in rustc itself under the same terms.
diff --git a/vendor/ena/measurements.txt b/vendor/ena/measurements.txt
new file mode 100644
index 000000000..ee7496349
--- /dev/null
+++ b/vendor/ena/measurements.txt
@@ -0,0 +1,6 @@
+base
+test unify::tests::big_array_bench ... bench:     740,192 ns/iter (+/- 35,823)
+test unify::tests::big_array_bench ... bench:     745,031 ns/iter (+/- 240,463)
+test unify::tests::big_array_bench ... bench:     762,031 ns/iter (+/- 240,463)
+test unify::tests::big_array_bench ... bench:     756,234 ns/iter (+/- 264,710)
+
diff --git a/vendor/ena/src/bitvec.rs b/vendor/ena/src/bitvec.rs
new file mode 100644
index 000000000..3677c8c5e
--- /dev/null
+++ b/vendor/ena/src/bitvec.rs
@@ -0,0 +1,301 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/// A very simple BitVector type.
+pub struct BitVector {
+    data: Vec<u64>,
+}
+
+impl BitVector {
+    pub fn new(num_bits: usize) -> BitVector {
+        let num_words = u64s(num_bits);
+        BitVector { data: vec![0; num_words] }
+    }
+
+    pub fn contains(&self, bit: usize) -> bool {
+        let (word, mask) = word_mask(bit);
+        (self.data[word] & mask) != 0
+    }
+
+    /// Returns true if the bit has changed.
+    pub fn insert(&mut self, bit: usize) -> bool {
+        let (word, mask) = word_mask(bit);
+        let data = &mut self.data[word];
+        let value = *data;
+        let new_value = value | mask;
+        *data = new_value;
+        new_value != value
+    }
+
+    pub fn insert_all(&mut self, all: &BitVector) -> bool {
+        assert!(self.data.len() == all.data.len());
+        let mut changed = false;
+        for (i, j) in self.data.iter_mut().zip(&all.data) {
+            let value = *i;
+            *i = value | *j;
+            if value != *i {
+                changed = true;
+            }
+        }
+        changed
+    }
+
+    pub fn grow(&mut self, num_bits: usize) {
+        let num_words = u64s(num_bits);
+        let extra_words = self.data.len() - num_words;
+        self.data.extend((0..extra_words).map(|_| 0));
+    }
+
+    /// Iterates over indexes of set bits in a sorted order
+    pub fn iter<'a>(&'a self) -> BitVectorIter<'a> {
+        BitVectorIter {
+            iter: self.data.iter(),
+            current: 0,
+            idx: 0,
+        }
+    }
+}
+
+pub struct BitVectorIter<'a> {
+    iter: ::std::slice::Iter<'a, u64>,
+    current: u64,
+    idx: usize,
+}
+
+impl<'a> Iterator for BitVectorIter<'a> {
+    type Item = usize;
+    fn next(&mut self) -> Option<usize> {
+        while self.current == 0 {
+            self.current = if let Some(&i) = self.iter.next() {
+                if i == 0 {
+                    self.idx += 64;
+                    continue;
+                } else {
+                    self.idx = u64s(self.idx) * 64;
+                    i
+                }
+            } else {
+                return None;
+            }
+        }
+        let offset = self.current.trailing_zeros() as usize;
+        self.current >>= offset;
+        self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
+        self.idx += offset + 1;
+        return Some(self.idx - 1);
+    }
+}
+
+/// A "bit matrix" is basically a square matrix of booleans
+/// represented as one gigantic bitvector. In other words, it is as if
+/// you have N bitvectors, each of length N. Note that `elements` here is `N`/
+#[derive(Clone)]
+pub struct BitMatrix {
+    elements: usize,
+    vector: Vec<u64>,
+}
+
+impl BitMatrix {
+    // Create a new `elements x elements` matrix, initially empty.
+    pub fn new(elements: usize) -> BitMatrix {
+        // For every element, we need one bit for every other
+        // element. Round up to an even number of u64s.
+        let u64s_per_elem = u64s(elements);
+        BitMatrix {
+            elements: elements,
+            vector: vec![0; elements * u64s_per_elem],
+        }
+    }
+
+    /// The range of bits for a given element.
+    fn range(&self, element: usize) -> (usize, usize) {
+        let u64s_per_elem = u64s(self.elements);
+        let start = element * u64s_per_elem;
+        (start, start + u64s_per_elem)
+    }
+
+    pub fn add(&mut self, source: usize, target: usize) -> bool {
+        let (start, _) = self.range(source);
+        let (word, mask) = word_mask(target);
+        let mut vector = &mut self.vector[..];
+        let v1 = vector[start + word];
+        let v2 = v1 | mask;
+        vector[start + word] = v2;
+        v1 != v2
+    }
+
+    /// Do the bits from `source` contain `target`?
+    ///
+    /// Put another way, if the matrix represents (transitive)
+    /// reachability, can `source` reach `target`?
+    pub fn contains(&self, source: usize, target: usize) -> bool {
+        let (start, _) = self.range(source);
+        let (word, mask) = word_mask(target);
+        (self.vector[start + word] & mask) != 0
+    }
+
+    /// Returns those indices that are reachable from both `a` and
+    /// `b`. This is an O(n) operation where `n` is the number of
+    /// elements (somewhat independent from the actual size of the
+    /// intersection, in particular).
+    pub fn intersection(&self, a: usize, b: usize) -> Vec<usize> {
+        let (a_start, a_end) = self.range(a);
+        let (b_start, b_end) = self.range(b);
+        let mut result = Vec::with_capacity(self.elements);
+        for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
+            let mut v = self.vector[i] & self.vector[j];
+            for bit in 0..64 {
+                if v == 0 {
+                    break;
+                }
+                if v & 0x1 != 0 {
+                    result.push(base * 64 + bit);
+                }
+                v >>= 1;
+            }
+        }
+        result
+    }
+
+    /// Add the bits from `read` to the bits from `write`,
+    /// return true if anything changed.
+    ///
+    /// This is used when computing transitive reachability because if
+    /// you have an edge `write -> read`, because in that case
+    /// `write` can reach everything that `read` can (and
+    /// potentially more).
+    pub fn merge(&mut self, read: usize, write: usize) -> bool {
+        let (read_start, read_end) = self.range(read);
+        let (write_start, write_end) = self.range(write);
+        let vector = &mut self.vector[..];
+        let mut changed = false;
+        for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
+            let v1 = vector[write_index];
+            let v2 = v1 | vector[read_index];
+            vector[write_index] = v2;
+            changed = changed | (v1 != v2);
+        }
+        changed
+    }
+}
+
+fn u64s(elements: usize) -> usize {
+    (elements + 63) / 64
+}
+
+fn word_mask(index: usize) -> (usize, u64) {
+    let word = index / 64;
+    let mask = 1 << (index % 64);
+    (word, mask)
+}
+
+#[test]
+fn bitvec_iter_works() {
+    let mut bitvec = BitVector::new(100);
+    bitvec.insert(1);
+    bitvec.insert(10);
+    bitvec.insert(19);
+    bitvec.insert(62);
+    bitvec.insert(63);
+    bitvec.insert(64);
+    bitvec.insert(65);
+    bitvec.insert(66);
+    bitvec.insert(99);
+    assert_eq!(bitvec.iter().collect::<Vec<_>>(),
+               [1, 10, 19, 62, 63, 64, 65, 66, 99]);
+}
+
+#[test]
+fn bitvec_iter_works_2() {
+    let mut bitvec = BitVector::new(300);
+    bitvec.insert(1);
+    bitvec.insert(10);
+    bitvec.insert(19);
+    bitvec.insert(62);
+    bitvec.insert(66);
+    bitvec.insert(99);
+    bitvec.insert(299);
+    assert_eq!(bitvec.iter().collect::<Vec<_>>(),
+               [1, 10, 19, 62, 66, 99, 299]);
+
+}
+
+#[test]
+fn bitvec_iter_works_3() {
+    let mut bitvec = BitVector::new(319);
+    bitvec.insert(0);
+    bitvec.insert(127);
+    bitvec.insert(191);
+    bitvec.insert(255);
+    bitvec.insert(319);
+    assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
+}
+
+#[test]
+fn union_two_vecs() {
+    let mut vec1 = BitVector::new(65);
+    let mut vec2 = BitVector::new(65);
+    assert!(vec1.insert(3));
+    assert!(!vec1.insert(3));
+    assert!(vec2.insert(5));
+    assert!(vec2.insert(64));
+    assert!(vec1.insert_all(&vec2));
+    assert!(!vec1.insert_all(&vec2));
+    assert!(vec1.contains(3));
+    assert!(!vec1.contains(4));
+    assert!(vec1.contains(5));
+    assert!(!vec1.contains(63));
+    assert!(vec1.contains(64));
+}
+
+#[test]
+fn grow() {
+    let mut vec1 = BitVector::new(65);
+    assert!(vec1.insert(3));
+    assert!(!vec1.insert(3));
+    assert!(vec1.insert(5));
+    assert!(vec1.insert(64));
+    vec1.grow(128);
+    assert!(vec1.contains(3));
+    assert!(vec1.contains(5));
+    assert!(vec1.contains(64));
+    assert!(!vec1.contains(126));
+}
+
+#[test]
+fn matrix_intersection() {
+    let mut vec1 = BitMatrix::new(200);
+
+    // (*) Elements reachable from both 2 and 65.
+
+    vec1.add(2, 3);
+    vec1.add(2, 6);
+    vec1.add(2, 10); // (*)
+    vec1.add(2, 64); // (*)
+    vec1.add(2, 65);
+    vec1.add(2, 130);
+    vec1.add(2, 160); // (*)
+
+    vec1.add(64, 133);
+
+    vec1.add(65, 2);
+    vec1.add(65, 8);
+    vec1.add(65, 10); // (*)
+    vec1.add(65, 64); // (*)
+    vec1.add(65, 68);
+    vec1.add(65, 133);
+    vec1.add(65, 160); // (*)
+
+    let intersection = vec1.intersection(2, 64);
+    assert!(intersection.is_empty());
+
+    let intersection = vec1.intersection(2, 65);
+    assert_eq!(intersection, &[10, 64, 160]);
+}
diff --git a/vendor/ena/src/lib.rs b/vendor/ena/src/lib.rs
new file mode 100644
index 000000000..aed352407
--- /dev/null
+++ b/vendor/ena/src/lib.rs
@@ -0,0 +1,24 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! An implementation of union-find. See the `unify` module for more
+//! details.
+
+#![cfg_attr(feature = "bench", feature(test))]
+
+#[macro_use]
+extern crate log;
+
+#[cfg(feature = "persistent")]
+extern crate dogged;
+
+pub mod snapshot_vec;
+pub mod undo_log;
+pub mod unify;
diff --git a/vendor/ena/src/snapshot_vec.rs b/vendor/ena/src/snapshot_vec.rs
new file mode 100644
index 000000000..efde49aea
--- /dev/null
+++ b/vendor/ena/src/snapshot_vec.rs
@@ -0,0 +1,441 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits
+//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either
+//! to rollback to the start of the snapshot or commit those changes.
+//!
+//! This vector is intended to be used as part of an abstraction, not serve as a complete
+//! abstraction on its own. As such, while it will roll back most changes on its own, it also
+//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To
+//! ensure that any changes you make this with this pointer are rolled back, you must invoke
+//! `record` to record any changes you make and also supplying a delegate capable of reversing
+//! those changes.
+
+use self::UndoLog::*;
+
+use std::fmt;
+use std::marker::PhantomData;
+use std::mem;
+use std::ops;
+
+use undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
+
+#[derive(Debug)]
+pub enum UndoLog<D: SnapshotVecDelegate> {
+    /// New variable with given index was created.
+    NewElem(usize),
+
+    /// Variable with given index was changed *from* the given value.
+    SetElem(usize, D::Value),
+
+    /// Extensible set of actions
+    Other(D::Undo),
+}
+
+impl<D: SnapshotVecDelegate> Rollback<UndoLog<D>> for SnapshotVecStorage<D> {
+    fn reverse(&mut self, undo: UndoLog<D>) {
+        self.values.reverse(undo)
+    }
+}
+impl<D: SnapshotVecDelegate> Rollback<UndoLog<D>> for Vec<D::Value> {
+    fn reverse(&mut self, undo: UndoLog<D>) {
+        match undo {
+            NewElem(i) => {
+                self.pop();
+                assert!(Vec::len(self) == i);
+            }
+
+            SetElem(i, v) => {
+                self[i] = v;
+            }
+
+            Other(u) => {
+                D::reverse(self, u);
+            }
+        }
+    }
+}
+
+pub trait VecLike<D>: AsRef<[D::Value]> + AsMut<[D::Value]> + Rollback<UndoLog<D>>
+where
+    D: SnapshotVecDelegate,
+{
+    fn push(&mut self, item: D::Value);
+    fn len(&self) -> usize;
+    fn reserve(&mut self, size: usize);
+}
+
+impl<D> VecLike<D> for Vec<D::Value>
+where
+    D: SnapshotVecDelegate,
+{
+    fn push(&mut self, item: D::Value) {
+        Vec::push(self, item)
+    }
+    fn len(&self) -> usize {
+        Vec::len(self)
+    }
+    fn reserve(&mut self, size: usize) {
+        Vec::reserve(self, size)
+    }
+}
+
+impl<D> VecLike<D> for &'_ mut Vec<D::Value>
+where
+    D: SnapshotVecDelegate,
+{
+    fn push(&mut self, item: D::Value) {
+        Vec::push(self, item)
+    }
+    fn len(&self) -> usize {
+        Vec::len(self)
+    }
+    fn reserve(&mut self, size: usize) {
+        Vec::reserve(self, size)
+    }
+}
+
+#[allow(type_alias_bounds)]
+pub type SnapshotVecStorage<D: SnapshotVecDelegate> =
+    SnapshotVec<D, Vec<<D as SnapshotVecDelegate>::Value>, ()>;
+
+pub struct SnapshotVec<
+    D: SnapshotVecDelegate,
+    V: VecLike<D> = Vec<<D as SnapshotVecDelegate>::Value>,
+    L = VecLog<UndoLog<D>>,
+> {
+    values: V,
+    undo_log: L,
+    _marker: PhantomData<D>,
+}
+
+impl<D, V, L> fmt::Debug for SnapshotVec<D, V, L>
+where
+    D: SnapshotVecDelegate,
+    V: VecLike<D> + fmt::Debug,
+    L: fmt::Debug,
+{
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt.debug_struct("SnapshotVec")
+            .field("values", &self.values)
+            .field("undo_log", &self.undo_log)
+            .finish()
+    }
+}
+
+// Snapshots are tokens that should be created/consumed linearly.
+pub struct Snapshot<S = ::undo_log::Snapshot> {
+    pub(crate) value_count: usize,
+    snapshot: S,
+}
+
+pub trait SnapshotVecDelegate {
+    type Value;
+    type Undo;
+
+    fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
+}
+
+// HACK(eddyb) manual impl avoids `Default` bound on `D`.
+impl<D: SnapshotVecDelegate, V: VecLike<D> + Default, L: Default> Default for SnapshotVec<D, V, L> {
+    fn default() -> Self {
+        SnapshotVec {
+            values: V::default(),
+            undo_log: Default::default(),
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D> + Default, L: Default> SnapshotVec<D, V, L> {
+    /// Creates a new `SnapshotVec`. If `L` is set to `()` then most mutating functions will not
+    /// be accessible without calling `with_log` and supplying a compatibly `UndoLogs` instance.
+    pub fn new() -> Self {
+        Self::default()
+    }
+}
+
+impl<D: SnapshotVecDelegate> SnapshotVecStorage<D> {
+    /// Creates a `SnapshotVec` using the `undo_log`, allowing mutating methods to be called
+    pub fn with_log<'a, L>(
+        &'a mut self,
+        undo_log: L,
+    ) -> SnapshotVec<D, &'a mut Vec<<D as SnapshotVecDelegate>::Value>, L>
+    where
+        L: UndoLogs<UndoLog<D>>,
+    {
+        SnapshotVec {
+            values: &mut self.values,
+            undo_log,
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<D: SnapshotVecDelegate, L: Default> SnapshotVec<D, Vec<D::Value>, L> {
+    pub fn with_capacity(c: usize) -> Self {
+        SnapshotVec {
+            values: Vec::with_capacity(c),
+            undo_log: Default::default(),
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<V: VecLike<D>, D: SnapshotVecDelegate, U> SnapshotVec<D, V, U> {
+    pub fn len(&self) -> usize {
+        self.values.len()
+    }
+
+    pub fn get(&self, index: usize) -> &D::Value {
+        &self.values.as_ref()[index]
+    }
+
+    /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
+    /// automatically, so you should be sure call `record()` with some sort of suitable undo
+    /// action.
+    pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
+        &mut self.values.as_mut()[index]
+    }
+
+    /// Reserve space for new values, just like an ordinary vec.
+    pub fn reserve(&mut self, additional: usize) {
+        // This is not affected by snapshots or anything.
+        self.values.reserve(additional);
+    }
+}
+
+impl<V: VecLike<D>, D: SnapshotVecDelegate, L: UndoLogs<UndoLog<D>>> SnapshotVec<D, V, L> {
+    fn in_snapshot(&self) -> bool {
+        self.undo_log.in_snapshot()
+    }
+
+    pub fn record(&mut self, action: D::Undo) {
+        if self.in_snapshot() {
+            self.undo_log.push(Other(action));
+        }
+    }
+
+    pub fn push(&mut self, elem: D::Value) -> usize {
+        let len = self.values.len();
+        self.values.push(elem);
+
+        if self.in_snapshot() {
+            self.undo_log.push(NewElem(len));
+        }
+
+        len
+    }
+
+    /// Updates the element at the given index. The old value will saved (and perhaps restored) if
+    /// a snapshot is active.
+    pub fn set(&mut self, index: usize, new_elem: D::Value) {
+        let old_elem = mem::replace(&mut self.values.as_mut()[index], new_elem);
+        if self.undo_log.in_snapshot() {
+            self.undo_log.push(SetElem(index, old_elem));
+        }
+    }
+
+    /// Updates all elements. Potentially more efficient -- but
+    /// otherwise equivalent to -- invoking `set` for each element.
+    pub fn set_all(&mut self, mut new_elems: impl FnMut(usize) -> D::Value) {
+        if !self.undo_log.in_snapshot() {
+            for (index, slot) in self.values.as_mut().iter_mut().enumerate() {
+                *slot = new_elems(index);
+            }
+        } else {
+            for i in 0..self.values.len() {
+                self.set(i, new_elems(i));
+            }
+        }
+    }
+
+    pub fn update<OP>(&mut self, index: usize, op: OP)
+    where
+        OP: FnOnce(&mut D::Value),
+        D::Value: Clone,
+    {
+        if self.undo_log.in_snapshot() {
+            let old_elem = self.values.as_mut()[index].clone();
+            self.undo_log.push(SetElem(index, old_elem));
+        }
+        op(&mut self.values.as_mut()[index]);
+    }
+}
+
+impl<D, V, L> SnapshotVec<D, V, L>
+where
+    D: SnapshotVecDelegate,
+    V: VecLike<D> + Rollback<UndoLog<D>>,
+    L: Snapshots<UndoLog<D>>,
+{
+    pub fn start_snapshot(&mut self) -> Snapshot<L::Snapshot> {
+        Snapshot {
+            value_count: self.values.len(),
+            snapshot: self.undo_log.start_snapshot(),
+        }
+    }
+
+    pub fn actions_since_snapshot(&self, snapshot: &Snapshot<L::Snapshot>) -> &[UndoLog<D>] {
+        self.undo_log.actions_since_snapshot(&snapshot.snapshot)
+    }
+
+    pub fn rollback_to(&mut self, snapshot: Snapshot<L::Snapshot>) {
+        let values = &mut self.values;
+        self.undo_log.rollback_to(|| values, snapshot.snapshot);
+    }
+
+    /// Commits all changes since the last snapshot. Of course, they
+    /// can still be undone if there is a snapshot further out.
+    pub fn commit(&mut self, snapshot: Snapshot<L::Snapshot>) {
+        self.undo_log.commit(snapshot.snapshot);
+    }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::Deref for SnapshotVec<D, V, L> {
+    type Target = [D::Value];
+    fn deref(&self) -> &[D::Value] {
+        self.values.as_ref()
+    }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::DerefMut for SnapshotVec<D, V, L> {
+    fn deref_mut(&mut self) -> &mut [D::Value] {
+        self.values.as_mut()
+    }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::Index<usize> for SnapshotVec<D, V, L> {
+    type Output = D::Value;
+    fn index(&self, index: usize) -> &D::Value {
+        self.get(index)
+    }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::IndexMut<usize> for SnapshotVec<D, V, L> {
+    fn index_mut(&mut self, index: usize) -> &mut D::Value {
+        self.get_mut(index)
+    }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D> + Extend<D::Value>> Extend<D::Value>
+    for SnapshotVec<D, V>
+{
+    fn extend<T>(&mut self, iterable: T)
+    where
+        T: IntoIterator<Item = D::Value>,
+    {
+        let initial_len = self.values.len();
+        self.values.extend(iterable);
+        let final_len = self.values.len();
+
+        if self.in_snapshot() {
+            self.undo_log
+                .extend((initial_len..final_len).map(|len| NewElem(len)));
+        }
+    }
+}
+
+impl<D: SnapshotVecDelegate, V, L> Clone for SnapshotVec<D, V, L>
+where
+    V: VecLike<D> + Clone,
+    L: Clone,
+{
+    fn clone(&self) -> Self {
+        SnapshotVec {
+            values: self.values.clone(),
+            undo_log: self.undo_log.clone(),
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<D: SnapshotVecDelegate> Clone for UndoLog<D>
+where
+    D::Value: Clone,
+    D::Undo: Clone,
+{
+    fn clone(&self) -> Self {
+        match *self {
+            NewElem(i) => NewElem(i),
+            SetElem(i, ref v) => SetElem(i, v.clone()),
+            Other(ref u) => Other(u.clone()),
+        }
+    }
+}
+
+impl SnapshotVecDelegate for i32 {
+    type Value = i32;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<i32>, _: ()) {}
+}
+
+#[test]
+fn basic() {
+    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
+    assert!(!vec.in_snapshot());
+    assert_eq!(vec.len(), 0);
+    vec.push(22);
+    vec.push(33);
+    assert_eq!(vec.len(), 2);
+    assert_eq!(*vec.get(0), 22);
+    assert_eq!(*vec.get(1), 33);
+    vec.set(1, 34);
+    assert_eq!(vec.len(), 2);
+    assert_eq!(*vec.get(0), 22);
+    assert_eq!(*vec.get(1), 34);
+
+    let snapshot = vec.start_snapshot();
+    assert!(vec.in_snapshot());
+
+    vec.push(44);
+    vec.push(55);
+    vec.set(1, 35);
+    assert_eq!(vec.len(), 4);
+    assert_eq!(*vec.get(0), 22);
+    assert_eq!(*vec.get(1), 35);
+    assert_eq!(*vec.get(2), 44);
+    assert_eq!(*vec.get(3), 55);
+
+    vec.rollback_to(snapshot);
+    assert!(!vec.in_snapshot());
+
+    assert_eq!(vec.len(), 2);
+    assert_eq!(*vec.get(0), 22);
+    assert_eq!(*vec.get(1), 34);
+}
+
+#[test]
+#[should_panic]
+fn out_of_order() {
+    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
+    vec.push(22);
+    let snapshot1 = vec.start_snapshot();
+    vec.push(33);
+    let snapshot2 = vec.start_snapshot();
+    vec.push(44);
+    vec.rollback_to(snapshot1); // bogus, but accepted
+    vec.rollback_to(snapshot2); // asserts
+}
+
+#[test]
+fn nested_commit_then_rollback() {
+    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
+    vec.push(22);
+    let snapshot1 = vec.start_snapshot();
+    let snapshot2 = vec.start_snapshot();
+    vec.set(0, 23);
+    vec.commit(snapshot2);
+    assert_eq!(*vec.get(0), 23);
+    vec.rollback_to(snapshot1);
+    assert_eq!(*vec.get(0), 22);
+}
diff --git a/vendor/ena/src/undo_log.rs b/vendor/ena/src/undo_log.rs
new file mode 100644
index 000000000..93c38030a
--- /dev/null
+++ b/vendor/ena/src/undo_log.rs
@@ -0,0 +1,248 @@
+//! Module which contains the snapshot/rollback functionality of the `ena` data structures.
+//!
+//! For most usecases this is just an internal implementation detail. However if many `ena`
+//! data structures are used snapshotted simultaneously it is possible to use
+//! `UnificationTableStorage`/`SnapshotVecStorage` instead and use a custom `UndoLogs<T>`
+//! type capable of recording the actions of all used data structures.
+//!
+//! Since the `*Storage` variants do not have an undo log `with_log` must be called with the
+//! unified log before any mutating actions.
+
+/// A trait which allows undo actions (`T`) to be pushed which can be used to rollback actio at a
+/// later time if needed.
+///
+/// The undo actions themselves are opaque to `UndoLogs`, only specified `Rollback` implementations
+/// need to know what an action is and how to reverse it.
+pub trait UndoLogs<T> {
+    /// True if a snapshot has started, false otherwise
+    fn in_snapshot(&self) -> bool {
+        self.num_open_snapshots() > 0
+    }
+
+    /// How many open snapshots this undo log currently has
+    fn num_open_snapshots(&self) -> usize;
+
+    /// Pushes a new "undo item" onto the undo log. This method is invoked when some action is taken
+    /// (e.g., a variable is unified). It records the info needed to reverse that action should an
+    /// enclosing snapshot be rolleod back.
+    fn push(&mut self, undo: T);
+
+    /// Removes all items from the undo log.
+    fn clear(&mut self);
+
+    /// Extends the undo log with many undos.
+    fn extend<I>(&mut self, undos: I)
+    where
+        Self: Sized,
+        I: IntoIterator<Item = T>,
+    {
+        undos.into_iter().for_each(|undo| self.push(undo));
+    }
+}
+
+impl<'a, T, U> UndoLogs<T> for &'a mut U
+where
+    U: UndoLogs<T>,
+{
+    fn in_snapshot(&self) -> bool {
+        U::in_snapshot(self)
+    }
+    fn num_open_snapshots(&self) -> usize {
+        U::num_open_snapshots(self)
+    }
+    fn push(&mut self, undo: T) {
+        U::push(self, undo)
+    }
+    fn clear(&mut self) {
+        U::clear(self);
+    }
+    fn extend<I>(&mut self, undos: I)
+    where
+        Self: Sized,
+        I: IntoIterator<Item = T>,
+    {
+        U::extend(self, undos)
+    }
+}
+
+/// A trait which extends `UndoLogs` to allow snapshots to be done at specific points. Each snapshot can then be used to
+/// rollback any changes to an underlying data structures if they were not desirable.
+///
+/// Each snapshot must be consumed linearly with either `rollback_to` or `commit`.
+pub trait Snapshots<T>: UndoLogs<T> {
+    type Snapshot;
+
+    /// Returns true if `self` has made any changes since snapshot started.
+    fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
+        !self.actions_since_snapshot(snapshot).is_empty()
+    }
+
+    /// Returns the slice of actions that were taken since the snapshot began.
+    fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T];
+
+    /// Starts a new snapshot. That snapshot must eventually either be committed via a call to
+    /// commit or rollback via rollback_to. Snapshots can be nested (i.e., you can start a snapshot
+    /// whilst another snapshot is in progress) but you must then commit or rollback the inner
+    /// snapshot before attempting to commit or rollback the outer snapshot.
+    fn start_snapshot(&mut self) -> Self::Snapshot;
+
+    /// Rollback (undo) the changes made to `storage` since the snapshot.
+    fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
+    where
+        R: Rollback<T>;
+
+    /// Commit: keep the changes that have been made since the snapshot began
+    fn commit(&mut self, snapshot: Self::Snapshot);
+}
+
+impl<T, U> Snapshots<T> for &'_ mut U
+where
+    U: Snapshots<T>,
+{
+    type Snapshot = U::Snapshot;
+    fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
+        U::has_changes(self, snapshot)
+    }
+    fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T] {
+        U::actions_since_snapshot(self, snapshot)
+    }
+
+    fn start_snapshot(&mut self) -> Self::Snapshot {
+        U::start_snapshot(self)
+    }
+    fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
+    where
+        R: Rollback<T>,
+    {
+        U::rollback_to(self, storage, snapshot)
+    }
+
+    fn commit(&mut self, snapshot: Self::Snapshot) {
+        U::commit(self, snapshot)
+    }
+}
+
+pub struct NoUndo;
+impl<T> UndoLogs<T> for NoUndo {
+    fn num_open_snapshots(&self) -> usize {
+        0
+    }
+    fn push(&mut self, _undo: T) {}
+    fn clear(&mut self) {}
+}
+
+/// A basic undo log.
+#[derive(Clone, Debug)]
+pub struct VecLog<T> {
+    log: Vec<T>,
+    num_open_snapshots: usize,
+}
+
+impl<T> Default for VecLog<T> {
+    fn default() -> Self {
+        VecLog {
+            log: Vec::new(),
+            num_open_snapshots: 0,
+        }
+    }
+}
+
+impl<T> UndoLogs<T> for VecLog<T> {
+    fn num_open_snapshots(&self) -> usize {
+        self.num_open_snapshots
+    }
+    fn push(&mut self, undo: T) {
+        self.log.push(undo);
+    }
+    fn clear(&mut self) {
+        self.log.clear();
+        self.num_open_snapshots = 0;
+    }
+}
+
+impl<T> Snapshots<T> for VecLog<T> {
+    type Snapshot = Snapshot;
+
+    fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
+        self.log.len() > snapshot.undo_len
+    }
+    fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T] {
+        &self.log[snapshot.undo_len..]
+    }
+
+    fn start_snapshot(&mut self) -> Snapshot {
+        self.num_open_snapshots += 1;
+        Snapshot {
+            undo_len: self.log.len(),
+        }
+    }
+
+    fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Snapshot)
+    where
+        R: Rollback<T>,
+    {
+        debug!("rollback_to({})", snapshot.undo_len);
+
+        self.assert_open_snapshot(&snapshot);
+
+        if self.log.len() > snapshot.undo_len {
+            let mut values = values();
+            while self.log.len() > snapshot.undo_len {
+                values.reverse(self.log.pop().unwrap());
+            }
+        }
+
+        self.num_open_snapshots -= 1;
+    }
+
+    fn commit(&mut self, snapshot: Snapshot) {
+        debug!("commit({})", snapshot.undo_len);
+
+        self.assert_open_snapshot(&snapshot);
+
+        if self.num_open_snapshots == 1 {
+            // The root snapshot. It's safe to clear the undo log because
+            // there's no snapshot further out that we might need to roll back
+            // to.
+            assert!(snapshot.undo_len == 0);
+            self.log.clear();
+        }
+
+        self.num_open_snapshots -= 1;
+    }
+}
+
+impl<T> VecLog<T> {
+    fn assert_open_snapshot(&self, snapshot: &Snapshot) {
+        // Failures here may indicate a failure to follow a stack discipline.
+        assert!(self.log.len() >= snapshot.undo_len);
+        assert!(self.num_open_snapshots > 0);
+    }
+}
+
+impl<T> std::ops::Index<usize> for VecLog<T> {
+    type Output = T;
+    fn index(&self, key: usize) -> &T {
+        &self.log[key]
+    }
+}
+
+/// A trait implemented for storage types (like `SnapshotVecStorage`) which can be rolled back using actions of type `U`.
+pub trait Rollback<U> {
+    fn reverse(&mut self, undo: U);
+}
+
+impl<T, U> Rollback<U> for &'_ mut T
+where
+    T: Rollback<U>,
+{
+    fn reverse(&mut self, undo: U) {
+        T::reverse(self, undo)
+    }
+}
+
+/// Snapshots are tokens that should be created/consumed linearly.
+pub struct Snapshot {
+    // Length of the undo log at the time the snapshot was taken.
+    undo_len: usize,
+}
diff --git a/vendor/ena/src/unify/backing_vec.rs b/vendor/ena/src/unify/backing_vec.rs
new file mode 100644
index 000000000..7c1eb2ced
--- /dev/null
+++ b/vendor/ena/src/unify/backing_vec.rs
@@ -0,0 +1,263 @@
+#[cfg(feature = "persistent")]
+use dogged::DVec;
+use snapshot_vec as sv;
+use std::marker::PhantomData;
+use std::ops::{self, Range};
+
+use undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
+
+use super::{UnifyKey, UnifyValue, VarValue};
+
+#[allow(dead_code)] // rustc BUG
+#[allow(type_alias_bounds)]
+type Key<S: UnificationStoreBase> = <S as UnificationStoreBase>::Key;
+
+/// Largely internal trait implemented by the unification table
+/// backing store types. The most common such type is `InPlace`,
+/// which indicates a standard, mutable unification table.
+pub trait UnificationStoreBase: ops::Index<usize, Output = VarValue<Key<Self>>> {
+    type Key: UnifyKey<Value = Self::Value>;
+    type Value: UnifyValue;
+
+    fn len(&self) -> usize;
+
+    fn tag() -> &'static str {
+        Self::Key::tag()
+    }
+}
+
+pub trait UnificationStoreMut: UnificationStoreBase {
+    fn reset_unifications(&mut self, value: impl FnMut(u32) -> VarValue<Self::Key>);
+
+    fn push(&mut self, value: VarValue<Self::Key>);
+
+    fn reserve(&mut self, num_new_values: usize);
+
+    fn update<F>(&mut self, index: usize, op: F)
+    where
+        F: FnOnce(&mut VarValue<Self::Key>);
+}
+
+pub trait UnificationStore: UnificationStoreMut {
+    type Snapshot;
+
+    fn start_snapshot(&mut self) -> Self::Snapshot;
+
+    fn rollback_to(&mut self, snapshot: Self::Snapshot);
+
+    fn commit(&mut self, snapshot: Self::Snapshot);
+
+    fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize>;
+}
+
+/// Backing store for an in-place unification table.
+/// Not typically used directly.
+#[derive(Clone, Debug)]
+pub struct InPlace<
+    K: UnifyKey,
+    V: sv::VecLike<Delegate<K>> = Vec<VarValue<K>>,
+    L = VecLog<sv::UndoLog<Delegate<K>>>,
+> {
+    pub(crate) values: sv::SnapshotVec<Delegate<K>, V, L>,
+}
+
+// HACK(eddyb) manual impl avoids `Default` bound on `K`.
+impl<K: UnifyKey, V: sv::VecLike<Delegate<K>> + Default, L: Default> Default for InPlace<K, V, L> {
+    fn default() -> Self {
+        InPlace {
+            values: sv::SnapshotVec::new(),
+        }
+    }
+}
+
+impl<K, V, L> UnificationStoreBase for InPlace<K, V, L>
+where
+    K: UnifyKey,
+    V: sv::VecLike<Delegate<K>>,
+{
+    type Key = K;
+    type Value = K::Value;
+
+    fn len(&self) -> usize {
+        self.values.len()
+    }
+}
+
+impl<K, V, L> UnificationStoreMut for InPlace<K, V, L>
+where
+    K: UnifyKey,
+    V: sv::VecLike<Delegate<K>>,
+    L: UndoLogs<sv::UndoLog<Delegate<K>>>,
+{
+    #[inline]
+    fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue<Self::Key>) {
+        self.values.set_all(|i| value(i as u32));
+    }
+
+    #[inline]
+    fn push(&mut self, value: VarValue<Self::Key>) {
+        self.values.push(value);
+    }
+
+    #[inline]
+    fn reserve(&mut self, num_new_values: usize) {
+        self.values.reserve(num_new_values);
+    }
+
+    #[inline]
+    fn update<F>(&mut self, index: usize, op: F)
+    where
+        F: FnOnce(&mut VarValue<Self::Key>),
+    {
+        self.values.update(index, op)
+    }
+}
+
+impl<K, V, L> UnificationStore for InPlace<K, V, L>
+where
+    K: UnifyKey,
+    V: sv::VecLike<Delegate<K>>,
+    L: Snapshots<sv::UndoLog<Delegate<K>>>,
+{
+    type Snapshot = sv::Snapshot<L::Snapshot>;
+
+    #[inline]
+    fn start_snapshot(&mut self) -> Self::Snapshot {
+        self.values.start_snapshot()
+    }
+
+    #[inline]
+    fn rollback_to(&mut self, snapshot: Self::Snapshot) {
+        self.values.rollback_to(snapshot);
+    }
+
+    #[inline]
+    fn commit(&mut self, snapshot: Self::Snapshot) {
+        self.values.commit(snapshot);
+    }
+
+    #[inline]
+    fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize> {
+        snapshot.value_count..self.len()
+    }
+}
+
+impl<K, V, L> ops::Index<usize> for InPlace<K, V, L>
+where
+    V: sv::VecLike<Delegate<K>>,
+    K: UnifyKey,
+{
+    type Output = VarValue<K>;
+    fn index(&self, index: usize) -> &VarValue<K> {
+        &self.values[index]
+    }
+}
+
+#[doc(hidden)]
+#[derive(Copy, Clone, Debug)]
+pub struct Delegate<K>(PhantomData<K>);
+
+impl<K: UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
+    type Value = VarValue<K>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {}
+}
+
+impl<K: UnifyKey> Rollback<sv::UndoLog<Delegate<K>>> for super::UnificationTableStorage<K> {
+    fn reverse(&mut self, undo: sv::UndoLog<Delegate<K>>) {
+        self.values.values.reverse(undo);
+    }
+}
+
+#[cfg(feature = "persistent")]
+#[derive(Clone, Debug)]
+pub struct Persistent<K: UnifyKey> {
+    values: DVec<VarValue<K>>,
+}
+
+// HACK(eddyb) manual impl avoids `Default` bound on `K`.
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> Default for Persistent<K> {
+    fn default() -> Self {
+        Persistent {
+            values: DVec::new(),
+        }
+    }
+}
+
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> UnificationStoreBase for Persistent<K> {
+    type Key = K;
+    type Value = K::Value;
+
+    fn len(&self) -> usize {
+        self.values.len()
+    }
+}
+
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> UnificationStoreMut for Persistent<K> {
+    #[inline]
+    fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue<Self::Key>) {
+        // Without extending dogged, there isn't obviously a more
+        // efficient way to do this. But it's pretty dumb. Maybe
+        // dogged needs a `map`.
+        for i in 0..self.values.len() {
+            self.values[i] = value(i as u32);
+        }
+    }
+
+    #[inline]
+    fn push(&mut self, value: VarValue<Self::Key>) {
+        self.values.push(value);
+    }
+
+    #[inline]
+    fn reserve(&mut self, _num_new_values: usize) {
+        // not obviously relevant to DVec.
+    }
+
+    #[inline]
+    fn update<F>(&mut self, index: usize, op: F)
+    where
+        F: FnOnce(&mut VarValue<Self::Key>),
+    {
+        let p = &mut self.values[index];
+        op(p);
+    }
+}
+
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> UnificationStore for Persistent<K> {
+    type Snapshot = Self;
+
+    #[inline]
+    fn start_snapshot(&mut self) -> Self::Snapshot {
+        self.clone()
+    }
+
+    #[inline]
+    fn rollback_to(&mut self, snapshot: Self::Snapshot) {
+        *self = snapshot;
+    }
+
+    #[inline]
+    fn commit(&mut self, _snapshot: Self::Snapshot) {}
+
+    #[inline]
+    fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize> {
+        snapshot.len()..self.len()
+    }
+}
+
+#[cfg(feature = "persistent")]
+impl<K> ops::Index<usize> for Persistent<K>
+where
+    K: UnifyKey,
+{
+    type Output = VarValue<K>;
+    fn index(&self, index: usize) -> &VarValue<K> {
+        &self.values[index]
+    }
+}
diff --git a/vendor/ena/src/unify/mod.rs b/vendor/ena/src/unify/mod.rs
new file mode 100644
index 000000000..a26d699d8
--- /dev/null
+++ b/vendor/ena/src/unify/mod.rs
@@ -0,0 +1,594 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Union-find implementation. The main type is `UnificationTable`.
+//!
+//! You can define your own type for the *keys* in the table, but you
+//! must implement `UnifyKey` for that type. The assumption is that
+//! keys will be newtyped integers, hence we require that they
+//! implement `Copy`.
+//!
+//! Keys can have values associated with them. The assumption is that
+//! these values are cheaply cloneable (ideally, `Copy`), and some of
+//! the interfaces are oriented around that assumption. If you just
+//! want the classical "union-find" algorithm where you group things
+//! into sets, use the `Value` type of `()`.
+//!
+//! When you have keys with non-trivial values, you must also define
+//! how those values can be merged. As part of doing this, you can
+//! define the "error" type to return on error; if errors are not
+//! possible, use `NoError` (an uninstantiable struct). Using this
+//! type also unlocks various more ergonomic methods (e.g., `union()`
+//! in place of `unify_var_var()`).
+//!
+//! The best way to see how it is used is to read the `tests.rs` file;
+//! search for e.g. `UnitKey`.
+
+use std::fmt::Debug;
+use std::marker;
+use std::ops::Range;
+
+use snapshot_vec::{self as sv, UndoLog};
+use undo_log::{UndoLogs, VecLog};
+
+mod backing_vec;
+pub use self::backing_vec::{
+    Delegate, InPlace, UnificationStore, UnificationStoreBase, UnificationStoreMut,
+};
+
+#[cfg(feature = "persistent")]
+pub use self::backing_vec::Persistent;
+
+#[cfg(test)]
+mod tests;
+
+/// This trait is implemented by any type that can serve as a type
+/// variable. We call such variables *unification keys*. For example,
+/// this trait is implemented by `IntVid`, which represents integral
+/// variables.
+///
+/// Each key type has an associated value type `V`. For example, for
+/// `IntVid`, this is `Option<IntVarValue>`, representing some
+/// (possibly not yet known) sort of integer.
+///
+/// Clients are expected to provide implementations of this trait; you
+/// can see some examples in the `test` module.
+pub trait UnifyKey: Copy + Clone + Debug + PartialEq {
+    type Value: UnifyValue;
+
+    fn index(&self) -> u32;
+
+    fn from_index(u: u32) -> Self;
+
+    fn tag() -> &'static str;
+
+    /// If true, then `self` should be preferred as root to `other`.
+    /// Note that we assume a consistent partial ordering, so
+    /// returning true implies that `other.prefer_as_root_to(self)`
+    /// would return false.  If there is no ordering between two keys
+    /// (i.e., `a.prefer_as_root_to(b)` and `b.prefer_as_root_to(a)`
+    /// both return false) then the rank will be used to determine the
+    /// root in an optimal way.
+    ///
+    /// NB. The only reason to implement this method is if you want to
+    /// control what value is returned from `find()`. In general, it
+    /// is better to let the unification table determine the root,
+    /// since overriding the rank can cause execution time to increase
+    /// dramatically.
+    #[allow(unused_variables)]
+    fn order_roots(
+        a: Self,
+        a_value: &Self::Value,
+        b: Self,
+        b_value: &Self::Value,
+    ) -> Option<(Self, Self)> {
+        None
+    }
+}
+
+/// Trait implemented for **values** associated with a unification
+/// key. This trait defines how to merge the values from two keys that
+/// are unioned together. This merging can be fallible. If you attempt
+/// to union two keys whose values cannot be merged, then the error is
+/// propagated up and the two keys are not unioned.
+///
+/// This crate provides implementations of `UnifyValue` for `()`
+/// (which is infallible) and `Option<T>` (where `T: UnifyValue`). The
+/// option implementation merges two sum-values using the `UnifyValue`
+/// implementation of `T`.
+///
+/// See also `EqUnifyValue`, which is a convenience trait for cases
+/// where the "merge" operation succeeds only if the two values are
+/// equal.
+pub trait UnifyValue: Clone + Debug {
+    /// Defines the type to return when merging of two values fails.
+    /// If merging is infallible, use the special struct `NoError`
+    /// found in this crate, which unlocks various more convenient
+    /// methods on the unification table.
+    type Error;
+
+    /// Given two values, produce a new value that combines them.
+    /// If that is not possible, produce an error.
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error>;
+}
+
+/// A convenient helper for unification values which must be equal or
+/// else an error occurs. For example, if you are unifying types in a
+/// simple functional language, this may be appropriate, since (e.g.)
+/// you can't unify a type variable bound to `int` with one bound to
+/// `float` (but you can unify two type variables both bound to
+/// `int`).
+///
+/// Any type which implements `EqUnifyValue` automatially implements
+/// `UnifyValue`; if the two values are equal, merging is permitted.
+/// Otherwise, the error `(v1, v2)` is returned, where `v1` and `v2`
+/// are the two unequal values.
+pub trait EqUnifyValue: Eq + Clone + Debug {}
+
+impl<T: EqUnifyValue> UnifyValue for T {
+    type Error = (T, T);
+
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error> {
+        if value1 == value2 {
+            Ok(value1.clone())
+        } else {
+            Err((value1.clone(), value2.clone()))
+        }
+    }
+}
+
+/// A struct which can never be instantiated. Used
+/// for the error type for infallible cases.
+#[derive(Debug)]
+pub struct NoError {
+    _dummy: (),
+}
+
+/// Value of a unification key. We implement Tarjan's union-find
+/// algorithm: when two keys are unified, one of them is converted
+/// into a "redirect" pointing at the other. These redirects form a
+/// DAG: the roots of the DAG (nodes that are not redirected) are each
+/// associated with a value of type `V` and a rank. The rank is used
+/// to keep the DAG relatively balanced, which helps keep the running
+/// time of the algorithm under control. For more information, see
+/// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
+#[derive(PartialEq, Clone, Debug)]
+pub struct VarValue<K: UnifyKey> {
+    parent: K,       // if equal to self, this is a root
+    value: K::Value, // value assigned (only relevant to root)
+    rank: u32,       // max depth (only relevant to root)
+}
+
+/// Table of unification keys and their values. You must define a key type K
+/// that implements the `UnifyKey` trait. Unification tables can be used in two-modes:
+///
+/// - in-place (`UnificationTable<InPlace<K>>` or `InPlaceUnificationTable<K>`):
+///   - This is the standard mutable mode, where the array is modified
+///     in place.
+///   - To do backtracking, you can employ the `snapshot` and `rollback_to`
+///     methods.
+/// - persistent (`UnificationTable<Persistent<K>>` or `PersistentUnificationTable<K>`):
+///   - In this mode, we use a persistent vector to store the data, so that
+///     cloning the table is an O(1) operation.
+///   - This implies that ordinary operations are quite a bit slower though.
+///   - Requires the `persistent` feature be selected in your Cargo.toml file.
+#[derive(Clone, Debug, Default)]
+pub struct UnificationTable<S: UnificationStoreBase> {
+    /// Indicates the current value of each key.
+    values: S,
+}
+
+pub type UnificationStorage<K> = Vec<VarValue<K>>;
+pub type UnificationTableStorage<K> = UnificationTable<InPlace<K, UnificationStorage<K>, ()>>;
+
+/// A unification table that uses an "in-place" vector.
+#[allow(type_alias_bounds)]
+pub type InPlaceUnificationTable<
+    K: UnifyKey,
+    V: sv::VecLike<Delegate<K>> = Vec<VarValue<K>>,
+    L = VecLog<UndoLog<Delegate<K>>>,
+> = UnificationTable<InPlace<K, V, L>>;
+
+/// A unification table that uses a "persistent" vector.
+#[cfg(feature = "persistent")]
+#[allow(type_alias_bounds)]
+pub type PersistentUnificationTable<K: UnifyKey> = UnificationTable<Persistent<K>>;
+
+/// At any time, users may snapshot a unification table.  The changes
+/// made during the snapshot may either be *committed* or *rolled back*.
+pub struct Snapshot<S: UnificationStore> {
+    // Link snapshot to the unification store `S` of the table.
+    marker: marker::PhantomData<S>,
+    snapshot: S::Snapshot,
+}
+
+impl<K: UnifyKey> VarValue<K> {
+    fn new_var(key: K, value: K::Value) -> VarValue<K> {
+        VarValue::new(key, value, 0)
+    }
+
+    fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> {
+        VarValue {
+            parent: parent, // this is a root
+            value: value,
+            rank: rank,
+        }
+    }
+
+    fn redirect(&mut self, to: K) {
+        self.parent = to;
+    }
+
+    fn root(&mut self, rank: u32, value: K::Value) {
+        self.rank = rank;
+        self.value = value;
+    }
+
+    fn parent(&self, self_key: K) -> Option<K> {
+        self.if_not_self(self.parent, self_key)
+    }
+
+    fn if_not_self(&self, key: K, self_key: K) -> Option<K> {
+        if key == self_key {
+            None
+        } else {
+            Some(key)
+        }
+    }
+}
+impl<K> UnificationTableStorage<K>
+where
+    K: UnifyKey,
+{
+    /// Creates a `UnificationTable` using an external `undo_log`, allowing mutating methods to be
+    /// called if `L` does not implement `UndoLogs`
+    pub fn with_log<'a, L>(
+        &'a mut self,
+        undo_log: L,
+    ) -> UnificationTable<InPlace<K, &'a mut UnificationStorage<K>, L>>
+    where
+        L: UndoLogs<sv::UndoLog<Delegate<K>>>,
+    {
+        UnificationTable {
+            values: InPlace {
+                values: self.values.values.with_log(undo_log),
+            },
+        }
+    }
+}
+
+// We can't use V:LatticeValue, much as I would like to,
+// because frequently the pattern is that V=Option<U> for some
+// other type parameter U, and we have no way to say
+// Option<U>:LatticeValue.
+
+impl<S: UnificationStoreBase + Default> UnificationTable<S> {
+    pub fn new() -> Self {
+        Self::default()
+    }
+}
+
+impl<S: UnificationStore> UnificationTable<S> {
+    /// Starts a new snapshot. Each snapshot must be either
+    /// rolled back or committed in a "LIFO" (stack) order.
+    pub fn snapshot(&mut self) -> Snapshot<S> {
+        Snapshot {
+            marker: marker::PhantomData::<S>,
+            snapshot: self.values.start_snapshot(),
+        }
+    }
+
+    /// Reverses all changes since the last snapshot. Also
+    /// removes any keys that have been created since then.
+    pub fn rollback_to(&mut self, snapshot: Snapshot<S>) {
+        debug!("{}: rollback_to()", S::tag());
+        self.values.rollback_to(snapshot.snapshot);
+    }
+
+    /// Commits all changes since the last snapshot. Of course, they
+    /// can still be undone if there is a snapshot further out.
+    pub fn commit(&mut self, snapshot: Snapshot<S>) {
+        debug!("{}: commit()", S::tag());
+        self.values.commit(snapshot.snapshot);
+    }
+
+    /// Returns the keys of all variables created since the `snapshot`.
+    pub fn vars_since_snapshot(&self, snapshot: &Snapshot<S>) -> Range<S::Key> {
+        let range = self.values.values_since_snapshot(&snapshot.snapshot);
+        S::Key::from_index(range.start as u32)..S::Key::from_index(range.end as u32)
+    }
+}
+
+impl<S: UnificationStoreBase> UnificationTable<S> {
+    /// Returns the number of keys created so far.
+    pub fn len(&self) -> usize {
+        self.values.len()
+    }
+}
+
+impl<S: UnificationStoreMut> UnificationTable<S> {
+    /// Starts a new snapshot. Each snapshot must be either
+    /// Creates a fresh key with the given value.
+    pub fn new_key(&mut self, value: S::Value) -> S::Key {
+        let len = self.values.len();
+        let key: S::Key = UnifyKey::from_index(len as u32);
+        self.values.push(VarValue::new_var(key, value));
+        debug!("{}: created new key: {:?}", S::tag(), key);
+        key
+    }
+
+    /// Reserve memory for `num_new_keys` to be created. Does not
+    /// actually create the new keys; you must then invoke `new_key`.
+    pub fn reserve(&mut self, num_new_keys: usize) {
+        self.values.reserve(num_new_keys);
+    }
+
+    /// Clears all unifications that have been performed, resetting to
+    /// the initial state. The values of each variable are given by
+    /// the closure.
+    pub fn reset_unifications(&mut self, mut value: impl FnMut(S::Key) -> S::Value) {
+        self.values.reset_unifications(|i| {
+            let key = UnifyKey::from_index(i as u32);
+            let value = value(key);
+            VarValue::new_var(key, value)
+        });
+    }
+
+    /// Obtains the current value for a particular key.
+    /// Not for end-users; they can use `probe_value`.
+    fn value(&self, key: S::Key) -> &VarValue<S::Key> {
+        &self.values[key.index() as usize]
+    }
+
+    /// Find the root node for `vid`. This uses the standard
+    /// union-find algorithm with path compression:
+    /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
+    ///
+    /// NB. This is a building-block operation and you would probably
+    /// prefer to call `probe` below.
+    ///
+    /// This is an always-inlined version of this function for the hot
+    /// callsites. `uninlined_get_root_key` is the never-inlined version.
+    #[inline(always)]
+    fn inlined_get_root_key(&mut self, vid: S::Key) -> S::Key {
+        let redirect = {
+            match self.value(vid).parent(vid) {
+                None => return vid,
+                Some(redirect) => redirect,
+            }
+        };
+
+        let root_key: S::Key = self.uninlined_get_root_key(redirect);
+        if root_key != redirect {
+            // Path compression
+            self.update_value(vid, |value| value.parent = root_key);
+        }
+
+        root_key
+    }
+
+    // This is a never-inlined version of this function for cold callsites.
+    // 'inlined_get_root_key` is the always-inlined version.
+    #[inline(never)]
+    fn uninlined_get_root_key(&mut self, vid: S::Key) -> S::Key {
+        self.inlined_get_root_key(vid)
+    }
+
+    fn update_value<OP>(&mut self, key: S::Key, op: OP)
+    where
+        OP: FnOnce(&mut VarValue<S::Key>),
+    {
+        self.values.update(key.index() as usize, op);
+        debug!("Updated variable {:?} to {:?}", key, self.value(key));
+    }
+
+    /// Either redirects `node_a` to `node_b` or vice versa, depending
+    /// on the relative rank. The value associated with the new root
+    /// will be `new_value`.
+    ///
+    /// NB: This is the "union" operation of "union-find". It is
+    /// really more of a building block. If the values associated with
+    /// your key are non-trivial, you would probably prefer to call
+    /// `unify_var_var` below.
+    fn unify_roots(&mut self, key_a: S::Key, key_b: S::Key, new_value: S::Value) {
+        debug!("unify(key_a={:?}, key_b={:?})", key_a, key_b);
+
+        let rank_a = self.value(key_a).rank;
+        let rank_b = self.value(key_b).rank;
+        if let Some((new_root, redirected)) = S::Key::order_roots(
+            key_a,
+            &self.value(key_a).value,
+            key_b,
+            &self.value(key_b).value,
+        ) {
+            // compute the new rank for the new root that they chose;
+            // this may not be the optimal choice.
+            let new_rank = if new_root == key_a {
+                debug_assert!(redirected == key_b);
+                if rank_a > rank_b {
+                    rank_a
+                } else {
+                    rank_b + 1
+                }
+            } else {
+                debug_assert!(new_root == key_b);
+                debug_assert!(redirected == key_a);
+                if rank_b > rank_a {
+                    rank_b
+                } else {
+                    rank_a + 1
+                }
+            };
+            self.redirect_root(new_rank, redirected, new_root, new_value);
+        } else if rank_a > rank_b {
+            // a has greater rank, so a should become b's parent,
+            // i.e., b should redirect to a.
+            self.redirect_root(rank_a, key_b, key_a, new_value);
+        } else if rank_a < rank_b {
+            // b has greater rank, so a should redirect to b.
+            self.redirect_root(rank_b, key_a, key_b, new_value);
+        } else {
+            // If equal, redirect one to the other and increment the
+            // other's rank.
+            self.redirect_root(rank_a + 1, key_a, key_b, new_value);
+        }
+    }
+
+    /// Internal method to redirect `old_root_key` (which is currently
+    /// a root) to a child of `new_root_key` (which will remain a
+    /// root). The rank and value of `new_root_key` will be updated to
+    /// `new_rank` and `new_value` respectively.
+    fn redirect_root(
+        &mut self,
+        new_rank: u32,
+        old_root_key: S::Key,
+        new_root_key: S::Key,
+        new_value: S::Value,
+    ) {
+        self.update_value(old_root_key, |old_root_value| {
+            old_root_value.redirect(new_root_key);
+        });
+        self.update_value(new_root_key, |new_root_value| {
+            new_root_value.root(new_rank, new_value);
+        });
+    }
+}
+
+/// ////////////////////////////////////////////////////////////////////////
+/// Public API
+
+impl<S, K, V> UnificationTable<S>
+where
+    S: UnificationStoreMut<Key = K, Value = V>,
+    K: UnifyKey<Value = V>,
+    V: UnifyValue,
+{
+    /// Unions two keys without the possibility of failure; only
+    /// applicable when unify values use `NoError` as their error
+    /// type.
+    pub fn union<K1, K2>(&mut self, a_id: K1, b_id: K2)
+    where
+        K1: Into<K>,
+        K2: Into<K>,
+        V: UnifyValue<Error = NoError>,
+    {
+        self.unify_var_var(a_id, b_id).unwrap();
+    }
+
+    /// Unions a key and a value without the possibility of failure;
+    /// only applicable when unify values use `NoError` as their error
+    /// type.
+    pub fn union_value<K1>(&mut self, id: K1, value: V)
+    where
+        K1: Into<K>,
+        V: UnifyValue<Error = NoError>,
+    {
+        self.unify_var_value(id, value).unwrap();
+    }
+
+    /// Given two keys, indicates whether they have been unioned together.
+    pub fn unioned<K1, K2>(&mut self, a_id: K1, b_id: K2) -> bool
+    where
+        K1: Into<K>,
+        K2: Into<K>,
+    {
+        self.find(a_id) == self.find(b_id)
+    }
+
+    /// Given a key, returns the (current) root key.
+    pub fn find<K1>(&mut self, id: K1) -> K
+    where
+        K1: Into<K>,
+    {
+        let id = id.into();
+        self.uninlined_get_root_key(id)
+    }
+
+    /// Unions together two variables, merging their values. If
+    /// merging the values fails, the error is propagated and this
+    /// method has no effect.
+    pub fn unify_var_var<K1, K2>(&mut self, a_id: K1, b_id: K2) -> Result<(), V::Error>
+    where
+        K1: Into<K>,
+        K2: Into<K>,
+    {
+        let a_id = a_id.into();
+        let b_id = b_id.into();
+
+        let root_a = self.uninlined_get_root_key(a_id);
+        let root_b = self.uninlined_get_root_key(b_id);
+
+        if root_a == root_b {
+            return Ok(());
+        }
+
+        let combined = V::unify_values(&self.value(root_a).value, &self.value(root_b).value)?;
+
+        Ok(self.unify_roots(root_a, root_b, combined))
+    }
+
+    /// Sets the value of the key `a_id` to `b`, attempting to merge
+    /// with the previous value.
+    pub fn unify_var_value<K1>(&mut self, a_id: K1, b: V) -> Result<(), V::Error>
+    where
+        K1: Into<K>,
+    {
+        let a_id = a_id.into();
+        let root_a = self.uninlined_get_root_key(a_id);
+        let value = V::unify_values(&self.value(root_a).value, &b)?;
+        self.update_value(root_a, |node| node.value = value);
+        Ok(())
+    }
+
+    /// Returns the current value for the given key. If the key has
+    /// been union'd, this will give the value from the current root.
+    pub fn probe_value<K1>(&mut self, id: K1) -> V
+    where
+        K1: Into<K>,
+    {
+        self.inlined_probe_value(id)
+    }
+
+    // An always-inlined version of `probe_value`, for hot callsites.
+    #[inline(always)]
+    pub fn inlined_probe_value<K1>(&mut self, id: K1) -> V
+    where
+        K1: Into<K>,
+    {
+        let id = id.into();
+        let id = self.inlined_get_root_key(id);
+        self.value(id).value.clone()
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+impl UnifyValue for () {
+    type Error = NoError;
+
+    fn unify_values(_: &(), _: &()) -> Result<(), NoError> {
+        Ok(())
+    }
+}
+
+impl<V: UnifyValue> UnifyValue for Option<V> {
+    type Error = V::Error;
+
+    fn unify_values(a: &Option<V>, b: &Option<V>) -> Result<Self, V::Error> {
+        match (a, b) {
+            (&None, &None) => Ok(None),
+            (&Some(ref v), &None) | (&None, &Some(ref v)) => Ok(Some(v.clone())),
+            (&Some(ref a), &Some(ref b)) => match V::unify_values(a, b) {
+                Ok(v) => Ok(Some(v)),
+                Err(err) => Err(err),
+            },
+        }
+    }
+}
diff --git a/vendor/ena/src/unify/tests.rs b/vendor/ena/src/unify/tests.rs
new file mode 100644
index 000000000..5665aba0c
--- /dev/null
+++ b/vendor/ena/src/unify/tests.rs
@@ -0,0 +1,486 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Naming the benchmarks using uppercase letters helps them sort
+// better.
+#![allow(non_snake_case)]
+
+#[cfg(feature = "bench")]
+extern crate test;
+#[cfg(feature = "bench")]
+use self::test::Bencher;
+use std::cmp;
+#[cfg(feature = "persistent")]
+use unify::Persistent;
+use unify::{EqUnifyValue, InPlace, InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
+use unify::{UnificationStore, UnificationTable};
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct UnitKey(u32);
+
+impl UnifyKey for UnitKey {
+    type Value = ();
+    fn index(&self) -> u32 {
+        self.0
+    }
+    fn from_index(u: u32) -> UnitKey {
+        UnitKey(u)
+    }
+    fn tag() -> &'static str {
+        "UnitKey"
+    }
+}
+
+macro_rules! all_modes {
+    ($name:ident for $t:ty => $body:tt) => {
+        fn test_body<
+            $name: Clone + Default + UnificationStore<Key = $t, Value = <$t as UnifyKey>::Value>,
+        >() {
+            $body
+        }
+
+        test_body::<InPlace<$t>>();
+
+        #[cfg(feature = "persistent")]
+        test_body::<Persistent<$t>>();
+    };
+}
+
+#[test]
+fn basic() {
+    all_modes! {
+        S for UnitKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(());
+            let k2 = ut.new_key(());
+            assert_eq!(ut.unioned(k1, k2), false);
+            ut.union(k1, k2);
+            assert_eq!(ut.unioned(k1, k2), true);
+        }
+    }
+}
+
+#[test]
+fn big_array() {
+    all_modes! {
+        S for UnitKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let mut keys = Vec::new();
+            const MAX: usize = 1 << 15;
+
+            for _ in 0..MAX {
+                keys.push(ut.new_key(()));
+            }
+
+            for i in 1..MAX {
+                let l = keys[i - 1];
+                let r = keys[i];
+                ut.union(l, r);
+            }
+
+            for i in 0..MAX {
+                assert!(ut.unioned(keys[0], keys[i]));
+            }
+        }
+    }
+}
+
+#[cfg(feature = "bench")]
+fn big_array_bench_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>(
+    b: &mut Bencher,
+) {
+    let mut ut: UnificationTable<S> = UnificationTable::new();
+    let mut keys = Vec::new();
+    const MAX: usize = 1 << 15;
+
+    for _ in 0..MAX {
+        keys.push(ut.new_key(()));
+    }
+
+    b.iter(|| {
+        for i in 1..MAX {
+            let l = keys[i - 1];
+            let r = keys[i];
+            ut.union(l, r);
+        }
+
+        for i in 0..MAX {
+            assert!(ut.unioned(keys[0], keys[i]));
+        }
+    })
+}
+
+#[cfg(feature = "bench")]
+#[bench]
+fn big_array_bench_InPlace(b: &mut Bencher) {
+    big_array_bench_generic::<InPlace<UnitKey>>(b);
+}
+
+#[cfg(all(feature = "bench", feature = "persistent"))]
+#[bench]
+fn big_array_bench_Persistent(b: &mut Bencher) {
+    big_array_bench_generic::<Persistent<UnitKey>>(b);
+}
+
+#[cfg(feature = "bench")]
+fn big_array_bench_in_snapshot_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>(
+    b: &mut Bencher,
+) {
+    let mut ut: UnificationTable<S> = UnificationTable::new();
+    let mut keys = Vec::new();
+    const MAX: usize = 1 << 15;
+
+    for _ in 0..MAX {
+        keys.push(ut.new_key(()));
+    }
+
+    b.iter(|| {
+        let snapshot = ut.snapshot();
+
+        for i in 1..MAX {
+            let l = keys[i - 1];
+            let r = keys[i];
+            ut.union(l, r);
+        }
+
+        for i in 0..MAX {
+            assert!(ut.unioned(keys[0], keys[i]));
+        }
+
+        ut.rollback_to(snapshot);
+    })
+}
+
+#[cfg(feature = "bench")]
+#[bench]
+fn big_array_bench_in_snapshot_InPlace(b: &mut Bencher) {
+    big_array_bench_in_snapshot_generic::<InPlace<UnitKey>>(b);
+}
+
+#[cfg(all(feature = "bench", feature = "persistent"))]
+#[bench]
+fn big_array_bench_in_snapshot_Persistent(b: &mut Bencher) {
+    big_array_bench_in_snapshot_generic::<Persistent<UnitKey>>(b);
+}
+
+#[cfg(feature = "bench")]
+fn big_array_bench_clone_generic<
+    S: Default + Clone + UnificationStore<Key = UnitKey, Value = ()>,
+>(
+    b: &mut Bencher,
+) {
+    let mut ut: UnificationTable<S> = UnificationTable::new();
+    let mut keys = Vec::new();
+    const MAX: usize = 1 << 15;
+
+    for _ in 0..MAX {
+        keys.push(ut.new_key(()));
+    }
+
+    b.iter(|| {
+        let saved_table = ut.clone();
+
+        for i in 1..MAX {
+            let l = keys[i - 1];
+            let r = keys[i];
+            ut.union(l, r);
+        }
+
+        for i in 0..MAX {
+            assert!(ut.unioned(keys[0], keys[i]));
+        }
+
+        ut = saved_table;
+    })
+}
+
+#[cfg(feature = "bench")]
+#[bench]
+fn big_array_bench_clone_InPlace(b: &mut Bencher) {
+    big_array_bench_clone_generic::<InPlace<UnitKey>>(b);
+}
+
+#[cfg(all(feature = "bench", feature = "persistent"))]
+#[bench]
+fn big_array_bench_clone_Persistent(b: &mut Bencher) {
+    big_array_bench_clone_generic::<Persistent<UnitKey>>(b);
+}
+
+#[test]
+fn even_odd() {
+    all_modes! {
+        S for UnitKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let mut keys = Vec::new();
+            const MAX: usize = 1 << 10;
+
+            for i in 0..MAX {
+                let key = ut.new_key(());
+                keys.push(key);
+
+                if i >= 2 {
+                    ut.union(key, keys[i - 2]);
+                }
+            }
+
+            for i in 1..MAX {
+                assert!(!ut.unioned(keys[i - 1], keys[i]));
+            }
+
+            for i in 2..MAX {
+                assert!(ut.unioned(keys[i - 2], keys[i]));
+            }
+        }
+    }
+}
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct IntKey(u32);
+
+impl UnifyKey for IntKey {
+    type Value = Option<i32>;
+    fn index(&self) -> u32 {
+        self.0
+    }
+    fn from_index(u: u32) -> IntKey {
+        IntKey(u)
+    }
+    fn tag() -> &'static str {
+        "IntKey"
+    }
+}
+
+impl EqUnifyValue for i32 {}
+
+#[test]
+fn unify_same_int_twice() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_value(k2, Some(22)).is_ok());
+            assert!(ut.unify_var_var(k1, k2).is_ok());
+            assert_eq!(ut.probe_value(k1), Some(22));
+        }
+    }
+}
+
+#[test]
+fn unify_vars_then_int_indirect() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            assert!(ut.unify_var_var(k1, k2).is_ok());
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert_eq!(ut.probe_value(k2), Some(22));
+        }
+    }
+}
+
+#[test]
+fn unify_vars_different_ints_1() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            assert!(ut.unify_var_var(k1, k2).is_ok());
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_value(k2, Some(23)).is_err());
+        }
+    }
+}
+
+#[test]
+fn unify_vars_different_ints_2() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            assert!(ut.unify_var_var(k2, k1).is_ok());
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_value(k2, Some(23)).is_err());
+        }
+    }
+}
+
+#[test]
+fn unify_distinct_ints_then_vars() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_value(k2, Some(23)).is_ok());
+            assert!(ut.unify_var_var(k2, k1).is_err());
+        }
+    }
+}
+
+#[test]
+fn unify_root_value_1() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            let k3 = ut.new_key(None);
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_var(k1, k2).is_ok());
+            assert!(ut.unify_var_value(k3, Some(23)).is_ok());
+            assert!(ut.unify_var_var(k1, k3).is_err());
+        }
+    }
+}
+
+#[test]
+fn unify_root_value_2() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            let k3 = ut.new_key(None);
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_var(k2, k1).is_ok());
+            assert!(ut.unify_var_value(k3, Some(23)).is_ok());
+            assert!(ut.unify_var_var(k1, k3).is_err());
+        }
+    }
+}
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct OrderedKey(u32);
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
+struct OrderedRank(u32);
+
+impl UnifyKey for OrderedKey {
+    type Value = OrderedRank;
+    fn index(&self) -> u32 {
+        self.0
+    }
+    fn from_index(u: u32) -> OrderedKey {
+        OrderedKey(u)
+    }
+    fn tag() -> &'static str {
+        "OrderedKey"
+    }
+    fn order_roots(
+        a: OrderedKey,
+        a_rank: &OrderedRank,
+        b: OrderedKey,
+        b_rank: &OrderedRank,
+    ) -> Option<(OrderedKey, OrderedKey)> {
+        println!("{:?} vs {:?}", a_rank, b_rank);
+        if a_rank > b_rank {
+            Some((a, b))
+        } else if b_rank > a_rank {
+            Some((b, a))
+        } else {
+            None
+        }
+    }
+}
+
+impl UnifyValue for OrderedRank {
+    type Error = NoError;
+
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
+        Ok(OrderedRank(cmp::max(value1.0, value2.0)))
+    }
+}
+
+#[test]
+fn ordered_key() {
+    all_modes! {
+        S for OrderedKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+
+            let k0_1 = ut.new_key(OrderedRank(0));
+            let k0_2 = ut.new_key(OrderedRank(0));
+            let k0_3 = ut.new_key(OrderedRank(0));
+            let k0_4 = ut.new_key(OrderedRank(0));
+
+            ut.union(k0_1, k0_2); // rank of one of those will now be 1
+            ut.union(k0_3, k0_4); // rank of new root also 1
+            ut.union(k0_1, k0_3); // rank of new root now 2
+
+            let k0_5 = ut.new_key(OrderedRank(0));
+            let k0_6 = ut.new_key(OrderedRank(0));
+            ut.union(k0_5, k0_6); // rank of new root now 1
+
+            ut.union(k0_1, k0_5); // new root rank 2, should not be k0_5 or k0_6
+            assert!(vec![k0_1, k0_2, k0_3, k0_4].contains(&ut.find(k0_1)));
+        }
+    }
+}
+
+#[test]
+fn ordered_key_k1() {
+    all_modes! {
+        S for UnitKey => {
+            let mut ut: InPlaceUnificationTable<OrderedKey> = UnificationTable::new();
+
+            let k0_1 = ut.new_key(OrderedRank(0));
+            let k0_2 = ut.new_key(OrderedRank(0));
+            let k0_3 = ut.new_key(OrderedRank(0));
+            let k0_4 = ut.new_key(OrderedRank(0));
+
+            ut.union(k0_1, k0_2); // rank of one of those will now be 1
+            ut.union(k0_3, k0_4); // rank of new root also 1
+            ut.union(k0_1, k0_3); // rank of new root now 2
+
+            let k1_5 = ut.new_key(OrderedRank(1));
+            let k1_6 = ut.new_key(OrderedRank(1));
+            ut.union(k1_5, k1_6); // rank of new root now 1
+
+            ut.union(k0_1, k1_5); // even though k1 has lower rank, it wins
+            assert!(
+                vec![k1_5, k1_6].contains(&ut.find(k0_1)),
+                "unexpected choice for root: {:?}",
+                ut.find(k0_1)
+            );
+        }
+    }
+}
+
+/// Test that we *can* clone.
+#[test]
+fn clone_table() {
+    all_modes! {
+        S for IntKey => {
+            let mut ut: UnificationTable<S> = UnificationTable::new();
+            let k1 = ut.new_key(None);
+            let k2 = ut.new_key(None);
+            let k3 = ut.new_key(None);
+            assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+            assert!(ut.unify_var_value(k2, Some(22)).is_ok());
+            assert!(ut.unify_var_var(k1, k2).is_ok());
+            assert_eq!(ut.probe_value(k3), None);
+
+            let mut ut1 = ut.clone();
+            assert_eq!(ut1.probe_value(k1), Some(22));
+            assert_eq!(ut1.probe_value(k3), None);
+
+            assert!(ut.unify_var_value(k3, Some(44)).is_ok());
+
+            assert_eq!(ut1.probe_value(k1), Some(22));
+            assert_eq!(ut1.probe_value(k3), None);
+            assert_eq!(ut.probe_value(k3), Some(44));
+        }
+    }
+}
diff --git a/vendor/ena/tests/external_undo_log.rs b/vendor/ena/tests/external_undo_log.rs
new file mode 100644
index 000000000..2537826c9
--- /dev/null
+++ b/vendor/ena/tests/external_undo_log.rs
@@ -0,0 +1,202 @@
+#[macro_use]
+extern crate log;
+extern crate ena;
+
+use ena::{
+    snapshot_vec as sv,
+    undo_log::{Rollback, Snapshots, UndoLogs},
+    unify::{self as ut, EqUnifyValue, UnifyKey},
+};
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct IntKey(u32);
+
+impl UnifyKey for IntKey {
+    type Value = Option<IntKey>;
+    fn index(&self) -> u32 {
+        self.0
+    }
+    fn from_index(u: u32) -> IntKey {
+        IntKey(u)
+    }
+    fn tag() -> &'static str {
+        "IntKey"
+    }
+}
+
+impl EqUnifyValue for IntKey {}
+
+enum UndoLog {
+    EqRelation(sv::UndoLog<ut::Delegate<IntKey>>),
+    Values(sv::UndoLog<i32>),
+}
+
+impl From<sv::UndoLog<ut::Delegate<IntKey>>> for UndoLog {
+    fn from(l: sv::UndoLog<ut::Delegate<IntKey>>) -> Self {
+        UndoLog::EqRelation(l)
+    }
+}
+
+impl From<sv::UndoLog<i32>> for UndoLog {
+    fn from(l: sv::UndoLog<i32>) -> Self {
+        UndoLog::Values(l)
+    }
+}
+
+impl Rollback<UndoLog> for TypeVariableStorage {
+    fn reverse(&mut self, undo: UndoLog) {
+        match undo {
+            UndoLog::EqRelation(undo) => self.eq_relations.reverse(undo),
+            UndoLog::Values(undo) => self.values.reverse(undo),
+        }
+    }
+}
+
+#[derive(Default)]
+struct TypeVariableStorage {
+    values: sv::SnapshotVecStorage<i32>,
+
+    eq_relations: ut::UnificationTableStorage<IntKey>,
+}
+
+impl TypeVariableStorage {
+    fn with_log<'a>(&'a mut self, undo_log: &'a mut TypeVariableUndoLogs) -> TypeVariableTable<'a> {
+        TypeVariableTable {
+            storage: self,
+            undo_log,
+        }
+    }
+
+    fn len(&mut self) -> usize {
+        assert_eq!(self.values.len(), self.eq_relations.len());
+        self.values.len()
+    }
+}
+
+struct TypeVariableTable<'a> {
+    storage: &'a mut TypeVariableStorage,
+
+    undo_log: &'a mut TypeVariableUndoLogs,
+}
+
+impl TypeVariableTable<'_> {
+    fn new(&mut self, i: i32) -> IntKey {
+        self.storage.values.with_log(&mut self.undo_log).push(i);
+        self.storage
+            .eq_relations
+            .with_log(&mut self.undo_log)
+            .new_key(None)
+    }
+}
+
+struct Snapshot {
+    undo_len: usize,
+}
+
+struct TypeVariableUndoLogs {
+    logs: Vec<UndoLog>,
+    num_open_snapshots: usize,
+}
+
+impl Default for TypeVariableUndoLogs {
+    fn default() -> Self {
+        Self {
+            logs: Default::default(),
+            num_open_snapshots: Default::default(),
+        }
+    }
+}
+
+impl<T> UndoLogs<T> for TypeVariableUndoLogs
+where
+    UndoLog: From<T>,
+{
+    fn num_open_snapshots(&self) -> usize {
+        self.num_open_snapshots
+    }
+    fn push(&mut self, undo: T) {
+        if self.in_snapshot() {
+            self.logs.push(undo.into())
+        }
+    }
+    fn clear(&mut self) {
+        self.logs.clear();
+        self.num_open_snapshots = 0;
+    }
+    fn extend<J>(&mut self, undos: J)
+    where
+        Self: Sized,
+        J: IntoIterator<Item = T>,
+    {
+        if self.in_snapshot() {
+            self.logs.extend(undos.into_iter().map(UndoLog::from))
+        }
+    }
+}
+
+impl Snapshots<UndoLog> for TypeVariableUndoLogs {
+    type Snapshot = Snapshot;
+    fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[UndoLog] {
+        &self.logs[snapshot.undo_len..]
+    }
+
+    fn start_snapshot(&mut self) -> Self::Snapshot {
+        self.num_open_snapshots += 1;
+        Snapshot {
+            undo_len: self.logs.len(),
+        }
+    }
+
+    fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Self::Snapshot)
+    where
+        R: Rollback<UndoLog>,
+    {
+        debug!("rollback_to({})", snapshot.undo_len);
+
+        if self.logs.len() > snapshot.undo_len {
+            let mut values = values();
+            while self.logs.len() > snapshot.undo_len {
+                values.reverse(self.logs.pop().unwrap());
+            }
+        }
+
+        if self.num_open_snapshots == 1 {
+            // The root snapshot. It's safe to clear the undo log because
+            // there's no snapshot further out that we might need to roll back
+            // to.
+            assert!(snapshot.undo_len == 0);
+            self.logs.clear();
+        }
+
+        self.num_open_snapshots -= 1;
+    }
+
+    fn commit(&mut self, snapshot: Self::Snapshot) {
+        debug!("commit({})", snapshot.undo_len);
+
+        if self.num_open_snapshots == 1 {
+            // The root snapshot. It's safe to clear the undo log because
+            // there's no snapshot further out that we might need to roll back
+            // to.
+            assert!(snapshot.undo_len == 0);
+            self.logs.clear();
+        }
+
+        self.num_open_snapshots -= 1;
+    }
+}
+
+/// Tests that a undo log stored externally can be used with TypeVariableTable
+#[test]
+fn external_undo_log() {
+    let mut storage = TypeVariableStorage::default();
+    let mut undo_log = TypeVariableUndoLogs::default();
+
+    let snapshot = undo_log.start_snapshot();
+    storage.with_log(&mut undo_log).new(1);
+    storage.with_log(&mut undo_log).new(2);
+    assert_eq!(storage.len(), 2);
+
+    undo_log.rollback_to(|| &mut storage, snapshot);
+    assert_eq!(storage.len(), 0);
+}