source: documentation/trunk/packages/dokuwiki-2011-05-25a/inc/indexer.php@ 25027

Last change on this file since 25027 was 25027, checked in by jmt12, 12 years ago

Adding the packages directory, and within it a configured version of dokuwiki all ready to run
File size: 47.4 KB
Line 
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 <[email protected]>
7 * @author Tom N Harris <[email protected]>
8 */
9
10if(!defined('DOKU_INC')) die('meh.');
11
12// Version tag used to force rebuild on upgrade
13define('INDEXER_VERSION', 5);
14
15// set the minimum token length to use in the index (note, this doesn't apply to numeric tokens)
16if (!defined('IDX_MINWORDLENGTH')) define('IDX_MINWORDLENGTH',2);
17
18// Asian characters are handled as words. The following regexp defines the
19// Unicode-Ranges for Asian characters
20// Ranges taken from http://en.wikipedia.org/wiki/Unicode_block
21// I'm no language expert. If you think some ranges are wrongly chosen or
22// a range is missing, please contact me
23define('IDX_ASIAN1','[\x{0E00}-\x{0E7F}]'); // Thai
24define('IDX_ASIAN2','['.
25 '\x{2E80}-\x{3040}'. // CJK -> Hangul
26 '\x{309D}-\x{30A0}'.
27 '\x{30FD}-\x{31EF}\x{3200}-\x{D7AF}'.
28 '\x{F900}-\x{FAFF}'. // CJK Compatibility Ideographs
29 '\x{FE30}-\x{FE4F}'. // CJK Compatibility Forms
30 "\xF0\xA0\x80\x80-\xF0\xAA\x9B\x9F". // CJK Extension B
31 "\xF0\xAA\x9C\x80-\xF0\xAB\x9C\xBF". // CJK Extension C
32 "\xF0\xAB\x9D\x80-\xF0\xAB\xA0\x9F". // CJK Extension D
33 "\xF0\xAF\xA0\x80-\xF0\xAF\xAB\xBF". // CJK Compatibility Supplement
34 ']');
35define('IDX_ASIAN3','['. // Hiragana/Katakana (can be two characters)
36 '\x{3042}\x{3044}\x{3046}\x{3048}'.
37 '\x{304A}-\x{3062}\x{3064}-\x{3082}'.
38 '\x{3084}\x{3086}\x{3088}-\x{308D}'.
39 '\x{308F}-\x{3094}'.
40 '\x{30A2}\x{30A4}\x{30A6}\x{30A8}'.
41 '\x{30AA}-\x{30C2}\x{30C4}-\x{30E2}'.
42 '\x{30E4}\x{30E6}\x{30E8}-\x{30ED}'.
43 '\x{30EF}-\x{30F4}\x{30F7}-\x{30FA}'.
44 ']['.
45 '\x{3041}\x{3043}\x{3045}\x{3047}\x{3049}'.
46 '\x{3063}\x{3083}\x{3085}\x{3087}\x{308E}\x{3095}-\x{309C}'.
47 '\x{30A1}\x{30A3}\x{30A5}\x{30A7}\x{30A9}'.
48 '\x{30C3}\x{30E3}\x{30E5}\x{30E7}\x{30EE}\x{30F5}\x{30F6}\x{30FB}\x{30FC}'.
49 '\x{31F0}-\x{31FF}'.
50 ']?');
51define('IDX_ASIAN', '(?:'.IDX_ASIAN1.'|'.IDX_ASIAN2.'|'.IDX_ASIAN3.')');
52
53/**
54 * Version of the indexer taking into consideration the external tokenizer.
55 * The indexer is only compatible with data written by the same version.
56 *
57 * @triggers INDEXER_VERSION_GET
58 * Plugins that modify what gets indexed should hook this event and
59 * add their version info to the event data like so:
60 * $data[$plugin_name] = $plugin_version;
61 *
62 * @author Tom N Harris <[email protected]>
63 * @author Michael Hamann <[email protected]>
64 */
65function idx_get_version(){
66 static $indexer_version = null;
67 if ($indexer_version == null) {
68 global $conf;
69 $version = INDEXER_VERSION;
70
71 // DokuWiki version is included for the convenience of plugins
72 $data = array('dokuwiki'=>$version);
73 trigger_event('INDEXER_VERSION_GET', $data, null, false);
74 unset($data['dokuwiki']); // this needs to be first
75 ksort($data);
76 foreach ($data as $plugin=>$vers)
77 $version .= '+'.$plugin.'='.$vers;
78 $indexer_version = $version;
79 }
80 return $indexer_version;
81}
82
83/**
84 * Measure the length of a string.
85 * Differs from strlen in handling of asian characters.
86 *
87 * @author Tom N Harris <[email protected]>
88 */
89function wordlen($w){
90 $l = strlen($w);
91 // If left alone, all chinese "words" will get put into w3.idx
92 // So the "length" of a "word" is faked
93 if(preg_match_all('/[\xE2-\xEF]/',$w,$leadbytes)) {
94 foreach($leadbytes[0] as $b)
95 $l += ord($b) - 0xE1;
96 }
97 return $l;
98}
99
100/**
101 * Class that encapsulates operations on the indexer database.
102 *
103 * @author Tom N Harris <[email protected]>
104 */
105class Doku_Indexer {
106
107 /**
108 * Adds the contents of a page to the fulltext index
109 *
110 * The added text replaces previous words for the same page.
111 * An empty value erases the page.
112 *
113 * @param string $page a page name
114 * @param string $text the body of the page
115 * @return boolean the function completed successfully
116 * @author Tom N Harris <[email protected]>
117 * @author Andreas Gohr <[email protected]>
118 */
119 public function addPageWords($page, $text) {
120 if (!$this->lock())
121 return "locked";
122
123 // load known documents
124 $pid = $this->addIndexKey('page', '', $page);
125 if ($pid === false) {
126 $this->unlock();
127 return false;
128 }
129
130 $pagewords = array();
131 // get word usage in page
132 $words = $this->getPageWords($text);
133 if ($words === false) {
134 $this->unlock();
135 return false;
136 }
137
138 if (!empty($words)) {
139 foreach (array_keys($words) as $wlen) {
140 $index = $this->getIndex('i', $wlen);
141 foreach ($words[$wlen] as $wid => $freq) {
142 $idx = ($wid<count($index)) ? $index[$wid] : '';
143 $index[$wid] = $this->updateTuple($idx, $pid, $freq);
144 $pagewords[] = "$wlen*$wid";
145 }
146 if (!$this->saveIndex('i', $wlen, $index)) {
147 $this->unlock();
148 return false;
149 }
150 }
151 }
152
153 // Remove obsolete index entries
154 $pageword_idx = $this->getIndexKey('pageword', '', $pid);
155 if ($pageword_idx !== '') {
156 $oldwords = explode(':',$pageword_idx);
157 $delwords = array_diff($oldwords, $pagewords);
158 $upwords = array();
159 foreach ($delwords as $word) {
160 if ($word != '') {
161 list($wlen,$wid) = explode('*', $word);
162 $wid = (int)$wid;
163 $upwords[$wlen][] = $wid;
164 }
165 }
166 foreach ($upwords as $wlen => $widx) {
167 $index = $this->getIndex('i', $wlen);
168 foreach ($widx as $wid) {
169 $index[$wid] = $this->updateTuple($index[$wid], $pid, 0);
170 }
171 $this->saveIndex('i', $wlen, $index);
172 }
173 }
174 // Save the reverse index
175 $pageword_idx = join(':', $pagewords);
176 if (!$this->saveIndexKey('pageword', '', $pid, $pageword_idx)) {
177 $this->unlock();
178 return false;
179 }
180
181 $this->unlock();
182 return true;
183 }
184
185 /**
186 * Split the words in a page and add them to the index.
187 *
188 * @param string $text content of the page
189 * @return array list of word IDs and number of times used
190 * @author Andreas Gohr <[email protected]>
191 * @author Christopher Smith <[email protected]>
192 * @author Tom N Harris <[email protected]>
193 */
194 protected function getPageWords($text) {
195 global $conf;
196
197 $tokens = $this->tokenizer($text);
198 $tokens = array_count_values($tokens); // count the frequency of each token
199
200 $words = array();
201 foreach ($tokens as $w=>$c) {
202 $l = wordlen($w);
203 if (isset($words[$l])){
204 $words[$l][$w] = $c + (isset($words[$l][$w]) ? $words[$l][$w] : 0);
205 }else{
206 $words[$l] = array($w => $c);
207 }
208 }
209
210 // arrive here with $words = array(wordlen => array(word => frequency))
211 $word_idx_modified = false;
212 $index = array(); //resulting index
213 foreach (array_keys($words) as $wlen) {
214 $word_idx = $this->getIndex('w', $wlen);
215 foreach ($words[$wlen] as $word => $freq) {
216 $wid = array_search($word, $word_idx);
217 if ($wid === false) {
218 $wid = count($word_idx);
219 $word_idx[] = $word;
220 $word_idx_modified = true;
221 }
222 if (!isset($index[$wlen]))
223 $index[$wlen] = array();
224 $index[$wlen][$wid] = $freq;
225 }
226 // save back the word index
227 if ($word_idx_modified && !$this->saveIndex('w', $wlen, $word_idx))
228 return false;
229 }
230
231 return $index;
232 }
233
234 /**
235 * Add/update keys to/of the metadata index.
236 *
237 * Adding new keys does not remove other keys for the page.
238 * An empty value will erase the key.
239 * The $key parameter can be an array to add multiple keys. $value will
240 * not be used if $key is an array.
241 *
242 * @param string $page a page name
243 * @param mixed $key a key string or array of key=>value pairs
244 * @param mixed $value the value or list of values
245 * @return boolean the function completed successfully
246 * @author Tom N Harris <[email protected]>
247 * @author Michael Hamann <[email protected]>
248 */
249 public function addMetaKeys($page, $key, $value=null) {
250 if (!is_array($key)) {
251 $key = array($key => $value);
252 } elseif (!is_null($value)) {
253 // $key is array, but $value is not null
254 trigger_error("array passed to addMetaKeys but value is not null", E_USER_WARNING);
255 }
256
257 if (!$this->lock())
258 return "locked";
259
260 // load known documents
261 $pid = $this->addIndexKey('page', '', $page);
262 if ($pid === false) {
263 $this->unlock();
264 return false;
265 }
266
267 // Special handling for titles so the index file is simpler
268 if (array_key_exists('title', $key)) {
269 $value = $key['title'];
270 if (is_array($value))
271 $value = $value[0];
272 $this->saveIndexKey('title', '', $pid, $value);
273 unset($key['title']);
274 }
275
276 foreach ($key as $name => $values) {
277 $metaname = idx_cleanName($name);
278 $this->addIndexKey('metadata', '', $metaname);
279 $metaidx = $this->getIndex($metaname.'_i', '');
280 $metawords = $this->getIndex($metaname.'_w', '');
281 $addwords = false;
282
283 if (!is_array($values)) $values = array($values);
284
285 $val_idx = $this->getIndexKey($metaname.'_p', '', $pid);
286 if ($val_idx != '') {
287 $val_idx = explode(':', $val_idx);
288 // -1 means remove, 0 keep, 1 add
289 $val_idx = array_combine($val_idx, array_fill(0, count($val_idx), -1));
290 } else {
291 $val_idx = array();
292 }
293
294
295 foreach ($values as $val) {
296 $val = (string)$val;
297 if ($val !== "") {
298 $id = array_search($val, $metawords);
299 if ($id === false) {
300 $id = count($metawords);
301 $metawords[$id] = $val;
302 $addwords = true;
303 }
304 // test if value is already in the index
305 if (isset($val_idx[$id]) && $val_idx[$id] <= 0)
306 $val_idx[$id] = 0;
307 else // else add it
308 $val_idx[$id] = 1;
309 }
310 }
311
312 if ($addwords)
313 $this->saveIndex($metaname.'_w', '', $metawords);
314 $vals_changed = false;
315 foreach ($val_idx as $id => $action) {
316 if ($action == -1) {
317 $metaidx[$id] = $this->updateTuple($metaidx[$id], $pid, 0);
318 $vals_changed = true;
319 unset($val_idx[$id]);
320 } elseif ($action == 1) {
321 $metaidx[$id] = $this->updateTuple($metaidx[$id], $pid, 1);
322 $vals_changed = true;
323 }
324 }
325
326 if ($vals_changed) {
327 $this->saveIndex($metaname.'_i', '', $metaidx);
328 $val_idx = implode(':', array_keys($val_idx));
329 $this->saveIndexKey($metaname.'_p', '', $pid, $val_idx);
330 }
331
332 unset($metaidx);
333 unset($metawords);
334 }
335
336 $this->unlock();
337 return true;
338 }
339
340 /**
341 * Remove a page from the index
342 *
343 * Erases entries in all known indexes.
344 *
345 * @param string $page a page name
346 * @return boolean the function completed successfully
347 * @author Tom N Harris <[email protected]>
348 */
349 public function deletePage($page) {
350 if (!$this->lock())
351 return "locked";
352
353 // load known documents
354 $pid = $this->getIndexKey('page', '', $page);
355 if ($pid === false) {
356 $this->unlock();
357 return false;
358 }
359
360 // Remove obsolete index entries
361 $pageword_idx = $this->getIndexKey('pageword', '', $pid);
362 if ($pageword_idx !== '') {
363 $delwords = explode(':',$pageword_idx);
364 $upwords = array();
365 foreach ($delwords as $word) {
366 if ($word != '') {
367 list($wlen,$wid) = explode('*', $word);
368 $wid = (int)$wid;
369 $upwords[$wlen][] = $wid;
370 }
371 }
372 foreach ($upwords as $wlen => $widx) {
373 $index = $this->getIndex('i', $wlen);
374 foreach ($widx as $wid) {
375 $index[$wid] = $this->updateTuple($index[$wid], $pid, 0);
376 }
377 $this->saveIndex('i', $wlen, $index);
378 }
379 }
380 // Save the reverse index
381 if (!$this->saveIndexKey('pageword', '', $pid, "")) {
382 $this->unlock();
383 return false;
384 }
385
386 $this->saveIndexKey('title', '', $pid, "");
387 $keyidx = $this->getIndex('metadata', '');
388 foreach ($keyidx as $metaname) {
389 $val_idx = explode(':', $this->getIndexKey($metaname.'_p', '', $pid));
390 $meta_idx = $this->getIndex($metaname.'_i', '');
391 foreach ($val_idx as $id) {
392 $meta_idx[$id] = $this->updateTuple($meta_idx[$id], $pid, 0);
393 }
394 $this->saveIndex($metaname.'_i', '', $meta_idx);
395 $this->saveIndexKey($metaname.'_p', '', $pid, '');
396 }
397
398 $this->unlock();
399 return true;
400 }
401
402 /**
403 * Split the text into words for fulltext search
404 *
405 * TODO: does this also need &$stopwords ?
406 *
407 * @triggers INDEXER_TEXT_PREPARE
408 * This event allows plugins to modify the text before it gets tokenized.
409 * Plugins intercepting this event should also intercept INDEX_VERSION_GET
410 *
411 * @param string $text plain text
412 * @param boolean $wc are wildcards allowed?
413 * @return array list of words in the text
414 * @author Tom N Harris <[email protected]>
415 * @author Andreas Gohr <[email protected]>
416 */
417 public function tokenizer($text, $wc=false) {
418 global $conf;
419 $words = array();
420 $wc = ($wc) ? '' : '\*';
421 $stopwords =& idx_get_stopwords();
422
423 // prepare the text to be tokenized
424 $evt = new Doku_Event('INDEXER_TEXT_PREPARE', $text);
425 if ($evt->advise_before(true)) {
426 if (preg_match('/[^0-9A-Za-z ]/u', $text)) {
427 // handle asian chars as single words (may fail on older PHP version)
428 $asia = @preg_replace('/('.IDX_ASIAN.')/u', ' \1 ', $text);
429 if (!is_null($asia)) $text = $asia; // recover from regexp falure
430 }
431 }
432 $evt->advise_after();
433 unset($evt);
434
435 $text = strtr($text,
436 array(
437 "\r" => ' ',
438 "\n" => ' ',
439 "\t" => ' ',
440 "\xC2\xAD" => '', //soft-hyphen
441 )
442 );
443 if (preg_match('/[^0-9A-Za-z ]/u', $text))
444 $text = utf8_stripspecials($text, ' ', '\._\-:'.$wc);
445
446 $wordlist = explode(' ', $text);
447 foreach ($wordlist as $i => $word) {
448 $wordlist[$i] = (preg_match('/[^0-9A-Za-z]/u', $word)) ?
449 utf8_strtolower($word) : strtolower($word);
450 }
451
452 foreach ($wordlist as $i => $word) {
453 if ((!is_numeric($word) && strlen($word) < IDX_MINWORDLENGTH)
454 || array_search($word, $stopwords) !== false)
455 unset($wordlist[$i]);
456 }
457 return array_values($wordlist);
458 }
459
460 /**
461 * Find pages in the fulltext index containing the words,
462 *
463 * The search words must be pre-tokenized, meaning only letters and
464 * numbers with an optional wildcard
465 *
466 * The returned array will have the original tokens as key. The values
467 * in the returned list is an array with the page names as keys and the
468 * number of times that token appears on the page as value.
469 *
470 * @param arrayref $tokens list of words to search for
471 * @return array list of page names with usage counts
472 * @author Tom N Harris <[email protected]>
473 * @author Andreas Gohr <[email protected]>
474 */
475 public function lookup(&$tokens) {
476 $result = array();
477 $wids = $this->getIndexWords($tokens, $result);
478 if (empty($wids)) return array();
479 // load known words and documents
480 $page_idx = $this->getIndex('page', '');
481 $docs = array();
482 foreach (array_keys($wids) as $wlen) {
483 $wids[$wlen] = array_unique($wids[$wlen]);
484 $index = $this->getIndex('i', $wlen);
485 foreach($wids[$wlen] as $ixid) {
486 if ($ixid < count($index))
487 $docs["$wlen*$ixid"] = $this->parseTuples($page_idx, $index[$ixid]);
488 }
489 }
490 // merge found pages into final result array
491 $final = array();
492 foreach ($result as $word => $res) {
493 $final[$word] = array();
494 foreach ($res as $wid) {
495 // handle the case when ($ixid < count($index)) has been false
496 // and thus $docs[$wid] hasn't been set.
497 if (!isset($docs[$wid])) continue;
498 $hits = &$docs[$wid];
499 foreach ($hits as $hitkey => $hitcnt) {
500 // make sure the document still exists
501 if (!page_exists($hitkey, '', false)) continue;
502 if (!isset($final[$word][$hitkey]))
503 $final[$word][$hitkey] = $hitcnt;
504 else
505 $final[$word][$hitkey] += $hitcnt;
506 }
507 }
508 }
509 return $final;
510 }
511
512 /**
513 * Find pages containing a metadata key.
514 *
515 * The metadata values are compared as case-sensitive strings. Pass a
516 * callback function that returns true or false to use a different
517 * comparison function. The function will be called with the $value being
518 * searched for as the first argument, and the word in the index as the
519 * second argument. The function preg_match can be used directly if the
520 * values are regexes.
521 *
522 * @param string $key name of the metadata key to look for
523 * @param string $value search term to look for, must be a string or array of strings
524 * @param callback $func comparison function
525 * @return array lists with page names, keys are query values if $value is array
526 * @author Tom N Harris <[email protected]>
527 * @author Michael Hamann <[email protected]>
528 */
529 public function lookupKey($key, &$value, $func=null) {
530 if (!is_array($value))
531 $value_array = array($value);
532 else
533 $value_array =& $value;
534
535 // the matching ids for the provided value(s)
536 $value_ids = array();
537
538 $metaname = idx_cleanName($key);
539
540 // get all words in order to search the matching ids
541 if ($key == 'title') {
542 $words = $this->getIndex('title', '');
543 } else {
544 $words = $this->getIndex($metaname.'_w', '');
545 }
546
547 if (!is_null($func)) {
548 foreach ($value_array as $val) {
549 foreach ($words as $i => $word) {
550 if (call_user_func_array($func, array($val, $word)))
551 $value_ids[$i][] = $val;
552 }
553 }
554 } else {
555 foreach ($value_array as $val) {
556 $xval = $val;
557 $caret = '^';
558 $dollar = '$';
559 // check for wildcards
560 if (substr($xval, 0, 1) == '*') {
561 $xval = substr($xval, 1);
562 $caret = '';
563 }
564 if (substr($xval, -1, 1) == '*') {
565 $xval = substr($xval, 0, -1);
566 $dollar = '';
567 }
568 if (!$caret || !$dollar) {
569 $re = $caret.preg_quote($xval, '/').$dollar;
570 foreach(array_keys(preg_grep('/'.$re.'/', $words)) as $i)
571 $value_ids[$i][] = $val;
572 } else {
573 if (($i = array_search($val, $words)) !== false)
574 $value_ids[$i][] = $val;
575 }
576 }
577 }
578
579 unset($words); // free the used memory
580
581 // initialize the result so it won't be null
582 $result = array();
583 foreach ($value_array as $val) {
584 $result[$val] = array();
585 }
586
587 $page_idx = $this->getIndex('page', '');
588
589 // Special handling for titles
590 if ($key == 'title') {
591 foreach ($value_ids as $pid => $val_list) {
592 $page = $page_idx[$pid];
593 foreach ($val_list as $val) {
594 $result[$val][] = $page;
595 }
596 }
597 } else {
598 // load all lines and pages so the used lines can be taken and matched with the pages
599 $lines = $this->getIndex($metaname.'_i', '');
600
601 foreach ($value_ids as $value_id => $val_list) {
602 // parse the tuples of the form page_id*1:page2_id*1 and so on, return value
603 // is an array with page_id => 1, page2_id => 1 etc. so take the keys only
604 $pages = array_keys($this->parseTuples($page_idx, $lines[$value_id]));
605 foreach ($val_list as $val) {
606 $result[$val] = array_merge($result[$val], $pages);
607 }
608 }
609 }
610 if (!is_array($value)) $result = $result[$value];
611 return $result;
612 }
613
614 /**
615 * Find the index ID of each search term.
616 *
617 * The query terms should only contain valid characters, with a '*' at
618 * either the beginning or end of the word (or both).
619 * The $result parameter can be used to merge the index locations with
620 * the appropriate query term.
621 *
622 * @param arrayref $words The query terms.
623 * @param arrayref $result Set to word => array("length*id" ...)
624 * @return array Set to length => array(id ...)
625 * @author Tom N Harris <[email protected]>
626 */
627 protected function getIndexWords(&$words, &$result) {
628 $tokens = array();
629 $tokenlength = array();
630 $tokenwild = array();
631 foreach ($words as $word) {
632 $result[$word] = array();
633 $caret = '^';
634 $dollar = '$';
635 $xword = $word;
636 $wlen = wordlen($word);
637
638 // check for wildcards
639 if (substr($xword, 0, 1) == '*') {
640 $xword = substr($xword, 1);
641 $caret = '';
642 $wlen -= 1;
643 }
644 if (substr($xword, -1, 1) == '*') {
645 $xword = substr($xword, 0, -1);
646 $dollar = '';
647 $wlen -= 1;
648 }
649 if ($wlen < IDX_MINWORDLENGTH && $caret && $dollar && !is_numeric($xword))
650 continue;
651 if (!isset($tokens[$xword]))
652 $tokenlength[$wlen][] = $xword;
653 if (!$caret || !$dollar) {
654 $re = $caret.preg_quote($xword, '/').$dollar;
655 $tokens[$xword][] = array($word, '/'.$re.'/');
656 if (!isset($tokenwild[$xword]))
657 $tokenwild[$xword] = $wlen;
658 } else {
659 $tokens[$xword][] = array($word, null);
660 }
661 }
662 asort($tokenwild);
663 // $tokens = array( base word => array( [ query term , regexp ] ... ) ... )
664 // $tokenlength = array( base word length => base word ... )
665 // $tokenwild = array( base word => base word length ... )
666 $length_filter = empty($tokenwild) ? $tokenlength : min(array_keys($tokenlength));
667 $indexes_known = $this->indexLengths($length_filter);
668 if (!empty($tokenwild)) sort($indexes_known);
669 // get word IDs
670 $wids = array();
671 foreach ($indexes_known as $ixlen) {
672 $word_idx = $this->getIndex('w', $ixlen);
673 // handle exact search
674 if (isset($tokenlength[$ixlen])) {
675 foreach ($tokenlength[$ixlen] as $xword) {
676 $wid = array_search($xword, $word_idx);
677 if ($wid !== false) {
678 $wids[$ixlen][] = $wid;
679 foreach ($tokens[$xword] as $w)
680 $result[$w[0]][] = "$ixlen*$wid";
681 }
682 }
683 }
684 // handle wildcard search
685 foreach ($tokenwild as $xword => $wlen) {
686 if ($wlen >= $ixlen) break;
687 foreach ($tokens[$xword] as $w) {
688 if (is_null($w[1])) continue;
689 foreach(array_keys(preg_grep($w[1], $word_idx)) as $wid) {
690 $wids[$ixlen][] = $wid;
691 $result[$w[0]][] = "$ixlen*$wid";
692 }
693 }
694 }
695 }
696 return $wids;
697 }
698
699 /**
700 * Return a list of all pages
701 * Warning: pages may not exist!
702 *
703 * @param string $key list only pages containing the metadata key (optional)
704 * @return array list of page names
705 * @author Tom N Harris <[email protected]>
706 */
707 public function getPages($key=null) {
708 $page_idx = $this->getIndex('page', '');
709 if (is_null($key)) return $page_idx;
710
711 $metaname = idx_cleanName($key);
712
713 // Special handling for titles
714 if ($key == 'title') {
715 $title_idx = $this->getIndex('title', '');
716 array_splice($page_idx, count($title_idx));
717 foreach ($title_idx as $i => $title)
718 if ($title === "") unset($page_idx[$i]);
719 return array_values($page_idx);
720 }
721
722 $pages = array();
723 $lines = $this->getIndex($metaname.'_i', '');
724 foreach ($lines as $line) {
725 $pages = array_merge($pages, $this->parseTuples($page_idx, $line));
726 }
727 return array_keys($pages);
728 }
729
730 /**
731 * Return a list of words sorted by number of times used
732 *
733 * @param int $min bottom frequency threshold
734 * @param int $max upper frequency limit. No limit if $max<$min
735 * @param int $length minimum length of words to count
736 * @param string $key metadata key to list. Uses the fulltext index if not given
737 * @return array list of words as the keys and frequency as values
738 * @author Tom N Harris <[email protected]>
739 */
740 public function histogram($min=1, $max=0, $minlen=3, $key=null) {
741 if ($min < 1)
742 $min = 1;
743 if ($max < $min)
744 $max = 0;
745
746 $result = array();
747
748 if ($key == 'title') {
749 $index = $this->getIndex('title', '');
750 $index = array_count_values($index);
751 foreach ($index as $val => $cnt) {
752 if ($cnt >= $min && (!$max || $cnt <= $max) && strlen($val) >= $minlen)
753 $result[$val] = $cnt;
754 }
755 }
756 elseif (!is_null($key)) {
757 $metaname = idx_cleanName($key);
758 $index = $this->getIndex($metaname.'_i', '');
759 $val_idx = array();
760 foreach ($index as $wid => $line) {
761 $freq = $this->countTuples($line);
762 if ($freq >= $min && (!$max || $freq <= $max) && strlen($val) >= $minlen)
763 $val_idx[$wid] = $freq;
764 }
765 if (!empty($val_idx)) {
766 $words = $this->getIndex($metaname.'_w', '');
767 foreach ($val_idx as $wid => $freq)
768 $result[$words[$wid]] = $freq;
769 }
770 }
771 else {
772 $lengths = idx_listIndexLengths();
773 foreach ($lengths as $length) {
774 if ($length < $minlen) continue;
775 $index = $this->getIndex('i', $length);
776 $words = null;
777 foreach ($index as $wid => $line) {
778 $freq = $this->countTuples($line);
779 if ($freq >= $min && (!$max || $freq <= $max)) {
780 if ($words === null)
781 $words = $this->getIndex('w', $length);
782 $result[$words[$wid]] = $freq;
783 }
784 }
785 }
786 }
787
788 arsort($result);
789 return $result;
790 }
791
792 /**
793 * Lock the indexer.
794 *
795 * @author Tom N Harris <[email protected]>
796 */
797 protected function lock() {
798 global $conf;
799 $status = true;
800 $run = 0;
801 $lock = $conf['lockdir'].'/_indexer.lock';
802 while (!@mkdir($lock, $conf['dmode'])) {
803 usleep(50);
804 if(is_dir($lock) && time()-@filemtime($lock) > 60*5){
805 // looks like a stale lock - remove it
806 if (!@rmdir($lock)) {
807 $status = "removing the stale lock failed";
808 return false;
809 } else {
810 $status = "stale lock removed";
811 }
812 }elseif($run++ == 1000){
813 // we waited 5 seconds for that lock
814 return false;
815 }
816 }
817 if ($conf['dperm'])
818 chmod($lock, $conf['dperm']);
819 return $status;
820 }
821
822 /**
823 * Release the indexer lock.
824 *
825 * @author Tom N Harris <[email protected]>
826 */
827 protected function unlock() {
828 global $conf;
829 @rmdir($conf['lockdir'].'/_indexer.lock');
830 return true;
831 }
832
833 /**
834 * Retrieve the entire index.
835 *
836 * The $suffix argument is for an index that is split into
837 * multiple parts. Different index files should use different
838 * base names.
839 *
840 * @param string $idx name of the index
841 * @param string $suffix subpart identifier
842 * @return array list of lines without CR or LF
843 * @author Tom N Harris <[email protected]>
844 */
845 protected function getIndex($idx, $suffix) {
846 global $conf;
847 $fn = $conf['indexdir'].'/'.$idx.$suffix.'.idx';
848 if (!@file_exists($fn)) return array();
849 return file($fn, FILE_IGNORE_NEW_LINES);
850 }
851
852 /**
853 * Replace the contents of the index with an array.
854 *
855 * @param string $idx name of the index
856 * @param string $suffix subpart identifier
857 * @param arrayref $linex list of lines without LF
858 * @author Tom N Harris <[email protected]>
859 */
860 protected function saveIndex($idx, $suffix, &$lines) {
861 global $conf;
862 $fn = $conf['indexdir'].'/'.$idx.$suffix;
863 $fh = @fopen($fn.'.tmp', 'w');
864 if (!$fh) return false;
865 fwrite($fh, join("\n", $lines));
866 if (!empty($lines))
867 fwrite($fh, "\n");
868 fclose($fh);
869 if (isset($conf['fperm']))
870 chmod($fn.'.tmp', $conf['fperm']);
871 io_rename($fn.'.tmp', $fn.'.idx');
872 if ($suffix !== '')
873 $this->cacheIndexDir($idx, $suffix, empty($lines));
874 return true;
875 }
876
877 /**
878 * Retrieve a line from the index.
879 *
880 * @param string $idx name of the index
881 * @param string $suffix subpart identifier
882 * @param int $id the line number
883 * @return string a line with trailing whitespace removed
884 * @author Tom N Harris <[email protected]>
885 */
886 protected function getIndexKey($idx, $suffix, $id) {
887 global $conf;
888 $fn = $conf['indexdir'].'/'.$idx.$suffix.'.idx';
889 if (!@file_exists($fn)) return '';
890 $fh = @fopen($fn, 'r');
891 if (!$fh) return '';
892 $ln = -1;
893 while (($line = fgets($fh)) !== false) {
894 if (++$ln == $id) break;
895 }
896 fclose($fh);
897 return rtrim((string)$line);
898 }
899
900 /**
901 * Write a line into the index.
902 *
903 * @param string $idx name of the index
904 * @param string $suffix subpart identifier
905 * @param int $id the line number
906 * @param string $line line to write
907 * @author Tom N Harris <[email protected]>
908 */
909 protected function saveIndexKey($idx, $suffix, $id, $line) {
910 global $conf;
911 if (substr($line, -1) != "\n")
912 $line .= "\n";
913 $fn = $conf['indexdir'].'/'.$idx.$suffix;
914 $fh = @fopen($fn.'.tmp', 'w');
915 if (!$fh) return false;
916 $ih = @fopen($fn.'.idx', 'r');
917 if ($ih) {
918 $ln = -1;
919 while (($curline = fgets($ih)) !== false) {
920 fwrite($fh, (++$ln == $id) ? $line : $curline);
921 }
922 if ($id > $ln) {
923 while ($id > ++$ln)
924 fwrite($fh, "\n");
925 fwrite($fh, $line);
926 }
927 fclose($ih);
928 } else {
929 $ln = -1;
930 while ($id > ++$ln)
931 fwrite($fh, "\n");
932 fwrite($fh, $line);
933 }
934 fclose($fh);
935 if (isset($conf['fperm']))
936 chmod($fn.'.tmp', $conf['fperm']);
937 io_rename($fn.'.tmp', $fn.'.idx');
938 if ($suffix !== '')
939 $this->cacheIndexDir($idx, $suffix);
940 return true;
941 }
942
943 /**
944 * Retrieve or insert a value in the index.
945 *
946 * @param string $idx name of the index
947 * @param string $suffix subpart identifier
948 * @param string $value line to find in the index
949 * @return int line number of the value in the index
950 * @author Tom N Harris <[email protected]>
951 */
952 protected function addIndexKey($idx, $suffix, $value) {
953 $index = $this->getIndex($idx, $suffix);
954 $id = array_search($value, $index);
955 if ($id === false) {
956 $id = count($index);
957 $index[$id] = $value;
958 if (!$this->saveIndex($idx, $suffix, $index)) {
959 trigger_error("Failed to write $idx index", E_USER_ERROR);
960 return false;
961 }
962 }
963 return $id;
964 }
965
966 protected function cacheIndexDir($idx, $suffix, $delete=false) {
967 global $conf;
968 if ($idx == 'i')
969 $cachename = $conf['indexdir'].'/lengths';
970 else
971 $cachename = $conf['indexdir'].'/'.$idx.'lengths';
972 $lengths = @file($cachename.'.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
973 if ($lengths === false) $lengths = array();
974 $old = array_search((string)$suffix, $lengths);
975 if (empty($lines)) {
976 if ($old === false) return;
977 unset($lengths[$old]);
978 } else {
979 if ($old !== false) return;
980 $lengths[] = $suffix;
981 sort($lengths);
982 }
983 $fh = @fopen($cachename.'.tmp', 'w');
984 if (!$fh) {
985 trigger_error("Failed to write index cache", E_USER_ERROR);
986 return;
987 }
988 @fwrite($fh, implode("\n", $lengths));
989 @fclose($fh);
990 if (isset($conf['fperm']))
991 chmod($cachename.'.tmp', $conf['fperm']);
992 io_rename($cachename.'.tmp', $cachename.'.idx');
993 }
994
995 /**
996 * Get the list of lengths indexed in the wiki.
997 *
998 * Read the index directory or a cache file and returns
999 * a sorted array of lengths of the words used in the wiki.
1000 *
1001 * @author YoBoY <[email protected]>
1002 */
1003 protected function listIndexLengths() {
1004 global $conf;
1005 $cachename = $conf['indexdir'].'/lengths';
1006 clearstatcache();
1007 if (@file_exists($cachename.'.idx')) {
1008 $lengths = @file($cachename.'.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
1009 if ($lengths !== false) {
1010 $idx = array();
1011 foreach ($lengths as $length)
1012 $idx[] = (int)$length;
1013 return $idx;
1014 }
1015 }
1016
1017 $dir = @opendir($conf['indexdir']);
1018 if ($dir === false)
1019 return array();
1020 $lengths[] = array();
1021 while (($f = readdir($dir)) !== false) {
1022 if (substr($f, 0, 1) == 'i' && substr($f, -4) == '.idx') {
1023 $i = substr($f, 1, -4);
1024 if (is_numeric($i))
1025 $lengths[] = (int)$i;
1026 }
1027 }
1028 closedir($dir);
1029 sort($lengths);
1030 // save this in a file
1031 $fh = @fopen($cachename.'.tmp', 'w');
1032 if (!$fh) {
1033 trigger_error("Failed to write index cache", E_USER_ERROR);
1034 return;
1035 }
1036 @fwrite($fh, implode("\n", $lengths));
1037 @fclose($fh);
1038 if (isset($conf['fperm']))
1039 chmod($cachename.'.tmp', $conf['fperm']);
1040 io_rename($cachename.'.tmp', $cachename.'.idx');
1041
1042 return $lengths;
1043 }
1044
1045 /**
1046 * Get the word lengths that have been indexed.
1047 *
1048 * Reads the index directory and returns an array of lengths
1049 * that there are indices for.
1050 *
1051 * @author YoBoY <[email protected]>
1052 */
1053 protected function indexLengths($filter) {
1054 global $conf;
1055 $idx = array();
1056 if (is_array($filter)) {
1057 // testing if index files exist only
1058 $path = $conf['indexdir']."/i";
1059 foreach ($filter as $key => $value) {
1060 if (@file_exists($path.$key.'.idx'))
1061 $idx[] = $key;
1062 }
1063 } else {
1064 $lengths = idx_listIndexLengths();
1065 foreach ($lengths as $key => $length) {
1066 // keep all the values equal or superior
1067 if ((int)$length >= (int)$filter)
1068 $idx[] = $length;
1069 }
1070 }
1071 return $idx;
1072 }
1073
1074 /**
1075 * Insert or replace a tuple in a line.
1076 *
1077 * @author Tom N Harris <[email protected]>
1078 */
1079 protected function updateTuple($line, $id, $count) {
1080 $newLine = $line;
1081 if ($newLine !== '')
1082 $newLine = preg_replace('/(^|:)'.preg_quote($id,'/').'\*\d*/', '', $newLine);
1083 $newLine = trim($newLine, ':');
1084 if ($count) {
1085 if (strlen($newLine) > 0)
1086 return "$id*$count:".$newLine;
1087 else
1088 return "$id*$count".$newLine;
1089 }
1090 return $newLine;
1091 }
1092
1093 /**
1094 * Split a line into an array of tuples.
1095 *
1096 * @author Tom N Harris <[email protected]>
1097 * @author Andreas Gohr <[email protected]>
1098 */
1099 protected function parseTuples(&$keys, $line) {
1100 $result = array();
1101 if ($line == '') return $result;
1102 $parts = explode(':', $line);
1103 foreach ($parts as $tuple) {
1104 if ($tuple === '') continue;
1105 list($key, $cnt) = explode('*', $tuple);
1106 if (!$cnt) continue;
1107 $key = $keys[$key];
1108 if (!$key) continue;
1109 $result[$key] = $cnt;
1110 }
1111 return $result;
1112 }
1113
1114 /**
1115 * Sum the counts in a list of tuples.
1116 *
1117 * @author Tom N Harris <[email protected]>
1118 */
1119 protected function countTuples($line) {
1120 $freq = 0;
1121 $parts = explode(':', $line);
1122 foreach ($parts as $tuple) {
1123 if ($tuple === '') continue;
1124 list($pid, $cnt) = explode('*', $tuple);
1125 $freq += (int)$cnt;
1126 }
1127 return $freq;
1128 }
1129}
1130
1131/**
1132 * Create an instance of the indexer.
1133 *
1134 * @return object a Doku_Indexer
1135 * @author Tom N Harris <[email protected]>
1136 */
1137function idx_get_indexer() {
1138 static $Indexer = null;
1139 if (is_null($Indexer)) {
1140 $Indexer = new Doku_Indexer();
1141 }
1142 return $Indexer;
1143}
1144
1145/**
1146 * Returns words that will be ignored.
1147 *
1148 * @return array list of stop words
1149 * @author Tom N Harris <[email protected]>
1150 */
1151function & idx_get_stopwords() {
1152 static $stopwords = null;
1153 if (is_null($stopwords)) {
1154 global $conf;
1155 $swfile = DOKU_INC.'inc/lang/'.$conf['lang'].'/stopwords.txt';
1156 if(@file_exists($swfile)){
1157 $stopwords = file($swfile, FILE_IGNORE_NEW_LINES);
1158 }else{
1159 $stopwords = array();
1160 }
1161 }
1162 return $stopwords;
1163}
1164
1165/**
1166 * Adds/updates the search index for the given page
1167 *
1168 * Locking is handled internally.
1169 *
1170 * @param string $page name of the page to index
1171 * @param boolean $verbose print status messages
1172 * @param boolean $force force reindexing even when the index is up to date
1173 * @return boolean the function completed successfully
1174 * @author Tom N Harris <[email protected]>
1175 */
1176function idx_addPage($page, $verbose=false, $force=false) {
1177 // check if indexing needed
1178 $idxtag = metaFN($page,'.indexed');
1179 if(!$force && @file_exists($idxtag)){
1180 if(trim(io_readFile($idxtag)) == idx_get_version()){
1181 $last = @filemtime($idxtag);
1182 if($last > @filemtime(wikiFN($page))){
1183 if ($verbose) print("Indexer: index for $page up to date".DOKU_LF);
1184 return false;
1185 }
1186 }
1187 }
1188
1189 if (!page_exists($page)) {
1190 if (!@file_exists($idxtag)) {
1191 if ($verbose) print("Indexer: $page does not exist, ignoring".DOKU_LF);
1192 return false;
1193 }
1194 $Indexer = idx_get_indexer();
1195 $result = $Indexer->deletePage($page);
1196 if ($result === "locked") {
1197 if ($verbose) print("Indexer: locked".DOKU_LF);
1198 return false;
1199 }
1200 @unlink($idxtag);
1201 return $result;
1202 }
1203 $indexenabled = p_get_metadata($page, 'internal index', METADATA_RENDER_UNLIMITED);
1204 if ($indexenabled === false) {
1205 $result = false;
1206 if (@file_exists($idxtag)) {
1207 $Indexer = idx_get_indexer();
1208 $result = $Indexer->deletePage($page);
1209 if ($result === "locked") {
1210 if ($verbose) print("Indexer: locked".DOKU_LF);
1211 return false;
1212 }
1213 @unlink($idxtag);
1214 }
1215 if ($verbose) print("Indexer: index disabled for $page".DOKU_LF);
1216 return $result;
1217 }
1218
1219 $body = '';
1220 $metadata = array();
1221 $metadata['title'] = p_get_metadata($page, 'title', METADATA_RENDER_UNLIMITED);
1222 if (($references = p_get_metadata($page, 'relation references', METADATA_RENDER_UNLIMITED)) !== null)
1223 $metadata['relation_references'] = array_keys($references);
1224 else
1225 $metadata['relation_references'] = array();
1226 $data = compact('page', 'body', 'metadata');
1227 $evt = new Doku_Event('INDEXER_PAGE_ADD', $data);
1228 if ($evt->advise_before()) $data['body'] = $data['body'] . " " . rawWiki($page);
1229 $evt->advise_after();
1230 unset($evt);
1231 extract($data);
1232
1233 $Indexer = idx_get_indexer();
1234 $result = $Indexer->addPageWords($page, $body);
1235 if ($result === "locked") {
1236 if ($verbose) print("Indexer: locked".DOKU_LF);
1237 return false;
1238 }
1239
1240 if ($result) {
1241 $result = $Indexer->addMetaKeys($page, $metadata);
1242 if ($result === "locked") {
1243 if ($verbose) print("Indexer: locked".DOKU_LF);
1244 return false;
1245 }
1246 }
1247
1248 if ($result)
1249 io_saveFile(metaFN($page,'.indexed'), idx_get_version());
1250 if ($verbose) {
1251 print("Indexer: finished".DOKU_LF);
1252 return true;
1253 }
1254 return $result;
1255}
1256
1257/**
1258 * Find tokens in the fulltext index
1259 *
1260 * Takes an array of words and will return a list of matching
1261 * pages for each one.
1262 *
1263 * Important: No ACL checking is done here! All results are
1264 * returned, regardless of permissions
1265 *
1266 * @param arrayref $words list of words to search for
1267 * @return array list of pages found, associated with the search terms
1268 */
1269function idx_lookup(&$words) {
1270 $Indexer = idx_get_indexer();
1271 return $Indexer->lookup($words);
1272}
1273
1274/**
1275 * Split a string into tokens
1276 *
1277 */
1278function idx_tokenizer($string, $wc=false) {
1279 $Indexer = idx_get_indexer();
1280 return $Indexer->tokenizer($string, $wc);
1281}
1282
1283/* For compatibility */
1284
1285/**
1286 * Read the list of words in an index (if it exists).
1287 *
1288 * @author Tom N Harris <[email protected]>
1289 */
1290function idx_getIndex($idx, $suffix) {
1291 global $conf;
1292 $fn = $conf['indexdir'].'/'.$idx.$suffix.'.idx';
1293 if (!@file_exists($fn)) return array();
1294 return file($fn);
1295}
1296
1297/**
1298 * Get the list of lengths indexed in the wiki.
1299 *
1300 * Read the index directory or a cache file and returns
1301 * a sorted array of lengths of the words used in the wiki.
1302 *
1303 * @author YoBoY <[email protected]>
1304 */
1305function idx_listIndexLengths() {
1306 global $conf;
1307 // testing what we have to do, create a cache file or not.
1308 if ($conf['readdircache'] == 0) {
1309 $docache = false;
1310 } else {
1311 clearstatcache();
1312 if (@file_exists($conf['indexdir'].'/lengths.idx')
1313 && (time() < @filemtime($conf['indexdir'].'/lengths.idx') + $conf['readdircache'])) {
1314 if (($lengths = @file($conf['indexdir'].'/lengths.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES)) !== false) {
1315 $idx = array();
1316 foreach ($lengths as $length) {
1317 $idx[] = (int)$length;
1318 }
1319 return $idx;
1320 }
1321 }
1322 $docache = true;
1323 }
1324
1325 if ($conf['readdircache'] == 0 || $docache) {
1326 $dir = @opendir($conf['indexdir']);
1327 if ($dir === false)
1328 return array();
1329 $idx = array();
1330 while (($f = readdir($dir)) !== false) {
1331 if (substr($f, 0, 1) == 'i' && substr($f, -4) == '.idx') {
1332 $i = substr($f, 1, -4);
1333 if (is_numeric($i))
1334 $idx[] = (int)$i;
1335 }
1336 }
1337 closedir($dir);
1338 sort($idx);
1339 // save this in a file
1340 if ($docache) {
1341 $handle = @fopen($conf['indexdir'].'/lengths.idx', 'w');
1342 @fwrite($handle, implode("\n", $idx));
1343 @fclose($handle);
1344 }
1345 return $idx;
1346 }
1347
1348 return array();
1349}
1350
1351/**
1352 * Get the word lengths that have been indexed.
1353 *
1354 * Reads the index directory and returns an array of lengths
1355 * that there are indices for.
1356 *
1357 * @author YoBoY <[email protected]>
1358 */
1359function idx_indexLengths($filter) {
1360 global $conf;
1361 $idx = array();
1362 if (is_array($filter)) {
1363 // testing if index files exist only
1364 $path = $conf['indexdir']."/i";
1365 foreach ($filter as $key => $value) {
1366 if (@file_exists($path.$key.'.idx'))
1367 $idx[] = $key;
1368 }
1369 } else {
1370 $lengths = idx_listIndexLengths();
1371 foreach ($lengths as $key => $length) {
1372 // keep all the values equal or superior
1373 if ((int)$length >= (int)$filter)
1374 $idx[] = $length;
1375 }
1376 }
1377 return $idx;
1378}
1379
1380/**
1381 * Clean a name of a key for use as a file name.
1382 *
1383 * Romanizes non-latin characters, then strips away anything that's
1384 * not a letter, number, or underscore.
1385 *
1386 * @author Tom N Harris <[email protected]>
1387 */
1388function idx_cleanName($name) {
1389 $name = utf8_romanize(trim((string)$name));
1390 $name = preg_replace('#[ \./\\:-]+#', '_', $name);
1391 $name = preg_replace('/[^A-Za-z0-9_]/', '', $name);
1392 return strtolower($name);
1393}
1394
1395//Setup VIM: ex: et ts=4 :
Note: See TracBrowser for help on using the repository browser.