THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1290 lines
32KB

  1. #include "git-compat-util.h"
  2. #include "line-range.h"
  3. #include "cache.h"
  4. #include "tag.h"
  5. #include "blob.h"
  6. #include "tree.h"
  7. #include "diff.h"
  8. #include "commit.h"
  9. #include "decorate.h"
  10. #include "revision.h"
  11. #include "xdiff-interface.h"
  12. #include "strbuf.h"
  13. #include "log-tree.h"
  14. #include "graph.h"
  15. #include "userdiff.h"
  16. #include "line-log.h"
  17. #include "argv-array.h"
  18. static void range_set_grow(struct range_set *rs, size_t extra)
  19. {
  20. ALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc);
  21. }
  22. /* Either initialization would be fine */
  23. #define RANGE_SET_INIT {0}
  24. void range_set_init(struct range_set *rs, size_t prealloc)
  25. {
  26. rs->alloc = rs->nr = 0;
  27. rs->ranges = NULL;
  28. if (prealloc)
  29. range_set_grow(rs, prealloc);
  30. }
  31. void range_set_release(struct range_set *rs)
  32. {
  33. FREE_AND_NULL(rs->ranges);
  34. rs->alloc = rs->nr = 0;
  35. }
  36. /* dst must be uninitialized! */
  37. static void range_set_copy(struct range_set *dst, struct range_set *src)
  38. {
  39. range_set_init(dst, src->nr);
  40. COPY_ARRAY(dst->ranges, src->ranges, src->nr);
  41. dst->nr = src->nr;
  42. }
  43. static void range_set_move(struct range_set *dst, struct range_set *src)
  44. {
  45. range_set_release(dst);
  46. dst->ranges = src->ranges;
  47. dst->nr = src->nr;
  48. dst->alloc = src->alloc;
  49. src->ranges = NULL;
  50. src->alloc = src->nr = 0;
  51. }
  52. /* tack on a _new_ range _at the end_ */
  53. void range_set_append_unsafe(struct range_set *rs, long a, long b)
  54. {
  55. assert(a <= b);
  56. range_set_grow(rs, 1);
  57. rs->ranges[rs->nr].start = a;
  58. rs->ranges[rs->nr].end = b;
  59. rs->nr++;
  60. }
  61. void range_set_append(struct range_set *rs, long a, long b)
  62. {
  63. assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
  64. range_set_append_unsafe(rs, a, b);
  65. }
  66. static int range_cmp(const void *_r, const void *_s)
  67. {
  68. const struct range *r = _r;
  69. const struct range *s = _s;
  70. /* this could be simply 'return r.start-s.start', but for the types */
  71. if (r->start == s->start)
  72. return 0;
  73. if (r->start < s->start)
  74. return -1;
  75. return 1;
  76. }
  77. /*
  78. * Check that the ranges are non-empty, sorted and non-overlapping
  79. */
  80. static void range_set_check_invariants(struct range_set *rs)
  81. {
  82. unsigned int i;
  83. if (!rs)
  84. return;
  85. if (rs->nr)
  86. assert(rs->ranges[0].start < rs->ranges[0].end);
  87. for (i = 1; i < rs->nr; i++) {
  88. assert(rs->ranges[i-1].end < rs->ranges[i].start);
  89. assert(rs->ranges[i].start < rs->ranges[i].end);
  90. }
  91. }
  92. /*
  93. * In-place pass of sorting and merging the ranges in the range set,
  94. * to establish the invariants when we get the ranges from the user
  95. */
  96. void sort_and_merge_range_set(struct range_set *rs)
  97. {
  98. unsigned int i;
  99. unsigned int o = 0; /* output cursor */
  100. QSORT(rs->ranges, rs->nr, range_cmp);
  101. for (i = 0; i < rs->nr; i++) {
  102. if (rs->ranges[i].start == rs->ranges[i].end)
  103. continue;
  104. if (o > 0 && rs->ranges[i].start <= rs->ranges[o-1].end) {
  105. if (rs->ranges[o-1].end < rs->ranges[i].end)
  106. rs->ranges[o-1].end = rs->ranges[i].end;
  107. } else {
  108. rs->ranges[o].start = rs->ranges[i].start;
  109. rs->ranges[o].end = rs->ranges[i].end;
  110. o++;
  111. }
  112. }
  113. assert(o <= rs->nr);
  114. rs->nr = o;
  115. range_set_check_invariants(rs);
  116. }
  117. /*
  118. * Union of range sets (i.e., sets of line numbers). Used to merge
  119. * them when searches meet at a common ancestor.
  120. *
  121. * This is also where the ranges are consolidated into canonical form:
  122. * overlapping and adjacent ranges are merged, and empty ranges are
  123. * removed.
  124. */
  125. static void range_set_union(struct range_set *out,
  126. struct range_set *a, struct range_set *b)
  127. {
  128. unsigned int i = 0, j = 0;
  129. struct range *ra = a->ranges;
  130. struct range *rb = b->ranges;
  131. /* cannot make an alias of out->ranges: it may change during grow */
  132. assert(out->nr == 0);
  133. while (i < a->nr || j < b->nr) {
  134. struct range *new_range;
  135. if (i < a->nr && j < b->nr) {
  136. if (ra[i].start < rb[j].start)
  137. new_range = &ra[i++];
  138. else if (ra[i].start > rb[j].start)
  139. new_range = &rb[j++];
  140. else if (ra[i].end < rb[j].end)
  141. new_range = &ra[i++];
  142. else
  143. new_range = &rb[j++];
  144. } else if (i < a->nr) /* b exhausted */
  145. new_range = &ra[i++];
  146. else /* a exhausted */
  147. new_range = &rb[j++];
  148. if (new_range->start == new_range->end)
  149. ; /* empty range */
  150. else if (!out->nr || out->ranges[out->nr-1].end < new_range->start) {
  151. range_set_grow(out, 1);
  152. out->ranges[out->nr].start = new_range->start;
  153. out->ranges[out->nr].end = new_range->end;
  154. out->nr++;
  155. } else if (out->ranges[out->nr-1].end < new_range->end) {
  156. out->ranges[out->nr-1].end = new_range->end;
  157. }
  158. }
  159. }
  160. /*
  161. * Difference of range sets (out = a \ b). Pass the "interesting"
  162. * ranges as 'a' and the target side of the diff as 'b': it removes
  163. * the ranges for which the commit is responsible.
  164. */
  165. static void range_set_difference(struct range_set *out,
  166. struct range_set *a, struct range_set *b)
  167. {
  168. unsigned int i, j = 0;
  169. for (i = 0; i < a->nr; i++) {
  170. long start = a->ranges[i].start;
  171. long end = a->ranges[i].end;
  172. while (start < end) {
  173. while (j < b->nr && start >= b->ranges[j].end)
  174. /*
  175. * a: |-------
  176. * b: ------|
  177. */
  178. j++;
  179. if (j >= b->nr || end < b->ranges[j].start) {
  180. /*
  181. * b exhausted, or
  182. * a: ----|
  183. * b: |----
  184. */
  185. range_set_append(out, start, end);
  186. break;
  187. }
  188. if (start >= b->ranges[j].start) {
  189. /*
  190. * a: |--????
  191. * b: |------|
  192. */
  193. start = b->ranges[j].end;
  194. } else if (end > b->ranges[j].start) {
  195. /*
  196. * a: |-----|
  197. * b: |--?????
  198. */
  199. if (start < b->ranges[j].start)
  200. range_set_append(out, start, b->ranges[j].start);
  201. start = b->ranges[j].end;
  202. }
  203. }
  204. }
  205. }
  206. static void diff_ranges_init(struct diff_ranges *diff)
  207. {
  208. range_set_init(&diff->parent, 0);
  209. range_set_init(&diff->target, 0);
  210. }
  211. static void diff_ranges_release(struct diff_ranges *diff)
  212. {
  213. range_set_release(&diff->parent);
  214. range_set_release(&diff->target);
  215. }
  216. static void line_log_data_init(struct line_log_data *r)
  217. {
  218. memset(r, 0, sizeof(struct line_log_data));
  219. range_set_init(&r->ranges, 0);
  220. }
  221. static void line_log_data_clear(struct line_log_data *r)
  222. {
  223. range_set_release(&r->ranges);
  224. if (r->pair)
  225. diff_free_filepair(r->pair);
  226. }
  227. static void free_line_log_data(struct line_log_data *r)
  228. {
  229. while (r) {
  230. struct line_log_data *next = r->next;
  231. line_log_data_clear(r);
  232. free(r);
  233. r = next;
  234. }
  235. }
  236. static struct line_log_data *
  237. search_line_log_data(struct line_log_data *list, const char *path,
  238. struct line_log_data **insertion_point)
  239. {
  240. struct line_log_data *p = list;
  241. if (insertion_point)
  242. *insertion_point = NULL;
  243. while (p) {
  244. int cmp = strcmp(p->path, path);
  245. if (!cmp)
  246. return p;
  247. if (insertion_point && cmp < 0)
  248. *insertion_point = p;
  249. p = p->next;
  250. }
  251. return NULL;
  252. }
  253. /*
  254. * Note: takes ownership of 'path', which happens to be what the only
  255. * caller needs.
  256. */
  257. static void line_log_data_insert(struct line_log_data **list,
  258. char *path,
  259. long begin, long end)
  260. {
  261. struct line_log_data *ip;
  262. struct line_log_data *p = search_line_log_data(*list, path, &ip);
  263. if (p) {
  264. range_set_append_unsafe(&p->ranges, begin, end);
  265. free(path);
  266. return;
  267. }
  268. p = xcalloc(1, sizeof(struct line_log_data));
  269. p->path = path;
  270. range_set_append(&p->ranges, begin, end);
  271. if (ip) {
  272. p->next = ip->next;
  273. ip->next = p;
  274. } else {
  275. p->next = *list;
  276. *list = p;
  277. }
  278. }
  279. struct collect_diff_cbdata {
  280. struct diff_ranges *diff;
  281. };
  282. static int collect_diff_cb(long start_a, long count_a,
  283. long start_b, long count_b,
  284. void *data)
  285. {
  286. struct collect_diff_cbdata *d = data;
  287. if (count_a >= 0)
  288. range_set_append(&d->diff->parent, start_a, start_a + count_a);
  289. if (count_b >= 0)
  290. range_set_append(&d->diff->target, start_b, start_b + count_b);
  291. return 0;
  292. }
  293. static int collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out)
  294. {
  295. struct collect_diff_cbdata cbdata = {NULL};
  296. xpparam_t xpp;
  297. xdemitconf_t xecfg;
  298. xdemitcb_t ecb;
  299. memset(&xpp, 0, sizeof(xpp));
  300. memset(&xecfg, 0, sizeof(xecfg));
  301. xecfg.ctxlen = xecfg.interhunkctxlen = 0;
  302. cbdata.diff = out;
  303. xecfg.hunk_func = collect_diff_cb;
  304. memset(&ecb, 0, sizeof(ecb));
  305. ecb.priv = &cbdata;
  306. return xdi_diff(parent, target, &xpp, &xecfg, &ecb);
  307. }
  308. /*
  309. * These are handy for debugging. Removing them with #if 0 silences
  310. * the "unused function" warning.
  311. */
  312. #if 0
  313. static void dump_range_set(struct range_set *rs, const char *desc)
  314. {
  315. int i;
  316. printf("range set %s (%d items):\n", desc, rs->nr);
  317. for (i = 0; i < rs->nr; i++)
  318. printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end);
  319. }
  320. static void dump_line_log_data(struct line_log_data *r)
  321. {
  322. char buf[4096];
  323. while (r) {
  324. snprintf(buf, 4096, "file %s\n", r->path);
  325. dump_range_set(&r->ranges, buf);
  326. r = r->next;
  327. }
  328. }
  329. static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
  330. {
  331. int i;
  332. assert(diff->parent.nr == diff->target.nr);
  333. printf("diff ranges %s (%d items):\n", desc, diff->parent.nr);
  334. printf("\tparent\ttarget\n");
  335. for (i = 0; i < diff->parent.nr; i++) {
  336. printf("\t[%ld,%ld]\t[%ld,%ld]\n",
  337. diff->parent.ranges[i].start,
  338. diff->parent.ranges[i].end,
  339. diff->target.ranges[i].start,
  340. diff->target.ranges[i].end);
  341. }
  342. }
  343. #endif
  344. static int ranges_overlap(struct range *a, struct range *b)
  345. {
  346. return !(a->end <= b->start || b->end <= a->start);
  347. }
  348. /*
  349. * Given a diff and the set of interesting ranges, determine all hunks
  350. * of the diff which touch (overlap) at least one of the interesting
  351. * ranges in the target.
  352. */
  353. static void diff_ranges_filter_touched(struct diff_ranges *out,
  354. struct diff_ranges *diff,
  355. struct range_set *rs)
  356. {
  357. unsigned int i, j = 0;
  358. assert(out->target.nr == 0);
  359. for (i = 0; i < diff->target.nr; i++) {
  360. while (diff->target.ranges[i].start > rs->ranges[j].end) {
  361. j++;
  362. if (j == rs->nr)
  363. return;
  364. }
  365. if (ranges_overlap(&diff->target.ranges[i], &rs->ranges[j])) {
  366. range_set_append(&out->parent,
  367. diff->parent.ranges[i].start,
  368. diff->parent.ranges[i].end);
  369. range_set_append(&out->target,
  370. diff->target.ranges[i].start,
  371. diff->target.ranges[i].end);
  372. }
  373. }
  374. }
  375. /*
  376. * Adjust the line counts in 'rs' to account for the lines
  377. * added/removed in the diff.
  378. */
  379. static void range_set_shift_diff(struct range_set *out,
  380. struct range_set *rs,
  381. struct diff_ranges *diff)
  382. {
  383. unsigned int i, j = 0;
  384. long offset = 0;
  385. struct range *src = rs->ranges;
  386. struct range *target = diff->target.ranges;
  387. struct range *parent = diff->parent.ranges;
  388. for (i = 0; i < rs->nr; i++) {
  389. while (j < diff->target.nr && src[i].start >= target[j].start) {
  390. offset += (parent[j].end-parent[j].start)
  391. - (target[j].end-target[j].start);
  392. j++;
  393. }
  394. range_set_append(out, src[i].start+offset, src[i].end+offset);
  395. }
  396. }
  397. /*
  398. * Given a diff and the set of interesting ranges, map the ranges
  399. * across the diff. That is: observe that the target commit takes
  400. * blame for all the + (target-side) ranges. So for every pair of
  401. * ranges in the diff that was touched, we remove the latter and add
  402. * its parent side.
  403. */
  404. static void range_set_map_across_diff(struct range_set *out,
  405. struct range_set *rs,
  406. struct diff_ranges *diff,
  407. struct diff_ranges **touched_out)
  408. {
  409. struct diff_ranges *touched = xmalloc(sizeof(*touched));
  410. struct range_set tmp1 = RANGE_SET_INIT;
  411. struct range_set tmp2 = RANGE_SET_INIT;
  412. diff_ranges_init(touched);
  413. diff_ranges_filter_touched(touched, diff, rs);
  414. range_set_difference(&tmp1, rs, &touched->target);
  415. range_set_shift_diff(&tmp2, &tmp1, diff);
  416. range_set_union(out, &tmp2, &touched->parent);
  417. range_set_release(&tmp1);
  418. range_set_release(&tmp2);
  419. *touched_out = touched;
  420. }
  421. static struct commit *check_single_commit(struct rev_info *revs)
  422. {
  423. struct object *commit = NULL;
  424. int found = -1;
  425. int i;
  426. for (i = 0; i < revs->pending.nr; i++) {
  427. struct object *obj = revs->pending.objects[i].item;
  428. if (obj->flags & UNINTERESTING)
  429. continue;
  430. obj = deref_tag(revs->repo, obj, NULL, 0);
  431. if (obj->type != OBJ_COMMIT)
  432. die("Non commit %s?", revs->pending.objects[i].name);
  433. if (commit)
  434. die("More than one commit to dig from: %s and %s?",
  435. revs->pending.objects[i].name,
  436. revs->pending.objects[found].name);
  437. commit = obj;
  438. found = i;
  439. }
  440. if (!commit)
  441. die("No commit specified?");
  442. return (struct commit *) commit;
  443. }
  444. static void fill_blob_sha1(struct repository *r, struct commit *commit,
  445. struct diff_filespec *spec)
  446. {
  447. unsigned short mode;
  448. struct object_id oid;
  449. if (get_tree_entry(r, &commit->object.oid, spec->path, &oid, &mode))
  450. die("There is no path %s in the commit", spec->path);
  451. fill_filespec(spec, &oid, 1, mode);
  452. return;
  453. }
  454. static void fill_line_ends(struct repository *r,
  455. struct diff_filespec *spec,
  456. long *lines,
  457. unsigned long **line_ends)
  458. {
  459. int num = 0, size = 50;
  460. long cur = 0;
  461. unsigned long *ends = NULL;
  462. char *data = NULL;
  463. if (diff_populate_filespec(r, spec, 0))
  464. die("Cannot read blob %s", oid_to_hex(&spec->oid));
  465. ALLOC_ARRAY(ends, size);
  466. ends[cur++] = 0;
  467. data = spec->data;
  468. while (num < spec->size) {
  469. if (data[num] == '\n' || num == spec->size - 1) {
  470. ALLOC_GROW(ends, (cur + 1), size);
  471. ends[cur++] = num;
  472. }
  473. num++;
  474. }
  475. /* shrink the array to fit the elements */
  476. REALLOC_ARRAY(ends, cur);
  477. *lines = cur-1;
  478. *line_ends = ends;
  479. }
  480. struct nth_line_cb {
  481. struct diff_filespec *spec;
  482. long lines;
  483. unsigned long *line_ends;
  484. };
  485. static const char *nth_line(void *data, long line)
  486. {
  487. struct nth_line_cb *d = data;
  488. assert(d && line <= d->lines);
  489. assert(d->spec && d->spec->data);
  490. if (line == 0)
  491. return (char *)d->spec->data;
  492. else
  493. return (char *)d->spec->data + d->line_ends[line] + 1;
  494. }
  495. static struct line_log_data *
  496. parse_lines(struct repository *r, struct commit *commit,
  497. const char *prefix, struct string_list *args)
  498. {
  499. long lines = 0;
  500. unsigned long *ends = NULL;
  501. struct nth_line_cb cb_data;
  502. struct string_list_item *item;
  503. struct line_log_data *ranges = NULL;
  504. struct line_log_data *p;
  505. for_each_string_list_item(item, args) {
  506. const char *name_part, *range_part;
  507. char *full_name;
  508. struct diff_filespec *spec;
  509. long begin = 0, end = 0;
  510. long anchor;
  511. name_part = skip_range_arg(item->string, r->index);
  512. if (!name_part || *name_part != ':' || !name_part[1])
  513. die("-L argument not 'start,end:file' or ':funcname:file': %s",
  514. item->string);
  515. range_part = xstrndup(item->string, name_part - item->string);
  516. name_part++;
  517. full_name = prefix_path(prefix, prefix ? strlen(prefix) : 0,
  518. name_part);
  519. spec = alloc_filespec(full_name);
  520. fill_blob_sha1(r, commit, spec);
  521. fill_line_ends(r, spec, &lines, &ends);
  522. cb_data.spec = spec;
  523. cb_data.lines = lines;
  524. cb_data.line_ends = ends;
  525. p = search_line_log_data(ranges, full_name, NULL);
  526. if (p && p->ranges.nr)
  527. anchor = p->ranges.ranges[p->ranges.nr - 1].end + 1;
  528. else
  529. anchor = 1;
  530. if (parse_range_arg(range_part, nth_line, &cb_data,
  531. lines, anchor, &begin, &end,
  532. full_name, r->index))
  533. die("malformed -L argument '%s'", range_part);
  534. if ((!lines && (begin || end)) || lines < begin)
  535. die("file %s has only %lu lines", name_part, lines);
  536. if (begin < 1)
  537. begin = 1;
  538. if (end < 1 || lines < end)
  539. end = lines;
  540. begin--;
  541. line_log_data_insert(&ranges, full_name, begin, end);
  542. free_filespec(spec);
  543. FREE_AND_NULL(ends);
  544. }
  545. for (p = ranges; p; p = p->next)
  546. sort_and_merge_range_set(&p->ranges);
  547. return ranges;
  548. }
  549. static struct line_log_data *line_log_data_copy_one(struct line_log_data *r)
  550. {
  551. struct line_log_data *ret = xmalloc(sizeof(*ret));
  552. assert(r);
  553. line_log_data_init(ret);
  554. range_set_copy(&ret->ranges, &r->ranges);
  555. ret->path = xstrdup(r->path);
  556. return ret;
  557. }
  558. static struct line_log_data *
  559. line_log_data_copy(struct line_log_data *r)
  560. {
  561. struct line_log_data *ret = NULL;
  562. struct line_log_data *tmp = NULL, *prev = NULL;
  563. assert(r);
  564. ret = tmp = prev = line_log_data_copy_one(r);
  565. r = r->next;
  566. while (r) {
  567. tmp = line_log_data_copy_one(r);
  568. prev->next = tmp;
  569. prev = tmp;
  570. r = r->next;
  571. }
  572. return ret;
  573. }
  574. /* merge two range sets across files */
  575. static struct line_log_data *line_log_data_merge(struct line_log_data *a,
  576. struct line_log_data *b)
  577. {
  578. struct line_log_data *head = NULL, **pp = &head;
  579. while (a || b) {
  580. struct line_log_data *src;
  581. struct line_log_data *src2 = NULL;
  582. struct line_log_data *d;
  583. int cmp;
  584. if (!a)
  585. cmp = 1;
  586. else if (!b)
  587. cmp = -1;
  588. else
  589. cmp = strcmp(a->path, b->path);
  590. if (cmp < 0) {
  591. src = a;
  592. a = a->next;
  593. } else if (cmp == 0) {
  594. src = a;
  595. a = a->next;
  596. src2 = b;
  597. b = b->next;
  598. } else {
  599. src = b;
  600. b = b->next;
  601. }
  602. d = xmalloc(sizeof(struct line_log_data));
  603. line_log_data_init(d);
  604. d->path = xstrdup(src->path);
  605. *pp = d;
  606. pp = &d->next;
  607. if (src2)
  608. range_set_union(&d->ranges, &src->ranges, &src2->ranges);
  609. else
  610. range_set_copy(&d->ranges, &src->ranges);
  611. }
  612. return head;
  613. }
  614. static void add_line_range(struct rev_info *revs, struct commit *commit,
  615. struct line_log_data *range)
  616. {
  617. struct line_log_data *old_line = NULL;
  618. struct line_log_data *new_line = NULL;
  619. old_line = lookup_decoration(&revs->line_log_data, &commit->object);
  620. if (old_line && range) {
  621. new_line = line_log_data_merge(old_line, range);
  622. free_line_log_data(old_line);
  623. } else if (range)
  624. new_line = line_log_data_copy(range);
  625. if (new_line)
  626. add_decoration(&revs->line_log_data, &commit->object, new_line);
  627. }
  628. static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)
  629. {
  630. struct line_log_data *r;
  631. r = lookup_decoration(&revs->line_log_data, &commit->object);
  632. if (!r)
  633. return;
  634. free_line_log_data(r);
  635. add_decoration(&revs->line_log_data, &commit->object, NULL);
  636. }
  637. static struct line_log_data *lookup_line_range(struct rev_info *revs,
  638. struct commit *commit)
  639. {
  640. struct line_log_data *ret = NULL;
  641. struct line_log_data *d;
  642. ret = lookup_decoration(&revs->line_log_data, &commit->object);
  643. for (d = ret; d; d = d->next)
  644. range_set_check_invariants(&d->ranges);
  645. return ret;
  646. }
  647. static int same_paths_in_pathspec_and_range(struct pathspec *pathspec,
  648. struct line_log_data *range)
  649. {
  650. int i;
  651. struct line_log_data *r;
  652. for (i = 0, r = range; i < pathspec->nr && r; i++, r = r->next)
  653. if (strcmp(pathspec->items[i].match, r->path))
  654. return 0;
  655. if (i < pathspec->nr || r)
  656. /* different number of pathspec items and ranges */
  657. return 0;
  658. return 1;
  659. }
  660. static void parse_pathspec_from_ranges(struct pathspec *pathspec,
  661. struct line_log_data *range)
  662. {
  663. struct line_log_data *r;
  664. struct argv_array array = ARGV_ARRAY_INIT;
  665. const char **paths;
  666. for (r = range; r; r = r->next)
  667. argv_array_push(&array, r->path);
  668. paths = argv_array_detach(&array);
  669. parse_pathspec(pathspec, 0, PATHSPEC_PREFER_FULL, "", paths);
  670. /* strings are now owned by pathspec */
  671. free(paths);
  672. }
  673. void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)
  674. {
  675. struct commit *commit = NULL;
  676. struct line_log_data *range;
  677. commit = check_single_commit(rev);
  678. range = parse_lines(rev->diffopt.repo, commit, prefix, args);
  679. add_line_range(rev, commit, range);
  680. parse_pathspec_from_ranges(&rev->diffopt.pathspec, range);
  681. }
  682. static void move_diff_queue(struct diff_queue_struct *dst,
  683. struct diff_queue_struct *src)
  684. {
  685. assert(src != dst);
  686. memcpy(dst, src, sizeof(struct diff_queue_struct));
  687. DIFF_QUEUE_CLEAR(src);
  688. }
  689. static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)
  690. {
  691. int i;
  692. struct diff_queue_struct outq;
  693. DIFF_QUEUE_CLEAR(&outq);
  694. for (i = 0; i < diff_queued_diff.nr; i++) {
  695. struct diff_filepair *p = diff_queued_diff.queue[i];
  696. struct line_log_data *rg = NULL;
  697. if (!DIFF_FILE_VALID(p->two)) {
  698. if (keep_deletions)
  699. diff_q(&outq, p);
  700. else
  701. diff_free_filepair(p);
  702. continue;
  703. }
  704. for (rg = range; rg; rg = rg->next) {
  705. if (!strcmp(rg->path, p->two->path))
  706. break;
  707. }
  708. if (rg)
  709. diff_q(&outq, p);
  710. else
  711. diff_free_filepair(p);
  712. }
  713. free(diff_queued_diff.queue);
  714. diff_queued_diff = outq;
  715. }
  716. static inline int diff_might_be_rename(void)
  717. {
  718. int i;
  719. for (i = 0; i < diff_queued_diff.nr; i++)
  720. if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {
  721. /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
  722. /* diff_queued_diff.queue[i]->two->path); */
  723. return 1;
  724. }
  725. return 0;
  726. }
  727. static void queue_diffs(struct line_log_data *range,
  728. struct diff_options *opt,
  729. struct diff_queue_struct *queue,
  730. struct commit *commit, struct commit *parent)
  731. {
  732. struct object_id *tree_oid, *parent_tree_oid;
  733. assert(commit);
  734. tree_oid = get_commit_tree_oid(commit);
  735. parent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;
  736. if (opt->detect_rename &&
  737. !same_paths_in_pathspec_and_range(&opt->pathspec, range)) {
  738. clear_pathspec(&opt->pathspec);
  739. parse_pathspec_from_ranges(&opt->pathspec, range);
  740. }
  741. DIFF_QUEUE_CLEAR(&diff_queued_diff);
  742. diff_tree_oid(parent_tree_oid, tree_oid, "", opt);
  743. if (opt->detect_rename && diff_might_be_rename()) {
  744. /* must look at the full tree diff to detect renames */
  745. clear_pathspec(&opt->pathspec);
  746. DIFF_QUEUE_CLEAR(&diff_queued_diff);
  747. diff_tree_oid(parent_tree_oid, tree_oid, "", opt);
  748. filter_diffs_for_paths(range, 1);
  749. diffcore_std(opt);
  750. filter_diffs_for_paths(range, 0);
  751. }
  752. move_diff_queue(queue, &diff_queued_diff);
  753. }
  754. static char *get_nth_line(long line, unsigned long *ends, void *data)
  755. {
  756. if (line == 0)
  757. return (char *)data;
  758. else
  759. return (char *)data + ends[line] + 1;
  760. }
  761. static void print_line(const char *prefix, char first,
  762. long line, unsigned long *ends, void *data,
  763. const char *color, const char *reset, FILE *file)
  764. {
  765. char *begin = get_nth_line(line, ends, data);
  766. char *end = get_nth_line(line+1, ends, data);
  767. int had_nl = 0;
  768. if (end > begin && end[-1] == '\n') {
  769. end--;
  770. had_nl = 1;
  771. }
  772. fputs(prefix, file);
  773. fputs(color, file);
  774. putc(first, file);
  775. fwrite(begin, 1, end-begin, file);
  776. fputs(reset, file);
  777. putc('\n', file);
  778. if (!had_nl)
  779. fputs("\\ No newline at end of file\n", file);
  780. }
  781. static char *output_prefix(struct diff_options *opt)
  782. {
  783. char *prefix = "";
  784. if (opt->output_prefix) {
  785. struct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);
  786. prefix = sb->buf;
  787. }
  788. return prefix;
  789. }
  790. static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)
  791. {
  792. unsigned int i, j = 0;
  793. long p_lines, t_lines;
  794. unsigned long *p_ends = NULL, *t_ends = NULL;
  795. struct diff_filepair *pair = range->pair;
  796. struct diff_ranges *diff = &range->diff;
  797. struct diff_options *opt = &rev->diffopt;
  798. char *prefix = output_prefix(opt);
  799. const char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);
  800. const char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);
  801. const char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);
  802. const char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);
  803. const char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);
  804. const char *c_context = diff_get_color(opt->use_color, DIFF_CONTEXT);
  805. if (!pair || !diff)
  806. return;
  807. if (pair->one->oid_valid)
  808. fill_line_ends(rev->diffopt.repo, pair->one, &p_lines, &p_ends);
  809. fill_line_ends(rev->diffopt.repo, pair->two, &t_lines, &t_ends);
  810. fprintf(opt->file, "%s%sdiff --git a/%s b/%s%s\n", prefix, c_meta, pair->one->path, pair->two->path, c_reset);
  811. fprintf(opt->file, "%s%s--- %s%s%s\n", prefix, c_meta,
  812. pair->one->oid_valid ? "a/" : "",
  813. pair->one->oid_valid ? pair->one->path : "/dev/null",
  814. c_reset);
  815. fprintf(opt->file, "%s%s+++ b/%s%s\n", prefix, c_meta, pair->two->path, c_reset);
  816. for (i = 0; i < range->ranges.nr; i++) {
  817. long p_start, p_end;
  818. long t_start = range->ranges.ranges[i].start;
  819. long t_end = range->ranges.ranges[i].end;
  820. long t_cur = t_start;
  821. unsigned int j_last;
  822. while (j < diff->target.nr && diff->target.ranges[j].end < t_start)
  823. j++;
  824. if (j == diff->target.nr || diff->target.ranges[j].start > t_end)
  825. continue;
  826. /* Scan ahead to determine the last diff that falls in this range */
  827. j_last = j;
  828. while (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)
  829. j_last++;
  830. if (j_last > j)
  831. j_last--;
  832. /*
  833. * Compute parent hunk headers: we know that the diff
  834. * has the correct line numbers (but not all hunks).
  835. * So it suffices to shift the start/end according to
  836. * the line numbers of the first/last hunk(s) that
  837. * fall in this range.
  838. */
  839. if (t_start < diff->target.ranges[j].start)
  840. p_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);
  841. else
  842. p_start = diff->parent.ranges[j].start;
  843. if (t_end > diff->target.ranges[j_last].end)
  844. p_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);
  845. else
  846. p_end = diff->parent.ranges[j_last].end;
  847. if (!p_start && !p_end) {
  848. p_start = -1;
  849. p_end = -1;
  850. }
  851. /* Now output a diff hunk for this range */
  852. fprintf(opt->file, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
  853. prefix, c_frag,
  854. p_start+1, p_end-p_start, t_start+1, t_end-t_start,
  855. c_reset);
  856. while (j < diff->target.nr && diff->target.ranges[j].start < t_end) {
  857. int k;
  858. for (; t_cur < diff->target.ranges[j].start; t_cur++)
  859. print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
  860. c_context, c_reset, opt->file);
  861. for (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)
  862. print_line(prefix, '-', k, p_ends, pair->one->data,
  863. c_old, c_reset, opt->file);
  864. for (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)
  865. print_line(prefix, '+', t_cur, t_ends, pair->two->data,
  866. c_new, c_reset, opt->file);
  867. j++;
  868. }
  869. for (; t_cur < t_end; t_cur++)
  870. print_line(prefix, ' ', t_cur, t_ends, pair->two->data,
  871. c_context, c_reset, opt->file);
  872. }
  873. free(p_ends);
  874. free(t_ends);
  875. }
  876. /*
  877. * NEEDSWORK: manually building a diff here is not the Right
  878. * Thing(tm). log -L should be built into the diff pipeline.
  879. */
  880. static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)
  881. {
  882. fprintf(rev->diffopt.file, "%s\n", output_prefix(&rev->diffopt));
  883. while (range) {
  884. dump_diff_hacky_one(rev, range);
  885. range = range->next;
  886. }
  887. }
  888. /*
  889. * Unlike most other functions, this destructively operates on
  890. * 'range'.
  891. */
  892. static int process_diff_filepair(struct rev_info *rev,
  893. struct diff_filepair *pair,
  894. struct line_log_data *range,
  895. struct diff_ranges **diff_out)
  896. {
  897. struct line_log_data *rg = range;
  898. struct range_set tmp;
  899. struct diff_ranges diff;
  900. mmfile_t file_parent, file_target;
  901. assert(pair->two->path);
  902. while (rg) {
  903. assert(rg->path);
  904. if (!strcmp(rg->path, pair->two->path))
  905. break;
  906. rg = rg->next;
  907. }
  908. if (!rg)
  909. return 0;
  910. if (rg->ranges.nr == 0)
  911. return 0;
  912. assert(pair->two->oid_valid);
  913. diff_populate_filespec(rev->diffopt.repo, pair->two, 0);
  914. file_target.ptr = pair->two->data;
  915. file_target.size = pair->two->size;
  916. if (pair->one->oid_valid) {
  917. diff_populate_filespec(rev->diffopt.repo, pair->one, 0);
  918. file_parent.ptr = pair->one->data;
  919. file_parent.size = pair->one->size;
  920. } else {
  921. file_parent.ptr = "";
  922. file_parent.size = 0;
  923. }
  924. diff_ranges_init(&diff);
  925. if (collect_diff(&file_parent, &file_target, &diff))
  926. die("unable to generate diff for %s", pair->one->path);
  927. /* NEEDSWORK should apply some heuristics to prevent mismatches */
  928. free(rg->path);
  929. rg->path = xstrdup(pair->one->path);
  930. range_set_init(&tmp, 0);
  931. range_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);
  932. range_set_release(&rg->ranges);
  933. range_set_move(&rg->ranges, &tmp);
  934. diff_ranges_release(&diff);
  935. return ((*diff_out)->parent.nr > 0);
  936. }
  937. static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)
  938. {
  939. struct diff_filepair *new_filepair = xmalloc(sizeof(struct diff_filepair));
  940. new_filepair->one = pair->one;
  941. new_filepair->two = pair->two;
  942. new_filepair->one->count++;
  943. new_filepair->two->count++;
  944. return new_filepair;
  945. }
  946. static void free_diffqueues(int n, struct diff_queue_struct *dq)
  947. {
  948. int i, j;
  949. for (i = 0; i < n; i++)
  950. for (j = 0; j < dq[i].nr; j++)
  951. diff_free_filepair(dq[i].queue[j]);
  952. free(dq);
  953. }
  954. static int process_all_files(struct line_log_data **range_out,
  955. struct rev_info *rev,
  956. struct diff_queue_struct *queue,
  957. struct line_log_data *range)
  958. {
  959. int i, changed = 0;
  960. *range_out = line_log_data_copy(range);
  961. for (i = 0; i < queue->nr; i++) {
  962. struct diff_ranges *pairdiff = NULL;
  963. struct diff_filepair *pair = queue->queue[i];
  964. if (process_diff_filepair(rev, pair, *range_out, &pairdiff)) {
  965. /*
  966. * Store away the diff for later output. We
  967. * tuck it in the ranges we got as _input_,
  968. * since that's the commit that caused the
  969. * diff.
  970. *
  971. * NEEDSWORK not enough when we get around to
  972. * doing something interesting with merges;
  973. * currently each invocation on a merge parent
  974. * trashes the previous one's diff.
  975. *
  976. * NEEDSWORK tramples over data structures not owned here
  977. */
  978. struct line_log_data *rg = range;
  979. changed++;
  980. while (rg && strcmp(rg->path, pair->two->path))
  981. rg = rg->next;
  982. assert(rg);
  983. rg->pair = diff_filepair_dup(queue->queue[i]);
  984. memcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));
  985. }
  986. free(pairdiff);
  987. }
  988. return changed;
  989. }
  990. int line_log_print(struct rev_info *rev, struct commit *commit)
  991. {
  992. show_log(rev);
  993. if (!(rev->diffopt.output_format & DIFF_FORMAT_NO_OUTPUT)) {
  994. struct line_log_data *range = lookup_line_range(rev, commit);
  995. dump_diff_hacky(rev, range);
  996. }
  997. return 1;
  998. }
  999. static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,
  1000. struct line_log_data *range)
  1001. {
  1002. struct commit *parent = NULL;
  1003. struct diff_queue_struct queue;
  1004. struct line_log_data *parent_range;
  1005. int changed;
  1006. if (commit->parents)
  1007. parent = commit->parents->item;
  1008. queue_diffs(range, &rev->diffopt, &queue, commit, parent);
  1009. changed = process_all_files(&parent_range, rev, &queue, range);
  1010. if (parent)
  1011. add_line_range(rev, parent, parent_range);
  1012. free_line_log_data(parent_range);
  1013. return changed;
  1014. }
  1015. static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,
  1016. struct line_log_data *range)
  1017. {
  1018. struct diff_queue_struct *diffqueues;
  1019. struct line_log_data **cand;
  1020. struct commit **parents;
  1021. struct commit_list *p;
  1022. int i;
  1023. int nparents = commit_list_count(commit->parents);
  1024. if (nparents > 1 && rev->first_parent_only)
  1025. nparents = 1;
  1026. ALLOC_ARRAY(diffqueues, nparents);
  1027. ALLOC_ARRAY(cand, nparents);
  1028. ALLOC_ARRAY(parents, nparents);
  1029. p = commit->parents;
  1030. for (i = 0; i < nparents; i++) {
  1031. parents[i] = p->item;
  1032. p = p->next;
  1033. queue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);
  1034. }
  1035. for (i = 0; i < nparents; i++) {
  1036. int changed;
  1037. cand[i] = NULL;
  1038. changed = process_all_files(&cand[i], rev, &diffqueues[i], range);
  1039. if (!changed) {
  1040. /*
  1041. * This parent can take all the blame, so we
  1042. * don't follow any other path in history
  1043. */
  1044. add_line_range(rev, parents[i], cand[i]);
  1045. clear_commit_line_range(rev, commit);
  1046. commit_list_append(parents[i], &commit->parents);
  1047. free(parents);
  1048. free(cand);
  1049. free_diffqueues(nparents, diffqueues);
  1050. /* NEEDSWORK leaking like a sieve */
  1051. return 0;
  1052. }
  1053. }
  1054. /*
  1055. * No single parent took the blame. We add the candidates
  1056. * from the above loop to the parents.
  1057. */
  1058. for (i = 0; i < nparents; i++) {
  1059. add_line_range(rev, parents[i], cand[i]);
  1060. }
  1061. clear_commit_line_range(rev, commit);
  1062. free(parents);
  1063. free(cand);
  1064. free_diffqueues(nparents, diffqueues);
  1065. return 1;
  1066. /* NEEDSWORK evil merge detection stuff */
  1067. /* NEEDSWORK leaking like a sieve */
  1068. }
  1069. static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)
  1070. {
  1071. struct line_log_data *range = lookup_line_range(rev, commit);
  1072. int changed = 0;
  1073. if (range) {
  1074. if (!commit->parents || !commit->parents->next)
  1075. changed = process_ranges_ordinary_commit(rev, commit, range);
  1076. else
  1077. changed = process_ranges_merge_commit(rev, commit, range);
  1078. }
  1079. if (!changed)
  1080. commit->object.flags |= TREESAME;
  1081. return changed;
  1082. }
  1083. static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp)
  1084. {
  1085. for (;;) {
  1086. struct commit *p = *pp;
  1087. if (p->parents && p->parents->next)
  1088. return rewrite_one_ok;
  1089. if (p->object.flags & UNINTERESTING)
  1090. return rewrite_one_ok;
  1091. if (!(p->object.flags & TREESAME))
  1092. return rewrite_one_ok;
  1093. if (!p->parents)
  1094. return rewrite_one_noparents;
  1095. *pp = p->parents->item;
  1096. }
  1097. }
  1098. int line_log_filter(struct rev_info *rev)
  1099. {
  1100. struct commit *commit;
  1101. struct commit_list *list = rev->commits;
  1102. struct commit_list *out = NULL, **pp = &out;
  1103. while (list) {
  1104. struct commit_list *to_free = NULL;
  1105. commit = list->item;
  1106. if (process_ranges_arbitrary_commit(rev, commit)) {
  1107. *pp = list;
  1108. pp = &list->next;
  1109. } else
  1110. to_free = list;
  1111. list = list->next;
  1112. free(to_free);
  1113. }
  1114. *pp = NULL;
  1115. for (list = out; list; list = list->next)
  1116. rewrite_parents(rev, list->item, line_log_rewrite_one);
  1117. rev->commits = out;
  1118. return 0;
  1119. }