xref: /dokuwiki/inc/fulltext.php (revision 70a6aa16e600e1ec2fc65fd0e84ece3b4a046fd7) 
1<?php
2/**
3 * DokuWiki fulltextsearch functions using the index
4 *
5 * @license    GPL 2 (http://www.gnu.org/licenses/gpl.html)
6 * @author     Andreas Gohr <andi@splitbrain.org>
7 */
8
9  if(!defined('DOKU_INC')) define('DOKU_INC',realpath(dirname(__FILE__).'/../').'/');
10  require_once(DOKU_INC.'inc/indexer.php');
11
12
13/**
14 * The fulltext search
15 *
16 * Returns a list of matching documents for the given query
17 *
18 */
19function ft_pageSearch($query,&$poswords){
20    $q = ft_queryParser($query);
21    // use this for higlighting later:
22    $poswords = str_replace('*','',join(' ',$q['and']));
23
24    // lookup all words found in the query
25    $words  = array_merge($q['and'],$q['not']);
26    if(!count($words)) return array();
27    $result = idx_lookup($words);
28
29    // merge search results with query
30    foreach($q['and'] as $pos => $w){
31        $q['and'][$pos] = $result[$w];
32    }
33    // create a list of unwanted docs
34    $not = array();
35    foreach($q['not'] as $pos => $w){
36        $not = array_merge($not,array_keys($result[$w]));
37    }
38
39    // combine and-words
40    if(count($q['and']) > 1){
41        $docs = ft_resultCombine($q['and']);
42    }else{
43        $docs = $q['and'][0];
44    }
45    if(!count($docs)) return array();
46
47    // create a list of hidden pages in the result
48    $hidden = array();
49    $hidden = array_filter(array_keys($docs),'isHiddenPage');
50    $not = array_merge($not,$hidden);
51
52    // filter unmatched namespaces
53    if(!empty($q['ns'])) {
54        $pattern = implode('|^',$q['ns']);
55        foreach($docs as $key => $val) {
56            if(!preg_match('/^'.$pattern.'/',$key)) {
57                unset($docs[$key]);
58            }
59        }
60    }
61
62    // remove negative matches
63    foreach($not as $n){
64        unset($docs[$n]);
65    }
66
67    if(!count($docs)) return array();
68    // handle phrases
69    if(count($q['phrases'])){
70        //build a regexp
71        $q['phrases'] = array_map('utf8_strtolower',$q['phrases']);
72        $q['phrases'] = array_map('preg_quote',$q['phrases']);
73        $regex = '('.join('|',$q['phrases']).')';
74        // check the source of all documents for the exact phrases
75        foreach(array_keys($docs) as $id){
76            $text  = utf8_strtolower(rawWiki($id));
77            if(!preg_match('/'.$regex.'/usi',$text)){
78                unset($docs[$id]); // no hit - remove
79            }
80        }
81    }
82
83    if(!count($docs)) return array();
84
85    // check ACL permissions
86    foreach(array_keys($docs) as $doc){
87        if(auth_quickaclcheck($doc) < AUTH_READ){
88            unset($docs[$doc]);
89        }
90    }
91
92    if(!count($docs)) return array();
93
94    // if there are any hits left, sort them by count
95    arsort($docs);
96
97    return $docs;
98}
99
100/**
101 * Returns the backlinks for a given page
102 *
103 * Does a quick lookup with the fulltext index, then
104 * evaluates the instructions of the found pages
105 */
106function ft_backlinks($id){
107    global $conf;
108    $result = array();
109
110    // quick lookup of the pagename
111    $page    = noNS($id);
112    $sw      = array(); // we don't use stopwords here
113    $matches = idx_lookup(idx_tokenizer($page,$sw));  // pagename may contain specials (_ or .)
114    $docs    = array_keys(ft_resultCombine(array_values($matches)));
115    $docs    = array_filter($docs,'isVisiblePage'); // discard hidden pages
116    if(!count($docs)) return $result;
117    require_once(DOKU_INC.'inc/parserutils.php');
118
119    // check instructions for matching links
120    foreach($docs as $match){
121/*
122// orig code, examine each page's instruction list
123        $instructions = p_cached_instructions(wikiFN($match),true);
124        if(is_null($instructions)) continue;
125
126        $match_ns =  getNS($match);
127
128        foreach($instructions as $ins){
129            if($ins[0] == 'internallink' || ($conf['camelcase'] && $ins[0] == 'camelcaselink') ){
130                $link = $ins[1][0];
131                resolve_pageid($match_ns,$link,$exists); //exists is not used
132                if($link == $id){
133                    //we have a match - finish
134                    $result[] = $match;
135                    break;
136                }
137            }
138        }
139*/
140// now with metadata (metadata relation reference links are already resolved)
141        $links = p_get_metadata($match,"relation references");
142        if (isset($links[$id])) $result[] = $match;
143    }
144
145    if(!count($result)) return $result;
146
147    // check ACL permissions
148    foreach(array_keys($result) as $idx){
149        if(auth_quickaclcheck($result[$idx]) < AUTH_READ){
150            unset($result[$idx]);
151        }
152    }
153
154    sort($result);
155    return $result;
156}
157
158/**
159 * Quicksearch for pagenames
160 *
161 * By default it only matches the pagename and ignores the
162 * namespace. This can be changed with the second parameter
163 *
164 * @author Andreas Gohr <andi@splitbrain.org>
165 */
166function ft_pageLookup($id,$pageonly=true){
167    global $conf;
168    $id    = preg_quote($id,'/');
169    $pages = file($conf['cachedir'].'/page.idx');
170    $pages = array_values(preg_grep('/'.$id.'/',$pages));
171
172    $cnt = count($pages);
173    for($i=0; $i<$cnt; $i++){
174        if($pageonly){
175            if(!preg_match('/'.$id.'/',noNS($pages[$i]))){
176                unset($pages[$i]);
177                continue;
178            }
179        }
180        if(!@file_exists(wikiFN($pages[$i]))){
181            unset($pages[$i]);
182            continue;
183        }
184    }
185
186    $pages = array_filter($pages,'isVisiblePage'); // discard hidden pages
187    if(!count($pages)) return array();
188
189    // check ACL permissions
190    foreach(array_keys($pages) as $idx){
191        if(auth_quickaclcheck($pages[$idx]) < AUTH_READ){
192            unset($pages[$idx]);
193        }
194    }
195
196    sort($pages);
197    return $pages;
198}
199
200/**
201 * Creates a snippet extract
202 *
203 * @author Andreas Gohr <andi@splitbrain.org>
204 */
205function ft_snippet($id,$poswords){
206    $poswords = preg_quote($poswords,'#');
207    $re       = '('.str_replace(' ','|',$poswords).')';
208    $text     = rawWiki($id);
209
210// extra code to allow selection of search algorithm - remove before release
211global $conf;
212$algorithm = '';
213if ($conf['allowdebug']) {
214  if (!empty($_REQUEST['_search'])) $algorithm = $_REQUEST['_search'];
215}
216
217switch ($algorithm) {
218  case 'orig' :
219// original code ... dokuwiki
220
221    //FIXME caseinsensitive matching doesn't work with UTF-8!?
222    preg_match_all('#(.{0,50})'.$re.'(.{0,50})#iu',$text,$matches,PREG_SET_ORDER);
223
224    $cnt = 0;
225    $snippet = '';
226    foreach($matches as $match){
227        $snippet .= '...'.htmlspecialchars($match[1]);
228        $snippet .= '<span class="search_hit">';
229        $snippet .= htmlspecialchars($match[2]);
230        $snippet .= '</span>';
231        $snippet .= htmlspecialchars($match[3]).'... ';
232        if($cnt++ == 2) break;
233    }
234
235  break;
236
237  case 'opt1' :
238// my snippet algorithm, first cut ... CS 2006-08-25
239// reduce the impact of the original regex
240    $matches = array();
241    preg_match_all('#'.$re.'#iu',$text,$matches,PREG_OFFSET_CAPTURE|PREG_SET_ORDER);
242
243    $cnt = 3;
244    $snippets = array();
245    $len = strlen($text);
246    foreach ($matches as $match) {
247      list($str,$idx) = $match[0];
248      if ($idx < $end) continue;
249
250      $pre = min($idx,50);
251      $start = utf8_correctIdx($text, $idx - $pre);
252      $end = utf8_correctIdx($text, min($idx+100+strlen($str)-$pre,$len));
253      $snippets[] = substr($text,$start,$end-$start);
254      if (!($cnt--)) break;
255    }
256
257    $m = "\1";
258    $snippets = preg_replace('#'.$re.'#iu',$m.'$1'.$m,$snippets);
259    $snippet = preg_replace('#'.$m.'([^'.$m.']*?)'.$m.'#iu','<span class="search_hit">$1</span>',hsc(join('... ',$snippets)));
260
261  break;
262
263  case 'opt2' :
264// option 2 ... CS 2006-08-25
265// above + reduce amount of the file searched
266    $match = array();
267    $snippets = array();
268    $offset = 0;
269    $len = strlen($text);
270    for ($cnt=3; $cnt--;) {
271      if (!preg_match('#'.$re.'#iu',$text,$match,PREG_OFFSET_CAPTURE,$offset)) break;
272
273      list($str,$idx) = $match[0];
274
275      // establish context, 100 bytes surrounding the match string
276      // first look to see if we can go 100 either side,
277      // then drop to 50 adding any excess if the other side can't go to 50,
278      // NOTE: these are byte adjustments and will have to be corrected for utf-8
279      $pre = min($idx-$offset,100);
280      $post = min($len-$idx-strlen($str),100);
281
282      if ($pre>50 && $post>50) {
283        $pre = $post = 50;
284      } else if ($pre>50) {
285        $pre = min($pre,100-$post);
286      } else if ($post>50) {
287        $post = min($post, 100-$pre);
288      } else {
289        // means both pre & post are less than 50, the context is the whole string
290        // make it so and break out of this loop - there is no need for the complex snippet calculations
291        $snippets = array($text);
292        break;
293      }
294
295      // establish context start and end points, try to append to previous context if possible
296      $start = utf8_correctIdx($text,$idx - $pre);
297      $append = ($start < $end) ? $end : false;                     // still the end of the previous context snippet
298      $end = utf8_correctIdx($text, $idx + strlen($str) + $post);   // now set it to the end of this context
299
300      if ($append) {
301        $snippets[count($snippets)-1] .= substr($text,$append,$end-$append);
302      } else {
303        $snippets[] = substr($text,$start,$end-$start);
304      }
305
306      // set $offset for next match attempt
307      //   substract strlen to avoid splitting a potential search success, this is an approximation as the
308      //   search pattern may match strings of varying length and it will fail if the context snippet
309      //   boundary breaks a matching string longer than the current match
310      $offset = $end - strlen($str);
311    }
312    $m = "\1";
313    $snippets = preg_replace('#'.$re.'#iu',$m.'$1'.$m,$snippets);
314    $snippet = preg_replace('#'.$m.'([^'.$m.']*?)'.$m.'#iu','<span class="search_hit">$1</span>',hsc(join('... ',$snippets)));
315
316  break;
317
318  case 'utf8':
319  default :
320
321    $match = array();
322    $snippets = array();
323    $utf8_offset = $offset = $end = 0;
324    $len = utf8_strlen($text);
325
326    for ($cnt=3; $cnt--;) {
327      if (!preg_match('#'.$re.'#iu',$text,$match,PREG_OFFSET_CAPTURE,$offset)) break;
328
329      list($str,$idx) = $match[0];
330
331      // convert $idx (a byte offset) into a utf8 character offset
332      $utf8_idx = utf8_strlen(substr($text,0,$idx));
333      $utf8_len = utf8_strlen($str);
334
335      // establish context, 100 bytes surrounding the match string
336      // first look to see if we can go 100 either side,
337      // then drop to 50 adding any excess if the other side can't go to 50,
338      $pre = min($utf8_idx-$utf8_offset,100);
339      $post = min($len-$utf8_idx-$utf8_len,100);
340
341      if ($pre>50 && $post>50) {
342        $pre = $post = 50;
343      } else if ($pre>50) {
344        $pre = min($pre,100-$post);
345      } else if ($post>50) {
346        $post = min($post, 100-$pre);
347      } else {
348        // both are less than 50, means the context is the whole string
349        // make it so and break out of this loop - there is no need for the complex snippet calculations
350        $snippets = array($text);
351        break;
352      }
353
354      // establish context start and end points, try to append to previous context if possible
355      $start = $utf8_idx - $pre;
356      $append = ($start < $end) ? $end : false;       // still the end of the previous context snippet
357      $end = $utf8_idx + $utf8_len + $post;           // now set it to the end of this context
358
359      if ($append) {
360        $snippets[count($snippets)-1] .= utf8_substr($text,$append,$end-$append);
361      } else {
362        $snippets[] = utf8_substr($text,$start,$end-$start);
363      }
364
365      // set $offset for next match attempt
366      //   substract strlen to avoid splitting a potential search success, this is an approximation as the
367      //   search pattern may match strings of varying length and it will fail if the context snippet
368      //   boundary breaks a matching string longer than the current match
369      $utf8_offset = $utf8_idx + $post;
370      $offset = $idx + strlen(utf8_substr($text,$utf8_idx,$post));
371      $offset = utf8_correctIdx($text,$offset);
372    }
373
374    $m = "\1";
375    $snippets = preg_replace('#'.$re.'#iu',$m.'$1'.$m,$snippets);
376    $snippet = preg_replace('#'.$m.'([^'.$m.']*?)'.$m.'#iu','<span class="search_hit">$1</span>',hsc(join('... ',$snippets)));
377  break;
378}
379
380    return $snippet;
381}
382
383/**
384 * Combine found documents and sum up their scores
385 *
386 * This function is used to combine searched words with a logical
387 * AND. Only documents available in all arrays are returned.
388 *
389 * based upon PEAR's PHP_Compat function for array_intersect_key()
390 *
391 * @param array $args An array of page arrays
392 */
393function ft_resultCombine($args){
394    $array_count = count($args);
395    if($array_count == 1){
396        return $args[0];
397    }
398
399    $result = array();
400    foreach ($args[0] as $key1 => $value1) {
401        for ($i = 1; $i !== $array_count; $i++) {
402            foreach ($args[$i] as $key2 => $value2) {
403                if ((string) $key1 === (string) $key2) {
404                    if(!isset($result[$key1])) $result[$key1] = $value1;
405                    $result[$key1] += $value2;
406                }
407            }
408        }
409    }
410    return $result;
411}
412
413/**
414 * Builds an array of search words from a query
415 *
416 * @todo support OR and parenthesises?
417 * @todo add namespace handling
418 */
419function ft_queryParser($query){
420    global $conf;
421    $swfile   = DOKU_INC.'inc/lang/'.$conf['lang'].'/stopwords.txt';
422    if(@file_exists($swfile)){
423        $stopwords = file($swfile);
424    }else{
425        $stopwords = array();
426    }
427
428    $q = array();
429    $q['query']   = $query;
430    $q['ns']      = array();
431    $q['phrases'] = array();
432    $q['and']     = array();
433    $q['not']     = array();
434
435    // strip namespace from query
436    if(preg_match('/([^@]*)@(.*)/',$query,$match))  {
437        $query = $match[1];
438        $q['ns'] = explode('@',preg_replace("/ /",'',$match[2]));
439    }
440
441    // handle phrase searches
442    while(preg_match('/"(.*?)"/',$query,$match)){
443        $q['phrases'][] = $match[1];
444        $q['and'] = array_merge(idx_tokenizer($match[0],$stopwords));
445        $query = preg_replace('/"(.*?)"/','',$query,1);
446    }
447
448    $words = explode(' ',$query);
449    foreach($words as $w){
450        if($w{0} == '-'){
451            $token = idx_tokenizer($w,$stopwords,true);
452            if(count($token)) $q['not'] = array_merge($q['not'],$token);
453        }else{
454            // asian "words" need to be searched as phrases
455            if(@preg_match_all('/('.IDX_ASIAN.'+)/u',$w,$matches)){
456                $q['phrases'] = array_merge($q['phrases'],$matches[1]);
457
458            }
459            $token = idx_tokenizer($w,$stopwords,true);
460            if(count($token)) $q['and'] = array_merge($q['and'],$token);
461        }
462    }
463
464    return $q;
465}
466
467//Setup VIM: ex: et ts=4 enc=utf-8 :
468