Add test that tsort fails (incorrect detection of cycle).

Based on a test case found by Dragos Ruiu (dr@kyx.net)

3 files changed, 1758 insertions, 12 deletions

diff --git a/regress/usr.bin/tsort/Makefile b/regress/usr.bin/tsort/Makefile
index e5b206f2fb1..275638eaa3e 100644
--- a/regress/usr.bin/tsort/Makefile
+++ b/regress/usr.bin/tsort/Makefile
@@ -1,9 +1,9 @@
-# $OpenBSD: Makefile,v 1.2 2001/03/07 16:20:42 espie Exp $
+# $OpenBSD: Makefile,v 1.3 2001/07/09 10:48:03 espie Exp $
 
 NOMAN=
 NOPROG=
 
-regress: t1 t2 t3 t4
+regress: t1 t2 t3 t4 #t6
 
 t1: t1.out
 	perl ${.CURDIR}/tsort-check t1.out ${.CURDIR}/pairs1
@@ -12,10 +12,13 @@ t2: t2.out
 	perl ${.CURDIR}/normalize-cycles <t2.out|head -1|diff - ${.CURDIR}/t2.canonical
 
 t3: t3.out pairs3
-	perl ${.CURDIR}/tsort-check t3.out pairs3
+	time perl ${.CURDIR}/tsort-check t3.out pairs3
 
 t4: t4.out pairs4
-	perl ${.CURDIR}/tsort-check t4.out pairs4
+	time perl ${.CURDIR}/tsort-check t4.out pairs4
+
+t6:
+	tsort <pairs6
 
 t1.out:
 	tsort <${.CURDIR}/pairs1 >$@
diff --git a/regress/usr.bin/tsort/pairs6 b/regress/usr.bin/tsort/pairs6
new file mode 100644
index 00000000000..d74941da15f
--- /dev/null
+++ b/regress/usr.bin/tsort/pairs6
@@ -0,0 +1,1742 @@
+1 1
+2 2
+3 3
+4 4
+5 5
+6 6
+7 7
+8 8
+9 9
+10 10
+11 11
+12 12
+13 13
+14 14
+15 15
+16 16
+17 17
+18 18
+19 19
+20 20
+21 21
+22 22
+23 23
+24 24
+25 25
+26 26
+27 27
+28 28
+29 29
+30 30
+31 31
+32 32
+33 33
+34 34
+35 35
+36 36
+37 37
+38 38
+39 39
+40 40
+41 41
+42 42
+23 34
+33 34
+37 34
+37 34
+23 34
+33 34
+37 34
+37 34
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+36 17
+36 40
+37 17
+37 40
+41 17
+41 40
+42 17
+42 40
+1 7
+1 22
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+37 17
+37 40
+42 17
+42 40
+42 17
+42 40
+1 11
+1 29
+17 11
+17 29
+39 11
+39 29
+40 11
+40 29
+40 8
+40 25
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+1 4
+1 19
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+7 10
+7 27
+8 10
+8 27
+9 10
+9 27
+12 10
+12 27
+14 10
+14 27
+16 10
+16 27
+17 10
+17 27
+18 10
+18 27
+19 10
+19 27
+21 10
+21 27
+22 10
+22 27
+23 10
+23 27
+24 10
+24 27
+25 10
+25 27
+26 10
+26 27
+28 10
+28 27
+30 10
+30 27
+32 10
+32 27
+33 10
+33 27
+34 10
+34 27
+36 10
+36 27
+37 10
+37 27
+38 10
+38 27
+40 10
+40 27
+41 10
+41 27
+42 10
+42 27
+16 15
+16 35
+38 15
+38 35
+4 14
+4 32
+8 14
+8 32
+19 14
+19 32
+25 14
+25 32
+42 16
+42 38
+42 16
+42 38
+1 16
+1 38
+15 16
+15 38
+18 16
+18 38
+23 16
+23 38
+24 16
+24 38
+28 16
+28 38
+33 16
+33 38
+35 16
+35 38
+36 16
+36 38
+37 16
+37 38
+40 16
+40 38
+41 16
+41 38
+42 16
+42 38
+18 16
+18 38
+23 16
+23 38
+24 16
+24 38
+28 16
+28 38
+33 16
+33 38
+37 16
+37 38
+41 16
+41 38
+42 16
+42 38
+17 16
+17 38
+36 16
+36 38
+39 16
+39 38
+40 16
+40 38
+1 16
+1 38
+6 16
+6 38
+8 16
+8 38
+15 16
+15 38
+17 16
+17 38
+18 16
+18 38
+21 16
+21 38
+23 16
+23 38
+24 16
+24 38
+25 16
+25 38
+28 16
+28 38
+33 16
+33 38
+35 16
+35 38
+36 16
+36 38
+37 16
+37 38
+39 16
+39 38
+40 16
+40 38
+41 16
+41 38
+42 16
+42 38
+40 37
+23 17
+23 40
+28 17
+28 40
+33 17
+33 40
+37 17
+37 40
+1 7
+1 22
+40 23
+1 11
+1 29
+17 11
+17 29
+39 11
+39 29
+40 11
+40 29
+40 8
+40 25
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+1 4
+1 19
+7 4
+7 19
+22 4
+22 19
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+8 10
+8 27
+9 10
+9 27
+14 10
+14 27
+16 10
+16 27
+17 10
+17 27
+19 10
+19 27
+21 10
+21 27
+25 10
+25 27
+26 10
+26 27
+32 10
+32 27
+33 10
+33 27
+34 10
+34 27
+36 10
+36 27
+38 10
+38 27
+40 10
+40 27
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+7 10
+7 27
+14 10
+14 27
+17 10
+17 27
+18 10
+18 27
+19 10
+19 27
+21 10
+21 27
+22 10
+22 27
+23 10
+23 27
+24 10
+24 27
+28 10
+28 27
+32 10
+32 27
+33 10
+33 27
+36 10
+36 27
+37 10
+37 27
+40 10
+40 27
+41 10
+41 27
+42 10
+42 27
+6 10
+6 27
+8 10
+8 27
+14 10
+14 27
+21 10
+21 27
+25 10
+25 27
+32 10
+32 27
+40 10
+40 27
+16 15
+16 35
+38 15
+38 35
+17 16
+17 38
+39 16
+39 38
+40 16
+40 38
+1 16
+1 38
+39 16
+39 38
+42 16
+42 38
+1 16
+1 38
+8 16
+8 38
+15 16
+15 38
+17 16
+17 38
+18 16
+18 38
+23 16
+23 38
+24 16
+24 38
+25 16
+25 38
+28 16
+28 38
+33 16
+33 38
+35 16
+35 38
+36 16
+36 38
+37 16
+37 38
+39 16
+39 38
+40 16
+40 38
+41 16
+41 38
+42 16
+42 38
+1 16
+1 38
+8 16
+8 38
+25 16
+25 38
+1 6
+1 21
+12 6
+12 21
+16 6
+16 21
+17 6
+17 21
+30 6
+30 21
+34 6
+34 21
+38 6
+38 21
+40 6
+40 21
+1 6
+1 21
+17 6
+17 21
+18 6
+18 21
+23 6
+23 21
+24 6
+24 21
+28 6
+28 21
+37 6
+37 21
+40 6
+40 21
+41 6
+41 21
+42 6
+42 21
+40 28
+4 14
+4 32
+8 14
+8 32
+19 14
+19 32
+25 14
+25 32
+40 33
+1 16
+1 38
+15 16
+15 38
+17 16
+17 38
+18 16
+18 38
+23 16
+23 38
+24 16
+24 38
+28 16
+28 38
+33 16
+33 38
+35 16
+35 38
+37 16
+37 38
+40 16
+40 38
+41 16
+41 38
+42 16
+42 38
+1 16
+1 38
+39 16
+39 38
+15 16
+15 38
+17 16
+17 38
+35 16
+35 38
+40 16
+40 38
+1 6
+1 21
+12 6
+12 21
+30 6
+30 21
+33 6
+33 21
+8 6
+8 21
+25 6
+25 21
+33 6
+33 21
+36 6
+36 21
+1 16
+1 38
+8 16
+8 38
+15 16
+15 38
+25 16
+25 38
+35 16
+35 38
+39 16
+39 38
+1 16
+1 38
+1 16
+1 38
+15 16
+15 38
+17 16
+17 38
+35 16
+35 38
+40 16
+40 38
+39 16
+39 38
+39 16
+39 38
+40 7
+40 22
+11 7
+11 22
+13 7
+13 22
+16 7
+16 22
+29 7
+29 22
+31 7
+31 22
+38 7
+38 22
+39 7
+39 22
+39 16
+39 38
+16 6
+16 21
+38 6
+38 21
+39 16
+39 38
+1 11
+1 29
+1 11
+1 29
+17 11
+17 29
+39 11
+39 29
+40 11
+40 29
+40 7
+40 22
+6 7
+6 22
+11 7
+11 22
+13 7
+13 22
+16 7
+16 22
+21 7
+21 22
+29 7
+29 22
+31 7
+31 22
+38 7
+38 22
+39 7
+39 22
+39 16
+39 38
+16 6
+16 21
+38 6
+38 21
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+36 17
+36 40
+37 17
+37 40
+41 17
+41 40
+42 17
+42 40
+11 5
+11 20
+13 5
+13 20
+29 5
+29 20
+31 5
+31 20
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+37 17
+37 40
+42 17
+42 40
+42 17
+42 40
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+7 10
+7 27
+8 10
+8 27
+9 10
+9 27
+12 10
+12 27
+14 10
+14 27
+16 10
+16 27
+17 10
+17 27
+18 10
+18 27
+19 10
+19 27
+21 10
+21 27
+22 10
+22 27
+23 10
+23 27
+24 10
+24 27
+25 10
+25 27
+26 10
+26 27
+28 10
+28 27
+30 10
+30 27
+32 10
+32 27
+33 10
+33 27
+34 10
+34 27
+36 10
+36 27
+37 10
+37 27
+38 10
+38 27
+40 10
+40 27
+41 10
+41 27
+42 10
+42 27
+4 14
+4 32
+8 14
+8 32
+19 14
+19 32
+25 14
+25 32
+40 18
+40 42
+11 5
+11 20
+13 5
+13 20
+29 5
+29 20
+31 5
+31 20
+40 24
+40 41
+40 42
+40 36
+40 36
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+37 17
+37 40
+42 17
+42 40
+42 17
+42 40
+1 2
+1 11
+1 29
+13 11
+13 29
+31 11
+31 29
+40 11
+40 29
+1 16
+1 38
+6 16
+6 38
+21 16
+21 38
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+19 10
+19 27
+21 10
+21 27
+34 10
+34 27
+40 10
+40 27
+4 14
+4 32
+8 14
+8 32
+19 14
+19 32
+25 14
+25 32
+8 9
+8 26
+25 9
+25 26
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+36 17
+36 40
+37 17
+37 40
+41 17
+41 40
+42 17
+42 40
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+36 17
+36 40
+37 17
+37 40
+41 17
+41 40
+42 17
+42 40
+17 16
+17 38
+36 16
+36 38
+40 16
+40 38
+1 2
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+8 9
+8 26
+25 9
+25 26
+1 17
+1 40
+16 17
+16 40
+38 17
+38 40
+16 17
+16 40
+38 17
+38 40
+1 17
+1 40
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+1 11
+1 29
+6 16
+6 38
+21 16
+21 38
+39 16
+39 38
+39 16
+39 38
+36 16
+36 38
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+7 10
+7 27
+8 10
+8 27
+9 10
+9 27
+12 10
+12 27
+14 10
+14 27
+16 10
+16 27
+17 10
+17 27
+18 10
+18 27
+19 10
+19 27
+21 10
+21 27
+22 10
+22 27
+23 10
+23 27
+24 10
+24 27
+25 10
+25 27
+26 10
+26 27
+28 10
+28 27
+30 10
+30 27
+32 10
+32 27
+33 10
+33 27
+34 10
+34 27
+36 10
+36 27
+37 10
+37 27
+38 10
+38 27
+40 10
+40 27
+41 10
+41 27
+42 10
+42 27
+11 5
+11 20
+13 5
+13 20
+29 5
+29 20
+31 5
+31 20
+1 16
+1 38
+6 16
+6 38
+8 16
+8 38
+15 16
+15 38
+17 16
+17 38
+18 16
+18 38
+21 16
+21 38
+23 16
+23 38
+24 16
+24 38
+25 16
+25 38
+28 16
+28 38
+33 16
+33 38
+35 16
+35 38
+36 16
+36 38
+37 16
+37 38
+39 16
+39 38
+40 16
+40 38
+41 16
+41 38
+42 16
+42 38
+36 16
+36 38
+1 10
+1 27
+6 10
+6 27
+9 10
+9 27
+17 10
+17 27
+21 10
+21 27
+26 10
+26 27
+40 10
+40 27
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+7 10
+7 27
+8 10
+8 27
+9 10
+9 27
+12 10
+12 27
+14 10
+14 27
+16 10
+16 27
+17 10
+17 27
+18 10
+18 27
+19 10
+19 27
+21 10
+21 27
+22 10
+22 27
+23 10
+23 27
+24 10
+24 27
+25 10
+25 27
+26 10
+26 27
+28 10
+28 27
+30 10
+30 27
+32 10
+32 27
+33 10
+33 27
+34 10
+34 27
+36 10
+36 27
+37 10
+37 27
+38 10
+38 27
+40 10
+40 27
+41 10
+41 27
+42 10
+42 27
+9 8
+9 25
+26 8
+26 25
+6 10
+6 27
+21 10
+21 27
+6 16
+6 38
+21 16
+21 38
+6 16
+6 38
+21 16
+21 38
+39 16
+39 38
+1 6
+1 21
+1 6
+1 21
+34 6
+34 21
+1 11
+1 29
+38 11
+38 29
+1 16
+1 38
+6 16
+6 38
+15 16
+15 38
+17 16
+17 38
+21 16
+21 38
+35 16
+35 38
+40 16
+40 38
+8 16
+8 38
+25 16
+25 38
+16 17
+16 40
+38 17
+38 40
+42 17
+42 40
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+36 17
+36 40
+37 17
+37 40
+41 17
+41 40
+42 17
+42 40
+9 8
+9 25
+26 8
+26 25
+1 2
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+1 16
+1 38
+11 13
+11 31
+29 13
+29 31
+15 16
+15 38
+35 16
+35 38
+17 16
+17 38
+40 16
+40 38
+36 16
+36 38
+17 16
+17 38
+40 16
+40 38
+15 16
+15 38
+35 16
+35 38
+1 11
+1 29
+1 16
+1 38
+2 16
+2 38
+1 6
+1 21
+8 16
+8 38
+25 16
+25 38
+17 11
+17 29
+40 11
+40 29
+17 16
+17 38
+40 16
+40 38
+1 6
+1 21
+36 17
+36 40
+41 17
+41 40
+18 17
+18 40
+23 17
+23 40
+24 17
+24 40
+28 17
+28 40
+33 17
+33 40
+36 17
+36 40
+37 17
+37 40
+41 17
+41 40
+42 17
+42 40
+1 16
+1 38
+8 16
+8 38
+15 16
+15 38
+17 16
+17 38
+18 16
+18 38
+23 16
+23 38
+24 16
+24 38
+25 16
+25 38
+28 16
+28 38
+33 16
+33 38
+35 16
+35 38
+36 16
+36 38
+37 16
+37 38
+39 16
+39 38
+40 16
+40 38
+41 16
+41 38
+42 16
+42 38
+16 15
+16 35
+38 15
+38 35
+39 15
+39 35
+39 16
+39 38
+1 6
+1 21
+34 6
+34 21
+1 10
+1 27
+6 10
+6 27
+8 10
+8 27
+9 10
+9 27
+16 10
+16 27
+17 10
+17 27
+21 10
+21 27
+25 10
+25 27
+26 10
+26 27
+38 10
+38 27
+40 10
+40 27
+23 34
+33 34
+37 34
+1 10
+1 27
+4 10
+4 27
+6 10
+6 27
+7 10
+7 27
+8 10
+8 27
+9 10
+9 27
+12 10
+12 27
+14 10
+14 27
+16 10
+16 27
+17 10
+17 27
+18 10
+18 27
+19 10
+19 27
+21 10
+21 27
+22 10
+22 27
+23 10
+23 27
+24 10
+24 27
+25 10
+25 27
+26 10
+26 27
+28 10
+28 27
+30 10
+30 27
+32 10
+32 27
+33 10
+33 27
+34 10
+34 27
+36 10
+36 27
+37 10
+37 27
+38 10
+38 27
+40 10
+40 27
+41 10
+41 27
+42 10
+42 27
+1 5
+1 20
+2 5
+2 20
+11 5
+11 20
+12 5
+12 20
+13 5
+13 20
+17 5
+17 20
+29 5
+29 20
+30 5
+30 20
+31 5
+31 20
+38 5
+38 20
+40 5
+40 20
+1 11
+1 29
+8 9
+8 26
+25 9
+25 26
+40 9
+40 26
+1 4
+1 19
+1 12
+1 30
+15 12
+15 30
+35 12
+35 30
+7 12
+7 30
+22 12
+22 30
+1 12
+1 30
+2 12
+2 30
+4 12
+4 30
+6 12
+6 30
+7 12
+7 30
+8 12
+8 30
+9 12
+9 30
+10 12
+10 30
+11 12
+11 30
+13 12
+13 30
+14 12
+14 30
+15 12
+15 30
+16 12
+16 30
+17 12
+17 30
+19 12
+19 30
+21 12
+21 30
+22 12
+22 30
+25 12
+25 30
+26 12
+26 30
+27 12
+27 30
+29 12
+29 30
+31 12
+31 30
+32 12
+32 30
+35 12
+35 30
+38 12
+38 30
+40 12
+40 30
+1 6
+1 21
+17 6
+17 21
+40 6
+40 21
+23 6
+23 21
+24 6
+24 21
+28 6
+28 21
+33 6
+33 21
+34 6
+34 21
+37 6
+37 21
+41 6
+41 21
+18 6
+18 21
+23 6
+23 21
+24 6
+24 21
+28 6
+28 21
+33 6
+33 21
+37 6
+37 21
+40 6
+40 21
+3 1
+1 12
+1 30
+2 12
+2 30
+4 12
+4 30
+6 12
+6 30
+7 12
+7 30
+8 12
+8 30
+10 12
+10 30
+11 12
+11 30
+13 12
+13 30
+15 12
+15 30
+19 12
+19 30
+21 12
+21 30
+22 12
+22 30
+25 12
+25 30
+27 12
+27 30
+29 12
+29 30
+31 12
+31 30
+35 12
+35 30
+8 9
+8 26
+25 9
+25 26
+2 1
+1 3
+1 3
+1 2
+3 2
+3 1
+8 9
+8 26
+25 9
+25 26
+8 14
+8 32
+25 14
+25 32
+6 7
+6 22
+16 7
+16 22
+21 7
+21 22
+38 7
+38 22
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+1 11
+1 29
+8 9
+8 26
+25 9
+25 26
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+6 16
+6 38
+21 16
+21 38
+4 10
+4 27
+6 10
+6 27
+8 10
+8 27
+19 10
+19 27
+21 10
+21 27
+25 10
+25 27
+40 10
+40 27
+1 6
+1 21
+8 6
+8 21
+9 6
+9 21
+18 6
+18 21
+23 6
+23 21
+24 6
+24 21
+25 6
+25 21
+26 6
+26 21
+28 6
+28 21
+37 6
+37 21
+42 6
+42 21
+11 13
+11 31
+29 13
+29 31
+1 6
+1 21
+4 14
+4 32
+9 14
+9 32
+19 14
+19 32
+26 14
+26 32
+4 14
+4 32
+9 14
+9 32
+19 14
+19 32
+26 14
+26 32
+4 14
+4 32
+8 14
+8 32
+9 14
+9 32
+19 14
+19 32
+25 14
+25 32
+26 14
+26 32
+9 14
+9 32
+26 14
+26 32
+40 16
+40 38
+23 17
+23 40
+33 17
+33 40
+37 17
+37 40
+17 16
+17 38
+40 16
+40 38
+1 6
+1 21
+8 9
+8 26
+25 9
+25 26
+1 39
+6 10
+6 27
+21 10
+21 27
+17 16
+17 38
+40 16
+40 38
+1 6
+1 21
+34 6
+34 21
+40 6
+40 21
+36 16
+36 38
+1 11
+1 29
+1 11
+1 29
+42 17
+42 40
+1 17
+1 40
+36 16
+36 38
+17 16
+17 38
+40 16
+40 38
+1 16
+1 38
+36 16
+36 38
+8 9
+8 26
+25 9
+25 26
+1 4
+1 19
+8 14
+8 32
+25 14
+25 32
+6 7
+6 22
+16 7
+16 22
+21 7
+21 22
+38 7
+38 22
+1 11
+1 29
+17 11
+17 29
+38 11
+38 29
+40 11
+40 29
+3 1
diff --git a/regress/usr.bin/tsort/tsort-check b/regress/usr.bin/tsort/tsort-check
index 5c826f86337..b056575c7f9 100644
--- a/regress/usr.bin/tsort/tsort-check
+++ b/regress/usr.bin/tsort/tsort-check
@@ -13,12 +13,13 @@ while(<SORTED>) {
 close(SORTED);
 
 open(PAIRS, shift) or die "No pairs\n";
-undef $/;
-$_ = <PAIRS>;
-close(PAIRS);
-@pairs = split(/\s+/, $_);
-while (@pairs > 0) {
-	($a, $b) = (pop @pairs, pop @pairs);
-	next unless $order{$a} < $order{$b};
-	die "Bad pair $a $b\n";
+while (<PAIRS>) {
+	chomp;
+	push(@pairs, split(/\s+/, $_));
+	while (@pairs >= 2) {
+	    ($a, $b) = (pop @pairs, pop @pairs);
+	    next unless $order{$a} < $order{$b};
+	    die "Bad pair $a $b\n";
+    	}
 }
+close(PAIRS);