src/tree-cache.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "tree-cache.h"
   9 #include "pool.h"
  10 #include "tree.h"
  11
  12 static git_tree_cache *find_child(
  13         const git_tree_cache *tree, const char *path, const char *end)
  14 {
  15         size_t i, dirlen = end ? (size_t)(end - path) : strlen(path);
  16
  17         for (i = 0; i < tree->children_count; ++i) {
  18                 git_tree_cache *child = tree->children[i];
  19
  20                 if (child->namelen == dirlen && !memcmp(path, child->name, dirlen))
  21                         return child;
  22         }
  23
  24         return NULL;
  25 }
  26
  27 void git_tree_cache_invalidate_path(git_tree_cache *tree, const char *path)
  28 {
  29         const char *ptr = path, *end;
  30
  31         if (tree == NULL)
  32                 return;
  33
  34         tree->entry_count = -1;
  35
  36         while (ptr != NULL) {
  37                 end = strchr(ptr, '/');
  38
  39                 if (end == NULL) /* End of path */
  40                         break;
  41
  42                 tree = find_child(tree, ptr, end);
  43                 if (tree == NULL) /* We don't have that tree */
  44                         return;
  45
  46                 tree->entry_count = -1;
  47                 ptr = end + 1;
  48         }
  49 }
  50
  51 const git_tree_cache *git_tree_cache_get(const git_tree_cache *tree, const char *path)
  52 {
  53         const char *ptr = path, *end;
  54
  55         if (tree == NULL) {
  56                 return NULL;
  57         }
  58
  59         while (1) {
  60                 end = strchr(ptr, '/');
  61
  62                 tree = find_child(tree, ptr, end);
  63                 if (tree == NULL) /* Can't find it */
  64                         return NULL;
  65
  66                 if (end == NULL || *end + 1 == '\0')
  67                         return tree;
  68
  69                 ptr = end + 1;
  70         }
  71 }
  72
  73 static int read_tree_internal(git_tree_cache **out,
  74                               const char **buffer_in, const char *buffer_end,
  75                               git_pool *pool)
  76 {
  77         git_tree_cache *tree = NULL;
  78         const char *name_start, *buffer;
  79         int count;
  80
  81         buffer = name_start = *buffer_in;
  82
  83         if ((buffer = memchr(buffer, '\0', buffer_end - buffer)) == NULL)
  84                 goto corrupted;
  85
  86         if (++buffer >= buffer_end)
  87                 goto corrupted;
  88
  89         if (git_tree_cache_new(&tree, name_start, pool) < 0)
  90                 return -1;
  91
  92         /* Blank-terminated ASCII decimal number of entries in this tree */
  93         if (git__strtol32(&count, buffer, &buffer, 10) < 0)
  94                 goto corrupted;
  95
  96         tree->entry_count = count;
  97
  98         if (*buffer != ' ' || ++buffer >= buffer_end)
  99                 goto corrupted;
 100
 101          /* Number of children of the tree, newline-terminated */
 102         if (git__strtol32(&count, buffer, &buffer, 10) < 0 || count < 0)
 103                 goto corrupted;
 104
 105         tree->children_count = count;
 106
 107         if (*buffer != '\n' || ++buffer > buffer_end)
 108                 goto corrupted;
 109
 110         /* The SHA1 is only there if it's not invalidated */
 111         if (tree->entry_count >= 0) {
 112                 /* 160-bit SHA-1 for this tree and it's children */
 113                 if (buffer + GIT_OID_RAWSZ > buffer_end)
 114                         goto corrupted;
 115
 116                 git_oid_fromraw(&tree->oid, (const unsigned char *)buffer);
 117                 buffer += GIT_OID_RAWSZ;
 118         }
 119
 120         /* Parse children: */
 121         if (tree->children_count > 0) {
 122                 unsigned int i;
 123
 124                 tree->children = git_pool_malloc(pool, tree->children_count * sizeof(git_tree_cache *));
 125                 GITERR_CHECK_ALLOC(tree->children);
 126
 127                 memset(tree->children, 0x0, tree->children_count * sizeof(git_tree_cache *));
 128
 129                 for (i = 0; i < tree->children_count; ++i) {
 130                         if (read_tree_internal(&tree->children[i], &buffer, buffer_end, pool) < 0)
 131                                 goto corrupted;
 132                 }
 133         }
 134
 135         *buffer_in = buffer;
 136         *out = tree;
 137         return 0;
 138
 139  corrupted:
 140         giterr_set(GITERR_INDEX, "Corrupted TREE extension in index");
 141         return -1;
 142 }
 143
 144 int git_tree_cache_read(git_tree_cache **tree, const char *buffer, size_t buffer_size, git_pool *pool)
 145 {
 146         const char *buffer_end = buffer + buffer_size;
 147
 148         if (read_tree_internal(tree, &buffer, buffer_end, pool) < 0)
 149                 return -1;
 150
 151         if (buffer < buffer_end) {
 152                 giterr_set(GITERR_INDEX, "Corrupted TREE extension in index (unexpected trailing data)");
 153                 return -1;
 154         }
 155
 156         return 0;
 157 }
 158
 159 static int read_tree_recursive(git_tree_cache *cache, const git_tree *tree, git_pool *pool)
 160 {
 161         git_repository *repo;
 162         size_t i, j, nentries, ntrees;
 163         int error;
 164
 165         repo = git_tree_owner(tree);
 166
 167         git_oid_cpy(&cache->oid, git_tree_id(tree));
 168         nentries = git_tree_entrycount(tree);
 169
 170         /*
 171          * We make sure we know how many trees we need to allocate for
 172          * so we don't have to realloc and change the pointers for the
 173          * parents.
 174          */
 175         ntrees = 0;
 176         for (i = 0; i < nentries; i++) {
 177                 const git_tree_entry *entry;
 178
 179                 entry = git_tree_entry_byindex(tree, i);
 180                 if (git_tree_entry_filemode(entry) == GIT_FILEMODE_TREE)
 181                         ntrees++;
 182         }
 183
 184         cache->children_count = ntrees;
 185         cache->children = git_pool_mallocz(pool, ntrees * sizeof(git_tree_cache *));
 186         GITERR_CHECK_ALLOC(cache->children);
 187
 188         j = 0;
 189         for (i = 0; i < nentries; i++) {
 190                 const git_tree_entry *entry;
 191                 git_tree *subtree;
 192
 193                 entry = git_tree_entry_byindex(tree, i);
 194                 if (git_tree_entry_filemode(entry) != GIT_FILEMODE_TREE)
 195                         continue;
 196
 197                 if ((error = git_tree_cache_new(&cache->children[j], git_tree_entry_name(entry), pool)) < 0)
 198                         return error;
 199
 200                 if ((error = git_tree_lookup(&subtree, repo, git_tree_entry_id(entry))) < 0)
 201                         return error;
 202
 203                 error = read_tree_recursive(cache->children[j], subtree, pool);
 204                 git_tree_free(subtree);
 205                 j++;
 206
 207                 if (error < 0)
 208                         return error;
 209         }
 210
 211         return 0;
 212 }
 213
 214 int git_tree_cache_read_tree(git_tree_cache **out, const git_tree *tree, git_pool *pool)
 215 {
 216         int error;
 217         git_tree_cache *cache;
 218
 219         if ((error = git_tree_cache_new(&cache, "", pool)) < 0)
 220                 return error;
 221
 222         if ((error = read_tree_recursive(cache, tree, pool)) < 0)
 223                 return error;
 224
 225         *out = cache;
 226         return 0;
 227 }
 228
 229 int git_tree_cache_new(git_tree_cache **out, const char *name, git_pool *pool)
 230 {
 231         size_t name_len;
 232         git_tree_cache *tree;
 233
 234         name_len = strlen(name);
 235         tree = git_pool_malloc(pool, sizeof(git_tree_cache) + name_len + 1);
 236         GITERR_CHECK_ALLOC(tree);
 237
 238         memset(tree, 0x0, sizeof(git_tree_cache));
 239         /* NUL-terminated tree name */
 240         tree->namelen = name_len;
 241         memcpy(tree->name, name, name_len);
 242         tree->name[name_len] = '\0';
 243
 244         *out = tree;
 245         return 0;
 246 }
 247
 248 /**
 249  * Recursively recalculate the total entry count, which we need to
 250  * write out to the index
 251  */
 252 static void recount_entries(git_tree_cache *tree)
 253 {
 254         size_t i;
 255         ssize_t entry_count;
 256         git_tree_cache *child;
 257
 258         for (i = 0; i < tree->children_count; i++)
 259                 recount_entries(tree->children[i]);
 260
 261         if (tree->entry_count == -1)
 262                 return;
 263
 264         entry_count = 0;
 265         for (i = 0; i < tree->children_count; i++) {
 266                 child = tree->children[i];
 267
 268                 if (child->entry_count == -1)
 269                         continue;
 270
 271                 entry_count += tree->children[i]->children_count;
 272         }
 273
 274         tree->entry_count = entry_count;
 275 }
 276
 277 static void write_tree(git_buf *out, git_tree_cache *tree)
 278 {
 279         size_t i;
 280
 281         git_buf_printf(out, "%s%c%"PRIdZ" %"PRIuZ"\n", tree->name, 0, tree->entry_count, tree->children_count);
 282
 283         if (tree->entry_count != -1)
 284                 git_buf_put(out, (const char *) &tree->oid, GIT_OID_RAWSZ);
 285
 286         for (i = 0; i < tree->children_count; i++)
 287                 write_tree(out, tree->children[i]);
 288 }
 289
 290 int git_tree_cache_write(git_buf *out, git_tree_cache *tree)
 291 {
 292         recount_entries(tree);
 293         write_tree(out, tree);
 294
 295         return git_buf_oom(out) ? -1 : 0;
 296 }