1 /* $OpenBSD: targequiv.c,v 1.9 2019/12/21 15:29:25 espie 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 "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 = { 56 offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free, 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 *); 64 static char *names_match_with_dir(const char *, const char *, char *, 65 char *, const char *); 66 static char *names_match_with_dirs(const char *, const char *, char *, 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. 79 * 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 = Lst_Datum(ln); 169 170 if (Lst_AddNew(&gn->children, cgn)) { 171 Lst_AtEnd(&cgn->parents, gn); 172 gn->children_left++; 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 183 * always the case yet, so we merge the two lists 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 = PATH_MAX; 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 if (src[0] == '/') 225 buffer[i++] = *src++; 226 } 227 buffer[i++] = 0; 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); 241 return estrdup(buffer); 242 } 243 244 static char * 245 relative_reduce(const char *dir, const char *src) 246 { 247 size_t i = 0; 248 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); 259 return estrdup(buffer); 260 } 261 262 static char * 263 relative_reduce2(const char *dir1, const char *dir2, const char *src) 264 { 265 size_t i = 0; 266 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); 282 return estrdup(buffer); 283 } 284 285 static char * 286 names_match_with_dir(const char *a, const char *b, char *ra, 287 char *rb, const char *dir) 288 { 289 bool r; 290 bool free_a, free_b; 291 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 * 318 names_match_with_dirs(const char *a, const char *b, char *ra, 319 char *rb, const char *dir1, const char *dir2) 320 { 321 bool r; 322 bool free_a, free_b; 323 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) 367 r = names_match_with_dir(a->name, b->name, ra, rb, 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] == '/') { 377 r = names_match_with_dir(a->name, 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; 450 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 } 460