src/commit.c

   1 /*
   2  * This file is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License, version 2,
   4  * as published by the Free Software Foundation.
   5  *
   6  * In addition to the permissions in the GNU General Public License,
   7  * the authors give you unlimited permission to link the compiled
   8  * version of this file into combinations with other programs,
   9  * and to distribute those combinations without any restriction
  10  * coming from the use of this file.  (The General Public License
  11  * restrictions do apply in other respects; for example, they cover
  12  * modification of the file, and distribution when not linked into
  13  * a combined executable.)
  14  *
  15  * This file is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; see the file COPYING.  If not, write to
  22  * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  23  * Boston, MA 02110-1301, USA.
  24  */
  25
  26 #include <time.h>
  27
  28 #include "common.h"
  29 #include "commit.h"
  30 #include "revwalk.h"
  31 #include "git/odb.h"
  32
  33 #define COMMIT_PRINT(commit) {\
  34     char oid[41]; oid[40] = 0;\
  35     git_oid_fmt(oid, &commit->object.id);\
  36     printf("Oid: %s | In degree: %d | Time: %u\n", oid, commit->in_degree, commit->commit_time);\
  37 }
  38
  39 const git_oid *git_commit_id(git_commit *c)
  40 {
  41         return &c->object.id;
  42 }
  43
  44 void git_commit__mark_uninteresting(git_commit *commit)
  45 {
  46         if (commit == NULL)
  47                 return;
  48
  49         git_commit_node *parents = commit->parents.head;
  50
  51         commit->uninteresting = 1;
  52
  53         while (parents) {
  54                 parents->commit->uninteresting = 1;
  55                 parents = parents->next;
  56         }
  57 }
  58
  59 git_commit *git_commit_parse(git_revpool *pool, const git_oid *id)
  60 {
  61         git_commit *commit = NULL;
  62
  63         if ((commit = git_commit_lookup(pool, id)) == NULL)
  64                 return NULL;
  65
  66         if (git_commit_parse_existing(commit) < 0)
  67                 goto error_cleanup;
  68
  69         return commit;
  70
  71 error_cleanup:
  72         free(commit);
  73         return NULL;
  74 }
  75
  76 int git_commit_parse_existing(git_commit *commit)
  77 {
  78         git_obj commit_obj;
  79
  80         if (commit->parsed)
  81                 return 0;
  82
  83         if (git_odb_read(&commit_obj, commit->object.pool->db, &commit->object.id) < 0)
  84                 return GIT_ENOTFOUND;
  85
  86         if (commit_obj.type != GIT_OBJ_COMMIT)
  87                 goto error_cleanup;
  88
  89         if (git_commit__parse_buffer(commit, commit_obj.data, commit_obj.len) < 0)
  90                 goto error_cleanup;
  91
  92         git_obj_close(&commit_obj);
  93
  94         return 0;
  95
  96 error_cleanup:
  97         git_obj_close(&commit_obj);
  98         return -1;
  99 }
 100
 101 git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id)
 102 {
 103         git_commit *commit = NULL;
 104
 105         if (pool == NULL)
 106                 return NULL;
 107
 108         commit = (git_commit *)git_revpool_table_lookup(pool->commits, id);
 109         if (commit != NULL)
 110                 return commit;
 111
 112         commit = git__malloc(sizeof(git_commit));
 113
 114         if (commit == NULL)
 115                 return NULL;
 116
 117         memset(commit, 0x0, sizeof(git_commit));
 118
 119         // Initialize parent object
 120         git_oid_cpy(&commit->object.id, id);
 121         commit->object.pool = pool;
 122
 123         git_revpool_table_insert(pool->commits, (git_revpool_object *)commit);
 124
 125         return commit;
 126 }
 127
 128 int git_commit__parse_time(time_t *commit_time, char *buffer, const char *buffer_end)
 129 {
 130         if (memcmp(buffer, "author ", 7) != 0)
 131                 return GIT_EOBJCORRUPTED;
 132
 133         buffer = memchr(buffer, '\n', buffer_end - buffer);
 134         if (buffer == 0 || ++buffer >= buffer_end)
 135                 return GIT_EOBJCORRUPTED;
 136
 137         if (memcmp(buffer, "committer ", 10) != 0)
 138                 return GIT_EOBJCORRUPTED;
 139
 140         buffer = memchr(buffer, '>', buffer_end - buffer);
 141         if (buffer == 0 || ++buffer >= buffer_end)
 142                 return GIT_EOBJCORRUPTED;
 143
 144         *commit_time = strtol(buffer, &buffer, 10);
 145
 146         if (*commit_time == 0)
 147                 return GIT_EOBJCORRUPTED;
 148
 149         buffer = memchr(buffer, '\n', buffer_end - buffer);
 150         if (buffer == 0 || ++buffer >= buffer_end)
 151                 return GIT_EOBJCORRUPTED;
 152
 153         return (buffer < buffer_end) ? 0 : -1;
 154 }
 155
 156 int git_commit__parse_oid(git_oid *oid, char **buffer_out, const char *buffer_end, const char *header)
 157 {
 158         const size_t sha_len = GIT_OID_HEXSZ;
 159         const size_t header_len = strlen(header);
 160
 161         char *buffer = *buffer_out;
 162
 163         if (buffer + (header_len + sha_len + 1) > buffer_end)
 164                 return GIT_EOBJCORRUPTED;
 165
 166         if (memcmp(buffer, header, header_len) != 0)
 167                 return GIT_EOBJCORRUPTED;
 168
 169         if (buffer[header_len + sha_len] != '\n')
 170                 return GIT_EOBJCORRUPTED;
 171
 172         if (git_oid_mkstr(oid, buffer + header_len) < 0)
 173                 return GIT_EOBJCORRUPTED;
 174
 175         *buffer_out = buffer + (header_len + sha_len + 1);
 176
 177         return 0;
 178 }
 179
 180 int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
 181 {
 182         char *buffer = (char *)data;
 183         const char *buffer_end = (char *)data + len;
 184
 185         git_oid oid;
 186
 187         if (commit->parsed)
 188                 return 0;
 189
 190         if (git_commit__parse_oid(&oid, &buffer, buffer_end, "tree ") < 0)
 191                 return GIT_EOBJCORRUPTED;
 192
 193         /*
 194          * TODO: load tree into commit object
 195          * TODO: commit grafts!
 196          */
 197
 198         while (git_commit__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) {
 199                 git_commit *parent;
 200
 201                 if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL)
 202                         return GIT_ENOTFOUND;
 203
 204                 // Inherit uninteresting flag
 205                 if (commit->uninteresting)
 206                         parent->uninteresting = 1;
 207
 208                 git_commit_list_push_back(&commit->parents, parent);
 209         }
 210
 211         if (git_commit__parse_time(&commit->commit_time, buffer, buffer_end) < 0)
 212                 return GIT_EOBJCORRUPTED;
 213
 214         commit->parsed = 1;
 215
 216         return 0;
 217 }
 218
 219 int git_commit_list_push_back(git_commit_list *list, git_commit *commit)
 220 {
 221         git_commit_node *node = NULL;
 222
 223         node = git__malloc(sizeof(git_commit_list));
 224
 225         if (node == NULL)
 226                 return GIT_ENOMEM;
 227
 228         node->commit = commit;
 229         node->next = NULL;
 230         node->prev = list->tail;
 231
 232         if (list->tail == NULL) {
 233                 list->head = list->tail = node;
 234         } else {
 235                 list->tail->next = node;
 236                 list->tail = node;
 237         }
 238
 239         list->size++;
 240         return 0;
 241 }
 242
 243 int git_commit_list_push_front(git_commit_list *list, git_commit *commit)
 244 {
 245         git_commit_node *node = NULL;
 246
 247         node = git__malloc(sizeof(git_commit_list));
 248
 249         if (node == NULL)
 250                 return GIT_ENOMEM;
 251
 252         node->commit = commit;
 253         node->next = list->head;
 254         node->prev = NULL;
 255
 256         if (list->head == NULL) {
 257                 list->head = list->tail = node;
 258         } else {
 259                 list->head->prev = node;
 260                 list->head = node;
 261         }
 262
 263         list->size++;
 264         return 0;
 265 }
 266
 267
 268 git_commit *git_commit_list_pop_back(git_commit_list *list)
 269 {
 270         git_commit_node *node;
 271         git_commit *commit;
 272
 273         if (list->tail == NULL)
 274                 return NULL;
 275
 276         node = list->tail;
 277         list->tail = list->tail->prev;
 278         if (list->tail == NULL)
 279                 list->head = NULL;
 280
 281         commit = node->commit;
 282         free(node);
 283
 284         list->size--;
 285
 286         return commit;
 287 }
 288
 289 git_commit *git_commit_list_pop_front(git_commit_list *list)
 290 {
 291         git_commit_node *node;
 292         git_commit *commit;
 293
 294         if (list->head == NULL)
 295                 return NULL;
 296
 297         node = list->head;
 298         list->head = list->head->next;
 299         if (list->head == NULL)
 300                 list->tail = NULL;
 301
 302         commit = node->commit;
 303         free(node);
 304
 305         list->size--;
 306
 307         return commit;
 308 }
 309
 310 void git_commit_list_clear(git_commit_list *list, int free_commits)
 311 {
 312         git_commit_node *node, *next_node;
 313
 314         node = list->head;
 315         while (node) {
 316                 if (free_commits)
 317                         free(node->commit);
 318
 319                 next_node = node->next;
 320                 free(node);
 321                 node = next_node;
 322         }
 323
 324         list->head = list->tail = NULL;
 325         list->size = 0;
 326 }
 327
 328 void git_commit_list_timesort(git_commit_list *list)
 329 {
 330         git_commit_node *p, *q, *e;
 331         int in_size, p_size, q_size, merge_count, i;
 332
 333         if (list->head == NULL)
 334                 return;
 335
 336         in_size = 1;
 337
 338         do {
 339                 p = list->head;
 340                 list->tail = NULL;
 341                 merge_count = 0;
 342
 343                 while (p != NULL) {
 344                         merge_count++;
 345                         q = p;
 346                         p_size = 0;
 347                         q_size = in_size;
 348
 349                         for (i = 0; i < in_size && q; ++i, q = q->next)
 350                                 p_size++;
 351
 352                         while (p_size > 0 || (q_size > 0 && q)) {
 353
 354                                 if (p_size == 0)
 355                                         e = q, q = q->next, q_size--;
 356
 357                                 else if (q_size == 0 || q == NULL ||
 358                                                 p->commit->commit_time >= q->commit->commit_time)
 359                                         e = p, p = p->next, p_size--;
 360
 361                                 else
 362                                         e = q, q = q->next, q_size--;
 363
 364                                 if (list->tail != NULL)
 365                                         list->tail->next = e;
 366                                 else
 367                                         list->head = e;
 368
 369                                 e->prev = list->tail;
 370                                 list->tail = e;
 371                         }
 372
 373                         p = q;
 374                 }
 375
 376                 list->tail->next = NULL;
 377                 in_size *= 2;
 378
 379         } while (merge_count > 1);
 380 }
 381
 382 void git_commit_list_toposort(git_commit_list *list)
 383 {
 384         git_commit *commit;
 385         git_commit_list topo;
 386         memset(&topo, 0x0, sizeof(git_commit_list));
 387
 388         while ((commit = git_commit_list_pop_back(list)) != NULL) {
 389                 git_commit_node *p;
 390
 391                 if (commit->in_degree > 0) {
 392                         commit->topo_delay = 1;
 393                         continue;
 394                 }
 395
 396                 for (p = commit->parents.head; p != NULL; p = p->next) {
 397                         p->commit->in_degree--;
 398
 399                         if (p->commit->in_degree == 0 && p->commit->topo_delay) {
 400                                 p->commit->topo_delay = 0;
 401                                 git_commit_list_push_back(list, p->commit);
 402                         }
 403                 }
 404
 405                 git_commit_list_push_back(&topo, commit);
 406         }
 407
 408         list->head = topo.head;
 409         list->tail = topo.tail;
 410         list->size = topo.size;
 411 }
 412