<commit_before>// Package denco provides fast URL router.
package denco

import (
	"fmt"
	"sort"
	"strings"
)

const (
	// A special character for path parameter.
	ParamCharacter = ':'

	// A special character for wildcard path parameter.
	WildcardCharacter = '*'

	// TerminalCharacter is a special character for end of path.
	TerminationCharacter = '#'
)

// Router represents a URL router.
type Router struct {
	static map[string]interface{}
	param  *doubleArray
}

// New returns a new Router.
func New() *Router {
	return &Router{
		static: make(map[string]interface{}),
		param:  newDoubleArray(),
	}
}

// Lookup returns data and path parameters that associated with path.
// params is a slice of the Param that arranged in the order in which parameters appeared.
// e.g. when built routing path is "/path/:id/:name" and given path is "/path/to/1/alice". params order is [{"id": "1"}, {"name": "alice"}], not [{"name": "alice"}, {"id": "1"}].
func (rt *Router) Lookup(path string) (data interface{}, params []Param, found bool) {
	if data, found := rt.static[path]; found {
		return data, nil, true
	}
	nd, params, found := rt.param.lookup(path, 1)
	if !found {
		return nil, nil, false
	}
	for i := 0; i < len(params); i++ {
		params[i].Name = nd.paramNames[i]
	}
	return nd.data, params, true
}

// Build builds URL router from records.
func (rt *Router) Build(records []Record) error {
	statics, params := makeRecords(records)
	for _, r := range statics {
		rt.static[r.Key] = r.Value
	}
	if err := rt.param.build(params, 1, 0, make(map[int]struct{})); err != nil {
		return err
	}
	return nil
}

// Param represents name and value of path parameter.
type Param struct {
	Name  string
	Value string
}

type doubleArray struct {
	bc   []baseCheck
	node []*node
}

func newDoubleArray() *doubleArray {
	return &doubleArray{
		bc:   []baseCheck{0},
		node: []*node{nil}, // A start index is adjusting to 1 because 0 will be used as a mark of non-existent node.
	}
}

// baseCheck contains BASE, CHECK and Extra flags.
// From the top, 22bits of BASE, 2bits of Extra flags and 8bits of CHECK.
//
//  BASE (22bit) | Extra flags (2bit) | CHECK (8bit)
// |----------------------|--|--------|
// 32                    10  8         0
type baseCheck uint32

func (bc baseCheck) Base() int {
	return int(bc >> 10)
}

func (bc *baseCheck) SetBase(base int) {
	*bc |= baseCheck(base) << 10
}

func (bc baseCheck) Check() byte {
	return byte(bc)
}

func (bc *baseCheck) SetCheck(check byte) {
	*bc |= baseCheck(check)
}

func (bc baseCheck) IsEmpty() bool {
	return bc&0xfffffcff == 0
}

func (bc baseCheck) Index() int {
	return int(bc >> 10)
}

func (bc *baseCheck) SetIndex(i int) {
	*bc |= baseCheck(i) << 10
}

func (bc baseCheck) IsSingleParam() bool {
	return bc&paramTypeSingle == paramTypeSingle
}

func (bc baseCheck) IsWildcardParam() bool {
	return bc&paramTypeWildcard == paramTypeWildcard
}

func (bc baseCheck) IsAnyParam() bool {
	return bc&paramTypeAny != 0
}

func (bc *baseCheck) SetSingleParam() {
	*bc |= (1 << 8)
}

func (bc *baseCheck) SetWildcardParam() {
	*bc |= (1 << 9)
}

const (
	paramTypeSingle   = 0x0100
	paramTypeWildcard = 0x0200
	paramTypeAny      = 0x0300
)

func (da *doubleArray) lookup(path string, idx int) (*node, []Param, bool) {
	indices := make([]uint64, 0, 1)
	for i := 0; i < len(path); i++ {
		if da.bc[idx].IsAnyParam() {
			indices = append(indices, (uint64(i)<<32)|uint64(idx&0xffffffff))
		}
		c := path[i]
		next := nextIndex(da.bc[idx].Base(), c)
		if next >= len(da.bc) || da.bc[next].Check() != c {
			goto BACKTRACKING
		}
		idx = next
	}
	if next := nextIndex(da.bc[idx].Base(), TerminationCharacter); da.bc[next].Check() == TerminationCharacter {
		return da.node[da.bc[next].Index()], nil, true
	}
	return nil, nil, false
BACKTRACKING:
	for j := len(indices) - 1; j >= 0; j-- {
		i, idx := int(indices[j]>>32), int(indices[j]&0xffffffff)
		if da.bc[idx].IsSingleParam() {
			idx := nextIndex(da.bc[idx].Base(), ParamCharacter)
			if idx >= len(da.bc) {
				break
			}
			next := NextSeparator(path, i)
			if nd, params, found := da.lookup(path[next:], idx); found {
				return nd, append([]Param{{Value: path[i:next]}}, params...), true
			}
		}
		if da.bc[idx].IsWildcardParam() {
			idx := nextIndex(da.bc[idx].Base(), WildcardCharacter)
			params := []Param{{Value: path[i:]}}
			return da.node[da.bc[idx].Index()], params, true
		}
	}
	return nil, nil, false
}

// build builds double-array from records.
func (da *doubleArray) build(srcs []*record, idx, depth int, usedBase map[int]struct{}) error {
	sort.Sort(recordSlice(srcs))
	base, siblings, leaf, err := da.arrange(srcs, idx, depth, usedBase)
	if err != nil {
		return err
	}
	if leaf != nil {
		nd, err := makeNode(leaf)
		if err != nil {
			return err
		}
		da.bc[idx].SetIndex(len(da.node))
		da.node = append(da.node, nd)
	}
	for _, sib := range siblings {
		da.setCheck(nextIndex(base, sib.c), sib.c)
	}
	for _, sib := range siblings {<commit_msg>Modify da.lookup() to take a []Param slice to optimize the memory allocation<commit_after>// Package denco provides fast URL router.
package denco

import (
	"fmt"
	"sort"
	"strings"
)

const (
	// A special character for path parameter.
	ParamCharacter = ':'

	// A special character for wildcard path parameter.
	WildcardCharacter = '*'

	// TerminalCharacter is a special character for end of path.
	TerminationCharacter = '#'
)

// Router represents a URL router.
type Router struct {
	static map[string]interface{}
	param  *doubleArray
}

// New returns a new Router.
func New() *Router {
	return &Router{
		static: make(map[string]interface{}),
		param:  newDoubleArray(),
	}
}

// Lookup returns data and path parameters that associated with path.
// params is a slice of the Param that arranged in the order in which parameters appeared.
// e.g. when built routing path is "/path/:id/:name" and given path is "/path/to/1/alice". params order is [{"id": "1"}, {"name": "alice"}], not [{"name": "alice"}, {"id": "1"}].
func (rt *Router) Lookup(path string) (data interface{}, params []Param, found bool) {
	if data, found := rt.static[path]; found {
		return data, nil, true
	}
	nd, params, found := rt.param.lookup(path, params, 1)
	if !found {
		return nil, nil, false
	}
	for i := 0; i < len(params); i++ {
		params[i].Name = nd.paramNames[i]
	}
	return nd.data, params, true
}

// Build builds URL router from records.
func (rt *Router) Build(records []Record) error {
	statics, params := makeRecords(records)
	for _, r := range statics {
		rt.static[r.Key] = r.Value
	}
	if err := rt.param.build(params, 1, 0, make(map[int]struct{})); err != nil {
		return err
	}
	return nil
}

// Param represents name and value of path parameter.
type Param struct {
	Name  string
	Value string
}

type doubleArray struct {
	bc   []baseCheck
	node []*node
}

func newDoubleArray() *doubleArray {
	return &doubleArray{
		bc:   []baseCheck{0},
		node: []*node{nil}, // A start index is adjusting to 1 because 0 will be used as a mark of non-existent node.
	}
}

// baseCheck contains BASE, CHECK and Extra flags.
// From the top, 22bits of BASE, 2bits of Extra flags and 8bits of CHECK.
//
//  BASE (22bit) | Extra flags (2bit) | CHECK (8bit)
// |----------------------|--|--------|
// 32                    10  8         0
type baseCheck uint32

func (bc baseCheck) Base() int {
	return int(bc >> 10)
}

func (bc *baseCheck) SetBase(base int) {
	*bc |= baseCheck(base) << 10
}

func (bc baseCheck) Check() byte {
	return byte(bc)
}

func (bc *baseCheck) SetCheck(check byte) {
	*bc |= baseCheck(check)
}

func (bc baseCheck) IsEmpty() bool {
	return bc&0xfffffcff == 0
}

func (bc baseCheck) Index() int {
	return int(bc >> 10)
}

func (bc *baseCheck) SetIndex(i int) {
	*bc |= baseCheck(i) << 10
}

func (bc baseCheck) IsSingleParam() bool {
	return bc&paramTypeSingle == paramTypeSingle
}

func (bc baseCheck) IsWildcardParam() bool {
	return bc&paramTypeWildcard == paramTypeWildcard
}

func (bc baseCheck) IsAnyParam() bool {
	return bc&paramTypeAny != 0
}

func (bc *baseCheck) SetSingleParam() {
	*bc |= (1 << 8)
}

func (bc *baseCheck) SetWildcardParam() {
	*bc |= (1 << 9)
}

const (
	paramTypeSingle   = 0x0100
	paramTypeWildcard = 0x0200
	paramTypeAny      = 0x0300
)

func (da *doubleArray) lookup(path string, params []Param, idx int) (*node, []Param, bool) {
	indices := make([]uint64, 0, 1)
	for i := 0; i < len(path); i++ {
		if da.bc[idx].IsAnyParam() {
			indices = append(indices, (uint64(i)<<32)|uint64(idx&0xffffffff))
		}
		c := path[i]
		next := nextIndex(da.bc[idx].Base(), c)
		if next >= len(da.bc) || da.bc[next].Check() != c {
			goto BACKTRACKING
		}
		idx = next
	}
	if next := nextIndex(da.bc[idx].Base(), TerminationCharacter); da.bc[next].Check() == TerminationCharacter {
		return da.node[da.bc[next].Index()], params, true
	}
	return nil, nil, false
BACKTRACKING:
	for j := len(indices) - 1; j >= 0; j-- {
		i, idx := int(indices[j]>>32), int(indices[j]&0xffffffff)
		if da.bc[idx].IsSingleParam() {
			idx := nextIndex(da.bc[idx].Base(), ParamCharacter)
			if idx >= len(da.bc) {
				break
			}
			next := NextSeparator(path, i)
			params := append(params, Param{Value: path[i:next]})
			if nd, params, found := da.lookup(path[next:], params, idx); found {
				return nd, params, true
			}
		}
		if da.bc[idx].IsWildcardParam() {
			idx := nextIndex(da.bc[idx].Base(), WildcardCharacter)
			params := append(params, Param{Value: path[i:]})
			return da.node[da.bc[idx].Index()], params, true
		}
	}
	return nil, nil, false
}

// build builds double-array from records.
func (da *doubleArray) build(srcs []*record, idx, depth int, usedBase map[int]struct{}) error {
	sort.Sort(recordSlice(srcs))
	base, siblings, leaf, err := da.arrange(srcs, idx, depth, usedBase)
	if err != nil {
		return err
	}
	if leaf != nil {
		nd, err := makeNode(leaf)
		if err != nil {
			return err
		}
		da.bc[idx].SetIndex(len(da.node))
		da.node = append(da.node, nd)
	}
	for _, sib := range siblings {
		da.setCheck(nextIndex(base, sib.c), sib.c)
	}
	for _, sib := range siblings {
{'fraction_non_alphanumeric': 0.16340324023456912, 'fraction_numerical': 0.014511479972169764, 'mean_word_length': 3.5385656292286876, 'pattern_counts': {'":': 8, '<': 27, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2031777', 'n_tokens_mistral': 3810, 'n_tokens_neox': 3560, 'n_words': 1090}