pathmux

README

Pathmux: tree lookup with wildcard matching

Pathmux is a package that implements an effective tree lookup with wildcard matching. It is a fork of the awesome httptreemux. This fork makes visible the interface of the internal tree lookup implementation of the original httptreemux package, and with the HTTP-related wrapper code stripped away.

In addition to having the original httptreemux logic, pathmux offers one small feature: backtracking. This means that when a path is matched, it is possible to instruct the lookup not to return the found object when other, custom conditions are not met, but instead continue the lookup by backtracking from the current point in the tree.

Pathmux is used by Skipper, an extensible HTTP routing server used in production at Zalando.

When to Use pathmux Instead of httptreemux

Almost never, except when:

• you want to store a large number of custom objects in an effective lookup tree, keyed by path values
• you want to use the backtracking feature to refine the evaluation of wildcard matching with custom logic

Installation

go get github.com/zalando/pathmux

Pathmux is 'go get compatible'. The master head is always stable (at least by intent), and it doesn't use any vendoring itself. However, we strongly recommend that you use vendoring in the final, importing, executable package.

Documentation

You can find detailed package documentation here.

Working with the Code

While it is enough to use go get to import the package, when modifying the code, it is worth cherry-picking from the tasks in the provided simple Makefile.

Contributing

See our detailed contribution guidelines. If you plan on contributing to the current repository, please make sure:

1. to run the precommit checks:

make precommit

Please fix all reported errors and please make sure that the overall test coverage is not decreased. (Please feel free to provide tests for the missing spots :))

1. compare the performance of the new version to the current master, and avoid degradations:

make bench

(Comparison currently can happen only by running the same make bench on the master branch. Automating the comparison would be a nice contribution.)

License

Copyright (c) 2014 Daniel Imfeld, 2015 Zalando SE

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Documentation

Overview

Package pathmux implements a tree lookup for values associated to paths.

This package is a fork of https://github.com/dimfeld/httptreemux.

Index

• type Matcher
• type Tree
  • func (t *Tree) Add(path string, value interface{}) error
  • func (t *Tree) Lookup(path string) (interface{}, []string)
  • func (t *Tree) LookupMatcher(path string, m Matcher) (interface{}, []string, interface{})
• type VizTree
  • func NewVizTree(tree *Tree) *VizTree

Types

type Matcher

type Matcher interface {

	// Match should return true and the object to be returned by the lookup, when the argument value fulfils the
	// conditions defined by the custom logic in the matcher itself. If it returns false, it instructs the
	// lookup to continue with backtracking from the current tree position.
	Match(value interface{}) (bool, interface{})
}

Matcher objects, when using the LookupMatcher function, can be used for additional checks and to override the default result in case of path matches. The argument passed to the Match function is the original value passed to the Tree.Add function.

type Tree

type Tree node

Tree structure to store values associated to paths.

func (*Tree) Add

func (t *Tree) Add(path string, value interface{}) error

Add a value to the tree associated with a path. Paths may contain wildcards. Wildcards can be of two types:

- simple wildcard: e.g. /some/:wildcard/path, where a wildcard is matched to a single name in the path.

- free wildcard: e.g. /some/path/*wildcard, where a wildcard at the end of a path matches anything.

func (*Tree) Lookup

func (t *Tree) Lookup(path string) (interface{}, []string)

Lookup tries to find a value in the tree associated to a path. If the found path definition contains wildcards, the values of the wildcards are returned in the second argument.

func (*Tree) LookupMatcher

func (t *Tree) LookupMatcher(path string, m Matcher) (interface{}, []string, interface{})

LookupMatcher tries to find value in the tree associated to a path. If the found path definition contains wildcards, the values of the wildcards are returned in the second argument. When a value is found, the matcher is called to check if the value meets the conditions implemented by the custom matcher. If it returns true, then the lookup is done and the additional return value from the matcher is returned as the lookup result. If it returns false, the lookup continues with backtracking from the current tree position.

type VizTree

type VizTree struct {
	Path     string     // string representation of the node path
	Children []*VizTree // children nodes of the current node
	CanMatch bool       // flag that is set to true if the node has a matcher
}

Exploded version of the pathmux tree designed for being easy to use in a visualization. Simple wildcard nodes are represented by the ':' prefix and free wildcard nodes with the '*' prefix.

func NewVizTree

func NewVizTree(tree *Tree) *VizTree

Creates a new visualization tree from a pathmux.Tree.