Web框架的快速路由实现

route_dict = {
    "/": index_route,
    "/api/user": user_route,
    "/api/manager": manager_route,
}

route_list = [
    ("/", index_route),
    ("/api/user/<user_id>", user_route),
    ("/api/manager", manager_route),
]

route_list = [
    ("", "/", index_route),
    ("", "/api/user/<user_id>", user_route),
    ("example.com", "/api/manager", manager_route_1),
    ("www.example.com", "/api/manager", manager_route_2),
]

class Route(object):
    def __init__(self, url: str):
        self.url: str = url

        # 用于后面匹配URL的正则表达式
        self.url_re = url
    
    # 用于格式化打印
    def __repr__(self):
        return f"<Route url={self.url}>"

class RouteNode(object):
    def __init__(
        self,
        route_list: Optional[List[Route]] = None,
        node: Optional[Dict[str, "RouteNode"]] = None,
    ):
        # 当URL包含正则时，可能会绑定多个路由
        self.route_list: List[Route] = route_list if route_list else []
        # 子节点与当前节点的映射关系
        self.node: Dict[str, "RouteNode"] = node if node else dict()
        # 如果当前的节点不是普通的字符串，而是正则表达式，那么就存储它的正则表达式的key名
        self.var_name: Optional[str] = None

class RouteTrie(object):
    def __init__(self) -> None:
        # 构造树的根节点
        self.root_node: "RouteNode" = RouteNode()

    def insert(self, route: Route) -> None:
        """向路由树插入节点的功能"""
        cur_node: "RouteNode" = self.root_node
        for node_url in route.url.strip().split("/"):
            # 按/拆分URL
            if node_url and "<" == node_url[0] and ">" == node_url[-1]:
                # 如果属于正则的URL就存储变量名，并替换url，方便后面通过正则匹配
                cur_node.var_name = node_url[1:-1]
                route.url_re = route.url_re.replace(node_url, "(\w+)")
                break
            elif node_url not in cur_node.node:
                # 如果是普通的URL则构建子节点并与自己建立映射关系
                cur_node.node[node_url] = RouteNode()
            cur_node = cur_node.node[node_url]
        # 为当前节点绑定路由
        cur_node.route_list.append(route)

    def _search_node(self, url_path: str) -> Tuple[RouteNode, Dict]:
        """通过路由树查找节点"""
        cur_node = self.root_node
        var_dict = {}
        for url_node in url_path.strip().split("/"):
            # 按/拆分URL
            if url_node in cur_node.node:
                # 对于普通路由则通过映射关系找到下一个节点
                cur_node = cur_node.node[url_node]
            elif cur_node.var_name:
                # 对于正则路由则附上变量的值
                var_dict[cur_node.var_name] = url_node
                break
        return cur_node, var_dict

    def search(self, url_path: str) -> Tuple[Optional[Route], Dict]:
        # 根据URL查出对应的节点
        cur_node, var_dict = self._search_node(url_path)
        if var_dict and cur_node.route_list:
            # 如果是带有正则的URL，需要遍历匹配每个路由
            for route in cur_node.route_list:
                if re.match(route.url_re, url_path):
                    return route, var_dict
        elif cur_node.route_list:
            # 如果是普通的URL，直接返回节点的第一个路由
            return cur_node.route_list[0], var_dict
        # 如果当前节点并没有绑定路由，那么寻找失败
        return None, var_dict

route_trie = RouteTrie()
route_trie.insert(Route("/api/user/create"))
route_trie.insert(Route("/api/user/delete"))
route_trie.insert(Route("/api/user/<user_id>/info"))
route_trie.insert(Route("/api/blog/list"))
route_trie.insert(Route("/api/blog/content"))
route_trie.insert(Route("/api/blog/comment"))
route_trie.insert(Route("/internal/metric"))
route_trie.insert(Route("/internal/info"))
route_trie.insert(Route("/internal/health"))

print(route_trie.search("/api/user/create"))
# >>> (<Route url=/api/user/create>, {})
print(route_trie.search("/api/user/123"))
# >>> (None, {'user_id': '123'})
print(route_trie.search("/api/user/123/info"))
# >>> (<Route url=/api/user/<user_id>/info>, {'user_id': '123'})
print(route_trie.search("/internal/health"))
# >>> (<Route url=/internal/health>, {})

from routers.compiled import CompiledTreeRouter

# 生成AST路由树
ctr = CompiledTreeRouter()


# 向路由树添加路由
for url in [
    "/api/user/create",
    "/api/user/delete",
    "/api/user/{user_id}/info",  # < -- ctr支持的URL是{user_id}而不是<user_id>
    "/api/blog/list",
    "/api/blog/content",
    "/api/blog/comment",
    "/internal/metric",
    "/internal/info",
    "/internal/health"
]:
    ctr.add_route(url, lambda : print(url))

# 匹配路由
# 第一次寻找路由时会通过路由树生成匹配逻辑代码，这里略
print(ctr.find_responder("/api/user/create"))
# (<function <lambda> at 0x7f70299cf1e0>, {})
print(ctr.find_responder("/api/user/123"))
# (None, {'user_id': '123'})
print(ctr.find_responder("/api/user/123/info"))
# (<function <lambda> at 0x7f702980af28>, {'user_id': '123'})
print(ctr.find_responder("/internal/health"))
# (<function <lambda> at 0x7f702980e488>, {})
print(ctr.find_responder("/internal/health")[0]())
# "/internal/health"

def find(path, responders, expressions, params):
  path_len = len(path)
  if path_len > 0 and path[0] == "api":
    if path_len > 1 and path[1] == "user":
      if path_len > 2 and path[2] == "create":
        return responders[0]
      if path_len > 2 and path[2] == "delete":
        return responders[1]
      if path_len > 2:
        params["user_id"] = path[2]
        if path_len > 3 and path[3] == "info":
          return responders[2]
    if path_len > 1 and path[1] == "blog":
      if path_len > 2 and path[2] == "list":
        return responders[3]
      if path_len > 2 and path[2] == "content":
        return responders[4]
      if path_len > 2 and path[2] == "comment":
        return responders[5]
  if path_len > 0 and path[0] == "internal":
    if path_len > 1 and path[1] == "metric":
      return responders[6]
    if path_len > 1 and path[1] == "info":
      return responders[7]
    if path_len > 1 and path[1] == "health":
      return responders[8]