search

rust-lang / datafrog

A lightweight Datalog engine in Rust
Apache License 2.0
796 stars 43 forks source link

Unleash the treefrog #11

Closed lqd closed 5 years ago

lqd commented 6 years ago

It could be time, for the :frog: to leap from its tree and join us. Worst case, that leap is optimal!

:)

frankmcsherry commented 5 years ago

👍

frankmcsherry commented 5 years ago

Do you have merge rights, or should I click the big "merge pull request" button for you?

nikomatsakis commented 5 years ago

I have merge rights; I was going to let travis finish.

nikomatsakis commented 5 years ago

@frankmcsherry btw have you given any thought to how to do automated testing? I was contemplating trying to generate random data and some kind of "mega naive merge" algorithm and use that to create unit tests of the various join combinators.

nikomatsakis commented 5 years ago

Possible mega naive join would be something like:

let mut join = source1.clone();
join.extend(source2.clone());
join.sort();
join.dedup();
frankmcsherry commented 5 years ago

I have given it thought, and not come up with anything especially good. At least, over in more general "differential" space, I've not had great ideas about how to cover the sketchy cases with confidence. What I've done over there is try to do something like Graydon's philosophy that when you land commits you also put in tests that break before but not afterwards. These were more perf-oriented than correctness, though. =/

nikomatsakis commented 5 years ago

OK. I figured I'd start off with a base of various "smoke tests" that use random data like I suggested, and then we'd add regression tests for specific bugs that are found (as you suggest).

frankmcsherry commented 5 years ago

That seems sane. One should be able to write fuzzing tests with random data, I'd bet, relating e.g. treefrog, naive datafrog, and brute-force, but I'm not sure about the confidence (e.g. would cover random data, but not random queries which are more strongly bound to the code itself).

nikomatsakis commented 5 years ago

Indeed. I opened https://github.com/rust-lang-nursery/datafrog/issues/15 for further discussion.