![[BACK]](/icons/back.gif){kind=icon}
Return to targequiv.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / make|
Return to targequiv.c CVS log | Up to [local] / src / usr.bin / make |
1.10 ! espie 1: /* $OpenBSD: targequiv.c,v 1.9 2019/12/21 15:29:25 espie Exp $ */
1.1 espie 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:
1.4 espie 33: #include <stddef.h>
1.1 espie 34: #include <stdint.h>
35: #include <stdio.h>
1.4 espie 36: #include <stdlib.h>
1.1 espie 37: #include <string.h>
1.4 espie 38: #include <ohash.h>
1.7 deraadt 39: #include <limits.h>
1.1 espie 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 = {
1.5 espie 55: offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free,
1.1 espie 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 *);
1.2 espie 63: static char *names_match_with_dir(const char *, const char *, char *,
1.1 espie 64: char *, const char *);
1.2 espie 65: static char *names_match_with_dirs(const char *, const char *, char *,
1.1 espie 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.
1.2 espie 78: *
1.1 espie 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
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
112: build_equivalence()
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
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
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)) {
1.8 espie 167: cgn = Lst_Datum(ln);
1.1 espie 168:
169: if (Lst_AddNew(&gn->children, cgn)) {
170: Lst_AtEnd(&cgn->parents, gn);
1.9 espie 171: gn->children_left++;
1.1 espie 172: }
173: }
174: }
175: }
176: }
177:
178: static void
179: attach_node(GNode *gn, GNode *extra)
180: {
181: /* XXX normally extra->sibling == extra, but this is not
1.2 espie 182: * always the case yet, so we merge the two lists
1.1 espie 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;
1.7 deraadt 192: static size_t bufsize = PATH_MAX;
1.1 espie 193:
194: static size_t
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: }
1.6 espie 223: if (src[0] == '/')
224: buffer[i++] = *src++;
1.1 espie 225: }
1.6 espie 226: buffer[i++] = 0;
1.1 espie 227: return i;
228: }
229:
230: static char *
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);
1.2 espie 240: return estrdup(buffer);
1.1 espie 241: }
242:
243: static char *
244: relative_reduce(const char *dir, const char *src)
245: {
246: size_t i = 0;
1.2 espie 247:
1.1 espie 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);
1.2 espie 258: return estrdup(buffer);
1.1 espie 259: }
260:
261: static char *
262: relative_reduce2(const char *dir1, const char *dir2, const char *src)
263: {
264: size_t i = 0;
1.2 espie 265:
1.1 espie 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);
1.2 espie 281: return estrdup(buffer);
1.1 espie 282: }
283:
284: static char *
1.2 espie 285: names_match_with_dir(const char *a, const char *b, char *ra,
1.1 espie 286: char *rb, const char *dir)
287: {
288: bool r;
289: bool free_a, free_b;
1.2 espie 290:
1.1 espie 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 *
1.2 espie 317: names_match_with_dirs(const char *a, const char *b, char *ra,
1.1 espie 318: char *rb, const char *dir1, const char *dir2)
319: {
320: bool r;
321: bool free_a, free_b;
1.2 espie 322:
1.1 espie 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 *
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)
1.2 espie 366: r = names_match_with_dir(a->name, b->name, ra, rb,
1.1 espie 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] == '/') {
1.2 espie 376: r = names_match_with_dir(a->name,
1.1 espie 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
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
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
446: is_sibling(GNode *gn, GNode *gn2)
447: {
448: GNode *sibling;
1.2 espie 449:
1.1 espie 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: }