Annotation of src/usr.bin/make/targequiv.c, Revision 1.3
1.3 ! espie 1: /* $OpenBSD: targequiv.c,v 1.2 2010/04/25 13:59:53 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:
33: #include <stdlib.h>
34: #include <stdint.h>
35: #include <stddef.h>
36: #include <stdio.h>
37: #include <sys/param.h>
38: #include <string.h>
39: #include "config.h"
40: #include "defines.h"
41: #include "memory.h"
42: #include "ohash.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.2 espie 56: offsetof(struct equiv_list, name), NULL, hash_alloc, 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)) {
168: cgn = (GNode *)Lst_Datum(ln);
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;
193: static size_t bufsize = MAXPATHLEN;
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: }
224: buffer[i++] = *src;
225: }
226: return i;
227: }
228:
229: static char *
230: absolute_reduce(const char *src)
231: {
232: size_t i = 0;
233:
234: if (buffer == NULL)
235: buffer = emalloc(bufsize);
236:
237: buffer[i++] = '/';
238: i = parse_reduce(i, src);
1.2 espie 239: return estrdup(buffer);
1.1 espie 240: }
241:
242: static char *
243: relative_reduce(const char *dir, const char *src)
244: {
245: size_t i = 0;
1.2 espie 246:
1.1 espie 247: if (buffer == NULL)
248: buffer = emalloc(bufsize);
249:
250: buffer[i++] = '/';
251: i = parse_reduce(i, dir);
252: i--;
253:
254: if (buffer[i-1] != '/')
255: buffer[i++] = '/';
256: i = parse_reduce(i, src);
1.2 espie 257: return estrdup(buffer);
1.1 espie 258: }
259:
260: static char *
261: relative_reduce2(const char *dir1, const char *dir2, const char *src)
262: {
263: size_t i = 0;
1.2 espie 264:
1.1 espie 265: if (buffer == NULL)
266: buffer = emalloc(bufsize);
267:
268: buffer[i++] = '/';
269: i = parse_reduce(i, dir1);
270: i--;
271: if (buffer[i-1] != '/')
272: buffer[i++] = '/';
273:
274: i = parse_reduce(i, dir2);
275: i--;
276: if (buffer[i-1] != '/')
277: buffer[i++] = '/';
278:
279: i = parse_reduce(i, src);
1.2 espie 280: return estrdup(buffer);
1.1 espie 281: }
282:
283: static char *
1.2 espie 284: names_match_with_dir(const char *a, const char *b, char *ra,
1.1 espie 285: char *rb, const char *dir)
286: {
287: bool r;
288: bool free_a, free_b;
1.2 espie 289:
1.1 espie 290: if (ra == NULL) {
291: ra = relative_reduce(dir, a);
292: free_a = true;
293: } else {
294: free_a = false;
295: }
296:
297: if (rb == NULL) {
298: rb = relative_reduce(dir, b);
299: free_b = true;
300: } else {
301: free_b = false;
302: }
303: r = strcmp(ra, rb) == 0;
304: if (free_a)
305: free(ra);
306: if (r)
307: return rb;
308: else {
309: if (free_b)
310: free(rb);
311: return NULL;
312: }
313: }
314:
315: static char *
1.2 espie 316: names_match_with_dirs(const char *a, const char *b, char *ra,
1.1 espie 317: char *rb, const char *dir1, const char *dir2)
318: {
319: bool r;
320: bool free_a, free_b;
1.2 espie 321:
1.1 espie 322: if (ra == NULL) {
323: ra = relative_reduce2(dir1, dir2, a);
324: free_a = true;
325: } else {
326: free_a = false;
327: }
328:
329: if (rb == NULL) {
330: rb = relative_reduce2(dir1, dir2, b);
331: free_b = true;
332: } else {
333: free_b = false;
334: }
335: r = strcmp(ra, rb) == 0;
336: if (free_a)
337: free(ra);
338: if (r)
339: return rb;
340: else {
341: if (free_b)
342: free(rb);
343: return NULL;
344: }
345: }
346:
347: static char *
348: names_match(GNode *a, GNode *b)
349: {
350: char *ra = NULL , *rb = NULL;
351: char *r;
352:
353: if (a->name[0] == '/')
354: ra = absolute_reduce(a->name);
355: if (b->name[0] == '/')
356: rb = absolute_reduce(b->name);
357: if (ra && rb) {
358: if (strcmp(ra, rb) == 0)
359: r = rb;
360: else
361: r = NULL;
362: } else {
363: r = names_match_with_dir(a->name, b->name, ra, rb, objdir);
364: if (!r)
1.2 espie 365: r = names_match_with_dir(a->name, b->name, ra, rb,
1.1 espie 366: curdir);
367: if (!r) {
368: /* b has necessarily the same one */
369: Lst l = find_suffix_path(a);
370: LstNode ln;
371:
372: for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
373: const char *p = PathEntry_name(Lst_Datum(ln));
374: if (p[0] == '/') {
1.2 espie 375: r = names_match_with_dir(a->name,
1.1 espie 376: b->name, ra, rb, p);
377: if (r)
378: break;
379: } else {
380: r = names_match_with_dirs(a->name,
381: b->name, ra, rb, p, objdir);
382: if (r)
383: break;
384: r = names_match_with_dirs(a->name,
385: b->name, ra, rb, p, curdir);
386: if (r)
387: break;
388: }
389: }
390: }
391: }
392: free(ra);
393: if (r != rb)
394: free(rb);
395: return r;
396: }
397:
398: static void
399: find_siblings(GNode *gn)
400: {
401: GNode *gn2;
402: char *fullpath;
403:
404: /* not part of an equivalence class: can't alias */
405: if (gn->next == NULL)
406: return;
407: /* already resolved, actually */
408: if (gn->sibling != gn)
409: return;
410: if (DEBUG(NAME_MATCHING))
411: fprintf(stderr, "Matching for %s:", gn->name);
412: /* look through the aliases */
413: for (gn2 = gn->next; gn2 != gn; gn2 = gn2->next) {
414: fullpath = names_match(gn, gn2);
415: if (fullpath) {
416: attach_node(gn, gn2);
417: } else {
418: if (DEBUG(NAME_MATCHING))
419: fputc('!', stderr);
420: }
421: if (DEBUG(NAME_MATCHING))
422: fprintf(stderr, "%s ", gn2->name);
423: }
424: if (DEBUG(NAME_MATCHING))
425: fputc('\n', stderr);
426: }
427:
428: void
429: look_harder_for_target(GNode *gn)
430: {
431: static bool equiv_was_built = false;
432:
433: if (!equiv_was_built) {
434: build_equivalence();
435: equiv_was_built = true;
436: }
437:
438: if (gn->type & (OP_RESOLVED | OP_PHONY))
439: return;
440: gn->type |= OP_RESOLVED;
441: find_siblings(gn);
442: }
443:
444: bool
445: is_sibling(GNode *gn, GNode *gn2)
446: {
447: GNode *sibling;
1.2 espie 448:
1.1 espie 449: sibling = gn;
450: do {
451: if (sibling == gn2)
452: return true;
453: sibling = sibling->sibling;
454: } while (sibling != gn);
455:
456: return false;
457: }