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