xonecas.io
7814
Ta

tiny-c-agent / files

tiny-c-agent / src / diff.c

18.2 KB
1// Working-tree snapshots and unified diffs.
2
3#include "diff.h"
4
5#include <dirent.h>
6#include <errno.h>
7#include <fcntl.h>
8#include <stdbool.h>
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12#include <sys/stat.h>
13#include <unistd.h>
14
15#include "util.h"
16
17#define MAX_FILE_BYTES (1u << 20)
18#define MAX_TOTAL_BYTES (32u << 20)
19#define BINARY_SNIFF 8192
20#define CONTEXT 3
21#define MAX_TRACE_BYTES (64u << 20)
22
23// ---- small helpers --------------------------------------------------------
24
25
26// ---- file states and cache ------------------------------------------------
27
28enum { FS_TEXT, FS_BINARY, FS_LARGE, FS_LINK, FS_UNTRACKED };
29
30typedef struct {
31    size_t size;
32    struct timespec mtime;
33    ino_t ino;
34    int kind;
35    char *content;  // NULL unless FS_TEXT
36    int refs;
37} file_state;
38
39// A captured file. `rel` and `abs` are owned.
40typedef struct {
41    char *rel;
42    char *abs;
43    size_t size;
44    struct timespec mtime;
45    ino_t ino;
46    bool link;
47} found;
48
49typedef struct {
50    found *items;
51    size_t len;
52    size_t cap;
53} found_list;
54
55static void found_add(found_list *l, char *rel, char *abs, const struct stat *st, bool link) {
56    if (l->len == l->cap) {
57        l->cap = l->cap ? l->cap * 2 : 64;
58        l->items = realloc(l->items, l->cap * sizeof *l->items);
59        if (!l->items) abort();
60    }
61    l->items[l->len++] = (found){
62        .rel = rel,
63        .abs = abs,
64        .size = (size_t)st->st_size,
65        .mtime = st->st_mtim,
66        .ino = st->st_ino,
67        .link = link,
68    };
69}
70
71static const char *const IGNORED_DIRS[] = {
72    ".git", ".hg", ".svn", "node_modules", ".venv", "venv",
73    "__pycache__", ".mypy_cache", ".pytest_cache",
74};
75
76static bool ignored_dir(const char *name) {
77    for (size_t i = 0; i < sizeof IGNORED_DIRS / sizeof *IGNORED_DIRS; i++)
78        if (strcmp(name, IGNORED_DIRS[i]) == 0) return true;
79    return false;
80}
81
82static void walk_dir(const char *dir, const char *relbase, found_list *out) {
83    DIR *d = opendir(dir);
84    if (!d) return;
85    struct dirent *de;
86    while ((de = readdir(d))) {
87        if (strcmp(de->d_name, ".") == 0 || strcmp(de->d_name, "..") == 0) continue;
88
89        size_t fl = strlen(dir) + strlen(de->d_name) + 2;
90        char *full = xmalloc(fl);
91        snprintf(full, fl, "%s/%s", dir, de->d_name);
92        size_t rl = strlen(relbase) + strlen(de->d_name) + 2;
93        char *rel = xmalloc(rl);
94        if (relbase[0]) snprintf(rel, rl, "%s/%s", relbase, de->d_name);
95        else snprintf(rel, rl, "%s", de->d_name);
96
97        struct stat st;
98        if (lstat(full, &st) == 0) {
99            if (S_ISDIR(st.st_mode)) {
100                if (!ignored_dir(de->d_name)) walk_dir(full, rel, out);
101            } else if (S_ISLNK(st.st_mode)) {
102                found_add(out, rel, full, &st, true);
103                rel = NULL;
104                full = NULL;
105            } else if (S_ISREG(st.st_mode)) {
106                found_add(out, rel, full, &st, false);
107                rel = NULL;
108                full = NULL;
109            }
110        }
111        free(rel);
112        free(full);
113    }
114    closedir(d);
115}
116
117static bool same_stat(const file_state *s, const found *f) {
118    return s->size == f->size && s->ino == f->ino &&
119           s->mtime.tv_sec == f->mtime.tv_sec && s->mtime.tv_nsec == f->mtime.tv_nsec;
120}
121
122static bool mtime_at_or_after(const found *f, const struct timespec *since) {
123    if (f->mtime.tv_sec != since->tv_sec) return f->mtime.tv_sec > since->tv_sec;
124    return f->mtime.tv_nsec >= since->tv_nsec;
125}
126
127static file_state *build_state(const found *f, bool over_budget) {
128    file_state *s = xcalloc(1, sizeof *s);
129    s->size = f->size;
130    s->mtime = f->mtime;
131    s->ino = f->ino;
132    if (f->link) {
133        s->kind = FS_LINK;
134        return s;
135    }
136    if (f->size > MAX_FILE_BYTES) {
137        s->kind = FS_LARGE;
138        return s;
139    }
140    if (over_budget) {
141        s->kind = FS_UNTRACKED;
142        return s;
143    }
144    int fd = open(f->abs, O_RDONLY);
145    if (fd < 0) {
146        s->kind = FS_UNTRACKED;
147        return s;
148    }
149    char *data = xmalloc(f->size + 1);
150    size_t off = 0;
151    while (off < f->size) {
152        ssize_t n = read(fd, data + off, f->size - off);
153        if (n < 0) {
154            if (errno == EINTR) continue;
155            break;
156        }
157        if (n == 0) break;
158        off += (size_t)n;
159    }
160    close(fd);
161    data[off] = '\0';
162    size_t sniff = off < BINARY_SNIFF ? off : BINARY_SNIFF;
163    for (size_t i = 0; i < sniff; i++) {
164        if (data[i] == '\0') {
165            free(data);
166            s->kind = FS_BINARY;
167            return s;
168        }
169    }
170    s->kind = FS_TEXT;
171    s->content = data;
172    s->size = off;
173    return s;
174}
175
176static void release(file_state *s) {
177    if (--s->refs > 0) return;
178    free(s->content);
179    free(s);
180}
181
182typedef struct {
183    char *path;
184    file_state *state;
185} cache_entry;
186
187static cache_entry *g_cache;
188static size_t g_cache_len;
189
190static int cmp_cache(const void *a, const void *b) {
191    const cache_entry *x = a, *y = b;
192    return strcmp(x->path, y->path);
193}
194
195// The cache is kept sorted by path so lookups stay logarithmic.
196static file_state *cache_find(const char *path) {
197    size_t lo = 0, hi = g_cache_len;
198    while (lo < hi) {
199        size_t mid = lo + (hi - lo) / 2;
200        int c = strcmp(path, g_cache[mid].path);
201        if (c == 0) return g_cache[mid].state;
202        if (c < 0) hi = mid;
203        else lo = mid + 1;
204    }
205    return NULL;
206}
207
208struct snapshot_entry {
209    char *path;
210    file_state *state;
211};
212
213struct tiny_snapshot {
214    struct snapshot_entry *entries;
215    size_t len;
216};
217
218static int cmp_entry(const void *a, const void *b) {
219    const struct snapshot_entry *x = a, *y = b;
220    return strcmp(x->path, y->path);
221}
222
223struct tiny_snapshot *tiny_snapshot_capture(const struct timespec *force_since) {
224    found_list files = {0};
225    char cwd[4096];
226    if (!getcwd(cwd, sizeof cwd)) strcpy(cwd, ".");
227    walk_dir(cwd, "", &files);
228
229    struct tiny_snapshot *snap = xcalloc(1, sizeof *snap);
230    snap->entries = xmalloc((files.len ? files.len : 1) * sizeof *snap->entries);
231    cache_entry *new_cache = xmalloc((files.len ? files.len : 1) * sizeof *new_cache);
232    size_t new_len = 0;
233    size_t total = 0;
234
235    for (size_t i = 0; i < files.len; i++) {
236        found *f = &files.items[i];
237        file_state *old = cache_find(f->rel);
238        bool forced = force_since && mtime_at_or_after(f, force_since);
239        bool reuse = old && !f->link && !forced && same_stat(old, f);
240        file_state *s = reuse ? old : build_state(f, total >= MAX_TOTAL_BYTES);
241
242        s->refs++;  // the new cache holds a reference
243        new_cache[new_len++] = (cache_entry){.path = xstrdup(f->rel), .state = s};
244        s->refs++;  // the snapshot holds a reference
245        snap->entries[snap->len++] = (struct snapshot_entry){.path = xstrdup(f->rel), .state = s};
246        if (s->kind == FS_TEXT) total += s->size;
247    }
248
249    for (size_t i = 0; i < g_cache_len; i++) {
250        release(g_cache[i].state);
251        free(g_cache[i].path);
252    }
253    free(g_cache);
254    qsort(new_cache, new_len, sizeof *new_cache, cmp_cache);
255    g_cache = new_cache;
256    g_cache_len = new_len;
257
258    for (size_t i = 0; i < files.len; i++) {
259        free(files.items[i].rel);
260        free(files.items[i].abs);
261    }
262    free(files.items);
263
264    qsort(snap->entries, snap->len, sizeof *snap->entries, cmp_entry);
265    return snap;
266}
267
268void tiny_snapshot_free(struct tiny_snapshot *s) {
269    if (!s) return;
270    for (size_t i = 0; i < s->len; i++) {
271        release(s->entries[i].state);
272        free(s->entries[i].path);
273    }
274    free(s->entries);
275    free(s);
276}
277
278// ---- unified diff ---------------------------------------------------------
279
280typedef struct {
281    const char *p;
282    size_t len;
283    bool nl;  // the line ended with a newline
284} line;
285
286static line *split_lines(const char *s, size_t n, size_t *count) {
287    size_t cap = 16, cnt = 0;
288    line *ls = xmalloc(cap * sizeof *ls);
289    size_t i = 0;
290    while (i < n) {
291        size_t start = i;
292        while (i < n && s[i] != '\n') i++;
293        ls[cnt].p = s + start;
294        ls[cnt].len = i - start;
295        ls[cnt].nl = i < n;
296        if (i < n) i++;
297        if (++cnt == cap) {
298            cap *= 2;
299            ls = realloc(ls, cap * sizeof *ls);
300            if (!ls) abort();
301        }
302    }
303    *count = cnt;
304    return ls;
305}
306
307static bool line_eq(const line *a, const line *b) {
308    return a->len == b->len && memcmp(a->p, b->p, a->len) == 0;
309}
310
311enum { OP_EQ, OP_DEL, OP_INS };
312
313typedef struct {
314    int kind;
315    line l;
316} op;
317
318// Myers O(ND) diff of two line arrays, producing an edit script in order.
319static op *myers(const line *a, size_t n, const line *b, size_t m, size_t *out_len) {
320    if (n == 0 && m == 0) {
321        *out_len = 0;
322        return NULL;
323    }
324    size_t cap = n + m;
325    op *ops = xmalloc((cap ? cap : 1) * sizeof *ops);
326    size_t cnt = 0;
327
328    if (n == 0) {
329        for (size_t i = 0; i < m; i++) ops[cnt++] = (op){OP_INS, b[i]};
330        *out_len = cnt;
331        return ops;
332    }
333    if (m == 0) {
334        for (size_t i = 0; i < n; i++) ops[cnt++] = (op){OP_DEL, a[i]};
335        *out_len = cnt;
336        return ops;
337    }
338
339    int max = (int)(n + m);
340    size_t vsize = (size_t)(2 * max + 3);
341    int offset = max + 1;
342    int *v = xcalloc(vsize, sizeof *v);
343    v[offset + 1] = 0;
344
345    int **trace = NULL;
346    size_t trace_len = 0, trace_cap = 0;
347    size_t trace_bytes = 0;
348    int found_d = -1;
349
350    for (int d = 0; d <= max; d++) {
351        if (trace_bytes + vsize * sizeof *v > MAX_TRACE_BYTES) break;
352        if (trace_len == trace_cap) {
353            trace_cap = trace_cap ? trace_cap * 2 : 16;
354            trace = realloc(trace, trace_cap * sizeof *trace);
355            if (!trace) abort();
356        }
357        int *snap = xmalloc(vsize * sizeof *snap);
358        memcpy(snap, v, vsize * sizeof *snap);
359        trace[trace_len++] = snap;
360        trace_bytes += vsize * sizeof *snap;
361
362        for (int k = -d; k <= d; k += 2) {
363            int x;
364            if (k == -d || (k != d && v[k - 1 + offset] < v[k + 1 + offset]))
365                x = v[k + 1 + offset];
366            else
367                x = v[k - 1 + offset] + 1;
368            int y = x - k;
369            while (x < (int)n && y < (int)m && line_eq(&a[x], &b[y])) {
370                x++;
371                y++;
372            }
373            v[k + offset] = x;
374            if (x >= (int)n && y >= (int)m) {
375                found_d = d;
376                break;
377            }
378        }
379        if (found_d >= 0) break;
380    }
381
382    if (found_d < 0) {
383        // Trace budget exceeded: fall back to a coarse replacement.
384        for (size_t i = 0; i < n; i++) ops[cnt++] = (op){OP_DEL, a[i]};
385        for (size_t i = 0; i < m; i++) ops[cnt++] = (op){OP_INS, b[i]};
386        for (size_t i = 0; i < trace_len; i++) free(trace[i]);
387        free(trace);
388        free(v);
389        *out_len = cnt;
390        return ops;
391    }
392
393    int x = (int)n, y = (int)m;
394    for (int d = found_d; d >= 0; d--) {
395        int *vt = trace[d];
396        int k = x - y;
397        int prev_k;
398        if (k == -d || (k != d && vt[k - 1 + offset] < vt[k + 1 + offset]))
399            prev_k = k + 1;
400        else
401            prev_k = k - 1;
402        int prev_x = vt[prev_k + offset];
403        int prev_y = prev_x - prev_k;
404        while (x > prev_x && y > prev_y) {
405            ops[cnt++] = (op){OP_EQ, a[x - 1]};
406            x--;
407            y--;
408        }
409        if (d > 0) {
410            if (x == prev_x) {
411                ops[cnt++] = (op){OP_INS, b[y - 1]};
412                y--;
413            } else {
414                ops[cnt++] = (op){OP_DEL, a[x - 1]};
415                x--;
416            }
417        }
418    }
419
420    for (size_t i = 0; i < trace_len; i++) free(trace[i]);
421    free(trace);
422    free(v);
423
424    for (size_t i = 0, j = cnt - 1; i < j; i++, j--) {
425        op tmp = ops[i];
426        ops[i] = ops[j];
427        ops[j] = tmp;
428    }
429    *out_len = cnt;
430    return ops;
431}
432
433static void add_range(char *dst, size_t cap, size_t start, size_t count) {
434    if (count == 0) snprintf(dst, cap, "%zu,0", start - 1);
435    else snprintf(dst, cap, "%zu,%zu", start, count);
436}
437
438char *tiny_unified_diff(const char *path, const char *a, size_t alen,
439                        const char *b, size_t blen) {
440    size_t na, nb;
441    line *la = split_lines(a, alen, &na);
442    line *lb = split_lines(b, blen, &nb);
443    size_t on;
444    op *ops = myers(la, na, lb, nb, &on);
445
446    size_t *opref = xmalloc((on + 1) * sizeof *opref);
447    size_t *npref = xmalloc((on + 1) * sizeof *npref);
448    opref[0] = npref[0] = 0;
449    for (size_t i = 0; i < on; i++) {
450        opref[i + 1] = opref[i] + (ops[i].kind == OP_EQ || ops[i].kind == OP_DEL);
451        npref[i + 1] = npref[i] + (ops[i].kind == OP_EQ || ops[i].kind == OP_INS);
452    }
453
454    tiny_buf out = {0};
455    buf_adds(&out, "Index: ");
456    buf_adds(&out, path);
457    buf_adds(&out, "\n===================================================================\n--- ");
458    buf_adds(&out, path);
459    buf_adds(&out, "\n+++ ");
460    buf_adds(&out, path);
461    buf_adds(&out, "\n");
462
463    size_t i = 0;
464    while (i < on) {
465        while (i < on && ops[i].kind == OP_EQ) i++;
466        if (i >= on) break;
467        size_t block_start = i;
468        size_t block_end = i;
469        while (block_end < on && ops[block_end].kind != OP_EQ) block_end++;
470        size_t last = block_end;
471        for (;;) {
472            size_t g = last;
473            while (g < on && ops[g].kind == OP_EQ) g++;
474            if (g >= on) break;
475            if (g - last > 2 * CONTEXT) break;
476            size_t b2 = g;
477            while (b2 < on && ops[b2].kind != OP_EQ) b2++;
478            last = b2;
479        }
480        size_t hs = block_start >= CONTEXT ? block_start - CONTEXT : 0;
481        size_t he = last + CONTEXT <= on ? last + CONTEXT : on;
482
483        char r1[32], r2[32], hdr[96];
484        add_range(r1, sizeof r1, opref[hs] + 1, opref[he] - opref[hs]);
485        add_range(r2, sizeof r2, npref[hs] + 1, npref[he] - npref[hs]);
486        snprintf(hdr, sizeof hdr, "@@ -%s +%s @@\n", r1, r2);
487        buf_adds(&out, hdr);
488
489        for (size_t k = hs; k < he; k++) {
490            char prefix = ops[k].kind == OP_DEL ? '-' : ops[k].kind == OP_INS ? '+' : ' ';
491            buf_add(&out, &prefix, 1);
492            buf_add(&out, ops[k].l.p, ops[k].l.len);
493            buf_adds(&out, "\n");
494            if (!ops[k].l.nl) buf_adds(&out, "\\ No newline at end of file\n");
495        }
496        i = he;
497    }
498
499    free(opref);
500    free(npref);
501    free(ops);
502    free(la);
503    free(lb);
504    return out.data;
505}
506
507// ---- diffs between snapshots ----------------------------------------------
508
509static const char *note_base(int kind) {
510    if (kind == FS_BINARY) return "binary file";
511    if (kind == FS_LARGE) return "large file";
512    return "file not tracked";
513}
514
515static char *note_text(int kind, const char *verb) {
516    const char *base = note_base(kind);
517    char *out = xmalloc(strlen(base) + strlen(verb) + 2);
518    sprintf(out, "%s %s", base, verb);
519    return out;
520}
521
522// Fills `*out` and returns true when the file changed; false means no change.
523static bool diff_one(const char *path, const file_state *before,
524                     const file_state *after, tiny_file_diff *out) {
525    out->path = xstrdup(path);
526    out->patch = NULL;
527    out->note = NULL;
528
529    if (before == NULL) {
530        if (after->kind == FS_LINK) {
531            out->note = xstrdup("symlink created");
532        } else if (after->content == NULL) {
533            out->note = note_text(after->kind, "created");
534        } else {
535            out->patch = tiny_unified_diff(path, "", 0, after->content, after->size);
536        }
537        return true;
538    }
539    if (after == NULL) {
540        if (before->kind == FS_LINK) {
541            out->note = xstrdup("symlink removed");
542        } else if (before->content == NULL) {
543            out->note = note_text(before->kind, "deleted");
544        } else {
545            out->patch = tiny_unified_diff(path, before->content, before->size, "", 0);
546        }
547        return true;
548    }
549    if (before->kind == FS_LINK || after->kind == FS_LINK) {
550        if (before->ino == after->ino && before->size == after->size &&
551            before->mtime.tv_sec == after->mtime.tv_sec &&
552            before->mtime.tv_nsec == after->mtime.tv_nsec)
553            return false;
554        out->note = xstrdup("symlink changed");
555        return true;
556    }
557    if (before->content != NULL && after->content != NULL) {
558        if (before->size == after->size && memcmp(before->content, after->content, before->size) == 0)
559            return false;
560        out->patch = tiny_unified_diff(path, before->content, before->size, after->content, after->size);
561        return true;
562    }
563    if (before->size == after->size && before->ino == after->ino &&
564        before->mtime.tv_sec == after->mtime.tv_sec && before->mtime.tv_nsec == after->mtime.tv_nsec)
565        return false;
566    int kind = after->content == NULL ? after->kind : before->kind;
567    out->note = note_text(kind, "changed");
568    return true;
569}
570
571tiny_file_diff *tiny_snapshot_diff(const struct tiny_snapshot *before,
572                                   const struct tiny_snapshot *after, size_t *len) {
573    tiny_file_diff *out = NULL;
574    size_t cap = 0, n = 0;
575    size_t i = 0, j = 0;
576    while (i < before->len || j < after->len) {
577        const char *path;
578        int cmp;
579        if (i >= before->len) cmp = 1;
580        else if (j >= after->len) cmp = -1;
581        else cmp = strcmp(before->entries[i].path, after->entries[j].path);
582
583        tiny_file_diff d;
584        bool changed;
585        if (cmp < 0) {
586            path = before->entries[i].path;
587            changed = diff_one(path, before->entries[i].state, NULL, &d);
588            i++;
589        } else if (cmp > 0) {
590            path = after->entries[j].path;
591            changed = diff_one(path, NULL, after->entries[j].state, &d);
592            j++;
593        } else {
594            path = before->entries[i].path;
595            changed = diff_one(path, before->entries[i].state, after->entries[j].state, &d);
596            i++;
597            j++;
598        }
599        if (!changed) {
600            free(d.path);
601            continue;
602        }
603        if (n == cap) {
604            cap = cap ? cap * 2 : 8;
605            out = realloc(out, cap * sizeof *out);
606            if (!out) abort();
607        }
608        out[n++] = d;
609    }
610    *len = n;
611    return out;
612}
613
614void tiny_file_diffs_free(tiny_file_diff *diffs, size_t len) {
615    if (!diffs) return;
616    for (size_t i = 0; i < len; i++) {
617        free(diffs[i].path);
618        free(diffs[i].patch);
619        free(diffs[i].note);
620    }
621    free(diffs);
622}