Metadata-Version: 2.4
Name: weighted-gss
Version: 0.2.1
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
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: Programming Language :: Rust
Classifier: Typing :: Typed
Classifier: Topic :: Software Development :: Libraries
License-File: LICENSE-MIT
License-File: LICENSE-APACHE
Summary: Persistent weighted graph-structured stacks
Keywords: graph-structured-stack,weighted,glr,parsing,persistent-data-structure
Home-Page: https://github.com/IsaacBreen/weighted-gss
Author-email: Isaac Breen <mail@isaacbreen.com>
License-Expression: MIT OR Apache-2.0
Requires-Python: >=3.8
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Changelog, https://github.com/IsaacBreen/weighted-gss/blob/main/CHANGELOG.md
Project-URL: Homepage, https://github.com/IsaacBreen/weighted-gss
Project-URL: Issues, https://github.com/IsaacBreen/weighted-gss/issues
Project-URL: Python API, https://github.com/IsaacBreen/weighted-gss/blob/main/docs/python.md
Project-URL: Rust API, https://docs.rs/weighted-gss
Project-URL: Source, https://github.com/IsaacBreen/weighted-gss

# weighted-gss

[![CI](https://github.com/IsaacBreen/weighted-gss/actions/workflows/ci.yml/badge.svg)](https://github.com/IsaacBreen/weighted-gss/actions/workflows/ci.yml)
[![Fuzz](https://github.com/IsaacBreen/weighted-gss/actions/workflows/fuzz.yml/badge.svg)](https://github.com/IsaacBreen/weighted-gss/actions/workflows/fuzz.yml)

A persistent weighted graph-structured stack.

`WeightedGss<S, W>` represents a finite collection of stack alternatives. Each stack carries a weight. When stack operations make alternatives denote the same concrete stack, their weights are joined.

The graph representation is private. The Rust API contains semantic stack operations, bounded concrete-stack inspection, and a linear-prefix fast path without exposing graph nodes or canonical representation machinery.

## Installation

The latest release is version 0.2.1.

```toml
[dependencies]
weighted-gss = "0.2.1"
```

Python 3.8 or later:

```bash
python -m pip install "weighted-gss==0.2.1"
```

## Rust

Stacks are supplied and returned bottom-to-top.

```rust
use weighted_gss::{Weight, WeightedGss};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Possibilities(u32);

impl Weight for Possibilities {
    fn join(&self, other: &Self) -> Self {
        Self(self.0 | other.0)
    }
}

let left = WeightedGss::from_stack([0_u32, 1, 2], Possibilities(0b001));
let right = WeightedGss::from_stack([0_u32, 1, 3], Possibilities(0b100));
let stacks = left.merge(&right);

assert_eq!(stacks.top(), None);
assert_eq!(
    stacks.tops().collect::<std::collections::BTreeSet<_>>(),
    [2, 3].into(),
);

let reduced = stacks.pop_top(&2).push(9);
assert_eq!(
    reduced.to_stacks(8).unwrap(),
    vec![(vec![0, 1, 9], Possibilities(0b001))],
);
```

A weight must implement ordinary equality. `join` must be associative, commutative, and idempotent.

The exported Rust names are:

```rust
Weight
WeightedGss
Gss
LinearPrefix
StackLimitExceeded
linear_prefix
for_each_stack_top_first
```

The core methods are:

- construction: `new`, `from_stack`, `from_stacks`, `from_stacks_with_weight`;
- alternatives: `merge`;
- stack operations: `push`, `pop`, `popn`;
- top selection: `top`, `tops`, `has_empty_stack`, `retain_top`, `retain_empty`, `pop_top`;
- weights: `weights`, `map_weights`, `filter_map_weights`, `joined_weight`;
- observations: `is_empty`, `max_depth`, `to_stacks`.

`to_stacks(max_stacks)` returns canonical `(stack, weight)` pairs and fails with the opaque `StackLimitExceeded` error rather than returning more than the requested number of distinct stacks.

`weights()` iterates stored factored weight regions, not concrete stacks. One weight may cover many stacks, equal weights may appear more than once, and count/order are unspecified. `map_weights` and `filter_map_weights` transform those regions without materialising stacks; see [Semantics and invariants](docs/semantics.md) for the representation-independence condition.

## Bounded inspection and linear prefixes

`for_each_stack_top_first(&gss, max_stacks, visit)` visits canonical distinct stacks as borrowed top-first slices. It completes only when the complete result fits within `max_stacks`.

`linear_prefix(&gss)` returns a `LinearPrefix` when the current value has one homogeneous weight and a directly accessible linear top prefix. The hidden floor may still branch. The view supports indexed reads from the top, pushes, bounded pops, and conversion back into a `WeightedGss` while retaining the unchanged floor.

Neither operation exposes graph nodes, structural paths, or canonical stack-language IDs.

## Validation and performance characteristics

Correctness is checked against an explicit stack-to-weight map through deterministic tests, shrinkable property-based operation sequences, and an oracle-backed `cargo-fuzz` target. The benchmark suite compares the compact representation with an explicit map, an explicit unweighted stack set, and a benchmark-only `weight -> stack set` ablation.

Representative Criterion medians from one clean Apple M1 Pro run are shown below. They describe these particular shapes and operations, not a machine-independent speed claim.

| Workload | `WeightedGss` | Explicit map | What it shows |
|---|---:|---:|---|
| Persistent fork of a 512-stack value | 174 ns | 141 µs | Immutable structural sharing makes forks cheap |
| Merge across a 20,000-symbol common top prefix | 8.25 µs | 22.6 µs | Compact prefix reuse can avoid copying long stacks |
| Pop 1,024 alternatives that collapse to one stack | 113 µs | 42.6 µs | An explicit map remains faster for this join-heavy operation |
| Construct 1,024 already-explicit weighted stacks | 3.54 ms | 60.5 µs | Bulk construction is not the graph representation's strength |

The intended trade-off is therefore specific: `WeightedGss` pays construction and representation costs to support persistent evolution and structural sharing. It is not a universally faster replacement for an explicit stack map.

```bash
cargo test --all-targets
cargo bench
cargo +nightly fuzz run operation_sequences
```

See [Correctness validation](docs/validation.md), [Benchmarks](docs/benchmarks.md), and the [2026-07-28 validation record](https://github.com/IsaacBreen/weighted-gss/blob/main/docs/https://github.com/IsaacBreen/weighted-gss/blob/main/docs/validation/validation-and-benchmarks-2026-07-28.md).

## Python

```python
from dataclasses import dataclass
from weighted_gss import WeightedGSS

@dataclass(frozen=True)
class Possibilities:
    bits: int

    def join(self, other: "Possibilities") -> "Possibilities":
        return Possibilities(self.bits | other.bits)

stacks = WeightedGSS.from_stacks([
    ([0, 1, 2], Possibilities(0b001)),
    ([0, 1, 3], Possibilities(0b100)),
])

assert stacks.tops() == {2, 3}
assert stacks.pop_top(2).to_stacks() == [
    ([0, 1], Possibilities(0b001)),
]
```

Python weights need not be hashable. Exceptions raised by `join()` are propagated normally. See the [Python API](docs/python.md).

## Semantics

Weights and stack operations have an extensional meaning independent of the private graph representation. Rust 1.85 is the declared minimum version. See [Semantics and invariants](docs/semantics.md).

Licensed under either Apache-2.0 or MIT, at your option.

