1// Copyright (c) 2017 Couchbase, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package vellum 16 17// Automaton represents the general contract of a byte-based finite automaton 18type Automaton interface { 19 20 // Start returns the start state 21 Start() int 22 23 // IsMatch returns true if and only if the state is a match 24 IsMatch(int) bool 25 26 // CanMatch returns true if and only if it is possible to reach a match 27 // in zero or more steps 28 CanMatch(int) bool 29 30 // WillAlwaysMatch returns true if and only if the current state matches 31 // and will always match no matter what steps are taken 32 WillAlwaysMatch(int) bool 33 34 // Accept returns the next state given the input to the specified state 35 Accept(int, byte) int 36} 37 38// AutomatonContains implements an generic Contains() method which works 39// on any implementation of Automaton 40func AutomatonContains(a Automaton, k []byte) bool { 41 i := 0 42 curr := a.Start() 43 for a.CanMatch(curr) && i < len(k) { 44 curr = a.Accept(curr, k[i]) 45 if curr == noneAddr { 46 break 47 } 48 i++ 49 } 50 if i != len(k) { 51 return false 52 } 53 return a.IsMatch(curr) 54} 55 56// AlwaysMatch is an Automaton implementation which always matches 57type AlwaysMatch struct{} 58 59// Start returns the AlwaysMatch start state 60func (m *AlwaysMatch) Start() int { 61 return 0 62} 63 64// IsMatch always returns true 65func (m *AlwaysMatch) IsMatch(int) bool { 66 return true 67} 68 69// CanMatch always returns true 70func (m *AlwaysMatch) CanMatch(int) bool { 71 return true 72} 73 74// WillAlwaysMatch always returns true 75func (m *AlwaysMatch) WillAlwaysMatch(int) bool { 76 return true 77} 78 79// Accept returns the next AlwaysMatch state 80func (m *AlwaysMatch) Accept(int, byte) int { 81 return 0 82} 83 84// creating an alwaysMatchAutomaton to avoid unnecessary repeated allocations. 85var alwaysMatchAutomaton = &AlwaysMatch{} 86