Localisation updates from https://translatewiki.net.
[mediawiki.git] / includes / HistoryBlob.php
blob69f1120d43f6df9bedb4349478228fb0454e1d11
1 <?php
2 /**
3 * Efficient concatenated text storage.
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 * http://www.gnu.org/copyleft/gpl.html
20 * @file
23 /**
24 * Base class for general text storage via the "object" flag in old_flags, or
25 * two-part external storage URLs. Used for represent efficient concatenated
26 * storage, and migration-related pointer objects.
28 interface HistoryBlob {
29 /**
30 * Adds an item of text, returns a stub object which points to the item.
31 * You must call setLocation() on the stub object before storing it to the
32 * database
34 * @param string $text
36 * @return string The key for getItem()
38 function addItem( $text );
40 /**
41 * Get item by key, or false if the key is not present
43 * @param string $key
45 * @return string|bool
47 function getItem( $key );
49 /**
50 * Set the "default text"
51 * This concept is an odd property of the current DB schema, whereby each text item has a revision
52 * associated with it. The default text is the text of the associated revision. There may, however,
53 * be other revisions in the same object.
55 * Default text is not required for two-part external storage URLs.
57 * @param string $text
59 function setText( $text );
61 /**
62 * Get default text. This is called from Revision::getRevisionText()
64 * @return string
66 function getText();
69 /**
70 * Concatenated gzip (CGZ) storage
71 * Improves compression ratio by concatenating like objects before gzipping
73 class ConcatenatedGzipHistoryBlob implements HistoryBlob {
74 public $mVersion = 0, $mCompressed = false, $mItems = array(), $mDefaultHash = '';
75 public $mSize = 0;
76 public $mMaxSize = 10000000;
77 public $mMaxCount = 100;
79 /**
80 * Constructor
82 public function __construct() {
83 if ( !function_exists( 'gzdeflate' ) ) {
84 throw new MWException( "Need zlib support to read or write this "
85 . "kind of history object (ConcatenatedGzipHistoryBlob)\n" );
89 /**
90 * @param string $text
91 * @return string
93 public function addItem( $text ) {
94 $this->uncompress();
95 $hash = md5( $text );
96 if ( !isset( $this->mItems[$hash] ) ) {
97 $this->mItems[$hash] = $text;
98 $this->mSize += strlen( $text );
100 return $hash;
104 * @param string $hash
105 * @return array|bool
107 public function getItem( $hash ) {
108 $this->uncompress();
109 if ( array_key_exists( $hash, $this->mItems ) ) {
110 return $this->mItems[$hash];
111 } else {
112 return false;
117 * @param string $text
118 * @return void
120 public function setText( $text ) {
121 $this->uncompress();
122 $this->mDefaultHash = $this->addItem( $text );
126 * @return array|bool
128 public function getText() {
129 $this->uncompress();
130 return $this->getItem( $this->mDefaultHash );
134 * Remove an item
136 * @param string $hash
138 public function removeItem( $hash ) {
139 $this->mSize -= strlen( $this->mItems[$hash] );
140 unset( $this->mItems[$hash] );
144 * Compress the bulk data in the object
146 public function compress() {
147 if ( !$this->mCompressed ) {
148 $this->mItems = gzdeflate( serialize( $this->mItems ) );
149 $this->mCompressed = true;
154 * Uncompress bulk data
156 public function uncompress() {
157 if ( $this->mCompressed ) {
158 $this->mItems = unserialize( gzinflate( $this->mItems ) );
159 $this->mCompressed = false;
164 * @return array
166 function __sleep() {
167 $this->compress();
168 return array( 'mVersion', 'mCompressed', 'mItems', 'mDefaultHash' );
171 function __wakeup() {
172 $this->uncompress();
176 * Helper function for compression jobs
177 * Returns true until the object is "full" and ready to be committed
179 * @return bool
181 public function isHappy() {
182 return $this->mSize < $this->mMaxSize
183 && count( $this->mItems ) < $this->mMaxCount;
188 * Pointer object for an item within a CGZ blob stored in the text table.
190 class HistoryBlobStub {
192 * @var array One-step cache variable to hold base blobs; operations that
193 * pull multiple revisions may often pull multiple times from the same
194 * blob. By keeping the last-used one open, we avoid redundant
195 * unserialization and decompression overhead.
197 protected static $blobCache = array();
199 /** @var int */
200 public $mOldId;
202 /** @var string */
203 public $mHash;
205 /** @var string */
206 public $mRef;
209 * @param string $hash The content hash of the text
210 * @param int $oldid The old_id for the CGZ object
212 function __construct( $hash = '', $oldid = 0 ) {
213 $this->mHash = $hash;
217 * Sets the location (old_id) of the main object to which this object
218 * points
219 * @param int $id
221 function setLocation( $id ) {
222 $this->mOldId = $id;
226 * Sets the location (old_id) of the referring object
227 * @param string $id
229 function setReferrer( $id ) {
230 $this->mRef = $id;
234 * Gets the location of the referring object
235 * @return string
237 function getReferrer() {
238 return $this->mRef;
242 * @return string
244 function getText() {
245 if ( isset( self::$blobCache[$this->mOldId] ) ) {
246 $obj = self::$blobCache[$this->mOldId];
247 } else {
248 $dbr = wfGetDB( DB_SLAVE );
249 $row = $dbr->selectRow(
250 'text',
251 array( 'old_flags', 'old_text' ),
252 array( 'old_id' => $this->mOldId )
255 if ( !$row ) {
256 return false;
259 $flags = explode( ',', $row->old_flags );
260 if ( in_array( 'external', $flags ) ) {
261 $url = $row->old_text;
262 $parts = explode( '://', $url, 2 );
263 if ( !isset( $parts[1] ) || $parts[1] == '' ) {
264 return false;
266 $row->old_text = ExternalStore::fetchFromUrl( $url );
270 if ( !in_array( 'object', $flags ) ) {
271 return false;
274 if ( in_array( 'gzip', $flags ) ) {
275 // This shouldn't happen, but a bug in the compress script
276 // may at times gzip-compress a HistoryBlob object row.
277 $obj = unserialize( gzinflate( $row->old_text ) );
278 } else {
279 $obj = unserialize( $row->old_text );
282 if ( !is_object( $obj ) ) {
283 // Correct for old double-serialization bug.
284 $obj = unserialize( $obj );
287 // Save this item for reference; if pulling many
288 // items in a row we'll likely use it again.
289 $obj->uncompress();
290 self::$blobCache = array( $this->mOldId => $obj );
293 return $obj->getItem( $this->mHash );
297 * Get the content hash
299 * @return string
301 function getHash() {
302 return $this->mHash;
307 * To speed up conversion from 1.4 to 1.5 schema, text rows can refer to the
308 * leftover cur table as the backend. This avoids expensively copying hundreds
309 * of megabytes of data during the conversion downtime.
311 * Serialized HistoryBlobCurStub objects will be inserted into the text table
312 * on conversion if $wgLegacySchemaConversion is set to true.
314 class HistoryBlobCurStub {
315 /** @var int */
316 public $mCurId;
319 * @param int $curid The cur_id pointed to
321 function __construct( $curid = 0 ) {
322 $this->mCurId = $curid;
326 * Sets the location (cur_id) of the main object to which this object
327 * points
329 * @param int $id
331 function setLocation( $id ) {
332 $this->mCurId = $id;
336 * @return string|bool
338 function getText() {
339 $dbr = wfGetDB( DB_SLAVE );
340 $row = $dbr->selectRow( 'cur', array( 'cur_text' ), array( 'cur_id' => $this->mCurId ) );
341 if ( !$row ) {
342 return false;
344 return $row->cur_text;
349 * Diff-based history compression
350 * Requires xdiff 1.5+ and zlib
352 class DiffHistoryBlob implements HistoryBlob {
353 /** @var array Uncompressed item cache */
354 public $mItems = array();
356 /** @var int Total uncompressed size */
357 public $mSize = 0;
360 * @var array Array of diffs. If a diff D from A to B is notated D = B - A,
361 * and Z is an empty string:
363 * { item[map[i]] - item[map[i-1]] where i > 0
364 * diff[i] = {
365 * { item[map[i]] - Z where i = 0
367 public $mDiffs;
369 /** @var array The diff map, see above */
370 public $mDiffMap;
372 /** @var int The key for getText()
374 public $mDefaultKey;
376 /** @var string Compressed storage */
377 public $mCompressed;
379 /** @var bool True if the object is locked against further writes */
380 public $mFrozen = false;
383 * @var int The maximum uncompressed size before the object becomes sad
384 * Should be less than max_allowed_packet
386 public $mMaxSize = 10000000;
388 /** @var int The maximum number of text items before the object becomes sad */
389 public $mMaxCount = 100;
391 /** Constants from xdiff.h */
392 const XDL_BDOP_INS = 1;
393 const XDL_BDOP_CPY = 2;
394 const XDL_BDOP_INSB = 3;
396 function __construct() {
397 if ( !function_exists( 'gzdeflate' ) ) {
398 throw new MWException( "Need zlib support to read or write DiffHistoryBlob\n" );
403 * @throws MWException
404 * @param string $text
405 * @return int
407 function addItem( $text ) {
408 if ( $this->mFrozen ) {
409 throw new MWException( __METHOD__ . ": Cannot add more items after sleep/wakeup" );
412 $this->mItems[] = $text;
413 $this->mSize += strlen( $text );
414 $this->mDiffs = null; // later
415 return count( $this->mItems ) - 1;
419 * @param string $key
420 * @return string
422 function getItem( $key ) {
423 return $this->mItems[$key];
427 * @param string $text
429 function setText( $text ) {
430 $this->mDefaultKey = $this->addItem( $text );
434 * @return string
436 function getText() {
437 return $this->getItem( $this->mDefaultKey );
441 * @throws MWException
443 function compress() {
444 if ( !function_exists( 'xdiff_string_rabdiff' ) ) {
445 throw new MWException( "Need xdiff 1.5+ support to write DiffHistoryBlob\n" );
447 if ( isset( $this->mDiffs ) ) {
448 // Already compressed
449 return;
451 if ( !count( $this->mItems ) ) {
452 // Empty
453 return;
456 // Create two diff sequences: one for main text and one for small text
457 $sequences = array(
458 'small' => array(
459 'tail' => '',
460 'diffs' => array(),
461 'map' => array(),
463 'main' => array(
464 'tail' => '',
465 'diffs' => array(),
466 'map' => array(),
469 $smallFactor = 0.5;
471 $mItemsCount = count( $this->mItems );
472 for ( $i = 0; $i < $mItemsCount; $i++ ) {
473 $text = $this->mItems[$i];
474 if ( $i == 0 ) {
475 $seqName = 'main';
476 } else {
477 $mainTail = $sequences['main']['tail'];
478 if ( strlen( $text ) < strlen( $mainTail ) * $smallFactor ) {
479 $seqName = 'small';
480 } else {
481 $seqName = 'main';
484 $seq =& $sequences[$seqName];
485 $tail = $seq['tail'];
486 $diff = $this->diff( $tail, $text );
487 $seq['diffs'][] = $diff;
488 $seq['map'][] = $i;
489 $seq['tail'] = $text;
491 unset( $seq ); // unlink dangerous alias
493 // Knit the sequences together
494 $tail = '';
495 $this->mDiffs = array();
496 $this->mDiffMap = array();
497 foreach ( $sequences as $seq ) {
498 if ( !count( $seq['diffs'] ) ) {
499 continue;
501 if ( $tail === '' ) {
502 $this->mDiffs[] = $seq['diffs'][0];
503 } else {
504 $head = $this->patch( '', $seq['diffs'][0] );
505 $this->mDiffs[] = $this->diff( $tail, $head );
507 $this->mDiffMap[] = $seq['map'][0];
508 $diffsCount = count( $seq['diffs'] );
509 for ( $i = 1; $i < $diffsCount; $i++ ) {
510 $this->mDiffs[] = $seq['diffs'][$i];
511 $this->mDiffMap[] = $seq['map'][$i];
513 $tail = $seq['tail'];
518 * @param string $t1
519 * @param string $t2
520 * @return string
522 function diff( $t1, $t2 ) {
523 # Need to do a null concatenation with warnings off, due to bugs in the current version of xdiff
524 # "String is not zero-terminated"
525 wfSuppressWarnings();
526 $diff = xdiff_string_rabdiff( $t1, $t2 ) . '';
527 wfRestoreWarnings();
528 return $diff;
532 * @param string $base
533 * @param string $diff
534 * @return bool|string
536 function patch( $base, $diff ) {
537 if ( function_exists( 'xdiff_string_bpatch' ) ) {
538 wfSuppressWarnings();
539 $text = xdiff_string_bpatch( $base, $diff ) . '';
540 wfRestoreWarnings();
541 return $text;
544 # Pure PHP implementation
546 $header = unpack( 'Vofp/Vcsize', substr( $diff, 0, 8 ) );
548 # Check the checksum if hash extension is available
549 $ofp = $this->xdiffAdler32( $base );
550 if ( $ofp !== false && $ofp !== substr( $diff, 0, 4 ) ) {
551 wfDebug( __METHOD__ . ": incorrect base checksum\n" );
552 return false;
554 if ( $header['csize'] != strlen( $base ) ) {
555 wfDebug( __METHOD__ . ": incorrect base length\n" );
556 return false;
559 $p = 8;
560 $out = '';
561 while ( $p < strlen( $diff ) ) {
562 $x = unpack( 'Cop', substr( $diff, $p, 1 ) );
563 $op = $x['op'];
564 ++$p;
565 switch ( $op ) {
566 case self::XDL_BDOP_INS:
567 $x = unpack( 'Csize', substr( $diff, $p, 1 ) );
568 $p++;
569 $out .= substr( $diff, $p, $x['size'] );
570 $p += $x['size'];
571 break;
572 case self::XDL_BDOP_INSB:
573 $x = unpack( 'Vcsize', substr( $diff, $p, 4 ) );
574 $p += 4;
575 $out .= substr( $diff, $p, $x['csize'] );
576 $p += $x['csize'];
577 break;
578 case self::XDL_BDOP_CPY:
579 $x = unpack( 'Voff/Vcsize', substr( $diff, $p, 8 ) );
580 $p += 8;
581 $out .= substr( $base, $x['off'], $x['csize'] );
582 break;
583 default:
584 wfDebug( __METHOD__ . ": invalid op\n" );
585 return false;
588 return $out;
592 * Compute a binary "Adler-32" checksum as defined by LibXDiff, i.e. with
593 * the bytes backwards and initialised with 0 instead of 1. See bug 34428.
595 * @param string $s
596 * @return string|bool False if the hash extension is not available
598 function xdiffAdler32( $s ) {
599 if ( !function_exists( 'hash' ) ) {
600 return false;
603 static $init;
604 if ( $init === null ) {
605 $init = str_repeat( "\xf0", 205 ) . "\xee" . str_repeat( "\xf0", 67 ) . "\x02";
608 // The real Adler-32 checksum of $init is zero, so it initialises the
609 // state to zero, as it is at the start of LibXDiff's checksum
610 // algorithm. Appending the subject string then simulates LibXDiff.
611 return strrev( hash( 'adler32', $init . $s, true ) );
614 function uncompress() {
615 if ( !$this->mDiffs ) {
616 return;
618 $tail = '';
619 $mDiffsCount = count( $this->mDiffs );
620 for ( $diffKey = 0; $diffKey < $mDiffsCount; $diffKey++ ) {
621 $textKey = $this->mDiffMap[$diffKey];
622 $text = $this->patch( $tail, $this->mDiffs[$diffKey] );
623 $this->mItems[$textKey] = $text;
624 $tail = $text;
629 * @return array
631 function __sleep() {
632 $this->compress();
633 if ( !count( $this->mItems ) ) {
634 // Empty object
635 $info = false;
636 } else {
637 // Take forward differences to improve the compression ratio for sequences
638 $map = '';
639 $prev = 0;
640 foreach ( $this->mDiffMap as $i ) {
641 if ( $map !== '' ) {
642 $map .= ',';
644 $map .= $i - $prev;
645 $prev = $i;
647 $info = array(
648 'diffs' => $this->mDiffs,
649 'map' => $map
652 if ( isset( $this->mDefaultKey ) ) {
653 $info['default'] = $this->mDefaultKey;
655 $this->mCompressed = gzdeflate( serialize( $info ) );
656 return array( 'mCompressed' );
659 function __wakeup() {
660 // addItem() doesn't work if mItems is partially filled from mDiffs
661 $this->mFrozen = true;
662 $info = unserialize( gzinflate( $this->mCompressed ) );
663 unset( $this->mCompressed );
665 if ( !$info ) {
666 // Empty object
667 return;
670 if ( isset( $info['default'] ) ) {
671 $this->mDefaultKey = $info['default'];
673 $this->mDiffs = $info['diffs'];
674 if ( isset( $info['base'] ) ) {
675 // Old format
676 $this->mDiffMap = range( 0, count( $this->mDiffs ) - 1 );
677 array_unshift( $this->mDiffs,
678 pack( 'VVCV', 0, 0, self::XDL_BDOP_INSB, strlen( $info['base'] ) ) .
679 $info['base'] );
680 } else {
681 // New format
682 $map = explode( ',', $info['map'] );
683 $cur = 0;
684 $this->mDiffMap = array();
685 foreach ( $map as $i ) {
686 $cur += $i;
687 $this->mDiffMap[] = $cur;
690 $this->uncompress();
694 * Helper function for compression jobs
695 * Returns true until the object is "full" and ready to be committed
697 * @return bool
699 function isHappy() {
700 return $this->mSize < $this->mMaxSize
701 && count( $this->mItems ) < $this->mMaxCount;