# 3.07 路由树-通配符匹配之路由注册

本节课工程结构如下:

```
(base) yanglei@yuanhong 11-embeddingRouterIntoServer % tree ./
./
├── context.go
├── handleFunc.go
├── httpServer.go
├── httpServer_test.go
├── node.go
├── router.go
├── router_test.go
└── serverInterface.go

0 directories, 8 files
```

## PART1. 学习路线

![学习路线](https://1407465062-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FyoSgzgsmuneFp7VNWUbE%2Fuploads%2Fgit-blob-9181d753fdf3c7db33e5b66260531391169b8905%2F%E5%AD%A6%E4%B9%A0%E8%B7%AF%E7%BA%BF.png?alt=media)

## PART2. 通配符匹配的定义与设计

### 2.1 通配符匹配的定义

通配符匹配:是指用`*`表达匹配任何路径

### 2.2 通配符匹配的设计

这里就要考虑定义中所说的**任何路径**.

#### Question1:若用户输入的URI为`/a/b/c`,能否命中`/a/*`?

这个问题本质上是我们作为设计者,要考虑**通配符`*`在路由中的语义,是只能代表1段路由,还是可以代表多段路由?**

这里我们选择**让通配符`*`只能表达1段路由**.

我们假定通配符`*`表达多段路由.那么从框架使用者的视角上来看,路由`/a/*`和`/a/*/*`就很让人困惑:当路由为`/a/b/c`时,究竟匹配到了哪个路由?

从框架设计者的视角上来看,就干脆不要给使用者做出这种不良实践的机会.

#### Question2:若注册了2个路由:`/user/123/home`和`/user/*/*`,那么用户输入路径`/user/123/detail`时,能否命中路由`/user/*/*`?

这个问题本质上是我们作为设计者,要考虑我们的**路由匹配过程是否可回溯?**

可回溯的匹配过程如下图示:

![可回溯的路由匹配过程](https://1407465062-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FyoSgzgsmuneFp7VNWUbE%2Fuploads%2Fgit-blob-df6cf399b13c3db5a27a41bb2ab11926a34139a5%2F%E5%8F%AF%E5%9B%9E%E6%BA%AF%E7%9A%84%E8%B7%AF%E7%94%B1%E5%8C%B9%E9%85%8D%E8%BF%87%E7%A8%8B.jpg?alt=media)

简单理解就是:当发现`/user/123/home`不能匹配`/user/123/detail`时,要回溯到`/user/*`节点进行进一步查找的过程.

可以做,但这是一个**投入大产出低的特性**.

这里我们选择不支持这种路由,有2个原因:

1. 可回溯的特性会使得你的代码变得非常复杂
2. 从框架设计者的角度上来讲,通过不提供这种匹配方式的做法,限制框架的使用者不能定义形如`/user/*/*`的路由.
   * `/user/*/*`不好的地方在于:当使用者A读使用者B的代码时,他一定是要非常清晰的了解一个前提:**当路由`/user/123/detail`不能匹配到`/user/123/home`时,则能够匹配到`/user/*/*`**.这样的代码可读性本身就不高,因此通过不提供支持回溯匹配过程的方式,限制使用者不要去写这种模糊的代码
   * 更进一步的,框架的使用者本身也不应该同时注册`/user/123/home`和`/user/*/*`这两个路由

## PART3. 实现通配符节点的创建

### 3.1 修改`Node`的结构

`node.go`:

```go
// node 路由树的节点
type node struct {
	// path 当前节点的路径
	path string

	// children 子路由路径到子节点的映射
	children map[string]*node
	
	// wildcardChild 通配符子节点
	wildcardChild *node

	// HandleFunc 路由对应的业务逻辑
	HandleFunc
}
```

由于通配符节点的逻辑是需要特殊处理的(不管在注册路由还是查找路由时),因此需要为`node`结构体单独定义表示其通配符子节点的成员属性.

### 3.2 定义测试用例

此处还是在`router_test.go`中新建一个函数用于测试通配符匹配:

```go
// TestRouter_wildcard 测试通配符路由的注册与查找
func TestRouter_wildcard(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{
		// 普通节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/order/*",
		},
	}

	r := newRouter()
	mockHandleFunc := func(ctx *Context) {}

	for _, testRoute := range testRoutes {
		r.addRoute(testRoute.method, testRoute.path, mockHandleFunc)
	}

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{
			http.MethodGet: {
				path: "/",
				children: map[string]*node{
					"order": {
						path:     "order",
						children: nil,
						wildcardChild: &node{
							path:          "*",
							children:      nil,
							wildcardChild: nil,
							HandleFunc:    mockHandleFunc,
						},
						HandleFunc: nil,
					},
				},
				wildcardChild: nil,
				HandleFunc:    nil,
			},
		},
	}

	msg, ok := wantRouter.equal(&r)
	assert.True(t, ok, msg)
}
```

现在运行这个测试用例,结果是不符合预期的:

```
/usr/local/go/bin/go tool test2json -t /private/var/folders/9x/kkdcw3dx7js8frvbxh8gns580000gn/T/dlvLauncher.sh /Users/yanglei/Applications/GoLand.app/Contents/plugins/go-plugin/lib/dlv/mac/dlv --listen=127.0.0.1:57140 --headless=true --api-version=2 --check-go-version=false --only-same-user=false exec /Users/yanglei/Library/Caches/JetBrains/GoLand2023.2/tmp/GoLand/___TestRouter_wildcard_in_server_12_matchWildcard.test -- -test.v -test.paniconexit0 -test.run ^\QTestRouter_wildcard\E$
=== RUN   TestRouter_wildcard
    router_test.go:426: 
        	Error Trace:	/Users/yanglei/Desktop/GO实战训练营/GoInAction/code/week1/server/12-matchWildcard/router_test.go:426
        	Error:      	Should be true
        	Test:       	TestRouter_wildcard
        	Messages:   	GET-两个节点的子节点数量不相等,源节点的子节点数量为 0,目标节点的子节点数量为 1
--- FAIL: TestRouter_wildcard (0.00s)

FAIL
```

很明显,按我们现在的逻辑,`/order/*`中,通配符`*`成为了`order`节点的子节点,而我们预期中通配符`*`应该是`order`节点的通配符子节点(也就是`wildcardChild`字段值).

![预期结果](https://1407465062-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FyoSgzgsmuneFp7VNWUbE%2Fuploads%2Fgit-blob-b893949e74f8a410e30b3a71bc828aea518ac9fc%2F%E9%A2%84%E6%9C%9F%E7%BB%93%E6%9E%9C.png?alt=media)

![实际结果](https://1407465062-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FyoSgzgsmuneFp7VNWUbE%2Fuploads%2Fgit-blob-52ae3898c2a1831493fe1b5ed43b0a850f8ef090%2F%E5%AE%9E%E9%99%85%E7%BB%93%E6%9E%9C.png?alt=media)

注:这里还是看他TDD的思路,是用测试用例告诉自己"哪里不符合预期".

很明显,在创建子节点的操作中出问题了.创建时不应该把`*`放在子节点集合里,而是应该放在`wildcardChild`字段上.

### 3.3 修改创建子节点的逻辑

`node.go`:

```go
// childOrCreate 本方法用于在节点上获取给定的子节点,如果给定的子节点不存在则创建
func (n *node) childOrCreate(segment string) *node {
	// 若路径为通配符 则查找当前节点的通配符子节点 或创建一个当前节点的通配符子节点 并返回
	if segment == "*" {
		if n.wildcardChild == nil {
			n.wildcardChild = &node{
				path: segment,
			}
		}
		return n.wildcardChild
	}

	// 如果当前节点的子节点映射为空 则创建一个子节点映射
	if n.children == nil {
		n.children = map[string]*node{}
	}

	res, ok := n.children[segment]
	// 如果没有找到子节点,则创建一个子节点
	// 否则返回找到的子节点
	if !ok {
		res = &node{
			path: segment,
		}
		n.children[segment] = res
	}
	return res
}
```

`childOrCreate()`方法中,添加了单独处理通配符子节点的逻辑.注意在`childOrCreate()`方法并不需要单独检测通配符子节点是否重复注册,因为其调用者`router.addRoute()`方法中有这个逻辑,不需要也不应该在`childOrCreate()`方法中检测通配符子节点是否重复注册.

这时候再去跑测试用例,实际上就已经通过了.

### 3.4 修改判断子节点相等的逻辑

在比对完两个节点的子节点映射数量之后,还要比对两个节点的通配符子节点是否相同.

`router_test.go`:

```go
// equal 比较两棵路由树是否相等
// msg: 两棵路由树不相等时的错误信息
// ok: 两棵路由树是否相等
func (n *node) equal(target *node) (msg string, ok bool) {
	// 如果目标节点为nil 则不相等
	if target == nil {
		return fmt.Sprintf("目标节点为nil"), false
	}

	// 如果两个节点的path不相等 则不相等
	if n.path != target.path {
		return fmt.Sprintf("两个节点的path不相等,源节点的path为 %s,目标节点的path为 %s", n.path, target.path), false
	}

	// 若两个节点的子节点数量不相等 则不相等
	nChildrenNum := len(n.children)
	yChildrenNum := len(target.children)
	if nChildrenNum != yChildrenNum {
		return fmt.Sprintf("两个节点的子节点数量不相等,源节点的子节点数量为 %d,目标节点的子节点数量为 %d", nChildrenNum, yChildrenNum), false
	}

	// 若两个节点的通配符子节点不相等 则不相等
	if n.wildcardChild != nil {
		if target.wildcardChild == nil {
			return fmt.Sprintf("目标节点的通配符子节点为空"), false
		}
		_, wildcardIsEqual := n.wildcardChild.equal(target.wildcardChild)
		if !wildcardIsEqual {
			return fmt.Sprintf("两个节点的通配符子节点不相等"), false
		}
	}

	// 若两个节点的handleFunc类型不同 则不相等
	nHandler := reflect.ValueOf(n.HandleFunc)
	yHandler := reflect.ValueOf(target.HandleFunc)
	if nHandler != yHandler {
		return fmt.Sprintf("%s节点的handleFunc不相等,源节点的handleFunc为 %v,目标节点的handleFunc为 %v", n.path, nHandler.Type().String(), yHandler.Type().String()), false
	}

	// 比对两个节点的子节点映射是否相等
	for path, child := range n.children {
		dstChild, ok := target.children[path]
		// 如果源节点的子节点中 存在目标节点没有的子节点 则不相等
		if !ok {
			return fmt.Sprintf("目标节点的子节点中没有path为 %s 的子节点", path), false
		}

		// 比对两个子节点是否相等
		msg, equal := child.equal(dstChild)
		if !equal {
			return msg, false
		}
	}

	return "", true
}
```

添加了比对两个节点的通配符子节点是否相等的逻辑

注:这里我将原来的形参`y`改名为`target`,为了提升可读性.

再跑单测也还是能跑的通的.

### 3.5 添加其他测试用例

#### 3.5.1 根节点的通配符子节点

因为我们的实现中针对根节点有特殊逻辑,所以这里我们单独测试根节点的通配符子节点

`router_test.go`:

```go
// TestRouter_wildcard 测试通配符路由的注册与查找
func TestRouter_wildcard(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{
		// 普通节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/order/*",
		},
		// 根节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*",
		},
	}

	r := newRouter()
	mockHandleFunc := func(ctx *Context) {}

	for _, testRoute := range testRoutes {
		r.addRoute(testRoute.method, testRoute.path, mockHandleFunc)
	}

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{
			http.MethodGet: {
				path: "/",
				children: map[string]*node{
					"order": {
						path:     "order",
						children: nil,
						wildcardChild: &node{
							path:          "*",
							children:      nil,
							wildcardChild: nil,
							HandleFunc:    mockHandleFunc,
						},
						HandleFunc: nil,
					},
				},
				wildcardChild: &node{
					path:          "*",
					children:      nil,
					wildcardChild: nil,
					HandleFunc:    mockHandleFunc,
				},
				HandleFunc: nil,
			},
		},
	}

	msg, ok := wantRouter.equal(&r)
	assert.True(t, ok, msg)
}
```

跑单测能够顺利通过.

#### 3.5.2 通配符子节点的通配符子节点

`router_test.go`:

```go
// TestRouter_wildcard 测试通配符路由的注册与查找
func TestRouter_wildcard(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{
		// 普通节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/order/*",
		},
		// 根节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*",
		},
		// 通配符子节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*/*",
		},
	}

	r := newRouter()
	mockHandleFunc := func(ctx *Context) {}

	for _, testRoute := range testRoutes {
		r.addRoute(testRoute.method, testRoute.path, mockHandleFunc)
	}

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{
			http.MethodGet: {
				path: "/",
				children: map[string]*node{
					"order": {
						path:     "order",
						children: nil,
						wildcardChild: &node{
							path:          "*",
							children:      nil,
							wildcardChild: nil,
							HandleFunc:    mockHandleFunc,
						},
						HandleFunc: nil,
					},
				},
				wildcardChild: &node{
					path:     "*",
					children: nil,
					wildcardChild: &node{
						path:          "*",
						children:      nil,
						wildcardChild: nil,
						HandleFunc:    mockHandleFunc,
					},
					HandleFunc: mockHandleFunc,
				},
				HandleFunc: nil,
			},
		},
	}

	msg, ok := wantRouter.equal(&r)
	assert.True(t, ok, msg)
}
```

#### 3.5.3 通配符子节点的普通子节点

`router_test.go`:

```go
// TestRouter_wildcard 测试通配符路由的注册与查找
func TestRouter_wildcard(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{
		// 普通节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/order/*",
		},
		// 根节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*",
		},
		// 通配符子节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*/*",
		},
		// 通配符子节点的普通子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*/*/order",
		},
	}

	r := newRouter()
	mockHandleFunc := func(ctx *Context) {}

	for _, testRoute := range testRoutes {
		r.addRoute(testRoute.method, testRoute.path, mockHandleFunc)
	}

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{
			http.MethodGet: {
				path: "/",
				children: map[string]*node{
					"order": {
						path:     "order",
						children: nil,
						wildcardChild: &node{
							path:          "*",
							children:      nil,
							wildcardChild: nil,
							HandleFunc:    mockHandleFunc,
						},
						HandleFunc: nil,
					},
				},
				wildcardChild: &node{
					path:     "*",
					children: nil,
					wildcardChild: &node{
						path: "*",
						children: map[string]*node{
							"order": {
								path:          "order",
								children:      nil,
								wildcardChild: nil,
								HandleFunc:    mockHandleFunc,
							},
						},
						wildcardChild: nil,
						HandleFunc:    mockHandleFunc,
					},
					HandleFunc: mockHandleFunc,
				},
				HandleFunc: nil,
			},
		},
	}

	msg, ok := wantRouter.equal(&r)
	assert.True(t, ok, msg)
}
```

#### 3.5.4 通配符子节点的普通子节点的通配符子节点

`router_test.go`:

```go
// TestRouter_wildcard 测试通配符路由的注册与查找
func TestRouter_wildcard(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{
		// 普通节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/order/*",
		},
		// 根节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*",
		},
		// 通配符子节点的通配符子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*/*",
		},
		// 通配符子节点的普通子节点测试用例
		{
			method: http.MethodGet,
			path:   "/*/*/order",
		},
		// 通配符子节点的普通子节点的通配符子节点
		{
			method: http.MethodGet,
			path:   "/*/*/order/*",
		},
	}

	r := newRouter()
	mockHandleFunc := func(ctx *Context) {}

	for _, testRoute := range testRoutes {
		r.addRoute(testRoute.method, testRoute.path, mockHandleFunc)
	}

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{
			http.MethodGet: {
				path: "/",
				children: map[string]*node{
					"order": {
						path:     "order",
						children: nil,
						wildcardChild: &node{
							path:          "*",
							children:      nil,
							wildcardChild: nil,
							HandleFunc:    mockHandleFunc,
						},
						HandleFunc: nil,
					},
				},
				wildcardChild: &node{
					path:     "*",
					children: nil,
					wildcardChild: &node{
						path: "*",
						children: map[string]*node{
							"order": {
								path:     "order",
								children: nil,
								wildcardChild: &node{
									path:          "*",
									children:      nil,
									wildcardChild: nil,
									HandleFunc:    mockHandleFunc,
								},
								HandleFunc: mockHandleFunc,
							},
						},
						wildcardChild: nil,
						HandleFunc:    mockHandleFunc,
					},
					HandleFunc: mockHandleFunc,
				},
				HandleFunc: nil,
			},
		},
	}

	msg, ok := wantRouter.equal(&r)
	assert.True(t, ok, msg)
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://go.sai.show/part03.-lu-you-shu/3.07-lu-you-shu-tong-pei-fu-pi-pei-zhi-lu-you-zhu-ce.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.