Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Possible soundness bug in borrow-ck #56477

Closed
rmanoka opened this issue Dec 3, 2018 · 2 comments
Closed

Possible soundness bug in borrow-ck #56477

rmanoka opened this issue Dec 3, 2018 · 2 comments
Labels
A-NLL Area: Non-lexical lifetimes (NLL) NLL-sound Working towards the "invalid code does not compile" goal

Comments

@rmanoka
Copy link

rmanoka commented Dec 3, 2018

Hello!
Here's a snippet of code which I believe should not compile. The program compiles and exhibits undefined behaviour (sometimes garbled output, sometimes seg-fault, and sometimes the correct output!) on recent nightlies, and beta.

fn run() -> Result<u64, Error> {
    use serde_json::Value;
    use std::collections::BTreeMap;

    let mut stdin = std::io::stdin();
    let mut out: BTreeMap<&str, BTreeMap<&str, f64>> = BTreeMap::new();
    out.insert("hello", BTreeMap::new());
    out.insert("world", BTreeMap::new());

    let iter = serde_json::Deserializer::from_reader(&mut stdin)
            .into_iter::<BTreeMap<String, Value>>();

    for map in iter {
        let map = map?;

        let mut cb = |key: &str, map: BTreeMap<String, Value>| {
            out.get_mut(key).map(|out| {

                map.keys().for_each(|k| {
                    if let Some(val) = out.get_mut(k.as_str()) {
                        *val += 1.0;
                    } else {
                        out.insert(k.as_str(), 1.0);
                    }
                })

            });
        };

        if map.len() % 2 == 0 {
            cb("hello", map);
        } else {
            cb("world", map);
        }
    }

    for (key, map) in out {
        println!("Map {}", key);
        for (key, val) in map {
            println!("key={} val={}", key, val);
        }
    }
    Ok(0)
}


fn main() {
    run();
}

struct Error;
use std::error::Error as StdError;
impl<E: StdError> From<E> for Error {
    fn from(err: E) -> Self {
        println!("{}", err);
        Error
    }
}

The crux is in run() function, where I tried to construct a BTreeMap<&str, BTreeMap<&str, f64>>. However, it is being constructed from inside a for loop via references which clearly do not last beyond one iteration.

Here are a few different outputs obtained on the same input:

Map hello
key=num1 val=1
key=PB val=2
key=num1 val=2
key=PB val=1
key=PBval=1
key=num1 val=2
key=PB val=1
Map world

Output 2 (on same input)

Map hello
key=num1 val=1
key=PBval=2
key=num1 val=2
key=PBval=1
key=PBval=1
key=num1 val=2
key=PBval=1
Map world

Note that in both cases, we have evidence of memory-UB because the println! statement clearly has a space between the key and the val, so output like: key=PBval=1 shouldn't be happening.

The input and the source code as a Cargo is available here. To test: cargo run < test.json from the root of repository.

A couple of observations that may be relevant:

  1. Bug is present on 1.32.0-nightly (21f268495 2018-12-02), (9fefb6766 2018-11-13), and current beta with 2018 edition. However, 2015 editions, and the current stable compilers report error as we would expect. See playground.

  2. The callback closure is necessary to create the bug. If I throw the code inside the closure outside, and do necessary cleanups, the borrowck indeed complains.

  3. two-level map is also necessary: if I had used BTreeMap<&str, f64> (but similar code), then again, the checker complains about the incorrect lifetimes.

This is a contrived example, but is derived out of a reasonably common use-case (of processing a db and keeping some cumulative stats). I would be happy to help in figuring/fixing the bug here.

@matthewjasper matthewjasper added A-NLL Area: Non-lexical lifetimes (NLL) NLL-sound Working towards the "invalid code does not compile" goal NLL-priority labels Dec 3, 2018
@matthewjasper
Copy link
Contributor

Somewhat minimised:

fn once<S, T, U, F: FnOnce(S, T) -> U>(f: F, s: S, t: T) -> U {
    f(s, t)
}

pub fn dangle() -> &'static [i32] {
    let other_local_arr = [0, 2, 4];
    let local_arr = other_local_arr;
    let mut out: &mut &'static [i32] = &mut (&[1] as _);
    once(|mut z: &[i32], mut out_val: &mut &[i32]| {
        z = &local_arr; // Comment out this line for an error!
        *out_val = &local_arr;
    }, &[] as &[_], &mut *out);
    *out
}

fn main() {
    println!("{:?}", dangle());
}

https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=cb02ee113da324dc1a2cfa90cb2cdc6d

It appears that we don't propagate enough closure bounds - I'll see if I can get a fix for this done quickly.

bors added a commit that referenced this issue Dec 4, 2018
…pnkfelix

Propagate all closure requirements to the caller

Closes #56477

This should be backported to 1.32 if it doesn't make the cut.

r? @pnkfelix
cc @nikomatsakis
@pietroalbini
Copy link
Member

The fix for this will be included in 1.31.0.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-NLL Area: Non-lexical lifetimes (NLL) NLL-sound Working towards the "invalid code does not compile" goal
Projects
None yet
Development

No branches or pull requests

3 participants