oils-for-unix / oils

Oils is our upgrade path from bash to a better language and runtime. It's also for Python and JavaScript users who avoid shell!
http://www.oilshell.org/
Other
2.84k stars 157 forks source link

[mycpp] add assign/define annotations to CFG #2022

Closed melvinw closed 3 months ago

melvinw commented 3 months ago

This commit updates control_flow_pass to annotate the control flow graph with variable assignments and allocations. The comments in visit_assignment_expr and get_variable_name contain more information about the approach. Another commit will build on this to by adding a basic dataflow program to track aliases.

@andychu have a look? The rest of the the dataflow stuff will be built on top of this, so I want to make sure the ideas are clear and captured well in the source so others can extend in the future. Happy to do a few rounds on this to get it right.

andychu commented 3 months ago

Oh sorry somehow I thought this one was a draft still, let me look

melvinw commented 3 months ago

Oh it was until like an hour ago :)

andychu commented 3 months ago

Oops one thing I kinda forgot about and should have emphasized is that I disabled a test you added!

https://github.com/oilshell/oil/commit/caf3322aae2d9da3005ac1d0e1cbb8f06bf9faef

I think there were 3 files, and one of them changed because of this with GC crash that a user reported.

And actually that case is tricky and might affect the control flow graph?


Oh yeah this is the bug - the problem was GC rooting for context managers, which is kind of an annoying extra special case

https://github.com/oilshell/oil/issues/1986


I wonder if it's time to re-enable the tests, with this change?

andychu commented 3 months ago

I think that was sort of at an awkward moment, I didn't know how to regenerate the souffle once I changed mycpp/examples/...

andychu commented 3 months ago

Oh yeah now I remember that the testdata is here .. (this could also go in mycpp/testdata I think)

$ head -n 20 testdata/control-flow-graph/*/*
==> testdata/control-flow-graph/control_flow/cf_edge.facts <==
examples.control_flow.ExceptDemo        0       1
examples.control_flow.ExceptDemo        1       2

Does this commit affect those files?

The comments seem good, but it may help me get it to see a minimal example in the tests of assign/define ? Or does it need more work before that?

melvinw commented 3 months ago

Oh, huh. I thought I checked in a script to generate that test data, but I don't see it in the repo. I'll fix the existing ones (which shouldn't be affected by this change), add a test that illustrates the new stuff, and check in a script to re-generate all of them when needed

melvinw commented 3 months ago

I think I don't have the full picture, but it seems like reasonable code to make progress on

Yeah, this full picture is probably still hard to grok because up to this point we've just been generating inputs for the souffle programs. The next commit will start adding actual souffle that will make use of these inputs. Hopefully that will make the flow more obvious

andychu commented 3 months ago

I think in terms of aliasing, "variable" is sort of an ambiguous term. What's a variable? It can mean a few things

I like to use terms like place/location, and reference

I think "place" comes from Rich Hickey -- it's a location where a value can be stored.

Rust has "place expressions", and Oils has value.Place which is a (name, stack frame) pair

https://doc.rust-lang.org/reference/expressions.html#place-expressions-and-value-expressions

Also there is this idea of "reference vs referent" ... the referent is the place

https://en.wikipedia.org/wiki/Referent

I guess that is mainly for List and Dict and Class.

For integers and bools aliasing doesn't apply, so we don't need to handle them at all, right?

andychu commented 3 months ago

Or there could be some existing terms I don't know about ...

But I guess in an assignment, the place is always on the left, and the reference is on the right

x = 42  # x evaluates to  a place here

y = x  # x evaluates to a value here, like 42
melvinw commented 3 months ago

Ahhh, I see what you mean now! I actually use "Reference" in the the next datalog PR 😅 Now I'm not sure why I didn't connect the two... We should spend some time hashing out the distinction between place/referent and references over in that PR once I rebase it tonight