7 static unsigned char (*skipped_sha1
)[20];
8 static int skipped_sha1_nr
;
10 /* bits #0-15 in revision.h */
12 #define COUNTED (1u<<16)
15 * This is a truly stupid algorithm, but it's only
16 * used for bisection, and we just don't care enough.
18 * We care just barely enough to avoid recursing for
21 static int count_distance(struct commit_list
*entry
)
26 struct commit
*commit
= entry
->item
;
27 struct commit_list
*p
;
29 if (commit
->object
.flags
& (UNINTERESTING
| COUNTED
))
31 if (!(commit
->object
.flags
& TREESAME
))
33 commit
->object
.flags
|= COUNTED
;
39 nr
+= count_distance(p
);
48 static void clear_distance(struct commit_list
*list
)
51 struct commit
*commit
= list
->item
;
52 commit
->object
.flags
&= ~COUNTED
;
57 #define DEBUG_BISECT 0
59 static inline int weight(struct commit_list
*elem
)
61 return *((int*)(elem
->item
->util
));
64 static inline void weight_set(struct commit_list
*elem
, int weight
)
66 *((int*)(elem
->item
->util
)) = weight
;
69 static int count_interesting_parents(struct commit
*commit
)
71 struct commit_list
*p
;
74 for (count
= 0, p
= commit
->parents
; p
; p
= p
->next
) {
75 if (p
->item
->object
.flags
& UNINTERESTING
)
82 static inline int halfway(struct commit_list
*p
, int nr
)
85 * Don't short-cut something we are not going to return!
87 if (p
->item
->object
.flags
& TREESAME
)
92 * 2 and 3 are halfway of 5.
93 * 3 is halfway of 6 but 2 and 4 are not.
95 switch (2 * weight(p
) - nr
) {
96 case -1: case 0: case 1:
104 #define show_list(a,b,c,d) do { ; } while (0)
106 static void show_list(const char *debug
, int counted
, int nr
,
107 struct commit_list
*list
)
109 struct commit_list
*p
;
111 fprintf(stderr
, "%s (%d/%d)\n", debug
, counted
, nr
);
113 for (p
= list
; p
; p
= p
->next
) {
114 struct commit_list
*pp
;
115 struct commit
*commit
= p
->item
;
116 unsigned flags
= commit
->object
.flags
;
117 enum object_type type
;
119 char *buf
= read_sha1_file(commit
->object
.sha1
, &type
, &size
);
122 fprintf(stderr
, "%c%c%c ",
123 (flags
& TREESAME
) ? ' ' : 'T',
124 (flags
& UNINTERESTING
) ? 'U' : ' ',
125 (flags
& COUNTED
) ? 'C' : ' ');
127 fprintf(stderr
, "%3d", weight(p
));
129 fprintf(stderr
, "---");
130 fprintf(stderr
, " %.*s", 8, sha1_to_hex(commit
->object
.sha1
));
131 for (pp
= commit
->parents
; pp
; pp
= pp
->next
)
132 fprintf(stderr
, " %.*s", 8,
133 sha1_to_hex(pp
->item
->object
.sha1
));
135 sp
= strstr(buf
, "\n\n");
138 for (ep
= sp
; *ep
&& *ep
!= '\n'; ep
++)
140 fprintf(stderr
, " %.*s", (int)(ep
- sp
), sp
);
142 fprintf(stderr
, "\n");
145 #endif /* DEBUG_BISECT */
147 static struct commit_list
*best_bisection(struct commit_list
*list
, int nr
)
149 struct commit_list
*p
, *best
;
150 int best_distance
= -1;
153 for (p
= list
; p
; p
= p
->next
) {
155 unsigned flags
= p
->item
->object
.flags
;
157 if (flags
& TREESAME
)
159 distance
= weight(p
);
160 if (nr
- distance
< distance
)
161 distance
= nr
- distance
;
162 if (distance
> best_distance
) {
164 best_distance
= distance
;
172 struct commit
*commit
;
176 static int compare_commit_dist(const void *a_
, const void *b_
)
178 struct commit_dist
*a
, *b
;
180 a
= (struct commit_dist
*)a_
;
181 b
= (struct commit_dist
*)b_
;
182 if (a
->distance
!= b
->distance
)
183 return b
->distance
- a
->distance
; /* desc sort */
184 return hashcmp(a
->commit
->object
.sha1
, b
->commit
->object
.sha1
);
187 static struct commit_list
*best_bisection_sorted(struct commit_list
*list
, int nr
)
189 struct commit_list
*p
;
190 struct commit_dist
*array
= xcalloc(nr
, sizeof(*array
));
193 for (p
= list
, cnt
= 0; p
; p
= p
->next
) {
195 unsigned flags
= p
->item
->object
.flags
;
197 if (flags
& TREESAME
)
199 distance
= weight(p
);
200 if (nr
- distance
< distance
)
201 distance
= nr
- distance
;
202 array
[cnt
].commit
= p
->item
;
203 array
[cnt
].distance
= distance
;
206 qsort(array
, cnt
, sizeof(*array
), compare_commit_dist
);
207 for (p
= list
, i
= 0; i
< cnt
; i
++) {
208 struct name_decoration
*r
= xmalloc(sizeof(*r
) + 100);
209 struct object
*obj
= &(array
[i
].commit
->object
);
211 sprintf(r
->name
, "dist=%d", array
[i
].distance
);
212 r
->next
= add_decoration(&name_decoration
, obj
, r
);
213 p
->item
= array
[i
].commit
;
223 * zero or positive weight is the number of interesting commits it can
224 * reach, including itself. Especially, weight = 0 means it does not
225 * reach any tree-changing commits (e.g. just above uninteresting one
226 * but traversal is with pathspec).
228 * weight = -1 means it has one parent and its distance is yet to
231 * weight = -2 means it has more than one parent and its distance is
232 * unknown. After running count_distance() first, they will get zero
233 * or positive distance.
235 static struct commit_list
*do_find_bisection(struct commit_list
*list
,
236 int nr
, int *weights
,
240 struct commit_list
*p
;
244 for (n
= 0, p
= list
; p
; p
= p
->next
) {
245 struct commit
*commit
= p
->item
;
246 unsigned flags
= commit
->object
.flags
;
248 p
->item
->util
= &weights
[n
++];
249 switch (count_interesting_parents(commit
)) {
251 if (!(flags
& TREESAME
)) {
254 show_list("bisection 2 count one",
258 * otherwise, it is known not to reach any
259 * tree-changing commit and gets weight 0.
271 show_list("bisection 2 initialize", counted
, nr
, list
);
274 * If you have only one parent in the resulting set
275 * then you can reach one commit more than that parent
276 * can reach. So we do not have to run the expensive
277 * count_distance() for single strand of pearls.
279 * However, if you have more than one parents, you cannot
280 * just add their distance and one for yourself, since
281 * they usually reach the same ancestor and you would
282 * end up counting them twice that way.
284 * So we will first count distance of merges the usual
285 * way, and then fill the blanks using cheaper algorithm.
287 for (p
= list
; p
; p
= p
->next
) {
288 if (p
->item
->object
.flags
& UNINTERESTING
)
292 weight_set(p
, count_distance(p
));
293 clear_distance(list
);
295 /* Does it happen to be at exactly half-way? */
296 if (!find_all
&& halfway(p
, nr
))
301 show_list("bisection 2 count_distance", counted
, nr
, list
);
303 while (counted
< nr
) {
304 for (p
= list
; p
; p
= p
->next
) {
305 struct commit_list
*q
;
306 unsigned flags
= p
->item
->object
.flags
;
310 for (q
= p
->item
->parents
; q
; q
= q
->next
) {
311 if (q
->item
->object
.flags
& UNINTERESTING
)
320 * weight for p is unknown but q is known.
321 * add one for p itself if p is to be counted,
322 * otherwise inherit it from q directly.
324 if (!(flags
& TREESAME
)) {
325 weight_set(p
, weight(q
)+1);
327 show_list("bisection 2 count one",
331 weight_set(p
, weight(q
));
333 /* Does it happen to be at exactly half-way? */
334 if (!find_all
&& halfway(p
, nr
))
339 show_list("bisection 2 counted all", counted
, nr
, list
);
342 return best_bisection(list
, nr
);
344 return best_bisection_sorted(list
, nr
);
347 struct commit_list
*find_bisection(struct commit_list
*list
,
348 int *reaches
, int *all
,
352 struct commit_list
*p
, *best
, *next
, *last
;
355 show_list("bisection 2 entry", 0, 0, list
);
358 * Count the number of total and tree-changing items on the
359 * list, while reversing the list.
361 for (nr
= on_list
= 0, last
= NULL
, p
= list
;
364 unsigned flags
= p
->item
->object
.flags
;
367 if (flags
& UNINTERESTING
)
371 if (!(flags
& TREESAME
))
376 show_list("bisection 2 sorted", 0, nr
, list
);
379 weights
= xcalloc(on_list
, sizeof(*weights
));
381 /* Do the real work of finding bisection commit. */
382 best
= do_find_bisection(list
, nr
, weights
, find_all
);
386 *reaches
= weight(best
);
392 static int skipcmp(const void *a
, const void *b
)
394 return hashcmp(a
, b
);
397 static void prepare_skipped(void)
399 qsort(skipped_sha1
, skipped_sha1_nr
, sizeof(*skipped_sha1
), skipcmp
);
402 static int lookup_skipped(unsigned char *sha1
)
406 hi
= skipped_sha1_nr
;
408 int mi
= (lo
+ hi
) / 2;
409 int cmp
= hashcmp(sha1
, skipped_sha1
[mi
]);
420 struct commit_list
*filter_skipped(struct commit_list
*list
,
421 struct commit_list
**tried
,
424 struct commit_list
*filtered
= NULL
, **f
= &filtered
;
428 if (!skipped_sha1_nr
)
434 struct commit_list
*next
= list
->next
;
436 if (0 <= lookup_skipped(list
->item
->object
.sha1
)) {
437 /* Move current to tried list */
443 /* Move current to filtered list */