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