correct.c

   1 /*
   2  * Copyright (C) 2012, 2013
   3  *     Dale Weiler
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23 #include "gmqcc.h"
  24
  25 /*
  26  * This is a very clever method for correcting mistakes in QuakeC code
  27  * most notably when invalid identifiers are used or inproper assignments;
  28  * we can proprly lookup in multiple dictonaries (depening on the rules
  29  * of what the task is trying to acomplish) to find the best possible
  30  * match.
  31  *
  32  *
  33  * A little about how it works, and probability theory:
  34  *
  35  *  When given an identifier (which we will denote I), we're essentially
  36  *  just trying to choose the most likely correction for that identifier.
  37  *  (the actual "correction" can very well be the identifier itself).
  38  *  There is actually no way to know for sure that certian identifers
  39  *  such as "lates", need to be corrected to "late" or "latest" or any
  40  *  other permutations that look lexically the same.  This is why we
  41  *  must advocate the usage of probabilities.  This means that instead of
  42  *  just guessing, instead we're trying to find the correction for C,
  43  *  out of all possible corrections that maximizes the probability of C
  44  *  for the original identifer I.
  45  *
  46  *  Bayes' Therom suggests something of the following:
  47  *      AC P(I|C) P(C) / P(I)
  48  *  Since P(I) is the same for every possibly I, we can ignore it giving
  49  *      AC P(I|C) P(C)
  50  *
  51  *  This greatly helps visualize how the parts of the expression are performed
  52  *  there is essentially three, from right to left we perform the following:
  53  *
  54  *  1: P(C), the probability that a proposed correction C will stand on its
  55  *     own.  This is called the language model.
  56  *
  57  *  2: P(I|C), the probability that I would be used, when the programmer
  58  *     really meant C.  This is the error model.
  59  *
  60  *  3: AC, the control mechanisim, an enumerator if you will, one that
  61  *     enumerates all feasible values of C, to determine the one that
  62  *     gives the greatest probability score.
  63  *
  64  *      In reality the requirement for a more complex expression involving
  65  *  two seperate models is considerably a waste.  But one must recognize
  66  *  that P(C|I) is already conflating two factors.  It's just much simpler
  67  *  to seperate the two models and deal with them explicitaly.  To properly
  68  *  estimate P(C|I) you have to consider both the probability of C and
  69  *  probability of the transposition from C to I.  It's simply much more
  70  *  cleaner, and direct to seperate the two factors.
  71  *
  72  * A little information on additional algorithms used:
  73  *
  74  *   Initially when I implemented this corrector, it was very slow.
  75  *   Need I remind you this is essentially a brute force attack on strings,
  76  *   and since every transformation requires dynamic memory allocations,
  77  *   you can easily imagine where most of the runtime conflated.  Yes
  78  *   It went right to malloc.  More than THREE MILLION malloc calls are
  79  *   performed for an identifier about 16 bytes long.  This was such a
  80  *   shock to me.  A forward allocator (or as some call it a bump-point
  81  *   allocator, or just a memory pool) was implemented. To combat this.
  82  *
  83  *   But of course even other factors were making it slow.  Initially
  84  *   this used a hashtable.  And hashtables have a good constant lookup
  85  *   time complexity.  But the problem wasn't in the hashtable, it was
  86  *   in the hashing (despite having one of the fastest hash functions
  87  *   known).  Remember those 3 million mallocs? Well for every malloc
  88  *   there is also a hash.  After 3 million hashes .. you start to get
  89  *   very slow.  To combat this I had suggested burst tries to Blub.
  90  *   The next day he had implemented them. Sure enough this brought
  91  *   down the runtime by a factory > 100%
  92  */
  93
  94
  95 #define CORRECT_POOLSIZE (128*1024*1024)
  96 /*
  97  * A forward allcator for the corrector.  This corrector requires a lot
  98  * of allocations.  This forward allocator combats all those allocations
  99  * and speeds us up a little.  It also saves us space in a way since each
 100  * allocation isn't wasting a little header space for when NOTRACK isn't
 101  * defined.
 102  */
 103 static unsigned char **correct_pool_data = NULL;
 104 static unsigned char  *correct_pool_this = NULL;
 105 static size_t          correct_pool_addr = 0;
 106
 107 static GMQCC_INLINE void correct_pool_new(void) {
 108     correct_pool_addr = 0;
 109     correct_pool_this = (unsigned char *)mem_a(CORRECT_POOLSIZE);
 110
 111     vec_push(correct_pool_data, correct_pool_this);
 112 }
 113
 114 static GMQCC_INLINE void *correct_pool_alloc(size_t bytes) {
 115     void *data;
 116     if (correct_pool_addr + bytes >= CORRECT_POOLSIZE)
 117         correct_pool_new();
 118
 119     data               = correct_pool_this;
 120     correct_pool_this += bytes;
 121     correct_pool_addr += bytes;
 122
 123     return data;
 124 }
 125
 126 static GMQCC_INLINE void correct_pool_delete(void) {
 127     size_t i;
 128     for (i = 0; i < vec_size(correct_pool_data); ++i)
 129         mem_d(correct_pool_data[i]);
 130
 131     correct_pool_data = NULL;
 132     correct_pool_this = NULL;
 133     correct_pool_addr = 0;
 134 }
 135
 136
 137 static GMQCC_INLINE char *correct_pool_claim(const char *data) {
 138     char *claim = util_strdup(data);
 139     correct_pool_delete();
 140     return claim;
 141 }
 142
 143 /*
 144  * A fast space efficent trie for a disctonary of identifiers.  This is
 145  * faster than a hashtable for one reason.  A hashtable itself may have
 146  * fast constant lookup time, but the hash itself must be very fast. We
 147  * have one of the fastest hash functions for strings, but if you do a
 148  * lost of hashing (which we do, almost 3 million hashes per identifier)
 149  * a hashtable becomes slow. Very Very Slow.
 150  */
 151 correct_trie_t* correct_trie_new() {
 152     correct_trie_t *t = (correct_trie_t*)mem_a(sizeof(correct_trie_t));
 153     t->value   = NULL;
 154     t->entries = NULL;
 155     return t;
 156 }
 157
 158 void correct_trie_del_sub(correct_trie_t *t) {
 159     size_t i;
 160     for (i = 0; i < vec_size(t->entries); ++i)
 161         correct_trie_del_sub(&t->entries[i]);
 162     vec_free(t->entries);
 163 }
 164
 165 void correct_trie_del(correct_trie_t *t) {
 166     size_t i;
 167     for (i = 0; i < vec_size(t->entries); ++i)
 168         correct_trie_del_sub(&t->entries[i]);
 169     vec_free(t->entries);
 170     mem_d(t);
 171 }
 172
 173 void* correct_trie_get(const correct_trie_t *t, const char *key) {
 174     const unsigned char *data = (const unsigned char*)key;
 175     while (*data) {
 176         unsigned char ch = *data;
 177         const size_t  vs = vec_size(t->entries);
 178         size_t        i;
 179         const correct_trie_t *entries = t->entries;
 180         for (i = 0; i < vs; ++i) {
 181             if (entries[i].ch == ch) {
 182                 t = &entries[i];
 183                 ++data;
 184                 break;
 185             }
 186         }
 187         if (i == vs)
 188             return NULL;
 189     }
 190     return t->value;
 191 }
 192
 193 void correct_trie_set(correct_trie_t *t, const char *key, void * const value) {
 194     const unsigned char *data = (const unsigned char*)key;
 195     while (*data) {
 196         unsigned char ch = *data;
 197         correct_trie_t       *entries = t->entries;
 198         const size_t  vs = vec_size(t->entries);
 199         size_t        i;
 200         for (i = 0; i < vs; ++i) {
 201             if (entries[i].ch == ch) {
 202                 t = &entries[i];
 203                 break;
 204             }
 205         }
 206         if (i == vs) {
 207             correct_trie_t *elem  = (correct_trie_t*)vec_add(t->entries, 1);
 208             elem->ch      = ch;
 209             elem->value   = NULL;
 210             elem->entries = NULL;
 211             t = elem;
 212         }
 213         ++data;
 214     }
 215     t->value = value;
 216 }
 217
 218
 219 /*
 220  * Implementation of the corrector algorithm commences. A very efficent
 221  * brute-force attack (thanks to tries and mempool :-)).
 222  */
 223 static size_t *correct_find(correct_trie_t *table, const char *word) {
 224     return (size_t*)correct_trie_get(table, word);
 225 }
 226
 227 static int correct_update(correct_trie_t* *table, const char *word) {
 228     size_t *data = correct_find(*table, word);
 229     if (!data)
 230         return 0;
 231
 232     (*data)++;
 233     return 1;
 234 }
 235
 236 void correct_add(correct_trie_t* table, size_t ***size, const char *ident) {
 237     size_t     *data = NULL;
 238     const char *add  = ident;
 239
 240     if (!correct_update(&table, add)) {
 241         data  = (size_t*)mem_a(sizeof(size_t));
 242         *data = 1;
 243
 244         vec_push((*size), data);
 245         correct_trie_set(table, add, data);
 246     }
 247 }
 248
 249 void correct_del(correct_trie_t* dictonary, size_t **data) {
 250     size_t i;
 251     const size_t vs = vec_size(data);
 252     for (i = 0; i < vs; i++)
 253         mem_d(data[i]);
 254
 255     vec_free(data);
 256     correct_trie_del(dictonary);
 257 }
 258
 259 /*
 260  * _ is valid in identifiers. I've yet to implement numerics however
 261  * because they're only valid after the first character is of a _, or
 262  * alpha character.
 263  */
 264 static const char correct_alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";
 265
 266 /*
 267  * correcting logic for the following forms of transformations:
 268  *  1) deletion
 269  *  2) transposition
 270  *  3) alteration
 271  *  4) insertion
 272  */
 273 static size_t correct_deletion(const char *ident, char **array, size_t index) {
 274     size_t itr;
 275     size_t len = strlen(ident);
 276
 277     for (itr = 0; itr < len; itr++) {
 278         char *a = (char*)correct_pool_alloc(len+1);
 279         memcpy(a, ident, itr);
 280         memcpy(a + itr, ident + itr + 1, len - itr);
 281         array[index + itr] = a;
 282     }
 283
 284     return itr;
 285 }
 286
 287 static size_t correct_transposition(const char *ident, char **array, size_t index) {
 288     size_t itr;
 289     size_t len = strlen(ident);
 290
 291     for (itr = 0; itr < len - 1; itr++) {
 292         char  tmp;
 293         char *a = (char*)correct_pool_alloc(len+1);
 294         memcpy(a, ident, len+1);
 295         tmp      = a[itr];
 296         a[itr  ] = a[itr+1];
 297         a[itr+1] = tmp;
 298         array[index + itr] = a;
 299     }
 300
 301     return itr;
 302 }
 303
 304 static size_t correct_alteration(const char *ident, char **array, size_t index) {
 305     size_t itr;
 306     size_t jtr;
 307     size_t ktr;
 308     size_t len    = strlen(ident);
 309
 310     for (itr = 0, ktr = 0; itr < len; itr++) {
 311         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
 312             char *a = (char*)correct_pool_alloc(len+1);
 313             memcpy(a, ident, len+1);
 314             a[itr] = correct_alpha[jtr];
 315             array[index + ktr] = a;
 316         }
 317     }
 318
 319     return ktr;
 320 }
 321
 322 static size_t correct_insertion(const char *ident, char **array, size_t index) {
 323     size_t itr;
 324     size_t jtr;
 325     size_t ktr;
 326     const size_t len    = strlen(ident);
 327
 328     for (itr = 0, ktr = 0; itr <= len; itr++) {
 329         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
 330             char *a = (char*)correct_pool_alloc(len+2);
 331             memcpy(a, ident, itr);
 332             memcpy(a + itr + 1, ident + itr, len - itr + 1);
 333             a[itr] = correct_alpha[jtr];
 334             array[index + ktr] = a;
 335         }
 336     }
 337
 338     return ktr;
 339 }
 340
 341 static GMQCC_INLINE size_t correct_size(const char *ident) {
 342     /*
 343      * deletion      = len
 344      * transposition = len - 1
 345      * alteration    = len * sizeof(correct_alpha)
 346      * insertion     = (len + 1) * sizeof(correct_alpha)
 347      */
 348
 349     register size_t len = strlen(ident);
 350     return (len) + (len - 1) + (len * (sizeof(correct_alpha)-1)) + ((len + 1) * (sizeof(correct_alpha)-1));
 351 }
 352
 353 static char **correct_edit(const char *ident) {
 354     size_t next;
 355     char **find = (char**)correct_pool_alloc(correct_size(ident) * sizeof(char*));
 356
 357     if (!find)
 358         return NULL;
 359
 360     next  = correct_deletion     (ident, find, 0);
 361     next += correct_transposition(ident, find, next);
 362     next += correct_alteration   (ident, find, next);
 363     /*****/ correct_insertion    (ident, find, next);
 364
 365     return find;
 366 }
 367
 368 /*
 369  * We could use a hashtable but the space complexity isn't worth it
 370  * since we're only going to determine the "did you mean?" identifier
 371  * on error.
 372  */
 373 static int correct_exist(char **array, size_t rows, char *ident) {
 374     size_t itr;
 375     for (itr = 0; itr < rows; itr++)
 376         if (!strcmp(array[itr], ident))
 377             return 1;
 378
 379     return 0;
 380 }
 381
 382 static GMQCC_INLINE char **correct_known_resize(char **res, size_t *allocated, size_t size) {
 383     size_t oldallocated = *allocated;
 384     char **out;
 385     if (size+1 < *allocated)
 386         return res;
 387
 388     *allocated += 32;
 389     out = correct_pool_alloc(sizeof(*res) * *allocated);
 390     memcpy(out, res, sizeof(*res) * oldallocated);
 391     return out;
 392 }
 393
 394 static char **correct_known(correct_trie_t* table, char **array, size_t rows, size_t *next) {
 395     size_t itr;
 396     size_t jtr;
 397     size_t len;
 398     size_t row;
 399     size_t nxt = 8;
 400     char **res = correct_pool_alloc(sizeof(char *) * nxt);
 401     char **end = NULL;
 402
 403     for (itr = 0, len = 0; itr < rows; itr++) {
 404         end = correct_edit(array[itr]);
 405         row = correct_size(array[itr]);
 406
 407         for (jtr = 0; jtr < row; jtr++) {
 408             if (correct_find(table, end[jtr]) && !correct_exist(res, len, end[jtr])) {
 409                 res        = correct_known_resize(res, &nxt, len+1);
 410                 res[len++] = end[jtr];
 411             }
 412         }
 413     }
 414
 415     *next = len;
 416     return res;
 417 }
 418
 419 static char *correct_maximum(correct_trie_t* table, char **array, size_t rows) {
 420     char   *str  = NULL;
 421     size_t *itm  = NULL;
 422     size_t  itr;
 423     size_t  top;
 424
 425     for (itr = 0, top = 0; itr < rows; itr++) {
 426         if ((itm = correct_find(table, array[itr])) && (*itm > top)) {
 427             top = *itm;
 428             str = array[itr];
 429         }
 430     }
 431
 432     return str;
 433 }
 434
 435 /*
 436  * This is the exposed interface:
 437  * takes a table for the dictonary a vector of sizes (used for internal
 438  * probability calculation, and an identifier to "correct"
 439  *
 440  * the add function works the same.  Except the identifier is used to
 441  * add to the dictonary.
 442  */
 443
 444 char *correct_str(correct_trie_t* table, const char *ident) {
 445     char **e1;
 446     char **e2;
 447     char  *e1ident;
 448     char  *e2ident;
 449
 450     size_t e1rows = 0;
 451     size_t e2rows = 0;
 452
 453     correct_pool_new();
 454
 455     /* needs to be allocated for free later */
 456     if (correct_find(table, ident))
 457         return correct_pool_claim(ident);
 458
 459     if ((e1rows = correct_size(ident))) {
 460         e1      = correct_edit(ident);
 461
 462         if ((e1ident = correct_maximum(table, e1, e1rows)))
 463             return correct_pool_claim(e1ident);
 464     }
 465
 466     e2 = correct_known(table, e1, e1rows, &e2rows);
 467     if (e2rows && ((e2ident = correct_maximum(table, e2, e2rows))))
 468         return correct_pool_claim(e2ident);
 469
 470
 471     correct_pool_delete();
 472     return util_strdup(ident);
 473 }