3 * Class for fetching backlink lists, approximate backlink counts and
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, write to the Free Software Foundation, Inc.,
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 * http://www.gnu.org/copyleft/gpl.html
22 * @author Tim Starling
23 * @copyright © 2009, Tim Starling, Domas Mituzas
24 * @copyright © 2010, Max Sem
25 * @copyright © 2011, Antoine Musso
28 use Wikimedia\Rdbms\ResultWrapper
;
29 use Wikimedia\Rdbms\FakeResultWrapper
;
30 use Wikimedia\Rdbms\IDatabase
;
33 * Class for fetching backlink lists, approximate backlink counts and
34 * partitions. This is a shared cache.
36 * Instances of this class should typically be fetched with the method
37 * $title->getBacklinkCache().
39 * Ideally you should only get your backlinks from here when you think
40 * there is some advantage in caching them. Otherwise it's just a waste
43 * Introduced by r47317
46 /** @var BacklinkCache */
47 protected static $instance;
50 * Multi dimensions array representing batches. Keys are:
51 * > (string) links table name
53 * > 'numRows' : Number of rows for this link table
54 * > 'batches' : [ $start, $end ]
56 * @see BacklinkCache::partitionResult()
58 * Cleared with BacklinkCache::clear()
61 protected $partitionCache = [];
64 * Contains the whole links from a database result.
65 * This is raw data that will be partitioned in $partitionCache
67 * Initialized with BacklinkCache::getLinks()
68 * Cleared with BacklinkCache::clear()
69 * @var ResultWrapper[]
71 protected $fullResultCache = [];
74 * Local copy of a database object.
76 * Accessor: BacklinkCache::getDB()
77 * Mutator : BacklinkCache::setDB()
78 * Cleared with BacklinkCache::clear()
83 * Local copy of a Title object
87 const CACHE_EXPIRY
= 3600;
90 * Create a new BacklinkCache
92 * @param Title $title : Title object to create a backlink cache for
94 public function __construct( Title
$title ) {
95 $this->title
= $title;
99 * Create a new BacklinkCache or reuse any existing one.
100 * Currently, only one cache instance can exist; callers that
101 * need multiple backlink cache objects should keep them in scope.
103 * @param Title $title Title object to get a backlink cache for
104 * @return BacklinkCache
106 public static function get( Title
$title ) {
107 if ( !self
::$instance ||
!self
::$instance->title
->equals( $title ) ) {
108 self
::$instance = new self( $title );
110 return self
::$instance;
114 * Serialization handler, diasallows to serialize the database to prevent
115 * failures after this class is deserialized from cache with dead DB
121 return [ 'partitionCache', 'fullResultCache', 'title' ];
125 * Clear locally stored data and database object.
127 public function clear() {
128 $this->partitionCache
= [];
129 $this->fullResultCache
= [];
134 * Set the Database object to use
136 * @param IDatabase $db
138 public function setDB( $db ) {
143 * Get the replica DB connection to the database
144 * When non existing, will initialize the connection.
147 protected function getDB() {
148 if ( !isset( $this->db
) ) {
149 $this->db
= wfGetDB( DB_REPLICA
);
156 * Get the backlinks for a given table. Cached in process memory only.
157 * @param string $table
158 * @param int|bool $startId
159 * @param int|bool $endId
161 * @return TitleArrayFromResult
163 public function getLinks( $table, $startId = false, $endId = false, $max = INF
) {
164 return TitleArray
::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) );
168 * Get the backlinks for a given table. Cached in process memory only.
169 * @param string $table
170 * @param int|bool $startId
171 * @param int|bool $endId
173 * @param string $select 'all' or 'ids'
174 * @return ResultWrapper
176 protected function queryLinks( $table, $startId, $endId, $max, $select = 'all' ) {
177 $fromField = $this->getPrefix( $table ) . '_from';
179 if ( !$startId && !$endId && is_infinite( $max )
180 && isset( $this->fullResultCache
[$table] )
182 wfDebug( __METHOD__
. ": got results from cache\n" );
183 $res = $this->fullResultCache
[$table];
185 wfDebug( __METHOD__
. ": got results from DB\n" );
186 $conds = $this->getConditions( $table );
187 // Use the from field in the condition rather than the joined page_id,
188 // because databases are stupid and don't necessarily propagate indexes.
190 $conds[] = "$fromField >= " . intval( $startId );
193 $conds[] = "$fromField <= " . intval( $endId );
195 $options = [ 'ORDER BY' => $fromField ];
196 if ( is_finite( $max ) && $max > 0 ) {
197 $options['LIMIT'] = $max;
200 if ( $select === 'ids' ) {
201 // Just select from the backlink table and ignore the page JOIN
202 $res = $this->getDB()->select(
204 [ $this->getPrefix( $table ) . '_from AS page_id' ],
205 array_filter( $conds, function ( $clause ) { // kind of janky
206 return !preg_match( '/(\b|=)page_id(\b|=)/', $clause );
212 // Select from the backlink table and JOIN with page title information
213 $res = $this->getDB()->select(
215 [ 'page_namespace', 'page_title', 'page_id' ],
218 array_merge( [ 'STRAIGHT_JOIN' ], $options )
222 if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) {
223 // The full results fit within the limit, so cache them
224 $this->fullResultCache
[$table] = $res;
226 wfDebug( __METHOD__
. ": results from DB were uncacheable\n" );
234 * Get the field name prefix for a given table
235 * @param string $table
236 * @throws MWException
237 * @return null|string
239 protected function getPrefix( $table ) {
242 'imagelinks' => 'il',
243 'categorylinks' => 'cl',
244 'templatelinks' => 'tl',
248 if ( isset( $prefixes[$table] ) ) {
249 return $prefixes[$table];
252 Hooks
::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] );
256 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
262 * Get the SQL condition array for selecting backlinks, with a join
264 * @param string $table
265 * @throws MWException
268 protected function getConditions( $table ) {
269 $prefix = $this->getPrefix( $table );
273 case 'templatelinks':
275 "{$prefix}_namespace" => $this->title
->getNamespace(),
276 "{$prefix}_title" => $this->title
->getDBkey(),
277 "page_id={$prefix}_from"
282 "{$prefix}_namespace" => $this->title
->getNamespace(),
283 "{$prefix}_title" => $this->title
->getDBkey(),
284 $this->getDB()->makeList( [
285 "{$prefix}_interwiki" => '',
286 "{$prefix}_interwiki IS NULL",
288 "page_id={$prefix}_from"
292 case 'categorylinks':
294 "{$prefix}_to" => $this->title
->getDBkey(),
295 "page_id={$prefix}_from"
300 Hooks
::run( 'BacklinkCacheGetConditions', [ $table, $this->title
, &$conds ] );
302 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
310 * Check if there are any backlinks
311 * @param string $table
314 public function hasLinks( $table ) {
315 return ( $this->getNumLinks( $table, 1 ) > 0 );
319 * Get the approximate number of backlinks
320 * @param string $table
321 * @param int $max Only count up to this many backlinks
324 public function getNumLinks( $table, $max = INF
) {
325 global $wgUpdateRowsPerJob;
327 $cache = ObjectCache
::getMainWANInstance();
328 // 1) try partition cache ...
329 if ( isset( $this->partitionCache
[$table] ) ) {
330 $entry = reset( $this->partitionCache
[$table] );
332 return min( $max, $entry['numRows'] );
335 // 2) ... then try full result cache ...
336 if ( isset( $this->fullResultCache
[$table] ) ) {
337 return min( $max, $this->fullResultCache
[$table]->numRows() );
340 $memcKey = $cache->makeKey(
342 md5( $this->title
->getPrefixedDBkey() ),
346 // 3) ... fallback to memcached ...
347 $count = $cache->get( $memcKey );
349 return min( $max, $count );
352 // 4) fetch from the database ...
353 if ( is_infinite( $max ) ) { // no limit at all
354 // Use partition() since it will batch the query and skip the JOIN.
355 // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
356 $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
357 return $this->partitionCache
[$table][$wgUpdateRowsPerJob]['numRows'];
358 } else { // probably some sane limit
359 // Fetch the full title info, since the caller will likely need it next
360 $count = $this->getLinks( $table, false, false, $max )->count();
361 if ( $count < $max ) { // full count
362 $cache->set( $memcKey, $count, self
::CACHE_EXPIRY
);
366 return min( $max, $count );
370 * Partition the backlinks into batches.
371 * Returns an array giving the start and end of each range. The first
372 * batch has a start of false, and the last batch has an end of false.
374 * @param string $table The links table name
375 * @param int $batchSize
378 public function partition( $table, $batchSize ) {
379 // 1) try partition cache ...
380 if ( isset( $this->partitionCache
[$table][$batchSize] ) ) {
381 wfDebug( __METHOD__
. ": got from partition cache\n" );
383 return $this->partitionCache
[$table][$batchSize]['batches'];
386 $cache = ObjectCache
::getMainWANInstance();
387 $this->partitionCache
[$table][$batchSize] = false;
388 $cacheEntry =& $this->partitionCache
[$table][$batchSize];
390 // 2) ... then try full result cache ...
391 if ( isset( $this->fullResultCache
[$table] ) ) {
392 $cacheEntry = $this->partitionResult( $this->fullResultCache
[$table], $batchSize );
393 wfDebug( __METHOD__
. ": got from full result cache\n" );
395 return $cacheEntry['batches'];
398 $memcKey = $cache->makeKey(
400 md5( $this->title
->getPrefixedDBkey() ),
405 // 3) ... fallback to memcached ...
406 $memcValue = $cache->get( $memcKey );
407 if ( is_array( $memcValue ) ) {
408 $cacheEntry = $memcValue;
409 wfDebug( __METHOD__
. ": got from memcached $memcKey\n" );
411 return $cacheEntry['batches'];
414 // 4) ... finally fetch from the slow database :(
415 $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result
416 // Do the selects in batches to avoid client-side OOMs (T45452).
417 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
418 $selectSize = max( $batchSize, 200000 - ( 200000 %
$batchSize ) );
421 $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
422 $partitions = $this->partitionResult( $res, $batchSize, false );
423 // Merge the link count and range partitions for this chunk
424 $cacheEntry['numRows'] +
= $partitions['numRows'];
425 $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
426 if ( count( $partitions['batches'] ) ) {
427 list( , $lEnd ) = end( $partitions['batches'] );
428 $start = $lEnd +
1; // pick up after this inclusive range
430 } while ( $partitions['numRows'] >= $selectSize );
431 // Make sure the first range has start=false and the last one has end=false
432 if ( count( $cacheEntry['batches'] ) ) {
433 $cacheEntry['batches'][0][0] = false;
434 $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
437 // Save partitions to memcached
438 $cache->set( $memcKey, $cacheEntry, self
::CACHE_EXPIRY
);
440 // Save backlink count to memcached
441 $memcKey = $cache->makeKey(
443 md5( $this->title
->getPrefixedDBkey() ),
446 $cache->set( $memcKey, $cacheEntry['numRows'], self
::CACHE_EXPIRY
);
448 wfDebug( __METHOD__
. ": got from database\n" );
450 return $cacheEntry['batches'];
454 * Partition a DB result with backlinks in it into batches
455 * @param ResultWrapper $res Database result
456 * @param int $batchSize
457 * @param bool $isComplete Whether $res includes all the backlinks
458 * @throws MWException
461 protected function partitionResult( $res, $batchSize, $isComplete = true ) {
463 $numRows = $res->numRows();
464 $numBatches = ceil( $numRows / $batchSize );
466 for ( $i = 0; $i < $numBatches; $i++
) {
467 if ( $i == 0 && $isComplete ) {
470 $rowNum = $i * $batchSize;
471 $res->seek( $rowNum );
472 $row = $res->fetchObject();
473 $start = (int)$row->page_id
;
476 if ( $i == ( $numBatches - 1 ) && $isComplete ) {
479 $rowNum = min( $numRows - 1, ( $i +
1 ) * $batchSize - 1 );
480 $res->seek( $rowNum );
481 $row = $res->fetchObject();
482 $end = (int)$row->page_id
;
486 if ( $start && $end && $start > $end ) {
487 throw new MWException( __METHOD__
. ': Internal error: query result out of order' );
490 $batches[] = [ $start, $end ];
493 return [ 'numRows' => $numRows, 'batches' => $batches ];
497 * Get a Title iterator for cascade-protected template/file use backlinks
502 public function getCascadeProtectedLinks() {
503 $dbr = $this->getDB();
505 // @todo: use UNION without breaking tests that use temp tables
507 $resSets[] = $dbr->select(
508 [ 'templatelinks', 'page_restrictions', 'page' ],
509 [ 'page_namespace', 'page_title', 'page_id' ],
511 'tl_namespace' => $this->title
->getNamespace(),
512 'tl_title' => $this->title
->getDBkey(),
520 if ( $this->title
->getNamespace() == NS_FILE
) {
521 $resSets[] = $dbr->select(
522 [ 'imagelinks', 'page_restrictions', 'page' ],
523 [ 'page_namespace', 'page_title', 'page_id' ],
525 'il_to' => $this->title
->getDBkey(),
535 // Combine and de-duplicate the results
537 foreach ( $resSets as $res ) {
538 foreach ( $res as $row ) {
539 $mergedRes[$row->page_id
] = $row;
543 return TitleArray
::newFromResult(
544 new FakeResultWrapper( array_values( $mergedRes ) ) );