| | | 1 | | using NGql.Core.Abstractions; |
| | | 2 | | using NGql.Core.Extensions; |
| | | 3 | | |
| | | 4 | | namespace NGql.Core.Features; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// Bucketed candidate index for <c>QueryMerger.FindMergeTarget</c>, owned by a single |
| | | 8 | | /// <see cref="QueryDefinition"/>'s root field dictionary. Without this index, finding a merge |
| | | 9 | | /// target scans every existing root field for every incoming field — O(N) per <c>Include()</c>, |
| | | 10 | | /// O(N²) for a chain of N includes that all share one field <c>Name</c> (the production shape: |
| | | 11 | | /// N fragments at the same field path with differing argument filters). |
| | | 12 | | /// |
| | | 13 | | /// <para> |
| | | 14 | | /// Bucketing has TWO tiers. The outer tier is by <c>Name</c> (OrdinalIgnoreCase) — mirrors the |
| | | 15 | | /// cheap check <c>FindMergeTarget</c> already performed before falling through to the expensive |
| | | 16 | | /// <see cref="FieldDefinitionExtensions.CanMergeFields"/> call. The inner tier further narrows by |
| | | 17 | | /// <see cref="FieldDefinitionExtensions.ComputeDeepFingerprint"/>, so a chain of N same-named |
| | | 18 | | /// incoming fields that are all mutually incompatible (the production shape — every fragment |
| | | 19 | | /// shares one root field name but carries a different deep argument filter) lands in N distinct, |
| | | 20 | | /// small fingerprint buckets instead of one O(N) name bucket. <see cref="GetMergeCandidatesByFingerprint"/> |
| | | 21 | | /// is the O(1)-average entry point <c>QueryMerger.FindMergeTarget</c> uses to exploit this. |
| | | 22 | | /// </para> |
| | | 23 | | /// |
| | | 24 | | /// </summary> |
| | | 25 | | internal sealed class FieldMergeIndex |
| | | 26 | | { |
| | | 27 | | // Name (OrdinalIgnoreCase) -> ordered list of root-dictionary keys sharing that name, in the |
| | | 28 | | // order they were inserted. Preserving insertion order keeps FindMergeTarget's "first match |
| | | 29 | | // wins" behavior identical to a linear scan of the dictionary. This remains the ground truth |
| | | 30 | | // for resync and for NextUniqueKey; GetMergeCandidatesByFingerprint below is a narrower, faster |
| | | 31 | | // view derived from the same underlying keys. |
| | 546 | 32 | | private readonly Dictionary<string, List<string>> _byName = new(StringComparer.OrdinalIgnoreCase); |
| | | 33 | | |
| | | 34 | | // Name (OrdinalIgnoreCase) -> deep fingerprint -> ordered list of keys currently believed to |
| | | 35 | | // share that (Name, fingerprint) pair. Built lazily per name (see EnsureFingerprintBucketsBuilt) |
| | | 36 | | // the first time GetMergeCandidatesByFingerprint is asked for that name. Entries can become |
| | | 37 | | // stale (see class remarks); staleness is detected and healed per-entry at read time, never |
| | | 38 | | // assumed away. |
| | 546 | 39 | | private readonly Dictionary<string, Dictionary<ulong, List<string>>> _byNameFingerprint = new(StringComparer.Ordinal |
| | | 40 | | |
| | | 41 | | // Names whose fingerprint sub-buckets have been built at least once, so a second call for the |
| | | 42 | | // same name during the same synced generation reuses them instead of rebuilding. |
| | 546 | 43 | | private readonly HashSet<string> _fingerprintBucketsBuilt = new(StringComparer.OrdinalIgnoreCase); |
| | | 44 | | |
| | | 45 | | // Name (OrdinalIgnoreCase) -> key -> the fingerprint that key is CURRENTLY bucketed under in |
| | | 46 | | // _byNameFingerprint[name]. Reverse index of the same data _byNameFingerprint holds forward, |
| | | 47 | | // maintained in lock-step everywhere a key's bucket membership changes (build, IndexAdd, |
| | | 48 | | // HealBucketInPlace, ReindexFingerprint) so ReindexFingerprint's re-key can look up "which |
| | | 49 | | // bucket currently holds this key" in O(1) instead of scanning every fingerprint bucket under |
| | | 50 | | // the name — the fix for the production shape where a name accumulates many singleton buckets |
| | | 51 | | // (one per distinct incoming filter) and re-keying after every successful merge would otherwise |
| | | 52 | | // cost O(bucket count) each time, i.e. O(N) per merge / O(N^2) over a chain of N Includes. |
| | 546 | 53 | | private readonly Dictionary<string, Dictionary<string, ulong>> _keyFingerprint = new(StringComparer.OrdinalIgnoreCas |
| | | 54 | | |
| | | 55 | | // Every key currently in the root dictionary, plus a per-base-name suffix counter — backs |
| | | 56 | | // KeyGenerator.GenerateUniqueKey(FieldMergeIndex, ...) so it can produce the next unique key |
| | | 57 | | // directly instead of rebuilding a HashSet from fields.Keys on every call. |
| | 546 | 58 | | private readonly HashSet<string> _allKeys = new(StringComparer.OrdinalIgnoreCase); |
| | 546 | 59 | | private readonly Dictionary<string, int> _suffixCounters = new(StringComparer.OrdinalIgnoreCase); |
| | | 60 | | |
| | | 61 | | // Snapshot of the root dictionary's Count as of the last time this index was known to be |
| | | 62 | | // fully consistent with it. Compared against the live Count on every read — an O(1) staleness |
| | | 63 | | // check that catches any insertion which bypassed IndexAdd (e.g. a plain AddField/Preserve |
| | | 64 | | // call mixed into the same builder as Include() calls). |
| | | 65 | | private int _syncedCount; |
| | | 66 | | |
| | 546 | 67 | | private long _syncedMergeMemoEpoch = -1; |
| | 546 | 68 | | private readonly MergeMemoScope _memoScope = new(); |
| | | 69 | | |
| | | 70 | | /// <summary> |
| | | 71 | | /// Registers a newly inserted root-level field's KEY so future |
| | | 72 | | /// <see cref="GetMergeCandidatesByFingerprint"/> and <see cref="NextUniqueKey"/> calls see it. |
| | | 73 | | /// Must be called at every site that adds a NEW key to the owning <see cref="QueryDefinition"/>'s |
| | | 74 | | /// root field dictionary. Never-merge fields are still indexed (harmless — <c>FindMergeTarget</c> |
| | | 75 | | /// itself skips <c>IsNeverMerge</c> candidates) so a later field of the same name still gets an |
| | | 76 | | /// accurate candidate list. |
| | | 77 | | /// </summary> |
| | | 78 | | public void IndexAdd(string key, FieldDefinition field) |
| | | 79 | | { |
| | 963 | 80 | | GetOrCreateBucket(field.Name).Add(key); |
| | 963 | 81 | | _allKeys.Add(key); |
| | 963 | 82 | | _syncedCount++; |
| | | 83 | | |
| | | 84 | | // Only append to a name's fingerprint sub-buckets if they have already been built for this |
| | | 85 | | // name (i.e. GetMergeCandidatesByFingerprint has been called for it before) — otherwise |
| | | 86 | | // leave it to the lazy build, which will pick this key up from _byName along with every |
| | | 87 | | // other key for that name the first time it is needed. _fingerprintBucketsBuilt and |
| | | 88 | | // _byNameFingerprint entries are always created together (see EnsureFingerprintBucketsBuilt), |
| | | 89 | | // so the outer dictionary lookup below is guaranteed to hit. |
| | 963 | 90 | | if (_fingerprintBucketsBuilt.Contains(field.Name)) |
| | | 91 | | { |
| | 792 | 92 | | field.EnsureMergeMemoTracker().Attach(_memoScope); |
| | 792 | 93 | | var fingerprint = FieldDefinitionExtensions.ComputeDeepFingerprint(field); |
| | 792 | 94 | | GetOrCreateFingerprintBucket(_byNameFingerprint[field.Name], fingerprint).Add(key); |
| | 792 | 95 | | SetKeyFingerprint(field.Name, key, fingerprint); |
| | | 96 | | } |
| | 963 | 97 | | } |
| | | 98 | | |
| | | 99 | | // Records `key`'s current bucket fingerprint under `name` in the reverse index, creating the |
| | | 100 | | // per-name map on first use. Every write to a _byNameFingerprint bucket has a matching call |
| | | 101 | | // here so the two stay in lock-step. |
| | | 102 | | private void SetKeyFingerprint(string name, string key, ulong fingerprint) |
| | | 103 | | { |
| | 2208 | 104 | | if (!_keyFingerprint.TryGetValue(name, out var perName)) |
| | | 105 | | { |
| | 624 | 106 | | perName = new Dictionary<string, ulong>(StringComparer.Ordinal); |
| | 624 | 107 | | _keyFingerprint[name] = perName; |
| | | 108 | | } |
| | 2208 | 109 | | perName[key] = fingerprint; |
| | 2208 | 110 | | } |
| | | 111 | | |
| | | 112 | | // Every call site adds exactly one entry immediately after creating a fresh bucket (see |
| | | 113 | | // IndexAdd, ReindexFingerprint, EnsureFingerprintBucketsBuilt), and the production shape — every |
| | | 114 | | // fragment carrying a distinct deep-argument fingerprint — means the overwhelming majority of |
| | | 115 | | // buckets ever created hold exactly one entry for their entire lifetime. Pre-sizing to 1 avoids |
| | | 116 | | // List{T}'s default first-growth to a 4-slot backing array, which would otherwise waste 3 slots |
| | | 117 | | // per singleton bucket. |
| | | 118 | | private const int InitialBucketCapacity = 1; |
| | | 119 | | |
| | | 120 | | private List<string> GetOrCreateBucket(string name) |
| | | 121 | | { |
| | 1236 | 122 | | if (!_byName.TryGetValue(name, out var bucket)) |
| | | 123 | | { |
| | 588 | 124 | | bucket = new List<string>(InitialBucketCapacity); |
| | 588 | 125 | | _byName[name] = bucket; |
| | | 126 | | } |
| | 1236 | 127 | | return bucket; |
| | | 128 | | } |
| | | 129 | | |
| | | 130 | | private static List<string> GetOrCreateFingerprintBucket(Dictionary<ulong, List<string>> byFingerprint, ulong finger |
| | | 131 | | { |
| | 2208 | 132 | | if (!byFingerprint.TryGetValue(fingerprint, out var bucket)) |
| | | 133 | | { |
| | 1188 | 134 | | bucket = new List<string>(InitialBucketCapacity); |
| | 1188 | 135 | | byFingerprint[fingerprint] = bucket; |
| | | 136 | | } |
| | 2208 | 137 | | return bucket; |
| | | 138 | | } |
| | | 139 | | |
| | | 140 | | /// <summary> |
| | | 141 | | /// Returns the keys sharing BOTH <paramref name="name"/> AND the live deep fingerprint |
| | | 142 | | /// <paramref name="fingerprint"/> — the O(1)-average entry point <c>QueryMerger.FindMergeTarget</c> |
| | | 143 | | /// uses instead of scanning every same-named candidate. Self-heals: any visited entry whose |
| | | 144 | | /// live fingerprint no longer matches the bucket it was found in is moved to its correct |
| | | 145 | | /// current bucket and excluded from this call's result (see class remarks on the two ways a |
| | | 146 | | /// fingerprint can drift after indexing). The returned list, if non-null, is safe for the |
| | | 147 | | /// caller to enumerate directly — no further filtering is required. |
| | | 148 | | /// </summary> |
| | | 149 | | public List<string>? GetMergeCandidatesByFingerprint(Dictionary<string, FieldDefinition> fields, string name, ulong |
| | | 150 | | { |
| | 1962 | 151 | | EnsureSynced(fields); |
| | 1962 | 152 | | EnsureFingerprintEpochCurrent(); |
| | 1962 | 153 | | var byFingerprint = EnsureFingerprintBucketsBuilt(fields, name); |
| | | 154 | | |
| | 1962 | 155 | | if (!byFingerprint.TryGetValue(fingerprint, out var bucket) || bucket.Count == 0) |
| | 753 | 156 | | return null; |
| | | 157 | | |
| | 1209 | 158 | | HealBucketInPlace(fields, name, byFingerprint, fingerprint, bucket); |
| | 1209 | 159 | | return bucket.Count > 0 ? bucket : null; |
| | | 160 | | } |
| | | 161 | | |
| | | 162 | | // Walks `bucket` (believed to hold `expectedFingerprint` under `name`'s sub-index) and, for |
| | | 163 | | // every entry whose LIVE field fingerprint no longer matches, removes it from `bucket` and |
| | | 164 | | // re-inserts it into its correct current bucket within the same `byFingerprint` map. Runs in a |
| | | 165 | | // single forward pass with swap-remove, so healing is O(entries actually stale) beyond the |
| | | 166 | | // unavoidable O(bucket size) fingerprint recompute — each recompute is itself O(1) when the |
| | | 167 | | // field's own memo is valid. |
| | | 168 | | private void HealBucketInPlace( |
| | | 169 | | Dictionary<string, FieldDefinition> fields, |
| | | 170 | | string name, |
| | | 171 | | Dictionary<ulong, List<string>> byFingerprint, |
| | | 172 | | ulong expectedFingerprint, |
| | | 173 | | List<string> bucket) |
| | | 174 | | { |
| | 4878 | 175 | | for (var i = bucket.Count - 1; i >= 0; i--) |
| | | 176 | | { |
| | 1230 | 177 | | var key = bucket[i]; |
| | | 178 | | |
| | | 179 | | // The key itself can vanish from the root dictionary between indexing and this read |
| | | 180 | | // only via a path that changes Count (caught by EnsureSynced above and rebuilt from |
| | | 181 | | // scratch) — so fields.TryGetValue here is expected to always hit. Guard defensively |
| | | 182 | | // rather than throw: treat a miss as "no longer a candidate" and drop it. |
| | 1230 | 183 | | if (!fields.TryGetValue(key, out var liveField)) |
| | | 184 | | { |
| | 3 | 185 | | bucket.RemoveAt(i); |
| | | 186 | | |
| | | 187 | | // _keyFingerprint[name] is written in lock-step with every _byNameFingerprint bucket |
| | | 188 | | // insertion (see SetKeyFingerprint), so reaching a populated bucket under `name` |
| | | 189 | | // guarantees the per-name reverse map already exists. |
| | 3 | 190 | | _keyFingerprint[name].Remove(key); |
| | 3 | 191 | | continue; |
| | | 192 | | } |
| | | 193 | | |
| | 1227 | 194 | | var liveFingerprint = FieldDefinitionExtensions.ComputeDeepFingerprint(liveField); |
| | 1227 | 195 | | if (liveFingerprint == expectedFingerprint) continue; |
| | | 196 | | |
| | 6 | 197 | | bucket.RemoveAt(i); |
| | 6 | 198 | | GetOrCreateFingerprintBucket(byFingerprint, liveFingerprint).Add(key); |
| | 6 | 199 | | SetKeyFingerprint(name, key, liveFingerprint); |
| | | 200 | | } |
| | 1209 | 201 | | } |
| | | 202 | | |
| | | 203 | | /// <summary> |
| | | 204 | | /// Notifies the index that the field at <paramref name="key"/> (sharing <paramref name="name"/>) |
| | | 205 | | /// was just mutated in place by <see cref="FieldDefinitionExtensions.MergeFieldsInPlace"/> and |
| | | 206 | | /// its deep fingerprint may have changed, so it must be re-bucketed under its new live |
| | | 207 | | /// fingerprint. Must be called immediately after every in-place merge that goes through |
| | | 208 | | /// <see cref="FieldDefinitionExtensions.MergeFieldsInPlace"/> — otherwise the entry would sit |
| | | 209 | | /// under its stale pre-merge fingerprint until it happens to be visited and healed by |
| | | 210 | | /// <see cref="GetMergeCandidatesByFingerprint"/> for that old bucket, which a bucketing scheme |
| | | 211 | | /// keyed on the NEW fingerprint would never trigger on its own. |
| | | 212 | | /// </summary> |
| | | 213 | | public void ReindexFingerprint(Dictionary<string, FieldDefinition> fields, string name, string key) |
| | | 214 | | { |
| | | 215 | | // If this name's fingerprint sub-buckets were never built, there is nothing to fix — the |
| | | 216 | | // next GetMergeCandidatesByFingerprint call for this name builds them fresh from the live |
| | | 217 | | // (already-mutated) fields, picking up the correct fingerprint directly. |
| | 981 | 218 | | if (!_byNameFingerprint.TryGetValue(name, out var byFingerprint)) return; |
| | 978 | 219 | | if (!fields.TryGetValue(key, out var liveField)) return; |
| | | 220 | | |
| | 972 | 221 | | liveField.EnsureMergeMemoTracker().Attach(_memoScope); |
| | 972 | 222 | | var liveFingerprint = FieldDefinitionExtensions.ComputeDeepFingerprint(liveField); |
| | | 223 | | |
| | | 224 | | // Remove the key from whichever bucket currently holds it. _keyFingerprint[name] records |
| | | 225 | | // exactly that bucket's fingerprint, so this is an O(1) dictionary lookup + O(bucket size) |
| | | 226 | | // removal from that ONE bucket — never a scan across every fingerprint bucket under the |
| | | 227 | | // name. That per-name scan was the quadratic hazard this reverse index exists to remove: |
| | | 228 | | // the production shape accumulates many singleton buckets (one per distinct incoming |
| | | 229 | | // filter) under one name, so scanning all of them on every successful merge was O(N) per |
| | | 230 | | // merge / O(N^2) over a chain of N Includes. A miss here (key not yet tracked, e.g. it was |
| | | 231 | | // added to _byName but its fingerprint buckets were built before this key existed under an |
| | | 232 | | // old code path) is harmless — it just means there is no stale bucket entry to remove. |
| | 972 | 233 | | if (_keyFingerprint.TryGetValue(name, out var perName) |
| | 972 | 234 | | && perName.TryGetValue(key, out var oldFingerprint) |
| | 972 | 235 | | && oldFingerprint != liveFingerprint |
| | 972 | 236 | | && byFingerprint.TryGetValue(oldFingerprint, out var oldBucket)) |
| | | 237 | | { |
| | 3 | 238 | | oldBucket.Remove(key); |
| | | 239 | | } |
| | | 240 | | |
| | 972 | 241 | | var targetBucket = GetOrCreateFingerprintBucket(byFingerprint, liveFingerprint); |
| | 972 | 242 | | if (!targetBucket.Contains(key)) |
| | | 243 | | { |
| | 3 | 244 | | targetBucket.Add(key); |
| | | 245 | | } |
| | 972 | 246 | | SetKeyFingerprint(name, key, liveFingerprint); |
| | 972 | 247 | | } |
| | | 248 | | |
| | | 249 | | private void EnsureFingerprintEpochCurrent() |
| | | 250 | | { |
| | 1962 | 251 | | var liveEpoch = _memoScope.Version; |
| | 3564 | 252 | | if (liveEpoch == _syncedMergeMemoEpoch) return; |
| | | 253 | | |
| | 360 | 254 | | _byNameFingerprint.Clear(); |
| | 360 | 255 | | _fingerprintBucketsBuilt.Clear(); |
| | 360 | 256 | | _keyFingerprint.Clear(); |
| | 360 | 257 | | _syncedMergeMemoEpoch = liveEpoch; |
| | 360 | 258 | | } |
| | | 259 | | |
| | | 260 | | // Returns `name`'s fingerprint sub-index, building it on first use for this synced/epoch |
| | | 261 | | // generation. Always returns a live, non-null dictionary (created here if absent) — callers |
| | | 262 | | // never need to re-check for its existence afterwards. |
| | | 263 | | private Dictionary<ulong, List<string>> EnsureFingerprintBucketsBuilt(Dictionary<string, FieldDefinition> fields, st |
| | | 264 | | { |
| | 1962 | 265 | | if (_fingerprintBucketsBuilt.Contains(name)) |
| | | 266 | | { |
| | 1338 | 267 | | return _byNameFingerprint[name]; |
| | | 268 | | } |
| | | 269 | | |
| | 624 | 270 | | var byFingerprint = new Dictionary<ulong, List<string>>(); |
| | 624 | 271 | | _byNameFingerprint[name] = byFingerprint; |
| | | 272 | | |
| | 624 | 273 | | if (_byName.TryGetValue(name, out var keys)) |
| | | 274 | | { |
| | 1710 | 275 | | foreach (var key in keys) |
| | | 276 | | { |
| | 438 | 277 | | if (!fields.TryGetValue(key, out var field)) continue; |
| | 438 | 278 | | field.EnsureMergeMemoTracker().Attach(_memoScope); |
| | 438 | 279 | | var fingerprint = FieldDefinitionExtensions.ComputeDeepFingerprint(field); |
| | | 280 | | |
| | 438 | 281 | | GetOrCreateFingerprintBucket(byFingerprint, fingerprint).Add(key); |
| | 438 | 282 | | SetKeyFingerprint(name, key, fingerprint); |
| | | 283 | | } |
| | | 284 | | } |
| | | 285 | | |
| | 624 | 286 | | _fingerprintBucketsBuilt.Add(name); |
| | 624 | 287 | | return byFingerprint; |
| | | 288 | | } |
| | | 289 | | |
| | | 290 | | /// <summary> |
| | | 291 | | /// Produces the next unique key for <paramref name="baseKey"/> in O(1) amortized time: a |
| | | 292 | | /// per-base-name counter is advanced past every suffix already handed out, instead of |
| | | 293 | | /// rebuilding a <see cref="HashSet{T}"/> from all existing keys on every call (the prior |
| | | 294 | | /// quadratic source — <c>AddFieldWithUniqueKey</c> was calling |
| | | 295 | | /// <c>KeyGenerator.GenerateUniqueKey(name, fields.Keys)</c>, an O(N) rebuild, for every one of |
| | | 296 | | /// N inserted fields). |
| | | 297 | | /// </summary> |
| | | 298 | | public string NextUniqueKey(Dictionary<string, FieldDefinition> fields, string baseKey) |
| | | 299 | | { |
| | 924 | 300 | | EnsureSynced(fields); |
| | | 301 | | |
| | 924 | 302 | | if (!_allKeys.Contains(baseKey)) |
| | | 303 | | { |
| | 315 | 304 | | return baseKey; |
| | | 305 | | } |
| | | 306 | | |
| | 609 | 307 | | var counter = _suffixCounters.GetValueOrDefault(baseKey, 0); |
| | | 308 | | string candidate; |
| | | 309 | | do |
| | | 310 | | { |
| | 618 | 311 | | counter++; |
| | 618 | 312 | | candidate = $"{baseKey}_{counter}"; |
| | 618 | 313 | | } while (_allKeys.Contains(candidate)); |
| | | 314 | | |
| | 609 | 315 | | _suffixCounters[baseKey] = counter; |
| | 609 | 316 | | return candidate; |
| | | 317 | | } |
| | | 318 | | |
| | | 319 | | private void EnsureSynced(Dictionary<string, FieldDefinition> fields) |
| | | 320 | | { |
| | 5508 | 321 | | if (fields.Count == _syncedCount) return; |
| | | 322 | | |
| | 264 | 323 | | _byName.Clear(); |
| | 264 | 324 | | _byNameFingerprint.Clear(); |
| | 264 | 325 | | _fingerprintBucketsBuilt.Clear(); |
| | 264 | 326 | | _keyFingerprint.Clear(); |
| | 264 | 327 | | _allKeys.Clear(); |
| | 264 | 328 | | _suffixCounters.Clear(); |
| | 1074 | 329 | | foreach (var (key, field) in fields) |
| | | 330 | | { |
| | 273 | 331 | | GetOrCreateBucket(field.Name).Add(key); |
| | 273 | 332 | | _allKeys.Add(key); |
| | | 333 | | } |
| | 264 | 334 | | _syncedCount = fields.Count; |
| | | 335 | | |
| | | 336 | | // The fingerprint sub-buckets were just cleared and will rebuild lazily against the |
| | | 337 | | // now-current field tree — resync the epoch snapshot too, so EnsureFingerprintEpochCurrent |
| | | 338 | | // does not immediately consider that fresh rebuild stale on the very next check. |
| | 264 | 339 | | _syncedMergeMemoEpoch = _memoScope.Version; |
| | 264 | 340 | | } |
| | | 341 | | } |