javascript - 难以在 JavaScript 中实现简化的借用检查器

Question

出于所有意图和目的，我有一堆具有这种 AST 结构的函数和函数调用。它是一个函数数组。

const ast = [
  {
    type: 'function',
    name: 'doX',
    inputs: [
      {
        name: 'x',
        type: 'String'
      }
    ],
    calls: [
      {
        type: 'call',
        name: 'do123',
        args: [
          {
            type: 'literal',
            value: 123
          },
          {
            type: 'reference',
            value: 'x'
          }
        ]
      },
      {
        type: 'call',
        name: 'test',
        args: [
          {
            type: 'borrow',
            value: 'x'
          }
        ],
        block: [
          {
            type: 'call',
            name: 'set',
            args: [
              {
                type: 'reference',
                value: 'a'
              },
              {
                type: 'move',
                value: {
                  type: 'call',
                  name: 'multiply',
                  args: [
                    {
                      type: 'borrow',
                      value: 'x'
                    },
                    {
                      type: 'literal',
                      value: 2
                    }
                  ]
                }
              }
            ]
          },
          {
            type: 'call',
            name: 'doFoo',
            args: [
              {
                name: 'a',
                value: {
                  type: 'literal',
                  value: 'foo'
                }
              },
              {
                name: 'b',
                value: {
                  type: 'reference',
                  value: 'x'
                }
              }
            ]
          }
        ]
      }
    ]
  }
]

这将是这样的结果:

function doX(x) {
  do123(123, x)
  test(x) {
    set(a, multiply(x, 2))
    doFoo('foo', a)
  }
}

现在忘记我也在尝试处理词法范围(即嵌套函数)这一事实，因为这可能只会使这个问题变得不必要地复杂。

另请注意，一切皆函数，因此您需要set(foo, 'bar') 来实例化一个变量。尽管它以命令式方式执行，但它不是函数式语言 AST。这只是为了简化问题，所以不会有各种复杂的类型。这个例子只有函数和调用。

另请注意，我们在其中有borrow(“引用”的几种类型之一)。您可以拥有借用(共享所有权)或移动(转让所有权)，借用可以标记为可变或不可变(默认值不)。目标是重现 Rust 所做的事情，让这个迷你/演示“编译器”完全按照 Rust 对借用检查器所做的事情进行操作。

此外，我们在该函数中创建了一个新的局部作用域，并定义了变量 a。

目标是弄清楚这一点:

The lifetime of each variable (when it can be freed from memory, like in Rust). And to insert a free(name) call into the AST.

使用 Rust 借用检查器，它会检查变量的所有者和生命周期，以便判断它是否被正确使用以及何时超出范围。

所以首先我们必须收集变量声明(然后提升它们，这样我们就知道有多少局部变量，这样我们就可以创建合适大小的激活记录)。为此，我认为我们只需要向下遍历 AST 一次。

其次，我开始迷失了究竟要做什么才能完成 (1)。首先，创建一个 map 。然后从头开始遍历 AST。对于每个变量，检查它是否在 map 中(是否已被标记/遍历/遇到)。如果它不在 map 中，请将其添加到 map 中，还不知道为什么我们需要这样做。为每个范围创建一个新 map 。在每个范围的末尾，释放变量。这就是我所处的位置。

process(ast)

function process(ast) {
  ast.forEach(fxn => {
    let stack = []
    let locals = { count: 0, vars: {} }
    fxn.inputs.forEach(input => {
      locals.vars[input.name] = locals.count++
    })
    fxn.calls.forEach(call => {
      handleCall(call, locals)
    })

    function handleCall(call, locals) {
      if (call.name == 'set') {
        let name = call.args[0].value
        locals.vars[name] = locals.count++
      }
      if (call.block) {
        call.block.forEach(nestedCall => {
          handleCall(nestedCall, locals)
        })
      }
    }
  })
}

现在的问题是，如何添加借用检查，以便知道在哪里插入 free(name)？

process(ast)

function process(ast) {
  ast.forEach(fxn => {
    let stack = []
    let locals = { count: 0, vars: {} }
    fxn.inputs.forEach(input => {
      locals.vars[input.name] = {
        id: locals.count++,
        status: '?'
      }
    })
    fxn.calls.forEach(call => {
      handleCall(call, locals)
    })

    function handleCall(call, locals) {
      if (call.name == 'set') {
        let name = call.args[0].value
        let local = locals.vars[name] = {
          id: locals.count++
        }
        let value = call.args[1]
        if (value.type == 'move') {
          local.status = 'owner'
        } else if (value.type == 'borrow') {
          local.status = 'borrow'
        } else {
          // literal
        }
        if (value.value.type == 'call') {
          handleCall(value.value, locals)
        }
      } else {
        
      }
      if (call.block) {
        let newLocals = {}
        call.block.forEach(nestedCall => {
          handleCall(nestedCall, newLocals)
        })
      }
    }
  })
}

我开始迷失在杂草中，只见树木不见森林。到目前为止，我已经阅读了很多关于 Rust 中的借用检查器的信息，但不知道它是如何实现的。我查看了 Polonius 的源代码，阅读了大部分 Oxide paper ，并阅读有关生命周期、借用、可变性和所有权的文档，以及一些编译器组 session 记录和 blog posts .但似乎没有人以简单的方式解释在实践中进行借用检查的算法。

寻求有关此特定示例的一些帮助，以帮助我开始研究 JavaScript 中的借用检查器的算法。想知道是否可以概述算法应该做什么，以便弄清楚变量是否被正确借用以及何时可以释放它们，使用这个或稍微复杂一点的想出的例子。

不过，在我真正编写算法之前，我需要更好地了解算法应该做什么，它应该如何工作。这就是这个问题的内容。如果您知道如何编写它的演示，那就太好了!但只是对步骤进行更深入的解释(而不是掩盖关键步骤)也会有所帮助。

Answer 1

我可以看到一些问题:

1. 我在您的代码中没有看到任何引用语法，因为我没有看到任何“&”。你唯一拥有的就是移动。如果您开始摆脱这种语法，它就会开始毁掉一切。
2. 您还在您的 javascript 中同时使用了 "reference" 和 "borrow"，这令人困惑，因为它们在 Rust 中的含义相同。
3. 您没有doX 参数的类型，这意味着您无法正确处理该变量，因为它可能是一个移动，这可能会导致调用函数的范围问题.
4. b 是如何成为对 x 的引用的？

---

Rust/理解所有权:
https://doc.rust-lang.org/book/ch04-00-understanding-ownership.html

这是上面链接的概要:

对于所有这些，当我说“变量”时，我的意思是“使用堆的变量”。另外，请随意将“引用”替换/解释为“借用”。

变量在其作用域结束时被丢弃，如果它仍然有效。丢弃意味着释放内存。范围是从引入变量到最后一次使用它的时间。如果对该变量的任何引用仍在范围内，则为错误。

默认情况下，变量是移动而不是复制。

复制变量时，会创建一个新的唯一变量并复制数据。这会创建一个全新的自变量。

当一个变量移动到另一个变量时，初始变量被标记为无效并且不能再使用。 (这种内存管理方式的一个很大的折衷。)新变量指向与旧变量相同的堆数据。如果在标记为无效后使用初始变量，则为错误。

可以通过以下三种方式之一将变量分配给另一个变量来移动:

1. 直接。例如x = y
2. 通过设置函数参数的值。例如f(x)
3. 通过函数返回它，例如x = f()

如果您将一个变量传递给另一个函数并希望在该调用之后继续使用它，那么该函数必须通过返回它来“归还它”(与预期的另一个主要偏差)。这只是 (2) 后跟 (3)，例如x = f(x).

可以为变量创建两种类型的引用:不可变(默认)和可变。 引用只是指向变量而不是数据。

您可以对一个变量有无限数量的不可变引用。您只能有一个可变引用，并且前提是范围内没有其他类型的引用(包括不可变引用)。

当引用超出范围时，它们不会调用drop。当引用指向的变量已被删除时，引用继续存在是错误的。

---

如果我要实现这个，我会按顺序执行以下操作:

• 让范围发挥作用。这是从第一次引入变量或引用到最后一次使用它的时间。请注意，同一 block 中的范围可能重叠也可能不重叠。
• 开始复制工作
• 开始移动工作，包括下降方面。检测超出有效性的范围。如上所示，对于移动类型 (1)、(2)、(3)，分阶段执行此操作。
• 让不可变引用工作，如果尝试更改变量则出错，如果范围超出有效性则出错。
• 让可变引用工作，如果范围内有任何其他引用则出错，如果范围超出有效性则出错。