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 ']'); 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 int $length minimum length of words to count 711 * @param string $key metadata key to list. Uses the fulltext index if not given 712 * @return array list of words as the keys and frequency as values 713 * @author Tom N Harris <tnharris@whoopdedo.org> 714 */ 715 public function histogram($min=1, $max=0, $minlen=3, $key=null) { 716 if ($min < 1) 717 $min = 1; 718 if ($max < $min) 719 $max = 0; 720 721 $result = array(); 722 723 if ($key == 'title') { 724 $index = $this->_getIndex('title', ''); 725 $index = array_count_values($index); 726 foreach ($index as $val => $cnt) { 727 if ($cnt >= $min && (!$max || $cnt <= $max) && strlen($val) >= $minlen) 728 $result[$val] = $cnt; 729 } 730 } 731 elseif (!is_null($key)) { 732 $metaname = idx_cleanName($key); 733 $index = $this->_getIndex($metaname.'_i', ''); 734 $val_idx = array(); 735 foreach ($index as $wid => $line) { 736 $freq = $this->_countTuples($line); 737 if ($freq >= $min && (!$max || $freq <= $max) && strlen($val) >= $minlen) 738 $val_idx[$wid] = $freq; 739 } 740 if (!empty($val_idx)) { 741 $words = $this->_getIndex($metaname.'_w', ''); 742 foreach ($val_idx as $wid => $freq) 743 $result[$words[$wid]] = $freq; 744 } 745 } 746 else { 747 $lengths = idx_listIndexLengths(); 748 foreach ($lengths as $length) { 749 if ($length < $minlen) continue; 750 $index = $this->_getIndex('i', $length); 751 $words = null; 752 foreach ($index as $wid => $line) { 753 $freq = $this->_countTuples($line); 754 if ($freq >= $min && (!$max || $freq <= $max)) { 755 if ($words === null) 756 $words = $this->_getIndex('w', $length); 757 $result[$words[$wid]] = $freq; 758 } 759 } 760 } 761 } 762 763 arsort($result); 764 return $result; 765 } 766 767 /** 768 * Lock the indexer. 769 * 770 * @author Tom N Harris <tnharris@whoopdedo.org> 771 */ 772 private function _lock() { 773 global $conf; 774 $status = true; 775 $lock = $conf['lockdir'].'/_indexer.lock'; 776 while (!@mkdir($lock, $conf['dmode'])) { 777 usleep(50); 778 if (time() - @filemtime($lock) > 60*5) { 779 // looks like a stale lock, remove it 780 @rmdir($lock); 781 $status = "stale lock removed"; 782 } else { 783 return false; 784 } 785 } 786 if ($conf['dperm']) 787 chmod($lock, $conf['dperm']); 788 return $status; 789 } 790 791 /** 792 * Release the indexer lock. 793 * 794 * @author Tom N Harris <tnharris@whoopdedo.org> 795 */ 796 private function _unlock() { 797 global $conf; 798 @rmdir($conf['lockdir'].'/_indexer.lock'); 799 return true; 800 } 801 802 /** 803 * Retrieve the entire index. 804 * 805 * @author Tom N Harris <tnharris@whoopdedo.org> 806 */ 807 private function _getIndex($idx, $suffix) { 808 global $conf; 809 $fn = $conf['indexdir'].'/'.$idx.$suffix.'.idx'; 810 if (!@file_exists($fn)) return array(); 811 return file($fn, FILE_IGNORE_NEW_LINES); 812 } 813 814 /** 815 * Replace the contents of the index with an array. 816 * 817 * @author Tom N Harris <tnharris@whoopdedo.org> 818 */ 819 private function _saveIndex($idx, $suffix, &$lines) { 820 global $conf; 821 $fn = $conf['indexdir'].'/'.$idx.$suffix; 822 $fh = @fopen($fn.'.tmp', 'w'); 823 if (!$fh) return false; 824 fwrite($fh, join("\n", $lines)); 825 fclose($fh); 826 if (isset($conf['fperm'])) 827 chmod($fn.'.tmp', $conf['fperm']); 828 io_rename($fn.'.tmp', $fn.'.idx'); 829 if ($suffix !== '') 830 $this->_cacheIndexDir($idx, $suffix, empty($lines)); 831 return true; 832 } 833 834 /** 835 * Retrieve a line from the index. 836 * 837 * @author Tom N Harris <tnharris@whoopdedo.org> 838 */ 839 private function _getIndexKey($idx, $suffix, $id) { 840 global $conf; 841 $fn = $conf['indexdir'].'/'.$idx.$suffix.'.idx'; 842 if (!@file_exists($fn)) return ''; 843 $fh = @fopen($fn, 'r'); 844 if (!$fh) return ''; 845 $ln = -1; 846 while (($line = fgets($fh)) !== false) { 847 if (++$ln == $id) break; 848 } 849 fclose($fh); 850 return rtrim((string)$line); 851 } 852 853 /** 854 * Write a line into the index. 855 * 856 * @author Tom N Harris <tnharris@whoopdedo.org> 857 */ 858 private function _saveIndexKey($idx, $suffix, $id, $line) { 859 global $conf; 860 if (substr($line, -1) != "\n") 861 $line .= "\n"; 862 $fn = $conf['indexdir'].'/'.$idx.$suffix; 863 $fh = @fopen($fn.'.tmp', 'w'); 864 if (!fh) return false; 865 $ih = @fopen($fn.'.idx', 'r'); 866 if ($ih) { 867 $ln = -1; 868 while (($curline = fgets($ih)) !== false) { 869 fwrite($fh, (++$ln == $id) ? $line : $curline); 870 } 871 if ($id > $ln) { 872 while ($id > ++$ln) 873 fwrite($fh, "\n"); 874 fwrite($fh, $line); 875 } 876 fclose($ih); 877 } else { 878 $ln = -1; 879 while ($id > ++$ln) 880 fwrite($fh, "\n"); 881 fwrite($fh, $line); 882 } 883 fclose($fh); 884 if (isset($conf['fperm'])) 885 chmod($fn.'.tmp', $conf['fperm']); 886 io_rename($fn.'.tmp', $fn.'.idx'); 887 if ($suffix !== '') 888 $this->_cacheIndexDir($idx, $suffix); 889 return true; 890 } 891 892 /** 893 * Retrieve or insert a value in the index. 894 * 895 * @author Tom N Harris <tnharris@whoopdedo.org> 896 */ 897 private function _addIndexKey($idx, $suffix, $value) { 898 $index = $this->_getIndex($idx, $suffix); 899 $id = array_search($value, $index); 900 if ($id === false) { 901 $id = count($index); 902 $index[$id] = $value; 903 if (!$this->_saveIndex($idx, $suffix, $index)) { 904 trigger_error("Failed to write $idx index", E_USER_ERROR); 905 return false; 906 } 907 } 908 return $id; 909 } 910 911 private function _cacheIndexDir($idx, $suffix, $delete=false) { 912 global $conf; 913 if ($idx == 'i') 914 $cachename = $conf['indexdir'].'/lengths'; 915 else 916 $cachename = $conf['indexdir'].'/'.$idx.'lengths'; 917 $lengths = @file($cachename.'.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES); 918 if ($lengths === false) $lengths = array(); 919 $old = array_search((string)$suffix, $lengths); 920 if (empty($lines)) { 921 if ($old === false) return; 922 unset($lengths[$old]); 923 } else { 924 if ($old !== false) return; 925 $lengths[] = $suffix; 926 sort($lengths); 927 } 928 $fh = @fopen($cachename.'.tmp', 'w'); 929 if (!$fh) { 930 trigger_error("Failed to write index cache", E_USER_ERROR); 931 return; 932 } 933 @fwrite($fh, implode("\n", $lengths)); 934 @fclose($fh); 935 if (isset($conf['fperm'])) 936 chmod($cachename.'.tmp', $conf['fperm']); 937 io_rename($cachename.'.tmp', $cachename.'.idx'); 938 } 939 940 /** 941 * Get the list of lengths indexed in the wiki. 942 * 943 * Read the index directory or a cache file and returns 944 * a sorted array of lengths of the words used in the wiki. 945 * 946 * @author YoBoY <yoboy.leguesh@gmail.com> 947 */ 948 private function _listIndexLengths() { 949 global $conf; 950 $cachename = $conf['indexdir'].'/lengths'; 951 clearstatcache(); 952 if (@file_exists($cachename.'.idx')) { 953 $lengths = @file($cachename.'.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES); 954 if ($lengths !== false) { 955 $idx = array(); 956 foreach ($lengths as $length) 957 $idx[] = (int)$length; 958 return $idx; 959 } 960 } 961 962 $dir = @opendir($conf['indexdir']); 963 if ($dir === false) 964 return array(); 965 $lengths[] = array(); 966 while (($f = readdir($dir)) !== false) { 967 if (substr($f, 0, 1) == 'i' && substr($f, -4) == '.idx') { 968 $i = substr($f, 1, -4); 969 if (is_numeric($i)) 970 $lengths[] = (int)$i; 971 } 972 } 973 closedir($dir); 974 sort($lengths); 975 // save this in a file 976 $fh = @fopen($cachename.'.tmp', 'w'); 977 if (!$fh) { 978 trigger_error("Failed to write index cache", E_USER_ERROR); 979 return; 980 } 981 @fwrite($fh, implode("\n", $lengths)); 982 @fclose($fh); 983 if (isset($conf['fperm'])) 984 chmod($cachename.'.tmp', $conf['fperm']); 985 io_rename($cachename.'.tmp', $cachename.'.idx'); 986 987 return $lengths; 988 } 989 990 /** 991 * Get the word lengths that have been indexed. 992 * 993 * Reads the index directory and returns an array of lengths 994 * that there are indices for. 995 * 996 * @author YoBoY <yoboy.leguesh@gmail.com> 997 */ 998 private function _indexLengths($filter) { 999 global $conf; 1000 $idx = array(); 1001 if (is_array($filter)) { 1002 // testing if index files exist only 1003 $path = $conf['indexdir']."/i"; 1004 foreach ($filter as $key => $value) { 1005 if (@file_exists($path.$key.'.idx')) 1006 $idx[] = $key; 1007 } 1008 } else { 1009 $lengths = idx_listIndexLengths(); 1010 foreach ($lengths as $key => $length) { 1011 // keep all the values equal or superior 1012 if ((int)$length >= (int)$filter) 1013 $idx[] = $length; 1014 } 1015 } 1016 return $idx; 1017 } 1018 1019 /** 1020 * Insert or replace a tuple in a line. 1021 * 1022 * @author Tom N Harris <tnharris@whoopdedo.org> 1023 */ 1024 private function _updateTuple($line, $id, $count) { 1025 $newLine = $line; 1026 if ($newLine !== '') 1027 $newLine = preg_replace('/(^|:)'.preg_quote($id,'/').'\*\d*/', '', $newLine); 1028 $newLine = trim($newLine, ':'); 1029 if ($count) { 1030 if (strlen($newLine) > 0) 1031 return "$id*$count:".$newLine; 1032 else 1033 return "$id*$count".$newLine; 1034 } 1035 return $newLine; 1036 } 1037 1038 /** 1039 * Split a line into an array of tuples. 1040 * 1041 * @author Tom N Harris <tnharris@whoopdedo.org> 1042 * @author Andreas Gohr <andi@splitbrain.org> 1043 */ 1044 private function _parseTuples(&$keys, $line) { 1045 $result = array(); 1046 if ($line == '') return $result; 1047 $parts = explode(':', $line); 1048 foreach ($parts as $tuple) { 1049 if ($tuple == '') continue; 1050 list($key, $cnt) = explode('*', $tuple); 1051 if (!$cnt) continue; 1052 $key = $keys[$key]; 1053 if (!$key) continue; 1054 $result[$key] = $cnt; 1055 } 1056 return $result; 1057 } 1058 1059 /** 1060 * Sum the counts in a list of tuples. 1061 * 1062 * @author Tom N Harris <tnharris@whoopdedo.org> 1063 */ 1064 private function _countTuples($line) { 1065 $freq = 0; 1066 $parts = explode(':', $line); 1067 foreach ($parts as $tuple) { 1068 if ($tuple == '') continue; 1069 list($pid, $cnt) = explode('*', $tuple); 1070 $freq += (int)$cnt; 1071 } 1072 return $freq; 1073 } 1074} 1075 1076/** 1077 * Create an instance of the indexer. 1078 * 1079 * @return object a Doku_Indexer 1080 * @author Tom N Harris <tnharris@whoopdedo.org> 1081 */ 1082function idx_get_indexer() { 1083 static $Indexer = null; 1084 if (is_null($Indexer)) { 1085 $Indexer = new Doku_Indexer(); 1086 } 1087 return $Indexer; 1088} 1089 1090/** 1091 * Returns words that will be ignored. 1092 * 1093 * @return array list of stop words 1094 * @author Tom N Harris <tnharris@whoopdedo.org> 1095 */ 1096function & idx_get_stopwords() { 1097 static $stopwords = null; 1098 if (is_null($stopwords)) { 1099 global $conf; 1100 $swfile = DOKU_INC.'inc/lang/'.$conf['lang'].'/stopwords.txt'; 1101 if(@file_exists($swfile)){ 1102 $stopwords = file($swfile, FILE_IGNORE_NEW_LINES); 1103 }else{ 1104 $stopwords = array(); 1105 } 1106 } 1107 return $stopwords; 1108} 1109 1110/** 1111 * Adds/updates the search index for the given page 1112 * 1113 * Locking is handled internally. 1114 * 1115 * @param string $page name of the page to index 1116 * @param boolean $verbose print status messages 1117 * @return boolean the function completed successfully 1118 * @author Tom N Harris <tnharris@whoopdedo.org> 1119 */ 1120function idx_addPage($page, $verbose=false) { 1121 // check if indexing needed 1122 $idxtag = metaFN($page,'.indexed'); 1123 if(@file_exists($idxtag)){ 1124 if(trim(io_readFile($idxtag)) == idx_get_version()){ 1125 $last = @filemtime($idxtag); 1126 if($last > @filemtime(wikiFN($ID))){ 1127 if ($verbose) print("Indexer: index for $page up to date".DOKU_LF); 1128 return false; 1129 } 1130 } 1131 } 1132 1133 if (!page_exists($page)) { 1134 if (!@file_exists($idxtag)) { 1135 if ($verbose) print("Indexer: $page does not exist, ignoring".DOKU_LF); 1136 return false; 1137 } 1138 $Indexer = idx_get_indexer(); 1139 $result = $Indexer->deletePage($page); 1140 if ($result === "locked") { 1141 if ($verbose) print("Indexer: locked".DOKU_LF); 1142 return false; 1143 } 1144 @unlink($idxtag); 1145 return $result; 1146 } 1147 $indexenabled = p_get_metadata($page, 'internal index', false); 1148 if ($indexenabled === false) { 1149 $result = false; 1150 if (@file_exists($idxtag)) { 1151 $Indexer = idx_get_indexer(); 1152 $result = $Indexer->deletePage($page); 1153 if ($result === "locked") { 1154 if ($verbose) print("Indexer: locked".DOKU_LF); 1155 return false; 1156 } 1157 @unlink($idxtag); 1158 } 1159 if ($verbose) print("Indexer: index disabled for $page".DOKU_LF); 1160 return $result; 1161 } 1162 1163 $body = ''; 1164 $data = array($page, $body); 1165 $evt = new Doku_Event('INDEXER_PAGE_ADD', $data); 1166 if ($evt->advise_before()) $data[1] = $data[1] . " " . rawWiki($page); 1167 $evt->advise_after(); 1168 unset($evt); 1169 list($page,$body) = $data; 1170 1171 $Indexer = idx_get_indexer(); 1172 $result = $Indexer->addPageWords($page, $body); 1173 if ($result === "locked") { 1174 if ($verbose) print("Indexer: locked".DOKU_LF); 1175 return false; 1176 } 1177 1178 if ($result) { 1179 $data = array('page' => $page, 'metadata' => array()); 1180 1181 $data['metadata']['title'] = p_get_metadata($page, 'title', false); 1182 if (($references = p_get_metadata($page, 'relation references', false)) !== null) 1183 $data['metadata']['relation_references'] = array_keys($references); 1184 1185 $evt = new Doku_Event('INDEXER_METADATA_INDEX', $data); 1186 if ($evt->advise_before()) { 1187 $result = $Indexer->addMetaKeys($page, $data['metadata']); 1188 if ($result === "locked") { 1189 if ($verbose) print("Indexer: locked".DOKU_LF); 1190 return false; 1191 } 1192 } 1193 $evt->advise_after(); 1194 unset($evt); 1195 } 1196 1197 if ($result) 1198 io_saveFile(metaFN($page,'.indexed'), idx_get_version()); 1199 if ($verbose) { 1200 print("Indexer: finished".DOKU_LF); 1201 return true; 1202 } 1203 return $result; 1204} 1205 1206/** 1207 * Find tokens in the fulltext index 1208 * 1209 * Takes an array of words and will return a list of matching 1210 * pages for each one. 1211 * 1212 * Important: No ACL checking is done here! All results are 1213 * returned, regardless of permissions 1214 * 1215 * @param arrayref $words list of words to search for 1216 * @return array list of pages found, associated with the search terms 1217 */ 1218function idx_lookup(&$words) { 1219 $Indexer = idx_get_indexer(); 1220 return $Indexer->lookup($words); 1221} 1222 1223/** 1224 * Split a string into tokens 1225 * 1226 */ 1227function idx_tokenizer($string, $wc=false) { 1228 $Indexer = idx_get_indexer(); 1229 return $Indexer->tokenizer($string, $wc); 1230} 1231 1232/* For compatibility */ 1233 1234/** 1235 * Read the list of words in an index (if it exists). 1236 * 1237 * @author Tom N Harris <tnharris@whoopdedo.org> 1238 */ 1239function idx_getIndex($idx, $suffix) { 1240 global $conf; 1241 $fn = $conf['indexdir'].'/'.$idx.$suffix.'.idx'; 1242 if (!@file_exists($fn)) return array(); 1243 return file($fn); 1244} 1245 1246/** 1247 * Get the list of lengths indexed in the wiki. 1248 * 1249 * Read the index directory or a cache file and returns 1250 * a sorted array of lengths of the words used in the wiki. 1251 * 1252 * @author YoBoY <yoboy.leguesh@gmail.com> 1253 */ 1254function idx_listIndexLengths() { 1255 global $conf; 1256 // testing what we have to do, create a cache file or not. 1257 if ($conf['readdircache'] == 0) { 1258 $docache = false; 1259 } else { 1260 clearstatcache(); 1261 if (@file_exists($conf['indexdir'].'/lengths.idx') 1262 && (time() < @filemtime($conf['indexdir'].'/lengths.idx') + $conf['readdircache'])) { 1263 if (($lengths = @file($conf['indexdir'].'/lengths.idx', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES)) !== false) { 1264 $idx = array(); 1265 foreach ($lengths as $length) { 1266 $idx[] = (int)$length; 1267 } 1268 return $idx; 1269 } 1270 } 1271 $docache = true; 1272 } 1273 1274 if ($conf['readdircache'] == 0 || $docache) { 1275 $dir = @opendir($conf['indexdir']); 1276 if ($dir === false) 1277 return array(); 1278 $idx[] = array(); 1279 while (($f = readdir($dir)) !== false) { 1280 if (substr($f, 0, 1) == 'i' && substr($f, -4) == '.idx') { 1281 $i = substr($f, 1, -4); 1282 if (is_numeric($i)) 1283 $idx[] = (int)$i; 1284 } 1285 } 1286 closedir($dir); 1287 sort($idx); 1288 // save this in a file 1289 if ($docache) { 1290 $handle = @fopen($conf['indexdir'].'/lengths.idx', 'w'); 1291 @fwrite($handle, implode("\n", $idx)); 1292 @fclose($handle); 1293 } 1294 return $idx; 1295 } 1296 1297 return array(); 1298} 1299 1300/** 1301 * Get the word lengths that have been indexed. 1302 * 1303 * Reads the index directory and returns an array of lengths 1304 * that there are indices for. 1305 * 1306 * @author YoBoY <yoboy.leguesh@gmail.com> 1307 */ 1308function idx_indexLengths($filter) { 1309 global $conf; 1310 $idx = array(); 1311 if (is_array($filter)) { 1312 // testing if index files exist only 1313 $path = $conf['indexdir']."/i"; 1314 foreach ($filter as $key => $value) { 1315 if (@file_exists($path.$key.'.idx')) 1316 $idx[] = $key; 1317 } 1318 } else { 1319 $lengths = idx_listIndexLengths(); 1320 foreach ($lengths as $key => $length) { 1321 // keep all the values equal or superior 1322 if ((int)$length >= (int)$filter) 1323 $idx[] = $length; 1324 } 1325 } 1326 return $idx; 1327} 1328 1329/** 1330 * Clean a name of a key for use as a file name. 1331 * 1332 * Romanizes non-latin characters, then strips away anything that's 1333 * not a letter, number, or underscore. 1334 * 1335 * @author Tom N Harris <tnharris@whoopdedo.org> 1336 */ 1337function idx_cleanName($name) { 1338 $name = utf8_romanize(trim((string)$name)); 1339 $name = preg_replace('#[ \./\\:-]+#', '_', $name); 1340 $name = preg_replace('/[^A-Za-z0-9_]/', '', $name); 1341 return strtolower($name); 1342} 1343 1344//Setup VIM: ex: et ts=4 : 1345