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