forked from HPAC/matchpy
/
test_utils.py
340 lines (294 loc) · 12.8 KB
/
test_utils.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
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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
# -*- coding: utf-8 -*-
import itertools
import os
from hypothesis import assume, example, given
import hypothesis.strategies as st
import pytest
from multiset import Multiset
from matchpy.utils import (
VariableWithCount, base_solution_linear, cached_property, commutative_sequence_variable_partition_iter,
extended_euclid, fixed_integer_vector_iter, get_short_lambda_source, weak_composition_iter, slot_cached_property,
solve_linear_diop
)
def is_unique_list(l):
for i, v1 in enumerate(l):
for v2 in l[:i]:
if v1 == v2:
return False
return True
class TestFixedIntegerVectorIterator:
@given(st.lists(st.integers(min_value=0, max_value=10), max_size=5), st.integers(50))
def test_correctness(self, vector, length):
vector = tuple(vector)
for result in fixed_integer_vector_iter(vector, length):
assert sum(result) == length, '{}, {}, {}'.format(vector, length, result)
@given(st.integers(min_value=1, max_value=1000), st.integers(min_value=1, max_value=1000))
def test_extended_euclid(a, b):
x, y, d = extended_euclid(a, b)
assert a % d == 0
assert b % d == 0
assert a * x + b * y == d
class TestBaseSolutionLinear:
@given(
st.integers(min_value=1, max_value=1000),
st.integers(min_value=1, max_value=1000),
st.integers(min_value=0, max_value=1000),
)
def test_correctness(self, a, b, c):
for x, y in base_solution_linear(a, b, c):
assert x >= 0
assert y >= 0
assert a * x + b * y == c, "Invalid solution {!r},{!r}".format(x, y)
@given(
st.integers(min_value=1, max_value=1000),
st.integers(min_value=1, max_value=1000),
st.integers(min_value=0, max_value=1000),
)
def test_completeness(self, a, b, c):
solutions = set(base_solution_linear(a, b, c))
for x in range(c + 1):
for y in range(c - a * x):
if a * x + b * y == c:
assert (x, y) in solutions, "Missing solution {!r},{!r}".format(x, y)
@given(
st.integers(min_value=1, max_value=1000),
st.integers(min_value=1, max_value=1000),
st.integers(min_value=0, max_value=1000),
)
def test_uniqueness(self, a, b, c):
solutions = list(base_solution_linear(a, b, c))
assert is_unique_list(solutions), "Duplicate solution found"
@pytest.mark.parametrize(
' a, b, c',
[
(0, 1, 1),
(-1, 1, 1),
(1, 0, 1),
(1, -1, 1),
(1, 1, -1),
]
) # yapf: disable
def test_error(self, a, b, c):
with pytest.raises(ValueError):
next(base_solution_linear(a, b, c))
class TestIntegerPartitionVectorIter:
@pytest.mark.parametrize('n', range(0, 11))
@pytest.mark.parametrize('m', range(0, 4))
def test_correctness(self, n, m):
for part in weak_composition_iter(n, m):
assert all(p >= 0 for p in part)
assert sum(part) == n
assert len(part) == m
@pytest.mark.parametrize('n', range(0, 11))
@pytest.mark.parametrize('m', range(0, 4))
def test_completeness_and_uniqueness(self, n, m):
solutions = set(weak_composition_iter(n, m))
if m == 0 and n > 0:
expected_count = 0
else:
# the total number of distinct partitions is given by (n+m-1)!/((m-1)!*n!)
expected_count = 1
for i in range(1, m):
expected_count *= n + m - i
for i in range(1, m):
expected_count /= i
assert len(solutions) == expected_count
assert len(set(solutions)) == expected_count
def test_error(self):
with pytest.raises(ValueError):
next(weak_composition_iter(-1, 1))
with pytest.raises(ValueError):
next(weak_composition_iter(1, -1))
class TestSolveLinearDiop:
@staticmethod
def _limit_possible_solution_count(coeffs, c):
total_solutions_approx = 1
for coeff in coeffs:
if c % coeff == 0:
total_solutions_approx *= c / coeff
assume(total_solutions_approx <= 100)
@given(st.lists(st.integers(min_value=1, max_value=100), max_size=5), st.integers(min_value=0, max_value=100))
@example([1, 2, 2], 4)
def test_correctness(self, coeffs, c):
self._limit_possible_solution_count(coeffs, c)
for solution in solve_linear_diop(c, *coeffs):
assert len(solution) == len(coeffs), "Solution size differs from coefficient count"
result = sum(c * x for c, x in zip(coeffs, solution))
for x in solution:
assert x >= 0
assert result == c, "Invalid solution {!r}".format(solution)
@given(st.lists(st.integers(min_value=1, max_value=100), max_size=5), st.integers(min_value=0, max_value=100))
@example([1, 2, 2], 4)
def test_completeness(self, coeffs, c):
self._limit_possible_solution_count(coeffs, c)
solutions = set(solve_linear_diop(c, *coeffs))
values = [range(c // x) for x in coeffs]
for solution2 in itertools.product(*values):
result = sum(c * x for c, x in zip(coeffs, solution2))
if result == c:
assert solution2 in solutions, "Missing solution {!r}".format(solution2)
@given(st.lists(st.integers(min_value=1, max_value=100), max_size=5), st.integers(min_value=0, max_value=100))
@example([1, 2, 2], 4)
def test_uniqueness(self, coeffs, c):
self._limit_possible_solution_count(coeffs, c)
solutions = list(solve_linear_diop(c, *coeffs))
assert is_unique_list(solutions), "Duplicate solution found"
@st.composite
def sequence_vars(draw):
num_vars = draw(st.integers(min_value=1, max_value=4))
variables = []
for i in range(num_vars):
name = 'var{:d}'.format(i)
count = draw(st.integers(min_value=1, max_value=4))
minimum = draw(st.integers(min_value=0, max_value=2))
variables.append(VariableWithCount(name, count, minimum))
return variables
class TestCommutativeSequenceVariablePartitionIter:
@given(sequence_vars(), st.lists(st.integers(1, 4), min_size=1, max_size=10))
def test_correctness_randomized(self, variables, values):
values = Multiset(values)
for subst in commutative_sequence_variable_partition_iter(values, variables):
assert len(variables) == len(subst)
result_union = Multiset()
for var in variables:
assert len(subst[var.name]) >= var.minimum
result_union.update(subst[var.name] * var.count)
assert result_union == values
@pytest.mark.parametrize(
' variables, values, expected_iter_count',
# Variables have the form (count, minimum length)
[
([], 'a', 0),
([], '', 1),
([(1, 0)], '', 1),
([(1, 0)], 'a', 1),
([(1, 1)], '', 0),
([(1, 1)], 'a', 1),
([(1, 2)], 'a', 0),
([(2, 0)], '', 1),
([(2, 0)], 'a', 0),
([(2, 1)], '', 0),
([(2, 1)], 'a', 0),
([(2, 2)], 'a', 0),
([(2, 0)], 'ab', 0),
([(2, 1)], 'ab', 0),
([(2, 2)], 'ab', 0),
([(2, 0)], 'aa', 1),
([(2, 1)], 'aa', 1),
([(2, 2)], 'aa', 0),
([(2, 0)], 'aaa', 0),
([(2, 1)], 'aaa', 0),
([(2, 2)], 'aaa', 0),
([(2, 0)], 'aabb', 1),
([(2, 1)], 'aabb', 1),
([(2, 2)], 'aabb', 1),
([(1, 0), (1, 0)], '', 1),
([(1, 0), (1, 0)], 'a', 2),
([(1, 1), (1, 0)], '', 0),
([(1, 1), (1, 0)], 'a', 1),
([(1, 0), (1, 0)], 'aa', 3),
([(1, 1), (1, 0)], 'aa', 2),
([(1, 0), (1, 0)], 'ab', 4),
([(1, 1), (1, 0)], 'ab', 3),
([(1, 0), (1, 0)], 'aaa', 4),
([(1, 1), (1, 0)], 'aaa', 3),
([(1, 0), (1, 0)], 'aab', 6),
([(1, 1), (1, 0)], 'aab', 5),
([(1, 0), (1, 0)], 'a', 2),
([(1, 1), (1, 0)], 'a', 1),
([(2, 0), (1, 0)], '', 1),
([(2, 0), (1, 0)], 'aa', 2),
([(2, 1), (1, 0)], '', 0),
([(2, 1), (1, 0)], 'aa', 1),
([(2, 0), (1, 0)], 'ab', 1),
([(2, 1), (1, 0)], 'ab', 0),
([(2, 0), (1, 0)], 'aaa', 2),
([(2, 1), (1, 0)], 'aaa', 1),
([(2, 0), (1, 0)], 'aab', 2),
([(2, 1), (1, 0)], 'aab', 1),
]
) # yapf: disable
def test_correctness(self, variables, values, expected_iter_count):
values = Multiset(values)
variables = [VariableWithCount('var{:d}'.format(i), c, m) for i, (c, m) in enumerate(variables)]
count = 0
for subst in commutative_sequence_variable_partition_iter(values, variables):
assert len(variables) == len(subst), "Wrong number of variables in the substitution"
result_union = Multiset()
for var in variables:
assert len(subst[var.name]) >= var.minimum, "Variable did not get its minimum number of expressions"
result_union.update(subst[var.name] * var.count)
assert result_union == values, "Substitution is not a partition of the values"
count += 1
assert count == expected_iter_count, "Invalid number of substitution in the iterable"
# yapf: disable
# =========================================================================
# DON'T CHANGE THE FORMATTING OF THESE LINES, IT IS IMPORTANT FOR THE TESTS
lambda_example = lambda a: a > 0, 0
def not_a_lambda(): pass
lambda_multiline_example = [
lambda x, y: x == y
]
# =========================================================================
# yapf: enable
@pytest.mark.parametrize(
' lambda_func, expected_source',
[
((lambda x: x == 1), 'x == 1'),
(lambda x: x == 1, 'x == 1'),
(lambda_example[0], 'a > 0'),
(lambda_multiline_example[0], 'x == y'),
(lambda x: x[0], 'x[0]'),
(lambda x: x == (0, 1), 'x == (0, 1)'),
# FORMATTING IS IMPORTANT HERE TOO
(lambda x: x > 1 and \
x < 5, 'x > 1 and \\{}x < 5'.format(os.linesep)),
([lambda x: x == 42, 5][0], 'x == 42'),
(not_a_lambda, None),
(5, None),
]
) # yapf: disable
def test_get_short_lambda_source(lambda_func, expected_source):
source = get_short_lambda_source(lambda_func)
assert source == expected_source
def test_cached_property():
class A:
call_count = 0
@cached_property
def example(self):
"""Docstring Test"""
A.call_count += 1
return 42
a = A()
b = A()
assert A.call_count == 0
assert a.example == 42
assert A.call_count == 1
assert a.example == 42
assert A.call_count == 1
assert b.example == 42
assert A.call_count == 2
assert b.example == 42
assert A.call_count == 2
assert A.example.__doc__ == "Docstring Test"
def test_slot_cached_property():
class A:
__slots__ = ('cache', )
call_count = 0
@slot_cached_property('cache')
def example(self):
"""Docstring Test"""
A.call_count += 1
return 42
a = A()
b = A()
assert A.call_count == 0
assert a.example == 42
assert A.call_count == 1
assert a.example == 42
assert A.call_count == 1
assert b.example == 42
assert A.call_count == 2
assert b.example == 42
assert A.call_count == 2
assert A.example.__doc__ == "Docstring Test"