1 /* tsort.c - topological sort dependency resolver
2 *
3 * Copyright 2023 Rob Landley <[email protected]>
4 *
5 * See http://opengroup.org/onlinepubs/9699919799/utilities/tsort.html
6
7 USE_TSORT(NEWTOY(tsort, ">1", TOYFLAG_USR|TOYFLAG_BIN))
8
9 config TSORT
10 bool "tsort"
11 default y
12 help
13 usage: tsort [FILE]
14
15 Topological sort dependency resolver.
16
17 Read pairs of input strings indicating before/after dependency relationships
18 and find an ordering that respects all dependencies. On success output each
19 string once to stdout, on failure print error and output cycle pairs.
20 */
21
22 #include "toys.h"
23
24 // Comparison callback for qsort and bsearch: sort by second element
sbse(char ** a,char ** b)25 static int sbse(char **a, char **b)
26 {
27 return strcmp(a[1], b[1]);
28 }
29
30 // Read pairs of "A must go before B" input strings into pair list. Sort pair
31 // list by second element. Loop over list to find pairs where the first string
32 // is not any pair's second string (I.E. nothing depends on this) and remove
33 // each pair from list. For each removed pair, add first string to output
34 // list, and also add second string to output if after removing it no other
35 // pair has it as the second string. Suppress duplicates by checking each
36 // string added to output against the strings added in the last 2 passes
37 // through the pair list. (Because "a b c a" removes "c a" pair after checking
38 // "a b" pair, so removing "a b" next pass would try to output "a" again.)
39 // If a pass through the pair list finds no pairs to remove, what's left is
40 // all circular dependencies.
41
42 // TODO: this treats NUL in input as EOF
do_tsort(int fd,char * name)43 static void do_tsort(int fd, char *name)
44 {
45 off_t plen = 0;
46 char *ss, **pair, *keep[2];
47 long count, // remaining unprocessed pairs
48 len, // total strings in pair list
49 out, // most recently added output (counts down from len)
50 otop, // out at start of this loop over pair[]
51 otop2, // out at start of previous loop over pair[]
52 ii, jj, kk;
53 unsigned long sigh;
54
55 // bsearch()'s first argument is the element to search for,
56 // and sbse() compares the second element of each pair, so to find
57 // which FIRST element matches a second element, we need to feed bsearch
58 // keep-1 but the compiler clutches its pearls about this even when
59 // typecast to (void *), so do the usual LP64 trick to MAKE IT SHUT UP.
60 // (The search function adds 1 to each argument so we never access
61 // memory outside the pair.)
62 sigh = ((unsigned long)keep)-sizeof(*keep);
63
64 // Count input entries in data block read from fd
65 if (!(ss = readfd(fd, 0, &plen))) return;
66 for (ii = len = 0; ii<plen; len++) {
67 while (isspace(ss[ii])) ii++;
68 if (ii==plen) break;
69 while (ii<plen && !isspace(ss[ii])) ii++;
70 }
71 if (len&1) error_exit("bad input (not pairs)");
72
73 // get dependency pair list, null terminate strings, mark depends-on-self
74 pair = xmalloc(len*sizeof(char *));
75 for (ii = len = 0;;) {
76 while (isspace(ss[ii])) ii++;
77 if (ii>=plen) break;
78 pair[len] = ss+ii;
79 while (ii<plen && !isspace(ss[ii])) ii++;
80 if (ii<plen) ss[ii++] = 0;
81 if ((len&1) && !strcmp(pair[len], pair[len-1])) pair[len] = pair[len-1];
82 len++;
83 }
84
85 // sort pair list by 2nd element to binary search "does anyone depend on this"
86 count = (out = otop = otop2 = len)/2;
87 qsort(pair, count, sizeof(keep), (void *)sbse);
88
89 // repeat until pair list empty or nothing added to output list.
90 while (count) {
91 // find/remove/process pairs no other pair depends on
92 for (ii = 0; ii<count; ii++) {
93 // Find pair that depends on itself or no other pair depends on first str
94 memcpy(keep, pair+2*ii, sizeof(keep));
95 // The compiler won't shut up about keep-1 no matter how we typecast it.
96 if (keep[0]!=keep[1] && bsearch((void *)sigh, pair, count, sizeof(keep),
97 (void *)sbse)) continue;
98
99 // Remove from pair list
100 memmove(pair+2*ii, pair+2*(ii+1), (--count-ii)*sizeof(keep));
101 ii--;
102
103 // Drop depends-on-self pairs that any other pair depends on
104 if (keep[0]==keep[1] &&
105 bsearch(keep, pair, count, sizeof(keep),(void *)sbse)) continue;
106
107 // Process removed pair: add unique strings to output list in reverse
108 // order. Output is stored in space at end of list freed up by memmove(),
109 // defers output until we know there are no cycles, and zaps duplicates.
110 for (kk = 0;; kk++) {
111 // duplicate killer checks through previous TWO passes, because
112 // "a b c a" removes "c a" pair after checking "a b" pair, so removing
113 // "a b" next pass tries to output "a" again.
114
115 for (jj = out; jj<otop2; jj++) if (!strcmp(keep[kk], pair[jj])) break;
116 if (jj==otop2) pair[--out] = keep[kk];
117
118 // Print second string too if no other pair depends on it
119 if (kk || bsearch(keep, pair, count, sizeof(keep), (void *)sbse)) break;
120 }
121 }
122 if (out == otop) break;
123 otop2 = otop;
124 otop = out;
125 }
126
127 // If we couldn't empty the list there's a cycle
128 if (count) {
129 error_msg("cycle pairs");
130 while (count--) xprintf("%s %s\n", pair[count*2], pair[count*2+1]);
131 } else while (len>out) xprintf("%s\n", pair[--len]);
132 }
133
tsort_main(void)134 void tsort_main(void)
135 {
136 loopfiles(toys.optargs, do_tsort);
137 }
138