1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
const std = @import("std");
pub const Token = struct {
pub const Kind = enum { Literal, LParen, RParen, Class, Dot, Star, Plus, Question, Or };
pub const Value = union(Token.Kind) { Literal: u8, LParen, RParen, Class: RangeList, Dot, Star, Plus, Question, Or };
kind: Token.Kind,
value: ?Token.Value,
pos: usize,
pub fn format(self: *const Token, comptime fmt: []const u8, _: std.fmt.FormatOptions, writer: anytype) !void {
if (fmt.len != 0) { // must be {} or {any}
return std.invalidFmtError(fmt, self);
}
try writer.print("{{ kind: {s}", .{@tagName(self.kind)});
if (self.value) |val| {
switch (val) {
.Literal => |literal| try writer.print(", value: {c}", .{literal}),
.Class => |rl| try writer.print(", value: {}", .{rl}),
else => {},
}
}
try writer.print(" }}", .{});
}
};
pub const Lexer = struct {
start: usize,
cursor: usize,
regexp: []const u8,
allocator: *std.mem.Allocator,
pub const Error = error{ EndOfBuffer, InvalidCharacter, UnexpectedCharater };
pub fn init(regexp: []const u8, allocator: *std.mem.Allocator) Lexer {
return .{ .cursor = 0, .start = 0, .regexp = regexp, .allocator = allocator };
}
fn readChar(self: *Lexer) !u8 {
if (self.cursor >= self.regexp.len) {
return Error.EndOfBuffer;
}
return self.regexp[self.cursor];
}
pub fn advance(self: *Lexer) !Token {
self.start = self.cursor;
var c = try self.readChar();
const inferred_type: Token.Kind = switch (c) {
'(' => .LParen,
')' => .RParen,
'[' => .Class,
'.' => .Dot,
'*' => .Star,
'+' => .Plus,
'?' => .Question,
'|' => .Or,
else => .Literal,
};
switch (inferred_type) {
.Literal => {
if (c == '\\') {
self.cursor += 1;
c = try self.readChar(); // needs more verbose error handling
c = escapedChar(c);
}
self.cursor += 1;
return .{ .kind = inferred_type, .value = .{ .Literal = c }, .pos = self.start };
},
.Class => {
while (c != ']') { // needs more verbose error handling
if (self.cursor >= self.regexp.len) {
return Error.EndOfBuffer;
}
self.cursor += 1;
}
return .{ .kind = inferred_type, .value = .{ .Class = try RangeList.init(self.regexp[self.start + 1 .. self.cursor - 1], self.allocator) }, .pos = self.start };
},
else => {
self.cursor += 1;
return .{ .kind = inferred_type, .pos = self.start, .value = null };
},
}
}
fn escapedChar(c: u8) u8 {
return switch (c) {
'n' => '\n', // placeholder for now
't' => '\t',
'r' => '\r',
else => c,
};
}
};
// could use something like a bst, but thinking about what regex classes people actually write makes me think that a list is more efficient
pub const RangeList = struct {
negated: bool,
head: ?*Node,
allocator: *std.mem.Allocator,
const Node = struct {
range: struct { min: u8, max: u8 },
next: ?*Node,
};
// need to do more error handling
pub fn init(str: []const u8, allocator: *std.mem.Allocator) !RangeList {
var rl = RangeList{
.negated = false,
.head = null,
.allocator = allocator,
};
var i: usize = 0;
if (str.len == 0) {
return rl;
}
if (str[0] == '^') {
rl.negated = true;
i += 1;
}
var p = rl.head;
while (i < str.len) : (i += 1) {
const node = try rl.allocator.create(Node);
const min = str[i];
var max = min;
i += 1;
if (i + 1 < str.len and str[i] == '-') {
i += 1;
max = str[i];
i += 1;
}
node.* = .{
.range = .{ .min = min, .max = max },
.next = null,
};
if (p) |tail| {
tail.next = node;
p = tail.next;
} else {
rl.head = node;
p = rl.head;
}
}
return rl;
}
pub fn deinit(self: *const RangeList) void {
var itr = self.head;
while (itr) |node| {
const prev = node;
itr = node.next;
self.allocator.destroy(prev);
}
}
pub fn format(self: *const RangeList, comptime fmt: []const u8, _: std.fmt.FormatOptions, writer: anytype) !void {
var itr = self.head;
if (fmt.len != 0) { // must be {} or {any}
return std.invalidFmtError(fmt, self);
}
if (self.negated) {
try writer.print("^", .{});
}
try writer.print("[", .{});
while (itr) |node| : (itr = node.next) {
if (node.range.min == node.range.max) {
try writer.print("{c}", .{node.range.min});
} else {
try writer.print("{c}-{c}", .{ node.range.min, node.range.max });
}
if (node.next) |_| {
try writer.print(", ", .{});
}
}
try writer.print("]", .{});
}
};
|
