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' ) {
178 $fromField = $this->getPrefix( $table ) . '_from';
180 if ( !$startId && !$endId && is_infinite( $max )
181 && isset( $this->fullResultCache
[$table] )
183 wfDebug( __METHOD__
. ": got results from cache\n" );
184 $res = $this->fullResultCache
[$table];
186 wfDebug( __METHOD__
. ": got results from DB\n" );
187 $conds = $this->getConditions( $table );
188 // Use the from field in the condition rather than the joined page_id,
189 // because databases are stupid and don't necessarily propagate indexes.
191 $conds[] = "$fromField >= " . intval( $startId );
194 $conds[] = "$fromField <= " . intval( $endId );
196 $options = [ 'ORDER BY' => $fromField ];
197 if ( is_finite( $max ) && $max > 0 ) {
198 $options['LIMIT'] = $max;
201 if ( $select === 'ids' ) {
202 // Just select from the backlink table and ignore the page JOIN
203 $res = $this->getDB()->select(
205 [ $this->getPrefix( $table ) . '_from AS page_id' ],
206 array_filter( $conds, function ( $clause ) { // kind of janky
207 return !preg_match( '/(\b|=)page_id(\b|=)/', $clause );
213 // Select from the backlink table and JOIN with page title information
214 $res = $this->getDB()->select(
216 [ 'page_namespace', 'page_title', 'page_id' ],
219 array_merge( [ 'STRAIGHT_JOIN' ], $options )
223 if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) {
224 // The full results fit within the limit, so cache them
225 $this->fullResultCache
[$table] = $res;
227 wfDebug( __METHOD__
. ": results from DB were uncacheable\n" );
235 * Get the field name prefix for a given table
236 * @param string $table
237 * @throws MWException
238 * @return null|string
240 protected function getPrefix( $table ) {
243 'imagelinks' => 'il',
244 'categorylinks' => 'cl',
245 'templatelinks' => 'tl',
249 if ( isset( $prefixes[$table] ) ) {
250 return $prefixes[$table];
253 Hooks
::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] );
257 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
263 * Get the SQL condition array for selecting backlinks, with a join
265 * @param string $table
266 * @throws MWException
269 protected function getConditions( $table ) {
270 $prefix = $this->getPrefix( $table );
274 case 'templatelinks':
276 "{$prefix}_namespace" => $this->title
->getNamespace(),
277 "{$prefix}_title" => $this->title
->getDBkey(),
278 "page_id={$prefix}_from"
283 "{$prefix}_namespace" => $this->title
->getNamespace(),
284 "{$prefix}_title" => $this->title
->getDBkey(),
285 $this->getDB()->makeList( [
286 "{$prefix}_interwiki" => '',
287 "{$prefix}_interwiki IS NULL",
289 "page_id={$prefix}_from"
293 case 'categorylinks':
295 "{$prefix}_to" => $this->title
->getDBkey(),
296 "page_id={$prefix}_from"
301 Hooks
::run( 'BacklinkCacheGetConditions', [ $table, $this->title
, &$conds ] );
303 throw new MWException( "Invalid table \"$table\" in " . __CLASS__
);
311 * Check if there are any backlinks
312 * @param string $table
315 public function hasLinks( $table ) {
316 return ( $this->getNumLinks( $table, 1 ) > 0 );
320 * Get the approximate number of backlinks
321 * @param string $table
322 * @param int $max Only count up to this many backlinks
325 public function getNumLinks( $table, $max = INF
) {
326 global $wgUpdateRowsPerJob;
328 $cache = ObjectCache
::getMainWANInstance();
329 // 1) try partition cache ...
330 if ( isset( $this->partitionCache
[$table] ) ) {
331 $entry = reset( $this->partitionCache
[$table] );
333 return min( $max, $entry['numRows'] );
336 // 2) ... then try full result cache ...
337 if ( isset( $this->fullResultCache
[$table] ) ) {
338 return min( $max, $this->fullResultCache
[$table]->numRows() );
341 $memcKey = $cache->makeKey(
343 md5( $this->title
->getPrefixedDBkey() ),
347 // 3) ... fallback to memcached ...
348 $count = $cache->get( $memcKey );
350 return min( $max, $count );
353 // 4) fetch from the database ...
354 if ( is_infinite( $max ) ) { // no limit at all
355 // Use partition() since it will batch the query and skip the JOIN.
356 // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
357 $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
358 return $this->partitionCache
[$table][$wgUpdateRowsPerJob]['numRows'];
359 } else { // probably some sane limit
360 // Fetch the full title info, since the caller will likely need it next
361 $count = $this->getLinks( $table, false, false, $max )->count();
362 if ( $count < $max ) { // full count
363 $cache->set( $memcKey, $count, self
::CACHE_EXPIRY
);
367 return min( $max, $count );
371 * Partition the backlinks into batches.
372 * Returns an array giving the start and end of each range. The first
373 * batch has a start of false, and the last batch has an end of false.
375 * @param string $table The links table name
376 * @param int $batchSize
379 public function partition( $table, $batchSize ) {
380 // 1) try partition cache ...
381 if ( isset( $this->partitionCache
[$table][$batchSize] ) ) {
382 wfDebug( __METHOD__
. ": got from partition cache\n" );
384 return $this->partitionCache
[$table][$batchSize]['batches'];
387 $cache = ObjectCache
::getMainWANInstance();
388 $this->partitionCache
[$table][$batchSize] = false;
389 $cacheEntry =& $this->partitionCache
[$table][$batchSize];
391 // 2) ... then try full result cache ...
392 if ( isset( $this->fullResultCache
[$table] ) ) {
393 $cacheEntry = $this->partitionResult( $this->fullResultCache
[$table], $batchSize );
394 wfDebug( __METHOD__
. ": got from full result cache\n" );
396 return $cacheEntry['batches'];
399 $memcKey = $cache->makeKey(
401 md5( $this->title
->getPrefixedDBkey() ),
406 // 3) ... fallback to memcached ...
407 $memcValue = $cache->get( $memcKey );
408 if ( is_array( $memcValue ) ) {
409 $cacheEntry = $memcValue;
410 wfDebug( __METHOD__
. ": got from memcached $memcKey\n" );
412 return $cacheEntry['batches'];
415 // 4) ... finally fetch from the slow database :(
416 $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result
417 // Do the selects in batches to avoid client-side OOMs (T45452).
418 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
419 $selectSize = max( $batchSize, 200000 - ( 200000 %
$batchSize ) );
422 $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
423 $partitions = $this->partitionResult( $res, $batchSize, false );
424 // Merge the link count and range partitions for this chunk
425 $cacheEntry['numRows'] +
= $partitions['numRows'];
426 $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
427 if ( count( $partitions['batches'] ) ) {
428 list( , $lEnd ) = end( $partitions['batches'] );
429 $start = $lEnd +
1; // pick up after this inclusive range
431 } while ( $partitions['numRows'] >= $selectSize );
432 // Make sure the first range has start=false and the last one has end=false
433 if ( count( $cacheEntry['batches'] ) ) {
434 $cacheEntry['batches'][0][0] = false;
435 $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
438 // Save partitions to memcached
439 $cache->set( $memcKey, $cacheEntry, self
::CACHE_EXPIRY
);
441 // Save backlink count to memcached
442 $memcKey = $cache->makeKey(
444 md5( $this->title
->getPrefixedDBkey() ),
447 $cache->set( $memcKey, $cacheEntry['numRows'], self
::CACHE_EXPIRY
);
449 wfDebug( __METHOD__
. ": got from database\n" );
451 return $cacheEntry['batches'];
455 * Partition a DB result with backlinks in it into batches
456 * @param ResultWrapper $res Database result
457 * @param int $batchSize
458 * @param bool $isComplete Whether $res includes all the backlinks
459 * @throws MWException
462 protected function partitionResult( $res, $batchSize, $isComplete = true ) {
464 $numRows = $res->numRows();
465 $numBatches = ceil( $numRows / $batchSize );
467 for ( $i = 0; $i < $numBatches; $i++
) {
468 if ( $i == 0 && $isComplete ) {
471 $rowNum = $i * $batchSize;
472 $res->seek( $rowNum );
473 $row = $res->fetchObject();
474 $start = (int)$row->page_id
;
477 if ( $i == ( $numBatches - 1 ) && $isComplete ) {
480 $rowNum = min( $numRows - 1, ( $i +
1 ) * $batchSize - 1 );
481 $res->seek( $rowNum );
482 $row = $res->fetchObject();
483 $end = (int)$row->page_id
;
487 if ( $start && $end && $start > $end ) {
488 throw new MWException( __METHOD__
. ': Internal error: query result out of order' );
491 $batches[] = [ $start, $end ];
494 return [ 'numRows' => $numRows, 'batches' => $batches ];
498 * Get a Title iterator for cascade-protected template/file use backlinks
503 public function getCascadeProtectedLinks() {
504 $dbr = $this->getDB();
506 // @todo: use UNION without breaking tests that use temp tables
508 $resSets[] = $dbr->select(
509 [ 'templatelinks', 'page_restrictions', 'page' ],
510 [ 'page_namespace', 'page_title', 'page_id' ],
512 'tl_namespace' => $this->title
->getNamespace(),
513 'tl_title' => $this->title
->getDBkey(),
521 if ( $this->title
->getNamespace() == NS_FILE
) {
522 $resSets[] = $dbr->select(
523 [ 'imagelinks', 'page_restrictions', 'page' ],
524 [ 'page_namespace', 'page_title', 'page_id' ],
526 'il_to' => $this->title
->getDBkey(),
536 // Combine and de-duplicate the results
538 foreach ( $resSets as $res ) {
539 foreach ( $res as $row ) {
540 $mergedRes[$row->page_id
] = $row;
544 return TitleArray
::newFromResult(
545 new FakeResultWrapper( array_values( $mergedRes ) ) );