jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2005, Jon Seymour |
| 3 | * |
| 4 | * For more information about epoch theory on which this module is based, |
| 5 | * refer to http://blackcubes.dyndns.org/epoch/. That web page defines |
| 6 | * terms such as "epoch" and "minimal, non-linear epoch" and provides rationales |
| 7 | * for some of the algorithms used here. |
| 8 | * |
| 9 | */ |
| 10 | #include <stdlib.h> |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 11 | |
| 12 | /* Provides arbitrary precision integers required to accurately represent |
| 13 | * fractional mass: */ |
| 14 | #include <openssl/bn.h> |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 15 | |
| 16 | #include "cache.h" |
| 17 | #include "commit.h" |
| 18 | #include "epoch.h" |
| 19 | |
| 20 | struct fraction { |
| 21 | BIGNUM numerator; |
| 22 | BIGNUM denominator; |
| 23 | }; |
| 24 | |
| 25 | #define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next) |
| 26 | |
| 27 | static BN_CTX *context = NULL; |
| 28 | static struct fraction *one = NULL; |
| 29 | static struct fraction *zero = NULL; |
| 30 | |
Linus Torvalds | 6da4016 | 2005-07-03 10:10:45 -0700 | [diff] [blame] | 31 | static BN_CTX *get_BN_CTX(void) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 32 | { |
| 33 | if (!context) { |
| 34 | context = BN_CTX_new(); |
| 35 | } |
| 36 | return context; |
| 37 | } |
| 38 | |
Linus Torvalds | 6da4016 | 2005-07-03 10:10:45 -0700 | [diff] [blame] | 39 | static struct fraction *new_zero(void) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 40 | { |
| 41 | struct fraction *result = xmalloc(sizeof(*result)); |
| 42 | BN_init(&result->numerator); |
| 43 | BN_init(&result->denominator); |
| 44 | BN_zero(&result->numerator); |
| 45 | BN_one(&result->denominator); |
| 46 | return result; |
| 47 | } |
| 48 | |
| 49 | static void clear_fraction(struct fraction *fraction) |
| 50 | { |
| 51 | BN_clear(&fraction->numerator); |
| 52 | BN_clear(&fraction->denominator); |
| 53 | } |
| 54 | |
| 55 | static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor) |
| 56 | { |
| 57 | BIGNUM bn_divisor; |
| 58 | |
| 59 | BN_init(&bn_divisor); |
| 60 | BN_set_word(&bn_divisor, divisor); |
| 61 | |
| 62 | BN_copy(&result->numerator, &fraction->numerator); |
| 63 | BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX()); |
| 64 | |
| 65 | BN_clear(&bn_divisor); |
| 66 | return result; |
| 67 | } |
| 68 | |
| 69 | static struct fraction *init_fraction(struct fraction *fraction) |
| 70 | { |
| 71 | BN_init(&fraction->numerator); |
| 72 | BN_init(&fraction->denominator); |
| 73 | BN_zero(&fraction->numerator); |
| 74 | BN_one(&fraction->denominator); |
| 75 | return fraction; |
| 76 | } |
| 77 | |
Linus Torvalds | 6da4016 | 2005-07-03 10:10:45 -0700 | [diff] [blame] | 78 | static struct fraction *get_one(void) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 79 | { |
| 80 | if (!one) { |
| 81 | one = new_zero(); |
| 82 | BN_one(&one->numerator); |
| 83 | } |
| 84 | return one; |
| 85 | } |
| 86 | |
Linus Torvalds | 6da4016 | 2005-07-03 10:10:45 -0700 | [diff] [blame] | 87 | static struct fraction *get_zero(void) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 88 | { |
| 89 | if (!zero) { |
| 90 | zero = new_zero(); |
| 91 | } |
| 92 | return zero; |
| 93 | } |
| 94 | |
| 95 | static struct fraction *copy(struct fraction *to, struct fraction *from) |
| 96 | { |
| 97 | BN_copy(&to->numerator, &from->numerator); |
| 98 | BN_copy(&to->denominator, &from->denominator); |
| 99 | return to; |
| 100 | } |
| 101 | |
| 102 | static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right) |
| 103 | { |
| 104 | BIGNUM a, b, gcd; |
| 105 | |
| 106 | BN_init(&a); |
| 107 | BN_init(&b); |
| 108 | BN_init(&gcd); |
| 109 | |
| 110 | BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX()); |
| 111 | BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX()); |
| 112 | BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX()); |
| 113 | BN_add(&result->numerator, &a, &b); |
| 114 | |
| 115 | BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX()); |
| 116 | BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX()); |
| 117 | BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX()); |
| 118 | |
| 119 | BN_clear(&a); |
| 120 | BN_clear(&b); |
| 121 | BN_clear(&gcd); |
| 122 | |
| 123 | return result; |
| 124 | } |
| 125 | |
| 126 | static int compare(struct fraction *left, struct fraction *right) |
| 127 | { |
| 128 | BIGNUM a, b; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 129 | int result; |
| 130 | |
| 131 | BN_init(&a); |
| 132 | BN_init(&b); |
| 133 | |
| 134 | BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX()); |
| 135 | BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX()); |
| 136 | |
| 137 | result = BN_cmp(&a, &b); |
| 138 | |
| 139 | BN_clear(&a); |
| 140 | BN_clear(&b); |
| 141 | |
| 142 | return result; |
| 143 | } |
| 144 | |
| 145 | struct mass_counter { |
| 146 | struct fraction seen; |
| 147 | struct fraction pending; |
| 148 | }; |
| 149 | |
| 150 | static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending) |
| 151 | { |
| 152 | struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter)); |
| 153 | memset(mass_counter, 0, sizeof(*mass_counter)); |
| 154 | |
| 155 | init_fraction(&mass_counter->seen); |
| 156 | init_fraction(&mass_counter->pending); |
| 157 | |
| 158 | copy(&mass_counter->pending, pending); |
| 159 | copy(&mass_counter->seen, get_zero()); |
| 160 | |
| 161 | if (commit->object.util) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 162 | die("multiple attempts to initialize mass counter for %s", |
| 163 | sha1_to_hex(commit->object.sha1)); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 164 | } |
| 165 | |
| 166 | commit->object.util = mass_counter; |
| 167 | |
| 168 | return mass_counter; |
| 169 | } |
| 170 | |
| 171 | static void free_mass_counter(struct mass_counter *counter) |
| 172 | { |
| 173 | clear_fraction(&counter->seen); |
| 174 | clear_fraction(&counter->pending); |
| 175 | free(counter); |
| 176 | } |
| 177 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 178 | /* |
| 179 | * Finds the base commit of a list of commits. |
| 180 | * |
| 181 | * One property of the commit being searched for is that every commit reachable |
| 182 | * from the base commit is reachable from the commits in the starting list only |
| 183 | * via paths that include the base commit. |
| 184 | * |
| 185 | * This algorithm uses a conservation of mass approach to find the base commit. |
| 186 | * |
| 187 | * We start by injecting one unit of mass into the graph at each |
| 188 | * of the commits in the starting list. Injecting mass into a commit |
| 189 | * is achieved by adding to its pending mass counter and, if it is not already |
| 190 | * enqueued, enqueuing the commit in a list of pending commits, in latest |
| 191 | * commit date first order. |
| 192 | * |
| 193 | * The algorithm then preceeds to visit each commit in the pending queue. |
| 194 | * Upon each visit, the pending mass is added to the mass already seen for that |
| 195 | * commit and then divided into N equal portions, where N is the number of |
| 196 | * parents of the commit being visited. The divided portions are then injected |
| 197 | * into each of the parents. |
| 198 | * |
| 199 | * The algorithm continues until we discover a commit which has seen all the |
| 200 | * mass originally injected or until we run out of things to do. |
| 201 | * |
| 202 | * If we find a commit that has seen all the original mass, we have found |
| 203 | * the common base of all the commits in the starting list. |
| 204 | * |
| 205 | * The algorithm does _not_ depend on accurate timestamps for correct operation. |
| 206 | * However, reasonably sane (e.g. non-random) timestamps are required in order |
| 207 | * to prevent an exponential performance characteristic. The occasional |
| 208 | * timestamp inaccuracy will not dramatically affect performance but may |
| 209 | * result in more nodes being processed than strictly necessary. |
| 210 | * |
| 211 | * This procedure sets *boundary to the address of the base commit. It returns |
| 212 | * non-zero if, and only if, there was a problem parsing one of the |
| 213 | * commits discovered during the traversal. |
| 214 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 215 | static int find_base_for_list(struct commit_list *list, struct commit **boundary) |
| 216 | { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 217 | int ret = 0; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 218 | struct commit_list *cleaner = NULL; |
| 219 | struct commit_list *pending = NULL; |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 220 | struct fraction injected; |
| 221 | init_fraction(&injected); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 222 | *boundary = NULL; |
| 223 | |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 224 | for (; list; list = list->next) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 225 | struct commit *item = list->item; |
| 226 | |
Jon Seymour | c3c1163 | 2005-06-20 12:29:33 +1000 | [diff] [blame] | 227 | if (!item->object.util) { |
| 228 | new_mass_counter(list->item, get_one()); |
| 229 | add(&injected, &injected, get_one()); |
| 230 | |
| 231 | commit_list_insert(list->item, &cleaner); |
| 232 | commit_list_insert(list->item, &pending); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 233 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | while (!*boundary && pending && !ret) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 237 | struct commit *latest = pop_commit(&pending); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 238 | struct mass_counter *latest_node = (struct mass_counter *) latest->object.util; |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 239 | int num_parents; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 240 | |
| 241 | if ((ret = parse_commit(latest))) |
| 242 | continue; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 243 | add(&latest_node->seen, &latest_node->seen, &latest_node->pending); |
| 244 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 245 | num_parents = count_parents(latest); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 246 | if (num_parents) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 247 | struct fraction distribution; |
| 248 | struct commit_list *parents; |
| 249 | |
| 250 | divide(init_fraction(&distribution), &latest_node->pending, num_parents); |
| 251 | |
| 252 | for (parents = latest->parents; parents; parents = parents->next) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 253 | struct commit *parent = parents->item; |
| 254 | struct mass_counter *parent_node = (struct mass_counter *) parent->object.util; |
| 255 | |
| 256 | if (!parent_node) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 257 | parent_node = new_mass_counter(parent, &distribution); |
Linus Torvalds | f755494 | 2005-07-06 09:31:17 -0700 | [diff] [blame] | 258 | insert_by_date(parent, &pending); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 259 | commit_list_insert(parent, &cleaner); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 260 | } else { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 261 | if (!compare(&parent_node->pending, get_zero())) |
Linus Torvalds | f755494 | 2005-07-06 09:31:17 -0700 | [diff] [blame] | 262 | insert_by_date(parent, &pending); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 263 | add(&parent_node->pending, &parent_node->pending, &distribution); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 264 | } |
| 265 | } |
| 266 | |
| 267 | clear_fraction(&distribution); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 268 | } |
| 269 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 270 | if (!compare(&latest_node->seen, &injected)) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 271 | *boundary = latest; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 272 | copy(&latest_node->pending, get_zero()); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 273 | } |
| 274 | |
| 275 | while (cleaner) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 276 | struct commit *next = pop_commit(&cleaner); |
| 277 | free_mass_counter((struct mass_counter *) next->object.util); |
| 278 | next->object.util = NULL; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 279 | } |
| 280 | |
| 281 | if (pending) |
| 282 | free_commit_list(pending); |
| 283 | |
| 284 | clear_fraction(&injected); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 285 | return ret; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 286 | } |
| 287 | |
| 288 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 289 | /* |
| 290 | * Finds the base of an minimal, non-linear epoch, headed at head, by |
| 291 | * applying the find_base_for_list to a list consisting of the parents |
| 292 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 293 | static int find_base(struct commit *head, struct commit **boundary) |
| 294 | { |
| 295 | int ret = 0; |
| 296 | struct commit_list *pending = NULL; |
| 297 | struct commit_list *next; |
| 298 | |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 299 | for (next = head->parents; next; next = next->next) { |
| 300 | commit_list_insert(next->item, &pending); |
| 301 | } |
| 302 | ret = find_base_for_list(pending, boundary); |
| 303 | free_commit_list(pending); |
| 304 | |
| 305 | return ret; |
| 306 | } |
| 307 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 308 | /* |
| 309 | * This procedure traverses to the boundary of the first epoch in the epoch |
| 310 | * sequence of the epoch headed at head_of_epoch. This is either the end of |
| 311 | * the maximal linear epoch or the base of a minimal non-linear epoch. |
| 312 | * |
| 313 | * The queue of pending nodes is sorted in reverse date order and each node |
| 314 | * is currently in the queue at most once. |
| 315 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 316 | static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary) |
| 317 | { |
| 318 | int ret; |
| 319 | struct commit *item = head_of_epoch; |
| 320 | |
| 321 | ret = parse_commit(item); |
| 322 | if (ret) |
| 323 | return ret; |
| 324 | |
| 325 | if (HAS_EXACTLY_ONE_PARENT(item)) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 326 | /* |
| 327 | * We are at the start of a maximimal linear epoch. |
| 328 | * Traverse to the end. |
| 329 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 330 | while (HAS_EXACTLY_ONE_PARENT(item) && !ret) { |
| 331 | item = item->parents->item; |
| 332 | ret = parse_commit(item); |
| 333 | } |
| 334 | *boundary = item; |
| 335 | |
| 336 | } else { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 337 | /* |
| 338 | * Otherwise, we are at the start of a minimal, non-linear |
| 339 | * epoch - find the common base of all parents. |
| 340 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 341 | ret = find_base(item, boundary); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 342 | } |
| 343 | |
| 344 | return ret; |
| 345 | } |
| 346 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 347 | /* |
| 348 | * Returns non-zero if parent is known to be a parent of child. |
| 349 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 350 | static int is_parent_of(struct commit *parent, struct commit *child) |
| 351 | { |
| 352 | struct commit_list *parents; |
| 353 | for (parents = child->parents; parents; parents = parents->next) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 354 | if (!memcmp(parent->object.sha1, parents->item->object.sha1, |
| 355 | sizeof(parents->item->object.sha1))) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 356 | return 1; |
| 357 | } |
| 358 | return 0; |
| 359 | } |
| 360 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 361 | /* |
| 362 | * Pushes an item onto the merge order stack. If the top of the stack is |
| 363 | * marked as being a possible "break", we check to see whether it actually |
| 364 | * is a break. |
| 365 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 366 | static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item) |
| 367 | { |
| 368 | struct commit_list *top = *stack; |
| 369 | if (top && (top->item->object.flags & DISCONTINUITY)) { |
| 370 | if (is_parent_of(top->item, item)) { |
| 371 | top->item->object.flags &= ~DISCONTINUITY; |
| 372 | } |
| 373 | } |
| 374 | commit_list_insert(item, stack); |
| 375 | } |
| 376 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 377 | /* |
| 378 | * Marks all interesting, visited commits reachable from this commit |
| 379 | * as uninteresting. We stop recursing when we reach the epoch boundary, |
| 380 | * an unvisited node or a node that has already been marking uninteresting. |
| 381 | * |
| 382 | * This doesn't actually mark all ancestors between the start node and the |
| 383 | * epoch boundary uninteresting, but does ensure that they will eventually |
| 384 | * be marked uninteresting when the main sort_first_epoch() traversal |
| 385 | * eventually reaches them. |
| 386 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 387 | static void mark_ancestors_uninteresting(struct commit *commit) |
| 388 | { |
| 389 | unsigned int flags = commit->object.flags; |
| 390 | int visited = flags & VISITED; |
| 391 | int boundary = flags & BOUNDARY; |
| 392 | int uninteresting = flags & UNINTERESTING; |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 393 | struct commit_list *next; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 394 | |
Jon Seymour | 4e73467 | 2005-06-09 00:37:41 +1000 | [diff] [blame] | 395 | commit->object.flags |= UNINTERESTING; |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 396 | |
| 397 | /* |
| 398 | * We only need to recurse if |
| 399 | * we are not on the boundary and |
| 400 | * we have not already been marked uninteresting and |
| 401 | * we have already been visited. |
| 402 | * |
| 403 | * The main sort_first_epoch traverse will mark unreachable |
| 404 | * all uninteresting, unvisited parents as they are visited |
| 405 | * so there is no need to duplicate that traversal here. |
| 406 | * |
| 407 | * Similarly, if we are already marked uninteresting |
| 408 | * then either all ancestors have already been marked |
| 409 | * uninteresting or will be once the sort_first_epoch |
| 410 | * traverse reaches them. |
| 411 | */ |
| 412 | |
| 413 | if (uninteresting || boundary || !visited) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 414 | return; |
| 415 | |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 416 | for (next = commit->parents; next; next = next->next) |
| 417 | mark_ancestors_uninteresting(next->item); |
| 418 | } |
| 419 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 420 | /* |
| 421 | * Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head |
| 422 | * into merge order. |
| 423 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 424 | static void sort_first_epoch(struct commit *head, struct commit_list **stack) |
| 425 | { |
| 426 | struct commit_list *parents; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 427 | |
| 428 | head->object.flags |= VISITED; |
| 429 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 430 | /* |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 431 | * TODO: By sorting the parents in a different order, we can alter the |
| 432 | * merge order to show contemporaneous changes in parallel branches |
| 433 | * occurring after "local" changes. This is useful for a developer |
| 434 | * when a developer wants to see all changes that were incorporated |
| 435 | * into the same merge as her own changes occur after her own |
| 436 | * changes. |
| 437 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 438 | |
Jon Seymour | 60646e9 | 2005-06-22 01:58:46 +1000 | [diff] [blame] | 439 | for (parents = head->parents; parents; parents = parents->next) { |
| 440 | struct commit *parent = parents->item; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 441 | |
| 442 | if (head->object.flags & UNINTERESTING) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 443 | /* |
| 444 | * Propagates the uninteresting bit to all parents. |
| 445 | * if we have already visited this parent, then |
| 446 | * the uninteresting bit will be propagated to each |
| 447 | * reachable commit that is still not marked |
| 448 | * uninteresting and won't otherwise be reached. |
| 449 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 450 | mark_ancestors_uninteresting(parent); |
| 451 | } |
| 452 | |
| 453 | if (!(parent->object.flags & VISITED)) { |
| 454 | if (parent->object.flags & BOUNDARY) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 455 | if (*stack) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 456 | die("something else is on the stack - %s", |
| 457 | sha1_to_hex((*stack)->item->object.sha1)); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 458 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 459 | push_onto_merge_order_stack(stack, parent); |
| 460 | parent->object.flags |= VISITED; |
| 461 | |
| 462 | } else { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 463 | sort_first_epoch(parent, stack); |
Jon Seymour | 60646e9 | 2005-06-22 01:58:46 +1000 | [diff] [blame] | 464 | if (parents) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 465 | /* |
| 466 | * This indicates a possible |
| 467 | * discontinuity it may not be be |
| 468 | * actual discontinuity if the head |
| 469 | * of parent N happens to be the tail |
| 470 | * of parent N+1. |
| 471 | * |
| 472 | * The next push onto the stack will |
| 473 | * resolve the question. |
| 474 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 475 | (*stack)->item->object.flags |= DISCONTINUITY; |
| 476 | } |
| 477 | } |
| 478 | } |
| 479 | } |
| 480 | |
| 481 | push_onto_merge_order_stack(stack, head); |
| 482 | } |
| 483 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 484 | /* |
| 485 | * Emit the contents of the stack. |
| 486 | * |
| 487 | * The stack is freed and replaced by NULL. |
| 488 | * |
| 489 | * Sets the return value to STOP if no further output should be generated. |
| 490 | */ |
Jon Seymour | 170774a | 2005-06-23 12:01:12 +1000 | [diff] [blame] | 491 | static int emit_stack(struct commit_list **stack, emitter_func emitter, int include_last) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 492 | { |
| 493 | unsigned int seen = 0; |
| 494 | int action = CONTINUE; |
| 495 | |
| 496 | while (*stack && (action != STOP)) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 497 | struct commit *next = pop_commit(stack); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 498 | seen |= next->object.flags; |
Jon Seymour | 170774a | 2005-06-23 12:01:12 +1000 | [diff] [blame] | 499 | if (*stack || include_last) { |
| 500 | if (!*stack) |
| 501 | next->object.flags |= BOUNDARY; |
Jon Seymour | 84b18a8 | 2005-07-07 11:26:43 +1000 | [diff] [blame] | 502 | action = emitter(next); |
Jon Seymour | 170774a | 2005-06-23 12:01:12 +1000 | [diff] [blame] | 503 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 504 | } |
| 505 | |
| 506 | if (*stack) { |
| 507 | free_commit_list(*stack); |
| 508 | *stack = NULL; |
| 509 | } |
| 510 | |
| 511 | return (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE; |
| 512 | } |
| 513 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 514 | /* |
| 515 | * Sorts an arbitrary epoch into merge order by sorting each epoch |
| 516 | * of its epoch sequence into order. |
| 517 | * |
| 518 | * Note: this algorithm currently leaves traces of its execution in the |
| 519 | * object flags of nodes it discovers. This should probably be fixed. |
| 520 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 521 | static int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter) |
| 522 | { |
| 523 | struct commit *next = head_of_epoch; |
| 524 | int ret = 0; |
| 525 | int action = CONTINUE; |
| 526 | |
| 527 | ret = parse_commit(head_of_epoch); |
| 528 | |
Jon Seymour | 8cd1033 | 2005-06-20 12:29:29 +1000 | [diff] [blame] | 529 | next->object.flags |= BOUNDARY; |
| 530 | |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 531 | while (next && next->parents && !ret && (action != STOP)) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 532 | struct commit *base = NULL; |
| 533 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 534 | ret = find_next_epoch_boundary(next, &base); |
| 535 | if (ret) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 536 | return ret; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 537 | next->object.flags |= BOUNDARY; |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 538 | if (base) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 539 | base->object.flags |= BOUNDARY; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 540 | |
| 541 | if (HAS_EXACTLY_ONE_PARENT(next)) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 542 | while (HAS_EXACTLY_ONE_PARENT(next) |
| 543 | && (action != STOP) |
| 544 | && !ret) { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 545 | if (next->object.flags & UNINTERESTING) { |
| 546 | action = STOP; |
| 547 | } else { |
Jon Seymour | 84b18a8 | 2005-07-07 11:26:43 +1000 | [diff] [blame] | 548 | action = emitter(next); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 549 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 550 | if (action != STOP) { |
| 551 | next = next->parents->item; |
| 552 | ret = parse_commit(next); |
| 553 | } |
| 554 | } |
| 555 | |
| 556 | } else { |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 557 | struct commit_list *stack = NULL; |
| 558 | sort_first_epoch(next, &stack); |
Jon Seymour | 170774a | 2005-06-23 12:01:12 +1000 | [diff] [blame] | 559 | action = emit_stack(&stack, emitter, (base == NULL)); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 560 | next = base; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 561 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 562 | } |
| 563 | |
| 564 | if (next && (action != STOP) && !ret) { |
Jon Seymour | 84b18a8 | 2005-07-07 11:26:43 +1000 | [diff] [blame] | 565 | emitter(next); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 566 | } |
| 567 | |
| 568 | return ret; |
| 569 | } |
| 570 | |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 571 | /* |
| 572 | * Sorts the nodes reachable from a starting list in merge order, we |
| 573 | * first find the base for the starting list and then sort all nodes |
| 574 | * in this subgraph using the sort_first_epoch algorithm. Once we have |
| 575 | * reached the base we can continue sorting using sort_in_merge_order. |
| 576 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 577 | int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter) |
| 578 | { |
| 579 | struct commit_list *stack = NULL; |
| 580 | struct commit *base; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 581 | int ret = 0; |
| 582 | int action = CONTINUE; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 583 | struct commit_list *reversed = NULL; |
| 584 | |
Linus Torvalds | bce6286 | 2005-07-06 09:56:16 -0700 | [diff] [blame] | 585 | for (; list; list = list->next) |
| 586 | commit_list_insert(list->item, &reversed); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 587 | |
Jon Seymour | d6bd56a | 2005-06-20 12:29:31 +1000 | [diff] [blame] | 588 | if (!reversed) |
| 589 | return ret; |
| 590 | else if (!reversed->next) { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 591 | /* |
| 592 | * If there is only one element in the list, we can sort it |
| 593 | * using sort_in_merge_order. |
| 594 | */ |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 595 | base = reversed->item; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 596 | } else { |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 597 | /* |
| 598 | * Otherwise, we search for the base of the list. |
| 599 | */ |
| 600 | ret = find_base_for_list(reversed, &base); |
| 601 | if (ret) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 602 | return ret; |
Petr Baudis | 17ebe97 | 2005-06-08 22:59:43 +0200 | [diff] [blame] | 603 | if (base) |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 604 | base->object.flags |= BOUNDARY; |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 605 | |
| 606 | while (reversed) { |
Jon Seymour | eff19d5 | 2005-06-20 12:29:36 +1000 | [diff] [blame] | 607 | struct commit * next = pop_commit(&reversed); |
| 608 | |
Jon Seymour | ff9206e | 2005-07-07 02:39:35 +1000 | [diff] [blame] | 609 | if (!(next->object.flags & VISITED) && next!=base) { |
Jon Seymour | eff19d5 | 2005-06-20 12:29:36 +1000 | [diff] [blame] | 610 | sort_first_epoch(next, &stack); |
| 611 | if (reversed) { |
| 612 | /* |
| 613 | * If we have more commits |
| 614 | * to push, then the first |
| 615 | * push for the next parent may |
| 616 | * (or may * not) represent a |
| 617 | * discontinuity with respect |
| 618 | * to the parent currently on |
| 619 | * the top of the stack. |
| 620 | * |
| 621 | * Mark it for checking here, |
| 622 | * and check it with the next |
| 623 | * push. See sort_first_epoch() |
| 624 | * for more details. |
| 625 | */ |
| 626 | stack->item->object.flags |= DISCONTINUITY; |
| 627 | } |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 628 | } |
| 629 | } |
| 630 | |
Jon Seymour | 170774a | 2005-06-23 12:01:12 +1000 | [diff] [blame] | 631 | action = emit_stack(&stack, emitter, (base==NULL)); |
jon@blackcubes.dyndns.org | a3437b8 | 2005-06-06 15:39:40 +0000 | [diff] [blame] | 632 | } |
| 633 | |
| 634 | if (base && (action != STOP)) { |
| 635 | ret = sort_in_merge_order(base, emitter); |
| 636 | } |
| 637 | |
| 638 | return ret; |
| 639 | } |