1: /*
    2:  * 学習の履歴などを管理するためのデータベース
    3:  * 文字列(xstr)をキーにして高速に行(row)を検索することができる．
    4:  * 複数のセクションをもつことができ，学習の違うフェーズなどに対応する
    5:  *  (セクション * 文字列 -> 行)
    6:  * 各行は文字列か数を持つ配列になっている
    7:  *
    8:  * 「パトリシア・トライ」というデータ構造を使用している。
    9:  * 自然言語の検索などを扱っている教科書を参照のこと
   10:  */
   11: /*
   12:   This library is free software; you can redistribute it and/or
   13:   modify it under the terms of the GNU Lesser General Public
   14:   License as published by the Free Software Foundation; either
   15:   version 2 of the License, or (at your option) any later version.
   16: 
   17:   This library is distributed in the hope that it will be useful,
   18:   but WITHOUT ANY WARRANTY; without even the implied warranty of
   19:   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   20:   Lesser General Public License for more details.
   21: 
   22:   You should have received a copy of the GNU Lesser General Public
   23:   License along with this library; if not, write to the Free Software
   24:   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
   25:  */
   26: /*
   27:  * Funded by IPA未踏ソフトウェア創造事業 2002 1/18
   28:  * Funded by IPA未踏ソフトウェア創造事業 2005
   29:  * Copyright (C) 2005 YOSHIDA Yuichi
   30:  * Copyright (C) 2000-2006 TABATA Yusuke
   31:  * Copyright (C) 2000-2003 UGAWA Tomoharu
   32:  * Copyright (C) 2001-2002 TAKAI Kosuke
   33:  */
   34: /*
   35:  * パーソナリティ""は匿名パーソナリティであり，
   36:  * ファイルへの読み書きは行わない．
   37:  */
   38: #include <sys/types.h>
   39: #include <sys/stat.h>
   40: #include <errno.h>
   41: #include <unistd.h>
   42: #include <string.h>
   43: #include <stdio.h>
   44: #include <stdlib.h>
   45: 
   46: #include "config.h"
   47: #include <anthy/anthy.h>
   48: #include <anthy/dic.h>
   49: #include <anthy/alloc.h>
   50: #include <anthy/conf.h>
   51: #include <anthy/ruleparser.h>
   52: #include <anthy/record.h>
   53: #include <anthy/logger.h>
   54: #include <anthy/prediction.h>
   55: 
   56: #include "dic_main.h"
   57: #include "dic_personality.h"
   58: 
   59: /* 個人辞書をセーブするファイル名のsuffix */
   60: #define ENCODING_SUFFIX ".utf8"
   61: 
   62: 
   63: enum val_type {
   64:   RT_EMPTY, RT_VAL, RT_XSTR, RT_XSTRP
   65: };
   66: 
   67: /* 値 */
   68: struct record_val {
   69:   enum val_type type;
   70:   union {
   71:     xstr str;
   72:     int val;
   73:     xstr* strp;
   74:   } u;
   75: };
   76: 
   77: /* 行 */
   78: struct record_row {
   79:   xstr key;
   80:   int nr_vals;
   81:   struct record_val *vals;
   82: };
   83: 
   84: /* trie node管理用 */
   85: struct trie_node {
   86:   struct trie_node *l;
   87:   struct trie_node *r;
   88:   int bit;
   89:   struct record_row row;
   90:   struct trie_node *lru_prev, *lru_next; /* 両端ループ */
   91:   int dirty; /* LRU のための used, sused ビット */
   92: };
   93: 
   94: /* trie treeのroot */
   95: struct trie_root {
   96:   struct trie_node root;
   97:   allocator node_ator;
   98: };
   99: 
  100: #define LRU_USED  0x01
  101: #define LRU_SUSED 0x02
  102: #define PROTECT   0x04 /* 差分書き出し時に使う(LRUとは関係ない)
  103:                         *   差分書き出しでは、ファイルに書き出す前に
  104:                         *   ファイル上に他のプロセスが記録した更新を
  105:                         *   読み込む。それによって、これから追加しよ
  106:                         *   うとするノードが消されるのを防ぐ
  107:                         */
  108: /*
  109:  * LRU:
  110:  *   USED:  メモリ上で使われた
  111:  *   SUSED: 保存された used ビット
  112:  *
  113:  * LRUリスト上では、 USED は必ずリスト先頭に並んでいるが、 SUSED は
  114:  * フラグなしのノードと混在している可能性がある。
  115:  *
  116:  * n個を残すように指定された時の動作
  117:  *    1. used > n
  118:  *        LRU リストの先頭から n 番目以降を消す
  119:  *    2. used + sused > n
  120:  *        used -> 残す
  121:  *        sused -> sused フラグを落す
  122:  *        それ以外 -> 消す
  123:  *    3. それ以外
  124:  *        全て残す
  125:  * ファイルに書き出す時に、 used || sused -> sused として書き出す
  126:  */
  127: 
  128: /** セクション */
  129: struct record_section {
  130:   const char *name;
  131:   struct trie_root cols;
  132:   struct record_section *next;
  133:   int lru_nr_used, lru_nr_sused; /* LRU 用 */
  134: };
  135: 
  136: /** データベース */
  137: struct record_stat {
  138:   struct record_section section_list; /* sectionのリスト*/
  139:   struct record_section *cur_section;
  140:   struct trie_root xstrs; /* xstr を intern するための trie */
  141:   struct trie_node *cur_row;
  142:   int row_dirty; /* cur_row が保存の必要があるか */
  143:   int encoding;
  144:   /**/
  145:   int is_anon;
  146:   const char *id;         /* パーソナリティのid */
  147:   char *base_fn; /* 基本ファイル 絶対パス */
  148:   char *journal_fn; /* 差分ファイル 絶対パス */
  149:   /**/
  150:   time_t base_timestamp; /* 基本ファイルのタイムスタンプ */
  151:   int last_update;  /* 差分ファイルの最後に読んだ位置 */
  152:   time_t journal_timestamp; /* 差分ファイルのタイムスタンプ */
  153: };
  154: 
  155: /* 差分が100KB越えたら基本ファイルへマージ */
  156: #define FILE2_LIMIT 102400
  157: 
  158: 
  159: /*
  160:  * xstr の intern:
  161:  *  個人ごと( record_stat ごと)に文字列を intern する。これは、
  162:  *  メモリの節約の他に、データベースの flush 時にデータベースに
  163:  *  由来する xstr が無効になるのを防ぐ目的がある。
  164:  *  したがって、データベースの flush 時でも xstr の intern 用
  165:  *  のデータベース xstrs はそのまま保存する。
  166:  *  
  167:  *  xstrs: xstr の intern 用のデータベース
  168:  *         row の key を intern された xstr として使う。
  169:  *         row に value は持たない。
  170:  *                    (将来的には参照カウンタをつけてもいいかも)
  171:  *  参照: intern_xstr()
  172:  */
  173: 
  174: /*
  175:  * 差分書き出し:
  176:  *  データベースの保存、複数の anthy ライブラリをリンクした
  177:  *  プロセスの学習履歴の同期のために、学習履歴の更新情報を
  178:  *  逐一ファイルに書き出す。
  179:  *
  180:  * ・基本ファイル  古い anthy の学習履歴と同じ形式。
  181:  *                 差分情報を適用する元となるファイル。
  182:  *                 基本的には起動時だけに読み込む。
  183:  *                 このプログラム中でファイル1，baseと呼ぶことがある。
  184:  * ・差分ファイル  基本ファイルに対する更新情報。
  185:  *                 データベースに対する更新がコミットされるたびに
  186:  *                 読み書きされる。
  187:  *                 このプログラム中でファイル2，journalと呼ぶことがある。
  188:  *  基本方針:
  189:  *     データベースに対する更新がコミットされると、まず差分ファイル
  190:  *     に他のプロセスが追加した更新情報を読み込み、その後に自分の
  191:  *     コミットした更新を差分ファイルに書き出す。
  192:  *     これらはロックファイルを用いてアトミックに行われる。また、
  193:  *     基本ファイル、差分ファイルとも、ロックを取っている間しか
  194:  *     オープンしていてはいけない。
  195:  *  追加と削除:
  196:  *     追加はすでにメモリ上で更新された row をコミットによって
  197:  *     メモリに書き出すため、
  198:  *       1. コミット対象 row 以外を差分ファイルの情報で
  199:  *       2. コミット対象 row を差分ファイルに書き出し
  200:  *     とする。削除はまだメモリ上に row が残っている状態でコミット
  201:  *     が行われる(削除要求をコミットとして扱う)ため、
  202:  *       1. 削除の情報を差分ファイルに書き出し
  203:  *       2. 差分ファイルの読み込みにより削除要求も実行する
  204:  *     とする。
  205:  *  基本ファイルの更新:
  206:  *     差分ファイルがある程度肥大化すると、差分ファイルの情報を
  207:  *     基本ファイルに反映して差分ファイルを空にする。
  208:  *     更新するプロセス:
  209:  *       差分ファイルに書き出しを行った後、差分ファイルの大きさを調べ、
  210:  *       肥大化していれば、そのときのメモリ上のデータベース(これには
  211:  *       全ての差分ファイルの更新が適用されている)を基本ファイルに
  212:  *       書き出す。
  213:  *     それ以外のプロセス:
  214:  *       差分ファイルを読む前に、基本ファイルが更新されているかを
  215:  *       ファイルのタイムスタンプで調べ、更新されていれば、コミット
  216:  *       された更新情報を直ちに更新ファイルに追加し、メモリ上の
  217:  *       データベースを flush した後基本ファイル、差分ファイルを
  218:  *       読み込み直す。
  219:  *       データベースの flush により、 
  220:  *           ・cur_row が無効になる (NULL になる)
  221:  *           ・cur_section の有効性は保存される(sectionは解放しない)
  222:  *           ・xstr は intern していれば保存される
  223:  *                              (すべての xstr は intern されているはず)
  224:  *   結局、次の様になる:
  225:  *     if (基本ファイルが更新されている) {
  226:  *             差分ファイルへコミットされた更新を書き出す;
  227:  *             データベースのフラッシュ;
  228:  *             基本ファイルの読込と差分ファイルの最終読込位置クリア;
  229:  *             差分ファイルの読込と差分ファイルの最終読込位置更新;
  230:  *     } else {
  231:  *             if (追加) {
  232:  *                     差分ファイルの読込と差分ファイルの最終読込位置更新;
  233:  *                     差分ファイルへの書き出し;
  234:  *             } else {
  235:  *                     差分ファイルへの書き出し;
  236:  *                     差分ファイルの読込と差分ファイルの最終読込位置更新;
  237:  *             }
  238:  *     }
  239:  *     if (差分ファイルが大きい) {
  240:  *             基本ファイルへの書き出し;
  241:  *             差分ファイルのクリア;
  242:  *     }
  243:  */
  244: 
  245: static allocator record_ator;
  246: 
  247: /* trie操作用 */
  248: static void init_trie_root(struct trie_root *n);
  249: static int trie_key_nth_bit(xstr* key, int n);
  250: static int trie_key_first_diff_bit_1byte(xchar c1, xchar c2);
  251: static int trie_key_first_diff_bit(xstr *k1, xstr *k2);
  252: static int trie_key_cmp(xstr *k1, xstr *k2);
  253: static void trie_key_dup(xstr *dst, xstr *src);
  254: static void trie_row_init(struct record_row *rc);
  255: static void trie_row_free(struct record_row *rc);
  256: static struct trie_node *trie_find(struct trie_root *root, xstr *key);
  257: static struct trie_node *trie_insert(struct trie_root *root, xstr *key,
  258:                                      int dirty, int *nr_used, int *nr_sused);
  259: static void trie_remove(struct trie_root *root, xstr *key,
  260:                         int *nr_used, int *nr_sused);
  261: static struct trie_node *trie_first(struct trie_root *root);
  262: static struct trie_node *trie_next(struct trie_root *root,
  263:                                    struct trie_node *cur);
  264: static void trie_remove_all(struct trie_root *root,
  265:                             int *nr_used, int *nr_sused);
  266: static void trie_remove_old(struct trie_root *root, int count,
  267:                             int* nr_used, int* nr_sused);
  268: static void trie_mark_used(struct trie_root *root, struct trie_node *n,
  269:                            int *nr_used, int *nr_sused);
  270: 
  271: 
  272: /* 
  273:  * トライの実装
  274:  * struct trie_nodeのうちrow以外の部分とrow.keyを使用
  275:  * 削除の時はtrie_row_freeを使ってrowの内容を解放
  276:  */
  277: 
  278: #define PUTNODE(x) ((x) == &root->root ? printf("root\n") : anthy_putxstrln(&(x)->row.key))
  279: static int
  280: debug_trie_dump(FILE* fp, struct trie_node* n, int encoding)
  281: {
  282:   int cnt = 0;
  283:   char buf[1024];
  284: 
  285:   if (n->l->bit > n->bit) {
  286:     cnt = debug_trie_dump(fp, n->l, encoding);
  287:   } else {
  288:     if (n->l->row.key.len == -1) {
  289:       if (fp) {
  290:         fprintf(fp, "root\n");
  291:       }
  292:     } else {
  293:       if (fp) {
  294:         anthy_sputxstr(buf, &n->l->row.key, encoding);
  295:         fprintf(fp, "%s\n", buf);
  296:       }
  297:       cnt = 1;
  298:     }
  299:   }
  300: 
  301:   if (n->r->bit > n->bit) {
  302:     return cnt + debug_trie_dump(fp, n->r, encoding);
  303:   } else {
  304:     if (n->r->row.key.len == -1) {
  305:       if(fp) {
  306:         fprintf(fp, "root\n");
  307:       }
  308:     } else {
  309:       if(fp) {
  310:         anthy_sputxstr(buf, &n->r->row.key, encoding);
  311:         fprintf(fp, "%s\n", buf);
  312:       }
  313:       return cnt + 1;
  314:     }
  315:   }
  316: 
  317:   return cnt;
  318: }
  319: 
  320: static void
  321: init_trie_root(struct trie_root *root)
  322: {
  323:   struct trie_node* n;
  324:   root->node_ator = anthy_create_allocator(sizeof(struct trie_node), NULL);
  325:   n = &root->root;
  326:   n->l = n;
  327:   n->r = n;
  328:   n->bit = 0;
  329:   n->lru_next = n;
  330:   n->lru_prev = n;
  331:   n->dirty = 0;
  332:   trie_row_init(&n->row);
  333:   n->row.key.len = -1;
  334: }
  335: 
  336: /*
  337:  * bit0: 0
  338:  * bit1: headのキーだけ0
  339:  * bit2: 文字列のビット0
  340:  * bit3: 文字列のビット1
  341:  *   ...
  342:  * 文字列長を越えると0
  343:  */
  344: static int
  345: trie_key_nth_bit(xstr* key, int n)
  346: {
  347:   switch (n) {
  348:   case 0:
  349:     return 0;
  350:   case 1:
  351:     return key->len + 1; /* key->len == -1 ? 0 : non-zero */
  352:   default:
  353:     {
  354:       int pos;
  355:       n -= 2;
  356:       pos = n / (sizeof(xchar) << 3);
  357:       if (pos >= key->len) {
  358:         return 0;
  359:       }
  360:       return key->str[pos] & (1 << (n % (sizeof(xchar) << 3)));
  361:     }
  362:   }
  363: }
  364: 
  365: /* c1 == c2 では呼んではいけない */
  366: static int
  367: trie_key_first_diff_bit_1byte(xchar c1, xchar c2)
  368: {
  369:   int i;
  370:   int ptn;
  371:   for (i = 0, ptn = c1 ^ c2; !(ptn & 1); i++, ptn >>= 1 )
  372:     ;
  373:   return i;
  374: }
  375: 
  376: /*
  377:  * k1 == k2 では呼んではいけない
  378:  * ki->str[0 .. (ki->len - 1)]に0はないと仮定
  379:  */
  380: #define MIN(a,b) ((a)<(b)?(a):(b))
  381: static int
  382: trie_key_first_diff_bit(xstr *k1, xstr *k2)
  383: {
  384:   int len;
  385:   int i;
  386: 
  387:   len = MIN(k1->len, k2->len);
  388:   if (len == -1) {
  389:     return 1;
  390:   }
  391:   for ( i = 0 ; i < len ; i++ ){
  392:     if (k1->str[i] != k2->str[i]) {
  393:       return (2 + (i * (sizeof(xchar) << 3)) + 
  394:               trie_key_first_diff_bit_1byte(k1->str[i], k2->str[i]));
  395:     }
  396:   }
  397:   if (k1->len < k2->len) {
  398:     return (2 + (i * (sizeof(xchar) << 3)) +
  399:             trie_key_first_diff_bit_1byte(0, k2->str[i]));
  400:   } else {
  401:     return (2 + (i * (sizeof(xchar) << 3)) +
  402:             trie_key_first_diff_bit_1byte(k1->str[i], 0));
  403:   }
  404: }
  405: #undef MIN
  406: 
  407: static int
  408: trie_key_cmp(xstr *k1, xstr *k2)
  409: {
  410:   if (k1->len == -1 || k2->len == -1) {
  411:     return k1->len - k2->len;
  412:   }
  413:   return anthy_xstrcmp(k1, k2);
  414: }
  415: 
  416: static void
  417: trie_key_dup(xstr *dst, xstr *src)
  418: {
  419:   dst->str = anthy_xstr_dup_str(src);
  420:   dst->len = src->len;
  421: }
  422: 
  423: /*
  424:  * 見つからなければ 0 
  425:  */
  426: static struct trie_node *
  427: trie_find(struct trie_root *root, xstr *key)
  428: {
  429:   struct trie_node *p;
  430:   struct trie_node *q;
  431: 
  432:   p = &root->root;
  433:   q = p->l;
  434:   while (p->bit < q->bit) {
  435:     p = q;
  436:     q = trie_key_nth_bit(key, p->bit) ? p->r : p->l;
  437:   }
  438:   return trie_key_cmp(&q->row.key,key) ? NULL : q; 
  439: }
  440: 
  441: /*
  442:  * 最長マッチのための補助関数
  443:  *  key で探索して、始めて一致しなくなったノードを返す。
  444:  */
  445: static struct trie_node *
  446: trie_find_longest (struct trie_root* root, xstr *key)
  447: {
  448:   struct trie_node *p;
  449:   struct trie_node *q;
  450: 
  451:   p = &root->root;
  452:   q = p->l;
  453:   while (p->bit < q->bit) {
  454:     p = q;
  455:     q = trie_key_nth_bit(key, p->bit) ? p->r : p->l;
  456:   }
  457: 
  458:   return q;
  459: }
  460: 
  461: /* 
  462:  * 追加したノードを返す
  463:  * すでに同じキーをもつノードがあるときは、追加せずに0を返す
  464:  */
  465: static struct trie_node *
  466: trie_insert(struct trie_root *root, xstr *key,
  467:             int dirty, int *nr_used, int *nr_sused)
  468: {
  469:   struct trie_node *n;
  470:   struct trie_node *p;
  471:   struct trie_node *q;
  472:   int i;
  473: 
  474:   p = &root->root;
  475:   q = p->l;
  476:   while (p->bit < q->bit) {
  477:     p = q;
  478:     q = trie_key_nth_bit(key, p->bit) ? p->r : p->l;
  479:   }
  480:   if (trie_key_cmp(&q->row.key,key) == 0) {
  481:     /* USED > SUSED > 0 で強い方を残す */
  482:     if (dirty == LRU_USED) {
  483:       trie_mark_used(root, q, nr_used, nr_sused);
  484:     } else if (q->dirty == 0) {
  485:       q->dirty = dirty;
  486:     }
  487:     return 0;
  488:   }
  489:   i = trie_key_first_diff_bit(&q->row.key, key);
  490:   p = &root->root;
  491:   q = p->l;
  492:   while (p->bit < q->bit && i > q->bit) {
  493:     p = q;
  494:     q = trie_key_nth_bit(key, p->bit) ? p->r : p->l;
  495:   }
  496:   n = anthy_smalloc(root->node_ator);
  497:   trie_row_init(&n->row);
  498:   trie_key_dup(&n->row.key, key);
  499:   n->bit = i;
  500:   if (trie_key_nth_bit(key, i)) {
  501:     n->l = q;
  502:     n->r = n;
  503:   } else {
  504:     n->l = n;
  505:     n->r = q;
  506:   }
  507:   if (p->l == q) {
  508:     p->l = n;
  509:   } else {
  510:     p->r = n;
  511:   }
  512: 
  513:   /* LRU の処理 */
  514:   if (dirty == LRU_USED) {
  515:     root->root.lru_next->lru_prev = n;
  516:     n->lru_prev = &root->root;
  517:     n->lru_next = root->root.lru_next;
  518:     root->root.lru_next = n;
  519:     (*nr_used)++;
  520:   } else {
  521:     root->root.lru_prev->lru_next = n;
  522:     n->lru_next = &root->root;
  523:     n->lru_prev = root->root.lru_prev;
  524:     root->root.lru_prev = n;
  525:     if (dirty == LRU_SUSED) {
  526:       (*nr_sused)++;
  527:     }
  528:   }
  529:   n->dirty = dirty;
  530:   return n;
  531: }
  532: 
  533: /* 
  534:  * ノードを見つけると削除する
  535:  * 内部でtrie_row_freeを呼び、キーを含むデータ部分をfreeする
  536:  *
  537:  * データとノードを削除する。
  538:  * 削除対象のデータは削除対象のノードに格納されているとは
  539:  * 限らないことに注意。
  540:  * 1. 削除対象の葉を持つノードに削除対象の葉が含まれているとき
  541:  *  削除対象のノードは、子への枝のうち、生きのこる枝を親に渡して死ぬ
  542:  * 2. 削除対象の葉を持つノードの祖先に削除対象の葉が含まれているとき
  543:  *  1. に加えて、削除対象の葉をもつノードを殺して、代わりに削除
  544:  *  対象のノードを削除対象の葉をもつノードの位置に移動させ生かす
  545:  */
  546: static void
  547: trie_remove(struct trie_root *root, xstr *key, 
  548:             int *nr_used, int *nr_sused)
  549: {
  550:   struct trie_node *p;
  551:   struct trie_node *q;
  552:   struct trie_node **pp = NULL; /* gcc の warning 回避 *