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