repo_tree.c

   1 /******************************************************************************
   2  *
   3  * Copyright (C) 2010 David Barr <david.barr@cordelta.com>.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice(s), this list of conditions and the following disclaimer
  11  *    unmodified other than the allowable addition of one or more
  12  *    copyright notices.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice(s), this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  27  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  28  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  ******************************************************************************/
  31
  32 #include <string.h>
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <stdint.h>
  36 #include <time.h>
  37
  38 #include "string_pool.h"
  39 #include "repo_tree.h"
  40 #include "obj_pool.h"
  41
  42 typedef struct repo_dirent_s repo_dirent_t;
  43
  44 struct repo_dirent_s {
  45     uint32_t name_offset;
  46     uint32_t mode;
  47     uint32_t content_offset;
  48 };
  49
  50 typedef struct repo_dir_s repo_dir_t;
  51
  52 struct repo_dir_s {
  53     uint32_t size;
  54     uint32_t first_offset;
  55 };
  56
  57 typedef struct repo_commit_s repo_commit_t;
  58
  59 struct repo_commit_s {
  60     uint32_t mark;
  61     uint32_t root_dir_offset;
  62 };
  63
  64 obj_pool_gen(commit, repo_commit_t, 4096);
  65 obj_pool_gen(dir, repo_dir_t, 4096);
  66 obj_pool_gen(dirent, repo_dirent_t, 4096);
  67
  68 static uint32_t num_dirs_saved = 0;
  69 static uint32_t num_dirents_saved = 0;
  70 static uint32_t active_commit = -1;
  71
  72 static repo_dir_t *repo_commit_root_dir(repo_commit_t * commit)
  73 {
  74     return dir_pointer(commit->root_dir_offset);
  75 }
  76
  77 static repo_dirent_t *repo_first_dirent(repo_dir_t * dir)
  78 {
  79     return dirent_pointer(dir->first_offset);
  80 }
  81
  82 static int repo_dirent_name_cmp(const void *a, const void *b)
  83 {
  84     return (((repo_dirent_t *) a)->name_offset
  85             > ((repo_dirent_t *) b)->name_offset) -
  86         (((repo_dirent_t *) a)->name_offset
  87          < ((repo_dirent_t *) b)->name_offset);
  88 }
  89
  90 static repo_dirent_t *repo_dirent_by_name(repo_dir_t * dir,
  91                                           uint32_t name_offset)
  92 {
  93     repo_dirent_t key;
  94     if (dir == NULL || dir->size == 0)
  95         return NULL;
  96     key.name_offset = name_offset;
  97     return bsearch(&key, repo_first_dirent(dir), dir->size,
  98                    sizeof(repo_dirent_t), repo_dirent_name_cmp);
  99 }
 100
 101 static int repo_dirent_is_dir(repo_dirent_t * dirent)
 102 {
 103     return dirent != NULL && dirent->mode == REPO_MODE_DIR;
 104 }
 105
 106 static int repo_dirent_is_blob(repo_dirent_t * dirent)
 107 {
 108     return dirent->mode == REPO_MODE_BLB || dirent->mode == REPO_MODE_EXE;
 109 }
 110
 111 static int repo_dirent_is_executable(repo_dirent_t * dirent)
 112 {
 113     return dirent->mode == REPO_MODE_EXE;
 114 }
 115
 116 static int repo_dirent_is_symlink(repo_dirent_t * dirent)
 117 {
 118     return dirent->mode == REPO_MODE_LNK;
 119 }
 120
 121 static repo_dir_t *repo_dir_from_dirent(repo_dirent_t * dirent)
 122 {
 123     if (!repo_dirent_is_dir(dirent))
 124         return NULL;
 125     return dir_pointer(dirent->content_offset);
 126 }
 127
 128 static uint32_t dir_with_dirents_alloc(uint32_t size)
 129 {
 130     uint32_t offset = dir_alloc(1);
 131     dir_pointer(offset)->size = size;
 132     dir_pointer(offset)->first_offset = dirent_alloc(size);
 133     return offset;
 134 }
 135
 136 static repo_dir_t *repo_clone_dir(repo_dir_t * orig_dir, uint32_t padding)
 137 {
 138     uint32_t orig_o, new_o, dirent_o;
 139     orig_o = dir_offset(orig_dir);
 140     if (orig_o < num_dirs_saved) {
 141         new_o = dir_with_dirents_alloc(orig_dir->size + padding);
 142         orig_dir = dir_pointer(orig_o);
 143         dirent_o = dir_pointer(new_o)->first_offset;
 144     } else {
 145         if (padding == 0)
 146             return orig_dir;
 147         new_o = orig_o;
 148         dirent_o = dirent_alloc(orig_dir->size + padding);
 149     }
 150     memcpy(dirent_pointer(dirent_o), repo_first_dirent(orig_dir),
 151            orig_dir->size * sizeof(repo_dirent_t));
 152     dir_pointer(new_o)->size = orig_dir->size + padding;
 153     dir_pointer(new_o)->first_offset = dirent_o;
 154     return dir_pointer(new_o);
 155 }
 156
 157 static char repo_path_buffer[REPO_MAX_PATH_LEN];
 158 static repo_dirent_t *repo_read_dirent(uint32_t revision, char *path)
 159 {
 160     char *ctx = NULL;
 161     uint32_t name = 0;
 162     repo_dir_t *dir = NULL;
 163     repo_dirent_t *dirent = NULL;
 164     dir = repo_commit_root_dir(commit_pointer(revision));
 165     strncpy(repo_path_buffer, path, REPO_MAX_PATH_LEN);
 166     repo_path_buffer[REPO_MAX_PATH_LEN - 1] = '\0';
 167     path = repo_path_buffer;
 168     for (name = pool_tok_r(path, "/", &ctx);
 169          ~name; name = pool_tok_r(NULL, "/", &ctx)) {
 170         dirent = repo_dirent_by_name(dir, name);
 171         if (dirent == NULL) {
 172             return NULL;
 173         } else if (repo_dirent_is_dir(dirent)) {
 174             dir = repo_dir_from_dirent(dirent);
 175         } else {
 176             break;
 177         }
 178     }
 179     return dirent;
 180 }
 181
 182 static void
 183 repo_write_dirent(char *path, uint32_t mode, uint32_t content_offset,
 184                   uint32_t del)
 185 {
 186     char *ctx;
 187     uint32_t name, revision, dirent_o, dir_o, parent_dir_o;
 188     repo_dir_t *dir;
 189     repo_dirent_t *dirent = NULL;
 190     revision = active_commit;
 191     dir = repo_commit_root_dir(commit_pointer(revision));
 192     dir = repo_clone_dir(dir, 0);
 193     commit_pointer(revision)->root_dir_offset = dir_offset(dir);
 194     strncpy(repo_path_buffer, path, REPO_MAX_PATH_LEN);
 195     repo_path_buffer[REPO_MAX_PATH_LEN - 1] = '\0';
 196     path = repo_path_buffer;
 197     for (name = pool_tok_r(path, "/", &ctx); ~name;
 198          name = pool_tok_r(NULL, "/", &ctx)) {
 199         parent_dir_o = dir_offset(dir);
 200         dirent = repo_dirent_by_name(dir, name);
 201         if (dirent == NULL) {
 202             dir = repo_clone_dir(dir, 1);
 203             dirent = &repo_first_dirent(dir)[dir->size - 1];
 204             dirent->name_offset = name;
 205             dirent->mode = REPO_MODE_DIR;
 206             qsort(repo_first_dirent(dir), dir->size,
 207                   sizeof(repo_dirent_t), repo_dirent_name_cmp);
 208             dirent = repo_dirent_by_name(dir, name);
 209             dir_o = dir_with_dirents_alloc(0);
 210             dirent->content_offset = dir_o;
 211             dir = dir_pointer(dir_o);
 212         } else if (dir = repo_dir_from_dirent(dirent)) {
 213             dirent_o = dirent_offset(dirent);
 214             dir = repo_clone_dir(dir, 0);
 215             if (dirent_o != ~0)
 216                 dirent_pointer(dirent_o)->content_offset = dir_offset(dir);
 217         } else {
 218             dirent->mode = REPO_MODE_DIR;
 219             dirent_o = dirent_offset(dirent);
 220             dir_o = dir_with_dirents_alloc(0);
 221             dirent = dirent_pointer(dirent_o);
 222             dir = dir_pointer(dir_o);
 223             dirent->content_offset = dir_o;
 224         }
 225     }
 226     if (dirent) {
 227         dirent->mode = mode;
 228         dirent->content_offset = content_offset;
 229         if (del && ~parent_dir_o) {
 230             dirent->name_offset = ~0;
 231             dir = dir_pointer(parent_dir_o);
 232             qsort(repo_first_dirent(dir), dir->size,
 233                   sizeof(repo_dirent_t), repo_dirent_name_cmp);
 234             dir->size--;
 235         }
 236     }
 237 }
 238
 239 uint32_t repo_copy(uint32_t revision, char *src, char *dst)
 240 {
 241     uint32_t mode = 0, content_offset = 0;
 242     repo_dirent_t *src_dirent;
 243     fprintf(stderr, "C %d:%s %s\n", revision, src, dst);
 244     src_dirent = repo_read_dirent(revision, src);
 245     if (src_dirent != NULL) {
 246         mode = src_dirent->mode;
 247         content_offset = src_dirent->content_offset;
 248         repo_write_dirent(dst, mode, content_offset, 0);
 249     }
 250     return mode;
 251 }
 252
 253 void repo_add(char *path, uint32_t mode, uint32_t blob_mark)
 254 {
 255     fprintf(stderr, "A %s %d\n", path, blob_mark);
 256     repo_write_dirent(path, mode, blob_mark, 0);
 257 }
 258
 259 uint32_t repo_replace(char *path, uint32_t blob_mark)
 260 {
 261     uint32_t mode = 0;
 262     repo_dirent_t *src_dirent;
 263     src_dirent = repo_read_dirent(active_commit, path);
 264     if (src_dirent != NULL) {
 265         mode = src_dirent->mode;
 266         fprintf(stderr, "R %s %06o %d\n", path, mode, blob_mark);
 267         repo_write_dirent(path, mode, blob_mark, 0);
 268     }
 269     return mode;
 270 }
 271
 272 void repo_modify(char *path, uint32_t mode, uint32_t blob_mark)
 273 {
 274     fprintf(stderr, "M %s %d\n", path, blob_mark);
 275     repo_write_dirent(path, mode, blob_mark, 0);
 276 }
 277
 278 void repo_delete(char *path)
 279 {
 280     fprintf(stderr, "D %s\n", path);
 281     repo_write_dirent(path, 0, 0, 1);
 282 }
 283
 284 static void repo_print_path(uint32_t depth, uint32_t * path)
 285 {
 286     pool_print_seq(depth, path, '/', stdout);
 287 }
 288
 289 static void repo_git_delete(uint32_t depth, uint32_t * path)
 290 {
 291     putchar('D');
 292     putchar(' ');
 293     repo_print_path(depth, path);
 294     putchar('\n');
 295 }
 296
 297 static void
 298 repo_git_add_r(uint32_t depth, uint32_t * path, repo_dir_t * dir);
 299
 300 static void
 301 repo_git_add(uint32_t depth, uint32_t * path, repo_dirent_t * dirent)
 302 {
 303     if (repo_dirent_is_dir(dirent)) {
 304         repo_git_add_r(depth, path, repo_dir_from_dirent(dirent));
 305     } else {
 306         printf("M %06o :%d ", dirent->mode, dirent->content_offset);
 307         repo_print_path(depth, path);
 308         putchar('\n');
 309     }
 310 }
 311
 312 static void
 313 repo_git_add_r(uint32_t depth, uint32_t * path, repo_dir_t * dir)
 314 {
 315     uint32_t o;
 316     repo_dirent_t *de;
 317     de = repo_first_dirent(dir);
 318     for (o = 0; o < dir->size; o++) {
 319         path[depth] = de[o].name_offset;
 320         repo_git_add(depth + 1, path, &de[o]);
 321     }
 322 }
 323
 324 static void
 325 repo_diff_r(uint32_t depth, uint32_t * path, repo_dir_t * dir1,
 326             repo_dir_t * dir2)
 327 {
 328     uint32_t o1, o2, p;
 329     repo_dirent_t *de1, *de2;
 330     de1 = repo_first_dirent(dir1);
 331     de2 = repo_first_dirent(dir2);
 332     for (o1 = o2 = 0; o1 < dir1->size && o2 < dir2->size;) {
 333         if (de1[o1].name_offset < de2[o2].name_offset) {
 334             /* delete(o1) */
 335             path[depth] = de1[o1].name_offset;
 336             repo_git_delete(depth + 1, path);
 337             o1++;
 338         } else if (de1[o1].name_offset == de2[o2].name_offset) {
 339             path[depth] = de1[o1].name_offset;
 340             if (de1[o1].content_offset != de2[o2].content_offset) {
 341                 if (repo_dirent_is_dir(&de1[o1])
 342                     && repo_dirent_is_dir(&de2[o2])) {
 343                     /* recursive diff */
 344                     repo_diff_r(depth + 1, path,
 345                                 repo_dir_from_dirent(&de1[o1]),
 346                                 repo_dir_from_dirent(&de2[o2]));
 347                 } else {
 348                     /* delete o1, add o2 */
 349                     if (repo_dirent_is_dir(&de1[o1]) !=
 350                         repo_dirent_is_dir(&de2[o2])) {
 351                         repo_git_delete(depth + 1, path);
 352                     }
 353                     repo_git_add(depth + 1, path, &de2[o2]);
 354                 }
 355             }
 356             o1++;
 357             o2++;
 358         } else {
 359             /* add(o2) */
 360             path[depth] = de2[o2].name_offset;
 361             repo_git_add(depth + 1, path, &de2[o2]);
 362             o2++;
 363         }
 364     }
 365     for (; o1 < dir1->size; o1++) {
 366         /* delete(o1) */
 367         path[depth] = de1[o1].name_offset;
 368         repo_git_delete(depth + 1, path);
 369     }
 370     for (; o2 < dir2->size; o2++) {
 371         /* add(o2) */
 372         path[depth] = de2[o2].name_offset;
 373         repo_git_add(depth + 1, path, &de2[o2]);
 374     }
 375 }
 376
 377 static uint32_t path_stack[1000];
 378 static void repo_diff(uint32_t r1, uint32_t r2)
 379 {
 380     repo_diff_r(0,
 381                 path_stack,
 382                 repo_commit_root_dir(commit_pointer(r1)),
 383                 repo_commit_root_dir(commit_pointer(r2)));
 384 }
 385
 386 static char gitsvnline[4096];
 387
 388 static void repo_git_commit(uint32_t revision, char * author, char * log,
 389                             char * uuid, char * url, time_t timestamp)
 390 {
 391     printf("commit refs/heads/master\nmark :%d\n", revision);
 392     printf("committer %s <%s@%s> %ld +0000\n",
 393          author, author, uuid ? uuid : "local", timestamp);
 394     if (uuid && url) {
 395         snprintf(gitsvnline, 4096, "\n\ngit-svn-id: %s@%d %s\n",
 396              url, revision, uuid);
 397     } else {
 398         *gitsvnline = '\0';
 399     }
 400     printf("data %ld\n%s%s\n",
 401            strlen(log) + strlen(gitsvnline), log, gitsvnline);
 402     repo_diff(revision - 1, revision);
 403     fputc('\n', stdout);
 404
 405     printf("progress Imported commit %d.\n\n", revision);
 406 }
 407
 408 void repo_commit(uint32_t revision, char * author, char * log, char * uuid,
 409                  char * url, time_t timestamp)
 410 {
 411     fprintf(stderr, "R %d\n", revision);
 412     if (revision == 0) {
 413         active_commit = commit_alloc(1);
 414         commit_pointer(active_commit)->root_dir_offset =
 415             dir_with_dirents_alloc(0);
 416     } else {
 417         repo_git_commit(revision, author, log, uuid, url, timestamp);
 418     }
 419     num_dirs_saved = dir_pool.size;
 420     num_dirents_saved = dirent_pool.size;
 421     active_commit = commit_alloc(1);
 422     commit_pointer(active_commit)->root_dir_offset =
 423         commit_pointer(active_commit - 1)->root_dir_offset;
 424 }
 425
 426 void repo_copy_blob(uint32_t mode, uint32_t mark, uint32_t len)
 427 {
 428     if (mode == REPO_MODE_LNK) {
 429         /* svn symlink blobs start with "link " */
 430         buffer_skip_bytes(5);
 431         len -= 5;
 432     }
 433     printf("blob\nmark :%d\ndata %d\n", mark, len);
 434     buffer_copy_bytes(len);
 435     fputc('\n', stdout);
 436 }