moczarr.intersect

Two-store occupancy intersection (cross-sensor cell masks) — issue #39.

The read-side composition primitive englacial/zagg#426 needs (GEDI waveform stores composed with ATL03 stores): the exact cell occupancy TWO hive stores share, where the store-vs-AOI helpers (root_coverage_and / box_and / bitmap_and) answer only one store against a cover. The flow is the §5 tier discipline applied twice:

1. Root prefilter — each store's root coverage.moc (or the discovery walk when it is unusable; D9) names its committed shards, and the shared regions are their intersection. Shard orders may differ; regions sit at the FINER shard order, so each region maps to exactly one leaf per store.
2. Per-region exact AND — each leaf's exact occupancy (the "bitmap" sidecar, or the whole subtree for encoding: "full", which short-circuits without a sidecar GET) is restricted to the region and intersected cell-for-cell.
3. Order harmonization — when the stores' cell orders differ (e.g. ATL03 o19 vs GEDI o18), the finer store's cells coarsen to the coarser order by 4:1 OR-coarsening (clip2order + unique: a coarse cell is occupied iff any of its four children is) before the AND. All results are at min(cell_order_a, cell_order_b) — the manifests set the harmonized OUTPUT order, but the order of a leaf's decoded cells is what that leaf's OWN envelope declares (coverage["cell_order"], which is what the sidecar decoded against). Reading the manifest's value there is a silent false negative: a word carries its order in its low bits, so words at two orders are never bit-equal and the AND simply matches nothing.

Degradation, documented: a shared leaf WITHOUT exact occupancy at the harmonized order — a stamp with no usable coverage envelope, a box-only envelope, a "bitmap" envelope whose sidecar object is missing, or an envelope whose declared cell_order sits BELOW the harmonized order (its cells name subtrees there, not cells) — contributes its conservative cover instead (the tier-0 box, the decoded cells read as a cover, or the whole shard subtree when even the box is unusable). The intersection is then a conservative SUPERSET for cells under that leaf: false positives possible, false negatives impossible — the same posture as the box tier everywhere else — and the first such leaf per call raises a :class:moczarr.exceptions.ConservativeCoverageWarning (a UserWarning subclass, so it stays filterable by class without catching everything). That is the degrade="conservative" default; degrade="skip" drops such leaves instead (nothing is yielded under them, so everything returned IS exact — exact-or-under rather than superset) and degrade="raise" refuses the call, naming the first one. Debris and absent leaves contribute nothing under every policy (absence is definitive; a clean GET miss is trustworthy on its own).

Two API shapes, ruled on the measured comparison of zagg#422 open question 7 — one is the surface, the other is derived from it:

• :func:iter_occupancy_and — shape (a), THE public surface: an iterator of (leaf_id, intersected cell words) per shared leaf, streaming, and the shape the zagg#426 consumer reads through (leaf identity is what fetches the payloads for the aligned per-leaf tensors).
• :func:occupancy_and — shape (b), a documented thin convenience DERIVED from (a): one flat compacted MOC of the whole intersection, semantically compress_moc over (a)'s stream (a fully-shared subtree compacts to its ancestor word, so dense overlap stays small). It is the currency for MOC algebra — it feeds open_hive(aoi=...), moc_and and :func:moczarr.coverage.aoi_mask directly, and is the compact thing to persist or ship.

The derivation runs ONE way: (b) is one compress_moc over (a), while (a) is NOT recoverable from (b) — compaction discards the leaf attribution that per-leaf reads need. Reach for (a) to read cells under a leaf, (b) to do MOC algebra with the answer.

aoi= is SHARD-level on both, by contract: it restricts the shard cover through the same candidate-leaves arithmetic the opener uses, and the cells of a kept leaf are never clipped to it. Both shapes are therefore supersets with respect to the AOI — false positives possible, false negatives impossible, zagg's AOI-overhang convention — and :func:moczarr.coverage.aoi_mask is the documented exact cell-level cut. Keeping the clip out of here is what lets a fully-shared subtree stay one compact word under a partial AOI instead of expanding to be trimmed.

The AND itself runs in MOC currency and never materializes a subtree: exact cells against a conservative cover are filtered by containment (coverage.aoi_mask), cover against cover is a moc_and, so the work is bounded by the exact side wherever one exists. Cells are materialized only where shape (a) has to yield them, and only for a region that is a cover on BOTH sides — full-on-both (exact by construction; its whole subtree IS the answer) or degraded on both — at 4^(out_order - region_order) words. Shape (b) never expands — which is why it is not implemented as the literal composition over (a), only documented as equivalent to it (see :func:occupancy_and).

Spec + fixtures only, per the moczarr contract: everything here decodes from zagg docs/specification.md via this package's own convention / coverage / store layers — no zagg import.

iter_occupancy_and(root_a, root_b, *, aoi=None, window_a=None, window_b=None, store_a=None, store_b=None, concurrency=32, degrade=_CONSERVATIVE, **store_kwargs)

Exact shared occupancy of two hive stores, streamed per shared leaf.

Shape (a), and the module's public surface (zagg#422 open question 7, ruled on this PR's measured comparison): the shape per-leaf readers want, because leaf_id is what fetches a leaf's payloads — the zagg#426 flow builds its aligned side-by-side tensors that way (moczarr.hhdc.read_tensors / :func:moczarr.open_leaf per yielded leaf). :func:occupancy_and is one compress_moc over this stream; the reverse does not exist, since compaction discards leaf attribution.

Yields (leaf_id, cells) in ascending packed-word order — leaf_id the shared region's packed shard word (the finer store's leaf when shard orders differ; both stores' when equal) and cells the sorted occupied cell words BOTH stores share under it, at the coarser of the two cell orders (4:1 OR-coarsening harmonizes a finer store — a coarse cell is occupied iff any of its four children is). Regions whose exact intersection is empty are skipped; an exhausted iterator with no yields means the stores share no occupancy.

aoi (a morton cover: packed words, decimal strings, or an object exposing __morton_moc__() — mortie's Moc — mixed orders allowed) is a SHARD-LEVEL prefilter, and that is the contract, not an implementation detail: it runs through the same candidate-leaves arithmetic :func:moczarr.open_hive uses, so a leaf whose subtree misses the cover never loads — but the cells of a KEPT leaf are NOT clipped to the cover. Results are therefore a SUPERSET with respect to the AOI: cells outside it can be yielded (false positives possible), cells inside it are never dropped (false negatives impossible). That is zagg's AOI-overhang convention, the same one-directional posture the box tier keeps everywhere else here, and it is what lets a region full on both sides stay compact under a partial AOI instead of expanding to be clipped. The documented EXACT cell-level cut is :func:moczarr.coverage.aoi_mask over the yielded cells: cells[aoi_mask(cells, aoi_words)].

window_a / window_b name the time window per store (morton-hive/2); store_a / store_b pass pre-built obstore handles (required when the two stores need different credentials — store_kwargs apply to BOTH roots otherwise). concurrency bounds the batched stamp GETs and walk LISTs.

degrade picks what a leaf without exact occupancy at the harmonized order does — the module docstring lists which leaves those are: "conservative" (default) contributes its cover, so the result is a SUPERSET under that leaf (false positives possible, false negatives impossible) and the first such leaf per call raises one :class:moczarr.exceptions.ConservativeCoverageWarning — its own UserWarning subclass, so a consumer can promote it to an error or silence it by category; "skip" drops it, so the leaf contributes nothing and EVERYTHING yielded is exact — exact-or-under instead of superset, the discriminator a per-cell consumer needs — at the price of silently missing real shared occupancy under it; "raise" refuses, naming the first such leaf. Raises ValueError AT CALL TIME — not at the first next() — when a root has no manifest, or when the orders do not compose (one store's cell order above the other's shard order): both stores are opened and validated before the iterator exists, so a store-root typo surfaces where it was made.

Cost: yielding CELLS is what shape (a) is for, and a region whose result is a cover on BOTH sides — full-on-both (exact, and bounded by the region's own subtree), or degraded on both — materializes 4^(out_order - region_order) words for that one yield. Everywhere else the intersection is bounded by the exact side and nothing is expanded, degraded leaves included. :func:occupancy_and never expands at all; reach for it when the harmonized order is far below the shard order.

Source code in src/moczarr/intersect.py

def iter_occupancy_and(
    root_a: str,
    root_b: str,
    *,
    aoi=None,
    window_a: str | None = None,
    window_b: str | None = None,
    store_a: Any = None,
    store_b: Any = None,
    concurrency: int | None = 32,
    degrade: str = _CONSERVATIVE,
    **store_kwargs: Any,
) -> Iterator[tuple[int, np.ndarray]]:
    """Exact shared occupancy of two hive stores, streamed per shared leaf.

    Shape (a), and the module's public surface (zagg#422 open question 7,
    ruled on this PR's measured comparison): the shape per-leaf readers
    want, because ``leaf_id`` is what fetches a leaf's payloads — the
    zagg#426 flow builds its aligned side-by-side tensors that way
    (``moczarr.hhdc.read_tensors`` / :func:`moczarr.open_leaf` per yielded
    leaf). :func:`occupancy_and` is one ``compress_moc`` over this stream;
    the reverse does not exist, since compaction discards leaf attribution.

    Yields ``(leaf_id, cells)``
    in ascending packed-word order — ``leaf_id`` the shared region's packed
    shard word (the finer store's leaf when shard orders differ; both
    stores' when equal) and ``cells`` the sorted occupied cell words BOTH
    stores share under it, at the coarser of the two cell orders (4:1
    OR-coarsening harmonizes a finer store — a coarse cell is occupied iff
    any of its four children is). Regions whose exact intersection is empty
    are skipped; an exhausted iterator with no yields means the stores share
    no occupancy.

    ``aoi`` (a morton cover: packed words, decimal strings, or an object
    exposing ``__morton_moc__()`` — mortie's ``Moc`` — mixed orders
    allowed) is a SHARD-LEVEL prefilter, and that is the contract, not an
    implementation detail: it runs through the same candidate-leaves
    arithmetic :func:`moczarr.open_hive` uses, so a leaf whose subtree
    misses the cover never loads — but the cells of a KEPT leaf are NOT
    clipped to the cover. Results are therefore a SUPERSET with respect to
    the AOI: cells outside it can be yielded (false positives possible),
    cells inside it are never dropped (false negatives impossible). That is
    zagg's AOI-overhang convention, the same one-directional posture the
    box tier keeps everywhere else here, and it is what lets a region full
    on both sides stay compact under a partial AOI instead of expanding to
    be clipped. The documented EXACT cell-level cut is
    :func:`moczarr.coverage.aoi_mask` over the yielded cells:
    ``cells[aoi_mask(cells, aoi_words)]``.

    ``window_a`` / ``window_b`` name the time window per
    store (``morton-hive/2``); ``store_a`` / ``store_b`` pass pre-built
    obstore handles (required when the two stores need different
    credentials — ``store_kwargs`` apply to BOTH roots otherwise).
    ``concurrency`` bounds the batched stamp GETs and walk LISTs.

    ``degrade`` picks what a leaf without exact occupancy at the harmonized
    order does — the module docstring lists which leaves those are:
    ``"conservative"`` (default) contributes its cover, so the result is a
    SUPERSET under that leaf (false positives possible, false negatives
    impossible) and the first such leaf per call raises one
    :class:`moczarr.exceptions.ConservativeCoverageWarning` — its own
    ``UserWarning`` subclass, so a consumer can promote it to an error or
    silence it by category;
    ``"skip"`` drops it, so the leaf contributes nothing and EVERYTHING
    yielded is exact — exact-or-under instead of superset, the discriminator
    a per-cell consumer needs — at the price of silently missing real shared
    occupancy under it; ``"raise"`` refuses, naming the first such leaf.
    Raises ``ValueError`` AT CALL
    TIME — not at the first ``next()`` — when a root has no manifest, or when
    the orders do not compose (one store's cell order above the other's shard
    order): both stores are opened and validated before the iterator exists,
    so a store-root typo surfaces where it was made.

    Cost: yielding CELLS is what shape (a) is for, and a region whose result
    is a cover on BOTH sides — full-on-both (exact, and bounded by the
    region's own subtree), or degraded on both — materializes
    ``4^(out_order - region_order)`` words for that one yield. Everywhere
    else the intersection is bounded by the exact side and nothing is
    expanded, degraded leaves included. :func:`occupancy_and` never expands
    at all; reach for it when the harmonized order is far below the shard
    order.
    """
    return _iter_cells(
        _setup(
            root_a,
            root_b,
            aoi,
            window_a,
            window_b,
            store_a,
            store_b,
            concurrency,
            store_kwargs,
            degrade,
        )
    )

occupancy_and(root_a, root_b, *, aoi=None, window_a=None, window_b=None, store_a=None, store_b=None, concurrency=32, degrade=_CONSERVATIVE, **store_kwargs)

The :func:iter_occupancy_and intersection, compacted to one flat MOC.

Shape (b): a thin convenience DERIVED from the public surface — semantically compress_moc over everything :func:iter_occupancy_and yields, returned whole as a canonical compact morton cover (uint64, ascending). A fully-shared subtree compacts to its ancestor word, so dense overlap stays small, and the empty intersection is an empty array. Parameters (degrade included), degradation, and errors are identical to :func:iter_occupancy_and.

aoi keeps the same contract it has there — the same accepted forms (packed words, decimal strings, or an object exposing __morton_moc__()), and a SHARD-LEVEL prefilter, with the cells of a kept leaf left unclipped, so the returned MOC is a superset with respect to the AOI (false positives possible, false negatives impossible: zagg's AOI-overhang convention). Worth restating on this shape, because a MOC is what gets composed onward: feed the result to moc_and(result, aoi_words) (or :func:moczarr.coverage.aoi_mask on cells) when the consumer needs the exact cut rather than the overhang.

The derivation is one-way, and that asymmetry is what picks between the two:

• (b) from (a) is one line — compress_moc(concatenate([cells for _leaf, cells in iter_occupancy_and(...)])) — and equals this function's result member-for-member (pinned by test_flat_moc_is_the_compressed_stream).
• (a) from (b) does not exist: compaction discards leaf attribution, and a member may sit above, at, or below a leaf. Use shape (a) for per-leaf reads — the zagg#426 tensor path, which needs the leaf id to fetch payloads — and this shape as MOC-algebra currency: it is what open_hive(aoi=...), moc_and and :func:moczarr.coverage.aoi_mask consume, and the compact thing to persist or ship.

Cost — the reason this is NOT implemented as the literal one-liner: the composition above would expand a region that is full (or degraded) on both sides to its 4^(out_order - region_order) cells, purely to compact them back to the ancestor word they came from (~262k words at the zagg#426 o9-shard/o18-cell scale, per region). This stays in MOC currency end to end instead — same result, no subtree ever materialized (pinned by test_only_the_iterator_expands_full_on_both). Expanding every member back to the harmonized cell order yields exactly the union of the iterator's cells (the shared golden test).

Source code in src/moczarr/intersect.py

def occupancy_and(
    root_a: str,
    root_b: str,
    *,
    aoi=None,
    window_a: str | None = None,
    window_b: str | None = None,
    store_a: Any = None,
    store_b: Any = None,
    concurrency: int | None = 32,
    degrade: str = _CONSERVATIVE,
    **store_kwargs: Any,
) -> np.ndarray:
    """The :func:`iter_occupancy_and` intersection, compacted to one flat MOC.

    Shape (b): a thin convenience DERIVED from the public surface —
    semantically ``compress_moc`` over everything
    :func:`iter_occupancy_and` yields, returned whole as a canonical
    compact morton cover (``uint64``, ascending). A fully-shared subtree
    compacts to its ancestor word, so dense overlap stays small, and the
    empty intersection is an empty array. Parameters (``degrade``
    included), degradation, and errors are identical to
    :func:`iter_occupancy_and`.

    ``aoi`` keeps the same contract it has there — the same accepted forms
    (packed words, decimal strings, or an object exposing
    ``__morton_moc__()``), and a SHARD-LEVEL prefilter,
    with the cells of a kept leaf left unclipped, so the returned MOC is a
    superset with respect to the AOI (false positives possible, false
    negatives impossible: zagg's AOI-overhang convention). Worth restating
    on this shape, because a MOC is what gets composed onward: feed the
    result to ``moc_and(result, aoi_words)`` (or
    :func:`moczarr.coverage.aoi_mask` on cells) when the consumer needs the
    exact cut rather than the overhang.

    The derivation is one-way, and that asymmetry is what picks between
    the two:

    - **(b) from (a)** is one line —
      ``compress_moc(concatenate([cells for _leaf, cells in
      iter_occupancy_and(...)]))`` — and equals this function's result
      member-for-member (pinned by ``test_flat_moc_is_the_compressed_stream``).
    - **(a) from (b)** does not exist: compaction discards leaf
      attribution, and a member may sit above, at, or below a leaf. Use
      shape (a) for per-leaf reads — the zagg#426 tensor path, which needs
      the leaf id to fetch payloads — and this shape as MOC-algebra
      currency: it is what ``open_hive(aoi=...)``, ``moc_and`` and
      :func:`moczarr.coverage.aoi_mask` consume, and the compact thing to
      persist or ship.

    Cost — the reason this is NOT implemented as the literal one-liner:
    the composition above would expand a region that is full (or degraded)
    on both sides to its ``4^(out_order - region_order)`` cells, purely to
    compact them back to the ancestor word they came from (~262k words at
    the zagg#426 o9-shard/o18-cell scale, per region). This stays in MOC
    currency end to end instead — same result, no subtree ever
    materialized (pinned by ``test_only_the_iterator_expands_full_on_both``).
    Expanding every member back to the harmonized cell order yields exactly
    the union of the iterator's cells (the shared golden test).
    """
    plan = _setup(
        root_a,
        root_b,
        aoi,
        window_a,
        window_b,
        store_a,
        store_b,
        concurrency,
        store_kwargs,
        degrade,
    )
    parts = [part.words for _region, part in _iter_parts(plan)]
    if not parts:
        return np.empty(0, dtype=np.uint64)
    from mortie import compress_moc

    return np.sort(np.asarray(compress_moc(np.concatenate(parts)), dtype=np.uint64))