1<?php
2
3/**
4 * DokuWiki fulltextsearch functions using the index
5 *
6 * @license    GPL 2 (http://www.gnu.org/licenses/gpl.html)
7 * @author     Andreas Gohr <andi@splitbrain.org>
8 */
9
10use dokuwiki\Utf8\Asian;
11use dokuwiki\Search\Indexer;
12use dokuwiki\Extension\Event;
13use dokuwiki\Utf8\Clean;
14use dokuwiki\Utf8\PhpString;
15use dokuwiki\Utf8\Sort;
16
17/**
18 * create snippets for the first few results only
19 */
20if (!defined('FT_SNIPPET_NUMBER')) define('FT_SNIPPET_NUMBER', 15);
21
22/**
23 * The fulltext search
24 *
25 * Returns a list of matching documents for the given query
26 *
27 * refactored into ft_pageSearch(), _ft_pageSearch() and trigger_event()
28 *
29 * @param string     $query
30 * @param array      $highlight
31 * @param string     $sort
32 * @param int|string $after  only show results with mtime after this date, accepts timestap or strtotime arguments
33 * @param int|string $before only show results with mtime before this date, accepts timestap or strtotime arguments
34 *
35 * @return array
36 */
37function ft_pageSearch($query, &$highlight, $sort = null, $after = null, $before = null)
38{
39
40    if ($sort === null) {
41        $sort = 'hits';
42    }
43    $data = [
44        'query' => $query,
45        'sort' => $sort,
46        'after' => $after,
47        'before' => $before
48    ];
49    $data['highlight'] =& $highlight;
50
51    return Event::createAndTrigger('SEARCH_QUERY_FULLPAGE', $data, '_ft_pageSearch');
52}
53
54/**
55 * Returns a list of matching documents for the given query
56 *
57 * @author Andreas Gohr <andi@splitbrain.org>
58 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
59 *
60 * @param array $data event data
61 * @return array matching documents
62 */
63function _ft_pageSearch(&$data)
64{
65    $Indexer = idx_get_indexer();
66
67    // parse the given query
68    $q = ft_queryParser($Indexer, $data['query']);
69    $data['highlight'] = $q['highlight'];
70
71    if (empty($q['parsed_ary'])) return [];
72
73    // lookup all words found in the query
74    $lookup = $Indexer->lookup($q['words']);
75
76    // get all pages in this dokuwiki site (!: includes nonexistent pages)
77    $pages_all = [];
78    foreach ($Indexer->getPages() as $id) {
79        $pages_all[$id] = 0; // base: 0 hit
80    }
81
82    // process the query
83    $stack = [];
84    foreach ($q['parsed_ary'] as $token) {
85        switch (substr($token, 0, 3)) {
86            case 'W+:':
87            case 'W-:':
88            case 'W_:': // word
89                $word    = substr($token, 3);
90                if (isset($lookup[$word])) {
91                    $stack[] = (array)$lookup[$word];
92                }
93                break;
94            case 'P+:':
95            case 'P-:': // phrase
96                $phrase = substr($token, 3);
97                // since phrases are always parsed as ((W1)(W2)...(P)),
98                // the end($stack) always points at the pages that contain
99                // all words in this phrase
100                $pages  = $stack ? end($stack) : [];
101                $pages_matched = [];
102                foreach (array_keys($pages) as $id) {
103                    $evdata = [
104                        'id' => $id,
105                        'phrase' => $phrase,
106                        'text' => rawWiki($id)
107                    ];
108                    $evt = new Event('FULLTEXT_PHRASE_MATCH', $evdata);
109                    if ($evt->advise_before() && $evt->result !== true) {
110                        $text = PhpString::strtolower($evdata['text']);
111                        if (strpos($text, $phrase) !== false) {
112                            $evt->result = true;
113                        }
114                    }
115                    $evt->advise_after();
116                    if ($evt->result === true) {
117                        $pages_matched[$id] = 0; // phrase: always 0 hit
118                    }
119                }
120                $stack[] = $pages_matched;
121                break;
122            case 'N+:':
123            case 'N-:': // namespace
124                $ns = cleanID(substr($token, 3)) . ':';
125                $pages_matched = [];
126                foreach (array_keys($pages_all) as $id) {
127                    if (strpos($id, $ns) === 0) {
128                        $pages_matched[$id] = 0; // namespace: always 0 hit
129                    }
130                }
131                $stack[] = $pages_matched;
132                break;
133            case 'AND': // and operation
134                $pages = array_splice($stack, -2);
135                if ($pages === []) {
136                    break;
137                }
138                $stack[] = ft_resultCombine($pages);
139                break;
140            case 'OR':  // or operation
141                $pages = array_splice($stack, -2);
142                if ($pages === []) {
143                    break;
144                }
145                $stack[] = ft_resultUnite($pages);
146                break;
147            case 'NOT': // not operation (unary)
148                $pages   = array_pop($stack);
149                $stack[] = ft_resultComplement([$pages_all, $pages]);
150                break;
151        }
152    }
153    $docs = array_pop($stack);
154
155    if (empty($docs)) return [];
156
157    // check: settings, acls, existence
158    foreach (array_keys($docs) as $id) {
159        if (isHiddenPage($id) || auth_quickaclcheck($id) < AUTH_READ || !page_exists($id, '', false)) {
160            unset($docs[$id]);
161        }
162    }
163
164    $docs = _ft_filterResultsByTime($docs, $data['after'], $data['before']);
165
166    if ($data['sort'] === 'mtime') {
167        uksort($docs, 'ft_pagemtimesorter');
168    } else {
169        // sort docs by count
170        uksort($docs, 'ft_pagesorter');
171        arsort($docs);
172    }
173
174    return $docs;
175}
176
177/**
178 * Returns the backlinks for a given page
179 *
180 * Uses the metadata index.
181 *
182 * @param string $id           The id for which links shall be returned
183 * @param bool   $ignore_perms Ignore the fact that pages are hidden or read-protected
184 * @return array The pages that contain links to the given page
185 */
186function ft_backlinks($id, $ignore_perms = false)
187{
188    $result = idx_get_indexer()->lookupKey('relation_references', $id);
189
190    if ($result === []) return $result;
191
192    // check ACL permissions
193    foreach (array_keys($result) as $idx) {
194        if (
195            (!$ignore_perms && (
196                isHiddenPage($result[$idx]) || auth_quickaclcheck($result[$idx]) < AUTH_READ
197            )) || !page_exists($result[$idx], '', false)
198        ) {
199            unset($result[$idx]);
200        }
201    }
202
203    Sort::sort($result);
204    return $result;
205}
206
207/**
208 * Returns the pages that use a given media file
209 *
210 * Uses the relation media metadata property and the metadata index.
211 *
212 * Note that before 2013-07-31 the second parameter was the maximum number of results and
213 * permissions were ignored. That's why the parameter is now checked to be explicitely set
214 * to true (with type bool) in order to be compatible with older uses of the function.
215 *
216 * @param string $id           The media id to look for
217 * @param bool   $ignore_perms Ignore hidden pages and acls (optional, default: false)
218 * @return array A list of pages that use the given media file
219 */
220function ft_mediause($id, $ignore_perms = false)
221{
222    $result = idx_get_indexer()->lookupKey('relation_media', $id);
223
224    if ($result === []) return $result;
225
226    // check ACL permissions
227    foreach (array_keys($result) as $idx) {
228        if (
229            (!$ignore_perms && (
230                    isHiddenPage($result[$idx]) || auth_quickaclcheck($result[$idx]) < AUTH_READ
231                )) || !page_exists($result[$idx], '', false)
232        ) {
233            unset($result[$idx]);
234        }
235    }
236
237    Sort::sort($result);
238    return $result;
239}
240
241
242/**
243 * Quicksearch for pagenames
244 *
245 * By default it only matches the pagename and ignores the
246 * namespace. This can be changed with the second parameter.
247 * The third parameter allows to search in titles as well.
248 *
249 * The function always returns titles as well
250 *
251 * @triggers SEARCH_QUERY_PAGELOOKUP
252 * @author   Andreas Gohr <andi@splitbrain.org>
253 * @author   Adrian Lang <lang@cosmocode.de>
254 *
255 * @param string     $id       page id
256 * @param bool       $in_ns    match against namespace as well?
257 * @param bool       $in_title search in title?
258 * @param int|string $after    only show results with mtime after this date, accepts timestap or strtotime arguments
259 * @param int|string $before   only show results with mtime before this date, accepts timestap or strtotime arguments
260 *
261 * @return string[]
262 */
263function ft_pageLookup($id, $in_ns = false, $in_title = false, $after = null, $before = null)
264{
265    $data = [
266        'id' => $id,
267        'in_ns' => $in_ns,
268        'in_title' => $in_title,
269        'after' => $after,
270        'before' => $before
271    ];
272    $data['has_titles'] = true; // for plugin backward compatibility check
273    return Event::createAndTrigger('SEARCH_QUERY_PAGELOOKUP', $data, '_ft_pageLookup');
274}
275
276/**
277 * Returns list of pages as array(pageid => First Heading)
278 *
279 * @param array &$data event data
280 * @return string[]
281 */
282function _ft_pageLookup(&$data)
283{
284    // split out original parameters
285    $id = $data['id'];
286    $Indexer = idx_get_indexer();
287    $parsedQuery = ft_queryParser($Indexer, $id);
288    if (count($parsedQuery['ns']) > 0) {
289        $ns = cleanID($parsedQuery['ns'][0]) . ':';
290        $id = implode(' ', $parsedQuery['highlight']);
291    }
292    if (count($parsedQuery['notns']) > 0) {
293        $notns = cleanID($parsedQuery['notns'][0]) . ':';
294        $id = implode(' ', $parsedQuery['highlight']);
295    }
296
297    $in_ns    = $data['in_ns'];
298    $in_title = $data['in_title'];
299    $cleaned = cleanID($id);
300
301    $Indexer = idx_get_indexer();
302    $page_idx = $Indexer->getPages();
303
304    $pages = [];
305    if ($id !== '' && $cleaned !== '') {
306        foreach ($page_idx as $p_id) {
307            if ((strpos($in_ns ? $p_id : noNSorNS($p_id), $cleaned) !== false)) {
308                if (!isset($pages[$p_id]))
309                    $pages[$p_id] = p_get_first_heading($p_id, METADATA_DONT_RENDER);
310            }
311        }
312        if ($in_title) {
313            foreach ($Indexer->lookupKey('title', $id, '_ft_pageLookupTitleCompare') as $p_id) {
314                if (!isset($pages[$p_id]))
315                    $pages[$p_id] = p_get_first_heading($p_id, METADATA_DONT_RENDER);
316            }
317        }
318    }
319
320    if (isset($ns)) {
321        foreach (array_keys($pages) as $p_id) {
322            if (strpos($p_id, $ns) !== 0) {
323                unset($pages[$p_id]);
324            }
325        }
326    }
327    if (isset($notns)) {
328        foreach (array_keys($pages) as $p_id) {
329            if (strpos($p_id, $notns) === 0) {
330                unset($pages[$p_id]);
331            }
332        }
333    }
334
335    // discard hidden pages
336    // discard nonexistent pages
337    // check ACL permissions
338    foreach (array_keys($pages) as $idx) {
339        if (
340            !isVisiblePage($idx) || !page_exists($idx) ||
341            auth_quickaclcheck($idx) < AUTH_READ
342        ) {
343            unset($pages[$idx]);
344        }
345    }
346
347    $pages = _ft_filterResultsByTime($pages, $data['after'], $data['before']);
348
349    uksort($pages, 'ft_pagesorter');
350    return $pages;
351}
352
353
354/**
355 * @param array      $results search results in the form pageid => value
356 * @param int|string $after   only returns results with mtime after this date, accepts timestap or strtotime arguments
357 * @param int|string $before  only returns results with mtime after this date, accepts timestap or strtotime arguments
358 *
359 * @return array
360 */
361function _ft_filterResultsByTime(array $results, $after, $before)
362{
363    if ($after || $before) {
364        $after = is_int($after) ? $after : strtotime($after);
365        $before = is_int($before) ? $before : strtotime($before);
366
367        foreach (array_keys($results) as $id) {
368            $mTime = filemtime(wikiFN($id));
369            if ($after && $after > $mTime) {
370                unset($results[$id]);
371                continue;
372            }
373            if ($before && $before < $mTime) {
374                unset($results[$id]);
375            }
376        }
377    }
378
379    return $results;
380}
381
382/**
383 * Tiny helper function for comparing the searched title with the title
384 * from the search index. This function is a wrapper around stripos with
385 * adapted argument order and return value.
386 *
387 * @param string $search searched title
388 * @param string $title  title from index
389 * @return bool
390 */
391function _ft_pageLookupTitleCompare($search, $title)
392{
393    if (Clean::isASCII($search)) {
394        $pos = stripos($title, $search);
395    } else {
396        $pos = PhpString::strpos(
397            PhpString::strtolower($title),
398            PhpString::strtolower($search)
399        );
400    }
401
402    return $pos !== false;
403}
404
405/**
406 * Sort pages based on their namespace level first, then on their string
407 * values. This makes higher hierarchy pages rank higher than lower hierarchy
408 * pages.
409 *
410 * @param string $a
411 * @param string $b
412 * @return int Returns < 0 if $a is less than $b; > 0 if $a is greater than $b, and 0 if they are equal.
413 */
414function ft_pagesorter($a, $b)
415{
416    $ac = count(explode(':', $a));
417    $bc = count(explode(':', $b));
418    if ($ac < $bc) {
419        return -1;
420    } elseif ($ac > $bc) {
421        return 1;
422    }
423    return Sort::strcmp($a, $b);
424}
425
426/**
427 * Sort pages by their mtime, from newest to oldest
428 *
429 * @param string $a
430 * @param string $b
431 *
432 * @return int Returns < 0 if $a is newer than $b, > 0 if $b is newer than $a and 0 if they are of the same age
433 */
434function ft_pagemtimesorter($a, $b)
435{
436    $mtimeA = filemtime(wikiFN($a));
437    $mtimeB = filemtime(wikiFN($b));
438    return $mtimeB - $mtimeA;
439}
440
441/**
442 * Creates a snippet extract
443 *
444 * @author Andreas Gohr <andi@splitbrain.org>
445 * @triggers FULLTEXT_SNIPPET_CREATE
446 *
447 * @param string $id page id
448 * @param array $highlight
449 * @return mixed
450 */
451function ft_snippet($id, $highlight)
452{
453    $text = rawWiki($id);
454    $text = str_replace("\xC2\xAD", '', $text);
455     // remove soft-hyphens
456    $evdata = [
457        'id'        => $id,
458        'text'      => &$text,
459        'highlight' => &$highlight,
460        'snippet'   => ''
461    ];
462
463    $evt = new Event('FULLTEXT_SNIPPET_CREATE', $evdata);
464    if ($evt->advise_before()) {
465        $match = [];
466        $snippets = [];
467        $utf8_offset = 0;
468        $offset = 0;
469        $end = 0;
470        $len = PhpString::strlen($text);
471
472        // build a regexp from the phrases to highlight
473        $re1 = '(' .
474            implode(
475                '|',
476                array_map(
477                    'ft_snippet_re_preprocess',
478                    array_map(
479                        'preg_quote_cb',
480                        array_filter((array) $highlight)
481                    )
482                )
483            ) .
484            ')';
485        $re2 = "$re1.{0,75}(?!\\1)$re1";
486        $re3 = "$re1.{0,45}(?!\\1)$re1.{0,45}(?!\\1)(?!\\2)$re1";
487
488        for ($cnt = 4; $cnt--;) {
489            if (0) {
490            } elseif (preg_match('/' . $re3 . '/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
491            } elseif (preg_match('/' . $re2 . '/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
492            } elseif (preg_match('/' . $re1 . '/iu', $text, $match, PREG_OFFSET_CAPTURE, $offset)) {
493            } else {
494                break;
495            }
496
497            [$str, $idx] = $match[0];
498
499            // convert $idx (a byte offset) into a utf8 character offset
500            $utf8_idx = PhpString::strlen(substr($text, 0, $idx));
501            $utf8_len = PhpString::strlen($str);
502
503            // establish context, 100 bytes surrounding the match string
504            // first look to see if we can go 100 either side,
505            // then drop to 50 adding any excess if the other side can't go to 50,
506            $pre = min($utf8_idx - $utf8_offset, 100);
507            $post = min($len - $utf8_idx - $utf8_len, 100);
508
509            if ($pre > 50 && $post > 50) {
510                $pre = 50;
511                $post = 50;
512            } elseif ($pre > 50) {
513                $pre = min($pre, 100 - $post);
514            } elseif ($post > 50) {
515                $post = min($post, 100 - $pre);
516            } elseif ($offset == 0) {
517                // both are less than 50, means the context is the whole string
518                // make it so and break out of this loop - there is no need for the
519                // complex snippet calculations
520                $snippets = [$text];
521                break;
522            }
523
524            // establish context start and end points, try to append to previous
525            // context if possible
526            $start = $utf8_idx - $pre;
527            $append = ($start < $end) ? $end : false;  // still the end of the previous context snippet
528            $end = $utf8_idx + $utf8_len + $post;      // now set it to the end of this context
529
530            if ($append) {
531                $snippets[count($snippets) - 1] .= PhpString::substr($text, $append, $end - $append);
532            } else {
533                $snippets[] = PhpString::substr($text, $start, $end - $start);
534            }
535
536            // set $offset for next match attempt
537            // continue matching after the current match
538            // if the current match is not the longest possible match starting at the current offset
539            // this prevents further matching of this snippet but for possible matches of length
540            // smaller than match length + context (at least 50 characters) this match is part of the context
541            $utf8_offset = $utf8_idx + $utf8_len;
542            $offset = $idx + strlen(PhpString::substr($text, $utf8_idx, $utf8_len));
543            $offset = Clean::correctIdx($text, $offset);
544        }
545
546        $m = "\1";
547        $snippets = preg_replace('/' . $re1 . '/iu', $m . '$1' . $m, $snippets);
548        $snippet = preg_replace(
549            '/' . $m . '([^' . $m . ']*?)' . $m . '/iu',
550            '<strong class="search_hit">$1</strong>',
551            hsc(implode('... ', $snippets))
552        );
553
554        $evdata['snippet'] = $snippet;
555    }
556    $evt->advise_after();
557    unset($evt);
558
559    return $evdata['snippet'];
560}
561
562/**
563 * Wraps a search term in regex boundary checks.
564 *
565 * @param string $term
566 * @return string
567 */
568function ft_snippet_re_preprocess($term)
569{
570    // do not process asian terms where word boundaries are not explicit
571    if (Asian::isAsianWords($term)) return $term;
572
573    if (UTF8_PROPERTYSUPPORT) {
574        // unicode word boundaries
575        // see http://stackoverflow.com/a/2449017/172068
576        $BL = '(?<!\pL)';
577        $BR = '(?!\pL)';
578    } else {
579        // not as correct as above, but at least won't break
580        $BL = '\b';
581        $BR = '\b';
582    }
583
584    if (str_starts_with($term, '\\*')) {
585        $term = substr($term, 2);
586    } else {
587        $term = $BL . $term;
588    }
589
590    if (str_ends_with($term, '\\*')) {
591        $term = substr($term, 0, -2);
592    } else {
593        $term .= $BR;
594    }
595
596    if ($term == $BL || $term == $BR || $term == $BL . $BR) $term = '';
597    return $term;
598}
599
600/**
601 * Combine found documents and sum up their scores
602 *
603 * This function is used to combine searched words with a logical
604 * AND. Only documents available in all arrays are returned.
605 *
606 * based upon PEAR's PHP_Compat function for array_intersect_key()
607 *
608 * @param array $args An array of page arrays
609 * @return array
610 */
611function ft_resultCombine($args)
612{
613    $array_count = count($args);
614    if ($array_count == 1) {
615        return $args[0];
616    }
617
618    $result = [];
619    if ($array_count > 1) {
620        foreach ($args[0] as $key => $value) {
621            $result[$key] = $value;
622            for ($i = 1; $i !== $array_count; $i++) {
623                if (!isset($args[$i][$key])) {
624                    unset($result[$key]);
625                    break;
626                }
627                $result[$key] += $args[$i][$key];
628            }
629        }
630    }
631    return $result;
632}
633
634/**
635 * Unites found documents and sum up their scores
636 *
637 * based upon ft_resultCombine() function
638 *
639 * @param array $args An array of page arrays
640 * @return array
641 *
642 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
643 */
644function ft_resultUnite($args)
645{
646    $array_count = count($args);
647    if ($array_count === 1) {
648        return $args[0];
649    }
650
651    $result = $args[0];
652    for ($i = 1; $i !== $array_count; $i++) {
653        foreach (array_keys($args[$i]) as $id) {
654            $result[$id] += $args[$i][$id];
655        }
656    }
657    return $result;
658}
659
660/**
661 * Computes the difference of documents using page id for comparison
662 *
663 * nearly identical to PHP5's array_diff_key()
664 *
665 * @param array $args An array of page arrays
666 * @return array
667 *
668 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
669 */
670function ft_resultComplement($args)
671{
672    $array_count = count($args);
673    if ($array_count === 1) {
674        return $args[0];
675    }
676
677    $result = $args[0];
678    foreach (array_keys($result) as $id) {
679        for ($i = 1; $i !== $array_count; $i++) {
680            if (isset($args[$i][$id])) unset($result[$id]);
681        }
682    }
683    return $result;
684}
685
686/**
687 * Parses a search query and builds an array of search formulas
688 *
689 * @author Andreas Gohr <andi@splitbrain.org>
690 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
691 *
692 * @param Indexer $Indexer
693 * @param string                  $query search query
694 * @return array of search formulas
695 */
696function ft_queryParser($Indexer, $query)
697{
698    /**
699     * parse a search query and transform it into intermediate representation
700     *
701     * in a search query, you can use the following expressions:
702     *
703     *   words:
704     *     include
705     *     -exclude
706     *   phrases:
707     *     "phrase to be included"
708     *     -"phrase you want to exclude"
709     *   namespaces:
710     *     @include:namespace (or ns:include:namespace)
711     *     ^exclude:namespace (or -ns:exclude:namespace)
712     *   groups:
713     *     ()
714     *     -()
715     *   operators:
716     *     and ('and' is the default operator: you can always omit this)
717     *     or  (or pipe symbol '|', lower precedence than 'and')
718     *
719     * e.g. a query [ aa "bb cc" @dd:ee ] means "search pages which contain
720     *      a word 'aa', a phrase 'bb cc' and are within a namespace 'dd:ee'".
721     *      this query is equivalent to [ -(-aa or -"bb cc" or -ns:dd:ee) ]
722     *      as long as you don't mind hit counts.
723     *
724     * intermediate representation consists of the following parts:
725     *
726     *   ( )           - group
727     *   AND           - logical and
728     *   OR            - logical or
729     *   NOT           - logical not
730     *   W+:, W-:, W_: - word      (underscore: no need to highlight)
731     *   P+:, P-:      - phrase    (minus sign: logically in NOT group)
732     *   N+:, N-:      - namespace
733     */
734    $parsed_query = '';
735    $parens_level = 0;
736    $terms = preg_split(
737        '/(-?".*?")/u',
738        PhpString::strtolower($query),
739        -1,
740        PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY
741    );
742
743    foreach ($terms as $term) {
744        $parsed = '';
745        if (preg_match('/^(-?)"(.+)"$/u', $term, $matches)) {
746            // phrase-include and phrase-exclude
747            $not = $matches[1] ? 'NOT' : '';
748            $parsed = $not . ft_termParser($Indexer, $matches[2], false, true);
749        } else {
750            // fix incomplete phrase
751            $term = str_replace('"', ' ', $term);
752
753            // fix parentheses
754            $term = str_replace(')', ' ) ', $term);
755            $term = str_replace('(', ' ( ', $term);
756            $term = str_replace('- (', ' -(', $term);
757
758            // treat pipe symbols as 'OR' operators
759            $term = str_replace('|', ' or ', $term);
760
761            // treat ideographic spaces (U+3000) as search term separators
762            // FIXME: some more separators?
763            $term = preg_replace('/[ \x{3000}]+/u', ' ', $term);
764            $term = trim($term);
765            if ($term === '') continue;
766
767            $tokens = explode(' ', $term);
768            foreach ($tokens as $token) {
769                if ($token === '(') {
770                    // parenthesis-include-open
771                    $parsed .= '(';
772                    ++$parens_level;
773                } elseif ($token === '-(') {
774                    // parenthesis-exclude-open
775                    $parsed .= 'NOT(';
776                    ++$parens_level;
777                } elseif ($token === ')') {
778                    // parenthesis-any-close
779                    if ($parens_level === 0) continue;
780                    $parsed .= ')';
781                    $parens_level--;
782                } elseif ($token === 'and') {
783                    // logical-and (do nothing)
784                } elseif ($token === 'or') {
785                    // logical-or
786                    $parsed .= 'OR';
787                } elseif (preg_match('/^(?:\^|-ns:)(.+)$/u', $token, $matches)) {
788                    // namespace-exclude
789                    $parsed .= 'NOT(N+:' . $matches[1] . ')';
790                } elseif (preg_match('/^(?:@|ns:)(.+)$/u', $token, $matches)) {
791                    // namespace-include
792                    $parsed .= '(N+:' . $matches[1] . ')';
793                } elseif (preg_match('/^-(.+)$/', $token, $matches)) {
794                    // word-exclude
795                    $parsed .= 'NOT(' . ft_termParser($Indexer, $matches[1]) . ')';
796                } else {
797                    // word-include
798                    $parsed .= ft_termParser($Indexer, $token);
799                }
800            }
801        }
802        $parsed_query .= $parsed;
803    }
804
805    // cleanup (very sensitive)
806    $parsed_query .= str_repeat(')', $parens_level);
807    do {
808        $parsed_query_old = $parsed_query;
809        $parsed_query = preg_replace('/(NOT)?\(\)/u', '', $parsed_query);
810    } while ($parsed_query !== $parsed_query_old);
811    $parsed_query = preg_replace('/(NOT|OR)+\)/u', ')', $parsed_query);
812    $parsed_query = preg_replace('/(OR)+/u', 'OR', $parsed_query);
813    $parsed_query = preg_replace('/\(OR/u', '(', $parsed_query);
814    $parsed_query = preg_replace('/^OR|OR$/u', '', $parsed_query);
815    $parsed_query = preg_replace('/\)(NOT)?\(/u', ')AND$1(', $parsed_query);
816
817    // adjustment: make highlightings right
818    $parens_level     = 0;
819    $notgrp_levels    = [];
820    $parsed_query_new = '';
821    $tokens = preg_split('/(NOT\(|[()])/u', $parsed_query, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
822    foreach ($tokens as $token) {
823        if ($token === 'NOT(') {
824            $notgrp_levels[] = ++$parens_level;
825        } elseif ($token === '(') {
826            ++$parens_level;
827        } elseif ($token === ')') {
828            if ($parens_level-- === end($notgrp_levels)) array_pop($notgrp_levels);
829        } elseif (count($notgrp_levels) % 2 === 1) {
830            // turn highlight-flag off if terms are logically in "NOT" group
831            $token = preg_replace('/([WPN])\+\:/u', '$1-:', $token);
832        }
833        $parsed_query_new .= $token;
834    }
835    $parsed_query = $parsed_query_new;
836
837    /**
838     * convert infix notation string into postfix (Reverse Polish notation) array
839     * by Shunting-yard algorithm
840     *
841     * see: http://en.wikipedia.org/wiki/Reverse_Polish_notation
842     * see: http://en.wikipedia.org/wiki/Shunting-yard_algorithm
843     */
844    $parsed_ary     = [];
845    $ope_stack      = [];
846    $ope_precedence = [')' => 1, 'OR' => 2, 'AND' => 3, 'NOT' => 4, '(' => 5];
847    $ope_regex      = '/([()]|OR|AND|NOT)/u';
848
849    $tokens = preg_split($ope_regex, $parsed_query, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
850    foreach ($tokens as $token) {
851        if (preg_match($ope_regex, $token)) {
852            // operator
853            $last_ope = end($ope_stack);
854            while ($last_ope !== false && $ope_precedence[$token] <= $ope_precedence[$last_ope] && $last_ope != '(') {
855                $parsed_ary[] = array_pop($ope_stack);
856                $last_ope = end($ope_stack);
857            }
858            if ($token == ')') {
859                array_pop($ope_stack); // this array_pop always deletes '('
860            } else {
861                $ope_stack[] = $token;
862            }
863        } else {
864            // operand
865            $token_decoded = str_replace(['OP', 'CP'], ['(', ')'], $token);
866            $parsed_ary[] = $token_decoded;
867        }
868    }
869    $parsed_ary = array_values([...$parsed_ary, ...array_reverse($ope_stack)]);
870
871    // cleanup: each double "NOT" in RPN array actually does nothing
872    $parsed_ary_count = count($parsed_ary);
873    for ($i = 1; $i < $parsed_ary_count; ++$i) {
874        if ($parsed_ary[$i] === 'NOT' && $parsed_ary[$i - 1] === 'NOT') {
875            unset($parsed_ary[$i], $parsed_ary[$i - 1]);
876        }
877    }
878    $parsed_ary = array_values($parsed_ary);
879
880    // build return value
881    $q = [];
882    $q['query']      = $query;
883    $q['parsed_str'] = $parsed_query;
884    $q['parsed_ary'] = $parsed_ary;
885
886    foreach ($q['parsed_ary'] as $token) {
887        if (strlen($token) < 3 || $token[2] !== ':') continue;
888        $body = substr($token, 3);
889
890        switch (substr($token, 0, 3)) {
891            case 'N+:':
892                     $q['ns'][]        = $body; // for backward compatibility
893                break;
894            case 'N-:':
895                     $q['notns'][]     = $body; // for backward compatibility
896                break;
897            case 'W_:':
898                     $q['words'][]     = $body;
899                break;
900            case 'W-:':
901                     $q['words'][]     = $body;
902                     $q['not'][]       = $body; // for backward compatibility
903                break;
904            case 'W+:':
905                     $q['words'][]     = $body;
906                     $q['highlight'][] = $body;
907                     $q['and'][]       = $body; // for backward compatibility
908                break;
909            case 'P-:':
910                     $q['phrases'][]   = $body;
911                break;
912            case 'P+:':
913                     $q['phrases'][]   = $body;
914                     $q['highlight'][] = $body;
915                break;
916        }
917    }
918    foreach (['words', 'phrases', 'highlight', 'ns', 'notns', 'and', 'not'] as $key) {
919        $q[$key] = empty($q[$key]) ? [] : array_values(array_unique($q[$key]));
920    }
921
922    return $q;
923}
924
925/**
926 * Transforms given search term into intermediate representation
927 *
928 * This function is used in ft_queryParser() and not for general purpose use.
929 *
930 * @author Kazutaka Miyasaka <kazmiya@gmail.com>
931 *
932 * @param Indexer $Indexer
933 * @param string                  $term
934 * @param bool                    $consider_asian
935 * @param bool                    $phrase_mode
936 * @return string
937 */
938function ft_termParser($Indexer, $term, $consider_asian = true, $phrase_mode = false)
939{
940    $parsed = '';
941    if ($consider_asian) {
942        // successive asian characters need to be searched as a phrase
943        $words = Asian::splitAsianWords($term);
944        foreach ($words as $word) {
945            $phrase_mode = $phrase_mode ? true : Asian::isAsianWords($word);
946            $parsed .= ft_termParser($Indexer, $word, false, $phrase_mode);
947        }
948    } else {
949        $term_noparen = str_replace(['(', ')'], ' ', $term);
950        $words = $Indexer->tokenizer($term_noparen, true);
951
952        // W_: no need to highlight
953        if (empty($words)) {
954            $parsed = '()'; // important: do not remove
955        } elseif ($words[0] === $term) {
956            $parsed = '(W+:' . $words[0] . ')';
957        } elseif ($phrase_mode) {
958            $term_encoded = str_replace(['(', ')'], ['OP', 'CP'], $term);
959            $parsed = '((W_:' . implode(')(W_:', $words) . ')(P+:' . $term_encoded . '))';
960        } else {
961            $parsed = '((W+:' . implode(')(W+:', $words) . '))';
962        }
963    }
964    return $parsed;
965}
966
967/**
968 * Recreate a search query string based on parsed parts, doesn't support negated phrases and `OR` searches
969 *
970 * @param array $and
971 * @param array $not
972 * @param array $phrases
973 * @param array $ns
974 * @param array $notns
975 *
976 * @return string
977 */
978function ft_queryUnparser_simple(array $and, array $not, array $phrases, array $ns, array $notns)
979{
980    $query = implode(' ', $and);
981    if ($not !== []) {
982        $query .= ' -' . implode(' -', $not);
983    }
984
985    if ($phrases !== []) {
986        $query .= ' "' . implode('" "', $phrases) . '"';
987    }
988
989    if ($ns !== []) {
990        $query .= ' @' . implode(' @', $ns);
991    }
992
993    if ($notns !== []) {
994        $query .= ' ^' . implode(' ^', $notns);
995    }
996
997    return $query;
998}
999
1000//Setup VIM: ex: et ts=4 :
1001