MediaWiki  master
MediaWiki\Rest\PathTemplateMatcher\PathMatcher Class Reference

A tree-based path routing algorithm. More...

Public Member Functions

 add ( $template, $userData)
 Add a template to the matcher. More...
 
 getCacheData ()
 Get a data array for later use by newFromCache(). More...
 
 match ( $path)
 Match a path against the current match trees. More...
 

Static Public Member Functions

static newFromCache ( $data)
 Create a PathMatcher from cache data. More...
 

Private Member Functions

 findConflict ( $node, $parts, $index=0)
 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. More...
 
 getParamName ( $part)
 If a path template component is a parameter, return the parameter name. More...
 
 isParam ( $part)
 Determine whether a path template component is a parameter. More...
 

Private Attributes

array $treesByLength = []
 An array of trees indexed by the number of path components in the input. More...
 

Detailed Description

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.

Definition at line 16 of file PathMatcher.php.

Member Function Documentation

◆ add()

MediaWiki\Rest\PathTemplateMatcher\PathMatcher::add (   $template,
  $userData 
)

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.

Parameters
string$templateThe path template
mixed$userDataUser data used to identify the matched route to the caller of match()
Exceptions
PathConflict

Definition at line 149 of file PathMatcher.php.

References MediaWiki\Rest\PathTemplateMatcher\PathMatcher\findConflict(), and MediaWiki\Rest\PathTemplateMatcher\PathMatcher\getParamName().

Referenced by MediaWiki\Rest\Router\getMatchers().

◆ findConflict()

MediaWiki\Rest\PathTemplateMatcher\PathMatcher::findConflict (   $node,
  $parts,
  $index = 0 
)
private

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.

Parameters
array$nodeThe tree node to check against
string[]$parts The array of path template parts
int$indexThe current index into $parts
Returns
array|false

Definition at line 106 of file PathMatcher.php.

References MediaWiki\Rest\PathTemplateMatcher\PathMatcher\isParam().

Referenced by MediaWiki\Rest\PathTemplateMatcher\PathMatcher\add().

◆ getCacheData()

MediaWiki\Rest\PathTemplateMatcher\PathMatcher::getCacheData ( )

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.

Returns
array

Definition at line 57 of file PathMatcher.php.

References MediaWiki\Rest\PathTemplateMatcher\PathMatcher\$treesByLength.

◆ getParamName()

MediaWiki\Rest\PathTemplateMatcher\PathMatcher::getParamName (   $part)
private

If a path template component is a parameter, return the parameter name.

Otherwise, return false.

Parameters
string$part
Returns
string|false

Definition at line 79 of file PathMatcher.php.

References MediaWiki\Rest\PathTemplateMatcher\PathMatcher\isParam().

Referenced by MediaWiki\Rest\PathTemplateMatcher\PathMatcher\add().

◆ isParam()

MediaWiki\Rest\PathTemplateMatcher\PathMatcher::isParam (   $part)
private

Determine whether a path template component is a parameter.

Parameters
string$part
Returns
bool

Definition at line 67 of file PathMatcher.php.

Referenced by MediaWiki\Rest\PathTemplateMatcher\PathMatcher\findConflict(), and MediaWiki\Rest\PathTemplateMatcher\PathMatcher\getParamName().

◆ match()

MediaWiki\Rest\PathTemplateMatcher\PathMatcher::match (   $path)

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.

Parameters
string$path
Returns
array|false

Definition at line 196 of file PathMatcher.php.

References $path.

◆ newFromCache()

static MediaWiki\Rest\PathTemplateMatcher\PathMatcher::newFromCache (   $data)
static

Create a PathMatcher from cache data.

Parameters
array$dataThe data array previously returned by getCacheData()
Returns
PathMatcher

Definition at line 42 of file PathMatcher.php.

Referenced by MediaWiki\Rest\Router\getMatchers().

Member Data Documentation

◆ $treesByLength

array MediaWiki\Rest\PathTemplateMatcher\PathMatcher::$treesByLength = []
private

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.

Definition at line 34 of file PathMatcher.php.

Referenced by MediaWiki\Rest\PathTemplateMatcher\PathMatcher\getCacheData().


The documentation for this class was generated from the following file: