Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
37.93% covered (danger)
37.93%
55 / 145
20.00% covered (danger)
20.00%
4 / 20
CRAP
0.00% covered (danger)
0.00%
0 / 1
FeatureIndex
37.93% covered (danger)
37.93%
55 / 145
20.00% covered (danger)
20.00%
4 / 20
920.85
0.00% covered (danger)
0.00%
0 / 1
 getLimit
n/a
0 / 0
n/a
0 / 0
0
 queryOptions
n/a
0 / 0
n/a
0 / 0
0
 removeFromIndex
n/a
0 / 0
n/a
0 / 0
0
 __construct
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
1
 getPrimaryKeyColumns
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 canAnswer
0.00% covered (danger)
0.00%
0 / 10
0.00% covered (danger)
0.00%
0 / 1
30
 getSort
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 getOrder
0.00% covered (danger)
0.00%
0 / 3
0.00% covered (danger)
0.00%
0 / 1
12
 cachePurge
0.00% covered (danger)
0.00%
0 / 4
0.00% covered (danger)
0.00%
0 / 1
6
 onAfterInsert
0.00% covered (danger)
0.00%
0 / 5
0.00% covered (danger)
0.00%
0 / 1
6
 onAfterUpdate
0.00% covered (danger)
0.00%
0 / 15
0.00% covered (danger)
0.00%
0 / 1
30
 onAfterRemove
0.00% covered (danger)
0.00%
0 / 5
0.00% covered (danger)
0.00%
0 / 1
6
 onAfterLoad
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 onAfterClear
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 find
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
1
 findMulti
80.00% covered (warning)
80.00%
24 / 30
0.00% covered (danger)
0.00%
0 / 1
9.65
 filterResults
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 found
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 foundMulti
0.00% covered (danger)
0.00%
0 / 22
0.00% covered (danger)
0.00%
0 / 1
110
 getCacheKeys
70.00% covered (warning)
70.00%
7 / 10
0.00% covered (danger)
0.00%
0 / 1
3.24
 backingStoreFindMulti
0.00% covered (danger)
0.00%
0 / 10
0.00% covered (danger)
0.00%
0 / 1
20
 cacheKey
83.33% covered (warning)
83.33%
10 / 12
0.00% covered (danger)
0.00%
0 / 1
5.12
 cachedDbId
66.67% covered (warning)
66.67%
2 / 3
0.00% covered (danger)
0.00%
0 / 1
2.15
1<?php
2
3namespace Flow\Data\Index;
4
5use Flow\Data\Compactor;
6use Flow\Data\Compactor\FeatureCompactor;
7use Flow\Data\Compactor\ShallowCompactor;
8use Flow\Data\FlowObjectCache;
9use Flow\Data\Index;
10use Flow\Data\ObjectManager;
11use Flow\Data\ObjectMapper;
12use Flow\Data\ObjectStorage;
13use Flow\Exception\DataModelException;
14use Flow\Model\UUID;
15use MediaWiki\Json\FormatJson;
16use MediaWiki\WikiMap\WikiMap;
17
18/**
19 * Index objects with equal features($indexedColumns) into the same buckets.
20 */
21abstract class FeatureIndex implements Index {
22
23    /**
24     * @var FlowObjectCache
25     */
26    protected $cache;
27
28    /**
29     * @var ObjectStorage
30     */
31    protected $storage;
32
33    /**
34     * @var ObjectMapper
35     */
36    protected $mapper;
37
38    /**
39     * @var string
40     */
41    protected $prefix;
42
43    /**
44     * @var Compactor
45     */
46    protected $rowCompactor;
47
48    /**
49     * @var string[]
50     */
51    protected $indexed;
52
53    /**
54     * @var string[] The indexed columns in alphabetical order. This is
55     *  ordered so that cache keys can be generated in a stable manner.
56     */
57    protected $indexedOrdered;
58
59    /**
60     * @var array
61     */
62    protected $options;
63
64    /**
65     * @inheritDoc
66     */
67    abstract public function getLimit();
68
69    /**
70     * @return array The options used for querying self::$storage
71     */
72    abstract public function queryOptions();
73
74    /**
75     * @todo Similar, Could the cache key be passed in instead of $indexed?
76     * @param array $indexed The portion of $row that makes up the cache key
77     * @param array $row A single row of data to remove from its related feature bucket
78     */
79    abstract protected function removeFromIndex( array $indexed, array $row );
80
81    /**
82     * @param FlowObjectCache $cache
83     * @param ObjectStorage $storage
84     * @param ObjectMapper $mapper
85     * @param string $prefix Prefix to utilize for all cache keys
86     * @param string[] $indexedColumns List of columns to index
87     */
88    public function __construct( FlowObjectCache $cache, ObjectStorage $storage, ObjectMapper $mapper, $prefix, array $indexedColumns ) {
89        $this->cache = $cache;
90        $this->storage = $storage;
91        $this->mapper = $mapper;
92        $this->prefix = $prefix;
93        $this->rowCompactor = new FeatureCompactor( $indexedColumns );
94        $this->indexed = $indexedColumns;
95        // sort this and ksort in self::cacheKey to always have cache key
96        // fields in same order
97        sort( $indexedColumns );
98        $this->indexedOrdered = $indexedColumns;
99    }
100
101    /**
102     * @return string[] The list of columns to bucket database rows by in
103     *  the same order as provided to the constructor.
104     */
105    public function getPrimaryKeyColumns() {
106        return $this->indexed;
107    }
108
109    /**
110     * @inheritDoc
111     */
112    public function canAnswer( array $featureColumns, array $options ) {
113        sort( $featureColumns );
114        if ( $featureColumns !== $this->indexedOrdered ) {
115            return false;
116        }
117
118        // This can probably be moved to TopKIndex if it's not used
119        // by anything else.
120        if ( isset( $options['limit'] ) ) {
121            $max = $options['limit'];
122            if ( isset( $options['offset'] ) ) {
123                $max += $options['offset'];
124            }
125            if ( $max > $this->getLimit() ) {
126                return false;
127            }
128        }
129        return true;
130    }
131
132    /**
133     * Rows are first sorted based on the first term of the result, then ties
134     * are broken by evaluating the second term and so on.
135     *
136     * @return string[]|false The columns to sort by, or false if no sorting is defined
137     */
138    public function getSort() {
139        return $this->options['sort'] ?? false;
140    }
141
142    /**
143     * @inheritDoc
144     */
145    public function getOrder() {
146        if ( isset( $this->options['order'] ) && strtoupper( $this->options['order'] ) === 'ASC' ) {
147            return 'ASC';
148        } else {
149            return 'DESC';
150        }
151    }
152
153    /**
154     * Delete any feature bucket $object would be contained in from the cache
155     *
156     * @param object $object
157     * @param array $row
158     * @throws DataModelException
159     */
160    public function cachePurge( $object, array $row ) {
161        $indexed = ObjectManager::splitFromRow( $row, $this->indexed );
162        if ( !$indexed ) {
163            throw new DataModelException( 'Un-indexable row: ' . FormatJson::encode( $row ), 'process-data' );
164        }
165        // We don't want to just remove this object from the index, then the index would be incorrect.
166        // We want to delete the bucket that contains this object.
167        $this->cache->delete( $this->cacheKey( $indexed ) );
168    }
169
170    /**
171     * @inheritDoc
172     */
173    public function onAfterInsert( $object, array $new, array $metadata ) {
174        $indexed = ObjectManager::splitFromRow( $new, $this->indexed );
175        // is un-indexable a bail-worthy occasion? Probably not but makes debugging easier
176        if ( !$indexed ) {
177            throw new DataModelException( 'Un-indexable row: ' . FormatJson::encode( $new ), 'process-data' );
178        }
179        $compacted = $this->rowCompactor->compactRow( UUID::convertUUIDs( $new, 'alphadecimal' ) );
180        $this->removeFromIndex( $indexed, $compacted );
181    }
182
183    /**
184     * @inheritDoc
185     */
186    public function onAfterUpdate( $object, array $old, array $new, array $metadata ) {
187        $oldIndexed = ObjectManager::splitFromRow( $old, $this->indexed );
188        $newIndexed = ObjectManager::splitFromRow( $new, $this->indexed );
189        if ( !$oldIndexed ) {
190            throw new DataModelException( 'Un-indexable row: ' . FormatJson::encode( $oldIndexed ), 'process-data' );
191        }
192        if ( !$newIndexed ) {
193            throw new DataModelException( 'Un-indexable row: ' . FormatJson::encode( $newIndexed ), 'process-data' );
194        }
195        $oldCompacted = $this->rowCompactor->compactRow( UUID::convertUUIDs( $old, 'alphadecimal' ) );
196        $newCompacted = $this->rowCompactor->compactRow( UUID::convertUUIDs( $new, 'alphadecimal' ) );
197        $oldIndexedForComparison = UUID::convertUUIDs( $oldIndexed, 'alphadecimal' );
198        $newIndexedForComparison = UUID::convertUUIDs( $newIndexed, 'alphadecimal' );
199        if ( ObjectManager::arrayEquals( $oldIndexedForComparison, $newIndexedForComparison ) ) {
200            if ( ObjectManager::arrayEquals( $oldCompacted, $newCompacted ) ) {
201                // Nothing changed in the index
202                return;
203            }
204            // object representation in feature bucket has changed
205            $this->removeFromIndex( $oldIndexed, $oldCompacted );
206        } else {
207            // object has moved from one feature bucket to another
208            $this->removeFromIndex( $oldIndexed, $oldCompacted );
209        }
210    }
211
212    /**
213     * @inheritDoc
214     */
215    public function onAfterRemove( $object, array $old, array $metadata ) {
216        $indexed = ObjectManager::splitFromRow( $old, $this->indexed );
217        if ( !$indexed ) {
218            throw new DataModelException( 'Unindexable row: ' . FormatJson::encode( $old ), 'process-data' );
219        }
220        $compacted = $this->rowCompactor->compactRow( UUID::convertUUIDs( $old, 'alphadecimal' ) );
221        $this->removeFromIndex( $indexed, $compacted );
222    }
223
224    /**
225     * @inheritDoc
226     */
227    public function onAfterLoad( $object, array $old ) {
228        // nothing to do
229    }
230
231    /**
232     * @inheritDoc
233     */
234    public function onAfterClear() {
235        // nothing to do
236    }
237
238    /**
239     * @inheritDoc
240     */
241    public function find( array $attributes, array $options = [] ) {
242        $results = $this->findMulti( [ $attributes ], $options );
243        return reset( $results );
244    }
245
246    /**
247     * @inheritDoc
248     */
249    public function findMulti( array $queries, array $options = [] ) {
250        if ( !$queries ) {
251            return [];
252        }
253
254        // get cache keys for all queries
255        $cacheKeys = $this->getCacheKeys( $queries );
256
257        // retrieve from cache (only query duplicate queries once)
258        // $fromCache will be an array containing compacted results as value and
259        // cache keys as key
260        $fromCache = $this->cache->getMulti( array_unique( $cacheKeys ) );
261
262        // figure out what queries were resolved in cache
263        // $keysFromCache will be an array where values are cache keys and keys
264        // are the same index as their corresponding $queries
265        // (intersect with $cacheKeys to guarantee order)
266        $keysFromCache = array_intersect( $cacheKeys, array_keys( $fromCache ) );
267
268        // filter out all queries that have been resolved from cache and fetch
269        // them from storage
270        // $fromStorage will be an array containing (expanded) results as value
271        // and indexes matching $query as key
272        $storageQueries = array_diff_key( $queries, $keysFromCache );
273        $fromStorage = [];
274        if ( $storageQueries ) {
275            $fromStorage = $this->backingStoreFindMulti( $storageQueries );
276            foreach ( $fromStorage as $idx => $resultFromStorage ) {
277                $key = $this->cacheKey( $storageQueries[$idx] );
278                $this->cache->set( $key, $resultFromStorage );
279            }
280        }
281
282        $results = $fromStorage;
283
284        // $queries may have had duplicates that we've ignored to minimize
285        // cache requests - now re-duplicate values from cache & match the
286        // results against their respective original keys in $queries
287        foreach ( $keysFromCache as $index => $cacheKey ) {
288            $results[$index] = $fromCache[$cacheKey];
289        }
290
291        // now that we have all data, both from cache & backing storage, filter
292        // out all data we don't need
293        $results = $this->filterResults( $results, $options );
294
295        // if we have no data from cache, there's nothing left - quit early
296        if ( !$fromCache ) {
297            return $results;
298        }
299
300        // because we may have combined data from 2 different sources, chances
301        // are the order of the data is no longer in sync with the order
302        // $queries were in - fix that by replacing $queries values with
303        // the corresponding $results value
304        // note that there may be missing results, hence the intersect ;)
305        $order = array_intersect_key( $queries, $results );
306        $results = array_replace( $order, $results );
307
308        $keyToQuery = [];
309        foreach ( $keysFromCache as $index => $key ) {
310            // all redundant data has been stripped, now expand all cache values
311            // (we're only doing this now to avoid expanding redundant data)
312            $fromCache[$key] = $results[$index];
313
314            // to expand rows, we'll need the $query info mapped to the cache
315            // key instead of the $query index
316            if ( !isset( $keyToQuery[$key] ) ) {
317                $keyToQuery[$key] = $queries[$index];
318                $keyToQuery[$key] = UUID::convertUUIDs( $keyToQuery[$key], 'alphadecimal' );
319            }
320        }
321
322        // expand and replace the stubs in $results with complete data
323        $fromCache = $this->rowCompactor->expandCacheResult( $fromCache, $keyToQuery );
324        foreach ( $keysFromCache as $index => $cacheKey ) {
325            $results[$index] = $fromCache[$cacheKey];
326        }
327
328        return $results;
329    }
330
331    /**
332     * Get rid of unneeded, according to the given $options.
333     *
334     * This is used to strip entries before expanding them;
335     * basically, at that point, we may only have a list of ids, which we need
336     * to expand (= fetch from cache) - don't want to do this for more than
337     * what is needed
338     *
339     * @param array[] $results
340     * @param array $options
341     * @return array[]
342     */
343    protected function filterResults( array $results, array $options = [] ) {
344        // Overriden in TopKIndex
345        return $results;
346    }
347
348    /**
349     * Returns a boolean true/false if the find()-operation for the given
350     * attributes has already been resolves and doesn't need to query any
351     * outside cache/database.
352     * Determining if a find() has not yet been resolved may be useful so that
353     * additional data may be loaded at once.
354     *
355     * @param array $attributes Attributes to find()
356     * @param array $options Options to find()
357     * @return bool
358     */
359    public function found( array $attributes, array $options = [] ) {
360        return $this->foundMulti( [ $attributes ], $options );
361    }
362
363    /**
364     * Returns a boolean true/false if the findMulti()-operation for the given
365     * attributes has already been resolves and doesn't need to query any
366     * outside cache/database.
367     * Determining if a find() has not yet been resolved may be useful so that
368     * additional data may be loaded at once.
369     *
370     * @param array $queries Queries to findMulti()
371     * @param array $options Options to findMulti()
372     * @return bool
373     */
374    public function foundMulti( array $queries, array $options = [] ) {
375        if ( !$queries ) {
376            return true;
377        }
378
379        // get cache keys for all queries
380        $cacheKeys = $this->getCacheKeys( $queries );
381
382        // check if cache has a way of identifying what's stored locally
383        if ( !method_exists( $this->cache, 'has' ) ) {
384            return false;
385        }
386
387        // check if keys matching given queries are already known in local cache
388        foreach ( $cacheKeys as $key ) {
389            // @phan-suppress-next-line PhanUndeclaredMethod Checked with method_exists above
390            if ( !$this->cache->has( $key ) ) {
391                return false;
392            }
393        }
394
395        $keyToQuery = [];
396        foreach ( $cacheKeys as $i => $key ) {
397            // These results will be merged into the query results, and as such need binary
398            // uuid's as would be received from storage
399            if ( !isset( $keyToQuery[$key] ) ) {
400                $keyToQuery[$key] = $queries[$i];
401            }
402        }
403
404        // retrieve from cache - this is cheap, it's is local storage
405        $cached = $this->cache->getMulti( $cacheKeys );
406        foreach ( $cached as $i => $result ) {
407            $limit = $options['limit'] ?? $this->getLimit();
408            $cached[$i] = array_splice( $result, 0, $limit );
409        }
410
411        // if we have a shallow compactor, the returned data are PKs of objects
412        // that need to be fetched too
413        if ( $this->rowCompactor instanceof ShallowCompactor ) {
414            // test of the keys to be expanded are already in local cache
415            $duplicator = $this->rowCompactor->getResultDuplicator( $cached, $keyToQuery );
416            $queries = $duplicator->getUniqueQueries();
417            if ( !$this->rowCompactor->getShallow()->foundMulti( $queries ) ) {
418                return false;
419            }
420        }
421
422        return true;
423    }
424
425    /**
426     * Build a map from cache key to its index in $queries.
427     *
428     * @param array $queries
429     * @return array Array of [query index => cache key]
430     * @throws DataModelException
431     */
432    protected function getCacheKeys( $queries ) {
433        $idxToKey = [];
434        foreach ( $queries as $idx => $query ) {
435            ksort( $query );
436            if ( array_keys( $query ) !== $this->indexedOrdered ) {
437                throw new DataModelException(
438                    'Cannot answer query for columns: ' . implode( ', ', array_keys( $queries[$idx] ) ), 'process-data'
439                );
440            }
441            $key = $this->cacheKey( $query );
442            $idxToKey[$idx] = $key;
443        }
444
445        return $idxToKey;
446    }
447
448    /**
449     * Query persistent storage for data not found in cache.  Note that this
450     * does not use the query options because an individual bucket contents is
451     * based on constructor options, and not query options.  Query options merely
452     * change what part of the bucket is returned(or if the query has to fail over
453     * to direct from storage due to being beyond the set of cached values).
454     *
455     * @param array $queries
456     * @return array
457     */
458    protected function backingStoreFindMulti( array $queries ) {
459        // query backing store
460        $options = $this->queryOptions();
461        $stored = $this->storage->findMulti( $queries, $options );
462        $results = [];
463
464        // map store results to cache key
465        foreach ( $stored as $idx => $rows ) {
466            if ( !$rows ) {
467                // Nothing found,  should we cache failures as well as success?
468                continue;
469            }
470            $results[$idx] = $rows;
471            unset( $queries[$idx] );
472        }
473
474        if ( count( $queries ) !== 0 ) {
475            // Log something about not finding everything?
476        }
477
478        return $results;
479    }
480
481    /**
482     * Generate the cache key representing the attributes
483     * @param array $attributes
484     * @return string
485     */
486    protected function cacheKey( array $attributes ) {
487        global $wgFlowCacheVersion;
488        foreach ( $attributes as $key => $attr ) {
489            if ( $attr instanceof UUID ) {
490                $attributes[$key] = $attr->getAlphadecimal();
491            } elseif ( strlen( $attr ) === UUID::BIN_LEN && substr( $key, -3 ) === '_id' ) {
492                $attributes[$key] = UUID::create( $attr )->getAlphadecimal();
493            }
494        }
495
496        // values in $attributes may not always be in the exact same order,
497        // which would lead to differences in cache key if we don't force that
498        ksort( $attributes );
499
500        return $this->cache->makeGlobalKey(
501            $this->prefix,
502            self::cachedDbId(),
503            md5( implode( ':', $attributes ) ),
504            $wgFlowCacheVersion
505        );
506    }
507
508    /**
509     * @return string The id of the database being cached
510     */
511    public static function cachedDbId() {
512        global $wgFlowDefaultWikiDb;
513        if ( $wgFlowDefaultWikiDb === false ) {
514            return WikiMap::getCurrentWikiDbDomain()->getId();
515        } else {
516            return $wgFlowDefaultWikiDb;
517        }
518    }
519}