Improve asymptotics of merge-tree reconnect

[Abe27342]

Description

The previous implementation of regeneratePendingOp necessitated a linear walk over segments of the merge tree. This strategy can be improved by augmenting the partialLengths structures stored at each block with information about unacked segments. However, that information isn't particularly cheap or straightforward to update: it could be done at the same asymptotic cost, but would likely add some undesirable constant factors to the partial lengths bookkeeping (which already needs to be updated on each insert/delete/structural change). As a compromise, this adds the ability to optionally compute local partial length information to PartialSequenceLengths, with the restriction that it's invalidated on update. This is sufficient for the reconnect flow, which regenerates all outstanding local ops upon reconnection without interleaving new ops.

Overall, for a merge tree with N segments, this reduces the cost of rebasing M local ops from O(NM) to O(N + Mlog(N)).

[msfluid-bot]

⯅ @fluid-example/bundle-size-tests: +7.28 KB

Metric Name	Baseline Size	Compare Size	Size Diff
aqueduct.js	389.93 KB	392.36 KB	⯅ +2.43 KB
connectionState.js	680 Bytes	680 Bytes	■ No change
containerRuntime.js	191.92 KB	191.92 KB	■ No change
loader.js	151.12 KB	151.12 KB	■ No change
map.js	42.63 KB	42.63 KB	■ No change
matrix.js	129.27 KB	131.7 KB	⯅ +2.43 KB
odspDriver.js	150.23 KB	150.23 KB	■ No change
odspPrefetchSnapshot.js	38.39 KB	38.39 KB	■ No change
sharedString.js	149.91 KB	152.34 KB	⯅ +2.43 KB
Total Size	1.25 MB	1.25 MB	⯅ +7.28 KB

---

Baseline commit: dca1cbe0e2572a902982f335707d955d54ad439a

Generated by :no_entry_sign: dangerJS against 35827519585340d06f3fcc9e6bbb23cc9ab091e6

[anthony-murphy]

there is another place we do a similar costly walk: packages\dds\matrix\src\permutationvector.ts would be good to ensure we can support that case as well.

[Abe27342]

looks good. added some comments that are mainly around maintainability here, but logic looks sound. please also get an issue filed for the matrix usage.

Filed AB#1577 for this. Looks not too bad.

[github-actions[bot]]

This commit is queued for merging with the next branch! Please ignore this PR for now. Contact @microsoft/fluid-cr-infra for help.