Coverage for tests\test_derivepassphrase_sequin.py: 99.123%
196 statements
« prev ^ index » next coverage.py v7.9.2, created at 2025-07-23 12:17 +0200
1# SPDX-FileCopyrightText: 2025 Marco Ricci <software@the13thletter.info>
2#
3# SPDX-License-Identifier: Zlib
5"""Test sequin.Sequin."""
7from __future__ import annotations
9import collections
10import contextlib
11import functools
12import math
13import operator
14import types
15from typing import TYPE_CHECKING, NamedTuple
17import hypothesis
18import pytest
19from hypothesis import strategies
21from derivepassphrase import sequin
23if TYPE_CHECKING:
24 from collections.abc import Sequence
27def bits(num: int, /, byte_width: int | None = None) -> list[int]:
28 """Return the list of bits of an integer, in big endian order.
30 Args:
31 num:
32 The number whose bits are to be returned.
33 byte_width:
34 Pad the returned list of bits to the given byte width if given,
35 else its natural byte width.
37 """
38 if num < 0: # pragma: no cover 1ceb
39 err_msg = 'Negative numbers are unsupported'
40 raise NotImplementedError(err_msg)
41 if byte_width is None: 1ceb
42 byte_width = math.ceil(math.log2(num) / 8) if num else 1 1c
43 seq: list[int] = [] 1ceb
44 while num: 1ceb
45 seq.append(num % 2) 1ceb
46 num >>= 1 1ceb
47 seq.reverse() 1ceb
48 missing_bit_count = 8 * byte_width - len(seq) 1ceb
49 seq[:0] = [0] * missing_bit_count 1ceb
50 return seq 1ceb
53def bitseq(string: str) -> list[int]:
54 """Convert a 0/1-string into a list of bits."""
55 return [int(char, 2) for char in string] 1aehg
58class Parametrize(types.SimpleNamespace):
59 BIG_ENDIAN_NUMBER_EXCEPTIONS = pytest.mark.parametrize(
60 ['exc_type', 'exc_pattern', 'sequence', 'base'],
61 [
62 (ValueError, 'invalid base 3 digit:', [-1], 3),
63 (ValueError, 'invalid base:', [0], 1),
64 (TypeError, 'not an integer:', [0.0, 1.0, 0.0, 1.0], 2),
65 ],
66 )
67 INVALID_SEQUIN_INPUTS = pytest.mark.parametrize(
68 ['sequence', 'is_bitstring', 'exc_type', 'exc_pattern'],
69 [
70 (
71 [0, 1, 2, 3, 4, 5, 6, 7],
72 True,
73 ValueError,
74 'sequence item out of range',
75 ),
76 ('こんにちは。', False, ValueError, 'sequence item out of range'),
77 ],
78 )
81class TestStaticFunctionality:
82 """Test the static functionality in the `sequin` module."""
84 @hypothesis.given(
85 num=strategies.integers(min_value=0, max_value=0xFFFFFFFFFFFFFFFF),
86 )
87 def test_100_bits(self, num: int) -> None:
88 """Extract the bits from a number in big-endian format."""
89 seq1 = bits(num) 1c
90 n = len(seq1) 1c
91 seq2 = bits(num, byte_width=8) 1c
92 m = len(seq2) 1c
93 assert m == 64 1c
94 assert seq2[-n:] == seq1 1c
95 assert seq2[: m - n] == [0] * (m - n) 1c
96 text1 = ''.join(str(bit) for bit in seq1) 1c
97 text2 = ''.join(str(bit) for bit in seq2) 1c
98 assert text1.lstrip('0') == (f'{num:b}' if num else '') 1c
99 assert text2 == f'{num:064b}' 1c
101 @hypothesis.given(
102 num=strategies.integers(min_value=0, max_value=0xFFFFFFFFFFFFFFFF),
103 )
104 def test_101_bits(self, num: int) -> None:
105 """Extract the bits from a number in big-endian format."""
106 text1 = f'{num:064b}' 1e
107 seq1 = bitseq(text1) 1e
108 seq2 = bits(num, byte_width=8) 1e
109 assert seq1 == seq2 1e
110 text2 = ''.join(str(bit) for bit in seq1) 1e
111 assert int(text2, 2) == num 1e
113 class BigEndianNumberTest(NamedTuple):
114 """Test data for
115 [`TestStaticFunctionality.test_200_big_endian_number`][].
117 Attributes:
118 sequence: A sequence of integers.
119 base: The numeric base.
120 expected: The expected result.
122 """
124 sequence: list[int]
125 """"""
126 base: int
127 """"""
128 expected: int
129 """"""
131 @strategies.composite
132 @staticmethod
133 def strategy(
134 draw: strategies.DrawFn,
135 *,
136 base: int | None = None,
137 max_size: int | None = None,
138 ) -> TestStaticFunctionality.BigEndianNumberTest:
139 """Return a sample BigEndianNumberTest.
141 Args:
142 draw:
143 The `draw` function, as provided for by hypothesis.
144 base:
145 The numeric base, an integer between 2 and 65536 (inclusive).
146 max_size:
147 The maximum size of the sequence, up to 128.
149 Raises:
150 AssertionError:
151 `base` or `max_size` are invalid.
153 """
154 if base is None: # pragma: no cover 1f
155 base = 256 1f
156 assert isinstance(base, int) 1f
157 assert base in range(2, 65537) 1f
158 if max_size is None: # pragma: no cover 1f
159 max_size = 128 1f
160 assert isinstance(max_size, int) 1f
161 assert max_size in range(129) 1f
162 sequence = draw( 1f
163 strategies.lists(
164 strategies.integers(min_value=0, max_value=(base - 1)),
165 max_size=max_size,
166 ),
167 )
168 value = functools.reduce(lambda x, y: x * base + y, sequence, 0) 1f
169 return TestStaticFunctionality.BigEndianNumberTest( 1f
170 sequence, base, value
171 )
173 @hypothesis.given(test_case=BigEndianNumberTest.strategy())
174 @hypothesis.example( 1af
175 BigEndianNumberTest([1, 2, 3, 4, 5, 6], 10, 123456)
176 ).via('manual decimal example')
177 @hypothesis.example(
178 BigEndianNumberTest([1, 2, 3, 4, 5, 6], 100, 10203040506)
179 ).via('manual decimal example in different base')
180 @hypothesis.example(BigEndianNumberTest([0, 0, 1, 4, 9, 7], 10, 1497)).via(
181 'manual example with leading zeroes'
182 )
183 @hypothesis.example(
184 BigEndianNumberTest([1, 0, 0, 1, 0, 0, 0, 0], 2, 144)
185 ).via('manual binary example')
186 @hypothesis.example(BigEndianNumberTest([1, 7, 5, 5], 8, 0o1755)).via(
187 'manual octal example'
188 )
189 def test_200_big_endian_number(
190 self, test_case: BigEndianNumberTest
191 ) -> None:
192 """Conversion to big endian numbers in any base works.
194 See [`sequin.Sequin.generate`][] for where this is used.
196 """
197 sequence, base, expected = test_case 1f
198 assert ( 1f
199 sequin.Sequin._big_endian_number(sequence, base=base)
200 ) == expected
202 @Parametrize.BIG_ENDIAN_NUMBER_EXCEPTIONS
203 def test_300_big_endian_number_exceptions(
204 self,
205 exc_type: type[Exception],
206 exc_pattern: str,
207 sequence: list[int],
208 base: int,
209 ) -> None:
210 """Nonsensical conversion of numbers in a given base raises.
212 See [`sequin.Sequin.generate`][] for where this is used.
214 """
215 with pytest.raises(exc_type, match=exc_pattern): 1k
216 sequin.Sequin._big_endian_number(sequence, base=base) 1k
219class TestSequin:
220 """Test the `Sequin` class."""
222 class ConstructorTestCase(NamedTuple):
223 """A test case for the constructor.
225 Attributes:
226 sequence:
227 A sequence of ints, bits, or Latin1 characters.
228 is_bitstring:
229 True if and only if `sequence` denotes bits.
230 expected:
231 The expected bit sequence of the internal entropy pool.
233 """
235 sequence: Sequence[int] | str
236 """"""
237 is_bitstring: bool
238 """"""
239 expected: Sequence[int]
241 @strategies.composite
242 @staticmethod
243 def strategy(
244 draw: strategies.DrawFn,
245 *,
246 max_entropy: int | None = None,
247 ) -> TestSequin.ConstructorTestCase:
248 """Return a constructor test case.
250 Args:
251 max_entropy:
252 The maximum entropy, in bits. Must be between 0 and
253 256, inclusive.
255 Raises:
256 AssertionError:
257 `max_entropy` is invalid.
259 """
260 if max_entropy is None: # pragma: no branch 1b
261 max_entropy = 256 1b
262 assert max_entropy in range(257) 1b
263 is_bytecount = max_entropy % 8 == 0 1b
264 is_bitstring = ( 1b
265 draw(strategies.randoms()).choice([False, True])
266 if is_bytecount
267 else True
268 )
269 sequence: Sequence[int] | str
270 expected: Sequence[int]
271 if is_bitstring: 1b
272 sequence = draw( 1b
273 strategies.lists(
274 strategies.integers(min_value=0, max_value=1),
275 max_size=max_entropy,
276 )
277 )
278 expected = sequence 1b
279 else:
280 bytecount = max_entropy // 8 1b
281 raw_sequence = draw(strategies.binary(max_size=bytecount)) 1b
282 sequence_format = draw(strategies.randoms()).choice([ 1b
283 'bytes',
284 'ints',
285 'text',
286 ])
287 if sequence_format == 'bytes': 1b
288 sequence = raw_sequence 1b
289 elif sequence_format == 'ints': 289 ↛ 292line 289 didn't jump to line 292 because the condition on line 289 was always true1b
290 sequence = list(raw_sequence) 1b
291 else:
292 sequence = raw_sequence.decode('latin1')
293 bytestring = ( 1b
294 sequence.encode('latin1')
295 if isinstance(sequence, str)
296 else bytes(sequence)
297 )
298 expected = [] 1b
299 for byte in bytestring: 1b
300 expected.extend(bits(byte, byte_width=1)) 1b
301 return TestSequin.ConstructorTestCase( 1b
302 sequence, is_bitstring, expected
303 )
305 @hypothesis.given(test_case=ConstructorTestCase.strategy())
306 @hypothesis.example( 1ab
307 ConstructorTestCase([1, 0, 0, 1, 0, 1], True, [1, 0, 0, 1, 0, 1])
308 ).via('manual example bitstring')
309 @hypothesis.example(
310 ConstructorTestCase(
311 [1, 0, 0, 1, 0, 1],
312 False,
313 bitseq('000000010000000000000000000000010000000000000001'),
314 )
315 ).via('manual example bitstring as byte string')
316 @hypothesis.example(
317 ConstructorTestCase(b'OK', False, bitseq('0100111101001011'))
318 ).via('manual example true byte string')
319 @hypothesis.example(
320 ConstructorTestCase('OK', False, bitseq('0100111101001011'))
321 ).via('manual example latin1 text')
322 def test_200_constructor(
323 self,
324 test_case: ConstructorTestCase,
325 ) -> None:
326 """The constructor handles both bit and integer sequences."""
327 sequence, is_bitstring, expected = test_case 1b
328 seq = sequin.Sequin(sequence, is_bitstring=is_bitstring) 1b
329 assert seq.bases == {2: collections.deque(expected)} 1b
331 class GenerationSequence(NamedTuple):
332 """A sequence of generation results.
334 Attributes:
335 bit_sequence:
336 The input bit sequence.
337 steps:
338 A sequence of generation steps. Each step details
339 a requested number base, and the respective result (a
340 number, or [`sequin.SequinExhaustedError`][]).
342 """
344 bit_sequence: Sequence[int]
345 """"""
346 steps: Sequence[tuple[int, int | type[sequin.SequinExhaustedError]]]
347 """"""
349 @strategies.composite
350 @staticmethod
351 def strategy(draw: strategies.DrawFn) -> TestSequin.GenerationSequence:
352 """Return a generation sequence."""
353 # Signal that there is only one value.
354 draw(strategies.just(None)) 1hg
355 return TestSequin.GenerationSequence( 1hg
356 bitseq('110101011111001'),
357 [
358 (1, 0),
359 (5, 3),
360 (5, 3),
361 (5, 1),
362 (5, sequin.SequinExhaustedError),
363 (1, sequin.SequinExhaustedError),
364 ],
365 )
367 @hypothesis.example(
368 GenerationSequence(
369 bitseq('110101011111001'),
370 [
371 (1, 0),
372 (5, 3),
373 (5, 3),
374 (5, 1),
375 (5, sequin.SequinExhaustedError),
376 (1, sequin.SequinExhaustedError),
377 ],
378 )
379 ).via('manual, pre-hypothesis parametrization value')
380 @hypothesis.given(sequence=GenerationSequence.strategy())
381 def test_201_generating(self, sequence: GenerationSequence) -> None:
382 """The sequin generates deterministic sequences."""
383 seq = sequin.Sequin(sequence.bit_sequence, is_bitstring=True) 1h
384 for i, (num, result) in enumerate(sequence.steps, start=1): 1h
385 if isinstance(result, int): 1h
386 assert seq.generate(num) == result, ( 1h
387 f'Failed to generate {result:d} in step {i}'
388 )
389 else:
390 # Can't use pytest.raises here, because the assertion error
391 # message is not customizable and we would lose information
392 # about which step we're executing.
393 with contextlib.suppress(sequin.SequinExhaustedError): 1h
394 result2 = seq.generate(num) 1h
395 pytest.fail( 1h
396 f'Expected to be exhausted in step {i}, '
397 f'but generated {result2:d} instead'
398 )
400 def test_201a_generating_errors(self) -> None:
401 """The sequin errors deterministically when generating sequences."""
402 seq = sequin.Sequin( 1j
403 [1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1], is_bitstring=True
404 )
405 with pytest.raises(ValueError, match='invalid target range'): 1j
406 seq.generate(0) 1j
408 @hypothesis.example(
409 GenerationSequence(
410 bitseq('110101011111001'),
411 [
412 (1, 0),
413 (5, 3),
414 (5, 3),
415 (5, 1),
416 (5, sequin.SequinExhaustedError),
417 (1, sequin.SequinExhaustedError),
418 ],
419 )
420 ).via('manual, pre-hypothesis parametrization value')
421 @hypothesis.given(sequence=GenerationSequence.strategy())
422 def test_210_internal_generating(
423 self, sequence: GenerationSequence
424 ) -> None:
425 """The sequin internals generate deterministic sequences."""
426 seq = sequin.Sequin(sequence.bit_sequence, is_bitstring=True) 1g
427 for i, (num, result) in enumerate(sequence.steps, start=1): 1g
428 if num == 1: 1g
429 assert seq._generate_inner(num) == 0, ( 1g
430 f'Failed to generate {result:d} in step {i}'
431 )
432 elif isinstance(result, int): 1g
433 assert seq._generate_inner(num) == result, ( 1g
434 f'Failed to generate {result:d} in step {i}'
435 )
436 else:
437 result2 = seq._generate_inner(num) 1g
438 assert result2 == num, ( 1g
439 f'Expected to be exhausted in step {i}, '
440 f'but generated {result2:d} instead'
441 )
443 def test_210a_internal_generating_errors(self) -> None:
444 """The sequin generation internals error deterministically."""
445 seq = sequin.Sequin( 1i
446 [1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1], is_bitstring=True
447 )
448 with pytest.raises(ValueError, match='invalid target range'): 1i
449 seq._generate_inner(0) 1i
450 with pytest.raises(ValueError, match='invalid base:'): 1i
451 seq._generate_inner(16, base=1) 1i
453 class ShiftSequence(NamedTuple):
454 """A sequence of bit sequence shift operations.
456 Attributes:
457 bit_sequence:
458 The input bit sequence.
459 steps:
460 A sequence of shift steps. Each step details
461 a requested shift size, the respective result, and the
462 bit sequence status afterward.
464 """
466 bit_sequence: Sequence[int]
467 """"""
468 steps: Sequence[tuple[int, Sequence[int], Sequence[int]]]
469 """"""
471 @strategies.composite
472 @staticmethod
473 def strategy(draw: strategies.DrawFn) -> TestSequin.ShiftSequence:
474 """Return a generation sequence."""
475 no_op_counts_strategy = strategies.lists( 1d
476 strategies.integers(min_value=0, max_value=0),
477 min_size=3,
478 max_size=3,
479 )
480 true_counts_strategy = strategies.lists( 1d
481 strategies.integers(min_value=1, max_value=5),
482 min_size=3,
483 max_size=10,
484 ).map(sorted)
485 bits_strategy = strategies.integers(min_value=0, max_value=1) 1d
486 counts = draw( 1d
487 strategies.builds(
488 operator.add,
489 no_op_counts_strategy,
490 true_counts_strategy,
491 ).flatmap(strategies.permutations)
492 )
493 bit_sequence: list[int] = [] 1d
494 steps: list[tuple[int, Sequence[int], list[int]]] = [] 1d
495 for i, count in enumerate(counts): 1d
496 shift_result = draw( 1d
497 strategies.lists(
498 bits_strategy, min_size=count, max_size=count
499 )
500 )
501 for step in steps[:i]: 1d
502 step[2].extend(shift_result) 1d
503 bit_sequence.extend(shift_result) 1d
504 steps.append((count, shift_result, [])) 1d
505 return TestSequin.ShiftSequence(bit_sequence, steps) 1d
507 @hypothesis.given(sequence=ShiftSequence.strategy())
508 @hypothesis.example( 1ad
509 ShiftSequence(
510 bitseq('1010010001'),
511 [
512 (3, bitseq('101'), bitseq('0010001')),
513 (3, bitseq('001'), bitseq('0001')),
514 (5, bitseq(''), bitseq('0001')),
515 (4, bitseq('0001'), bitseq('')),
516 ],
517 )
518 )
519 def test_211_shifting(self, sequence: ShiftSequence) -> None:
520 """The sequin manages the pool of remaining entropy for each base.
522 Specifically, the sequin implements all-or-nothing fixed-length
523 draws from the entropy pool.
525 """
526 seq = sequin.Sequin(sequence.bit_sequence, is_bitstring=True) 1d
527 assert seq.bases == {2: collections.deque(sequence.bit_sequence)} 1d
528 for i, (count, result, remaining) in enumerate( 1d
529 sequence.steps, start=1
530 ):
531 actual_result = seq._all_or_nothing_shift(count) 1d
532 assert actual_result == tuple(result), ( 1d
533 f'At step {i}, the shifting result differs'
534 )
535 if remaining: 1d
536 assert seq.bases[2] == collections.deque(remaining), ( 1d
537 f'After step {i}, the remaining bit sequence differs'
538 )
539 else:
540 assert 2 not in seq.bases, ( 1d
541 f'After step {i}, the bit sequence is not exhausted yet'
542 )
544 @Parametrize.INVALID_SEQUIN_INPUTS
545 def test_300_constructor_exceptions(
546 self,
547 sequence: list[int] | str,
548 is_bitstring: bool,
549 exc_type: type[Exception],
550 exc_pattern: str,
551 ) -> None:
552 """The sequin raises on invalid bit and integer sequences."""
553 with pytest.raises(exc_type, match=exc_pattern): 1l
554 sequin.Sequin(sequence, is_bitstring=is_bitstring) 1l