# moonbit-roaring

[![CI](https://github.com/xcc-ordinary/moonbit-roaring/actions/workflows/ci.yml/badge.svg)](https://github.com/xcc-ordinary/moonbit-roaring/actions/workflows/ci.yml)

[English](README.md) | [简体中文](README.zh-CN.md)

An interoperability-focused RoaringBitmap implementation for MoonBit. It
combines automatic Array/Bitmap/Run representation selection with the Roaring
portable binary format.

The project complements, rather than replaces,
[`kesmeey/RoaringBitmap`](https://github.com/kesmeey/RoaringBitmap). That package
established the core bitmap and set-operation API in MoonBit; this package
focuses on portable-format interoperability, automatic run compression on the
normal mutation path, strict decoding, and current-toolchain reproducibility.

## Why another package?

The overlap is deliberate and documented: both packages provide 32-bit integer
sets and standard set operations. The independently useful additions here are:

- **Portable interoperability** — reads and writes the format specified by
  [`RoaringFormatSpec`](https://github.com/RoaringBitmap/RoaringFormatSpec), so
  MoonBit can participate in existing cross-language Roaring data pipelines.
- **Run optimization on normal operations** — `add`, `remove`, range methods,
  and all set operations reselect Array, Bitmap, or Run representation by
  encoded byte cost.
- **Defensive decoding** — rejects truncated input, invalid offsets, unordered
  keys or arrays, overlapping runs, cardinality mismatches, and trailing bytes.
- **Additional bitmap-level APIs** — half-open range construction/mutation,
  lazy iteration, `rank`, `select`, multi-way operations, plus compatibility
  helpers `clear`, inclusive `range`, and `jaccard_similarity`.

A source-linked, fair comparison is in
[`docs/competition/competitor-research.md`](docs/competition/competitor-research.md).

## Installation

```bash
moon add xcc-ordinary/moonbit-roaring
```

Until the Mooncakes package is published, depend on the Git repository or clone
this repository to run the examples and tests.

## Example

```moonbit
let sparse = @roaring.RoaringBitmap::from_array([1U, 100U, 1000U])
let consecutive = @roaring.RoaringBitmap::from_range(0U, 10000U)
let result = sparse.union(consecutive)

// The only exposed wire format is the interoperable portable format.
let bytes = result.serialize()
let restored = match @roaring.RoaringBitmap::deserialize(bytes) {
  Ok(bitmap) => bitmap
  Err(error) => panic("invalid bitmap: \{error}")
}

let first_three = restored.iter().take(3).to_array()
let count_at_or_below_500 = restored.rank(500U)
let fifth = restored.select(4)
```

Runnable user paths:

```bash
moon run examples/inverted_index
moon run examples/portable_window
moon run examples/analytics
```

They demonstrate postings-list queries, a portable time-window handoff, and
bitmap-level cumulative/order analytics respectively.

## Implemented surface

- Array, Bitmap, and Run containers
- standard set operations and multi-way union/intersection
- half-open range construction, mutation, and containment
- lazy `Iter[UInt]`, bitmap-level `rank` and `select`
- Roaring portable serialization and strict deserialization
- immutable compatibility helpers: `clear`, inclusive `range`, Jaccard similarity
- statistics exposing container choices and encoded payload sizes

## Verification evidence

- Tests run on `wasm`, `wasm-gc`, and `js` in CI.
- Official Java-generated files from `RoaringFormatSpec/testdata` are decoded,
  checked for known values, and re-encoded byte-for-byte.
- Six additional fixture shapes are generated by `roaring-wasm` v1.1.0, a
  third-party CRoaring-based WASM package. CI verifies deterministic regeneration.
- Malformed-format tests cover structural and semantic validation, including
  every truncated prefix of representative serialized data.
- Release-mode benchmark fixtures and a reproducible baseline are documented in
  [`docs/benchmarks.md`](docs/benchmarks.md). They are not a competitor-speed claim.

```bash
moon info
moon fmt --check
moon check -d
moon test
moon test --target wasm-gc
moon test --target js
moon bench --release --target wasm
```

## Comparison scope

As reproduced on 2026-09-17 at competitor commit
`f19c4977512aa120cd1add61e32f9dec36bd3102`:

| Area | `kesmeey/RoaringBitmap` | `moonbit-roaring` |
| --- | --- | --- |
| Basic 32-bit set operations | Yes | Yes |
| Array/Bitmap/Run definitions | Yes | Yes |
| Run selection on ordinary mutation paths | Optimizer has no call site at that commit | Integrated into mutations and set operations |
| Roaring portable bytes | Not found at that commit | Tested with official testdata |
| Range API | Inclusive filtering of existing values | Same compatibility API plus half-open construction/mutation |
| Iteration | Callback traversal | Lazy `Iter[UInt]` |
| Rank | Container-level helper | Bitmap-level `rank` and `select` |
| Current toolchain | Pinned commit has old-generic-syntax parse errors on `moon 0.1.20260904` | Three-target CI |

These are commit- and toolchain-specific observations, not a judgment about the
other project's overall quality. Reproduction commands and source links are in
the comparison document.

## Scope and limitations

- 32-bit unsigned values only; no Roaring64.
- Portable format only; no native/frozen/mmap formats.
- Immutable operations; no thread-safe mutable bitmap API.
- No SIMD-specific kernels and no claim of outperforming other implementations.
- The native target is not currently part of the verified matrix.

## License

Apache-2.0.

This project is being prepared for the September 2026 MoonBit Hackathon. The
resubmission evidence is tracked in
[`docs/competition/resubmission-strategy.zh-CN.md`](docs/competition/resubmission-strategy.zh-CN.md).