| #include "cache.h" |
| #include "tag.h" |
| #include "commit.h" |
| #include "pkt-line.h" |
| #include "utf8.h" |
| #include "diff.h" |
| #include "revision.h" |
| |
| int save_commit_buffer = 1; |
| |
| const char *commit_type = "commit"; |
| |
| static struct commit *check_commit(struct object *obj, |
| const unsigned char *sha1, |
| int quiet) |
| { |
| if (obj->type != OBJ_COMMIT) { |
| if (!quiet) |
| error("Object %s is a %s, not a commit", |
| sha1_to_hex(sha1), typename(obj->type)); |
| return NULL; |
| } |
| return (struct commit *) obj; |
| } |
| |
| struct commit *lookup_commit_reference_gently(const unsigned char *sha1, |
| int quiet) |
| { |
| struct object *obj = deref_tag(parse_object(sha1), NULL, 0); |
| |
| if (!obj) |
| return NULL; |
| return check_commit(obj, sha1, quiet); |
| } |
| |
| struct commit *lookup_commit_reference(const unsigned char *sha1) |
| { |
| return lookup_commit_reference_gently(sha1, 0); |
| } |
| |
| struct commit *lookup_commit(const unsigned char *sha1) |
| { |
| struct object *obj = lookup_object(sha1); |
| if (!obj) |
| return create_object(sha1, OBJ_COMMIT, alloc_commit_node()); |
| if (!obj->type) |
| obj->type = OBJ_COMMIT; |
| return check_commit(obj, sha1, 0); |
| } |
| |
| static unsigned long parse_commit_date(const char *buf, const char *tail) |
| { |
| const char *dateptr; |
| |
| if (buf + 6 >= tail) |
| return 0; |
| if (memcmp(buf, "author", 6)) |
| return 0; |
| while (buf < tail && *buf++ != '\n') |
| /* nada */; |
| if (buf + 9 >= tail) |
| return 0; |
| if (memcmp(buf, "committer", 9)) |
| return 0; |
| while (buf < tail && *buf++ != '>') |
| /* nada */; |
| if (buf >= tail) |
| return 0; |
| dateptr = buf; |
| while (buf < tail && *buf++ != '\n') |
| /* nada */; |
| if (buf >= tail) |
| return 0; |
| /* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */ |
| return strtoul(dateptr, NULL, 10); |
| } |
| |
| static struct commit_graft **commit_graft; |
| static int commit_graft_alloc, commit_graft_nr; |
| |
| static int commit_graft_pos(const unsigned char *sha1) |
| { |
| int lo, hi; |
| lo = 0; |
| hi = commit_graft_nr; |
| while (lo < hi) { |
| int mi = (lo + hi) / 2; |
| struct commit_graft *graft = commit_graft[mi]; |
| int cmp = hashcmp(sha1, graft->sha1); |
| if (!cmp) |
| return mi; |
| if (cmp < 0) |
| hi = mi; |
| else |
| lo = mi + 1; |
| } |
| return -lo - 1; |
| } |
| |
| int register_commit_graft(struct commit_graft *graft, int ignore_dups) |
| { |
| int pos = commit_graft_pos(graft->sha1); |
| |
| if (0 <= pos) { |
| if (ignore_dups) |
| free(graft); |
| else { |
| free(commit_graft[pos]); |
| commit_graft[pos] = graft; |
| } |
| return 1; |
| } |
| pos = -pos - 1; |
| if (commit_graft_alloc <= ++commit_graft_nr) { |
| commit_graft_alloc = alloc_nr(commit_graft_alloc); |
| commit_graft = xrealloc(commit_graft, |
| sizeof(*commit_graft) * |
| commit_graft_alloc); |
| } |
| if (pos < commit_graft_nr) |
| memmove(commit_graft + pos + 1, |
| commit_graft + pos, |
| (commit_graft_nr - pos - 1) * |
| sizeof(*commit_graft)); |
| commit_graft[pos] = graft; |
| return 0; |
| } |
| |
| struct commit_graft *read_graft_line(char *buf, int len) |
| { |
| /* The format is just "Commit Parent1 Parent2 ...\n" */ |
| int i; |
| struct commit_graft *graft = NULL; |
| |
| if (buf[len-1] == '\n') |
| buf[--len] = 0; |
| if (buf[0] == '#' || buf[0] == '\0') |
| return NULL; |
| if ((len + 1) % 41) { |
| bad_graft_data: |
| error("bad graft data: %s", buf); |
| free(graft); |
| return NULL; |
| } |
| i = (len + 1) / 41 - 1; |
| graft = xmalloc(sizeof(*graft) + 20 * i); |
| graft->nr_parent = i; |
| if (get_sha1_hex(buf, graft->sha1)) |
| goto bad_graft_data; |
| for (i = 40; i < len; i += 41) { |
| if (buf[i] != ' ') |
| goto bad_graft_data; |
| if (get_sha1_hex(buf + i + 1, graft->parent[i/41])) |
| goto bad_graft_data; |
| } |
| return graft; |
| } |
| |
| static int read_graft_file(const char *graft_file) |
| { |
| FILE *fp = fopen(graft_file, "r"); |
| char buf[1024]; |
| if (!fp) |
| return -1; |
| while (fgets(buf, sizeof(buf), fp)) { |
| /* The format is just "Commit Parent1 Parent2 ...\n" */ |
| int len = strlen(buf); |
| struct commit_graft *graft = read_graft_line(buf, len); |
| if (!graft) |
| continue; |
| if (register_commit_graft(graft, 1)) |
| error("duplicate graft data: %s", buf); |
| } |
| fclose(fp); |
| return 0; |
| } |
| |
| static void prepare_commit_graft(void) |
| { |
| static int commit_graft_prepared; |
| char *graft_file; |
| |
| if (commit_graft_prepared) |
| return; |
| graft_file = get_graft_file(); |
| read_graft_file(graft_file); |
| /* make sure shallows are read */ |
| is_repository_shallow(); |
| commit_graft_prepared = 1; |
| } |
| |
| struct commit_graft *lookup_commit_graft(const unsigned char *sha1) |
| { |
| int pos; |
| prepare_commit_graft(); |
| pos = commit_graft_pos(sha1); |
| if (pos < 0) |
| return NULL; |
| return commit_graft[pos]; |
| } |
| |
| int write_shallow_commits(int fd, int use_pack_protocol) |
| { |
| int i, count = 0; |
| for (i = 0; i < commit_graft_nr; i++) |
| if (commit_graft[i]->nr_parent < 0) { |
| const char *hex = |
| sha1_to_hex(commit_graft[i]->sha1); |
| count++; |
| if (use_pack_protocol) |
| packet_write(fd, "shallow %s", hex); |
| else { |
| if (write_in_full(fd, hex, 40) != 40) |
| break; |
| if (write_in_full(fd, "\n", 1) != 1) |
| break; |
| } |
| } |
| return count; |
| } |
| |
| int unregister_shallow(const unsigned char *sha1) |
| { |
| int pos = commit_graft_pos(sha1); |
| if (pos < 0) |
| return -1; |
| if (pos + 1 < commit_graft_nr) |
| memcpy(commit_graft + pos, commit_graft + pos + 1, |
| sizeof(struct commit_graft *) |
| * (commit_graft_nr - pos - 1)); |
| commit_graft_nr--; |
| return 0; |
| } |
| |
| int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size) |
| { |
| char *tail = buffer; |
| char *bufptr = buffer; |
| unsigned char parent[20]; |
| struct commit_list **pptr; |
| struct commit_graft *graft; |
| |
| if (item->object.parsed) |
| return 0; |
| item->object.parsed = 1; |
| tail += size; |
| if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n') |
| return error("bogus commit object %s", sha1_to_hex(item->object.sha1)); |
| if (get_sha1_hex(bufptr + 5, parent) < 0) |
| return error("bad tree pointer in commit %s", |
| sha1_to_hex(item->object.sha1)); |
| item->tree = lookup_tree(parent); |
| bufptr += 46; /* "tree " + "hex sha1" + "\n" */ |
| pptr = &item->parents; |
| |
| graft = lookup_commit_graft(item->object.sha1); |
| while (bufptr + 48 < tail && !memcmp(bufptr, "parent ", 7)) { |
| struct commit *new_parent; |
| |
| if (tail <= bufptr + 48 || |
| get_sha1_hex(bufptr + 7, parent) || |
| bufptr[47] != '\n') |
| return error("bad parents in commit %s", sha1_to_hex(item->object.sha1)); |
| bufptr += 48; |
| /* |
| * The clone is shallow if nr_parent < 0, and we must |
| * not traverse its real parents even when we unhide them. |
| */ |
| if (graft && (graft->nr_parent < 0 || grafts_replace_parents)) |
| continue; |
| new_parent = lookup_commit(parent); |
| if (new_parent) |
| pptr = &commit_list_insert(new_parent, pptr)->next; |
| } |
| if (graft) { |
| int i; |
| struct commit *new_parent; |
| for (i = 0; i < graft->nr_parent; i++) { |
| new_parent = lookup_commit(graft->parent[i]); |
| if (!new_parent) |
| continue; |
| pptr = &commit_list_insert(new_parent, pptr)->next; |
| } |
| } |
| item->date = parse_commit_date(bufptr, tail); |
| |
| return 0; |
| } |
| |
| int parse_commit(struct commit *item) |
| { |
| enum object_type type; |
| void *buffer; |
| unsigned long size; |
| int ret; |
| |
| if (!item) |
| return -1; |
| if (item->object.parsed) |
| return 0; |
| buffer = read_sha1_file(item->object.sha1, &type, &size); |
| if (!buffer) |
| return error("Could not read %s", |
| sha1_to_hex(item->object.sha1)); |
| if (type != OBJ_COMMIT) { |
| free(buffer); |
| return error("Object %s not a commit", |
| sha1_to_hex(item->object.sha1)); |
| } |
| ret = parse_commit_buffer(item, buffer, size); |
| if (save_commit_buffer && !ret) { |
| item->buffer = buffer; |
| return 0; |
| } |
| free(buffer); |
| return ret; |
| } |
| |
| struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p) |
| { |
| struct commit_list *new_list = xmalloc(sizeof(struct commit_list)); |
| new_list->item = item; |
| new_list->next = *list_p; |
| *list_p = new_list; |
| return new_list; |
| } |
| |
| unsigned commit_list_count(const struct commit_list *l) |
| { |
| unsigned c = 0; |
| for (; l; l = l->next ) |
| c++; |
| return c; |
| } |
| |
| void free_commit_list(struct commit_list *list) |
| { |
| while (list) { |
| struct commit_list *temp = list; |
| list = temp->next; |
| free(temp); |
| } |
| } |
| |
| struct commit_list * insert_by_date(struct commit *item, struct commit_list **list) |
| { |
| struct commit_list **pp = list; |
| struct commit_list *p; |
| while ((p = *pp) != NULL) { |
| if (p->item->date < item->date) { |
| break; |
| } |
| pp = &p->next; |
| } |
| return commit_list_insert(item, pp); |
| } |
| |
| |
| void sort_by_date(struct commit_list **list) |
| { |
| struct commit_list *ret = NULL; |
| while (*list) { |
| insert_by_date((*list)->item, &ret); |
| *list = (*list)->next; |
| } |
| *list = ret; |
| } |
| |
| struct commit *pop_most_recent_commit(struct commit_list **list, |
| unsigned int mark) |
| { |
| struct commit *ret = (*list)->item; |
| struct commit_list *parents = ret->parents; |
| struct commit_list *old = *list; |
| |
| *list = (*list)->next; |
| free(old); |
| |
| while (parents) { |
| struct commit *commit = parents->item; |
| if (!parse_commit(commit) && !(commit->object.flags & mark)) { |
| commit->object.flags |= mark; |
| insert_by_date(commit, list); |
| } |
| parents = parents->next; |
| } |
| return ret; |
| } |
| |
| void clear_commit_marks(struct commit *commit, unsigned int mark) |
| { |
| while (commit) { |
| struct commit_list *parents; |
| |
| if (!(mark & commit->object.flags)) |
| return; |
| |
| commit->object.flags &= ~mark; |
| |
| parents = commit->parents; |
| if (!parents) |
| return; |
| |
| while ((parents = parents->next)) |
| clear_commit_marks(parents->item, mark); |
| |
| commit = commit->parents->item; |
| } |
| } |
| |
| struct commit *pop_commit(struct commit_list **stack) |
| { |
| struct commit_list *top = *stack; |
| struct commit *item = top ? top->item : NULL; |
| |
| if (top) { |
| *stack = top->next; |
| free(top); |
| } |
| return item; |
| } |
| |
| /* |
| * Performs an in-place topological sort on the list supplied. |
| */ |
| void sort_in_topological_order(struct commit_list ** list, int lifo) |
| { |
| struct commit_list *next, *orig = *list; |
| struct commit_list *work, **insert; |
| struct commit_list **pptr; |
| |
| if (!orig) |
| return; |
| *list = NULL; |
| |
| /* Mark them and clear the indegree */ |
| for (next = orig; next; next = next->next) { |
| struct commit *commit = next->item; |
| commit->indegree = 1; |
| } |
| |
| /* update the indegree */ |
| for (next = orig; next; next = next->next) { |
| struct commit_list * parents = next->item->parents; |
| while (parents) { |
| struct commit *parent = parents->item; |
| |
| if (parent->indegree) |
| parent->indegree++; |
| parents = parents->next; |
| } |
| } |
| |
| /* |
| * find the tips |
| * |
| * tips are nodes not reachable from any other node in the list |
| * |
| * the tips serve as a starting set for the work queue. |
| */ |
| work = NULL; |
| insert = &work; |
| for (next = orig; next; next = next->next) { |
| struct commit *commit = next->item; |
| |
| if (commit->indegree == 1) |
| insert = &commit_list_insert(commit, insert)->next; |
| } |
| |
| /* process the list in topological order */ |
| if (!lifo) |
| sort_by_date(&work); |
| |
| pptr = list; |
| *list = NULL; |
| while (work) { |
| struct commit *commit; |
| struct commit_list *parents, *work_item; |
| |
| work_item = work; |
| work = work_item->next; |
| work_item->next = NULL; |
| |
| commit = work_item->item; |
| for (parents = commit->parents; parents ; parents = parents->next) { |
| struct commit *parent=parents->item; |
| |
| if (!parent->indegree) |
| continue; |
| |
| /* |
| * parents are only enqueued for emission |
| * when all their children have been emitted thereby |
| * guaranteeing topological order. |
| */ |
| if (--parent->indegree == 1) { |
| if (!lifo) |
| insert_by_date(parent, &work); |
| else |
| commit_list_insert(parent, &work); |
| } |
| } |
| /* |
| * work_item is a commit all of whose children |
| * have already been emitted. we can emit it now. |
| */ |
| commit->indegree = 0; |
| *pptr = work_item; |
| pptr = &work_item->next; |
| } |
| } |
| |
| /* merge-base stuff */ |
| |
| /* bits #0..15 in revision.h */ |
| #define PARENT1 (1u<<16) |
| #define PARENT2 (1u<<17) |
| #define STALE (1u<<18) |
| #define RESULT (1u<<19) |
| |
| static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT); |
| |
| static struct commit *interesting(struct commit_list *list) |
| { |
| while (list) { |
| struct commit *commit = list->item; |
| list = list->next; |
| if (commit->object.flags & STALE) |
| continue; |
| return commit; |
| } |
| return NULL; |
| } |
| |
| static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos) |
| { |
| struct commit_list *list = NULL; |
| struct commit_list *result = NULL; |
| int i; |
| |
| for (i = 0; i < n; i++) { |
| if (one == twos[i]) |
| /* |
| * We do not mark this even with RESULT so we do not |
| * have to clean it up. |
| */ |
| return commit_list_insert(one, &result); |
| } |
| |
| if (parse_commit(one)) |
| return NULL; |
| for (i = 0; i < n; i++) { |
| if (parse_commit(twos[i])) |
| return NULL; |
| } |
| |
| one->object.flags |= PARENT1; |
| insert_by_date(one, &list); |
| for (i = 0; i < n; i++) { |
| twos[i]->object.flags |= PARENT2; |
| insert_by_date(twos[i], &list); |
| } |
| |
| while (interesting(list)) { |
| struct commit *commit; |
| struct commit_list *parents; |
| struct commit_list *next; |
| int flags; |
| |
| commit = list->item; |
| next = list->next; |
| free(list); |
| list = next; |
| |
| flags = commit->object.flags & (PARENT1 | PARENT2 | STALE); |
| if (flags == (PARENT1 | PARENT2)) { |
| if (!(commit->object.flags & RESULT)) { |
| commit->object.flags |= RESULT; |
| insert_by_date(commit, &result); |
| } |
| /* Mark parents of a found merge stale */ |
| flags |= STALE; |
| } |
| parents = commit->parents; |
| while (parents) { |
| struct commit *p = parents->item; |
| parents = parents->next; |
| if ((p->object.flags & flags) == flags) |
| continue; |
| if (parse_commit(p)) |
| return NULL; |
| p->object.flags |= flags; |
| insert_by_date(p, &list); |
| } |
| } |
| |
| /* Clean up the result to remove stale ones */ |
| free_commit_list(list); |
| list = result; result = NULL; |
| while (list) { |
| struct commit_list *next = list->next; |
| if (!(list->item->object.flags & STALE)) |
| insert_by_date(list->item, &result); |
| free(list); |
| list = next; |
| } |
| return result; |
| } |
| |
| struct commit_list *get_octopus_merge_bases(struct commit_list *in) |
| { |
| struct commit_list *i, *j, *k, *ret = NULL; |
| struct commit_list **pptr = &ret; |
| |
| for (i = in; i; i = i->next) { |
| if (!ret) |
| pptr = &commit_list_insert(i->item, pptr)->next; |
| else { |
| struct commit_list *new = NULL, *end = NULL; |
| |
| for (j = ret; j; j = j->next) { |
| struct commit_list *bases; |
| bases = get_merge_bases(i->item, j->item, 1); |
| if (!new) |
| new = bases; |
| else |
| end->next = bases; |
| for (k = bases; k; k = k->next) |
| end = k; |
| } |
| ret = new; |
| } |
| } |
| return ret; |
| } |
| |
| struct commit_list *get_merge_bases_many(struct commit *one, |
| int n, |
| struct commit **twos, |
| int cleanup) |
| { |
| struct commit_list *list; |
| struct commit **rslt; |
| struct commit_list *result; |
| int cnt, i, j; |
| |
| result = merge_bases_many(one, n, twos); |
| for (i = 0; i < n; i++) { |
| if (one == twos[i]) |
| return result; |
| } |
| if (!result || !result->next) { |
| if (cleanup) { |
| clear_commit_marks(one, all_flags); |
| for (i = 0; i < n; i++) |
| clear_commit_marks(twos[i], all_flags); |
| } |
| return result; |
| } |
| |
| /* There are more than one */ |
| cnt = 0; |
| list = result; |
| while (list) { |
| list = list->next; |
| cnt++; |
| } |
| rslt = xcalloc(cnt, sizeof(*rslt)); |
| for (list = result, i = 0; list; list = list->next) |
| rslt[i++] = list->item; |
| free_commit_list(result); |
| |
| clear_commit_marks(one, all_flags); |
| for (i = 0; i < n; i++) |
| clear_commit_marks(twos[i], all_flags); |
| for (i = 0; i < cnt - 1; i++) { |
| for (j = i+1; j < cnt; j++) { |
| if (!rslt[i] || !rslt[j]) |
| continue; |
| result = merge_bases_many(rslt[i], 1, &rslt[j]); |
| clear_commit_marks(rslt[i], all_flags); |
| clear_commit_marks(rslt[j], all_flags); |
| for (list = result; list; list = list->next) { |
| if (rslt[i] == list->item) |
| rslt[i] = NULL; |
| if (rslt[j] == list->item) |
| rslt[j] = NULL; |
| } |
| } |
| } |
| |
| /* Surviving ones in rslt[] are the independent results */ |
| result = NULL; |
| for (i = 0; i < cnt; i++) { |
| if (rslt[i]) |
| insert_by_date(rslt[i], &result); |
| } |
| free(rslt); |
| return result; |
| } |
| |
| struct commit_list *get_merge_bases(struct commit *one, struct commit *two, |
| int cleanup) |
| { |
| return get_merge_bases_many(one, 1, &two, cleanup); |
| } |
| |
| int is_descendant_of(struct commit *commit, struct commit_list *with_commit) |
| { |
| if (!with_commit) |
| return 1; |
| while (with_commit) { |
| struct commit *other; |
| |
| other = with_commit->item; |
| with_commit = with_commit->next; |
| if (in_merge_bases(other, &commit, 1)) |
| return 1; |
| } |
| return 0; |
| } |
| |
| int in_merge_bases(struct commit *commit, struct commit **reference, int num) |
| { |
| struct commit_list *bases, *b; |
| int ret = 0; |
| |
| if (num == 1) |
| bases = get_merge_bases(commit, *reference, 1); |
| else |
| die("not yet"); |
| for (b = bases; b; b = b->next) { |
| if (!hashcmp(commit->object.sha1, b->item->object.sha1)) { |
| ret = 1; |
| break; |
| } |
| } |
| |
| free_commit_list(bases); |
| return ret; |
| } |
| |
| struct commit_list *reduce_heads(struct commit_list *heads) |
| { |
| struct commit_list *p; |
| struct commit_list *result = NULL, **tail = &result; |
| struct commit **other; |
| size_t num_head, num_other; |
| |
| if (!heads) |
| return NULL; |
| |
| /* Avoid unnecessary reallocations */ |
| for (p = heads, num_head = 0; p; p = p->next) |
| num_head++; |
| other = xcalloc(sizeof(*other), num_head); |
| |
| /* For each commit, see if it can be reached by others */ |
| for (p = heads; p; p = p->next) { |
| struct commit_list *q, *base; |
| |
| /* Do we already have this in the result? */ |
| for (q = result; q; q = q->next) |
| if (p->item == q->item) |
| break; |
| if (q) |
| continue; |
| |
| num_other = 0; |
| for (q = heads; q; q = q->next) { |
| if (p->item == q->item) |
| continue; |
| other[num_other++] = q->item; |
| } |
| if (num_other) |
| base = get_merge_bases_many(p->item, num_other, other, 1); |
| else |
| base = NULL; |
| /* |
| * If p->item does not have anything common with other |
| * commits, there won't be any merge base. If it is |
| * reachable from some of the others, p->item will be |
| * the merge base. If its history is connected with |
| * others, but p->item is not reachable by others, we |
| * will get something other than p->item back. |
| */ |
| if (!base || (base->item != p->item)) |
| tail = &(commit_list_insert(p->item, tail)->next); |
| free_commit_list(base); |
| } |
| free(other); |
| return result; |
| } |