blob: 49ba38aa7c0a58433380e560f6d84e0cc084a67f [file] [log] [blame]
Junio C Hamanof345b0a2005-05-30 00:08:37 -07001/*
2 * Copyright (C) 2005 Junio C Hamano
3 */
Elijah Newren08c46a42023-05-16 06:33:56 +00004#include "git-compat-util.h"
Junio C Hamanof345b0a2005-05-30 00:08:37 -07005#include "diffcore.h"
Elijah Newrendf6e8742023-05-16 06:34:00 +00006#include "hash.h"
Elijah Newren08c46a42023-05-16 06:33:56 +00007#include "object.h"
Jonathan Tan95acf112020-04-07 15:11:43 -07008#include "promisor-remote.h"
Junio C Hamanof345b0a2005-05-30 00:08:37 -07009
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +020010static int should_break(struct repository *r,
11 struct diff_filespec *src,
Junio C Hamanoeeaa4602005-06-03 01:40:28 -070012 struct diff_filespec *dst,
13 int break_score,
14 int *merge_score_p)
Junio C Hamanof345b0a2005-05-30 00:08:37 -070015{
16 /* dst is recorded as a modification of src. Are they so
17 * different that we are better off recording this as a pair
Junio C Hamanoeeaa4602005-06-03 01:40:28 -070018 * of delete and create?
Junio C Hamanof345b0a2005-05-30 00:08:37 -070019 *
Junio C Hamanoeeaa4602005-06-03 01:40:28 -070020 * There are two criteria used in this algorithm. For the
21 * purposes of helping later rename/copy, we take both delete
22 * and insert into account and estimate the amount of "edit".
23 * If the edit is very large, we break this pair so that
24 * rename/copy can pick the pieces up to match with other
25 * files.
26 *
27 * On the other hand, we would want to ignore inserts for the
28 * pure "complete rewrite" detection. As long as most of the
29 * existing contents were removed from the file, it is a
30 * complete rewrite, and if sizable chunk from the original
31 * still remains in the result, it is not a rewrite. It does
32 * not matter how much or how little new material is added to
33 * the file.
34 *
35 * The score we leave for such a broken filepair uses the
36 * latter definition so that later clean-up stage can find the
37 * pieces that should not have been broken according to the
38 * latter definition after rename/copy runs, and merge the
39 * broken pair that have a score lower than given criteria
40 * back together. The break operation itself happens
41 * according to the former definition.
42 *
43 * The minimum_edit parameter tells us when to break (the
44 * amount of "edit" required for us to consider breaking the
45 * pair). We leave the amount of deletion in *merge_score_p
46 * when we return.
47 *
48 * The value we return is 1 if we want the pair to be broken,
49 * or 0 if we do not.
Junio C Hamanof345b0a2005-05-30 00:08:37 -070050 */
Benjamin Kramereb3a9dd2009-03-07 21:02:10 +010051 unsigned long delta_size, max_size;
Linus Torvalds6dd4b662007-10-20 12:31:31 -070052 unsigned long src_copied, literal_added, src_removed;
Junio C Hamanoeeaa4602005-06-03 01:40:28 -070053
Jonathan Tan95acf112020-04-07 15:11:43 -070054 struct diff_populate_filespec_options options = { 0 };
55
Junio C Hamanoeeaa4602005-06-03 01:40:28 -070056 *merge_score_p = 0; /* assume no deletion --- "do not break"
57 * is the default.
58 */
Junio C Hamanof345b0a2005-05-30 00:08:37 -070059
Junio C Hamanob45563a2007-11-30 22:22:38 -080060 if (S_ISREG(src->mode) != S_ISREG(dst->mode)) {
61 *merge_score_p = (int)MAX_SCORE;
62 return 1; /* even their types are different */
63 }
Junio C Hamanof345b0a2005-05-30 00:08:37 -070064
brian m. carlson41c95602016-06-24 23:09:24 +000065 if (src->oid_valid && dst->oid_valid &&
Jeff King4a7e27e2018-08-28 17:22:40 -040066 oideq(&src->oid, &dst->oid))
Junio C Hamanoaeecd232006-02-28 20:19:47 -080067 return 0; /* they are the same */
68
Ævar Arnfjörð Bjarmasona5183d72023-03-28 15:58:53 +020069 if (r == the_repository && repo_has_promisor_remote(the_repository)) {
Jonathan Tan95acf112020-04-07 15:11:43 -070070 options.missing_object_cb = diff_queued_diff_prefetch;
71 options.missing_object_data = r;
72 }
73
74 if (diff_populate_filespec(r, src, &options) ||
75 diff_populate_filespec(r, dst, &options))
Junio C Hamanof345b0a2005-05-30 00:08:37 -070076 return 0; /* error but caught downstream */
77
Linus Torvalds6dd4b662007-10-20 12:31:31 -070078 max_size = ((src->size > dst->size) ? src->size : dst->size);
79 if (max_size < MINIMUM_BREAK_SIZE)
Junio C Hamano0532a5e2005-12-12 17:15:55 -080080 return 0; /* we do not break too small filepair */
Junio C Hamanof345b0a2005-05-30 00:08:37 -070081
John Keepinge7b00c52013-04-03 20:24:05 +010082 if (!src->size)
83 return 0; /* we do not let empty files get renamed */
84
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +020085 if (diffcore_count_changes(r, src, dst,
Jeff King8282de92009-11-16 11:02:02 -050086 &src->cnt_data, &dst->cnt_data,
Junio C Hamano65416752006-02-28 16:01:36 -080087 &src_copied, &literal_added))
88 return 0;
Junio C Hamano355e76a2005-06-03 01:36:03 -070089
Junio C Hamano4d0f39c2006-03-04 01:03:53 -080090 /* sanity */
91 if (src->size < src_copied)
92 src_copied = src->size;
93 if (dst->size < literal_added + src_copied) {
94 if (src_copied < dst->size)
95 literal_added = dst->size - src_copied;
96 else
97 literal_added = 0;
98 }
99 src_removed = src->size - src_copied;
100
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700101 /* Compute merge-score, which is "how much is removed
102 * from the source material". The clean-up stage will
103 * merge the surviving pair together if the score is
104 * less than the minimum, after rename/copy runs.
105 */
Shawn O. Pearcedc49cd72007-03-06 20:44:37 -0500106 *merge_score_p = (int)(src_removed * MAX_SCORE / src->size);
Linus Torvalds6dd4b662007-10-20 12:31:31 -0700107 if (*merge_score_p > break_score)
108 return 1;
Junio C Hamano4d0f39c2006-03-04 01:03:53 -0800109
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700110 /* Extent of damage, which counts both inserts and
111 * deletes.
112 */
Junio C Hamano4d0f39c2006-03-04 01:03:53 -0800113 delta_size = src_removed + literal_added;
Linus Torvalds6dd4b662007-10-20 12:31:31 -0700114 if (delta_size * MAX_SCORE / max_size < break_score)
Junio C Hamano4d0f39c2006-03-04 01:03:53 -0800115 return 0;
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700116
Junio C Hamano4d0f39c2006-03-04 01:03:53 -0800117 /* If you removed a lot without adding new material, that is
118 * not really a rewrite.
119 */
120 if ((src->size * break_score < src_removed * MAX_SCORE) &&
121 (literal_added * 20 < src_removed) &&
122 (literal_added * 20 < src_copied))
123 return 0;
124
125 return 1;
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700126}
127
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200128void diffcore_break(struct repository *r, int break_score)
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700129{
130 struct diff_queue_struct *q = &diff_queued_diff;
131 struct diff_queue_struct outq;
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700132
133 /* When the filepair has this much edit (insert and delete),
134 * it is first considered to be a rewrite and broken into a
135 * create and delete filepair. This is to help breaking a
136 * file that had too much new stuff added, possibly from
137 * moving contents from another file, so that rename/copy can
138 * match it with the other file.
139 *
140 * int break_score; we reuse incoming parameter for this.
141 */
142
143 /* After a pair is broken according to break_score and
144 * subjected to rename/copy, both of them may survive intact,
145 * due to lack of suitable rename/copy peer. Or, the caller
146 * may be calling us without using rename/copy. When that
147 * happens, we merge the broken pieces back into one
148 * modification together if the pair did not have more than
149 * this much delete. For this computation, we do not take
150 * insert into account at all. If you start from a 100-line
151 * file and delete 97 lines of it, it does not matter if you
152 * add 27 lines to it to make a new 30-line file or if you add
153 * 997 lines to it to make a 1000-line file. Either way what
154 * you did was a rewrite of 97%. On the other hand, if you
155 * delete 3 lines, keeping 97 lines intact, it does not matter
156 * if you add 3 lines to it to make a new 100-line file or if
157 * you add 903 lines to it to make a new 1000-line file.
158 * Either way you did a lot of additions and not a rewrite.
159 * This merge happens to catch the latter case. A merge_score
160 * of 80% would be a good default value (a broken pair that
161 * has score lower than merge_score will be merged back
162 * together).
163 */
164 int merge_score;
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700165 int i;
166
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700167 /* See comment on DEFAULT_BREAK_SCORE and
168 * DEFAULT_MERGE_SCORE in diffcore.h
169 */
170 merge_score = (break_score >> 16) & 0xFFFF;
171 break_score = (break_score & 0xFFFF);
172
173 if (!break_score)
174 break_score = DEFAULT_BREAK_SCORE;
175 if (!merge_score)
176 merge_score = DEFAULT_MERGE_SCORE;
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700177
Bo Yang9ca5df92010-05-06 21:52:27 -0700178 DIFF_QUEUE_CLEAR(&outq);
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700179
180 for (i = 0; i < q->nr; i++) {
181 struct diff_filepair *p = q->queue[i];
182 int score;
183
Junio C Hamanob45563a2007-11-30 22:22:38 -0800184 /*
185 * We deal only with in-place edit of blobs.
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700186 * We do not break anything else.
187 */
188 if (DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two) &&
Junio C Hamanob45563a2007-11-30 22:22:38 -0800189 object_type(p->one->mode) == OBJ_BLOB &&
190 object_type(p->two->mode) == OBJ_BLOB &&
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700191 !strcmp(p->one->path, p->two->path)) {
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200192 if (should_break(r, p->one, p->two,
Junio C Hamano0532a5e2005-12-12 17:15:55 -0800193 break_score, &score)) {
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700194 /* Split this into delete and create */
195 struct diff_filespec *null_one, *null_two;
196 struct diff_filepair *dp;
197
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700198 /* Set score to 0 for the pair that
199 * needs to be merged back together
200 * should they survive rename/copy.
201 * Also we do not want to break very
202 * small files.
203 */
Junio C Hamanof78c79c2005-06-03 23:05:57 -0700204 if (score < merge_score)
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700205 score = 0;
206
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700207 /* deletion of one */
208 null_one = alloc_filespec(p->one->path);
209 dp = diff_queue(&outq, p->one, null_one);
210 dp->score = score;
211 dp->broken_pair = 1;
212
213 /* creation of two */
214 null_two = alloc_filespec(p->two->path);
215 dp = diff_queue(&outq, null_two, p->two);
216 dp->score = score;
217 dp->broken_pair = 1;
218
Jeff King8282de92009-11-16 11:02:02 -0500219 diff_free_filespec_blob(p->one);
220 diff_free_filespec_blob(p->two);
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700221 free(p); /* not diff_free_filepair(), we are
222 * reusing one and two here.
223 */
224 continue;
225 }
226 }
Jeff Kingf4f19fb2009-11-16 10:56:25 -0500227 diff_free_filespec_data(p->one);
228 diff_free_filespec_data(p->two);
Junio C Hamanof345b0a2005-05-30 00:08:37 -0700229 diff_q(&outq, p);
230 }
231 free(q->queue);
232 *q = outq;
233
234 return;
235}
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700236
237static void merge_broken(struct diff_filepair *p,
238 struct diff_filepair *pp,
239 struct diff_queue_struct *outq)
240{
241 /* p and pp are broken pairs we want to merge */
Junio C Hamano366175e2005-06-19 13:17:50 -0700242 struct diff_filepair *c = p, *d = pp, *dp;
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700243 if (DIFF_FILE_VALID(p->one)) {
244 /* this must be a delete half */
245 d = p; c = pp;
246 }
247 /* Sanity check */
248 if (!DIFF_FILE_VALID(d->one))
249 die("internal error in merge #1");
250 if (DIFF_FILE_VALID(d->two))
251 die("internal error in merge #2");
252 if (DIFF_FILE_VALID(c->one))
253 die("internal error in merge #3");
254 if (!DIFF_FILE_VALID(c->two))
255 die("internal error in merge #4");
256
Junio C Hamano366175e2005-06-19 13:17:50 -0700257 dp = diff_queue(outq, d->one, c->two);
258 dp->score = p->score;
Junio C Hamano6936b582014-10-23 10:02:02 -0700259 /*
260 * We will be one extra user of the same src side of the
261 * broken pair, if it was used as the rename source for other
262 * paths elsewhere. Increment to mark that the path stays
263 * in the resulting tree.
264 */
265 d->one->rename_used++;
Junio C Hamano19397b42005-09-14 14:06:50 -0700266 diff_free_filespec_data(d->two);
267 diff_free_filespec_data(c->one);
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700268 free(d);
269 free(c);
270}
271
272void diffcore_merge_broken(void)
273{
274 struct diff_queue_struct *q = &diff_queued_diff;
275 struct diff_queue_struct outq;
276 int i, j;
277
Bo Yang9ca5df92010-05-06 21:52:27 -0700278 DIFF_QUEUE_CLEAR(&outq);
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700279
280 for (i = 0; i < q->nr; i++) {
281 struct diff_filepair *p = q->queue[i];
282 if (!p)
283 /* we already merged this with its peer */
284 continue;
285 else if (p->broken_pair &&
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700286 !strcmp(p->one->path, p->two->path)) {
287 /* If the peer also survived rename/copy, then
288 * we merge them back together.
289 */
290 for (j = i + 1; j < q->nr; j++) {
291 struct diff_filepair *pp = q->queue[j];
292 if (pp->broken_pair &&
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700293 !strcmp(pp->one->path, pp->two->path) &&
294 !strcmp(p->one->path, pp->two->path)) {
295 /* Peer survived. Merge them */
296 merge_broken(p, pp, &outq);
297 q->queue[j] = NULL;
Alex Henriebaed6bb2019-09-30 20:29:35 -0600298 goto next;
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700299 }
300 }
Alex Henriebaed6bb2019-09-30 20:29:35 -0600301 /* The peer did not survive, so we keep
302 * it in the output.
303 */
304 diff_q(&outq, p);
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700305 }
306 else
307 diff_q(&outq, p);
Alex Henriebaed6bb2019-09-30 20:29:35 -0600308next:;
Junio C Hamanoeeaa4602005-06-03 01:40:28 -0700309 }
310 free(q->queue);
311 *q = outq;
312
313 return;
314}