1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101
102. 102
103. 103
104. 104
105. 105
106. 106
107. 107
108. 108
109. 109
110. 110
111. 111
112. 112
113. 113
114. 114
115. 115
116. 116
117. 117
118. 118
119. 119

//  Copyright (c) 2017 Couchbase, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 		http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package regexp

import (
	"fmt"
	"regexp/syntax"
)

// ErrNoEmpty returned when "zero width assertions" are used
var ErrNoEmpty = fmt.Errorf("zero width assertions not allowed")

// ErrNoWordBoundary returned when word boundaries are used
var ErrNoWordBoundary = fmt.Errorf("word boundaries are not allowed")

// ErrNoBytes returned when byte literals are used
var ErrNoBytes = fmt.Errorf("byte literals are not allowed")

// ErrNoLazy returned when lazy quantifiers are used
var ErrNoLazy = fmt.Errorf("lazy quantifiers are not allowed")

// ErrCompiledTooBig returned when regular expression parses into
// too many instructions
var ErrCompiledTooBig = fmt.Errorf("too many instructions")

var DefaultLimit = uint(10 * (1 << 20))

// Regexp implements the vellum.Automaton interface for matcing a user
// specified regular expression.
type Regexp struct {
	orig string
	dfa  *dfa
}

// NewRegexp creates a new Regular Expression automaton with the specified
// expression.  By default it is limited to approximately 10MB for the
// compiled finite state automaton.  If this size is exceeded,
// ErrCompiledTooBig will be returned.
func New(expr string) (*Regexp, error) {
	return NewWithLimit(expr, DefaultLimit)
}

// NewRegexpWithLimit creates a new Regular Expression automaton with
// the specified expression.  The size of the compiled finite state
// automaton exceeds the user specified size,  ErrCompiledTooBig will be
// returned.
func NewWithLimit(expr string, size uint) (*Regexp, error) {
	parsed, err := syntax.Parse(expr, syntax.Perl)
	if err != nil {
		return nil, err
	}
	return NewParsedWithLimit(expr, parsed, size)
}

func NewParsedWithLimit(expr string, parsed *syntax.Regexp, size uint) (*Regexp, error) {
	compiler := newCompiler(size)
	insts, err := compiler.compile(parsed)
	if err != nil {
		return nil, err
	}
	dfaBuilder := newDfaBuilder(insts)
	dfa, err := dfaBuilder.build()
	if err != nil {
		return nil, err
	}
	return &Regexp{
		orig: expr,
		dfa:  dfa,
	}, nil
}

// Start returns the start state of this automaton.
func (r *Regexp) Start() int {
	return 1
}

// IsMatch returns if the specified state is a matching state.
func (r *Regexp) IsMatch(s int) bool {
	if s < len(r.dfa.states) {
		return r.dfa.states[s].match
	}
	return false
}

// CanMatch returns if the specified state can ever transition to a matching
// state.
func (r *Regexp) CanMatch(s int) bool {
	if s < len(r.dfa.states) && s > 0 {
		return true
	}
	return false
}

// WillAlwaysMatch returns if the specified state will always end in a
// matching state.
func (r *Regexp) WillAlwaysMatch(int) bool {
	return false
}

// Accept returns the new state, resulting from the transition byte b
// when currently in the state s.
func (r *Regexp) Accept(s int, b byte) int {
	if s < len(r.dfa.states) {
		return r.dfa.states[s].next[b]
	}
	return 0
}