#include "common.h"

#include "commit.h"

#include "odb.h"

#include "hashtable.h"

#include "pqueue.h"

#include "git2/revwalk.h"

typedef struct commit_object {

} commit_object;

typedef struct commit_list {

commit_object *item;

struct commit_list *next;

} commit_list;

struct git_revwalk {

};

static commit_list *commit_list_insert(commit_object *item, commit_list **list_p)

{

commit_list *new_list = git__malloc(sizeof(commit_list));

new_list->item = item;

new_list->next = *list_p;

*list_p = new_list;

return new_list;

}

static void commit_list_free(commit_list **list_p)

{

commit_list *list = *list_p;

while (list) {

commit_list *temp = list;

list = temp->next;

git__free(temp);

}

*list_p = NULL;

}

static commit_object *commit_list_pop(commit_list **stack)

{

commit_list *top = *stack;

commit_object *item = top ? top->item : NULL;

if (top) {

*stack = top->next;

git__free(top);

}

return item;

}

static int commit_time_cmp(void *a, void *b)

{

commit_object *commit_a = (commit_object *)a;

commit_object *commit_b = (commit_object *)b;

return (commit_a->time < commit_b->time);

}

static uint32_t object_table_hash(const void *key, int hash_id)

{

uint32_t r;

const git_oid *id = key;

memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));

return r;

}

#define COMMITS_PER_CHUNK 128

#define CHUNK_STEP 64

#define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *))

static int alloc_chunk(git_revwalk *walk)

{

void *chunk;

chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP);

if (chunk == NULL)

return GIT_ENOMEM;

walk->chunk_size = 0;

return git_vector_insert(&walk->memory_alloc, chunk);

}

static commit_object *alloc_commit(git_revwalk *walk)

{

unsigned char *chunk;

if (walk->chunk_size == COMMITS_PER_CHUNK)

alloc_chunk(walk);

chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1);

chunk += (walk->chunk_size * CHUNK_STEP);

walk->chunk_size++;

return (commit_object *)chunk;

}

static commit_object **alloc_parents(commit_object *commit, size_t n_parents)

{

if (n_parents <= PARENTS_PER_COMMIT)

return (commit_object **)((unsigned char *)commit + sizeof(commit_object));

return git__malloc(n_parents * sizeof(commit_object *));

}

static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)

{

commit_object *commit;

if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)

return commit;

commit = alloc_commit(walk);

if (commit == NULL)

return NULL;

git_oid_cpy(&commit->oid, oid);

if (git_hashtable_insert(walk->commits, &commit->oid, commit) < GIT_SUCCESS) {

git__free(commit);

return NULL;

}

return commit;

}

static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)

{

const int parent_len = strlen("parent ") + GIT_OID_HEXSZ + 1;

unsigned char *buffer = raw->data;

unsigned char *buffer_end = buffer + raw->len;

unsigned char *parents_start;

int i, parents = 0;

int commit_time;

buffer += strlen("tree ") + GIT_OID_HEXSZ + 1;

parents_start = buffer;

while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", strlen("parent ")) == 0) {

parents++;

buffer += parent_len;

}

commit->parents = alloc_parents(commit, parents);

if (commit->parents == NULL)

return GIT_ENOMEM;

buffer = parents_start;

for (i = 0; i < parents; ++i) {

git_oid oid;

if (git_oid_fromstr(&oid, (char *)buffer + strlen("parent ")) < GIT_SUCCESS)

return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Parent object is corrupted");

commit->parents[i] = commit_lookup(walk, &oid);

if (commit->parents[i] == NULL)

return GIT_ENOMEM;

buffer += parent_len;

}

commit->out_degree = (unsigned short)parents;

if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)

return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Object is corrupted");

buffer = memchr(buffer, '>', buffer_end - buffer);

if (buffer == NULL)

return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Can't find author");

if (git__strtol32(&commit_time, (char *)buffer + 2, NULL, 10) < GIT_SUCCESS)

return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Can't parse commit time");

commit->time = (time_t)commit_time;

commit->parsed = 1;

return GIT_SUCCESS;

}

static int commit_parse(git_revwalk *walk, commit_object *commit)

{

git_odb_object *obj;

int error;

if (commit->parsed)

return GIT_SUCCESS;

if ((error = git_odb_read(&obj, walk->repo->db, &commit->oid)) < GIT_SUCCESS)

return git__rethrow(error, "Failed to parse commit. Can't read object");

if (obj->raw.type != GIT_OBJ_COMMIT) {

git_odb_object_close(obj);

return git__throw(GIT_EOBJTYPE, "Failed to parse commit. Object is no commit object");

}

error = commit_quick_parse(walk, commit, &obj->raw);

git_odb_object_close(obj);

return error == GIT_SUCCESS ? GIT_SUCCESS : git__rethrow(error, "Failed to parse commit");

}

static void mark_uninteresting(commit_object *commit)

{

unsigned short i;

assert(commit);

commit->uninteresting = 1;

for (i = 0; i < commit->out_degree; ++i)

if (!commit->parents[i]->uninteresting)

mark_uninteresting(commit->parents[i]);

}

static int process_commit(git_revwalk *walk, commit_object *commit, int hide)

{

int error;

if (hide)

mark_uninteresting(commit);

if (commit->seen)

return GIT_SUCCESS;

commit->seen = 1;

if ((error = commit_parse(walk, commit)) < GIT_SUCCESS)

return git__rethrow(error, "Failed to process commit");

return walk->enqueue(walk, commit);

}

static int process_commit_parents(git_revwalk *walk, commit_object *commit)

{

unsigned short i;

int error = GIT_SUCCESS;

for (i = 0; i < commit->out_degree && error == GIT_SUCCESS; ++i) {

error = process_commit(walk, commit->parents[i], commit->uninteresting);

}

return error == GIT_SUCCESS ? GIT_SUCCESS : git__rethrow(error, "Failed to process commit parents");

}

static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)

{

commit_object *commit;

commit = commit_lookup(walk, oid);

if (commit == NULL)

return git__throw(GIT_ENOTFOUND, "Failed to push commit. Object not found");

return process_commit(walk, commit, uninteresting);

}

int git_revwalk_push(git_revwalk *walk, const git_oid *oid)

{

assert(walk && oid);

return push_commit(walk, oid, 0);

}

int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)

{

assert(walk && oid);

return push_commit(walk, oid, 1);

}

static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)

{

return git_pqueue_insert(&walk->iterator_time, commit);

}

static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)

{

return commit_list_insert(commit, &walk->iterator_rand) ? GIT_SUCCESS : GIT_ENOMEM;

}

static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)

{

int error;

commit_object *next;

while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {

if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)

return git__rethrow(error, "Failed to load next revision");

if (!next->uninteresting) {

*object_out = next;

return GIT_SUCCESS;

}

}

return git__throw(GIT_EREVWALKOVER, "Failed to load next revision");

}

static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)

{

int error;

commit_object *next;

while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {

if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)

return git__rethrow(error, "Failed to load next revision");

if (!next->uninteresting) {

*object_out = next;

return GIT_SUCCESS;

}

}

return git__throw(GIT_EREVWALKOVER, "Failed to load next revision");

}

static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)

{

commit_object *next;

unsigned short i;

for (;;) {

next = commit_list_pop(&walk->iterator_topo);

if (next == NULL)

return git__throw(GIT_EREVWALKOVER, "Failed to load next revision");

if (next->in_degree > 0) {

next->topo_delay = 1;

continue;

}

for (i = 0; i < next->out_degree; ++i) {

commit_object *parent = next->parents[i];

if (--parent->in_degree == 0 && parent->topo_delay) {

parent->topo_delay = 0;

commit_list_insert(parent, &walk->iterator_topo);

}

}

*object_out = next;

return GIT_SUCCESS;

}

}

static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)

{

*object_out = commit_list_pop(&walk->iterator_reverse);

return *object_out ? GIT_SUCCESS : GIT_EREVWALKOVER;

}

static int prepare_walk(git_revwalk *walk)

{

int error;

commit_object *next;

if (walk->sorting & GIT_SORT_TOPOLOGICAL) {

unsigned short i;

while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) {

for (i = 0; i < next->out_degree; ++i) {

commit_object *parent = next->parents[i];

parent->in_degree++;

}

commit_list_insert(next, &walk->iterator_topo);

}

if (error != GIT_EREVWALKOVER)

return git__rethrow(error, "Failed to prepare revision walk");

walk->get_next = &revwalk_next_toposort;

}

if (walk->sorting & GIT_SORT_REVERSE) {

while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS)

commit_list_insert(next, &walk->iterator_reverse);

if (error != GIT_EREVWALKOVER)

return git__rethrow(error, "Failed to prepare revision walk");

walk->get_next = &revwalk_next_reverse;

}

walk->walking = 1;

return GIT_SUCCESS;

}

int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)

{

git_revwalk *walk;

walk = git__malloc(sizeof(git_revwalk));

if (walk == NULL)

return GIT_ENOMEM;

memset(walk, 0x0, sizeof(git_revwalk));

walk->commits = git_hashtable_alloc(64,

object_table_hash,

(git_hash_keyeq_ptr)git_oid_cmp);

if (walk->commits == NULL) {

git__free(walk);

return GIT_ENOMEM;

}

git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp);

git_vector_init(&walk->memory_alloc, 8, NULL);

alloc_chunk(walk);

walk->get_next = &revwalk_next_unsorted;

walk->enqueue = &revwalk_enqueue_unsorted;

walk->repo = repo;

*revwalk_out = walk;

return GIT_SUCCESS;

}

void git_revwalk_free(git_revwalk *walk)

{

unsigned int i;

const void *GIT_UNUSED(_unused);

commit_object *commit;

if (walk == NULL)

return;

git_revwalk_reset(walk);

/* if the parent has more than PARENTS_PER_COMMIT parents,

GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit, {

if (commit->out_degree > PARENTS_PER_COMMIT)

git__free(commit->parents);

});

git_hashtable_free(walk->commits);

git_pqueue_free(&walk->iterator_time);

for (i = 0; i < walk->memory_alloc.length; ++i)

git__free(git_vector_get(&walk->memory_alloc, i));

git_vector_free(&walk->memory_alloc);

git__free(walk);

}

git_repository *git_revwalk_repository(git_revwalk *walk)

{

assert(walk);

return walk->repo;

}

void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)

{

assert(walk);

if (walk->walking)

git_revwalk_reset(walk);

walk->sorting = sort_mode;

if (walk->sorting & GIT_SORT_TIME) {

walk->get_next = &revwalk_next_timesort;

walk->enqueue = &revwalk_enqueue_timesort;

} else {

walk->get_next = &revwalk_next_unsorted;

walk->enqueue = &revwalk_enqueue_unsorted;

}

}

int git_revwalk_next(git_oid *oid, git_revwalk *walk)

{

int error;

commit_object *next;

assert(walk && oid);

if (!walk->walking) {

if ((error = prepare_walk(walk)) < GIT_SUCCESS)

return git__rethrow(error, "Failed to load next revision");

}

error = walk->get_next(&next, walk);

if (error == GIT_EREVWALKOVER) {

git_revwalk_reset(walk);

return GIT_EREVWALKOVER;

}

if (error < GIT_SUCCESS)

return git__rethrow(error, "Failed to load next revision");

git_oid_cpy(oid, &next->oid);

return GIT_SUCCESS;

}

void git_revwalk_reset(git_revwalk *walk)

{

const void *GIT_UNUSED(_unused);

commit_object *commit;

assert(walk);

GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit,

commit->seen = 0;

commit->in_degree = 0;

commit->topo_delay = 0;

);

git_pqueue_clear(&walk->iterator_time);

commit_list_free(&walk->iterator_topo);

commit_list_free(&walk->iterator_rand);

commit_list_free(&walk->iterator_reverse);

walk->walking = 0;

}