# 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`的路由,那么我们预期的路由树结构应该如下图示:

![预期路由树结构](https://1407465062-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FyoSgzgsmuneFp7VNWUbE%2Fuploads%2Fgit-blob-8c0630e31d6bc8696000f0daa2d5d7e3444b20bb%2F%E9%A2%84%E6%9C%9F%E8%B7%AF%E7%94%B1%E6%A0%91%E7%BB%93%E6%9E%84.jpg?alt=media)

```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. 但更深层次的原因是,他写了单测,才能支持他把代码运行起来.我以后也得考虑用这种方式开发,会高效很多