Код ржавчины (без опасности) продолжает сбоить (musl)

связанный код 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 кажется пустым. Это часть библиотеки угадывания мимов, которую я писал ради развлечения.

Вероятно, вы переполняете стек. Как определяется MIME?

cafce25 03.06.2024 20:49

Можете попробовать побегать с --release? Я считаю, что в этом случае оптимизация должна иметь возможность преобразовать хвостовую рекурсию в итерацию и предотвратить переполнение стека (если это действительно является причиной проблемы).

Dogbert 03.06.2024 20:57

Подсказка: стандартная библиотека уже предоставляет слайс::binary_search_by_key, который вы можете использовать.

cafce25 03.06.2024 21:19

Насколько глубок стек вызовов при сегфолте?

Carson 03.06.2024 21:37

Ваш «binary_search» не выполняет двоичный поиск, поэтому практически любое достаточно большое значение MIME переполнит стек отладочной сборкой.. Обратите внимание, что ci увеличивается на 1 при каждой рекурсии, при двоичном поиске оставшееся пространство будет разделено на 2, а не вычтено 1.

cafce25 03.06.2024 21:55
Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
0
5
56
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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» на самом деле представляет собой линейный поиск, начинающийся с середины.

cafce25 03.06.2024 21:59

Другие вопросы по теме