concurrent requests may skip loading some cache paths

This describes the fundamental issue behind https://github.com/docker/buildx/issues/2144 https://github.com/docker/buildx/pull/2265

In BuildKit, all steps from concurrent requests are loaded into the same solve graph. If two requests have some overlapping areas, this is deduplicated; both requests point to the same vertex in a graph with an aggregated reference count.

During a solve, the edge in the graph increments through multiple states. It monitors the parent states(and sets the desired state for them), looks up its cache keys, sees if there are loadable cache records, loads snapshots from the cache, or executes the step. It does it until it has reached the desired state for the current edge(or gets canceled).

The desired state can be initial, cache-fast(all definition-based cache keys loaded), cache-slow(all content based cache keys loaded), complete. The algorithm is designed to find biggest possible cache match and avoid solving edges to complete state unless it is absolutely needed (eg. we may not need to load parent step cache and take it to complete state if we can already determine we have loadable cache for child, this is how in Dockerfile+inline cache you don't need cache for intermediate stages to get cache for the last change).

In the case described in https://github.com/docker/buildx/issues/2144 there are two builds where first is a subset of the first one.

What happens is that first build request is made and starts to be evaluated. As this build has cache sources, it finds that cache already exists and it is loaded (it seems that there might be some progressbar issue where second build overrides the visual "cached" status but I have verified that these steps do load from cache without issues). The result edge of this build goes to completed state.

Now the second build comes and it has new cache sources. The shared parts from the previous build are directly connected to the vertices already in memory. The result edge for new build starts with desiredstate=complete state=initial. Solver will start to find cache keys for this step. To do that it first needs cache keys from the parent step. Normally it would start by setting the desiredstate to cache-fast and then to cache-slow if needed. But in this case, the parent step reports that it is already in the completed step and reports its cache keys. The issue is that these are only the cache keys that were found from the first build and do not contain the keys from the new cache source of the second build. The state machine works in only one direction, if the edge is already in completed state, it never goes back to cache-fast or cache-slow state where it would request more cache keys.

In https://github.com/docker/buildx/pull/2265 workaround is to change the timing so that the result edge of first build does not go to completed state before the child step for the second build has already been loaded to the graph already. But this does not work in all cases, eg. two independent parallel builds with shared steps happening with specific timing and cache conditions.

Start by tracing the solve graph edge state machine described in the issue, focusing on how shared vertices report cache keys after reaching the completed state. Reproduce the concurrent-build scenario from buildx issue 2144 and verify that newly supplied cache sources are considered for shared steps without regressing cache reuse.