1#include <ctype.h>
2#include <stdbool.h>
3#include <stdlib.h>
4#include <string.h>
5#include "env.h"
6#include "graph.h"
7#include "htab.h"
8#include "os.h"
9#include "util.h"
10
11static struct hashtable *allnodes;
12struct edge *alledges;
13
14static void
15delnode(void *p)
16{
17 struct node *n = p;
18
19 if (n->shellpath != n->path)
20 free(n->shellpath);
21 free(n->use);
22 free(n->path);
23 free(n);
24}
25
26void
27graphinit(void)
28{
29 struct edge *e;
30
31 /* delete old nodes and edges in case we rebuilt the manifest */
32 delhtab(allnodes, delnode);
33 while (alledges) {
34 e = alledges;
35 alledges = e->allnext;
36 free(e->out);
37 free(e->in);
38 free(e);
39 }
40 allnodes = mkhtab(1024);
41}
42
43struct node *
44mknode(struct string *path)
45{
46 void **v;
47 struct node *n;
48 struct hashtablekey k;
49
50 htabkey(&k, path->s, path->n);
51 v = htabput(allnodes, &k);
52 if (*v) {
53 free(path);
54 return *v;
55 }
56 n = xmalloc(sizeof(*n));
57 n->path = path;
58 n->shellpath = NULL;
59 n->gen = NULL;
60 n->use = NULL;
61 n->nuse = 0;
62 n->mtime = MTIME_UNKNOWN;
63 n->logmtime = MTIME_MISSING;
64 n->hash = 0;
65 n->id = -1;
66 *v = n;
67
68 return n;
69}
70
71struct node *
72nodeget(const char *path, size_t len)
73{
74 struct hashtablekey k;
75
76 if (!len)
77 len = strlen(path);
78 htabkey(&k, path, len);
79 return htabget(allnodes, &k);
80}
81
82void
83nodestat(struct node *n)
84{
85 n->mtime = osmtime(n->path->s);
86}
87
88struct string *
89nodepath(struct node *n, bool escape)
90{
91 char *s, *d;
92 int nquote;
93
94 if (!escape)
95 return n->path;
96 if (n->shellpath)
97 return n->shellpath;
98 escape = false;
99 nquote = 0;
100 for (s = n->path->s; *s; ++s) {
101 if (!isalnum(*(unsigned char *)s) && !strchr("_+-./", *s))
102 escape = true;
103 if (*s == '\'')
104 ++nquote;
105 }
106 if (escape) {
107 n->shellpath = mkstr(n->path->n + 2 + 3 * nquote);
108 d = n->shellpath->s;
109 *d++ = '\'';
110 for (s = n->path->s; *s; ++s) {
111 *d++ = *s;
112 if (*s == '\'') {
113 *d++ = '\\';
114 *d++ = '\'';
115 *d++ = '\'';
116 }
117 }
118 *d++ = '\'';
119 } else {
120 n->shellpath = n->path;
121 }
122 return n->shellpath;
123}
124
125void
126nodeuse(struct node *n, struct edge *e)
127{
128 /* allocate in powers of two */
129 if (!(n->nuse & (n->nuse - 1)))
130 n->use = xreallocarray(n->use, n->nuse ? n->nuse * 2 : 1, sizeof(e));
131 n->use[n->nuse++] = e;
132}
133
134struct edge *
135mkedge(struct environment *parent)
136{
137 struct edge *e;
138
139 e = xmalloc(sizeof(*e));
140 e->env = mkenv(parent);
141 e->pool = NULL;
142 e->out = NULL;
143 e->nout = 0;
144 e->in = NULL;
145 e->nin = 0;
146 e->flags = 0;
147 e->allnext = alledges;
148 alledges = e;
149
150 return e;
151}
152
153void
154edgehash(struct edge *e)
155{
156 static const char sep[] = ";rspfile=";
157 struct string *cmd, *rsp, *s;
158
159 if (e->flags & FLAG_HASH)
160 return;
161 e->flags |= FLAG_HASH;
162 cmd = edgevar(e, "command", true);
163 if (!cmd)
164 fatal("rule '%s' has no command", e->rule->name);
165 rsp = edgevar(e, "rspfile_content", true);
166 if (rsp && rsp->n > 0) {
167 s = mkstr(cmd->n + sizeof(sep) - 1 + rsp->n);
168 memcpy(s->s, cmd->s, cmd->n);
169 memcpy(s->s + cmd->n, sep, sizeof(sep) - 1);
170 memcpy(s->s + cmd->n + sizeof(sep) - 1, rsp->s, rsp->n);
171 s->s[s->n] = '\0';
172 e->hash = rapidhashv1(s->s, s->n);
173 free(s);
174 } else {
175 e->hash = rapidhashv1(cmd->s, cmd->n);
176 }
177}
178
179static struct edge *
180mkphony(struct node *n)
181{
182 struct edge *e;
183
184 e = mkedge(rootenv);
185 e->rule = &phonyrule;
186 e->inimpidx = 0;
187 e->inorderidx = 0;
188 e->outimpidx = 1;
189 e->nout = 1;
190 e->out = xmalloc(sizeof(n));
191 e->out[0] = n;
192
193 return e;
194}
195
196void
197edgeadddeps(struct edge *e, struct node **deps, size_t ndeps)
198{
199 struct node **order, *n;
200 size_t norder, i;
201
202 for (i = 0; i < ndeps; ++i) {
203 n = deps[i];
204 if (!n->gen)
205 n->gen = mkphony(n);
206 nodeuse(n, e);
207 }
208 e->in = xreallocarray(e->in, e->nin + ndeps, sizeof(e->in[0]));
209 order = e->in + e->inorderidx;
210 norder = e->nin - e->inorderidx;
211 memmove(order + ndeps, order, norder * sizeof(e->in[0]));
212 memcpy(order, deps, ndeps * sizeof(e->in[0]));
213 e->inorderidx += ndeps;
214 e->nin += ndeps;
215}
