связанный код main.rs
fn main() {
println!("{:?}",mimey::binary_search("zsh"));
}
lib.rs
// MIME is a [(&str, &str); 670]
fn strcmp(x: &[u8], z: &[u8]) -> isize {
if x.is_empty() || z.is_empty() {
return 0;
}
if x[0] != z[0] {
// clamp (dont want to skip an index now do i)
return ((x[0] as isize) - z[0] as isize).clamp(-1, 1);
}
strcmp(&x[1..], &z[1..])
}
// it segfaults. somehow
fn bins(k: &[u8], ci: usize) -> Option<&str> {
let sp = strcmp(k, MIME[ci].0.as_bytes());
if sp == 0 {
return Some(MIME[ci].1);
}
if ci == 0 || ci == MIME.len() - 1 {
return None;
}
bins(k, ci.checked_add_signed(sp)?)
}
pub fn binary_search(k: &str) -> Option<&str> {
bins(k.as_bytes(), MIME.len() / 2)
}
имя:
Linux r0 6.9.1-0-edge #1-Alpine SMP PREEMPT_DYNAMIC
ржавчина -vV:
rustc 1.78.0 (9b00956e5 2024-04-29) (Alpine Linux 1.78.0-r0)
binary: rustc
commit-hash: 9b00956e56009bab2aa15d7bff10916599e3d6d6
commit-date: 2024-04-29
host: x86_64-alpine-linux-musl
release: 1.78.0
LLVM version: 17.0.6
лдб:
* thread #1, name = 'mimey', stop reason = signal SIGSEGV: address not mapped to object (fault address: 0x7fffff7fe9a8)
frame #0: 0x0000555555563d01 mimey`mimey::bins::hee7c9bb096833bc5(k=(data_ptr = "", length = 1), ci=1) at lib.rs:706
703 }
704
705 // it segfaults. somehow
-> 706 fn bins(k: &[u8], ci: usize) -> Option<&str> {
707 let sp = strcmp(k, MIME[ci].0.as_bytes());
708 if sp == 0 {
709 return Some(MIME[ci].1);
MIME
определяется в lib.rs
. Я понятия не имею, почему k
кажется пустым.
Это часть библиотеки угадывания мимов, которую я писал ради развлечения.
Можете попробовать побегать с --release
? Я считаю, что в этом случае оптимизация должна иметь возможность преобразовать хвостовую рекурсию в итерацию и предотвратить переполнение стека (если это действительно является причиной проблемы).
Подсказка: стандартная библиотека уже предоставляет слайс::binary_search_by_key, который вы можете использовать.
Насколько глубок стек вызовов при сегфолте?
Ваш «binary_search
» не выполняет двоичный поиск, поэтому практически любое достаточно большое значение MIME переполнит стек отладочной сборкой.. Обратите внимание, что ci
увеличивается на 1 при каждой рекурсии, при двоичном поиске оставшееся пространство будет разделено на 2, а не вычтено 1.
Недостаточно информации для 100%, но, похоже, в вашем коде есть логическая ошибка, которая может привести к бесконечному циклу, который приведет к переполнению стека, а затем к SIGSEGV.
Imagine Mime определяется так:
const MIME: [(&'static str, &'static str); 4] =
[("000", "?"), ("002", "?"), ("006", "?"), ("007", "?")];
тогда binary_search("005")
никогда не выйдет, переполнит стек и выкинет SIGSEGV. В частности, вы входите в состояние, когда bins(k, 2)
звонит bins(k, 3)
, который звонит bins(k, 2)
.
Не зная точных значений MIME, невозможно быть уверенным, но я подозреваю, что именно это и происходит. Добавьте строку sp
перед проверкой sp == 0
, и вы увидите чередующиеся значения 1 и -1.
Это, а также ОП «binary_search» на самом деле представляет собой линейный поиск, начинающийся с середины.
Вероятно, вы переполняете стек. Как определяется
MIME
?