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