1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
//! Helper body for the `find_implementations` MCP tool.
//!
//! Mirrors the structure of `helpers_calls.rs`: a full-partition scan over
//! `implementations_by_trait` with a `memmem` case-sensitive substring filter,
//! bounded by `scan_cap = limit * 8`, with optional language filtering via the
//! in-RAM `MapCache`.
use std::ops::Bound;
use rmcp::ErrorData as McpError;
use rmcp::model::CallToolResult;
use super::cursor::Cursor;
use super::helpers::{SEARCH_LIMIT_DEFAULT, SEARCH_LIMIT_MAX, json_result};
use super::types_impls::{
FindImplementationsParams, FindImplementationsResponse, ImplementationHit,
};
/// Body of the `find_implementations` MCP tool. Performs a full-partition scan over the
/// `implementations_by_trait` Fjall partition with a case-sensitive substring filter on
/// `trait_name`, returning up to `limit` hits with optional language filtering.
pub(super) fn run_find_implementations(
idx: Option<&crate::index::IndexDb>,
params: FindImplementationsParams,
cache: &super::MapCache,
) -> Result<CallToolResult, McpError> {
let limit = params
.limit
.unwrap_or(SEARCH_LIMIT_DEFAULT)
.min(SEARCH_LIMIT_MAX) as usize;
let Some(idx) = idx else {
return json_result(&FindImplementationsResponse {
trait_name: params.trait_name,
total: 0,
total_is_partial: false,
budgeted: false,
hits: Vec::new(),
next_cursor: None,
});
};
let cursor_bytes = params
.cursor
.as_ref()
.map(|c| c.decode_fjall())
.transpose()?;
// Build the finder once for the full-partition substring scan.
let finder = memchr::memmem::Finder::new(params.trait_name.as_bytes());
let lower: Bound<Vec<u8>> = match cursor_bytes.as_deref() {
Some(k) => Bound::Excluded(k.to_vec()),
None => Bound::Unbounded,
};
let scan_cap = limit.saturating_mul(8).max(2_000);
let mut hits: Vec<ImplementationHit> = Vec::with_capacity(limit.min(64));
// Parallel to `hits`: the Fjall key for each emitted hit, so a token budget can re-anchor
// the cursor to the last KEPT hit instead of the last scanned one.
let mut hit_keys: Vec<Vec<u8>> = Vec::with_capacity(limit.min(64));
let mut total: usize = 0;
let mut total_is_partial = false;
let mut last_emitted_key: Option<Vec<u8>> = None;
let mut has_more = false;
let mut matched: usize = 0;
for guard in idx
.implementations_by_trait
.range::<Vec<u8>, _>((lower, Bound::Unbounded))
{
let (k, _) = guard
.into_inner()
.map_err(|e| McpError::internal_error(format!("impl index iter: {e}"), None))?;
let Some((trait_name, impl_type, rel, start_byte)) =
crate::index::keys::parse_impl_by_trait(&k)
else {
continue;
};
// Case-sensitive substring filter on trait_name.
if finder.find(trait_name.as_bytes()).is_none() {
continue;
}
// Language filter: look up the file's L1 blob in the in-RAM cache.
// Applied after the substring filter — filtered entries don't count toward scan_cap.
if let Some(lang_filter) = params.language.as_deref() {
let l1_lang = cache.by_path.get(&rel).map(|l1| l1.language.as_str());
if l1_lang != Some(lang_filter) {
continue;
}
}
total += 1;
matched += 1;
if hits.len() < limit {
// Resolve start_row / start_col from the stored Implementation in the L1 blob.
let (start_row, start_col) = resolve_impl_row_col(cache, &rel, start_byte);
hits.push(ImplementationHit {
path: rel,
trait_name,
impl_type,
start_row,
start_col,
});
hit_keys.push(k.to_vec());
last_emitted_key = Some(k.to_vec());
} else {
has_more = true;
}
if matched >= scan_cap {
total_is_partial = true;
break;
}
}
let next_cursor = if has_more {
last_emitted_key.as_deref().map(Cursor::encode_fjall)
} else {
None
};
// Apply the token budget. When it drops trailing hits, re-anchor the cursor to the last
// KEPT hit's Fjall key so the next page resumes exactly after it. A no-op when
// `max_tokens` is None or every hit fit.
let budget = super::budget::apply_budget(hits, params.max_tokens);
let (hits, budgeted, next_cursor) = if budget.budgeted {
let kept = budget.items.len();
let cursor = hit_keys.get(kept - 1).map(|k| Cursor::encode_fjall(k));
(budget.items, true, cursor)
} else {
(budget.items, false, next_cursor)
};
json_result(&FindImplementationsResponse {
trait_name: params.trait_name,
total,
total_is_partial,
budgeted,
hits,
next_cursor,
})
}
/// Look up `(start_row, start_col)` for an `Implementation` record from the in-RAM L1
/// cache. Falls back to `(0, 0)` when the cache entry is absent or the matching
/// `Implementation` record isn't found (e.g. an older blob predating the field).
///
/// `start_byte` is the sole discriminant: an impl/class block has a unique byte offset
/// within a file, so no additional fields are needed.
fn resolve_impl_row_col(
cache: &super::MapCache,
rel: &crate::path::RelPath,
start_byte: u32,
) -> (u32, u32) {
let Some(l1) = cache.by_path.get(rel) else {
return (0, 0);
};
// Match by start_byte alone: an `impl` / class definition has a unique byte offset
// within a file, so start_byte is a sufficient key into l1.implementations. The
// index writer encodes exactly one record per (path, start_byte) pair, making
// trait_name and impl_type redundant discriminants here.
if let Some(imp) = l1
.implementations
.iter()
.find(|i| i.start_byte == start_byte)
{
// start_row is 0-based in the blob; emit 1-based for line numbers per editor convention.
(imp.start_row + 1, imp.start_col)
} else {
(0, 0)
}
}