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 "common.h"
  27 #include "commit.h"
  28 #include "revwalk.h"
  29 #include "git/odb.h"
  30
  31 #define COMMIT_PRINT(commit) {\
  32     char oid[41]; oid[40] = 0;\
  33     git_oid_fmt(oid, &commit->object.id);\
  34     printf("Oid: %s | In degree: %d | Time: %u\n", oid, commit->in_degree, commit->commit_time);\
  35 }
  36
  37 const git_oid *git_commit_id(git_commit *c)
  38 {
  39         return &c->object.id;
  40 }
  41
  42 void git_commit__mark_uninteresting(git_commit *commit)
  43 {
  44         git_commit_node *parents;
  45
  46         if (commit == NULL)
  47                 return;
  48
  49         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         int error = 0;
  79         git_obj commit_obj;
  80
  81         if (commit->parsed)
  82                 return 0;
  83
  84         error = git_odb_read(&commit_obj, commit->object.pool->db, &commit->object.id);
  85         if (error < 0)
  86                 return error;
  87
  88         if (commit_obj.type != GIT_OBJ_COMMIT) {
  89                 error = GIT_EOBJTYPE;
  90                 goto cleanup;
  91         }
  92
  93         error = git_commit__parse_buffer(commit, commit_obj.data, commit_obj.len);
  94
  95 cleanup:
  96         git_obj_close(&commit_obj);
  97         return error;
  98 }
  99
 100 git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id)
 101 {
 102         git_commit *commit = NULL;
 103
 104         if (pool == NULL)
 105                 return NULL;
 106
 107         commit = (git_commit *)git_revpool_table_lookup(pool->commits, id);
 108         if (commit != NULL)
 109                 return commit;
 110
 111         commit = git__malloc(sizeof(git_commit));
 112
 113         if (commit == NULL)
 114                 return NULL;
 115
 116         memset(commit, 0x0, sizeof(git_commit));
 117
 118         // Initialize parent object
 119         git_oid_cpy(&commit->object.id, id);
 120         commit->object.pool = pool;
 121
 122         git_revpool_table_insert(pool->commits, (git_revpool_object *)commit);
 123
 124         return commit;
 125 }
 126
 127 int git_commit__parse_time(time_t *commit_time, char *buffer, const char *buffer_end)
 128 {
 129         if (memcmp(buffer, "author ", 7) != 0)
 130                 return GIT_EOBJCORRUPTED;
 131
 132         buffer = memchr(buffer, '\n', buffer_end - buffer);
 133         if (!buffer || ++buffer >= buffer_end)
 134                 return GIT_EOBJCORRUPTED;
 135
 136         if (memcmp(buffer, "committer ", 10) != 0)
 137                 return GIT_EOBJCORRUPTED;
 138
 139         buffer = memchr(buffer, '>', buffer_end - buffer);
 140         if (!buffer || ++buffer >= buffer_end)
 141                 return GIT_EOBJCORRUPTED;
 142
 143         *commit_time = strtol(buffer, &buffer, 10);
 144
 145         if (*commit_time == 0)
 146                 return GIT_EOBJCORRUPTED;
 147
 148         buffer = memchr(buffer, '\n', buffer_end - buffer);
 149         if (!buffer || ++buffer >= buffer_end)
 150                 return GIT_EOBJCORRUPTED;
 151
 152         return (buffer < buffer_end) ? 0 : -1;
 153 }
 154
 155 int git_commit__parse_oid(git_oid *oid, char **buffer_out, const char *buffer_end, const char *header)
 156 {
 157         const size_t sha_len = GIT_OID_HEXSZ;
 158         const size_t header_len = strlen(header);
 159
 160         char *buffer = *buffer_out;
 161
 162         if (buffer + (header_len + sha_len + 1) > buffer_end)
 163                 return GIT_EOBJCORRUPTED;
 164
 165         if (memcmp(buffer, header, header_len) != 0)
 166                 return GIT_EOBJCORRUPTED;
 167
 168         if (buffer[header_len + sha_len] != '\n')
 169                 return GIT_EOBJCORRUPTED;
 170
 171         if (git_oid_mkstr(oid, buffer + header_len) < 0)
 172                 return GIT_EOBJCORRUPTED;
 173
 174         *buffer_out = buffer + (header_len + sha_len + 1);
 175
 176         return 0;
 177 }
 178
 179 int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
 180 {
 181         char *buffer = (char *)data;
 182         const char *buffer_end = (char *)data + len;
 183
 184         git_oid oid;
 185
 186         if (commit->parsed)
 187                 return 0;
 188
 189         if (git_commit__parse_oid(&oid, &buffer, buffer_end, "tree ") < 0)
 190                 return GIT_EOBJCORRUPTED;
 191
 192         /*
 193          * TODO: load tree into commit object
 194          * TODO: commit grafts!
 195          */
 196
 197         while (git_commit__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) {
 198                 git_commit *parent;
 199
 200                 if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL)
 201                         return GIT_ENOTFOUND;
 202
 203                 // Inherit uninteresting flag
 204                 if (commit->uninteresting)
 205                         parent->uninteresting = 1;
 206
 207                 if (git_commit_list_push_back(&commit->parents, parent))
 208                         return GIT_ENOMEM;
 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