code/cl8y-dex-terraclassic

Fork 0

Factory Pairs query: O(1) pagination cursor via pair-key index map #258

New issue

Closed

opened 2026-05-31 13:45:56 +00:00 by PlasticDigits · 4 comments

PlasticDigits commented

2026-05-31 13:45:56 +00:00

(Migrated from gitlab.com)

Summary

Add a sibling storage map pair_key → PAIR_INDEX index so QueryMsg::Pairs { start_after, limit } resolves the pagination cursor in O(1) instead of scanning the full PAIR_INDEX range.

Current codebase

Factory state (smartcontracts/contracts/factory/src/state.rs):
- PAIRS: Map<&str, PairInfo> — canonical asset key → pair (already used on CreatePair / QueryMsg::Pair).
- PAIR_INDEX: Map<u64, PairInfo> — sequential enumeration.
- PAIR_ADDR_REGISTERED: Map<Addr, bool> — O(1) membership for governance (#122).
query_pairs (factory/src/contract.rs): when start_after: Option<[AssetInfo; 2]> is set, loops PAIR_INDEX.range from the start, compares pair_key(&info.asset_infos) until match — O(N) per query page.
Page fetch then uses PAIR_INDEX.range from start_idx with calc_limit (default 10, max 30).
Write path: reply_instantiate_pair saves PAIRS, PAIR_INDEX, PAIR_ADDR_REGISTERED, increments PAIR_COUNT.
Migrate: 1.0.0 → 1.1.0 backfilled PAIR_ADDR_REGISTERED from index — pattern exists for sibling maps.

Why this is needed

Indexers and discovery tools paginate all pairs; cursor resolution degrades linearly as factory grows (page 100 ≈ 100× index scans).
Read-only query cost on public LCD nodes; not taker swap gas, but affects sync time and operator tooling.
Aligns with #122 philosophy: O(1) lookups where enumeration is hot.

Constraints and guardrails

Invariant: For every PAIR_INDEX entry at idx, PAIR_KEY_INDEX[pair_key(asset_infos)] == idx (name TBD).
Updates: Only reply_instantiate_pair (and any future pair-removal — none today) mutates index; keep in sync atomically in reply handler.
Migration: New map must be backfilled for existing deployments (migrate from current version), same style as PAIR_ADDR_REGISTERED backfill.
Do not remove PAIR_INDEX — still used for bounded governance batch scans (SetDiscountRegistryBatch).
start_after wire format: unchanged ([AssetInfo; 2]) for API compatibility.
Key function: reuse dex_common::types::pair_key / canonical_order — same as PAIRS keys.

Relevant files

Area	Path
State	`smartcontracts/contracts/factory/src/state.rs`
Query / reply / migrate	`smartcontracts/contracts/factory/src/contract.rs`
Key helper	`smartcontracts/packages/dex-common/src/types.rs`
Docs	`docs/contracts-terraclassic.md`, `docs/indexer-invariants.md`
Tests	`factory/src/contract.rs` (`#[cfg(test)]`), factory tests in `smartcontracts/tests/src/lib.rs`

Recommended direction

Add PAIR_KEY_INDEX: Map<&str, u64> (or Map<String, u64> consistent with PAIRS keys).
In reply_instantiate_pair, after computing key and count, save PAIR_KEY_INDEX[key] = count.
Replace query_pairs scan loop with PAIR_KEY_INDEX.load(key)? → start_idx = found + 1 for exclusive cursor semantics (match current Bound::exclusive behavior).
migrate: iterate PAIR_INDEX 0..PAIR_COUNT, populate map.
Unit test: N pairs, query page with start_after last asset of page k — constant storage reads (mock / assert no full range in test hook if possible).

Acceptance criteria

Pairs query with start_after uses O(1) key lookup (no full-index scan).
Pagination order unchanged (ascending index, same pairs as before migration).
Pair { asset_infos } and Pairs without start_after unchanged.
Migrate backfills existing chains; new pairs write map on create.
Invalid start_after still returns clear error.

Test plan (functional paths)

Path	Expectation
First page, no cursor	First `limit` pairs
Second page with `start_after`	Continues after cursor
Invalid `start_after`	Error: not found
`limit` default / max	`calc_limit` respected
After `CreatePair`	New pair appears; key index updated

Test plan (attack / abuse / hack vectors)

Vector	Verification
Duplicate asset pair create	Rejected before index write (existing)
Wrong cursor assets	Not found, no panic
Huge `limit`	Clamped to `MAX_LIMIT` (30)

Verification criteria

Factory unit + integration tests green.
docs/indexer-invariants.md updated: pagination is O(1) cursor resolve + O(limit) page read.
Optional: indexer sync smoke on multi-pair localnet.

## Summary Add a sibling storage map `pair_key → PAIR_INDEX` index so `QueryMsg::Pairs { start_after, limit }` resolves the pagination cursor in O(1) instead of scanning the full `PAIR_INDEX` range. ## Current codebase - **Factory state** (`smartcontracts/contracts/factory/src/state.rs`): - `PAIRS: Map<&str, PairInfo>` — canonical asset key → pair (already used on `CreatePair` / `QueryMsg::Pair`). - `PAIR_INDEX: Map<u64, PairInfo>` — sequential enumeration. - `PAIR_ADDR_REGISTERED: Map<Addr, bool>` — O(1) membership for governance (#122). - **`query_pairs`** (`factory/src/contract.rs`): when `start_after: Option<[AssetInfo; 2]>` is set, loops `PAIR_INDEX.range` from the start, compares `pair_key(&info.asset_infos)` until match — **O(N)** per query page. - Page fetch then uses `PAIR_INDEX.range` from `start_idx` with `calc_limit` (default 10, max 30). - **Write path:** `reply_instantiate_pair` saves `PAIRS`, `PAIR_INDEX`, `PAIR_ADDR_REGISTERED`, increments `PAIR_COUNT`. - **Migrate:** `1.0.0 → 1.1.0` backfilled `PAIR_ADDR_REGISTERED` from index — pattern exists for sibling maps. ## Why this is needed - Indexers and discovery tools paginate all pairs; cursor resolution degrades linearly as factory grows (page 100 ≈ 100× index scans). - Read-only query cost on public LCD nodes; not taker swap gas, but affects sync time and operator tooling. - Aligns with #122 philosophy: O(1) lookups where enumeration is hot. ## Constraints and guardrails - **Invariant:** For every `PAIR_INDEX` entry at `idx`, `PAIR_KEY_INDEX[pair_key(asset_infos)] == idx` (name TBD). - **Updates:** Only `reply_instantiate_pair` (and any future pair-removal — none today) mutates index; keep in sync atomically in reply handler. - **Migration:** New map must be backfilled for existing deployments (`migrate` from current version), same style as `PAIR_ADDR_REGISTERED` backfill. - **Do not** remove `PAIR_INDEX` — still used for bounded governance batch scans (`SetDiscountRegistryBatch`). - **`start_after` wire format:** unchanged (`[AssetInfo; 2]`) for API compatibility. - **Key function:** reuse `dex_common::types::pair_key` / `canonical_order` — same as `PAIRS` keys. ## Relevant files | Area | Path | |------|------| | State | `smartcontracts/contracts/factory/src/state.rs` | | Query / reply / migrate | `smartcontracts/contracts/factory/src/contract.rs` | | Key helper | `smartcontracts/packages/dex-common/src/types.rs` | | Docs | `docs/contracts-terraclassic.md`, `docs/indexer-invariants.md` | | Tests | `factory/src/contract.rs` (`#[cfg(test)]`), factory tests in `smartcontracts/tests/src/lib.rs` | ## Recommended direction 1. Add `PAIR_KEY_INDEX: Map<&str, u64>` (or `Map<String, u64>` consistent with `PAIRS` keys). 2. In `reply_instantiate_pair`, after computing `key` and `count`, save `PAIR_KEY_INDEX[key] = count`. 3. Replace `query_pairs` scan loop with `PAIR_KEY_INDEX.load(key)?` → `start_idx = found + 1` for exclusive cursor semantics (match current `Bound::exclusive` behavior). 4. `migrate`: iterate `PAIR_INDEX` 0..`PAIR_COUNT`, populate map. 5. Unit test: N pairs, query page with `start_after` last asset of page k — constant storage reads (mock / assert no full range in test hook if possible). ## Acceptance criteria - [ ] `Pairs` query with `start_after` uses O(1) key lookup (no full-index scan). - [ ] Pagination order unchanged (ascending index, same pairs as before migration). - [ ] `Pair { asset_infos }` and `Pairs` without `start_after` unchanged. - [ ] Migrate backfills existing chains; new pairs write map on create. - [ ] Invalid `start_after` still returns clear error. ## Test plan (functional paths) | Path | Expectation | |------|-------------| | First page, no cursor | First `limit` pairs | | Second page with `start_after` | Continues after cursor | | Invalid `start_after` | Error: not found | | `limit` default / max | `calc_limit` respected | | After `CreatePair` | New pair appears; key index updated | ## Test plan (attack / abuse / hack vectors) | Vector | Verification | |--------|----------------| | Duplicate asset pair create | Rejected before index write (existing) | | Wrong cursor assets | Not found, no panic | | Huge `limit` | Clamped to `MAX_LIMIT` (30) | ## Verification criteria - Factory unit + integration tests green. - `docs/indexer-invariants.md` updated: pagination is O(1) cursor resolve + O(limit) page read. - Optional: indexer sync smoke on multi-pair localnet.

PlasticDigits commented

2026-05-31 14:08:53 +00:00

(Migrated from gitlab.com)

mentioned in commit 4054fec5c9

mentioned in commit 4054fec5c9f1e6788efdf7474e032147876938a2

PlasticDigits commented

2026-05-31 14:09:01 +00:00

(Migrated from gitlab.com)

Implementation complete (merged to `main` @ `4054fec`)

Added PAIR_KEY_INDEX (pair_key_idx storage) so QueryMsg::Pairs { start_after, limit } resolves the asset-pair cursor in O(1) via pair_key lookup instead of scanning the full PAIR_INDEX range.

Changes

State: PAIR_KEY_INDEX: Map<&str, u64> with documented invariant (pair_key_idx[key] == idx for every pair_index entry).
Write path: reply_instantiate_pair saves PAIR_KEY_INDEX[key] = count atomically with PAIRS / PAIR_INDEX / PAIR_ADDR_REGISTERED.
Query: query_pairs uses PAIR_KEY_INDEX.may_load → Bound::exclusive (unchanged pagination order / wire format).
Migrate: Factory 1.3.0 backfills pair_key_idx from pair_index (same loop as pair_addr_reg backfill).
Tests: Unit tests in factory/src/contract.rs; integration test_factory_pairs_pagination_start_after in smartcontracts/tests.
Docs: docs/contracts-terraclassic.md, docs/indexer-invariants.md, skills/AGENTS_TERRACLASSIC_GAS.md (rule 18).

Verification checklist

cargo test -p cl8y-dex-factory pair_addr_registry — migrate backfill + unit pagination
cargo test -p cl8y-dex-tests test_factory_pairs_pagination_start_after test_query_pairs_pagination — multi-pair LCD-style pagination
First page (start_after: null) unchanged; second page with valid cursor continues after cursor pair
Invalid start_after returns "start_after pair not found in registry" (no panic)
CreatePair on fresh factory writes pair_key_idx for new pair
Deploy: existing factory wasm ≤ 1.2.0 requires one-time migrate to 1.3.0 before relying on map (fresh instantiations already populated)

Follow-ups

Optional: indexer sync smoke on multi-pair localnet to confirm LCD pagination latency improvement at high page depth (not required for correctness).

@qa-agent-team — please verify the checklist above on main (4054fec) and confirm migrate 1.2.0 → 1.3.0 backfill on any staged factory deployment.

Issue left open pending QA sign-off.

## Implementation complete (merged to `main` @ 4054fec) Added **`PAIR_KEY_INDEX`** (`pair_key_idx` storage) so `QueryMsg::Pairs { start_after, limit }` resolves the asset-pair cursor in **O(1)** via `pair_key` lookup instead of scanning the full `PAIR_INDEX` range. ### Changes - **State:** `PAIR_KEY_INDEX: Map<&str, u64>` with documented invariant (`pair_key_idx[key] == idx` for every `pair_index` entry). - **Write path:** `reply_instantiate_pair` saves `PAIR_KEY_INDEX[key] = count` atomically with `PAIRS` / `PAIR_INDEX` / `PAIR_ADDR_REGISTERED`. - **Query:** `query_pairs` uses `PAIR_KEY_INDEX.may_load` → `Bound::exclusive` (unchanged pagination order / wire format). - **Migrate:** Factory **1.3.0** backfills `pair_key_idx` from `pair_index` (same loop as `pair_addr_reg` backfill). - **Tests:** Unit tests in `factory/src/contract.rs`; integration `test_factory_pairs_pagination_start_after` in `smartcontracts/tests`. - **Docs:** [`docs/contracts-terraclassic.md`](docs/contracts-terraclassic.md), [`docs/indexer-invariants.md`](docs/indexer-invariants.md), [`skills/AGENTS_TERRACLASSIC_GAS.md`](skills/AGENTS_TERRACLASSIC_GAS.md) (rule 18). ### Verification checklist - [ ] `cargo test -p cl8y-dex-factory pair_addr_registry` — migrate backfill + unit pagination - [ ] `cargo test -p cl8y-dex-tests test_factory_pairs_pagination_start_after test_query_pairs_pagination` — multi-pair LCD-style pagination - [ ] First page (`start_after: null`) unchanged; second page with valid cursor continues after cursor pair - [ ] Invalid `start_after` returns `"start_after pair not found in registry"` (no panic) - [ ] `CreatePair` on fresh factory writes `pair_key_idx` for new pair - [ ] **Deploy:** existing factory wasm **≤ 1.2.0** requires one-time migrate to **1.3.0** before relying on map (fresh instantiations already populated) ### Follow-ups - Optional: indexer sync smoke on multi-pair localnet to confirm LCD pagination latency improvement at high page depth (not required for correctness). --- **@qa-agent-team** — please verify the checklist above on `main` (4054fec) and confirm migrate **1.2.0 → 1.3.0** backfill on any staged factory deployment. Issue left **open** pending QA sign-off.

Brouie commented

2026-06-01 05:25:47 +00:00

(Migrated from gitlab.com)

Verified #258 on the live deploy. First, the deploy state: 4054fec5 is an ancestor of our deployed 6b22feb, so this is already live — verified on the current deploy, no redeploy needed.

Headline — the O(1) cursor resolves correctly across the whole book

Read-only optimization, so the bar is correctness, and it holds. On the live factory I ran a full cursor-walk: every pair used as start_after returns the correct next pair, the last pair returns empty, 0 violations across the book. Plus:

page 1 (no cursor, default limit) == full[0:10]
page 2 (start_after = page-1 last pair) == full[10:20] — continues after the cursor, no dupes, no gaps

That's the AC1/2/3 core confirmed live: same pairs, same ascending index order, O(1) key-lookup cursor, and Pair{asset_infos} (single) + Pairs with no cursor both unchanged.

The rest

AC4 — new pairs write the map + migrate backfill:
- New pairs: live — CreatePair (ZINC/CORAL) → code=0, GetPairCount 25→26, the new pair appears as the last entry and is usable as a start_after cursor with no "not found" error → its pair_key_idx entry was written on create. Plus all 25 pre-existing pairs paginate cleanly (each created via the same reply path). Source: reply_instantiate_pair saves PAIR_KEY_INDEX[key]=count atomically with PAIRS/PAIR_INDEX/PAIR_ADDR_REGISTERED.
- Migrate: test migrate_from_1_0_0_backfills_pair_addr_registered_and_pair_key_index + source (the backfill loop) + the live invariant — the cursor-walk proves pair_key_idx[key] == idx for all 26 live pairs, which is exactly the end-state the backfill produces.
AC5 — invalid start_after: live, a non-registered pair (ZINC/CL8Y) returns "start_after pair not found in registry", no panic. Test query_pairs_start_after_uses_pair_key_index.
Functional + attack + your 6 checklist items: all covered — the 4 named tests green on the deploy (migrate_from_1_0_0_backfills_…, query_pairs_start_after_uses_pair_key_index, test_factory_pairs_pagination_start_after, test_query_pairs_pagination), plus live pagination / cursor / invalid / CreatePair. Huge limit → live limit=1000 returns 26 (≤ 30); the clamp-to-30 boundary is unit-tested in calc_limit. PAIR_INDEX retained for the governance batch scans, wire format [AssetInfo;2] unchanged.

Layer honesty

Live 1.2.0 → 1.3.0 migrate transition — NOT staged. Why it isn't a real gap: the migrate is version-agnostic — it gates on ensure_from_older_version(…, "1.3.0") (any < 1.3.0) then runs an unconditional backfill loop (for idx in 0..PAIR_COUNT { PAIR_KEY_INDEX.save(pair_key(info.asset_infos), idx) }). So 1.2.0→1.3.0 executes the identical code that migrate_from_1_0_0_backfills_… exercises — the source version doesn't change the backfill path. And the live cursor-walk confirms the end-state invariant that backfill produces (pair_key_idx[key]==idx, all 26 pairs). Staging a 1.2.0 factory specifically would just re-run that same loop, so I flagged it not-live-staged rather than chase the churn (our deploy is a fresh 1.3.0 instantiation — map populated on instantiate).
O(1)-vs-O(N) is a structural change (PAIR_KEY_INDEX.may_load replacing the PAIR_INDEX.range scan loop) — no numeric before/after query gas, since there's no pre-#258 build deployed (same baseline gap as the rest of the wave). Structural improvement, confirmed correct live; not a measured timing delta.

@PlasticDigits — #258 verified and signed off from my side, no issues found (O(1) cursor correct across the book, invariant holds on all 26 live pairs, migrate backfill test+source-verified). Over to you to close.

And that closes out the contract wave from my side — #251, #254, #255, #256, #257, #258 all have verification notes posted and are ready for your close pass (plus the #254 indexer follow-up + the limit_order_fills per-maker item awaiting your triage call).

Verified #258 on the live deploy. First, the deploy state: `4054fec5` is an ancestor of our deployed `6b22feb`, so this is **already live** — verified on the current deploy, no redeploy needed. ## Headline — the O(1) cursor resolves correctly across the whole book Read-only optimization, so the bar is correctness, and it holds. On the live factory I ran a **full cursor-walk**: every pair used as `start_after` returns the correct *next* pair, the last pair returns empty, **0 violations** across the book. Plus: - page 1 (no cursor, default limit) == `full[0:10]` - page 2 (`start_after` = page-1 last pair) == `full[10:20]` — continues after the cursor, no dupes, no gaps That's the AC1/2/3 core confirmed live: same pairs, same ascending index order, O(1) key-lookup cursor, and `Pair{asset_infos}` (single) + `Pairs` with no cursor both unchanged. ## The rest - **AC4 — new pairs write the map + migrate backfill:** - New pairs: live — `CreatePair` (ZINC/CORAL) → `code=0`, `GetPairCount` 25→26, the new pair appears as the last entry **and** is usable as a `start_after` cursor with no "not found" error → its `pair_key_idx` entry was written on create. Plus all 25 pre-existing pairs paginate cleanly (each created via the same reply path). Source: `reply_instantiate_pair` saves `PAIR_KEY_INDEX[key]=count` atomically with `PAIRS`/`PAIR_INDEX`/`PAIR_ADDR_REGISTERED`. - Migrate: test `migrate_from_1_0_0_backfills_pair_addr_registered_and_pair_key_index` + source (the backfill loop) + the **live invariant** — the cursor-walk proves `pair_key_idx[key] == idx` for all 26 live pairs, which is exactly the end-state the backfill produces. - **AC5 — invalid start_after:** live, a non-registered pair (ZINC/CL8Y) returns `"start_after pair not found in registry"`, no panic. Test `query_pairs_start_after_uses_pair_key_index`. - **Functional + attack + your 6 checklist items:** all covered — the 4 named tests green on the deploy (`migrate_from_1_0_0_backfills_…`, `query_pairs_start_after_uses_pair_key_index`, `test_factory_pairs_pagination_start_after`, `test_query_pairs_pagination`), plus live pagination / cursor / invalid / CreatePair. Huge `limit` → live `limit=1000` returns 26 (≤ 30); the clamp-to-30 boundary is unit-tested in `calc_limit`. `PAIR_INDEX` retained for the governance batch scans, wire format `[AssetInfo;2]` unchanged. ## Layer honesty - **Live 1.2.0 → 1.3.0 migrate transition — NOT staged.** Why it isn't a real gap: the migrate is **version-agnostic** — it gates on `ensure_from_older_version(…, "1.3.0")` (any `< 1.3.0`) then runs an *unconditional* backfill loop (`for idx in 0..PAIR_COUNT { PAIR_KEY_INDEX.save(pair_key(info.asset_infos), idx) }`). So 1.2.0→1.3.0 executes the identical code that `migrate_from_1_0_0_backfills_…` exercises — the source version doesn't change the backfill path. And the live cursor-walk confirms the end-state invariant that backfill produces (`pair_key_idx[key]==idx`, all 26 pairs). Staging a 1.2.0 factory specifically would just re-run that same loop, so I flagged it not-live-staged rather than chase the churn (our deploy is a fresh 1.3.0 instantiation — map populated on instantiate). - **O(1)-vs-O(N) is a structural change** (`PAIR_KEY_INDEX.may_load` replacing the `PAIR_INDEX.range` scan loop) — no numeric before/after query gas, since there's no pre-#258 build deployed (same baseline gap as the rest of the wave). Structural improvement, confirmed correct live; not a measured timing delta. @PlasticDigits — #258 verified and signed off from my side, no issues found (O(1) cursor correct across the book, invariant holds on all 26 live pairs, migrate backfill test+source-verified). Over to you to close. And that closes out the contract wave from my side — #251, #254, #255, #256, #257, #258 all have verification notes posted and are ready for your close pass (plus the #254 indexer follow-up + the `limit_order_fills` per-maker item awaiting your triage call).

PlasticDigits (Migrated from gitlab.com) closed this issue

2026-06-01 05:29:10 +00:00

PlasticDigits commented

2026-08-25 01:55:34 +00:00

(Migrated from gitlab.com)

mentioned in issue #631