src/tsort.c

   1 /* tsort - topological sort.
   2    Copyright (C) 1998-2024 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Mark Kettenis <kettenis@phys.uva.nl>.  */
  18
  19 /* The topological sort is done according to Algorithm T (Topological
  20    sort) in Donald E. Knuth, The Art of Computer Programming, Volume
  21    1/Fundamental Algorithms, page 262.  */
  22
  23 #include <config.h>
  24
  25 #include <sys/types.h>
  26
  27 #include "system.h"
  28 #include "assure.h"
  29 #include "long-options.h"
  30 #include "fadvise.h"
  31 #include "readtokens.h"
  32 #include "stdio--.h"
  33 #include "quote.h"
  34
  35 /* The official name of this program (e.g., no 'g' prefix).  */
  36 #define PROGRAM_NAME "tsort"
  37
  38 #define AUTHORS proper_name ("Mark Kettenis")
  39
  40 /* Token delimiters when reading from a file.  */
  41 #define DELIM " \t\n"
  42
  43 /* Members of the list of successors.  */
  44 struct successor
  45 {
  46   struct item *suc;
  47   struct successor *next;
  48 };
  49
  50 /* Each string is held in memory as the head of a list of successors.  */
  51 struct item
  52 {
  53   char const *str;
  54   struct item *left, *right;
  55   signed char balance; /* -1, 0, or +1 */
  56   bool printed;
  57   size_t count;
  58   struct item *qlink;
  59   struct successor *top;
  60 };
  61
  62 /* The head of the sorted list.  */
  63 static struct item *head = nullptr;
  64
  65 /* The tail of the list of 'zeros', strings that have no predecessors.  */
  66 static struct item *zeros = nullptr;
  67
  68 /* Used for loop detection.  */
  69 static struct item *loop = nullptr;
  70
  71 /* The number of strings to sort.  */
  72 static size_t n_strings = 0;
  73
  74 void
  75 usage (int status)
  76 {
  77   if (status != EXIT_SUCCESS)
  78     emit_try_help ();
  79   else
  80     {
  81       printf (_("\
  82 Usage: %s [OPTION] [FILE]\n\
  83 Write totally ordered list consistent with the partial ordering in FILE.\n\
  84 "), program_name);
  85
  86       emit_stdin_note ();
  87
  88       fputs (_("\
  89 \n\
  90 "), stdout);
  91       fputs (HELP_OPTION_DESCRIPTION, stdout);
  92       fputs (VERSION_OPTION_DESCRIPTION, stdout);
  93       emit_ancillary_info (PROGRAM_NAME);
  94     }
  95
  96   exit (status);
  97 }
  98
  99 /* Create a new item/node for STR.  */
 100 static struct item *
 101 new_item (char const *str)
 102 {
 103   /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^).  */
 104   struct item *k = xzalloc (sizeof *k);
 105   if (str)
 106     k->str = xstrdup (str);
 107   return k;
 108 }
 109
 110 /* Search binary tree rooted at *ROOT for STR.  Allocate a new tree if
 111    *ROOT is null.  Insert a node/item for STR if not found.  Return
 112    the node/item found/created for STR.
 113
 114    This is done according to Algorithm A (Balanced tree search and
 115    insertion) in Donald E. Knuth, The Art of Computer Programming,
 116    Volume 3/Searching and Sorting, pages 455--457.  */
 117
 118 static struct item *
 119 search_item (struct item *root, char const *str)
 120 {
 121   struct item *p, *q, *r, *s, *t;
 122   int a;
 123
 124   /* Make sure the tree is not empty, since that is what the algorithm
 125      below expects.  */
 126   if (root->right == nullptr)
 127     return (root->right = new_item (str));
 128
 129   /* A1. Initialize.  */
 130   t = root;
 131   s = p = root->right;
 132
 133   while (true)
 134     {
 135       /* A2. Compare.  */
 136       a = strcmp (str, p->str);
 137       if (a == 0)
 138         return p;
 139
 140       /* A3 & A4.  Move left & right.  */
 141       if (a < 0)
 142         q = p->left;
 143       else
 144         q = p->right;
 145
 146       if (q == nullptr)
 147         {
 148           /* A5. Insert.  */
 149           q = new_item (str);
 150
 151           /* A3 & A4.  (continued).  */
 152           if (a < 0)
 153             p->left = q;
 154           else
 155             p->right = q;
 156
 157           /* A6. Adjust balance factors.  */
 158           a = strcmp (str, s->str);
 159           if (a < 0)
 160             {
 161               r = p = s->left;
 162               a = -1;
 163             }
 164           else
 165             {
 166               affirm (0 < a);
 167               r = p = s->right;
 168               a = 1;
 169             }
 170
 171           while (p != q)
 172             {
 173               int cmp = strcmp (str, p->str);
 174               if (cmp < 0)
 175                 {
 176                   p->balance = -1;
 177                   p = p->left;
 178                 }
 179               else
 180                 {
 181                   affirm (0 < cmp);
 182                   p->balance = 1;
 183                   p = p->right;
 184                 }
 185             }
 186
 187           /* A7. Balancing act.  */
 188           if (s->balance == 0 || s->balance == -a)
 189             {
 190               s->balance += a;
 191               return q;
 192             }
 193
 194           if (r->balance == a)
 195             {
 196               /* A8. Single Rotation.  */
 197               p = r;
 198               if (a < 0)
 199                 {
 200                   s->left = r->right;
 201                   r->right = s;
 202                 }
 203               else
 204                 {
 205                   s->right = r->left;
 206                   r->left = s;
 207                 }
 208               s->balance = r->balance = 0;
 209             }
 210           else
 211             {
 212               /* A9. Double rotation.  */
 213               if (a < 0)
 214                 {
 215                   p = r->right;
 216                   r->right = p->left;
 217                   p->left = r;
 218                   s->left = p->right;
 219                   p->right = s;
 220                 }
 221               else
 222                 {
 223                   p = r->left;
 224                   r->left = p->right;
 225                   p->right = r;
 226                   s->right = p->left;
 227                   p->left = s;
 228                 }
 229
 230               s->balance = 0;
 231               r->balance = 0;
 232               if (p->balance == a)
 233                 s->balance = -a;
 234               else if (p->balance == -a)
 235                 r->balance = a;
 236               p->balance = 0;
 237             }
 238
 239           /* A10. Finishing touch.  */
 240           if (s == t->right)
 241             t->right = p;
 242           else
 243             t->left = p;
 244
 245           return q;
 246         }
 247
 248       /* A3 & A4.  (continued).  */
 249       if (q->balance)
 250         {
 251           t = p;
 252           s = q;
 253         }
 254
 255       p = q;
 256     }
 257
 258   /* NOTREACHED */
 259 }
 260
 261 /* Record the fact that J precedes K.  */
 262
 263 static void
 264 record_relation (struct item *j, struct item *k)
 265 {
 266   struct successor *p;
 267
 268   if (!STREQ (j->str, k->str))
 269     {
 270       k->count++;
 271       p = xmalloc (sizeof *p);
 272       p->suc = k;
 273       p->next = j->top;
 274       j->top = p;
 275     }
 276 }
 277
 278 static bool
 279 count_items (MAYBE_UNUSED struct item *unused)
 280 {
 281   n_strings++;
 282   return false;
 283 }
 284
 285 static bool
 286 scan_zeros (struct item *k)
 287 {
 288   /* Ignore strings that have already been printed.  */
 289   if (k->count == 0 && !k->printed)
 290     {
 291       if (head == nullptr)
 292         head = k;
 293       else
 294         zeros->qlink = k;
 295
 296       zeros = k;
 297     }
 298
 299   return false;
 300 }
 301
 302 /* Try to detect the loop.  If we have detected that K is part of a
 303    loop, print the loop on standard error, remove a relation to break
 304    the loop, and return true.
 305
 306    The loop detection strategy is as follows: Realize that what we're
 307    dealing with is essentially a directed graph.  If we find an item
 308    that is part of a graph that contains a cycle we traverse the graph
 309    in backwards direction.  In general there is no unique way to do
 310    this, but that is no problem.  If we encounter an item that we have
 311    encountered before, we know that we've found a cycle.  All we have
 312    to do now is retrace our steps, printing out the items until we
 313    encounter that item again.  (This is not necessarily the item that
 314    we started from originally.)  Since the order in which the items
 315    are stored in the tree is not related to the specified partial
 316    ordering, we may need to walk the tree several times before the
 317    loop has completely been constructed.  If the loop was found, the
 318    global variable LOOP will be null.  */
 319
 320 static bool
 321 detect_loop (struct item *k)
 322 {
 323   if (k->count > 0)
 324     {
 325       /* K does not have to be part of a cycle.  It is however part of
 326          a graph that contains a cycle.  */
 327
 328       if (loop == nullptr)
 329         /* Start traversing the graph at K.  */
 330         loop = k;
 331       else
 332         {
 333           struct successor **p = &k->top;
 334
 335           while (*p)
 336             {
 337               if ((*p)->suc == loop)
 338                 {
 339                   if (k->qlink)
 340                     {
 341                       /* We have found a loop.  Retrace our steps.  */
 342                       while (loop)
 343                         {
 344                           struct item *tmp = loop->qlink;
 345
 346                           error (0, 0, "%s", (loop->str));
 347
 348                           /* Until we encounter K again.  */
 349                           if (loop == k)
 350                             {
 351                               /* Remove relation.  */
 352                               struct successor *s = *p;
 353                               s->suc->count--;
 354                               *p = s->next;
 355                               IF_LINT (free (s));
 356                               break;
 357                             }
 358
 359                           /* Tidy things up since we might have to
 360                              detect another loop.  */
 361                           loop->qlink = nullptr;
 362                           loop = tmp;
 363                         }
 364
 365                       while (loop)
 366                         {
 367                           struct item *tmp = loop->qlink;
 368
 369                           loop->qlink = nullptr;
 370                           loop = tmp;
 371                         }
 372
 373                       /* Since we have found the loop, stop walking
 374                          the tree.  */
 375                       return true;
 376                     }
 377                   else
 378                     {
 379                       k->qlink = loop;
 380                       loop = k;
 381                       break;
 382                     }
 383                 }
 384
 385               p = &(*p)->next;
 386             }
 387         }
 388     }
 389
 390   return false;
 391 }
 392
 393 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
 394    Stop when ACTION returns true.  */
 395
 396 static bool
 397 recurse_tree (struct item *root, bool (*action) (struct item *))
 398 {
 399   if (root->left == nullptr && root->right == nullptr)
 400     return (*action) (root);
 401   else
 402     {
 403       if (root->left != nullptr)
 404         if (recurse_tree (root->left, action))
 405           return true;
 406       if ((*action) (root))
 407         return true;
 408       if (root->right != nullptr)
 409         if (recurse_tree (root->right, action))
 410           return true;
 411     }
 412
 413   return false;
 414 }
 415
 416 /* Walk the tree specified by the head ROOT, calling ACTION for
 417    each node.  */
 418
 419 static void
 420 walk_tree (struct item *root, bool (*action) (struct item *))
 421 {
 422   if (root->right)
 423     recurse_tree (root->right, action);
 424 }
 425
 426 /* Do a topological sort on FILE.  Exit with appropriate exit status.  */
 427
 428 static _Noreturn void
 429 tsort (char const *file)
 430 {
 431   bool ok = true;
 432   struct item *j = nullptr;
 433   struct item *k = nullptr;
 434   token_buffer tokenbuffer;
 435   bool is_stdin = STREQ (file, "-");
 436
 437   /* Initialize the head of the tree holding the strings we're sorting.  */
 438   struct item *root = new_item (nullptr);
 439
 440   if (!is_stdin && ! freopen (file, "r", stdin))
 441     error (EXIT_FAILURE, errno, "%s", quotef (file));
 442
 443   fadvise (stdin, FADVISE_SEQUENTIAL);
 444
 445   init_tokenbuffer (&tokenbuffer);
 446
 447   while (true)
 448     {
 449       /* T2. Next Relation.  */
 450       size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
 451       if (len == (size_t) -1)
 452         {
 453           if (ferror (stdin))
 454             error (EXIT_FAILURE, errno, _("%s: read error"), quotef (file));
 455           break;
 456         }
 457
 458       affirm (len != 0);
 459
 460       k = search_item (root, tokenbuffer.buffer);
 461       if (j)
 462         {
 463           /* T3. Record the relation.  */
 464           record_relation (j, k);
 465           k = nullptr;
 466         }
 467
 468       j = k;
 469     }
 470
 471   if (k != nullptr)
 472     error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
 473            quotef (file));
 474
 475   /* T1. Initialize (N <- n).  */
 476   walk_tree (root, count_items);
 477
 478   while (n_strings > 0)
 479     {
 480       /* T4. Scan for zeros.  */
 481       walk_tree (root, scan_zeros);
 482
 483       while (head)
 484         {
 485           struct successor *p = head->top;
 486
 487           /* T5. Output front of queue.  */
 488           puts (head->str);
 489           head->printed = true;
 490           n_strings--;
 491
 492           /* T6. Erase relations.  */
 493           while (p)
 494             {
 495               p->suc->count--;
 496               if (p->suc->count == 0)
 497                 {
 498                   zeros->qlink = p->suc;
 499                   zeros = p->suc;
 500                 }
 501
 502               p = p->next;
 503             }
 504
 505           /* T7. Remove from queue.  */
 506           head = head->qlink;
 507         }
 508
 509       /* T8.  End of process.  */
 510       if (n_strings > 0)
 511         {
 512           /* The input contains a loop.  */
 513           error (0, 0, _("%s: input contains a loop:"), quotef (file));
 514           ok = false;
 515
 516           /* Print the loop and remove a relation to break it.  */
 517           do
 518             walk_tree (root, detect_loop);
 519           while (loop);
 520         }
 521     }
 522
 523   if (fclose (stdin) != 0)
 524     error (EXIT_FAILURE, errno, "%s",
 525            is_stdin ? _("standard input") : quotef (file));
 526
 527   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 528 }
 529
 530 int
 531 main (int argc, char **argv)
 532 {
 533   initialize_main (&argc, &argv);
 534   set_program_name (argv[0]);
 535   setlocale (LC_ALL, "");
 536   bindtextdomain (PACKAGE, LOCALEDIR);
 537   textdomain (PACKAGE);
 538
 539   atexit (close_stdout);
 540
 541   parse_gnu_standard_options_only (argc, argv, PROGRAM_NAME, PACKAGE_NAME,
 542                                    Version, true, usage, AUTHORS,
 543                                    (char const *) nullptr);
 544
 545   if (1 < argc - optind)
 546     {
 547       error (0, 0, _("extra operand %s"), quote (argv[optind + 1]));
 548       usage (EXIT_FAILURE);
 549     }
 550
 551   tsort (optind == argc ? "-" : argv[optind]);
 552 }