Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
Total | |
46.60% |
96 / 206 |
|
23.53% |
4 / 17 |
CRAP | |
0.00% |
0 / 1 |
TreeRepository | |
46.60% |
96 / 206 |
|
23.53% |
4 / 17 |
447.02 | |
0.00% |
0 / 1 |
__construct | |
100.00% |
2 / 2 |
|
100.00% |
1 / 1 |
1 | |||
cacheKey | |
100.00% |
1 / 1 |
|
100.00% |
1 / 1 |
1 | |||
insert | |
96.49% |
55 / 57 |
|
0.00% |
0 / 1 |
9 | |||
deleteSubtreeCache | |
100.00% |
3 / 3 |
|
100.00% |
1 / 1 |
2 | |||
delete | |
0.00% |
0 / 14 |
|
0.00% |
0 / 1 |
2 | |||
findParent | |
0.00% |
0 / 2 |
|
0.00% |
0 / 1 |
2 | |||
findRootPaths | |
89.19% |
33 / 37 |
|
0.00% |
0 / 1 |
9.10 | |||
findRootPath | |
100.00% |
2 / 2 |
|
100.00% |
1 / 1 |
1 | |||
findRoots | |
0.00% |
0 / 7 |
|
0.00% |
0 / 1 |
12 | |||
findRoot | |
0.00% |
0 / 5 |
|
0.00% |
0 / 1 |
6 | |||
fetchSubtreeIdentityMap | |
0.00% |
0 / 21 |
|
0.00% |
0 / 1 |
72 | |||
fetchSubtree | |
0.00% |
0 / 4 |
|
0.00% |
0 / 1 |
6 | |||
fetchFullTree | |
0.00% |
0 / 1 |
|
0.00% |
0 / 1 |
2 | |||
fetchSubtreeNodeList | |
0.00% |
0 / 10 |
|
0.00% |
0 / 1 |
6 | |||
fetchSubtreeNodeListFromDb | |
0.00% |
0 / 14 |
|
0.00% |
0 / 1 |
6 | |||
fetchParentMap | |
0.00% |
0 / 6 |
|
0.00% |
0 / 1 |
2 | |||
fetchParentMapFromDb | |
0.00% |
0 / 20 |
|
0.00% |
0 / 1 |
30 |
1 | <?php |
2 | |
3 | namespace Flow\Repository; |
4 | |
5 | use Flow\Data\FlowObjectCache; |
6 | use Flow\Data\ObjectManager; |
7 | use Flow\DbFactory; |
8 | use Flow\Exception\DataModelException; |
9 | use Flow\Model\UUID; |
10 | use Wikimedia\Rdbms\DBQueryError; |
11 | |
12 | /* |
13 | * In SQL |
14 | * |
15 | * CREATE TABLE flow_tree_node ( |
16 | * descendant DECIMAL(39) UNSIGNED NOT NULL, |
17 | * ancestor DECIMAL(39) UNSIGNED NULL, |
18 | * depth SMALLINT UNSIGNED NOT NULL, |
19 | * PRIMARY KEY ( ancestor, descendant ), |
20 | * UNIQUE KEY ( descendant, depth ) |
21 | * ); |
22 | * |
23 | * In Memcache |
24 | * |
25 | * flow:tree:subtree:<descendant> |
26 | * flow:tree:rootpath:<descendant> |
27 | * flow:tree:parent:<descendant> - should we just use rootpath? |
28 | * |
29 | * Not sure how to handle topic splits with caching yet, i can imagine |
30 | * a number of potential race conditions for writing root paths and sub trees |
31 | * during a topic split |
32 | */ |
33 | class TreeRepository { |
34 | |
35 | /** |
36 | * @var string |
37 | */ |
38 | protected $tableName = 'flow_tree_node'; |
39 | |
40 | /** |
41 | * @var DbFactory |
42 | */ |
43 | protected $dbFactory; |
44 | |
45 | /** |
46 | * @var FlowObjectCache |
47 | */ |
48 | protected $cache; |
49 | |
50 | /** |
51 | * @param DbFactory $dbFactory Factory to source connection objects from |
52 | * @param FlowObjectCache $cache |
53 | */ |
54 | public function __construct( DbFactory $dbFactory, FlowObjectCache $cache ) { |
55 | $this->dbFactory = $dbFactory; |
56 | $this->cache = $cache; |
57 | } |
58 | |
59 | /** |
60 | * A helper function to generate cache keys for tree repository |
61 | * @param string $treeType |
62 | * @param UUID $uuid |
63 | * @return string |
64 | */ |
65 | protected function cacheKey( $treeType, UUID $uuid ) { |
66 | return TreeCacheKey::build( $treeType, $uuid ); |
67 | } |
68 | |
69 | /** |
70 | * Insert a new tree node. If ancestor === null then this node is a root. |
71 | * |
72 | * Also delete cache entries related to this tree. |
73 | * @param UUID $descendant |
74 | * @param UUID|null $ancestor |
75 | * @return true |
76 | * @throws DataModelException |
77 | */ |
78 | public function insert( UUID $descendant, UUID $ancestor = null ) { |
79 | $this->cache->delete( $this->cacheKey( 'subtree', $descendant ) ); |
80 | $this->cache->delete( $this->cacheKey( 'parent', $descendant ) ); |
81 | $this->cache->delete( $this->cacheKey( 'rootpath', $descendant ) ); |
82 | |
83 | if ( $ancestor === null ) { |
84 | $path = [ $descendant ]; |
85 | } else { |
86 | $path = $this->findRootPath( $ancestor ); |
87 | $path[] = $descendant; |
88 | } |
89 | $this->deleteSubtreeCache( $descendant, $path ); |
90 | |
91 | $dbw = $this->dbFactory->getDB( DB_PRIMARY ); |
92 | $dbw->newInsertQueryBuilder() |
93 | ->insertInto( $this->tableName ) |
94 | ->row( [ |
95 | 'tree_descendant_id' => $descendant->getBinary(), |
96 | 'tree_ancestor_id' => $descendant->getBinary(), |
97 | 'tree_depth' => 0, |
98 | ] ) |
99 | ->caller( __METHOD__ ) |
100 | ->execute(); |
101 | |
102 | $ok = true; |
103 | if ( $ancestor !== null ) { |
104 | try { |
105 | if ( defined( 'MW_PHPUNIT_TEST' ) && $dbw->getType() == 'mysql' ) { |
106 | /* |
107 | * Combination of MW unit tests + MySQL DB is known to cause |
108 | * query failures of code 1137, so instead of executing a |
109 | * known bad query, let's just consider it failed right away |
110 | * (and let catch statement deal with it) |
111 | */ |
112 | throw new DBQueryError( $dbw, 'Prevented execution of known bad query', 1137, '', __METHOD__ ); |
113 | } |
114 | |
115 | $dbw->insertSelect( |
116 | $this->tableName, |
117 | $this->tableName, |
118 | [ |
119 | 'tree_descendant_id' => $dbw->addQuotes( $descendant->getBinary() ), |
120 | 'tree_ancestor_id' => 'tree_ancestor_id', |
121 | 'tree_depth' => 'tree_depth + 1', |
122 | ], |
123 | [ |
124 | 'tree_descendant_id' => $ancestor->getBinary(), |
125 | ], |
126 | __METHOD__ |
127 | ); |
128 | } catch ( DBQueryError $e ) { |
129 | /* |
130 | * insertSelect won't work on temporary tables (as used for MW |
131 | * unit tests), because it refers to the same table twice, in |
132 | * one query. |
133 | * In this case, we'll do a separate select & insert. This used |
134 | * to always be detected via the DBQueryError, but it can also |
135 | * return false from insertSelect. |
136 | * |
137 | * @see https://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html |
138 | * @see http://dba.stackexchange.com/questions/45270/mysql-error-1137-hy000-at-line-9-cant-reopen-table-temp-table |
139 | */ |
140 | if ( $e->errno === 1137 ) { |
141 | $rows = $dbw->newSelectQueryBuilder() |
142 | ->select( [ 'tree_depth', 'tree_ancestor_id' ] ) |
143 | ->from( $this->tableName ) |
144 | ->where( [ 'tree_descendant_id' => $ancestor->getBinary() ] ) |
145 | ->caller( __METHOD__ ) |
146 | ->fetchResultSet(); |
147 | |
148 | foreach ( $rows as $row ) { |
149 | $dbw->newInsertQueryBuilder() |
150 | ->insertInto( $this->tableName ) |
151 | ->row( [ |
152 | 'tree_descendant_id' => $descendant->getBinary(), |
153 | 'tree_ancestor_id' => $row->tree_ancestor_id, |
154 | 'tree_depth' => $row->tree_depth + 1, |
155 | ] ) |
156 | ->caller( __METHOD__ ) |
157 | ->execute(); |
158 | } |
159 | } else { |
160 | $ok = false; |
161 | } |
162 | } |
163 | } |
164 | |
165 | if ( !$ok ) { |
166 | throw new DataModelException( 'Failed inserting new tree node', 'process-data' ); |
167 | } |
168 | |
169 | return true; |
170 | } |
171 | |
172 | protected function deleteSubtreeCache( UUID $descendant, array $rootPath ) { |
173 | foreach ( $rootPath as $subtreeRoot ) { |
174 | $cacheKey = $this->cacheKey( 'subtree', $subtreeRoot ); |
175 | $this->cache->delete( $cacheKey ); |
176 | } |
177 | } |
178 | |
179 | /** |
180 | * Deletes a descendant from the tree repo. |
181 | * |
182 | * @param UUID $descendant |
183 | */ |
184 | public function delete( UUID $descendant ) { |
185 | $dbw = $this->dbFactory->getDB( DB_PRIMARY ); |
186 | $dbw->newDeleteQueryBuilder() |
187 | ->deleteFrom( $this->tableName ) |
188 | ->where( [ |
189 | 'tree_descendant_id' => $descendant->getBinary(), |
190 | ] ) |
191 | ->caller( __METHOD__ ) |
192 | ->execute(); |
193 | |
194 | $subtreeKey = $this->cacheKey( 'subtree', $descendant ); |
195 | $parentKey = $this->cacheKey( 'parent', $descendant ); |
196 | $pathKey = $this->cacheKey( 'rootpath', $descendant ); |
197 | |
198 | $this->cache->delete( $subtreeKey ); |
199 | $this->cache->delete( $parentKey ); |
200 | $this->cache->delete( $pathKey ); |
201 | } |
202 | |
203 | public function findParent( UUID $descendant ) { |
204 | $map = $this->fetchParentMap( [ $descendant ] ); |
205 | return $map[$descendant->getAlphadecimal()] ?? null; |
206 | } |
207 | |
208 | /** |
209 | * Given a list of nodes, find the path from each node to the root of its tree. |
210 | * the root must be the first element of the array, $node must be the last element. |
211 | * @param UUID[] $descendants Array of UUID objects to find the root paths for. |
212 | * @return UUID[][] Associative array, key is the post ID in hex, value is the path as an array. |
213 | */ |
214 | public function findRootPaths( array $descendants ) { |
215 | // alphadecimal => cachekey |
216 | $cacheKeys = []; |
217 | // alphadecimal => cache result ( distance => parent uuid obj ) |
218 | $cacheValues = []; |
219 | // list of binary values for db query |
220 | $missingValues = []; |
221 | // alphadecimal => distance => parent uuid obj |
222 | $paths = []; |
223 | |
224 | foreach ( $descendants as $descendant ) { |
225 | $cacheKeys[$descendant->getAlphadecimal()] = $this->cacheKey( 'rootpath', $descendant ); |
226 | } |
227 | |
228 | $cacheResult = $this->cache->getMulti( array_values( $cacheKeys ) ); |
229 | foreach ( $descendants as $descendant ) { |
230 | $alpha = $descendant->getAlphadecimal(); |
231 | if ( isset( $cacheResult[$cacheKeys[$alpha]] ) ) { |
232 | $cacheValues[$alpha] = $cacheResult[$cacheKeys[$alpha]]; |
233 | } else { |
234 | $missingValues[] = $descendant->getBinary(); |
235 | $paths[$alpha] = []; |
236 | } |
237 | } |
238 | |
239 | if ( !count( $missingValues ) ) { |
240 | return $cacheValues; |
241 | } |
242 | |
243 | $dbr = $this->dbFactory->getDB( DB_REPLICA ); |
244 | $res = $dbr->newSelectQueryBuilder() |
245 | ->select( [ 'tree_descendant_id', 'tree_ancestor_id', 'tree_depth' ] ) |
246 | ->from( $this->tableName ) |
247 | ->where( [ |
248 | 'tree_descendant_id' => $missingValues, |
249 | ] ) |
250 | ->caller( __METHOD__ ) |
251 | ->fetchResultSet(); |
252 | |
253 | if ( $res->numRows() === 0 ) { |
254 | return $cacheValues; |
255 | } |
256 | |
257 | foreach ( $res as $row ) { |
258 | $alpha = UUID::create( $row->tree_descendant_id )->getAlphadecimal(); |
259 | $paths[$alpha][$row->tree_depth] = UUID::create( $row->tree_ancestor_id ); |
260 | } |
261 | |
262 | foreach ( $paths as $descendantId => &$path ) { |
263 | if ( !$path ) { |
264 | $path = null; |
265 | continue; |
266 | } |
267 | |
268 | // sort by reverse distance, so furthest away |
269 | // parent (root) is at position 0. |
270 | ksort( $path ); |
271 | $path = array_reverse( $path ); |
272 | |
273 | $this->cache->set( $cacheKeys[$descendantId], $path ); |
274 | } |
275 | |
276 | return $paths + $cacheValues; |
277 | } |
278 | |
279 | /** |
280 | * Finds the root path for a single post ID. |
281 | * @param UUID $descendant Post ID |
282 | * @return UUID[]|null Path to the root of that node. |
283 | */ |
284 | public function findRootPath( UUID $descendant ) { |
285 | $paths = $this->findRootPaths( [ $descendant ] ); |
286 | |
287 | return $paths[$descendant->getAlphadecimal()] ?? null; |
288 | } |
289 | |
290 | /** |
291 | * Finds the root posts of a list of posts. |
292 | * @param UUID[] $descendants Array of PostRevision objects to find roots for. |
293 | * @return UUID[] Associative array of post ID (as hex) to UUID object representing its root. |
294 | */ |
295 | public function findRoots( array $descendants ) { |
296 | $paths = $this->findRootPaths( $descendants ); |
297 | $roots = []; |
298 | |
299 | foreach ( $descendants as $descendant ) { |
300 | $alpha = $descendant->getAlphadecimal(); |
301 | if ( isset( $paths[$alpha] ) ) { |
302 | $roots[$alpha] = $paths[$alpha][0]; |
303 | } |
304 | } |
305 | |
306 | return $roots; |
307 | } |
308 | |
309 | /** |
310 | * Given a specific child node find the associated root node |
311 | * |
312 | * @param UUID $descendant |
313 | * @return UUID |
314 | * @throws DataModelException |
315 | */ |
316 | public function findRoot( UUID $descendant ) { |
317 | // To simplify caching we will work through the root path instead |
318 | // of caching our own value |
319 | $path = $this->findRootPath( $descendant ); |
320 | if ( !$path ) { |
321 | throw new DataModelException( $descendant->getAlphadecimal() . ' has no root post. Probably is a root post.', 'process-data' ); |
322 | } |
323 | |
324 | $root = array_shift( $path ); |
325 | |
326 | return $root; |
327 | } |
328 | |
329 | /** |
330 | * Fetch a node and all its descendants. Children are returned in the |
331 | * same order they were inserted. |
332 | * |
333 | * @param UUID|UUID[] $roots |
334 | * @return array Multi-dimensional tree. The top level is a map from the uuid of a node |
335 | * to attributes about that node. The top level contains not just the parents, but all nodes |
336 | * within this tree. Within each node there is a 'children' key that contains a map from |
337 | * the child uuid's to references back to the top level of this identity map. As such this |
338 | * result can be read either as a list or a tree. |
339 | * @throws DataModelException When invalid data is received from self::fetchSubtreeNodeList |
340 | */ |
341 | public function fetchSubtreeIdentityMap( $roots ) { |
342 | $roots = ObjectManager::makeArray( $roots ); |
343 | if ( !$roots ) { |
344 | return []; |
345 | } |
346 | $nodes = $this->fetchSubtreeNodeList( $roots ); |
347 | if ( !$nodes ) { |
348 | throw new DataModelException( |
349 | 'subtree node list should have at least returned root: ' . implode( ', ', $roots ), |
350 | 'process-data' |
351 | ); |
352 | } elseif ( count( $nodes ) === 1 ) { |
353 | $parentMap = $this->fetchParentMap( reset( $nodes ) ); |
354 | } else { |
355 | $parentMap = $this->fetchParentMap( array_merge( ...array_values( $nodes ) ) ); |
356 | } |
357 | $identityMap = []; |
358 | foreach ( $parentMap as $child => $parent ) { |
359 | if ( !array_key_exists( $child, $identityMap ) ) { |
360 | $identityMap[$child] = [ 'children' => [] ]; |
361 | } |
362 | // Root nodes have no parent |
363 | if ( $parent !== null ) { |
364 | $identityMap[$parent->getAlphadecimal()]['children'][$child] =& $identityMap[$child]; |
365 | } |
366 | } |
367 | foreach ( array_keys( $identityMap ) as $parent ) { |
368 | ksort( $identityMap[$parent]['children'] ); |
369 | } |
370 | |
371 | return $identityMap; |
372 | } |
373 | |
374 | public function fetchSubtree( UUID $root ) { |
375 | $identityMap = $this->fetchSubtreeIdentityMap( $root ); |
376 | if ( !isset( $identityMap[$root->getAlphadecimal()] ) ) { |
377 | throw new DataModelException( 'No root exists in the identityMap', 'process-data' ); |
378 | } |
379 | |
380 | return $identityMap[$root->getAlphadecimal()]; |
381 | } |
382 | |
383 | public function fetchFullTree( UUID $nodeId ) { |
384 | return $this->fetchSubtree( $this->findRoot( $nodeId ) ); |
385 | } |
386 | |
387 | /** |
388 | * Return the id's of all nodes which are a descendant of provided roots |
389 | * |
390 | * @param UUID[] $roots |
391 | * @return array map from root id to its descendant list |
392 | * @throws \Flow\Exception\InvalidInputException |
393 | */ |
394 | public function fetchSubtreeNodeList( array $roots ) { |
395 | $list = new MultiGetList( $this->cache ); |
396 | $res = $list->get( |
397 | 'subtree', |
398 | $roots, |
399 | [ $this, 'fetchSubtreeNodeListFromDb' ] |
400 | ); |
401 | // $idx is a binary UUID |
402 | $retval = []; |
403 | foreach ( $res as $idx => $val ) { |
404 | $retval[UUID::create( $idx )->getAlphadecimal()] = $val; |
405 | } |
406 | return $retval; |
407 | } |
408 | |
409 | public function fetchSubtreeNodeListFromDb( array $roots ) { |
410 | $res = $this->dbFactory->getDB( DB_REPLICA )->newSelectQueryBuilder() |
411 | ->select( [ 'tree_ancestor_id', 'tree_descendant_id' ] ) |
412 | ->from( $this->tableName ) |
413 | ->where( [ |
414 | 'tree_ancestor_id' => UUID::convertUUIDs( $roots ), |
415 | ] ) |
416 | ->caller( __METHOD__ ) |
417 | ->fetchResultSet(); |
418 | $nodes = []; |
419 | foreach ( $res as $node ) { |
420 | $ancestor = UUID::create( $node->tree_ancestor_id ); |
421 | $descendant = UUID::create( $node->tree_descendant_id ); |
422 | $nodes[$ancestor->getAlphadecimal()][$descendant->getAlphadecimal()] = $descendant; |
423 | } |
424 | |
425 | return $nodes; |
426 | } |
427 | |
428 | /** |
429 | * Fetch the id of the immediate parent node of all ids in $nodes. Non-existent |
430 | * nodes are not represented in the result set. |
431 | * @param array $nodes |
432 | * @return array |
433 | */ |
434 | public function fetchParentMap( array $nodes ) { |
435 | $list = new MultiGetList( $this->cache ); |
436 | return $list->get( |
437 | 'parent', |
438 | $nodes, |
439 | [ $this, 'fetchParentMapFromDb' ] |
440 | ); |
441 | } |
442 | |
443 | /** |
444 | * @param UUID[] $nodes |
445 | * @return UUID[] |
446 | * @throws DataModelException |
447 | */ |
448 | public function fetchParentMapFromDb( array $nodes ) { |
449 | // Find out who the parent is for those nodes |
450 | $dbr = $this->dbFactory->getDB( DB_REPLICA ); |
451 | $res = $dbr->newSelectQueryBuilder() |
452 | ->select( [ 'tree_ancestor_id', 'tree_descendant_id' ] ) |
453 | ->from( $this->tableName ) |
454 | ->where( [ |
455 | 'tree_descendant_id' => UUID::convertUUIDs( $nodes ), |
456 | 'tree_depth' => 1, |
457 | ] ) |
458 | ->caller( __METHOD__ ) |
459 | ->fetchResultSet(); |
460 | $result = []; |
461 | foreach ( $res as $node ) { |
462 | if ( isset( $result[$node->tree_descendant_id] ) ) { |
463 | throw new DataModelException( 'Already have a parent for ' . $node->tree_descendant_id, 'process-data' ); |
464 | } |
465 | $descendant = UUID::create( $node->tree_descendant_id ); |
466 | $result[$descendant->getAlphadecimal()] = UUID::create( $node->tree_ancestor_id ); |
467 | } |
468 | foreach ( $nodes as $node ) { |
469 | if ( !isset( $result[$node->getAlphadecimal()] ) ) { |
470 | // $node is a root, it has no parent |
471 | $result[$node->getAlphadecimal()] = null; |
472 | } |
473 | } |
474 | |
475 | return $result; |
476 | } |
477 | } |