Committing an evil allocator and a trie to speed up the correction stuff
[xonotic/gmqcc.git] / 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 unsigned char **pools;
26 unsigned char  *poolptr;
27 size_t          poolat;
28 #define C_POOLSIZE (128*1024*1024)
29
30 static GMQCC_INLINE void newpool() {
31     poolat = 0;
32     poolptr = mem_a(C_POOLSIZE);
33     vec_push(pools, poolptr);
34 }
35
36 void correct_init(void) {
37     newpool();
38 }
39
40 static GMQCC_INLINE void *correct_alloc(size_t _b) {
41     size_t *ptr;
42     size_t b = _b + sizeof(size_t);
43     if (poolat + b >= C_POOLSIZE)
44         newpool();
45     poolat += b;
46     ptr = (size_t*)poolptr;
47     poolptr += b;
48     *ptr = _b;
49     return (void*)(ptr+1);
50 }
51
52 static GMQCC_INLINE void *correct_realloc(void *_ptr, size_t _b) {
53     size_t *ptr   = ((size_t*)_ptr) - 1;
54     size_t oldlen = *ptr;
55     size_t len    = (oldlen < _b ? oldlen : _b);
56     size_t b      = _b + sizeof(size_t);
57     size_t *newptr;
58
59     newptr    = (size_t*)correct_alloc(b);
60     *newptr++ = _b;
61     memcpy(newptr, _ptr, len);
62     return (void*)(newptr);
63 }
64
65 void correct_delete(void) {
66     size_t i;
67     for (i = 0; i < vec_size(pools); ++i)
68         mem_d(pools[i]);
69     pools   = NULL;
70     poolptr = NULL;
71     poolat  = 0;
72 }
73
74 static GMQCC_INLINE char *correct_outstr(const char *s) {
75     char *o = util_strdup(s);
76     correct_delete();
77     return o;
78 }
79
80 correct_trie_t* correct_trie_new()
81 {
82     correct_trie_t *t = (correct_trie_t*)mem_a(sizeof(correct_trie_t));
83     t->value   = NULL;
84     t->entries = NULL;
85     return t;
86 }
87
88 void correct_trie_del_sub(correct_trie_t *t)
89 {
90     size_t i;
91     for (i = 0; i < vec_size(t->entries); ++i)
92         correct_trie_del_sub(&t->entries[i]);
93     vec_free(t->entries);
94 }
95
96 void correct_trie_del(correct_trie_t *t)
97 {
98     size_t i;
99     for (i = 0; i < vec_size(t->entries); ++i)
100         correct_trie_del_sub(&t->entries[i]);
101     vec_free(t->entries);
102     mem_d(t);
103 }
104
105 void* correct_trie_get(const correct_trie_t *t, const char *key)
106 {
107     const unsigned char *data = (const unsigned char*)key;
108     while (*data) {
109         unsigned char ch = *data;
110         const size_t  vs = vec_size(t->entries);
111         size_t        i;
112         const correct_trie_t *entries = t->entries;
113         for (i = 0; i < vs; ++i) {
114             if (entries[i].ch == ch) {
115                 t = &entries[i];
116                 ++data;
117                 break;
118             }
119         }
120         if (i == vs)
121             return NULL;
122     }
123     return t->value;
124 }
125
126 void correct_trie_set(correct_trie_t *t, const char *key, void * const value)
127 {
128     const unsigned char *data = (const unsigned char*)key;
129     while (*data) {
130         unsigned char ch = *data;
131         correct_trie_t       *entries = t->entries;
132         const size_t  vs = vec_size(t->entries);
133         size_t        i;
134         for (i = 0; i < vs; ++i) {
135             if (entries[i].ch == ch) {
136                 t = &entries[i];
137                 break;
138             }
139         }
140         if (i == vs) {
141             correct_trie_t *elem  = (correct_trie_t*)vec_add(t->entries, 1);
142             elem->ch      = ch;
143             elem->value   = NULL;
144             elem->entries = NULL;
145             t = elem;
146         }
147         ++data;
148     }
149     t->value = value;
150 }
151
152 /*
153  * This is a very clever method for correcting mistakes in QuakeC code
154  * most notably when invalid identifiers are used or inproper assignments;
155  * we can proprly lookup in multiple dictonaries (depening on the rules
156  * of what the task is trying to acomplish) to find the best possible
157  * match.
158  *
159  *
160  * A little about how it works, and probability theory:
161  *
162  *  When given an identifier (which we will denote I), we're essentially
163  *  just trying to choose the most likely correction for that identifier.
164  *  (the actual "correction" can very well be the identifier itself).
165  *  There is actually no way to know for sure that certian identifers
166  *  such as "lates", need to be corrected to "late" or "latest" or any
167  *  other permutations that look lexically the same.  This is why we
168  *  must advocate the usage of probabilities.  This implies that we're
169  *  trying to find the correction for C, out of all possible corrections
170  *  that maximizes the probability of C for the original identifer I.
171  *
172  *  Bayes' Therom suggests something of the following:
173  *      AC P(I|C) P(C) / P(I)
174  *  Since P(I) is the same for every possibly I, we can ignore it giving
175  *      AC P(I|C) P(C)
176  *
177  *  This greatly helps visualize how the parts of the expression are performed
178  *  there is essentially three, from right to left we perform the following:
179  *
180  *  1: P(C), the probability that a proposed correction C will stand on its
181  *     own.  This is called the language model.
182  *
183  *  2: P(I|C), the probability that I would be used, when the programmer
184  *     really meant C.  This is the error model.
185  *
186  *  3: AC, the control mechanisim, which implies the enumeration of all
187  *     feasible values of C, and then determine the one that gives the
188  *     greatest probability score. Selecting it as the "correction"
189  *   
190  *
191  * The requirement for complex expression involving two models:
192  * 
193  *  In reality the requirement for a more complex expression involving
194  *  two seperate models is considerably a waste.  But one must recognize
195  *  that P(C|I) is already conflating two factors.  It's just much simpler
196  *  to seperate the two models and deal with them explicitaly.  To properly
197  *  estimate P(C|I) you have to consider both the probability of C and
198  *  probability of the transposition from C to I.  It's simply much more
199  *  cleaner, and direct to seperate the two factors.
200  */
201
202 /* some hashtable management for dictonaries */
203 static size_t *correct_find(correct_trie_t *table, const char *word) {
204     return (size_t*)correct_trie_get(table, word);
205 }
206
207 static int correct_update(correct_trie_t* *table, const char *word) {
208     size_t *data = correct_find(*table, word);
209     if (!data)
210         return 0;
211
212     (*data)++;
213     return 1;
214 }
215
216 void correct_add(correct_trie_t* table, size_t ***size, const char *ident) {
217     size_t     *data = NULL;
218     const char *add  = ident;
219     
220     if (!correct_update(&table, add)) {
221         data  = (size_t*)mem_a(sizeof(size_t));
222         *data = 1;
223
224         vec_push((*size), data);
225         correct_trie_set(table, add, data);
226     }
227 }
228
229 void correct_del(correct_trie_t* dictonary, size_t **data) {
230     size_t i;
231     const size_t vs = vec_size(data);
232     for (i = 0; i < vs; i++)
233         mem_d(data[i]);
234
235     vec_free(data);
236     correct_trie_del(dictonary);
237 }
238 #if 1
239 #undef mem_a
240 #undef mem_r
241 #undef mem_d
242 #define mem_a(x)   correct_alloc((x))
243 #define mem_r(a,b) correct_realloc((a),(b))
244 /* doing this in order to avoid 'unused variable' warnings */
245 #define mem_d(x)   ((void)(0 && (x)))
246 #endif
247
248
249 /*
250  * _ is valid in identifiers. I've yet to implement numerics however
251  * because they're only valid after the first character is of a _, or
252  * alpha character.
253  */
254 static const char correct_alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";
255
256 /*
257  * correcting logic for the following forms of transformations:
258  *  1) deletion
259  *  2) transposition
260  *  3) alteration
261  *  4) insertion
262  */
263 static size_t correct_deletion(const char *ident, char **array, size_t index) {
264     size_t itr;
265     size_t len = strlen(ident);
266
267     for (itr = 0; itr < len; itr++) {
268         char *a = (char*)mem_a(len+1);
269         memcpy(a, ident, itr);
270         memcpy(a + itr, ident + itr + 1, len - itr);
271         array[index + itr] = a;
272     }
273
274     return itr;
275 }
276
277 static size_t correct_transposition(const char *ident, char **array, size_t index) {
278     size_t itr;
279     size_t len = strlen(ident);
280
281     for (itr = 0; itr < len - 1; itr++) {
282         char  tmp;
283         char *a = (char*)mem_a(len+1);
284         memcpy(a, ident, len+1);
285         tmp      = a[itr];
286         a[itr  ] = a[itr+1];
287         a[itr+1] = tmp;
288         array[index + itr] = a;
289     }
290
291     return itr;
292 }
293
294 static size_t correct_alteration(const char *ident, char **array, size_t index) {
295     size_t itr;
296     size_t jtr;
297     size_t ktr;
298     size_t len    = strlen(ident);
299
300     for (itr = 0, ktr = 0; itr < len; itr++) {
301         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
302             char *a = (char*)mem_a(len+1);
303             memcpy(a, ident, len+1);
304             a[itr] = correct_alpha[jtr];
305             array[index + ktr] = a;
306         }
307     }
308
309     return ktr;
310 }
311
312 static size_t correct_insertion(const char *ident, char **array, size_t index) {
313     size_t itr;
314     size_t jtr;
315     size_t ktr;
316     const size_t len    = strlen(ident);
317
318     for (itr = 0, ktr = 0; itr <= len; itr++) {
319         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
320             char *a = (char*)mem_a(len+2);
321             memcpy(a, ident, itr);
322             memcpy(a + itr + 1, ident + itr, len - itr + 1);
323             a[itr] = correct_alpha[jtr];
324             array[index + ktr] = a;
325         }
326     }
327
328     return ktr;
329 }
330
331 static GMQCC_INLINE size_t correct_size(const char *ident) {
332     /*
333      * deletion      = len
334      * transposition = len - 1
335      * alteration    = len * sizeof(correct_alpha)
336      * insertion     = (len + 1) * sizeof(correct_alpha)
337      */   
338
339     register size_t len = strlen(ident);
340     return (len) + (len - 1) + (len * (sizeof(correct_alpha)-1)) + ((len + 1) * (sizeof(correct_alpha)-1));
341 }
342
343 static char **correct_edit(const char *ident) {
344     size_t next;
345     char **find = (char**)mem_a(correct_size(ident) * sizeof(char*));
346
347     if (!find)
348         return NULL;
349
350     next  = correct_deletion     (ident, find, 0);
351     next += correct_transposition(ident, find, next);
352     next += correct_alteration   (ident, find, next);
353     /*****/ correct_insertion    (ident, find, next);
354
355     return find;
356 }
357
358 /*
359  * We could use a hashtable but the space complexity isn't worth it
360  * since we're only going to determine the "did you mean?" identifier
361  * on error.
362  */   
363 static int correct_exist(char **array, size_t rows, char *ident) {
364     size_t itr;
365     for (itr = 0; itr < rows; itr++)
366         if (!strcmp(array[itr], ident))
367             return 1;
368
369     return 0;
370 }
371
372 static char **correct_known(correct_trie_t* table, char **array, size_t rows, size_t *next) {
373     size_t itr;
374     size_t jtr;
375     size_t len;
376     size_t row;
377     char **res = NULL;
378     char **end;
379
380     for (itr = 0, len = 0; itr < rows; itr++) {
381         end = correct_edit(array[itr]);
382         row = correct_size(array[itr]);
383
384         for (jtr = 0; jtr < row; jtr++) {
385             if (correct_find(table, end[jtr]) && !correct_exist(res, len, end[jtr])) {
386                 res        = mem_r(res, sizeof(char*) * (len + 1));
387                 res[len++] = end[jtr];
388             } else {
389                 mem_d(end[jtr]);
390             }
391         }
392
393         mem_d(end);
394     }
395
396     *next = len;
397     return res;
398 }
399
400 static char *correct_maximum(correct_trie_t* table, char **array, size_t rows) {
401     char   *str  = NULL;
402     size_t *itm  = NULL;
403     size_t  itr;
404     size_t  top;
405
406     for (itr = 0, top = 0; itr < rows; itr++) {
407         if ((itm = correct_find(table, array[itr])) && (*itm > top)) {
408             top = *itm;
409             str = array[itr];
410         }
411     }
412
413     return str;
414 }
415
416 static void correct_cleanup(char **array, size_t rows) {
417     size_t itr;
418     for (itr = 0; itr < rows; itr++)
419         mem_d(array[itr]);
420
421     mem_d(array);
422 }
423
424 /*
425  * This is the exposed interface:
426  * takes a table for the dictonary a vector of sizes (used for internal
427  * probability calculation, and an identifier to "correct"
428  *
429  * the add function works the same.  Except the identifier is used to
430  * add to the dictonary.  
431  */   
432
433 char *correct_str(correct_trie_t* table, const char *ident) {
434     char **e1;
435     char **e2;
436     char  *e1ident;
437     char  *e2ident;
438     char  *found = util_strdup(ident);
439
440     size_t e1rows = 0;
441     size_t e2rows = 0;
442
443     correct_init();
444
445     /* needs to be allocated for free later */
446     if (correct_find(table, ident))
447         return correct_outstr(found);
448
449     if ((e1rows = correct_size(ident))) {
450         e1      = correct_edit(ident);
451
452         if ((e1ident = correct_maximum(table, e1, e1rows))) {
453             mem_d(found);
454             found = util_strdup(e1ident);
455             correct_cleanup(e1, e1rows);
456             return correct_outstr(found);
457         }
458     }
459
460     e2 = correct_known(table, e1, e1rows, &e2rows);
461     if (e2rows && ((e2ident = correct_maximum(table, e2, e2rows)))) {
462         mem_d(found);
463         found = util_strdup(e2ident);
464     }
465     
466     correct_cleanup(e1, e1rows);
467     correct_cleanup(e2, e2rows);
468
469     return correct_outstr(found);
470 }