Analysis of Gin Framework Routing Prefix‑Tree Implementation

The Gin framework is a lightweight web framework for Go that includes a dispatch router; this article analyses how Gin builds a routing prefix‑tree based on request paths, using the Gin 1.6.3 source code as a reference.

1. Route storage structure and algorithm

The Engine struct holds an array called trees , one element per HTTP method (e.g., GET, POST). Each element is a methodTree containing the method name and a root node.

type Engine struct {
    trees methodTrees
}

type methodTrees []methodTree

type methodTree struct {
    method string
    root   *node
}

1.1 Prefix‑tree node definition

type node struct {
    path      string
    indices   string
    children  []*node
    handlers  HandlersChain
    priority  uint32
    nType     nodeType
    maxParams uint8
    wildChild bool
    fullPath  string
}

The fields store the node's own path segment, a compact index string of its children’s first characters, child pointers, handler chain, priority for ordering, node type (static, param, catchAll, root), wildcard information, and the full path from the root.

1.2 Example route configuration

engine.GET("/admin/model/get", api.GetTemplate)
engine.GET("/admin/model/query", api.QueryTemplate)
engine.POST("/admin/model/set", api.SetTemplate)
engine.POST("/admin/model/upload", api.UploadTemplate)
engine.POST("/admin/model/uploadv2", api.GetTemplateWithSignature)
engine.POST("/admin/model/update", api.UpdateTemplate)

These routes generate two separate prefix‑trees, one for GET and one for POST, as illustrated by the accompanying diagrams.

2. Route initialization process

When a route is added, Gin first creates an absolute path, obtains (or creates) the method‑specific root node via Engine.addRoute , and then calls node.addRoute to insert the path into the tree.

2.1 Engine.addRoute method

func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
    root := engine.trees.get(method)
    if root == nil {
        root = new(node)
        root.fullPath = "/"
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    root.addRoute(path, handlers)
}

2.2 findWildcard function

func findWildcard(path string) (wildcard string, i int, valid bool) {
    for start, c := range []byte(path) {
        if c != ':' && c != '*' {
            continue
        }
        valid = true
        for end, c := range []byte(path[start+1:]) {
            switch c {
            case '/':
                return path[start : start+1+end], start, valid
            case ':', '*':
                valid = false
            }
        }
        return path[start:], start, valid
    }
    return "", -1, false
}

This routine locates the first wildcard (colon or asterisk) in a path and reports its position and validity.

2.3 insertChild (adding child nodes)

func (n *node) insertChild(numParams uint8, path, fullPath string, handlers HandlersChain) {
    for numParams > 0 {
        wildcard, i, valid := findWildcard(path)
        if i < 0 { // no wildcard
            break
        }
        if !valid {
            panic("only one wildcard per path segment is allowed, has: '" + wildcard + "' in path '" + fullPath + "'")
        }
        if len(wildcard) < 2 {
            panic("wildcards must be named with a non‑empty name in path '" + fullPath + "'")
        }
        if len(n.children) > 0 {
            panic("wildcard segment '" + wildcard + "' conflicts with existing children in path '" + fullPath + "'")
        }
        // colon wildcard handling
        if wildcard[0] == ':' {
            if i > 0 {
                n.path = path[:i]
                path = path[i:]
            }
            n.wildChild = true
            child := &node{nType: param, path: wildcard, maxParams: numParams, fullPath: fullPath}
            n.children = []*node{child}
            n = child
            n.priority++
            numParams--
            if len(wildcard) < len(path) {
                path = path[len(wildcard):]
                child := &node{maxParams: numParams, priority: 1, fullPath: fullPath}
                n.children = []*node{child}
                n = child
                continue
            }
            n.handlers = handlers
            return
        }
        // asterisk (catch‑all) handling
        if i+len(wildcard) != len(path) || numParams > 1 {
            panic("catch‑all routes are only allowed at the end of the path in path '" + fullPath + "'")
        }
        if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
            panic("catch‑all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
        }
        i--
        if path[i] != '/' {
            panic("no / before catch‑all in path '" + fullPath + "'")
        }
        n.path = path[:i]
        child := &node{wildChild: true, nType: catchAll, maxParams: 1, fullPath: fullPath}
        n.children = []*node{child}
        n.indices = string('/')
        n = child
        n.priority++
        child = &node{path: path[i:], nType: catchAll, maxParams: 1, handlers: handlers, priority: 1, fullPath: fullPath}
        n.children = []*node{child}
        return
    }
    // no more wildcards – insert the remaining static path
    n.path = path
    n.handlers = handlers
    n.fullPath = fullPath
}

This function inserts a new child node, handling colon parameters and asterisk catch‑all segments, while performing conflict checks and updating priorities.

2.4 node.addRoute (searching/inserting nodes)

func (n *node) addRoute(path string, handlers HandlersChain) {
    fullPath := path
    n.priority++
    numParams := countParams(path)
    if len(n.path) == 0 && len(n.children) == 0 {
        n.insertChild(numParams, path, fullPath, handlers)
        n.nType = root
        return
    }
    parentFullPathIndex := 0
    walk:
    for {
        if numParams > n.maxParams {
            n.maxParams = numParams
        }
        i := longestCommonPrefix(path, n.path)
        if i < len(n.path) {
            child := node{path: n.path[i:], wildChild: n.wildChild, indices: n.indices, children: n.children, handlers: n.handlers, priority: n.priority - 1, fullPath: n.fullPath}
            for _, v := range child.children {
                if v.maxParams > child.maxParams {
                    child.maxParams = v.maxParams
                }
            }
            n.children = []*node{&child}
            n.indices = string([]byte{n.path[i]})
            n.path = path[:i]
            n.handlers = nil
            n.wildChild = false
            n.fullPath = fullPath[:parentFullPathIndex+i]
        }
        if i < len(path) {
            path = path[i:]
            if n.wildChild {
                parentFullPathIndex += len(n.path)
                n = n.children[0]
                n.priority++
                if numParams > n.maxParams {
                    n.maxParams = numParams
                }
                numParams--
                if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
                    if len(n.path) >= len(path) || path[len(n.path)] == '/' {
                        continue walk
                    }
                }
                pathSeg := path
                if n.nType != catchAll {
                    pathSeg = strings.SplitN(path, "/", 2)[0]
                }
                prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
                panic("'" + pathSeg + "' in new path '" + fullPath + "' conflicts with existing wildcard '" + n.path + "' in existing prefix '" + prefix + "'")
            }
            c := path[0]
            if n.nType == param && c == '/' && len(n.children) == 1 {
                parentFullPathIndex += len(n.path)
                n = n.children[0]
                n.priority++
                continue walk
            }
            for i, max := 0, len(n.indices); i < max; i++ {
                if c == n.indices[i] {
                    parentFullPathIndex += len(n.path)
                    i = n.incrementChildPrio(i)
                    n = n.children[i]
                    continue walk
                }
            }
            if c != ':' && c != '*' {
                n.indices += string([]byte{c})
                child := &node{maxParams: numParams, fullPath: fullPath}
                n.children = append(n.children, child)
                n.incrementChildPrio(len(n.indices) - 1)
                n = child
            }
            n.insertChild(numParams, path, fullPath, handlers)
            return
        }
        if n.handlers != nil {
            panic("handlers are already registered for path '" + fullPath + "'")
        }
        n.handlers = handlers
        return
    }
}

The method walks the existing tree, splits nodes when a partial match occurs, follows wildcard children, creates new static or wildcard children as needed, and finally attaches the handler chain.

3. Case analyses

Case 1: a single route with two colon parameters ( /user/:name/:age ) – demonstrates successive insertion of param nodes.

Case 2: a route with a colon and a catch‑all ( /user/:name/*age ) – shows the extra validation that the asterisk must be the final segment and that the preceding character must be ‘/’.

Case 3: multiple routes sharing prefixes ( /user/info , /user/info/:name , /user/info/:name/*age ) – illustrates how the tree grows, reuses common prefixes, and handles conflicts.

Each case is accompanied by diagrams of the resulting prefix‑tree.

4. Usage pitfalls

Routes at the same level must use identical wildcard names; mixing :name and *age in the same segment causes a conflict.

The asterisk wildcard is only allowed as the final segment; otherwise Gin panics.

There is a known bug where a catch‑all route ( /user/info/*name ) masks a longer route ( /user/info/*name/age ) during matching, though the latter can still be registered.

Understanding these constraints helps developers avoid routing errors when using Gin.