routing_tree.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file implements a decision tree for fast matching of requests to
     6  // patterns.
     7  //
     8  // The root of the tree branches on the host of the request.
     9  // The next level branches on the method.
    10  // The remaining levels branch on consecutive segments of the path.
    11  //
    12  // The "more specific wins" precedence rule can result in backtracking.
    13  // For example, given the patterns
    14  //     /a/b/z
    15  //     /a/{x}/c
    16  // we will first try to match the path "/a/b/c" with /a/b/z, and
    17  // when that fails we will try against /a/{x}/c.
    18  
    19  package http
    20  
    21  import (
    22  	"strings"
    23  )
    24  
    25  // A routingNode is a node in the decision tree.
    26  // The same struct is used for leaf and interior nodes.
    27  type routingNode struct {
    28  	// A leaf node holds a single pattern and the Handler it was registered
    29  	// with.
    30  	pattern *pattern
    31  	handler Handler
    32  
    33  	// An interior node maps parts of the incoming request to child nodes.
    34  	// special children keys:
    35  	//     "/"	trailing slash (resulting from {$})
    36  	//	   ""   single wildcard
    37  	//	   "*"  multi wildcard
    38  	children   mapping[string, *routingNode]
    39  	emptyChild *routingNode // optimization: child with key ""
    40  }
    41  
    42  // addPattern adds a pattern and its associated Handler to the tree
    43  // at root.
    44  func (root *routingNode) addPattern(p *pattern, h Handler) {
    45  	// First level of tree is host.
    46  	n := root.addChild(p.host)
    47  	// Second level of tree is method.
    48  	n = n.addChild(p.method)
    49  	// Remaining levels are path.
    50  	n.addSegments(p.segments, p, h)
    51  }
    52  
    53  // addSegments adds the given segments to the tree rooted at n.
    54  // If there are no segments, then n is a leaf node that holds
    55  // the given pattern and handler.
    56  func (n *routingNode) addSegments(segs []segment, p *pattern, h Handler) {
    57  	if len(segs) == 0 {
    58  		n.set(p, h)
    59  		return
    60  	}
    61  	seg := segs[0]
    62  	if seg.multi {
    63  		if len(segs) != 1 {
    64  			panic("multi wildcard not last")
    65  		}
    66  		n.addChild("*").set(p, h)
    67  	} else if seg.wild {
    68  		n.addChild("").addSegments(segs[1:], p, h)
    69  	} else {
    70  		n.addChild(seg.s).addSegments(segs[1:], p, h)
    71  	}
    72  }
    73  
    74  // set sets the pattern and handler for n, which
    75  // must be a leaf node.
    76  func (n *routingNode) set(p *pattern, h Handler) {
    77  	if n.pattern != nil || n.handler != nil {
    78  		panic("non-nil leaf fields")
    79  	}
    80  	n.pattern = p
    81  	n.handler = h
    82  }
    83  
    84  // addChild adds a child node with the given key to n
    85  // if one does not exist, and returns the child.
    86  func (n *routingNode) addChild(key string) *routingNode {
    87  	if key == "" {
    88  		if n.emptyChild == nil {
    89  			n.emptyChild = &routingNode{}
    90  		}
    91  		return n.emptyChild
    92  	}
    93  	if c := n.findChild(key); c != nil {
    94  		return c
    95  	}
    96  	c := &routingNode{}
    97  	n.children.add(key, c)
    98  	return c
    99  }
   100  
   101  // findChild returns the child of n with the given key, or nil
   102  // if there is no child with that key.
   103  func (n *routingNode) findChild(key string) *routingNode {
   104  	if key == "" {
   105  		return n.emptyChild
   106  	}
   107  	r, _ := n.children.find(key)
   108  	return r
   109  }
   110  
   111  // match returns the leaf node under root that matches the arguments, and a list
   112  // of values for pattern wildcards in the order that the wildcards appear.
   113  // For example, if the request path is "/a/b/c" and the pattern is "/{x}/b/{y}",
   114  // then the second return value will be []string{"a", "c"}.
   115  func (root *routingNode) match(host, method, path string) (*routingNode, []string) {
   116  	if host != "" {
   117  		// There is a host. If there is a pattern that specifies that host and it
   118  		// matches, we are done. If the pattern doesn't match, fall through to
   119  		// try patterns with no host.
   120  		if l, m := root.findChild(host).matchMethodAndPath(method, path); l != nil {
   121  			return l, m
   122  		}
   123  	}
   124  	return root.emptyChild.matchMethodAndPath(method, path)
   125  }
   126  
   127  // matchMethodAndPath matches the method and path.
   128  // Its return values are the same as [routingNode.match].
   129  // The receiver should be a child of the root.
   130  func (n *routingNode) matchMethodAndPath(method, path string) (*routingNode, []string) {
   131  	if n == nil {
   132  		return nil, nil
   133  	}
   134  	if l, m := n.findChild(method).matchPath(path, nil); l != nil {
   135  		// Exact match of method name.
   136  		return l, m
   137  	}
   138  	if method == "HEAD" {
   139  		// GET matches HEAD too.
   140  		if l, m := n.findChild("GET").matchPath(path, nil); l != nil {
   141  			return l, m
   142  		}
   143  	}
   144  	// No exact match; try patterns with no method.
   145  	return n.emptyChild.matchPath(path, nil)
   146  }
   147  
   148  // matchPath matches a path.
   149  // Its return values are the same as [routingNode.match].
   150  // matchPath calls itself recursively. The matches argument holds the wildcard matches
   151  // found so far.
   152  func (n *routingNode) matchPath(path string, matches []string) (*routingNode, []string) {
   153  	if n == nil {
   154  		return nil, nil
   155  	}
   156  	// If path is empty, then we are done.
   157  	// If n is a leaf node, we found a match; return it.
   158  	// If n is an interior node (which means it has a nil pattern),
   159  	// then we failed to match.
   160  	if path == "" {
   161  		if n.pattern == nil {
   162  			return nil, nil
   163  		}
   164  		return n, matches
   165  	}
   166  	// Get the first segment of path.
   167  	seg, rest := firstSegment(path)
   168  	// First try matching against patterns that have a literal for this position.
   169  	// We know by construction that such patterns are more specific than those
   170  	// with a wildcard at this position (they are either more specific, equivalent,
   171  	// or overlap, and we ruled out the first two when the patterns were registered).
   172  	if n, m := n.findChild(seg).matchPath(rest, matches); n != nil {
   173  		return n, m
   174  	}
   175  	// If matching a literal fails, try again with patterns that have a single
   176  	// wildcard (represented by an empty string in the child mapping).
   177  	// Again, by construction, patterns with a single wildcard must be more specific than
   178  	// those with a multi wildcard.
   179  	// We skip this step if the segment is a trailing slash, because single wildcards
   180  	// don't match trailing slashes.
   181  	if seg != "/" {
   182  		if n, m := n.emptyChild.matchPath(rest, append(matches, seg)); n != nil {
   183  			return n, m
   184  		}
   185  	}
   186  	// Lastly, match the pattern (there can be at most one) that has a multi
   187  	// wildcard in this position to the rest of the path.
   188  	if c := n.findChild("*"); c != nil {
   189  		// Don't record a match for a nameless wildcard (which arises from a
   190  		// trailing slash in the pattern).
   191  		if c.pattern.lastSegment().s != "" {
   192  			matches = append(matches, pathUnescape(path[1:])) // remove initial slash
   193  		}
   194  		return c, matches
   195  	}
   196  	return nil, nil
   197  }
   198  
   199  // firstSegment splits path into its first segment, and the rest.
   200  // The path must begin with "/".
   201  // If path consists of only a slash, firstSegment returns ("/", "").
   202  // The segment is returned unescaped, if possible.
   203  func firstSegment(path string) (seg, rest string) {
   204  	if path == "/" {
   205  		return "/", ""
   206  	}
   207  	path = path[1:] // drop initial slash
   208  	i := strings.IndexByte(path, '/')
   209  	if i < 0 {
   210  		i = len(path)
   211  	}
   212  	return pathUnescape(path[:i]), path[i:]
   213  }
   214  
   215  // matchingMethods adds to methodSet all the methods that would result in a
   216  // match if passed to routingNode.match with the given host and path.
   217  func (root *routingNode) matchingMethods(host, path string, methodSet map[string]bool) {
   218  	if host != "" {
   219  		root.findChild(host).matchingMethodsPath(path, methodSet)
   220  	}
   221  	root.emptyChild.matchingMethodsPath(path, methodSet)
   222  	if methodSet["GET"] {
   223  		methodSet["HEAD"] = true
   224  	}
   225  }
   226  
   227  func (n *routingNode) matchingMethodsPath(path string, set map[string]bool) {
   228  	if n == nil {
   229  		return
   230  	}
   231  	n.children.eachPair(func(method string, c *routingNode) bool {
   232  		if p, _ := c.matchPath(path, nil); p != nil {
   233  			set[method] = true
   234  		}
   235  		return true
   236  	})
   237  	// Don't look at the empty child. If there were an empty
   238  	// child, it would match on any method, but we only
   239  	// call this when we fail to match on a method.
   240  }
   241
View as plain text