3 namespace MediaWiki\Rest\PathTemplateMatcher
;
6 * A tree-based path routing algorithm.
8 * This container builds defined routing templates into a tree, allowing
9 * paths to be efficiently matched against all templates. The match time is
10 * independent of the number of registered path templates.
12 * Efficient matching comes at the cost of a potentially significant setup time.
13 * We measured ~10ms for 1000 templates. Using getCacheData() and
14 * newFromCache(), this setup time may be amortized over multiple requests.
18 * An array of trees indexed by the number of path components in the input.
20 * A tree node consists of an associative array in which the key is a match
21 * specifier string, and the value is another node. A leaf node, which is
22 * identifiable by its fixed depth in the tree, consists of an associative
23 * array with the following keys:
24 * - template: The path template string
25 * - paramNames: A list of parameter names extracted from the template
26 * - userData: The user data supplied to add()
28 * A match specifier string may be either "*", which matches any path
29 * component, or a literal string prefixed with "=", which matches the
30 * specified deprefixed string literal.
34 private $treesByLength = [];
37 * Create a PathMatcher from cache data
39 * @param array $data The data array previously returned by getCacheData()
42 public static function newFromCache( $data ) {
44 $matcher->treesByLength
= $data;
49 * Get a data array for later use by newFromCache().
51 * The internal format is private to PathMatcher, but note that it includes
52 * any data passed as $userData to add(). The array returned will be
53 * serializable as long as all $userData values are serializable.
57 public function getCacheData() {
58 return $this->treesByLength
;
62 * Determine whether a path template component is a parameter
67 private function isParam( $part ) {
68 $partLength = strlen( $part );
69 return $partLength > 2 && $part[0] === '{' && $part[$partLength - 1] === '}';
73 * If a path template component is a parameter, return the parameter name.
74 * Otherwise, return false.
77 * @return string|false
79 private function getParamName( $part ) {
80 if ( $this->isParam( $part ) ) {
81 return substr( $part, 1, -1 );
88 * Recursively search the match tree, checking whether the proposed path
89 * template, passed as an array of component parts, can be added to the
90 * matcher without ambiguity.
92 * Ambiguity means that a path exists which matches multiple templates.
94 * The function calls itself recursively, incrementing $index so as to
95 * ignore a prefix of the input, in order to check deeper parts of the
98 * If a conflict is discovered, the conflicting leaf node is returned.
99 * Otherwise, false is returned.
101 * @param array $node The tree node to check against
102 * @param string[] $parts The array of path template parts
103 * @param int $index The current index into $parts
104 * @return array|false
106 private function findConflict( $node, $parts, $index = 0 ) {
107 if ( $index >= count( $parts ) ) {
108 // If we reached the leaf node then a conflict is detected
111 $part = $parts[$index];
113 if ( $this->isParam( $part ) ) {
114 foreach ( $node as $key => $childNode ) {
115 $result = $this->findConflict( $childNode, $parts, $index +
1 );
116 if ( $result !== false ) {
121 if ( isset( $node["=$part"] ) ) {
122 $result = $this->findConflict( $node["=$part"], $parts, $index +
1 );
124 if ( $result === false && isset( $node['*'] ) ) {
125 $result = $this->findConflict( $node['*'], $parts, $index +
1 );
132 * Add a template to the matcher.
134 * The path template consists of components separated by "/". Each component
135 * may be either a parameter of the form {paramName}, or a literal string.
136 * A parameter matches any input path component, whereas a literal string
139 * Path templates must not conflict with each other, that is, any input
140 * path must match at most one path template. If a path template conflicts
141 * with another already registered, this function throws a PathConflict
144 * @param string $template The path template
145 * @param mixed $userData User data used to identify the matched route to
146 * the caller of match()
147 * @throws PathConflict
149 public function add( $template, $userData ) {
150 $parts = explode( '/', $template );
151 $length = count( $parts );
152 if ( !isset( $this->treesByLength
[$length] ) ) {
153 $this->treesByLength
[$length] = [];
155 $tree =& $this->treesByLength
[$length];
156 $conflict = $this->findConflict( $tree, $parts );
157 if ( $conflict !== false ) {
158 throw new PathConflict( $template, $userData, $conflict );
162 foreach ( $parts as $index => $part ) {
163 $paramName = $this->getParamName( $part );
164 if ( $paramName !== false ) {
165 $params[] = $paramName;
170 if ( $index === $length - 1 ) {
172 'template' => $template,
173 'paramNames' => $params,
174 'userData' => $userData
176 } elseif ( !isset( $tree[$key] ) ) {
179 $tree =& $tree[$key];
184 * Match a path against the current match trees.
186 * If the path matches a previously added path template, an array will be
187 * returned with the following keys:
188 * - params: An array mapping parameter names to their detected values
189 * - userData: The user data passed to add(), which identifies the route
191 * If the path does not match any template, false is returned.
193 * @param string $path
194 * @return array|false
196 public function match( $path ) {
197 $parts = explode( '/', $path );
198 $length = count( $parts );
199 if ( !isset( $this->treesByLength
[$length] ) ) {
202 $node = $this->treesByLength
[$length];
205 foreach ( $parts as $part ) {
206 if ( isset( $node["=$part"] ) ) {
207 $node = $node["=$part"];
208 } elseif ( isset( $node['*'] ) ) {
210 $paramValues[] = $part;
217 'params' => array_combine( $node['paramNames'], $paramValues ),
218 'userData' => $node['userData']