sbin/rcorder/rcorder.c

   1 # if 0
   2 /*      $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $        */
   3 #endif
   4
   5 /*-
   6  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   7  *
   8  * Copyright (c) 1998, 1999 Matthew R. Green
   9  * All rights reserved.
  10  * Copyright (c) 1998
  11  *      Perry E. Metzger.  All rights reserved.
  12  * Copyright (c) 2020
  13  *     Boris N. Lytochkin. All rights reserved.
  14  *
  15  * Redistribution and use in source and binary forms, with or without
  16  * modification, are permitted provided that the following conditions
  17  * are met:
  18  * 1. Redistributions of source code must retain the above copyright
  19  *    notice, this list of conditions and the following disclaimer.
  20  * 2. Redistributions in binary form must reproduce the above copyright
  21  *    notice, this list of conditions and the following disclaimer in the
  22  *    documentation and/or other materials provided with the distribution.
  23  * 3. All advertising materials mentioning features or use of this software
  24  *    must display the following acknowledgement:
  25  *      This product includes software developed for the NetBSD Project
  26  *      by Perry E. Metzger.
  27  * 4. The name of the author may not be used to endorse or promote products
  28  *    derived from this software without specific prior written permission.
  29  *
  30  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  31  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  32  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  33  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  34  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  35  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  39  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  */
  41
  42 #include <sys/types.h>
  43 __FBSDID("$FreeBSD$");
  44
  45 #include <sys/stat.h>
  46
  47 #include <err.h>
  48 #include <stdio.h>
  49 #include <libutil.h>
  50 #include <stdlib.h>
  51 #include <string.h>
  52 #include <unistd.h>
  53 #include <libgen.h>
  54 #include <stdbool.h>
  55
  56 #include "ealloc.h"
  57 #include "sprite.h"
  58 #include "hash.h"
  59
  60 #ifdef DEBUG
  61 static int debug = 0;
  62 # define        DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
  63 #else
  64 # define        DPRINTF(args)
  65 #endif
  66
  67 #define REQUIRE_STR     "# REQUIRE:"
  68 #define REQUIRE_LEN     (sizeof(REQUIRE_STR) - 1)
  69 #define REQUIRES_STR    "# REQUIRES:"
  70 #define REQUIRES_LEN    (sizeof(REQUIRES_STR) - 1)
  71 #define PROVIDE_STR     "# PROVIDE:"
  72 #define PROVIDE_LEN     (sizeof(PROVIDE_STR) - 1)
  73 #define PROVIDES_STR    "# PROVIDES:"
  74 #define PROVIDES_LEN    (sizeof(PROVIDES_STR) - 1)
  75 #define BEFORE_STR      "# BEFORE:"
  76 #define BEFORE_LEN      (sizeof(BEFORE_STR) - 1)
  77 #define KEYWORD_STR     "# KEYWORD:"
  78 #define KEYWORD_LEN     (sizeof(KEYWORD_STR) - 1)
  79 #define KEYWORDS_STR    "# KEYWORDS:"
  80 #define KEYWORDS_LEN    (sizeof(KEYWORDS_STR) - 1)
  81
  82 #define FAKE_PROV_NAME  "fake_prov_"
  83
  84 static int exit_code;
  85 static int file_count;
  86 static char **file_list;
  87
  88 #define TRUE 1
  89 #define FALSE 0
  90 typedef bool flag;
  91 #define SET TRUE
  92 #define RESET FALSE
  93
  94 static flag do_graphviz = false;
  95 static flag do_parallel = false;
  96
  97 static Hash_Table provide_hash_s, *provide_hash;
  98
  99 typedef struct provnode provnode;
 100 typedef struct filenode filenode;
 101 typedef struct f_provnode f_provnode;
 102 typedef struct f_reqnode f_reqnode;
 103 typedef struct strnodelist strnodelist;
 104
 105 struct provnode {
 106         flag            head;
 107         flag            in_progress;
 108         int             sequence;
 109         filenode        *fnode;
 110         provnode        *next, *last;
 111 };
 112
 113 struct f_provnode {
 114         provnode        *pnode;
 115         Hash_Entry      *entry;
 116         f_provnode      *next;
 117 };
 118
 119 struct f_reqnode {
 120         Hash_Entry      *entry;
 121         f_reqnode       *next;
 122 };
 123
 124 struct strnodelist {
 125         filenode        *node;
 126         strnodelist     *next;
 127         char            s[1];
 128 };
 129
 130 struct filenode {
 131         char            *filename;
 132         flag            in_progress;
 133         filenode        *next, *last;
 134         f_reqnode       *req_list;
 135         f_provnode      *prov_list;
 136         strnodelist     *keyword_list;
 137         int             issues_count;
 138         int             sequence;
 139 };
 140
 141 static filenode fn_head_s, *fn_head, **fn_seqlist;
 142 static int max_sequence = 0;
 143
 144 static strnodelist *bl_list;
 145 static strnodelist *keep_list;
 146 static strnodelist *skip_list;
 147
 148 static void do_file(filenode *fnode, strnodelist *);
 149 static void strnode_add(strnodelist **, char *, filenode *);
 150 static int skip_ok(filenode *fnode);
 151 static int keep_ok(filenode *fnode);
 152 static char *generate_loop_for_req(strnodelist *, provnode *, filenode *);
 153 static void satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *);
 154 static void crunch_file(char *);
 155 static void parse_require(filenode *, char *);
 156 static void parse_provide(filenode *, char *);
 157 static void parse_before(filenode *, char *);
 158 static void parse_keywords(filenode *, char *);
 159 static filenode *filenode_new(char *);
 160 static void add_require(filenode *, char *);
 161 static void add_provide(filenode *, char *);
 162 static void add_before(filenode *, char *);
 163 static void add_keyword(filenode *, char *);
 164 static void insert_before(void);
 165 static Hash_Entry *make_fake_provision(filenode *);
 166 static void crunch_all_files(void);
 167 static void initialize(void);
 168 static void generate_graphviz_header(void);
 169 static void generate_graphviz_footer(void);
 170 static void generate_graphviz_file_links(Hash_Entry *, filenode *);
 171 static void generate_graphviz_providers(void);
 172 static inline int is_fake_prov(const char *);
 173 static int sequence_cmp(const void *, const void *);
 174 static void generate_ordering(void);
 175
 176 int
 177 main(int argc, char *argv[])
 178 {
 179         int ch;
 180
 181         while ((ch = getopt(argc, argv, "dgk:ps:")) != -1)
 182                 switch (ch) {
 183                 case 'd':
 184 #ifdef DEBUG
 185                         debug = 1;
 186 #else
 187                         warnx("debugging not compiled in, -d ignored");
 188 #endif
 189                         break;
 190                 case 'g':
 191                         do_graphviz = true;
 192                         break;
 193                 case 'k':
 194                         strnode_add(&keep_list, optarg, 0);
 195                         break;
 196                 case 'p':
 197                         do_parallel = true;
 198                         break;
 199                 case 's':
 200                         strnode_add(&skip_list, optarg, 0);
 201                         break;
 202                 default:
 203                         /* XXX should crunch it? */
 204                         break;
 205                 }
 206         argc -= optind;
 207         argv += optind;
 208
 209         file_count = argc;
 210         file_list = argv;
 211
 212         DPRINTF((stderr, "parse_args\n"));
 213         initialize();
 214         DPRINTF((stderr, "initialize\n"));
 215         generate_graphviz_header();
 216         crunch_all_files();
 217         DPRINTF((stderr, "crunch_all_files\n"));
 218         generate_graphviz_providers();
 219         generate_ordering();
 220         DPRINTF((stderr, "generate_ordering\n"));
 221         generate_graphviz_footer();
 222
 223         exit(exit_code);
 224 }
 225
 226 /*
 227  * initialise various variables.
 228  */
 229 static void
 230 initialize(void)
 231 {
 232
 233         fn_head = &fn_head_s;
 234
 235         provide_hash = &provide_hash_s;
 236         Hash_InitTable(provide_hash, file_count);
 237 }
 238
 239 /* generic function to insert a new strnodelist element */
 240 static void
 241 strnode_add(strnodelist **listp, char *s, filenode *fnode)
 242 {
 243         strnodelist *ent;
 244
 245         ent = emalloc(sizeof *ent + strlen(s));
 246         ent->node = fnode;
 247         strcpy(ent->s, s);
 248         ent->next = *listp;
 249         *listp = ent;
 250 }
 251
 252 /*
 253  * below are the functions that deal with creating the lists
 254  * from the filename's given dependencies and provisions
 255  * in each of these files.  no ordering or checking is done here.
 256  */
 257
 258 /*
 259  * we have a new filename, create a new filenode structure.
 260  * fill in the bits, and put it in the filenode linked list
 261  */
 262 static filenode *
 263 filenode_new(char *filename)
 264 {
 265         filenode *temp;
 266
 267         temp = emalloc(sizeof(*temp));
 268         memset(temp, 0, sizeof(*temp));
 269         temp->filename = estrdup(filename);
 270         temp->req_list = NULL;
 271         temp->prov_list = NULL;
 272         temp->keyword_list = NULL;
 273         temp->in_progress = RESET;
 274         /*
 275          * link the filenode into the list of filenodes.
 276          * note that the double linking means we can delete a
 277          * filenode without searching for where it belongs.
 278          */
 279         temp->next = fn_head->next;
 280         if (temp->next != NULL)
 281                 temp->next->last = temp;
 282         temp->last = fn_head;
 283         fn_head->next = temp;
 284         return (temp);
 285 }
 286
 287 /*
 288  * add a requirement to a filenode.
 289  */
 290 static void
 291 add_require(filenode *fnode, char *s)
 292 {
 293         Hash_Entry *entry;
 294         f_reqnode *rnode;
 295         int new;
 296
 297         entry = Hash_CreateEntry(provide_hash, s, &new);
 298         if (new)
 299                 Hash_SetValue(entry, NULL);
 300         rnode = emalloc(sizeof(*rnode));
 301         rnode->entry = entry;
 302         rnode->next = fnode->req_list;
 303         fnode->req_list = rnode;
 304 }
 305
 306 /*
 307  * add a provision to a filenode.  if this provision doesn't
 308  * have a head node, create one here.
 309  */
 310 static void
 311 add_provide(filenode *fnode, char *s)
 312 {
 313         Hash_Entry *entry;
 314         f_provnode *f_pnode;
 315         provnode *pnode, *head;
 316         int new;
 317
 318         entry = Hash_CreateEntry(provide_hash, s, &new);
 319         head = Hash_GetValue(entry);
 320
 321         /* create a head node if necessary. */
 322         if (head == NULL) {
 323                 head = emalloc(sizeof(*head));
 324                 head->head = SET;
 325                 head->in_progress = RESET;
 326                 head->fnode = NULL;
 327                 head->sequence = 0;
 328                 head->last = head->next = NULL;
 329                 Hash_SetValue(entry, head);
 330         }
 331 #if 0
 332         /*
 333          * Don't warn about this.  We want to be able to support
 334          * scripts that do two complex things:
 335          *
 336          *      - Two independent scripts which both provide the
 337          *        same thing.  Both scripts must be executed in
 338          *        any order to meet the barrier.  An example:
 339          *
 340          *              Script 1:
 341          *
 342          *                      PROVIDE: mail
 343          *                      REQUIRE: LOGIN
 344          *
 345          *              Script 2:
 346          *
 347          *                      PROVIDE: mail
 348          *                      REQUIRE: LOGIN
 349          *
 350          *      - Two interdependent scripts which both provide the
 351          *        same thing.  Both scripts must be executed in
 352          *        graph order to meet the barrier.  An example:
 353          *
 354          *              Script 1:
 355          *
 356          *                      PROVIDE: nameservice dnscache
 357          *                      REQUIRE: SERVERS
 358          *
 359          *              Script 2:
 360          *
 361          *                      PROVIDE: nameservice nscd
 362          *                      REQUIRE: dnscache
 363          */
 364         else if (new == 0) {
 365                 warnx("file `%s' provides `%s'.", fnode->filename, s);
 366                 warnx("\tpreviously seen in `%s'.",
 367                     head->next->fnode->filename);
 368         }
 369 #endif
 370
 371         pnode = emalloc(sizeof(*pnode));
 372         pnode->head = RESET;
 373         pnode->in_progress = RESET;
 374         pnode->fnode = fnode;
 375         pnode->next = head->next;
 376         pnode->last = head;
 377         head->next = pnode;
 378         if (pnode->next != NULL)
 379                 pnode->next->last = pnode;
 380
 381         f_pnode = emalloc(sizeof(*f_pnode));
 382         f_pnode->pnode = pnode;
 383         f_pnode->entry = entry;
 384         f_pnode->next = fnode->prov_list;
 385         fnode->prov_list = f_pnode;
 386 }
 387
 388 /*
 389  * put the BEFORE: lines to a list and handle them later.
 390  */
 391 static void
 392 add_before(filenode *fnode, char *s)
 393 {
 394         strnodelist *bf_ent;
 395
 396         bf_ent = emalloc(sizeof *bf_ent + strlen(s));
 397         bf_ent->node = fnode;
 398         strcpy(bf_ent->s, s);
 399         bf_ent->next = bl_list;
 400         bl_list = bf_ent;
 401 }
 402
 403 /*
 404  * add a key to a filenode.
 405  */
 406 static void
 407 add_keyword(filenode *fnode, char *s)
 408 {
 409
 410         strnode_add(&fnode->keyword_list, s, fnode);
 411 }
 412
 413 /*
 414  * loop over the rest of a REQUIRE line, giving each word to
 415  * add_require() to do the real work.
 416  */
 417 static void
 418 parse_require(filenode *node, char *buffer)
 419 {
 420         char *s;
 421
 422         while ((s = strsep(&buffer, " \t\n")) != NULL)
 423                 if (*s != '\0')
 424                         add_require(node, s);
 425 }
 426
 427 /*
 428  * loop over the rest of a PROVIDE line, giving each word to
 429  * add_provide() to do the real work.
 430  */
 431 static void
 432 parse_provide(filenode *node, char *buffer)
 433 {
 434         char *s;
 435
 436         while ((s = strsep(&buffer, " \t\n")) != NULL)
 437                 if (*s != '\0')
 438                         add_provide(node, s);
 439 }
 440
 441 /*
 442  * loop over the rest of a BEFORE line, giving each word to
 443  * add_before() to do the real work.
 444  */
 445 static void
 446 parse_before(filenode *node, char *buffer)
 447 {
 448         char *s;
 449
 450         while ((s = strsep(&buffer, " \t\n")) != NULL)
 451                 if (*s != '\0')
 452                         add_before(node, s);
 453 }
 454
 455 /*
 456  * loop over the rest of a KEYWORD line, giving each word to
 457  * add_keyword() to do the real work.
 458  */
 459 static void
 460 parse_keywords(filenode *node, char *buffer)
 461 {
 462         char *s;
 463
 464         while ((s = strsep(&buffer, " \t\n")) != NULL)
 465                 if (*s != '\0')
 466                         add_keyword(node, s);
 467 }
 468
 469 /*
 470  * given a file name, create a filenode for it, read in lines looking
 471  * for provision and requirement lines, building the graphs as needed.
 472  */
 473 static void
 474 crunch_file(char *filename)
 475 {
 476         FILE *fp;
 477         char *buf;
 478         int require_flag, provide_flag, before_flag, keywords_flag;
 479         enum { BEFORE_PARSING, PARSING, PARSING_DONE } state;
 480         filenode *node;
 481         char delims[3] = { '\\', '\\', '\0' };
 482         struct stat st;
 483
 484         if ((fp = fopen(filename, "r")) == NULL) {
 485                 warn("could not open %s", filename);
 486                 return;
 487         }
 488
 489         if (fstat(fileno(fp), &st) == -1) {
 490                 warn("could not stat %s", filename);
 491                 fclose(fp);
 492                 return;
 493         }
 494
 495         if (!S_ISREG(st.st_mode)) {
 496 #if 0
 497                 warnx("%s is not a file", filename);
 498 #endif
 499                 fclose(fp);
 500                 return;
 501         }
 502
 503         node = filenode_new(filename);
 504
 505         /*
 506          * we don't care about length, line number, don't want # for comments,
 507          * and have no flags.
 508          */
 509         for (state = BEFORE_PARSING; state != PARSING_DONE &&
 510             (buf = fparseln(fp, NULL, NULL, delims, 0)) != NULL; free(buf)) {
 511                 require_flag = provide_flag = before_flag = keywords_flag = 0;
 512                 if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0)
 513                         require_flag = REQUIRE_LEN;
 514                 else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0)
 515                         require_flag = REQUIRES_LEN;
 516                 else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0)
 517                         provide_flag = PROVIDE_LEN;
 518                 else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0)
 519                         provide_flag = PROVIDES_LEN;
 520                 else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0)
 521                         before_flag = BEFORE_LEN;
 522                 else if (strncmp(KEYWORD_STR, buf, KEYWORD_LEN) == 0)
 523                         keywords_flag = KEYWORD_LEN;
 524                 else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0)
 525                         keywords_flag = KEYWORDS_LEN;
 526                 else {
 527                         if (state == PARSING)
 528                                 state = PARSING_DONE;
 529                         continue;
 530                 }
 531
 532                 state = PARSING;
 533                 if (require_flag)
 534                         parse_require(node, buf + require_flag);
 535                 else if (provide_flag)
 536                         parse_provide(node, buf + provide_flag);
 537                 else if (before_flag)
 538                         parse_before(node, buf + before_flag);
 539                 else if (keywords_flag)
 540                         parse_keywords(node, buf + keywords_flag);
 541         }
 542         fclose(fp);
 543 }
 544
 545 static Hash_Entry *
 546 make_fake_provision(filenode *node)
 547 {
 548         Hash_Entry *entry;
 549         f_provnode *f_pnode;
 550         provnode *head, *pnode;
 551         static  int i = 0;
 552         int     new;
 553         char buffer[30];
 554
 555         do {
 556                 snprintf(buffer, sizeof buffer, FAKE_PROV_NAME "%08d", i++);
 557                 entry = Hash_CreateEntry(provide_hash, buffer, &new);
 558         } while (new == 0);
 559         head = emalloc(sizeof(*head));
 560         head->head = SET;
 561         head->in_progress = RESET;
 562         head->fnode = NULL;
 563         head->last = head->next = NULL;
 564         Hash_SetValue(entry, head);
 565
 566         pnode = emalloc(sizeof(*pnode));
 567         pnode->head = RESET;
 568         pnode->in_progress = RESET;
 569         pnode->fnode = node;
 570         pnode->next = head->next;
 571         pnode->last = head;
 572         head->next = pnode;
 573         if (pnode->next != NULL)
 574                 pnode->next->last = pnode;
 575
 576         f_pnode = emalloc(sizeof(*f_pnode));
 577         f_pnode->entry = entry;
 578         f_pnode->pnode = pnode;
 579         f_pnode->next = node->prov_list;
 580         node->prov_list = f_pnode;
 581
 582         return (entry);
 583 }
 584
 585 /*
 586  * go through the BEFORE list, inserting requirements into the graph(s)
 587  * as required.  in the before list, for each entry B, we have a file F
 588  * and a string S.  we create a "fake" provision (P) that F provides.
 589  * for each entry in the provision list for S, add a requirement to
 590  * that provisions filenode for P.
 591  */
 592 static void
 593 insert_before(void)
 594 {
 595         Hash_Entry *entry, *fake_prov_entry;
 596         provnode *pnode;
 597         f_reqnode *rnode;
 598         strnodelist *bl;
 599         int new;
 600
 601         while (bl_list != NULL) {
 602                 bl = bl_list->next;
 603
 604                 fake_prov_entry = make_fake_provision(bl_list->node);
 605
 606                 entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
 607                 if (new == 1)
 608                         warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);
 609
 610                 if (new == 1 && do_graphviz == true)
 611                         generate_graphviz_file_links(
 612                             Hash_FindEntry(provide_hash, bl_list->s),
 613                             bl_list->node);
 614
 615                 for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
 616                         if (pnode->head)
 617                                 continue;
 618
 619                         rnode = emalloc(sizeof(*rnode));
 620                         rnode->entry = fake_prov_entry;
 621                         rnode->next = pnode->fnode->req_list;
 622                         pnode->fnode->req_list = rnode;
 623                 }
 624
 625                 free(bl_list);
 626                 bl_list = bl;
 627         }
 628 }
 629
 630 /*
 631  * loop over all the files calling crunch_file() on them to do the
 632  * real work.  after we have built all the nodes, insert the BEFORE:
 633  * lines into graph(s).
 634  */
 635 static void
 636 crunch_all_files(void)
 637 {
 638         int i;
 639
 640         for (i = 0; i < file_count; i++)
 641                 crunch_file(file_list[i]);
 642         insert_before();
 643 }
 644
 645 static inline int
 646 is_fake_prov(const char *name)
 647 {
 648
 649         return (name == strstr(name, FAKE_PROV_NAME));
 650 }
 651
 652 /* loop though provide list of vnode drawing all non-fake dependencies */
 653 static void
 654 generate_graphviz_file_links(Hash_Entry *entry, filenode *fnode)
 655 {
 656         char *dep_name, *fname;
 657         provnode *head;
 658         f_provnode *fpnode, *rfpnode;
 659         int is_before = 0;
 660
 661         dep_name = Hash_GetKey(entry);
 662         if (is_fake_prov(dep_name))
 663                 is_before = 1;
 664         head = Hash_GetValue(entry);
 665
 666         for (fpnode = fnode->prov_list; fpnode && fpnode->entry;
 667             fpnode = fpnode->next) {
 668                 fname = Hash_GetKey(fpnode->entry);
 669                 if (is_fake_prov(fname))
 670                         continue;
 671                 rfpnode = NULL;
 672                 do {
 673                         if (rfpnode)
 674                                 dep_name = Hash_GetKey(rfpnode->entry);
 675                         else
 676                                 dep_name = Hash_GetKey(entry);
 677
 678                         if (!is_fake_prov(dep_name)) {
 679                                 printf("\"%s\" -> \"%s\" [%s%s];\n",
 680                                     fname, dep_name,
 681                                     /* edge style */
 682                                     (is_before ? "style=dashed" : "style=solid"),
 683                                     /* circular dep? */
 684                                     ((head == NULL ||
 685                                     (head->next && head->in_progress == SET)) ?
 686                                     ", color=red, penwidth=4" : ""));
 687                                 if (rfpnode == NULL)
 688                                         break;
 689                         }
 690                         /* dependency is solved already */
 691                         if (head == NULL || head->next == NULL)
 692                                 break;
 693
 694                         if (rfpnode == NULL)
 695                                 rfpnode = head->next->fnode->prov_list;
 696                         else
 697                                 rfpnode = rfpnode->next;
 698                 } while (rfpnode);
 699         }
 700 }
 701
 702 /*
 703  * Walk the stack, find the looping point and generate traceback.
 704  * NULL is returned on failure, otherwize pointer to a buffer holding
 705  * text representation is returned, caller must run free(3) for the
 706  * pointer.
 707  */
 708 static char *
 709 generate_loop_for_req(strnodelist *stack_tail, provnode *head,
 710     filenode *fnode)
 711 {
 712         provnode *pnode;
 713         strnodelist *stack_ptr, *loop_entry;
 714         char *buf, **revstack;
 715         size_t bufsize;
 716         int i, stack_depth;
 717
 718         loop_entry = NULL;
 719         /* fast forward stack to the component that is required now */
 720         for (pnode = head->next; pnode; pnode = pnode->next) {
 721                 if (loop_entry)
 722                         break;
 723                 stack_depth = 0;
 724                 for (stack_ptr = stack_tail; stack_ptr;
 725                     stack_ptr = stack_ptr->next) {
 726                         stack_depth++;
 727                         if (stack_ptr->node == pnode->fnode) {
 728                                 loop_entry = stack_ptr;
 729                                 break;
 730                         }
 731                 }
 732         }
 733
 734         if (loop_entry == NULL)
 735                 return (NULL);
 736
 737         stack_depth += 2; /* fnode + loop_entry */
 738         revstack = emalloc(sizeof(char *) * stack_depth);
 739         bzero(revstack, (sizeof(char *) * stack_depth));
 740
 741         /* reverse stack and estimate buffer size to allocate */
 742         bufsize = 1; /* tralining \0 */
 743
 744         revstack[stack_depth - 1] = loop_entry->node->filename;
 745         bufsize += strlen(revstack[stack_depth - 1]);
 746
 747         revstack[stack_depth - 2] = fnode->filename;
 748         bufsize += strlen(revstack[stack_depth - 2]);
 749         fnode->issues_count++;
 750
 751         stack_ptr = stack_tail;
 752         for (i = stack_depth - 3; i >= 0; i--) {
 753                 revstack[i] = stack_ptr->node->filename;
 754                 stack_ptr->node->issues_count++;
 755                 stack_ptr = stack_ptr->next;
 756                 bufsize += strlen(revstack[i]);
 757         }
 758         bufsize += strlen(" -> ") * (stack_depth - 1);
 759
 760         buf = emalloc(bufsize);
 761         bzero(buf, bufsize);
 762
 763         for (i = 0; i < stack_depth; i++) {
 764                 strlcat(buf, revstack[i], bufsize);
 765                 if (i < stack_depth - 1)
 766                         strlcat(buf, " -> ", bufsize);
 767         }
 768
 769         free(revstack);
 770         return (buf);
 771 }
 772 /*
 773  * below are the functions that traverse the graphs we have built
 774  * finding out the desired ordering, printing each file in turn.
 775  * if missing requirements, or cyclic graphs are detected, a
 776  * warning will be issued, and we will continue on..
 777  */
 778
 779 /*
 780  * given a requirement node (in a filename) we attempt to satisfy it.
 781  * we do some sanity checking first, to ensure that we have providers,
 782  * aren't already satisfied and aren't already being satisfied (ie,
 783  * cyclic).  if we pass all this, we loop over the provision list
 784  * calling do_file() (enter recursion) for each filenode in this
 785  * provision.
 786  */
 787 static void
 788 satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *stack_ptr)
 789 {
 790         Hash_Entry *entry;
 791         provnode *head;
 792         strnodelist stack_item;
 793         char *buf;
 794
 795         entry = rnode->entry;
 796         head = Hash_GetValue(entry);
 797
 798         if (do_graphviz == true)
 799                 generate_graphviz_file_links(entry, fnode);
 800
 801         if (head == NULL) {
 802                 warnx("requirement `%s' in file `%s' has no providers.",
 803                     Hash_GetKey(entry), fnode->filename);
 804                 exit_code = 1;
 805                 return;
 806         }
 807
 808         /* return if the requirement is already satisfied. */
 809         if (head->next == NULL)
 810                 return;
 811
 812         /*
 813          * if list is marked as in progress,
 814          *      print that there is a circular dependency on it and abort
 815          */
 816         if (head->in_progress == SET) {
 817                 exit_code = 1;
 818                 buf = generate_loop_for_req(stack_ptr, head,
 819                     fnode);
 820
 821                 if (buf == NULL) {
 822                         warnx("Circular dependency on provision `%s' in "
 823                             "file `%s' (tracing has failed).",
 824                             Hash_GetKey(entry), fnode->filename);
 825                         return;
 826                 }
 827
 828                 warnx("Circular dependency on provision `%s': %s.",
 829                     Hash_GetKey(entry), buf);
 830                 free(buf);
 831                 return;
 832         }
 833
 834         head->in_progress = SET;
 835
 836         stack_item.next = stack_ptr;
 837         stack_item.node = fnode;
 838
 839         /*
 840          * while provision_list is not empty
 841          *      do_file(first_member_of(provision_list));
 842          */
 843         while (head->next != NULL)
 844                 do_file(head->next->fnode, &stack_item);
 845 }
 846
 847 static int
 848 skip_ok(filenode *fnode)
 849 {
 850         strnodelist *s;
 851         strnodelist *k;
 852
 853         for (s = skip_list; s; s = s->next)
 854                 for (k = fnode->keyword_list; k; k = k->next)
 855                         if (strcmp(k->s, s->s) == 0)
 856                                 return (0);
 857
 858         return (1);
 859 }
 860
 861 static int
 862 keep_ok(filenode *fnode)
 863 {
 864         strnodelist *s;
 865         strnodelist *k;
 866
 867         for (s = keep_list; s; s = s->next)
 868                 for (k = fnode->keyword_list; k; k = k->next)
 869                         if (strcmp(k->s, s->s) == 0)
 870                                 return (1);
 871
 872         /* an empty keep_list means every one */
 873         return (!keep_list);
 874 }
 875
 876 /*
 877  * given a filenode, we ensure we are not a cyclic graph.  if this
 878  * is ok, we loop over the filenodes requirements, calling satisfy_req()
 879  * for each of them.. once we have done this, remove this filenode
 880  * from each provision table, as we are now done.
 881  *
 882  * NOTE: do_file() is called recursively from several places and cannot
 883  * safely free() anything related to items that may be recursed on.
 884  * Circular dependencies will cause problems if we do.
 885  */
 886 static void
 887 do_file(filenode *fnode, strnodelist *stack_ptr)
 888 {
 889         f_reqnode *r;
 890         f_provnode *p, *p_tmp;
 891         provnode *pnode, *head;
 892         int was_set;
 893         char *dep_name;
 894
 895         DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
 896
 897         /*
 898          * if fnode is marked as in progress,
 899          *       print that fnode; is circularly depended upon and abort.
 900          */
 901         if (fnode->in_progress == SET) {
 902                 warnx("Circular dependency on file `%s'.",
 903                         fnode->filename);
 904                 was_set = exit_code = 1;
 905         } else
 906                 was_set = 0;
 907
 908         /* mark fnode */
 909         fnode->in_progress = SET;
 910
 911         /*
 912          * for each requirement of fnode -> r
 913          *      satisfy_req(r, filename)
 914          */
 915         r = fnode->req_list;
 916         fnode->sequence = 0;
 917         while (r != NULL) {
 918                 satisfy_req(r, fnode, stack_ptr);
 919                 /* find sequence number where all requirements are satisfied */
 920                 head = Hash_GetValue(r->entry);
 921                 if (head && head->sequence > fnode->sequence)
 922                         fnode->sequence = head->sequence;
 923                 r = r->next;
 924         }
 925         fnode->req_list = NULL;
 926         fnode->sequence++;
 927
 928         /* if we've seen issues with this file - put it to the tail */
 929         if (fnode->issues_count)
 930                 fnode->sequence = max_sequence + 1;
 931
 932         if (max_sequence < fnode->sequence)
 933                 max_sequence = fnode->sequence;
 934
 935         /*
 936          * for each provision of fnode -> p
 937          *      remove fnode from provision list for p in hash table
 938          */
 939         p = fnode->prov_list;
 940         while (p != NULL) {
 941                 /* mark all troublemakers on graphviz */
 942                 if (do_graphviz == true && fnode->issues_count) {
 943                         dep_name = Hash_GetKey(p->entry);
 944                         if (!is_fake_prov(dep_name))
 945                                 printf("\"%s\" [ color=red, penwidth=4 ];\n",
 946                                     dep_name);
 947                 }
 948
 949                 /* update sequence when provided requirements are satisfied */
 950                 head = Hash_GetValue(p->entry);
 951                 if (head->sequence < fnode->sequence)
 952                         head->sequence = fnode->sequence;
 953
 954                 p_tmp = p;
 955                 pnode = p->pnode;
 956                 if (pnode->next != NULL) {
 957                         pnode->next->last = pnode->last;
 958                 }
 959                 if (pnode->last != NULL) {
 960                         pnode->last->next = pnode->next;
 961                 }
 962                 free(pnode);
 963                 p = p->next;
 964                 free(p_tmp);
 965         }
 966         fnode->prov_list = NULL;
 967
 968         /* do_it(fnode) */
 969         DPRINTF((stderr, "next do: "));
 970
 971         /* if we were already in progress, don't print again */
 972         if (do_graphviz != true && was_set == 0 && skip_ok(fnode) &&
 973             keep_ok(fnode)) {
 974                 *fn_seqlist = fnode;
 975                 fn_seqlist++;
 976         }
 977
 978         if (fnode->next != NULL) {
 979                 fnode->next->last = fnode->last;
 980         }
 981         if (fnode->last != NULL) {
 982                 fnode->last->next = fnode->next;
 983         }
 984
 985         if (fnode->issues_count)
 986                 warnx("`%s' was seen in circular dependencies for %d times.",
 987                     fnode->filename, fnode->issues_count);
 988
 989         DPRINTF((stderr, "nuking %s\n", fnode->filename));
 990 }
 991
 992 static void
 993 generate_graphviz_header(void)
 994 {
 995
 996         if (do_graphviz != true)
 997                 return;
 998
 999         printf("digraph rcorder {\n"
1000             "rankdir=\"BT\";\n"
1001             "node [style=rounded, shape=record];\n"
1002             "graph [overlap = false];\n");
1003 }
1004
1005 static void
1006 generate_graphviz_footer(void)
1007 {
1008
1009         if (do_graphviz == true)
1010                 printf("}\n");
1011 }
1012
1013 static void
1014 generate_graphviz_providers(void)
1015 {
1016         Hash_Entry *entry;
1017         Hash_Search psearch;
1018         provnode *head, *pnode;
1019         char *dep_name;
1020
1021         if (do_graphviz != true)
1022                 return;
1023
1024         entry = Hash_EnumFirst(provide_hash, &psearch);
1025         if (entry == NULL)
1026                 return;
1027
1028         do {
1029                 dep_name = Hash_GetKey(entry);
1030                 if (is_fake_prov(dep_name))
1031                         continue;
1032                 head = Hash_GetValue(entry);
1033                 /* no providers for this requirement */
1034                 if (head == NULL || head->next == NULL) {
1035                         printf("\"%s\" [label=\"{ %s | ENOENT }\", "
1036                             "style=\"rounded,filled\", color=red];\n",
1037                             dep_name, dep_name);
1038                         continue;
1039                 }
1040                 /* one PROVIDE word for one file that matches */
1041                 if (head->next->next == NULL &&
1042                     strcmp(dep_name,
1043                     basename(head->next->fnode->filename)) == 0) {
1044                         continue;
1045                 }
1046                 printf("\"%s\" [label=\"{ %s | ", dep_name, dep_name);
1047                 for (pnode = head->next; pnode; pnode = pnode->next)
1048                         printf("%s\\n", basename(pnode->fnode->filename));
1049
1050                 printf("}\"];\n");
1051         } while (NULL != (entry = Hash_EnumNext(&psearch)));
1052 }
1053
1054 static int
1055 sequence_cmp(const void *a, const void *b)
1056 {
1057         const filenode *fna = *((const filenode * const *)a);
1058         const filenode *fnb = *((const filenode * const *)b);
1059         int left, right;
1060
1061         /* push phantom files to the end */
1062         if (fna == NULL || fnb == NULL)
1063                 return ((fna < fnb) - (fna > fnb));
1064
1065         left =  fna->sequence;
1066         right = fnb->sequence;
1067
1068         return ((left > right) - (left < right));
1069 }
1070
1071 static void
1072 generate_ordering(void)
1073 {
1074         filenode **seqlist, **psl;
1075         int last_seq = 0;
1076
1077         /* Prepare order buffer, use an additional one as a list terminator */
1078         seqlist = emalloc(sizeof(filenode *) * (file_count + 1));
1079         bzero(seqlist, sizeof(filenode *) * (file_count + 1));
1080         fn_seqlist = seqlist;
1081
1082         /*
1083          * while there remain undone files{f},
1084          *      pick an arbitrary f, and do_file(f)
1085          * Note that the first file in the file list is perfectly
1086          * arbitrary, and easy to find, so we use that.
1087          */
1088
1089         /*
1090          * N.B.: the file nodes "self delete" after they execute, so
1091          * after each iteration of the loop, the head will be pointing
1092          * to something totally different. The loop ends up being
1093          * executed only once for every strongly connected set of
1094          * nodes.
1095          */
1096         while (fn_head->next != NULL) {
1097                 DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
1098                 do_file(fn_head->next, NULL);
1099         }
1100
1101         /* Sort filenode list based on sequence */
1102         qsort(seqlist, file_count, sizeof(filenode *), sequence_cmp);
1103
1104         for (psl = seqlist; *psl; psl++) {
1105                 printf("%s%s",
1106                     (last_seq == 0 ? "" :
1107                     (do_parallel != true || last_seq != (*psl)->sequence) ?
1108                     "\n" : " "),
1109                 (*psl)->filename);
1110                 last_seq = (*psl)->sequence;
1111                 free((*psl)->filename);
1112                 free(*psl);
1113         }
1114         if (last_seq)
1115                 printf("\n");
1116
1117         free(seqlist);
1118 }