Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
Total | |
37.93% |
55 / 145 |
|
20.00% |
4 / 20 |
CRAP | |
0.00% |
0 / 1 |
FeatureIndex | |
37.93% |
55 / 145 |
|
20.00% |
4 / 20 |
920.85 | |
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% |
8 / 8 |
|
100.00% |
1 / 1 |
1 | |||
getPrimaryKeyColumns | |
100.00% |
1 / 1 |
|
100.00% |
1 / 1 |
1 | |||
canAnswer | |
0.00% |
0 / 10 |
|
0.00% |
0 / 1 |
30 | |||
getSort | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
2 | |||
getOrder | |
0.00% |
0 / 3 |
|
0.00% |
0 / 1 |
12 | |||
cachePurge | |
0.00% |
0 / 4 |
|
0.00% |
0 / 1 |
6 | |||
onAfterInsert | |
0.00% |
0 / 5 |
|
0.00% |
0 / 1 |
6 | |||
onAfterUpdate | |
0.00% |
0 / 15 |
|
0.00% |
0 / 1 |
30 | |||
onAfterRemove | |
0.00% |
0 / 5 |
|
0.00% |
0 / 1 |
6 | |||
onAfterLoad | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
2 | |||
onAfterClear | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
2 | |||
find | |
100.00% |
2 / 2 |
|
100.00% |
1 / 1 |
1 | |||
findMulti | |
80.00% |
24 / 30 |
|
0.00% |
0 / 1 |
9.65 | |||
filterResults | |
100.00% |
1 / 1 |
|
100.00% |
1 / 1 |
1 | |||
found | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
2 | |||
foundMulti | |
0.00% |
0 / 22 |
|
0.00% |
0 / 1 |
110 | |||
getCacheKeys | |
70.00% |
7 / 10 |
|
0.00% |
0 / 1 |
3.24 | |||
backingStoreFindMulti | |
0.00% |
0 / 10 |
|
0.00% |
0 / 1 |
20 | |||
cacheKey | |
83.33% |
10 / 12 |
|
0.00% |
0 / 1 |
5.12 | |||
cachedDbId | |
66.67% |
2 / 3 |
|
0.00% |
0 / 1 |
2.15 |
1 | <?php |
2 | |
3 | namespace Flow\Data\Index; |
4 | |
5 | use Flow\Data\Compactor; |
6 | use Flow\Data\Compactor\FeatureCompactor; |
7 | use Flow\Data\Compactor\ShallowCompactor; |
8 | use Flow\Data\FlowObjectCache; |
9 | use Flow\Data\Index; |
10 | use Flow\Data\ObjectManager; |
11 | use Flow\Data\ObjectMapper; |
12 | use Flow\Data\ObjectStorage; |
13 | use Flow\Exception\DataModelException; |
14 | use Flow\Model\UUID; |
15 | use MediaWiki\Json\FormatJson; |
16 | use MediaWiki\WikiMap\WikiMap; |
17 | |
18 | /** |
19 | * Index objects with equal features($indexedColumns) into the same buckets. |
20 | */ |
21 | abstract 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 | } |