# 3.03 路由树-TDD起步

在有了类型定义之后,我们就可以考虑按照TDD的思路,用测试来驱动我们的实现.

我们使用简化版的TDD,即:

1. 定义API(这一步上节课已经定义好了)
2. 定义测试
3. 添加测试用例
4. 实现,并且确保实现能够通过测试用例
5. 重复3-4直到考虑了所有的场景
6. 重复步骤1-5

## PART1. 定义测试文件

初态工程结构如下:

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

0 directories, 7 files
```

我们本节课主要是针对路由树进行测试,实际上是要测试`router.AddRoute()`方法注册路由的结果是否符合预期.因此创建文件`router_test.go`

```
(base) yanglei@yuanhong 07-TDD % tree ./
./
├── context.go
├── handleFunc.go
├── httpServer.go
├── httpServer_test.go
├── node.go
├── router.go
├── router_test.go		// router.go的测试文件
└── serverInterface.go

0 directories, 8 files
```

### 1.1 构造与验证路由树

我们要测试的是注册路由后,路由树的结构和预期是否相同,因此测试分为2个步骤:

1. 构造路由树
2. 验证路由树

`router_test.go`:

```go
package tdd

import "testing"

// TestNode 测试路由树节点
// 由于此处我们要测试的是路由树的结构,因此不需要在测试路由树节点中添加路由处理函数
// 调用AddRoute时写死一个HandleFunc即可
type TestNode struct {
	method string
	path   string
}

// TestRouter_AddRoute 测试路由注册功能的结果是否符合预期
func TestRouter_AddRoute(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{}

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

	for _, testRoute := range testRoutes {
		r.AddRoute(testRoute.method, testRoute.path, mockHandleFunc)
	}
	
	// step2. 验证路由树
}
```

此处我们其实并不关心HandleFunc,因此也就没有在`TestNode`结构体上定义这个字段,调用`router.AddRoute()`方法时也是传入了一个mock值

### 1.2 断言路由树

注意断言的时候我们无法使用`assert.Equal()`,因为`HandleFunc`类型不是可比较的.也就是说以下代码是不行的:

```go
package tdd

import (
	"github.com/stretchr/testify/assert"
	"testing"
)

// TestNode 测试路由树节点
// 由于此处我们要测试的是路由树的结构,因此不需要在测试路由树节点中添加路由处理函数
// 调用AddRoute时写死一个HandleFunc即可
type TestNode struct {
	method string
	path   string
}

// TestRouter_AddRoute 测试路由注册功能的结果是否符合预期
func TestRouter_AddRoute(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{}

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

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

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{},
	}

	// HandleFunc类型是方法,方法不可比较,因此只能比较两个路由树的结构是否相等
	assert.Equal(t, wantRouter, r)
}
```

因此我们需要自定义判断二者是否相等的方法.

### 1.2.1 断言router是否相等

此处我们需要判断2个router是否相等.逻辑上很简单:

* 如果两个路由森林中的路由树数量不同,则不相等
* 如果目标router中没有对应HTTP方法的路由树,则不相等
* 比对相同HTTP方法的路由树结构是否相等.这个方法下一小节实现

```go
package tdd

import (
	"fmt"
	"github.com/stretchr/testify/assert"
	"testing"
)

// TestNode 测试路由树节点
// 由于此处我们要测试的是路由树的结构,因此不需要在测试路由树节点中添加路由处理函数
// 调用AddRoute时写死一个HandleFunc即可
type TestNode struct {
	method string
	path   string
}

// TestRouter_AddRoute 测试路由注册功能的结果是否符合预期
func TestRouter_AddRoute(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{}

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

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

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{},
	}

	// HandleFunc类型是方法,方法不可比较,因此只能比较两个路由树的结构是否相等
	assert.Equal(t, wantRouter, r)
}

// equal 比较两个路由森林是否相等
// msg: 两个路由森林不相等时的错误信息
// ok: 两个路由森林是否相等
func (r *router) equal(y *router) (msg string, ok bool) {
	// 如果两个路由森林中的路由树数量不同 则不相等
	rTreesNum := len(r.trees)
	yTreesNum := len(y.trees)
	if rTreesNum != yTreesNum {
		return fmt.Sprintf("路由森林中的路由树数量不相等,源路由森林有 %d 棵路由树, 目标路由森林有 %d 棵路由树", rTreesNum, yTreesNum), false
	}

	for method, tree := range r.trees {
		dstTree, ok := y.trees[method]

		// 如果目标router中没有对应HTTP方法的路由树 则不相等
		if !ok {
			return fmt.Sprintf("目标 router 中没有HTTP方法 %s的路由树", method), false
		}

		// 比对两棵路由树的结构是否相等
		msg, ok := tree.equal(dstTree)
	}
	return "", true
}

// equal 比较两棵路由树是否相等
func (n *node) equal(y *node) (msg string, ok bool) {

}
```

### 1.2.2 断言node是否相等

虽然上述代码的注释中写的是"比对两棵路由树的结构是否相等",但实际上它们都是`node`结构体的实例,因此在`node`结构体上实现`equal()`方法即可.

断言node是否相等的逻辑就稍微复杂一些:

* 如果目标节点为nil,则不相等
* 如果两个节点的path不相等,则不相等
* 若两个节点的子节点数量不相等,则不相等
* 若两个节点的handleFunc类型不同,则不相等(TODO:反射我用的很少,这块代码是直接抄的)
* 比对两个节点的子节点映射是否相等
  * 如果源节点的子节点中,存在目标节点没有的子节点,则不相等
  * 两个path相同的节点再次递归比对

```go
package tdd

import (
	"fmt"
	"github.com/stretchr/testify/assert"
	"reflect"
	"testing"
)

// TestNode 测试路由树节点
// 由于此处我们要测试的是路由树的结构,因此不需要在测试路由树节点中添加路由处理函数
// 调用AddRoute时写死一个HandleFunc即可
type TestNode struct {
	method string
	path   string
}

// TestRouter_AddRoute 测试路由注册功能的结果是否符合预期
func TestRouter_AddRoute(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{}

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

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

	// step2. 验证路由树 断言二者是否相等
	wantRouter := &router{
		trees: map[string]*node{},
	}

	// HandleFunc类型是方法,方法不可比较,因此只能比较两个路由树的结构是否相等
	// assert.Equal(t, wantRouter, r)

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

// equal 比较两个路由森林是否相等
// msg: 两个路由森林不相等时的错误信息
// ok: 两个路由森林是否相等
func (r *router) equal(y *router) (msg string, ok bool) {
	// 如果目标路由森林为nil 则不相等
	if y == nil {
		return fmt.Sprintf("目标路由森林为nil"), false
	}

	// 如果两个路由森林中的路由树数量不同 则不相等
	rTreesNum := len(r.trees)
	yTreesNum := len(y.trees)
	if rTreesNum != yTreesNum {
		return fmt.Sprintf("路由森林中的路由树数量不相等,源路由森林有 %d 棵路由树, 目标路由森林有 %d 棵路由树", rTreesNum, yTreesNum), false
	}

	for method, tree := range r.trees {
		dstTree, ok := y.trees[method]

		// 如果目标router中没有对应HTTP方法的路由树 则不相等
		if !ok {
			return fmt.Sprintf("目标 router 中没有HTTP方法 %s的路由树", method), false
		}

		// 比对两棵路由树的结构是否相等
		msg, equal := tree.equal(dstTree)
		if !equal {
			return method + "-" + msg, false
		}
	}
	return "", true
}

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

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

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

	// 比对handleFunc
	nHandler := reflect.ValueOf(n.HandleFunc)
	yHandler := reflect.ValueOf(y.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 := y.children[path]
		// 如果源节点的子节点中 存在目标节点没有的子节点 则不相等
		if !ok {
			return fmt.Sprintf("目标节点的子节点中没有path为 %s 的子节点", path), false
		}

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

	return "", true
}
```

## PART2. 添加测试用例

假定我们注册了一个名为`/user/home`的路由,那么我们预期的路由树结构应该如下图示:

![预期路由树结构](/files/vCIr10Ntt2u6ne6sgjdM)

```go
package tdd

import (
	"fmt"
	"github.com/stretchr/testify/assert"
	"net/http"
	"reflect"
	"testing"
)

// TestNode 测试路由树节点
// 由于此处我们要测试的是路由树的结构,因此不需要在测试路由树节点中添加路由处理函数
// 调用AddRoute时写死一个HandleFunc即可
type TestNode struct {
	method string
	path   string
}

// TestRouter_AddRoute 测试路由注册功能的结果是否符合预期
func TestRouter_AddRoute(t *testing.T) {
	// step1. 构造路由树
	testRoutes := []TestNode{
		{
			method: http.MethodGet,
			path:   "/user/home",
		},
	}

	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: &node{
				path: "/",
				children: map[string]*node{
					"user": &node{
						path: "user",
						children: map[string]*node{
							"home": &node{
								path:     "home",
								children: nil,
								// 注意路由是/user/home 因此只有最深层的节点才有handleFunc
								// /user和/ 都是没有handleFunc的
								HandleFunc: mockHandleFunc,
							},
						},
						HandleFunc: nil,
					},
				},
				HandleFunc: nil,
			},
		},
	}

	// HandleFunc类型是方法,方法不可比较,因此只能比较两个路由树的结构是否相等
	// assert.Equal(t, wantRouter, r)

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

// equal 比较两个路由森林是否相等
// msg: 两个路由森林不相等时的错误信息
// ok: 两个路由森林是否相等
func (r *router) equal(y *router) (msg string, ok bool) {
	// 如果目标路由森林为nil 则不相等
	if y == nil {
		return fmt.Sprintf("目标路由森林为nil"), false
	}

	// 如果两个路由森林中的路由树数量不同 则不相等
	rTreesNum := len(r.trees)
	yTreesNum := len(y.trees)
	if rTreesNum != yTreesNum {
		return fmt.Sprintf("路由森林中的路由树数量不相等,源路由森林有 %d 棵路由树, 目标路由森林有 %d 棵路由树", rTreesNum, yTreesNum), false
	}

	for method, tree := range r.trees {
		dstTree, ok := y.trees[method]

		// 如果目标router中没有对应HTTP方法的路由树 则不相等
		if !ok {
			return fmt.Sprintf("目标 router 中没有HTTP方法 %s的路由树", method), false
		}

		// 比对两棵路由树的结构是否相等
		msg, equal := tree.equal(dstTree)
		if !equal {
			return method + "-" + msg, false
		}
	}
	return "", true
}

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

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

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

	// 若两个节点的handleFunc类型不同 则不相等
	nHandler := reflect.ValueOf(n.HandleFunc)
	yHandler := reflect.ValueOf(y.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 := y.children[path]
		// 如果源节点的子节点中 存在目标节点没有的子节点 则不相等
		if !ok {
			return fmt.Sprintf("目标节点的子节点中没有path为 %s 的子节点", path), false
		}

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

	return "", true
}
```

需要注意的是,只有"home"节点是有HandleFunc的.因为最终路由是注册在"home"节点上的.

## PART3. 实现AddRoute方法

### 3.1 查找或创建子节点

#### 3.1.1 根据method查找根节点

这一步比较简单,根据根据method查找根节点,不存在则创建

`router.go`:

```go
package tdd

import "strings"

// router 路由森林 用于支持对路由树的操作
type router struct {
	// trees 路由森林 按HTTP动词组织路由树
	// 该map中 key为HTTP动词 value为路由树的根节点
	// 即: 每个HTTP动词对应一棵路由树 指向每棵路由树的根节点
	trees map[string]*node
}

// newRouter 创建路由森林
func newRouter() *router {
	return &router{
		trees: map[string]*node{},
	}
}

// AddRoute 注册路由到路由森林中的路由树上
func (r *router) AddRoute(method string, path string, handleFunc HandleFunc) {
	// step1. 找到路由树
	root, ok := r.trees[method]
	// 如果没有找到路由树,则创建一棵路由树
	if !ok {
		root = &node{
			path: "/",
		}
		r.trees[method] = root
	}
}
```

#### 3.1.2 在根节点上查找目标节点

这里就需要考虑:

* 若在根节点的children映射中查找到了目标节点,则添加HandleFunc后返回
* 若在根节点的children映射中没有查找到子节点,则创建目标节点
  * 树中途存在未被创建的节点,则创建该节点,然后以该节点为目标节点,继续创建子节点,直到找到目标节点为止
  * 为目标节点添加HandleFunc

`node.go`:

```go
package tdd

import "strings"

// router 路由森林 用于支持对路由树的操作
type router struct {
	// trees 路由森林 按HTTP动词组织路由树
	// 该map中 key为HTTP动词 value为路由树的根节点
	// 即: 每个HTTP动词对应一棵路由树 指向每棵路由树的根节点
	trees map[string]*node
}

// newRouter 创建路由森林
func newRouter() *router {
	return &router{
		trees: map[string]*node{},
	}
}

// AddRoute 注册路由到路由森林中的路由树上
func (r *router) AddRoute(method string, path string, handleFunc HandleFunc) {
	// step1. 找到路由树
	root, ok := r.trees[method]
	// 如果没有找到路由树,则创建一棵路由树
	if !ok {
		root = &node{
			path: "/",
		}
		r.trees[method] = root
	}

	// step2. 切割path
	// Tips: 去掉前导的"/" 否则直接切割出来的第一个元素为空字符串
	// Tips: 以下代码是老师写的去掉前导的"/"的方式 我认为表达力有点弱 但是性能应该会好于strings.TrimLeft
	// path = path[1:]
	path = strings.TrimLeft(path, "/")
	segments := strings.Split(path, "/")

	// step3. 为路由树添加路由
	// Tips: 此处我认为用target指代要添加路由的节点更好理解
	target := root
	for _, segment := range segments {
		// 如果路由树中途有节点没有创建,则创建该节点;
		// 如果路由树中途存在子节点,则找到该子节点
		child := target.childOrCreate(segment)
		// 继续为子节点创建子节点
		target = child
	}
	// 为目标节点设置HandleFunc
	target.HandleFunc = handleFunc
}
```

到这一步,就可以跑一下单测了

## 附录

### 发现自身的问题

1. 这里老师debug的过程是比我日常开发的方式要强很多的,我还是最古老的`fmt.Printf()`的方式
   * 学人家怎么用IDE去Debug的
2. 但更深层次的原因是,他写了单测,才能支持他把代码运行起来.我以后也得考虑用这种方式开发,会高效很多


---

# 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.03-lu-you-shu-tdd-qi-bu.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.