Database Schema

[llogiq]

Since I'd like to use Diesel with a SQLite database to store the data, I need a database schema that can do the following:

• insert and lookup type composition relation (i.e. Type_A ⊂ Type_B) – generics are a complication here
• store and query the method call graph – traits and specialization are the big problems for this

[cramertj]

I'd be interested in helping out with this if I can get a bit more info on how you'd like things organized. I'm familiar with Postgres and SQLite but haven't yet had an excuse go in-depth with Diesel.

[llogiq]

Great! This issue is more about the design side of things and probably requires more understanding of the Rust HIR than of database work (with or without Diesel).

You can look at the (very sparse) internal compiler docs at Manish's github page: https://manishearth.github.io/rust-internals-docs/std/index.html – look for the rustc::hir::Expr_ enum, especially the Call and MethodCall variants. Also the Generics struct. This is the model we'll have to...well, model.

[cramertj]

How stable is the HIR at the moment? I know there are lots of changes at the moment going on with respect to the MIR-- will any of these have a noticeable impact on NSA's internal representation? In other words, how stable can the schema be at this point in time?

[Manishearth]

HIR changes slightly around once a week.

[llogiq]

I don't think that will be a problem for our schema – Generics aren't likely to change much (until we get HKTs that is – but then I'll gladly extend the schema to make it work 😄)

[cramertj]

Sounds good. I'll try and get a first attempt posted here sometime tomorrow night (I'm in PST).

[cramertj]

Looking at rustc::hir::Expr_ I see that there are separate expressions for ExprCall and ExprMethodCall. Aside from trait objects calls (which are an admittedly confusing special case) is there any reason to represent method calls (which can be resolved to UFCs) separately from normal function calls?

[llogiq]

Yes. Plain Calls are always statically dispatched, whereas MethodCalls may be dynamically dispatched (if self is a trait object).

[cramertj]

Sorry, maybe my question was unclear. I was trying to ask if MethodCall should be kept separate in the case that self is not a trait object (which I believe we can detect fairly easily). It seems like the semantics for handling trait objects will be different from all other function calls (including non-trait object method calls), which could all be resolved statically.

For example, you list in the README several goals including determining if a function may panic, is pure, is recursive, or allocates memory. Following the call graph to determine any of these properties is relatively simple in the case of statically dispatched functions, but much more complicated in the case of trait objects, where it would involve pointer analysis to determine all the different types a given trait object could possibly point to.

Because of this, the handling of statically dispatched methods is going to be much more similar to that of plain function calls than that of methods on trait objects.

[llogiq]

Yes. Luckily, a) dynamic dispatch isn't all that common in Rust and b) for most intents & purposes it's sufficient to look up all possible impls and see if their methods panic, allocate, call back or whatever.

This also means we'll need to store trait impls for later lookup.

[cramertj]

Obviously very early, but here's what I've got so far.

The visualizer didn't quite get my foreign keys right, so I'll just explain them here:

Paths foreign key to (nullable) parent paths to create a hierarchical structure (mem, for instance, would have the parent std, which would have no parent).

Function calls can be static or not, and this decides whether or not they have a foreign key to a function implementation or a trait function.

Function call arguments are foreign keyed to type, the function call instance, and the patkind (I wasn't sure what information from rustc_front::hir::PatKind was relevant, so I haven't yet created this).

Function implementations, a path foreign key, a name, and (if they are an implementation of a trait function) a foreign key to the relevant trait and type. Eventually, this is where I forsee we will attach attributes such as whether or not a function can panic, which can then be propagated upwards after all the data has been entered.

Traits currently just have an id, name and path.

Trait bounds are a many-to-many linking traits to their children (i.e. id of Eq -> id of PartialEq).

Trait functions are the functions that need to be implemented in order to satisfy a trait.

The trait implementation lists is another many-to-many linking traits to the types that implement them.

Finally, types have a path, name, and other associated metadata.

Let me know your thoughts-- am I headed in the right direction? Should I be sticking more closely to the exact representation used in HIR? Does anything not make sense?

[cramertj]

I left this out in my description, but obviously there will also be a many-to-many piece describing what functions are called by what other functions.

[llogiq]

@cramertj Just a heads-up – I renamed the project to metacollect due to some people feeling uneasy about the old name. No need to stoke emotions.

[cramertj]

@llogiq Yeah, I saw the Reddit discussion. Some very strong opinions out there... That aside, it seems like a good move as it's a far more descriptive name.