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  *  Research tells us that 80% to 95% of all spelling errors have an edit
  73  *  distance no greater than one.  Knowing this we can optimize for most
  74  *  cases of mistakes without taking a performance hit.  Which is what we
  75  *  base longer edit distances off of.  Opposed to the original method of
  76  *  I had concieved of checking everything.
  77  *
  78  * A little information on additional algorithms used:
  79  *
  80  *   Initially when I implemented this corrector, it was very slow.
  81  *   Need I remind you this is essentially a brute force attack on strings,
  82  *   and since every transformation requires dynamic memory allocations,
  83  *   you can easily imagine where most of the runtime conflated.  Yes
  84  *   It went right to malloc.  More than THREE MILLION malloc calls are
  85  *   performed for an identifier about 16 bytes long.  This was such a
  86  *   shock to me.  A forward allocator (or as some call it a bump-point
  87  *   allocator, or just a memory pool) was implemented. To combat this.
  88  *
  89  *   But of course even other factors were making it slow.  Initially
  90  *   this used a hashtable.  And hashtables have a good constant lookup
  91  *   time complexity.  But the problem wasn't in the hashtable, it was
  92  *   in the hashing (despite having one of the fastest hash functions
  93  *   known).  Remember those 3 million mallocs? Well for every malloc
  94  *   there is also a hash.  After 3 million hashes .. you start to get
  95  *   very slow.  To combat this I had suggested burst tries to Blub.
  96  *   The next day he had implemented them. Sure enough this brought
  97  *   down the runtime by a factory > 100%
  98  *
  99  * Future Work (If we really need it)
 100  *
 101  *   Currently we can only distinguishes one source of error in the
 102  *   language model we use.  This could become an issue for identifiers
 103  *   that have close colliding rates, e.g colate->coat yields collate.
 104  *
 105  *   Currently the error model has been fairly trivial, the smaller the
 106  *   edit distance the smaller the error.  This usually causes some un-
 107  *   expected problems. e.g reciet->recite yields recipt.  For QuakeC
 108  *   this could become a problem when lots of identifiers are involved.
 109  *
 110  *   Our control mechanisim could use a limit, i.e limit the number of
 111  *   sets of edits for distance X.  This would also increase execution
 112  *   speed considerably.
 113  */
 114
 115
 116 #define CORRECT_POOLSIZE (128*1024*1024)
 117 /*
 118  * A forward allcator for the corrector.  This corrector requires a lot
 119  * of allocations.  This forward allocator combats all those allocations
 120  * and speeds us up a little.  It also saves us space in a way since each
 121  * allocation isn't wasting a little header space for when NOTRACK isn't
 122  * defined.
 123  */
 124 static unsigned char **correct_pool_data = NULL;
 125 static unsigned char  *correct_pool_this = NULL;
 126 static size_t          correct_pool_addr = 0;
 127
 128 static GMQCC_INLINE void correct_pool_new(void) {
 129     correct_pool_addr = 0;
 130     correct_pool_this = (unsigned char *)mem_a(CORRECT_POOLSIZE);
 131
 132     vec_push(correct_pool_data, correct_pool_this);
 133 }
 134
 135 static GMQCC_INLINE void *correct_pool_alloc(size_t bytes) {
 136     void *data;
 137     if (correct_pool_addr + bytes >= CORRECT_POOLSIZE)
 138         correct_pool_new();
 139
 140     data               = correct_pool_this;
 141     correct_pool_this += bytes;
 142     correct_pool_addr += bytes;
 143
 144     return data;
 145 }
 146
 147 static GMQCC_INLINE void correct_pool_delete(void) {
 148     size_t i;
 149     for (i = 0; i < vec_size(correct_pool_data); ++i)
 150         mem_d(correct_pool_data[i]);
 151
 152     correct_pool_data = NULL;
 153     correct_pool_this = NULL;
 154     correct_pool_addr = 0;
 155 }
 156
 157
 158 static GMQCC_INLINE char *correct_pool_claim(const char *data) {
 159     char *claim = util_strdup(data);
 160     correct_pool_delete();
 161     return claim;
 162 }
 163
 164 /*
 165  * A fast space efficent trie for a disctonary of identifiers.  This is
 166  * faster than a hashtable for one reason.  A hashtable itself may have
 167  * fast constant lookup time, but the hash itself must be very fast. We
 168  * have one of the fastest hash functions for strings, but if you do a
 169  * lost of hashing (which we do, almost 3 million hashes per identifier)
 170  * a hashtable becomes slow. Very Very Slow.
 171  */
 172 correct_trie_t* correct_trie_new() {
 173     correct_trie_t *t = (correct_trie_t*)mem_a(sizeof(correct_trie_t));
 174     t->value   = NULL;
 175     t->entries = NULL;
 176     return t;
 177 }
 178
 179 void correct_trie_del_sub(correct_trie_t *t) {
 180     size_t i;
 181     for (i = 0; i < vec_size(t->entries); ++i)
 182         correct_trie_del_sub(&t->entries[i]);
 183     vec_free(t->entries);
 184 }
 185
 186 void correct_trie_del(correct_trie_t *t) {
 187     size_t i;
 188     for (i = 0; i < vec_size(t->entries); ++i)
 189         correct_trie_del_sub(&t->entries[i]);
 190     vec_free(t->entries);
 191     mem_d(t);
 192 }
 193
 194 void* correct_trie_get(const correct_trie_t *t, const char *key) {
 195     const unsigned char *data = (const unsigned char*)key;
 196     while (*data) {
 197         unsigned char ch = *data;
 198         const size_t  vs = vec_size(t->entries);
 199         size_t        i;
 200         const correct_trie_t *entries = t->entries;
 201         for (i = 0; i < vs; ++i) {
 202             if (entries[i].ch == ch) {
 203                 t = &entries[i];
 204                 ++data;
 205                 break;
 206             }
 207         }
 208         if (i == vs)
 209             return NULL;
 210     }
 211     return t->value;
 212 }
 213
 214 void correct_trie_set(correct_trie_t *t, const char *key, void * const value) {
 215     const unsigned char *data = (const unsigned char*)key;
 216     while (*data) {
 217         const size_t    vs      = vec_size(t->entries);
 218         unsigned char   ch      = *data;
 219         correct_trie_t *entries = t->entries;
 220         size_t          i;
 221
 222         for (i = 0; i < vs; ++i) {
 223             if (entries[i].ch == ch) {
 224                 t = &entries[i];
 225                 break;
 226             }
 227         }
 228         if (i == vs) {
 229             correct_trie_t *elem  = (correct_trie_t*)vec_add(t->entries, 1);
 230
 231             elem->ch      = ch;
 232             elem->value   = NULL;
 233             elem->entries = NULL;
 234             t             = elem;
 235         }
 236         ++data;
 237     }
 238     t->value = value;
 239 }
 240
 241
 242 /*
 243  * Implementation of the corrector algorithm commences. A very efficent
 244  * brute-force attack (thanks to tries and mempool :-)).
 245  */
 246 static size_t *correct_find(correct_trie_t *table, const char *word) {
 247     return (size_t*)correct_trie_get(table, word);
 248 }
 249
 250 static int correct_update(correct_trie_t* *table, const char *word) {
 251     size_t *data = correct_find(*table, word);
 252     if (!data)
 253         return 0;
 254
 255     (*data)++;
 256     return 1;
 257 }
 258
 259 void correct_add(correct_trie_t* table, size_t ***size, const char *ident) {
 260     size_t     *data = NULL;
 261     const char *add  = ident;
 262
 263     if (!correct_update(&table, add)) {
 264         data  = (size_t*)mem_a(sizeof(size_t));
 265         *data = 1;
 266
 267         vec_push((*size), data);
 268         correct_trie_set(table, add, data);
 269     }
 270 }
 271
 272 void correct_del(correct_trie_t* dictonary, size_t **data) {
 273     size_t       i;
 274     const size_t vs = vec_size(data);
 275
 276     for (i = 0; i < vs; i++)
 277         mem_d(data[i]);
 278
 279     vec_free(data);
 280     correct_trie_del(dictonary);
 281 }
 282
 283 /*
 284  * _ is valid in identifiers. I've yet to implement numerics however
 285  * because they're only valid after the first character is of a _, or
 286  * alpha character.
 287  */
 288 static const char correct_alpha[] = "abcdefghijklmnopqrstuvwxyz"
 289                                     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 290                                     "_"; /* TODO: Numbers ... */
 291
 292 /*
 293  * correcting logic for the following forms of transformations:
 294  *  1) deletion
 295  *  2) transposition
 296  *  3) alteration
 297  *  4) insertion
 298  */
 299 static size_t correct_deletion(const char *ident, char **array, size_t index) {
 300     size_t itr;
 301     size_t len = strlen(ident);
 302
 303     for (itr = 0; itr < len; itr++) {
 304         char *a = (char*)correct_pool_alloc(len+1);
 305         memcpy(a, ident, itr);
 306         memcpy(a + itr, ident + itr + 1, len - itr);
 307         array[index + itr] = a;
 308     }
 309
 310     return itr;
 311 }
 312
 313 static size_t correct_transposition(const char *ident, char **array, size_t index) {
 314     size_t itr;
 315     size_t len = strlen(ident);
 316
 317     for (itr = 0; itr < len - 1; itr++) {
 318         char  tmp;
 319         char *a = (char*)correct_pool_alloc(len+1);
 320         memcpy(a, ident, len+1);
 321         tmp      = a[itr];
 322         a[itr  ] = a[itr+1];
 323         a[itr+1] = tmp;
 324         array[index + itr] = a;
 325     }
 326
 327     return itr;
 328 }
 329
 330 static size_t correct_alteration(const char *ident, char **array, size_t index) {
 331     size_t itr;
 332     size_t jtr;
 333     size_t ktr;
 334     size_t len    = strlen(ident);
 335
 336     for (itr = 0, ktr = 0; itr < len; itr++) {
 337         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
 338             char *a = (char*)correct_pool_alloc(len+1);
 339             memcpy(a, ident, len+1);
 340             a[itr] = correct_alpha[jtr];
 341             array[index + ktr] = a;
 342         }
 343     }
 344
 345     return ktr;
 346 }
 347
 348 static size_t correct_insertion(const char *ident, char **array, size_t index) {
 349     size_t itr;
 350     size_t jtr;
 351     size_t ktr;
 352     const size_t len    = strlen(ident);
 353
 354     for (itr = 0, ktr = 0; itr <= len; itr++) {
 355         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
 356             char *a = (char*)correct_pool_alloc(len+2);
 357             memcpy(a, ident, itr);
 358             memcpy(a + itr + 1, ident + itr, len - itr + 1);
 359             a[itr] = correct_alpha[jtr];
 360             array[index + ktr] = a;
 361         }
 362     }
 363
 364     return ktr;
 365 }
 366
 367 static GMQCC_INLINE size_t correct_size(const char *ident) {
 368     /*
 369      * deletion      = len
 370      * transposition = len - 1
 371      * alteration    = len * sizeof(correct_alpha)
 372      * insertion     = (len + 1) * sizeof(correct_alpha)
 373      */
 374
 375     register size_t len = strlen(ident);
 376     return (len) + (len - 1) + (len * (sizeof(correct_alpha)-1)) + ((len + 1) * (sizeof(correct_alpha)-1));
 377 }
 378
 379 static char **correct_edit(const char *ident) {
 380     size_t next;
 381     char **find = (char**)correct_pool_alloc(correct_size(ident) * sizeof(char*));
 382
 383     if (!find)
 384         return NULL;
 385
 386     next  = correct_deletion     (ident, find, 0);
 387     next += correct_transposition(ident, find, next);
 388     next += correct_alteration   (ident, find, next);
 389     /*****/ correct_insertion    (ident, find, next);
 390
 391     return find;
 392 }
 393
 394 /*
 395  * We could use a hashtable but the space complexity isn't worth it
 396  * since we're only going to determine the "did you mean?" identifier
 397  * on error.
 398  */
 399 static int correct_exist(char **array, size_t rows, char *ident) {
 400     size_t itr;
 401     for (itr = 0; itr < rows; itr++)
 402         if (!strcmp(array[itr], ident))
 403             return 1;
 404
 405     return 0;
 406 }
 407
 408 static GMQCC_INLINE char **correct_known_resize(char **res, size_t *allocated, size_t size) {
 409     size_t oldallocated = *allocated;
 410     char **out;
 411     if (size+1 < *allocated)
 412         return res;
 413
 414     *allocated += 32;
 415     out = correct_pool_alloc(sizeof(*res) * *allocated);
 416     memcpy(out, res, sizeof(*res) * oldallocated);
 417     return out;
 418 }
 419
 420 static char **correct_known(correct_trie_t* table, char **array, size_t rows, size_t *next) {
 421     size_t itr = 0;
 422     size_t jtr = 0;
 423     size_t len = 0;
 424     size_t row = 0;
 425     size_t nxt = 8;
 426     char **res = correct_pool_alloc(sizeof(char *) * nxt);
 427     char **end = NULL;
 428
 429     for (; itr < rows; itr++) {
 430         end = correct_edit(array[itr]);
 431         row = correct_size(array[itr]);
 432
 433         for (; jtr < row; jtr++) {
 434             if (correct_find(table, end[jtr]) && !correct_exist(res, len, end[jtr])) {
 435                 res        = correct_known_resize(res, &nxt, len+1);
 436                 res[len++] = end[jtr];
 437             }
 438         }
 439     }
 440
 441     *next = len;
 442     return res;
 443 }
 444
 445 static char *correct_maximum(correct_trie_t* table, char **array, size_t rows) {
 446     char   *str = NULL;
 447     size_t *itm = NULL;
 448     size_t  itr = 0;
 449     size_t  top = 0;
 450
 451     for (; itr < rows; itr++) {
 452         if ((itm = correct_find(table, array[itr])) && (*itm > top)) {
 453             top = *itm;
 454             str = array[itr];
 455         }
 456     }
 457
 458     return str;
 459 }
 460
 461 /*
 462  * This is the exposed interface:
 463  * takes a table for the dictonary a vector of sizes (used for internal
 464  * probability calculation, and an identifier to "correct"
 465  *
 466  * the add function works the same.  Except the identifier is used to
 467  * add to the dictonary.
 468  */
 469 char *correct_str(correct_trie_t* table, const char *ident) {
 470     char **e1;
 471     char **e2;
 472     char  *e1ident;
 473     char  *e2ident;
 474
 475     size_t e1rows = 0;
 476     size_t e2rows = 0;
 477
 478     correct_pool_new();
 479
 480     /* needs to be allocated for free later */
 481     if (correct_find(table, ident))
 482         return correct_pool_claim(ident);
 483
 484     if ((e1rows = correct_size(ident))) {
 485         e1      = correct_edit(ident);
 486
 487         if ((e1ident = correct_maximum(table, e1, e1rows)))
 488             return correct_pool_claim(e1ident);
 489     }
 490
 491     e2 = correct_known(table, e1, e1rows, &e2rows);
 492     if (e2rows && ((e2ident = correct_maximum(table, e2, e2rows))))
 493         return correct_pool_claim(e2ident);
 494
 495
 496     correct_pool_delete();
 497     return util_strdup(ident);
 498 }