From e00cdd73456a3258e317bf68f8fa3a26c9922deb Mon Sep 17 00:00:00 2001
From: Markus Westerlind <marwes91@gmail.com>
Date: Thu, 3 Mar 2016 10:43:52 +0100
Subject: Improve time complexity of equality relations

This PR adds a `UnificationTable` to the `TypeVariableTable` type which
is used store information about variable equality instead of just
storing them in a vector for later processing. By using a
`UnificationTable` equality relations can be resolved in O(n) (for all
realistic values of n) rather than O(n!) which can give massive
speedups in certain cases (see combine as an example).

Link to combine: https://github.com/Marwes/combine
---
 src/test/run-pass/bench/issue-32062.rs | 58 ++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
 create mode 100644 src/test/run-pass/bench/issue-32062.rs

(limited to 'src/test')

diff --git a/src/test/run-pass/bench/issue-32062.rs b/src/test/run-pass/bench/issue-32062.rs
new file mode 100644
index 00000000000..8f6457d820a
--- /dev/null
+++ b/src/test/run-pass/bench/issue-32062.rs
@@ -0,0 +1,58 @@
+// Copyright 2016 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.
+
+// pretty-expanded FIXME #23616
+
+fn main() {
+    let _ = test(Some(0).into_iter());
+}
+
+trait Parser {
+    type Input: Iterator;
+    type Output;
+    fn parse(self, input: Self::Input) -> Result<(Self::Output, Self::Input), ()>;
+    fn chain<P>(self, p: P) -> Chain<Self, P> where Self: Sized {
+        Chain(self, p)
+    }
+}
+
+struct Token<T>(T::Item) where T: Iterator;
+
+impl<T> Parser for Token<T> where T: Iterator {
+    type Input = T;
+    type Output = T::Item;
+    fn parse(self, _input: Self::Input) -> Result<(Self::Output, Self::Input), ()> {
+        Err(())
+    }
+}
+
+struct Chain<L, R>(L, R);
+
+impl<L, R> Parser for Chain<L, R> where L: Parser, R: Parser<Input = L::Input> {
+    type Input = L::Input;
+    type Output = (L::Output, R::Output);
+    fn parse(self, _input: Self::Input) -> Result<(Self::Output, Self::Input), ()> {
+        Err(())
+    }
+}
+
+fn test<I>(i: I) -> Result<((), I), ()> where I: Iterator<Item = i32> {
+    Chain(Token(0), Token(1))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .chain(Chain(Token(0), Token(1)))
+        .parse(i)
+        .map(|(_, i)| ((), i))
+}
-- 
cgit 1.4.1-3-g733a5