src/refdb_fs.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 "refdb_fs.h"
   9
  10 #include "refs.h"
  11 #include "hash.h"
  12 #include "repository.h"
  13 #include "fileops.h"
  14 #include "filebuf.h"
  15 #include "pack.h"
  16 #include "reflog.h"
  17 #include "refdb.h"
  18 #include "iterator.h"
  19 #include "sortedcache.h"
  20 #include "signature.h"
  21
  22 #include <git2/tag.h>
  23 #include <git2/object.h>
  24 #include <git2/refdb.h>
  25 #include <git2/branch.h>
  26 #include <git2/sys/refdb_backend.h>
  27 #include <git2/sys/refs.h>
  28 #include <git2/sys/reflog.h>
  29
  30 #define DEFAULT_NESTING_LEVEL   5
  31 #define MAX_NESTING_LEVEL               10
  32
  33 enum {
  34         PACKREF_HAS_PEEL = 1,
  35         PACKREF_WAS_LOOSE = 2,
  36         PACKREF_CANNOT_PEEL = 4,
  37         PACKREF_SHADOWED = 8,
  38 };
  39
  40 enum {
  41         PEELING_NONE = 0,
  42         PEELING_STANDARD,
  43         PEELING_FULL
  44 };
  45
  46 struct packref {
  47         git_oid oid;
  48         git_oid peel;
  49         char flags;
  50         char name[GIT_FLEX_ARRAY];
  51 };
  52
  53 typedef struct refdb_fs_backend {
  54         git_refdb_backend parent;
  55
  56         git_repository *repo;
  57         /* path to git directory */
  58         char *gitpath;
  59         /* path to common objects' directory */
  60         char *commonpath;
  61
  62         git_sortedcache *refcache;
  63         int peeling_mode;
  64         git_iterator_flag_t iterator_flags;
  65         uint32_t direach_flags;
  66         int fsync;
  67 } refdb_fs_backend;
  68
  69 static int refdb_reflog_fs__delete(git_refdb_backend *_backend, const char *name);
  70
  71 static int packref_cmp(const void *a_, const void *b_)
  72 {
  73         const struct packref *a = a_, *b = b_;
  74         return strcmp(a->name, b->name);
  75 }
  76
  77 static int packed_reload(refdb_fs_backend *backend)
  78 {
  79         int error;
  80         git_buf packedrefs = GIT_BUF_INIT;
  81         char *scan, *eof, *eol;
  82
  83         if (!backend->gitpath)
  84                 return 0;
  85
  86         error = git_sortedcache_lockandload(backend->refcache, &packedrefs);
  87
  88         /*
  89          * If we can't find the packed-refs, clear table and return.
  90          * Any other error just gets passed through.
  91          * If no error, and file wasn't changed, just return.
  92          * Anything else means we need to refresh the packed refs.
  93          */
  94         if (error <= 0) {
  95                 if (error == GIT_ENOTFOUND) {
  96                         git_sortedcache_clear(backend->refcache, true);
  97                         giterr_clear();
  98                         error = 0;
  99                 }
 100                 return error;
 101         }
 102
 103         /* At this point, refresh the packed refs from the loaded buffer. */
 104
 105         git_sortedcache_clear(backend->refcache, false);
 106
 107         scan = (char *)packedrefs.ptr;
 108         eof  = scan + packedrefs.size;
 109
 110         backend->peeling_mode = PEELING_NONE;
 111
 112         if (*scan == '#') {
 113                 static const char *traits_header = "# pack-refs with: ";
 114
 115                 if (git__prefixcmp(scan, traits_header) == 0) {
 116                         scan += strlen(traits_header);
 117                         eol = strchr(scan, '\n');
 118
 119                         if (!eol)
 120                                 goto parse_failed;
 121                         *eol = '\0';
 122
 123                         if (strstr(scan, " fully-peeled ") != NULL) {
 124                                 backend->peeling_mode = PEELING_FULL;
 125                         } else if (strstr(scan, " peeled ") != NULL) {
 126                                 backend->peeling_mode = PEELING_STANDARD;
 127                         }
 128
 129                         scan = eol + 1;
 130                 }
 131         }
 132
 133         while (scan < eof && *scan == '#') {
 134                 if (!(eol = strchr(scan, '\n')))
 135                         goto parse_failed;
 136                 scan = eol + 1;
 137         }
 138
 139         while (scan < eof) {
 140                 struct packref *ref;
 141                 git_oid oid;
 142
 143                 /* parse "<OID> <refname>\n" */
 144
 145                 if (git_oid_fromstr(&oid, scan) < 0)
 146                         goto parse_failed;
 147                 scan += GIT_OID_HEXSZ;
 148
 149                 if (*scan++ != ' ')
 150                         goto parse_failed;
 151                 if (!(eol = strchr(scan, '\n')))
 152                         goto parse_failed;
 153                 *eol = '\0';
 154                 if (eol[-1] == '\r')
 155                         eol[-1] = '\0';
 156
 157                 if (git_sortedcache_upsert((void **)&ref, backend->refcache, scan) < 0)
 158                         goto parse_failed;
 159                 scan = eol + 1;
 160
 161                 git_oid_cpy(&ref->oid, &oid);
 162
 163                 /* look for optional "^<OID>\n" */
 164
 165                 if (*scan == '^') {
 166                         if (git_oid_fromstr(&oid, scan + 1) < 0)
 167                                 goto parse_failed;
 168                         scan += GIT_OID_HEXSZ + 1;
 169
 170                         if (scan < eof) {
 171                                 if (!(eol = strchr(scan, '\n')))
 172                                         goto parse_failed;
 173                                 scan = eol + 1;
 174                         }
 175
 176                         git_oid_cpy(&ref->peel, &oid);
 177                         ref->flags |= PACKREF_HAS_PEEL;
 178                 }
 179                 else if (backend->peeling_mode == PEELING_FULL ||
 180                                 (backend->peeling_mode == PEELING_STANDARD &&
 181                                  git__prefixcmp(ref->name, GIT_REFS_TAGS_DIR) == 0))
 182                         ref->flags |= PACKREF_CANNOT_PEEL;
 183         }
 184
 185         git_sortedcache_wunlock(backend->refcache);
 186         git_buf_free(&packedrefs);
 187
 188         return 0;
 189
 190 parse_failed:
 191         giterr_set(GITERR_REFERENCE, "corrupted packed references file");
 192
 193         git_sortedcache_clear(backend->refcache, false);
 194         git_sortedcache_wunlock(backend->refcache);
 195         git_buf_free(&packedrefs);
 196
 197         return -1;
 198 }
 199
 200 static int loose_parse_oid(
 201         git_oid *oid, const char *filename, git_buf *file_content)
 202 {
 203         const char *str = git_buf_cstr(file_content);
 204
 205         if (git_buf_len(file_content) < GIT_OID_HEXSZ)
 206                 goto corrupted;
 207
 208         /* we need to get 40 OID characters from the file */
 209         if (git_oid_fromstr(oid, str) < 0)
 210                 goto corrupted;
 211
 212         /* If the file is longer than 40 chars, the 41st must be a space */
 213         str += GIT_OID_HEXSZ;
 214         if (*str == '\0' || git__isspace(*str))
 215                 return 0;
 216
 217 corrupted:
 218         giterr_set(GITERR_REFERENCE, "corrupted loose reference file: %s", filename);
 219         return -1;
 220 }
 221
 222 static int loose_readbuffer(git_buf *buf, const char *base, const char *path)
 223 {
 224         int error;
 225
 226         /* build full path to file */
 227         if ((error = git_buf_joinpath(buf, base, path)) < 0 ||
 228                 (error = git_futils_readbuffer(buf, buf->ptr)) < 0)
 229                 git_buf_free(buf);
 230
 231         return error;
 232 }
 233
 234 static int loose_lookup_to_packfile(refdb_fs_backend *backend, const char *name)
 235 {
 236         int error = 0;
 237         git_buf ref_file = GIT_BUF_INIT;
 238         struct packref *ref = NULL;
 239         git_oid oid;
 240
 241         /* if we fail to load the loose reference, assume someone changed
 242          * the filesystem under us and skip it...
 243          */
 244         if (loose_readbuffer(&ref_file, backend->gitpath, name) < 0) {
 245                 giterr_clear();
 246                 goto done;
 247         }
 248
 249         /* skip symbolic refs */
 250         if (!git__prefixcmp(git_buf_cstr(&ref_file), GIT_SYMREF))
 251                 goto done;
 252
 253         /* parse OID from file */
 254         if ((error = loose_parse_oid(&oid, name, &ref_file)) < 0)
 255                 goto done;
 256
 257         git_sortedcache_wlock(backend->refcache);
 258
 259         if (!(error = git_sortedcache_upsert(
 260                         (void **)&ref, backend->refcache, name))) {
 261
 262                 git_oid_cpy(&ref->oid, &oid);
 263                 ref->flags = PACKREF_WAS_LOOSE;
 264         }
 265
 266         git_sortedcache_wunlock(backend->refcache);
 267
 268 done:
 269         git_buf_free(&ref_file);
 270         return error;
 271 }
 272
 273 static int _dirent_loose_load(void *payload, git_buf *full_path)
 274 {
 275         refdb_fs_backend *backend = payload;
 276         const char *file_path;
 277
 278         if (git__suffixcmp(full_path->ptr, ".lock") == 0)
 279                 return 0;
 280
 281         if (git_path_isdir(full_path->ptr)) {
 282                 int error = git_path_direach(
 283                         full_path, backend->direach_flags, _dirent_loose_load, backend);
 284                 /* Race with the filesystem, ignore it */
 285                 if (error == GIT_ENOTFOUND) {
 286                         giterr_clear();
 287                         return 0;
 288                 }
 289
 290                 return error;
 291         }
 292
 293         file_path = full_path->ptr + strlen(backend->gitpath);
 294
 295         return loose_lookup_to_packfile(backend, file_path);
 296 }
 297
 298 /*
 299  * Load all the loose references from the repository
 300  * into the in-memory Packfile, and build a vector with
 301  * all the references so it can be written back to
 302  * disk.
 303  */
 304 static int packed_loadloose(refdb_fs_backend *backend)
 305 {
 306         int error;
 307         git_buf refs_path = GIT_BUF_INIT;
 308
 309         if (git_buf_joinpath(&refs_path, backend->gitpath, GIT_REFS_DIR) < 0)
 310                 return -1;
 311
 312         /*
 313          * Load all the loose files from disk into the Packfile table.
 314          * This will overwrite any old packed entries with their
 315          * updated loose versions
 316          */
 317         error = git_path_direach(
 318                 &refs_path, backend->direach_flags, _dirent_loose_load, backend);
 319
 320         git_buf_free(&refs_path);
 321
 322         return error;
 323 }
 324
 325 static int refdb_fs_backend__exists(
 326         int *exists,
 327         git_refdb_backend *_backend,
 328         const char *ref_name)
 329 {
 330         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 331         git_buf ref_path = GIT_BUF_INIT;
 332         int error;
 333
 334         assert(backend);
 335
 336         if ((error = packed_reload(backend)) < 0 ||
 337                 (error = git_buf_joinpath(&ref_path, backend->gitpath, ref_name)) < 0)
 338                 return error;
 339
 340         *exists = git_path_isfile(ref_path.ptr) ||
 341                 (git_sortedcache_lookup(backend->refcache, ref_name) != NULL);
 342
 343         git_buf_free(&ref_path);
 344         return 0;
 345 }
 346
 347 static const char *loose_parse_symbolic(git_buf *file_content)
 348 {
 349         const unsigned int header_len = (unsigned int)strlen(GIT_SYMREF);
 350         const char *refname_start;
 351
 352         refname_start = (const char *)file_content->ptr;
 353
 354         if (git_buf_len(file_content) < header_len + 1) {
 355                 giterr_set(GITERR_REFERENCE, "corrupted loose reference file");
 356                 return NULL;
 357         }
 358
 359         /*
 360          * Assume we have already checked for the header
 361          * before calling this function
 362          */
 363         refname_start += header_len;
 364
 365         return refname_start;
 366 }
 367
 368 /*
 369  * Returns whether a reference is stored per worktree or not.
 370  * Per-worktree references are:
 371  *
 372  * - all pseudorefs, e.g. HEAD and MERGE_HEAD
 373  * - all references stored inside of "refs/bisect/"
 374  */
 375 static bool is_per_worktree_ref(const char *ref_name)
 376 {
 377         return git__prefixcmp(ref_name, "refs/") != 0 ||
 378             git__prefixcmp(ref_name, "refs/bisect/") == 0;
 379 }
 380
 381 static int loose_lookup(
 382         git_reference **out,
 383         refdb_fs_backend *backend,
 384         const char *ref_name)
 385 {
 386         git_buf ref_file = GIT_BUF_INIT;
 387         int error = 0;
 388         const char *ref_dir;
 389
 390         if (out)
 391                 *out = NULL;
 392
 393         if (is_per_worktree_ref(ref_name))
 394                 ref_dir = backend->gitpath;
 395         else
 396                 ref_dir = backend->commonpath;
 397
 398         if ((error = loose_readbuffer(&ref_file, ref_dir, ref_name)) < 0)
 399                 /* cannot read loose ref file - gah */;
 400         else if (git__prefixcmp(git_buf_cstr(&ref_file), GIT_SYMREF) == 0) {
 401                 const char *target;
 402
 403                 git_buf_rtrim(&ref_file);
 404
 405                 if (!(target = loose_parse_symbolic(&ref_file)))
 406                         error = -1;
 407                 else if (out != NULL)
 408                         *out = git_reference__alloc_symbolic(ref_name, target);
 409         } else {
 410                 git_oid oid;
 411
 412                 if (!(error = loose_parse_oid(&oid, ref_name, &ref_file)) &&
 413                         out != NULL)
 414                         *out = git_reference__alloc(ref_name, &oid, NULL);
 415         }
 416
 417         git_buf_free(&ref_file);
 418         return error;
 419 }
 420
 421 static int ref_error_notfound(const char *name)
 422 {
 423         giterr_set(GITERR_REFERENCE, "reference '%s' not found", name);
 424         return GIT_ENOTFOUND;
 425 }
 426
 427 static int packed_lookup(
 428         git_reference **out,
 429         refdb_fs_backend *backend,
 430         const char *ref_name)
 431 {
 432         int error = 0;
 433         struct packref *entry;
 434
 435         if ((error = packed_reload(backend)) < 0)
 436                 return error;
 437
 438         if (git_sortedcache_rlock(backend->refcache) < 0)
 439                 return -1;
 440
 441         entry = git_sortedcache_lookup(backend->refcache, ref_name);
 442         if (!entry) {
 443                 error = ref_error_notfound(ref_name);
 444         } else {
 445                 *out = git_reference__alloc(ref_name, &entry->oid, &entry->peel);
 446                 if (!*out)
 447                         error = -1;
 448         }
 449
 450         git_sortedcache_runlock(backend->refcache);
 451
 452         return error;
 453 }
 454
 455 static int refdb_fs_backend__lookup(
 456         git_reference **out,
 457         git_refdb_backend *_backend,
 458         const char *ref_name)
 459 {
 460         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 461         int error;
 462
 463         assert(backend);
 464
 465         if (!(error = loose_lookup(out, backend, ref_name)))
 466                 return 0;
 467
 468         /* only try to lookup this reference on the packfile if it
 469          * wasn't found on the loose refs; not if there was a critical error */
 470         if (error == GIT_ENOTFOUND) {
 471                 giterr_clear();
 472                 error = packed_lookup(out, backend, ref_name);
 473         }
 474
 475         return error;
 476 }
 477
 478 typedef struct {
 479         git_reference_iterator parent;
 480
 481         char *glob;
 482
 483         git_pool pool;
 484         git_vector loose;
 485
 486         git_sortedcache *cache;
 487         size_t loose_pos;
 488         size_t packed_pos;
 489 } refdb_fs_iter;
 490
 491 static void refdb_fs_backend__iterator_free(git_reference_iterator *_iter)
 492 {
 493         refdb_fs_iter *iter = (refdb_fs_iter *) _iter;
 494
 495         git_vector_free(&iter->loose);
 496         git_pool_clear(&iter->pool);
 497         git_sortedcache_free(iter->cache);
 498         git__free(iter);
 499 }
 500
 501 static int iter_load_loose_paths(refdb_fs_backend *backend, refdb_fs_iter *iter)
 502 {
 503         int error = 0;
 504         git_buf path = GIT_BUF_INIT;
 505         git_iterator *fsit = NULL;
 506         git_iterator_options fsit_opts = GIT_ITERATOR_OPTIONS_INIT;
 507         const git_index_entry *entry = NULL;
 508
 509         if (!backend->commonpath) /* do nothing if no commonpath for loose refs */
 510                 return 0;
 511
 512         fsit_opts.flags = backend->iterator_flags;
 513
 514         if ((error = git_buf_printf(&path, "%s/refs", backend->commonpath)) < 0 ||
 515                 (error = git_iterator_for_filesystem(&fsit, path.ptr, &fsit_opts)) < 0) {
 516                 git_buf_free(&path);
 517                 return error;
 518         }
 519
 520         error = git_buf_sets(&path, GIT_REFS_DIR);
 521
 522         while (!error && !git_iterator_advance(&entry, fsit)) {
 523                 const char *ref_name;
 524                 struct packref *ref;
 525                 char *ref_dup;
 526
 527                 git_buf_truncate(&path, strlen(GIT_REFS_DIR));
 528                 git_buf_puts(&path, entry->path);
 529                 ref_name = git_buf_cstr(&path);
 530
 531                 if (git__suffixcmp(ref_name, ".lock") == 0 ||
 532                         (iter->glob && p_fnmatch(iter->glob, ref_name, 0) != 0))
 533                         continue;
 534
 535                 git_sortedcache_rlock(backend->refcache);
 536                 ref = git_sortedcache_lookup(backend->refcache, ref_name);
 537                 if (ref)
 538                         ref->flags |= PACKREF_SHADOWED;
 539                 git_sortedcache_runlock(backend->refcache);
 540
 541                 ref_dup = git_pool_strdup(&iter->pool, ref_name);
 542                 if (!ref_dup)
 543                         error = -1;
 544                 else
 545                         error = git_vector_insert(&iter->loose, ref_dup);
 546         }
 547
 548         git_iterator_free(fsit);
 549         git_buf_free(&path);
 550
 551         return error;
 552 }
 553
 554 static int refdb_fs_backend__iterator_next(
 555         git_reference **out, git_reference_iterator *_iter)
 556 {
 557         int error = GIT_ITEROVER;
 558         refdb_fs_iter *iter = (refdb_fs_iter *)_iter;
 559         refdb_fs_backend *backend = (refdb_fs_backend *)iter->parent.db->backend;
 560         struct packref *ref;
 561
 562         while (iter->loose_pos < iter->loose.length) {
 563                 const char *path = git_vector_get(&iter->loose, iter->loose_pos++);
 564
 565                 if (loose_lookup(out, backend, path) == 0)
 566                         return 0;
 567
 568                 giterr_clear();
 569         }
 570
 571         if (!iter->cache) {
 572                 if ((error = git_sortedcache_copy(&iter->cache, backend->refcache, 1, NULL, NULL)) < 0)
 573                         return error;
 574         }
 575
 576         error = GIT_ITEROVER;
 577         while (iter->packed_pos < git_sortedcache_entrycount(iter->cache)) {
 578                 ref = git_sortedcache_entry(iter->cache, iter->packed_pos++);
 579                 if (!ref) /* stop now if another thread deleted refs and we past end */
 580                         break;
 581
 582                 if (ref->flags & PACKREF_SHADOWED)
 583                         continue;
 584                 if (iter->glob && p_fnmatch(iter->glob, ref->name, 0) != 0)
 585                         continue;
 586
 587                 *out = git_reference__alloc(ref->name, &ref->oid, &ref->peel);
 588                 error = (*out != NULL) ? 0 : -1;
 589                 break;
 590         }
 591
 592         return error;
 593 }
 594
 595 static int refdb_fs_backend__iterator_next_name(
 596         const char **out, git_reference_iterator *_iter)
 597 {
 598         int error = GIT_ITEROVER;
 599         refdb_fs_iter *iter = (refdb_fs_iter *)_iter;
 600         refdb_fs_backend *backend = (refdb_fs_backend *)iter->parent.db->backend;
 601         struct packref *ref;
 602
 603         while (iter->loose_pos < iter->loose.length) {
 604                 const char *path = git_vector_get(&iter->loose, iter->loose_pos++);
 605
 606                 if (loose_lookup(NULL, backend, path) == 0) {
 607                         *out = path;
 608                         return 0;
 609                 }
 610
 611                 giterr_clear();
 612         }
 613
 614         if (!iter->cache) {
 615                 if ((error = git_sortedcache_copy(&iter->cache, backend->refcache, 1, NULL, NULL)) < 0)
 616                         return error;
 617         }
 618
 619         error = GIT_ITEROVER;
 620         while (iter->packed_pos < git_sortedcache_entrycount(iter->cache)) {
 621                 ref = git_sortedcache_entry(iter->cache, iter->packed_pos++);
 622                 if (!ref) /* stop now if another thread deleted refs and we past end */
 623                         break;
 624
 625                 if (ref->flags & PACKREF_SHADOWED)
 626                         continue;
 627                 if (iter->glob && p_fnmatch(iter->glob, ref->name, 0) != 0)
 628                         continue;
 629
 630                 *out = ref->name;
 631                 error = 0;
 632                 break;
 633         }
 634
 635         return error;
 636 }
 637
 638 static int refdb_fs_backend__iterator(
 639         git_reference_iterator **out, git_refdb_backend *_backend, const char *glob)
 640 {
 641         int error;
 642         refdb_fs_iter *iter;
 643         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 644
 645         assert(backend);
 646
 647         if ((error = packed_reload(backend)) < 0)
 648                 return error;
 649
 650         iter = git__calloc(1, sizeof(refdb_fs_iter));
 651         GITERR_CHECK_ALLOC(iter);
 652
 653         git_pool_init(&iter->pool, 1);
 654
 655         if (git_vector_init(&iter->loose, 8, NULL) < 0)
 656                 goto fail;
 657
 658         if (glob != NULL &&
 659                 (iter->glob = git_pool_strdup(&iter->pool, glob)) == NULL)
 660                 goto fail;
 661
 662         iter->parent.next = refdb_fs_backend__iterator_next;
 663         iter->parent.next_name = refdb_fs_backend__iterator_next_name;
 664         iter->parent.free = refdb_fs_backend__iterator_free;
 665
 666         if (iter_load_loose_paths(backend, iter) < 0)
 667                 goto fail;
 668
 669         *out = (git_reference_iterator *)iter;
 670         return 0;
 671
 672 fail:
 673         refdb_fs_backend__iterator_free((git_reference_iterator *)iter);
 674         return -1;
 675 }
 676
 677 static bool ref_is_available(
 678         const char *old_ref, const char *new_ref, const char *this_ref)
 679 {
 680         if (old_ref == NULL || strcmp(old_ref, this_ref)) {
 681                 size_t reflen = strlen(this_ref);
 682                 size_t newlen = strlen(new_ref);
 683                 size_t cmplen = reflen < newlen ? reflen : newlen;
 684                 const char *lead = reflen < newlen ? new_ref : this_ref;
 685
 686                 if (!strncmp(new_ref, this_ref, cmplen) && lead[cmplen] == '/') {
 687                         return false;
 688                 }
 689         }
 690
 691         return true;
 692 }
 693
 694 static int reference_path_available(
 695         refdb_fs_backend *backend,
 696         const char *new_ref,
 697         const char* old_ref,
 698         int force)
 699 {
 700         size_t i;
 701         int error;
 702
 703         if ((error = packed_reload(backend)) < 0)
 704                 return error;
 705
 706         if (!force) {
 707                 int exists;
 708
 709                 if ((error = refdb_fs_backend__exists(
 710                         &exists, (git_refdb_backend *)backend, new_ref)) < 0) {
 711                         return error;
 712                 }
 713
 714                 if (exists) {
 715                         giterr_set(GITERR_REFERENCE,
 716                                 "failed to write reference '%s': a reference with "
 717                                 "that name already exists.", new_ref);
 718                         return GIT_EEXISTS;
 719                 }
 720         }
 721
 722         git_sortedcache_rlock(backend->refcache);
 723
 724         for (i = 0; i < git_sortedcache_entrycount(backend->refcache); ++i) {
 725                 struct packref *ref = git_sortedcache_entry(backend->refcache, i);
 726
 727                 if (ref && !ref_is_available(old_ref, new_ref, ref->name)) {
 728                         git_sortedcache_runlock(backend->refcache);
 729                         giterr_set(GITERR_REFERENCE,
 730                                 "path to reference '%s' collides with existing one", new_ref);
 731                         return -1;
 732                 }
 733         }
 734
 735         git_sortedcache_runlock(backend->refcache);
 736         return 0;
 737 }
 738
 739 static int loose_lock(git_filebuf *file, refdb_fs_backend *backend, const char *name)
 740 {
 741         int error, filebuf_flags;
 742         git_buf ref_path = GIT_BUF_INIT;
 743         const char *basedir;
 744
 745         assert(file && backend && name);
 746
 747         if (!git_path_isvalid(backend->repo, name, 0, GIT_PATH_REJECT_FILESYSTEM_DEFAULTS)) {
 748                 giterr_set(GITERR_INVALID, "invalid reference name '%s'", name);
 749                 return GIT_EINVALIDSPEC;
 750         }
 751
 752         if (is_per_worktree_ref(name))
 753                 basedir = backend->gitpath;
 754         else
 755                 basedir = backend->commonpath;
 756
 757         /* Remove a possibly existing empty directory hierarchy
 758          * which name would collide with the reference name
 759          */
 760         if ((error = git_futils_rmdir_r(name, basedir, GIT_RMDIR_SKIP_NONEMPTY)) < 0)
 761                 return error;
 762
 763         if (git_buf_joinpath(&ref_path, basedir, name) < 0)
 764                 return -1;
 765
 766         filebuf_flags = GIT_FILEBUF_FORCE;
 767         if (backend->fsync)
 768                 filebuf_flags |= GIT_FILEBUF_FSYNC;
 769
 770         error = git_filebuf_open(file, ref_path.ptr, filebuf_flags, GIT_REFS_FILE_MODE);
 771
 772         if (error == GIT_EDIRECTORY)
 773                 giterr_set(GITERR_REFERENCE, "cannot lock ref '%s', there are refs beneath that folder", name);
 774
 775         git_buf_free(&ref_path);
 776         return error;
 777 }
 778
 779 static int loose_commit(git_filebuf *file, const git_reference *ref)
 780 {
 781         assert(file && ref);
 782
 783         if (ref->type == GIT_REF_OID) {
 784                 char oid[GIT_OID_HEXSZ + 1];
 785                 git_oid_nfmt(oid, sizeof(oid), &ref->target.oid);
 786
 787                 git_filebuf_printf(file, "%s\n", oid);
 788         } else if (ref->type == GIT_REF_SYMBOLIC) {
 789                 git_filebuf_printf(file, GIT_SYMREF "%s\n", ref->target.symbolic);
 790         } else {
 791                 assert(0); /* don't let this happen */
 792         }
 793
 794         return git_filebuf_commit(file);
 795 }
 796
 797 static int refdb_fs_backend__lock(void **out, git_refdb_backend *_backend, const char *refname)
 798 {
 799         int error;
 800         git_filebuf *lock;
 801         refdb_fs_backend *backend = (refdb_fs_backend *) _backend;
 802
 803         lock = git__calloc(1, sizeof(git_filebuf));
 804         GITERR_CHECK_ALLOC(lock);
 805
 806         if ((error = loose_lock(lock, backend, refname)) < 0) {
 807                 git__free(lock);
 808                 return error;
 809         }
 810
 811         *out = lock;
 812         return 0;
 813 }
 814
 815 static int refdb_fs_backend__write_tail(
 816         git_refdb_backend *_backend,
 817         const git_reference *ref,
 818         git_filebuf *file,
 819         int update_reflog,
 820         const git_signature *who,
 821         const char *message,
 822         const git_oid *old_id,
 823         const char *old_target);
 824
 825 static int refdb_fs_backend__delete_tail(
 826         git_refdb_backend *_backend,
 827         git_filebuf *file,
 828         const char *ref_name,
 829         const git_oid *old_id, const char *old_target);
 830
 831 static int refdb_fs_backend__unlock(git_refdb_backend *backend, void *payload, int success, int update_reflog,
 832                                     const git_reference *ref, const git_signature *sig, const char *message)
 833 {
 834         git_filebuf *lock = (git_filebuf *) payload;
 835         int error = 0;
 836
 837         if (success == 2)
 838                 error = refdb_fs_backend__delete_tail(backend, lock, ref->name, NULL, NULL);
 839         else if (success)
 840                 error = refdb_fs_backend__write_tail(backend, ref, lock, update_reflog, sig, message, NULL, NULL);
 841         else
 842                 git_filebuf_cleanup(lock);
 843
 844         git__free(lock);
 845         return error;
 846 }
 847
 848 /*
 849  * Find out what object this reference resolves to.
 850  *
 851  * For references that point to a 'big' tag (e.g. an
 852  * actual tag object on the repository), we need to
 853  * cache on the packfile the OID of the object to
 854  * which that 'big tag' is pointing to.
 855  */
 856 static int packed_find_peel(refdb_fs_backend *backend, struct packref *ref)
 857 {
 858         git_object *object;
 859
 860         if (ref->flags & PACKREF_HAS_PEEL || ref->flags & PACKREF_CANNOT_PEEL)
 861                 return 0;
 862
 863         /*
 864          * Find the tagged object in the repository
 865          */
 866         if (git_object_lookup(&object, backend->repo, &ref->oid, GIT_OBJ_ANY) < 0)
 867                 return -1;
 868
 869         /*
 870          * If the tagged object is a Tag object, we need to resolve it;
 871          * if the ref is actually a 'weak' ref, we don't need to resolve
 872          * anything.
 873          */
 874         if (git_object_type(object) == GIT_OBJ_TAG) {
 875                 git_tag *tag = (git_tag *)object;
 876
 877                 /*
 878                  * Find the object pointed at by this tag
 879                  */
 880                 git_oid_cpy(&ref->peel, git_tag_target_id(tag));
 881                 ref->flags |= PACKREF_HAS_PEEL;
 882
 883                 /*
 884                  * The reference has now cached the resolved OID, and is
 885                  * marked at such. When written to the packfile, it'll be
 886                  * accompanied by this resolved oid
 887                  */
 888         }
 889
 890         git_object_free(object);
 891         return 0;
 892 }
 893
 894 /*
 895  * Write a single reference into a packfile
 896  */
 897 static int packed_write_ref(struct packref *ref, git_filebuf *file)
 898 {
 899         char oid[GIT_OID_HEXSZ + 1];
 900         git_oid_nfmt(oid, sizeof(oid), &ref->oid);
 901
 902         /*
 903          * For references that peel to an object in the repo, we must
 904          * write the resulting peel on a separate line, e.g.
 905          *
 906          *      6fa8a902cc1d18527e1355773c86721945475d37 refs/tags/libgit2-0.4
 907          *      ^2ec0cb7959b0bf965d54f95453f5b4b34e8d3100
 908          *
 909          * This obviously only applies to tags.
 910          * The required peels have already been loaded into `ref->peel_target`.
 911          */
 912         if (ref->flags & PACKREF_HAS_PEEL) {
 913                 char peel[GIT_OID_HEXSZ + 1];
 914                 git_oid_nfmt(peel, sizeof(peel), &ref->peel);
 915
 916                 if (git_filebuf_printf(file, "%s %s\n^%s\n", oid, ref->name, peel) < 0)
 917                         return -1;
 918         } else {
 919                 if (git_filebuf_printf(file, "%s %s\n", oid, ref->name) < 0)
 920                         return -1;
 921         }
 922
 923         return 0;
 924 }
 925
 926 /*
 927  * Remove all loose references
 928  *
 929  * Once we have successfully written a packfile,
 930  * all the loose references that were packed must be
 931  * removed from disk.
 932  *
 933  * This is a dangerous method; make sure the packfile
 934  * is well-written, because we are destructing references
 935  * here otherwise.
 936  */
 937 static int packed_remove_loose(refdb_fs_backend *backend)
 938 {
 939         size_t i;
 940         git_filebuf lock = GIT_FILEBUF_INIT;
 941         git_buf ref_content = GIT_BUF_INIT;
 942         int error = 0;
 943
 944         /* backend->refcache is already locked when this is called */
 945
 946         for (i = 0; i < git_sortedcache_entrycount(backend->refcache); ++i) {
 947                 struct packref *ref = git_sortedcache_entry(backend->refcache, i);
 948                 git_oid current_id;
 949
 950                 if (!ref || !(ref->flags & PACKREF_WAS_LOOSE))
 951                         continue;
 952
 953                 git_filebuf_cleanup(&lock);
 954
 955                 /* We need to stop anybody from updating the ref while we try to do a safe delete */
 956                 error = loose_lock(&lock, backend, ref->name);
 957                 /* If someone else is updating it, let them do it */
 958                 if (error == GIT_EEXISTS || error == GIT_ENOTFOUND)
 959                         continue;
 960
 961                 if (error < 0) {
 962                         git_buf_free(&ref_content);
 963                         giterr_set(GITERR_REFERENCE, "failed to lock loose reference '%s'", ref->name);
 964                         return error;
 965                 }
 966
 967                 error = git_futils_readbuffer(&ref_content, lock.path_original);
 968                 /* Someone else beat us to cleaning up the ref, let's simply continue */
 969                 if (error == GIT_ENOTFOUND)
 970                         continue;
 971
 972                 /* This became a symref between us packing and trying to delete it, so ignore it */
 973                 if (!git__prefixcmp(ref_content.ptr, GIT_SYMREF))
 974                         continue;
 975
 976                 /* Figure out the current id; if we find a bad ref file, skip it so we can do the rest */
 977                 if (loose_parse_oid(&current_id, lock.path_original, &ref_content) < 0)
 978                         continue;
 979
 980                 /* If the ref moved since we packed it, we must not delete it */
 981                 if (!git_oid_equal(&current_id, &ref->oid))
 982                         continue;
 983
 984                 /*
 985                  * if we fail to remove a single file, this is *not* good,
 986                  * but we should keep going and remove as many as possible.
 987                  * If we fail to remove, the ref is still in the old state, so
 988                  * we haven't lost information.
 989                  */
 990                 p_unlink(lock.path_original);
 991         }
 992
 993         git_buf_free(&ref_content);
 994         git_filebuf_cleanup(&lock);
 995         return 0;
 996 }
 997
 998 /*
 999  * Write all the contents in the in-memory packfile to disk.
1000  */
1001 static int packed_write(refdb_fs_backend *backend)
1002 {
1003         git_sortedcache *refcache = backend->refcache;
1004         git_filebuf pack_file = GIT_FILEBUF_INIT;
1005         int error, open_flags = 0;
1006         size_t i;
1007
1008         /* lock the cache to updates while we do this */
1009         if ((error = git_sortedcache_wlock(refcache)) < 0)
1010                 return error;
1011
1012         if (backend->fsync)
1013                 open_flags = GIT_FILEBUF_FSYNC;
1014
1015         /* Open the file! */
1016         if ((error = git_filebuf_open(&pack_file, git_sortedcache_path(refcache), open_flags, GIT_PACKEDREFS_FILE_MODE)) < 0)
1017                 goto fail;
1018
1019         /* Packfiles have a header... apparently
1020          * This is in fact not required, but we might as well print it
1021          * just for kicks */
1022         if ((error = git_filebuf_printf(&pack_file, "%s\n", GIT_PACKEDREFS_HEADER)) < 0)
1023                 goto fail;
1024
1025         for (i = 0; i < git_sortedcache_entrycount(refcache); ++i) {
1026                 struct packref *ref = git_sortedcache_entry(refcache, i);
1027                 assert(ref);
1028
1029                 if ((error = packed_find_peel(backend, ref)) < 0)
1030                         goto fail;
1031
1032                 if ((error = packed_write_ref(ref, &pack_file)) < 0)
1033                         goto fail;
1034         }
1035
1036         /* if we've written all the references properly, we can commit
1037          * the packfile to make the changes effective */
1038         if ((error = git_filebuf_commit(&pack_file)) < 0)
1039                 goto fail;
1040
1041         /* when and only when the packfile has been properly written,
1042          * we can go ahead and remove the loose refs */
1043         if ((error = packed_remove_loose(backend)) < 0)
1044                 goto fail;
1045
1046         git_sortedcache_updated(refcache);
1047         git_sortedcache_wunlock(refcache);
1048
1049         /* we're good now */
1050         return 0;
1051
1052 fail:
1053         git_filebuf_cleanup(&pack_file);
1054         git_sortedcache_wunlock(refcache);
1055
1056         return error;
1057 }
1058
1059 static int reflog_append(refdb_fs_backend *backend, const git_reference *ref, const git_oid *old, const git_oid *new, const git_signature *author, const char *message);
1060 static int has_reflog(git_repository *repo, const char *name);
1061
1062 /* We only write if it's under heads/, remotes/ or notes/ or if it already has a log */
1063 static int should_write_reflog(int *write, git_repository *repo, const char *name)
1064 {
1065         int error, logall;
1066
1067         error = git_repository__cvar(&logall, repo, GIT_CVAR_LOGALLREFUPDATES);
1068         if (error < 0)
1069                 return error;
1070
1071         /* Defaults to the opposite of the repo being bare */
1072         if (logall == GIT_LOGALLREFUPDATES_UNSET)
1073                 logall = !git_repository_is_bare(repo);
1074
1075         if (!logall) {
1076                 *write = 0;
1077         } else if (has_reflog(repo, name)) {
1078                 *write = 1;
1079         } else if (!git__prefixcmp(name, GIT_REFS_HEADS_DIR) ||
1080                    !git__strcmp(name, GIT_HEAD_FILE) ||
1081                    !git__prefixcmp(name, GIT_REFS_REMOTES_DIR) ||
1082                    !git__prefixcmp(name, GIT_REFS_NOTES_DIR)) {
1083                 *write = 1;
1084         } else {
1085                 *write = 0;
1086         }
1087
1088         return 0;
1089 }
1090
1091 static int cmp_old_ref(int *cmp, git_refdb_backend *backend, const char *name,
1092         const git_oid *old_id, const char *old_target)
1093 {
1094         int error = 0;
1095         git_reference *old_ref = NULL;
1096
1097         *cmp = 0;
1098         /* It "matches" if there is no old value to compare against */
1099         if (!old_id && !old_target)
1100                 return 0;
1101
1102         if ((error = refdb_fs_backend__lookup(&old_ref, backend, name)) < 0)
1103                 goto out;
1104
1105         /* If the types don't match, there's no way the values do */
1106         if (old_id && old_ref->type != GIT_REF_OID) {
1107                 *cmp = -1;
1108                 goto out;
1109         }
1110         if (old_target && old_ref->type != GIT_REF_SYMBOLIC) {
1111                 *cmp = 1;
1112                 goto out;
1113         }
1114
1115         if (old_id && old_ref->type == GIT_REF_OID)
1116                 *cmp = git_oid_cmp(old_id, &old_ref->target.oid);
1117
1118         if (old_target && old_ref->type == GIT_REF_SYMBOLIC)
1119                 *cmp = git__strcmp(old_target, old_ref->target.symbolic);
1120
1121 out:
1122         git_reference_free(old_ref);
1123
1124         return error;
1125 }
1126
1127 /*
1128  * The git.git comment regarding this, for your viewing pleasure:
1129  *
1130  * Special hack: If a branch is updated directly and HEAD
1131  * points to it (may happen on the remote side of a push
1132  * for example) then logically the HEAD reflog should be
1133  * updated too.
1134  * A generic solution implies reverse symref information,
1135  * but finding all symrefs pointing to the given branch
1136  * would be rather costly for this rare event (the direct
1137  * update of a branch) to be worth it.  So let's cheat and
1138  * check with HEAD only which should cover 99% of all usage
1139  * scenarios (even 100% of the default ones).
1140  */
1141 static int maybe_append_head(refdb_fs_backend *backend, const git_reference *ref, const git_signature *who, const char *message)
1142 {
1143         int error;
1144         git_oid old_id;
1145         git_reference *tmp = NULL, *head = NULL, *peeled = NULL;
1146         const char *name;
1147
1148         if (ref->type == GIT_REF_SYMBOLIC)
1149                 return 0;
1150
1151         /* if we can't resolve, we use {0}*40 as old id */
1152         if (git_reference_name_to_id(&old_id, backend->repo, ref->name) < 0)
1153                 memset(&old_id, 0, sizeof(old_id));
1154
1155         if ((error = git_reference_lookup(&head, backend->repo, GIT_HEAD_FILE)) < 0)
1156                 return error;
1157
1158         if (git_reference_type(head) == GIT_REF_OID)
1159                 goto cleanup;
1160
1161         if ((error = git_reference_lookup(&tmp, backend->repo, GIT_HEAD_FILE)) < 0)
1162                 goto cleanup;
1163
1164         /* Go down the symref chain until we find the branch */
1165         while (git_reference_type(tmp) == GIT_REF_SYMBOLIC) {
1166                 error = git_reference_lookup(&peeled, backend->repo, git_reference_symbolic_target(tmp));
1167                 if (error < 0)
1168                         break;
1169
1170                 git_reference_free(tmp);
1171                 tmp = peeled;
1172         }
1173
1174         if (error == GIT_ENOTFOUND) {
1175                 error = 0;
1176                 name = git_reference_symbolic_target(tmp);
1177         } else if (error < 0) {
1178                 goto cleanup;
1179         } else {
1180                 name = git_reference_name(tmp);
1181         }
1182
1183         if (strcmp(name, ref->name))
1184                 goto cleanup;
1185
1186         error = reflog_append(backend, head, &old_id, git_reference_target(ref), who, message);
1187
1188 cleanup:
1189         git_reference_free(tmp);
1190         git_reference_free(head);
1191         return error;
1192 }
1193
1194 static int refdb_fs_backend__write(
1195         git_refdb_backend *_backend,
1196         const git_reference *ref,
1197         int force,
1198         const git_signature *who,
1199         const char *message,
1200         const git_oid *old_id,
1201         const char *old_target)
1202 {
1203         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1204         git_filebuf file = GIT_FILEBUF_INIT;
1205         int error = 0;
1206
1207         assert(backend);
1208
1209         if ((error = reference_path_available(backend, ref->name, NULL, force)) < 0)
1210                 return error;
1211
1212         /* We need to perform the reflog append and old value check under the ref's lock */
1213         if ((error = loose_lock(&file, backend, ref->name)) < 0)
1214                 return error;
1215
1216         return refdb_fs_backend__write_tail(_backend, ref, &file, true, who, message, old_id, old_target);
1217 }
1218
1219 static int refdb_fs_backend__write_tail(
1220         git_refdb_backend *_backend,
1221         const git_reference *ref,
1222         git_filebuf *file,
1223         int update_reflog,
1224         const git_signature *who,
1225         const char *message,
1226         const git_oid *old_id,
1227         const char *old_target)
1228 {
1229         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1230         int error = 0, cmp = 0, should_write;
1231         const char *new_target = NULL;
1232         const git_oid *new_id = NULL;
1233
1234         if ((error = cmp_old_ref(&cmp, _backend, ref->name, old_id, old_target)) < 0)
1235                 goto on_error;
1236
1237         if (cmp) {
1238                 giterr_set(GITERR_REFERENCE, "old reference value does not match");
1239                 error = GIT_EMODIFIED;
1240                 goto on_error;
1241         }
1242
1243         if (ref->type == GIT_REF_SYMBOLIC)
1244                 new_target = ref->target.symbolic;
1245         else
1246                 new_id = &ref->target.oid;
1247
1248         error = cmp_old_ref(&cmp, _backend, ref->name, new_id, new_target);
1249         if (error < 0 && error != GIT_ENOTFOUND)
1250                 goto on_error;
1251
1252         /* Don't update if we have the same value */
1253         if (!error && !cmp) {
1254                 error = 0;
1255                 goto on_error; /* not really error */
1256         }
1257
1258         if (update_reflog) {
1259                 if ((error = should_write_reflog(&should_write, backend->repo, ref->name)) < 0)
1260                         goto on_error;
1261
1262                 if (should_write) {
1263                         if ((error = reflog_append(backend, ref, NULL, NULL, who, message)) < 0)
1264                                 goto on_error;
1265                         if ((error = maybe_append_head(backend, ref, who, message)) < 0)
1266                                 goto on_error;
1267                 }
1268         }
1269
1270         return loose_commit(file, ref);
1271
1272 on_error:
1273         git_filebuf_cleanup(file);
1274         return error;
1275 }
1276
1277 static int refdb_fs_backend__delete(
1278         git_refdb_backend *_backend,
1279         const char *ref_name,
1280         const git_oid *old_id, const char *old_target)
1281 {
1282         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1283         git_filebuf file = GIT_FILEBUF_INIT;
1284         int error = 0;
1285
1286         assert(backend && ref_name);
1287
1288         if ((error = loose_lock(&file, backend, ref_name)) < 0)
1289                 return error;
1290
1291         if ((error = refdb_reflog_fs__delete(_backend, ref_name)) < 0) {
1292                 git_filebuf_cleanup(&file);
1293                 return error;
1294         }
1295
1296         return refdb_fs_backend__delete_tail(_backend, &file, ref_name, old_id, old_target);
1297 }
1298
1299 static int refdb_fs_backend__delete_tail(
1300         git_refdb_backend *_backend,
1301         git_filebuf *file,
1302         const char *ref_name,
1303         const git_oid *old_id, const char *old_target)
1304 {
1305         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1306         git_buf loose_path = GIT_BUF_INIT;
1307         size_t pack_pos;
1308         int error = 0, cmp = 0;
1309         bool loose_deleted = 0;
1310
1311         error = cmp_old_ref(&cmp, _backend, ref_name, old_id, old_target);
1312         if (error < 0)
1313                 goto cleanup;
1314
1315         if (cmp) {
1316                 giterr_set(GITERR_REFERENCE, "old reference value does not match");
1317                 error = GIT_EMODIFIED;
1318                 goto cleanup;
1319         }
1320
1321         /* If a loose reference exists, remove it from the filesystem */
1322         if (git_buf_joinpath(&loose_path, backend->gitpath, ref_name) < 0)
1323                 return -1;
1324
1325
1326         error = p_unlink(loose_path.ptr);
1327         if (error < 0 && errno == ENOENT)
1328                 error = 0;
1329         else if (error < 0)
1330                 goto cleanup;
1331         else if (error == 0)
1332                 loose_deleted = 1;
1333
1334         if ((error = packed_reload(backend)) < 0)
1335                 goto cleanup;
1336
1337         /* If a packed reference exists, remove it from the packfile and repack */
1338         if ((error = git_sortedcache_wlock(backend->refcache)) < 0)
1339                 goto cleanup;
1340
1341         if (!(error = git_sortedcache_lookup_index(
1342                         &pack_pos, backend->refcache, ref_name)))
1343                 error = git_sortedcache_remove(backend->refcache, pack_pos);
1344
1345         git_sortedcache_wunlock(backend->refcache);
1346
1347         if (error == GIT_ENOTFOUND) {
1348                 error = loose_deleted ? 0 : ref_error_notfound(ref_name);
1349                 goto cleanup;
1350         }
1351
1352         error = packed_write(backend);
1353
1354 cleanup:
1355         git_buf_free(&loose_path);
1356         git_filebuf_cleanup(file);
1357
1358         return error;
1359 }
1360
1361 static int refdb_reflog_fs__rename(git_refdb_backend *_backend, const char *old_name, const char *new_name);
1362
1363 static int refdb_fs_backend__rename(
1364         git_reference **out,
1365         git_refdb_backend *_backend,
1366         const char *old_name,
1367         const char *new_name,
1368         int force,
1369         const git_signature *who,
1370         const char *message)
1371 {
1372         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1373         git_reference *old, *new;
1374         git_filebuf file = GIT_FILEBUF_INIT;
1375         int error;
1376
1377         assert(backend);
1378
1379         if ((error = reference_path_available(
1380                         backend, new_name, old_name, force)) < 0 ||
1381                 (error = refdb_fs_backend__lookup(&old, _backend, old_name)) < 0)
1382                 return error;
1383
1384         if ((error = refdb_fs_backend__delete(_backend, old_name, NULL, NULL)) < 0) {
1385                 git_reference_free(old);
1386                 return error;
1387         }
1388
1389         new = git_reference__set_name(old, new_name);
1390         if (!new) {
1391                 git_reference_free(old);
1392                 return -1;
1393         }
1394
1395         if ((error = loose_lock(&file, backend, new->name)) < 0) {
1396                 git_reference_free(new);
1397                 return error;
1398         }
1399
1400         /* Try to rename the refog; it's ok if the old doesn't exist */
1401         error = refdb_reflog_fs__rename(_backend, old_name, new_name);
1402         if (((error == 0) || (error == GIT_ENOTFOUND)) &&
1403             ((error = reflog_append(backend, new, git_reference_target(new), NULL, who, message)) < 0)) {
1404                 git_reference_free(new);
1405                 git_filebuf_cleanup(&file);
1406                 return error;
1407         }
1408
1409         if (error < 0) {
1410                 git_reference_free(new);
1411                 git_filebuf_cleanup(&file);
1412                 return error;
1413         }
1414
1415
1416         if ((error = loose_commit(&file, new)) < 0 || out == NULL) {
1417                 git_reference_free(new);
1418                 return error;
1419         }
1420
1421         *out = new;
1422         return 0;
1423 }
1424
1425 static int refdb_fs_backend__compress(git_refdb_backend *_backend)
1426 {
1427         int error;
1428         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1429
1430         assert(backend);
1431
1432         if ((error = packed_reload(backend)) < 0 || /* load the existing packfile */
1433             (error = packed_loadloose(backend)) < 0 || /* add all the loose refs */
1434             (error = packed_write(backend)) < 0) /* write back to disk */
1435                 return error;
1436
1437         return 0;
1438 }
1439
1440 static void refdb_fs_backend__free(git_refdb_backend *_backend)
1441 {
1442         refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
1443
1444         assert(backend);
1445
1446         git_sortedcache_free(backend->refcache);
1447         git__free(backend->gitpath);
1448         git__free(backend->commonpath);
1449         git__free(backend);
1450 }
1451
1452 static char *setup_namespace(git_repository *repo, const char *in)
1453 {
1454         git_buf path = GIT_BUF_INIT;
1455         char *parts, *start, *end, *out = NULL;
1456
1457         if (!in)
1458                 goto done;
1459
1460         git_buf_puts(&path, in);
1461
1462         /* if the repo is not namespaced, nothing else to do */
1463         if (repo->namespace == NULL) {
1464                 out = git_buf_detach(&path);
1465                 goto done;
1466         }
1467
1468         parts = end = git__strdup(repo->namespace);
1469         if (parts == NULL)
1470                 goto done;
1471
1472         /*
1473          * From `man gitnamespaces`:
1474          *  namespaces which include a / will expand to a hierarchy
1475          *  of namespaces; for example, GIT_NAMESPACE=foo/bar will store
1476          *  refs under refs/namespaces/foo/refs/namespaces/bar/
1477          */
1478         while ((start = git__strsep(&end, "/")) != NULL)
1479                 git_buf_printf(&path, "refs/namespaces/%s/", start);
1480
1481         git_buf_printf(&path, "refs/namespaces/%s/refs", end);
1482         git__free(parts);
1483
1484         /* Make sure that the folder with the namespace exists */
1485         if (git_futils_mkdir_relative(git_buf_cstr(&path), in, 0777,
1486                         GIT_MKDIR_PATH, NULL) < 0)
1487                 goto done;
1488
1489         /* Return root of the namespaced gitpath, i.e. without the trailing '/refs' */
1490         git_buf_rtruncate_at_char(&path, '/');
1491         out = git_buf_detach(&path);
1492
1493 done:
1494         git_buf_free(&path);
1495         return out;
1496 }
1497
1498 static int reflog_alloc(git_reflog **reflog, const char *name)
1499 {
1500         git_reflog *log;
1501
1502         *reflog = NULL;
1503
1504         log = git__calloc(1, sizeof(git_reflog));
1505         GITERR_CHECK_ALLOC(log);
1506
1507         log->ref_name = git__strdup(name);
1508         GITERR_CHECK_ALLOC(log->ref_name);
1509
1510         if (git_vector_init(&log->entries, 0, NULL) < 0) {
1511                 git__free(log->ref_name);
1512                 git__free(log);
1513                 return -1;
1514         }
1515
1516         *reflog = log;
1517
1518         return 0;
1519 }
1520
1521 static int reflog_parse(git_reflog *log, const char *buf, size_t buf_size)
1522 {
1523         const char *ptr;
1524         git_reflog_entry *entry;
1525
1526 #define seek_forward(_increase) do { \
1527         if (_increase >= buf_size) { \
1528                 giterr_set(GITERR_INVALID, "ran out of data while parsing reflog"); \
1529                 goto fail; \
1530         } \
1531         buf += _increase; \
1532         buf_size -= _increase; \
1533         } while (0)
1534
1535         while (buf_size > GIT_REFLOG_SIZE_MIN) {
1536                 entry = git__calloc(1, sizeof(git_reflog_entry));
1537                 GITERR_CHECK_ALLOC(entry);
1538
1539                 entry->committer = git__calloc(1, sizeof(git_signature));
1540                 GITERR_CHECK_ALLOC(entry->committer);
1541
1542                 if (git_oid_fromstrn(&entry->oid_old, buf, GIT_OID_HEXSZ) < 0)
1543                         goto fail;
1544                 seek_forward(GIT_OID_HEXSZ + 1);
1545
1546                 if (git_oid_fromstrn(&entry->oid_cur, buf, GIT_OID_HEXSZ) < 0)
1547                         goto fail;
1548                 seek_forward(GIT_OID_HEXSZ + 1);
1549
1550                 ptr = buf;
1551
1552                 /* Seek forward to the end of the signature. */
1553                 while (*buf && *buf != '\t' && *buf != '\n')
1554                         seek_forward(1);
1555
1556                 if (git_signature__parse(entry->committer, &ptr, buf + 1, NULL, *buf) < 0)
1557                         goto fail;
1558
1559                 if (*buf == '\t') {
1560                         /* We got a message. Read everything till we reach LF. */
1561                         seek_forward(1);
1562                         ptr = buf;
1563
1564                         while (*buf && *buf != '\n')
1565                                 seek_forward(1);
1566
1567                         entry->msg = git__strndup(ptr, buf - ptr);
1568                         GITERR_CHECK_ALLOC(entry->msg);
1569                 } else
1570                         entry->msg = NULL;
1571
1572                 while (*buf && *buf == '\n' && buf_size > 1)
1573                         seek_forward(1);
1574
1575                 if (git_vector_insert(&log->entries, entry) < 0)
1576                         goto fail;
1577         }
1578
1579         return 0;
1580
1581 #undef seek_forward
1582
1583 fail:
1584         git_reflog_entry__free(entry);
1585
1586         return -1;
1587 }
1588
1589 static int create_new_reflog_file(const char *filepath)
1590 {
1591         int fd, error;
1592
1593         if ((error = git_futils_mkpath2file(filepath, GIT_REFLOG_DIR_MODE)) < 0)
1594                 return error;
1595
1596         if ((fd = p_open(filepath,
1597                         O_WRONLY | O_CREAT,
1598                         GIT_REFLOG_FILE_MODE)) < 0)
1599                 return -1;
1600
1601         return p_close(fd);
1602 }
1603
1604 GIT_INLINE(int) retrieve_reflog_path(git_buf *path, git_repository *repo, const char *name)
1605 {
1606         if (strcmp(name, GIT_HEAD_FILE) == 0)
1607                 return git_buf_join3(path, '/', repo->gitdir, GIT_REFLOG_DIR, name);
1608         return git_buf_join3(path, '/', repo->commondir, GIT_REFLOG_DIR, name);
1609 }
1610
1611 static int refdb_reflog_fs__ensure_log(git_refdb_backend *_backend, const char *name)
1612 {
1613         refdb_fs_backend *backend;
1614         git_repository *repo;
1615         git_buf path = GIT_BUF_INIT;
1616         int error;
1617
1618         assert(_backend && name);
1619
1620         backend = (refdb_fs_backend *) _backend;
1621         repo = backend->repo;
1622
1623         if ((error = retrieve_reflog_path(&path, repo, name)) < 0)
1624                 return error;
1625
1626         error = create_new_reflog_file(git_buf_cstr(&path));
1627         git_buf_free(&path);
1628
1629         return error;
1630 }
1631
1632 static int has_reflog(git_repository *repo, const char *name)
1633 {
1634         int ret = 0;
1635         git_buf path = GIT_BUF_INIT;
1636
1637         if (retrieve_reflog_path(&path, repo, name) < 0)
1638                 goto cleanup;
1639
1640         ret = git_path_isfile(git_buf_cstr(&path));
1641
1642 cleanup:
1643         git_buf_free(&path);
1644         return ret;
1645 }
1646
1647 static int refdb_reflog_fs__has_log(git_refdb_backend *_backend, const char *name)
1648 {
1649         refdb_fs_backend *backend;
1650
1651         assert(_backend && name);
1652
1653         backend = (refdb_fs_backend *) _backend;
1654
1655         return has_reflog(backend->repo, name);
1656 }
1657
1658 static int refdb_reflog_fs__read(git_reflog **out, git_refdb_backend *_backend, const char *name)
1659 {
1660         int error = -1;
1661         git_buf log_path = GIT_BUF_INIT;
1662         git_buf log_file = GIT_BUF_INIT;
1663         git_reflog *log = NULL;
1664         git_repository *repo;
1665         refdb_fs_backend *backend;
1666
1667         assert(out && _backend && name);
1668
1669         backend = (refdb_fs_backend *) _backend;
1670         repo = backend->repo;
1671
1672         if (reflog_alloc(&log, name) < 0)
1673                 return -1;
1674
1675         if (retrieve_reflog_path(&log_path, repo, name) < 0)
1676                 goto cleanup;
1677
1678         error = git_futils_readbuffer(&log_file, git_buf_cstr(&log_path));
1679         if (error < 0 && error != GIT_ENOTFOUND)
1680                 goto cleanup;
1681
1682         if ((error == GIT_ENOTFOUND) &&
1683                 ((error = create_new_reflog_file(git_buf_cstr(&log_path))) < 0))
1684                 goto cleanup;
1685
1686         if ((error = reflog_parse(log,
1687                 git_buf_cstr(&log_file), git_buf_len(&log_file))) < 0)
1688                 goto cleanup;
1689
1690         *out = log;
1691         goto success;
1692
1693 cleanup:
1694         git_reflog_free(log);
1695
1696 success:
1697         git_buf_free(&log_file);
1698         git_buf_free(&log_path);
1699
1700         return error;
1701 }
1702
1703 static int serialize_reflog_entry(
1704         git_buf *buf,
1705         const git_oid *oid_old,
1706         const git_oid *oid_new,
1707         const git_signature *committer,
1708         const char *msg)
1709 {
1710         char raw_old[GIT_OID_HEXSZ+1];
1711         char raw_new[GIT_OID_HEXSZ+1];
1712
1713         git_oid_tostr(raw_old, GIT_OID_HEXSZ+1, oid_old);
1714         git_oid_tostr(raw_new, GIT_OID_HEXSZ+1, oid_new);
1715
1716         git_buf_clear(buf);
1717
1718         git_buf_puts(buf, raw_old);
1719         git_buf_putc(buf, ' ');
1720         git_buf_puts(buf, raw_new);
1721
1722         git_signature__writebuf(buf, " ", committer);
1723
1724         /* drop trailing LF */
1725         git_buf_rtrim(buf);
1726
1727         if (msg) {
1728                 git_buf_putc(buf, '\t');
1729                 git_buf_puts(buf, msg);
1730         }
1731
1732         git_buf_putc(buf, '\n');
1733
1734         return git_buf_oom(buf);
1735 }
1736
1737 static int lock_reflog(git_filebuf *file, refdb_fs_backend *backend, const char *refname)
1738 {
1739         git_repository *repo;
1740         git_buf log_path = GIT_BUF_INIT;
1741         int error;
1742
1743         repo = backend->repo;
1744
1745         if (!git_path_isvalid(backend->repo, refname, 0, GIT_PATH_REJECT_FILESYSTEM_DEFAULTS)) {
1746                 giterr_set(GITERR_INVALID, "invalid reference name '%s'", refname);
1747                 return GIT_EINVALIDSPEC;
1748         }
1749
1750         if (retrieve_reflog_path(&log_path, repo, refname) < 0)
1751                 return -1;
1752
1753         if (!git_path_isfile(git_buf_cstr(&log_path))) {
1754                 giterr_set(GITERR_INVALID,
1755                         "log file for reference '%s' doesn't exist", refname);
1756                 error = -1;
1757                 goto cleanup;
1758         }
1759
1760         error = git_filebuf_open(file, git_buf_cstr(&log_path), 0, GIT_REFLOG_FILE_MODE);
1761
1762 cleanup:
1763         git_buf_free(&log_path);
1764
1765         return error;
1766 }
1767
1768 static int refdb_reflog_fs__write(git_refdb_backend *_backend, git_reflog *reflog)
1769 {
1770         int error = -1;
1771         unsigned int i;
1772         git_reflog_entry *entry;
1773         refdb_fs_backend *backend;
1774         git_buf log = GIT_BUF_INIT;
1775         git_filebuf fbuf = GIT_FILEBUF_INIT;
1776
1777         assert(_backend && reflog);
1778
1779         backend = (refdb_fs_backend *) _backend;
1780
1781         if ((error = lock_reflog(&fbuf, backend, reflog->ref_name)) < 0)
1782                 return -1;
1783
1784         git_vector_foreach(&reflog->entries, i, entry) {
1785                 if (serialize_reflog_entry(&log, &(entry->oid_old), &(entry->oid_cur), entry->committer, entry->msg) < 0)
1786                         goto cleanup;
1787
1788                 if ((error = git_filebuf_write(&fbuf, log.ptr, log.size)) < 0)
1789                         goto cleanup;
1790         }
1791
1792         error = git_filebuf_commit(&fbuf);
1793         goto success;
1794
1795 cleanup:
1796         git_filebuf_cleanup(&fbuf);
1797
1798 success:
1799         git_buf_free(&log);
1800
1801         return error;
1802 }
1803
1804 /* Append to the reflog, must be called under reference lock */
1805 static int reflog_append(refdb_fs_backend *backend, const git_reference *ref, const git_oid *old, const git_oid *new, const git_signature *who, const char *message)
1806 {
1807         int error, is_symbolic, open_flags;
1808         git_oid old_id = {{0}}, new_id = {{0}};
1809         git_buf buf = GIT_BUF_INIT, path = GIT_BUF_INIT;
1810         git_repository *repo = backend->repo;
1811
1812         is_symbolic = ref->type == GIT_REF_SYMBOLIC;
1813
1814         /* "normal" symbolic updates do not write */
1815         if (is_symbolic &&
1816             strcmp(ref->name, GIT_HEAD_FILE) &&
1817             !(old && new))
1818                 return 0;
1819
1820         /* From here on is_symoblic also means that it's HEAD */
1821
1822         if (old) {
1823                 git_oid_cpy(&old_id, old);
1824         } else {
1825                 error = git_reference_name_to_id(&old_id, repo, ref->name);
1826                 if (error < 0 && error != GIT_ENOTFOUND)
1827                         return error;
1828         }
1829
1830         if (new) {
1831                 git_oid_cpy(&new_id, new);
1832         } else {
1833                 if (!is_symbolic) {
1834                         git_oid_cpy(&new_id, git_reference_target(ref));
1835                 } else {
1836                         error = git_reference_name_to_id(&new_id, repo, git_reference_symbolic_target(ref));
1837                         if (error < 0 && error != GIT_ENOTFOUND)
1838                                 return error;
1839                         /* detaching HEAD does not create an entry */
1840                         if (error == GIT_ENOTFOUND)
1841                                 return 0;
1842
1843                         giterr_clear();
1844                 }
1845         }
1846
1847         if ((error = serialize_reflog_entry(&buf, &old_id, &new_id, who, message)) < 0)
1848                 goto cleanup;
1849
1850         if ((error = retrieve_reflog_path(&path, repo, ref->name)) < 0)
1851                 goto cleanup;
1852
1853         if (((error = git_futils_mkpath2file(git_buf_cstr(&path), 0777)) < 0) &&
1854             (error != GIT_EEXISTS)) {
1855                 goto cleanup;
1856         }
1857
1858         /* If the new branch matches part of the namespace of a previously deleted branch,
1859          * there maybe an obsolete/unused directory (or directory hierarchy) in the way.
1860          */
1861         if (git_path_isdir(git_buf_cstr(&path))) {
1862                 if ((error = git_futils_rmdir_r(git_buf_cstr(&path), NULL, GIT_RMDIR_SKIP_NONEMPTY)) < 0) {
1863                         if (error == GIT_ENOTFOUND)
1864                                 error = 0;
1865                 } else if (git_path_isdir(git_buf_cstr(&path))) {
1866                         giterr_set(GITERR_REFERENCE, "cannot create reflog at '%s', there are reflogs beneath that folder",
1867                                 ref->name);
1868                         error = GIT_EDIRECTORY;
1869                 }
1870
1871                 if (error != 0)
1872                         goto cleanup;
1873         }
1874
1875         open_flags = O_WRONLY | O_CREAT | O_APPEND;
1876
1877         if (backend->fsync)
1878                 open_flags |= O_FSYNC;
1879
1880         error = git_futils_writebuffer(&buf, git_buf_cstr(&path), open_flags, GIT_REFLOG_FILE_MODE);
1881
1882 cleanup:
1883         git_buf_free(&buf);
1884         git_buf_free(&path);
1885
1886         return error;
1887 }
1888
1889 static int refdb_reflog_fs__rename(git_refdb_backend *_backend, const char *old_name, const char *new_name)
1890 {
1891         int error = 0, fd;
1892         git_buf old_path = GIT_BUF_INIT;
1893         git_buf new_path = GIT_BUF_INIT;
1894         git_buf temp_path = GIT_BUF_INIT;
1895         git_buf normalized = GIT_BUF_INIT;
1896         git_repository *repo;
1897         refdb_fs_backend *backend;
1898
1899         assert(_backend && old_name && new_name);
1900
1901         backend = (refdb_fs_backend *) _backend;
1902         repo = backend->repo;
1903
1904         if ((error = git_reference__normalize_name(
1905                 &normalized, new_name, GIT_REF_FORMAT_ALLOW_ONELEVEL)) < 0)
1906                         return error;
1907
1908         if (git_buf_joinpath(&temp_path, repo->gitdir, GIT_REFLOG_DIR) < 0)
1909                 return -1;
1910
1911         if (git_buf_joinpath(&old_path, git_buf_cstr(&temp_path), old_name) < 0)
1912                 return -1;
1913
1914         if (git_buf_joinpath(&new_path, git_buf_cstr(&temp_path), git_buf_cstr(&normalized)) < 0)
1915                 return -1;
1916
1917         if (!git_path_exists(git_buf_cstr(&old_path))) {
1918                 error = GIT_ENOTFOUND;
1919                 goto cleanup;
1920         }
1921
1922         /*
1923          * Move the reflog to a temporary place. This two-phase renaming is required
1924          * in order to cope with funny renaming use cases when one tries to move a reference
1925          * to a partially colliding namespace:
1926          *  - a/b -> a/b/c
1927          *  - a/b/c/d -> a/b/c
1928          */
1929         if (git_buf_joinpath(&temp_path, git_buf_cstr(&temp_path), "temp_reflog") < 0)
1930                 return -1;
1931
1932         if ((fd = git_futils_mktmp(&temp_path, git_buf_cstr(&temp_path), GIT_REFLOG_FILE_MODE)) < 0) {
1933                 error = -1;
1934                 goto cleanup;
1935         }
1936
1937         p_close(fd);
1938
1939         if (p_rename(git_buf_cstr(&old_path), git_buf_cstr(&temp_path)) < 0) {
1940                 giterr_set(GITERR_OS, "failed to rename reflog for %s", new_name);
1941                 error = -1;
1942                 goto cleanup;
1943         }
1944
1945         if (git_path_isdir(git_buf_cstr(&new_path)) &&
1946                 (git_futils_rmdir_r(git_buf_cstr(&new_path), NULL, GIT_RMDIR_SKIP_NONEMPTY) < 0)) {
1947                 error = -1;
1948                 goto cleanup;
1949         }
1950
1951         if (git_futils_mkpath2file(git_buf_cstr(&new_path), GIT_REFLOG_DIR_MODE) < 0) {
1952                 error = -1;
1953                 goto cleanup;
1954         }
1955
1956         if (p_rename(git_buf_cstr(&temp_path), git_buf_cstr(&new_path)) < 0) {
1957                 giterr_set(GITERR_OS, "failed to rename reflog for %s", new_name);
1958                 error = -1;
1959         }
1960
1961 cleanup:
1962         git_buf_free(&temp_path);
1963         git_buf_free(&old_path);
1964         git_buf_free(&new_path);
1965         git_buf_free(&normalized);
1966
1967         return error;
1968 }
1969
1970 static int refdb_reflog_fs__delete(git_refdb_backend *_backend, const char *name)
1971 {
1972         int error;
1973         git_buf path = GIT_BUF_INIT;
1974
1975         git_repository *repo;
1976         refdb_fs_backend *backend;
1977
1978         assert(_backend && name);
1979
1980         backend = (refdb_fs_backend *) _backend;
1981         repo = backend->repo;
1982
1983         error = retrieve_reflog_path(&path, repo, name);
1984
1985         if (!error && git_path_exists(path.ptr))
1986                 error = p_unlink(path.ptr);
1987
1988         git_buf_free(&path);
1989
1990         return error;
1991
1992 }
1993
1994 int git_refdb_backend_fs(
1995         git_refdb_backend **backend_out,
1996         git_repository *repository)
1997 {
1998         int t = 0;
1999         git_buf gitpath = GIT_BUF_INIT;
2000         refdb_fs_backend *backend;
2001
2002         backend = git__calloc(1, sizeof(refdb_fs_backend));
2003         GITERR_CHECK_ALLOC(backend);
2004
2005         backend->repo = repository;
2006
2007         if (repository->gitdir) {
2008                 backend->gitpath = setup_namespace(repository, repository->gitdir);
2009
2010                 if (backend->gitpath == NULL)
2011                         goto fail;
2012         }
2013
2014         if (repository->commondir) {
2015                 backend->commonpath = setup_namespace(repository, repository->commondir);
2016
2017                 if (backend->commonpath == NULL)
2018                         goto fail;
2019         }
2020
2021         if (git_buf_joinpath(&gitpath, backend->commonpath, GIT_PACKEDREFS_FILE) < 0 ||
2022                 git_sortedcache_new(
2023                         &backend->refcache, offsetof(struct packref, name),
2024                         NULL, NULL, packref_cmp, git_buf_cstr(&gitpath)) < 0)
2025                 goto fail;
2026
2027         git_buf_free(&gitpath);
2028
2029         if (!git_repository__cvar(&t, backend->repo, GIT_CVAR_IGNORECASE) && t) {
2030                 backend->iterator_flags |= GIT_ITERATOR_IGNORE_CASE;
2031                 backend->direach_flags  |= GIT_PATH_DIR_IGNORE_CASE;
2032         }
2033         if (!git_repository__cvar(&t, backend->repo, GIT_CVAR_PRECOMPOSE) && t) {
2034                 backend->iterator_flags |= GIT_ITERATOR_PRECOMPOSE_UNICODE;
2035                 backend->direach_flags  |= GIT_PATH_DIR_PRECOMPOSE_UNICODE;
2036         }
2037         if ((!git_repository__cvar(&t, backend->repo, GIT_CVAR_FSYNCOBJECTFILES) && t) ||
2038                 git_repository__fsync_gitdir)
2039                 backend->fsync = 1;
2040         backend->iterator_flags |= GIT_ITERATOR_DESCEND_SYMLINKS;
2041
2042         backend->parent.exists = &refdb_fs_backend__exists;
2043         backend->parent.lookup = &refdb_fs_backend__lookup;
2044         backend->parent.iterator = &refdb_fs_backend__iterator;
2045         backend->parent.write = &refdb_fs_backend__write;
2046         backend->parent.del = &refdb_fs_backend__delete;
2047         backend->parent.rename = &refdb_fs_backend__rename;
2048         backend->parent.compress = &refdb_fs_backend__compress;
2049         backend->parent.lock = &refdb_fs_backend__lock;
2050         backend->parent.unlock = &refdb_fs_backend__unlock;
2051         backend->parent.has_log = &refdb_reflog_fs__has_log;
2052         backend->parent.ensure_log = &refdb_reflog_fs__ensure_log;
2053         backend->parent.free = &refdb_fs_backend__free;
2054         backend->parent.reflog_read = &refdb_reflog_fs__read;
2055         backend->parent.reflog_write = &refdb_reflog_fs__write;
2056         backend->parent.reflog_rename = &refdb_reflog_fs__rename;
2057         backend->parent.reflog_delete = &refdb_reflog_fs__delete;
2058
2059         *backend_out = (git_refdb_backend *)backend;
2060         return 0;
2061
2062 fail:
2063         git_buf_free(&gitpath);
2064         git__free(backend->gitpath);
2065         git__free(backend->commonpath);
2066         git__free(backend);
2067         return -1;
2068 }