# Polonius notes

## 1. Make it work

### Correctness

1. With [PR #64749](https://github.com/rust-lang/rust/pull/64749) the single remaining rustc UI test failure was fixed (and also re-enabled a liveness optimization in rustc) apart from a couple OOMs.

2. Tests succeed except for said OOMs:
- `ui/numbers-arithmetic/saturating-float-casts.rs` is materializing 10 948 x 136 664 outlives constraints (15GB+; i.e. materializing placeholder region subsets at all points of the CFG) [here](https://github.com/rust-lang/rust/blob/8301de16dafc81a3b5d94aa0707ad83bdb56a599/src/librustc_mir/borrow_check/nll/type_check/mod.rs#L229-L233). (The NLL MIR dump is 200MB+, the .dot files are 15MB+ and fail to generate a png on my machine, as I was trying to check these regions' SCCs)
- since then, another similar OOM-ing test was added: `ui/wrapping-int-combinations.rs` (it's possible new ones have been added since I last checked)

These are similar to the cases we had during NLL dev: where some tests with lots of `assert_eq!` were slow, and faster when switching to regular `assert!`.

(I think we talked about this materializing as being the "`Location::All` hack" which we could/would remove, but didn't since it's technically correct ? or maybe I'm confusing with the similar situation with NLLs)

Note that a lot of those are actually equal origins, and that the "equality variant" could help here, by storing them in a dedicated relation (though this can be done for the Naive/DatafrogOpt variants, but don't map as cleanly) though we'd need to make sure the datalog rules themselves don't end up materializing the same huge number of tuples when computing the subsets TC.

3. Not all Polonius errors actually show up as rustc errors (examples in the UI test suite and `rand` when killing loans on `Call`s only; 7 of the run-pass tests which pass in rustc fail if we assert that there should be no Polonius errors):

[run-pass (polonius)] run-pass/array-slice-vec/check-static-mut-slices.rs
[run-pass (polonius)] run-pass/array-slice-vec/check-static-slice.rs
[run-pass (polonius)] run-pass/consts/const-vec-of-fns.rs
[run-pass (polonius)] run-pass/drop/dynamic-drop-async.rs
[run-pass (polonius)] run-pass/generator/addassign-yield.rs
[run-pass (polonius)] run-pass/generator/issue-52398.rs
[run-pass (polonius)] run-pass/generator/static-generators.rs

There were more cases like this in the ui tests, but run-pass was easier to capture at the time. I've started looking at a couple cases and they seemed related to statics, maybe they all are ?

4. Ensuring correctness and non-regressions, by enabling the polonius compare mode on CI.
Current blockers:
* the previously mentioned OOMs on materializing placeholder region subsets at all points of the CFG
* performance ? need to quantify the slowdown to see whether it's a blocker (last I checked it was slower but not particularly bad)

### Completeness

1. illegal subset relations (more details in [this blogpost](http://smallcultfollowing.com/babysteps/blog/2019/01/17/polonius-and-region-errors/))
- Placeholder loans technique implemented, which is not described in the blogpost (but prototyped in [a branch whose main logic is here](https://github.com/lqd/borrow-check/blob/174980ab299110feddae2217573dbe02e6535bcf/polonius-engine/src/output/naive.rs#L196-L216)) in both `Naive` and `Datafrogopt`, simple tests seem to work but not yet reviewed or in a PR
- Some open questions in the [dedicated zulip thread](https://rust-lang.zulipchat.com/#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/placeholder.20loans), e.g. about rustc integration (how to emit these placeholder loans facts, but also would we "just" need to change
`RegionInferenceContext::check_universal_regions` to instead look at the Polonius errors when in `-Zpolonius` mode).
- Possible concern about the impact on `LocationInsensitive`, and thus `Hybrid`, variants
- Once the ["context PR #134"](https://github.com/rust-lang/polonius/pull/134) is finalized, a placeholder loans PR can be opened (with book updates describing the facts and rules), but tests might be hard to write until rustc is modified to emit those facts so that we can reuse the existing tests

2. are there still NLL optimizations disabled in Polonius mode ? (there was one such disabled optimization about computing liveness, but was removed in [PR #64749](https://github.com/rust-lang/rust/pull/64749))

3. Higher-rank subtyping, and relation to Chalk, so a lot of overlap with wg-traits.
The problem is described in more detail in [this blog post](http://smallcultfollowing.com/babysteps/blog/2019/01/21/hereditary-harrop-region-constraints/), but most of the solutions design work and plan to fix are not yet written down (but some explorations have been done already IIRC)

4. Move/initialization analysis
- possibly almost complete on the Polonius side with [PR #135](https://github.com/rust-lang/polonius/pull/135)

### Precision

The "flow-sensitive equality" variant which better distinguishes instantaneous data flow from persistent data flow:

- even if this endeavour also started to avoid tracking subsets along the CFG, it seems a TC of the `equal` origins must also be done. So the variant seems similar to the `Naive` variant operationally (but in practice is a bit worse in the current implementation, but that can be improved)

- [dedicated zulip thread](https://rust-lang.zulipchat.com/#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/equality.20regions) (where most recently I was "live-zuliping" the analysis of a test failure which lead to me to the need for the TC)

- WIP implementation [in this branch](https://github.com/lqd/borrow-check/blob/variant_prototype2/polonius-engine/src/output/prototype.rs), still not 100% correct: 2 failures on rustc tests, for code which should apparently fail to compile but passes (more details in the thread, [around here](https://rust-lang.zulipchat.com/#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/equality.20regions/near/177823183))

---

## II. Make it good

### 1. refactoring:

- finalizing naming/terminology: some of that has already been done, but still needs to be done in the relation names, the parser, etc (for the previous renaming of, say, `regions` to `origins`, but also we were looking for more representative relation names, like renaming the `requires` relation to `contains` or similar).
- code organization:
* in polonius itself, eg unit tests written as-is won't really scale (and we need to figure out our relation with rustc's tests, as those are not checked in the Polonius CI when we do PRs)
* fact generation in rustc is a bit ad-hoc and spaghetti (understandably so, but we can probably make it clearer)
-> [issue #117](https://github.com/rust-lang/polonius/issues/117) is a proposal about this
* passing data between rustc and polonius, eliminating clones, sharing data between Polonius steps (and not just partial resuts between the locinsensitive and regular analysis, but also input data: no need to create Relations multiple times)
* the more analyses polonius does, the less a single type of errors makes sense in the communication between rustc and polonius
-> the ["context PR"](https://github.com/rust-lang/polonius/pull/134) proposal helps with the previous two points (but does not fix some of the cloning of `AllFacts` since rustc does not give ownership of the facts yet)
* taking better control of allocation, which is related to both code organization and performance (and datafrog)

### 2. Misc

- leapjoins/datafrog: encode WF-ness of leapjoins in the API if possible, loosen the requirements so we can have leapjoins that only filter

- a plan for testing (maybe also better architecture/tools for writing tests): testing is still better done in rustc, which is unfortunate/hard. Do we copy all of rustc's tests, how do we synchronize facts ?

- is the optimized variant still necessary ? (what about the location insensitive one ?)

- docs: beginnings of the book have been merged; it's built on CI and hosted on GH pages [here](https://rust-lang.github.io/polonius/)
-> there's a [WIP doc PR](https://github.com/rust-lang/polonius/pull/126) which is almost ready to go: only a question remains about the expected terminology of universal regions (and then renaming CFG "nodes" back to "points")

- more videos ?
- issues for new contributors / quest issues / etc

- try to make tests faster to compile (might require moving away from lalrpop) to follow-up on [PR #128](https://github.com/rust-lang/polonius/pull/128) which did this for the regular `polonius-bin`

- upstreaming some tools into datafrog: basic tracing "provenance" information, rule transformations and datalog-to-datafrog skeleton generator (at the moment located in [an external repo](https://github.com/lqd/datapond))

---

## III. Make it fast

- pushing the filtering as early as possible: on loans, regions, subsets. Different prototypes have been done, in the liveness and borrowcking phases, (on both limiting tracking only loans which could end up in errors, and on the ones pre-filtered by `LocationInsensitive`) and are only waiting on more progress on the completeness front to be turned into PRs
- datafrog leapjoins (and the WF-ness question)
- maybe the more precise "equality variant" has different performance characteristics (static equality in particular is among the fastest, while flow-sensitive equality seems similar to the Naive one)
- CFG compression (but heavy filtering seems to have even more of a performance boost; maybe combining both would be interesting, as it seems sensible to have a specialized data structure to compute some analyses, maybe arielb's iterated dominance frontier but I'm not sure yet I agree/understand it makes sense for liveness per se)
- benchmarking effort: Albin has lots of benchmarks and data but imprecise as timing the polonius binary and not polonius-engine itself or rustc; lokalmatador was working on instrumenting rustc with measureme/-Z self-profile but deleted their github account so this WIP work is lost
- Comment: I have been considering reimplementing roughly the same analysis again as an execution mode of polonius-cli. Would that make sense? E.g. `polonius --benchmark-to-tsv=results.tsv folder` would take a folder of inputs by crate (i.e. `folder/clap/nll-facts/` and so on) and produce a TSV with the results per function and crate. The advantage to what I have now is more precision (and also the ability to time the different steps), and the ability to do analysis on outputs as well, including intermediate ones. -- Albin
- out of the 2 datasets I have access to, here are some stats about interesting crates/functions to look at: [first batch](https://gist.github.com/lqd/51344ae68afb576d4d8ee48ac47a536e#file-first-txt), [second batch](https://gist.github.com/lqd/51344ae68afb576d4d8ee48ac47a536e#file-second-txt)
- also, while this benchmarking will help inform and improve polonius and rustc's fact generation, it will not yet provide information on the parts of NLLs which could be replaced by Polonius
- the liveness work ended up regenerating clap which made it 2x faster, maybe we can add the old version if it's a better benchmark ? (then again, this better performance is because of rustc improvements and bugfixes, so the new data is definitely more realistic towards what one would experience using polonius on the same piece of code)
- is it possible/easy to compare liveness via polonius vs the existing liveness computations ? can we measure NLL borrowck with just "polonius liveness" ? would that data be useful ?
- optimizing datafrog itself: can we use subsumptive tabling (and DTs, so this is related to "datapond") ? sorting networks w/ SIMD ? integer compression and intersection (surely via SIMD as well) ? specific hash joins or bitmap structures, for relations known to be "small" (a bounded max number of tuples really), or where the query structure can allow it (more notes about these possible the specialized `Relation`s can be found in a [dedicated zulip thread](https://rust-lang.zulipchat.com/#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/notes.20on.20datafrog)) ? parallelizing the 3 joins/steps per iteration of the semi-naive evaluation ?