Changeset View
Changeset View
Standalone View
Standalone View
rcorder.c
# if 0 | # if 0 | ||||
/* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */ | /* $NetBSD: rcorder.c,v 1.7 2000/08/04 07:33:55 enami Exp $ */ | ||||
#endif | #endif | ||||
/*- | /*- | ||||
* SPDX-License-Identifier: BSD-2-Clause-FreeBSD | * SPDX-License-Identifier: BSD-2-Clause-FreeBSD | ||||
* | * | ||||
* Copyright (c) 1998, 1999 Matthew R. Green | * Copyright (c) 1998, 1999 Matthew R. Green | ||||
* All rights reserved. | * All rights reserved. | ||||
* Copyright (c) 1998 | * Copyright (c) 1998 | ||||
* Perry E. Metzger. All rights reserved. | * Perry E. Metzger. All rights reserved. | ||||
* Copyright (c) 2020 | |||||
* Boris N. Lytochkin. All rights reserved. | |||||
* | * | ||||
* Redistribution and use in source and binary forms, with or without | * Redistribution and use in source and binary forms, with or without | ||||
* modification, are permitted provided that the following conditions | * modification, are permitted provided that the following conditions | ||||
* are met: | * are met: | ||||
* 1. Redistributions of source code must retain the above copyright | * 1. Redistributions of source code must retain the above copyright | ||||
* notice, this list of conditions and the following disclaimer. | * notice, this list of conditions and the following disclaimer. | ||||
* 2. Redistributions in binary form must reproduce the above copyright | * 2. Redistributions in binary form must reproduce the above copyright | ||||
* notice, this list of conditions and the following disclaimer in the | * notice, this list of conditions and the following disclaimer in the | ||||
Show All 23 Lines | |||||
#include <sys/stat.h> | #include <sys/stat.h> | ||||
#include <err.h> | #include <err.h> | ||||
#include <stdio.h> | #include <stdio.h> | ||||
#include <libutil.h> | #include <libutil.h> | ||||
#include <stdlib.h> | #include <stdlib.h> | ||||
#include <string.h> | #include <string.h> | ||||
#include <unistd.h> | #include <unistd.h> | ||||
#include <libgen.h> | |||||
#include <stdbool.h> | |||||
#include "ealloc.h" | #include "ealloc.h" | ||||
#include "sprite.h" | #include "sprite.h" | ||||
#include "hash.h" | #include "hash.h" | ||||
#ifdef DEBUG | #ifdef DEBUG | ||||
static int debug = 0; | static int debug = 0; | ||||
# define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; } | # define DPRINTF(args) if (debug) { fflush(stdout); fprintf args; } | ||||
Show All 11 Lines | |||||
#define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1) | #define PROVIDES_LEN (sizeof(PROVIDES_STR) - 1) | ||||
#define BEFORE_STR "# BEFORE:" | #define BEFORE_STR "# BEFORE:" | ||||
#define BEFORE_LEN (sizeof(BEFORE_STR) - 1) | #define BEFORE_LEN (sizeof(BEFORE_STR) - 1) | ||||
#define KEYWORD_STR "# KEYWORD:" | #define KEYWORD_STR "# KEYWORD:" | ||||
#define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1) | #define KEYWORD_LEN (sizeof(KEYWORD_STR) - 1) | ||||
#define KEYWORDS_STR "# KEYWORDS:" | #define KEYWORDS_STR "# KEYWORDS:" | ||||
#define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1) | #define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1) | ||||
#define FAKE_PROV_NAME "fake_prov_" | |||||
static int exit_code; | static int exit_code; | ||||
static int file_count; | static int file_count; | ||||
static char **file_list; | static char **file_list; | ||||
typedef int bool; | |||||
#define TRUE 1 | #define TRUE 1 | ||||
#define FALSE 0 | #define FALSE 0 | ||||
typedef bool flag; | typedef bool flag; | ||||
#define SET TRUE | #define SET TRUE | ||||
#define RESET FALSE | #define RESET FALSE | ||||
static flag do_graphviz = false; | |||||
static flag do_parallel = false; | |||||
static Hash_Table provide_hash_s, *provide_hash; | static Hash_Table provide_hash_s, *provide_hash; | ||||
typedef struct provnode provnode; | typedef struct provnode provnode; | ||||
typedef struct filenode filenode; | typedef struct filenode filenode; | ||||
typedef struct f_provnode f_provnode; | typedef struct f_provnode f_provnode; | ||||
typedef struct f_reqnode f_reqnode; | typedef struct f_reqnode f_reqnode; | ||||
typedef struct strnodelist strnodelist; | typedef struct strnodelist strnodelist; | ||||
struct provnode { | struct provnode { | ||||
flag head; | flag head; | ||||
flag in_progress; | flag in_progress; | ||||
int sequence; | |||||
filenode *fnode; | filenode *fnode; | ||||
provnode *next, *last; | provnode *next, *last; | ||||
}; | }; | ||||
struct f_provnode { | struct f_provnode { | ||||
provnode *pnode; | provnode *pnode; | ||||
Hash_Entry *entry; | |||||
f_provnode *next; | f_provnode *next; | ||||
}; | }; | ||||
struct f_reqnode { | struct f_reqnode { | ||||
Hash_Entry *entry; | Hash_Entry *entry; | ||||
f_reqnode *next; | f_reqnode *next; | ||||
}; | }; | ||||
struct strnodelist { | struct strnodelist { | ||||
filenode *node; | filenode *node; | ||||
strnodelist *next; | strnodelist *next; | ||||
char s[1]; | char s[1]; | ||||
}; | }; | ||||
struct filenode { | struct filenode { | ||||
char *filename; | char *filename; | ||||
flag in_progress; | flag in_progress; | ||||
filenode *next, *last; | filenode *next, *last; | ||||
f_reqnode *req_list; | f_reqnode *req_list; | ||||
f_provnode *prov_list; | f_provnode *prov_list; | ||||
strnodelist *keyword_list; | strnodelist *keyword_list; | ||||
int issues_count; | |||||
int sequence; | |||||
}; | }; | ||||
static filenode fn_head_s, *fn_head; | static filenode fn_head_s, *fn_head, **fn_seqlist; | ||||
static int max_sequence = 0; | |||||
static strnodelist *bl_list; | static strnodelist *bl_list; | ||||
static strnodelist *keep_list; | static strnodelist *keep_list; | ||||
static strnodelist *skip_list; | static strnodelist *skip_list; | ||||
static void do_file(filenode *fnode); | static void do_file(filenode *fnode, strnodelist *); | ||||
static void strnode_add(strnodelist **, char *, filenode *); | static void strnode_add(strnodelist **, char *, filenode *); | ||||
static int skip_ok(filenode *fnode); | static int skip_ok(filenode *fnode); | ||||
static int keep_ok(filenode *fnode); | static int keep_ok(filenode *fnode); | ||||
static void satisfy_req(f_reqnode *rnode, char *filename); | static char *generate_loop_for_req(strnodelist *, provnode *, filenode *); | ||||
static void satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *); | |||||
static void crunch_file(char *); | static void crunch_file(char *); | ||||
static void parse_require(filenode *, char *); | static void parse_require(filenode *, char *); | ||||
static void parse_provide(filenode *, char *); | static void parse_provide(filenode *, char *); | ||||
static void parse_before(filenode *, char *); | static void parse_before(filenode *, char *); | ||||
static void parse_keywords(filenode *, char *); | static void parse_keywords(filenode *, char *); | ||||
static filenode *filenode_new(char *); | static filenode *filenode_new(char *); | ||||
static void add_require(filenode *, char *); | static void add_require(filenode *, char *); | ||||
static void add_provide(filenode *, char *); | static void add_provide(filenode *, char *); | ||||
static void add_before(filenode *, char *); | static void add_before(filenode *, char *); | ||||
static void add_keyword(filenode *, char *); | static void add_keyword(filenode *, char *); | ||||
static void insert_before(void); | static void insert_before(void); | ||||
static Hash_Entry *make_fake_provision(filenode *); | static Hash_Entry *make_fake_provision(filenode *); | ||||
static void crunch_all_files(void); | static void crunch_all_files(void); | ||||
static void initialize(void); | static void initialize(void); | ||||
static void generate_graphviz_header(void); | |||||
static void generate_graphviz_footer(void); | |||||
static void generate_graphviz_file_links(Hash_Entry *, filenode *); | |||||
static void generate_graphviz_providers(void); | |||||
static inline int is_fake_prov(const char *); | |||||
static int sequence_cmp(const void *, const void *); | |||||
static void generate_ordering(void); | static void generate_ordering(void); | ||||
int | int | ||||
main(int argc, char *argv[]) | main(int argc, char *argv[]) | ||||
{ | { | ||||
int ch; | int ch; | ||||
while ((ch = getopt(argc, argv, "dk:s:")) != -1) | while ((ch = getopt(argc, argv, "dgk:ps:")) != -1) | ||||
switch (ch) { | switch (ch) { | ||||
case 'd': | case 'd': | ||||
#ifdef DEBUG | #ifdef DEBUG | ||||
debug = 1; | debug = 1; | ||||
#else | #else | ||||
warnx("debugging not compiled in, -d ignored"); | warnx("debugging not compiled in, -d ignored"); | ||||
#endif | #endif | ||||
break; | break; | ||||
case 'g': | |||||
do_graphviz = true; | |||||
break; | |||||
case 'k': | case 'k': | ||||
strnode_add(&keep_list, optarg, 0); | strnode_add(&keep_list, optarg, 0); | ||||
break; | break; | ||||
case 'p': | |||||
do_parallel = true; | |||||
break; | |||||
case 's': | case 's': | ||||
strnode_add(&skip_list, optarg, 0); | strnode_add(&skip_list, optarg, 0); | ||||
break; | break; | ||||
default: | default: | ||||
/* XXX should crunch it? */ | /* XXX should crunch it? */ | ||||
break; | break; | ||||
} | } | ||||
argc -= optind; | argc -= optind; | ||||
argv += optind; | argv += optind; | ||||
file_count = argc; | file_count = argc; | ||||
file_list = argv; | file_list = argv; | ||||
DPRINTF((stderr, "parse_args\n")); | DPRINTF((stderr, "parse_args\n")); | ||||
initialize(); | initialize(); | ||||
DPRINTF((stderr, "initialize\n")); | DPRINTF((stderr, "initialize\n")); | ||||
generate_graphviz_header(); | |||||
crunch_all_files(); | crunch_all_files(); | ||||
DPRINTF((stderr, "crunch_all_files\n")); | DPRINTF((stderr, "crunch_all_files\n")); | ||||
generate_graphviz_providers(); | |||||
generate_ordering(); | generate_ordering(); | ||||
DPRINTF((stderr, "generate_ordering\n")); | DPRINTF((stderr, "generate_ordering\n")); | ||||
generate_graphviz_footer(); | |||||
exit(exit_code); | exit(exit_code); | ||||
} | } | ||||
/* | /* | ||||
* initialise various variables. | * initialise various variables. | ||||
*/ | */ | ||||
static void | static void | ||||
▲ Show 20 Lines • Show All 89 Lines • ▼ Show 20 Lines | add_provide(filenode *fnode, char *s) | ||||
head = Hash_GetValue(entry); | head = Hash_GetValue(entry); | ||||
/* create a head node if necessary. */ | /* create a head node if necessary. */ | ||||
if (head == NULL) { | if (head == NULL) { | ||||
head = emalloc(sizeof(*head)); | head = emalloc(sizeof(*head)); | ||||
head->head = SET; | head->head = SET; | ||||
head->in_progress = RESET; | head->in_progress = RESET; | ||||
head->fnode = NULL; | head->fnode = NULL; | ||||
head->sequence = 0; | |||||
head->last = head->next = NULL; | head->last = head->next = NULL; | ||||
Hash_SetValue(entry, head); | Hash_SetValue(entry, head); | ||||
} | } | ||||
#if 0 | #if 0 | ||||
/* | /* | ||||
* Don't warn about this. We want to be able to support | * Don't warn about this. We want to be able to support | ||||
* scripts that do two complex things: | * scripts that do two complex things: | ||||
* | * | ||||
Show All 39 Lines | #endif | ||||
pnode->next = head->next; | pnode->next = head->next; | ||||
pnode->last = head; | pnode->last = head; | ||||
head->next = pnode; | head->next = pnode; | ||||
if (pnode->next != NULL) | if (pnode->next != NULL) | ||||
pnode->next->last = pnode; | pnode->next->last = pnode; | ||||
f_pnode = emalloc(sizeof(*f_pnode)); | f_pnode = emalloc(sizeof(*f_pnode)); | ||||
f_pnode->pnode = pnode; | f_pnode->pnode = pnode; | ||||
f_pnode->entry = entry; | |||||
f_pnode->next = fnode->prov_list; | f_pnode->next = fnode->prov_list; | ||||
fnode->prov_list = f_pnode; | fnode->prov_list = f_pnode; | ||||
} | } | ||||
/* | /* | ||||
* put the BEFORE: lines to a list and handle them later. | * put the BEFORE: lines to a list and handle them later. | ||||
*/ | */ | ||||
static void | static void | ||||
▲ Show 20 Lines • Show All 156 Lines • ▼ Show 20 Lines | make_fake_provision(filenode *node) | ||||
Hash_Entry *entry; | Hash_Entry *entry; | ||||
f_provnode *f_pnode; | f_provnode *f_pnode; | ||||
provnode *head, *pnode; | provnode *head, *pnode; | ||||
static int i = 0; | static int i = 0; | ||||
int new; | int new; | ||||
char buffer[30]; | char buffer[30]; | ||||
do { | do { | ||||
snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++); | snprintf(buffer, sizeof buffer, FAKE_PROV_NAME "%08d", i++); | ||||
entry = Hash_CreateEntry(provide_hash, buffer, &new); | entry = Hash_CreateEntry(provide_hash, buffer, &new); | ||||
} while (new == 0); | } while (new == 0); | ||||
head = emalloc(sizeof(*head)); | head = emalloc(sizeof(*head)); | ||||
head->head = SET; | head->head = SET; | ||||
head->in_progress = RESET; | head->in_progress = RESET; | ||||
head->fnode = NULL; | head->fnode = NULL; | ||||
head->last = head->next = NULL; | head->last = head->next = NULL; | ||||
Hash_SetValue(entry, head); | Hash_SetValue(entry, head); | ||||
pnode = emalloc(sizeof(*pnode)); | pnode = emalloc(sizeof(*pnode)); | ||||
pnode->head = RESET; | pnode->head = RESET; | ||||
pnode->in_progress = RESET; | pnode->in_progress = RESET; | ||||
pnode->fnode = node; | pnode->fnode = node; | ||||
pnode->next = head->next; | pnode->next = head->next; | ||||
pnode->last = head; | pnode->last = head; | ||||
head->next = pnode; | head->next = pnode; | ||||
if (pnode->next != NULL) | if (pnode->next != NULL) | ||||
pnode->next->last = pnode; | pnode->next->last = pnode; | ||||
f_pnode = emalloc(sizeof(*f_pnode)); | f_pnode = emalloc(sizeof(*f_pnode)); | ||||
f_pnode->entry = entry; | |||||
f_pnode->pnode = pnode; | f_pnode->pnode = pnode; | ||||
f_pnode->next = node->prov_list; | f_pnode->next = node->prov_list; | ||||
node->prov_list = f_pnode; | node->prov_list = f_pnode; | ||||
return (entry); | return (entry); | ||||
} | } | ||||
/* | /* | ||||
Show All 16 Lines | while (bl_list != NULL) { | ||||
bl = bl_list->next; | bl = bl_list->next; | ||||
fake_prov_entry = make_fake_provision(bl_list->node); | fake_prov_entry = make_fake_provision(bl_list->node); | ||||
entry = Hash_CreateEntry(provide_hash, bl_list->s, &new); | entry = Hash_CreateEntry(provide_hash, bl_list->s, &new); | ||||
if (new == 1) | if (new == 1) | ||||
warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s); | warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s); | ||||
if (new == 1 && do_graphviz == true) | |||||
generate_graphviz_file_links( | |||||
Hash_FindEntry(provide_hash, bl_list->s), | |||||
bl_list->node); | |||||
for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) { | for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) { | ||||
if (pnode->head) | if (pnode->head) | ||||
continue; | continue; | ||||
rnode = emalloc(sizeof(*rnode)); | rnode = emalloc(sizeof(*rnode)); | ||||
rnode->entry = fake_prov_entry; | rnode->entry = fake_prov_entry; | ||||
rnode->next = pnode->fnode->req_list; | rnode->next = pnode->fnode->req_list; | ||||
pnode->fnode->req_list = rnode; | pnode->fnode->req_list = rnode; | ||||
Show All 14 Lines | |||||
{ | { | ||||
int i; | int i; | ||||
for (i = 0; i < file_count; i++) | for (i = 0; i < file_count; i++) | ||||
crunch_file(file_list[i]); | crunch_file(file_list[i]); | ||||
insert_before(); | insert_before(); | ||||
} | } | ||||
static inline int | |||||
melifaro: Typo? | |||||
is_fake_prov(const char *name) | |||||
{ | |||||
return (name == strstr(name, FAKE_PROV_NAME)); | |||||
} | |||||
/* loop though provide list of vnode drawing all non-fake dependencies */ | |||||
static void | |||||
generate_graphviz_file_links(Hash_Entry *entry, filenode *fnode) | |||||
Done Inline ActionsThis 3-line pattern gets repeated 3 times. Mind moving to an inline func? melifaro: This 3-line pattern gets repeated 3 times. Mind moving to an inline func? | |||||
{ | |||||
char *dep_name, *fname; | |||||
provnode *head; | |||||
f_provnode *fpnode, *rfpnode; | |||||
int is_before = 0; | |||||
dep_name = Hash_GetKey(entry); | |||||
if (is_fake_prov(dep_name)) | |||||
is_before = 1; | |||||
head = Hash_GetValue(entry); | |||||
for (fpnode = fnode->prov_list; fpnode && fpnode->entry; | |||||
fpnode = fpnode->next) { | |||||
fname = Hash_GetKey(fpnode->entry); | |||||
if (is_fake_prov(fname)) | |||||
continue; | |||||
rfpnode = NULL; | |||||
do { | |||||
if (rfpnode) | |||||
dep_name = Hash_GetKey(rfpnode->entry); | |||||
else | |||||
dep_name = Hash_GetKey(entry); | |||||
if (!is_fake_prov(dep_name)) { | |||||
printf("\"%s\" -> \"%s\" [%s%s];\n", | |||||
fname, dep_name, | |||||
/* edge style */ | |||||
(is_before ? "style=dashed" : "style=solid"), | |||||
/* circular dep? */ | |||||
((head == NULL || | |||||
(head->next && head->in_progress == SET)) ? | |||||
", color=red, penwidth=4" : "")); | |||||
if (rfpnode == NULL) | |||||
break; | |||||
} | |||||
/* dependency is solved already */ | |||||
if (head == NULL || head->next == NULL) | |||||
break; | |||||
if (rfpnode == NULL) | |||||
rfpnode = head->next->fnode->prov_list; | |||||
else | |||||
rfpnode = rfpnode->next; | |||||
} while (rfpnode); | |||||
} | |||||
} | |||||
/* | /* | ||||
* Walk the stack, find the looping point and generate traceback. | |||||
* NULL is returned on failure, otherwize pointer to a buffer holding | |||||
Done Inline Actionsdoes it print or return the loop string? melifaro: does it print or return the loop string? | |||||
* text representation is returned, caller must run free(3) for the | |||||
* pointer. | |||||
*/ | |||||
static char * | |||||
generate_loop_for_req(strnodelist *stack_tail, provnode *head, | |||||
filenode *fnode) | |||||
{ | |||||
provnode *pnode; | |||||
strnodelist *stack_ptr, *loop_entry; | |||||
char *buf, **revstack; | |||||
size_t bufsize, stack_depth; | |||||
int i; | |||||
loop_entry = NULL; | |||||
/* fast forward stack to the component that is required now */ | |||||
for (pnode = head->next; pnode; pnode = pnode->next) { | |||||
if (loop_entry) | |||||
break; | |||||
stack_depth = 0; | |||||
for (stack_ptr = stack_tail; stack_ptr; | |||||
stack_ptr = stack_ptr->next) { | |||||
Done Inline ActionsIIRC style(9) requires space after while melifaro: IIRC style(9) requires space after while | |||||
stack_depth++; | |||||
if (stack_ptr->node == pnode->fnode) { | |||||
Done Inline ActionsCould you please use strlen here as well? melifaro: Could you please use strlen here as well? | |||||
loop_entry = stack_ptr; | |||||
break; | |||||
} | |||||
} | |||||
} | |||||
if (loop_entry == NULL) | |||||
return (NULL); | |||||
stack_depth += 2; /* fnode + loop_entry */ | |||||
revstack = emalloc(sizeof(char *) * stack_depth); | |||||
bzero(revstack, (sizeof(char *) * stack_depth)); | |||||
/* reverse stack and estimate buffer size to allocate */ | |||||
Done Inline ActionsIt’s not bufsize anymore melifaro: It’s not bufsize anymore | |||||
Done Inline ActionsIt is still bufsize as long as I use strlcat(3): strlcat() appends string src to the end of dst. It will append at most dstsize - strlen(dst) - 1 characters. lytboris_gmail.com: It is still bufsize as long as I use strlcat(3):
```
strlcat() appends string src to the… | |||||
bufsize = 1; /* tralining \0 */ | |||||
revstack[stack_depth - 1] = loop_entry->node->filename; | |||||
bufsize += strlen(revstack[stack_depth - 1]); | |||||
revstack[stack_depth - 2] = fnode->filename; | |||||
bufsize += strlen(revstack[stack_depth - 2]); | |||||
Done Inline ActionsYou need to decrease bufsize with each invocation melifaro: You need to decrease bufsize with each invocation | |||||
fnode->issues_count++; | |||||
stack_ptr = stack_tail; | |||||
for (i = stack_depth - 3; i >= 0; i--) { | |||||
revstack[i] = stack_ptr->node->filename; | |||||
stack_ptr->node->issues_count++; | |||||
stack_ptr = stack_ptr->next; | |||||
bufsize += strlen(revstack[i]); | |||||
} | |||||
bufsize += strlen(" -> ") * (stack_depth - 1); | |||||
buf = emalloc(bufsize); | |||||
bzero(buf, bufsize); | |||||
for (i = 0; i < stack_depth; i++) { | |||||
strlcat(buf, revstack[i], bufsize); | |||||
if (i < stack_depth - 1) | |||||
strlcat(buf, " -> ", bufsize); | |||||
} | |||||
free(revstack); | |||||
return (buf); | |||||
} | |||||
/* | |||||
* below are the functions that traverse the graphs we have built | * below are the functions that traverse the graphs we have built | ||||
* finding out the desired ordering, printing each file in turn. | * finding out the desired ordering, printing each file in turn. | ||||
* if missing requirements, or cyclic graphs are detected, a | * if missing requirements, or cyclic graphs are detected, a | ||||
* warning will be issued, and we will continue on.. | * warning will be issued, and we will continue on.. | ||||
*/ | */ | ||||
/* | /* | ||||
* given a requirement node (in a filename) we attempt to satisfy it. | * given a requirement node (in a filename) we attempt to satisfy it. | ||||
* we do some sanity checking first, to ensure that we have providers, | * we do some sanity checking first, to ensure that we have providers, | ||||
* aren't already satisfied and aren't already being satisfied (ie, | * aren't already satisfied and aren't already being satisfied (ie, | ||||
* cyclic). if we pass all this, we loop over the provision list | * cyclic). if we pass all this, we loop over the provision list | ||||
* calling do_file() (enter recursion) for each filenode in this | * calling do_file() (enter recursion) for each filenode in this | ||||
* provision. | * provision. | ||||
*/ | */ | ||||
static void | static void | ||||
satisfy_req(f_reqnode *rnode, char *filename) | satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *stack_ptr) | ||||
{ | { | ||||
Hash_Entry *entry; | Hash_Entry *entry; | ||||
provnode *head; | provnode *head; | ||||
strnodelist stack_item; | |||||
Done Inline ActionsPlease do not use static variables. melifaro: Please do not use static variables. | |||||
char *buf; | |||||
entry = rnode->entry; | entry = rnode->entry; | ||||
head = Hash_GetValue(entry); | head = Hash_GetValue(entry); | ||||
if (do_graphviz == true) | |||||
generate_graphviz_file_links(entry, fnode); | |||||
if (head == NULL) { | if (head == NULL) { | ||||
warnx("requirement `%s' in file `%s' has no providers.", | warnx("requirement `%s' in file `%s' has no providers.", | ||||
Hash_GetKey(entry), filename); | Hash_GetKey(entry), fnode->filename); | ||||
exit_code = 1; | exit_code = 1; | ||||
return; | return; | ||||
} | } | ||||
/* return if the requirement is already satisfied. */ | /* return if the requirement is already satisfied. */ | ||||
if (head->next == NULL) | if (head->next == NULL) | ||||
return; | return; | ||||
/* | /* | ||||
* if list is marked as in progress, | * if list is marked as in progress, | ||||
* print that there is a circular dependency on it and abort | * print that there is a circular dependency on it and abort | ||||
*/ | */ | ||||
if (head->in_progress == SET) { | if (head->in_progress == SET) { | ||||
warnx("Circular dependency on provision `%s' in file `%s'.", | |||||
Hash_GetKey(entry), filename); | |||||
exit_code = 1; | exit_code = 1; | ||||
buf = generate_loop_for_req(stack_ptr, head, | |||||
fnode); | |||||
if (buf == NULL) { | |||||
warnx("Circular dependency on provision `%s' in " | |||||
"file `%s' (tracing has failed).", | |||||
Hash_GetKey(entry), fnode->filename); | |||||
return; | return; | ||||
} | } | ||||
warnx("Circular dependency on provision `%s': %s.", | |||||
Hash_GetKey(entry), buf); | |||||
free(buf); | |||||
return; | |||||
} | |||||
head->in_progress = SET; | head->in_progress = SET; | ||||
stack_item.next = stack_ptr; | |||||
stack_item.node = fnode; | |||||
/* | /* | ||||
* while provision_list is not empty | * while provision_list is not empty | ||||
* do_file(first_member_of(provision_list)); | * do_file(first_member_of(provision_list)); | ||||
*/ | */ | ||||
while (head->next != NULL) | while (head->next != NULL) | ||||
do_file(head->next->fnode); | do_file(head->next->fnode, &stack_item); | ||||
} | } | ||||
static int | static int | ||||
skip_ok(filenode *fnode) | skip_ok(filenode *fnode) | ||||
{ | { | ||||
strnodelist *s; | strnodelist *s; | ||||
strnodelist *k; | strnodelist *k; | ||||
Show All 26 Lines | |||||
* for each of them.. once we have done this, remove this filenode | * for each of them.. once we have done this, remove this filenode | ||||
* from each provision table, as we are now done. | * from each provision table, as we are now done. | ||||
* | * | ||||
* NOTE: do_file() is called recursively from several places and cannot | * NOTE: do_file() is called recursively from several places and cannot | ||||
* safely free() anything related to items that may be recursed on. | * safely free() anything related to items that may be recursed on. | ||||
* Circular dependencies will cause problems if we do. | * Circular dependencies will cause problems if we do. | ||||
*/ | */ | ||||
static void | static void | ||||
do_file(filenode *fnode) | do_file(filenode *fnode, strnodelist *stack_ptr) | ||||
{ | { | ||||
f_reqnode *r; | f_reqnode *r; | ||||
f_provnode *p, *p_tmp; | f_provnode *p, *p_tmp; | ||||
provnode *pnode; | provnode *pnode, *head; | ||||
int was_set; | int was_set; | ||||
char *dep_name; | |||||
DPRINTF((stderr, "do_file on %s.\n", fnode->filename)); | DPRINTF((stderr, "do_file on %s.\n", fnode->filename)); | ||||
/* | /* | ||||
* if fnode is marked as in progress, | * if fnode is marked as in progress, | ||||
* print that fnode; is circularly depended upon and abort. | * print that fnode; is circularly depended upon and abort. | ||||
*/ | */ | ||||
if (fnode->in_progress == SET) { | if (fnode->in_progress == SET) { | ||||
warnx("Circular dependency on file `%s'.", | warnx("Circular dependency on file `%s'.", | ||||
fnode->filename); | fnode->filename); | ||||
was_set = exit_code = 1; | was_set = exit_code = 1; | ||||
} else | } else | ||||
was_set = 0; | was_set = 0; | ||||
/* mark fnode */ | /* mark fnode */ | ||||
fnode->in_progress = SET; | fnode->in_progress = SET; | ||||
/* | /* | ||||
* for each requirement of fnode -> r | * for each requirement of fnode -> r | ||||
* satisfy_req(r, filename) | * satisfy_req(r, filename) | ||||
*/ | */ | ||||
r = fnode->req_list; | r = fnode->req_list; | ||||
fnode->sequence = 0; | |||||
while (r != NULL) { | while (r != NULL) { | ||||
satisfy_req(r, fnode->filename); | satisfy_req(r, fnode, stack_ptr); | ||||
/* find sequence number where all requirements are satisfied */ | |||||
head = Hash_GetValue(r->entry); | |||||
if (head && head->sequence > fnode->sequence) | |||||
fnode->sequence = head->sequence; | |||||
r = r->next; | r = r->next; | ||||
} | } | ||||
fnode->req_list = NULL; | fnode->req_list = NULL; | ||||
fnode->sequence++; | |||||
/* if we've seen issues with this file - put it to the tail */ | |||||
if (fnode->issues_count) | |||||
fnode->sequence = max_sequence + 1; | |||||
if (max_sequence < fnode->sequence) | |||||
max_sequence = fnode->sequence; | |||||
/* | /* | ||||
* for each provision of fnode -> p | * for each provision of fnode -> p | ||||
* remove fnode from provision list for p in hash table | * remove fnode from provision list for p in hash table | ||||
*/ | */ | ||||
p = fnode->prov_list; | p = fnode->prov_list; | ||||
while (p != NULL) { | while (p != NULL) { | ||||
/* mark all troublemakers on graphviz */ | |||||
if (do_graphviz == true && fnode->issues_count) { | |||||
dep_name = Hash_GetKey(p->entry); | |||||
if (!is_fake_prov(dep_name)) | |||||
printf("\"%s\" [ color=red, penwidth=4 ];\n", | |||||
dep_name); | |||||
} | |||||
/* update sequence when provided requirements are satisfied */ | |||||
head = Hash_GetValue(p->entry); | |||||
if (head->sequence < fnode->sequence) | |||||
head->sequence = fnode->sequence; | |||||
p_tmp = p; | p_tmp = p; | ||||
pnode = p->pnode; | pnode = p->pnode; | ||||
if (pnode->next != NULL) { | if (pnode->next != NULL) { | ||||
pnode->next->last = pnode->last; | pnode->next->last = pnode->last; | ||||
} | } | ||||
if (pnode->last != NULL) { | if (pnode->last != NULL) { | ||||
pnode->last->next = pnode->next; | pnode->last->next = pnode->next; | ||||
} | } | ||||
free(pnode); | free(pnode); | ||||
p = p->next; | p = p->next; | ||||
free(p_tmp); | free(p_tmp); | ||||
} | } | ||||
fnode->prov_list = NULL; | fnode->prov_list = NULL; | ||||
/* do_it(fnode) */ | /* do_it(fnode) */ | ||||
DPRINTF((stderr, "next do: ")); | DPRINTF((stderr, "next do: ")); | ||||
/* if we were already in progress, don't print again */ | /* if we were already in progress, don't print again */ | ||||
if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) | if (do_graphviz != true && was_set == 0 && skip_ok(fnode) && | ||||
printf("%s\n", fnode->filename); | keep_ok(fnode)) { | ||||
*fn_seqlist = fnode; | |||||
fn_seqlist++; | |||||
} | |||||
if (fnode->next != NULL) { | if (fnode->next != NULL) { | ||||
fnode->next->last = fnode->last; | fnode->next->last = fnode->last; | ||||
} | } | ||||
if (fnode->last != NULL) { | if (fnode->last != NULL) { | ||||
fnode->last->next = fnode->next; | fnode->last->next = fnode->next; | ||||
} | } | ||||
if (fnode->issues_count) | |||||
warnx("`%s' was seen in circular dependencies for %d times.", | |||||
fnode->filename, fnode->issues_count); | |||||
DPRINTF((stderr, "nuking %s\n", fnode->filename)); | DPRINTF((stderr, "nuking %s\n", fnode->filename)); | ||||
#if 0 | |||||
if (was_set == 0) { | |||||
free(fnode->filename); | |||||
free(fnode); | |||||
} | } | ||||
#endif | |||||
static void | |||||
generate_graphviz_header() | |||||
{ | |||||
Done Inline Actionsstyle(9) empty line if no vars melifaro: style(9) empty line if no vars | |||||
if (do_graphviz != true) | |||||
return; | |||||
printf("digraph rcorder {\n" | |||||
"rankdir=\"BT\";\n" | |||||
"node [style=rounded, shape=record];\n" | |||||
"graph [overlap = false];\n"); | |||||
} | } | ||||
static void | static void | ||||
generate_graphviz_footer() | |||||
{ | |||||
if (do_graphviz == true) | |||||
printf("}\n"); | |||||
} | |||||
static void | |||||
generate_graphviz_providers() | |||||
{ | |||||
Hash_Entry *entry; | |||||
Hash_Search psearch; | |||||
Done Inline Actionstypo? melifaro: typo? | |||||
provnode *head, *pnode; | |||||
char *dep_name; | |||||
if (do_graphviz != true) | |||||
return; | |||||
entry = Hash_EnumFirst(provide_hash, &psearch); | |||||
if (entry == NULL) | |||||
return; | |||||
do { | |||||
dep_name = Hash_GetKey(entry); | |||||
if (is_fake_prov(dep_name)) | |||||
continue; | |||||
head = Hash_GetValue(entry); | |||||
/* no providers for this requirement */ | |||||
if (head == NULL || head->next == NULL) { | |||||
printf("\"%s\" [label=\"{ %s | ENOENT }\", " | |||||
"style=\"rounded,filled\", color=red];\n", | |||||
dep_name, dep_name); | |||||
continue; | |||||
} | |||||
/* one PROVIDE word for one file that matches */ | |||||
if (head->next->next == NULL && | |||||
strcmp(dep_name, | |||||
basename(head->next->fnode->filename)) == 0) { | |||||
continue; | |||||
} | |||||
printf("\"%s\" [label=\"{ %s | ", dep_name, dep_name); | |||||
for (pnode = head->next; pnode; pnode = pnode->next) | |||||
printf("%s\\n", basename(pnode->fnode->filename)); | |||||
printf("}\"];\n"); | |||||
} while (NULL != (entry = Hash_EnumNext(&psearch))); | |||||
} | |||||
static int | |||||
sequence_cmp(const void *a, const void *b) | |||||
{ | |||||
Done Inline ActionsWhy not typecast to const filenode *? melifaro: Why not typecast to const filenode *? | |||||
int left, right; | |||||
filenode *fna = *((filenode **)a); | |||||
filenode *fnb = *((filenode **)b); | |||||
/* push phantom files to the end */ | |||||
if (fna == NULL || fnb == NULL) | |||||
return ((fna < fnb) - (fna > fnb)); | |||||
Done Inline ActionsWorth declaring in header melifaro: Worth declaring in header | |||||
left = fna->sequence; | |||||
right = fnb->sequence; | |||||
return ((left > right) - (left < right)); | |||||
} | |||||
static void | |||||
generate_ordering(void) | generate_ordering(void) | ||||
{ | { | ||||
filenode **seqlist, **psl; | |||||
int last_seq = 0; | |||||
/* Prepare order buffer, use an additional one as a list terminator */ | |||||
seqlist = emalloc(sizeof(filenode *) * (file_count + 1)); | |||||
Done Inline Actionswhy +1? melifaro: why +1? | |||||
bzero(seqlist, sizeof(filenode *) * (file_count + 1)); | |||||
fn_seqlist = seqlist; | |||||
/* | /* | ||||
* while there remain undone files{f}, | * while there remain undone files{f}, | ||||
* pick an arbitrary f, and do_file(f) | * pick an arbitrary f, and do_file(f) | ||||
* Note that the first file in the file list is perfectly | * Note that the first file in the file list is perfectly | ||||
* arbitrary, and easy to find, so we use that. | * arbitrary, and easy to find, so we use that. | ||||
*/ | */ | ||||
/* | /* | ||||
* N.B.: the file nodes "self delete" after they execute, so | * N.B.: the file nodes "self delete" after they execute, so | ||||
* after each iteration of the loop, the head will be pointing | * after each iteration of the loop, the head will be pointing | ||||
* to something totally different. The loop ends up being | * to something totally different. The loop ends up being | ||||
* executed only once for every strongly connected set of | * executed only once for every strongly connected set of | ||||
* nodes. | * nodes. | ||||
*/ | */ | ||||
while (fn_head->next != NULL) { | while (fn_head->next != NULL) { | ||||
DPRINTF((stderr, "generate on %s\n", fn_head->next->filename)); | DPRINTF((stderr, "generate on %s\n", fn_head->next->filename)); | ||||
do_file(fn_head->next); | do_file(fn_head->next, NULL); | ||||
} | } | ||||
/* Sort filenode list based on sequence */ | |||||
qsort(seqlist, file_count, sizeof(filenode *), sequence_cmp); | |||||
for (psl = seqlist; *psl; psl++) { | |||||
printf("%s%s", | |||||
(last_seq == 0 ? "" : | |||||
(do_parallel != true || last_seq != (*psl)->sequence) ? | |||||
"\n" : " "), | |||||
(*psl)->filename); | |||||
last_seq = (*psl)->sequence; | |||||
free((*psl)->filename); | |||||
free(*psl); | |||||
} | |||||
if (last_seq) | |||||
printf("\n"); | |||||
free(seqlist); | |||||
} | } |
Typo?