matcher

package
v0.0.0-...-53e5e69 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 10, 2022 License: MIT Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source 
const PrimeRK = 16777619

PrimeRK is the prime base used in Rabin-Karp algorithm.

Variables

View Source 
var (
	NilGroup = &matcherGroup{}
)

Functions

func AddMatcherToGroup 

func AddMatcherToGroup(g Group, matcher Matcher, value uint32) error

AddMatcherToGroup is a helper function to try to add a Matcher to any kind of Group. It returns error if the Group does not accept the provided Matcher's type. This function is provided to help writing code to test a Group.

func RollingHash 

func RollingHash(s string) uint32

RollingHash calculate the rolling murmurHash of given string

Types

type ACAutomatonMatcherGroup 

type ACAutomatonMatcherGroup struct {
	// contains filtered or unexported fields
}

ACAutomatonMatcherGroup is an implementation of Group. It uses an AC Automata to provide support for Full, Domain and Substr matcher. Trie node is char based.

NOTICE: ACAutomatonMatcherGroup currently uses a restricted charset (LDH Subset), upstream should manually in a way to ensure all patterns and inputs passed to it to be in this charset.

func NewACAutomatonMatcherGroup 

func NewACAutomatonMatcherGroup() *ACAutomatonMatcherGroup

func (*ACAutomatonMatcherGroup) AddDomainMatcher 

func (ac *ACAutomatonMatcherGroup) AddDomainMatcher(matcher DomainMatcher, value uint32)

AddDomainMatcher implements GroupForDomain.AddDomainMatcher.

func (*ACAutomatonMatcherGroup) AddFullMatcher 

func (ac *ACAutomatonMatcherGroup) AddFullMatcher(matcher FullMatcher, value uint32)

AddFullMatcher implements GroupForFull.AddFullMatcher.

func (*ACAutomatonMatcherGroup) AddSubstrMatcher 

func (ac *ACAutomatonMatcherGroup) AddSubstrMatcher(matcher SubstrMatcher, value uint32)

AddSubstrMatcher implements GroupForSubstr.AddSubstrMatcher.

func (*ACAutomatonMatcherGroup) Build 

func (ac *ACAutomatonMatcherGroup) Build() error

func (*ACAutomatonMatcherGroup) Match 

func (ac *ACAutomatonMatcherGroup) Match(input string) []uint32

Match implements Group.Match.

func (*ACAutomatonMatcherGroup) MatchAny 

func (ac *ACAutomatonMatcherGroup) MatchAny(input string) bool

MatchAny implements Group.MatchAny.

type CIDR 

type CIDR struct {
	Ip     []byte
	Prefix uint32
}

func (*CIDR) UnmarshalJSON 

func (c *CIDR) UnmarshalJSON(s []byte) error

type CIDRList 

type CIDRList []*CIDR

CIDRList is an alias of []*CIDR to provide sort.Interface.

func (*CIDRList) Len 

func (l *CIDRList) Len() int

Len implements sort.Interface.

func (*CIDRList) Less 

func (l *CIDRList) Less(i int, j int) bool

Less implements sort.Interface.

func (*CIDRList) Swap 

func (l *CIDRList) Swap(i int, j int)

Swap implements sort.Interface.

type DomainMatcher 

type DomainMatcher string

DomainMatcher is an implementation of Matcher.

func (DomainMatcher) Match 

func (m DomainMatcher) Match(s string) bool

func (DomainMatcher) Pattern 

func (m DomainMatcher) Pattern() string

func (DomainMatcher) String 

func (m DomainMatcher) String() string

func (DomainMatcher) Type 

func (DomainMatcher) Type() Type

func (*DomainMatcher) UnmarshalJSON 

func (m *DomainMatcher) UnmarshalJSON(s []byte) error

type DomainMatcherGroup 

type DomainMatcherGroup struct {
	// contains filtered or unexported fields
}

DomainMatcherGroup is an implementation of Group. It uses trie to optimize both memory consumption and lookup speed. Trie node is domain label based.

func (*DomainMatcherGroup) AddDomainMatcher 

func (g *DomainMatcherGroup) AddDomainMatcher(matcher DomainMatcher, value uint32)

AddDomainMatcher implements GroupForDomain.AddDomainMatcher.

func (*DomainMatcherGroup) Match 

func (g *DomainMatcherGroup) Match(domain string) []uint32

Match implements Group.Match.

func (*DomainMatcherGroup) MatchAny 

func (g *DomainMatcherGroup) MatchAny(domain string) bool

MatchAny implements Group.MatchAny.

type FullMatcher 

type FullMatcher string

FullMatcher is an implementation of Matcher.

func (FullMatcher) Match 

func (m FullMatcher) Match(s string) bool

func (FullMatcher) Pattern 

func (m FullMatcher) Pattern() string

func (FullMatcher) String 

func (m FullMatcher) String() string

func (FullMatcher) Type 

func (FullMatcher) Type() Type

func (*FullMatcher) UnmarshalJSON 

func (m *FullMatcher) UnmarshalJSON(s []byte) error

type FullMatcherGroup 

type FullMatcherGroup struct {
	// contains filtered or unexported fields
}

FullMatcherGroup is an implementation of Group. It uses a hash table to facilitate exact match lookup.

func (*FullMatcherGroup) AddFullMatcher 

func (g *FullMatcherGroup) AddFullMatcher(matcher FullMatcher, value uint32)

AddFullMatcher implements GroupForFull.AddFullMatcher.

func (*FullMatcherGroup) Match 

func (g *FullMatcherGroup) Match(input string) []uint32

Match implements Group.Match.

func (*FullMatcherGroup) MatchAny 

func (g *FullMatcherGroup) MatchAny(input string) bool

MatchAny implements Group.Any.

type GeoIPMatcher 

type GeoIPMatcher struct {
	// contains filtered or unexported fields
}

func (*GeoIPMatcher) Init 

func (m *GeoIPMatcher) Init(cidrs []*CIDR) error

func (*GeoIPMatcher) Match 

func (m *GeoIPMatcher) Match(ip net.IP) bool

Match returns true if the given ip is included by the GeoIP.

type Group 

type Group interface {
	// Match returns all matched matchers with their corresponding values.
	Match(input string) []uint32

	// MatchAny returns true as soon as one matching matcher is found.
	MatchAny(input string) bool
}

Group is an advanced type of matcher to accept a bunch of basic Matchers (of certain type, not all matcher types). For example:

  • FullMatcherGroup accepts FullMatcher and uses a hash table to facilitate lookup.
  • DomainMatcherGroup accepts DomainMatcher and uses a trie to optimize both memory consumption and lookup speed.

type GroupForAll 

type GroupForAll interface {
	AddMatcher(matcher Matcher, value uint32)
}

GroupForAll is an interface indicating a Group could accept all types of matchers.

type GroupForDomain 

type GroupForDomain interface {
	AddDomainMatcher(matcher DomainMatcher, value uint32)
}

GroupForDomain is an interface indicating a Group could accept DomainMatchers.

type GroupForFull 

type GroupForFull interface {
	AddFullMatcher(matcher FullMatcher, value uint32)
}

GroupForFull is an interface indicating a Group could accept FullMatchers.

type GroupForRegex 

type GroupForRegex interface {
	AddRegexMatcher(matcher *RegexMatcher, value uint32)
}

GroupForRegex is an interface indicating a Group could accept RegexMatchers.

type GroupForSubstr 

type GroupForSubstr interface {
	AddSubstrMatcher(matcher SubstrMatcher, value uint32)
}

GroupForSubstr is an interface indicating a Group could accept SubstrMatchers.

type IndexMatcher 

type IndexMatcher interface {
	// Size returns number of matchers added to IndexMatcher.
	Size() uint32

	// Add adds a new Matcher to IndexMatcher, and returns its index. The index will never be 0.
	Add(matcher Matcher) uint32

	// Build builds the IndexMatcher to be ready for matching.
	Build() error

	// Match returns the indices of all matchers that matches the input.
	//   * Empty array is returned if no such matcher exists.
	//   * The order of returned matchers should follow priority specification.
	// Priority specification:
	//   1. Priority between matcher types: full > domain > substr > regex.
	//   2. Priority of same-priority matchers matching at same position: the early added takes precedence.
	//   3. Priority of domain matchers matching at different levels: the further matched domain takes precedence.
	//   4. Priority of substr matchers matching at different positions: the further matched substr takes precedence.
	Match(input string) []uint32

	// MatchAny returns true as soon as one matching matcher is found.
	MatchAny(input string) bool
}

IndexMatcher is a general type of matcher that's accepts all kinds of basic matchers. It should:

  • Accept all Matcher types with no exception.
  • Optimize string matching with a combination of MatcherGroups.
  • Obey certain priority order specification when returning matched Matchers.

type LinearIndexMatcher 

type LinearIndexMatcher struct {
	// contains filtered or unexported fields
}

LinearIndexMatcher is an implementation of IndexMatcher. Empty initialization works.

func NewLinearIndexMatcher 

func NewLinearIndexMatcher() *LinearIndexMatcher

func (*LinearIndexMatcher) Add 

func (g *LinearIndexMatcher) Add(matcher Matcher) uint32

Add implements IndexMatcher.Add.

func (*LinearIndexMatcher) Build 

func (*LinearIndexMatcher) Build() error

Build implements IndexMatcher.Build.

func (*LinearIndexMatcher) Match 

func (g *LinearIndexMatcher) Match(input string) []uint32

Match implements IndexMatcher.Match.

func (*LinearIndexMatcher) MatchAny 

func (g *LinearIndexMatcher) MatchAny(input string) bool

MatchAny implements IndexMatcher.MatchAny.

func (*LinearIndexMatcher) Size 

func (g *LinearIndexMatcher) Size() uint32

Size implements IndexMatcher.Size.

type Matcher 

type Matcher interface {
	// Type returns the matcher's type.
	Type() Type

	// Pattern returns the matcher's raw string representation.
	Pattern() string

	// String returns a string representation of the matcher containing its type and pattern.
	String() string

	// Match returns true if the given string matches a predefined pattern.
	//   * This method is seldom used for performance reason
	//     and is generally taken over by their corresponding Group.
	Match(input string) bool
}

Matcher is the interface to determine a string matches a pattern.

  • This is a basic matcher to represent a certain kind of match semantic(full, substr, domain or regex).

type MphIndexMatcher 

type MphIndexMatcher struct {
	// contains filtered or unexported fields
}

A MphIndexMatcher is divided into three parts: 1. `full` and `domain` patterns are matched by Rabin-Karp algorithm and minimal perfect hash table; 2. `substr` patterns are matched by ac automaton; 3. `regex` patterns are matched with the regex library.

func NewMphIndexMatcher 

func NewMphIndexMatcher() *MphIndexMatcher

func (*MphIndexMatcher) Add 

func (g *MphIndexMatcher) Add(matcher Matcher) uint32

Add implements IndexMatcher.Add.

func (*MphIndexMatcher) Build 

func (g *MphIndexMatcher) Build() error

Build implements IndexMatcher.Build.

func (*MphIndexMatcher) Match 

func (*MphIndexMatcher) Match(string) []uint32

Match implements IndexMatcher.Match.

func (*MphIndexMatcher) MatchAny 

func (g *MphIndexMatcher) MatchAny(input string) bool

MatchAny implements IndexMatcher.MatchAny.

func (*MphIndexMatcher) Size 

func (g *MphIndexMatcher) Size() uint32

Size implements IndexMatcher.Size.

type MphMatcherGroup 

type MphMatcherGroup struct {
	// contains filtered or unexported fields
}

MphMatcherGroup is an implementation of Group. It implements Rabin-Karp algorithm and minimal perfect hash table for Full and Domain matcher.

func NewMphMatcherGroup 

func NewMphMatcherGroup() *MphMatcherGroup

func (*MphMatcherGroup) AddDomainMatcher 

func (g *MphMatcherGroup) AddDomainMatcher(matcher DomainMatcher, _ uint32)

AddDomainMatcher implements GroupForDomain.

func (*MphMatcherGroup) AddFullMatcher 

func (g *MphMatcherGroup) AddFullMatcher(matcher FullMatcher, _ uint32)

AddFullMatcher implements GroupForFull.

func (*MphMatcherGroup) Build 

func (g *MphMatcherGroup) Build()

Build builds a minimal perfect hash table for insert rules.

func (*MphMatcherGroup) Lookup 

func (g *MphMatcherGroup) Lookup(h uint32, s string) bool

Lookup searches for s in t and returns its index and whether it was found.

func (*MphMatcherGroup) Match 

func (*MphMatcherGroup) Match(_ string) []uint32

Match implements Group.Match.

func (*MphMatcherGroup) MatchAny 

func (g *MphMatcherGroup) MatchAny(pattern string) bool

MatchAny implements Group.MatchAny.

type RegexMatcher 

type RegexMatcher struct {
	// contains filtered or unexported fields
}

RegexMatcher is an implementation of Matcher.

func (*RegexMatcher) Match 

func (m *RegexMatcher) Match(s string) bool

func (*RegexMatcher) Pattern 

func (m *RegexMatcher) Pattern() string

func (*RegexMatcher) String 

func (m *RegexMatcher) String() string

func (*RegexMatcher) Type 

func (*RegexMatcher) Type() Type

func (*RegexMatcher) UnmarshalJSON 

func (m *RegexMatcher) UnmarshalJSON(s []byte) error

type SimpleMatcherGroup 

type SimpleMatcherGroup struct {
	// contains filtered or unexported fields
}

SimpleMatcherGroup is an implementation of Group. It simply stores all matchers in an array and sequentially matches them.

func (*SimpleMatcherGroup) AddMatcher 

func (g *SimpleMatcherGroup) AddMatcher(matcher Matcher, value uint32)

AddMatcher implements GroupForAll.AddMatcher.

func (*SimpleMatcherGroup) Match 

func (g *SimpleMatcherGroup) Match(input string) []uint32

Match implements Group.Match.

func (*SimpleMatcherGroup) MatchAny 

func (g *SimpleMatcherGroup) MatchAny(input string) bool

MatchAny implements Group.MatchAny.

type SubstrMatcher 

type SubstrMatcher string

SubstrMatcher is an implementation of Matcher.

func (SubstrMatcher) Match 

func (m SubstrMatcher) Match(s string) bool

func (SubstrMatcher) Pattern 

func (m SubstrMatcher) Pattern() string

func (SubstrMatcher) String 

func (m SubstrMatcher) String() string

func (SubstrMatcher) Type 

func (SubstrMatcher) Type() Type

func (*SubstrMatcher) UnmarshalJSON 

func (m *SubstrMatcher) UnmarshalJSON(s []byte) error

type SubstrMatcherGroup 

type SubstrMatcherGroup struct {
	// contains filtered or unexported fields
}

SubstrMatcherGroup is implementation of Group, It is simply implmeneted to comply with the priority specification of Substr matchers.

func (*SubstrMatcherGroup) AddSubstrMatcher 

func (g *SubstrMatcherGroup) AddSubstrMatcher(matcher SubstrMatcher, value uint32)

AddSubstrMatcher implements GroupForSubstr.AddSubstrMatcher.

func (*SubstrMatcherGroup) Match 

func (g *SubstrMatcherGroup) Match(input string) []uint32

Match implements Group.Match.

func (*SubstrMatcherGroup) MatchAny 

func (g *SubstrMatcherGroup) MatchAny(input string) bool

MatchAny implements Group.MatchAny.

type Type 

type Type byte

Type is the type of the matcher. 

const (
	// Full is the type of matcher that the input string must exactly equal to the pattern.
	Full Type = 0
	// Domain is the type of matcher that the input string must be a subdomain or itself of the pattern.
	Domain Type = 1
	// Substr is the type of matcher that the input string must contain the pattern as a sub-string.
	Substr Type = 2
	// Regex is the type of matcher that the input string must matches the regular-expression pattern.
	Regex Type = 3
)

func (Type) New 

func (t Type) New(pattern string) (Matcher, error)

New creates a new Matcher based on the given pattern.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.