在 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（“references”的几种类型之一）。您可以拥有 borrow（股份所有权）或 move（转让所有权），借入可以标记为 mutable 或否（默认为否）。目标是重现 Rust 所做的事情，让这个 mini/demo “编译器”完全按照 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。对于每个变量，检查它是否在地图中（如果它已经 marked/traversed/encountered 了）。如果它不在地图中，请将其添加到地图中，还不知道为什么我们需要这样做。为每个范围创建一个新地图。在每个范围的末尾，释放变量。这就是我所在的位置。

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, and read through the docs on lifetimes, borrowing, mutability, and ownership, as well as some of the compiler group meeting notes and blog posts。但是 none 似乎以一种简单的方式解释了一种在实践中进行借用检查的算法。

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

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

Answer 1

我可以看到一些问题：

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

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

以上内容的概要link:

对于所有这些，当我说“变量”时，我的意思是“使用堆的变量”。另外，请随时 substitute/interpret “参考”作为“借用”。

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

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

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

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

一个变量可以移动，方法是通过以下三种方式之一将其分配给另一个变量：

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

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

可以为一个变量创建两种类型的引用：不可变（默认）和可变。 reference 只是指向变量而不是数据。

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

当引用超出范围时，它们不会调用 drop。当引用指向的变量已 dropped.

时，引用继续存在是错误的

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

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

在 JavaScript 中难以实施简化的借用检查器

Difficulty implementing a simplified borrow-checker in JavaScript

javascript

algorithm

types

rust

borrow-checker