Page MenuHomeWickedGov Phorge
Files F5987565

PathMatcher.php
No OneTemporary
Actions

Size
6 KB
Referenced Files
None
Subscribers
None

PathMatcher.php
View Options

<?php
namespace MediaWiki\Rest\PathTemplateMatcher;
/**
* A tree-based path routing algorithm.
*
* This container builds defined routing templates into a tree, allowing
* paths to be efficiently matched against all templates. The match time is
* independent of the number of registered path templates.
*
* Efficient matching comes at the cost of a potentially significant setup time.
* We measured ~10ms for 1000 templates. Using getCacheData() and
* newFromCache(), this setup time may be amortized over multiple requests.
*/
class PathMatcher {
/**
* An array of trees indexed by the number of path components in the input.
*
* A tree node consists of an associative array in which the key is a match
* specifier string, and the value is another node. A leaf node, which is
* identifiable by its fixed depth in the tree, consists of an associative
* array with the following keys:
* - template: The path template string
* - paramNames: A list of parameter names extracted from the template
* - userData: The user data supplied to add()
*
* A match specifier string may be either "*", which matches any path
* component, or a literal string prefixed with "=", which matches the
* specified deprefixed string literal.
*
* @var array
*/
private $treesByLength = [];
/**
* Create a PathMatcher from cache data
*
* @param array $data The data array previously returned by getCacheData()
* @return PathMatcher
*/
public static function newFromCache( $data ) {
$matcher = new self;
$matcher->treesByLength = $data;
return $matcher;
}
/**
* Get a data array for later use by newFromCache().
*
* The internal format is private to PathMatcher, but note that it includes
* any data passed as $userData to add(). The array returned will be
* serializable as long as all $userData values are serializable.
*
* @return array
*/
public function getCacheData() {
return $this->treesByLength;
}
/**
* Determine whether a path template component is a parameter
*
* @param string $part
* @return bool
*/
private function isParam( $part ) {
$partLength = strlen( $part );
return $partLength > 2 && $part[0] === '{' && $part[$partLength - 1] === '}';
}
/**
* If a path template component is a parameter, return the parameter name.
* Otherwise, return false.
*
* @param string $part
* @return string|false
*/
private function getParamName( $part ) {
if ( $this->isParam( $part ) ) {
return substr( $part, 1, -1 );
} else {
return false;
}
}
/**
* Recursively search the match tree, checking whether the proposed path
* template, passed as an array of component parts, can be added to the
* matcher without ambiguity.
*
* Ambiguity means that a path exists which matches multiple templates.
*
* The function calls itself recursively, incrementing $index so as to
* ignore a prefix of the input, in order to check deeper parts of the
* match tree.
*
* If a conflict is discovered, the conflicting leaf node is returned.
* Otherwise, false is returned.
*
* @param array $node The tree node to check against
* @param string[] $parts The array of path template parts
* @param int $index The current index into $parts
* @return array|false
*/
private function findConflict( $node, $parts, $index = 0 ) {
if ( $index >= count( $parts ) ) {
// If we reached the leaf node then a conflict is detected
return $node;
}
$part = $parts[$index];
$result = false;
if ( $this->isParam( $part ) ) {
foreach ( $node as $childNode ) {
// Params and tree entries for trailing empty slashes ('=') do not conflict
if ( !isset( $node['='] ) ) {
$result = $this->findConflict( $childNode, $parts, $index + 1 );
if ( $result !== false ) {
break;
}
}
}
} else {
if ( isset( $node["=$part"] ) ) {
$result = $this->findConflict( $node["=$part"], $parts, $index + 1 );
}
// Trailing empty slashes (aka an empty $part) do not conflict with params
if ( $result === false && isset( $node['*'] ) && $part !== '' ) {
$result = $this->findConflict( $node['*'], $parts, $index + 1 );
}
}
return $result;
}
/**
* Add a template to the matcher.
*
* The path template consists of components separated by "/". Each component
* may be either a parameter of the form {paramName}, or a literal string.
* A parameter matches any input path component, whereas a literal string
* matches itself.
*
* Path templates must not conflict with each other, that is, any input
* path must match at most one path template. If a path template conflicts
* with another already registered, this function throws a PathConflict
* exception.
*
* @param string $template The path template
* @param mixed $userData User data used to identify the matched route to
* the caller of match()
* @throws PathConflict|PathSegmentException
*/
public function add( $template, $userData ) {
// This will produce an empty part before any leading slash and after any trailing slash
$parts = explode( '/', $template );
$length = count( $parts );
if ( !isset( $this->treesByLength[$length] ) ) {
$this->treesByLength[$length] = [];
}
$tree =& $this->treesByLength[$length];
// Disallow empty path parts within the path (but not leading or trailing).
for ( $i = 1; $i < $length - 1; $i++ ) {
if ( $parts[$i] == '' ) {
throw new PathSegmentException( $template, $userData );
}
}
$conflict = $this->findConflict( $tree, $parts );
if ( $conflict !== false ) {
throw new PathConflict( $template, $userData, $conflict );
}
$params = [];
foreach ( $parts as $index => $part ) {
$paramName = $this->getParamName( $part );
if ( $paramName !== false ) {
$params[] = $paramName;
$key = '*';
} else {
$key = "=$part";
}
if ( $index === $length - 1 ) {
$tree[$key] = [
'template' => $template,
'paramNames' => $params,
'userData' => $userData
];
} elseif ( !isset( $tree[$key] ) ) {
$tree[$key] = [];
}
$tree =& $tree[$key];
}
}
/**
* Match a path against the current match trees.
*
* If the path matches a previously added path template, an array will be
* returned with the following keys:
* - params: An array mapping parameter names to their detected values
* - userData: The user data passed to add(), which identifies the route
*
* If the path does not match any template, false is returned.
*
* @param string $path
* @return array|false
*/
public function match( $path ) {
$parts = explode( '/', $path );
$length = count( $parts );
if ( !isset( $this->treesByLength[$length] ) ) {
return false;
}
$node = $this->treesByLength[$length];
$paramValues = [];
foreach ( $parts as $part ) {
if ( isset( $node["=$part"] ) ) {
$node = $node["=$part"];
} elseif ( isset( $node['*'] ) ) {
$node = $node['*'];
$paramValues[] = $part;
} else {
return false;
}
}
return [
'params' => array_combine( $node['paramNames'], $paramValues ),
'userData' => $node['userData']
];
}
}

File Metadata

Mime Type
text/x-php
Expires
Sun, Oct 4, 00:29 (2 w, 6 d ago)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
89/91/8ef980e322af893251fb9db9ca71
Default Alt Text
PathMatcher.php (6 KB)

Event Timeline