1 /* $OpenBSD: targequiv.c,v 1.5 2014/05/12 19:11:19 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 <sys/param.h> 34 #include <stddef.h> 35 #include <stdint.h> 36 #include <stdio.h> 37 #include <stdlib.h> 38 #include <string.h> 39 #include <ohash.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 = (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 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 = 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); 239 return estrdup(buffer); 240 } 241 242 static char * 243 relative_reduce(const char *dir, const char *src) 244 { 245 size_t i = 0; 246 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); 257 return estrdup(buffer); 258 } 259 260 static char * 261 relative_reduce2(const char *dir1, const char *dir2, const char *src) 262 { 263 size_t i = 0; 264 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); 280 return estrdup(buffer); 281 } 282 283 static char * 284 names_match_with_dir(const char *a, const char *b, char *ra, 285 char *rb, const char *dir) 286 { 287 bool r; 288 bool free_a, free_b; 289 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 * 316 names_match_with_dirs(const char *a, const char *b, char *ra, 317 char *rb, const char *dir1, const char *dir2) 318 { 319 bool r; 320 bool free_a, free_b; 321 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) 365 r = names_match_with_dir(a->name, b->name, ra, rb, 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] == '/') { 375 r = names_match_with_dir(a->name, 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; 448 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 } 458