For all intents and purposes, I have a bunch of functions and function calls with this sort of AST structure. It's an array of functions.
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'
}
}
]
}
]
}
]
}
]
That would be the result of this:
function doX(x) {
do123(123, x)
test(x) {
set(a, multiply(x, 2))
doFoo('foo', a)
}
}
Forget now the fact that I am also trying to handle lexical scopes (i.e. nested functions), because that will probably just make this question unnecessarily complicated.
Also note that everything is a function, so you have set(foo, 'bar') to instantiate a variable. Although, it executes in an imperative fashion, it's not a functional language AST. This is just to simplify the question, so there's not all kinds of complicated types getting in the way. There are just functions and calls for this example.
Notice too that we have borrow in there (one of a few types of "references"). You can have either a borrow (share ownership) or a move (transfer ownership), and the borrow can be marked mutable or not (defaults to not). The goal is to reproduce what Rust does, to have this mini/demo "compiler" do exactly what Rust does with the borrow-checker.
Also, we have created a new local scope in that function, and defined the variable a.
The goal is to figure out this:
The lifetime of each variable (when it can be
freed from memory, like in Rust). And to insert afree(name)call into the AST.
With the Rust borrow-checker, it checks for the owner and lifetime of the variable so it can tell if it is used properly and when it falls out of scope.
So first we must gather the variable declarations (and just hoist them, so we know how many local variables there are, so we can create the activation record at the right size). To do this I think we just need to traverse down the AST one time.
Second, I start to get lost of what exactly to do to accomplish (1). First, create a map. Then go through the AST from the beginning. For each variable, check if it is in the map (if it has been marked/traversed/encountered yet). If it is not in the map, add it to the map, don't really know why we need to do this yet. Create a new map for each scope. At the end of each scope, free the variable. This is sort of where I'm at.
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)
})
}
}
})
}
Now the question is, how do you do add the borrow-checking so that you know where to insert the 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)
})
}
}
})
}
I start to get lost in the weeds, don't see the forest for the trees. I have read a lot about the borrow-checkr in Rust so far but don't know how it's implemented. I have looked through the source code of Polonius, read through most of the 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. But none seem to explain in a simple way an algorithm for doing the borrow checking in practice.
Looking for some help on this specific example to get me started on an algorithm for a borrow-checker in JavaScript. Wondering if one could outline what the algorithm should do in order to figure out if the variables are properly borrowed and when they can be freed, using this or a slightly more complicated came-up-with example.
Before I can really write the algorithm though, I need to have a better sense of what the algorithm should be doing, how it should work. Which is what this question is about. If you know how to write a demo of it, that would be great! But just having a deeper explanation of steps (and not glossing over key steps) will be helpful too.
{count: 0, vars: {}}also may be it will be helpful rust-lang.github.io/polonius – Daniil Loban