Skip to content

Instantly share code, notes, and snippets.

@flrdv

flrdv/matcher.go

Last active September 20, 2022 21:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save flrdv/7a5cdebe48223305093a20b40845a9de to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save flrdv/7a5cdebe48223305093a20b40845a9de to your computer and use it in GitHub Desktop.
Download ZIP
Dynamic path matcher
Raw
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)
}
Raw
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")
}
})
}
Raw
states.go
package main
type templateParserState uint8
const (
eStatic templateParserState = iota + 1
eSlash
ePartName
eEndPartName
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment