1#include <stdbool.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5#include "arg.h"
6#include "env.h"
7#include "graph.h"
8#include "os.h"
9#include "parse.h"
10#include "util.h"
11
12const char *argv0;
13
14static bool graphviz;
15static bool ascii;
16static bool firstroot = true;
17static struct node **seen;
18static size_t nseen, capseen;
19static struct node **dotnodes;
20static size_t ndotnodes, capdotnodes;
21static struct node **dotseen_nodes;
22static size_t ndotseen_nodes, capdotseen_nodes;
23
24static const char *
25progname(const char *arg, const char *def)
26{
27 const char *slash;
28
29 if (!arg)
30 return def;
31 slash = strrchr(arg, '/');
32 return slash ? slash + 1 : arg;
33}
34
35static void
36usage(void)
37{
38 fprintf(stderr, "usage: %s [-a] [-g] [-C dir] [-f buildfile] [target ...]\n", argv0);
39 exit(2);
40}
41
42static bool
43onstack(struct node *n, struct node **stack, size_t nstack)
44{
45 size_t i;
46
47 for (i = 0; i < nstack; ++i) {
48 if (stack[i] == n)
49 return true;
50 }
51 return false;
52}
53
54static bool
55seenbefore(struct node *n)
56{
57 size_t i;
58
59 for (i = 0; i < nseen; ++i) {
60 if (seen[i] == n)
61 return true;
62 }
63 return false;
64}
65
66static void
67markseen(struct node *n)
68{
69 if (seenbefore(n))
70 return;
71 if (nseen == capseen) {
72 capseen = capseen ? capseen * 2 : 128;
73 seen = xreallocarray(seen, capseen, sizeof(seen[0]));
74 }
75 seen[nseen++] = n;
76}
77
78static void
79emitstr(const char *s)
80{
81 for (; *s; ++s) {
82 if (*s == '"' || *s == '\\')
83 putchar('\\');
84 putchar(*s);
85 }
86}
87
88static bool
89isroot(struct node *n)
90{
91 return n->nuse == 0;
92}
93
94//dedup so we dont get two arrows
95static bool
96dotseen(struct node *n)
97{
98 size_t i;
99
100 for (i = 0; i < ndotnodes; ++i) {
101 if (dotnodes[i] == n)
102 return true;
103 }
104 return false;
105}
106
107static bool
108dotwalkseen(struct node *n)
109{
110 size_t i;
111
112 for (i = 0; i < ndotseen_nodes; ++i) {
113 if (dotseen_nodes[i] == n)
114 return true;
115 }
116 return false;
117}
118
119static void
120markdotwalk(struct node *n)
121{
122 if (dotwalkseen(n))
123 return;
124 if (ndotseen_nodes == capdotseen_nodes) {
125 capdotseen_nodes = capdotseen_nodes ? capdotseen_nodes * 2 : 128;
126 dotseen_nodes = xreallocarray(dotseen_nodes, capdotseen_nodes, sizeof(dotseen_nodes[0]));
127 }
128 dotseen_nodes[ndotseen_nodes++] = n;
129}
130
131static size_t
132dotid(struct node *n)
133{
134 size_t i;
135
136 for (i = 0; i < ndotnodes; ++i) {
137 if (dotnodes[i] == n)
138 return i;
139 }
140 if (ndotnodes == capdotnodes) {
141 capdotnodes = capdotnodes ? capdotnodes * 2 : 128;
142 dotnodes = xreallocarray(dotnodes, capdotnodes, sizeof(dotnodes[0]));
143 }
144 dotnodes[ndotnodes] = n;
145 return ndotnodes++;
146}
147
148static void
149emitdotnode(struct node *n)
150{
151 size_t id;
152
153 if (dotseen(n))
154 return;
155 id = dotid(n);
156 printf(" n%zu [label=\"", id);
157 emitstr(n->path->s);
158 printf("\"");
159 printf(", shape=box");
160 if (n->gen && n->gen->rule == &phonyrule) {
161 printf(", style=dashed");
162 } else if (isroot(n)) {
163 printf(", style=bold");
164 }
165 printf("];\n");
166}
167
168static void
169printindent(size_t depth, bool *more)
170{
171 size_t i;
172
173 for (i = 0; i < depth; ++i)
174 printf("%s", more[i] ? (ascii ? "| " : "│ ") : " ");
175}
176
177static void
178dumpdot(struct node *n, struct node **stack, size_t nstack)
179{
180 size_t i;
181 size_t nid, iid;
182
183 if (dotwalkseen(n))
184 return;
185 if (onstack(n, stack, nstack))
186 return;
187 markdotwalk(n);
188 emitdotnode(n);
189 stack[nstack++] = n;
190 if (!n->gen)
191 return;
192 nid = dotid(n);
193 for (i = 0; i < n->gen->nin; ++i) {
194 struct node *in = n->gen->in[i];
195
196 emitdotnode(in);
197 iid = dotid(in);
198 printf(" n%zu -> n%zu", iid, nid);
199 if (i >= n->gen->inorderidx)
200 printf(" [style=dashed]");
201 printf(";\n");
202 dumpdot(in, stack, nstack);
203 }
204}
205
206static void
207dumptree(struct node *n, size_t depth, bool last, bool *more, struct node **stack, size_t nstack)
208{
209 size_t i;
210
211 if (depth == 0) {
212 if (!firstroot)
213 putchar('\n');
214 firstroot = false;
215 printf("%s\n", n->path->s);
216 } else {
217 printindent(depth - 1, more);
218 printf("%s%s", last ? (ascii ? "`-- " : "└── ") : (ascii ? "|-- " : "├── "), n->path->s);
219 if (seenbefore(n)) {
220 printf(" [shared]\n");
221 return;
222 }
223 putchar('\n');
224 }
225 if (onstack(n, stack, nstack))
226 return;
227 markseen(n);
228 stack[nstack++] = n;
229 if (!n->gen)
230 return;
231 for (i = 0; i < n->gen->nin; ++i) {
232 more[depth] = i + 1 < n->gen->nin;
233 dumptree(n->gen->in[i], depth + 1, i + 1 == n->gen->nin, more, stack, nstack);
234 }
235}
236
237static void
238showroot(struct node *n)
239{
240 struct node *stack[512];
241 bool more[512];
242
243 memset(more, 0, sizeof(more));
244 if (graphviz)
245 dumpdot(n, stack, 0);
246 else
247 dumptree(n, 0, true, more, stack, 0);
248}
249
250int
251main(int argc, char *argv[])
252{
253 char *manifest;
254 struct node *n;
255 struct edge *e;
256 size_t i;
257
258 argv0 = progname(argv[0], "nviz");
259 manifest = "build.ninja";
260
261 ARGBEGIN {
262 case 'a':
263 ascii = true;
264 break;
265 case 'C':
266 oschdir(EARGF(usage()));
267 break;
268 case 'f':
269 manifest = EARGF(usage());
270 break;
271 case 'g':
272 graphviz = true;
273 break;
274 default:
275 usage();
276 } ARGEND
277
278 graphinit();
279 envinit();
280 parseinit();
281 parse(manifest, rootenv);
282
283 if (graphviz)
284 printf("digraph build {\n"
285 " rankdir=\"LR\";\n"
286 " graph [fontname=\"serif\"];\n"
287 " node [fontsize=10, fontname=\"serif\", shape=box, height=0.25];\n"
288 " edge [fontsize=10, fontname=\"serif\"];\n");
289
290 if (argc > 0) {
291 while (*argv) {
292 n = nodeget(*argv, 0);
293 if (!n)
294 fatal("unknown target '%s'", *argv);
295 showroot(n);
296 ++argv;
297 }
298 } else {
299 for (e = alledges; e; e = e->allnext) {
300 for (i = 0; i < e->nout; ++i) {
301 n = e->out[i];
302 if (n->nuse == 0)
303 showroot(n);
304 }
305 }
306 }
307
308 if (graphviz)
309 printf("}\n");
310 free(dotnodes);
311 free(dotseen_nodes);
312 free(seen);
313 return 0;
314}
