xref: /dokuwiki/inc/indexer.php (revision 1c07b9e622d139fa815c955c89569f96342475fb) 
1<?php
2/**
3 * Functions to create the fulltext search index
4 *
5 * @license    GPL 2 (http://www.gnu.org/licenses/gpl.html)
6 * @author     Andreas Gohr <andi@splitbrain.org>
7 */
8
9if(!defined('DOKU_INC')) die('meh.');
10
11// set the minimum token length to use in the index (note, this doesn't apply to numeric tokens)
12if (!defined('IDX_MINWORDLENGTH')) define('IDX_MINWORDLENGTH',2);
13
14// Asian characters are handled as words. The following regexp defines the
15// Unicode-Ranges for Asian characters
16// Ranges taken from http://en.wikipedia.org/wiki/Unicode_block
17// I'm no language expert. If you think some ranges are wrongly chosen or
18// a range is missing, please contact me
19define('IDX_ASIAN1','[\x{0E00}-\x{0E7F}]'); // Thai
20define('IDX_ASIAN2','['.
21                   '\x{2E80}-\x{3040}'.  // CJK -> Hangul
22                   '\x{309D}-\x{30A0}'.
23                   '\x{30FD}-\x{31EF}\x{3200}-\x{D7AF}'.
24                   '\x{F900}-\x{FAFF}'.  // CJK Compatibility Ideographs
25                   '\x{FE30}-\x{FE4F}'.  // CJK Compatibility Forms
26                   ']');
27define('IDX_ASIAN3','['.                // Hiragana/Katakana (can be two characters)
28                   '\x{3042}\x{3044}\x{3046}\x{3048}'.
29                   '\x{304A}-\x{3062}\x{3064}-\x{3082}'.
30                   '\x{3084}\x{3086}\x{3088}-\x{308D}'.
31                   '\x{308F}-\x{3094}'.
32                   '\x{30A2}\x{30A4}\x{30A6}\x{30A8}'.
33                   '\x{30AA}-\x{30C2}\x{30C4}-\x{30E2}'.
34                   '\x{30E4}\x{30E6}\x{30E8}-\x{30ED}'.
35                   '\x{30EF}-\x{30F4}\x{30F7}-\x{30FA}'.
36                   ']['.
37                   '\x{3041}\x{3043}\x{3045}\x{3047}\x{3049}'.
38                   '\x{3063}\x{3083}\x{3085}\x{3087}\x{308E}\x{3095}-\x{309C}'.
39                   '\x{30A1}\x{30A3}\x{30A5}\x{30A7}\x{30A9}'.
40                   '\x{30C3}\x{30E3}\x{30E5}\x{30E7}\x{30EE}\x{30F5}\x{30F6}\x{30FB}\x{30FC}'.
41                   '\x{31F0}-\x{31FF}'.
42                   ']?');
43define('IDX_ASIAN', '(?:'.IDX_ASIAN1.'|'.IDX_ASIAN2.'|'.IDX_ASIAN3.')');
44
45/**
46 * Measure the length of a string.
47 * Differs from strlen in handling of asian characters.
48 *
49 * @author Tom N Harris <tnharris@whoopdedo.org>
50 */
51function wordlen($w){
52    $l = strlen($w);
53    // If left alone, all chinese "words" will get put into w3.idx
54    // So the "length" of a "word" is faked
55    if(preg_match_all('/[\xE2-\xEF]/',$w,$leadbytes)) {
56        foreach($leadbytes[0] as $b)
57            $l += ord($b) - 0xE1;
58    }
59    return $l;
60}
61
62/**
63 * Write a list of strings to an index file.
64 *
65 * @author Tom N Harris <tnharris@whoopdedo.org>
66 */
67function idx_saveIndex($pre, $wlen, &$idx){
68    global $conf;
69    $fn = $conf['indexdir'].'/'.$pre.$wlen;
70    $fh = @fopen($fn.'.tmp','w');
71    if(!$fh) return false;
72    foreach ($idx as $line) {
73        fwrite($fh,$line);
74    }
75    fclose($fh);
76    if(isset($conf['fperm'])) chmod($fn.'.tmp', $conf['fperm']);
77    io_rename($fn.'.tmp', $fn.'.idx');
78    return true;
79}
80
81/**
82 * Append a given line to an index file.
83 *
84 * @author Andreas Gohr <andi@splitbrain.org>
85 */
86function idx_appendIndex($pre, $wlen, $line){
87    global $conf;
88    $fn = $conf['indexdir'].'/'.$pre.$wlen;
89    $fh = @fopen($fn.'.idx','a');
90    if(!$fh) return false;
91    fwrite($fh,$line);
92    fclose($fh);
93    return true;
94}
95
96/**
97 * Read the list of words in an index (if it exists).
98 *
99 * @author Tom N Harris <tnharris@whoopdedo.org>
100 */
101function idx_getIndex($pre, $wlen){
102    global $conf;
103    $fn = $conf['indexdir'].'/'.$pre.$wlen.'.idx';
104    if(!@file_exists($fn)) return array();
105    return file($fn);
106}
107
108/**
109 * Read a line ending with \n.
110 * Returns false on EOF.
111 *
112 * @author Tom N Harris <tnharris@whoopdedo.org>
113 */
114function _freadline($fh) {
115    if (feof($fh)) return false;
116    $ln = '';
117    while (($buf = fgets($fh,4096)) !== false) {
118        $ln .= $buf;
119        if (substr($buf,-1) == "\n") break;
120    }
121    if ($ln === '') return false;
122    if (substr($ln,-1) != "\n") $ln .= "\n";
123    return $ln;
124}
125
126/**
127 * Write a line to an index file.
128 *
129 * @author Tom N Harris <tnharris@whoopdedo.org>
130 */
131function idx_saveIndexLine($pre, $wlen, $idx, $line){
132    global $conf;
133    if(substr($line,-1) != "\n") $line .= "\n";
134    $fn = $conf['indexdir'].'/'.$pre.$wlen;
135    $fh = @fopen($fn.'.tmp','w');
136    if(!$fh) return false;
137    $ih = @fopen($fn.'.idx','r');
138    if ($ih) {
139        $ln = -1;
140        while (($curline = _freadline($ih)) !== false) {
141            if (++$ln == $idx) {
142                fwrite($fh, $line);
143            } else {
144                fwrite($fh, $curline);
145            }
146        }
147        if ($idx > $ln) {
148            fwrite($fh,$line);
149        }
150        fclose($ih);
151    } else {
152        fwrite($fh,$line);
153    }
154    fclose($fh);
155    if($conf['fperm']) chmod($fn.'.tmp', $conf['fperm']);
156    io_rename($fn.'.tmp', $fn.'.idx');
157    return true;
158}
159
160/**
161 * Read a single line from an index (if it exists).
162 *
163 * @author Tom N Harris <tnharris@whoopdedo.org>
164 */
165function idx_getIndexLine($pre, $wlen, $idx){
166    global $conf;
167    $fn = $conf['indexdir'].'/'.$pre.$wlen.'.idx';
168    if(!@file_exists($fn)) return '';
169    $fh = @fopen($fn,'r');
170    if(!$fh) return '';
171    $ln = -1;
172    while (($line = _freadline($fh)) !== false) {
173        if (++$ln == $idx) break;
174    }
175    fclose($fh);
176    return "$line";
177}
178
179/**
180 * Split a page into words
181 *
182 * Returns an array of word counts, false if an error occurred.
183 * Array is keyed on the word length, then the word index.
184 *
185 * @author Andreas Gohr <andi@splitbrain.org>
186 * @author Christopher Smith <chris@jalakai.co.uk>
187 */
188function idx_getPageWords($page){
189    global $conf;
190    $swfile   = DOKU_INC.'inc/lang/'.$conf['lang'].'/stopwords.txt';
191    if(@file_exists($swfile)){
192        $stopwords = file($swfile);
193    }else{
194        $stopwords = array();
195    }
196
197    $body = '';
198    $data = array($page, $body);
199    $evt = new Doku_Event('INDEXER_PAGE_ADD', $data);
200    if ($evt->advise_before()) $data[1] .= rawWiki($page);
201    $evt->advise_after();
202    unset($evt);
203
204    list($page,$body) = $data;
205
206    $tokens = idx_tokenizer($body, $stopwords);
207    $tokens = array_count_values($tokens);   // count the frequency of each token
208
209    // ensure the deaccented or romanised page names of internal links are added to the token array
210    // (this is necessary for the backlink function -- there maybe a better way!)
211    if ($conf['deaccent']) {
212        $links = p_get_metadata($page,'relation references');
213
214        if (!empty($links)) {
215            $tmp = join(' ',array_keys($links));                // make a single string
216            $tmp = strtr($tmp, ':', ' ');                       // replace namespace separator with a space
217            $link_tokens = array_unique(explode(' ', $tmp));    // break into tokens
218
219            foreach ($link_tokens as $link_token) {
220                if (isset($tokens[$link_token])) continue;
221                $tokens[$link_token] = 1;
222            }
223        }
224    }
225
226    $words = array();
227    foreach ($tokens as $w => $c) {
228        $l = wordlen($w);
229        if(isset($words[$l])){
230            $words[$l][$w] = $c + (isset($words[$l][$w]) ? $words[$l][$w] : 0);
231        }else{
232            $words[$l] = array($w => $c);
233        }
234    }
235
236    // arrive here with $words = array(wordlen => array(word => frequency))
237
238    $index = array(); //resulting index
239    foreach (array_keys($words) as $wlen){
240        $word_idx = idx_getIndex('w',$wlen);
241        foreach ($words[$wlen] as $word => $freq) {
242            $wid = array_search("$word\n",$word_idx);
243            if(!is_int($wid)){
244                $wid = count($word_idx);
245                $word_idx[] = "$word\n";
246            }
247            if(!isset($index[$wlen]))
248                $index[$wlen] = array();
249            $index[$wlen][$wid] = $freq;
250        }
251
252        // save back word index
253        if(!idx_saveIndex('w',$wlen,$word_idx)){
254            trigger_error("Failed to write word index", E_USER_ERROR);
255            return false;
256        }
257    }
258
259    return $index;
260}
261
262/**
263 * Adds/updates the search for the given page
264 *
265 * This is the core function of the indexer which does most
266 * of the work. This function needs to be called with proper
267 * locking!
268 *
269 * @author Andreas Gohr <andi@splitbrain.org>
270 */
271function idx_addPage($page){
272    global $conf;
273
274    // load known documents
275    $page_idx = idx_getIndex('page','');
276
277    // get page id (this is the linenumber in page.idx)
278    $pid = array_search("$page\n",$page_idx);
279    if(!is_int($pid)){
280        $pid = count($page_idx);
281        // page was new - write back
282        if (!idx_appendIndex('page','',"$page\n")){
283            trigger_error("Failed to write page index", E_USER_ERROR);
284            return false;
285        }
286    }
287    unset($page_idx); // free memory
288
289    idx_saveIndexLine('title', '', $pid, p_get_first_heading($page, false));
290
291    $pagewords = array();
292    // get word usage in page
293    $words = idx_getPageWords($page);
294    if($words === false) return false;
295
296    if(!empty($words)) {
297        foreach(array_keys($words) as $wlen){
298            $index = idx_getIndex('i',$wlen);
299            foreach($words[$wlen] as $wid => $freq){
300                if($wid<count($index)){
301                    $index[$wid] = idx_updateIndexLine($index[$wid],$pid,$freq);
302                }else{
303                    // New words **should** have been added in increasing order
304                    // starting with the first unassigned index.
305                    // If someone can show how this isn't true, then I'll need to sort
306                    // or do something special.
307                    $index[$wid] = idx_updateIndexLine('',$pid,$freq);
308                }
309                $pagewords[] = "$wlen*$wid";
310            }
311            // save back word index
312            if(!idx_saveIndex('i',$wlen,$index)){
313                trigger_error("Failed to write index", E_USER_ERROR);
314                return false;
315            }
316        }
317    }
318
319    // Remove obsolete index entries
320    $pageword_idx = trim(idx_getIndexLine('pageword','',$pid));
321    if ($pageword_idx !== '') {
322        $oldwords = explode(':',$pageword_idx);
323        $delwords = array_diff($oldwords, $pagewords);
324        $upwords = array();
325        foreach ($delwords as $word) {
326            if($word=='') continue;
327            list($wlen,$wid) = explode('*',$word);
328            $wid = (int)$wid;
329            $upwords[$wlen][] = $wid;
330        }
331        foreach ($upwords as $wlen => $widx) {
332            $index = idx_getIndex('i',$wlen);
333            foreach ($widx as $wid) {
334                $index[$wid] = idx_updateIndexLine($index[$wid],$pid,0);
335            }
336            idx_saveIndex('i',$wlen,$index);
337        }
338    }
339    // Save the reverse index
340    $pageword_idx = join(':',$pagewords)."\n";
341    if(!idx_saveIndexLine('pageword','',$pid,$pageword_idx)){
342        trigger_error("Failed to write word index", E_USER_ERROR);
343        return false;
344    }
345
346    return true;
347}
348
349/**
350 * Write a new index line to the filehandle
351 *
352 * This function writes an line for the index file to the
353 * given filehandle. It removes the given document from
354 * the given line and readds it when $count is >0.
355 *
356 * @deprecated - see idx_updateIndexLine
357 * @author Andreas Gohr <andi@splitbrain.org>
358 */
359function idx_writeIndexLine($fh,$line,$pid,$count){
360    fwrite($fh,idx_updateIndexLine($line,$pid,$count));
361}
362
363/**
364 * Modify an index line with new information
365 *
366 * This returns a line of the index. It removes the
367 * given document from the line and readds it if
368 * $count is >0.
369 *
370 * @author Tom N Harris <tnharris@whoopdedo.org>
371 * @author Andreas Gohr <andi@splitbrain.org>
372 */
373function idx_updateIndexLine($line,$pid,$count){
374    $line = trim($line);
375    $updated = array();
376    if($line != ''){
377        $parts = explode(':',$line);
378        // remove doc from given line
379        foreach($parts as $part){
380            if($part == '') continue;
381            list($doc,$cnt) = explode('*',$part);
382            if($doc != $pid){
383                $updated[] = $part;
384            }
385        }
386    }
387
388    // add doc
389    if ($count){
390        $updated[] = "$pid*$count";
391    }
392
393    return join(':',$updated)."\n";
394}
395
396/**
397 * Get the list of lenghts indexed in the wiki
398 *
399 * Read the index directory or a cache file and returns
400 * a sorted array of lengths of the words used in the wiki.
401 *
402 * @author YoBoY <yoboy.leguesh@gmail.com>
403 */
404function idx_listIndexLengths() {
405    global $conf;
406    // testing what we have to do, create a cache file or not.
407    if ($conf['readdircache'] == 0) {
408        $docache = false;
409    } else {
410        clearstatcache();
411        if (@file_exists($conf['indexdir'].'/lengths.idx') and (time() < @filemtime($conf['indexdir'].'/lengths.idx') + $conf['readdircache'])) {
412            if (($lengths = @file($conf['indexdir'].'/lengths.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES) ) !== false) {
413                $idx = array();
414                foreach ( $lengths as $length) {
415                    $idx[] = (int)$length;
416                }
417                return $idx;
418            }
419        }
420        $docache = true;
421    }
422
423    if ($conf['readdircache'] == 0 or $docache ) {
424        $dir = @opendir($conf['indexdir']);
425        if($dir===false)
426            return array();
427        $idx[] = array();
428        while (($f = readdir($dir)) !== false) {
429            if (substr($f,0,1) == 'i' && substr($f,-4) == '.idx'){
430                $i = substr($f,1,-4);
431                if (is_numeric($i))
432                    $idx[] = (int)$i;
433            }
434        }
435        closedir($dir);
436        sort($idx);
437        // we save this in a file.
438        if ($docache === true) {
439            $handle = @fopen($conf['indexdir'].'/lengths.idx','w');
440            @fwrite($handle, implode("\n",$idx));
441            @fclose($handle);
442        }
443        return $idx;
444    }
445
446    return array();
447}
448
449/**
450 * Get the word lengths that have been indexed.
451 *
452 * Reads the index directory and returns an array of lengths
453 * that there are indices for.
454 *
455 * @author YoBoY <yoboy.leguesh@gmail.com>
456 */
457function idx_indexLengths(&$filter){
458    global $conf;
459    $idx = array();
460    if (is_array($filter)){
461        // testing if index files exists only
462        foreach ($filter as $key => $value) {
463            if (@file_exists($conf['indexdir']."/i$key.idx")) {
464                $idx[] = $key;
465            }
466        }
467    } else {
468        $lengths = idx_listIndexLengths();
469        foreach ( $lengths as $key => $length) {
470            // we keep all the values equal or superior
471            if ((int)$length >= (int)$filter) {
472                $idx[] = $length;
473            }
474        }
475    }
476    return $idx;
477}
478
479/**
480 * Find the the index number of each search term.
481 *
482 * This will group together words that appear in the same index.
483 * So it should perform better, because it only opens each index once.
484 * Actually, it's not that great. (in my experience) Probably because of the disk cache.
485 * And the sorted function does more work, making it slightly slower in some cases.
486 *
487 * @param array    $words   The query terms. Words should only contain valid characters,
488 *                          with a '*' at either the beginning or end of the word (or both)
489 * @param arrayref $result  Set to word => array("length*id" ...), use this to merge the
490 *                          index locations with the appropriate query term.
491 * @return array            Set to length => array(id ...)
492 *
493 * @author Tom N Harris <tnharris@whoopdedo.org>
494 */
495function idx_getIndexWordsSorted($words,&$result){
496    // parse and sort tokens
497    $tokens = array();
498    $tokenlength = array();
499    $tokenwild = array();
500    foreach($words as $word){
501        $result[$word] = array();
502        $wild = 0;
503        $xword = $word;
504        $wlen = wordlen($word);
505
506        // check for wildcards
507        if(substr($xword,0,1) == '*'){
508            $xword = substr($xword,1);
509            $wild |= 1;
510            $wlen -= 1;
511        }
512        if(substr($xword,-1,1) == '*'){
513            $xword = substr($xword,0,-1);
514            $wild |= 2;
515            $wlen -= 1;
516        }
517        if ($wlen < IDX_MINWORDLENGTH && $wild == 0 && !is_numeric($xword)) continue;
518        if(!isset($tokens[$xword])){
519            $tokenlength[$wlen][] = $xword;
520        }
521        if($wild){
522            $ptn = preg_quote($xword,'/');
523            if(($wild&1) == 0) $ptn = '^'.$ptn;
524            if(($wild&2) == 0) $ptn = $ptn.'$';
525            $tokens[$xword][] = array($word, '/'.$ptn.'/');
526            if(!isset($tokenwild[$xword])) $tokenwild[$xword] = $wlen;
527        }else
528            $tokens[$xword][] = array($word, null);
529    }
530    asort($tokenwild);
531    // $tokens = array( base word => array( [ query word , grep pattern ] ... ) ... )
532    // $tokenlength = array( base word length => base word ... )
533    // $tokenwild = array( base word => base word length ... )
534
535    $length_filter = empty($tokenwild) ? $tokenlength : min(array_keys($tokenlength));
536    $indexes_known = idx_indexLengths($length_filter);
537    if(!empty($tokenwild)) sort($indexes_known);
538    // get word IDs
539    $wids = array();
540    foreach($indexes_known as $ixlen){
541        $word_idx = idx_getIndex('w',$ixlen);
542        // handle exact search
543        if(isset($tokenlength[$ixlen])){
544            foreach($tokenlength[$ixlen] as $xword){
545                $wid = array_search("$xword\n",$word_idx);
546                if(is_int($wid)){
547                    $wids[$ixlen][] = $wid;
548                    foreach($tokens[$xword] as $w)
549                        $result[$w[0]][] = "$ixlen*$wid";
550                }
551            }
552        }
553        // handle wildcard search
554        foreach($tokenwild as $xword => $wlen){
555            if($wlen >= $ixlen) break;
556            foreach($tokens[$xword] as $w){
557                if(is_null($w[1])) continue;
558                foreach(array_keys(preg_grep($w[1],$word_idx)) as $wid){
559                    $wids[$ixlen][] = $wid;
560                    $result[$w[0]][] = "$ixlen*$wid";
561                }
562            }
563        }
564    }
565    return $wids;
566}
567
568/**
569 * Lookup words in index
570 *
571 * Takes an array of word and will return a list of matching
572 * documents for each one.
573 *
574 * Important: No ACL checking is done here! All results are
575 *            returned, regardless of permissions
576 *
577 * @author Andreas Gohr <andi@splitbrain.org>
578 */
579function idx_lookup($words){
580    global $conf;
581
582    $result = array();
583
584    $wids = idx_getIndexWordsSorted($words, $result);
585    if(empty($wids)) return array();
586
587    // load known words and documents
588    $page_idx = idx_getIndex('page','');
589
590    $docs = array();                          // hold docs found
591    foreach(array_keys($wids) as $wlen){
592        $wids[$wlen] = array_unique($wids[$wlen]);
593        $index = idx_getIndex('i',$wlen);
594        foreach($wids[$wlen] as $ixid){
595            if($ixid < count($index))
596                $docs["$wlen*$ixid"] = idx_parseIndexLine($page_idx,$index[$ixid]);
597        }
598    }
599
600    // merge found pages into final result array
601    $final = array();
602    foreach($result as $word => $res){
603        $final[$word] = array();
604        foreach($res as $wid){
605            $hits = &$docs[$wid];
606            foreach ($hits as $hitkey => $hitcnt) {
607                if (!isset($final[$word][$hitkey])) {
608                    $final[$word][$hitkey] = $hitcnt;
609                } else {
610                    $final[$word][$hitkey] += $hitcnt;
611                }
612            }
613        }
614    }
615    return $final;
616}
617
618/**
619 * Returns a list of documents and counts from a index line
620 *
621 * It omits docs with a count of 0 and pages that no longer
622 * exist.
623 *
624 * @param  array  $page_idx The list of known pages
625 * @param  string $line     A line from the main index
626 * @author Andreas Gohr <andi@splitbrain.org>
627 */
628function idx_parseIndexLine(&$page_idx,$line){
629    $result = array();
630
631    $line = trim($line);
632    if($line == '') return $result;
633
634    $parts = explode(':',$line);
635    foreach($parts as $part){
636        if($part == '') continue;
637        list($doc,$cnt) = explode('*',$part);
638        if(!$cnt) continue;
639        $doc = trim($page_idx[$doc]);
640        if(!$doc) continue;
641        // make sure the document still exists
642        if(!page_exists($doc,'',false)) continue;
643
644        $result[$doc] = $cnt;
645    }
646    return $result;
647}
648
649/**
650 * Tokenizes a string into an array of search words
651 *
652 * Uses the same algorithm as idx_getPageWords()
653 * Takes an arbitrarily complex string and returns a list of words
654 * suitable for indexing. The string may include spaces and line
655 * breaks
656 *
657 * @param string   $string     the query as given by the user
658 * @param arrayref $stopwords  array of stopwords
659 * @param boolean  $wc         are wildcards allowed?
660 * @return array               list of indexable words
661 * @author Tom N Harris <tnharris@whoopdedo.org>
662 * @author Andreas Gohr <andi@splitbrain.org>
663 */
664function idx_tokenizer($string,&$stopwords,$wc=false){
665    global $conf;
666    $words = array();
667    $wc = ($wc) ? '' : $wc = '\*';
668
669    if (!$stopwords)
670        $sw = array();
671    else
672        $sw =& $stopwords;
673
674    if ($conf['external_tokenizer']) {
675	if (0 == io_runcmd($conf['tokenizer_cmd'], $string, $output))
676            $string = $output;
677    } else {
678        if(preg_match('/[^0-9A-Za-z ]/u', $string)) {
679            // handle asian chars as single words (may fail on older PHP version)
680            $asia = @preg_replace('/('.IDX_ASIAN.')/u',' \1 ',$string);
681            if(!is_null($asia)) $string = $asia; //recover from regexp failure
682        }
683    }
684    $string = strtr($string, "\r\n\t", '   ');
685    if(preg_match('/[^0-9A-Za-z ]/u', $string))
686        $string = utf8_stripspecials($string, ' ', '\._\-:'.$wc);
687
688    $wordlist = explode(' ', $string);
689    foreach ($wordlist as $word) {
690        if(preg_match('/[^0-9A-Za-z]/u', $word)){
691            $word = utf8_strtolower($word);
692        }else{
693            $word = strtolower($word);
694        }
695        if (!is_numeric($word) && strlen($word) < IDX_MINWORDLENGTH) continue;
696        if(is_int(array_search("$word\n",$stopwords))) continue;
697        $words[] = $word;
698    }
699
700    return $words;
701}
702
703//Setup VIM: ex: et ts=4 enc=utf-8 :
704