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
49struct equiv_list {
50	GNode *first, *last;
51	char name[1];
52};
53
54static struct ohash_info equiv_info = {
55	offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free,
56	element_alloc
57};
58
59static void attach_node(GNode *, GNode *);
60static void build_equivalence(void);
61static void add_to_equiv_list(struct ohash *, GNode *);
62static char *names_match(GNode *, GNode *);
63static char *names_match_with_dir(const char *, const char *, char *,
64    char *,  const char *);
65static char *names_match_with_dirs(const char *, const char *, char *,
66    char *,  const char *, const char *);
67static char *relative_reduce(const char *, const char *);
68static char *relative_reduce2(const char *, const char *, const char *);
69static char *absolute_reduce(const char *);
70static size_t parse_reduce(size_t, const char *);
71static 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 */
84static void
85add_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
111static void
112build_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
136static const char *curdir, *objdir;
137static char *kobjdir;
138static size_t objdir_len;
139
140void
141Targ_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
154void
155kludge_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
178static void
179attach_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
191static char *buffer = NULL;
192static size_t bufsize = PATH_MAX;
193
194static size_t
195parse_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
230static char *
231absolute_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
243static char *
244relative_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
261static char *
262relative_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
284static char *
285names_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
316static char *
317names_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
348static char *
349names_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
399static void
400find_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
429void
430look_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
445bool
446is_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