在 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。

目标是弄清楚这一点：

每个变量的生命周期（当它可以free从内存中获取时，就像在 Rust 中一样）。并将调用插入free(name)到 AST 中。

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

因此，首先我们必须收集变量声明（然后提升它们，这样我们就知道有多少个局部变量，这样我们就可以创建正确大小的激活记录）。为此，我认为我们只需要遍历 AST 一次即可。

其次，我开始迷失到底要做什么才能完成（1）。首先，创建一个map. 然后从头开始看 AST。对于每个变量，检查它是否在地图中（如果它已被标记/遍历/遇到）。如果它不在地图中，请将其添加到地图中，目前还不知道为什么我们需要这样做。为每个范围创建一个新地图。在每个作用域结束时，释放变量。这就是我现在的处境。

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 论文，并阅读了有关生命周期、借用、可变性和所有权的文档，以及一些编译器组会议笔记和博客文章。但似乎没有人以简单的方式解释在实践中进行借用检查的算法。

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

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

Answer 1

我可以看到几个问题：

1. 我在您的代码中没有看到任何参考语法，因为我没有看到任何“&”。你唯一拥有的就是move。如果你开始脱离这种语法，它就会开始毁掉一切。
2. 您还在javascript 中使用了"reference"和，这很令人困惑，因为它们在 Rust 中意味着相同的东西。"borrow"
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。当引用所指向的变量已被删除时，引用继续存在是错误的。

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

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