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