1 /* $OpenBSD: targequiv.c,v 1.11 2024/06/18 02:11:04 millert Exp $ */
2 /*
3 * Copyright (c) 2007-2008 Marc Espie.
4 *
5 * Extensive code changes for the OpenBSD project.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENBSD
20 * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /* Compute equivalence tables of targets, helpful for VPATH and parallel
30 * make.
31 */
32
33 #include <stddef.h>
34 #include <stdint.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <ohash.h>
39 #include <limits.h>
40 #include "defines.h"
41 #include "memory.h"
42 #include "gnode.h"
43 #include "lst.h"
44 #include "suff.h"
45 #include "dir.h"
46 #include "targ.h"
47 #include "targequiv.h"
48
49 struct equiv_list {
50 GNode *first, *last;
51 char name[1];
52 };
53
54 static struct ohash_info equiv_info = {
55 offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free,
56 element_alloc
57 };
58
59 static void attach_node(GNode *, GNode *);
60 static void build_equivalence(void);
61 static void add_to_equiv_list(struct ohash *, GNode *);
62 static char *names_match(GNode *, GNode *);
63 static char *names_match_with_dir(const char *, const char *, char *,
64 char *, const char *);
65 static char *names_match_with_dirs(const char *, const char *, char *,
66 char *, const char *, const char *);
67 static char *relative_reduce(const char *, const char *);
68 static char *relative_reduce2(const char *, const char *, const char *);
69 static char *absolute_reduce(const char *);
70 static size_t parse_reduce(size_t, const char *);
71 static void find_siblings(GNode *);
72
73 /* These functions build `equivalence lists' of targets with the same
74 * basename, as circular lists. They use an intermediate ohash as scaffold,
75 * to insert same-basename targets in a simply linked list. Then they make
76 * those lists circular, to the exception of lone elements, since they can't
77 * alias to anything.
78 *
79 * This structure is used to simplify alias-lookup to a great extent: two
80 * nodes can only alias each other if they're part of the same equivalence
81 * set. Most nodes either don't belong to an alias set, or to a very simple
82 * alias set, thus removing most possibilities.
83 */
84 static void
add_to_equiv_list(struct ohash * equiv,GNode * gn)85 add_to_equiv_list(struct ohash *equiv, GNode *gn)
86 {
87 const char *end = NULL;
88 struct equiv_list *e;
89 unsigned int slot;
90
91 if (!should_have_file(gn))
92 return;
93
94 gn->basename = strrchr(gn->name, '/');
95 if (gn->basename == NULL)
96 gn->basename = gn->name;
97 else
98 gn->basename++;
99 slot = ohash_qlookupi(equiv, gn->basename, &end);
100 e = ohash_find(equiv, slot);
101 if (e == NULL) {
102 e = ohash_create_entry(&equiv_info, gn->basename, &end);
103 e->first = NULL;
104 e->last = gn;
105 ohash_insert(equiv, slot, e);
106 }
107 gn->next = e->first;
108 e->first = gn;
109 }
110
111 static void
build_equivalence(void)112 build_equivalence(void)
113 {
114 unsigned int i;
115 GNode *gn;
116 struct equiv_list *e;
117 struct ohash equiv;
118 struct ohash *t = targets_hash();
119
120
121 ohash_init(&equiv, 10, &equiv_info);
122
123 for (gn = ohash_first(t, &i); gn != NULL; gn = ohash_next(t, &i))
124 add_to_equiv_list(&equiv, gn);
125
126 /* finish making the lists circular */
127 for (e = ohash_first(&equiv, &i); e != NULL;
128 e = ohash_next(&equiv, &i)) {
129 if (e->last != e->first)
130 e->last->next = e->first;
131 free(e);
132 }
133 ohash_delete(&equiv);
134 }
135
136 static const char *curdir, *objdir;
137 static char *kobjdir;
138 static size_t objdir_len;
139
140 void
Targ_setdirs(const char * c,const char * o)141 Targ_setdirs(const char *c, const char *o)
142 {
143 curdir = c;
144 objdir = o;
145
146 objdir_len = strlen(o);
147 kobjdir = emalloc(objdir_len+2);
148 memcpy(kobjdir, o, objdir_len);
149 kobjdir[objdir_len++] = '/';
150 kobjdir[objdir_len] = 0;
151 }
152
153
154 void
kludge_look_harder_for_target(GNode * gn)155 kludge_look_harder_for_target(GNode *gn)
156 {
157 GNode *extra, *cgn;
158 LstNode ln;
159
160 if (strncmp(gn->name, kobjdir, objdir_len) == 0) {
161 extra = Targ_FindNode(gn->name + objdir_len, TARG_NOCREATE);
162 if (extra != NULL) {
163 if (Lst_IsEmpty(&gn->commands))
164 Lst_Concat(&gn->commands, &extra->commands);
165 for (ln = Lst_First(&extra->children); ln != NULL;
166 ln = Lst_Adv(ln)) {
167 cgn = Lst_Datum(ln);
168
169 if (Lst_AddNew(&gn->children, cgn)) {
170 Lst_AtEnd(&cgn->parents, gn);
171 gn->children_left++;
172 }
173 }
174 }
175 }
176 }
177
178 static void
attach_node(GNode * gn,GNode * extra)179 attach_node(GNode *gn, GNode *extra)
180 {
181 /* XXX normally extra->sibling == extra, but this is not
182 * always the case yet, so we merge the two lists
183 */
184 GNode *tmp;
185
186 tmp = gn->sibling;
187 gn->sibling = extra->sibling;
188 extra->sibling = tmp;
189 }
190
191 static char *buffer = NULL;
192 static size_t bufsize = PATH_MAX;
193
194 static size_t
parse_reduce(size_t i,const char * src)195 parse_reduce(size_t i, const char *src)
196 {
197 while (src[0] != 0) {
198 while (src[0] == '/')
199 src++;
200 /* special cases */
201 if (src[0] == '.') {
202 if (src[1] == '/') {
203 src += 2;
204 continue;
205 }
206 if (src[1] == '.' && src[2] == '/') {
207 src += 3;
208 i--;
209 while (i > 0 && buffer[i-1] != '/')
210 i--;
211 if (i == 0)
212 i = 1;
213 continue;
214 }
215 }
216 while (src[0] != '/' && src[0] != 0) {
217 if (i > bufsize - 2) {
218 bufsize *= 2;
219 buffer = erealloc(buffer, bufsize);
220 }
221 buffer[i++] = *src++;
222 }
223 if (src[0] == '/')
224 buffer[i++] = *src++;
225 }
226 buffer[i++] = 0;
227 return i;
228 }
229
230 static char *
absolute_reduce(const char * src)231 absolute_reduce(const char *src)
232 {
233 size_t i = 0;
234
235 if (buffer == NULL)
236 buffer = emalloc(bufsize);
237
238 buffer[i++] = '/';
239 i = parse_reduce(i, src);
240 return estrdup(buffer);
241 }
242
243 static char *
relative_reduce(const char * dir,const char * src)244 relative_reduce(const char *dir, const char *src)
245 {
246 size_t i = 0;
247
248 if (buffer == NULL)
249 buffer = emalloc(bufsize);
250
251 buffer[i++] = '/';
252 i = parse_reduce(i, dir);
253 i--;
254
255 if (buffer[i-1] != '/')
256 buffer[i++] = '/';
257 i = parse_reduce(i, src);
258 return estrdup(buffer);
259 }
260
261 static char *
relative_reduce2(const char * dir1,const char * dir2,const char * src)262 relative_reduce2(const char *dir1, const char *dir2, const char *src)
263 {
264 size_t i = 0;
265
266 if (buffer == NULL)
267 buffer = emalloc(bufsize);
268
269 buffer[i++] = '/';
270 i = parse_reduce(i, dir1);
271 i--;
272 if (buffer[i-1] != '/')
273 buffer[i++] = '/';
274
275 i = parse_reduce(i, dir2);
276 i--;
277 if (buffer[i-1] != '/')
278 buffer[i++] = '/';
279
280 i = parse_reduce(i, src);
281 return estrdup(buffer);
282 }
283
284 static char *
names_match_with_dir(const char * a,const char * b,char * ra,char * rb,const char * dir)285 names_match_with_dir(const char *a, const char *b, char *ra,
286 char *rb, const char *dir)
287 {
288 bool r;
289 bool free_a, free_b;
290
291 if (ra == NULL) {
292 ra = relative_reduce(dir, a);
293 free_a = true;
294 } else {
295 free_a = false;
296 }
297
298 if (rb == NULL) {
299 rb = relative_reduce(dir, b);
300 free_b = true;
301 } else {
302 free_b = false;
303 }
304 r = strcmp(ra, rb) == 0;
305 if (free_a)
306 free(ra);
307 if (r)
308 return rb;
309 else {
310 if (free_b)
311 free(rb);
312 return NULL;
313 }
314 }
315
316 static char *
names_match_with_dirs(const char * a,const char * b,char * ra,char * rb,const char * dir1,const char * dir2)317 names_match_with_dirs(const char *a, const char *b, char *ra,
318 char *rb, const char *dir1, const char *dir2)
319 {
320 bool r;
321 bool free_a, free_b;
322
323 if (ra == NULL) {
324 ra = relative_reduce2(dir1, dir2, a);
325 free_a = true;
326 } else {
327 free_a = false;
328 }
329
330 if (rb == NULL) {
331 rb = relative_reduce2(dir1, dir2, b);
332 free_b = true;
333 } else {
334 free_b = false;
335 }
336 r = strcmp(ra, rb) == 0;
337 if (free_a)
338 free(ra);
339 if (r)
340 return rb;
341 else {
342 if (free_b)
343 free(rb);
344 return NULL;
345 }
346 }
347
348 static char *
names_match(GNode * a,GNode * b)349 names_match(GNode *a, GNode *b)
350 {
351 char *ra = NULL , *rb = NULL;
352 char *r;
353
354 if (a->name[0] == '/')
355 ra = absolute_reduce(a->name);
356 if (b->name[0] == '/')
357 rb = absolute_reduce(b->name);
358 if (ra && rb) {
359 if (strcmp(ra, rb) == 0)
360 r = rb;
361 else
362 r = NULL;
363 } else {
364 r = names_match_with_dir(a->name, b->name, ra, rb, objdir);
365 if (!r)
366 r = names_match_with_dir(a->name, b->name, ra, rb,
367 curdir);
368 if (!r) {
369 /* b has necessarily the same one */
370 Lst l = find_suffix_path(a);
371 LstNode ln;
372
373 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
374 const char *p = PathEntry_name(Lst_Datum(ln));
375 if (p[0] == '/') {
376 r = names_match_with_dir(a->name,
377 b->name, ra, rb, p);
378 if (r)
379 break;
380 } else {
381 r = names_match_with_dirs(a->name,
382 b->name, ra, rb, p, objdir);
383 if (r)
384 break;
385 r = names_match_with_dirs(a->name,
386 b->name, ra, rb, p, curdir);
387 if (r)
388 break;
389 }
390 }
391 }
392 }
393 free(ra);
394 if (r != rb)
395 free(rb);
396 return r;
397 }
398
399 static void
find_siblings(GNode * gn)400 find_siblings(GNode *gn)
401 {
402 GNode *gn2;
403 char *fullpath;
404
405 /* not part of an equivalence class: can't alias */
406 if (gn->next == NULL)
407 return;
408 /* already resolved, actually */
409 if (gn->sibling != gn)
410 return;
411 if (DEBUG(NAME_MATCHING))
412 fprintf(stderr, "Matching for %s:", gn->name);
413 /* look through the aliases */
414 for (gn2 = gn->next; gn2 != gn; gn2 = gn2->next) {
415 fullpath = names_match(gn, gn2);
416 if (fullpath) {
417 attach_node(gn, gn2);
418 } else {
419 if (DEBUG(NAME_MATCHING))
420 fputc('!', stderr);
421 }
422 if (DEBUG(NAME_MATCHING))
423 fprintf(stderr, "%s ", gn2->name);
424 }
425 if (DEBUG(NAME_MATCHING))
426 fputc('\n', stderr);
427 }
428
429 void
look_harder_for_target(GNode * gn)430 look_harder_for_target(GNode *gn)
431 {
432 static bool equiv_was_built = false;
433
434 if (!equiv_was_built) {
435 build_equivalence();
436 equiv_was_built = true;
437 }
438
439 if (gn->type & (OP_RESOLVED | OP_PHONY))
440 return;
441 gn->type |= OP_RESOLVED;
442 find_siblings(gn);
443 }
444
445 bool
is_sibling(GNode * gn,GNode * gn2)446 is_sibling(GNode *gn, GNode *gn2)
447 {
448 GNode *sibling;
449
450 sibling = gn;
451 do {
452 if (sibling == gn2)
453 return true;
454 sibling = sibling->sibling;
455 } while (sibling != gn);
456
457 return false;
458 }
459