-
Notifications
You must be signed in to change notification settings - Fork 0
/
simple.py
163 lines (145 loc) · 6.14 KB
/
simple.py
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
from .symbol import Nullable, TransSymbol
class NoMatchException(Exception):
pass
class Everything:
def __contains__(self, item):
return True
everything = Everything()
def get_default(obj, key):
# Equivalent of .get(key, None) on dicts, but works on non-dicts.
try:
return obj[key]
except TypeError as e:
pass
except KeyError as e:
pass
try:
return obj.__getattribute__(key)
except AttributeError as e:
return None
def unique(matches):
# TODO: write a not-terrible unique function. Requires recursively changing dicts to something hashable.
result = []
for m in matches:
if not m in result:
result.append(m)
return result
def cartesian(partials):
# Each 'partial' is a list of possible value maps for some subset of the symbols
# ex.: [[{'a':1},{'a':2}], [{'b':3},{'b':4}]] -> [{'a':1,'b':3},{'a':1,'b':4},{'a':2,'b':3},{'a':2,'b':4}]
if len(partials) == 0:
return []
if len(partials) == 1 and len(partials[0]) == 0:
# Annoying corner case, I should probably handle uniqueing earlier so it's not needed
return [{}]
if len(partials) == 1:
return partials[0]
if len(partials[0]) == 0:
# This lets match_simple handle parts of the data which don't contain any relevant symbols.
# TODO: refactor so it doesn't need special handling. Will probably involve uniqueing earlier.
return cartesian(partials[1:])
result = []
for remainder in cartesian(partials[1:]):
for candidate in partials[0]:
# If the two symbol sets have any symbols in common, then match on their values
# TODO: make this more efficient
common = set(remainder).intersection(candidate)
if {k: remainder[k] for k in common} != {k: candidate[k] for k in common}:
continue
# The "cartesian" part
full = {k:v for k,v in remainder.items()}
full.update(candidate)
result.append(full)
return result
def match_simple(template, data, symbols=everything):
if not symbols:
# Corner case, never reached by recursion.
return [{}]
if hasattr(template, '__substitute__') and template in symbols:
return [{template: data}]
elif hasattr(template, '__substitute__'):
return []
elif type(template) == Nullable:
try:
return match_simple(template.contents, data, symbols)
except NoMatchException:
return []
partials = []
if type(template) == TransSymbol:
if symbols != everything and len(set(get_symbols(template)).intersection(symbols)) == 0:
# template does not contain any of the symbols we care about
return []
deduced_data = template._reverse(data)
partials.append([{template: data}])
partials.append(match_simple(template._symbol, deduced_data, symbols))
elif type(template) == dict:
for key in template:
partials.append(match_simple(template.get(key, None), get_default(data, key), symbols))
elif type(template) == list:
for target_element in template:
matches = []
found_match = False
# I put a massive hack here so that, if data isn't list-like, we wrap it in a single-element list
# That will allow us to handle an issue with data parsed from xml, where the parser only sticks things
# in lists if there's more than one of the thing (so if there's only one, it doesn't go in a list).
if type(data) not in set([list, tuple]):
data = [data]
for candidate_element in (data or []):
try:
# attempt match; error means no match
# Note: can return something empty *without* an error; this means match is successful, there just weren't any symbols
matches += match_simple(target_element, candidate_element, symbols)
found_match = True
except NoMatchException:
continue
if not found_match:
# TODO: find some library to serialize stuff into something short but useful.
raise NoMatchException(target_element)
partials.append(matches)
elif template != data:
raise NoMatchException()
#print(partials)
return unique(cartesian(partials))
def get_symbols(template):
if type(template) == TransSymbol:
return get_symbols(template._symbol)
if hasattr(template, '__substitute__'):
return [template]
if type(template) == list:
return sum([get_symbols(v) for v in template], [])
if type(template) == dict:
return sum([get_symbols(v) for v in template.values()], [])
if type(template) == Nullable:
return get_symbols(template.contents)
return []
def format_simple_single(template, values):
if type(template) == dict:
return {key: format_simple_single(val, values) for key, val in template.items()}
elif type(template) == list:
return [format_simple_single(element, values) for element in template]
elif type(template) == Nullable:
result = format_simple_single(template.contents, values)
if get_symbols(result):
return Nullable(result)
return result
elif type(template) == TransSymbol:
if template in values:
return values[template]
result = format_simple_single(template._symbol, values)
if not get_symbols(result):
return template._forward(result)
return TransSymbol(result, template._forward, template._reverse)
try:
return template.__substitute__(values)
except AttributeError:
# Duck typing here, failure is normal.
# TODO: duck type in place of dict and list checks, too
pass
except KeyError:
# Hit for any symbols we're not substituting, failure normal
pass
return template
def format_simple(template, matches):
if type(matches) == list:
return [format_simple_single(template, m) for m in matches]
return format_simple_single(template, matches)