Boost API Permission Checks with Trie: A Go Implementation

Introduction

API path permission checking is essential for security in large web services. A Trie (prefix tree) provides fast longest‑prefix matching, making it suitable for storing many hierarchical routes.

Basic Structure of a Trie

A Trie is a tree where each node represents a character. The concatenation of characters from the root to a node forms a string. Nodes can store additional data, such as a list of permissions associated with a complete path.

Implementing API Path Permission Check with a Trie

1. Data Structure Design

Each node holds: children map[rune]*TrieNode – child edges keyed by character isEnd bool – marks the end of a registered path permissions []string – permission identifiers for that path

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)}} }

2. Insert API Paths and Permissions

The Insert method walks the characters of a path, creates missing child nodes, marks the final node as an endpoint, and stores the permission slice.

func (t *Trie) Insert(path string, permissions []string) {
    node := t.root
    for _, ch := range path {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
    node.permissions = permissions
}

3. Permission Validation

To check a request, traverse the Trie following the request path, remembering the deepest node that is an endpoint. If such a node exists, verify that its stored permissions contain all required permissions.

func (t *Trie) CheckPermissions(path string, required []string) bool {
    node := t.root
    var match *TrieNode
    for _, ch := range path {
        next, ok := node.children[ch]
        if !ok { break }
        node = next
        if node.isEnd { match = node }
    }
    if match == nil { return false }
    return hasRequiredPermissions(match.permissions, required)
}

func hasRequiredPermissions(stored, required []string) bool {
    set := make(map[string]bool)
    for _, p := range stored { set[p] = true }
    for _, r := range required {
        if !set[r] { return false }
    }
    return true
}

4. Example Application

Register three example routes: /api/user/create →

["admin","write"]

/api/user/delete

→

["admin","delete"]

/api/user/view

→ ["user","view"] Insert them into the Trie and run test cases that exercise both successful and failing permission checks.

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"})

    tests := []struct {
        path      string
        required  []string
        expected  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 tests {
        ok := trie.CheckPermissions(tc.path, tc.required)
        fmt.Printf("Path: %s, Required: %v, Result: %v (Expected: %v)
", tc.path, tc.required, ok, tc.expected)
    }
}

go run .
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: false (Expected: false)

Conclusion

Storing API routes in a Trie enables O(L) (where L is the path length) lookup of the longest matching prefix and efficient permission verification. The provided Go implementation demonstrates a complete, runnable solution suitable for services with large and complex route sets.