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}