Remove an illegal mem_d
[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 #if 1
233 #undef mem_a
234 #undef mem_r
235 #undef mem_d
236 #define mem_a(x)   correct_alloc((x))
237 #define mem_r(a,b) correct_realloc((a),(b))
238 /* doing this in order to avoid 'unused variable' warnings */
239 #define mem_d(x)   ((void)(0 && (x)))
240 #endif
241
242
243 /*
244  * _ is valid in identifiers. I've yet to implement numerics however
245  * because they're only valid after the first character is of a _, or
246  * alpha character.
247  */
248 static const char correct_alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";
249
250 /*
251  * correcting logic for the following forms of transformations:
252  *  1) deletion
253  *  2) transposition
254  *  3) alteration
255  *  4) insertion
256  */
257 static size_t correct_deletion(const char *ident, char **array, size_t index) {
258     size_t itr;
259     size_t len = strlen(ident);
260
261     for (itr = 0; itr < len; itr++) {
262         char *a = (char*)correct_pool_alloc(len+1);
263         memcpy(a, ident, itr);
264         memcpy(a + itr, ident + itr + 1, len - itr);
265         array[index + itr] = a;
266     }
267
268     return itr;
269 }
270
271 static size_t correct_transposition(const char *ident, char **array, size_t index) {
272     size_t itr;
273     size_t len = strlen(ident);
274
275     for (itr = 0; itr < len - 1; itr++) {
276         char  tmp;
277         char *a = (char*)correct_pool_alloc(len+1);
278         memcpy(a, ident, len+1);
279         tmp      = a[itr];
280         a[itr  ] = a[itr+1];
281         a[itr+1] = tmp;
282         array[index + itr] = a;
283     }
284
285     return itr;
286 }
287
288 static size_t correct_alteration(const char *ident, char **array, size_t index) {
289     size_t itr;
290     size_t jtr;
291     size_t ktr;
292     size_t len    = strlen(ident);
293
294     for (itr = 0, ktr = 0; itr < len; itr++) {
295         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
296             char *a = (char*)correct_pool_alloc(len+1);
297             memcpy(a, ident, len+1);
298             a[itr] = correct_alpha[jtr];
299             array[index + ktr] = a;
300         }
301     }
302
303     return ktr;
304 }
305
306 static size_t correct_insertion(const char *ident, char **array, size_t index) {
307     size_t itr;
308     size_t jtr;
309     size_t ktr;
310     const size_t len    = strlen(ident);
311
312     for (itr = 0, ktr = 0; itr <= len; itr++) {
313         for (jtr = 0; jtr < sizeof(correct_alpha)-1; jtr++, ktr++) {
314             char *a = (char*)correct_pool_alloc(len+2);
315             memcpy(a, ident, itr);
316             memcpy(a + itr + 1, ident + itr, len - itr + 1);
317             a[itr] = correct_alpha[jtr];
318             array[index + ktr] = a;
319         }
320     }
321
322     return ktr;
323 }
324
325 static GMQCC_INLINE size_t correct_size(const char *ident) {
326     /*
327      * deletion      = len
328      * transposition = len - 1
329      * alteration    = len * sizeof(correct_alpha)
330      * insertion     = (len + 1) * sizeof(correct_alpha)
331      */   
332
333     register size_t len = strlen(ident);
334     return (len) + (len - 1) + (len * (sizeof(correct_alpha)-1)) + ((len + 1) * (sizeof(correct_alpha)-1));
335 }
336
337 static char **correct_edit(const char *ident) {
338     size_t next;
339     char **find = (char**)correct_pool_alloc(correct_size(ident) * sizeof(char*));
340
341     if (!find)
342         return NULL;
343
344     next  = correct_deletion     (ident, find, 0);
345     next += correct_transposition(ident, find, next);
346     next += correct_alteration   (ident, find, next);
347     /*****/ correct_insertion    (ident, find, next);
348
349     return find;
350 }
351
352 /*
353  * We could use a hashtable but the space complexity isn't worth it
354  * since we're only going to determine the "did you mean?" identifier
355  * on error.
356  */   
357 static int correct_exist(char **array, size_t rows, char *ident) {
358     size_t itr;
359     for (itr = 0; itr < rows; itr++)
360         if (!strcmp(array[itr], ident))
361             return 1;
362
363     return 0;
364 }
365
366 static GMQCC_INLINE char **correct_known_resize(char **res, size_t *allocated, size_t size) {
367     size_t oldallocated = *allocated;
368     char **out;
369     if (size+1 < *allocated)
370         return res;
371
372     *allocated += 32;
373     out = correct_pool_alloc(sizeof(*res) * *allocated);
374     memcpy(out, res, sizeof(*res) * oldallocated);
375     return out;
376 }
377
378 static char **correct_known(correct_trie_t* table, char **array, size_t rows, size_t *next) {
379     size_t itr;
380     size_t jtr;
381     size_t len;
382     size_t row;
383     size_t nxt = 8;
384     char **res = correct_pool_alloc(sizeof(char *) * nxt);
385     char **end = NULL;
386
387     for (itr = 0, len = 0; itr < rows; itr++) {
388         end = correct_edit(array[itr]);
389         row = correct_size(array[itr]);
390
391         for (jtr = 0; jtr < row; jtr++) {
392             if (correct_find(table, end[jtr]) && !correct_exist(res, len, end[jtr])) {
393                 res        = correct_known_resize(res, &nxt, len+1);
394                 res[len++] = end[jtr];
395             }
396         }
397     }
398
399     *next = len;
400     return res;
401 }
402
403 static char *correct_maximum(correct_trie_t* table, char **array, size_t rows) {
404     char   *str  = NULL;
405     size_t *itm  = NULL;
406     size_t  itr;
407     size_t  top;
408
409     for (itr = 0, top = 0; itr < rows; itr++) {
410         if ((itm = correct_find(table, array[itr])) && (*itm > top)) {
411             top = *itm;
412             str = array[itr];
413         }
414     }
415
416     return str;
417 }
418
419 /*
420  * This is the exposed interface:
421  * takes a table for the dictonary a vector of sizes (used for internal
422  * probability calculation, and an identifier to "correct"
423  *
424  * the add function works the same.  Except the identifier is used to
425  * add to the dictonary.  
426  */   
427
428 char *correct_str(correct_trie_t* table, const char *ident) {
429     char **e1;
430     char **e2;
431     char  *e1ident;
432     char  *e2ident;
433     char  *found = util_strdup(ident);
434
435     size_t e1rows = 0;
436     size_t e2rows = 0;
437
438     correct_pool_new();
439
440     /* needs to be allocated for free later */
441     if (correct_find(table, ident))
442         return correct_outstr(found);
443
444     if ((e1rows = correct_size(ident))) {
445         e1      = correct_edit(ident);
446
447         if ((e1ident = correct_maximum(table, e1, e1rows))) {
448             found = util_strdup(e1ident);
449             return correct_outstr(found);
450         }
451     }
452
453     e2 = correct_known(table, e1, e1rows, &e2rows);
454     if (e2rows && ((e2ident = correct_maximum(table, e2, e2rows)))) {
455         found = util_strdup(e2ident);
456     }
457
458     return correct_outstr(found);
459 }