Dynamic path matcher

matcher.go

package main

import (
	"context"
	"errors"
	"fmt"
	context2 "github.com/fakefloordiv/indigo/internal/context"
	"strconv"
	"strings"
)

var (
	ErrNotImplemented  = errors.New("current implementation does not allows static text between slashes")
	ErrInvalidTemplate = errors.New("invalid template")
	ErrEmptyPath       = errors.New("path template cannot be empty")
)

// Template is a parsed template. It simply contains static parts, and marker names
// index of each corresponds to index of static part (first static part, then marker)
type Template struct {
	staticParts []string
	markerNames []string
}

func Parse(tmpl string) (Template, error) {
	var (
		offset   int
		template = Template{}
		state    = eStatic
	)

	if len(tmpl) == 0 {
		return template, ErrEmptyPath
	}

	for i, char := range tmpl {
		if i == 0 {
			if char != '/' {
				return template, ErrInvalidTemplate
			}

			// skip leading slash
			continue
		}

		switch state {
		case eStatic:
			switch char {
			case '/':
				state = eSlash
			case '{':
				return template, ErrNotImplemented
			}
		case eSlash:
			switch char {
			case '{':
				template.staticParts = append(template.staticParts, tmpl[offset:i])
				offset = i + 1
				state = ePartName
			default:
				state = eStatic
			}
		case ePartName:
			switch char {
			case '}':
				template.markerNames = append(template.markerNames, tmpl[offset:i])
				offset = i + 1
				state = eEndPartName
			case '/':
				return template, ErrInvalidTemplate
			}
		case eEndPartName:
			switch char {
			case '/':
				state = eSlash
			default:
				return template, ErrNotImplemented
			}
		}
	}

	if state == eStatic || state == eSlash {
		template.staticParts = append(template.staticParts, tmpl)
	}

	return template, nil
}

func (t Template) Match(ctx context.Context, path string) (context.Context, bool) {
	if len(t.staticParts) == 1 {
		return ctx, path == t.staticParts[0]
	}

	var (
		staticIndex int
	)

	for staticIndex < len(t.staticParts) {
		staticPart := t.staticParts[staticIndex]

		if len(path) < len(staticPart) || path[:len(staticPart)] != staticPart {
			return ctx, false
		}

		dynamicPart := path[len(staticPart):]

		if slash := strings.IndexByte(dynamicPart, '/'); slash != -1 {
			if name := t.markerNames[staticIndex]; len(name) > 0 {
				ctx = context2.WithValue(ctx, name, dynamicPart[:slash])
			}

			path = dynamicPart[slash:]
		} else {
			if name := t.markerNames[staticIndex]; len(name) > 0 {
				ctx = context2.WithValue(ctx, name, dynamicPart)
			}

			return ctx, staticIndex+1 == len(t.staticParts)
		}

		staticIndex++
	}

	return ctx, true
}

func main() {
	tmpl := "/hello/{world}/{ok}/good/{name}"
	fmt.Println("parsing:", strconv.Quote(tmpl))

	template, err := Parse(tmpl)
	fmt.Println("template:", template, "err:", err)

	sample := "/hello/world-world/ok-perfect/good/name-Akakiy"
	_, matched := template.Match(context.Background(), sample)
	fmt.Println("Sample:", sample)
	fmt.Println("matches:", matched)
}

matcher_test.go

package main

import (
	"context"
	"regexp"
	"testing"
)

func BenchmarkMatch(b *testing.B) {
	staticSample := "/hello/world/length/does/not/matter"
	staticTemplate, _ := Parse(staticSample)

	shortTemplateSample := "/hello/{world}"
	shortSample := "/hello/some-very-long-world"
	shortTemplate, _ := Parse(shortTemplateSample)

	mediumTemplateSample := "/hello/{world}/very/{good}/{ok}"
	mediumSample := "/hello/world-finally-became/very/good-as-fuck/ok-let-it-be"
	mediumTemplate, _ := Parse(mediumTemplateSample)

	longTemplateSample := "/hello/{world}/very/{good}/{ok}/{wanna}/somestatic/{finally}/good"
	longSample := "/hello/world-finally-became/very/good-as-fuck/ok-let-it-be/i-wanna-/somestatic/finally-matcher-is-here/good"
	longTemplate, _ := Parse(longTemplateSample)

	b.Run("OnlyStatic", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			staticTemplate.Match(context.Background(), staticSample)
		}
	})

	b.Run("Short", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			shortTemplate.Match(context.Background(), shortSample)
		}
	})

	b.Run("Medium", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			mediumTemplate.Match(context.Background(), mediumSample)
		}
	})

	b.Run("Long", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			longTemplate.Match(context.Background(), longSample)
		}
	})
}

func BenchmarkRegexp(b *testing.B) {
	staticSample := `\/hello\/world\/length\/does\/not\/matter$`
	static, _ := regexp.Compile(staticSample)

	shortTemplateSample := `\/hello\/\w+$`
	shortSample := "/hello/some-very-long-world"
	short, _ := regexp.Compile(shortTemplateSample)

	mediumTemplateSample := `\/hello\/\w+/very/\w+/\w+$`
	mediumSample := "/hello/world-finally-became/very/good-as-fuck/ok-let-it-be"
	medium, _ := regexp.Compile(mediumTemplateSample)

	longTemplateSample := `\/hello\/\w+\/very\/\w+/\w+\/\w+\/somestatic\/\w+\/good$`
	longSample := "/hello/world-finally-became/very/good-as-fuck/ok-let-it-be/i-wanna-/somestatic/finally-matcher-is-here/good"
	long, _ := regexp.Compile(longTemplateSample)

	b.Run("StaticPositive", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			static.MatchString(staticSample)
		}
	})

	b.Run("StaticNegative", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			static.MatchString(staticSample + "ok")
		}
	})

	b.Run("ShortPositive", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			short.MatchString(shortSample)
		}
	})

	b.Run("ShortNegative", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			short.MatchString(shortSample + "ok")
		}
	})

	b.Run("MediumPositive", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			medium.MatchString(mediumSample)
		}
	})

	b.Run("MediumNegative", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			medium.MatchString(mediumSample + "ok")
		}
	})

	b.Run("LongPositive", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			long.MatchString(longSample)
		}
	})

	b.Run("LongNegative", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			long.MatchString(longSample + "ok")
		}
	})
}

states.go

package main

type templateParserState uint8

const (
	eStatic templateParserState = iota + 1
	eSlash
	ePartName
	eEndPartName
)