patterns

ChunkMaskTensor

Bases: PatternTensor

Map n indices to chunks of size b.

shape is (ceil(n / b), n), and row j holds the indices of chunk j, so that the efficient row-major traversal visits each chunk and then its indices. The last chunk may be shorter.

Source code in src/finch/tensor/patterns.py

class ChunkMaskTensor(PatternTensor):
    """Map ``n`` indices to chunks of size ``b``.

    ``shape`` is ``(ceil(n / b), n)``, and row ``j`` holds the indices of chunk
    ``j``, so that the efficient row-major traversal visits each chunk and then
    its indices. The last chunk may be shorter.
    """

    def __init__(self, shape, *, b: int, dtype=None):
        self._b = operator.index(b)
        if self._b <= 0:
            raise ValueError("b must be positive")
        super().__init__(
            shape,
            dtype=dtype,
            default_dtype=np.bool_,
            fill_value=False,
            pattern_value=True,
            b=self._b,
        )
        chunks, n = map(operator.index, self.shape)
        if n < 0:
            raise ValueError("n must be nonnegative")
        if chunks != (n + self._b - 1) // self._b:
            raise ValueError("shape[0] must equal ceil(shape[1] / b)")

    def contains(self, j, i) -> bool:
        return j == i // self._b

FillTensor

Bases: OverrideTensor

A tensor that has a specific shape but contains no actual data. Used primarily for broadcasting operations where a tensor of a specific shape is needed but the values are irrelevant.

Source code in src/finch/tensor/patterns.py

class FillTensor(OverrideTensor):
    """
    A tensor that has a specific shape but contains no actual data.
    Used primarily for broadcasting operations where a tensor of a specific
    shape is needed but the values are irrelevant.
    """

    def with_fill(self, fill_value: AbstractFill) -> FillTensor:
        return FillTensor(self._shape, fill_value)

    def __init__(self, shape, fill_value):
        self._shape = shape
        self._fill = as_fill(fill_value)

    def __getitem__(self, idxs):
        return Scalar(self._fill.value, fill_value=self._fill)

    def item(self):
        if self.ndim != 0:
            raise ValueError("Cannot convert non-scalar tensor to Python scalar.")
        return self._fill.value

    def to_numpy(self):
        raise NotImplementedError(f"{type(self).__name__} does not support to_numpy.")

    def to_scipy(self):
        raise NotImplementedError(f"{type(self).__name__} does not support to_scipy.")

    @property
    def shape(self):
        return self._shape

    @property
    def fill_value(self) -> Any:
        """Default fill value."""
        return self._fill.value

    @property
    def element_type(self) -> FType:
        """Data type of the tensor's elements."""
        return self.ftype.element_type

    @property
    def shape_type(self) -> tuple[FType, ...]:
        """Shape type of the tensor."""
        return self.ftype.shape_type

    @property
    def ftype(self):
        return FillTensorFType(
            self._fill.ftype,
            self._fill.element_type,
            tuple(ftype(dim) for dim in self.shape),
        )

element_type property

Data type of the tensor's elements.

fill_value property

Default fill value.

shape_type property

Shape type of the tensor.

FillTensorFType dataclass

Bases: TensorFType

Source code in src/finch/tensor/patterns.py

@dataclass(frozen=True, eq=False)
class FillTensorFType(TensorFType):
    _fill_type: AbstractFillFType
    _element_type: FType
    _shape_type: tuple

    @property
    def fill_type(self) -> AbstractFillFType:
        return self._fill_type

    def with_fill(self, fill_type: AbstractFillFType) -> FillTensorFType:
        return replace(self, _fill_type=fill_type)

    @property
    def element_type(self) -> FType:
        return self._element_type

    @property
    def shape_type(self):
        return self._shape_type

    @property
    def level_format_properties(self) -> list[FormatProperty]:
        return [Dense(tuple(range(n + 1))) for n in range(self.ndim)] + [
            Repeated(tuple(range(n)), (n,)) for n in range(self.ndim)
        ]

    def from_numpy(self, arr):
        raise NotImplementedError

    def __eq__(self, other):
        if not isinstance(other, FillTensorFType):
            return False
        return (
            self._fill_type == other._fill_type
            and self._element_type == other._element_type
            and self._shape_type == other._shape_type
        )

    def __hash__(self):
        return hash((self._fill_type, self._element_type, self._shape_type))

    def construct(self, shape: tuple) -> FillTensor:
        return FillTensor(shape, resolve_fill(self._fill_type))

    def __call__(self, val: Any) -> FillTensor:
        """
        Convert a tensor to this fill tensor type.

        Args:
            val: A tensor to convert to this type.
        Returns:
            A FillTensor instance of this type.
        """
        raise NotImplementedError(
            f"Tensor conversion not yet implemented for {type(self).__name__}"
        )

__call__(val)

Convert a tensor to this fill tensor type.

Parameters:

Name	Type	Description	Default
val	Any	A tensor to convert to this type.	required

Returns: A FillTensor instance of this type.

Source code in src/finch/tensor/patterns.py

def __call__(self, val: Any) -> FillTensor:
    """
    Convert a tensor to this fill tensor type.

    Args:
        val: A tensor to convert to this type.
    Returns:
        A FillTensor instance of this type.
    """
    raise NotImplementedError(
        f"Tensor conversion not yet implemented for {type(self).__name__}"
    )

IndexTensor

Bases: OverrideTensor

A tensor that has a specific shape and returns the linear (flattened) index used to access it.

Source code in src/finch/tensor/patterns.py

class IndexTensor(OverrideTensor):
    """
    A tensor that has a specific shape and returns the linear (flattened) index used
    to access it.
    """

    def __init__(
        self,
        shape,
        element_type: FType | type = np.intp,
        fill_value: AbstractFill | None = None,
    ):
        self._shape = tuple(shape)
        self._element_type = ftype(element_type)
        self._fill = fill_value

    def with_fill(self, fill_value: AbstractFill) -> IndexTensor:
        return IndexTensor(self._shape, self._element_type, fill_value)

    def __getitem__(self, idxs):
        if self.ndim == 0 and idxs in ((), Ellipsis, (...,)):
            return Scalar(self.fill_value, fill_value=self.fill_value)
        if not isinstance(idxs, tuple):
            idxs = (idxs,)
        idxs = tuple(idx for idx in idxs if idx is not Ellipsis)
        if len(idxs) != self.ndim:
            raise IndexError("Incorrect number of indices for IndexTensor.")
        flat_index = 0
        for idx, dim in zip(idxs, self.shape, strict=True):
            flat_index = flat_index * dim + idx
        flat_index = self._element_type(flat_index)
        return Scalar(flat_index, fill_value=self.fill_value)

    def item(self):
        if self.ndim != 0:
            raise ValueError("Cannot convert non-scalar tensor to Python scalar.")
        return self.fill_value

    def to_numpy(self):
        raise NotImplementedError(f"{type(self).__name__} does not support to_numpy.")

    def to_scipy(self):
        raise NotImplementedError(f"{type(self).__name__} does not support to_scipy.")

    @property
    def shape(self):
        return self._shape

    @property
    def fill_value(self) -> Any:
        """Default fill value."""
        return resolve_fill(self.ftype.fill_type, self._fill).value

    @property
    def element_type(self) -> FType:
        """Data type of the tensor's elements."""
        return self.ftype.element_type

    @property
    def shape_type(self) -> tuple[FType, ...]:
        """Shape type of the tensor."""
        return self.ftype.shape_type

    @property
    def ftype(self):
        return IndexTensorFType(
            self._element_type,
            tuple(ftype(dim) for dim in self.shape),
            None if self._fill is None else self._fill.ftype,
        )

element_type property

Data type of the tensor's elements.

fill_value property

Default fill value.

shape_type property

Shape type of the tensor.

IndexTensorFType dataclass

Bases: TensorFType

Source code in src/finch/tensor/patterns.py

@dataclass(frozen=True, eq=False)
class IndexTensorFType(TensorFType):
    _element_type: FType
    _shape_type: tuple[FType, ...]
    _fill_type: AbstractFillFType

    def __init__(
        self,
        _element_type: FType | type = np.intp,
        _shape_type: tuple[FType | type, ...] = (),
        _fill_type: AbstractFillFType | None = None,
    ):
        # Frozen dataclass: fields have to be set through `object`.
        object.__setattr__(self, "_element_type", ftype(_element_type))
        object.__setattr__(
            self, "_shape_type", tuple(ftype(dim_t) for dim_t in _shape_type)
        )
        object.__setattr__(
            self,
            "_fill_type",
            StaticFillFType(self._element_type(0))
            if _fill_type is None
            else _fill_type,
        )

    @property
    def fill_type(self) -> AbstractFillFType:
        return self._fill_type

    def with_fill(self, fill_type: AbstractFillFType) -> IndexTensorFType:
        return IndexTensorFType(self._element_type, self._shape_type, fill_type)

    @property
    def element_type(self) -> FType:
        return self._element_type

    @property
    def shape_type(self):
        return self._shape_type

    @property
    def level_format_properties(self) -> list[FormatProperty]:
        return [Dense(tuple(range(n + 1))) for n in range(self.ndim)]

    def from_numpy(self, arr):
        raise NotImplementedError

    def __eq__(self, other):
        if not isinstance(other, IndexTensorFType):
            return False
        return (
            self.fill_type == other.fill_type
            and self._element_type == other._element_type
            and self._shape_type == other._shape_type
        )

    def __hash__(self):
        return hash((self.fill_type, self._element_type, self._shape_type))

    def construct(self, shape: tuple) -> IndexTensor:
        return IndexTensor(shape, self.element_type)

    def __call__(self, val: Any) -> IndexTensor:
        """
        Convert a tensor to this index tensor type.

        Args:
            val: A tensor to convert to this type.
        Returns:
            An IndexTensor instance of this type.
        """
        raise NotImplementedError(
            f"Tensor conversion not yet implemented for {type(self).__name__}"
        )

__call__(val)

Convert a tensor to this index tensor type.

Parameters:

Name	Type	Description	Default
val	Any	A tensor to convert to this type.	required

Returns: An IndexTensor instance of this type.

Source code in src/finch/tensor/patterns.py

def __call__(self, val: Any) -> IndexTensor:
    """
    Convert a tensor to this index tensor type.

    Args:
        val: A tensor to convert to this type.
    Returns:
        An IndexTensor instance of this type.
    """
    raise NotImplementedError(
        f"Tensor conversion not yet implemented for {type(self).__name__}"
    )

RandomMaskTensor

Bases: PatternTensor

A reproducible random mask with true probability p and no stored entries.

shape may be an integer for a vector, or a tuple (including ()). An omitted seed draws one random 64-bit seed from rng (a new NumPy generator by default). Reads consume no randomness; a fixed seed and coordinates give the same value even if the shape changes.

Like Finch.jl, indexed masks mix the seed, then each one-based coordinate from the first axis to the last, which is Finch.jl's order once the axes are reversed like other tensors. Scalar masks use the seed directly. The high 53 bits give a value in [0, 1) that is compared with p.

Source code in src/finch/tensor/patterns.py

class RandomMaskTensor(PatternTensor):
    """A reproducible random mask with true probability ``p`` and no stored entries.

    ``shape`` may be an integer for a vector, or a tuple (including ``()``).
    An omitted ``seed`` draws one random 64-bit seed from ``rng`` (a new NumPy
    generator by default). Reads consume no randomness; a fixed seed and
    coordinates give the same value even if the shape changes.

    Like Finch.jl, indexed masks mix the seed, then each one-based coordinate
    from the first axis to the last, which is Finch.jl's order once the axes
    are reversed like other tensors. Scalar masks use the seed directly.
    The high 53 bits give a value in ``[0, 1)`` that is compared with ``p``.
    """

    def __init__(
        self,
        shape,
        p: float,
        *,
        seed: int | None = None,
        rng: np.random.Generator | None = None,
        dtype=None,
    ):
        if not 0 <= p <= 1:
            raise ValueError("p must lie in [0, 1]")
        if isinstance(shape, int | np.integer):
            shape = (shape,)
        shape = tuple(operator.index(dim) for dim in shape)
        if any(dim < 0 for dim in shape):
            raise ValueError("shape dimensions must be nonnegative")
        if any(dim > np.iinfo(np.intp).max for dim in shape):
            raise OverflowError("shape dimensions must fit in intp")
        self._p = float(p)
        if seed is None:
            if rng is None:
                rng = np.random.default_rng()
            self._seed = int(rng.integers(0, 1 << 64, dtype=np.uint64))
        else:
            self._seed = operator.index(seed)
        if not 0 <= self._seed < 1 << 64:
            raise ValueError("seed must lie in [0, 2**64 - 1]")
        super().__init__(
            shape,
            ndim=len(shape),
            dtype=dtype,
            default_dtype=np.bool_,
            fill_value=False,
            pattern_value=True,
            p=self._p,
            seed=self._seed,
        )

    def contains(self, *idxs) -> bool:
        if not idxs:
            return _randommask_uniform(self._seed) < self._p
        state = _randommask_mix(self._seed)
        for idx in idxs:
            state = _randommask_mix(state ^ (operator.index(idx) + 1))
        return _randommask_uniform(state) < self._p

    def item(self):
        if self.ndim != 0:
            raise ValueError("Cannot convert non-scalar tensor to Python scalar.")
        return self[()].item()

RepeatTensor

Bases: PatternTensor

Map each of n indices to k repeated indices.

shape is (n, n * k), and row i holds the repeats j of i, so that the efficient row-major traversal visits each index and then its repeats. For k <= 0, all entries are false.

Source code in src/finch/tensor/patterns.py

class RepeatTensor(PatternTensor):
    """Map each of ``n`` indices to ``k`` repeated indices.

    ``shape`` is ``(n, n * k)``, and row ``i`` holds the repeats ``j`` of ``i``,
    so that the efficient row-major traversal visits each index and then its
    repeats. For ``k <= 0``, all entries are false.
    """

    def __init__(self, shape, *, k: int = 0, dtype=None):
        self._k = k
        super().__init__(shape, dtype=dtype, k=self._k)

    @classmethod
    def _level_format_properties(cls, ndim: int) -> list[FormatProperty]:
        return [Blocked((0,), (1,)), Repeated((0,), (1,))]

    def contains(self, i, j) -> bool:
        return self._k > 0 and i == j // self._k

SplitMaskTensor

Bases: PatternTensor

Partition n indices into p contiguous regions of nearly equal size.

shape is (p, n), and row j covers n*j//p <= i < n*(j+1)//p, so that the efficient row-major traversal visits each region and then its indices.

Source code in src/finch/tensor/patterns.py

class SplitMaskTensor(PatternTensor):
    """Partition ``n`` indices into ``p`` contiguous regions of nearly equal size.

    ``shape`` is ``(p, n)``, and row ``j`` covers ``n*j//p <= i < n*(j+1)//p``,
    so that the efficient row-major traversal visits each region and then its
    indices.
    """

    def __init__(self, shape, *, dtype=None):
        super().__init__(
            shape,
            dtype=dtype,
            default_dtype=np.bool_,
            fill_value=False,
            pattern_value=True,
        )
        p, n = map(operator.index, self.shape)
        if n < 0:
            raise ValueError("n must be nonnegative")
        if p <= 0:
            raise ValueError("shape[0] must be positive")

    def contains(self, j, i) -> bool:
        p, n = self.shape
        return n * j // p <= i < n * (j + 1) // p