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 * @author Aaron Schulz
24 * @copyright © 2009, Tim Starling, Domas Mituzas
25 * @copyright © 2010, Max Sem
26 * @copyright © 2011, Antoine Musso
29 use Wikimedia\Rdbms\ResultWrapper
;
30 use Wikimedia\Rdbms\FakeResultWrapper
;
31 use Wikimedia\Rdbms\IDatabase
;
34 * Class for fetching backlink lists, approximate backlink counts and
35 * partitions. This is a shared cache.
37 * Instances of this class should typically be fetched with the method
38 * $title->getBacklinkCache().
40 * Ideally you should only get your backlinks from here when you think
41 * there is some advantage in caching them. Otherwise it's just a waste
44 * Introduced by r47317
47 /** @var BacklinkCache */
48 protected static $instance;
51 * Multi dimensions array representing batches. Keys are:
52 * > (string) links table name
54 * > 'numRows' : Number of rows for this link table
55 * > 'batches' : [ $start, $end ]
57 * @see BacklinkCache::partitionResult()
59 * Cleared with BacklinkCache::clear()
62 protected $partitionCache = [];
65 * Contains the whole links from a database result.
66 * This is raw data that will be partitioned in $partitionCache
68 * Initialized with BacklinkCache::getLinks()
69 * Cleared with BacklinkCache::clear()
70 * @var ResultWrapper[]
72 protected $fullResultCache = [];
75 * Local copy of a database object.
77 * Accessor: BacklinkCache::getDB()
78 * Mutator : BacklinkCache::setDB()
79 * Cleared with BacklinkCache::clear()
84 * Local copy of a Title object
88 const CACHE_EXPIRY
= 3600;
91 * Create a new BacklinkCache
93 * @param Title $title : Title object to create a backlink cache for
95 public function __construct( Title
$title ) {
96 $this->title
= $title;
100 * Create a new BacklinkCache or reuse any existing one.
101 * Currently, only one cache instance can exist; callers that
102 * need multiple backlink cache objects should keep them in scope.
104 * @param Title $title Title object to get a backlink cache for
105 * @return BacklinkCache
107 public static function get( Title
$title ) {
108 if ( !self
::$instance ||
!self
::$instance->title
->equals( $title ) ) {
109 self
::$instance = new self( $title );
111 return self
::$instance;
115 * Serialization handler, diasallows to serialize the database to prevent
116 * failures after this class is deserialized from cache with dead DB
122 return [ 'partitionCache', 'fullResultCache', 'title' ];
126 * Clear locally stored data and database object.
128 public function clear() {
129 $this->partitionCache
= [];
130 $this->fullResultCache
= [];
135 * Set the Database object to use
137 * @param IDatabase $db
139 public function setDB( $db ) {
144 * Get the replica DB connection to the database
145 * When non existing, will initialize the connection.
148 protected function getDB() {
149 if ( !isset( $this->db
) ) {
150 $this->db
= wfGetDB( DB_REPLICA
);
157 * Get the backlinks for a given table. Cached in process memory only.
158 * @param string $table
159 * @param int|bool $startId
160 * @param int|bool $endId
162 * @return TitleArrayFromResult
164 public function getLinks( $table, $startId = false, $endId = false, $max = INF
) {
165 return TitleArray
::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) );
169 * Get the backlinks for a given table. Cached in process memory only.
170 * @param string $table
171 * @param int|bool $startId
172 * @param int|bool $endId
174 * @param string $select 'all' or 'ids'
175 * @return ResultWrapper
177 protected function queryLinks( $table, $startId, $endId, $max, $select = 'all' ) {
179 $fromField = $this->getPrefix( $table ) . '_from';
181 if ( !$startId && !$endId && is_infinite( $max )
182 && isset( $this->fullResultCache
[$table] )
184 wfDebug( __METHOD__
. ": got results from cache\n" );
185 $res = $this->fullResultCache
[$table];
187 wfDebug( __METHOD__
. ": got results from DB\n" );
188 $conds = $this->getConditions( $table );
189 // Use the from field in the condition rather than the joined page_id,
190 // because databases are stupid and don't necessarily propagate indexes.
192 $conds[] = "$fromField >= " . intval( $startId );
195 $conds[] = "$fromField <= " . intval( $endId );
197 $options = [ 'ORDER BY' => $fromField ];
198 if ( is_finite( $max ) && $max > 0 ) {
199 $options['LIMIT'] = $max;
202 if ( $select === 'ids' ) {
203 // Just select from the backlink table and ignore the page JOIN
204 $res = $this->getDB()->select(
206 [ $this->getPrefix( $table ) . '_from AS page_id' ],
207 array_filter( $conds, function ( $clause ) { // kind of janky
208 return !preg_match( '/(\b|=)page_id(\b|=)/', $clause );
214 // Select from the backlink table and JOIN with page title information
215 $res = $this->getDB()->select(
217 [ 'page_namespace', 'page_title', 'page_id' ],
220 array_merge( [ 'STRAIGHT_JOIN' ], $options )
224 if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) {
225 // The full results fit within the limit, so cache them
226 $this->fullResultCache
[$table] = $res;
228 wfDebug( __METHOD__
. ": results from DB were uncacheable\n" );
236 * Get the field name prefix for a given table
237 * @param string $table
238 * @throws MWException
239 * @return null|string
241 protected function getPrefix( $table ) {
244 'imagelinks' => 'il',
245 'categorylinks' => 'cl',
246 'templatelinks' => 'tl',
250 if ( isset( $prefixes[$table] ) ) {
251 return $prefixes[$table];
254 Hooks
::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] );
258 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
264 * Get the SQL condition array for selecting backlinks, with a join
266 * @param string $table
267 * @throws MWException
270 protected function getConditions( $table ) {
271 $prefix = $this->getPrefix( $table );
275 case 'templatelinks':
277 "{$prefix}_namespace" => $this->title
->getNamespace(),
278 "{$prefix}_title" => $this->title
->getDBkey(),
279 "page_id={$prefix}_from"
284 "{$prefix}_namespace" => $this->title
->getNamespace(),
285 "{$prefix}_title" => $this->title
->getDBkey(),
286 $this->getDB()->makeList( [
287 "{$prefix}_interwiki" => '',
288 "{$prefix}_interwiki IS NULL",
290 "page_id={$prefix}_from"
294 case 'categorylinks':
296 "{$prefix}_to" => $this->title
->getDBkey(),
297 "page_id={$prefix}_from"
302 Hooks
::run( 'BacklinkCacheGetConditions', [ $table, $this->title
, &$conds ] );
304 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
312 * Check if there are any backlinks
313 * @param string $table
316 public function hasLinks( $table ) {
317 return ( $this->getNumLinks( $table, 1 ) > 0 );
321 * Get the approximate number of backlinks
322 * @param string $table
323 * @param int $max Only count up to this many backlinks
326 public function getNumLinks( $table, $max = INF
) {
327 global $wgUpdateRowsPerJob;
329 $cache = ObjectCache
::getMainWANInstance();
330 // 1) try partition cache ...
331 if ( isset( $this->partitionCache
[$table] ) ) {
332 $entry = reset( $this->partitionCache
[$table] );
334 return min( $max, $entry['numRows'] );
337 // 2) ... then try full result cache ...
338 if ( isset( $this->fullResultCache
[$table] ) ) {
339 return min( $max, $this->fullResultCache
[$table]->numRows() );
342 $memcKey = $cache->makeKey(
344 md5( $this->title
->getPrefixedDBkey() ),
348 // 3) ... fallback to memcached ...
349 $count = $cache->get( $memcKey );
351 return min( $max, $count );
354 // 4) fetch from the database ...
355 if ( is_infinite( $max ) ) { // no limit at all
356 // Use partition() since it will batch the query and skip the JOIN.
357 // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
358 $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
359 return $this->partitionCache
[$table][$wgUpdateRowsPerJob]['numRows'];
360 } else { // probably some sane limit
361 // Fetch the full title info, since the caller will likely need it next
362 $count = $this->getLinks( $table, false, false, $max )->count();
363 if ( $count < $max ) { // full count
364 $cache->set( $memcKey, $count, self
::CACHE_EXPIRY
);
368 return min( $max, $count );
372 * Partition the backlinks into batches.
373 * Returns an array giving the start and end of each range. The first
374 * batch has a start of false, and the last batch has an end of false.
376 * @param string $table The links table name
377 * @param int $batchSize
380 public function partition( $table, $batchSize ) {
381 // 1) try partition cache ...
382 if ( isset( $this->partitionCache
[$table][$batchSize] ) ) {
383 wfDebug( __METHOD__
. ": got from partition cache\n" );
385 return $this->partitionCache
[$table][$batchSize]['batches'];
388 $cache = ObjectCache
::getMainWANInstance();
389 $this->partitionCache
[$table][$batchSize] = false;
390 $cacheEntry =& $this->partitionCache
[$table][$batchSize];
392 // 2) ... then try full result cache ...
393 if ( isset( $this->fullResultCache
[$table] ) ) {
394 $cacheEntry = $this->partitionResult( $this->fullResultCache
[$table], $batchSize );
395 wfDebug( __METHOD__
. ": got from full result cache\n" );
397 return $cacheEntry['batches'];
400 $memcKey = $cache->makeKey(
402 md5( $this->title
->getPrefixedDBkey() ),
407 // 3) ... fallback to memcached ...
408 $memcValue = $cache->get( $memcKey );
409 if ( is_array( $memcValue ) ) {
410 $cacheEntry = $memcValue;
411 wfDebug( __METHOD__
. ": got from memcached $memcKey\n" );
413 return $cacheEntry['batches'];
416 // 4) ... finally fetch from the slow database :(
417 $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result
418 // Do the selects in batches to avoid client-side OOMs (T45452).
419 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
420 $selectSize = max( $batchSize, 200000 - ( 200000 %
$batchSize ) );
423 $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
424 $partitions = $this->partitionResult( $res, $batchSize, false );
425 // Merge the link count and range partitions for this chunk
426 $cacheEntry['numRows'] +
= $partitions['numRows'];
427 $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
428 if ( count( $partitions['batches'] ) ) {
429 list( , $lEnd ) = end( $partitions['batches'] );
430 $start = $lEnd +
1; // pick up after this inclusive range
432 } while ( $partitions['numRows'] >= $selectSize );
433 // Make sure the first range has start=false and the last one has end=false
434 if ( count( $cacheEntry['batches'] ) ) {
435 $cacheEntry['batches'][0][0] = false;
436 $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
439 // Save partitions to memcached
440 $cache->set( $memcKey, $cacheEntry, self
::CACHE_EXPIRY
);
442 // Save backlink count to memcached
443 $memcKey = $cache->makeKey(
445 md5( $this->title
->getPrefixedDBkey() ),
448 $cache->set( $memcKey, $cacheEntry['numRows'], self
::CACHE_EXPIRY
);
450 wfDebug( __METHOD__
. ": got from database\n" );
452 return $cacheEntry['batches'];
456 * Partition a DB result with backlinks in it into batches
457 * @param ResultWrapper $res Database result
458 * @param int $batchSize
459 * @param bool $isComplete Whether $res includes all the backlinks
460 * @throws MWException
463 protected function partitionResult( $res, $batchSize, $isComplete = true ) {
465 $numRows = $res->numRows();
466 $numBatches = ceil( $numRows / $batchSize );
468 for ( $i = 0; $i < $numBatches; $i++
) {
469 if ( $i == 0 && $isComplete ) {
472 $rowNum = $i * $batchSize;
473 $res->seek( $rowNum );
474 $row = $res->fetchObject();
475 $start = (int)$row->page_id
;
478 if ( $i == ( $numBatches - 1 ) && $isComplete ) {
481 $rowNum = min( $numRows - 1, ( $i +
1 ) * $batchSize - 1 );
482 $res->seek( $rowNum );
483 $row = $res->fetchObject();
484 $end = (int)$row->page_id
;
488 if ( $start && $end && $start > $end ) {
489 throw new MWException( __METHOD__
. ': Internal error: query result out of order' );
492 $batches[] = [ $start, $end ];
495 return [ 'numRows' => $numRows, 'batches' => $batches ];
499 * Get a Title iterator for cascade-protected template/file use backlinks
504 public function getCascadeProtectedLinks() {
505 $dbr = $this->getDB();
507 // @todo: use UNION without breaking tests that use temp tables
509 $resSets[] = $dbr->select(
510 [ 'templatelinks', 'page_restrictions', 'page' ],
511 [ 'page_namespace', 'page_title', 'page_id' ],
513 'tl_namespace' => $this->title
->getNamespace(),
514 'tl_title' => $this->title
->getDBkey(),
522 if ( $this->title
->getNamespace() == NS_FILE
) {
523 $resSets[] = $dbr->select(
524 [ 'imagelinks', 'page_restrictions', 'page' ],
525 [ 'page_namespace', 'page_title', 'page_id' ],
527 'il_to' => $this->title
->getDBkey(),
537 // Combine and de-duplicate the results
539 foreach ( $resSets as $res ) {
540 foreach ( $res as $row ) {
541 $mergedRes[$row->page_id
] = $row;
545 return TitleArray
::newFromResult(
546 new FakeResultWrapper( array_values( $mergedRes ) ) );