How Candidate Pagination Works in Karukan's IME Engine

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, 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 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:

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:

// 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, which maintains the candidate list during active conversion sessions. The conversion logic in 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 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 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. 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 within the CandidateList implementation. The engine state management using this logic appears in karukan-im/src/core/engine/state.rs, with conversion handling and UI presentation logic in 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}