介绍
在现代Web开发中，API路径的权限校验是确保系统安全性和数据隐私的重要手段。传统的权限校验方法可能效率较低，尤其是当API数量庞大且路径复杂时。前缀树（Trie）作为一种高效的字符串存储和查询数据结构，可以很好地解决这个问题。本文将介绍如何利用前缀树来实现基于API路径的权限校验。
前缀树的基本结构
前缀树是一种树形数据结构，用于存储具有共同前缀的字符串。在前缀树中，每个节点表示一个字符，从根节点到某个节点的路径表示一个字符串。前缀树特别适用于处理动态集合的字符串，例如字典单词、URL路径等。
实现基于前缀树的API路径权限校验
1. 数据结构设计
我们需要一个前缀树结构来存储API路径及其对应的权限信息。每个节点不仅存储一个字符，还需要存储与该路径相关的权限。
2. 插入API路径和权限
我们首先定义前缀树节点的数据结构，并实现插入API路径和权限的方法。
代码示例
代码语言：javascript复制
go
package main
import "fmt"
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
permissions []string // 存储权限信息
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}
func (t *Trie) Insert(path string, permissions []string) {
node := t.root
for _, char := range path {
if _, found := node.children[char]; !found {
node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[char]
}
node.isEnd = true
node.permissions = permissions
}
func (t *Trie) Search(path string) (*TrieNode, bool) {
node := t.root
for _, char := range path {
if _, found := node.children[char]; !found {
return nil, false
}
node = node.children[char]
}
return node, node.isEnd
}
3. 权限校验
权限校验的关键在于找到最匹配的API路径节点，并检查其权限。由于API路径可能有通配符或相似前缀，我们需要从根节点开始匹配，逐层深入，同时记录匹配的最大权限节点。
代码示例
代码语言：javascript复制
go
func (t *Trie) CheckPermissions(path string, requiredPermissions []string) bool {
node := t.root
var maxMatchNode *TrieNode
for _, char := range path {
if nextNode, found := node.children[char]; found {
node = nextNode
if node.isEnd {
maxMatchNode = node
}
} else {
break
}
}
if maxMatchNode == nil {
return false
}
return hasRequiredPermissions(maxMatchNode.permissions, requiredPermissions)
}
func hasRequiredPermissions(nodePermissions, requiredPermissions []string) bool {
permSet := make(map[string]bool)
for _, perm := range nodePermissions {
permSet[perm] = true
}
for _, reqPerm := range requiredPermissions {
if !permSet[reqPerm] {
return false
}
}
return true
}
4. 示例应用
假设我们有以下API路径及其对应的权限：
/api/user/create->["admin", "write"]/api/user/delete->["admin", "delete"]/api/user/view->["user", "view"]
我们将这些路径和权限插入到前缀树中，并进行权限校验。
代码示例
代码语言：javascript复制
go
func main() {
trie := NewTrie()
trie.Insert("/api/user/create", []string{"admin", "write"})
trie.Insert("/api/user/delete", []string{"admin", "delete"})
trie.Insert("/api/user/view", []string{"user", "view"})
testCases := []struct {
path string
requiredPermissions []string
expectedResult bool
}{
{"/api/user/create", []string{"admin", "write"}, true},
{"/api/user/delete", []string{"admin", "delete"}, true},
{"/api/user/view", []string{"user", "view"}, true},
{"/api/user/view", []string{"admin", "view"}, false},
{"/api/user/create", []string{"write"}, false},
}
for _, tc := range testCases {
result := trie.CheckPermissions(tc.path, tc.requiredPermissions)
fmt.Printf("Path: %s, Required: %v, Result: %v (Expected: %v)n",
tc.path, tc.requiredPermissions, result, tc.expectedResult)
}
}
结论
通过使用前缀树来存储API路径及其权限信息，我们可以高效地进行路径匹配和权限校验。这种方法特别适用于路径复杂且数量庞大的API系统，可以显著提升权限校验的效率和准确性。希望通过本文的介绍，读者能够更好地理解并应用前缀树在API权限校验中的实际场景。
下面是完整的代码，展示了如何使用前缀树实现API路径的权限校验：
代码语言：javascript复制
go
package main
import (
"fmt"
"testing"
)
// TrieNode 定义前缀树的节点结构
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
permissions []string // 存储权限信息
}
// Trie 定义前缀树的结构
type Trie struct {
root *TrieNode
}
// NewTrie 创建一个新的前缀树
func NewTrie() *Trie {
return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}
// Insert 向前缀树中插入路径及其对应的权限信息
func (t *Trie) Insert(path string, permissions []string) {
node := t.root
for _, char := range path {
if _, found := node.children[char]; !found {
node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[char]
}
node.isEnd = true
node.permissions = permissions
}
// Search 查找路径是否存在于前缀树中
func (t *Trie) Search(path string) (*TrieNode, bool) {
node := t.root
for _, char := range path {
if _, found := node.children[char]; !found {
return nil, false
}
node = node.children[char]
}
return node, node.isEnd
}
// CheckPermissions 检查是否具有所需的权限
func (t *Trie) CheckPermissions(path string, requiredPermissions []string) bool {
node := t.root
var maxMatchNode *TrieNode
for _, char := range path {
if nextNode, found := node.children[char]; found {
node = nextNode
if node.isEnd {
maxMatchNode = node
}
} else {
break
}
}
if maxMatchNode == nil {
return false
}
return hasRequiredPermissions(maxMatchNode.permissions, requiredPermissions)
}
// hasRequiredPermissions 检查是否具有所有必需的权限
func hasRequiredPermissions(nodePermissions, requiredPermissions []string) bool {
permSet := make(map[string]bool)
for _, perm := range nodePermissions {
permSet[perm] = true
}
for _, reqPerm := range requiredPermissions {
if !permSet[reqPerm] {
return false
}
}
return true
}
// main 主函数展示如何使用前缀树进行权限校验
func main() {
trie := NewTrie()
trie.Insert("/api/user/create", []string{"admin", "write"})
trie.Insert("/api/user/delete", []string{"admin", "delete"})
trie.Insert("/api/user/view", []string{"user", "view"})
testCases := []struct {
path string
requiredPermissions []string
expectedResult bool
}{
{"/api/user/create", []string{"admin", "write"}, true},
{"/api/user/delete", []string{"admin", "delete"}, true},
{"/api/user/view", []string{"user", "view"}, true},
{"/api/user/view", []string{"admin", "view"}, false},
{"/api/user/create", []string{"write"}, false},
}
for _, tc := range testCases {
result := trie.CheckPermissions(tc.path, tc.requiredPermissions)
fmt.Printf("Path: %s, Required: %v, Result: %v (Expected: %v)n",
tc.path, tc.requiredPermissions, result, tc.expectedResult)
}
}
bash
go run .tree.go
Path: /api/user/create, Required: [admin write], Result: true (Expected: true)
Path: /api/user/delete, Required: [admin delete], Result: true (Expected: true)
Path: /api/user/view, Required: [user view], Result: true (Expected: true)
Path: /api/user/view, Required: [admin view], Result: false (Expected: false)
Path: /api/user/create, Required: [write], Result: true (Expected: false)
