tsort: add new tool1.5.0

8 files changed, 1209 insertions, 2 deletions

diff --git a/.gitignore b/.gitignore
index 17e1976..d519b23 100644
--- a/.gitignore
+++ b/.gitignore
@@ -11,5 +11,6 @@
 /patch
 /pax
 /signify
+/tsort
 /lib/libc/hash/*hl.c
 config.mk
diff --git a/Makefile b/Makefile
index 4cc5547..769f113 100644
--- a/Makefile
+++ b/Makefile
@@ -17,7 +17,8 @@ BIN    = \
 	 md5 \
 	 patch \
 	 pax \
-	 signify
+	 signify \
+	 tsort
 
 LIB    = lib/libbsd.a
 LIBOBJ = \
@@ -74,7 +75,8 @@ MAN = \
 	bin/pax/cpio.1 \
 	bin/pax/pax.1 \
 	bin/pax/tar.1 \
-	usr.bin/signify/signify.1
+	usr.bin/signify/signify.1 \
+	usr.bin/tsort/tsort.1
 
 MANDOCLIBS = ${LIB}
 GREPLIBS   = ${LIB}
@@ -314,6 +316,14 @@ signify: ${SIGNIFYOBJ} ${LIB}
 	${CC} ${LDFLAGS} -o $@ ${SIGNIFYOBJ} ${LIB}
 
 # ------------------------------------------------------------------------------
+# tsort
+TSORTOBJ = \
+	usr.bin/tsort/tsort.o
+BINOBJ += ${TSORTOBJ}
+tsort: ${TSORTOBJ} ${LIB}
+	${CC} ${LDFLAGS} -o $@ ${TSORTOBJ} ${LIB}
+
+# ------------------------------------------------------------------------------
 #  hash helpers
 HELPER  = lib/libc/hash/helper.c
 HASHOBJ = \
diff --git a/usr.bin/tsort/CVS/Entries b/usr.bin/tsort/CVS/Entries
new file mode 100644
index 0000000..528f3f2
--- /dev/null
+++ b/usr.bin/tsort/CVS/Entries
@@ -0,0 +1,4 @@
+/Makefile/1.7/Thu Sep 23 13:56:23 2021//
+/tsort.1/1.24/Thu Sep 23 13:56:23 2021//
+/tsort.c/1.37/Thu Sep 23 13:56:23 2021//
+D
diff --git a/usr.bin/tsort/CVS/Repository b/usr.bin/tsort/CVS/Repository
new file mode 100644
index 0000000..3079881
--- /dev/null
+++ b/usr.bin/tsort/CVS/Repository
@@ -0,0 +1 @@
+src/usr.bin/tsort
diff --git a/usr.bin/tsort/CVS/Root b/usr.bin/tsort/CVS/Root
new file mode 100644
index 0000000..3811072
--- /dev/null
+++ b/usr.bin/tsort/CVS/Root
@@ -0,0 +1 @@
+/cvs
diff --git a/usr.bin/tsort/Makefile b/usr.bin/tsort/Makefile
new file mode 100644
index 0000000..0c57770
--- /dev/null
+++ b/usr.bin/tsort/Makefile
@@ -0,0 +1,9 @@
+#	$OpenBSD: Makefile,v 1.7 2017/07/09 21:23:19 espie Exp $
+
+PROG =	tsort
+
+CDIAGFLAGS = -Wall -Wno-char-subscripts -Wstrict-prototypes -pedantic -W
+DPADD += ${LIBUTIL}
+LDADD += -lutil
+
+.include <bsd.prog.mk>
diff --git a/usr.bin/tsort/tsort.1 b/usr.bin/tsort/tsort.1
new file mode 100644
index 0000000..56f5fc3
--- /dev/null
+++ b/usr.bin/tsort/tsort.1
@@ -0,0 +1,167 @@
+.\"	$OpenBSD: tsort.1,v 1.24 2019/04/23 18:13:11 schwarze Exp $
+.\"	$NetBSD: tsort.1,v 1.6 1996/01/17 20:37:49 mycroft Exp $
+.\"
+.\" Copyright (c) 1990, 1993, 1994
+.\"	The Regents of the University of California.  All rights reserved.
+.\"
+.\" This manual is derived from one contributed to Berkeley by
+.\" Michael Rendell of Memorial University of Newfoundland.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\" 3. Neither the name of the University nor the names of its contributors
+.\"    may be used to endorse or promote products derived from this software
+.\"    without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\"     @(#)tsort.1	8.3 (Berkeley) 4/1/94
+.\"
+.Dd $Mdocdate: April 23 2019 $
+.Dt TSORT 1
+.Os
+.Sh NAME
+.Nm tsort
+.Nd topological sort of a directed graph
+.Sh SYNOPSIS
+.Nm tsort
+.Op Fl flqrvw
+.Op Fl h Ar file
+.Op Ar file
+.Sh DESCRIPTION
+.Nm tsort
+takes a list of pairs of node names representing directed arcs in
+a graph and prints the nodes in topological order on standard output.
+That is, the input describes a partial ordering relation, from which
+.Nm
+computes a total order compatible with this partial ordering.
+.Pp
+Input is taken from the named
+.Ar file ,
+or from standard input if no file
+is given.
+.Pp
+Node names in the input are separated by white space and there must
+be an even number of node names.
+.Pp
+Presence of a node in a graph can be represented by an arc from the node
+to itself.
+This is useful when a node is not connected to any other nodes.
+.Pp
+If the graph contains a cycle (and therefore cannot be properly sorted),
+one of the arcs in the cycle is ignored and the sort continues.
+Cycles are reported on standard error.
+.Pp
+The options are as follows:
+.Bl -tag -width Ds
+.It Fl f
+Resolve ambiguities by selecting nodes based on the order of appearance
+of the first component of the pairs.
+.It Fl h Ar file
+Use
+.Ar file ,
+which holds an ordered list of nodes, to resolve ambiguities.
+In case of duplicates, the first entry is chosen.
+.It Fl l
+Search for and display the longest cycle.
+Can take a very long time, as it may need to solve an NP-complete problem.
+.It Fl q
+Do not display informational messages about cycles.
+This is primarily intended for building libraries, where optimal ordering
+is not critical, and cycles occur often.
+.It Fl r
+Reverse the ordering relation.
+.It Fl v
+Inform on the exact number of edges broken while breaking cycles.
+If a hints file was used, inform on seen nodes absent from that file.
+.It Fl w
+Exit with exit code the number of cycles
+.Nm
+had to break.
+.El
+.Sh EXIT STATUS
+.Ex -std tsort
+.Sh EXAMPLES
+Faced with the input:
+.Bd -literal -offset indent
+a b
+b c
+b d
+d f
+c e
+.Ed
+.Pp
+.Nm
+outputs:
+.Bd -literal -offset indent
+a
+b
+c
+e
+d
+f
+.Ed
+.Pp
+which is one total ordering compatible with the individual relations.
+There is no unicity, another compatible total ordering would be:
+.Bd -literal -offset indent
+a
+b
+c
+d
+e
+f
+.Ed
+.Pp
+.Nm
+is commonly used to analyze dependencies and find a correct build order
+in a static way, whereas
+.Xr make 1
+accomplishes the same task in a dynamic way.
+.Sh SEE ALSO
+.Xr ar 1 ,
+.Xr lorder 1 ,
+.Xr make 1
+.Rs
+.%A Donald E. Knuth
+.%B The Art of Computer Programming
+.%V Vol. 1
+.%P pp. 258\(en268
+.%D 1973
+.Re
+.Sh STANDARDS
+The
+.Nm
+utility is compliant with the
+.St -p1003.1-2008
+specification.
+.Pp
+The flags
+.Op Fl fhlqrvw
+are extensions to that specification.
+.Sh HISTORY
+A
+.Nm
+command appeared in
+.At v7 .
+This
+.Nm tsort
+command was completely rewritten by Marc Espie for
+.Ox ,
+to finally use the well-known optimal algorithms for topological sorting.
diff --git a/usr.bin/tsort/tsort.c b/usr.bin/tsort/tsort.c
new file mode 100644
index 0000000..3e0e1ab
--- /dev/null
+++ b/usr.bin/tsort/tsort.c
@@ -0,0 +1,1014 @@
+/* $OpenBSD: tsort.c,v 1.37 2019/07/11 17:28:32 mestre Exp $ */
+/* ex:ts=8 sw=4:
+ *
+ * Copyright (c) 1999-2004 Marc Espie <espie@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <err.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <ohash.h>
+
+/* The complexity of topological sorting is O(e), where e is the
+ * size of input.  While reading input, vertices have to be identified,
+ * thus add the complexity of e keys retrieval among v keys using
+ * an appropriate data structure.  This program uses open double hashing
+ * for that purpose.  See Knuth for the expected complexity of double
+ * hashing (Brent variation should probably be used if v << e, as a user
+ * option).
+ *
+ * The algorithm used for longest cycle reporting is accurate, but somewhat
+ * expensive.  It may need to build all free paths of the graph (a free
+ * path is a path that never goes twice through the same node), whose
+ * number can be as high as O(2^e).  Usually, the number of free paths is
+ * much smaller though.  This program's author does not believe that a
+ * significantly better worst-case complexity algorithm exists.
+ *
+ * In case of a hints file, the set of minimal nodes is maintained as a
+ * heap.  The resulting complexity is O(e+v log v) for the worst case.
+ * The average should actually be near O(e).
+ *
+ * If the hints file is incomplete, there is some extra complexity incurred
+ * by make_transparent, which does propagate order values to unmarked
+ * nodes. In the worst case, make_transparent is  O(e u),
+ * where u is the number of originally unmarked nodes.
+ * In practice, it is much faster.
+ *
+ * The simple topological sort algorithm detects cycles.  This program
+ * goes further, breaking cycles through the use of simple heuristics.
+ * Each cycle break checks the whole set of nodes, hence if c cycles break
+ * are needed, this is an extra cost of O(c v).
+ *
+ * Possible heuristics are as follows:
+ * - break cycle at node with lowest number of predecessors (default case),
+ * - break longest cycle at node with lowest number of predecessors,
+ * - break cycle at next node from the hints file.
+ *
+ * Except for the hints file case, which sets an explicit constraint on
+ * which cycle to break, those heuristics locally result in the smallest
+ * number of broken edges.
+ *
+ * Those are admittedly greedy strategies, as is the selection of the next
+ * node from the hints file amongst equivalent candidates that is used for
+ * `stable' topological sorting.
+ */
+
+#ifdef __GNUC__
+#define UNUSED	__attribute__((unused))
+#else
+#define UNUSED
+#endif
+
+struct node;
+
+/* The set of arcs from a given node is stored as a linked list.  */
+struct link {
+	struct link *next;
+	struct node *node;
+};
+
+#define NO_ORDER	UINT_MAX
+
+struct node {
+	unsigned int refs;	/* Number of arcs left, coming into this node.
+				 * Note that nodes with a null count can't
+				 * be part of cycles.  */
+	unsigned int order; 	/* Order of nodes according to a hint file.  */
+
+	struct link  *arcs;	/* List of forward arcs.  */
+
+	/* Cycle detection algorithms build a free path of nodes.  */
+	struct node  *from; 	/* Previous node in the current path.  */
+	struct link  *traverse;	/* Next link to traverse when backtracking.  */
+	unsigned int mark;	/* Mark processed nodes in cycle discovery.  */
+
+	char         k[1];	/* Name of this node.  */
+};
+
+#define HASH_START 9
+
+struct array {
+	unsigned int entries;
+	struct node  **t;
+};
+
+static void nodes_init(struct ohash *);
+static struct node *node_lookup(struct ohash *, const char *, const char *);
+static __dead void usage(void);
+static struct node *new_node(const char *, const char *);
+
+static unsigned int read_pairs(FILE *, struct ohash *, int,
+    const char *, unsigned int, int);
+static void split_nodes(struct ohash *, struct array *, struct array *);
+static void make_transparent(struct ohash *);
+static void insert_arc(struct node *, struct node *);
+
+#ifdef DEBUG
+static void dump_node(struct node *);
+static void dump_array(struct array *);
+static void dump_hash(struct ohash *);
+#endif
+static unsigned int read_hints(FILE *, struct ohash *, int,
+    const char *, unsigned int);
+static struct node *find_smallest_node(struct array *);
+static struct node *find_good_cycle_break(struct array *);
+static void print_cycle(struct array *);
+static struct node *find_cycle_from(struct node *, struct array *);
+static struct node *find_predecessor(struct array *, struct node *);
+static unsigned int traverse_node(struct node *, unsigned int, struct array *);
+static struct node *find_longest_cycle(struct array *, struct array *);
+static struct node *find_normal_cycle(struct array *, struct array *);
+
+static void heap_down(struct array *, unsigned int);
+static void heapify(struct array *, int);
+static struct node *dequeue(struct array *);
+static void enqueue(struct array *, struct node *);
+
+
+
+static void *hash_calloc(size_t, size_t, void *);
+static void hash_free(void *, void *);
+static void* entry_alloc(size_t, void *);
+static void *ereallocarray(void *, size_t, size_t);
+static void *emem(void *);
+#define DEBUG_TRAVERSE 0
+static struct ohash_info node_info = {
+	offsetof(struct node, k), NULL, hash_calloc, hash_free, entry_alloc };
+static void parse_args(int, char *[], struct ohash *);
+static int tsort(struct ohash *);
+
+static int 		quiet_flag, long_flag,
+			warn_flag, hints_flag, verbose_flag;
+
+
+int main(int, char *[]);
+
+/***
+ *** Memory handling.
+ ***/
+
+static void *
+emem(void *p)
+{
+	if (p)
+		return p;
+	else
+		errx(1, "Memory exhausted");
+}
+
+static void *
+hash_calloc(size_t n, size_t s, void *u UNUSED)
+{
+	return emem(calloc(n, s));
+}
+
+static void
+hash_free(void *p, void *u UNUSED)
+{
+	free(p);
+}
+
+static void *
+entry_alloc(size_t s, void *u UNUSED)
+{
+	return ereallocarray(NULL, 1, s);
+}
+
+static void *
+ereallocarray(void *p, size_t n, size_t s)
+{
+	return emem(reallocarray(p, n, s));
+}
+
+
+/***
+ *** Hash table.
+ ***/
+
+/* Inserting and finding nodes in the hash structure.
+ * We handle interval strings for efficiency wrt fgetln.  */
+static struct node *
+new_node(const char *start, const char *end)
+{
+	struct node 	*n;
+
+	n = ohash_create_entry(&node_info, start, &end);
+	n->from = NULL;
+	n->arcs = NULL;
+	n->refs = 0;
+	n->mark = 0;
+	n->order = NO_ORDER;
+	n->traverse = NULL;
+	return n;
+}
+
+
+static void
+nodes_init(struct ohash *h)
+{
+	ohash_init(h, HASH_START, &node_info);
+}
+
+static struct node *
+node_lookup(struct ohash *h, const char *start, const char *end)
+{
+	unsigned int	i;
+	struct node *	n;
+
+	i = ohash_qlookupi(h, start, &end);
+
+	n = ohash_find(h, i);
+	if (n == NULL)
+		n = ohash_insert(h, i, new_node(start, end));
+	return n;
+}
+
+#ifdef DEBUG
+static void
+dump_node(struct node *n)
+{
+	struct link 	*l;
+
+	if (n->refs == 0)
+		return;
+	printf("%s (%u/%u): ", n->k, n->order, n->refs);
+	for (l = n->arcs; l != NULL; l = l->next)
+		if (n->refs != 0)
+		printf("%s(%u/%u) ", l->node->k, l->node->order, l->node->refs);
+    	putchar('\n');
+}
+
+static void
+dump_array(struct array *a)
+{
+	unsigned int 	i;
+
+	for (i = 0; i < a->entries; i++)
+		dump_node(a->t[i]);
+}
+
+static void
+dump_hash(struct ohash *h)
+{
+	unsigned int 	i;
+	struct node 	*n;
+
+	for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
+		dump_node(n);
+}
+#endif
+
+/***
+ *** Reading data.
+ ***/
+
+static void
+insert_arc(struct node *a, struct node *b)
+{
+	struct link 	*l;
+
+	/* Check that this arc is not already present.  */
+	for (l = a->arcs; l != NULL; l = l->next) {
+		if (l->node == b)
+			return;
+	}
+	b->refs++;
+	l = ereallocarray(NULL, 1, sizeof(struct link));
+	l->node = b;
+	l->next = a->arcs;
+	a->arcs = l;
+}
+
+static unsigned int
+read_pairs(FILE *f, struct ohash *h, int reverse, const char *name,
+    unsigned int order, int hint)
+{
+	int 		toggle;
+	struct node 	*a;
+	size_t 		size;
+	char 		*str;
+
+	toggle = 1;
+	a = NULL;
+
+	while ((str = fgetln(f, &size)) != NULL) {
+		char *sentinel;
+
+		sentinel = str + size;
+		for (;;) {
+			char *e;
+
+			while (str < sentinel &&
+			    isspace((unsigned char)*str))
+				str++;
+			if (str == sentinel)
+				break;
+			for (e = str;
+			    e < sentinel && !isspace((unsigned char)*e); e++)
+				continue;
+			if (toggle) {
+				a = node_lookup(h, str, e);
+				if (a->order == NO_ORDER && hint)
+					a->order = order++;
+			} else {
+				struct node *b;
+
+				b = node_lookup(h, str, e);
+				assert(a != NULL);
+				if (b != a) {
+					if (reverse)
+						insert_arc(b, a);
+					else
+						insert_arc(a, b);
+				}
+			}
+			toggle = !toggle;
+			str = e;
+		}
+	}
+	if (toggle == 0)
+		errx(1, "odd number of node names in %s", name);
+    	if (!feof(f))
+		err(1, "error reading %s", name);
+	return order;
+}
+
+static unsigned int
+read_hints(FILE *f, struct ohash *h, int quiet, const char *name,
+    unsigned int order)
+{
+	char 		*str;
+	size_t 		size;
+
+	while ((str = fgetln(f, &size)) != NULL) {
+		char *sentinel;
+
+		sentinel = str + size;
+		for (;;) {
+			char *e;
+			struct node *a;
+
+			while (str < sentinel && isspace((unsigned char)*str))
+				str++;
+			if (str == sentinel)
+				break;
+			for (e = str;
+			    e < sentinel && !isspace((unsigned char)*e); e++)
+				continue;
+			a = node_lookup(h, str, e);
+			if (a->order != NO_ORDER) {
+				if (!quiet)
+				    warnx(
+					"duplicate node %s in hints file %s",
+					a->k, name);
+			} else
+				a->order = order++;
+			str = e;
+		}
+	}
+    	if (!feof(f))
+		err(1, "error reading %s", name);
+	return order;
+}
+
+
+/***
+ *** Standard heap handling routines.
+ ***/
+
+static void
+heap_down(struct array *h, unsigned int i)
+{
+	unsigned int 	j;
+	struct node 	*swap;
+
+	for (; (j=2*i+1) < h->entries; i = j) {
+		if (j+1 < h->entries && h->t[j+1]->order < h->t[j]->order)
+		    	j++;
+		if (h->t[i]->order <= h->t[j]->order)
+			break;
+		swap = h->t[i];
+		h->t[i] = h->t[j];
+		h->t[j] = swap;
+	}
+}
+
+static void
+heapify(struct array *h, int verbose)
+{
+	unsigned int 	i;
+
+	for (i = h->entries; i != 0;) {
+		if (h->t[--i]->order == NO_ORDER && verbose)
+			warnx("node %s absent from hints file", h->t[i]->k);
+		heap_down(h, i);
+	}
+}
+
+#define DEQUEUE(h) ( hints_flag ? dequeue(h) : (h)->t[--(h)->entries] )
+
+static struct node *
+dequeue(struct array *h)
+{
+	struct node 	*n;
+
+	if (h->entries == 0)
+		n = NULL;
+	else {
+		n = h->t[0];
+		if (--h->entries != 0) {
+		    h->t[0] = h->t[h->entries];
+		    heap_down(h, 0);
+		}
+	}
+	return n;
+}
+
+#define ENQUEUE(h, n) do {			\
+	if (hints_flag)				\
+		enqueue((h), (n));		\
+	else					\
+		(h)->t[(h)->entries++] = (n);	\
+	} while(0);
+
+static void
+enqueue(struct array *h, struct node *n)
+{
+	unsigned int 	i, j;
+	struct node 	*swap;
+
+	h->t[h->entries++] = n;
+	for (i = h->entries-1; i > 0; i = j) {
+		j = (i-1)/2;
+		if (h->t[j]->order < h->t[i]->order)
+			break;
+		swap = h->t[j];
+		h->t[j] = h->t[i];
+		h->t[i] = swap;
+	}
+}
+
+/* Nodes without order should not hinder direct dependencies.
+ * Iterate until no nodes are left.
+ */
+static void
+make_transparent(struct ohash *hash)
+{
+	struct node 	*n;
+	unsigned int 	i;
+	struct link 	*l;
+	int		adjusted;
+	int		bad;
+	unsigned int	min;
+
+	/* first try to solve complete nodes */
+	do {
+		adjusted = 0;
+		bad = 0;
+		for (n = ohash_first(hash, &i); n != NULL;
+		    n = ohash_next(hash, &i)) {
+			if (n->order == NO_ORDER) {
+				min = NO_ORDER;
+
+				for (l = n->arcs; l != NULL; l = l->next) {
+					/* unsolved node -> delay resolution */
+					if (l->node->order == NO_ORDER) {
+						bad = 1;
+						break;
+					} else if (l->node->order < min)
+						min = l->node->order;
+				}
+				if (min < NO_ORDER && l == NULL) {
+					n->order = min;
+					adjusted = 1;
+				}
+			}
+		}
+
+	} while (adjusted);
+
+	/* then, if incomplete nodes are left, do them */
+	if (bad) do {
+		adjusted = 0;
+		for (n = ohash_first(hash, &i); n != NULL;
+		    n = ohash_next(hash, &i))
+			if (n->order == NO_ORDER)
+				for (l = n->arcs; l != NULL; l = l->next)
+					if (l->node->order < n->order) {
+						n->order = l->node->order;
+						adjusted = 1;
+					}
+	} while (adjusted);
+}
+
+
+/***
+ *** Search through hash array for nodes.
+ ***/
+
+/* Split nodes into unrefed nodes/live nodes.  */
+static void
+split_nodes(struct ohash *hash, struct array *heap, struct array *remaining)
+{
+
+	struct node *n;
+	unsigned int i;
+
+	heap->t = ereallocarray(NULL, ohash_entries(hash),
+	    sizeof(struct node *));
+	remaining->t = ereallocarray(NULL, ohash_entries(hash),
+	    sizeof(struct node *));
+	heap->entries = 0;
+	remaining->entries = 0;
+
+	for (n = ohash_first(hash, &i); n != NULL; n = ohash_next(hash, &i)) {
+		if (n->refs == 0)
+			heap->t[heap->entries++] = n;
+		else
+			remaining->t[remaining->entries++] = n;
+	}
+}
+
+/* Good point to break a cycle: live node with as few refs as possible. */
+static struct node *
+find_good_cycle_break(struct array *h)
+{
+	unsigned int 	i;
+	unsigned int 	best;
+	struct node 	*u;
+
+	best = UINT_MAX;
+	u = NULL;
+
+	assert(h->entries != 0);
+	for (i = 0; i < h->entries; i++) {
+		struct node *n = h->t[i];
+		/* No need to look further. */
+		if (n->refs == 1)
+			return n;
+		if (n->refs != 0 && n->refs < best) {
+			best = n->refs;
+			u = n;
+		}
+	}
+	assert(u != NULL);
+	return u;
+}
+
+/*  Retrieve the node with the smallest order.  */
+static struct node *
+find_smallest_node(struct array *h)
+{
+	unsigned int 	i;
+	unsigned int 	best;
+	struct node 	*u;
+
+	best = UINT_MAX;
+	u = NULL;
+
+	assert(h->entries != 0);
+	for (i = 0; i < h->entries; i++) {
+		struct node *n = h->t[i];
+		if (n->refs != 0 && n->order < best) {
+			best = n->order;
+			u = n;
+		}
+	}
+	assert(u != NULL);
+	return u;
+}
+
+
+/***
+ *** Graph algorithms.
+ ***/
+
+/* Explore the nodes reachable from i to find a cycle, store it in c.
+ * This may fail.  */
+static struct node *
+find_cycle_from(struct node *i, struct array *c)
+{
+	struct node 	*n;
+
+	n = i;
+	/* XXX Previous cycle findings may have left this pointer non-null.  */
+	i->from = NULL;
+
+	for (;;) {
+		/* Note that all marks are reversed before this code exits.  */
+		n->mark = 1;
+		if (n->traverse)
+			n->traverse = n->traverse->next;
+		else
+			n->traverse = n->arcs;
+		/* Skip over dead nodes.  */
+		while (n->traverse && n->traverse->node->refs == 0)
+			n->traverse = n->traverse->next;
+		if (n->traverse) {
+			struct node *go = n->traverse->node;
+
+			if (go->mark) {
+				c->entries = 0;
+				for (; n != NULL && n != go; n = n->from) {
+					c->t[c->entries++] = n;
+					n->mark = 0;
+				}
+				for (; n != NULL; n = n->from)
+					n->mark = 0;
+				c->t[c->entries++] = go;
+				return go;
+			} else {
+			    go->from = n;
+			    n = go;
+			}
+		} else {
+			n->mark = 0;
+			n = n->from;
+			if (n == NULL)
+				return NULL;
+		}
+	}
+}
+
+/* Find a live predecessor of node n.  This is a slow routine, as it needs
+ * to go through the whole array, but it is not needed often.
+ */
+static struct node *
+find_predecessor(struct array *a, struct node *n)
+{
+	unsigned int i;
+
+	for (i = 0; i < a->entries; i++) {
+		struct node *m;
+
+		m = a->t[i];
+		if (m->refs != 0) {
+			struct link *l;
+
+			for (l = m->arcs; l != NULL; l = l->next)
+				if (l->node == n)
+					return m;
+		}
+	}
+	assert(1 == 0);
+	return NULL;
+}
+
+/* Traverse all strongly connected components reachable from node n.
+   Start numbering them at o. Return the maximum order reached.
+   Update the largest cycle found so far.
+ */
+static unsigned int
+traverse_node(struct node *n, unsigned int o, struct array *c)
+{
+	unsigned int 	min, max;
+
+	n->from = NULL;
+	min = o;
+	max = ++o;
+
+	for (;;) {
+		n->mark = o;
+		if (DEBUG_TRAVERSE)
+			printf("%s(%u) ", n->k, n->mark);
+		/* Find next arc to explore.  */
+		if (n->traverse)
+			n->traverse = n->traverse->next;
+		else
+			n->traverse = n->arcs;
+		/* Skip over dead nodes.  */
+		while (n->traverse && n->traverse->node->refs == 0)
+			n->traverse = n->traverse->next;
+		/* If arc left.  */
+		if (n->traverse) {
+			struct node 	*go;
+
+			go = n->traverse->node;
+			/* Optimisation: if go->mark < min, we already
+			 * visited this strongly-connected component in
+			 * a previous pass.  Hence, this can yield no new
+			 * cycle.  */
+
+			/* Not part of the current path: go for it.  */
+			if (go->mark == 0 || go->mark == min) {
+				go->from = n;
+				n = go;
+				o++;
+				if (o > max)
+					max = o;
+			/* Part of the current path: check cycle length.  */
+			} else if (go->mark > min) {
+				if (DEBUG_TRAVERSE)
+					printf("%d\n", o - go->mark + 1);
+				if (o - go->mark + 1 > c->entries) {
+					struct node *t;
+					unsigned int i;
+
+					c->entries = o - go->mark + 1;
+					i = 0;
+					c->t[i++] = go;
+					for (t = n; t != go; t = t->from)
+						c->t[i++] = t;
+				}
+			}
+
+		/* No arc left: backtrack.  */
+		} else {
+			n->mark = min;
+			n = n->from;
+			if (!n)
+				return max;
+			o--;
+		}
+	}
+}
+
+static void
+print_cycle(struct array *c)
+{
+	unsigned int 	i;
+
+	/* Printing in reverse order, since cycle discoveries finds reverse
+	 * edges.  */
+	for (i = c->entries; i != 0;) {
+		i--;
+		warnx("%s", c->t[i]->k);
+	}
+}
+
+static struct node *
+find_longest_cycle(struct array *h, struct array *c)
+{
+	unsigned int 	i;
+	unsigned int 	o;
+	unsigned int 	best;
+	struct node 	*n;
+	static int 	notfirst = 0;
+
+	assert(h->entries != 0);
+
+	/* No cycle found yet.  */
+	c->entries = 0;
+
+	/* Reset the set of marks, except the first time around.  */
+	if (notfirst) {
+		for (i = 0; i < h->entries; i++)
+			h->t[i]->mark = 0;
+	} else
+		notfirst = 1;
+
+	o = 0;
+
+	/* Traverse the array.  Each unmarked, live node heralds a
+	 * new set of strongly connected components.  */
+	for (i = 0; i < h->entries; i++) {
+		n = h->t[i];
+		if (n->refs != 0 && n->mark == 0) {
+			/* Each call to traverse_node uses a separate
+			 * interval of numbers to mark nodes.  */
+			o++;
+			o = traverse_node(n, o, c);
+		}
+	}
+
+	assert(c->entries != 0);
+	n = c->t[0];
+	best = n->refs;
+	for (i = 0; i < c->entries; i++) {
+		if (c->t[i]->refs < best) {
+			n = c->t[i];
+			best = n->refs;
+		}
+	}
+	return n;
+}
+
+static struct node *
+find_normal_cycle(struct array *h, struct array *c)
+{
+	struct node *b, *n;
+
+	if (hints_flag)
+		n = find_smallest_node(h);
+	else
+		n = find_good_cycle_break(h);
+	while ((b = find_cycle_from(n, c)) == NULL)
+		n = find_predecessor(h, n);
+	return b;
+}
+
+
+#define plural(n) ((n) > 1 ? "s" : "")
+
+static void 
+parse_args(int argc, char *argv[], struct ohash *pairs)
+{
+	int c;
+	unsigned int	order;
+	int reverse_flag;
+	const char **files;
+	int i, j;
+
+	i = 0;
+
+	reverse_flag = quiet_flag = long_flag =
+		warn_flag = hints_flag = verbose_flag = 0;
+	/* argc is good enough, as we start at argv[1] */
+	files = ereallocarray(NULL, argc, sizeof (char *));
+	while ((c = getopt(argc, argv, "h:flqrvw")) != -1) {
+		switch(c) {
+		case 'h':
+			files[i++] = optarg;
+			hints_flag = 1;
+			break;
+			/*FALLTHRU*/
+		case 'f':
+			hints_flag = 2;
+			break;
+		case 'l':
+			long_flag = 1;
+			break;
+		case 'q':
+			quiet_flag = 1;
+			break;
+		case 'r':
+			reverse_flag = 1;
+			break;
+		case 'v':
+			verbose_flag = 1;
+			break;
+		case 'w':
+			warn_flag = 1;
+			break;
+		default:
+			usage();
+		}
+	}
+
+	argc -= optind;
+	argv += optind;
+
+	switch(argc) {
+	case 1:
+		files[i++] = argv[0];
+		break;
+	case 0:
+		break;
+	default:
+		usage();
+	}
+
+	files[i] = NULL;
+
+	nodes_init(pairs);
+	order = 0;
+		
+	for (j = 0; j != i-argc; j++) {
+		FILE *f;
+
+		f = fopen(files[j], "r");
+		if (f == NULL)
+			err(1, "Can't open hint file %s", files[i]);
+		order = read_hints(f, pairs, quiet_flag, files[i], order);
+		fclose(f);
+    	}
+	free(files);
+
+	if (argc == 1) {
+		FILE *f;
+
+		f = fopen(argv[0], "r");
+		if (f == NULL)
+			err(1, "Can't open file %s", argv[0]);
+		order = read_pairs(f, pairs, reverse_flag, argv[0], order,
+		    hints_flag == 2);
+		fclose(f);
+	} else {
+		order = read_pairs(stdin, pairs, reverse_flag, "stdin",
+		    order, hints_flag == 2);
+	}
+}
+
+static int
+tsort(struct ohash *pairs)
+{
+	    struct array 	aux;	/* Unrefed nodes/cycle reporting.  */
+	    struct array	remaining;
+	    unsigned int	broken_arcs, broken_cycles;
+	    unsigned int	left;
+
+	    broken_arcs = 0;
+	    broken_cycles = 0;
+
+	    if (hints_flag)
+		    make_transparent(pairs);
+	    split_nodes(pairs, &aux, &remaining);
+	    ohash_delete(pairs);
+
+	    if (hints_flag)
+		    heapify(&aux, verbose_flag);
+
+	    left = remaining.entries + aux.entries;
+	    while (left != 0) {
+
+		    /* Standard topological sort.  */
+		    while (aux.entries) {
+			    struct link *l;
+			    struct node *n;
+
+			    n = DEQUEUE(&aux);
+			    printf("%s\n", n->k);
+			    left--;
+			    /* We can't free nodes, as we don't know which
+			     * entry we can remove in the hash table.  We
+			     * rely on refs == 0 to recognize live nodes.
+			     * Decrease ref count of live nodes, enter new
+			     * candidates into the unrefed list.  */
+			    for (l = n->arcs; l != NULL; l = l->next)
+				    if (l->node->refs != 0 &&
+					--l->node->refs == 0) {
+					    ENQUEUE(&aux, l->node);
+				    }
+		    }
+		    /* There are still cycles to break.  */
+		    if (left != 0) {
+			    struct node *n;
+
+			    broken_cycles++;
+			    /* XXX Simple cycle detection and long cycle
+			     * detection are mutually exclusive.  */
+
+			    if (long_flag)
+				    n = find_longest_cycle(&remaining, &aux);
+			    else
+				    n = find_normal_cycle(&remaining, &aux);
+
+			    if (!quiet_flag) {
+				    warnx("cycle in data");
+				    print_cycle(&aux);
+			    }
+
+			    if (verbose_flag)
+				    warnx("%u edge%s broken", n->refs,
+					plural(n->refs));
+			    broken_arcs += n->refs;
+			    n->refs = 0;
+			    /* Reinitialization, cycle reporting uses aux.  */
+			    aux.t[0] = n;
+			    aux.entries = 1;
+		    }
+	    }
+	    if (verbose_flag && broken_cycles != 0)
+		    warnx("%u cycle%s broken, for a total of %u edge%s",
+			broken_cycles, plural(broken_cycles),
+			broken_arcs, plural(broken_arcs));
+	    if (warn_flag)
+		    return (broken_cycles < 256 ? broken_cycles : 255);
+	    else
+		    return (0);
+}
+
+int
+main(int argc, char *argv[])
+{
+	struct ohash 	pairs;
+
+	if (pledge("stdio rpath", NULL) == -1)
+		err(1, "pledge");
+
+	parse_args(argc, argv, &pairs);
+
+	if (pledge("stdio", NULL) == -1)
+		err(1, "pledge");
+
+	return tsort(&pairs);
+}
+
+
+extern char *__progname;
+
+static void
+usage(void)
+{
+	fprintf(stderr, "Usage: %s [-flqrvw] [-h file] [file]\n", __progname);
+	exit(1);
+}