![[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.8 ! espie 1: /* $OpenBSD: targequiv.c,v 1.7 2015/01/16 15:36:30 deraadt 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 "config.h"
41: #include "defines.h"
42: #include "memory.h"
43: #include "gnode.h"
44: #include "lst.h"
45: #include "suff.h"
46: #include "dir.h"
47: #include "targ.h"
48: #include "targequiv.h"
49:
50: struct equiv_list {
51: GNode *first, *last;
52: char name[1];
53: };
54:
55: static struct ohash_info equiv_info = {
1.5 espie 56: offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free,
1.1 espie 57: element_alloc
58: };
59:
60: static void attach_node(GNode *, GNode *);
61: static void build_equivalence(void);
62: static void add_to_equiv_list(struct ohash *, GNode *);
63: static char *names_match(GNode *, GNode *);
1.2 espie 64: static char *names_match_with_dir(const char *, const char *, char *,
1.1 espie 65: char *, const char *);
1.2 espie 66: static char *names_match_with_dirs(const char *, const char *, char *,
1.1 espie 67: char *, const char *, const char *);
68: static char *relative_reduce(const char *, const char *);
69: static char *relative_reduce2(const char *, const char *, const char *);
70: static char *absolute_reduce(const char *);
71: static size_t parse_reduce(size_t, const char *);
72: static void find_siblings(GNode *);
73:
74: /* These functions build `equivalence lists' of targets with the same
75: * basename, as circular lists. They use an intermediate ohash as scaffold,
76: * to insert same-basename targets in a simply linked list. Then they make
77: * those lists circular, to the exception of lone elements, since they can't
78: * alias to anything.
1.2 espie 79: *
1.1 espie 80: * This structure is used to simplify alias-lookup to a great extent: two
81: * nodes can only alias each other if they're part of the same equivalence
82: * set. Most nodes either don't belong to an alias set, or to a very simple
83: * alias set, thus removing most possibilities.
84: */
85: static void
86: add_to_equiv_list(struct ohash *equiv, GNode *gn)
87: {
88: const char *end = NULL;
89: struct equiv_list *e;
90: unsigned int slot;
91:
92: if (!should_have_file(gn))
93: return;
94:
95: gn->basename = strrchr(gn->name, '/');
96: if (gn->basename == NULL)
97: gn->basename = gn->name;
98: else
99: gn->basename++;
100: slot = ohash_qlookupi(equiv, gn->basename, &end);
101: e = ohash_find(equiv, slot);
102: if (e == NULL) {
103: e = ohash_create_entry(&equiv_info, gn->basename, &end);
104: e->first = NULL;
105: e->last = gn;
106: ohash_insert(equiv, slot, e);
107: }
108: gn->next = e->first;
109: e->first = gn;
110: }
111:
112: static void
113: build_equivalence()
114: {
115: unsigned int i;
116: GNode *gn;
117: struct equiv_list *e;
118: struct ohash equiv;
119: struct ohash *t = targets_hash();
120:
121:
122: ohash_init(&equiv, 10, &equiv_info);
123:
124: for (gn = ohash_first(t, &i); gn != NULL; gn = ohash_next(t, &i))
125: add_to_equiv_list(&equiv, gn);
126:
127: /* finish making the lists circular */
128: for (e = ohash_first(&equiv, &i); e != NULL;
129: e = ohash_next(&equiv, &i)) {
130: if (e->last != e->first)
131: e->last->next = e->first;
132: free(e);
133: }
134: ohash_delete(&equiv);
135: }
136:
137: static const char *curdir, *objdir;
138: static char *kobjdir;
139: static size_t objdir_len;
140:
141: void
142: Targ_setdirs(const char *c, const char *o)
143: {
144: curdir = c;
145: objdir = o;
146:
147: objdir_len = strlen(o);
148: kobjdir = emalloc(objdir_len+2);
149: memcpy(kobjdir, o, objdir_len);
150: kobjdir[objdir_len++] = '/';
151: kobjdir[objdir_len] = 0;
152: }
153:
154:
155: void
156: kludge_look_harder_for_target(GNode *gn)
157: {
158: GNode *extra, *cgn;
159: LstNode ln;
160:
161: if (strncmp(gn->name, kobjdir, objdir_len) == 0) {
162: extra = Targ_FindNode(gn->name + objdir_len, TARG_NOCREATE);
163: if (extra != NULL) {
164: if (Lst_IsEmpty(&gn->commands))
165: Lst_Concat(&gn->commands, &extra->commands);
166: for (ln = Lst_First(&extra->children); ln != NULL;
167: ln = Lst_Adv(ln)) {
1.8 ! espie 168: cgn = Lst_Datum(ln);
1.1 espie 169:
170: if (Lst_AddNew(&gn->children, cgn)) {
171: Lst_AtEnd(&cgn->parents, gn);
172: gn->unmade++;
173: }
174: }
175: }
176: }
177: }
178:
179: static void
180: attach_node(GNode *gn, GNode *extra)
181: {
182: /* XXX normally extra->sibling == extra, but this is not
1.2 espie 183: * always the case yet, so we merge the two lists
1.1 espie 184: */
185: GNode *tmp;
186:
187: tmp = gn->sibling;
188: gn->sibling = extra->sibling;
189: extra->sibling = tmp;
190: }
191:
192: static char *buffer = NULL;
1.7 deraadt 193: static size_t bufsize = PATH_MAX;
1.1 espie 194:
195: static size_t
196: parse_reduce(size_t i, const char *src)
197: {
198: while (src[0] != 0) {
199: while (src[0] == '/')
200: src++;
201: /* special cases */
202: if (src[0] == '.') {
203: if (src[1] == '/') {
204: src += 2;
205: continue;
206: }
207: if (src[1] == '.' && src[2] == '/') {
208: src += 3;
209: i--;
210: while (i > 0 && buffer[i-1] != '/')
211: i--;
212: if (i == 0)
213: i = 1;
214: continue;
215: }
216: }
217: while (src[0] != '/' && src[0] != 0) {
218: if (i > bufsize - 2) {
219: bufsize *= 2;
220: buffer = erealloc(buffer, bufsize);
221: }
222: buffer[i++] = *src++;
223: }
1.6 espie 224: if (src[0] == '/')
225: buffer[i++] = *src++;
1.1 espie 226: }
1.6 espie 227: buffer[i++] = 0;
1.1 espie 228: return i;
229: }
230:
231: static char *
232: absolute_reduce(const char *src)
233: {
234: size_t i = 0;
235:
236: if (buffer == NULL)
237: buffer = emalloc(bufsize);
238:
239: buffer[i++] = '/';
240: i = parse_reduce(i, src);
1.2 espie 241: return estrdup(buffer);
1.1 espie 242: }
243:
244: static char *
245: relative_reduce(const char *dir, const char *src)
246: {
247: size_t i = 0;
1.2 espie 248:
1.1 espie 249: if (buffer == NULL)
250: buffer = emalloc(bufsize);
251:
252: buffer[i++] = '/';
253: i = parse_reduce(i, dir);
254: i--;
255:
256: if (buffer[i-1] != '/')
257: buffer[i++] = '/';
258: i = parse_reduce(i, src);
1.2 espie 259: return estrdup(buffer);
1.1 espie 260: }
261:
262: static char *
263: relative_reduce2(const char *dir1, const char *dir2, const char *src)
264: {
265: size_t i = 0;
1.2 espie 266:
1.1 espie 267: if (buffer == NULL)
268: buffer = emalloc(bufsize);
269:
270: buffer[i++] = '/';
271: i = parse_reduce(i, dir1);
272: i--;
273: if (buffer[i-1] != '/')
274: buffer[i++] = '/';
275:
276: i = parse_reduce(i, dir2);
277: i--;
278: if (buffer[i-1] != '/')
279: buffer[i++] = '/';
280:
281: i = parse_reduce(i, src);
1.2 espie 282: return estrdup(buffer);
1.1 espie 283: }
284:
285: static char *
1.2 espie 286: names_match_with_dir(const char *a, const char *b, char *ra,
1.1 espie 287: char *rb, const char *dir)
288: {
289: bool r;
290: bool free_a, free_b;
1.2 espie 291:
1.1 espie 292: if (ra == NULL) {
293: ra = relative_reduce(dir, a);
294: free_a = true;
295: } else {
296: free_a = false;
297: }
298:
299: if (rb == NULL) {
300: rb = relative_reduce(dir, b);
301: free_b = true;
302: } else {
303: free_b = false;
304: }
305: r = strcmp(ra, rb) == 0;
306: if (free_a)
307: free(ra);
308: if (r)
309: return rb;
310: else {
311: if (free_b)
312: free(rb);
313: return NULL;
314: }
315: }
316:
317: static char *
1.2 espie 318: names_match_with_dirs(const char *a, const char *b, char *ra,
1.1 espie 319: char *rb, const char *dir1, const char *dir2)
320: {
321: bool r;
322: bool free_a, free_b;
1.2 espie 323:
1.1 espie 324: if (ra == NULL) {
325: ra = relative_reduce2(dir1, dir2, a);
326: free_a = true;
327: } else {
328: free_a = false;
329: }
330:
331: if (rb == NULL) {
332: rb = relative_reduce2(dir1, dir2, b);
333: free_b = true;
334: } else {
335: free_b = false;
336: }
337: r = strcmp(ra, rb) == 0;
338: if (free_a)
339: free(ra);
340: if (r)
341: return rb;
342: else {
343: if (free_b)
344: free(rb);
345: return NULL;
346: }
347: }
348:
349: static char *
350: names_match(GNode *a, GNode *b)
351: {
352: char *ra = NULL , *rb = NULL;
353: char *r;
354:
355: if (a->name[0] == '/')
356: ra = absolute_reduce(a->name);
357: if (b->name[0] == '/')
358: rb = absolute_reduce(b->name);
359: if (ra && rb) {
360: if (strcmp(ra, rb) == 0)
361: r = rb;
362: else
363: r = NULL;
364: } else {
365: r = names_match_with_dir(a->name, b->name, ra, rb, objdir);
366: if (!r)
1.2 espie 367: r = names_match_with_dir(a->name, b->name, ra, rb,
1.1 espie 368: curdir);
369: if (!r) {
370: /* b has necessarily the same one */
371: Lst l = find_suffix_path(a);
372: LstNode ln;
373:
374: for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
375: const char *p = PathEntry_name(Lst_Datum(ln));
376: if (p[0] == '/') {
1.2 espie 377: r = names_match_with_dir(a->name,
1.1 espie 378: b->name, ra, rb, p);
379: if (r)
380: break;
381: } else {
382: r = names_match_with_dirs(a->name,
383: b->name, ra, rb, p, objdir);
384: if (r)
385: break;
386: r = names_match_with_dirs(a->name,
387: b->name, ra, rb, p, curdir);
388: if (r)
389: break;
390: }
391: }
392: }
393: }
394: free(ra);
395: if (r != rb)
396: free(rb);
397: return r;
398: }
399:
400: static void
401: find_siblings(GNode *gn)
402: {
403: GNode *gn2;
404: char *fullpath;
405:
406: /* not part of an equivalence class: can't alias */
407: if (gn->next == NULL)
408: return;
409: /* already resolved, actually */
410: if (gn->sibling != gn)
411: return;
412: if (DEBUG(NAME_MATCHING))
413: fprintf(stderr, "Matching for %s:", gn->name);
414: /* look through the aliases */
415: for (gn2 = gn->next; gn2 != gn; gn2 = gn2->next) {
416: fullpath = names_match(gn, gn2);
417: if (fullpath) {
418: attach_node(gn, gn2);
419: } else {
420: if (DEBUG(NAME_MATCHING))
421: fputc('!', stderr);
422: }
423: if (DEBUG(NAME_MATCHING))
424: fprintf(stderr, "%s ", gn2->name);
425: }
426: if (DEBUG(NAME_MATCHING))
427: fputc('\n', stderr);
428: }
429:
430: void
431: look_harder_for_target(GNode *gn)
432: {
433: static bool equiv_was_built = false;
434:
435: if (!equiv_was_built) {
436: build_equivalence();
437: equiv_was_built = true;
438: }
439:
440: if (gn->type & (OP_RESOLVED | OP_PHONY))
441: return;
442: gn->type |= OP_RESOLVED;
443: find_siblings(gn);
444: }
445:
446: bool
447: is_sibling(GNode *gn, GNode *gn2)
448: {
449: GNode *sibling;
1.2 espie 450:
1.1 espie 451: sibling = gn;
452: do {
453: if (sibling == gn2)
454: return true;
455: sibling = sibling->sibling;
456: } while (sibling != gn);
457:
458: return false;
459: }