MediaWiki  master
PathMatcher.php
Go to the documentation of this file.
1 <?php
2 
4 
16 class PathMatcher {
34  private $treesByLength = [];
35 
42  public static function newFromCache( $data ) {
43  $matcher = new self;
44  $matcher->treesByLength = $data;
45  return $matcher;
46  }
47 
57  public function getCacheData() {
58  return $this->treesByLength;
59  }
60 
67  private function isParam( $part ) {
68  $partLength = strlen( $part );
69  return $partLength > 2 && $part[0] === '{' && $part[$partLength - 1] === '}';
70  }
71 
79  private function getParamName( $part ) {
80  if ( $this->isParam( $part ) ) {
81  return substr( $part, 1, -1 );
82  } else {
83  return false;
84  }
85  }
86 
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
109  return $node;
110  }
111  $part = $parts[$index];
112  $result = false;
113  if ( $this->isParam( $part ) ) {
114  foreach ( $node as $key => $childNode ) {
115  $result = $this->findConflict( $childNode, $parts, $index + 1 );
116  if ( $result !== false ) {
117  break;
118  }
119  }
120  } else {
121  if ( isset( $node["=$part"] ) ) {
122  $result = $this->findConflict( $node["=$part"], $parts, $index + 1 );
123  }
124  if ( $result === false && isset( $node['*'] ) ) {
125  $result = $this->findConflict( $node['*'], $parts, $index + 1 );
126  }
127  }
128  return $result;
129  }
130 
149  public function add( $template, $userData ) {
150  $parts = explode( '/', $template );
151  $length = count( $parts );
152  if ( !isset( $this->treesByLength[$length] ) ) {
153  $this->treesByLength[$length] = [];
154  }
155  $tree =& $this->treesByLength[$length];
156  $conflict = $this->findConflict( $tree, $parts );
157  if ( $conflict !== false ) {
158  throw new PathConflict( $template, $userData, $conflict );
159  }
160 
161  $params = [];
162  foreach ( $parts as $index => $part ) {
163  $paramName = $this->getParamName( $part );
164  if ( $paramName !== false ) {
165  $params[] = $paramName;
166  $key = '*';
167  } else {
168  $key = "=$part";
169  }
170  if ( $index === $length - 1 ) {
171  $tree[$key] = [
172  'template' => $template,
173  'paramNames' => $params,
174  'userData' => $userData
175  ];
176  } elseif ( !isset( $tree[$key] ) ) {
177  $tree[$key] = [];
178  }
179  $tree =& $tree[$key];
180  }
181  }
182 
196  public function match( $path ) {
197  $parts = explode( '/', $path );
198  $length = count( $parts );
199  if ( !isset( $this->treesByLength[$length] ) ) {
200  return false;
201  }
202  $node = $this->treesByLength[$length];
203 
204  $paramValues = [];
205  foreach ( $parts as $part ) {
206  if ( isset( $node["=$part"] ) ) {
207  $node = $node["=$part"];
208  } elseif ( isset( $node['*'] ) ) {
209  $node = $node['*'];
210  $paramValues[] = $part;
211  } else {
212  return false;
213  }
214  }
215 
216  return [
217  'params' => array_combine( $node['paramNames'], $paramValues ),
218  'userData' => $node['userData']
219  ];
220  }
221 }
isParam( $part)
Determine whether a path template component is a parameter.
Definition: PathMatcher.php:67
findConflict( $node, $parts, $index=0)
Recursively search the match tree, checking whether the proposed path template, passed as an array of...
getParamName( $part)
If a path template component is a parameter, return the parameter name.
Definition: PathMatcher.php:79
A tree-based path routing algorithm.
Definition: PathMatcher.php:16
array $treesByLength
An array of trees indexed by the number of path components in the input.
Definition: PathMatcher.php:34
getCacheData()
Get a data array for later use by newFromCache().
Definition: PathMatcher.php:57
static newFromCache( $data)
Create a PathMatcher from cache data.
Definition: PathMatcher.php:42
add( $template, $userData)
Add a template to the matcher.
match( $path)
Match a path against the current match trees.