8000 somemore pattern matching that doesn't work · dragoncoder047/pickle@a64af93 · GitHub
[go: up one dir, main page]
Skip to content

Commit a64af93

Browse files
dragoncoder047dragoncoder047
authored
somemore pattern matching that doesn't work
1 parent de3792d commit a64af93

File tree

2 files changed

+127
-72
lines changed

2 files changed

+127
-72
lines changed

‎python/pickle_lang/object.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,9 @@ def __eq__(self, other):
3232
def __len__(self):
3333
return len(self.pattern)
3434

35+
def __iter__(self):
36+
yield from self.pattern
37+
3538

3639
@dataclass
3740
class Var:

‎python/pickle_lang/pattern.py

Lines changed: 124 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,13 @@ class Match:
1111
end: int
1212
bindings: dict[Symbol, Any]
1313

14+
def __len__(self):
15+
return self.end - self.start
16+
17+
def __or__(self, other: "Match"):
18+
return (Match(self.pattern, self.start, other.end, self.bindings | other.bindings)
19+
if isinstance(other, Match) else NotImplemented)
20+
1421

1522
def pat(
1623
*pattern,
@@ -34,90 +41,132 @@ def partition_and_sort(patterns: list[Pattern]) -> tuple[list[Pattern], list[Pat
3441
return sorted(macros), sorted(non_macros)
3542

3643

44+
def _match_alternate(line: list, source_pat: Pattern, options: list, start: int) -> Match | None:
45+
for option in options:
46+
if result := match_one(line, source_pat, option, start):
47+
return result
48+
# No options matched, so the entire pattern doesn't match
49+
return None
50+
51+
52+
def _match_space(line: list, start: int):
53+
return isinstance(line[start], Space)
54+
55+
56+
def _match_var(line: list, source_pat: Pattern, what: Var, start: int):
57+
elem = line[start]
58+
if what.use_cls:
59+
success = isinstance(elem, what.cls)
60+
else:
61+
success = elem == what.cls
62+
if success:
63+
return Match(source_pat, start, start+1, {what.var: elem})
64+
return None
65+
66+
67+
def _match_repeat_fixed(line: list, source_pat: Pattern, what: list, start: int, num_repeats: int):
68+
result = None
69+
i = start
70+
for _ in range(num_repeats):
71+
result = match_one(line, source_pat, what, i)
72+
if result is None:
73+
break
74+
i = result.end
75+
return result
76+
77+
78+
def _match_repeat_greedy(line: list, source_pat: Pattern, what: list, start: int, max_rep: int):
79+
# NOTE HERE: it is NOT 'max_rep > 0' because max_rep == -1 if infinite repeats allowed
80+
i = start
81+
result = None
82+
while max_rep != 0 and i < len(line):
83+
result = match_one(line, source_pat, what, i)
84+
if result is None:
85+
# hit max number of repeats
86+
break
87+
max_rep -= 1
88+
assert result.start == i
89+
i = result.end
90+
return result
91+
92+
93+
def _match_repeat_lazy(
94+
line: list,
95+
source_pat: Pattern,
96+
what: list,
97+
rest_of_pat: list,
98+
start: int,
99+
max_rep: int):
100+
# NOTE HERE: it is NOT 'max_rep > 0' because max_rep == -1 if infinite repeats allowed
101+
i = start
102+
result = None
103+
while max_rep != 0 and i < len(line):
104+
# try to match remainder without more
105+
# if it works, stop (not greedy)
106+
if without := match_one(line, source_pat, rest_of_pat, i):
107+
assert result.start == i
108+
i = without.end
109+
result |= without
110+
break
111+
if result := match_one(line, source_pat, what, i):
112+
assert result.start == i
113+
i = result.end
114+
else:
115+
return None
116+
max_rep -= 1
117+
return result
118+
119+
37120
def match_one(line: list, source_pat: Pattern, pattern: list, start: int) -> Match | None:
38121
"""Try to match the mattern at the specified index in the line,
39122
or return None if it doesn't match."""
40-
# pylint:disable=assignment-from-none
41123
patt_i = 0
42124
line_i = start
43125
bindings = {}
44-
while patt_i < len(pattern) and line_i < len(line):
126+
for patt_i, item in enumerate(pattern):
45127
elem = line[line_i]
46-
match entry := pattern[patt_i]:
47-
case Alternate():
48-
for option in entry.options:
49-
if result := match_one(line, source_pat, option, line_i):
50-
bindings |= result.bindings
51-
line_i = result.end
52-
break
53-
else:
54-
# No options matched, so the entire pattern doesn't match
55-
return None
56-
case Repeat():
128+
result = None
129+
match item:
130+
case Alternate(options=opts):
131+
result = _match_alternate(line, source_pat, opts, line_i)
132+
case Repeat(min=min_rep, max=max_rep, what=what, greedy=greedy):
57133
# try to match min repeats first;
58-
# if there isn't enough for that even then bail
59-
for _ in range(entry.min):
60-
result = match_one(line, source_pat, entry.what, line_i)
61-
if result is None:
62-
return None
63-
bindings |= result.bindings
64-
line_i = result.end
65-
if entry.max is not None:
66-
more = entry.max - entry.min
67-
else:
68-
more = -1
69-
if entry.greedy:
70-
# NOTE HERE: it is NOT 'more > 0' because more == -1 if infinite repeats allowed
71-
while more != 0 and line_i < len(line):
72-
result = match_one(
73-
line, source_pat, entry.what, line_i)
74-
if result is None:
75-
# hit max number of repeats
76-
break
77-
bindings |= result.bindings
78-
line_i = result.end
79-
more -= 1
134+
# if there isn't enough for that, then bail
135+
result = _match_repeat_fixed(
136+
line, source_pat, what, line_i, min_rep)
137+
if result is None:
138+
return None
139+
more = max_rep - min_rep if max_rep else -1
140+
if greedy:
141+
more = _match_repeat_greedy(
142+
line, source_pat, what, line_i, more)
80143
else:
81-
# NOTE HERE: it is NOT 'more > 0' because more == -1 if infinite repeats allowed
82-
while more != 0 and line_i < len(line):
83-
# try to match remainder without more
84-
# if it works, stop (not greedy)
85-
if without := match_one(line, source_pat, pattern[patt_i + 1:], line_i):
86-
bindings |= without.bindings
87-
line_i = without.end
88-
patt_i = len(pattern)
89-
break
90-
if result := match_one(line, source_pat, entry.what, line_i):
91-
bindings |= result.bindings
92-
line_i = result.end
93-
else:
94-
return None
95-
more -= 1
144+
more = _match_repeat_lazy(
145+
line, source_pat, what, pattern[patt_i+1:], line_i, more)
146+
if more is not None:
147+
result |= more
96148
case Space():
97-
if isinstance(elem, Space):
98-
# greedy
99-
line_i += 1
100-
case Var():
101-
if entry.use_cls:
102-
success = isinstance(elem, entry.cls)
103-
else:
104-
success = elem == entry.cls
105-
if success:
106-
line_i += 1
107-
bindings[entry.var] = elem
108-
else:
109-
return None
110-
case _:
111-
if entry != elem:
112-
return None
113-
line_i += 1
114-
patt_i += 1
149+
result = _match_space(line, line_i)
150+
case Var() as entry:
151+
result = _match_var(line, source_pat, entry, line_i)
152+
case _ as entry:
153+
result = entry != elem
154+
if not result:
155+
return None
156+
if isinstance(result, Match):
157+
bindings |= result.bindings
158+
assert result.start == line_i
159+
line_i = result.end
160+
else:
161+
line_i += 1
162+
if line_i >= len(line):
163+
break
115164
if patt_i >= len(pattern):
116165
return Match(source_pat, start, line_i + 1, bindings)
117166
return None
118167

119168

120-
def match(line: list, patterns: list[Pattern]) -> Match:
169+
def match_patterns(line: list, patterns: list[Pattern]) -> Match | None:
121170
"""Finds the best match using the highest-precedence pattern that matches."""
122171
for pattern in sorted(patterns):
123172
matches: list[Match] = []
@@ -128,12 +177,15 @@ def match(line: list, patterns: list[Pattern]) -> Match:
128177
return matches[-1 if pattern.right else 0]
129178
return None
130179

180+
131181
if __name__ == "__main__":
132182
test_line = [0, 1, 2, 1, 2, 1, 2, 77]
183+
# """
133184
patts = [
134-
Pattern(1, [Repeat([1, 2], 1, None, False), Var("foo", int)], None),
185+
Pattern(1, [Repeat([1, 2], 1, None), Var("foo", int)], None),
135186
]
136-
m = match(test_line, patts)
137-
test_line[m.start:m.end] = ["foo"]
187+
m = match_patterns(test_line, patts)
188+
test_line[m.start:m.end] = ["replaced"]
138189
print(m)
139190
print(test_line)
191+
# """

0 commit comments

Comments
 (0)
0