test: update output to 9b3f95d9783d The unstable graph nodes are now shown with the character "*", update the test outputs. CORE-TEST-OUTPUT-UPDATE: 9b3f95d9783d

stablesort: use parent filtering in a place we forgot to Freak merge striked again.

obshashrange: add a progressbar to upgrade This section is the slowest, have some progress idea would be useful.

stablerange: add an sql index on subranges id too This should speed up query that find super ranges.

obshashrange: less brutal reset when receiving markers on existing node We now target the affected ranges only. The implementation is still slow but that should be better than what we had before.

obshashrange: update the cache updating logic Use the more modern option when available. (Same as the other caches).

stablerange: cleanup the update logic

stablesort: cleanup the update logic

firstmergecache: cleanup the update logic

depthcache: cleanup the update logic

changelog: add an entry about the obshashrange changes

stablerange: be more cautious when deleting the sql connection This triggered some crash in further development. This also match what is done elsewhere with this attribute.

stablerange: clarify sql transaction logic This should help concurrent access.

stablerange: use mergepoint based algorithm for the official stable range Changing the official stable range will impact all users of the infrastructure. We update version number of the cache file and discovery methods to clarify this. We do no keep compatibility with the old method over the wire. The new algorithm is much better and keeping compat is more work than we have time for right now.

stablerange: explicitly create a stablerange entry for branchpoint method We are about to change the default.

stablerange: have a mergepoint based sql backed class Everything is so generic that getting a class is 3 line of codes.

stablerange: introduce a sql backed version of the generic on disk cache This is getting use close to actually using the new sorting and algorithm for real.

stablerange: add a base class for on disk stored stablerange class

stablesort: use on disk cache for test

caches: factorise the cache warming check The old conditional was duplicated and hard to read. We factorise everything into the `utility` module.

stablerange: use repo-carried stablesortcache That one is common to all and disk persisted

stablesort: expose the cache through the repository Let have a unique instance, keep it warm and accessible.

stablesort: implement an ondisk cache Persisting the cache on disk will be important for large repositories.

stablesort: realign a misaligned continue We should make a better use of the jump cache now.

stablesort: remove some dead code This closure is no longer in use.

stablesort: abstract all cache access This prepare an on disk version of the cache

stablerange: use first merge cache to skip over linear section If we are to skip over a large section of the range, skipping everything until the first merge seems like a good idea.

stablerange: add a new 'firstmerge' cache This cache store the first merge ancestors of a changesets. This is useful to avoid iteration over the changelog when building stablerange.

stablerange: drop unused `until` utility We no longer needs this function.

stablerange: use cached size data instead of walking the graph Less iteration is better.

stablesort: record previous segment size in the jump That was, we can skip over a full jump without walking it. We'll make use of this in the next changeset.

stablesort: move jump recording inside the exclusive function This will allow use to record to cache size of segment in a later changeset. If the exclusive set is empty, we need to record it outside that function.

stablerange: compute jump size after jump retrieval only This prepares the caching of jump sizes.

stablesort: warm jump cache more efficiently We no longer for a full depth iteration for all request: - we exit early for non-merge, - for merge, we only iterate over the exclusive area.

stablesort: use a regular dict for jumps This will help knowing what revision we have already queried or not.

stablerange: use the jump information for faster iteration Instead of doing a full iteration over the exclusive set, we compare the jump information instead. This perform the same kind of logic than before but will allow for much faster iteration once all the caches are in place.

stablesort: expose the jumps sequence to other code The stable range needs it to build exclusive subrange efficiently.

stablesort: use 'depth' in mergepoint tie breaker The parents with the most depth will is considered lower. It has a couple of advantages. 1) the more shallow parent probably have less exclusive revision, 2) it makes Oedipus merge behave like close to the linear case,

stablesort: rework jump gathering The old code was buggy in some case, the new code give the same result as the 'headstart' version.

stablesort: stop recording jump type There are no mature user of this "jump type" data and the current implementation is known to be buggy. So we drop the logic for now. This will make on disk storage simpler. The data will be reintroduced later

stablesort: pass a jump recording function instead of a list This seems cleaner to abstract the underlying storage to the lower level. This also makes use more flexible about jump detection.

stablesort: minor indent fix

stablesort: clarify subcall to the exclusive side Before doing deeper rework of this logic, we tackle the simplest parts.

docgraph: update test output with new output

stablesort: record, cache and reuse jump Iterating below a merge means two things: 1) iterate over the part exclusive to the higher parents, 2) iterate from the lower parents. While iterating on the exclusive part, there will be case were we just go the next natural parent, and case were we'll have to "jump" to another revision. If we record all point this "jump" happens and their target, we can easily reproduce the iteration in the future. With that information we can iterate over the exclusive part of the merge without having to compute it entirely. In addition we store the reason of the jump. This will help the stable range processing later.

stablesort: fix head start computation The recursion was wrong and provided wrong result. As a side effect, this seems to hint that `stablesort_mergepoint_bounded` is not giving the right result for complex set.

stablesort: avoid attempting to sort a tuple This seems silly.

stablerange: use the filterparents utility

stablesort: use the filtered parents utility

depthcache: use parents filter in depth cache

parents: add a utility to filter parents There is various strange case of merge out there that needs to be handled. We add an utility function to handle them all.

stablerange: abstract the bit able to store cache into sql The part about actually storing the range is independent of the algorithm, so we should extract this before using it for the next iteration.

stablerange: split pure algorithm part from the on disk cache The stable cache file is getting long, we split the logic about keeping data on disk into a dedicated file.

stablerange: add an assert to detect buggy range Nothing can be negative in there, we add an assert to make sure it is so.

stablerange: warn cache for all relevant ancestors range Warming cache in the right order will prevent recursion to happens and unlock usage on large repository.

stablesort: move parent range computation into its own method Now that we have running code, we'll need to avoid too deep recursion. We extract the piece dealing with the parent range before we write more code to warm it.

stablerange: drop the basic inheritance from the 'mergepoint' version All necessary bits are implemented now (except for warmup which we explicitly bypass for now).

stablerange: cache known subrange at the stablerangecached level That way, the 'stablerange_mergepoint' class also benefit from it.

stablerange: use sort cache to build 'mergepoint' information Using the walk cache gives use a better complexity we need to scale. There are further improvement we could make, but this is a good first step.

stablesort: make the iteration from head available to all This will be useful for the stablerange code to work properly.