commit ce959b5
xplshn
·
2026-04-28 10:14:45 +0000 UTC
parent 09f3b9c
new memory model & intern table Signed-off-by: xplshn <anto@xplshn.com.ar>
8 files changed,
+411,
-104
+22,
-20
1@@ -15,10 +15,12 @@
2 struct Var *
3 findvar(struct Env *env, const char *name)
4 {
5+ const char *iname;
6 size_t i;
7
8+ iname = intern(name);
9 for (i = 0; i < env->n; i++) {
10- if (strcmp(env->v[i].name, name) == 0)
11+ if (env->v[i].name == iname)
12 return &env->v[i];
13 }
14 return 0;
15@@ -29,13 +31,12 @@ freeenv(struct Env *env)
16 {
17 size_t i;
18
19- for (i = 0; i < env->n; i++) {
20- free(env->v[i].name);
21+ for (i = 0; i < env->n; i++)
22 free(env->v[i].val);
23- }
24 free(env->v);
25 env->v = 0;
26 env->n = 0;
27+ env->cap = 0;
28 }
29
30 void
31@@ -47,13 +48,14 @@ copyenv(struct Env *dst, const struct Env *src)
32 if (src->n)
33 dst->v = xrealloc(0, src->n * sizeof(dst->v[0]));
34 for (i = 0; i < src->n; i++) {
35- dst->v[i].name = xstrdup(src->v[i].name);
36+ dst->v[i].name = src->v[i].name;
37 dst->v[i].val = xstrdup(src->v[i].val);
38 dst->v[i].simple = src->v[i].simple;
39 dst->v[i].origin = src->v[i].origin;
40 dst->v[i].exported = src->v[i].exported;
41 }
42 dst->n = src->n;
43+ dst->cap = src->n;
44 }
45
46 void
47@@ -349,35 +351,33 @@ freeruleset(struct RuleSet *ruleset)
48 memset(ruleset, 0, sizeof(*ruleset));
49 }
50
51+/*
52+ * strings in ast nodes are arena-owned, only free the v arrays and
53+ * the submake strings (xmalloc'd separately by parsesubmake)
54+ */
55 static void
56 freenodes(struct NodeList *list)
57 {
58- size_t i;
59+ size_t i, j;
60
61 for (i = 0; i < list->n; i++) {
62 switch (list->v[i].kind) {
63 case NODE_COMMENT:
64 case NODE_RAW:
65- free(list->v[i].data.raw.text);
66+ case NODE_INCLUDE:
67 break;
68 case NODE_ASSIGN:
69- free(list->v[i].data.assign.lhs);
70- free(list->v[i].data.assign.rhs);
71- freestrs(&list->v[i].data.assign.targets);
72+ free(list->v[i].data.assign.targets.v);
73 break;
74 case NODE_RULE:
75- freestrs(&list->v[i].data.rule.targets);
76- freestrs(&list->v[i].data.rule.prereqs);
77- freestrs(&list->v[i].data.rule.order_only);
78- freerecipes(&list->v[i].data.rule.recipes);
79- break;
80- case NODE_INCLUDE:
81- free(list->v[i].data.include.path);
82+ free(list->v[i].data.rule.targets.v);
83+ free(list->v[i].data.rule.prereqs.v);
84+ free(list->v[i].data.rule.order_only.v);
85+ for (j = 0; j < list->v[i].data.rule.recipes.n; j++)
86+ freesubmake(&list->v[i].data.rule.recipes.v[j].sm);
87+ free(list->v[i].data.rule.recipes.v);
88 break;
89 case NODE_COND:
90- free(list->v[i].data.cond.arg1);
91- free(list->v[i].data.cond.arg2);
92- free(list->v[i].data.cond.raw);
93 freenodes(&list->v[i].data.cond.thenpart);
94 freenodes(&list->v[i].data.cond.elsepart);
95 break;
96@@ -388,10 +388,12 @@ freenodes(struct NodeList *list)
97 free(list->v);
98 list->v = 0;
99 list->n = 0;
100+ list->cap = 0;
101 }
102
103 void
104 freeast(struct Ast *ast)
105 {
106 freenodes((struct NodeList *)ast);
107+ arena_free(&ast->arena);
108 }
+3,
-4
1@@ -126,7 +126,7 @@ addrule(struct GraphState *gs, const char *name, const struct RuleNode *rule)
2 gs->graph->v = xrealloc(gs->graph->v, (gs->graph->n + 1) * sizeof(gs->graph->v[0]));
3 t = &gs->graph->v[gs->graph->n++];
4 memset(t, 0, sizeof(*t));
5- t->name = xstrdup(name);
6+ t->name = intern(name);
7 t->dcolon = rule->dcolon;
8 } else if (t->defined && t->dcolon != rule->dcolon) {
9 fprintf(stderr, "target file `%s' has both : and :: entries, i can't handle that!\n", name);
10@@ -148,7 +148,7 @@ addrule(struct GraphState *gs, const char *name, const struct RuleNode *rule)
11 gs->graph->v = xrealloc(gs->graph->v, (gs->graph->n + 1) * sizeof(gs->graph->v[0]));
12 t = &gs->graph->v[gs->graph->n++];
13 memset(t, 0, sizeof(*t));
14- t->name = xstrdup(rule->prereqs.v[i]);
15+ t->name = intern(rule->prereqs.v[i]);
16 copyenv(&t->env, &env);
17 }
18 }
19@@ -259,7 +259,7 @@ buildgraph(const struct RuleSet *ruleset, struct Graph *graph)
20 graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
21 nt = &graph->v[graph->n++];
22 memset(nt, 0, sizeof(*nt));
23- nt->name = xstrdup(prereq);
24+ nt->name = intern(prereq);
25 t = &graph->v[i];
26 }
27 }
28@@ -357,7 +357,6 @@ freegraph(struct Graph *graph)
29 if (!graph)
30 return;
31 for (i = 0; i < graph->n; i++) {
32- free(graph->v[i].name);
33 free(graph->v[i].owner);
34 freestrs(&graph->v[i].prereqs);
35 freestrs(&graph->v[i].order_only);
+21,
-17
1@@ -149,22 +149,30 @@ instack(const struct SubGraphStack *stack, const char *key)
2 static char *
3 subgraphkey(const struct SubGraph *sg)
4 {
5- size_t i, n;
6+ size_t i, n, pos, len;
7 char *key;
8
9 n = strlen(sg->cwd) + 1 + strlen(sg->makefile ? sg->makefile : "") + 1;
10 for (i = 0; i < sg->assigns.n; i++)
11 n += strlen(sg->assigns.v[i]) + 1;
12 key = xmalloc(n + 1);
13- key[0] = 0;
14- strcat(key, sg->cwd);
15- strcat(key, "|");
16- if (sg->makefile)
17- strcat(key, sg->makefile);
18+ pos = 0;
19+ len = strlen(sg->cwd);
20+ memcpy(key + pos, sg->cwd, len);
21+ pos += len;
22+ key[pos++] = '|';
23+ if (sg->makefile) {
24+ len = strlen(sg->makefile);
25+ memcpy(key + pos, sg->makefile, len);
26+ pos += len;
27+ }
28 for (i = 0; i < sg->assigns.n; i++) {
29- strcat(key, "|");
30- strcat(key, sg->assigns.v[i]);
31+ key[pos++] = '|';
32+ len = strlen(sg->assigns.v[i]);
33+ memcpy(key + pos, sg->assigns.v[i], len);
34+ pos += len;
35 }
36+ key[pos] = 0;
37 return key;
38 }
39
40@@ -225,8 +233,8 @@ scopegraph(struct Graph *graph, const char *prefix)
41 char *name;
42
43 name = rebaseword(prefix, graph->v[i].name);
44- free(graph->v[i].name);
45- graph->v[i].name = name;
46+ graph->v[i].name = intern(name);
47+ free(name);
48 free(graph->v[i].owner);
49 if (graph->v[i].defined || graph->v[i].recipes.n > 0 ||
50 graph->v[i].prereqs.n > 0 || graph->v[i].order_only.n > 0)
51@@ -249,7 +257,7 @@ mergetarget(struct Graph *graph, const struct Target *src)
52 graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
53 dst = &graph->v[graph->n++];
54 memset(dst, 0, sizeof(*dst));
55- dst->name = xstrdup(src->name);
56+ dst->name = src->name;
57 if (src->owner)
58 dst->owner = xstrdup(src->owner);
59 } else if (!dst->owner && src->owner) {
60@@ -404,11 +412,11 @@ expandsubgraphs(struct SubGraph *sg, struct SubGraphStack *stack)
61
62 for (i = 0; i < sg->graph.n; i++) {
63 size_t k;
64- char *tname;
65+ const char *tname;
66 struct StrList prevgoals;
67
68 memset(&prevgoals, 0, sizeof(prevgoals));
69- tname = xstrdup(sg->graph.v[i].name);
70+ tname = sg->graph.v[i].name;
71 for (k = 0; k < sg->graph.v[i].recipes.n;) {
72 struct Recipe *r;
73 struct SubGraph child;
74@@ -444,7 +452,6 @@ expandsubgraphs(struct SubGraph *sg, struct SubGraphStack *stack)
75 if (rc < 0) {
76 freesubgraph(&child);
77 freestrs(&prevgoals);
78- free(tname);
79 return -1;
80 }
81 /* remove the make invocation, we replace it with a graph*/
82@@ -452,7 +459,6 @@ expandsubgraphs(struct SubGraph *sg, struct SubGraphStack *stack)
83 if (resolvegoals(&child, &goals) < 0) {
84 freesubgraph(&child);
85 freestrs(&prevgoals);
86- free(tname);
87 return -1;
88 }
89 subgraphorder(&child.graph, child.prefix, &prevgoals);
90@@ -460,7 +466,6 @@ expandsubgraphs(struct SubGraph *sg, struct SubGraphStack *stack)
91 freesubgraph(&child);
92 freestrs(&goals);
93 freestrs(&prevgoals);
94- free(tname);
95 return -1;
96 }
97 freestrs(&prevgoals);
98@@ -470,7 +475,6 @@ expandsubgraphs(struct SubGraph *sg, struct SubGraphStack *stack)
99 freesubgraph(&child);
100 }
101 freestrs(&prevgoals);
102- free(tname);
103 }
104 return 0;
105 }
+6,
-0
1@@ -30,6 +30,12 @@ void *xmalloc(size_t n);
2 void *xrealloc(void *p, size_t n);
3 char *xstrndup(const char *s, size_t n);
4 char *xstrdup(const char *s);
5+void arena_init(struct Arena *a, size_t block_size);
6+void *arena_alloc(struct Arena *a, size_t n);
7+char *arena_strndup(struct Arena *a, const char *s, size_t n);
8+char *arena_strdup(struct Arena *a, const char *s);
9+void arena_free(struct Arena *a);
10+const char *intern(const char *s);
11 char *readfile(const char *path);
12 int loadmakefile(const char *path, char **path_out, char **src_out);
13 char *appendassigns(char *src, const struct StrList *assigns);
+146,
-38
1@@ -31,11 +31,49 @@ struct Inc {
2
3 static int parseerrs;
4 static int deadlikemake;
5+static struct Arena *g_ast_arena;
6
7 static int preprocfile(const char *path, const char *src_override, struct Pre *pre, struct Inc *inc);
8 static int preprocfile0(const char *path, const char *src_override, struct Pre *pre, struct Inc *inc,
9 struct SpecialTargets *targets);
10
11+static char *
12+astdup(const char *s, size_t n)
13+{
14+ return arena_strndup(g_ast_arena, s, n);
15+}
16+
17+static char *
18+atrimdup(const char *s, size_t n)
19+{
20+ size_t i, j;
21+
22+ for (i = 0; i < n && isspace((unsigned char)s[i]); i++)
23+ ;
24+ for (j = n; j > i && isspace((unsigned char)s[j - 1]); j--)
25+ ;
26+ return astdup(s + i, j - i);
27+}
28+
29+static void
30+astsplitwords(struct StrList *out, const char *s, size_t n);
31+
32+static void
33+addrecipe_ast(struct RecipeList *dest, const char *raw);
34+
35+static void
36+addwords_ast(struct StrList *dest, const struct StrList *src)
37+{
38+ size_t i;
39+
40+ if (dest->n + src->n > dest->cap) {
41+ dest->cap = dest->n + src->n;
42+ dest->v = xrealloc(dest->v, dest->cap * sizeof(dest->v[0]));
43+ }
44+ for (i = 0; i < src->n; i++)
45+ dest->v[dest->n++] = src->v[i];
46+}
47+
48 static void
49 parseerr(const struct PreLine *line, const char *msg, const char *detail)
50 {
51@@ -299,12 +337,77 @@ splitwords(struct StrList *out, const char *s, size_t n)
52 break;
53 j++;
54 }
55- out->v = xrealloc(out->v, (out->n + 1) * sizeof(out->v[0]));
56+ if (out->n >= out->cap) {
57+ out->cap = out->cap ? out->cap * 2 : 4;
58+ out->v = xrealloc(out->v, out->cap * sizeof(out->v[0]));
59+ }
60 out->v[out->n++] = xstrndup(s + start, j - start);
61 i = j;
62 }
63 }
64
65+static void
66+astsplitwords(struct StrList *out, const char *s, size_t n)
67+{
68+ size_t i, j, start;
69+
70+ for (i = 0; i < n;) {
71+ while (i < n && isspace((unsigned char)s[i]))
72+ i++;
73+ if (i >= n)
74+ break;
75+ start = i;
76+ j = i;
77+ while (j < n) {
78+ if (s[j] == '$' && skipref(s, n, &j))
79+ continue;
80+ if (isspace((unsigned char)s[j]))
81+ break;
82+ j++;
83+ }
84+ if (out->n >= out->cap) {
85+ out->cap = out->cap ? out->cap * 2 : 4;
86+ out->v = xrealloc(out->v, out->cap * sizeof(out->v[0]));
87+ }
88+ out->v[out->n++] = astdup(s + start, j - start);
89+ i = j;
90+ }
91+}
92+
93+static void
94+addrecipe_ast(struct RecipeList *dest, const char *raw)
95+{
96+ struct Recipe *r;
97+ const char *s;
98+ size_t n;
99+
100+ s = raw;
101+ while (*s == ' ' || *s == '\t')
102+ s++;
103+ if (dest->n >= dest->cap) {
104+ dest->cap = dest->cap ? dest->cap * 2 : 4;
105+ dest->v = xrealloc(dest->v, dest->cap * sizeof(dest->v[0]));
106+ }
107+ r = &dest->v[dest->n++];
108+ memset(r, 0, sizeof(*r));
109+ while (*s == '@' || *s == '+' || *s == '-') {
110+ if (*s == '@')
111+ r->silent = 1;
112+ else if (*s == '+')
113+ r->recursive = 1;
114+ else if (*s == '-')
115+ r->ignore = 1;
116+ s++;
117+ while (*s == ' ' || *s == '\t')
118+ s++;
119+ }
120+ n = strlen(s);
121+ while (n > 0 && isspace((unsigned char)s[n - 1]))
122+ n--;
123+ r->body = astdup(s, n);
124+ r->submake = parsesubmake(&r->sm, r->body);
125+}
126+
127 static int
128 readline(const char **src, int *lineno, struct PreLine *line, char recipeprefix)
129 {
130@@ -592,7 +695,7 @@ parseinclude(const struct PreLine *line, const char *s)
131 } else {
132 off = strlen("include");
133 }
134- state.data.include.path = trimdup(s + off, strlen(s + off));
135+ state.data.include.path = atrimdup(s + off, strlen(s + off));
136 return state;
137 }
138
139@@ -607,7 +710,7 @@ parsecond(const struct PreLine *line, const char *s)
140 state.kind = NODE_COND;
141 state.loc.line0 = line->line0;
142 state.loc.line1 = line->line1;
143- state.data.cond.raw = xstrndup(s, strlen(s));
144+ state.data.cond.raw = astdup(s, strlen(s));
145
146 if (haskw(s, "ifeq")) {
147 state.data.cond.kind = COND_IFEQ;
148@@ -630,26 +733,24 @@ parsecond(const struct PreLine *line, const char *s)
149 p++;
150 n = strlen(p);
151 if (!n) {
152- state.data.cond.arg1 = xstrndup("", 0);
153- state.data.cond.arg2 = xstrndup("", 0);
154+ state.data.cond.arg1 = astdup("", 0);
155+ state.data.cond.arg2 = astdup("", 0);
156 return state;
157 }
158 if (state.data.cond.kind == COND_IFDEF || state.data.cond.kind == COND_IFNDEF) {
159- state.data.cond.arg1 = xstrndup(p, n);
160- state.data.cond.arg2 = xstrndup("", 0);
161+ state.data.cond.arg1 = astdup(p, n);
162+ state.data.cond.arg2 = astdup("", 0);
163 return state;
164 }
165 if (p[0] == '(' && p[n - 1] == ')') {
166- state.data.cond.arg1 = xstrndup("", 0);
167- state.data.cond.arg2 = xstrndup("", 0);
168 mid = (size_t)(findtop(p + 1, n - 2, ','));
169 if (mid != (size_t)-1) {
170- free(state.data.cond.arg1);
171- free(state.data.cond.arg2);
172- state.data.cond.arg1 = trimdup(p + 1, mid);
173- state.data.cond.arg2 = trimdup(p + 2 + mid, n - 3 - mid);
174+ state.data.cond.arg1 = atrimdup(p + 1, mid);
175+ state.data.cond.arg2 = atrimdup(p + 2 + mid, n - 3 - mid);
176 } else {
177 parseerr(line, "malformed ifeq/ifneq arguments", p);
178+ state.data.cond.arg1 = astdup("", 0);
179+ state.data.cond.arg2 = astdup("", 0);
180 }
181 } else if (p[0] == '"' || p[0] == '\'') {
182 size_t e1, s2, e2;
183@@ -659,8 +760,8 @@ parsecond(const struct PreLine *line, const char *s)
184 e1++;
185 if (e1 >= n) {
186 parseerr(line, "malformed ifeq/ifneq arguments", p);
187- state.data.cond.arg1 = xstrndup("", 0);
188- state.data.cond.arg2 = xstrndup("", 0);
189+ state.data.cond.arg1 = astdup("", 0);
190+ state.data.cond.arg2 = astdup("", 0);
191 return state;
192 }
193 s2 = e1 + 1;
194@@ -668,8 +769,8 @@ parsecond(const struct PreLine *line, const char *s)
195 s2++;
196 if (s2 >= n || (p[s2] != '"' && p[s2] != '\'')) {
197 parseerr(line, "malformed ifeq/ifneq arguments", p);
198- state.data.cond.arg1 = xstrndup("", 0);
199- state.data.cond.arg2 = xstrndup("", 0);
200+ state.data.cond.arg1 = astdup("", 0);
201+ state.data.cond.arg2 = astdup("", 0);
202 return state;
203 }
204 q2 = p[s2];
205@@ -678,16 +779,16 @@ parsecond(const struct PreLine *line, const char *s)
206 e2++;
207 if (e2 >= n || e2 != n - 1) {
208 parseerr(line, "malformed ifeq/ifneq arguments", p);
209- state.data.cond.arg1 = xstrndup("", 0);
210- state.data.cond.arg2 = xstrndup("", 0);
211+ state.data.cond.arg1 = astdup("", 0);
212+ state.data.cond.arg2 = astdup("", 0);
213 return state;
214 }
215- state.data.cond.arg1 = xstrndup(p + 1, e1 - 1);
216- state.data.cond.arg2 = xstrndup(p + s2 + 1, e2 - s2 - 1);
217+ state.data.cond.arg1 = astdup(p + 1, e1 - 1);
218+ state.data.cond.arg2 = astdup(p + s2 + 1, e2 - s2 - 1);
219 } else {
220 parseerr(line, "malformed ifeq/ifneq arguments", p);
221- state.data.cond.arg1 = xstrndup("", 0);
222- state.data.cond.arg2 = xstrndup("", 0);
223+ state.data.cond.arg1 = astdup("", 0);
224+ state.data.cond.arg2 = astdup("", 0);
225 }
226 return state;
227 }
228@@ -704,10 +805,10 @@ parseassign(const struct PreLine *line, const char *s, size_t n, size_t base, st
229 state.data.assign.op = as.op;
230 state.data.assign.exported = 0;
231 state.data.assign.tspec = tspec;
232- state.data.assign.lhs = trimdup(s + base, as.pos - base);
233- state.data.assign.rhs = trimdup(s + as.pos + as.len, n - as.pos - as.len);
234+ state.data.assign.lhs = atrimdup(s + base, as.pos - base);
235+ state.data.assign.rhs = atrimdup(s + as.pos + as.len, n - as.pos - as.len);
236 if (tspec)
237- splitwords(&state.data.assign.targets, s, tend);
238+ astsplitwords(&state.data.assign.targets, s, tend);
239 return state;
240 }
241
242@@ -726,7 +827,7 @@ parserule(const struct PreLine *line, const char *s, size_t n, size_t colon, int
243 state.loc.line1 = line->line1;
244 state.data.rule.dcolon = dcolon;
245
246- splitwords(&state.data.rule.targets, s, colon);
247+ astsplitwords(&state.data.rule.targets, s, colon);
248
249 off = dcolon ? 2 : 1;
250 rhs = s + colon + off;
251@@ -735,7 +836,7 @@ parserule(const struct PreLine *line, const char *s, size_t n, size_t colon, int
252 if (semi != (size_t)-1) {
253 recipe = trimdup(rhs + semi + 1, rhsn - semi - 1);
254 if (recipe[0]) {
255- addrecipe(&state.data.rule.recipes, recipe);
256+ addrecipe_ast(&state.data.rule.recipes, recipe);
257 free(recipe);
258 } else {
259 free(recipe);
260@@ -744,10 +845,10 @@ parserule(const struct PreLine *line, const char *s, size_t n, size_t colon, int
261 }
262 split = (size_t)findtop(rhs, rhsn, '|');
263 if (split != (size_t)-1) {
264- splitwords(&state.data.rule.prereqs, rhs, split);
265- splitwords(&state.data.rule.order_only, rhs + split + 1, rhsn - split - 1);
266+ astsplitwords(&state.data.rule.prereqs, rhs, split);
267+ astsplitwords(&state.data.rule.order_only, rhs + split + 1, rhsn - split - 1);
268 } else {
269- splitwords(&state.data.rule.prereqs, rhs, rhsn);
270+ astsplitwords(&state.data.rule.prereqs, rhs, rhsn);
271 }
272 return state;
273 }
274@@ -761,7 +862,7 @@ parseexpr(const struct PreLine *line, const char *s)
275 state.kind = NODE_RAW;
276 state.loc.line0 = line->line0;
277 state.loc.line1 = line->line1;
278- state.data.raw.text = xstrndup(s, strlen(s));
279+ state.data.raw.text = astdup(s, strlen(s));
280 return state;
281 }
282
283@@ -817,7 +918,7 @@ branchrule(struct NodeList *out, const struct Node *src, const struct PreLine *l
284 state.loc.line0 = line->line0;
285 state.loc.line1 = line->line1;
286 state.data.rule.dcolon = src->data.rule.dcolon;
287- addwords(&state.data.rule.targets, &src->data.rule.targets);
288+ addwords_ast(&state.data.rule.targets, &src->data.rule.targets);
289 addnode(out, state);
290 return &out->v[out->n - 1];
291 }
292@@ -833,7 +934,7 @@ parsedefine(const struct Pre *pre, size_t *i, struct Node *out)
293
294 line = &pre->v[*i];
295 trim = trimdup(line->text, strlen(line->text));
296- name = trimdup(trim + strlen("define"), strlen(trim + strlen("define")));
297+ name = atrimdup(trim + strlen("define"), strlen(trim + strlen("define")));
298 free(trim);
299
300 memset(out, 0, sizeof(*out));
301@@ -866,7 +967,8 @@ parsedefine(const struct Pre *pre, size_t *i, struct Node *out)
302 if (depth == 0) {
303 out->loc.line1 = cur->line1;
304 (*i)++;
305- out->data.assign.rhs = body;
306+ out->data.assign.rhs = astdup(body, bodylen);
307+ free(body);
308 return 0;
309 }
310 } else {
311@@ -937,7 +1039,8 @@ parseline(const struct PreLine *line, const struct SpecialTargets *targets)
312 state.kind = NODE_COMMENT;
313 state.loc.line0 = line->line0;
314 state.loc.line1 = line->line1;
315- state.data.raw.text = trim;
316+ state.data.raw.text = astdup(trim, strlen(trim));
317+ free(trim);
318 return state;
319 }
320 if (strncmp(trim, "ifeq(", 5) == 0 || strncmp(trim, "ifneq(", 6) == 0) {
321@@ -1068,7 +1171,7 @@ parseblock(const struct Pre *pre, size_t *i, struct NodeList *out, struct Node *
322 if (last_rule) {
323 if (!ruleinlist(out, last_rule))
324 last_rule = branchrule(out, last_rule, line);
325- addrecipe(&last_rule->data.rule.recipes, line->text + 1);
326+ addrecipe_ast(&last_rule->data.rule.recipes, line->text + 1);
327 last_rule->loc.line1 = line->line1;
328 (*i)++;
329 continue;
330@@ -1185,14 +1288,19 @@ buildast(const char *path, const struct Pre *pre, struct Ast *ast)
331 {
332 size_t i;
333 struct SpecialTargets targets;
334+ int rc;
335
336 (void)path;
337 memset(ast, 0, sizeof(*ast));
338+ arena_init(&ast->arena, 0);
339+ g_ast_arena = &ast->arena;
340 parseerrs = 0;
341 deadlikemake = 0;
342 initspecialtargets(&targets);
343 i = 0;
344- if (parseblock(pre, &i, (struct NodeList *)ast, 0, &targets) < 0)
345+ rc = parseblock(pre, &i, (struct NodeList *)ast, 0, &targets);
346+ g_ast_arena = 0;
347+ if (rc < 0)
348 return deadlikemake ? -2 : -1;
349 if (i < pre->n) {
350 char *trim;
+2,
-6
1@@ -92,12 +92,8 @@ addimpdouble(struct SufRules *rules,
2 static int
3 pathorargetexists(const struct Graph *graph, const char *name)
4 {
5- size_t i;
6-
7- for (i = 0; i < graph->n; i++) {
8- if (strcmp(graph->v[i].name, name) == 0)
9- return 1;
10- }
11+ if (findctarget(graph, name))
12+ return 1;
13 return access(name, F_OK) == 0;
14 }
15
+15,
-2
1@@ -11,6 +11,13 @@
2 * Ast: parsed nodes in source order with nested cond blocks
3 */
4
5+struct ArenaBlock;
6+
7+struct Arena {
8+ struct ArenaBlock *head;
9+ size_t block_size;
10+};
11+
12 enum NodeKind {
13 NODE_BLANK,
14 NODE_COMMENT,
15@@ -69,6 +76,7 @@ struct Pre {
16 struct StrList {
17 char **v;
18 size_t n;
19+ size_t cap;
20 };
21
22 struct SubMake {
23@@ -92,6 +100,7 @@ struct Recipe {
24 struct RecipeList {
25 struct Recipe *v;
26 size_t n;
27+ size_t cap;
28 };
29
30 struct AssignNode {
31@@ -126,6 +135,7 @@ struct Node;
32 struct NodeList {
33 struct Node *v;
34 size_t n;
35+ size_t cap;
36 };
37
38 struct CondNode {
39@@ -152,6 +162,8 @@ struct Node {
40 struct Ast {
41 struct Node *v;
42 size_t n;
43+ size_t cap;
44+ struct Arena arena;
45 };
46
47 struct RuleSet {
48@@ -166,7 +178,7 @@ struct RuleSet {
49 };
50
51 struct Var {
52- char *name;
53+ const char *name; /* interned */
54 char *val;
55 int simple;
56 enum Origin origin;
57@@ -176,10 +188,11 @@ struct Var {
58 struct Env {
59 struct Var *v;
60 size_t n;
61+ size_t cap;
62 };
63
64 struct Target {
65- char *name;
66+ const char *name; /* interned */
67 char *owner;
68 struct StrList prereqs;
69 struct StrList order_only;
+196,
-17
1@@ -51,6 +51,149 @@ xstrdup(const char *s)
2 return xstrndup(s, strlen(s));
3 }
4
5+/* bump-pointer arena: alloc grows a slab chain, arena_free drops all slabs */
6+
7+struct ArenaBlock {
8+ struct ArenaBlock *next;
9+ size_t cap;
10+ size_t pos;
11+ /* data follows in memory */
12+};
13+
14+#define ARENA_DEFAULT_BLOCK (64 * 1024)
15+#define ARENA_ALIGN sizeof(void *)
16+
17+void
18+arena_init(struct Arena *a, size_t block_size)
19+{
20+ a->head = 0;
21+ a->block_size = block_size ? block_size : ARENA_DEFAULT_BLOCK;
22+}
23+
24+void *
25+arena_alloc(struct Arena *a, size_t n)
26+{
27+ struct ArenaBlock *b;
28+ size_t aligned;
29+ char *p;
30+
31+ aligned = (n + ARENA_ALIGN - 1) & ~(ARENA_ALIGN - 1);
32+ b = a->head;
33+ if (!b || b->pos + aligned > b->cap) {
34+ size_t bsz;
35+
36+ bsz = aligned > a->block_size ? aligned : a->block_size;
37+ b = xmalloc(sizeof(*b) + bsz);
38+ b->cap = bsz;
39+ b->pos = 0;
40+ b->next = a->head;
41+ a->head = b;
42+ }
43+ p = (char *)(b + 1) + b->pos;
44+ b->pos += aligned;
45+ return p;
46+}
47+
48+char *
49+arena_strndup(struct Arena *a, const char *s, size_t n)
50+{
51+ char *p;
52+
53+ p = arena_alloc(a, n + 1);
54+ memcpy(p, s, n);
55+ p[n] = 0;
56+ return p;
57+}
58+
59+char *
60+arena_strdup(struct Arena *a, const char *s)
61+{
62+ return arena_strndup(a, s, strlen(s));
63+}
64+
65+void
66+arena_free(struct Arena *a)
67+{
68+ struct ArenaBlock *b, *next;
69+
70+ for (b = a->head; b; b = next) {
71+ next = b->next;
72+ free(b);
73+ }
74+ a->head = 0;
75+}
76+
77+/* intern table: == is enough to compare, strings live til exit */
78+
79+#define INTERN_INIT_CAP 512
80+
81+struct InternEntry {
82+ const char *s;
83+ size_t h;
84+};
85+
86+static struct InternEntry *intern_table;
87+static size_t intern_n;
88+static size_t intern_cap;
89+
90+static size_t
91+strhash(const char *s)
92+{
93+ /* fnv-1a */
94+ size_t h = 2166136261u;
95+ while (*s) {
96+ h ^= (unsigned char)*s++;
97+ h *= 16777619u;
98+ }
99+ return h;
100+}
101+
102+static void
103+interngrow(void)
104+{
105+ size_t i, newcap;
106+ struct InternEntry *newtbl;
107+
108+ newcap = intern_cap ? intern_cap * 2 : INTERN_INIT_CAP;
109+ newtbl = xmalloc(newcap * sizeof(newtbl[0]));
110+ memset(newtbl, 0, newcap * sizeof(newtbl[0]));
111+ for (i = 0; i < intern_cap; i++) {
112+ size_t j;
113+
114+ if (!intern_table[i].s)
115+ continue;
116+ j = intern_table[i].h & (newcap - 1);
117+ while (newtbl[j].s)
118+ j = (j + 1) & (newcap - 1);
119+ newtbl[j] = intern_table[i];
120+ }
121+ free(intern_table);
122+ intern_table = newtbl;
123+ intern_cap = newcap;
124+}
125+
126+const char *
127+intern(const char *s)
128+{
129+ size_t h, i;
130+
131+ if (!intern_cap || intern_n * 3 >= intern_cap * 2)
132+ interngrow();
133+ h = strhash(s);
134+ i = h & (intern_cap - 1);
135+ for (;;) {
136+ if (!intern_table[i].s) {
137+ intern_table[i].s = xstrdup(s);
138+ intern_table[i].h = h;
139+ intern_n++;
140+ return intern_table[i].s;
141+ }
142+ if (intern_table[i].h == h && strcmp(intern_table[i].s, s) == 0)
143+ return intern_table[i].s;
144+ i = (i + 1) & (intern_cap - 1);
145+ }
146+}
147+
148 char *
149 readfile(const char *path)
150 {
151@@ -254,22 +397,40 @@ normpath(const char *path)
152 char *
153 joinstrs(const struct StrList *list, const char *sep)
154 {
155- size_t i;
156- char *s, *next;
157+ size_t i, seplen, total, pos;
158+ char *s;
159
160- s = xstrdup("");
161+ if (!list->n)
162+ return xstrdup("");
163+ seplen = strlen(sep);
164+ total = 0;
165+ for (i = 0; i < list->n; i++)
166+ total += strlen(list->v[i]);
167+ total += seplen * (list->n - 1);
168+ s = xmalloc(total + 1);
169+ pos = 0;
170 for (i = 0; i < list->n; i++) {
171- next = s[0] ? cat3(s, sep, list->v[i]) : xstrdup(list->v[i]);
172- free(s);
173- s = next;
174+ size_t n;
175+
176+ if (i > 0) {
177+ memcpy(s + pos, sep, seplen);
178+ pos += seplen;
179+ }
180+ n = strlen(list->v[i]);
181+ memcpy(s + pos, list->v[i], n);
182+ pos += n;
183 }
184+ s[pos] = 0;
185 return s;
186 }
187
188 void
189 addstr(struct StrList *list, const char *s)
190 {
191- list->v = xrealloc(list->v, (list->n + 1) * sizeof(list->v[0]));
192+ if (list->n >= list->cap) {
193+ list->cap = list->cap ? list->cap * 2 : 4;
194+ list->v = xrealloc(list->v, list->cap * sizeof(list->v[0]));
195+ }
196 list->v[list->n++] = xstrdup(s);
197 }
198
199@@ -307,7 +468,7 @@ defaulttarget(const struct Graph *graph, const char *owner)
200 for (i = 0; i < graph->n; i++) {
201 if (!targetownedby(&graph->v[i], owner))
202 continue;
203- if (strcmp(graph->v[i].name, "clean") == 0 || strcmp(graph->v[i].name, "fmt") == 0)
204+ if (graph->v[i].name == intern("clean") || graph->v[i].name == intern("fmt"))
205 continue;
206 if (graph->v[i].recipes.n > 0 || graph->v[i].prereqs.n > 0 || graph->v[i].order_only.n > 0)
207 return &graph->v[i];
208@@ -335,7 +496,10 @@ cat3(const char *a, const char *b, const char *c)
209 void
210 addnode(struct NodeList *list, struct Node node)
211 {
212- list->v = xrealloc(list->v, (list->n + 1) * sizeof(list->v[0]));
213+ if (list->n >= list->cap) {
214+ list->cap = list->cap ? list->cap * 2 : 4;
215+ list->v = xrealloc(list->v, list->cap * sizeof(list->v[0]));
216+ }
217 list->v[list->n++] = node;
218 }
219
220@@ -344,10 +508,12 @@ addwords(struct StrList *dest, const struct StrList *src)
221 {
222 size_t i;
223
224- for (i = 0; i < src->n; i++) {
225- dest->v = xrealloc(dest->v, (dest->n + 1) * sizeof(dest->v[0]));
226- dest->v[dest->n++] = xstrdup(src->v[i]);
227+ if (dest->n + src->n > dest->cap) {
228+ dest->cap = dest->n + src->n;
229+ dest->v = xrealloc(dest->v, dest->cap * sizeof(dest->v[0]));
230 }
231+ for (i = 0; i < src->n; i++)
232+ dest->v[dest->n++] = xstrdup(src->v[i]);
233 }
234
235 void
236@@ -360,7 +526,10 @@ addrecipe(struct RecipeList *dest, const char *raw)
237 s = raw;
238 while (*s == ' ' || *s == '\t')
239 s++;
240- dest->v = xrealloc(dest->v, (dest->n + 1) * sizeof(dest->v[0]));
241+ if (dest->n >= dest->cap) {
242+ dest->cap = dest->cap ? dest->cap * 2 : 4;
243+ dest->v = xrealloc(dest->v, dest->cap * sizeof(dest->v[0]));
244+ }
245 r = &dest->v[dest->n++];
246 memset(r, 0, sizeof(*r));
247 while (*s == '@' || *s == '+' || *s == '-') {
248@@ -386,8 +555,11 @@ addrecipes(struct RecipeList *dest, const struct RecipeList *src)
249 {
250 size_t i;
251
252+ if (dest->n + src->n > dest->cap) {
253+ dest->cap = dest->n + src->n;
254+ dest->v = xrealloc(dest->v, dest->cap * sizeof(dest->v[0]));
255+ }
256 for (i = 0; i < src->n; i++) {
257- dest->v = xrealloc(dest->v, (dest->n + 1) * sizeof(dest->v[0]));
258 dest->v[dest->n].body = xstrdup(src->v[i].body);
259 dest->v[dest->n].silent = src->v[i].silent;
260 dest->v[dest->n].ignore = src->v[i].ignore;
261@@ -401,10 +573,12 @@ addrecipes(struct RecipeList *dest, const struct RecipeList *src)
262 static const struct Target *
263 findtarget0(const struct Graph *graph, const char *name)
264 {
265+ const char *iname;
266 size_t i;
267
268+ iname = intern(name);
269 for (i = 0; i < graph->n; i++) {
270- if (strcmp(graph->v[i].name, name) == 0)
271+ if (graph->v[i].name == iname)
272 return &graph->v[i];
273 }
274 return 0;
275@@ -434,6 +608,7 @@ freestrs(struct StrList *list)
276 free(list->v);
277 list->v = 0;
278 list->n = 0;
279+ list->cap = 0;
280 }
281
282 void
283@@ -450,6 +625,7 @@ freerecipes(struct RecipeList *list)
284 free(list->v);
285 list->v = 0;
286 list->n = 0;
287+ list->cap = 0;
288 }
289
290 void
291@@ -471,8 +647,11 @@ envsetvar(struct Env *env, const char *name, char *val, int simple, enum Origin
292 v->exported = 1;
293 return;
294 }
295- env->v = xrealloc(env->v, (env->n + 1) * sizeof(env->v[0]));
296- env->v[env->n].name = xstrdup(name);
297+ if (env->n >= env->cap) {
298+ env->cap = env->cap ? env->cap * 2 : 4;
299+ env->v = xrealloc(env->v, env->cap * sizeof(env->v[0]));
300+ }
301+ env->v[env->n].name = intern(name);
302 env->v[env->n].val = val;
303 env->v[env->n].simple = simple;
304 env->v[env->n].origin = origin;