solenv/bin/concat-deps.c

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  *    Copyright (C) 2011 Norbert Thiebaud
   4  *    License: GPLv3
   5  */
   6
   7 /* define to activate stats reporting on hash usage*/
   8 /* #define HASH_STAT */
   9
  10 /* ===============================================
  11  * Set-up: defines to identify the system and system related properties
  12  * ===============================================
  13  */
  14
  15 #ifdef __APPLE__
  16 #ifdef __x86_64__
  17 #undef CORE_BIG_ENDIAN
  18 #define CORE_LITTLE_ENDIAN
  19 #define USE_MEMORY_ALIGNMENT 64 /* big value -> no alignment */
  20 #else
  21 #define CORE_BIG_ENDIAN
  22 #undef CORE_LITTLE_ENDIAN
  23 #define USE_MEMORY_ALIGNMENT 4
  24 #endif
  25
  26 #endif
  27 #ifdef _AIX
  28 #define CORE_BIG_ENDIAN
  29 #undef CORE_LITTLE_ENDIAN
  30 #define USE_MEMORY_ALIGNMENT 4
  31 #endif /* Def _AIX */
  32
  33 #ifdef _MSC_VER
  34 #define __windows
  35 #undef CORE_BIG_ENDIAN
  36 #define CORE_LITTLE_ENDIAN
  37 #define USE_MEMORY_ALIGNMENT 64 /* big value -> no alignment */
  38 #endif /* Def _MSC_VER */
  39
  40 #if defined(__linux) || defined(__OpenBSD__) || \
  41     defined(__FreeBSD__) || defined(__NetBSD__) || \
  42     defined(__DragonFly__) || defined(__FreeBSD_kernel__)
  43 #include <sys/param.h>
  44 #if __BYTE_ORDER == __LITTLE_ENDIAN
  45 #undef CORE_BIG_ENDIAN
  46 #define CORE_LITTLE_ENDIAN
  47 #if defined(__x86_64) || defined(__i386)
  48 #define USE_MEMORY_ALIGNMENT 64
  49 #else
  50 #define USE_MEMORY_ALIGNMENT 4
  51 #endif
  52 #else /* !(__BYTE_ORDER == __LITTLE_ENDIAN) */
  53 #if __BYTE_ORDER == __BIG_ENDIAN
  54 #define CORE_BIG_ENDIAN
  55 #undef CORE_LITTLE_ENDIAN
  56 #define USE_MEMORY_ALIGNMENT 4
  57 #endif /* __BYTE_ORDER == __BIG_ENDIAN */
  58 #endif /* !(__BYTE_ORDER == __LITTLE_ENDIAN) */
  59 #endif /* Def __linux || Def *BSD */
  60
  61 #ifdef __sun
  62 #ifdef __sparc
  63 #define CORE_BIG_ENDIAN
  64 #undef CORE_LITTLE_ENDIAN
  65 #define USE_MEMORY_ALIGNMENT 4
  66 #else  /* Ndef __sparc */
  67 #undef CORE_BIG_ENDIAN
  68 #define CORE_LITTLE_ENDIAN
  69 #define USE_MEMORY_ALIGNMENT 4
  70 #endif /* Ndef __sparc */
  71 #endif /* Def __sun */
  72
  73 /* Note USE_MEMORY_ALIGNMENT is 4 for platform that allow short non-aligned but required int access to be aligned (e.g sparc, ppc, zos..)
  74  *      USE_MEMORY_ALIGNMENT is 2 for platform that require short and int access to be aligned (e.g hppa )
  75  * if the platform does not have alignment requirement (x86/amd64) use a big value (i.e > 16)
  76  */
  77 #ifndef USE_MEMORY_ALIGNMENT
  78 #error "USE_MEMORY_ALIGNMENT must be defined to the proper alignment value for the platform"
  79 #endif
  80
  81 #include <assert.h>
  82 #include <stdio.h>
  83 #include <stdlib.h>
  84 #include <sys/types.h>
  85 #include <sys/stat.h>
  86 #include <errno.h>
  87 #include <fcntl.h>
  88 #include <string.h>
  89 #include <ctype.h>
  90
  91 #ifdef __windows
  92 #include <io.h>
  93 #else
  94 #include <unistd.h>
  95 #endif
  96
  97 /* modes */
  98 #ifdef __windows
  99 #define FILE_O_RDONLY     _O_RDONLY
 100 #define FILE_O_BINARY     _O_BINARY
 101 #define PATHNCMP _strnicmp /* MSVC converts paths to lower-case sometimes? */
 102 #define inline __inline
 103 #define ssize_t long
 104 #define S_ISREG(mode) (((mode) & _S_IFMT) == (_S_IFREG)) /* MSVC does not have this macro */
 105 #else /* not windaube */
 106 #define FILE_O_RDONLY     O_RDONLY
 107 #define FILE_O_BINARY     0
 108 #define PATHNCMP strncmp
 109 #endif /* not windaube */
 110
 111 #ifndef TRUE
 112 #define TRUE 1
 113 #endif
 114 #ifndef FALSE
 115 #define FALSE 0
 116 #endif
 117
 118 int internal_boost = 0;
 119 static char* base_dir;
 120 static char* work_dir;
 121
 122 #ifdef __GNUC__
 123 #define clz __builtin_clz
 124 #else
 125 static inline int clz(unsigned int value)
 126 {
 127 int result = 32;
 128
 129     while(value)
 130     {
 131         value >>= 1;
 132         result -= 1;
 133     }
 134     return result;
 135 }
 136 #endif
 137
 138 #if (USE_MEMORY_ALIGNMENT > 4)
 139 #define get_unaligned_uint(str)           (*(unsigned int*)(str))
 140 #else
 141 static inline unsigned int get_unaligned_uint(const unsigned char* cursor)
 142 {
 143 unsigned int   result;
 144
 145     memcpy(&result, cursor, sizeof(unsigned int));
 146     return result;
 147 }
 148 #endif
 149
 150 /* ===============================================
 151  * memory pool for fast fix-size allocation (non-tread-safe)
 152  * ===============================================
 153  */
 154 struct pool
 155 {
 156     void*    head_free;  /**< head of a linked list of freed element */
 157     char*    fresh;      /**< top of a memory block to dig new element */
 158     char*    tail;       /**< to detect end of extent... when fresh pass tail */
 159     void*    extent;     /**< pointer to the primary extent block */
 160     int      size_elem;  /**< size of an element. */
 161     int      primary;    /**< primary allocation in bytes */
 162     int      secondary;  /**< secondary allocation in bytes */
 163 };
 164 #define POOL_ALIGN_INCREMENT 8 /**< Alignement, must be a power of 2 and of size > to sizeof(void*) */
 165
 166
 167 static void* pool_take_extent(struct pool* pool, int allocate)
 168 {
 169 unsigned int size = 0;
 170 void* extent;
 171 void* data = NULL;
 172
 173     if(pool->extent)
 174     {
 175         /* we already have an extent, so this is a secondary */
 176         if(pool->secondary)
 177         {
 178             size = pool->secondary;
 179         }
 180     }
 181     else
 182     {
 183         assert(pool->primary);
 184         size = pool->primary;
 185     }
 186     if(size)
 187     {
 188         extent = malloc(size);
 189         if(extent)
 190         {
 191             *(void**)extent = pool->extent;
 192             pool->extent = extent;
 193             if(allocate)
 194             {
 195                 data = ((char*)extent) + POOL_ALIGN_INCREMENT;
 196                 pool->fresh = ((char*)data) + pool->size_elem;
 197                 pool->tail = pool->fresh + (size - pool->size_elem);
 198             }
 199             else
 200             {
 201                 pool->fresh = ((char*)extent) + POOL_ALIGN_INCREMENT;
 202                 pool->tail = pool->fresh + (size - pool->size_elem);
 203             }
 204         }
 205     }
 206     return data;
 207 }
 208
 209 /* Create a memory pool for fix size objects
 210  * this is a simplified implementation that
 211  * is _not_ thread safe.
 212  */
 213 struct pool* pool_create(int size_elem, int primary, int secondary)
 214 {
 215 struct pool* pool;
 216
 217     assert(primary > 0);
 218     assert(secondary >= 0);
 219     assert(size_elem > 0);
 220
 221     pool = (struct pool*)calloc(1, sizeof(struct pool));
 222     if(!pool) return NULL;
 223     /* Adjust the element size so that it be aligned, and so that an element could
 224      * at least contain a void*
 225      */
 226     pool->size_elem = size_elem = (size_elem + POOL_ALIGN_INCREMENT - 1) & ~(POOL_ALIGN_INCREMENT - 1);
 227
 228     pool->primary = (size_elem * primary) + POOL_ALIGN_INCREMENT;
 229     pool->secondary = secondary > 0 ? (size_elem * secondary) + POOL_ALIGN_INCREMENT : 0;
 230     pool_take_extent(pool, FALSE);
 231
 232     return pool;
 233
 234 }
 235
 236 void pool_destroy(struct pool* pool)
 237 {
 238 void* extent;
 239 void* next;
 240
 241     if(pool != NULL)
 242     {
 243         extent = pool->extent;
 244         while(extent)
 245         {
 246             next = *(void**)extent;
 247             free(extent);
 248             extent = next;
 249         }
 250         free(pool);
 251     }
 252 }
 253
 254 static inline void* pool_alloc(struct pool* pool)
 255 {
 256 void* data;
 257
 258     data = pool->head_free;
 259     if(data == NULL)
 260     {
 261         /* we have no old-freed elem */
 262         if(pool->fresh <= pool->tail)
 263         {
 264             /* pick a slice of the current extent */
 265             data = (void*)pool->fresh;
 266             pool->fresh += pool->size_elem;
 267         }
 268         else
 269         {
 270             /* allocate a new extent */
 271             data = pool_take_extent(pool, TRUE);
 272         }
 273     }
 274     else
 275     {
 276         /* re-used old freed element by chopipng the head of the free list */
 277         pool->head_free = *(void**)data;
 278     }
 279
 280     return data;
 281 }
 282
 283
 284 static inline void pool_free(struct pool* pool, void* data)
 285 {
 286     assert(pool && data);
 287
 288     /* stack on top of the free list */
 289     *(void**)data = pool->head_free;
 290     pool->head_free = data;
 291 }
 292
 293
 294 /* ===============================================
 295  * Hash implementation custumized to be just tracking
 296  * a unique list of string (i.e no data associated
 297  * with the key, no need for retrieval, etc..
 298  *
 299  * This is tuned for the particular use-case we have here
 300  * measures in tail_build showed that
 301  * we can get north of 4000 distinct values stored in a hash
 302  * the collision rate is at worse around 2%
 303  * the collision needing an expensive memcmp to resolve
 304  * have a rate typically at 1 per 1000
 305  * for tail_build we register 37229 unique key
 306  * with a total of 377 extra memcmp needed
 307  * which is completely negligible compared to the
 308  * number of memcmp required to eliminate duplicate
 309  * entry (north of 2.5 millions for tail_build)
 310  * ===============================================
 311  */
 312
 313 struct hash_elem
 314 {
 315     struct hash_elem* next;
 316     const char*    key;
 317     int      key_len;
 318 };
 319
 320 struct hash
 321 {
 322     struct hash_elem** array;
 323     struct pool* elems_pool;
 324     int flags;
 325     unsigned int used;
 326     unsigned int size;
 327     unsigned int load_limit;
 328 #ifdef HASH_STAT
 329     int stored;
 330     int collisions;
 331     int cost;
 332     int memcmp;
 333 #endif
 334 };
 335 #define HASH_F_NO_RESIZE (1<<0)
 336
 337 /* The following hash_compute function was adapted from :
 338  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
 339  *
 340  * The changes from the original are mostly cosmetic
 341  */
 342 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
 343
 344
 345 #if defined CORE_BIG_ENDIAN
 346 #define MASK_C1 0xFFFFFF00
 347 #define MASK_C2 0xFFFF0000
 348 #define MASK_C3 0xFF000000
 349 #elif defined CORE_LITTLE_ENDIAN
 350 #define MASK_C1 0xFFFFFF
 351 #define MASK_C2 0xFFFF
 352 #define MASK_C3 0xFF
 353 #else
 354 #error "Missing Endianness definition"
 355 #endif
 356
 357
 358 #define mix(a,b,c) \
 359 { \
 360   a -= c;  a ^= rot(c, 4);  c += b; \
 361   b -= a;  b ^= rot(a, 6);  a += c; \
 362   c -= b;  c ^= rot(b, 8);  b += a; \
 363   a -= c;  a ^= rot(c,16);  c += b; \
 364   b -= a;  b ^= rot(a,19);  a += c; \
 365   c -= b;  c ^= rot(b, 4);  b += a; \
 366 }
 367 #define final(a,b,c) \
 368 { \
 369   c ^= b; c -= rot(b,14); \
 370   a ^= c; a -= rot(c,11); \
 371   b ^= a; b -= rot(a,25); \
 372   c ^= b; c -= rot(b,16); \
 373   a ^= c; a -= rot(c,4);  \
 374   b ^= a; b -= rot(a,14); \
 375   c ^= b; c -= rot(b,24); \
 376 }
 377
 378 static unsigned int hash_compute( struct hash* hash, const char* key, int length)
 379 {
 380     unsigned int a;
 381     unsigned int b;
 382     unsigned int c;                                          /* internal state */
 383     const unsigned char* uk = (const unsigned char*)key;
 384
 385     /* Set up the internal state */
 386     a = b = c = 0xdeadbeef + (length << 2);
 387
 388     /* we use this to 'hash' full path with mostly a common root
 389      * let's now waste too much cycles hashing mostly constant stuff
 390      */
 391     if(length > 36)
 392     {
 393         uk += length - 36;
 394         length = 36;
 395     }
 396     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 397     while (length > 12)
 398     {
 399         a += get_unaligned_uint(uk);
 400         b += get_unaligned_uint(uk+4);
 401         c += get_unaligned_uint(uk+8);
 402         mix(a,b,c);
 403         length -= 12;
 404         uk += 12;
 405     }
 406
 407     /*----------------------------- handle the last (probably partial) block */
 408     /* Note: we possibly over-read, which would trigger complaint from VALGRIND
 409      * but we mask the undefined stuff if any, so we are still good, thanks
 410      * to alignment of memory allocation and tail-memory management overhead
 411      * we always can read 3 bytes past the official end without triggering
 412      * a segfault -- if you find a platform/compiler couple for which that postulat
 413      * is false, then you just need to over-allocate by 2 more bytes in file_load()
 414      * file_load already over-allocate by 1 to sitck a \0 at the end of the buffer.
 415      */
 416     switch(length)
 417     {
 418     case 12: c+=get_unaligned_uint(uk+8); b+=get_unaligned_uint(uk+4); a+=get_unaligned_uint(uk); break;
 419     case 11: c+=get_unaligned_uint(uk+8) & MASK_C1; b+=get_unaligned_uint(uk+4); a+=get_unaligned_uint(uk); break;
 420     case 10: c+=get_unaligned_uint(uk+8) & MASK_C2; b+=get_unaligned_uint(uk+4); a+=get_unaligned_uint(uk); break;
 421     case 9 : c+=get_unaligned_uint(uk+8) & MASK_C3; b+=get_unaligned_uint(uk+4); a+=get_unaligned_uint(uk); break;
 422     case 8 : b+=get_unaligned_uint(uk+4); a+=get_unaligned_uint(uk); break;
 423     case 7 : b+=get_unaligned_uint(uk+4) & MASK_C1; a+=get_unaligned_uint(uk); break;
 424     case 6 : b+=get_unaligned_uint(uk+4) & MASK_C2; a+=get_unaligned_uint(uk); break;
 425     case 5 : b+=get_unaligned_uint(uk+4) & MASK_C3; a+=get_unaligned_uint(uk); break;
 426     case 4 : a+=get_unaligned_uint(uk); break;
 427     case 3 : a+=get_unaligned_uint(uk) & MASK_C1; break;
 428     case 2 : a+=get_unaligned_uint(uk) & MASK_C2; break;
 429     case 1 : a+=get_unaligned_uint(uk) & MASK_C3; break;
 430     case 0 : return c & hash->size;              /* zero length strings require no mixing */
 431     }
 432
 433     final(a,b,c);
 434     return c & hash->size;
 435 }
 436
 437 static void hash_destroy(struct hash* hash)
 438 {
 439     if(hash)
 440     {
 441         if(hash->array)
 442         {
 443             free(hash->array);
 444         }
 445         if(hash->elems_pool)
 446         {
 447             pool_destroy(hash->elems_pool);
 448         }
 449         free(hash);
 450     }
 451 }
 452
 453 static struct hash* hash_create(unsigned int size)
 454 {
 455 struct hash* hash;
 456
 457     assert(size > 0);
 458     hash = calloc(1, sizeof(struct hash));
 459     if(hash)
 460     {
 461         size += (size >> 2) + 1; /* ~ 75% load factor */
 462         if(size >= 15)
 463         {
 464             hash->size = (((unsigned int)0xFFFFFFFF) >> clz((unsigned int)size));
 465         }
 466         else
 467         {
 468             hash->size = size = 15;
 469         }
 470         hash->load_limit = hash->size - (hash->size >> 2);
 471         hash->used = 0;
 472         hash->array = (struct hash_elem**)calloc(hash->size + 1, sizeof(struct hash_elem*));
 473         if(hash->array == NULL)
 474         {
 475             hash_destroy(hash);
 476             hash = NULL;
 477         }
 478     }
 479     if(hash)
 480     {
 481         hash->elems_pool = pool_create(sizeof(struct hash_elem),
 482                                        size, size << 1);
 483         if(!hash->elems_pool)
 484         {
 485             hash_destroy(hash);
 486             hash = NULL;
 487         }
 488     }
 489     return hash;
 490 }
 491
 492 static void hash_resize(struct hash* hash)
 493 {
 494 unsigned int old_size = hash->size;
 495 unsigned int hashed;
 496 struct hash_elem* hash_elem;
 497 struct hash_elem* next;
 498 struct hash_elem** array;
 499 unsigned int i;
 500
 501     hash->size = (old_size << 1) + 1;
 502     /* we really should avoid to get there... so print a message to alert of the condition */
 503     fprintf(stderr, "resize hash %d -> %d\n", old_size, hash->size);
 504     if(hash->size == old_size)
 505     {
 506         hash->flags |= HASH_F_NO_RESIZE;
 507         return;
 508     }
 509     array = calloc(hash->size + 1, sizeof(struct hash_elem*));
 510     if(array)
 511     {
 512         hash->load_limit = hash->size - (hash->size >> 2);
 513         for(i=0; i <= old_size; i++)
 514         {
 515             hash_elem = (struct hash_elem*)hash->array[i];
 516             while(hash_elem)
 517             {
 518                 next = hash_elem->next;
 519
 520                 hashed = hash_compute(hash, hash_elem->key, hash_elem->key_len);
 521                 hash_elem->next = array[hashed];
 522                 array[hashed] = hash_elem;
 523                 hash_elem = next;
 524             }
 525         }
 526         free(hash->array);
 527         hash->array = (struct hash_elem**)array;
 528     }
 529     else
 530     {
 531         hash->size = old_size;
 532         hash->flags |= HASH_F_NO_RESIZE;
 533     }
 534 }
 535
 536 #ifdef HASH_STAT
 537 static inline int compare_key(struct hash* hash, const char* a, const char* b, int len, int* cost)
 538 {
 539     *cost += 1;
 540     hash->memcmp += 1;
 541     return memcmp(a,b, len);
 542 }
 543 #else
 544 #define compare_key(h,a,b,l,c) memcmp(a,b,l)
 545 #endif
 546
 547 /* a customized hash_store function that just store the key and return
 548  * TRUE if the key was effectively stored, or FALSE if the key was already there
 549  */
 550 static int hash_store(struct hash* hash, const char* key, int key_len)
 551 {
 552 unsigned int hashed;
 553 struct hash_elem* hash_elem;
 554 int cost = 0;
 555
 556     (void) cost;
 557     hashed = hash_compute(hash, key, key_len);
 558 #ifdef HASH_STAT
 559     hash->stored += 1;
 560 #endif
 561     hash_elem = (struct hash_elem*)hash->array[hashed];
 562     while(hash_elem && (hash_elem->key_len != key_len || compare_key(hash, hash_elem->key, key, key_len, &cost)))
 563     {
 564         hash_elem = hash_elem->next;
 565     }
 566
 567     if(!hash_elem)
 568     {
 569         hash_elem = pool_alloc(hash->elems_pool);
 570         if(hash_elem)
 571         {
 572             hash_elem->key = key;
 573             hash_elem->key_len = key_len;
 574             hash_elem->next = hash->array[hashed];
 575
 576 #ifdef HASH_STAT
 577             if(hash_elem->next)
 578             {
 579                 hash->collisions += 1;
 580                 hash->cost += cost;
 581             }
 582 #endif
 583             hash->array[hashed] = hash_elem;
 584             hash->used += 1;
 585             if(hash->used > hash->load_limit)
 586             {
 587                 hash_resize(hash);
 588             }
 589         }
 590         return TRUE;
 591     }
 592     return FALSE;
 593 }
 594
 595 static int file_stat(const char* name, struct stat* buffer_stat, int* rc)
 596 {
 597 int rc_local = 0;
 598
 599     rc_local = stat(name, buffer_stat);
 600     if (rc_local  < 0)
 601     {
 602         *rc = errno;
 603     }
 604     return rc_local;
 605 }
 606
 607 static off_t file_get_size(const char* name, int* rc)
 608 {
 609 struct stat buffer_stat;
 610 off_t       size = -1;
 611
 612     if (!file_stat(name, &buffer_stat, rc))
 613     {
 614         if(S_ISREG(buffer_stat.st_mode))
 615         {
 616             size = buffer_stat.st_size;
 617         }
 618         else
 619         {
 620             *rc = EINVAL;
 621         }
 622     }
 623     return size;
 624 }
 625
 626 static char* file_load(const char* name, off_t* size, int* return_rc)
 627 {
 628 off_t local_size = 0;
 629 int rc = 0;
 630 char* buffer = NULL;
 631 int fd;
 632
 633     assert(name != NULL);
 634
 635     if(!size)
 636     {
 637         size = &local_size;
 638     }
 639     *size = file_get_size(name, &rc);
 640     if (!rc)
 641     {
 642         fd = open(name, FILE_O_RDONLY | FILE_O_BINARY);
 643         if (!(fd == -1))
 644         {
 645             buffer = malloc((size_t)(*size + 1));
 646             if (buffer == NULL)
 647             {
 648                 rc = ENOMEM;
 649             }
 650             else
 651             {
 652             ssize_t i;
 653
 654               REDO:
 655                 i = read(fd, buffer, (size_t)(*size));
 656                 if(i == -1)
 657                 {
 658                     if(errno == EINTR)
 659                     {
 660                         goto REDO;
 661                     }
 662                     else
 663                     {
 664                         rc = errno;
 665                     }
 666                 }
 667                 else
 668                 {
 669                     if (i != *size)
 670                     {
 671                         rc = EIO;
 672                     }
 673                 }
 674                 buffer[*size] = 0;
 675             }
 676             close(fd);
 677         }
 678     }
 679
 680     if(rc && buffer)
 681     {
 682         free(buffer);
 683         buffer = NULL;
 684     }
 685     if(return_rc)
 686     {
 687         *return_rc = rc;
 688     }
 689     return buffer;
 690 }
 691
 692 static void _cancel_relative(char* base, char** ref_cursor, char** ref_cursor_out, char* end)
 693 {
 694     char* cursor = *ref_cursor;
 695     char* cursor_out = *ref_cursor_out;
 696
 697     do
 698     {
 699         cursor += 3;
 700         while(cursor_out > base && cursor_out[-1] == '/')
 701             cursor_out--;
 702         while(cursor_out > base && *--cursor_out != '/');
 703     }
 704     while(cursor + 3 < end && !memcmp(cursor, "/../", 4));
 705     *ref_cursor = cursor;
 706     *ref_cursor_out = cursor_out;
 707 }
 708
 709 static inline void eat_space(char ** token)
 710 {
 711     while ((' ' == **token) || ('\t' == **token)) {
 712         ++(*token);
 713     }
 714 }
 715
 716 /*
 717  * Prune LibreOffice specific duplicate dependencies to improve
 718  * gnumake startup time, and shrink the disk-space footprint.
 719  */
 720 static inline int
 721 elide_dependency(const char* key, int key_len, const char **unpacked_end)
 722 {
 723 #if 0
 724     {
 725         int i;
 726         fprintf (stderr, "elide?%d!: '", internal_boost);
 727         for (i = 0; i < key_len; i++) {
 728             fprintf (stderr, "%c", key[i]);
 729         }
 730         fprintf (stderr, "'\n");
 731     }
 732 #endif
 733
 734     /* boost brings a plague of header files */
 735     int i;
 736     int unpacked = 0;
 737     /* walk down path elements */
 738     for (i = 0; i < key_len - 1; i++)
 739     {
 740         if (key[i] == '/')
 741         {
 742             if (0 == unpacked)
 743             {
 744                 if (!PATHNCMP(key + i + 1, "workdir/", 8))
 745                 {
 746                     unpacked = 1;
 747                     continue;
 748                 }
 749             }
 750             else
 751             {
 752                 if (!PATHNCMP(key + i + 1, "UnpackedTarball/", 16))
 753                 {
 754                     if (unpacked_end)
 755                         *unpacked_end = strchr(key + i + 17, '/');
 756                     return 1;
 757                 }
 758             }
 759         }
 760     }
 761
 762     return 0;
 763 }
 764
 765 /*
 766  * We collapse tens of internal boost headers to the unpacked target, such
 767  * that you can re-compile / install boost and all is well.
 768  */
 769 static void emit_single_boost_header(void)
 770 {
 771 #define BOOST_TARGET "/UnpackedTarball/boost.done"
 772     fprintf(stdout, "%s" BOOST_TARGET " ", work_dir);
 773 }
 774
 775 static void emit_unpacked_target(const char* token, const char* end)
 776 {
 777     fwrite(token, 1, end-token, stdout);
 778     fputs(".done ", stdout);
 779 }
 780
 781 /* prefix paths to absolute */
 782 static inline void print_fullpaths(char* line)
 783 {
 784     char* token;
 785     char* end;
 786     int boost_count = 0;
 787     int token_len;
 788     const char * unpacked_end = 0; /* end of UnpackedTarget match (if any) */
 789     /* for UnpackedTarget the target is GenC{,xx}Object, dont mangle! */
 790     int target_seen = 0;
 791
 792     token = line;
 793     eat_space(&token);
 794     while (*token)
 795     {
 796         end = token;
 797         /* hard to believe that in this day and age drive letters still exist */
 798         if (*end && (':' == *(end+1)) &&
 799             (('\\' == *(end+2)) || ('/' == *(end+2))) && isalpha(*end))
 800         {
 801             end = end + 3; /* only one cross, err drive letter per filename */
 802         }
 803         while (*end && (' ' != *end) && ('\t' != *end) && (':' != *end)) {
 804             ++end;
 805         }
 806         token_len = end - token;
 807         if (target_seen &&
 808             elide_dependency(token, token_len, &unpacked_end))
 809         {
 810             if (unpacked_end)
 811             {
 812                 if (internal_boost && !PATHNCMP(unpacked_end - 5, "boost", 5))
 813                 {
 814                     ++boost_count;
 815                     if (boost_count == 1)
 816                         emit_single_boost_header();
 817                     else
 818                     {
 819                         /* don't output, and swallow trailing \\\n if any */
 820                         token = end;
 821                         eat_space(&token);
 822                         if (token[0] == '\\' && token[1] == '\n')
 823                             end = token + 2;
 824                     }
 825                 }
 826                 else
 827                 {
 828                     emit_unpacked_target(token, unpacked_end);
 829                 }
 830                 unpacked_end = 0;
 831             }
 832         }
 833         else
 834         {
 835             if (fwrite(token, token_len, 1, stdout) != 1)
 836                 abort();
 837             fputc(' ', stdout);
 838         }
 839         token = end;
 840         eat_space(&token);
 841         if (!target_seen)
 842         {
 843             if (':' == *token)
 844             {
 845                 target_seen = 1;
 846                 fputc(':', stdout);
 847                 ++token;
 848                 eat_space(&token);
 849             }
 850         }
 851     }
 852 }
 853
 854 static inline char * eat_space_at_end(char * end)
 855 {
 856     char * real_end;
 857     assert('\0' == *end);
 858     real_end = end - 1;
 859     while (' ' == *real_end || '\t' == *real_end || '\n' == *real_end
 860                 || ':' == *real_end)
 861     {    /* eat colon and whitespace at end */
 862          --real_end;
 863     }
 864     return real_end;
 865 }
 866
 867 static int _process(struct hash* dep_hash, char* fn)
 868 {
 869 int rc;
 870 char* buffer;
 871 char* end;
 872 char* cursor;
 873 char* cursor_out;
 874 char* base;
 875 int continuation = 0;
 876 char last_ns = 0;
 877 off_t size;
 878
 879     buffer = file_load(fn, &size, &rc);
 880     /* Note: yes we are going to leak 'buffer'
 881      * this is on purpose, to avoid cloning the 'key' out of it
 882      * and our special 'hash' just store the pointer to the key
 883      * inside of buffer, hence it need to remain allocated
 884      */
 885     if(!rc)
 886     {
 887         base = cursor_out = cursor = end = buffer;
 888         end += size;
 889
 890         /* first eat unneeded space at the beginning of file
 891          */
 892         while(cursor < end && (*cursor == ' ' || *cursor == '\\'))
 893             ++cursor;
 894
 895         while(cursor < end)
 896         {
 897             if(*cursor == '\\')
 898             {
 899                 continuation = 1;
 900                 *cursor_out++ = *cursor++;
 901             }
 902             else if(*cursor == '/')
 903             {
 904                 if(cursor + 3 < end)
 905                 {
 906                     if(!memcmp(cursor, "/../", 4))
 907                     {
 908                         _cancel_relative(base, &cursor, &cursor_out, end);
 909                     }
 910                 }
 911                 *cursor_out++ = *cursor++;
 912             }
 913             else if(*cursor == '\n')
 914             {
 915                 if(!continuation)
 916                 {
 917                     *cursor_out = 0;
 918                     if(base < cursor)
 919                     {
 920                         /* here we have a complete rule */
 921                         if(last_ns == ':')
 922                         {
 923                             /* if the rule ended in ':' that is a no-dep rule
 924                              * these are the one for which we want to filter
 925                              * duplicate out
 926                              */
 927                             int key_len = eat_space_at_end(cursor_out) - base;
 928                             if (!elide_dependency(base,key_len + 1, NULL)
 929                                 && hash_store(dep_hash, base, key_len))
 930                             {
 931                                 /* DO NOT modify base after it has been added
 932                                    as key by hash_store */
 933                                 print_fullpaths(base);
 934                                 putc('\n', stdout);
 935                             }
 936                         }
 937                         else
 938                         {
 939                             /* rule with dep, just write it */
 940                             print_fullpaths(base);
 941                             putc('\n', stdout);
 942                         }
 943                         last_ns = ' '; // cannot hurt to reset it
 944                     }
 945                     cursor += 1;
 946                     base = cursor_out = cursor;
 947                 }
 948                 else
 949                 {
 950                     /* here we have a '\' followed by \n this is a continuation
 951                      * i.e not a complete rule yet
 952                      */
 953                     *cursor_out++ = *cursor++;
 954                     continuation = 0; // cancel current one (empty lines!)
 955                 }
 956             }
 957             else
 958             {
 959                 continuation = 0;
 960                 /* not using isspace() here save 25% of I refs and 75% of D refs based on cachegrind */
 961                 if(*cursor != ' ' && *cursor != '\n' && *cursor != '\t' )
 962                 {
 963                     last_ns = *cursor;
 964                 }
 965                 *cursor_out++ = *cursor++;
 966             }
 967         }
 968         /* just in case the file did not end with a \n, there may be a pending rule */
 969         if(base < cursor_out)
 970         {
 971             if(last_ns == ':')
 972             {
 973                 int key_len = eat_space_at_end(cursor_out) - base;
 974                 if (!elide_dependency(base,key_len + 1, NULL) &&
 975                     hash_store(dep_hash, base, key_len))
 976                 {
 977                     puts(base);
 978                     putc('\n', stdout);
 979                 }
 980             }
 981             else
 982             {
 983                 puts(base);
 984                 putc('\n', stdout);
 985             }
 986         }
 987     }
 988     return rc;
 989 }
 990
 991 static void _usage(void)
 992 {
 993     fputs("Usage: concat-deps <file that contains dep_files>\n", stderr);
 994 }
 995
 996 #define kDEFAULT_HASH_SIZE 4096
 997
 998 static int get_var(char **var, const char *name)
 999 {
1000     *var = (char *)getenv(name);
1001     if(!*var)
1002     {
1003         fprintf(stderr,"Error: %s is missing in the environement\n", name);
1004         return 1;
1005     }
1006     return 0;
1007 }
1008
1009 int main(int argc, char** argv)
1010 {
1011 int rc = 0;
1012 off_t in_list_size = 0;
1013 char* in_list;
1014 char* in_list_cursor;
1015 char* in_list_base;
1016 struct hash* dep_hash;
1017 const char *env_str;
1018
1019     if(argc < 2)
1020     {
1021         _usage();
1022         return 1;
1023     }
1024     if(get_var(&base_dir, "SRCDIR") || get_var(&work_dir, "WORKDIR"))
1025         return 1;
1026
1027     env_str = getenv("SYSTEM_BOOST");
1028     internal_boost = !env_str || strcmp(env_str,"TRUE");
1029
1030     in_list = file_load(argv[1], &in_list_size, &rc);
1031     if(!rc)
1032     {
1033         dep_hash = hash_create( kDEFAULT_HASH_SIZE);
1034         in_list_base = in_list_cursor = in_list;
1035
1036         /* extract filename of dep file from a 'space' separated list */
1037         while(*in_list_cursor)
1038         {
1039             if(*in_list_cursor == ' ' || *in_list_cursor == '\n')
1040             {
1041                 *in_list_cursor = 0;
1042                 if(in_list_base < in_list_cursor)
1043                 {
1044                     rc = _process(dep_hash, in_list_base);
1045                     if(rc)
1046                     {
1047                         break;
1048                     }
1049                 }
1050                 in_list_cursor += 1;
1051                 in_list_base = in_list_cursor;
1052             }
1053             else
1054             {
1055                 in_list_cursor += 1;
1056             }
1057         }
1058         if(!rc)
1059         {
1060             /* catch the last entry in case the input did not terminate with a 'space' */
1061             if(in_list_base < in_list_cursor)
1062             {
1063                 rc = _process(dep_hash, in_list_base);
1064             }
1065         }
1066 #ifdef HASH_STAT
1067         fprintf(stderr, "stats: u:%d s:%d l:%d t:%d c:%d m:%d $:%d\n",
1068                 dep_hash->used, dep_hash->size, dep_hash->load_limit, dep_hash->stored,
1069                 dep_hash->collisions, dep_hash->memcmp, dep_hash->cost);
1070 #endif
1071     }
1072     return rc;
1073 }
1074
1075 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */