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