如何创建一个可接受可变引用并且其生命周期超出当前属性的属性？

Question

基本上我有这个结构体（省略了不必要的细节）：

struct Environment<'a> {
  parent: Option<&'a mut Environment<'a>>
}

这个结构体实际上并不是我想要的，因为我希望持有对parent引用的结构可以比其所持有的引用更长久。

我可以想象这可以通过更高阶的生命周期量化来实现，例如：

struct Environment {
  parent: <'a> Option<&'a mut Environment>
}

但是很明显，上面的代码不起作用（至少在 rustc 1.44 之前是这样）。

我需要这样做的原因是我正在尝试实现一个类型检查器，可以处理以下（示例）代码：

let x = 1  // parent environment
let f(y) = {
  // current environment
  x + y
}

当我在函数f内部进行符号查找时，比如查找x，我会首先在当前环境中进行查找，如果没有找到，则会在父环境中递归查找。在对函数f进行类型检查后，f的环境将被丢弃，但父环境应该仍然保留，以便可以对下一条语句进行类型检查。

希望这足够清晰地说明为什么我需要让包含它的结构体持有父引用并使其超出结构体的生命周期。

总之，问题是：如何声明一个结构体内的属性，它可以持有自身类型的可变引用，并且可以超出自身的生命周期？如果不可能，还有什么其他方案可以考虑？

- Wong Jia Hau

Answer 1

The declaration

struct Environment<'a> {
  parent: Option<&'a mut Environment<'a>>
}

并不意味着parent不能比结构体存在的时间更长。实际上，结构体上的生命周期参数总是指向比结构体本身存在更长的生命周期。

你面临的问题类似，但更加微妙：你写了&'a mut Environment<'a>，在这个类型中：

• Environment<'a>表示Environment内部可变引用对于'a是有效的。这意味着Environment必须在生命周期'a内创建。
• &'a mut表示该引用仅在'a时有效，这意味着其引用必须在'a之前创建。

这两个要求几乎相互矛盾，因此它们几乎不可能满足（除非'a: 'static）。解决这个问题的常规方法是避免过度约束生命周期，使用单独的生命周期参数。

struct Environment<'r, 'e> {
  parent: Option<&'r mut Environment<'e, ???>>
}

然而，在您的情况下，这种方法行不通，因为存在更深层次的问题，由<'e, ???>所示：通过具有&mut引用链，我们允许持有这些引用的人修改该链的任何级别中的任何部分，并且特别是将这些引用替换为不同的引用。但为了做到这一点，他们需要将其替换为具有相同生命周期的东西--而这个结构的形状是一个嵌套的越来越长的生命周期链，因此例如，获取两个Environment并突变以交换它们的位置是可能的，但会违反生命周期。

不过有一种方法是使用结构内部的不可变引用，虽然不像您想要的那样灵活。为了演示这一点，这里是一个简单的作用域检查器：

use std::collections::HashSet;
enum Tree {
    Definition(String),
    Use(String),
    Block(Vec<Tree>),
}

struct Environment<'r> {
    parent: Option<&'r Environment<'r>>,
    symbols: HashSet<String>,
}

impl<'r> Environment<'r> {
    fn contains(&self, x: &str) -> bool {
        self.symbols.contains(x) || self.parent.filter(|p| p.contains(x)).is_some()
    }
}

fn empty() -> Environment<'static> {
    Environment {
        parent: None,
        symbols: HashSet::new(),
    }
}

fn check<'r>(env: &'r mut Environment<'_>, tree: &Tree) -> Result<(), String> {
    use Tree::*;
    match tree {
        Definition(symbol) => {
            env.symbols.insert(symbol.clone());
            Ok(())
        }
        Use(symbol) => {
            if !env.contains(symbol) {
                return Err(symbol.clone());
            }
            Ok(())
        }
        Block(statements) => {
            let mut block_env = Environment {
                parent: Some(env),
                symbols: HashSet::new(),
            };
            for statement in statements.iter() {
                check(&mut block_env, statement)?;
            }
            Ok(())
        }
    }
}

#[test]
fn tests() {
    use Tree::*;
    assert_eq!(
        check(
            &mut empty(),
            &Block(vec![Definition("x".to_owned()), Use("x".to_owned())])
        ),
        Ok(())
    );
    assert_eq!(
        check(
            &mut empty(),
            &Block(vec![Definition("x".to_owned()), Use("y".to_owned())])
        ),
        Err("y".to_owned())
    );
    assert_eq!(
        check(
            &mut empty(),
            &Block(vec![
                Definition("x".to_owned()),
                Block(vec![Use("x".to_owned())])
            ])
        ),
        Ok(())
    );
}

请注意声明。

struct Environment<'r> {
    parent: Option<&'r Environment<'r>>,
    symbols: HashSet<String>,
}

包含Option<&'r Environment<'r>>，这正是我之前告诉你不要做的。 Environment<'r>不会过多地限制生命周期的原因在于不可变引用的引用类型是协变的，这意味着如果我们想要一个Environment<'r>，只要'e比'r更长，我们就可以接受一个Environment<'e>。 然而，对于可变引用，需要不变性：它们必须完全匹配。 （这是因为对于不可变引用，数据只能从中流出，但是对于可变引用，数据可以流入或流出，因此如果存在生命周期不匹配，则不安全。）

上述内容的一个警告是，在更高级别的环境中不能进行突变，如果正在执行类型推断（以便使用者可以确定声明的类型），则可能需要通过内部可变性来进行突变，即使没有可变引用也可以突变。

以下是修改后使用内部可变性工具std :: cell :: RefCell的示例。 请注意，此代码实际上没有使用额外的灵活性，但是您可以使用显式的运行时检查.symbols.borrow_mut()操作来修改任何父项的symbols。

use std::cell::RefCell;
use std::collections::HashSet;

enum Tree {
    Definition(String),
    Use(String),
    Block(Vec<Tree>),
}

struct Environment<'r> {
    parent: Option<&'r Environment<'r>>,
    symbols: RefCell<HashSet<String>>,
}

impl<'r> Environment<'r> {
    fn contains(&self, x: &str) -> bool {
        self.symbols.borrow().contains(x) || self.parent.filter(|p| p.contains(x)).is_some()
    }
}

fn empty() -> Environment<'static> {
    Environment {
        parent: None,
        symbols: RefCell::new(HashSet::new()),
    }
}

fn check<'r>(env: &'r Environment<'_>, tree: &Tree) -> Result<(), String> {
    use Tree::*;
    match tree {
        Definition(symbol) => {
            env.symbols.borrow_mut().insert(symbol.clone());
            Ok(())
        }
        Use(symbol) => {
            if !env.contains(symbol) {
                return Err(symbol.clone());
            }
            Ok(())
        }
        Block(statements) => {
            let block_env = Environment {
                parent: Some(env),
                symbols: RefCell::new(HashSet::new()),
            };
            for statement in statements.iter() {
                check(&block_env, statement)?;
            }
            Ok(())
        }
    }
}

#[test]
fn tests() {
    use Tree::*;
    assert_eq!(
        check(
            &mut empty(),
            &Block(vec![Definition("x".to_owned()), Use("x".to_owned())])
        ),
        Ok(())
    );
    assert_eq!(
        check(
            &mut empty(),
            &Block(vec![Definition("x".to_owned()), Use("y".to_owned())])
        ),
        Err("y".to_owned())
    );
    assert_eq!(
        check(
            &mut empty(),
            &Block(vec![
                Definition("x".to_owned()),
                Block(vec![Use("x".to_owned())])
            ])
        ),
        Ok(())
    );
}

- Kevin Reid