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
30 * Class for fetching backlink lists, approximate backlink counts and
31 * partitions. This is a shared cache.
33 * Instances of this class should typically be fetched with the method
34 * $title->getBacklinkCache().
36 * Ideally you should only get your backlinks from here when you think
37 * there is some advantage in caching them. Otherwise it's just a waste
40 * Introduced by r47317
43 /** @var ProcessCacheLRU */
44 protected static $cache;
47 * Multi dimensions array representing batches. Keys are:
48 * > (string) links table name
50 * > 'numRows' : Number of rows for this link table
51 * > 'batches' : array( $start, $end )
53 * @see BacklinkCache::partitionResult()
55 * Cleared with BacklinkCache::clear()
57 protected $partitionCache = array();
60 * Contains the whole links from a database result.
61 * This is raw data that will be partitioned in $partitionCache
63 * Initialized with BacklinkCache::getLinks()
64 * Cleared with BacklinkCache::clear()
66 protected $fullResultCache = array();
69 * Local copy of a database object.
71 * Accessor: BacklinkCache::getDB()
72 * Mutator : BacklinkCache::setDB()
73 * Cleared with BacklinkCache::clear()
78 * Local copy of a Title object
82 const CACHE_EXPIRY
= 3600;
85 * Create a new BacklinkCache
87 * @param Title $title : Title object to create a backlink cache for
89 public function __construct( Title
$title ) {
90 $this->title
= $title;
94 * Create a new BacklinkCache or reuse any existing one.
95 * Currently, only one cache instance can exist; callers that
96 * need multiple backlink cache objects should keep them in scope.
98 * @param Title $title Title object to get a backlink cache for
99 * @return BacklinkCache
101 public static function get( Title
$title ) {
102 if ( !self
::$cache ) { // init cache
103 self
::$cache = new ProcessCacheLRU( 1 );
105 $dbKey = $title->getPrefixedDBkey();
106 if ( !self
::$cache->has( $dbKey, 'obj', 3600 ) ) {
107 self
::$cache->set( $dbKey, 'obj', new self( $title ) );
110 return self
::$cache->get( $dbKey, 'obj' );
114 * Serialization handler, diasallows to serialize the database to prevent
115 * failures after this class is deserialized from cache with dead DB
121 return array( 'partitionCache', 'fullResultCache', 'title' );
125 * Clear locally stored data and database object.
127 public function clear() {
128 $this->partitionCache
= array();
129 $this->fullResultCache
= array();
134 * Set the Database object to use
136 * @param DatabaseBase $db
138 public function setDB( $db ) {
143 * Get the slave connection to the database
144 * When non existing, will initialize the connection.
145 * @return DatabaseBase
147 protected function getDB() {
148 if ( !isset( $this->db
) ) {
149 $this->db
= wfGetDB( DB_SLAVE
);
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 = array( '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 array( $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(
215 array( $table, 'page' ),
216 array( 'page_namespace', 'page_title', 'page_id' ),
219 array_merge( array( '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 ) {
241 static $prefixes = array(
243 'imagelinks' => 'il',
244 'categorylinks' => 'cl',
245 'templatelinks' => 'tl',
249 if ( isset( $prefixes[$table] ) ) {
250 return $prefixes[$table];
253 Hooks
::run( 'BacklinkCacheGetPrefix', array( $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( array(
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', array( $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 $wgMemc, $wgUpdateRowsPerJob;
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 = wfMemcKey( 'numbacklinks', md5( $this->title
->getPrefixedDBkey() ), $table );
342 // 3) ... fallback to memcached ...
343 $count = $wgMemc->get( $memcKey );
345 return min( $max, $count );
348 // 4) fetch from the database ...
349 if ( is_infinite( $max ) ) { // no limit at all
350 // Use partition() since it will batch the query and skip the JOIN.
351 // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
352 $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
353 return $this->partitionCache
[$table][$wgUpdateRowsPerJob]['numRows'];
354 } else { // probably some sane limit
355 // Fetch the full title info, since the caller will likely need it next
356 $count = $this->getLinks( $table, false, false, $max )->count();
357 if ( $count < $max ) { // full count
358 $wgMemc->set( $memcKey, $count, self
::CACHE_EXPIRY
);
362 return min( $max, $count );
366 * Partition the backlinks into batches.
367 * Returns an array giving the start and end of each range. The first
368 * batch has a start of false, and the last batch has an end of false.
370 * @param string $table The links table name
371 * @param int $batchSize
374 public function partition( $table, $batchSize ) {
377 // 1) try partition cache ...
378 if ( isset( $this->partitionCache
[$table][$batchSize] ) ) {
379 wfDebug( __METHOD__
. ": got from partition cache\n" );
381 return $this->partitionCache
[$table][$batchSize]['batches'];
384 $this->partitionCache
[$table][$batchSize] = false;
385 $cacheEntry =& $this->partitionCache
[$table][$batchSize];
387 // 2) ... then try full result cache ...
388 if ( isset( $this->fullResultCache
[$table] ) ) {
389 $cacheEntry = $this->partitionResult( $this->fullResultCache
[$table], $batchSize );
390 wfDebug( __METHOD__
. ": got from full result cache\n" );
392 return $cacheEntry['batches'];
395 $memcKey = wfMemcKey(
397 md5( $this->title
->getPrefixedDBkey() ),
402 // 3) ... fallback to memcached ...
403 $memcValue = $wgMemc->get( $memcKey );
404 if ( is_array( $memcValue ) ) {
405 $cacheEntry = $memcValue;
406 wfDebug( __METHOD__
. ": got from memcached $memcKey\n" );
408 return $cacheEntry['batches'];
411 // 4) ... finally fetch from the slow database :(
412 $cacheEntry = array( 'numRows' => 0, 'batches' => array() ); // final result
413 // Do the selects in batches to avoid client-side OOMs (bug 43452).
414 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
415 $selectSize = max( $batchSize, 200000 - ( 200000 %
$batchSize ) );
418 $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
419 $partitions = $this->partitionResult( $res, $batchSize, false );
420 // Merge the link count and range partitions for this chunk
421 $cacheEntry['numRows'] +
= $partitions['numRows'];
422 $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
423 if ( count( $partitions['batches'] ) ) {
424 list( , $lEnd ) = end( $partitions['batches'] );
425 $start = $lEnd +
1; // pick up after this inclusive range
427 } while ( $partitions['numRows'] >= $selectSize );
428 // Make sure the first range has start=false and the last one has end=false
429 if ( count( $cacheEntry['batches'] ) ) {
430 $cacheEntry['batches'][0][0] = false;
431 $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
434 // Save partitions to memcached
435 $wgMemc->set( $memcKey, $cacheEntry, self
::CACHE_EXPIRY
);
437 // Save backlink count to memcached
438 $memcKey = wfMemcKey( 'numbacklinks', md5( $this->title
->getPrefixedDBkey() ), $table );
439 $wgMemc->set( $memcKey, $cacheEntry['numRows'], self
::CACHE_EXPIRY
);
441 wfDebug( __METHOD__
. ": got from database\n" );
443 return $cacheEntry['batches'];
447 * Partition a DB result with backlinks in it into batches
448 * @param ResultWrapper $res Database result
449 * @param int $batchSize
450 * @param bool $isComplete Whether $res includes all the backlinks
451 * @throws MWException
454 protected function partitionResult( $res, $batchSize, $isComplete = true ) {
456 $numRows = $res->numRows();
457 $numBatches = ceil( $numRows / $batchSize );
459 for ( $i = 0; $i < $numBatches; $i++
) {
460 if ( $i == 0 && $isComplete ) {
463 $rowNum = $i * $batchSize;
464 $res->seek( $rowNum );
465 $row = $res->fetchObject();
466 $start = (int)$row->page_id
;
469 if ( $i == ( $numBatches - 1 ) && $isComplete ) {
472 $rowNum = min( $numRows - 1, ( $i +
1 ) * $batchSize - 1 );
473 $res->seek( $rowNum );
474 $row = $res->fetchObject();
475 $end = (int)$row->page_id
;
479 if ( $start && $end && $start > $end ) {
480 throw new MWException( __METHOD__
. ': Internal error: query result out of order' );
483 $batches[] = array( $start, $end );
486 return array( 'numRows' => $numRows, 'batches' => $batches );
490 * Get a Title iterator for cascade-protected template/file use backlinks
495 public function getCascadeProtectedLinks() {
496 $dbr = $this->getDB();
498 // @todo: use UNION without breaking tests that use temp tables
500 $resSets[] = $dbr->select(
501 array( 'templatelinks', 'page_restrictions', 'page' ),
502 array( 'page_namespace', 'page_title', 'page_id' ),
504 'tl_namespace' => $this->title
->getNamespace(),
505 'tl_title' => $this->title
->getDBkey(),
513 if ( $this->title
->getNamespace() == NS_FILE
) {
514 $resSets[] = $dbr->select(
515 array( 'imagelinks', 'page_restrictions', 'page' ),
516 array( 'page_namespace', 'page_title', 'page_id' ),
518 'il_to' => $this->title
->getDBkey(),
528 // Combine and de-duplicate the results
529 $mergedRes = array();
530 foreach ( $resSets as $res ) {
531 foreach ( $res as $row ) {
532 $mergedRes[$row->page_id
] = $row;
536 return TitleArray
::newFromResult(
537 new FakeResultWrapper( array_values( $mergedRes ) ) );