Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
74.73% covered (warning)
74.73%
136 / 182
44.44% covered (danger)
44.44%
8 / 18
CRAP
0.00% covered (danger)
0.00%
0 / 1
SuggestBuilder
74.73% covered (warning)
74.73%
136 / 182
44.44% covered (danger)
44.44%
8 / 18
112.31
0.00% covered (danger)
0.00%
0 / 1
 __construct
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
1
 create
0.00% covered (danger)
0.00%
0 / 11
0.00% covered (danger)
0.00%
0 / 1
20
 build
78.38% covered (warning)
78.38%
29 / 37
0.00% covered (danger)
0.00%
0 / 1
14.71
 buildCrossNsSuggestions
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
2
 buildNormalSuggestions
90.91% covered (success)
90.91%
10 / 11
0.00% covered (danger)
0.00%
0 / 1
4.01
 getRequiredFields
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
2
 buildTitleSuggestion
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
2
 buildRedirectsSuggestion
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
2
 buildSuggestion
100.00% covered (success)
100.00%
22 / 22
100.00% covered (success)
100.00%
1 / 1
3
 trimForDistanceCheck
66.67% covered (warning)
66.67%
2 / 3
0.00% covered (danger)
0.00%
0 / 1
2.15
 extractTitleAndSimilarRedirects
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
4
 extractSimilars
94.74% covered (success)
94.74%
18 / 19
0.00% covered (danger)
0.00%
0 / 1
7.01
 distance
85.71% covered (warning)
85.71%
12 / 14
0.00% covered (danger)
0.00%
0 / 1
4.05
 encodeDocId
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 encodePossibleDocIds
0.00% covered (danger)
0.00%
0 / 4
0.00% covered (danger)
0.00%
0 / 1
2
 getBatchId
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 getTargetNamespace
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 fetchMaxDoc
0.00% covered (danger)
0.00%
0 / 16
0.00% covered (danger)
0.00%
0 / 1
20
1<?php
2
3namespace CirrusSearch\BuildDocument\Completion;
4
5use CirrusSearch\CirrusConfigNames;
6use CirrusSearch\Connection;
7use Elastica\Multi\Search as MultiSearch;
8use Elastica\Search;
9use MediaWiki\MediaWikiServices;
10
11/**
12 * Build a doc ready for the titlesuggest index.
13 *
14 * @license GPL-2.0-or-later
15 */
16
17/**
18 * Builder used to create suggester docs
19 * NOTE: Experimental
20 */
21class SuggestBuilder {
22    /**
23     * We limit the input to 50 chars the search requests
24     * It'll be used when searching to trim the input query
25     * and when determining close redirects
26     */
27    public const MAX_INPUT_LENGTH = 50;
28
29    /**
30     * The acceptable edit distance to group similar strings
31     */
32    private const GROUP_ACCEPTABLE_DISTANCE = 2;
33
34    /**
35     * Discount suggestions based on redirects
36     */
37    public const REDIRECT_DISCOUNT = 0.1;
38
39    /**
40     * Discount suggestions based on cross namespace redirects
41     */
42    public const CROSSNS_DISCOUNT = 0.005;
43
44    /**
45     * Redirect suggestion type
46     */
47    public const REDIRECT_SUGGESTION = 'r';
48
49    /**
50     * Title suggestion type
51     */
52    public const TITLE_SUGGESTION = 't';
53
54    /**
55     * Number of common prefix chars a redirect must share with the title to be
56     * promoted as a title suggestion.
57     * This is useful not to promote Eraq as a title suggestion for Iraq
58     * Less than 3 can lead to weird results like oba => Osama Bin Laden
59     */
60    private const REDIRECT_COMMON_PREFIX_LEN = 3;
61
62    /**
63     * @var SuggestScoringMethod the scoring function
64     */
65    private $scoringMethod;
66
67    /**
68     * @var int batch id
69     */
70    private $batchId;
71
72    /**
73     * @var ExtraSuggestionsBuilder[]
74     */
75    private $extraBuilders;
76
77    /**
78     * NOTE: Currently a fixed value because the completion suggester does not support
79     * multi namespace suggestion.
80     *
81     * @var int
82     */
83    private $targetNamespace = NS_MAIN;
84
85    /**
86     * @param SuggestScoringMethod $scoringMethod the scoring function to use
87     * @param ExtraSuggestionsBuilder[] $extraBuilders set of extra builders
88     */
89    public function __construct( SuggestScoringMethod $scoringMethod, array $extraBuilders = [] ) {
90        $this->scoringMethod = $scoringMethod;
91        $this->extraBuilders = $extraBuilders;
92        $this->batchId = time();
93    }
94
95    /**
96     * @param Connection $connection
97     * @param string|null $scoreMethodName
98     * @param string|null $indexBaseName
99     * @return self
100     * @throws \Exception
101     */
102    public static function create( Connection $connection, $scoreMethodName = null, $indexBaseName = null ): self {
103        $config  = $connection->getConfig();
104        $scoreMethodName = $scoreMethodName ?: $config->get( CirrusConfigNames::CompletionDefaultScore );
105        $scoreMethod = SuggestScoringMethodFactory::getScoringMethod( $scoreMethodName );
106
107        $extraBuilders = [];
108        if ( $config->get( CirrusConfigNames::CompletionSuggesterUseDefaultSort ) ) {
109            $extraBuilders[] = new DefaultSortSuggestionsBuilder();
110        }
111        $subPhrasesConfig = $config->get( CirrusConfigNames::CompletionSuggesterSubphrases );
112        if ( $subPhrasesConfig['build'] ) {
113            $extraBuilders[] = NaiveSubphrasesSuggestionsBuilder::create( $subPhrasesConfig );
114        }
115        $scoreMethod->setMaxDocs( self::fetchMaxDoc( $connection, $indexBaseName ) );
116        return new self( $scoreMethod, $extraBuilders );
117    }
118
119    /**
120     * @param array[] $inputDocs a batch of docs to build
121     * @param bool $explain
122     * @return \Generator|\Elastica\Document[] a set of suggest documents
123     */
124    public function build( $inputDocs, $explain = false ) {
125        $titleFactory = MediaWikiServices::getInstance()->getTitleFactory();
126        // Cross namespace titles
127        $crossNsTitles = [];
128        foreach ( $inputDocs as $sourceDoc ) {
129            $inputDoc = $sourceDoc['source'];
130            $docId = $sourceDoc['id'];
131            // a bit of a hack but it's convenient to carry
132            // the id around
133            $inputDoc['id'] = $docId;
134            if ( !isset( $inputDoc['namespace'] ) ) {
135                // Bad doc, nothing to do here.
136                continue;
137            }
138            if ( $inputDoc['namespace'] == $this->targetNamespace ) {
139                if ( !isset( $inputDoc['title'] ) ) {
140                    // Bad doc, nothing to do here.
141                    continue;
142                }
143                yield from $this->buildNormalSuggestions( $docId, $inputDoc, $explain );
144            } else {
145                if ( !isset( $inputDoc['redirect'] ) ) {
146                    // Bad doc, nothing to do here.
147                    continue;
148                }
149
150                foreach ( $inputDoc['redirect'] as $redir ) {
151                    if ( !isset( $redir['namespace'] ) || !isset( $redir['title'] ) ) {
152                        continue;
153                    }
154                    if ( $redir['namespace'] != $this->targetNamespace ) {
155                        continue;
156                    }
157                    $score = $this->scoringMethod->score( $inputDoc );
158                    // Discount the score of these suggestions.
159                    $score = (int)( $score * self::CROSSNS_DISCOUNT );
160                    $explainDetails = null;
161                    if ( $explain ) {
162                        // TODO: add explanation of the crossns discount
163                        $explainDetails = $this->scoringMethod->explain( $inputDoc );
164                    }
165
166                    $title = $titleFactory->makeTitle( $redir['namespace'], $redir['title'] );
167                    $crossNsTitles[] = [
168                        'title' => $title,
169                        'score' => $score,
170                        'text' => $redir['title'],
171                        'inputDoc' => $inputDoc,
172                        'explain' => $explainDetails,
173                    ];
174                }
175            }
176            if ( count( $crossNsTitles ) > 3000 ) {
177                yield from $this->buildCrossNsSuggestions( $crossNsTitles );
178                $crossNsTitles = [];
179            }
180        }
181
182        if ( $crossNsTitles ) {
183            yield from $this->buildCrossNsSuggestions( $crossNsTitles );
184        }
185    }
186
187    /**
188     * @param array[] $crossNsTitles
189     * @return \Generator|\Elastica\Document[]
190     */
191    private function buildCrossNsSuggestions( array $crossNsTitles ) {
192        $titles = array_column( $crossNsTitles, 'title' );
193        $lb = MediaWikiServices::getInstance()->getLinkBatchFactory()->newLinkBatch( $titles );
194        $lb->setCaller( __METHOD__ );
195        $lb->execute();
196        // This is far from perfect:
197        // - we won't try to group similar redirects since we don't know which one
198        // is the official one
199        // - we will certainly suggest multiple times the same pages
200        // - we must not run a second pass at query time: no redirect suggestion
201        foreach ( $crossNsTitles as $data ) {
202            $suggestion = [
203                'text' => $data['text'],
204                'variants' => []
205            ];
206            yield $this->buildTitleSuggestion( (string)$data['title']->getArticleID(), $suggestion,
207                $data['score'], $data['inputDoc'], $data['explain'] );
208        }
209    }
210
211    /**
212     * Build classic suggestion
213     *
214     * @param string $docId
215     * @param array $inputDoc
216     * @param bool $explain
217     * @return \Elastica\Document[] a set of suggest documents
218     */
219    private function buildNormalSuggestions( $docId, array $inputDoc, $explain = false ) {
220        if ( !isset( $inputDoc['title'] ) ) {
221            // Bad doc, nothing to do here.
222            return [];
223        }
224
225        $score = $this->scoringMethod->score( $inputDoc );
226        $explainDetails = null;
227        if ( $explain ) {
228            $explainDetails = $this->scoringMethod->explain( $inputDoc );
229        }
230
231        $suggestions = $this->extractTitleAndSimilarRedirects( $inputDoc );
232
233        $docs = [ $this->buildTitleSuggestion( $docId, $suggestions['group'], $score, $inputDoc, $explainDetails ) ];
234        if ( !empty( $suggestions['candidates'] ) ) {
235            $docs[] = $this->buildRedirectsSuggestion( $docId, $suggestions['candidates'], $score, $inputDoc, $explainDetails );
236        }
237        return $docs;
238    }
239
240    /**
241     * The fields needed to build and score documents.
242     *
243     * @return string[] the list of fields
244     */
245    public function getRequiredFields() {
246        $fields = $this->scoringMethod->getRequiredFields();
247        $fields = array_merge( $fields, [ 'title', 'redirect', 'namespace' ] );
248        foreach ( $this->extraBuilders as $extraBuilder ) {
249            $fields = array_merge( $fields, $extraBuilder->getRequiredFields() );
250        }
251        return array_values( array_unique( $fields ) );
252    }
253
254    /**
255     * Builds the 'title' suggestion.
256     *
257     * @param string $docId the page id
258     * @param array $title the title in 'text' and an array of similar redirects in 'variants'
259     * @param int $score the weight of the suggestion
260     * @param mixed[] $inputDoc
261     * @param array|null $scoreExplanation
262     * @return \Elastica\Document the suggestion document
263     */
264    private function buildTitleSuggestion( $docId, array $title, $score, array $inputDoc, ?array $scoreExplanation = null ) {
265        $inputs = [ $title['text'] ];
266        foreach ( $title['variants'] as $variant ) {
267            $inputs[] = $variant;
268        }
269        return $this->buildSuggestion(
270            self::TITLE_SUGGESTION,
271            $docId,
272            $inputs,
273            $score,
274            $inputDoc,
275            $scoreExplanation
276        );
277    }
278
279    /**
280     * Builds the 'redirects' suggestion.
281     * The score will be discounted by the REDIRECT_DISCOUNT factor.
282     * NOTE: the client will have to fetch the doc redirects when searching
283     * and choose the best one to display. This is because we are unable
284     * to make this decision at index time.
285     *
286     * @param string $docId the elasticsearch document id
287     * @param string[] $redirects
288     * @param int $score the weight of the suggestion
289     * @param mixed[] $inputDoc
290     * @param array|null $scoreExplanation
291     * @return \Elastica\Document the suggestion document
292     */
293    private function buildRedirectsSuggestion( $docId, array $redirects, $score, array $inputDoc, ?array $scoreExplanation = null ) {
294        $inputs = [];
295        foreach ( $redirects as $redirect ) {
296            $inputs[] = $redirect;
297        }
298        // TODO: add redirect discount explanation
299        $score = (int)( $score * self::REDIRECT_DISCOUNT );
300        return $this->buildSuggestion( self::REDIRECT_SUGGESTION, $docId, $inputs,
301            $score, $inputDoc, $scoreExplanation );
302    }
303
304    /**
305     * Builds a suggestion document.
306     *
307     * @param string $suggestionType suggestion type (title or redirect)
308     * @param string $docId The document id
309     * @param string[] $inputs the suggestion inputs
310     * @param int $score the weight of the suggestion
311     * @param mixed[] $inputDoc
312     * @param array|null $scoreExplanation
313     * @return \Elastica\Document a doc ready to be indexed in the completion suggester
314     */
315    private function buildSuggestion( $suggestionType, $docId, array $inputs, $score, array $inputDoc, ?array $scoreExplanation = null ) {
316        $doc = [
317            'batch_id' => $this->batchId,
318            'source_doc_id' => $inputDoc['id'],
319            'target_title' => [
320                'title' => $inputDoc['title'],
321                'namespace' => $inputDoc['namespace'],
322            ],
323            'suggest' => [
324                'input' => $inputs,
325                'weight' => $score
326            ],
327            'suggest-stop' => [
328                'input' => $inputs,
329                'weight' => $score
330            ]
331        ];
332
333        $suggestDoc = new \Elastica\Document( self::encodeDocId( $suggestionType, $docId ), $doc );
334        foreach ( $this->extraBuilders as $builder ) {
335            $builder->build( $inputDoc, $suggestionType, $score, $suggestDoc, $this->targetNamespace );
336        }
337        if ( $scoreExplanation !== null ) {
338            $suggestDoc->set( 'score_explanation', $scoreExplanation );
339        }
340        return $suggestDoc;
341    }
342
343    /**
344     * @param string $input A page title
345     * @return string A page title short enough to not cause indexing
346     *  issues.
347     */
348    public function trimForDistanceCheck( $input ) {
349        if ( mb_strlen( $input ) > self::MAX_INPUT_LENGTH ) {
350            $input = mb_substr( $input, 0, self::MAX_INPUT_LENGTH );
351        }
352        return $input;
353    }
354
355    /**
356     * Extracts title with redirects that are very close.
357     * It will allow to make one suggestion with title as the
358     * output and title + similar redirects as the inputs.
359     * It can be useful to avoid displaying redirects created to
360     * to handle typos.
361     *
362     * e.g. :
363     *   title: Giraffe
364     *   redirects: Girafe, Girraffe, Mating Giraffes
365     * will output
366     *   - 'group' : { 'text': 'Giraffe', 'variants': ['Girafe', 'Girraffe'] }
367     *   - 'candidates' : ['Mating Giraffes']
368     *
369     * It would be nice to do this for redirects but we have no way to decide
370     * which redirect is a typo and this technique would simply take the first
371     * redirect in the list.
372     *
373     * @param array $doc
374     * @return array mixed 'group' key contains the group with the
375     *         lead and its variants and 'candidates' contains the remaining
376     *         candidates that were not close enough to $groupHead.
377     */
378    public function extractTitleAndSimilarRedirects( array $doc ) {
379        $redirects = [];
380        if ( isset( $doc['redirect'] ) ) {
381            foreach ( $doc['redirect'] as $redir ) {
382                // Avoid suggesting/displaying non existent titles
383                // in the target namespace
384                if ( $redir['namespace'] == $this->targetNamespace ) {
385                    $redirects[] = $redir['title'];
386                }
387            }
388        }
389        return $this->extractSimilars( $doc['title'], $redirects, true );
390    }
391
392    /**
393     * Extracts from $candidates the values that are "similar" to $groupHead
394     *
395     * @param string $groupHead
396     * @param string[] $candidates
397     * @param bool $checkVariants if the candidate does not match the groupHead try to match a variant
398     * @return array 'group' key contains the group with the
399     *         head and its variants and 'candidates' contains the remaining
400     *         candidates that were not close enough to $groupHead.
401     */
402    private function extractSimilars( $groupHead, array $candidates, $checkVariants = false ) {
403        $group = [
404            'text' => $groupHead,
405            'variants' => []
406        ];
407        $newCandidates = [];
408        foreach ( $candidates as $c ) {
409            $distance = $this->distance( $groupHead, $c );
410            if ( $distance > self::GROUP_ACCEPTABLE_DISTANCE && $checkVariants ) {
411                // Run a second pass over the variants
412                foreach ( $group['variants'] as $v ) {
413                    $distance = $this->distance( $v, $c );
414                    if ( $distance <= self::GROUP_ACCEPTABLE_DISTANCE ) {
415                        break;
416                    }
417                }
418            }
419            if ( $distance <= self::GROUP_ACCEPTABLE_DISTANCE ) {
420                $group['variants'][] = $c;
421            } else {
422                $newCandidates[] = $c;
423            }
424        }
425
426        return [
427            'group' => $group,
428            'candidates' => $newCandidates
429        ];
430    }
431
432    /**
433     * Computes the edit distance between $a and $b.
434     *
435     * @param string $a
436     * @param string $b
437     * @return int the edit distance between a and b
438     */
439    private function distance( $a, $b ) {
440        $a = $this->trimForDistanceCheck( $a );
441        $b = $this->trimForDistanceCheck( $b );
442        $a = mb_strtolower( $a );
443        $b = mb_strtolower( $b );
444
445        $aLength = mb_strlen( $a );
446        $bLength = mb_strlen( $b );
447
448        $commonPrefixLen = self::REDIRECT_COMMON_PREFIX_LEN;
449
450        if ( $aLength < $commonPrefixLen ) {
451            $commonPrefixLen = $aLength;
452        }
453        if ( $bLength < $commonPrefixLen ) {
454            $commonPrefixLen = $bLength;
455        }
456
457        // check the common prefix
458        if ( mb_substr( $a, 0, $commonPrefixLen ) != mb_substr( $b, 0, $commonPrefixLen ) ) {
459            return PHP_INT_MAX;
460        }
461
462        // TODO: switch to a ratio instead of raw distance would help to group
463        // longer strings
464        return levenshtein( $a, $b );
465    }
466
467    /**
468     * Encode the suggestion doc id
469     * @param string $suggestionType
470     * @param string $docId
471     * @return string
472     */
473    public static function encodeDocId( $suggestionType, $docId ) {
474        return $docId . $suggestionType;
475    }
476
477    /**
478     * Encode possible docIds used by the completion suggester index
479     *
480     * @param string $docId
481     * @return string[] list of docIds
482     */
483    public static function encodePossibleDocIds( $docId ) {
484        return [
485            self::encodeDocId( self::TITLE_SUGGESTION, $docId ),
486            self::encodeDocId( self::REDIRECT_SUGGESTION, $docId ),
487        ];
488    }
489
490    /**
491     * @return int the batchId
492     */
493    public function getBatchId() {
494        return $this->batchId;
495    }
496
497    /**
498     * @return int the target namespace
499     */
500    public function getTargetNamespace() {
501        return $this->targetNamespace;
502    }
503
504    /**
505     * @param Connection $connection
506     * @param string|null $indexBaseName
507     * @return int
508     */
509    private static function fetchMaxDoc( Connection $connection, $indexBaseName = null ) {
510        // Indices to use for counting max_docs used by scoring functions
511        // Since we work mostly on the content namespace it seems OK to count
512        // only docs in the CONTENT index.
513        $countIndices = [ Connection::CONTENT_INDEX_SUFFIX ];
514
515        $indexBaseName = $indexBaseName ?: $connection->getConfig()->get( CirrusConfigNames::IndexBaseName );
516
517        // Run a first query to count the number of docs.
518        // This is needed for the scoring methods that need
519        // to normalize values against wiki size.
520        $mSearch = new MultiSearch( $connection->getClient() );
521        foreach ( $countIndices as $sourceIndexSuffix ) {
522            $search = new Search( $connection->getClient() );
523            $search->addIndex(
524                $connection->getIndex( $indexBaseName, $sourceIndexSuffix )
525            );
526            $search->getQuery()->setSize( 0 );
527            $search->getQuery()->setTrackTotalHits( true );
528            $mSearch->addSearch( $search );
529        }
530
531        $mSearchRes = $mSearch->search();
532        $total = 0;
533        foreach ( $mSearchRes as $res ) {
534            $total += $res->getTotalHits();
535        }
536        return $total;
537    }
538}