You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@dubbo.apache.org by zt...@apache.org on 2021/11/25 03:53:39 UTC
[dubbo-go-pixiu] branch develop updated: add trie for route (#262)
This is an automated email from the ASF dual-hosted git repository.
ztelur pushed a commit to branch develop
in repository https://gitbox.apache.org/repos/asf/dubbo-go-pixiu.git
The following commit(s) were added to refs/heads/develop by this push:
new 11535b0 add trie for route (#262)
11535b0 is described below
commit 11535b0fd11ac4d5f676148dc0ad8e64e730757e
Author: yqxu <31...@qq.com>
AuthorDate: Thu Nov 25 11:53:35 2021 +0800
add trie for route (#262)
* add trie for route
* bug fix
* bug fix
* merge master
* add assert for params
* add assert for params
* a/b should match prefix:a/b
* a/b should match prefix:a/b
* a/b should match prefix:a/b
* a/b should match prefix:a/b
* a/b should match prefix:a/b
* a/b should match prefix:a/b
* merge with master
* merge with master
* merge with master
* merge with master
* merge with master
* merge with master
* merge with master
* review dog
* review dog
* review dog
* review dog
* review dog
* add note
* add note
* add note
* add note
* remove chinese
* update
* remove chinese and fix reviewdog issues
Co-authored-by: yangqing.xyq <ya...@gongdao.com>
Co-authored-by: Mark4z <36...@users.noreply.github.com>
Co-authored-by: zhangxun <18...@163.com>
Co-authored-by: Randy <zt...@gmail.com>
---
pkg/adapter/dubboregistry/registry/registry.go | 2 -
pkg/common/constant/http.go | 7 +
pkg/common/http/manager_test.go | 28 +-
pkg/common/router/router.go | 65 +++--
pkg/common/router/router_test.go | 22 +-
pkg/common/router/trie/trie.go | 348 +++++++++++++++++++++++++
pkg/common/router/trie/trie_test.go | 133 ++++++++++
pkg/common/util/stringutil/stringutil.go | 54 ++++
pkg/config/conf_test.yaml | 6 -
pkg/config/config_load.go | 1 +
pkg/config/config_load_test.go | 9 +-
pkg/context/http/util.go | 62 -----
pkg/model/router.go | 101 ++-----
pkg/model/router_test.go | 267 -------------------
pkg/server/http.go | 14 +-
samples/http/simple/server/app/server.go | 4 +-
16 files changed, 627 insertions(+), 496 deletions(-)
diff --git a/pkg/adapter/dubboregistry/registry/registry.go b/pkg/adapter/dubboregistry/registry/registry.go
index ca41d15..cf02afc 100644
--- a/pkg/adapter/dubboregistry/registry/registry.go
+++ b/pkg/adapter/dubboregistry/registry/registry.go
@@ -148,9 +148,7 @@ func GetRouter() model.Router {
Match: model.RouterMatch{
Prefix: "",
Path: "",
- Regex: "",
Methods: nil,
- Headers: nil,
},
}
}
diff --git a/pkg/common/constant/http.go b/pkg/common/constant/http.go
index 2aa59cf..0a488bc 100644
--- a/pkg/common/constant/http.go
+++ b/pkg/common/constant/http.go
@@ -43,3 +43,10 @@ const (
PprofDefaultAddress = "0.0.0.0"
PprofDefaultPort = 7070
)
+
+const (
+ Get = "GET"
+ Put = "PUT"
+ Post = "POST"
+ Delete = "DELETE"
+)
diff --git a/pkg/common/http/manager_test.go b/pkg/common/http/manager_test.go
index f06acb0..38b9ab3 100644
--- a/pkg/common/http/manager_test.go
+++ b/pkg/common/http/manager_test.go
@@ -30,6 +30,7 @@ import (
import (
"github.com/apache/dubbo-go-pixiu/pkg/common/extension/filter"
+ "github.com/apache/dubbo-go-pixiu/pkg/common/router/trie"
contexthttp "github.com/apache/dubbo-go-pixiu/pkg/context/http"
"github.com/apache/dubbo-go-pixiu/pkg/context/mock"
"github.com/apache/dubbo-go-pixiu/pkg/logger"
@@ -91,29 +92,10 @@ func TestCreateHttpConnectionManager(t *testing.T) {
hcmc := model.HttpConnectionManagerConfig{
RouteConfig: model.RouteConfiguration{
- Routes: []*model.Router{
- {
- ID: "1",
- Match: model.RouterMatch{
- Prefix: "/api/v1",
- Methods: []string{
- "POST",
- },
- Path: "",
- Regex: "",
- Headers: []model.HeaderMatcher{
- {Name: "X-Dgp-Way",
- Values: []string{"Dubbo"},
- Regex: false,
- },
- },
- },
- Route: model.RouteAction{
- Cluster: "test_dubbo",
- ClusterNotFoundResponseCode: 505,
- },
- },
- },
+ RouteTrie: trie.NewTrieWithDefault("POST/api/v1/**", model.RouteAction{
+ Cluster: "test_dubbo",
+ ClusterNotFoundResponseCode: 505,
+ }),
Dynamic: false,
},
HTTPFilters: []*model.HTTPFilter{
diff --git a/pkg/common/router/router.go b/pkg/common/router/router.go
index 856a768..ddbd3ce 100644
--- a/pkg/common/router/router.go
+++ b/pkg/common/router/router.go
@@ -18,10 +18,14 @@
package router
import (
+ "strings"
"sync"
)
import (
+ "github.com/apache/dubbo-go-pixiu/pkg/common/constant"
+ "github.com/apache/dubbo-go-pixiu/pkg/common/router/trie"
+ "github.com/apache/dubbo-go-pixiu/pkg/common/util/stringutil"
"github.com/apache/dubbo-go-pixiu/pkg/context/http"
"github.com/apache/dubbo-go-pixiu/pkg/model"
"github.com/apache/dubbo-go-pixiu/pkg/server"
@@ -31,18 +35,17 @@ type (
// RouterCoordinator the router coordinator for http connection manager
RouterCoordinator struct {
activeConfig *model.RouteConfiguration
-
- rw sync.RWMutex
+ rw sync.RWMutex
}
)
// CreateRouterCoordinator create coordinator for http connection manager
func CreateRouterCoordinator(hcmc *model.HttpConnectionManagerConfig) *RouterCoordinator {
-
rc := &RouterCoordinator{activeConfig: &hcmc.RouteConfig}
if hcmc.RouteConfig.Dynamic {
server.GetRouterManager().AddRouterListener(rc)
}
+ rc.initTrie()
return rc
}
@@ -54,31 +57,61 @@ func (rm *RouterCoordinator) Route(hc *http.HttpContext) (*model.RouteAction, er
return rm.activeConfig.Route(hc.Request)
}
+func getTrieKey(method string, path string, isPrefix bool) string {
+ if isPrefix {
+ if !strings.HasSuffix(path, constant.PathSlash) {
+ path = path + constant.PathSlash
+ }
+ path = path + "**"
+ }
+ return stringutil.GetTrieKey(method, path)
+}
+
+func (rm *RouterCoordinator) initTrie() {
+ if rm.activeConfig.RouteTrie.IsEmpty() {
+ rm.activeConfig.RouteTrie = trie.NewTrie()
+ }
+ for _, router := range rm.activeConfig.Routes {
+ rm.OnAddRouter(router)
+ }
+}
+
// OnAddRouter add router
func (rm *RouterCoordinator) OnAddRouter(r *model.Router) {
+ //TODO: lock move to trie node
rm.rw.Lock()
defer rm.rw.Unlock()
-
- for _, old := range rm.activeConfig.Routes {
- if old.ID == r.ID {
- old.Route = r.Route
- old.Match = r.Match
- return
+ if r.Match.Methods == nil {
+ r.Match.Methods = []string{constant.Get, constant.Put, constant.Delete, constant.Post}
+ }
+ isPrefix := r.Match.Prefix != ""
+ for _, method := range r.Match.Methods {
+ var key string
+ if isPrefix {
+ key = getTrieKey(method, r.Match.Prefix, isPrefix)
+ } else {
+ key = getTrieKey(method, r.Match.Path, isPrefix)
}
+ _, _ = rm.activeConfig.RouteTrie.Put(key, r.Route)
}
-
- rm.activeConfig.Routes = append(rm.activeConfig.Routes, r)
}
// OnDeleteRouter delete router
-func (rm *RouterCoordinator) OnDeleteRouter(new *model.Router) {
+func (rm *RouterCoordinator) OnDeleteRouter(r *model.Router) {
rm.rw.Lock()
defer rm.rw.Unlock()
- for i, r := range rm.activeConfig.Routes {
- if r.ID == new.ID {
- rm.activeConfig.Routes = append(rm.activeConfig.Routes[:i], rm.activeConfig.Routes[i+1:]...)
- break
+ if r.Match.Methods == nil {
+ r.Match.Methods = []string{constant.Get, constant.Put, constant.Delete, constant.Post}
+ }
+ isPrefix := r.Match.Prefix != ""
+ for _, method := range r.Match.Methods {
+ var key string
+ if isPrefix {
+ key = getTrieKey(method, r.Match.Prefix, isPrefix)
+ } else {
+ key = getTrieKey(method, r.Match.Path, isPrefix)
}
+ _, _ = rm.activeConfig.RouteTrie.Remove(key)
}
}
diff --git a/pkg/common/router/router_test.go b/pkg/common/router/router_test.go
index 6a14980..fb3e42f 100644
--- a/pkg/common/router/router_test.go
+++ b/pkg/common/router/router_test.go
@@ -19,6 +19,7 @@ package router
import (
"bytes"
+ "github.com/apache/dubbo-go-pixiu/pkg/common/router/trie"
"net/http"
"testing"
)
@@ -35,23 +36,10 @@ import (
func TestCreateRouterCoordinator(t *testing.T) {
hcmc := model.HttpConnectionManagerConfig{
RouteConfig: model.RouteConfiguration{
- Routes: []*model.Router{
- {
- ID: "1",
- Match: model.RouterMatch{
- Prefix: "/api/v1",
- Methods: []string{
- "POST",
- },
- Path: "",
- Regex: "",
- },
- Route: model.RouteAction{
- Cluster: "test_dubbo",
- ClusterNotFoundResponseCode: 505,
- },
- },
- },
+ RouteTrie: trie.NewTrieWithDefault("POST/api/v1/**", model.RouteAction{
+ Cluster: "test_dubbo",
+ ClusterNotFoundResponseCode: 505,
+ }),
Dynamic: false,
},
HTTPFilters: []*model.HTTPFilter{
diff --git a/pkg/common/router/trie/trie.go b/pkg/common/router/trie/trie.go
new file mode 100644
index 0000000..d34b84d
--- /dev/null
+++ b/pkg/common/router/trie/trie.go
@@ -0,0 +1,348 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package trie
+
+import (
+ "github.com/pkg/errors"
+)
+
+import (
+ "github.com/apache/dubbo-go-pixiu/pkg/common/util/stringutil"
+ "github.com/apache/dubbo-go-pixiu/pkg/logger"
+)
+
+// Trie
+type Trie struct {
+ root Node
+}
+
+// NewTrie
+func NewTrie() Trie {
+ return Trie{root: Node{endOfPath: false, matchStr: ""}}
+}
+
+// NewTrieWithDefault
+func NewTrieWithDefault(path string, defVal interface{}) Trie {
+ ret := Trie{root: Node{endOfPath: false, matchStr: ""}}
+ _, _ = ret.Put(path, defVal)
+ return ret
+}
+
+// Node
+type Node struct {
+ matchStr string //abc match abc, :a match all words as a variable names a , * match all words ,** match all words and children.
+ children map[string]*Node // in path /a/b/c , b is child of a , c is child of b
+ PathVariablesSet map[string]*Node // in path /:a/b/c/:d , :a is a path variable node of level1 , :d is path variable node of level4
+ PathVariableNode *Node // in path /:a/b/c/:d , /b/c/:d is a child tree of pathVariable node :a ,and some special logic for match pathVariable it better not store in children.
+ MatchAllNode *Node // /a/b/** /** is a match all Node.
+ endOfPath bool // if true means a real path exists , /a/b/c/d only node of d is true, a,b,c is false.
+ bizInfo interface{} // route info and any other info store here.
+}
+
+//IsEmpty put key and values into trie as map.
+func (trie *Trie) IsEmpty() bool {
+ return trie.root.IsEmpty()
+}
+
+//Put put key and values into trie as map.
+func (trie *Trie) Put(withOutHost string, bizInfo interface{}) (bool, error) {
+ if bizInfo == nil {
+ return false, errors.Errorf("data to put should not be nil.")
+ }
+ parts := stringutil.Split(withOutHost)
+ return trie.root.internalPut(parts, bizInfo)
+}
+
+//Put put key and values into trie as map.
+func (trie *Trie) PutOrUpdate(withOutHost string, bizInfo interface{}) (bool, error) {
+ if bizInfo == nil {
+ return false, errors.Errorf("data to put should not be nil.")
+ }
+ parts := stringutil.Split(withOutHost)
+ if _, err := trie.Remove(withOutHost); err != nil {
+ logger.Infof("PutOrUpdate function remote (withOutHost{%s}) = error{%v}", withOutHost, err)
+ }
+ //if n != nil {
+ // //TODO: log n.bizInfo for trouble shooting
+ //}
+ return trie.root.internalPut(parts, bizInfo)
+}
+
+//Get get values according key.pathVariable not supported.
+func (trie Trie) Get(withOutHost string) (*Node, []string, bool, error) {
+ parts := stringutil.Split(withOutHost)
+ node, param, ok, e := trie.root.Get(parts)
+ length := len(param)
+ for i := 0; i < length/2; i++ {
+ temp := param[length-1-i]
+ param[length-1-i] = param[i]
+ param[i] = temp
+ }
+ return node, param, ok, e
+}
+
+//Match get values according url , pathVariable supported.
+// returns:
+//*Node this node in path, if not exists return nil
+//[]string reversed array of pathVariable value /valA/valB/valC matchs /:aa/:bb/:cc returns array of (valC,valB,valA)
+//bool is ok
+//error
+func (trie Trie) Match(withOutHost string) (*Node, []string, bool) {
+ parts := stringutil.Split(withOutHost)
+ node, param, ok := trie.root.Match(parts)
+ length := len(param)
+ for i := 0; i < length/2; i++ {
+ temp := param[length-1-i]
+ param[length-1-i] = param[i]
+ param[i] = temp
+ }
+ return node, param, ok
+}
+
+//Remove remove key and value from trie. logic delete can't release memory, rebuild if necessary when lake of memory.
+func (trie Trie) Remove(withOutHost string) (*Node, error) {
+ n, _, _, e := trie.Get(withOutHost)
+ if e != nil {
+ return nil, e
+ }
+ if n != nil {
+ n.endOfPath = false
+ }
+ return n, nil
+}
+
+//Contains return if key exists in trie
+func (trie Trie) Contains(withOutHost string) (bool, error) {
+ parts := stringutil.Split(withOutHost)
+ ret, _, _, e := trie.root.Get(parts)
+ if e != nil {
+ return true, e
+ }
+ return !(ret == nil), nil
+}
+
+//Put node put
+func (node *Node) internalPut(keys []string, bizInfo interface{}) (bool, error) {
+ // empty node initialization
+ if node.children == nil {
+ node.children = map[string]*Node{}
+ }
+ if len(keys) == 0 {
+ return true, nil
+ }
+
+ key := keys[0]
+ // isReal is the end of url path, means node is a place of url end,so the path with parentNode has a real url exists.
+ isReal := len(keys) == 1
+ isSuccess := node.put(key, isReal, bizInfo)
+
+ if !isSuccess {
+ return false, nil
+ }
+ childKeys := keys[1:]
+
+ if stringutil.IsPathVariableOrWildcard(key) {
+ return node.PathVariableNode.internalPut(childKeys, bizInfo)
+ } else if stringutil.IsMatchAll(key) {
+ return isSuccess, nil
+ } else {
+ return node.children[key].internalPut(childKeys, bizInfo)
+ }
+
+}
+
+//IsEmpty return true if empty
+func (node *Node) IsEmpty() bool {
+ if node.children == nil && node.matchStr == "" && node.PathVariableNode == nil && node.PathVariablesSet == nil {
+ return true
+ }
+ return false
+}
+
+//GetBizInfo get info
+func (node *Node) GetBizInfo() interface{} {
+ return node.bizInfo
+}
+
+//Match node match
+
+func (node *Node) Match(parts []string) (*Node, []string, bool) {
+ key := parts[0]
+ childKeys := parts[1:]
+ // isEnd is the end of url path, means node is a place of url end,so the path with parentNode has a real url exists.
+ isEnd := len(childKeys) == 0
+ if isEnd {
+
+ if node.children != nil && node.children[key] != nil && node.children[key].endOfPath {
+ return node.children[key], []string{}, true
+ }
+ //consider trie node ：/aaa/bbb/xxxxx/ccc/ddd /aaa/bbb/:id/ccc and request url is ：/aaa/bbb/xxxxx/ccc
+ if node.PathVariableNode != nil {
+ if node.PathVariableNode.endOfPath {
+ return node.PathVariableNode, []string{key}, true
+ }
+ }
+
+ } else {
+ if node.children != nil && node.children[key] != nil {
+ n, param, ok := node.children[key].Match(childKeys)
+ if ok {
+ return n, param, ok
+ }
+ }
+ if node.PathVariableNode != nil {
+ n, param, ok := node.PathVariableNode.Match(childKeys)
+ param = append(param, key)
+ if ok {
+ return n, param, ok
+ }
+ }
+ }
+ if node.children != nil && node.children[key] != nil && node.children[key].MatchAllNode != nil {
+ return node.children[key].MatchAllNode, []string{}, true
+ }
+ if node.MatchAllNode != nil {
+ return node.MatchAllNode, []string{}, true
+ }
+ return nil, nil, false
+}
+
+//Get node get
+// returns:
+//*Node this node in path, if not exists return nil
+//[]string key reversed array of pathVariable /:aa/:bb/:cc returns array of (cc,bb,aa)
+//bool is ok
+//error
+func (node *Node) Get(keys []string) (*Node, []string, bool, error) {
+ key := keys[0]
+ childKeys := keys[1:]
+ isReal := len(childKeys) == 0
+ if isReal {
+ // exit condition
+ if stringutil.IsPathVariableOrWildcard(key) {
+ if node.PathVariableNode == nil || !node.PathVariableNode.endOfPath {
+ return nil, nil, false, nil
+ }
+ return node.PathVariableNode, []string{stringutil.VariableName(key)}, true, nil
+ } else if stringutil.IsMatchAll(key) {
+ return node.MatchAllNode, nil, true, nil
+ } else {
+ if node.children == nil {
+ return nil, nil, false, nil
+ }
+ return node.children[key], nil, true, nil
+ }
+ } else {
+
+ if stringutil.IsPathVariableOrWildcard(key) {
+ if node.PathVariableNode == nil {
+ return nil, nil, false, nil
+ }
+ retNode, pathVariableList, ok, e := node.PathVariableNode.Get(childKeys)
+ newList := []string{key}
+ copy(newList[1:], pathVariableList)
+ return retNode, newList, ok, e
+ } else if stringutil.IsMatchAll(key) {
+ return nil, nil, false, errors.Errorf("router configuration is empty")
+ } else {
+ if node.children == nil || node.children[key] == nil {
+ return nil, nil, false, nil
+ }
+ return node.children[key].Get(childKeys)
+ }
+ }
+
+}
+
+func (node *Node) put(key string, isReal bool, bizInfo interface{}) bool {
+
+ if !stringutil.IsPathVariableOrWildcard(key) {
+ if stringutil.IsMatchAll(key) {
+ return node.putMatchAllNode(key, isReal, bizInfo)
+ } else {
+ return node.putNode(key, isReal, bizInfo)
+ }
+ }
+ pathVariable := stringutil.VariableName(key)
+ return node.putPathVariable(pathVariable, isReal, bizInfo)
+}
+
+func (node *Node) putPathVariable(pathVariable string, isReal bool, bizInfo interface{}) bool {
+ //path variable put
+ if node.PathVariableNode == nil {
+ node.PathVariableNode = &Node{endOfPath: false}
+ }
+ if node.PathVariableNode.endOfPath && isReal {
+ //has a node with same path exists. conflicted.
+ return false
+ }
+ if isReal {
+ node.PathVariableNode.bizInfo = bizInfo
+ node.PathVariableNode.matchStr = pathVariable
+ }
+ node.PathVariableNode.endOfPath = node.PathVariableNode.endOfPath || isReal
+ if node.PathVariablesSet == nil {
+ node.PathVariablesSet = map[string]*Node{}
+ }
+ node.PathVariablesSet[pathVariable] = node.PathVariableNode
+ return true
+}
+
+func (node *Node) putNode(matchStr string, isReal bool, bizInfo interface{}) bool {
+
+ selfNode := &Node{endOfPath: isReal, matchStr: matchStr}
+ old := node.children[matchStr]
+ if old != nil {
+ if old.endOfPath && isReal {
+ // already has one same path url
+ return false
+ }
+ selfNode = old
+ } else {
+ old = selfNode
+ }
+
+ if isReal {
+ selfNode.bizInfo = bizInfo
+ }
+ selfNode.endOfPath = selfNode.endOfPath || old.endOfPath
+ node.children[matchStr] = selfNode
+ return true
+}
+
+func (node *Node) putMatchAllNode(matchStr string, isReal bool, bizInfo interface{}) bool {
+
+ selfNode := &Node{endOfPath: isReal, matchStr: matchStr}
+ old := node.MatchAllNode
+ if old != nil {
+ if old.endOfPath && isReal {
+ // already has one same path url
+ return false
+ }
+ selfNode = old
+ } else {
+ old = selfNode
+ }
+
+ if isReal {
+ selfNode.bizInfo = bizInfo
+ }
+ selfNode.endOfPath = selfNode.endOfPath || old.endOfPath
+ node.MatchAllNode = selfNode
+ return true
+}
diff --git a/pkg/common/router/trie/trie_test.go b/pkg/common/router/trie/trie_test.go
new file mode 100644
index 0000000..0585734
--- /dev/null
+++ b/pkg/common/router/trie/trie_test.go
@@ -0,0 +1,133 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package trie
+
+import (
+ "github.com/stretchr/testify/assert"
+ "testing"
+)
+
+func TestTrie_Put(t *testing.T) {
+ trie := NewTrie()
+ ret, _ := trie.Put("/path1/:pathvarible1/path2/:pathvarible2", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path1/:pathvarible1/path2/:pathvarible2/**", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/:pathvarible1/path2/:pathvarible2", "")
+ assert.True(t, ret)
+ ret, _ = trie.Put("/path2/3/path2/:pathvarible2", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:pathvarible2", "")
+ assert.False(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:pathvarible2/3", "")
+ assert.True(t, ret)
+ ret, _ = trie.Put("/path2/3/path2/:432423/3", "")
+ assert.False(t, ret)
+ ret, _ = trie.Put("/path2/3/path2/:432423/3/a/b/c/d/:fdsa", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:432423/3/a/b/c/c/:fdsa", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:432423/3/a/b/c/c/:fdsafdsafsdafsda", "")
+ assert.False(t, ret)
+
+ ret, _ = trie.Put("/path1/:pathvarible1/path2/:pathvarible2/:fdsa", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path1/:432/path2/:34", "")
+ assert.False(t, ret)
+}
+
+func TestTrie_MatchAndGet(t *testing.T) {
+ trie := NewTrie()
+
+ ret, _ := trie.Put("/path1/:pathvarible1/path2/:pathvarible2", "test1")
+ assert.True(t, ret)
+
+ _, _ = trie.Put("/a/b", "ab")
+ result, _, _ := trie.Match("/a/b")
+ assert.Equal(t, result.GetBizInfo(), "ab")
+
+ _, _ = trie.Put("POST/api/v1/**", "ab")
+ result, _, _ = trie.Match("POST/api/v1")
+ assert.Equal(t, "ab", result.GetBizInfo())
+
+ ret, _ = trie.Put("/path2/:pathvarible1/path2/:pathvarible2", "")
+ assert.True(t, ret)
+ ret, _ = trie.Put("/path2/3/path2/:pathvarible2", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:pathvarible2", "")
+ assert.False(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:pathvarible2/3", "")
+ assert.True(t, ret)
+ ret, _ = trie.Put("/path2/3/path2/:432423/3", "")
+ assert.False(t, ret)
+ ret, _ = trie.Put("/path2/3/path2/:432423/3/a/b/c/d/:fdsa", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:432423/3/a/b/c/c/:fdsa", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path2/3/path2/:432423/3/a/b/c/c/:fdsafdsafsdafsda", "")
+ assert.False(t, ret)
+
+ ret, _ = trie.Put("/path1/:pathvarible1/path2/:pathvarible2/:fdsa", "")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/path1/:432/path2/:34", "")
+ assert.False(t, ret)
+
+ ret, _ = trie.Put("/a/:432/b/:34/**", "test**")
+ assert.True(t, ret)
+
+ ret, _ = trie.Put("/a/:432/b/:34/**", "")
+ assert.False(t, ret)
+
+ node, param, ok := trie.Match("/a/v1/b/v2/sadf/asdf")
+ assert.Equal(t, (param)[0], "v1")
+ assert.Equal(t, (param)[1], "v2")
+ assert.Equal(t, node.GetBizInfo(), "test**")
+ assert.True(t, ok)
+
+ _, param, ok = trie.Match("/a/v1/b/v2/sadf")
+ assert.Equal(t, (param)[0], "v1")
+ assert.Equal(t, (param)[1], "v2")
+ assert.Equal(t, node.GetBizInfo(), "test**")
+ assert.True(t, ok)
+
+ node, param, ok = trie.Match("/path1/v1/path2/v2")
+ assert.True(t, ok)
+ assert.True(t, len(param) == 2)
+ assert.Equal(t, (param)[0], "v1")
+ assert.Equal(t, (param)[1], "v2")
+ assert.True(t, node.GetBizInfo() == "test1")
+
+ _, _, ok, _ = trie.Get("/path1/v1/path2/v2")
+ assert.False(t, ok)
+
+ node, _, ok, _ = trie.Get("/path1/:p/path2/:p2")
+ assert.True(t, ok)
+ assert.True(t, node.GetBizInfo() == "test1")
+}
diff --git a/pkg/common/util/stringutil/stringutil.go b/pkg/common/util/stringutil/stringutil.go
index 8396e67..3e0f635 100644
--- a/pkg/common/util/stringutil/stringutil.go
+++ b/pkg/common/util/stringutil/stringutil.go
@@ -17,6 +17,11 @@
package stringutil
+import (
+ "github.com/apache/dubbo-go-pixiu/pkg/common/constant"
+ "strings"
+)
+
// StrInSlice returns whether the string is in the slice.
func StrInSlice(str string, slice []string) bool {
for _, s := range slice {
@@ -26,3 +31,52 @@ func StrInSlice(str string, slice []string) bool {
}
return false
}
+
+//Split url split to []string by "/"
+func Split(path string) []string {
+ return strings.Split(strings.TrimLeft(path, constant.PathSlash), constant.PathSlash)
+}
+
+//VariableName extract VariableName (:id, name = id)
+func VariableName(key string) string {
+ return strings.TrimPrefix(key, constant.PathParamIdentifier)
+}
+
+//IsPathVariableOrWildcard return if is a PathVariable (:id, true)
+func IsPathVariableOrWildcard(key string) bool {
+ if key == "" {
+ return false
+ }
+ if strings.HasPrefix(key, constant.PathParamIdentifier) {
+ return true
+ }
+
+ if IsWildcard(key) {
+ return true
+ }
+ //return key[0] == '{' && key[len(key)-1] == '}'
+ return false
+}
+
+//IsWildcard return if is *
+func IsWildcard(key string) bool {
+ return key == "*"
+}
+
+func IsMatchAll(key string) bool {
+ return key == "**"
+}
+
+func GetTrieKey(method string, path string) string {
+ ret := ""
+ if strings.HasPrefix(path, constant.PathSlash) {
+ ret = method + path
+ } else {
+ ret = method + constant.PathSlash + path
+ }
+
+ if strings.HasSuffix(ret, constant.PathSlash) {
+ ret = ret[0 : len(ret)-1]
+ }
+ return ret
+}
diff --git a/pkg/config/conf_test.yaml b/pkg/config/conf_test.yaml
index 93b14f4..2d4e6fb 100644
--- a/pkg/config/conf_test.yaml
+++ b/pkg/config/conf_test.yaml
@@ -41,14 +41,8 @@ static_resources:
match:
prefix: "/api/v1"
path: ""
- regex: ""
methods:
- POST
- headers:
- - name: "X-DGP-WAY"
- regex: false
- values:
- - "Dubbo"
route:
cluster: "test_dubbo"
cluster_not_found_response_code: 505
diff --git a/pkg/config/config_load.go b/pkg/config/config_load.go
index 429d0fe..16d8b5b 100644
--- a/pkg/config/config_load.go
+++ b/pkg/config/config_load.go
@@ -137,6 +137,7 @@ func GetHttpConfig(cfg *model.Bootstrap) (err error) {
logger.Error(err)
}
cfg.StaticResources.Listeners[i].Config = *hc
+ //cfg.StaticResources.Listeners[i].FilterChains
}
}
}
diff --git a/pkg/config/config_load_test.go b/pkg/config/config_load_test.go
index 22704db..94aef4d 100644
--- a/pkg/config/config_load_test.go
+++ b/pkg/config/config_load_test.go
@@ -48,14 +48,7 @@ func TestMain(m *testing.M) {
Methods: []string{
"POST",
},
- Path: "",
- Regex: "",
- Headers: []model.HeaderMatcher{
- {Name: "X-DGP-WAY",
- Values: []string{"Dubbo"},
- Regex: false,
- },
- },
+ Path: "",
},
Route: model.RouteAction{
Cluster: "test_dubbo",
diff --git a/pkg/context/http/util.go b/pkg/context/http/util.go
deleted file mode 100644
index b073ab7..0000000
--- a/pkg/context/http/util.go
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package http
-
-import (
- "regexp"
- "strings"
-)
-
-import (
- "github.com/apache/dubbo-go-pixiu/pkg/config"
- "github.com/apache/dubbo-go-pixiu/pkg/model"
-)
-
-// HttpRouteMatch
-func HttpRouteMatch(c *HttpContext, rm model.RouterMatch) bool {
- if rm.Prefix != "" {
- if !strings.HasPrefix(c.GetUrl(), rm.Path) {
- return false
- }
- }
-
- if rm.Path != "" {
- if c.GetUrl() != rm.Path {
- return false
- }
- }
-
- if rm.Regex != "" {
- if !regexp.MustCompile(rm.Regex).MatchString(c.GetUrl()) {
- return false
- }
- }
-
- return true
-}
-
-// HttpRouteActionMatch
-func HttpRouteActionMatch(c *HttpContext, ra model.RouteAction) bool {
- conf := config.GetBootstrap()
-
- if ra.Cluster == "" || !conf.ExistCluster(ra.Cluster) {
- return false
- }
-
- return true
-}
diff --git a/pkg/model/router.go b/pkg/model/router.go
index cfaa569..5314418 100644
--- a/pkg/model/router.go
+++ b/pkg/model/router.go
@@ -20,7 +20,6 @@ package model
import (
stdHttp "net/http"
"regexp"
- "strings"
)
import (
@@ -28,6 +27,7 @@ import (
)
import (
+ "github.com/apache/dubbo-go-pixiu/pkg/common/router/trie"
"github.com/apache/dubbo-go-pixiu/pkg/common/util/stringutil"
)
@@ -41,12 +41,12 @@ type (
// RouterMatch
RouterMatch struct {
- Prefix string `yaml:"prefix" json:"prefix" mapstructure:"prefix"`
- Path string `yaml:"path" json:"path" mapstructure:"path"`
- Regex string `yaml:"regex" json:"regex" mapstructure:"regex"`
- Methods []string `yaml:"methods" json:"methods" mapstructure:"methods"`
- Headers []HeaderMatcher `yaml:"headers" json:"headers" mapstructure:"headers"`
- pathRE *regexp.Regexp
+ Prefix string `yaml:"prefix" json:"prefix" mapstructure:"prefix"`
+ Path string `yaml:"path" json:"path" mapstructure:"path"`
+ // Regex string `yaml:"regex" json:"regex" mapstructure:"regex"` TODO: next version
+ Methods []string `yaml:"methods" json:"methods" mapstructure:"methods"`
+ // Headers []HeaderMatcher `yaml:"headers" json:"headers" mapstructure:"headers"`
+ // pathRE *regexp.Regexp
}
// RouteAction match route should do
@@ -57,8 +57,9 @@ type (
// RouteConfiguration
RouteConfiguration struct {
- Routes []*Router `yaml:"routes" json:"routes" mapstructure:"routes"`
- Dynamic bool `yaml:"dynamic" json:"dynamic" mapstructure:"dynamic"`
+ RouteTrie trie.Trie `yaml:"-" json:"-" mapstructure:"-"`
+ Routes []*Router `yaml:"routes" json:"routes" mapstructure:"routes"`
+ Dynamic bool `yaml:"dynamic" json:"dynamic" mapstructure:"dynamic"`
}
// Name header key, Value header value, Regex header value is regex
@@ -71,83 +72,17 @@ type (
)
func (rc *RouteConfiguration) Route(req *stdHttp.Request) (*RouteAction, error) {
- if rc.Routes == nil {
+ if rc.RouteTrie.IsEmpty() {
return nil, errors.Errorf("router configuration is empty")
}
- for _, r := range rc.Routes {
- if r.MatchRouter(req) {
- return &r.Route, nil
- }
+ node, _, _ := rc.RouteTrie.Match(stringutil.GetTrieKey(req.Method, req.URL.Path))
+ if node == nil {
+ return nil, errors.Errorf("route failed for %s,no rules matched.", stringutil.GetTrieKey(req.Method, req.URL.Path))
}
-
- return nil, errors.Errorf("no matched route")
-}
-
-// MatchRouter find router (cluster) by request path and method and header
-func (r *Router) MatchRouter(req *stdHttp.Request) bool {
- if !r.Match.matchPath(req) {
- return false
- }
-
- if !r.Match.matchMethod(req) {
- return false
- }
-
- if !r.Match.matchHeader(req) {
- return false
- }
-
- return true
-}
-
-func (rm *RouterMatch) matchPath(req *stdHttp.Request) bool {
- if rm.Path == "" && rm.Prefix == "" && rm.Regex == "" {
- return true
- }
-
- path := req.URL.Path
-
- if rm.Path != "" && rm.Path == path {
- return true
+ if node.GetBizInfo() == nil {
+ return nil, errors.Errorf("info is nil.please check your configuration.")
}
- if rm.Prefix != "" && strings.HasPrefix(path, rm.Prefix) {
- return true
- }
- if rm.Regex != "" {
- if rm.pathRE == nil {
- rm.pathRE = regexp.MustCompile(rm.Regex)
- }
- return rm.pathRE.MatchString(path)
- }
-
- return false
-}
-
-func (rm *RouterMatch) matchMethod(req *stdHttp.Request) bool {
- if len(rm.Methods) == 0 {
- return true
- }
-
- return stringutil.StrInSlice(req.Method, rm.Methods)
-}
-
-func (rm *RouterMatch) matchHeader(req *stdHttp.Request) bool {
- if len(rm.Headers) == 0 {
- return true
- }
-
- for _, h := range rm.Headers {
- // notice use canonical keys
- v := req.Header.Get(h.Name)
- if stringutil.StrInSlice(v, h.Values) {
- return true
- }
-
- if h.valueRE != nil && h.valueRE.MatchString(v) {
- return true
- }
- }
-
- return false
+ ret := (node.GetBizInfo()).(RouteAction)
+ return &ret, nil
}
diff --git a/pkg/model/router_test.go b/pkg/model/router_test.go
deleted file mode 100644
index 511b03a..0000000
--- a/pkg/model/router_test.go
+++ /dev/null
@@ -1,267 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package model
-
-import (
- "net/http"
- "net/url"
- "testing"
-)
-
-import (
- "github.com/stretchr/testify/assert"
-)
-
-func TestRouterPathMatch(t *testing.T) {
- rm := &RouterMatch{
- Prefix: "/user/",
- Path: "/user2/test",
- Regex: "/user3/test",
- Methods: []string{"POST"},
- Headers: []HeaderMatcher{
- {
- Name: "content-type",
- Values: []string{
- "grpc",
- "json",
- },
- },
- },
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user/add",
- },
- }
- assert.True(t, rm.matchPath(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user2/add",
- },
- }
- assert.False(t, rm.matchPath(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user2/test",
- },
- }
- assert.True(t, rm.matchPath(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- }
- assert.True(t, rm.matchPath(req))
- }
-}
-
-func TestRouterMethodMatch(t *testing.T) {
- rm := &RouterMatch{
- Prefix: "/user",
- Methods: []string{"POST", "PUT"},
- Headers: []HeaderMatcher{
- {
- Name: "content-type",
- Values: []string{
- "grpc",
- "json",
- },
- },
- },
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST",
- }
- assert.True(t, rm.matchMethod(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "PUT",
- }
- assert.True(t, rm.matchMethod(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "GET",
- }
- assert.False(t, rm.matchMethod(req))
- }
-}
-
-func TestRouterHeaderMatch(t *testing.T) {
- rm := &RouterMatch{
- Prefix: "/user",
- Path: "/user2/test",
- Regex: "/user3/test",
- Methods: []string{"POST", "PUT"},
- Headers: []HeaderMatcher{
- {
- Name: "content-type",
- Values: []string{
- "grpc",
- },
- },
- },
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST",
- Header: map[string][]string{
- "Content-Type": []string{
- "grpc",
- },
- },
- }
- assert.True(t, rm.matchHeader(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST",
- }
- assert.False(t, rm.matchHeader(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST",
- Header: map[string][]string{
- "Content-Type": []string{
- "grpc2",
- },
- },
- }
- assert.False(t, rm.matchHeader(req))
- }
-}
-
-func TestRouterMatch(t *testing.T) {
- rm := RouterMatch{
- Prefix: "/user/",
- Path: "/user2/test",
- Regex: "/user3/test",
- Methods: []string{"POST"},
- Headers: []HeaderMatcher{
- {
- Name: "content-type",
- Values: []string{
- "grpc",
- "json",
- },
- },
- },
- }
-
- router := &Router{
- Match: rm,
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST",
- Header: map[string][]string{
- "Content-Type": []string{
- "grpc",
- },
- },
- }
- assert.True(t, router.MatchRouter(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/us3/test",
- },
- Method: "POST",
- Header: map[string][]string{
- "Content-Type": []string{
- "grpc",
- },
- },
- }
- assert.False(t, router.MatchRouter(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST11",
- Header: map[string][]string{
- "Content-Type": []string{
- "grpc",
- },
- },
- }
- assert.False(t, router.MatchRouter(req))
- }
-
- {
- req := &http.Request{
- URL: &url.URL{
- Path: "/user3/test",
- },
- Method: "POST",
- Header: map[string][]string{
- "Content-Type": []string{
- "grpc1111",
- },
- },
- }
- assert.False(t, router.MatchRouter(req))
- }
-}
diff --git a/pkg/server/http.go b/pkg/server/http.go
index 1e5e67b..b68f6d0 100644
--- a/pkg/server/http.go
+++ b/pkg/server/http.go
@@ -19,6 +19,7 @@ package server
import (
"github.com/apache/dubbo-go-pixiu/pkg/common/constant"
+ "github.com/apache/dubbo-go-pixiu/pkg/common/router/trie"
"github.com/apache/dubbo-go-pixiu/pkg/model"
)
@@ -26,16 +27,9 @@ import (
func DefaultHttpConnectionManager() *model.HttpConnectionManagerConfig {
return &model.HttpConnectionManagerConfig{
RouteConfig: model.RouteConfiguration{
- Routes: []*model.Router{
- {
- Match: model.RouterMatch{
- Prefix: "/api/v1",
- },
- Route: model.RouteAction{
- Cluster: constant.HeaderValueAll,
- },
- },
- },
+ RouteTrie: trie.NewTrieWithDefault("/api/v1/**", model.RouteAction{
+ Cluster: constant.HeaderValueAll,
+ }),
},
HTTPFilters: []*model.HTTPFilter{
{
diff --git a/samples/http/simple/server/app/server.go b/samples/http/simple/server/app/server.go
index 1597f80..b923684 100644
--- a/samples/http/simple/server/app/server.go
+++ b/samples/http/simple/server/app/server.go
@@ -38,7 +38,7 @@ func main() {
func user(w http.ResponseWriter, r *http.Request) {
switch r.Method {
- case "POST":
+ case constant.Post:
byts, err := ioutil.ReadAll(r.Body)
if err != nil {
w.Write([]byte(err.Error()))
@@ -62,7 +62,7 @@ func user(w http.ResponseWriter, r *http.Request) {
return
}
w.Write(nil)
- case "GET":
+ case constant.Get:
subPath := strings.TrimPrefix(r.URL.Path, "/user/")
userName := strings.Split(subPath, "/")[0]
var u *User