Remove the enumeration of challenge types.
[mnemon] / mnemon.c
1 /* mnemon - A memory training library
2  *
3  * Copyright © 2006,2011 Carl Worth
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 3, or (at your option)
8  * any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
18  */
19
20 #include "mnemon.h"
21
22 /* for asprintf */
23 #define _GNU_SOURCE
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <stdarg.h>
27 #include <stdint.h>
28 #include <math.h>
29
30 #include <sys/types.h>
31 #include <sys/time.h>
32 #include <sys/stat.h>
33 #include <unistd.h>
34 #include <dirent.h>
35 #include <errno.h>
36 #include <string.h>
37 #include <assert.h>
38
39 #include <readline/readline.h>
40 #include <readline/history.h>
41
42 #define ASSERT_NOT_REACHED              \
43 do {                                    \
44     static const int NOT_REACHED = 0;   \
45     assert (NOT_REACHED);               \
46 } while (0)
47
48 static void *
49 xmalloc (size_t size)
50 {
51     void *ret;
52
53     ret = malloc (size);
54     if (ret == NULL) {
55         fprintf (stderr, "Error: out of memory\n");
56         exit (1);
57     }
58
59     return ret;
60 }
61
62 static void *
63 xrealloc (void *ptr, size_t size)
64 {
65     void *ret;
66
67     ret = realloc (ptr, size);
68     if (ret == NULL) {
69         fprintf (stderr, "Error: out of memory\n");
70         exit (1);
71     }
72
73     return ret;
74 }
75
76 static char *
77 xstrdup (const char *s)
78 {
79     char *ret;
80
81     ret = strdup (s);
82     if (ret == NULL) {
83         fprintf (stderr, "Error: out of memory\n");
84         exit (1);
85     }
86
87     return ret;
88 }
89
90 static void
91 xasprintf (char **strp, const char *fmt, ...)
92 {
93     va_list ap;
94     int ret;
95
96     va_start (ap, fmt);
97     ret = vasprintf (strp, fmt, ap);
98     va_end (ap);
99
100     if (ret < 0) {
101         fprintf (stderr, "Error: out of memory\n");
102         exit (1);
103     }
104 }
105
106 static void
107 item_init (item_t       *item,
108            int           score,
109            const char   *challenge,
110            const char   *response)
111 {
112     item->score = score;
113
114     item->challenge = xmalloc (strlen (challenge) + 1 +
115                                strlen (response) + 1);
116     item->response = item->challenge + strlen (challenge) + 1;
117
118     strcpy (item->challenge, challenge);
119     strcpy (item->response, response);
120 }
121
122 static void
123 item_fini (item_t *item)
124 {
125     /* item->response shares allocation with item->challenge, so
126      * doesn't require a separate call to free */
127     free (item->challenge);
128 }
129
130 static void
131 category_init (category_t *category,
132                const char *name)
133 {
134     category->name = xstrdup (name);
135     
136     category->items_size = 0;
137     category->num_items = 0;
138     category->items = NULL;
139     category->order = CATEGORY_ORDER_RANDOM;
140     category->time_limit = 0.0;
141     category->bin_zero_head = 0;
142     category->challenge_type = xstrdup("");
143     category->repeat = 0;
144 }
145
146 static void
147 category_fini (category_t *category)
148 {
149     int i;
150
151     for (i = 0; i < category->num_items; i++)
152         item_fini (&category->items[i]);
153
154     free (category->items);
155
156     free (category->name);
157
158     free (category->challenge_type);
159 }
160
161 static void
162 category_grow (category_t *category)
163 {
164     if (category->items_size)
165         category->items_size *= 2;
166     else
167         category->items_size = 1;
168
169     category->items = xrealloc (category->items,
170                                 category->items_size * sizeof (item_t));
171 }
172
173 static item_t *
174 category_add_item (category_t   *category,
175                    int           score,
176                    const char   *challenge,
177                    const char   *response)
178 {
179     item_t *item;
180
181     if (category->num_items == category->items_size)
182         category_grow (category);
183
184     item = &category->items[category->num_items++];
185
186     item_init (item, score, challenge, response);
187
188     return item;
189 }
190
191 static item_t *
192 category_next_bin_zero_item (category_t *category)
193 {
194     int *i = &category->bin_zero_head;
195
196     for ( ; *i < category->num_items; *i = *i + 1)
197         if (category->items[*i].score == 0)
198             return &category->items[*i];
199
200     return NULL;
201 }
202
203 static void
204 category_print (category_t      *category,
205                 FILE            *file)
206 {
207     int i;
208     item_t *item;
209
210     fprintf (file, "order = %s\n\n",
211             category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
212     fprintf (file, "time = %f\n\n",
213              category->time_limit);
214
215     fprintf (file, "challenge = %s\n\n", category->challenge_type);
216
217     fprintf (file, "repeat = %d\n\n", category->repeat);
218
219     for (i = 0; i < category->num_items; i++) {
220         item = &category->items[i];
221         if (i != 0)
222             fprintf (file, "\n");
223         fprintf (file, "%d\n%s\n%s\n",
224                  item->score,
225                  item->challenge,
226                  item->response);
227     }
228 }
229
230 static void
231 bin_init (bin_t *bin,
232           int    score)
233 {
234     bin->score = score;
235
236     bin->items_size = 0;
237     bin->num_items = 0;
238     bin->items = NULL;
239 }
240
241 static void
242 bin_fini (bin_t *bin)
243 {
244     free (bin->items);
245 }
246
247 static void
248 bin_grow (bin_t *bin)
249 {
250     if (bin->items_size)
251         bin->items_size *= 2;
252     else
253         bin->items_size = 1;
254
255     bin->items = xrealloc (bin->items,
256                            bin->items_size * sizeof (item_t*));
257 }
258
259 static void
260 bin_add_item (bin_t     *bin,
261               item_t    *item)
262 {
263     assert (item->score == bin->score);
264
265     if (bin->num_items == bin->items_size)
266         bin_grow (bin);
267
268     bin->items[bin->num_items++] = item;
269 }
270
271 static void
272 bin_remove_item (bin_t  *bin,
273                  int     item_index)
274 {
275     /* Replace the current item with the last item, (no need to shift
276      * any more than that since we don't care about the order of the
277      * items within a bin). */
278     bin->num_items--;
279     if (bin->num_items)
280         bin->items[item_index] = bin->items[bin->num_items];
281 }
282
283 /* Find the index for an item within a bin.
284  *
285  * XXX: This is currently a linear search, so is a potential
286  * performance problem.
287  */
288 static int
289 bin_item_index (bin_t   *bin,
290                 item_t  *item)
291 {
292     int i;
293
294     for (i = 0; i < bin->num_items; i++)
295         if (bin->items[i] == item)
296             return i;
297
298     assert (0);
299 }
300
301 void
302 mnemon_init (mnemon_t *mnemon)
303 {
304     char *home;
305
306     home = getenv ("HOME");
307     if (home == NULL)
308         home = "";
309
310     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
311
312     mnemon->categories_size = 0;
313     mnemon->num_categories = 0;
314     mnemon->categories = NULL;
315
316     mnemon->bins_size = 0;
317     mnemon->num_bins = 0;
318     mnemon->bins = NULL;
319 }
320
321 void
322 mnemon_fini (mnemon_t *mnemon)
323 {
324     int i;
325
326     for (i = 0; i < mnemon->num_bins; i++)
327         bin_fini (&mnemon->bins[i]);
328     free (mnemon->bins);
329
330     for (i = 0; i < mnemon->num_categories; i++)
331         category_fini (&mnemon->categories[i]);
332     free (mnemon->categories);
333
334     free (mnemon->dir_name);
335 }
336
337 static void
338 mnemon_categories_grow (mnemon_t *mnemon)
339 {
340     if (mnemon->categories_size)
341         mnemon->categories_size *= 2;
342     else
343         mnemon->categories_size = 1;
344
345     mnemon->categories = xrealloc (mnemon->categories,
346                                    mnemon->categories_size * sizeof (category_t));
347 }
348
349 /* Get a category by name if it exists */
350 category_t *
351 mnemon_get_category_if_exists (mnemon_t     *mnemon,
352                                const char   *name)
353 {
354     int i;
355
356     for (i = 0; i < mnemon->num_categories; i++)
357         if (strcmp (mnemon->categories[i].name, name) == 0)
358             return &mnemon->categories[i];
359
360     return NULL;
361 }
362
363 /* Get a category by name, creating new one if necessary. */
364 static category_t *
365 mnemon_get_category (mnemon_t   *mnemon,
366                      const char *name)
367 {
368     category_t *category;
369
370     category = mnemon_get_category_if_exists (mnemon, name);
371     if (category)
372         return category;
373
374     mnemon_categories_grow (mnemon);
375
376     category = &mnemon->categories[mnemon->num_categories++];
377
378     category_init (category, name);
379
380     return category;
381 }
382
383 static void
384 mnemon_bins_grow (mnemon_t *mnemon)
385 {
386     if (mnemon->bins_size)
387         mnemon->bins_size *= 2;
388     else
389         mnemon->bins_size = 1;
390
391     mnemon->bins = xrealloc (mnemon->bins,
392                              mnemon->bins_size * sizeof (bin_t));
393 }
394
395 static bin_t *
396 mnemon_get_bin (mnemon_t        *mnemon,
397                 int              score)
398 {
399     int i;
400     bin_t *bin;
401
402     for (i = 0; i < mnemon->num_bins; i++)
403         if (mnemon->bins[i].score == score)
404             return &mnemon->bins[i];
405         else if (mnemon->bins[i].score > score)
406             break;
407
408     if (mnemon->num_bins == mnemon->bins_size)
409         mnemon_bins_grow (mnemon);
410
411     bin = &mnemon->bins[i];
412
413     /* Make room to insert new bin at its sorted location. */
414     if (i < mnemon->num_bins)
415         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
416     mnemon->num_bins++;
417
418     bin_init (bin, score);
419
420     return bin;
421 }
422
423 void
424 mnemon_remove_bin (mnemon_t *mnemon, int bin_number)
425 {
426     bin_t *bin = mnemon_get_bin (mnemon, bin_number);
427     int i;
428
429     if (bin == NULL)
430         return;
431
432     i = bin - mnemon->bins;
433
434     bin_fini (bin);
435
436     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
437     mnemon->num_bins--;
438 }
439
440 static void
441 chomp (char *s)
442 {
443     int len = strlen (s);
444     if (len == 0)
445         return;
446     if (s[len - 1] == '\n')
447         s[len - 1] = '\0';
448 }
449
450 static char *
451 trim_space (char *string)
452 {
453     char *s;
454
455     s = string;
456     while (*s && isspace (*s))
457         s++;
458
459     string = s;
460
461     s = string + strlen (string) - 1;
462     while (s > string && isspace (*s)) {
463         *s = '\0';
464         s--;
465     }
466
467     return string;
468 }
469
470 void
471 mnemon_load_category (mnemon_t          *mnemon,
472                       const char        *name)
473 {
474     FILE *file;
475     char *line = NULL, *end;
476     size_t line_size = 0;
477     ssize_t bytes_read;
478     int line_count = 0;
479     char *path;
480     category_t *category;
481     int i;
482     struct stat st;
483
484     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
485     sprintf (path, "%s/%s", mnemon->dir_name, name);
486
487     file = fopen (path, "r");
488     if (file == NULL) {
489         fprintf (stderr, "Error: Failed to open %s: %s\n",
490                  path, strerror (errno));
491         exit (1);
492     }
493
494     fstat (fileno(file), &st);
495     if (! S_ISREG(st.st_mode)) {
496         fprintf (stderr, "Error: File %s is not a regular file.\n", path);
497         exit (1);
498     }
499
500     category = mnemon_get_category (mnemon, name);
501
502 #define READ_LINE do {                                  \
503     bytes_read = getline (&line, &line_size, file);     \
504     if (bytes_read == -1)                               \
505         goto END_OF_FILE;                               \
506     line_count++;                                       \
507     chomp (line);                                       \
508 } while (0)
509
510     /* Parse options */
511     while (1) {
512         char *name, *equal, *value;
513
514         /* Ignore blank lines */
515         READ_LINE;
516         if (*line == '\0')
517             continue;
518
519         /* An initial digit means we hit an item. Trigger the
520          * spaghetti machine. */
521         if ((*line >= '0' && *line <= '9') || *line == '-')
522             goto PARSE_BIN;
523
524         equal = strchr (line, '=');
525         if (equal == NULL) {
526             fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
527                      line, path, line_count);
528             exit (1);
529         }
530
531         value = equal + 1;
532         name = line;
533         *equal = '\0';
534
535         name = trim_space (name);
536         value = trim_space (value);
537
538         if (strcmp (name, "order") == 0) {
539             if (strcmp (value, "sequential") == 0) {
540                 category->order = CATEGORY_ORDER_SEQUENTIAL;
541             } else if (strcmp (value, "random") == 0) {
542                 category->order = CATEGORY_ORDER_RANDOM;
543             } else {
544                 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
545                          value, path, line_count);
546                 exit (1);
547             }
548         } else if (strcmp (name, "time") == 0) {
549             double limit;
550             char *end;
551             limit = strtod (value, &end);
552             while (isspace (*end))
553                 end++;
554             if (*end == '\0') {
555                 category->time_limit = limit;
556             } else {
557                 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
558                          value, path, line_count);
559                 exit (1);
560             }
561         } else if (strcmp (name, "challenge") == 0) {
562             /* XXX: Need to switch to talloc here. */
563             free (category->challenge_type);
564             category->challenge_type = xstrdup (value);
565         } else if (strcmp (name, "repeat") == 0) {
566             if (strcmp (value, "0") == 0) 
567                 category->repeat = 0;
568             else
569                 category->repeat = 1;
570         } else {
571             fprintf (stderr, "Unknown option %s at %s:%d\n",
572                      name, path, line_count);
573             exit (1);
574         }
575     }
576
577     /* Parse items */
578     while (1) {
579         int score;
580         char *challenge, *response;
581
582         /* Ignore blank lines */
583         READ_LINE;
584         if (*line == '\0')
585             continue;
586
587         /* Read bin number */
588       PARSE_BIN:
589         score = strtol (line, &end, 10);
590         if (*end != '\0') {
591             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
592                      line, path, line_count);
593             exit (1);
594         }
595
596         /* Read challenge */
597         READ_LINE;
598         challenge = strdup (line);
599
600         /* Read response */
601         READ_LINE;
602         response = line;
603
604         category_add_item (category, score, challenge, response);
605
606         free (challenge);
607     }
608   END_OF_FILE:
609
610     free (line);
611     fclose (file);
612     free (path);
613
614     /* Resize category items to fit exactly. */
615     category->items_size = category->num_items;
616     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
617
618     /* Now that the category is completely loaded, with stable
619      * pointers to every item, we can add each item to its appropriate
620      * bin. */
621     for (i = 0; i < category->num_items; i++) {
622         item_t *item = &category->items[i];
623         bin_t *bin = mnemon_get_bin (mnemon, item->score);
624
625         bin_add_item (bin, item);
626     }
627 }
628
629 void
630 mnemon_load (mnemon_t *mnemon)
631 {
632     DIR *dir;
633     struct dirent *dirent;
634
635     dir = opendir (mnemon->dir_name);
636     if (dir == NULL) {
637         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
638                  mnemon->dir_name, strerror (errno));
639         exit (1);
640     }
641
642     while (1) {
643         dirent = readdir (dir);
644         if (dirent == NULL)
645             break;
646
647         if (dirent->d_type == DT_REG) {
648             /* Ignore files matching *~, (yes, this shouldn't be
649              * hard-coded in such an ad-hoc way, but there you go. */
650             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
651                 mnemon_load_category (mnemon, dirent->d_name);
652         }
653     }
654
655     closedir (dir);
656 }
657
658 void
659 mnemon_save (mnemon_t *mnemon)
660 {
661     int i, err;
662     char *filename, *lock_filename;
663     FILE *file;
664     category_t *category;
665
666     for (i = 0; i < mnemon->num_categories; i++) {
667         category = &mnemon->categories[i];
668
669         xasprintf (&filename, "%s/%s",
670                    mnemon->dir_name, category->name);
671         xasprintf (&lock_filename, "%s/.#%s",
672                    mnemon->dir_name, category->name);
673
674         file = fopen (lock_filename, "w");
675         if (file == NULL) {
676             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
677                      lock_filename, strerror (errno));
678             continue;
679         }
680
681         category_print (category, file);
682
683         fsync (fileno (file));
684         fclose (file);
685
686         err = rename (lock_filename, filename);
687         if (err < 0) {
688             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
689                      lock_filename, filename, strerror (errno));
690             continue;
691         }
692
693         free (filename);
694         free (lock_filename);
695     }
696 }
697
698 /* Return a uniformly-distributed pseudo-random integer within the
699  * range:
700  *
701  *      0 <= result < num_values
702  */
703 static int
704 rand_within (int num_values)
705 {
706     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
707 }
708
709 /* Return an exponentially-distributed pseudo-random integer within
710  * the range:
711  *
712  *      0 <= result < num_values
713  *
714  * The distribution is such that each successively larger value will
715  * occur with a probability of half of the previous value.
716  */
717 static int
718 rand_within_exponential (int num_values)
719 {
720     static int r;
721     static uint32_t mask = 0;
722     int ones;
723     int bit;
724
725     /* Optimize the constant case. */
726     if (num_values == 1)
727         return 0;
728
729     ones = 0;
730
731     do {
732         if (mask == 0) {
733             r = rand ();
734             mask = 1 << 31;
735             while (mask > RAND_MAX)
736                 mask >>= 1;
737         }
738         bit = r & mask;
739         mask >>= 1;
740         if (bit) {
741             ones++;
742             if (ones == num_values)
743                 ones = 0;
744         }
745     } while (bit);
746
747     return ones;
748 }
749
750 category_t *
751 mnemon_item_category (mnemon_t  *mnemon,
752                       item_t    *item)
753 {
754     category_t *category;
755     int i, item_index;
756
757     for (i = 0; i < mnemon->num_categories; i++) {
758         category = &mnemon->categories[i];
759         item_index = item - category->items;
760         if (item_index >= 0 && item_index < category->num_items)
761             return category;
762     }
763
764     assert (0);
765 }
766
767 void
768 mnemon_select_item (mnemon_t     *mnemon,
769                     bin_t       **bin_ret,
770                     int          *item_index_ret,
771                     category_t  **category_ret,
772                     int          *introduced_ret)
773 {
774     int bin_index, item_index;
775     bin_t *bin;
776     item_t *item;
777     category_t *category;
778
779     bin_index = rand_within_exponential (mnemon->num_bins);
780     bin = &mnemon->bins[bin_index];
781
782     /* The most intuitive understanding of the introduced flag that
783      * it's tracking never-before-learned items as they are pulled
784      * from the bin with score 0. But that bin can become empty. So
785      * the refined rule is that we also set introduced whenever we
786      * pull from the lowest-indexed bin with a non-negative score. */
787     if (bin->score >=0 &&
788         (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
789     {
790         *introduced_ret = 1;
791     }
792     else
793     {
794         *introduced_ret = 0;
795     }
796
797     item_index = rand_within (bin->num_items);
798
799     item = bin->items[item_index];
800     category = mnemon_item_category (mnemon, item);
801
802     if (bin->score == 0) {
803         if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
804             item = category_next_bin_zero_item (category);
805             if (item)
806                 item_index = bin_item_index (bin, item);
807         }
808     }
809
810     *bin_ret = bin;
811     *item_index_ret = item_index;
812     *category_ret = category;
813 }
814
815 void
816 mnemon_score_item (mnemon_t *mnemon,
817                    bin_t *bin,
818                    unsigned int item_index,
819                    bool_t correct)
820 {
821     item_t *item;
822
823     if (item_index >= bin->num_items)
824         return;
825
826     item = bin->items[item_index];
827     bin_remove_item (bin, item_index);
828
829     /* If the bin is now empty, we must remove it. */
830     if (bin->num_items == 0)
831     {
832         mnemon_remove_bin (mnemon, bin->score);
833     }
834
835     if (correct)
836     {
837         item->score++;
838         /* We reserve an item score of 0 for an item that has
839          * never been asked. */
840         if (item->score == 0)
841             item->score = 1;
842     }
843     else
844     {
845         /* Penalize an incorrect response by forcing the score
846          * negative. */
847         if (item->score >= 0) {
848             /* We go to -2 to force a little extra reinforcement
849              * when re-learning an item, (otherwise, it will often
850              * get asked again immediately where it is easy to get
851              * a correct response without any learning). */
852             item->score = -2;
853         } else {
854             item->score--;
855         }
856     }
857
858     bin = mnemon_get_bin (mnemon, item->score);
859
860     bin_add_item (bin, item);
861 }