简单前缀树路由实现

最简易版

最开始只是使用composer 搭建了一个基础的项目，用来进行一些简单的接口处理，开始的路由定义如下：

在项目的根目录下定义了一个routes.php 文件

return [
 // import template
 'import' => [
 'method' => 'get',
 'dispatch' => [\App\Controllers\ImportController::class, 'index']
 ],

 // import data web api
 'import_data' => [
 'method' => 'post',
 'dispatch' => [\App\Controllers\ImportController::class, 'importData']
 ],

 'check_inc_pk' => [
 'method' => 'post',
 'dispatch' => [\App\Controllers\ImportController::class, 'checkIncPk']
 ],

 // testing
 'test' => [\App\Controllers\TestController::class, 'test'],
];

这返回一个path与方法的映射关联数组map，然后在入口文件进行判断

function send()
{
    $method = $_SERVER['REQUEST_METHOD'];
    
    $routes = require_once BASE_PATH . '/routes.php';
    
    $action = trim(input('action', ''));
    
    if (! array_key_exists($action, $routes)) {
    header("HTTP/1.0 404 Not Found");
    echo '404 Not Found';
    exit();
    }
    
    $route = $routes[$action];
    
    if (isset($route['method'], $route['dispatch'])) {
    if ($method !== strtoupper($route['method'])) {
    header("HTTP/1.0 404 Not Found");
    echo '404 Not Found';
    exit();
 }

 $service = new $route['dispatch'][0];
 $callback = [$service, $route['dispatch'][1]];

 } else {
 $service = new $routes[$action][0];
 $callback = [$service, $routes[$action][1]];
 }

 $args = [];
 $result = call_user_func_array($callback, $args);

 echo $result;
 exit();
}

这种实现方式简单是简单了，但是只能完成静态的路由绑定，无法完成动态路由解析的功能，什么是动态路由呢？

例如： /user/{id} 这种或者 /user/:id ，也就是后面的path参数是可变的，并能完成路由的解析, 我的目标是可以完成类似如下的功能：

# 可以解析动态路由 /user/:id

# 可以在路由定义简单的 闭包函数 完成具体的实现

# 可以在 闭包或者类方法中接受到 动态路由的参数

动态路由实现

通过了解，有一种叫做前缀树的实现方式，如下：

首先我们需要设计一个树的节点

class TrieNode
{
 public $children; // 子节点
 public $isEndOfRoute; 
 public $handler; // 节点对应绑定的实现方法
 public $paramName; // 参数名称

 public function __construct() {
 $this->children = [];
 $this->isEndOfRoute = false;
 $this->handler = [];
 $this->paramName = null;
 }
}

然后来定义一个树，应该包含添加与查找的功能

class Trie
{
 private $root;

 public function __construct() {
     $this->root = new TrieNode();
 }

 /**
 * 这个方法用来单独添加绑定一个路由
 * @param $method
 * @param $path
 * @param $handler
 * @return void
 */
 public function insert($method, $path, $handler) {
     $node = $this->root;

     // 拆分 path
     $parts = explode('/', trim($path, '/'));
    
     foreach ($parts as $part) {
    
     // $part[0] Get the first character of a string
     // 这里获取字符串第一个字符 判断是否为 :
     // 是否为动态绑定
     if ($part !== '' && $part[0] === ':') {
     // Path parameter name   :id  param = id
     // 使用 substr 去除字符串前面的 : 得到需要的path参数的名称
     $paramName = substr($part, 1);

     // 使用:param 来进行判断是否存在动态的绑定 不存在则进行设置
     if (!isset($node->children[':param'])) {
         $node->children[':param'] = new TrieNode();
         $node->children[':param']->paramName = $paramName;
     }
     $node = $node->children[':param'];

 } else {
     // 普通的路由绑定
     if (!isset($node->children[$part])) {
        $node->children[$part] = new TrieNode();
     }
         $node = $node->children[$part];
     }
 }

     // 设置路由的方法
     $node->isEndOfRoute = true;
     // 根据不同的请求类型进行绑定
     $node->handler[$method] = $handler;
 }

 /**
 * 在树中检索 返回node的handle 与 param
 * @param $method
 * @param $path
 * @return array
 */
 public function search($method, $path) {
     $node = $this->root;
     $parts = explode('/', trim($path, '/'));
     $params = [];
    
     foreach ($parts as $part) {
     if (isset($node->children[$part])) {
        $node = $node->children[$part];
     } elseif (isset($node->children[':param'])) {
         $node = $node->children[':param'];
         $params[$node->paramName] = $part;
     } else {
        return [null, array()];
     }
 }

     if ($node->isEndOfRoute && isset($node->handler[$method])) {
        return [$node->handler[$method], $params];
     }

     return [null, array()];
 }
}

最后定一个Router类来调用这个树的方法

class Router
{
     private $trie;

 public function __construct() {
     $this->trie = new Trie();
 }

 public function addRoute($method, $path, $handler) {
     $this->trie->insert(strtoupper($method), $path, $handler);
 }

 public function getRouteHandler($method, $path) {
     list($handler, $params) = $this->trie->search(strtoupper($method), $path);
     return array($handler, $params);
 }

 public function getTrie()
 {
     return $this->trie;
 }

 /**
 * @param $method
 * @param $path
 * @return mixed|string
 * @throws RouteNotFoundException
 */
 public function dispatch($method, $path, $args = []) {

     list($handler, $params) = $this->getRouteHandler($method, $path);
    
     if ($handler) {
     // 这里主要想实现 通过数组定义的方式
     // 有点类似laravel 例如
     // [\App\Controllers\TestController::class, 'test'] 这样绑定handle
     if (is_array($handler) && is_callable($handler)) {
     $call = new $handler[0];
     $action = $handler[1];
     $callback = [$call, $action];
    
     return call_user_func_array($callback, array_merge($params, $args));
     }
    
     if (is_callable($handler)) {
     // 因为我还需要为每个方法 默认绑定一个 Symfony的Request对象

     // call_user_func 依次传递对应的参数
     // function ($param) => $param is array
    
     // call_user_func_array 可以按数组传递对应的参数
     // function ($param, $args1, $args2) => $param is value
    
     return call_user_func_array($handler, array_merge($params, $args));
     }
     }
    
     throw new RouteNotFoundException('404 Not Found', 404);
 }
}

到此就可以进行路由的定义了，修改根目录的routes.php 文件

use App\Helpers\Router\Router;

$router = new Router();

$router->addRoute('GET','/test', [\App\Controllers\TestController::class, 'test']);

$router->addRoute('GET', '/user/:id', function($id, $request) {

 return "User ID: " . $id;
});

$router->addRoute('GET', '/user', function() {
 return "Get User";
});

return $router;

如何使用，在入口文件index.php 中测试一下

const BASE_PATH = __DIR__;

require BASE_PATH . '/vendor/autoload.php';

$router = require_once BASE_PATH . '/routes.php';

$request = \request(); // 返回 Symfony的Request对象
$path = $request->getPathInfo();

$args['request'] = $request;
$response = $router->dispatch(strtoupper($method), $path, $args);

if ($response instanceof \Symfony\Component\HttpFoundation\Response) {
 $response->send();
}

echo $response;
exit();