Add spatial filtering support to Kart

[olsen232]

It should be possible to work with a "spatially filtered" Kart repo. This is a repo which has a particular geometry which is the stored in the config which is treated as a spatial filter, such that -

• when the working copy is written, only features that match the spatial filter are included
• when cloning and fetching features from the server, only features that match (or possibly match) the spatial filter are included
• when generating diffs, changes that happen entirely outside the spatial filter are omitted.

There is some more complexity around these concepts (such as, making sure the user doesn't accidentally reuse the PK from a feature that doesn't match their current filter, since PKs must be globally unique) but that is the basic idea.

[olsen232]

Kart spatial filtering a.intersects(b) test is naive right now -

• doesn't make sure long polygon edges are segmented into short lines before reprojecting, so the geographical location of the middle of the polygon's edge can change
• doesn't consider the anti-meridians at all - might behave unexpectedly if the spatial filter or the layer crosses the antimeridian
• doesn't check if a spatial filter geometry can be wholly (or partially) reprojected into a target CRS, so this will simply fail if it cannot

Generally works fine in spite of this but these will all be needed at some point

[olsen232]

Setting a spatial filter locally during a kart clone or kart init is mostly working - however, there are lots of gaps that need to be revisited. Tracking them here so they don't get forgotten:

Setting and applying spatial filters locally:

• no supported way to change the spatial filter after the repo after it has been created (workarounds exist eg if you manually edit the config and then recreate the workingcopy)
• update sequence generators in the working copy to try and avoid probably-accidental-PK-collisions
• detect and handle probably-accidental-PK-collisions somehow - maybe warn or maybe reassign PKs
• better intersection tests (see above Add spatial filtering support to Kart #456 (comment))
• Better experience for when a reference to a spatial filter is updated to point to a different spatial filter
• make sure refs/filters/* are being cloned as we expect, think about if we support other refs
• add info about the spatial filter to kart status, maybe kart diff

Applying spatial filters to data sent over network - partial clone:
This isn't even started at all, but basically kart needs to support the following:

• Maintaining a spatial index database in the server repo
• Sending the spatial filter or spatial filter reference via git clone
• Detecting when features are missing due to partial clone and generally just skipping those features
• Fetching missing objects when they are needed after all (ie, in a merge conflict, or, to find out what the first unassigned PK is)

[olsen232]

As of #475, spatial-index changes to kart have begun - these depend on S2 / pywraps2, and on git 2.33 or later.
For build-is-red reasons I'm not currently changing the kart build, so these deps will have to be fixed later. Relevant tests are skipped, these can be unskipped when these deps are fixed

[olsen232]

Code for maintaining a spatial index in a kart repo is mostly done at 92e590a, but still has the following issues:

• google/s2geometry isn't built into the windows build, only macos and linux, so it won't work on windows (obsolete due to removing S2 dependency)
• also isn't part of our dev build (not very sure how that works or why or when it is different from the actual build)
• the index generated sometimes differs on macos and linux, but probably due to CRS reprojection differences - isn't actually a bug with the S2 indexing code itself (obsolete due to removing S2 dependency)

Won't fix all of these immediately - will try and make progress on the overall flow, so as to get to something that works sooner rather than later (even if only one some platforms)

[olsen232]

Git filter extension is WIP at https://github.com/koordinates/kart/tree/git-spatial-filter-extension

• the C++ code itself is done - builds fine with our custom build of git, finds matching features in the S2 database
• messing with the RPATH isn't done - building it will likely make a git binary that can't find libsqlite or libs2, unless you modify it using install_name_tool or similar.
• it isn't part of our build system, so would have to be built manually and copied into the relevant place
• no plumbing code in place yet to actually perform the filter when doing a spatially filtered clone

[olsen232]

• Custom git with built in s2 filtering is now built into kart, but only on macos and linux. Not done on windows.
• Still no plumbing code in place to actually perform the filter when doing a spatially filtered clone
• Custom git doesn't yet support filtering by reference eg "Clone repo X and use object Y in repo X as the spatial filter"

[olsen232]

• You can do a proper spatially filtered clone by setting X_KART_SPATIAL_FILTERED_CLONE=1 before you run kart clone, but this feature is otherwise turned off
• A custom git which understands filter extensions but doesn't have any is now built into kart on windows - this still allows spatial filtering to work on windows; as long as windows is only client where the repo is being cloned to and macos or linux is the server (since the S2 based filtering happens on the server)

[olsen232]

Something else we need - when a kart repo is to be used as a server, it should have uploadpack.allowAnySHA1InWant set to true. That lets its clients fetch individual features that are outside the spatial filter, if they are needed for some particular operation (perhaps showing a diff were a feature moved into or out of the spatial filter)

[olsen232]

The index is switched from S2 cells that approximate envelopes - now it is simply envelopes. This removes our dependency on S2.

[olsen232]

Closing since spatial filtering is launched, will reopen either individual issues or a new tracking bug