tests/libgit2/object/raw/short.c

   1
   2 #include "clar_libgit2.h"
   3
   4 #include "odb.h"
   5 #include "hash.h"
   6
   7 void test_object_raw_short__oid_shortener_no_duplicates(void)
   8 {
   9         git_oid_shorten *os;
  10         int min_len;
  11
  12         os = git_oid_shorten_new(0);
  13         cl_assert(os != NULL);
  14
  15         git_oid_shorten_add(os, "22596363b3de40b06f981fb85d82312e8c0ed511");
  16         git_oid_shorten_add(os, "ce08fe4884650f067bd5703b6a59a8b3b3c99a09");
  17         git_oid_shorten_add(os, "16a0123456789abcdef4b775213c23a8bd74f5e0");
  18         min_len = git_oid_shorten_add(os, "ce08fe4884650f067bd5703b6a59a8b3b3c99a09");
  19
  20         cl_assert(min_len == GIT_OID_HEXSZ + 1);
  21
  22         git_oid_shorten_free(os);
  23 }
  24
  25 static int insert_sequential_oids(
  26         char ***out, git_oid_shorten *os, int n, int fail)
  27 {
  28         int i, min_len = 0;
  29         char numbuf[16];
  30         git_oid oid;
  31         unsigned char hashbuf[GIT_HASH_SHA1_SIZE];
  32         char **oids = git__calloc(n, sizeof(char *));
  33         cl_assert(oids != NULL);
  34
  35         for (i = 0; i < n; ++i) {
  36                 p_snprintf(numbuf, sizeof(numbuf), "%u", (unsigned int)i);
  37                 git_hash_buf(hashbuf, numbuf, strlen(numbuf), GIT_HASH_ALGORITHM_SHA1);
  38
  39                 git_oid_fromraw(&oid, hashbuf);
  40
  41                 oids[i] = git__malloc(GIT_OID_HEXSZ + 1);
  42                 cl_assert(oids[i]);
  43                 git_oid_nfmt(oids[i], GIT_OID_HEXSZ + 1, &oid);
  44
  45                 min_len = git_oid_shorten_add(os, oids[i]);
  46
  47                 /* After "fail", we expect git_oid_shorten_add to fail */
  48                 if (fail >= 0 && i >= fail)
  49             cl_assert(min_len < 0);
  50                 else
  51             cl_assert(min_len >= 0);
  52         }
  53
  54         *out = oids;
  55
  56         return min_len;
  57 }
  58
  59 static void free_oids(int n, char **oids)
  60 {
  61         int i;
  62
  63         for (i = 0; i < n; ++i) {
  64                 git__free(oids[i]);
  65         }
  66         git__free(oids);
  67 }
  68
  69 void test_object_raw_short__oid_shortener_stresstest_git_oid_shorten(void)
  70 {
  71 #define MAX_OIDS 1000
  72
  73         git_oid_shorten *os;
  74         size_t i, j;
  75         int min_len = 0, found_collision;
  76         char **oids;
  77
  78         os = git_oid_shorten_new(0);
  79         cl_assert(os != NULL);
  80
  81         /*
  82          * Insert in the shortener 1000 unique SHA1 ids
  83          */
  84         min_len = insert_sequential_oids(&oids, os, MAX_OIDS, MAX_OIDS);
  85         cl_assert(min_len > 0);
  86
  87         /*
  88          * Compare the first `min_char - 1` characters of each
  89          * SHA1 OID. If the minimizer worked, we should find at
  90          * least one collision
  91          */
  92         found_collision = 0;
  93         for (i = 0; i < MAX_OIDS; ++i) {
  94                 for (j = i + 1; j < MAX_OIDS; ++j) {
  95                         if (memcmp(oids[i], oids[j], min_len - 1) == 0)
  96                                 found_collision = 1;
  97                 }
  98         }
  99         cl_assert_equal_b(true, found_collision);
 100
 101         /*
 102          * Compare the first `min_char` characters of each
 103          * SHA1 OID. If the minimizer worked, every single preffix
 104          * should be unique.
 105          */
 106         found_collision = 0;
 107         for (i = 0; i < MAX_OIDS; ++i) {
 108                 for (j = i + 1; j < MAX_OIDS; ++j) {
 109                         if (memcmp(oids[i], oids[j], min_len) == 0)
 110                                 found_collision = 1;
 111                 }
 112         }
 113         cl_assert_equal_b(false, found_collision);
 114
 115         /* cleanup */
 116         free_oids(MAX_OIDS, oids);
 117         git_oid_shorten_free(os);
 118
 119 #undef MAX_OIDS
 120 }
 121
 122 void test_object_raw_short__oid_shortener_too_much_oids(void)
 123 {
 124     /* The magic number of oids at which an oid_shortener will fail.
 125      * This was experimentally established. */
 126 #define MAX_OIDS 24556
 127
 128         git_oid_shorten *os;
 129         char **oids;
 130
 131         os = git_oid_shorten_new(0);
 132         cl_assert(os != NULL);
 133
 134         cl_assert(insert_sequential_oids(&oids, os, MAX_OIDS, MAX_OIDS - 1) < 0);
 135
 136         free_oids(MAX_OIDS, oids);
 137         git_oid_shorten_free(os);
 138
 139 #undef MAX_OIDS
 140 }