[rustc.git] / compiler / rustc_data_structures / src / transitive_relation / tests.rs

use super::*;

impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
    /// A "best" parent in some sense. See `parents` and
    /// `postdom_upper_bound` for more details.
    fn postdom_parent(&self, a: T) -> Option<T> {
        self.mutual_immediate_postdominator(self.parents(a))
    }
}

#[test]
fn test_one_step() {
    let mut relation = TransitiveRelation::default();
    relation.add("a", "b");
    relation.add("a", "c");
    assert!(relation.contains("a", "c"));
    assert!(relation.contains("a", "b"));
    assert!(!relation.contains("b", "a"));
    assert!(!relation.contains("a", "d"));
}

#[test]
fn test_many_steps() {
    let mut relation = TransitiveRelation::default();
    relation.add("a", "b");
    relation.add("a", "c");
    relation.add("a", "f");

    relation.add("b", "c");
    relation.add("b", "d");
    relation.add("b", "e");

    relation.add("e", "g");

    assert!(relation.contains("a", "b"));
    assert!(relation.contains("a", "c"));
    assert!(relation.contains("a", "d"));
    assert!(relation.contains("a", "e"));
    assert!(relation.contains("a", "f"));
    assert!(relation.contains("a", "g"));

    assert!(relation.contains("b", "g"));

    assert!(!relation.contains("a", "x"));
    assert!(!relation.contains("b", "f"));
}

#[test]
fn mubs_triangle() {
    // a -> tcx
    //      ^
    //      |
    //      b
    let mut relation = TransitiveRelation::default();
    relation.add("a", "tcx");
    relation.add("b", "tcx");
    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["tcx"]);
    assert_eq!(relation.parents("a"), vec!["tcx"]);
    assert_eq!(relation.parents("b"), vec!["tcx"]);
}

#[test]
fn mubs_best_choice1() {
    // 0 -> 1 <- 3
    // |    ^    |
    // |    |    |
    // +--> 2 <--+
    //
    // mubs(0,3) = [1]

    // This tests a particular state in the algorithm, in which we
    // need the second pare down call to get the right result (after
    // intersection, we have [1, 2], but 2 -> 1).

    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("2", "1");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["2"]);
    assert_eq!(relation.parents("0"), vec!["2"]);
    assert_eq!(relation.parents("2"), vec!["1"]);
    assert!(relation.parents("1").is_empty());
}

#[test]
fn mubs_best_choice2() {
    // 0 -> 1 <- 3
    // |    |    |
    // |    v    |
    // +--> 2 <--+
    //
    // mubs(0,3) = [2]

    // Like the preceding test, but in this case intersection is [2,
    // 1], and hence we rely on the first pare down call.

    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("1", "2");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
    assert_eq!(relation.parents("0"), vec!["1"]);
    assert_eq!(relation.parents("1"), vec!["2"]);
    assert!(relation.parents("2").is_empty());
}

#[test]
fn mubs_no_best_choice() {
    // in this case, the intersection yields [1, 2], and the "pare
    // down" calls find nothing to remove.
    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1", "2"]);
    assert_eq!(relation.parents("0"), vec!["1", "2"]);
    assert_eq!(relation.parents("3"), vec!["1", "2"]);
}

#[test]
fn mubs_best_choice_scc() {
    // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
    // consistently).

    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("1", "2");
    relation.add("2", "1");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
    assert_eq!(relation.parents("0"), vec!["1"]);
}

#[test]
fn pdub_crisscross() {
    // diagonal edges run left-to-right
    // a -> a1 -> x
    //   \/       ^
    //   /\       |
    // b -> b1 ---+

    let mut relation = TransitiveRelation::default();
    relation.add("a", "a1");
    relation.add("a", "b1");
    relation.add("b", "a1");
    relation.add("b", "b1");
    relation.add("a1", "x");
    relation.add("b1", "x");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
    assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
    assert_eq!(relation.postdom_parent("a"), Some("x"));
    assert_eq!(relation.postdom_parent("b"), Some("x"));
}

#[test]
fn pdub_crisscross_more() {
    // diagonal edges run left-to-right
    // a -> a1 -> a2 -> a3 -> x
    //   \/    \/             ^
    //   /\    /\             |
    // b -> b1 -> b2 ---------+

    let mut relation = TransitiveRelation::default();
    relation.add("a", "a1");
    relation.add("a", "b1");
    relation.add("b", "a1");
    relation.add("b", "b1");

    relation.add("a1", "a2");
    relation.add("a1", "b2");
    relation.add("b1", "a2");
    relation.add("b1", "b2");

    relation.add("a2", "a3");

    relation.add("a3", "x");
    relation.add("b2", "x");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
    assert_eq!(relation.minimal_upper_bounds("a1", "b1"), vec!["a2", "b2"]);
    assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));

    assert_eq!(relation.postdom_parent("a"), Some("x"));
    assert_eq!(relation.postdom_parent("b"), Some("x"));
}

#[test]
fn pdub_lub() {
    // a -> a1 -> x
    //            ^
    //            |
    // b -> b1 ---+

    let mut relation = TransitiveRelation::default();
    relation.add("a", "a1");
    relation.add("b", "b1");
    relation.add("a1", "x");
    relation.add("b1", "x");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["x"]);
    assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));

    assert_eq!(relation.postdom_parent("a"), Some("a1"));
    assert_eq!(relation.postdom_parent("b"), Some("b1"));
    assert_eq!(relation.postdom_parent("a1"), Some("x"));
    assert_eq!(relation.postdom_parent("b1"), Some("x"));
}

#[test]
fn mubs_intermediate_node_on_one_side_only() {
    // a -> c -> d
    //           ^
    //           |
    //           b

    // "digraph { a -> c -> d; b -> d; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("b", "d");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["d"]);
}

#[test]
fn mubs_scc_1() {
    // +-------------+
    // |    +----+   |
    // |    v    |   |
    // a -> c -> d <-+
    //           ^
    //           |
    //           b

    // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "c");
    relation.add("a", "d");
    relation.add("b", "d");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}

#[test]
fn mubs_scc_2() {
    //      +----+
    //      v    |
    // a -> c -> d
    //      ^    ^
    //      |    |
    //      +--- b

    // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "c");
    relation.add("b", "d");
    relation.add("b", "c");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}

#[test]
fn mubs_scc_3() {
    //      +---------+
    //      v         |
    // a -> c -> d -> e
    //           ^    ^
    //           |    |
    //           b ---+

    // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "e");
    relation.add("e", "c");
    relation.add("b", "d");
    relation.add("b", "e");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}

#[test]
fn mubs_scc_4() {
    //      +---------+
    //      v         |
    // a -> c -> d -> e
    // |         ^    ^
    // +---------+    |
    //                |
    //           b ---+

    // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "e");
    relation.add("e", "c");
    relation.add("a", "d");
    relation.add("b", "e");

    assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
}

#[test]
fn parent() {
    // An example that was misbehaving in the compiler.
    //
    // 4 -> 1 -> 3
    //   \  |   /
    //    \ v  /
    // 2 -> 0
    //
    // plus a bunch of self-loops
    //
    // Here `->` represents `<=` and `0` is `'static`.

    let pairs = vec![
        (2, /*->*/ 0),
        (2, /*->*/ 2),
        (0, /*->*/ 0),
        (0, /*->*/ 0),
        (1, /*->*/ 0),
        (1, /*->*/ 1),
        (3, /*->*/ 0),
        (3, /*->*/ 3),
        (4, /*->*/ 0),
        (4, /*->*/ 1),
        (1, /*->*/ 3),
    ];

    let mut relation = TransitiveRelation::default();
    for (a, b) in pairs {
        relation.add(a, b);
    }

    let p = relation.postdom_parent(3);
    assert_eq!(p, Some(0));
}
Commit	Line	Data
416331ca XL	1	use super::*;
416331ca XL	2
ee023bcb	3	impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
6a06907d XL	4	/// A "best" parent in some sense. See `parents` and
6a06907d XL	5	/// `postdom_upper_bound` for more details.
ee023bcb	6	fn postdom_parent(&self, a: T) -> Option<T> {
6a06907d XL	7	self.mutual_immediate_postdominator(self.parents(a))
	8	}
	9	}
	10
416331ca XL	11	#[test]
	12	fn test_one_step() {
	13	let mut relation = TransitiveRelation::default();
	14	relation.add("a", "b");
	15	relation.add("a", "c");
ee023bcb FG	16	assert!(relation.contains("a", "c"));
	17	assert!(relation.contains("a", "b"));
	18	assert!(!relation.contains("b", "a"));
	19	assert!(!relation.contains("a", "d"));
416331ca XL	20	}
	21
	22	#[test]
	23	fn test_many_steps() {
	24	let mut relation = TransitiveRelation::default();
	25	relation.add("a", "b");
	26	relation.add("a", "c");
	27	relation.add("a", "f");
	28
	29	relation.add("b", "c");
	30	relation.add("b", "d");
	31	relation.add("b", "e");
	32
	33	relation.add("e", "g");
	34
ee023bcb FG	35	assert!(relation.contains("a", "b"));
	36	assert!(relation.contains("a", "c"));
	37	assert!(relation.contains("a", "d"));
	38	assert!(relation.contains("a", "e"));
	39	assert!(relation.contains("a", "f"));
	40	assert!(relation.contains("a", "g"));
416331ca	41
ee023bcb	42	assert!(relation.contains("b", "g"));
416331ca	43
ee023bcb FG	44	assert!(!relation.contains("a", "x"));
ee023bcb FG	45	assert!(!relation.contains("b", "f"));
416331ca XL	46	}
	47
	48	#[test]
	49	fn mubs_triangle() {
	50	// a -> tcx
	51	// ^
	52	// \|
	53	// b
	54	let mut relation = TransitiveRelation::default();
	55	relation.add("a", "tcx");
	56	relation.add("b", "tcx");
ee023bcb FG	57	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["tcx"]);
	58	assert_eq!(relation.parents("a"), vec!["tcx"]);
	59	assert_eq!(relation.parents("b"), vec!["tcx"]);
416331ca XL	60	}
	61
	62	#[test]
	63	fn mubs_best_choice1() {
	64	// 0 -> 1 <- 3
	65	// \| ^ \|
	66	// \| \| \|
	67	// +--> 2 <--+
	68	//
	69	// mubs(0,3) = [1]
	70
	71	// This tests a particular state in the algorithm, in which we
	72	// need the second pare down call to get the right result (after
	73	// intersection, we have [1, 2], but 2 -> 1).
	74
	75	let mut relation = TransitiveRelation::default();
	76	relation.add("0", "1");
	77	relation.add("0", "2");
	78
	79	relation.add("2", "1");
	80
	81	relation.add("3", "1");
	82	relation.add("3", "2");
	83
ee023bcb FG	84	assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["2"]);
	85	assert_eq!(relation.parents("0"), vec!["2"]);
	86	assert_eq!(relation.parents("2"), vec!["1"]);
	87	assert!(relation.parents("1").is_empty());
416331ca XL	88	}
	89
	90	#[test]
	91	fn mubs_best_choice2() {
	92	// 0 -> 1 <- 3
	93	// \| \| \|
	94	// \| v \|
	95	// +--> 2 <--+
	96	//
	97	// mubs(0,3) = [2]
	98
ee023bcb	99	// Like the preceding test, but in this case intersection is [2,
416331ca XL	100	// 1], and hence we rely on the first pare down call.
	101
	102	let mut relation = TransitiveRelation::default();
	103	relation.add("0", "1");
	104	relation.add("0", "2");
	105
	106	relation.add("1", "2");
	107
	108	relation.add("3", "1");
	109	relation.add("3", "2");
	110
ee023bcb FG	111	assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
	112	assert_eq!(relation.parents("0"), vec!["1"]);
	113	assert_eq!(relation.parents("1"), vec!["2"]);
	114	assert!(relation.parents("2").is_empty());
416331ca XL	115	}
	116
	117	#[test]
	118	fn mubs_no_best_choice() {
	119	// in this case, the intersection yields [1, 2], and the "pare
	120	// down" calls find nothing to remove.
	121	let mut relation = TransitiveRelation::default();
	122	relation.add("0", "1");
	123	relation.add("0", "2");
	124
	125	relation.add("3", "1");
	126	relation.add("3", "2");
	127
ee023bcb FG	128	assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1", "2"]);
	129	assert_eq!(relation.parents("0"), vec!["1", "2"]);
	130	assert_eq!(relation.parents("3"), vec!["1", "2"]);
416331ca XL	131	}
	132
	133	#[test]
	134	fn mubs_best_choice_scc() {
	135	// in this case, 1 and 2 form a cycle; we pick arbitrarily (but
	136	// consistently).
	137
	138	let mut relation = TransitiveRelation::default();
	139	relation.add("0", "1");
	140	relation.add("0", "2");
	141
	142	relation.add("1", "2");
	143	relation.add("2", "1");
	144
	145	relation.add("3", "1");
	146	relation.add("3", "2");
	147
ee023bcb FG	148	assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
ee023bcb FG	149	assert_eq!(relation.parents("0"), vec!["1"]);
416331ca XL	150	}
	151
	152	#[test]
	153	fn pdub_crisscross() {
	154	// diagonal edges run left-to-right
	155	// a -> a1 -> x
	156	// \/ ^
	157	// /\ \|
	158	// b -> b1 ---+
	159
	160	let mut relation = TransitiveRelation::default();
	161	relation.add("a", "a1");
	162	relation.add("a", "b1");
	163	relation.add("b", "a1");
	164	relation.add("b", "b1");
	165	relation.add("a1", "x");
	166	relation.add("b1", "x");
	167
ee023bcb FG	168	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
	169	assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
	170	assert_eq!(relation.postdom_parent("a"), Some("x"));
	171	assert_eq!(relation.postdom_parent("b"), Some("x"));
416331ca XL	172	}
	173
	174	#[test]
	175	fn pdub_crisscross_more() {
	176	// diagonal edges run left-to-right
	177	// a -> a1 -> a2 -> a3 -> x
	178	// \/ \/ ^
	179	// /\ /\ \|
	180	// b -> b1 -> b2 ---------+
	181
	182	let mut relation = TransitiveRelation::default();
	183	relation.add("a", "a1");
	184	relation.add("a", "b1");
	185	relation.add("b", "a1");
	186	relation.add("b", "b1");
	187
	188	relation.add("a1", "a2");
	189	relation.add("a1", "b2");
	190	relation.add("b1", "a2");
	191	relation.add("b1", "b2");
	192
	193	relation.add("a2", "a3");
	194
	195	relation.add("a3", "x");
	196	relation.add("b2", "x");
	197
ee023bcb FG	198	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
	199	assert_eq!(relation.minimal_upper_bounds("a1", "b1"), vec!["a2", "b2"]);
	200	assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
416331ca	201
ee023bcb FG	202	assert_eq!(relation.postdom_parent("a"), Some("x"));
ee023bcb FG	203	assert_eq!(relation.postdom_parent("b"), Some("x"));
416331ca XL	204	}
	205
	206	#[test]
	207	fn pdub_lub() {
	208	// a -> a1 -> x
	209	// ^
	210	// \|
	211	// b -> b1 ---+
	212
	213	let mut relation = TransitiveRelation::default();
	214	relation.add("a", "a1");
	215	relation.add("b", "b1");
	216	relation.add("a1", "x");
	217	relation.add("b1", "x");
	218
ee023bcb FG	219	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["x"]);
ee023bcb FG	220	assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
416331ca	221
ee023bcb FG	222	assert_eq!(relation.postdom_parent("a"), Some("a1"));
	223	assert_eq!(relation.postdom_parent("b"), Some("b1"));
	224	assert_eq!(relation.postdom_parent("a1"), Some("x"));
	225	assert_eq!(relation.postdom_parent("b1"), Some("x"));
416331ca XL	226	}
	227
	228	#[test]
	229	fn mubs_intermediate_node_on_one_side_only() {
	230	// a -> c -> d
	231	// ^
	232	// \|
	233	// b
	234
	235	// "digraph { a -> c -> d; b -> d; }",
	236	let mut relation = TransitiveRelation::default();
	237	relation.add("a", "c");
	238	relation.add("c", "d");
	239	relation.add("b", "d");
	240
ee023bcb	241	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["d"]);
416331ca XL	242	}
	243
	244	#[test]
	245	fn mubs_scc_1() {
	246	// +-------------+
	247	// \| +----+ \|
	248	// \| v \| \|
	249	// a -> c -> d <-+
	250	// ^
	251	// \|
	252	// b
	253
	254	// "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
	255	let mut relation = TransitiveRelation::default();
	256	relation.add("a", "c");
	257	relation.add("c", "d");
	258	relation.add("d", "c");
	259	relation.add("a", "d");
	260	relation.add("b", "d");
	261
ee023bcb	262	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
416331ca XL	263	}
	264
	265	#[test]
	266	fn mubs_scc_2() {
	267	// +----+
	268	// v \|
	269	// a -> c -> d
	270	// ^ ^
	271	// \| \|
	272	// +--- b
	273
	274	// "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
	275	let mut relation = TransitiveRelation::default();
	276	relation.add("a", "c");
	277	relation.add("c", "d");
	278	relation.add("d", "c");
	279	relation.add("b", "d");
	280	relation.add("b", "c");
	281
ee023bcb	282	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
416331ca XL	283	}
	284
	285	#[test]
	286	fn mubs_scc_3() {
	287	// +---------+
	288	// v \|
	289	// a -> c -> d -> e
	290	// ^ ^
	291	// \| \|
	292	// b ---+
	293
	294	// "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
	295	let mut relation = TransitiveRelation::default();
	296	relation.add("a", "c");
	297	relation.add("c", "d");
	298	relation.add("d", "e");
	299	relation.add("e", "c");
	300	relation.add("b", "d");
	301	relation.add("b", "e");
	302
ee023bcb	303	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
416331ca XL	304	}
	305
	306	#[test]
	307	fn mubs_scc_4() {
	308	// +---------+
	309	// v \|
	310	// a -> c -> d -> e
	311	// \| ^ ^
	312	// +---------+ \|
	313	// \|
	314	// b ---+
	315
	316	// "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
	317	let mut relation = TransitiveRelation::default();
	318	relation.add("a", "c");
	319	relation.add("c", "d");
	320	relation.add("d", "e");
	321	relation.add("e", "c");
	322	relation.add("a", "d");
	323	relation.add("b", "e");
	324
ee023bcb	325	assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
416331ca XL	326	}
	327
	328	#[test]
	329	fn parent() {
	330	// An example that was misbehaving in the compiler.
	331	//
	332	// 4 -> 1 -> 3
	333	// \ \| /
	334	// \ v /
	335	// 2 -> 0
	336	//
	337	// plus a bunch of self-loops
	338	//
	339	// Here `->` represents `<=` and `0` is `'static`.
	340
	341	let pairs = vec![
	342	(2, /->/ 0),
	343	(2, /->/ 2),
	344	(0, /->/ 0),
	345	(0, /->/ 0),
	346	(1, /->/ 0),
	347	(1, /->/ 1),
	348	(3, /->/ 0),
	349	(3, /->/ 3),
	350	(4, /->/ 0),
	351	(4, /->/ 1),
	352	(1, /->/ 3),
	353	];
	354
	355	let mut relation = TransitiveRelation::default();
	356	for (a, b) in pairs {
	357	relation.add(a, b);
	358	}
	359
ee023bcb FG	360	let p = relation.postdom_parent(3);
ee023bcb FG	361	assert_eq!(p, Some(0));
416331ca	362	}