vmware / differential-datalog Goto Github PK

• use distinct_total instead of distinct where possible.
• don't convert external collections to Variables in the nested scope (variables use a lot of memory)

Basic Datalog (Leonid)

• Invoke user callbacks on output relations
• Generate code for ground facts
• Framework for (incremental) input/output testing of Datalog programs
• More examples of interesting Datalog programs
  • span computation.
  • souffle examples.
• Tutorial on writing and testing Datalog programs (so far, wrote a mini-tutorial on adding new tests, but need a more detailed one introducing language basics and workflow)
• FFI
• Performance/memory tests
  • Tools for datalog program memory profiling
• Update main ddlog executable

FTL (Mihai)

• Generate Datalog schema from JSON
• Generate input and output adapters
• Adapters for external C functions invoked from FTL
• Test workload

Future improvements

• Debugging facility
• CLI interface to ddlog
• RPC interface to ddlog

Also, the error message is not very good.

error: file.dl:211:234-211:235: Argument _method must be specified in this context
 
RBasic_MethodLookup(_simplename, _descriptor, _type, _method) :- RDirectSuperclass(_type, _supertype), RBasic_MethodLookup(_simplename, _descriptor, _supertype, _method), not RBasic_MethodImplemented(_simplename, _descriptor, _type, _).

Currently one can have a type that depends on an undefined identifier

typedef t = x

... so that we can write x << 5 vs x << 32'd5

TODO list for DDlog/OVN integration:

• generate DDlog schema from OVSDB schema.
  • This can be done mostly automatically from OVSDB schema files; however we will need some way to specify which OVSDB relations are inputs and which our outputs (can they be both?). Should we add those as annotations to the OVSDB schema or just specify them as command line arguments to the schema conversion tool?
• port rules from northd.c to northd.dl
• create data sets for standalone testing of northd.dl (i.e., outside of OVN)
• generate runtime OVSDB input/output adapters for DDlog
• create OVN infrastructure to test northd.dl against northd.c on a live system
• integration testing
• scale testing (and CPU/memory profiling)
• suppress Rust warnings
• catch up with latest OVN master
• documentation
• fix remaining test failures
• test C and DDlog at the same time if DDlog is enabled in the build
• clean up DDlog patches

One should be able to escape symbols such as {, }, $, | in an interpolated string.

Also, there should be a way for users to specify the conversion to strings for user-defined types.
This will probably require string concatenation at the very least.

At the moment, constants can be simulated by 0-arity functions. The main downside is the need to use parenthesis every time a constant is referenced. Also, function names start with lower-case letters, whereas it is customary to capitalize constant names.

Use conventional C syntax instead of Verilog syntax for integer literals

E.g., parts of Compile.hs assume this

This is a little tricky, as we use different representations depending on the size of a bit vector (BitUint or uXX) depending on its width. Bit slicing may involve conversion between these representations

Implement a proper type inference algorithm based on unification. The current ad hoc implementation is hacky and fragile. No idea why I did not do the right thing straight away...

At the moment, the compiler refuses to convert type variables to strings.

This can be fixed by:

1. Infering that a function expects a type variable to be printable
2. In the generated Rust function, add the Display trait for this function
3. Whenever the function is called, check that its concrete arguments satisfy the trait
4. Implement Display trait for types that have a user-defined 2String method

• string interning
• use arrangements for relations that are used as the first atom in multiple rules (a special case of common subexpression elimination)
• use Box or Arc type for Value to save memory
• avoid redundant cloning in the generated code
• use per-key distinct when possible
• extract "by-self" arrangement from distinct
• 32-bit weights
• use unreachable() instead of panic!() in Compile.hs (see TODO in Compile.hs)

https://github.com/frankmcsherry/differential-dataflow/issues/113

Currently every test in tests/datalog_tests downloads and compiles its own Rust dependencies, as well as makes its own copy of differential_dataflow, taking a couple of gigabytes of space per test. There must be a way to share common parts across all tests.

• Add examples
• Add semantic constraints
• Ref and & syntax
• Standard library reference

goldenVsFiles behaves funny when more than one files has changed: it first complains about the first file only. Deleting the corresponding .expect file causes it to report that a new golden file has been generated (without an error). Finally, the third run reports a mismatch in the second golden file.

Seems important for very large Datalog programs

• Detect unused variables in rules and functions
• Detect unused intermediate relations (i.e., relations that are neither output nor used to compute other relations).
• Grouping by complex variables or variables wrapped in Ref<> is inefficient. Ideally, one should group by one or several small identifiers.
• ???

test.log
stack test log attached. Might be related to #84 - might be fixed if one tracks down which git version of timely & abomonation worked, and track that in rust/differential_datalog/Cargo.toml

Command to install differential datalog binary.

There should be a way to perform string interpolation.
https://en.wikipedia.org/wiki/String_interpolation
I suggest the C# syntax:
$"The value between braces ${expression + other} is treated like an expression"

to structure complex control flow

• Rename int -> bigint
• rename ground relation -> input relation
• add return statement

We currently don't have a way to compile arbitrary l-values to Rust, e.g.,

Constructor{var x, var y} = z

is ok, but

Constructor{x, y} = z

where x and y are previously introduced variables is illegal.

Either implement the logic to support this translation (e.g., by assigning to intermediate variables) or modify validation logic to disallow such programs

We rely on parsec's standard parser for strings, which supports unicode and escaping.

TODO:

• check and document its exact functionality
• can we handle all OVSDB strings?

ValMap is a data structure that stores the content of output tables. It is updated by each change callback invoked by the differential inspect() operator. ValMap is protected by a mutex, potentially introducing contention in workloads where outputs are frequently updated. One possible solution is to maintain ValMap in a separate thread and use mpsc queue to communicate with this thread from workers. We must be careful though to flush the queue before transaction_commit() returns. Another (even better?) option is to keep a ValMap per worker and only merge them when the client requests a copy of an output table.

x == (x,y).0
y == (x,y).1
z == (x,y,z).2
...

statements are printed without any indentation

0x123456_abcd_abcd_abcd. Allow this in:

• command language
• DDlog

@blp

E.g., start on a line and end on another one.
Also, if that is allowed, can the newline be escaped?

Replace {} with ${}.

Ben's version of FTL allows traversing cross-table pointers, e.g.:

let O = lspip.lsp.dhcpv6_options.option_args

To support this without using nested for loops, we'd need to add some notion of foreign keys and possibly other SQL constraints to the language

An error message that looks like this is generated whenever type unification fails:

Expression parameterized(string, int) has unknown type in CtxTop

Should we set up travis CI?

We use let in FTL, and var in the rest of the language. There is not reason for these two forms of variable declaration.

use extern keyword to make it explicit that a function is defined outside of Datalog

The Rust backend currently does not allow access to fields of types with multiple constructors (i.e., types compiled to enums), even if all constructors of a type have the same field

The unmerged tutorial has an example which does not seem to generate correct Rust code.
This is the dl code:

extern function split(s: string, sep: string): set<string>
function split_ip_list(x: string): set<string> =
   split(x, " ")

The generated code does not compile:

fn split_ip_list(x: &String) -> set<String> {
    split(x, (&r###" "###.to_string()))
}

since there is no set type in Rust.

This is allowed by the parser

typedef t = (t, t)

It should be possible to load a compiled DDlog program and execute transactions from Java.

This requires a couple of preparatory steps:

• DDlog currently generates static libraries. We have to change the crate type to build .so instead.
• DDlog still does not have a complete C API.

Background:

• The generated library file is written to the target/release directory, e.g., tests/datalog_tests/path/target/release/libpath.a.
• Associated header file is tests/datalog_tests/path/ddlog.h

https://p4.org/p4-spec/docs/P4-16-v1.0.0-spec.html#sec-literals

The most important use case is combining auto-generated schema (e.g., from OVSDB) with hand-written code. We may be able to get away with using CPP or m4, but must make sure that line numbers in error message refer to original input files.

Currently the compiler translates them to the element type.
Is this a good idea?