Metadata-Version: 2.5
Name: bitpattern
Version: 0.2.0
Summary: Very large sets of floats, IP addresses and other structured data, backed by binary decision diagrams
Project-URL: Source, https://github.com/bethebunny/bitpattern
Project-URL: Issues, https://github.com/bethebunny/bitpattern/issues
Author: Stef Lindall
License-Expression: MIT
License-File: LICENSE
Keywords: bdd,binary decision diagram,bitmask,cidr,hypothesis,ieee754,set
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Software Development :: Testing
Classifier: Typing :: Typed
Requires-Python: >=3.11
Provides-Extra: hypothesis
Requires-Dist: hypothesis>=6; extra == 'hypothesis'
Description-Content-Type: text/markdown

# bitpattern

> [!NOTE]
> ```bash
> pip install bitpattern
> pip install 'bitpattern[hypothesis]'  # with the hypothesis strategies
> ```

bitpattern provides `BDDSet`, a set type for values that can be encoded as fixed-width
integers: for instance, IEEE floats and twos-complement integers, unicode codepoints,
network addresses, UUIDs, dates and times, enums and tuples of any of these. BDDSets can
efficiently represent sets far too large to list and still support the usual set
operations, counting, uniform sampling and even indexing.

Consider for example 64 bit floats. How many finite normal floats are there? Can we
sample them directly? These sets are huge and noncontiguous, so you can't express them
in traditional data structures.

```python
>>> from bitpattern.codecs import float64
>>> normal = float64.finite - float64.subnormal - float64.zeros
>>> normal
BDDSet(float64, [2.2250738585072014e-308, 2.225073858507202e-308, 2.2250738585072024e-308, 2.225073858507203e-308, ..., -1.7976931348623155e+308, -1.7976931348623157e+308], size=18428729675200069632)
>>> 0.25 in normal
True
>>> list(normal[:3])
[2.2250738585072014e-308, 2.225073858507202e-308, 2.2250738585072024e-308]
>>> normal.choice()
2.3171912436506225e+167
>>> float64.range(1.0, 2.0).size
4503599627370496

```

`float64` is the [codec](#codecs) that tells bitpattern how to encode float64 values
as integers.

## Tour

Here's a quick tour, with sampling seeded so it's repeatable:

```python
>>> import random, uuid
>>> from datetime import UTC, date, datetime
>>> from enum import Flag
>>> from bitpattern.codecs import (
...     Flags, char, dates, datetimes, float8_e4m3fn, ipv4, project, uint16, uuid128,
... )
>>> rng = random.Random(0)

>>> # fp8
>>> float8_e4m3fn.finite.size
254
>>> float8_e4m3fn.positive[-1]
448.0
>>> float8_e4m3fn.decode(float8_e4m3fn.encode(0.3))
0.3125
>>> list(float8_e4m3fn.range(1.0, 2.0))
[1.0, 1.125, 1.25, 1.375, 1.5, 1.625, 1.75, 1.875]

>>> # Unicode characters
>>> "É" in char.category("Lu")
True
>>> "".join(char.category("Sm") & char.range("\0", "\x80"))
'+<=>|~'
>>> char.range("a", "{") == char.category("Ll") & char.range("\0", "\x80")
True

>>> # `a * b` is the set of pairs, ie. the cartesian product
>>> networks = ipv4.cidr("10.0.0.0/8") | ipv4.cidr("192.168.0.0/16")
>>> private = networks * uint16.range(1024, 65536)
>>> private.size
1086559617024
>>> ("10.1.2.3", 8080) in private
True
>>> private.choice(rng=rng)
(IPv4Address('10.100.105.211'), 22477)
>>> project(private, 1) == uint16.range(1024, 65536)
True

>>> # UUIDs
>>> uuid128.version(4).size == 2**122
True
>>> uuid.uuid4() in uuid128.version(4)
True
>>> uuid128.version(7).choice(rng=rng)
UUID('14ba5e5a-eaa5-7157-a3e7-0682c2094cac')

>>> # Dates and datetimes
>>> dates.range(date(2024, 1, 1), date(2025, 1, 1)).size
366
>>> new_year = datetime(2024, 1, 1, tzinfo=UTC)
>>> datetimes.range(new_year, datetime(2024, 1, 2, tzinfo=UTC)).size
86400000000

>>> # Flags
>>> class Permission(Flag):
...     READ = 4
...     WRITE = 2
...     EXECUTE = 1
>>> permissions = Flags(Permission)
>>> list(permissions.having(Permission.READ))
[<Permission.READ: 4>, <Permission.READ|EXECUTE: 5>, <Permission.READ|WRITE: 6>, <Permission.READ|WRITE|EXECUTE: 7>]
>>> permissions.pattern("?1?") == permissions.having(Permission.WRITE)
True

```

## Very large sets

bitpattern uses a data structure called a Binary Decision Diagram to encode
extremely large sets. Whereas set operations are typically described in terms
of the size of the set, bitpattern sets support most operations in O(#bits) of
the _largest member_ of the set. #bits is called the `width` of the set.

Here's how bitpattern's sets compare to other ways of storing a set. `n` and `m` are
set sizes, `w` is the width (number of bits of the largest member), and `|a|` is the
number of nodes in `a`'s diagram. `|a|` is at most `n * w` and usually much smaller. A
set written as a single pattern has `|a| <= w`, since only its fixed bits need nodes.
For most use cases `w` is a constant and may be read as `O(1)`.

| | sorted `list` | `set` | balanced tree | `BDDSet` |
| --- | --- | --- | --- | --- |
| `x in a` | O(log n) | O(1) | O(log n) | O(w) |
| `a[i]` | O(1) | n/a | O(log n) | O(w) |
| `len(a)` | O(1) | O(1) | O(1) | O(1) |
| `a \| b`, `a & b`, `a - b` | O(n + m) | O(n + m) | O(n + m) | O(\|a\| · \|b\|) |
| `~a` | O(2<sup>w</sup>) | O(2<sup>w</sup>) | O(2<sup>w</sup>) | O(\|a\|) |
| slice `a[i:j]` | O(j - i) | n/a | O(log n + j - i) | O(w) |
| `a == b` | O(n) | O(n) | O(n) | O(1) |
| `hash(a)` | O(n) | O(n) | O(n) | O(w) |
| random member | O(1) | O(n) | O(log n) | O(w) |
| memory | O(n) | O(n) | O(n) | O(\|a\|) |

`a == b` is O(1) between sets of the same codec. Between `IntSet`s of different widths
it's O(w).

> [!WARNING]
> Python isn't really designed for data structures larger than memory.
> In particular many operations will fail if `__len__` returns a number >= 2**63.
> When working with very large sets:
>
> - Use `myset.size` instead of `len(myset)`
> - Use `myset.choice()` instead of `random.choice(myset)` or `random.sample(myset, k)`
> - Use `myset[0]` and `myset[-1]` instead of `min(myset)` and `max(myset)`, which
>   look at every member
> - Use `bitpattern.strategies` instead of hypothesis's `sampled_from(myset)`

## Hypothesis

bitpattern's sets are particularly useful with [hypothesis](https://hypothesis.works/).

Hypothesis really likes you to express and sample from the _true domain_ of your
input data. Rejection sampling (in hypothesis literally sampling from the whole
range and then calling `reject` on inputs that don't match your criteria) frequently
eliminates too much data. By default hypothesis will fail tests that reject
more than ~80% of inputs, but for instance subnormals are well under 1% of floats, so
this isn't practical.

`bitpattern.strategies` turns these sets into hypothesis strategies:

```python
from hypothesis import given

from bitpattern.codecs import float64
from bitpattern.strategies import from_set


@given(from_set(float64.finite - float64.subnormal))
def test_kernel_matches_reference(x: float): ...
```

## Patterns

The pattern syntax follows normal glob rules. Patterns are expressed as quartets of 4
bits separated by `.`, most significant to least significant, with 0 and 1 representing
a fixed bit, ? can be either, and * is shorthand for multiple ?. The leading quartet can
be shorter for widths that aren't a multiple of 4.

Patterns are sets, and work with normal set operations.

```python
>>> from bitpattern import Pattern
>>> Pattern("*1.0000")
Pattern('???1.0000')
>>> Pattern("0000") | Pattern("0001")
Pattern('000?')
>>> ~Pattern("00??")
Pattern('01??') | Pattern('1???')

```

Codecs accept patterns too and match them against the bits of their encoding. A
float64 is a sign bit, 11 exponent bits and 52 mantissa bits. Quiet NaNs have every
exponent bit and the top mantissa bit set:

```python
>>> quiet = float64.pattern("?111.1111.1111.1*.*.*.*.*.*.*.*.*.*.*.*.*")
>>> quiet <= float64.nan
True

```

## Codecs

A `Codec` encodes values of a type as fixed-width integers and decodes them back. Its
sets are `BDDSet`s. To write one, subclass `Codec` and implement `encode` and `decode`:

```python
>>> from bitpattern import Codec
>>> class Ascii(Codec[str]):
...     def encode(self, value: object) -> int:
...         if not isinstance(value, str):
...             raise TypeError(f"{value!r} isn't a string")
...         if len(value) != 1 or not value.isascii():
...             raise ValueError(f"{value!r} isn't an ASCII character")
...         return ord(value)
...
...     def decode(self, bits: int) -> str:
...         return chr(bits)
>>> ascii = Ascii(7, "ascii")
>>> ascii.set("hello")
BDDSet(ascii, ['e', 'h', 'l', 'o'])
>>> ascii.pattern("1?0.0001")  # case only changes bit 5
BDDSet(ascii, ['A', 'a'])

```

`encode` should raise `TypeError` for a value of the wrong type and `ValueError` for a
value it can't encode. `decode` may raise `IndexError` for bits that aren't a value.
If some bit patterns aren't values, override `all` with the ones that are. `~` and
`pattern` then leave the others out. If encodings sort the same as their values,
subclass `OrderedCodec` instead for `min`, `max` and `range(start, stop)`.

`bitpattern.codecs` includes:

- `float16`, `float32` and `float64` as their IEEE 754 bits, and the ML formats
  `bfloat16`, `float8_e5m2` and `float8_e4m3fn`. They have sets like `finite`, `nan`,
  `infinities`, `subnormal` and `zeros`.
- `int8` through `int128` in two's complement, and `uint8` through `uint128`.
- `char`, Unicode scalar values as one-character strings, with `category(name)` for
  general categories like `"Lu"` or `"L"`.
- `ipv4` and `ipv6`, with `cidr("10.0.0.0/8")`. `networks(addresses)` finds the fewest
  CIDR blocks that make up a set.
- `mac`, MAC addresses like `01:23:45:67:89:ab`, with `multicast`, `unicast`, `local`,
  `universal`, `broadcast` and `oui(prefix)`.
- `uuid128`, `uuid.UUID`s, with `version(n)` for RFC 9562's versions 1 to 8 and
  `rfc9562` for its variant.
- `dates` and `datetimes`. `datetimes` holds timezone-aware datetimes and decodes them
  into UTC. `DateTime(tz)` decodes into `tz` instead, and `naive_datetimes` holds naive
  datetimes.
- `Members(SomeEnum)` for an Enum's members, and `Flags(SomeFlag)` for a Flag's
  combinations, with `having(flags)` and `lacking(flags)`.

All of these but the enums and flags are ordered, with `min`, `max` and
`range(start, stop)`. A bound of `None` leaves that end unbounded.

`product(a, b, c)` is the set of tuples `itertools.product(a, b, c)` would give, and
`a * b` is `product(a, b)`. Their codec is a `Tuple`, with the first field's bits on
top. A product has about as many nodes as its sets combined. `project` gets the values
of one field.

## IntSet

`IntSet` backs BDDSets and patterns, and works on its own too. An `IntSet` is an
immutable set of non-negative integers below `2 ** width`. It's a `collections.abc.Set`
and a `Sequence` of its members in sorted order. Slicing gives back a set.

An `IntSet` is a reduced, ordered binary decision diagram, or BDD ([Bryant, 1986]).
`bitpattern.BDD` is the diagram itself.

```python
>>> from bitpattern import IntSet
>>> s = IntSet.range(3, 17)
>>> s
IntSet([3, 4, 5, 6, ..., 15, 16], size=14, width=5)
>>> s[2]
5
>>> s[2:5]
IntSet([5, 6, 7], width=5)
>>> s & IntSet([1, 2, 3, 4])
IntSet([3, 4], width=5)
>>> ~IntSet([1, 3], width=2)
IntSet([0, 2], width=2)

```

[Bryant, 1986]: https://doi.org/10.1109/TC.1986.1676819

R. E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. _IEEE
Transactions on Computers_, 35(8):677–691, 1986.
