# How Candidate Pagination Works in Karukan's IME Engine

> Discover how Karukan's IME engine uses cursor-based pagination to efficiently manage conversion candidates. Explore wrap-around navigation with fixed-size pages and no memory reallocation.

- Repository: [Hitoshi Togasaki/karukan](https://github.com/togatoga/karukan)
- Tags: internals
- Published: 2026-07-03

---

**Karukan's IME engine implements lightweight candidate pagination through a cursor-based `CandidateList` struct that divides conversion candidates into fixed-size pages (default 9) and provides wrap-around navigation without reallocating memory.**

Karukan is an open-source input method editor (IME) written in Rust that manages Japanese text conversion through a specialized pagination system. The engine stores conversion candidates in a `CandidateList` structure defined in [`karukan-im/src/core/candidate.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/candidate.rs), which handles page calculation, cursor movement, and selection logic. This architecture ensures efficient memory usage while presenting candidates to macOS and fcitx5 front-ends.

## Core Architecture of CandidateList

The `CandidateList` struct in [`karukan-im/src/core/candidate.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/candidate.rs) serves as the central data structure for managing conversion candidates. It maintains three key fields: a vector of `Candidate` structs, an integer cursor pointing to the currently selected candidate, and a configurable **page size** (defaulting to 9).

Each `Candidate` struct stores the converted text, its original reading, a source label (e.g., "🤖 AI" or "📚 辞書") for the auxiliary bar, and an optional description displayed on the right side of the candidate entry. The pagination system never reallocates this vector during navigation—it simply moves the cursor index.

## Pagination Mechanics and Page Navigation

The pagination system operates through deterministic arithmetic calculations that map the linear cursor position to paginated views. The default **page size** of 9 candidates (`DEFAULT_PAGE_SIZE`) matches the UI layout constraints of supported front-ends.

The `CandidateList` implements several utility methods for page calculation:

- **`page_size()`** – Returns the configured page size (default 9)
- **`current_page()`** – Calculates the zero-based page index using `self.cursor.checked_div(self.page_size).unwrap_or(0)`
- **`total_pages()`** – Computes total pages via `self.candidates.len().div_ceil(self.page_size)`
- **`page_start()`** – Determines the first candidate index of the current page as `current_page() * page_size`
- **`page_candidates()`** – Returns a slice `&self.candidates[start..end]` where `end` is calculated as `(start + self.page_size).min(self.candidates.len())`

### Cursor Positioning Within Pages

The `page_cursor()` method calculates the relative cursor position within the current page by computing `self.cursor - self.page_start()`. This allows the UI to highlight the correct item regardless of which page is displayed, maintaining visual consistency during navigation.

### Page-Level Navigation Methods

For moving between pages, the implementation provides wrap-around behavior:

- **`next_page()`** – Advances the cursor to the first candidate of the next page (`page_start() + page_size`), wrapping to index 0 when exceeding the last page
- **`prev_page()`** – Moves the cursor to the first candidate of the previous page, wrapping to the last page when moving past the first

## Candidate Selection and Linear Navigation

Users interact with candidates through two distinct navigation paradigms: page-relative selection and linear traversal.

The **`select_on_page(idx)`** method enables direct selection by converting a 1-based page index to an absolute cursor position using the formula `page_start() + idx - 1`. This allows users to select candidates by their visible position in the UI window.

For sequential browsing, **`move_next()`** and **`move_prev()`** provide linear navigation across the entire candidate vector with wrap-around behavior at both ends. These methods simply increment or decrement the cursor by 1, wrapping from the last candidate to the first (and vice versa).

## Implementation Examples

Here is how to instantiate a candidate list and navigate through pages:

```rust
use karukan_im::core::candidate::{CandidateList, Candidate};

/// Build a candidate list from a vector of strings.
let items = (1..=20).map(|i| format!("item{}", i));
let mut list = CandidateList::from_strings(items);

assert_eq!(list.total_pages(), 3);          // 9 + 9 + 2 items
assert_eq!(list.current_page(), 0);
assert_eq!(list.page_candidates().len(), 9);

// Move to the second page and pick the 2nd candidate on that page.
list.next_page();                          // cursor → first item of page 2 (index 9)
list.select_on_page(2);                    // selects item 11
assert_eq!(list.selected_text(), Some("item11"));

// Cycle through pages – the cursor wraps back to the first page.
list.next_page(); // → page 3 (2 items)
list.next_page(); // wraps to page 1
assert_eq!(list.current_page(), 0);

```

Linear navigation with wrap-around works as follows:

```rust
// Linear navigation with wrap‑around
let mut list = CandidateList::from_strings(["a", "b", "c"]);
assert_eq!(list.selected_text(), Some("a"));

list.move_next();          // → "b"
list.move_next();          // → "c"
list.move_next();          // wraps → "a"
assert_eq!(list.selected_text(), Some("a"));

```

## Integration with the IME Engine

The `CandidateList` integrates with the broader engine through [`karukan-im/src/core/engine/state.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/engine/state.rs), which maintains the candidate list during active conversion sessions. The conversion logic in [`karukan-im/src/core/engine/conversion.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/engine/conversion.rs) utilizes these pagination methods to present candidates to front-end interfaces and handle user selection events.

Comprehensive unit tests in [`karukan-im/src/core/engine/tests/candidates.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/engine/tests/candidates.rs) verify pagination boundaries, page navigation, and wrap-around behavior, ensuring deterministic performance across the supported platforms.

## Summary

- The `CandidateList` struct in [`karukan-im/src/core/candidate.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/candidate.rs) manages candidates with a default page size of 9 items
- Pagination uses integer division and ceiling operations to calculate page boundaries without memory reallocation
- Navigation supports both page-based (`next_page`, `prev_page`) and linear (`move_next`, `move_prev`) traversal with wrap-around at boundaries
- The cursor-based approach ensures O(1) navigation time regardless of the total number of candidates

## Frequently Asked Questions

### What is the default page size for candidate pagination in Karukan?

The default page size is **9 candidates**, defined by the `DEFAULT_PAGE_SIZE` constant in [`karukan-im/src/core/candidate.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/candidate.rs). This value aligns with the display constraints of the macOS and fcitx5 front-ends, which render up to nine candidates in a single candidate window.

### How does Karukan handle navigation when reaching the end of candidate pages?

The pagination system implements **wrap-around behavior**. When `next_page()` is called on the last page, the cursor wraps to the first page (index 0). Conversely, `prev_page()` from the first page wraps to the starting index of the last page, creating a continuous navigation loop.

### Where is the candidate pagination logic implemented in the codebase?

Core pagination logic resides in [`karukan-im/src/core/candidate.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/candidate.rs) within the `CandidateList` implementation. The engine state management using this logic appears in [`karukan-im/src/core/engine/state.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/engine/state.rs), with conversion handling and UI presentation logic in [`karukan-im/src/core/engine/conversion.rs`](https://github.com/togatoga/karukan/blob/main/karukan-im/src/core/engine/conversion.rs).

### Does Karukan reallocate memory when navigating between candidate pages?

No. The system maintains a stable vector of candidates and only updates the cursor index during navigation. This **cursor-based pagination** ensures that page transitions require only integer arithmetic operations, making the process O(1) and memory-efficient regardless of the candidate list size.