Source

`tests/purrc/regex_e2e_test.cpp`

2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.

3// regex end-to-end adversarial suite (suite RegexE2E).

4//

5// Each test compiles a real .purr program with purrc and runs it under the cheatah runtime, checking

6// exact stdout — so this exercises the WHOLE pipeline (compiler + runtime + libcheatah_regex.a) the

7// way a user hits it. The emphasis is adversarial: catastrophic-backtracking (ReDoS) inputs that must

8// stay fast and correct, anchoring/quantifier/class edge cases, and the leftmost-longest contract.

9//

10// Every expected string here was captured from the built engine (build/debug) — not guessed.

11// `regex.find` returns `.text` as an OWNED `str` (the library copies the matched bytes), so it is

12// always safe — no borrow, no dangling, even off a temporary input.

13//

14// These are NOT named *CompileRun*, so they run by default in the gate (ctest stage). They are fast

15// (small inputs; the DFA is linear, so even the ReDoS rows return in microseconds).

17#include "e2e_harness.hpp"

19using e2e::expect_e2e;

// ── yes/no answers: search (unanchored) and full_match (anchored both ends) ───────────────

23TEST(RegexE2E, SearchPresentAbsent) {

24 expect_e2e("regex_search", R"PURR(import io

25import regex

26let d = regex.compile("[0-9]+")

27io.print(regex.search(d, "order 4567 shipped"))

28io.print(regex.search(d, "no digits here"))

29)PURR",

30 "True\nFalse\n");

31}

33TEST(RegexE2E, FullMatchIsAnchoredBothEnds) {

34 expect_e2e("regex_fullmatch", R"PURR(import io

35import regex

36let d = regex.compile("[0-9]+")

37io.print(regex.full_match(d, "4567"))

38io.print(regex.full_match(d, "x4567"))

39io.print(regex.full_match(d, "4567x"))

40)PURR",

41 "True\nFalse\nFalse\n");

42}

// ── find: leftmost-longest match, offsets, and the OWNED matched bytes ─────────────────────

46TEST(RegexE2E, FindOffsetsAndOwnedText) {

47 expect_e2e("regex_find", R"PURR(import io

48import regex

49let email = regex.compile("[a-z]+@[a-z.]+")

50let text = "contact bob@example.com now"

51let m = regex.find(email, text)

52io.print(m.matched)

53io.print(m.begin, m.end)

54io.print(m.text)

55io.print(m.text)

56)PURR",

57 "True\n8 23\nbob@example.com\nbob@example.com\n");

58}

60TEST(RegexE2E, FindIsLeftmostLongest) {

61 expect_e2e("regex_greedy", R"PURR(import io

62import regex

63let g = regex.compile("a+")

64let s = "baaab"

65let m = regex.find(g, s)

66io.print(m.text, m.begin, m.end)

67)PURR",

68 "aaa 1 4\n");

69}

71TEST(RegexE2E, FindAlternationLeftmost) {

72 expect_e2e("regex_alt", R"PURR(import io

73import regex

74let alt = regex.compile("cat|dog|bird")

75let s = "I have a dog and a cat"

76let m = regex.find(alt, s)

77io.print(m.text, m.begin, m.end)

78)PURR",

79 "dog 9 12\n");

80}

82// ── the whole point: adversarial ReDoS inputs stay fast AND correct (a backtracker hangs) ──

84TEST(RegexE2E, ReDoSNestedQuantifierReturnsFalseFast) {

85 // (a+)+$ over a long run of 'a' ending in '!' — a classic catastrophic-backtracking pattern.

86 // A backtracking engine explores ~2^n paths; the lazy DFA answers in linear time.

87 expect_e2e("regex_redos1", R"PURR(import io

88import regex

89let evil = regex.compile("(a+)+$")

90let s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"

91io.print(regex.search(evil, s))

92)PURR",

93 "False\n");

94}

96TEST(RegexE2E, ReDoSAlternationStarReturnsFalseFast) {

97 expect_e2e("regex_redos2", R"PURR(import io

98import regex

99let evil = regex.compile("(a|a)*c")

100let s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

101io.print(regex.search(evil, s))

102)PURR",

103 "False\n");

104}

105

106

// ── anchors ───────────────────────────────────────────────────────────────────────────────

107

108TEST(RegexE2E, Anchors) {

109 expect_e2e("regex_anchors", R"PURR(import io

110import regex

111io.print(regex.search(regex.compile("^foo"), "foo bar"))

112io.print(regex.search(regex.compile("^foo"), "bar foo"))

113io.print(regex.search(regex.compile("bar$"), "foo bar"))

114io.print(regex.search(regex.compile("bar$"), "bar foo"))

115)PURR",

116 "True\nFalse\nTrue\nFalse\n");

117}

118

119// ── empty matches: a pattern that can match "" matches EVERYWHERE the anchors allow ───────

120// (Pins the a*$ hole: the first-byte candidate scan must not skip the empty match at

121// end-of-input — see PreviouslyBroken.RegexEmptyMatchAtEndOfInput for the full story.)

122

123TEST(RegexE2E, EmptyMatchAtEveryAnchoring) {

124 expect_e2e("regex_empty", R"PURR(import io

125import regex

126io.print(regex.search(regex.compile("a*$"), "bbb"))

127io.print(regex.search(regex.compile("x*"), "yyy"))

128io.print(regex.search(regex.compile("^$"), ""))

129io.print(regex.search(regex.compile("^$"), "a"))

130io.print(regex.search(regex.compile("$"), "abc"))

131let m = regex.find(regex.compile("x*"), "yyy")

132io.print(m.matched, m.begin, m.end)

133)PURR",

134 "True\n" // a*$ — empty match at end-of-input

135 "True\n" // x* unanchored — empty match at position 0

136 "True\n" // ^$ on "" — the empty input matches

137 "False\n" // ^$ on "a" — both anchors can NOT hold around a byte

138 "True\n" // bare $ — empty match at end of any input

139 "True 0 0\n"); // find pins the leftmost empty match at [0,0)

140}

141

142

// ── quantifiers: * + ? ─────────────────────────────────────────────────────────────────────

143

144TEST(RegexE2E, Quantifiers) {

145 expect_e2e("regex_quant", R"PURR(import io

146import regex

147let plus = regex.compile("ab+c")

148io.print(regex.search(plus, "ac"))

149io.print(regex.search(plus, "abc"))

150io.print(regex.search(plus, "abbbbc"))

151io.print(regex.full_match(regex.compile("ab*c"), "ac"))

152io.print(regex.full_match(regex.compile("colou?r"), "color"))

153io.print(regex.full_match(regex.compile("colou?r"), "colour"))

154)PURR",

155 "False\nTrue\nTrue\nTrue\nTrue\nTrue\n");

156}

157

158

// ── character classes, negation, and the \d \w \s escapes ─────────────────────────────────

159

160TEST(RegexE2E, CharacterClasses) {

161 expect_e2e("regex_classes", R"PURR(import io

162import regex

163io.print(regex.full_match(regex.compile("[^0-9]+"), "abcDEF"))

164io.print(regex.full_match(regex.compile("\\d+"), "12345"))

165io.print(regex.full_match(regex.compile("\\w+"), "abc_123"))

166io.print(regex.search(regex.compile("\\s"), "a b"))

167io.print(regex.full_match(regex.compile("[A-Z]+"), "abc"))

168io.print(regex.full_match(regex.compile("[A-Z]+"), "ABC"))

169)PURR",

170 "True\nTrue\nTrue\nTrue\nFalse\nTrue\n");

171}

172

173

// ── `.` matches any byte EXCEPT newline ────────────────────────────────────────────────────

174

175TEST(RegexE2E, DotExcludesNewline) {

176 expect_e2e("regex_dot", R"PURR(import io

177import regex

178let dot = regex.compile("a.b")

179io.print(regex.search(dot, "axb"))

180io.print(regex.search(dot, "a\nb"))

181)PURR",

182 "True\nFalse\n");

183}

184

185

// ── escaped metacharacters are literals ────────────────────────────────────────────────────

186

187TEST(RegexE2E, EscapedDotIsLiteral) {

188 expect_e2e("regex_escape", R"PURR(import io

189import regex

190let re = regex.compile("a\\.b")

191io.print(regex.full_match(re, "a.b"))

192io.print(regex.full_match(re, "axb"))

193)PURR",

194 "True\nFalse\n");

195}

196

197

// ── a malformed pattern is rejected, not thrown: Pattern.ok == false ───────────────────────

198

199TEST(RegexE2E, MalformedPatternReportsNotOk) {

200 expect_e2e("regex_bad", R"PURR(import io

201import regex

202io.print(regex.compile("[0-9]+").ok)

203io.print(regex.compile("[").ok)

204)PURR",

205 "True\nFalse\n");

206}

207

208

// ── a worked loop: pull every number out of a line by advancing past each match ────────────

209

210TEST(RegexE2E, FindAllNumbersByAdvancing) {

211 expect_e2e("regex_findall", R"PURR(import io

212import regex

213let re = regex.compile("[0-9]+")

214let line = "id=48213 status=200 bytes=1274"

215let rest = line

216for _ in range(0, 10) {

217 let f = regex.find(re, rest)

218 if not f.matched { break }

219 io.print(f.text)

220 rest = rest[f.end:]

221}

222)PURR",

223 "48213\n200\n1274\n");

224}