Legoktm has uploaded a new change for review. https://gerrit.wikimedia.org/r/287009
Change subject: Bump wikimedia/ip-set to 1.1.0 ...................................................................... Bump wikimedia/ip-set to 1.1.0 Bug: T128169 Change-Id: Id43ca893fa6c7c6cb3b1eb23107e42a8f2bcceb8 --- M composer.json M composer.lock M composer/LICENSE M composer/installed.json M wikimedia/ip-set/src/IPSet.php 5 files changed, 99 insertions(+), 154 deletions(-) git pull ssh://gerrit.wikimedia.org:29418/mediawiki/vendor refs/changes/09/287009/1 diff --git a/composer.json b/composer.json index 5c6993f..d058eb0 100644 --- a/composer.json +++ b/composer.json @@ -38,7 +38,7 @@ "wikimedia/cldr-plural-rule-parser": "1.0.0", "wikimedia/composer-merge-plugin": "1.3.1", "wikimedia/html-formatter": "1.0.1", - "wikimedia/ip-set": "1.0.1", + "wikimedia/ip-set": "1.1.0", "wikimedia/php-session-serializer": "1.0.3", "wikimedia/relpath": "1.0.3", "wikimedia/running-stat": "1.1.0", diff --git a/composer.lock b/composer.lock index 603f8f0..bdd8ac6 100644 --- a/composer.lock +++ b/composer.lock @@ -4,8 +4,8 @@ "Read more about it at https://getcomposer.org/doc/01-basic-usage.md#composer-lock-the-lock-file", "This file is @generated automatically" ], - "hash": "2e032cbe0c06b4225c319a65930d7631", - "content-hash": "c61356e2af6e9a24a6629157061d8971", + "hash": "d4b69794468f794a8350339881319948", + "content-hash": "fbadb58818d15bd051e858b533bf2252", "packages": [ { "name": "composer/semver", @@ -1471,25 +1471,25 @@ }, { "name": "wikimedia/ip-set", - "version": "1.0.1", + "version": "1.1.0", "source": { "type": "git", "url": "https://github.com/wikimedia/IPSet.git", - "reference": "3c2dd6706546fe616e6ceba02044e64dce4fc9be" + "reference": "b71a3834b42e2bcb2d9fa037abbb654e82117a01" }, "dist": { "type": "zip", - "url": "https://api.github.com/repos/wikimedia/IPSet/zipball/3c2dd6706546fe616e6ceba02044e64dce4fc9be", - "reference": "3c2dd6706546fe616e6ceba02044e64dce4fc9be", + "url": "https://api.github.com/repos/wikimedia/IPSet/zipball/b71a3834b42e2bcb2d9fa037abbb654e82117a01", + "reference": "b71a3834b42e2bcb2d9fa037abbb654e82117a01", "shasum": "" }, "require": { "php": ">=5.3.3" }, "require-dev": { - "jakub-onderka/php-parallel-lint": "0.9", - "mediawiki/mediawiki-codesniffer": "0.3.0", - "phpunit/phpunit": "4.6.*" + "jakub-onderka/php-parallel-lint": "0.9.2", + "mediawiki/mediawiki-codesniffer": "0.5.1", + "phpunit/phpunit": "4.7.2" }, "type": "library", "autoload": { @@ -1509,7 +1509,7 @@ ], "description": "Efficiently match IP addresses against a set of CIDR specifications.", "homepage": "https://github.com/wikimedia/IPSet", - "time": "2015-06-29 20:21:27" + "time": "2016-02-12 15:19:10" }, { "name": "wikimedia/php-session-serializer", diff --git a/composer/LICENSE b/composer/LICENSE index 1a28124..b0794ff 100644 --- a/composer/LICENSE +++ b/composer/LICENSE @@ -1,4 +1,3 @@ - Copyright (c) 2016 Nils Adermann, Jordi Boggiano Permission is hereby granted, free of charge, to any person obtaining a copy @@ -18,4 +17,3 @@ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - diff --git a/composer/installed.json b/composer/installed.json index 637eb49..e593582 100644 --- a/composer/installed.json +++ b/composer/installed.json @@ -920,50 +920,6 @@ "homepage": "https://www.mediawiki.org/wiki/CLDRPluralRuleParser" }, { - "name": "wikimedia/ip-set", - "version": "1.0.1", - "version_normalized": "1.0.1.0", - "source": { - "type": "git", - "url": "https://github.com/wikimedia/IPSet.git", - "reference": "3c2dd6706546fe616e6ceba02044e64dce4fc9be" - }, - "dist": { - "type": "zip", - "url": "https://api.github.com/repos/wikimedia/IPSet/zipball/3c2dd6706546fe616e6ceba02044e64dce4fc9be", - "reference": "3c2dd6706546fe616e6ceba02044e64dce4fc9be", - "shasum": "" - }, - "require": { - "php": ">=5.3.3" - }, - "require-dev": { - "jakub-onderka/php-parallel-lint": "0.9", - "mediawiki/mediawiki-codesniffer": "0.3.0", - "phpunit/phpunit": "4.6.*" - }, - "time": "2015-06-29 20:21:27", - "type": "library", - "installation-source": "dist", - "autoload": { - "classmap": [ - "src/" - ] - }, - "notification-url": "https://packagist.org/downloads/", - "license": [ - "GPL-2.0+" - ], - "authors": [ - { - "name": "Brandon Black", - "email": "blbl...@gmail.com" - } - ], - "description": "Efficiently match IP addresses against a set of CIDR specifications.", - "homepage": "https://github.com/wikimedia/IPSet" - }, - { "name": "wikimedia/php-session-serializer", "version": "v1.0.3", "version_normalized": "1.0.3.0", @@ -1876,5 +1832,49 @@ ], "description": "Provides library of common widgets, layouts, and windows.", "homepage": "https://www.mediawiki.org/wiki/OOjs_UI" + }, + { + "name": "wikimedia/ip-set", + "version": "1.1.0", + "version_normalized": "1.1.0.0", + "source": { + "type": "git", + "url": "https://github.com/wikimedia/IPSet.git", + "reference": "b71a3834b42e2bcb2d9fa037abbb654e82117a01" + }, + "dist": { + "type": "zip", + "url": "https://api.github.com/repos/wikimedia/IPSet/zipball/b71a3834b42e2bcb2d9fa037abbb654e82117a01", + "reference": "b71a3834b42e2bcb2d9fa037abbb654e82117a01", + "shasum": "" + }, + "require": { + "php": ">=5.3.3" + }, + "require-dev": { + "jakub-onderka/php-parallel-lint": "0.9.2", + "mediawiki/mediawiki-codesniffer": "0.5.1", + "phpunit/phpunit": "4.7.2" + }, + "time": "2016-02-12 15:19:10", + "type": "library", + "installation-source": "dist", + "autoload": { + "classmap": [ + "src/" + ] + }, + "notification-url": "https://packagist.org/downloads/", + "license": [ + "GPL-2.0+" + ], + "authors": [ + { + "name": "Brandon Black", + "email": "blbl...@gmail.com" + } + ], + "description": "Efficiently match IP addresses against a set of CIDR specifications.", + "homepage": "https://github.com/wikimedia/IPSet" } ] diff --git a/wikimedia/ip-set/src/IPSet.php b/wikimedia/ip-set/src/IPSet.php index 1c79f06..d8a417f 100644 --- a/wikimedia/ip-set/src/IPSet.php +++ b/wikimedia/ip-set/src/IPSet.php @@ -80,11 +80,11 @@ * a net loss in my test scenarios due to additional match complexity) */ class IPSet { - /** @var array $root4 The root of the IPv4 matching tree */ - private $root4 = array( false, false ); + /** @var array|bool $root4 The root of the IPv4 matching tree */ + private $root4 = false; - /** @var array $root6 The root of the IPv6 matching tree */ - private $root6 = array( false, false ); + /** @var array|bool $root6 The root of the IPv6 matching tree */ + private $root6 = false; /** * Instantiate the object from an array of CIDR specs @@ -98,11 +98,6 @@ foreach ( $cfg as $cidr ) { $this->addCidr( $cidr ); } - - self::recOptimize( $this->root4 ); - self::recCompress( $this->root4, 0, 24 ); - self::recOptimize( $this->root6 ); - self::recCompress( $this->root6, 0, 120 ); } /** @@ -140,29 +135,56 @@ } $rawOrd = array_map( 'ord', str_split( $raw ) ); - // special-case: zero mask overwrites the whole tree with a pair of terminal successes - if ( $mask == 0 ) { - $node = array( true, true ); - return; - } - // iterate the bits of the address while walking the tree structure for inserts + // at the end, $snode will point to the highest node that could only lead to a + // successful match (and thus can be set to true) + $snode =& $node; $curBit = 0; while ( 1 ) { - $maskShift = 7 - ( $curBit & 7 ); - $node =& $node[( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift]; - ++$curBit; if ( $node === true ) { // already added a larger supernet, no need to go deeper return; } elseif ( $curBit == $mask ) { // this may wipe out deeper subnets from earlier - $node = true; + $snode = true; return; } elseif ( $node === false ) { // create new subarray to go deeper - $node = array( false, false ); + if ( !( $curBit & 7 ) && $curBit <= $mask - 8 ) { + $node = array( 'comp' => $rawOrd[$curBit >> 3], 'next' => false ); + } else { + $node = array( false, false ); + } } + + if ( isset( $node['comp'] ) ) { + $comp = $node['comp']; + if ( $rawOrd[$curBit >> 3] == $comp && $curBit <= $mask - 8 ) { + // whole byte matches, skip over the compressed node + $node =& $node['next']; + $snode =& $node; + $curBit += 8; + continue; + } else { + // have to decompress the node and check individual bits + $unode = $node['next']; + for ( $i = 0; $i < 8; ++$i ) { + $unode = ( $comp & ( 1 << $i ) ) + ? array( false, $unode ) + : array( $unode, false ); + } + $node = $unode; + } + } + + $maskShift = 7 - ( $curBit & 7 ); + $index = ( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift; + if ( $node[$index ^ 1] !== true ) { + // no adjacent subnet, can't form a supernet at this level + $snode =& $node[$index]; + } + $node =& $node[$index]; + ++$curBit; } } @@ -188,7 +210,7 @@ } $curBit = 0; - while ( 1 ) { + while ( $node !== true && $node !== false ) { if ( isset( $node['comp'] ) ) { // compressed node, matches 1 whole byte on a byte boundary if ( $rawOrd[$curBit >> 3] != $node['comp'] ) { @@ -202,83 +224,8 @@ $node =& $node[( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift]; ++$curBit; } - - if ( $node === true || $node === false ) { - return $node; - } - } - } - - /** - * Recursively merges adjacent nets into larger supernets - * - * @param array &$node Tree node to optimize, by-reference - * - * e.g.: 8.0.0.0/8 + 9.0.0.0/8 -> 8.0.0.0/7 - */ - private static function recOptimize( &$node ) { - if ( $node[0] !== false && $node[0] !== true && self::recOptimize( $node[0] ) ) { - $node[0] = true; - } - if ( $node[1] !== false && $node[1] !== true && self::recOptimize( $node[1] ) ) { - $node[1] = true; - } - if ( $node[0] === true && $node[1] === true ) { - return true; - } - return false; - } - - /** - * Recursively compresses a tree - * - * @param array &$node Tree node to compress, by-reference - * @param integer $curBit current depth in the tree - * @param integer $maxCompStart maximum depth at which compression can start, family-specific - * - * This is a very simplistic compression scheme: if we go through a whole - * byte of address starting at a byte boundary with no real branching - * other than immediate false-vs-(node|true), compress that subtree down to a single - * byte-matching node. - * The $maxCompStart check elides recursing the final 7 levels of depth (family-dependent) - */ - private static function recCompress( &$node, $curBit, $maxCompStart ) { - if ( !( $curBit & 7 ) ) { // byte boundary, check for depth-8 single path(s) - $byte = 0; - $cnode =& $node; - $i = 8; - while ( $i-- ) { - if ( $cnode[0] === false ) { - $byte |= 1 << $i; - $cnode =& $cnode[1]; - } elseif ( $cnode[1] === false ) { - $cnode =& $cnode[0]; - } else { - // partial-byte branching, give up - break; - } - } - if ( $i == -1 ) { // means we did not exit the while() via break - $node = array( - 'comp' => $byte, - 'next' => &$cnode, - ); - $curBit += 8; - if ( $cnode !== true ) { - self::recCompress( $cnode, $curBit, $maxCompStart ); - } - return; - } } - ++$curBit; - if ( $curBit <= $maxCompStart ) { - if ( $node[0] !== false && $node[0] !== true ) { - self::recCompress( $node[0], $curBit, $maxCompStart ); - } - if ( $node[1] !== false && $node[1] !== true ) { - self::recCompress( $node[1], $curBit, $maxCompStart ); - } - } + return $node; } } -- To view, visit https://gerrit.wikimedia.org/r/287009 To unsubscribe, visit https://gerrit.wikimedia.org/r/settings Gerrit-MessageType: newchange Gerrit-Change-Id: Id43ca893fa6c7c6cb3b1eb23107e42a8f2bcceb8 Gerrit-PatchSet: 1 Gerrit-Project: mediawiki/vendor Gerrit-Branch: master Gerrit-Owner: Legoktm <legoktm.wikipe...@gmail.com> _______________________________________________ MediaWiki-commits mailing list MediaWiki-commits@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits