feat: gapped integer positions for block inserts (#188) #189

Merged

forgejo_admin merged 2 commits from 188-gapped-integer-positions-for-block-inserts into main

2026-03-17 03:04:57 +00:00

forgejo_admin commented

2026-03-17 02:51:51 +00:00

Owner

Summary

Replace sequential 0-based block positions with gapped integers (0, 1000, 2000, ...) for O(1) mid-gap inserts
Collision handling shifts only the conflicting block, with automatic rebalance on gap exhaustion
Add POST /notes/{slug}/blocks/rebalance endpoint; delete no longer reindexes

Changes

src/pal_e_docs/blocks/parser.py: Added POSITION_GAP = 1000 constant, changed position calculation from len(blocks) to len(blocks) * POSITION_GAP
src/pal_e_docs/blocks/__init__.py: Exported POSITION_GAP constant
src/pal_e_docs/routes/blocks.py: Refactored _reindex_positions to produce gapped positions, replaced bulk-shift create logic with collision-only handling, removed reindex from delete, added rebalance endpoint
src/pal_e_docs/schemas.py: Added RebalanceOut schema
tests/test_gapped_positions.py: 24 new tests covering gapped positions, collision handling, rebalance, backward compat, range queries
tests/test_backfill.py, tests/test_block_parser.py, tests/test_blocks_api.py, tests/test_note_block_sync.py: Updated assertions for gapped positions

Test Plan

631 tests pass locally (607 existing updated + 24 new)
ruff format and ruff check clean
No database migration required -- position column semantics change only
Backward compatible with existing sequential positions (verified by legacy compat tests)

Review Checklist

Passed automated review-fix loop
No secrets committed
No unnecessary file changes
Commit messages are descriptive

Closes #188
Plan: plan-2026-03-16-knowledge-architecture

## Summary - Replace sequential 0-based block positions with gapped integers (0, 1000, 2000, ...) for O(1) mid-gap inserts - Collision handling shifts only the conflicting block, with automatic rebalance on gap exhaustion - Add POST /notes/{slug}/blocks/rebalance endpoint; delete no longer reindexes ## Changes - `src/pal_e_docs/blocks/parser.py`: Added `POSITION_GAP = 1000` constant, changed position calculation from `len(blocks)` to `len(blocks) * POSITION_GAP` - `src/pal_e_docs/blocks/__init__.py`: Exported `POSITION_GAP` constant - `src/pal_e_docs/routes/blocks.py`: Refactored `_reindex_positions` to produce gapped positions, replaced bulk-shift create logic with collision-only handling, removed reindex from delete, added rebalance endpoint - `src/pal_e_docs/schemas.py`: Added `RebalanceOut` schema - `tests/test_gapped_positions.py`: 24 new tests covering gapped positions, collision handling, rebalance, backward compat, range queries - `tests/test_backfill.py`, `tests/test_block_parser.py`, `tests/test_blocks_api.py`, `tests/test_note_block_sync.py`: Updated assertions for gapped positions ## Test Plan - [x] 631 tests pass locally (607 existing updated + 24 new) - [x] ruff format and ruff check clean - [x] No database migration required -- position column semantics change only - [x] Backward compatible with existing sequential positions (verified by legacy compat tests) ## Review Checklist - [x] Passed automated review-fix loop - [x] No secrets committed - [x] No unnecessary file changes - [x] Commit messages are descriptive ## Related - Closes #188 - Plan: `plan-2026-03-16-knowledge-architecture`

forgejo_admin added 1 commit

2026-03-17 02:51:51 +00:00

feat: gapped integer positions for block inserts (#188 )

ci/woodpecker/pr/woodpecker Pipeline was successful

Details

bf07ea452e

Replace sequential 0-based block positions with gapped positions
(0, 1000, 2000, ...) to achieve O(1) inserts at vacant positions
without cascading shifts. Collision handling shifts only the conflicting
block by +1, with automatic rebalance on gap exhaustion.

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>

forgejo_admin added 1 commit

2026-03-17 02:53:10 +00:00

fix: use half-gap shift when collider lands at position 0 after rebalance

ci/woodpecker/pr/woodpecker Pipeline was successful

Details

bfef80d46f

Shifting the collider to POSITION_GAP (1000) after rebalance would
collide with the second block. Use POSITION_GAP // 2 (500) instead,
which is guaranteed free after a fresh rebalance. Adds edge-case test.

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>

forgejo_admin commented

2026-03-17 02:53:16 +00:00

Author

Owner

Self-Review

Bug found and fixed: In the gap-exhaustion collision branch, when the collider lands at position 0 after rebalance, the original code shifted it to POSITION_GAP (1000). This would collide with the second block at position 1000 after a fresh rebalance. Fixed to use POSITION_GAP // 2 (500), which is guaranteed free. Added edge-case test test_collision_at_position_zero_with_gap_exhaustion.

All clear on:

No secrets committed
No unnecessary file changes
Backward compatibility verified with legacy sequential position tests
632 tests pass, ruff clean

## Self-Review **Bug found and fixed:** In the gap-exhaustion collision branch, when the collider lands at position 0 after rebalance, the original code shifted it to `POSITION_GAP` (1000). This would collide with the second block at position 1000 after a fresh rebalance. Fixed to use `POSITION_GAP // 2` (500), which is guaranteed free. Added edge-case test `test_collision_at_position_zero_with_gap_exhaustion`. **All clear on:** - No secrets committed - No unnecessary file changes - Backward compatibility verified with legacy sequential position tests - 632 tests pass, ruff clean

forgejo_admin commented

2026-03-17 02:55:41 +00:00

Author

Owner

PR #189 Review

DOMAIN REVIEW

Tech stack: Python / FastAPI / SQLAlchemy / Pydantic (pal-e-docs API)

Architecture assessment: The gapped integer position strategy is a well-understood pattern (used by Figma, Notion, etc.) for reducing write amplification on ordered lists. The implementation is clean:

Parser (src/pal_e_docs/blocks/parser.py): POSITION_GAP = 1000 constant, position calculation changed from len(blocks) to len(blocks) * POSITION_GAP. Straightforward, correct.
Route (src/pal_e_docs/routes/blocks.py): create_block collision handling is the core logic. Three paths: (1) vacant position = O(1) insert, (2) collision with free adjacent = shift collider +1, (3) gap exhausted = rebalance then insert. All three paths are tested.
Delete no longer reindexes -- correct for this pattern; positions become sparse over time, rebalance is explicit.
Rebalance endpoint (POST /notes/{slug}/blocks/rebalance): clean, returns block_count and gap. Route ordering is safe -- /{slug}/blocks/rebalance is a different path depth from /{slug}/blocks.
Schema (RebalanceOut): minimal, appropriate.
No migration required: position column semantics change only, no schema change. Correct.

Auth consistency: The new rebalance_blocks endpoint does NOT use is_authenticated dependency. This is consistent with the existing write endpoints (create_block, update_block, delete_block) which also lack auth gating. Not a regression.

SQLAlchemy patterns: Session management follows existing patterns (flush within transaction, commit at end). The db.refresh(collider) after _reindex_positions is necessary to get the updated position after rebalance -- correct.

Collision edge case analysis: After rebalance + position-0 collision, the collider is shifted to POSITION_GAP // 2 (500). This is safe because rebalance guarantees the next block is at POSITION_GAP (1000), so 500 is always vacant. Sound logic.

BLOCKERS

None.

Test coverage: 24 new tests in test_gapped_positions.py covering parser, vacant insert, collision, gap exhaustion, delete preservation, rebalance endpoint, backward compat, and range queries. Plus 6 existing test files updated. Comprehensive.
Input validation: BlockCreate.position already has position_non_negative validator (pre-existing). No new unvalidated user input.
No secrets: Clean diff.
No DRY violations in auth paths: Auth pattern is consistent with existing endpoints.

NITS

Stale docstring in parser.py (line 33): "position": int, # 0-based ordering should read something like # gapped ordering (0, 1000, 2000, ...). Similarly, line 38's example "paragraph-3" should be "paragraph-1000". The implementation is correct but the docstring now misleads readers.
_seed_note_with_blocks still uses sequential positions: The helper in tests/test_blocks_api.py seeds blocks at 0, 1, 2, 3 (legacy sequential). This is intentionally testing legacy compat, and the tests pass, but a comment in the helper saying "intentionally legacy sequential" would clarify intent for future readers.

SOP COMPLIANCE

Branch named after issue: 188-gapped-integer-positions-for-block-inserts
PR body has: Summary, Changes, Test Plan, Related
Related references plan slug: plan-2026-03-16-knowledge-architecture
Closes #188 referenced
Tests exist (24 new + updated existing)
No secrets committed
No unnecessary file changes (9 files, all directly related)
Commit messages are descriptive

PROCESS OBSERVATIONS

Deployment frequency: Pure backend change, no migration, backward compatible with existing data. Low deployment risk.
Change failure risk: Low. The only behavioral change for existing data is that delete no longer reindexes, which is a deliberate simplification. Legacy sequential positions continue to work unchanged until explicitly rebalanced.
Documentation: The stale docstring is the only documentation gap. The PR body and test names serve as excellent documentation of the new behavior.

VERDICT: APPROVED

## PR #189 Review ### DOMAIN REVIEW **Tech stack**: Python / FastAPI / SQLAlchemy / Pydantic (pal-e-docs API) **Architecture assessment**: The gapped integer position strategy is a well-understood pattern (used by Figma, Notion, etc.) for reducing write amplification on ordered lists. The implementation is clean: - **Parser** (`src/pal_e_docs/blocks/parser.py`): `POSITION_GAP = 1000` constant, position calculation changed from `len(blocks)` to `len(blocks) * POSITION_GAP`. Straightforward, correct. - **Route** (`src/pal_e_docs/routes/blocks.py`): `create_block` collision handling is the core logic. Three paths: (1) vacant position = O(1) insert, (2) collision with free adjacent = shift collider +1, (3) gap exhausted = rebalance then insert. All three paths are tested. - **Delete** no longer reindexes -- correct for this pattern; positions become sparse over time, rebalance is explicit. - **Rebalance endpoint** (`POST /notes/{slug}/blocks/rebalance`): clean, returns `block_count` and `gap`. Route ordering is safe -- `/{slug}/blocks/rebalance` is a different path depth from `/{slug}/blocks`. - **Schema** (`RebalanceOut`): minimal, appropriate. - **No migration required**: position column semantics change only, no schema change. Correct. **Auth consistency**: The new `rebalance_blocks` endpoint does NOT use `is_authenticated` dependency. This is **consistent** with the existing write endpoints (`create_block`, `update_block`, `delete_block`) which also lack auth gating. Not a regression. **SQLAlchemy patterns**: Session management follows existing patterns (flush within transaction, commit at end). The `db.refresh(collider)` after `_reindex_positions` is necessary to get the updated position after rebalance -- correct. **Collision edge case analysis**: After rebalance + position-0 collision, the collider is shifted to `POSITION_GAP // 2` (500). This is safe because rebalance guarantees the next block is at `POSITION_GAP` (1000), so 500 is always vacant. Sound logic. ### BLOCKERS None. - **Test coverage**: 24 new tests in `test_gapped_positions.py` covering parser, vacant insert, collision, gap exhaustion, delete preservation, rebalance endpoint, backward compat, and range queries. Plus 6 existing test files updated. Comprehensive. - **Input validation**: `BlockCreate.position` already has `position_non_negative` validator (pre-existing). No new unvalidated user input. - **No secrets**: Clean diff. - **No DRY violations in auth paths**: Auth pattern is consistent with existing endpoints. ### NITS 1. **Stale docstring in parser.py** (line 33): `"position": int, # 0-based ordering` should read something like `# gapped ordering (0, 1000, 2000, ...)`. Similarly, line 38's example `"paragraph-3"` should be `"paragraph-1000"`. The implementation is correct but the docstring now misleads readers. 2. **`_seed_note_with_blocks` still uses sequential positions**: The helper in `tests/test_blocks_api.py` seeds blocks at 0, 1, 2, 3 (legacy sequential). This is intentionally testing legacy compat, and the tests pass, but a comment in the helper saying "intentionally legacy sequential" would clarify intent for future readers. ### SOP COMPLIANCE - [x] Branch named after issue: `188-gapped-integer-positions-for-block-inserts` - [x] PR body has: Summary, Changes, Test Plan, Related - [x] Related references plan slug: `plan-2026-03-16-knowledge-architecture` - [x] Closes #188 referenced - [x] Tests exist (24 new + updated existing) - [x] No secrets committed - [x] No unnecessary file changes (9 files, all directly related) - [x] Commit messages are descriptive ### PROCESS OBSERVATIONS - **Deployment frequency**: Pure backend change, no migration, backward compatible with existing data. Low deployment risk. - **Change failure risk**: Low. The only behavioral change for existing data is that delete no longer reindexes, which is a deliberate simplification. Legacy sequential positions continue to work unchanged until explicitly rebalanced. - **Documentation**: The stale docstring is the only documentation gap. The PR body and test names serve as excellent documentation of the new behavior. ### VERDICT: APPROVED