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