Problem with borrow checker that who think a data it's borrow

Hello,
I writing a solver for the game tusmo:
There is a problem: i have to do a lot of computation.
So i tried to write a multi-threaded version of my app to accelerate it
but i run into un issue with the borow check that say

src/main.rs:45:29
   |
41 |     let words_vec = words_vec;
   |         --------- binding `words_vec` declared here
...
45 |             words_ref.push(&words_vec[i]);
   |                             ^^^^^^^^^ borrowed value does not live long enough
...
55 |             words_ref = get_guess_threaded(words_ref);
   |                         ----------------------------- argument requires that `words_vec` is borrowed for `'static`
...
68 | }
   | - `words_vec` dropped here while still borrowed

words_vec dropped at the end of the program so there is no real issue.
I pass ref to threads but thread don't outlive main so i dont' understand what the problem.
There is the app:

#[macro_use]
extern crate lazy_static;
type Sstrs = Vec<&'static str>;
use std::sync::Arc;
use std::sync::Mutex;
use std::thread::available_parallelism;
use std::thread::spawn;

static mut MIN: usize = usize::MAX;
static mut LOCK: Option<Arc<Mutex<()>>> = None;

#[derive(Debug)]
enum State {
    Placed(char),
    Toplace(char),
    Bad(char),
}
use std::usize;

use State::*;

fn main() {
    let args: Vec<_> = std::env::args().collect();
    println!("{:?}", &args);
    let (w_size_s, letter) = if args.len() == 3 {
        (args[1].clone(), args[2].clone())
    } else {
        (input("give w_size\n"), input("first letter\n"))
    };
    let c = letter.chars().nth(0).expect("can't acess letter");
    let mut words = get_words(w_size_s.trim().parse().expect("can't parse messaege"));

    words = words
        .into_iter()
        .filter(|i| (i.chars().nth(0).expect("error") == c))
        .collect();
    let mut words_vec: Vec<Vec<char>> = Vec::with_capacity(words.len());
    for word in &words {
        words_vec.push(word.chars().collect());
    }
    let words_vec = words_vec;
    {
        let mut words_ref: Vec<&Vec<char>> = Vec::with_capacity(words.len());
        for i in 0..words_vec.len() {
            words_ref.push(&words_vec[i]);
        }

        loop {
            for word in &words_ref {
                for letter in *word {
                    print!("{letter}");
                }
                println!();
            }
            words_ref = get_guess_threaded(words_ref);

            let guess = input("the word you try:\n").to_ascii_uppercase();
            let pattern = input("the pattern you got:\n").to_ascii_uppercase();
            let states = transform(&guess, &pattern);

            println!("{:?}", &states);
            apply2(&mut words_ref, states);
            if words_ref.len() == 1 {
                break;
            }
        }
    }
}
fn get_vec_words() -> Sstrs {
    lazy_static! {
        static ref WORDS_FILE: String =
            std::fs::read_to_string("word.txt").expect("can't find the file!");
        static ref WORDS_VEC: Sstrs = WORDS_FILE.split('\n').collect();
    };
    WORDS_VEC.clone()
}
fn get_words(cur: usize) -> Sstrs {
    let mut vec_words = get_vec_words();
    vec_words = vec_words.into_iter().filter(|i| i.len() == cur).collect();
    vec_words
}
fn transform(guess: &str, pattern: &str) -> Vec<State> {
    let mut vec = vec![];

    let guess: Vec<char> = guess.chars().collect();
    let pattern: Vec<char> = pattern.chars().collect();
    for i in 0..guess.len() {
        let c = guess[i];
        print!("{c}");
        let state = match pattern[i] {
            '-' => Placed(c),
            '_' => Toplace(c),
            ' ' => Bad(c),
            '\n' => break,
            a => panic!("wrong pattern {a}"),
        };
        vec.push(state);
    }
    vec
}
fn guess_to_patten(word: &Vec<char>, guess: &Vec<char>) -> Vec<State> {
    let mut arr = [0u8; 26];
    let len = guess.len();
    let mut vec = Vec::with_capacity(len);

    for i in 0..len {
        if word[i] != guess[i] {
            arr[(word[i] as u8 - 65u8) as usize] += 1;
        }
    }
    for i in 0..len {
        let c = guess[i];
        if c == word[i] {
            vec.push(Placed(c));
        } else {
            let index = (guess[i] as u8 - 65u8) as usize;
            if arr[index] > 0 {
                arr[index] -= 1;
                vec.push(Toplace(c));
            } else {
                vec.push(Bad(c));
            }
        }
    }

    vec
}

fn input(msg: &str) -> String {
    println!("{msg}");
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).expect("can't read");
    ret
}
fn get_guess(words: Vec<&Vec<char>>) -> (Vec<char>, usize) {
    unsafe {
        LOCK = Some(Arc::new(Mutex::new(())));
    }
    let mut min_word = words[0];
    let mut i = 0;
    println!("there is {} to compute", words.len());

    'loo: for guess in &words {
        let mut sum = 0;
        for word in &words {
            let mut words2 = words.clone();
            apply2(&mut words2, guess_to_patten(word, guess));
            sum += words2.len();
            unsafe {
                if sum > MIN {
                    i += 1;
                    println!("i:{i} aborted");
                    continue 'loo;
                }
            }
        }
        println!("i:{i} sum:{sum}");
        unsafe {
            if sum < MIN {
                let _lock = LOCK
                    .as_ref()
                    .expect("truc")
                    .lock()
                    .expect("failed to aquire lock");
                //println!("{}", &guess);
                if sum < MIN {
                    MIN = sum;
                }
                min_word = guess;
            }
        }
        i += 1;
    }
    unsafe { (min_word.to_owned().to_owned(), MIN) }
}
fn get_guess_threaded<'a>(words: Vec<&'static Vec<char>>) -> Vec<&'static Vec<char>> {
    unsafe {
        LOCK = Some(Arc::new(Mutex::new(())));
    }

    let nb_cpu: usize = available_parallelism().expect("can't get cpu").into();
    let chunks: Vec<_> = words.chunks(words.len() / nb_cpu).collect();
    //let chunks: Vec<_> = chunks.iter().map(|i| i.to_vec()).collect();
    let mut handles = vec![];
    for i in 0..nb_cpu {
        let temp = chunks[i].to_vec();
        let handle = spawn(move || get_guess(temp));

        handles.push(handle);
    }
    let joins: Vec<_> = handles
        .into_iter()
        .map(|i| i.join().expect("can't join"))
        .collect();
    let min = joins
        .iter()
        .min_by(|i, j| i.1.cmp(&j.1))
        .expect("can' get min");
    let msg = min.0.clone();
    println!("{:?}", &msg);
    words
}
fn filter_vec<T>(words: &mut Vec<&Vec<char>>, closur: T)
where
    T: Fn(&Vec<char>) -> bool,
{
    let mut real_len = words.len();
    let mut i = 0;
    while i < real_len {
        if closur(words[i]) {
            i += 1;
        } else {
            real_len -= 1;
            words[i] = words[real_len];
        }
    }
    words.truncate(real_len);
}

fn apply2(words: &mut Vec<&Vec<char>>, key: Vec<State>) {
    for i in 0..key.len() {
        match key[i] {
            Placed(c) => {
                let closur = move |v: &Vec<char>| -> bool { v[i] == c };
                filter_vec(words, closur);
            }
            Toplace(c) => {
                let closur = move |v: &Vec<char>| -> bool { v[i] != c };
                filter_vec(words, closur);
            }
            Bad(c) => {
                let closur = move |v: &Vec<char>| -> bool { v[i] != c };
                filter_vec(words, closur);

                let count = key
                    .iter()
                    .filter(|j| match &j {
                        Placed(l) => *l == c,
                        Toplace(l) => *l == c,
                        Bad(_) => false,
                    })
                    .count();
                let closur = move |v: &Vec<char>| -> bool {
                    let mut chars = 0;
                    for ch in v {
                        if *ch == c {
                            chars += 1;
                        }
                    }
                    chars == count
                };
                filter_vec(words, closur);
            }
        }
    }
}

Your use of statics is very concerning. A general rule of thumb is that if you need mutable access to a static variable, you are doing something wrong (unless maybe you need to deal with FFI or something). I assume this is just something that happened while you tried debugging your problem.

words_vec is dropped at the end of main and a reference to it is not 'static. So you can't capture it in a closure you pass to thread::spawn, which requires the function to be valid in 'static. That means the closure can only capture owned data (moving it in the process) or 'static references. The standard library provides thread::scope as an alternative to spawn that relaxes the 'static requirement. You should try to remodel your program to use thread::scope instead of thread::spawn.

2 Likes

Threads do outlive main by a tiny amount; the variables of main() are dropped before running threads are aborted. But there is another solution, thread::spawn() isn't compatible with borrowing in general, but thread::scope() is -- you can borrow any variables in a scoped thread, not just main()'s.

You'll also need to remove the 'statics from your types -- data doesn't ever become 'static at run time (unless you use Box::leak(), which is the wrong tool for this job), and you don't need 'static if you used scoped threads.

Another option to look at is the library rayon: it is designed to do computations like you want but lets you do it using a parallel iterator interface, rather than manually spawning threads yourself, and is also capable of splitting the work as-needed as the computation proceeds, rather than using an up-front division into equal size chunks (which may lead to waiting for one chunk to finish because it took longer).

This is roundabout and hazardous; you can do much better by putting the data in the Mutex, initializing it at compile time, and not using static mut at all:

static MIN: Mutex<Usize> = Mutex::new(usize::MAX);

Just use MIN.lock() and you have exclusive access. (You could also use a std::sync::atomic::AtomicUsize with the fetch_min() operation, which would be even more efficient for this case.)

4 Likes

Thanks you for all your awnser i will try to make my app work.
For the static int: i use this way of doing it because i have to read it every time in th nested loop, so i tried a something costless for reading with an external lock.
The usage of rayon seems very cool i think i will keep my way of doing it then i will make a 2.0 with it .
Have a good day !

I see, but this is not sound -- you may not even read a value without taking the lock. Unsafe code is tricky and you should avoid writing your own (use appropriate libraries instead) until you know more about Rust's fundamental rules.

If you want maximum performance in this situation, use AtomicUsize. This is the fastest possible way to check and update a shared value. (But it might be even faster to avoid sharing the value, by having each thread compute its own minimum and only compare across threads when you assemble the results.)

3 Likes