1 /* $OpenBSD: targequiv.c,v 1.1 2008/11/04 07:22:36 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 <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 = { 56 offsetof(struct equiv_list, name), NULL, hash_alloc, 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 #ifdef CLEANUP 133 free(e); 134 #endif 135 } 136 #ifdef CLEANUP 137 ohash_delete(&equiv); 138 #endif 139 } 140 141 static const char *curdir, *objdir; 142 static char *kobjdir; 143 static size_t objdir_len; 144 145 void 146 Targ_setdirs(const char *c, const char *o) 147 { 148 curdir = c; 149 objdir = o; 150 151 objdir_len = strlen(o); 152 kobjdir = emalloc(objdir_len+2); 153 memcpy(kobjdir, o, objdir_len); 154 kobjdir[objdir_len++] = '/'; 155 kobjdir[objdir_len] = 0; 156 } 157 158 159 void 160 kludge_look_harder_for_target(GNode *gn) 161 { 162 GNode *extra, *cgn; 163 LstNode ln; 164 165 if (strncmp(gn->name, kobjdir, objdir_len) == 0) { 166 extra = Targ_FindNode(gn->name + objdir_len, TARG_NOCREATE); 167 if (extra != NULL) { 168 if (Lst_IsEmpty(&gn->commands)) 169 Lst_Concat(&gn->commands, &extra->commands); 170 for (ln = Lst_First(&extra->children); ln != NULL; 171 ln = Lst_Adv(ln)) { 172 cgn = (GNode *)Lst_Datum(ln); 173 174 if (Lst_AddNew(&gn->children, cgn)) { 175 Lst_AtEnd(&cgn->parents, gn); 176 gn->unmade++; 177 } 178 } 179 } 180 } 181 } 182 183 static void 184 attach_node(GNode *gn, GNode *extra) 185 { 186 /* XXX normally extra->sibling == extra, but this is not 187 * always the case yet, so we merge the two lists 188 */ 189 GNode *tmp; 190 191 tmp = gn->sibling; 192 gn->sibling = extra->sibling; 193 extra->sibling = tmp; 194 } 195 196 static char *buffer = NULL; 197 static size_t bufsize = MAXPATHLEN; 198 199 static size_t 200 parse_reduce(size_t i, const char *src) 201 { 202 while (src[0] != 0) { 203 while (src[0] == '/') 204 src++; 205 /* special cases */ 206 if (src[0] == '.') { 207 if (src[1] == '/') { 208 src += 2; 209 continue; 210 } 211 if (src[1] == '.' && src[2] == '/') { 212 src += 3; 213 i--; 214 while (i > 0 && buffer[i-1] != '/') 215 i--; 216 if (i == 0) 217 i = 1; 218 continue; 219 } 220 } 221 while (src[0] != '/' && src[0] != 0) { 222 if (i > bufsize - 2) { 223 bufsize *= 2; 224 buffer = erealloc(buffer, bufsize); 225 } 226 buffer[i++] = *src++; 227 } 228 buffer[i++] = *src; 229 } 230 return i; 231 } 232 233 static char * 234 absolute_reduce(const char *src) 235 { 236 size_t i = 0; 237 238 if (buffer == NULL) 239 buffer = emalloc(bufsize); 240 241 buffer[i++] = '/'; 242 i = parse_reduce(i, src); 243 return estrdup(buffer); 244 } 245 246 static char * 247 relative_reduce(const char *dir, const char *src) 248 { 249 size_t i = 0; 250 251 if (buffer == NULL) 252 buffer = emalloc(bufsize); 253 254 buffer[i++] = '/'; 255 i = parse_reduce(i, dir); 256 i--; 257 258 if (buffer[i-1] != '/') 259 buffer[i++] = '/'; 260 i = parse_reduce(i, src); 261 return estrdup(buffer); 262 } 263 264 static char * 265 relative_reduce2(const char *dir1, const char *dir2, const char *src) 266 { 267 size_t i = 0; 268 269 if (buffer == NULL) 270 buffer = emalloc(bufsize); 271 272 buffer[i++] = '/'; 273 i = parse_reduce(i, dir1); 274 i--; 275 if (buffer[i-1] != '/') 276 buffer[i++] = '/'; 277 278 i = parse_reduce(i, dir2); 279 i--; 280 if (buffer[i-1] != '/') 281 buffer[i++] = '/'; 282 283 i = parse_reduce(i, src); 284 return estrdup(buffer); 285 } 286 287 static char * 288 names_match_with_dir(const char *a, const char *b, char *ra, 289 char *rb, const char *dir) 290 { 291 bool r; 292 bool free_a, free_b; 293 294 if (ra == NULL) { 295 ra = relative_reduce(dir, a); 296 free_a = true; 297 } else { 298 free_a = false; 299 } 300 301 if (rb == NULL) { 302 rb = relative_reduce(dir, b); 303 free_b = true; 304 } else { 305 free_b = false; 306 } 307 r = strcmp(ra, rb) == 0; 308 if (free_a) 309 free(ra); 310 if (r) 311 return rb; 312 else { 313 if (free_b) 314 free(rb); 315 return NULL; 316 } 317 } 318 319 static char * 320 names_match_with_dirs(const char *a, const char *b, char *ra, 321 char *rb, const char *dir1, const char *dir2) 322 { 323 bool r; 324 bool free_a, free_b; 325 326 if (ra == NULL) { 327 ra = relative_reduce2(dir1, dir2, a); 328 free_a = true; 329 } else { 330 free_a = false; 331 } 332 333 if (rb == NULL) { 334 rb = relative_reduce2(dir1, dir2, b); 335 free_b = true; 336 } else { 337 free_b = false; 338 } 339 r = strcmp(ra, rb) == 0; 340 if (free_a) 341 free(ra); 342 if (r) 343 return rb; 344 else { 345 if (free_b) 346 free(rb); 347 return NULL; 348 } 349 } 350 351 static char * 352 names_match(GNode *a, GNode *b) 353 { 354 char *ra = NULL , *rb = NULL; 355 char *r; 356 357 if (a->name[0] == '/') 358 ra = absolute_reduce(a->name); 359 if (b->name[0] == '/') 360 rb = absolute_reduce(b->name); 361 if (ra && rb) { 362 if (strcmp(ra, rb) == 0) 363 r = rb; 364 else 365 r = NULL; 366 } else { 367 r = names_match_with_dir(a->name, b->name, ra, rb, objdir); 368 if (!r) 369 r = names_match_with_dir(a->name, b->name, ra, rb, 370 curdir); 371 if (!r) { 372 /* b has necessarily the same one */ 373 Lst l = find_suffix_path(a); 374 LstNode ln; 375 376 for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { 377 const char *p = PathEntry_name(Lst_Datum(ln)); 378 if (p[0] == '/') { 379 r = names_match_with_dir(a->name, 380 b->name, ra, rb, p); 381 if (r) 382 break; 383 } else { 384 r = names_match_with_dirs(a->name, 385 b->name, ra, rb, p, objdir); 386 if (r) 387 break; 388 r = names_match_with_dirs(a->name, 389 b->name, ra, rb, p, curdir); 390 if (r) 391 break; 392 } 393 } 394 } 395 } 396 free(ra); 397 if (r != rb) 398 free(rb); 399 return r; 400 } 401 402 static void 403 find_siblings(GNode *gn) 404 { 405 GNode *gn2; 406 char *fullpath; 407 408 /* not part of an equivalence class: can't alias */ 409 if (gn->next == NULL) 410 return; 411 /* already resolved, actually */ 412 if (gn->sibling != gn) 413 return; 414 if (DEBUG(NAME_MATCHING)) 415 fprintf(stderr, "Matching for %s:", gn->name); 416 /* look through the aliases */ 417 for (gn2 = gn->next; gn2 != gn; gn2 = gn2->next) { 418 fullpath = names_match(gn, gn2); 419 if (fullpath) { 420 attach_node(gn, gn2); 421 } else { 422 if (DEBUG(NAME_MATCHING)) 423 fputc('!', stderr); 424 } 425 if (DEBUG(NAME_MATCHING)) 426 fprintf(stderr, "%s ", gn2->name); 427 } 428 if (DEBUG(NAME_MATCHING)) 429 fputc('\n', stderr); 430 } 431 432 void 433 look_harder_for_target(GNode *gn) 434 { 435 static bool equiv_was_built = false; 436 437 if (!equiv_was_built) { 438 build_equivalence(); 439 equiv_was_built = true; 440 } 441 442 if (gn->type & (OP_RESOLVED | OP_PHONY)) 443 return; 444 gn->type |= OP_RESOLVED; 445 find_siblings(gn); 446 } 447 448 bool 449 is_sibling(GNode *gn, GNode *gn2) 450 { 451 GNode *sibling; 452 453 sibling = gn; 454 do { 455 if (sibling == gn2) 456 return true; 457 sibling = sibling->sibling; 458 } while (sibling != gn); 459 460 return false; 461 } 462