union op causes out of bounds error using i_overlay 1.7.4

[urschrei]

Repro:

try to union this geometry (valid WKT AFAIK) using the unary_union branch in #1246.

Result:

---- algorithm::bool_ops::tests::unary_perf stdout ----
thread '<unnamed>' panicked at /Users/sth/.cargo/registry/src/index.crates.io-6f17d22bba15001f/i_overlay-1.7.4/src/bind/solver.rs:64:42:
index out of bounds: the len is 7 but the index is 18446744073709551615
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread '<unnamed>' panicked at /Users/sth/.cargo/registry/src/index.crates.io-6f17d22bba15001f/i_overlay-1.7.4/src/bind/solver.rs:64:42:
index out of bounds: the len is 4 but the index is 18446744073709551615
thread '<unnamed>' panicked at /Users/sth/.cargo/registry/src/index.crates.io-6f17d22bba15001f/i_overlay-1.7.4/src/bind/solver.rs:64:42:
index out of bounds: the len is 13 but the index is 18446744073709551615
thread '<unnamed>' panicked at /Users/sth/.cargo/registry/src/index.crates.io-6f17d22bba15001f/i_overlay-1.7.4/src/bind/solver.rs:64:42:
index out of bounds: the len is 42 but the index is 18446744073709551615
thread '<unnamed>' panicked at /Users/sth/.cargo/registry/src/index.crates.io-6f17d22bba15001f/i_overlay-1.7.4/src/bind/solver.rs:64:42:
index out of bounds: the len is 42 but the index is 18446744073709551615

Note the i_overlay version. Unfortunately there's no way to use 1.7.2 using our current Cargo.toml. This works:

-i_overlay = { version = "1.7.2, < 1.8.0", default-features = false }
+i_overlay = { version = "=1.7.2", default-features = false }

[urschrei]

(Test was run in release mode, fyi)

[kirillolenev-dm]

The same issue I got. geo 0.29.2. Any workaround so far?

[frewsxcv]

Should we pin to 1.7.2? And has this been reported upstream to i_overlay?

[urschrei]

I think we should pin, yes. We can't report yet because there have now been subsequent i_overlay releases which may have fixed the issue, but we can't test against them because of broken API compat.

So I think we need to do the following:

1. Pin to 1.72, which will unbreak geo
2. Rewrite our i_overlay compatibility module for the post 1.72 API
3. Write a (possibly breaking) test against the current i_overlay version and report that if necessary

Bonus:
establish a strategy which prevents geo and downstream consumers from being vulnerable to i_overlay breaking semver compat, while allowing us to keep abreast of released improvements, as there's a lot going on at the moment (better solver, multithreading etc) and we definitely want those changes. That may be as simple as pinning a version and maintaining an i_overlay_improvements branch for experimentation – haven't thought about it too much.

[michaelkirk]

I can take a look tomorrow.

[michaelkirk]

Can you zip and upload the wkt here? I don't have a dropbox account.

[michaelkirk]

Can you see if #1275 (i_overlay 1.8) fixes anything for you @urschrei ?

Or i_overaly 1.9: https://github.com/georust/geo/tree/mkirk/i_overlay_1.9

[urschrei]

Tests now pass on #1275, with a slight perf improvement over 1.72, but note that the results are different (we end up with fewer output points – I think this is good?)

Multi-Threaded Unary Union Perf Test

2.42s -> 2.05s
Using 1.9, perf improves a little more over #1275: 2.05s -> 1.85s

Note that this isn't a criterion-based test as that isn't feasible given the duration, but considering how much work is being done, the timings are stable.

[urschrei]

Uhhh possibly may have spoken too soon: results for the same test (number of output polygon points) varies between single- and multi-threaded versions of the algorithm.

multi-thread: 3539
single-thread: 3541

It's a small difference, but I'm not sure why it's arising. Let me check whether it's the same on 1.72…

[urschrei]

(I will also note that single-thread perf for that test using 1.9 is 11.3s -> 6.1s. That's a very big improvement…)

[urschrei]

Also seeing differences (different differences ofc) between single- and multi on 1.72, so that's something to dig into separately as part of #1246.

[urschrei]

Closed by #1275