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 const git_oid *git_commit_id(git_commit *c)
  34 {
  35         return &c->object.id;
  36 }
  37
  38 void git_commit__mark_uninteresting(git_commit *commit)
  39 {
  40     if (commit == NULL)
  41         return;
  42
  43         git_commit_node *parents = commit->parents.head;
  44
  45     commit->uninteresting = 1;
  46
  47         while (parents)
  48     {
  49         parents->commit->uninteresting = 1;
  50                 parents = parents->next;
  51         }
  52 }
  53
  54 git_commit *git_commit_parse(git_revpool *pool, const git_oid *id)
  55 {
  56     git_commit *commit = NULL;
  57
  58     if ((commit = git_commit_lookup(pool, id)) == NULL)
  59         return NULL;
  60
  61     if (git_commit_parse_existing(commit) < 0)
  62         goto error_cleanup;
  63
  64     return commit;
  65
  66 error_cleanup:
  67     free(commit);
  68     return NULL;
  69 }
  70
  71 int git_commit_parse_existing(git_commit *commit)
  72 {
  73     git_obj commit_obj;
  74
  75     if (commit->parsed)
  76         return 0;
  77
  78     if (git_odb_read(&commit_obj, commit->object.pool->db, &commit->object.id) < 0)
  79         return -1;
  80
  81     if (commit_obj.type != GIT_OBJ_COMMIT)
  82         goto error_cleanup;
  83
  84     if (git_commit__parse_buffer(commit, commit_obj.data, commit_obj.len) < 0)
  85         goto error_cleanup;
  86
  87     git_obj_close(&commit_obj);
  88
  89     return 0;
  90
  91 error_cleanup:
  92     git_obj_close(&commit_obj);
  93     return -1;
  94 }
  95
  96 git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id)
  97 {
  98     git_commit *commit = NULL;
  99
 100     if (pool == NULL)
 101         return NULL;
 102
 103     commit = (git_commit *)git_revpool_table_lookup(pool->commits, id);
 104     if (commit != NULL)
 105         return commit;
 106
 107     commit = git__malloc(sizeof(git_commit));
 108
 109     if (commit == NULL)
 110         return NULL;
 111
 112     memset(commit, 0x0, sizeof(git_commit));
 113
 114     // Initialize parent object
 115     git_oid_cpy(&commit->object.id, id);
 116     commit->object.pool = pool;
 117
 118     git_revpool_table_insert(pool->commits, (git_revpool_object *)commit);
 119
 120     return commit;
 121 }
 122
 123 int git_commit__parse_time(time_t *commit_time, char *buffer, const char *buffer_end)
 124 {
 125     if (memcmp(buffer, "author ", 7) != 0)
 126         return -1;
 127
 128     buffer = memchr(buffer, '\n', buffer_end - buffer);
 129     if (buffer == 0 || ++buffer >= buffer_end)
 130         return -1;
 131
 132     if (memcmp(buffer, "committer ", 10) != 0)
 133         return -1;
 134
 135     buffer = memchr(buffer, '\n', buffer_end - buffer);
 136     if (buffer == 0 || ++buffer >= buffer_end)
 137         return -1;
 138
 139     *commit_time = strtol(buffer, &buffer, 10);
 140
 141     return (buffer < buffer_end) ? 0 : -1;
 142 }
 143
 144 int git_commit__parse_oid(git_oid *oid, char **buffer_out, const char *buffer_end, const char *header)
 145 {
 146     const size_t sha_len = GIT_OID_HEXSZ;
 147     const size_t header_len = strlen(header);
 148
 149     char *buffer = *buffer_out;
 150
 151     if (buffer + (header_len + sha_len + 1) > buffer_end)
 152         return -1;
 153
 154     if (memcmp(buffer, header, header_len) != 0)
 155         return -1;
 156
 157     if (buffer[header_len + sha_len] != '\n')
 158         return -1;
 159
 160     if (git_oid_mkstr(oid, buffer + header_len) < 0)
 161         return -1;
 162
 163     *buffer_out = buffer + (header_len + sha_len + 1);
 164
 165     return 0;
 166 }
 167
 168 int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
 169 {
 170     char *buffer = (char *)data;
 171     const char *buffer_end = (char *)data + len;
 172
 173     git_oid oid;
 174
 175     if (commit->parsed)
 176                 return 0;
 177
 178     if (git_commit__parse_oid(&oid, &buffer, buffer_end, "tree ") < 0)
 179         return -1;
 180
 181     /*
 182      * TODO: load tree into commit object
 183      * TODO: commit grafts!
 184      */
 185
 186     while (git_commit__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) {
 187         git_commit *parent;
 188
 189         if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL)
 190             return -1;
 191
 192         // Inherit uninteresting flag
 193         if (commit->uninteresting)
 194             parent->uninteresting = 1;
 195
 196         git_commit_list_push_back(&commit->parents, parent);
 197     }
 198
 199     if (git_commit__parse_time(&commit->commit_time, buffer, buffer_end) < 0)
 200         return -1;
 201
 202     commit->parsed = 1;
 203
 204     return 0;
 205 }
 206
 207 void git_commit_list_push_back(git_commit_list *list, git_commit *commit)
 208 {
 209     git_commit_node *node = NULL;
 210
 211     node = git__malloc(sizeof(git_commit_list));
 212
 213     if (node == NULL)
 214         return;
 215
 216     node->commit = commit;
 217     node->next = NULL;
 218     node->prev = list->tail;
 219
 220     if (list->tail == NULL)
 221     {
 222         list->head = list->tail = node;
 223     }
 224     else
 225     {
 226         list->tail->next = node;
 227         list->tail = node;
 228     }
 229
 230     list->size++;
 231 }
 232
 233 void git_commit_list_push_front(git_commit_list *list, git_commit *commit)
 234 {
 235     git_commit_node *node = NULL;
 236
 237     node = git__malloc(sizeof(git_commit_list));
 238
 239     if (node == NULL)
 240         return;
 241
 242     node->commit = commit;
 243     node->next = list->head;
 244     node->prev = NULL;
 245
 246     if (list->head == NULL)
 247     {
 248         list->head = list->tail = node;
 249     }
 250     else
 251     {
 252         list->head->next = node;
 253         list->head = node;
 254     }
 255
 256     list->size++;
 257 }
 258
 259
 260 git_commit *git_commit_list_pop_back(git_commit_list *list)
 261 {
 262     git_commit_node *node;
 263     git_commit *commit;
 264
 265     if (list->tail == NULL)
 266         return NULL;
 267
 268     node = list->tail;
 269     list->tail = list->tail->prev;
 270     if (list->tail == NULL)
 271         list->head = NULL;
 272
 273     commit = node->commit;
 274     free(node);
 275
 276     list->size--;
 277
 278     return commit;
 279 }
 280
 281 git_commit *git_commit_list_pop_front(git_commit_list *list)
 282 {
 283     git_commit_node *node;
 284     git_commit *commit;
 285
 286     if (list->head == NULL)
 287         return NULL;
 288
 289     node = list->head;
 290     list->head = list->head->next;
 291     if (list->head == NULL)
 292         list->tail = NULL;
 293
 294     commit = node->commit;
 295     free(node);
 296
 297     list->size--;
 298
 299     return commit;
 300 }
 301
 302 void git_commit_list_clear(git_commit_list *list, int free_commits)
 303 {
 304     git_commit_node *node, *next_node;
 305
 306     node = list->head;
 307     while (node)
 308     {
 309         if (free_commits)
 310             free(node->commit);
 311
 312         next_node = node->next;
 313         free(node);
 314         node = next_node;
 315     }
 316
 317     list->head = list->tail = NULL;
 318     list->size = 0;
 319 }
 320
 321 void git_commit_list_timesort(git_commit_list *list)
 322 {
 323     git_commit_node *p, *q, *e;
 324     int in_size, p_size, q_size, merge_count, i;
 325
 326     if (list->head == NULL)
 327         return;
 328
 329     in_size = 1;
 330
 331     do
 332     {
 333         p = list->head;
 334         list->tail = NULL;
 335         merge_count = 0;
 336
 337         while (p != NULL)
 338         {
 339             merge_count++;
 340             q = p;
 341             p_size = 0;
 342             q_size = in_size;
 343
 344             for (i = 0; i < in_size && q; ++i, q = q->next)
 345                 p_size++;
 346
 347             while (p_size > 0 || (q_size > 0 && q))
 348             {
 349                 if (p_size == 0)
 350                     e = q, q = q->next, q_size--;
 351
 352                 else if (q_size == 0 || q == NULL ||
 353                     p->commit->commit_time >= q->commit->commit_time)
 354                     e = p, p = p->next, p_size--;
 355
 356                 else
 357                     e = q, q = q->next, q_size--;
 358
 359                 if (list->tail != NULL)
 360                     list->tail->next = e;
 361                 else
 362                     list->head = e;
 363
 364                 list->tail = e;
 365             }
 366
 367             p = q;
 368         }
 369
 370         list->tail->next = NULL;
 371         in_size *= 2;
 372
 373     } while (merge_count > 1);
 374 }
 375
 376 void git_commit_list_toposort(git_commit_list *list)
 377 {
 378     git_commit *commit;
 379     git_commit_list topo;
 380     memset(&topo, 0x0, sizeof(git_commit_list));
 381
 382     while ((commit = git_commit_list_pop_front(list)) != NULL)
 383     {
 384         git_commit_node *p;
 385
 386         if (commit->in_degree > 0)
 387         {
 388             commit->topo_delay = 1;
 389             continue;
 390         }
 391
 392         for (p = commit->parents.head; p != NULL; p = p->next)
 393         {
 394             p->commit->in_degree--;
 395
 396             if (p->commit->in_degree == 0 && p->commit->topo_delay)
 397             {
 398                 p->commit->topo_delay = 0;
 399                 git_commit_list_push_front(list, p->commit);
 400             }
 401         }
 402
 403         git_commit_list_push_back(&topo, commit);
 404     }
 405
 406     list->head = topo.head;
 407     list->tail = topo.tail;
 408     list->size = topo.size;
 409 }