Florian Ragwitz pushed to branch wip/rafl/hpc-tixdir at Glasgow Haskell Compiler / GHC

Commits:

2 changed files:

Changes:

  • .gitlab/ci.sh
    ... ... @@ -903,11 +903,11 @@ function save_hpc_coverage() {
    903 903
       # Keep whatever has been generated even if the build or tests failed.
    
    904 904
       $GHC -c -o tix-rle-merge.o tix-rle-merge.c
    
    905 905
       $GHC -no-hs-main -o tix-rle-merge tix-rle-merge.o
    
    906
    -  ./tix-rle-merge _build/ghc-tix/ _build/ghc.tix
    
    906
    +  ./tix-rle-merge _build/ghc-tix/ _build/tix-merged
    
    907 907
       if [[ -d _build/ghc-hpc || -d _build/ghc-tix ]]; then
    
    908 908
         mkdir -p _build/ghc-hpc _build/ghc-tix
    
    909
    -    du -sh _build/ghc-hpc _build/ghc-tix _build/ghc.tix
    
    910
    -    tar -czf ghc-hpc-coverage.tar.gz _build/ghc-hpc _build/ghc.tix
    
    909
    +    du -sh _build/ghc-hpc _build/ghc-tix _build/tix-merged
    
    910
    +    tar -czf ghc-hpc-coverage.tar.gz _build/ghc-hpc _build/tix-merged
    
    911 911
         ls -lh ghc-hpc-coverage.tar.gz
    
    912 912
       else
    
    913 913
         warn "No HPC coverage directories found"
    

  • tix-rle-merge.c
    1
    -/* Merge HPC prototype run-length-encoded .tix files (NOT part of GHC).
    
    1
    +/* Group and merge HPC binary RLE .tix files without combining incompatible
    
    2
    + * versions of the same module.
    
    2 3
      *
    
    3
    - * Build: cc -O3 -std=c11 -Wall -Wextra -o tix-rle-merge tix-rle-merge.c
    
    4
    - * Usage: ./tix-rle-merge RLE_DIRECTORY OUTPUT.tix
    
    4
    + * Build: cc -O2 -std=c11 -Wall -Wextra -pedantic -o tix-rle-merge tix-rle-merge-grouped.c
    
    5
    + * Usage: tix-rle-merge INPUT_DIRECTORY EMPTY_OUTPUT_DIRECTORY
    
    5 6
      *
    
    6
    - * Input and output format (HPCTIX\2):
    
    7
    - *   7 bytes "HPCTIX\2", ULEB128 module count;
    
    8
    - *   for each module:
    
    9
    - *     ULEB128 name length, name bytes, little-endian uint32 hash,
    
    10
    - *     ULEB128 box count;
    
    11
    - *     repeated (ULEB128 zero-run length, ULEB128 nonzero-run length,
    
    12
    - *               that many positive ULEB128 Word64 counts)
    
    13
    - *     until exactly 'box count' counters are described.
    
    7
    + * Input format: "HPCTIX\0", ULEB128 number of modules; each module has
    
    8
    + * ULEB128 name length, name bytes, little-endian uint32 HPC hash, ULEB128
    
    9
    + * box count, then alternating (zero run, nonzero run, positive counter values)
    
    10
    + * encoded in ULEB128 until all box positions are covered. Output is the same.
    
    14 11
      *
    
    15
    - * No terminator follows an RLE module. A trailing zero run is represented
    
    16
    - * by (zero-run length, 0). Modules with zero boxes contain no run records.
    
    12
    + * Group assignment is greedy, deterministic (lexicographic filename order):
    
    13
    + * - never group files with a shared module name but different hash/box count;
    
    14
    + * - require at least one shared module to merge into an existing group;
    
    15
    + * - prefer the compatible group sharing the most boxes, then most modules,
    
    16
    + *   then most existing files, then lowest group number;
    
    17
    + * - otherwise create a new group.
    
    17 18
      *
    
    18
    - * The accumulator is a dense uint64_t array per distinct module, as in
    
    19
    - * tix-sparse-prototype.c. Checks counter overflow and malformed inputs.
    
    19
    + * This is a conservative heuristic, not a unique/optimal partition.
    
    20
    + * Results are in merged-0001.tix, ... ; assignments.tsv lists every input;
    
    21
    + * groups.txt gives group sizes, contents and split explanations. The output
    
    22
    + * directory must be empty (or nonexistent) to avoid stale results.
    
    23
    + *
    
    24
    + * Two passes: inspect all inputs and assign groups without retaining counters;
    
    25
    + * then merge and write one group at a time. Thus memory is bounded by the
    
    26
    + * metadata for the groups plus one dense set of counters.
    
    20 27
      */
    
    21 28
     #define _POSIX_C_SOURCE 200809L
    
    22 29
     #include <dirent.h>
    
    23 30
     #include <errno.h>
    
    24 31
     #include <inttypes.h>
    
    32
    +#include <limits.h>
    
    25 33
     #include <stdint.h>
    
    26 34
     #include <stdio.h>
    
    27 35
     #include <stdlib.h>
    
    ... ... @@ -29,16 +37,35 @@
    29 37
     #include <sys/stat.h>
    
    30 38
     
    
    31 39
     #define MAGIC "HPCTIX\0"
    
    40
    +#define MAGIC_SIZE 7
    
    32 41
     #define BUCKETS 8192
    
    33 42
     
    
    34 43
     typedef struct { unsigned char *data; size_t len, cap; } Buffer;
    
    35 44
     typedef struct { const unsigned char *p, *end; } Reader;
    
    45
    +typedef struct { char *name; uint32_t hash; size_t n; } InputMod;
    
    46
    +typedef struct { InputMod *mods; size_t len, cap; } Input;
    
    47
    +typedef struct Sig {
    
    48
    +    char *name;
    
    49
    +    uint32_t hash;
    
    50
    +    size_t n;
    
    51
    +    const char *first_path;   /* borrowed from sorted input path list */
    
    52
    +    struct Sig *next;
    
    53
    +} Sig;
    
    54
    +typedef struct {
    
    55
    +    Sig *buckets[BUCKETS];
    
    56
    +    size_t *indices;          /* indices into the sorted input path list */
    
    57
    +    size_t len, cap, modules;
    
    58
    +    char *reason;
    
    59
    +} Group;
    
    60
    +typedef struct {
    
    61
    +    size_t group, shared_modules;
    
    62
    +    uint64_t shared_boxes;
    
    63
    +} Assignment;
    
    36 64
     typedef struct Module {
    
    37 65
         char *name;
    
    38 66
         uint32_t hash;
    
    39 67
         size_t n;
    
    40
    -    uint64_t *ticks;
    
    41
    -    uint64_t seen_epoch;
    
    68
    +    uint64_t *ticks, seen_epoch;
    
    42 69
         struct Module *next;
    
    43 70
     } Module;
    
    44 71
     typedef struct {
    
    ... ... @@ -58,11 +85,22 @@ static void *xmalloc(size_t n) {
    58 85
         if (!p) die("out of memory");
    
    59 86
         return p;
    
    60 87
     }
    
    88
    +static void *xcalloc(size_t n, size_t s) {
    
    89
    +    if (s && n > SIZE_MAX / s) die("allocation overflow");
    
    90
    +    void *p = calloc(n ? n : 1, s ? s : 1);
    
    91
    +    if (!p) die("out of memory");
    
    92
    +    return p;
    
    93
    +}
    
    61 94
     static void *xrealloc(void *p, size_t n) {
    
    62 95
         void *q = realloc(p, n ? n : 1);
    
    63 96
         if (!q) die("out of memory");
    
    64 97
         return q;
    
    65 98
     }
    
    99
    +static char *xstrdup(const char *s) {
    
    100
    +    char *p = strdup(s);
    
    101
    +    if (!p) die("out of memory");
    
    102
    +    return p;
    
    103
    +}
    
    66 104
     static void reserve(Buffer *b, size_t add) {
    
    67 105
         if (add > SIZE_MAX - b->len) die("buffer too large");
    
    68 106
         size_t need = b->len + add;
    
    ... ... @@ -97,20 +135,20 @@ static void put32(Buffer *b, uint32_t x) {
    97 135
     static uint64_t getvar(Reader *r) {
    
    98 136
         uint64_t x = 0;
    
    99 137
         for (unsigned k = 0; k < 10; k++) {
    
    100
    -        if (r->p == r->end) die("truncated variable-length integer");
    
    138
    +        if (r->p == r->end) die("truncated ULEB128");
    
    101 139
             unsigned c = *r->p++;
    
    102
    -        if (k == 9 && (c & 0xfe)) die("variable-length integer overflow");
    
    140
    +        if (k == 9 && (c & 0xfe)) die("ULEB128 overflow");
    
    103 141
             x |= (uint64_t)(c & 127) << (7*k);
    
    104 142
             if (!(c & 128)) {
    
    105
    -            if (k && c == 0) die("noncanonical variable-length integer");
    
    143
    +            if (k && c == 0) die("noncanonical ULEB128");
    
    106 144
                 return x;
    
    107 145
             }
    
    108 146
         }
    
    109
    -    die("unterminated variable-length integer");
    
    147
    +    die("unterminated ULEB128");
    
    110 148
         return 0;
    
    111 149
     }
    
    112 150
     static uint32_t get32(Reader *r) {
    
    113
    -    if ((size_t)(r->end - r->p) < 4) die("truncated hash");
    
    151
    +    if ((size_t)(r->end - r->p) < 4) die("truncated module hash");
    
    114 152
         uint32_t x = 0;
    
    115 153
         for (unsigned k = 0; k < 4; k++) x |= (uint32_t)(*r->p++) << (8*k);
    
    116 154
         return x;
    
    ... ... @@ -139,24 +177,194 @@ static uint64_t namehash(const char *s) {
    139 177
         for (; *s; s++) { h ^= (unsigned char)*s; h *= UINT64_C(1099511628211); }
    
    140 178
         return h;
    
    141 179
     }
    
    142
    -static Module *module(Acc *a, const char *name, uint32_t hash, size_t n) {
    
    143
    -    size_t bucket = namehash(name) % BUCKETS;
    
    144
    -    for (Module *m = a->buckets[bucket]; m; m = m->next) {
    
    180
    +static size_t bucket_of(const char *s) { return (size_t)(namehash(s) % BUCKETS); }
    
    181
    +static char *join(const char *dir, const char *file) {
    
    182
    +    size_t a = strlen(dir), b = strlen(file);
    
    183
    +    if (a > SIZE_MAX - b - 2) die("path too long");
    
    184
    +    char *p = xmalloc(a + b + 2);
    
    185
    +    snprintf(p, a + b + 2, "%s/%s", dir, file);
    
    186
    +    return p;
    
    187
    +}
    
    188
    +static int is_tix(const char *s) {
    
    189
    +    size_t n = strlen(s);
    
    190
    +    return n >= 4 && strcmp(s + n - 4, ".tix") == 0;
    
    191
    +}
    
    192
    +static int cmpstr(const void *a, const void *b) {
    
    193
    +    return strcmp(*(char *const *)a, *(char *const *)b);
    
    194
    +}
    
    195
    +static int cmp_input_mod(const void *a, const void *b) {
    
    196
    +    return strcmp(((const InputMod *)a)->name, ((const InputMod *)b)->name);
    
    197
    +}
    
    198
    +static void input_append(Input *in, const char *name, uint32_t hash, size_t n) {
    
    199
    +    if (in->len == in->cap) {
    
    200
    +        if (in->cap > SIZE_MAX / (2 * sizeof(*in->mods))) die("too many modules");
    
    201
    +        in->cap = in->cap ? in->cap * 2 : 64;
    
    202
    +        in->mods = xrealloc(in->mods, in->cap * sizeof(*in->mods));
    
    203
    +    }
    
    204
    +    in->mods[in->len++] = (InputMod){xstrdup(name), hash, n};
    
    205
    +}
    
    206
    +static void input_free(Input *in) {
    
    207
    +    for (size_t i = 0; i < in->len; i++) free(in->mods[i].name);
    
    208
    +    free(in->mods);
    
    209
    +}
    
    210
    +/* Validate the complete file and collect just its module signatures. */
    
    211
    +static Input inspect(const char *path) {
    
    212
    +    context = path;
    
    213
    +    size_t size;
    
    214
    +    unsigned char *data = readfile(path, &size);
    
    215
    +    Reader r = {data, data + size};
    
    216
    +    if (size < MAGIC_SIZE || memcmp(r.p, MAGIC, MAGIC_SIZE))
    
    217
    +        die("wrong magic/version (expected HPCTIX\\0)");
    
    218
    +    r.p += MAGIC_SIZE;
    
    219
    +    uint64_t nmods = getvar(&r);
    
    220
    +    if (nmods > (uint64_t)(r.end - r.p)) die("invalid module count");
    
    221
    +    Input in = {0};
    
    222
    +    for (uint64_t j = 0; j < nmods; j++) {
    
    223
    +        uint64_t length = getvar(&r);
    
    224
    +        if (length > SIZE_MAX - 1 || length > (uint64_t)(r.end - r.p))
    
    225
    +            die("invalid module name length");
    
    226
    +        char *name = xmalloc((size_t)length + 1);
    
    227
    +        memcpy(name, r.p, (size_t)length);
    
    228
    +        name[length] = 0;
    
    229
    +        if (memchr(name, 0, (size_t)length)) die("embedded NUL in module name");
    
    230
    +        r.p += (size_t)length;
    
    231
    +        uint32_t hash = get32(&r);
    
    232
    +        uint64_t boxes = getvar(&r);
    
    233
    +        if (boxes > SIZE_MAX / sizeof(uint64_t)) die("too many counters");
    
    234
    +        input_append(&in, name, hash, (size_t)boxes);
    
    235
    +        free(name);
    
    236
    +        size_t pos = 0;
    
    237
    +        while (pos < (size_t)boxes) {
    
    238
    +            uint64_t zeros = getvar(&r);
    
    239
    +            if (zeros > boxes - pos) die("zero run exceeds box count");
    
    240
    +            pos += (size_t)zeros;
    
    241
    +            uint64_t nonzeros = getvar(&r);
    
    242
    +            if (nonzeros > boxes - pos) die("nonzero run exceeds box count");
    
    243
    +            if (!zeros && !nonzeros) die("empty RLE record");
    
    244
    +            for (uint64_t k = 0; k < nonzeros; k++) {
    
    245
    +                if (!getvar(&r)) die("zero counter in nonzero run");
    
    246
    +            }
    
    247
    +            pos += (size_t)nonzeros;
    
    248
    +        }
    
    249
    +    }
    
    250
    +    if (r.p != r.end) die("unexpected trailing bytes");
    
    251
    +    free(data);
    
    252
    +    qsort(in.mods, in.len, sizeof(*in.mods), cmp_input_mod);
    
    253
    +    for (size_t i = 1; i < in.len; i++)
    
    254
    +        if (!strcmp(in.mods[i-1].name, in.mods[i].name)) die("duplicate module in input");
    
    255
    +    return in;
    
    256
    +}
    
    257
    +static Sig *lookup(const Group *g, const char *name) {
    
    258
    +    for (Sig *s = g->buckets[bucket_of(name)]; s; s = s->next)
    
    259
    +        if (!strcmp(s->name, name)) return s;
    
    260
    +    return NULL;
    
    261
    +}
    
    262
    +typedef struct {
    
    263
    +    size_t shared, conflicts;
    
    264
    +    uint64_t boxes;
    
    265
    +    const InputMod *bad_input;
    
    266
    +    const Sig *bad_group;
    
    267
    +} Comparison;
    
    268
    +static Comparison compare(const Group *g, const Input *in) {
    
    269
    +    Comparison c = {0};
    
    270
    +    for (size_t j = 0; j < in->len; j++) {
    
    271
    +        const InputMod *m = &in->mods[j];
    
    272
    +        const Sig *s = lookup(g, m->name);
    
    273
    +        if (!s) continue;
    
    274
    +        if (s->hash != m->hash || s->n != m->n) {
    
    275
    +            c.conflicts++;
    
    276
    +            if (!c.bad_input) { c.bad_input = m; c.bad_group = s; }
    
    277
    +        } else {
    
    278
    +            c.shared++;
    
    279
    +            if (UINT64_MAX - c.boxes < m->n) c.boxes = UINT64_MAX;
    
    280
    +            else c.boxes += m->n;
    
    281
    +        }
    
    282
    +    }
    
    283
    +    return c;
    
    284
    +}
    
    285
    +static void group_add(Group *g, const Input *in, size_t index, const char *path) {
    
    286
    +    for (size_t j = 0; j < in->len; j++) {
    
    287
    +        const InputMod *m = &in->mods[j];
    
    288
    +        if (lookup(g, m->name)) continue;
    
    289
    +        Sig *s = xmalloc(sizeof(*s));
    
    290
    +        *s = (Sig){xstrdup(m->name), m->hash, m->n, path, g->buckets[bucket_of(m->name)]};
    
    291
    +        g->buckets[bucket_of(m->name)] = s;
    
    292
    +        g->modules++;
    
    293
    +    }
    
    294
    +    if (g->len == g->cap) {
    
    295
    +        if (g->cap > SIZE_MAX / (2 * sizeof(*g->indices))) die("too many input files");
    
    296
    +        g->cap = g->cap ? 2 * g->cap : 16;
    
    297
    +        g->indices = xrealloc(g->indices, g->cap * sizeof(*g->indices));
    
    298
    +    }
    
    299
    +    g->indices[g->len++] = index;
    
    300
    +}
    
    301
    +static void group_free(Group *g) {
    
    302
    +    for (size_t i = 0; i < BUCKETS; i++) {
    
    303
    +        Sig *s = g->buckets[i];
    
    304
    +        while (s) { Sig *next = s->next; free(s->name); free(s); s = next; }
    
    305
    +    }
    
    306
    +    free(g->indices);
    
    307
    +    free(g->reason);
    
    308
    +    free(g);
    
    309
    +}
    
    310
    +static int better(const Comparison *a, const Group *ga,
    
    311
    +                  const Comparison *b, const Group *gb) {
    
    312
    +    if (a->boxes != b->boxes) return a->boxes > b->boxes;
    
    313
    +    if (a->shared != b->shared) return a->shared > b->shared;
    
    314
    +    return ga->len > gb->len;
    
    315
    +}
    
    316
    +static char *reason_for_new_group(Group **groups, size_t ng, const Input *in) {
    
    317
    +    if (!ng) return xstrdup("first input");
    
    318
    +    size_t nearest = SIZE_MAX, rejected = 0, unrelated = 0;
    
    319
    +    Comparison closest = {0};
    
    320
    +    for (size_t i = 0; i < ng; i++) {
    
    321
    +        Comparison c = compare(groups[i], in);
    
    322
    +        if (c.conflicts) {
    
    323
    +            rejected++;
    
    324
    +            if (nearest == SIZE_MAX || c.boxes > closest.boxes ||
    
    325
    +                (c.boxes == closest.boxes && c.shared > closest.shared)) {
    
    326
    +                nearest = i;
    
    327
    +                closest = c;
    
    328
    +            }
    
    329
    +        } else if (!c.shared) unrelated++;
    
    330
    +    }
    
    331
    +    char msg[1024];
    
    332
    +    if (nearest != SIZE_MAX) {
    
    333
    +        const InputMod *m = closest.bad_input;
    
    334
    +        const Sig *s = closest.bad_group;
    
    335
    +        snprintf(msg, sizeof(msg),
    
    336
    +                 "incompatible with %zu group(s); closest group %04zu shares "
    
    337
    +                 "%zu modules (%" PRIu64 " boxes), but %zu conflict(s); "
    
    338
    +                 "e.g. %s: existing hash=%08" PRIx32 " boxes=%zu (from %s); "
    
    339
    +                 "incoming hash=%08" PRIx32 " boxes=%zu",
    
    340
    +                 rejected, nearest + 1, closest.shared, closest.boxes,
    
    341
    +                 closest.conflicts, m->name, s->hash, s->n, s->first_path,
    
    342
    +                 m->hash, m->n);
    
    343
    +    } else {
    
    344
    +        snprintf(msg, sizeof(msg),
    
    345
    +                 "no shared module signatures with %zu existing group(s) (%zu disjoint)",
    
    346
    +                 ng, unrelated);
    
    347
    +    }
    
    348
    +    return xstrdup(msg);
    
    349
    +}
    
    350
    +
    
    351
    +/* The second pass is the original dense-counter merger, one group at a time. */
    
    352
    +static Module *acc_module(Acc *a, const char *name, uint32_t hash, size_t n) {
    
    353
    +    size_t b = bucket_of(name);
    
    354
    +    for (Module *m = a->buckets[b]; m; m = m->next) {
    
    145 355
             if (strcmp(m->name, name)) continue;
    
    146
    -        if (m->hash != hash || m->n != n) die("incompatible module hash/number of boxes");
    
    356
    +        if (m->hash != hash || m->n != n) die("grouping error: incompatible module");
    
    147 357
             return m;
    
    148 358
         }
    
    149 359
         if (n > SIZE_MAX / sizeof(uint64_t)) die("module too large");
    
    150 360
         Module *m = xmalloc(sizeof(*m));
    
    151
    -    m->name = strdup(name);
    
    152
    -    if (!m->name) die("out of memory");
    
    361
    +    *m = (Module){0};
    
    362
    +    m->name = xstrdup(name);
    
    153 363
         m->hash = hash;
    
    154 364
         m->n = n;
    
    155
    -    m->ticks = calloc(n ? n : 1, sizeof(uint64_t));
    
    156
    -    if (!m->ticks) die("out of memory");
    
    157
    -    m->seen_epoch = 0;
    
    158
    -    m->next = a->buckets[bucket];
    
    159
    -    a->buckets[bucket] = m;
    
    365
    +    m->ticks = xcalloc(n ? n : 1, sizeof(uint64_t));
    
    366
    +    m->next = a->buckets[b];
    
    367
    +    a->buckets[b] = m;
    
    160 368
         if (a->len == a->cap) {
    
    161 369
             if (a->cap > SIZE_MAX / (2 * sizeof(*a->mods))) die("too many modules");
    
    162 370
             a->cap = a->cap ? 2 * a->cap : 256;
    
    ... ... @@ -170,47 +378,40 @@ static void mergeone(Acc *a, const char *path) {
    170 378
         size_t size;
    
    171 379
         unsigned char *data = readfile(path, &size);
    
    172 380
         Reader r = {data, data + size};
    
    173
    -    if (size < 7 || memcmp(r.p, MAGIC, 7)) die("wrong magic/version (expected HPCTIX\\2)");
    
    174
    -    r.p += 7;
    
    381
    +    if (size < MAGIC_SIZE || memcmp(r.p, MAGIC, MAGIC_SIZE)) die("wrong magic/version");
    
    382
    +    r.p += MAGIC_SIZE;
    
    175 383
         uint64_t nmods = getvar(&r);
    
    176
    -    if (nmods > (uint64_t)(r.end - r.p)) die("invalid module count");
    
    177 384
         if (++a->epoch == 0) die("epoch overflow");
    
    178
    -
    
    179 385
         for (uint64_t j = 0; j < nmods; j++) {
    
    180
    -        uint64_t name_len = getvar(&r);
    
    181
    -        if (name_len > SIZE_MAX - 1 || name_len > (uint64_t)(r.end - r.p))
    
    386
    +        uint64_t length = getvar(&r);
    
    387
    +        if (length > SIZE_MAX - 1 || length > (uint64_t)(r.end - r.p))
    
    182 388
                 die("invalid name length");
    
    183
    -        char *name = xmalloc((size_t)name_len + 1);
    
    184
    -        memcpy(name, r.p, (size_t)name_len);
    
    185
    -        name[name_len] = 0;
    
    186
    -        if (memchr(name, 0, (size_t)name_len)) die("embedded NUL in module name");
    
    187
    -        r.p += (size_t)name_len;
    
    389
    +        char *name = xmalloc((size_t)length + 1);
    
    390
    +        memcpy(name, r.p, (size_t)length);
    
    391
    +        name[length] = 0;
    
    392
    +        r.p += (size_t)length;
    
    188 393
             uint32_t hash = get32(&r);
    
    189 394
             uint64_t boxes = getvar(&r);
    
    190 395
             if (boxes > SIZE_MAX / sizeof(uint64_t)) die("too many counters");
    
    191
    -        Module *m = module(a, name, hash, (size_t)boxes);
    
    396
    +        Module *m = acc_module(a, name, hash, (size_t)boxes);
    
    192 397
             free(name);
    
    193
    -        if (m->seen_epoch == a->epoch) die("duplicate module");
    
    398
    +        if (m->seen_epoch == a->epoch) die("duplicate module in input");
    
    194 399
             m->seen_epoch = a->epoch;
    
    195
    -
    
    196
    -        /* RLE records account for exactly 'boxes' positions. */
    
    197 400
             size_t pos = 0;
    
    198 401
             while (pos < m->n) {
    
    199 402
                 uint64_t zeros = getvar(&r);
    
    200
    -            if (zeros > m->n - pos) die("zero run exceeds module box count");
    
    403
    +            if (zeros > m->n - pos) die("zero run exceeds box count");
    
    201 404
                 pos += (size_t)zeros;
    
    202 405
                 uint64_t nonzeros = getvar(&r);
    
    203
    -            if (nonzeros > m->n - pos) die("nonzero run exceeds module box count");
    
    406
    +            if (nonzeros > m->n - pos) die("nonzero run exceeds box count");
    
    204 407
                 if (!zeros && !nonzeros) die("empty RLE record");
    
    205
    -
    
    206
    -            size_t stop = pos + (size_t)nonzeros;
    
    207
    -            for (; pos < stop; pos++) {
    
    208
    -                uint64_t value = getvar(&r);
    
    209
    -                if (!value) die("zero value in nonzero run");
    
    210
    -                if (UINT64_MAX - m->ticks[pos] < value) die("counter overflow");
    
    211
    -                m->ticks[pos] += value;
    
    408
    +            for (uint64_t k = 0; k < nonzeros; k++, pos++) {
    
    409
    +                uint64_t v = getvar(&r);
    
    410
    +                if (!v) die("zero counter in nonzero run");
    
    411
    +                if (v > UINT64_MAX - m->ticks[pos]) die("counter overflow");
    
    412
    +                m->ticks[pos] += v;
    
    212 413
                 }
    
    213
    -            if (UINT64_MAX - a->input_entries < nonzeros) die("entry count overflow");
    
    414
    +            if (nonzeros > UINT64_MAX - a->input_entries) die("entry count overflow");
    
    214 415
                 a->input_entries += nonzeros;
    
    215 416
             }
    
    216 417
         }
    
    ... ... @@ -222,60 +423,78 @@ static int cmpmod(const void *a, const void *b) {
    222 423
         const Module *const *x = a, *const *y = b;
    
    223 424
         return strcmp((*x)->name, (*y)->name);
    
    224 425
     }
    
    225
    -static Buffer serialise(const Acc *a) {
    
    426
    +static Buffer serialise(Acc *a) {
    
    226 427
         Buffer b = {0};
    
    227
    -    bytes(&b, MAGIC, 7);
    
    428
    +    qsort(a->mods, a->len, sizeof(*a->mods), cmpmod);
    
    429
    +    bytes(&b, MAGIC, MAGIC_SIZE);
    
    228 430
         putvar(&b, a->len);
    
    229 431
         for (size_t j = 0; j < a->len; j++) {
    
    230 432
             Module *m = a->mods[j];
    
    231
    -        size_t name_len = strlen(m->name);
    
    232
    -        putvar(&b, name_len);
    
    233
    -        bytes(&b, m->name, name_len);
    
    433
    +        size_t length = strlen(m->name);
    
    434
    +        putvar(&b, length);
    
    435
    +        bytes(&b, m->name, length);
    
    234 436
             put32(&b, m->hash);
    
    235 437
             putvar(&b, m->n);
    
    236
    -
    
    237 438
             size_t i = 0;
    
    238 439
             while (i < m->n) {
    
    239 440
                 size_t start = i;
    
    240
    -            while (i < m->n && m->ticks[i] == 0) i++;
    
    441
    +            while (i < m->n && !m->ticks[i]) i++;
    
    241 442
                 putvar(&b, i - start);
    
    242 443
                 start = i;
    
    243
    -            while (i < m->n && m->ticks[i] != 0) i++;
    
    444
    +            while (i < m->n && m->ticks[i]) i++;
    
    244 445
                 putvar(&b, i - start);
    
    245 446
                 for (size_t k = start; k < i; k++) putvar(&b, m->ticks[k]);
    
    246 447
             }
    
    247 448
         }
    
    248 449
         return b;
    
    249 450
     }
    
    250
    -static int is_tix(const char *s) {
    
    251
    -    size_t n = strlen(s);
    
    252
    -    return n >= 4 && strcmp(s + n - 4, ".tix") == 0;
    
    451
    +static void acc_free(Acc *a) {
    
    452
    +    for (size_t i = 0; i < a->len; i++) {
    
    453
    +        free(a->mods[i]->name);
    
    454
    +        free(a->mods[i]->ticks);
    
    455
    +        free(a->mods[i]);
    
    456
    +    }
    
    457
    +    free(a->mods);
    
    253 458
     }
    
    254
    -static int cmpstr(const void *a, const void *b) {
    
    255
    -    return strcmp(*(char *const *)a, *(char *const *)b);
    
    459
    +static void output_name(char *buf, size_t cap, size_t group) {
    
    460
    +    if (snprintf(buf, cap, "merged-%04zu.tix", group + 1) >= (int)cap)
    
    461
    +        die("too many output groups");
    
    462
    +}
    
    463
    +static void ensure_empty_output_dir(const char *in, const char *out) {
    
    464
    +    if (mkdir(out, 0777) && errno != EEXIST) { perror(out); exit(1); }
    
    465
    +    struct stat a, b;
    
    466
    +    if (stat(in, &a) || stat(out, &b) || !S_ISDIR(b.st_mode))
    
    467
    +        die("invalid input/output directory");
    
    468
    +    if (a.st_dev == b.st_dev && a.st_ino == b.st_ino)
    
    469
    +        die("output directory must differ from input directory");
    
    470
    +    DIR *d = opendir(out);
    
    471
    +    if (!d) { perror(out); exit(1); }
    
    472
    +    struct dirent *e;
    
    473
    +    while ((e = readdir(d))) {
    
    474
    +        if (!strcmp(e->d_name, ".") || !strcmp(e->d_name, "..")) continue;
    
    475
    +        closedir(d);
    
    476
    +        die("output directory is not empty");
    
    477
    +    }
    
    478
    +    closedir(d);
    
    256 479
     }
    
    257
    -static void merge_dir(const char *dir, const char *output) {
    
    480
    +static void checked_close(FILE *f) {
    
    481
    +    if (fclose(f)) die("could not write report");
    
    482
    +}
    
    483
    +static void merge_dir(const char *dir, const char *dest) {
    
    484
    +    context = dir;
    
    258 485
         DIR *d = opendir(dir);
    
    259 486
         if (!d) { perror(dir); exit(1); }
    
    260 487
         char **paths = NULL;
    
    261 488
         size_t n = 0, cap = 0;
    
    262 489
         struct dirent *e;
    
    263
    -    struct stat outstat;
    
    264
    -    int output_exists = stat(output, &outstat) == 0;
    
    265 490
         while ((e = readdir(d))) {
    
    266 491
             if (!is_tix(e->d_name)) continue;
    
    267
    -        size_t dlen = strlen(dir), flen = strlen(e->d_name);
    
    268
    -        if (dlen > SIZE_MAX - flen - 2) die("path too long");
    
    269
    -        char *path = xmalloc(dlen + flen + 2);
    
    270
    -        snprintf(path, dlen + flen + 2, "%s/%s", dir, e->d_name);
    
    492
    +        char *path = join(dir, e->d_name);
    
    271 493
             struct stat st;
    
    272 494
             if (stat(path, &st) || !S_ISREG(st.st_mode)) { free(path); continue; }
    
    273
    -        if (!strcmp(path, output) ||
    
    274
    -            (output_exists && st.st_dev == outstat.st_dev && st.st_ino == outstat.st_ino))
    
    275
    -            die("output file is among input files");
    
    276 495
             if (n == cap) {
    
    277 496
                 if (cap > SIZE_MAX / (2 * sizeof(*paths))) die("too many input files");
    
    278
    -            cap = cap ? 2 * cap : 256;
    
    497
    +            cap = cap ? cap * 2 : 256;
    
    279 498
                 paths = xrealloc(paths, cap * sizeof(*paths));
    
    280 499
             }
    
    281 500
             paths[n++] = path;
    
    ... ... @@ -283,32 +502,104 @@ static void merge_dir(const char *dir, const char *output) {
    283 502
         closedir(d);
    
    284 503
         if (!n) die("no input .tix files");
    
    285 504
         qsort(paths, n, sizeof(*paths), cmpstr);
    
    286
    -    Acc a = {0};
    
    505
    +    ensure_empty_output_dir(dir, dest);
    
    506
    +
    
    507
    +    Group **groups = NULL;
    
    508
    +    size_t ng = 0, gcap = 0;
    
    509
    +    Assignment *assign = xcalloc(n, sizeof(*assign));
    
    287 510
         for (size_t i = 0; i < n; i++) {
    
    288
    -        mergeone(&a, paths[i]);
    
    289
    -        free(paths[i]);
    
    290
    -        if (a.filecount % 1000 == 0)
    
    291
    -            fprintf(stderr, "Merged %" PRIu64 " files\n", a.filecount);
    
    511
    +        Input in = inspect(paths[i]);
    
    512
    +        size_t best = SIZE_MAX;
    
    513
    +        Comparison bestc = {0};
    
    514
    +        for (size_t j = 0; j < ng; j++) {
    
    515
    +            Comparison c = compare(groups[j], &in);
    
    516
    +            if (c.conflicts || !c.shared) continue;
    
    517
    +            if (best == SIZE_MAX || better(&c, groups[j], &bestc, groups[best])) {
    
    518
    +                best = j;
    
    519
    +                bestc = c;
    
    520
    +            }
    
    521
    +        }
    
    522
    +        if (best == SIZE_MAX) {
    
    523
    +            if (ng == gcap) {
    
    524
    +                if (gcap > SIZE_MAX / (2 * sizeof(*groups))) die("too many groups");
    
    525
    +                gcap = gcap ? gcap * 2 : 8;
    
    526
    +                groups = xrealloc(groups, gcap * sizeof(*groups));
    
    527
    +            }
    
    528
    +            Group *g = xcalloc(1, sizeof(*g));
    
    529
    +            g->reason = reason_for_new_group(groups, ng, &in);
    
    530
    +            groups[ng] = g;
    
    531
    +            best = ng++;
    
    532
    +            fprintf(stderr, "New group %04zu from %s: %s\n",
    
    533
    +                    best + 1, paths[i], g->reason);
    
    534
    +        }
    
    535
    +        group_add(groups[best], &in, i, paths[i]);
    
    536
    +        assign[i] = (Assignment){best, bestc.shared, bestc.boxes};
    
    537
    +        input_free(&in);
    
    538
    +        if ((i + 1) % 1000 == 0)
    
    539
    +            fprintf(stderr, "Classified %zu/%zu inputs into %zu groups\n", i + 1, n, ng);
    
    292 540
         }
    
    293
    -    free(paths);
    
    294
    -    qsort(a.mods, a.len, sizeof(*a.mods), cmpmod);
    
    295
    -    Buffer out = serialise(&a);
    
    296
    -    context = output;
    
    297
    -    writefile(output, out.data, out.len);
    
    298
    -    fprintf(stderr, "Merged %" PRIu64 " files, %zu modules, %" PRIu64
    
    299
    -            " nonzero input counters; result %zu bytes\n",
    
    300
    -            a.filecount, a.len, a.input_entries, out.len);
    
    301
    -    free(out.data);
    
    302
    -    for (size_t i = 0; i < a.len; i++) {
    
    303
    -        free(a.mods[i]->ticks);
    
    304
    -        free(a.mods[i]->name);
    
    305
    -        free(a.mods[i]);
    
    541
    +
    
    542
    +    char *manifest_path = join(dest, "assignments.tsv");
    
    543
    +    FILE *manifest = fopen(manifest_path, "wb");
    
    544
    +    if (!manifest) { perror(manifest_path); exit(1); }
    
    545
    +    fprintf(manifest, "output\tinput\tshared_modules\tshared_boxes\n");
    
    546
    +    for (size_t i = 0; i < n; i++) {
    
    547
    +        char name[80];
    
    548
    +        output_name(name, sizeof(name), assign[i].group);
    
    549
    +        fprintf(manifest, "%s\t%s\t%zu\t%" PRIu64 "\n",
    
    550
    +                name, paths[i], assign[i].shared_modules, assign[i].shared_boxes);
    
    306 551
         }
    
    307
    -    free(a.mods);
    
    552
    +    checked_close(manifest);
    
    553
    +    free(manifest_path);
    
    554
    +
    
    555
    +    char *report_path = join(dest, "groups.txt");
    
    556
    +    FILE *report = fopen(report_path, "wb");
    
    557
    +    if (!report) { perror(report_path); exit(1); }
    
    558
    +    fprintf(report, "%zu input files -> %zu output groups\n", n, ng);
    
    559
    +    fprintf(report, "Assignments: largest shared box count, then module count, "
    
    560
    +                    "then existing file count; no incompatible modules permitted.\n\n");
    
    561
    +
    
    562
    +    for (size_t gi = 0; gi < ng; gi++) {
    
    563
    +        Group *g = groups[gi];
    
    564
    +        Acc *a = xcalloc(1, sizeof(*a));
    
    565
    +        for (size_t j = 0; j < g->len; j++) mergeone(a, paths[g->indices[j]]);
    
    566
    +        if (a->len != g->modules) die("grouping error: module count changed");
    
    567
    +        Buffer b = serialise(a);
    
    568
    +        char name[80];
    
    569
    +        output_name(name, sizeof(name), gi);
    
    570
    +        char *target = join(dest, name);
    
    571
    +        context = target;
    
    572
    +        writefile(target, b.data, b.len);
    
    573
    +        fprintf(stderr, "%s: %zu input files, %zu modules, %" PRIu64
    
    574
    +                        " nonzero input counters, %zu output bytes\n",
    
    575
    +                target, g->len, a->len, a->input_entries, b.len);
    
    576
    +        fprintf(report, "%s: %zu files, %zu modules, %zu bytes\n",
    
    577
    +                name, g->len, a->len, b.len);
    
    578
    +        fprintf(report, "  Started by: %s\n  Reason: %s\n",
    
    579
    +                paths[g->indices[0]], g->reason);
    
    580
    +        for (size_t j = 0; j < g->len; j++) {
    
    581
    +            size_t index = g->indices[j];
    
    582
    +            fprintf(report, "  %s [matched %zu modules, %" PRIu64 " boxes]\n",
    
    583
    +                    paths[index], assign[index].shared_modules, assign[index].shared_boxes);
    
    584
    +        }
    
    585
    +        fputc('\n', report);
    
    586
    +        free(target);
    
    587
    +        free(b.data);
    
    588
    +        acc_free(a);
    
    589
    +        free(a);
    
    590
    +    }
    
    591
    +    checked_close(report);
    
    592
    +    fprintf(stderr, "Done: %zu files -> %zu output groups; diagnostics: %s\n", n, ng, report_path);
    
    593
    +    free(report_path);
    
    594
    +    for (size_t i = 0; i < ng; i++) group_free(groups[i]);
    
    595
    +    free(groups);
    
    596
    +    free(assign);
    
    597
    +    for (size_t i = 0; i < n; i++) free(paths[i]);
    
    598
    +    free(paths);
    
    308 599
     }
    
    309 600
     int main(int argc, char **argv) {
    
    310 601
         if (argc != 3) {
    
    311
    -        fprintf(stderr, "Usage: %s RLE_DIRECTORY OUTPUT.tix\n", argv[0]);
    
    602
    +        fprintf(stderr, "Usage: %s INPUT_DIRECTORY EMPTY_OUTPUT_DIRECTORY\n", argv[0]);
    
    312 603
             return 2;
    
    313 604
         }
    
    314 605
         merge_dir(argv[1], argv[2]);