1// Copyright (c) 2018 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 segment 16 17import ( 18 "regexp/syntax" 19 20 "github.com/couchbase/vellum/regexp" 21) 22 23func ParseRegexp(pattern string) (a *regexp.Regexp, prefixBeg, prefixEnd []byte, err error) { 24 // TODO: potential optimization where syntax.Regexp supports a Simplify() API? 25 26 parsed, err := syntax.Parse(pattern, syntax.Perl) 27 if err != nil { 28 return nil, nil, nil, err 29 } 30 31 re, err := regexp.NewParsedWithLimit(pattern, parsed, regexp.DefaultLimit) 32 if err != nil { 33 return nil, nil, nil, err 34 } 35 36 prefix := LiteralPrefix(parsed) 37 if prefix != "" { 38 prefixBeg := []byte(prefix) 39 prefixEnd := IncrementBytes(prefixBeg) 40 return re, prefixBeg, prefixEnd, nil 41 } 42 43 return re, nil, nil, nil 44} 45 46// Returns the literal prefix given the parse tree for a regexp 47func LiteralPrefix(s *syntax.Regexp) string { 48 // traverse the left-most branch in the parse tree as long as the 49 // node represents a concatenation 50 for s != nil && s.Op == syntax.OpConcat { 51 if len(s.Sub) < 1 { 52 return "" 53 } 54 55 s = s.Sub[0] 56 } 57 58 if s.Op == syntax.OpLiteral && (s.Flags&syntax.FoldCase == 0) { 59 return string(s.Rune) 60 } 61 62 return "" // no literal prefix 63} 64 65func IncrementBytes(in []byte) []byte { 66 rv := make([]byte, len(in)) 67 copy(rv, in) 68 for i := len(rv) - 1; i >= 0; i-- { 69 rv[i] = rv[i] + 1 70 if rv[i] != 0 { 71 return rv // didn't overflow, so stop 72 } 73 } 74 return nil // overflowed 75} 76