moving -Olocal-temps to -O4 until the issues are solved
[xonotic/gmqcc.git] / correct.c
1 /*
2  * Copyright (C) 2012, 2013
3  *     Dale Weiler
4  *     Wolfgang Bumiller
5  * 
6  * Permission is hereby granted, free of charge, to any person obtaining a copy of
7  * this software and associated documentation files (the "Software"), to deal in
8  * the Software without restriction, including without limitation the rights to
9  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
10  * of the Software, and to permit persons to whom the Software is furnished to do
11  * so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in all
14  * copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 #include "gmqcc.h"
25
26 /*
27  * This is a very clever method for correcting mistakes in QuakeC code
28  * most notably when invalid identifiers are used or inproper assignments;
29  * we can proprly lookup in multiple dictonaries (depening on the rules
30  * of what the task is trying to acomplish) to find the best possible
31  * match.
32  *
33  *
34  * A little about how it works, and probability theory:
35  *
36  *  When given an identifier (which we will denote I), we're essentially
37  *  just trying to choose the most likely correction for that identifier.
38  *  (the actual "correction" can very well be the identifier itself).
39  *  There is actually no way to know for sure that certian identifers
40  *  such as "lates", need to be corrected to "late" or "latest" or any
41  *  other permutations that look lexically the same.  This is why we
42  *  must advocate the usage of probabilities.  This means that instead of
43  *  just guessing, instead we're trying to find the correction for C,
44  *  out of all possible corrections that maximizes the probability of C
45  *  for the original identifer I.
46  *
47  *  Thankfully there exists some theroies for probalistic interpretations
48  *  of data.  Since we're operating on two distictive intepretations, the
49  *  transposition from I to C. We need something that can express how much
50  *  degree of I should rationally change to become C.  this is called the
51  *  Bayesian interpretation. You can read more about it from here:
52  *  http://www.celiagreen.com/charlesmccreery/statistics/bayestutorial.pdf
53  *  (which is probably the only good online documentation for bayes theroy
54  *  no lie.  Everything else just sucks ..)  
55  * 
56  *  Bayes' Thereom suggests something like the following:
57  *      AC P(I|C) P(C) / P(I)
58  * 
59  *  However since P(I) is the same for every possibility of I, we can
60  *  completley ignore it giving just:
61  *      AC P(I|C) P(C)
62  *
63  *  This greatly helps visualize how the parts of the expression are performed
64  *  there is essentially three, from right to left we perform the following:
65  *
66  *  1: P(C), the probability that a proposed correction C will stand on its
67  *     own.  This is called the language model.
68  *
69  *  2: P(I|C), the probability that I would be used, when the programmer
70  *     really meant C.  This is the error model.
71  *
72  *  3: AC, the control mechanisim, an enumerator if you will, one that
73  *     enumerates all feasible values of C, to determine the one that
74  *     gives the greatest probability score.
75  * 
76  *  In reality the requirement for a more complex expression involving
77  *  two seperate models is considerably a waste.  But one must recognize
78  *  that P(C|I) is already conflating two factors.  It's just much simpler
79  *  to seperate the two models and deal with them explicitaly.  To properly
80  *  estimate P(C|I) you have to consider both the probability of C and
81  *  probability of the transposition from C to I.  It's simply much more
82  *  cleaner, and direct to seperate the two factors.
83  *
84  *  Research tells us that 80% to 95% of all spelling errors have an edit
85  *  distance no greater than one.  Knowing this we can optimize for most
86  *  cases of mistakes without taking a performance hit.  Which is what we
87  *  base longer edit distances off of.  Opposed to the original method of
88  *  I had concieved of checking everything.     
89  *  
90  * A little information on additional algorithms used:
91  *
92  *   Initially when I implemented this corrector, it was very slow.
93  *   Need I remind you this is essentially a brute force attack on strings,
94  *   and since every transformation requires dynamic memory allocations,
95  *   you can easily imagine where most of the runtime conflated.  Yes
96  *   It went right to malloc.  More than THREE MILLION malloc calls are
97  *   performed for an identifier about 16 bytes long.  This was such a
98  *   shock to me.  A forward allocator (or as some call it a bump-point
99  *   allocator, or just a memory pool) was implemented. To combat this.
100  *
101  *   But of course even other factors were making it slow.  Initially
102  *   this used a hashtable.  And hashtables have a good constant lookup
103  *   time complexity.  But the problem wasn't in the hashtable, it was
104  *   in the hashing (despite having one of the fastest hash functions
105  *   known).  Remember those 3 million mallocs? Well for every malloc
106  *   there is also a hash.  After 3 million hashes .. you start to get
107  *   very slow.  To combat this I had suggested burst tries to Blub.
108  *   The next day he had implemented them. Sure enough this brought
109  *   down the runtime by a factor > 100%
110  *
111  *   The trie initially was designed to work on all strings, but later it
112  *   became aparent that not only was this not a requirement. It was also
113  *   slowing down get/sets' for the trie.  To fully understand, only
114  *   correct_alpha needs to be understood by the trie system, knowing this
115  *   We can combat the slowness using a very clever but evil optimization.
116  *   By Setting a fixed sized amount of branches for the trie using a
117  *   char-to-index map into the branches. We've complelty made the trie
118  *   accesses entierly constant in lookup time.  No really, a lookup is
119  *   literally trie[str[0]] [str[1]] [2] .... .value.
120  * 
121  * 
122  * Future Work (If we really need it)
123  *
124  *   Currently we can only distinguish one source of error in the
125  *   language model we use.  This could become an issue for identifiers
126  *   that have close colliding rates, e.g colate->coat yields collate.
127  *
128  *   Currently the error model has been fairly trivial, the smaller the
129  *   edit distance the smaller the error.  This usually causes some un-
130  *   expected problems. e.g reciet->recite yields recipt.  For QuakeC
131  *   this could become a problem when lots of identifiers are involved. 
132  *
133  *   Our control mechanisim could use a limit, i.e limit the number of
134  *   sets of edits for distance X.  This would also increase execution
135  *   speed considerably.
136  */
137
138
139 #define CORRECT_POOL_SIZE (128*1024*1024)
140 /*
141  * A forward allcator for the corrector.  This corrector requires a lot
142  * of allocations.  This forward allocator combats all those allocations
143  * and speeds us up a little.  It also saves us space in a way since each
144  * allocation isn't wasting a little header space for when NOTRACK isn't
145  * defined.
146  */
147 static unsigned char **correct_pool_data = NULL;
148 static unsigned char  *correct_pool_this = NULL;
149 static size_t          correct_pool_addr = 0;
150
151 static GMQCC_INLINE void correct_pool_new(void) {
152     correct_pool_addr = 0;
153     correct_pool_this = (unsigned char *)mem_a(CORRECT_POOL_SIZE);
154
155     vec_push(correct_pool_data, correct_pool_this);
156 }
157
158 static GMQCC_INLINE void *correct_pool_alloc(size_t bytes) {
159     void *data;
160     if (correct_pool_addr + bytes>= CORRECT_POOL_SIZE)
161         correct_pool_new();
162
163     data               = (void*)correct_pool_this;
164     correct_pool_this += bytes;
165     correct_pool_addr += bytes;
166     return data;
167 }
168
169 static GMQCC_INLINE void correct_pool_delete(void) {
170     size_t i;
171     for (i = 0; i < vec_size(correct_pool_data); ++i)
172         mem_d(correct_pool_data[i]);
173
174     correct_pool_data = NULL;
175     correct_pool_this = NULL;
176     correct_pool_addr = 0;
177 }
178
179
180 static GMQCC_INLINE char *correct_pool_claim(const char *data) {
181     char *claim = util_strdup(data);
182     correct_pool_delete();
183     return claim;
184 }
185
186 /*
187  * _ is valid in identifiers. I've yet to implement numerics however
188  * because they're only valid after the first character is of a _, or
189  * alpha character.
190  */
191 static const char correct_alpha[] = "abcdefghijklmnopqrstuvwxyz"
192                                     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
193                                     "_"; /* TODO: Numbers ... */
194
195 static const size_t correct_alpha_index[0x80] = {
196      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
197      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
198      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
199      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
200      0,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
201     15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,  0,  0,  0,  0, 52,
202      0, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
203     41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,  0,  0,  0,  0,  0
204 };
205
206 /*
207  * A fast space efficent trie for a dictionary of identifiers.  This is
208  * faster than a hashtable for one reason.  A hashtable itself may have
209  * fast constant lookup time, but the hash itself must be very fast. We
210  * have one of the fastest hash functions for strings, but if you do a
211  * lost of hashing (which we do, almost 3 million hashes per identifier)
212  * a hashtable becomes slow.
213  */
214 correct_trie_t* correct_trie_new() {
215     correct_trie_t *t = (correct_trie_t*)mem_a(sizeof(correct_trie_t));
216     t->value   = NULL;
217     t->entries = NULL;
218     return t;
219 }
220
221 void correct_trie_del_sub(correct_trie_t *t) {
222     size_t i;
223     if (!t->entries)
224         return;
225     for (i = 0; i < sizeof(correct_alpha)-1; ++i) {
226         correct_trie_del_sub(&t->entries[i]);
227     }
228     mem_d(t->entries);
229 }
230
231 void correct_trie_del(correct_trie_t *t) {
232     size_t i;
233     if (t->entries) {
234         for (i = 0; i < sizeof(correct_alpha)-1; ++i)
235             correct_trie_del_sub(&t->entries[i]);
236         mem_d(t->entries);
237     }
238     mem_d(t);
239 }
240
241 void* correct_trie_get(const correct_trie_t *t, const char *key) {
242     const unsigned char *data = (const unsigned char*)key;
243
244     while (*data) {
245         if (!t->entries)
246             return NULL;
247         t = t->entries + correct_alpha_index[*data];
248         ++data;
249     }
250     return t->value;
251 }
252
253 void correct_trie_set(correct_trie_t *t, const char *key, void * const value) {
254     const unsigned char *data = (const unsigned char*)key;
255     while (*data) {
256         if (!t->entries) {
257             t->entries = (correct_trie_t*)mem_a(sizeof(correct_trie_t)*(sizeof(correct_alpha)-1));
258             memset(t->entries, 0, sizeof(correct_trie_t)*(sizeof(correct_alpha)-1));
259         }
260         t = t->entries + correct_alpha_index[*data];
261         ++data;
262     }
263     t->value = value;
264 }
265
266
267 /*
268  * Implementation of the corrector algorithm commences. A very efficent
269  * brute-force attack (thanks to tries and mempool :-)).
270  */
271 static GMQCC_INLINE size_t *correct_find(correct_trie_t *table, const char *word) {
272     return (size_t*)correct_trie_get(table, word);
273 }
274
275 static GMQCC_INLINE bool correct_update(correct_trie_t* *table, const char *word) {
276     size_t *data = correct_find(*table, word);
277     if (!data)
278         return false;
279
280     (*data)++;
281     return true;
282 }
283
284 void correct_add(correct_trie_t* table, size_t ***size, const char *ident) {
285     size_t     *data = NULL;
286     const char *add  = ident;
287
288     if (!correct_update(&table, add)) {
289         data  = (size_t*)mem_a(sizeof(size_t));
290         *data = 1;
291
292         vec_push((*size), data);
293         correct_trie_set(table, add, data);
294     }
295 }
296
297 void correct_del(correct_trie_t* dictonary, size_t **data) {
298     size_t       i;
299     const size_t vs = vec_size(data);
300
301     for (i = 0; i < vs; i++)
302         mem_d(data[i]);
303
304     vec_free(data);
305     correct_trie_del(dictonary);
306 }
307
308 /*
309  * correcting logic for the following forms of transformations:
310  *  1) deletion
311  *  2) transposition
312  *  3) alteration
313  *  4) insertion
314  *
315  * These functions could take an additional size_t **size paramater
316  * and store back the results of their new length in an array that
317  * is the same as **array for the memcmp in correct_exists. I'm just
318  * not able to figure out how to do that just yet.  As my brain is
319  * not in the mood to figure out that logic.  This is a reminder to
320  * do it, or for someone else to :-) correct_edit however would also
321  * need to take a size_t ** to carry it along (would all the argument
322  * overhead be worth it?)  
323  */
324 static size_t correct_deletion(const char *ident, char **array) {
325     size_t       itr = 0;
326     const size_t len = strlen(ident);
327
328     for (; itr < len; itr++) {
329         char *a = (char*)correct_pool_alloc(len+1);
330         memcpy(a, ident, itr);
331         memcpy(a + itr, ident + itr + 1, len - itr);
332         array[itr] = a;
333     }
334
335     return itr;
336 }
337
338 static size_t correct_transposition(const char *ident, char **array) {
339     size_t       itr = 0;
340     const size_t len = strlen(ident);
341
342     for (; itr < len - 1; itr++) {
343         char  tmp;
344         char *a = (char*)correct_pool_alloc(len+1);
345         memcpy(a, ident, len+1);
346         tmp      = a[itr];
347         a[itr  ] = a[itr+1];
348         a[itr+1] = tmp;
349         array[itr] = a;
350     }
351
352     return itr;
353 }
354
355 static size_t correct_alteration(const char *ident, char **array) {
356     size_t       itr = 0;
357     size_t       jtr = 0;
358     size_t       ktr = 0;
359     const size_t len = strlen(ident);
360
361     for (; itr < len; itr++) {
362         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
363             char *a = (char*)correct_pool_alloc(len+1);
364             memcpy(a, ident, len+1);
365             a[itr] = correct_alpha[jtr];
366             array[ktr] = a;
367         }
368     }
369
370     return ktr;
371 }
372
373 static size_t correct_insertion(const char *ident, char **array) {
374     size_t       itr = 0;
375     size_t       jtr = 0;
376     const size_t len = strlen(ident);
377
378     for (; itr <= len; itr++) {
379         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++) {
380             char *a = (char*)correct_pool_alloc(len+2);
381             memcpy(a, ident, itr);
382             memcpy(a + itr + 1, ident + itr, len - itr + 1);
383             a[itr] = correct_alpha[jtr];
384             array[itr * (sizeof(correct_alpha)-1) + jtr] = a;
385         }
386     }
387
388     return (len+1)*(sizeof(correct_alpha)-1);
389 }
390
391 static GMQCC_INLINE size_t correct_size(const char *ident) {
392     /*
393      * deletion      = len
394      * transposition = len - 1
395      * alteration    = len * sizeof(correct_alpha)
396      * insertion     = (len + 1) * sizeof(correct_alpha)
397      */
398
399     register size_t len = strlen(ident);
400     return (len) + (len - 1) + (len * (sizeof(correct_alpha)-1)) + ((len + 1) * (sizeof(correct_alpha)-1));
401 }
402
403 static char **correct_edit(const char *ident) {
404     size_t next;
405     char **find = (char**)correct_pool_alloc(correct_size(ident) * sizeof(char*));
406
407     if (!find)
408         return NULL;
409
410     next  = correct_deletion     (ident, find);
411     next += correct_transposition(ident, find+next);
412     next += correct_alteration   (ident, find+next);
413     /*****/ correct_insertion    (ident, find+next);
414
415     return find;
416 }
417
418 /*
419  * We could use a hashtable but the space complexity isn't worth it
420  * since we're only going to determine the "did you mean?" identifier
421  * on error.
422  */
423 static int correct_exist(char **array, size_t rows, char *ident) {
424     size_t itr;
425     /*
426      * As an experiment I tried the following assembly for memcmp here:
427      *
428      * correct_cmp_loop: 
429      * incl %eax            ; eax =  LHS
430      * incl %edx            ; edx =  LRS
431      * cmpl %eax, %ebx      ; ebx = &LHS[END_POS]
432      *
433      * jbe correct_cmp_eq
434      * movb (%edx), %cl     ; micro-optimized even on atoms :-)
435      * cmpb %cl, (%eax)     ; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
436      * jg  correct_cmp_gt
437      * jge correct_cmp_loop
438      * ...
439      *
440      * Despite how much optimization went in to this, the speed was
441      * being conflicted by the strlen(ident) used for &LHS[END_POS]
442      * If we could eliminate the strlen with what I suggested on line
443      * 311 ... we can accelerate this whole damn thing quite a bit.
444      *
445      * However there is still something we can do here that does give
446      * us a little more speed.  Although one more branch, we know for
447      * sure there is at least one byte to compare, if that one byte
448      * simply isn't the same we can skip the full check. Which means
449      * we skip a whole strlen call.
450      */
451     for (itr = 0; itr < rows; itr++) {
452         if (!memcmp(array[itr], ident, strlen(ident)))
453             return 1;
454     }
455
456     return 0;
457 }
458
459 static GMQCC_INLINE char **correct_known_resize(char **res, size_t *allocated, size_t size) {
460     size_t oldallocated = *allocated;
461     char **out;
462     if (size < oldallocated)
463         return res;
464
465     out = correct_pool_alloc(sizeof(*res) * oldallocated + 32);
466     memcpy(out, res, sizeof(*res) * oldallocated);
467
468     *allocated += 32;
469     return out;
470 }
471
472 static char **correct_known(correct_trie_t* table, char **array, size_t rows, size_t *next) {
473     size_t itr = 0;
474     size_t jtr = 0;
475     size_t len = 0;
476     size_t row = 0;
477     size_t nxt = 8;
478     char **res = correct_pool_alloc(sizeof(char *) * nxt);
479     char **end = NULL;
480
481     for (; itr < rows; itr++) {
482         end = correct_edit(array[itr]);
483         row = correct_size(array[itr]);
484
485         /* removing jtr=0 here speeds it up by 100ms O_o */
486         for (jtr = 0; jtr < row; jtr++) {
487             if (correct_find(table, end[jtr]) && !correct_exist(res, len, end[jtr])) {
488                 res        = correct_known_resize(res, &nxt, len+1);
489                 res[len++] = end[jtr];
490             }
491         }
492     }
493
494     *next = len;
495     return res;
496 }
497
498 static char *correct_maximum(correct_trie_t* table, char **array, size_t rows) {
499     char   *str = NULL;
500     size_t *itm = NULL;
501     size_t  itr = 0;
502     size_t  top = 0;
503
504     for (; itr < rows; itr++) {
505         if ((itm = correct_find(table, array[itr])) && (*itm > top)) {
506             top = *itm;
507             str = array[itr];
508         }
509     }
510
511     return str;
512 }
513
514 /*
515  * This is the exposed interface:
516  * takes a table for the dictonary a vector of sizes (used for internal
517  * probability calculation), and an identifier to "correct".
518  */
519 char *correct_str(correct_trie_t* table, const char *ident) {
520     char **e1      = NULL;
521     char **e2      = NULL;
522     char  *e1ident = NULL;
523     char  *e2ident = NULL;
524     size_t e1rows  = 0;
525     size_t e2rows  = 0;
526
527     correct_pool_new();
528
529     /* needs to be allocated for free later */
530     if (correct_find(table, ident))
531         return correct_pool_claim(ident);
532
533     if ((e1rows = correct_size(ident))) {
534         e1      = correct_edit(ident);
535
536         if ((e1ident = correct_maximum(table, e1, e1rows)))
537             return correct_pool_claim(e1ident);
538     }
539
540     e2 = correct_known(table, e1, e1rows, &e2rows);
541     if (e2rows && ((e2ident = correct_maximum(table, e2, e2rows))))
542         return correct_pool_claim(e2ident);
543
544
545     correct_pool_delete();
546     return util_strdup(ident);
547 }