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": "[email protected]"
- }
- ],
- "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": "[email protected]"
+ }
+ ],
+ "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 <[email protected]>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
