< Summary

Information
Class: Trailblazer.Pathing.NavigationOperationProcessor
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Map/Operations/NavigationOperationProcessor.cs
Line coverage
100%
Covered lines: 564
Uncovered lines: 0
Coverable lines: 564
Total lines: 883
Line coverage: 100%
Branch coverage
100%
Covered branches: 232
Total branches: 232
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%11100%
get_Candidate()100%11100%
get_CoverageScratchBytes()100%11100%
get_RetainedOperationWorkBytes()100%22100%
get_RetainedOperationWorkPageCount()100%11100%
get_RetainedOperationWorkCount()100%66100%
RejectDeferredCapacity()100%22100%
Reset()100%22100%
Admit(...)100%11100%
Admit(...)100%11100%
Admit(...)100%11100%
ProcessFrame(...)100%11100%
ProcessFrame(...)100%116116100%
Admit(...)100%88100%
GetAdmissionRejection(...)100%2626100%
AdvanceSupersedence(...)100%4242100%
CompleteSupersedenceOperation()100%11100%
ResetSupersedence()100%11100%
WouldExceed(...)100%11100%
GetFixedScratchBytes(...)100%11100%
GetActiveAdditionalRetainedBytes()100%88100%
GetActiveAdditionalPersistentPages()100%88100%
GetAdditionalRetainedBytes(...)100%11100%
GetAdditionalPersistentPages(...)100%11100%
GetAdditionalRetainedBytes(...)100%11100%
GetAdditionalPersistentPages(...)100%11100%
GetAdditionalExplicitPayloadBytes(...)100%11100%
GetAdditionalExplicitPayloadPages(...)100%11100%
GetAdditionalMapStatePayloadBytes(...)100%11100%
GetAdditionalMapStatePayloadPages(...)100%11100%
GetPositiveNonPayloadRetainedDelta(...)100%11100%
GetPositiveNonPayloadPageDelta(...)100%11100%
GetPositiveRetainedDelta(...)100%11100%
GetPositivePersistentPageDelta(...)100%11100%
RemovePrefix(...)100%11100%
RemoveRange(...)100%66100%
.ctor(...)100%11100%
Equals(...)100%11100%
GetHashCode()100%11100%
.ctor(...)100%11100%
get_IsMapOperation()100%22100%
ToFrameChange()100%44100%
ForMapCommit(...)100%11100%
ForMapRemove(...)100%11100%
ForOverlay(...)100%11100%
GetOverlayCoverageScratchBytes(...)100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Map/Operations/NavigationOperationProcessor.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationOperationProcessor.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using FixedMathSharp;
 10using GridForge.Grids.Topology;
 11using SwiftCollections;
 12using SwiftCollections.Utility;
 13
 14namespace Trailblazer.Pathing;
 15
 16/// <summary>
 17/// Executes map and overlay candidates against persistent graph roots.
 18/// </summary>
 19internal sealed class NavigationOperationProcessor
 20{
 21    private const int BaseCoalescingScratchBytes = 2_048;
 22    private const int FixedScratchBytesPerOperation = 8;
 23    private const int MapCoverageScratchBytes = 64;
 24
 25    private readonly NavigationOperationLimits _limits;
 26    private readonly int _maxBakedCellsPerMap;
 27    private readonly int _navigationAreaCount;
 130228    private readonly SwiftList<PendingOperation> _pending = new();
 29    private NavigationOperationCandidate _candidate;
 30    private readonly GridCellPrism[] _corridorPrisms;
 31    private readonly Vector3d[] _corridorWaypoints;
 32    private readonly NavigationCellAddress[] _corridorAddresses;
 33    private readonly NavigationAddressStampSet _corridorAddressSet;
 130234    private readonly MaintenanceWorkMeter _unboundedMaintenanceMeter = new(
 130235        new MaintenanceWorkBudget(
 130236            int.MaxValue,
 130237            int.MaxValue,
 130238            int.MaxValue,
 130239            int.MaxValue,
 130240            int.MaxValue,
 130241            int.MaxValue,
 130242            int.MaxValue,
 130243            int.MaxValue));
 44    private readonly NavigationOperationRejection[] _outcomes;
 45    private readonly bool[] _superseded;
 46    private readonly NavigationOperationFrameChange[] _changes;
 47    private readonly SwiftHashSet<string> _mapOverwriters;
 48    private readonly SwiftHashSet<NavigationCellAddress> _coveredCells;
 49    private readonly SwiftHashSet<OverlayIdKey> _coveredConnections;
 50    private readonly SwiftHashSet<OverlayIdKey> _coveredTransitions;
 51    private readonly long _coverageScratchBytes;
 52
 53    private long _pendingDescriptorBytes;
 54    private long _pendingPreparedMapBytes;
 55    private long _sequenceHighWater;
 130256    private int _effectiveFrameHighWater = -1;
 130257    private int _lastProcessedFrame = -1;
 58    private int _deferredPrefixCount;
 59    private int _foldOperationIndex;
 60    private NavigationMapFoldWork? _mapFoldWork;
 61    private NavigationOverlayFoldWork? _overlayFoldWork;
 62    private NavigationOperationCandidate? _sourceCandidateForDeferred;
 63    private NavigationOperationCandidate? _deferredCandidate;
 64    private NavigationOperationCandidate? _activeFoldSourceCandidate;
 65    private bool _supersedenceActive;
 66    private int _supersedenceIndex;
 67    private int _supersedenceMapIndex;
 68    private int _supersedenceKind;
 69    private int _supersedenceItemIndex;
 70    private bool _supersedenceCovered;
 71    private bool _supersedenceComplete;
 72
 130273    internal NavigationOperationProcessor(
 130274        NavigationOperationLimits limits,
 130275        int maxBakedCellsPerMap = int.MaxValue,
 130276        int navigationAreaCount = ushort.MaxValue + 1)
 77    {
 130278        SwiftThrowHelper.ThrowIfArgument(
 130279            GetFixedScratchBytes(limits.MaxBatchItems) > limits.MaxBatchSortScratchBytes,
 130280            nameof(limits),
 130281            "Batch scratch capacity is smaller than the processor's fixed batch storage.");
 130282        _limits = limits;
 130283        _maxBakedCellsPerMap = maxBakedCellsPerMap;
 130284        _navigationAreaCount = navigationAreaCount;
 130285        _candidate = new NavigationOperationCandidate(navigationAreaCount);
 130286        _corridorPrisms = new GridCellPrism[limits.MaxCorridorCells];
 130287        _corridorWaypoints = new Vector3d[checked((limits.MaxCorridorCells - 1) * 2)];
 130288        _corridorAddresses = new NavigationCellAddress[limits.MaxCorridorCells];
 130289        _corridorAddressSet = new NavigationAddressStampSet(limits.MaxCorridorCells);
 130290        _outcomes = new NavigationOperationRejection[limits.MaxBatchItems];
 130291        _superseded = new bool[limits.MaxBatchItems];
 130292        _changes = new NavigationOperationFrameChange[limits.MaxBatchItems];
 130293        _mapOverwriters = new SwiftHashSet<string>(
 130294            limits.MaxMaps,
 130295            SwiftHashTools.GetDeterministicStringEqualityComparer());
 130296        _coveredCells = new SwiftHashSet<NavigationCellAddress>(
 130297            Math.Max(SwiftHashSet<NavigationCellAddress>.DefaultCapacity, limits.MaxOverlayCells));
 130298        _coveredConnections = new SwiftHashSet<OverlayIdKey>(
 130299            Math.Max(SwiftHashSet<OverlayIdKey>.DefaultCapacity, limits.MaxOverlayConnections));
 1302100        _coveredTransitions = new SwiftHashSet<OverlayIdKey>(
 1302101            Math.Max(SwiftHashSet<OverlayIdKey>.DefaultCapacity, limits.MaxOverlayTransitions));
 1302102        _coverageScratchBytes = checked(
 1302103            ((long)SwiftHashTools.NextPowerOfTwo(Math.Max(8, limits.MaxMaps)) * 32L)
 1302104            + ((long)SwiftHashTools.NextPowerOfTwo(Math.Max(8, limits.MaxOverlayCells)) * 40L)
 1302105            + ((long)SwiftHashTools.NextPowerOfTwo(Math.Max(8, limits.MaxOverlayConnections)) * 48L)
 1302106            + ((long)SwiftHashTools.NextPowerOfTwo(Math.Max(8, limits.MaxOverlayTransitions)) * 48L));
 1302107    }
 108
 2049109    internal NavigationOperationCandidate Candidate => _candidate;
 110
 5111    internal long CoverageScratchBytes => _coverageScratchBytes;
 112
 53815113    internal long RetainedOperationWorkBytes => checked(
 53815114        GetActiveAdditionalRetainedBytes()
 53815115        + (_supersedenceActive ? _coverageScratchBytes : 0));
 116
 54157117    internal int RetainedOperationWorkPageCount => GetActiveAdditionalPersistentPages();
 118
 119    internal int RetainedOperationWorkCount =>
 54369120        _mapFoldWork != null
 54369121        || _overlayFoldWork != null
 54369122        || _deferredCandidate != null
 54369123            ? 1
 54369124            : 0;
 125
 126    internal void RejectDeferredCapacity()
 127    {
 3128        int count = Math.Min(_deferredPrefixCount, _pending.Count);
 129        System.Diagnostics.Debug.Assert(_sourceCandidateForDeferred != null);
 3130        _candidate = _sourceCandidateForDeferred!;
 12131        for (int i = 0; i < count; i++)
 3132            _pending[i].Receipt.CompleteRejected(NavigationOperationRejection.CapacityExceeded);
 3133        RemovePrefix(count);
 3134        _deferredPrefixCount = 0;
 3135        _foldOperationIndex = 0;
 3136        _mapFoldWork = null;
 3137        _overlayFoldWork = null;
 3138        _sourceCandidateForDeferred = null;
 3139        _deferredCandidate = null;
 3140        _activeFoldSourceCandidate = null;
 3141        ResetSupersedence();
 3142    }
 143
 144    internal void Reset()
 145    {
 50146        for (int i = 0; i < _pending.Count; i++)
 2147            _pending[i].Receipt.CompleteSuperseded();
 23148        _pending.Clear();
 23149        _candidate = new NavigationOperationCandidate(_navigationAreaCount);
 23150        _pendingDescriptorBytes = 0;
 23151        _pendingPreparedMapBytes = 0;
 23152        _sequenceHighWater = 0;
 23153        _effectiveFrameHighWater = -1;
 23154        _lastProcessedFrame = -1;
 23155        _deferredPrefixCount = 0;
 23156        _foldOperationIndex = 0;
 23157        _mapFoldWork = null;
 23158        _overlayFoldWork = null;
 23159        _sourceCandidateForDeferred = null;
 23160        _deferredCandidate = null;
 23161        _activeFoldSourceCandidate = null;
 23162        ResetSupersedence();
 23163        _mapOverwriters.Clear();
 23164        _coveredCells.Clear();
 23165        _coveredConnections.Clear();
 23166        _coveredTransitions.Clear();
 23167    }
 168
 169    internal bool Admit(NavigationMapCommitOperation operation)
 170    {
 1311171        SwiftThrowHelper.ThrowIfNull(operation.PreparedMap, nameof(operation));
 1311172        return Admit(PendingOperation.ForMapCommit(operation));
 173    }
 174
 175    internal bool Admit(NavigationMapRemoveOperation operation)
 176    {
 22177        SwiftThrowHelper.ThrowIfNull(operation.MapId, nameof(operation));
 22178        return Admit(PendingOperation.ForMapRemove(operation));
 179    }
 180
 181    internal bool Admit(NavigationOverlayCommitOperation operation)
 182    {
 286183        SwiftThrowHelper.ThrowIfNull(operation.PreparedOverlay, nameof(operation));
 286184        return Admit(PendingOperation.ForOverlay(operation));
 185    }
 186
 187    internal void ProcessFrame(int frame)
 188    {
 184189        ProcessFrame(frame, static (_, _, _, _) => NavigationCandidatePublication.Published);
 184190    }
 191
 192    internal NavigationOperationFrameResult ProcessFrame(
 193        int frame,
 194        NavigationCandidatePublisher publishCandidate,
 195        MaintenanceWorkMeter? maintenanceMeter = null,
 196        NavigationRetainedWorkGuard? retainedWorkGuard = null)
 197    {
 17189198        SwiftThrowHelper.ThrowIfNull(publishCandidate, nameof(publishCandidate));
 17189199        SwiftThrowHelper.ThrowIfArgument(frame <= _lastProcessedFrame, nameof(frame));
 17189200        _lastProcessedFrame = frame;
 17189201        if (maintenanceMeter == null)
 202        {
 186203            _unboundedMaintenanceMeter.Reset();
 186204            maintenanceMeter = _unboundedMaintenanceMeter;
 205        }
 17189206        int eligibleCount = 0;
 17189207        long batchDescriptorBytes = 0;
 17189208        long batchScratchBytes = GetFixedScratchBytes(_limits.MaxBatchItems);
 17189209        int maximumEligible = _deferredPrefixCount == 0
 17189210            ? _pending.Count
 17189211            : Math.Min(_deferredPrefixCount, _pending.Count);
 59910212        while (eligibleCount < maximumEligible && _pending[eligibleCount].EffectiveFrame <= frame)
 213        {
 42724214            PendingOperation operation = _pending[eligibleCount];
 42724215            if (eligibleCount >= _limits.MaxBatchItems
 42724216                || WouldExceed(batchDescriptorBytes, operation.DescriptorBytes, _limits.MaxBatchDescriptorBytes)
 42724217                || WouldExceed(batchScratchBytes, operation.CoalescingScratchBytes, _limits.MaxBatchSortScratchBytes))
 218            {
 219                break;
 220            }
 221
 42721222            batchDescriptorBytes += operation.DescriptorBytes;
 42721223            batchScratchBytes += operation.CoalescingScratchBytes;
 42721224            eligibleCount++;
 225        }
 226
 17189227        NavigationOperationCandidate published = _sourceCandidateForDeferred ?? _candidate;
 17189228        NavigationOperationCandidate working = _deferredCandidate
 17189229            ?? (eligibleCount > 0 ? _candidate.Clone() : _candidate);
 17189230        _candidate = working;
 17189231        int foldStart = _deferredPrefixCount == 0 ? 0 : _foldOperationIndex;
 17189232        if (_mapFoldWork != null)
 2346233            _candidate = _mapFoldWork.Candidate;
 14843234        else if (_overlayFoldWork != null)
 185235            _candidate = _overlayFoldWork.Candidate;
 37570236        for (int i = foldStart; i < eligibleCount; i++)
 237        {
 4130238            if (_pending[i].Kind is PendingOperationKind.MapCommit or PendingOperationKind.MapRemove)
 239            {
 3661240                _mapFoldWork ??= _pending[i].Kind == PendingOperationKind.MapCommit
 3661241                    ? new NavigationMapFoldWork(
 3661242                        _candidate,
 3661243                        _pending[i].PreparedMap!,
 3661244                        _pending[i].ReplacementPolicy,
 3661245                        _limits,
 3661246                        _corridorPrisms,
 3661247                        _corridorWaypoints,
 3661248                        _corridorAddresses,
 3661249                        _corridorAddressSet)
 3661250                    : new NavigationMapFoldWork(
 3661251                        _candidate,
 3661252                        _pending[i].MapId!,
 3661253                        _corridorPrisms,
 3661254                        _corridorWaypoints,
 3661255                        _corridorAddresses,
 3661256                        _corridorAddressSet);
 3661257                _activeFoldSourceCandidate ??= _candidate;
 3661258                _foldOperationIndex = i;
 3661259                if (retainedWorkGuard != null
 3661260                    && !retainedWorkGuard(
 3661261                        GetAdditionalRetainedBytes(_mapFoldWork, published),
 3661262                        GetAdditionalPersistentPages(_mapFoldWork, published)))
 263                {
 2264                    _outcomes[i] = NavigationOperationRejection.CapacityExceeded;
 2265                    _candidate = _activeFoldSourceCandidate;
 2266                    _mapFoldWork = null;
 2267                    _activeFoldSourceCandidate = null;
 2268                    _foldOperationIndex = i + 1;
 2269                    _superseded[i] = false;
 2270                    continue;
 271                }
 3659272                if (!_mapFoldWork.Advance(maintenanceMeter, out _outcomes[i]))
 273                {
 2346274                    _sourceCandidateForDeferred ??= published;
 2346275                    _deferredCandidate = _mapFoldWork.Candidate;
 2346276                    _candidate = published;
 2346277                    _deferredPrefixCount = eligibleCount;
 2346278                    return NavigationOperationFrameResult.Deferred;
 279                }
 1313280                if (_outcomes[i] == NavigationOperationRejection.None
 1313281                    && retainedWorkGuard != null
 1313282                    && !retainedWorkGuard(
 1313283                        GetAdditionalRetainedBytes(_mapFoldWork, published),
 1313284                        GetAdditionalPersistentPages(_mapFoldWork, published)))
 285                {
 2286                    _outcomes[i] = NavigationOperationRejection.CapacityExceeded;
 287                }
 1313288                if (_outcomes[i] == NavigationOperationRejection.None)
 1282289                    _candidate = _mapFoldWork.Candidate;
 290                else
 31291                    _candidate = _activeFoldSourceCandidate!;
 1313292                _mapFoldWork = null;
 1313293                _activeFoldSourceCandidate = null;
 1313294                _foldOperationIndex = i + 1;
 295            }
 296            else
 297            {
 469298                _overlayFoldWork ??= new NavigationOverlayFoldWork(
 469299                    _candidate,
 469300                    _pending[i].PreparedOverlay!.Transaction,
 469301                    _pending[i].OperationSequence,
 469302                    _limits,
 469303                    _corridorPrisms,
 469304                    _corridorWaypoints,
 469305                    _corridorAddresses,
 469306                    _corridorAddressSet);
 469307                _activeFoldSourceCandidate ??= _candidate;
 469308                _foldOperationIndex = i;
 469309                if (retainedWorkGuard != null
 469310                    && !retainedWorkGuard(
 469311                        GetAdditionalRetainedBytes(_overlayFoldWork, published),
 469312                        GetAdditionalPersistentPages(_overlayFoldWork, published)))
 313                {
 1314                    _outcomes[i] = NavigationOperationRejection.CapacityExceeded;
 1315                    _candidate = _activeFoldSourceCandidate;
 1316                    _overlayFoldWork = null;
 1317                    _activeFoldSourceCandidate = null;
 1318                    _foldOperationIndex = i + 1;
 1319                    _superseded[i] = false;
 1320                    continue;
 321                }
 468322                if (!_overlayFoldWork.Advance(maintenanceMeter, out _outcomes[i]))
 323                {
 188324                    _sourceCandidateForDeferred ??= published;
 188325                    _deferredCandidate = _overlayFoldWork.Candidate;
 188326                    _candidate = published;
 188327                    _deferredPrefixCount = eligibleCount;
 188328                    return NavigationOperationFrameResult.Deferred;
 329                }
 280330                if (_outcomes[i] == NavigationOperationRejection.None
 280331                    && retainedWorkGuard != null
 280332                    && !retainedWorkGuard(
 280333                        GetAdditionalRetainedBytes(_overlayFoldWork, published),
 280334                        GetAdditionalPersistentPages(_overlayFoldWork, published)))
 335                {
 1336                    _outcomes[i] = NavigationOperationRejection.CapacityExceeded;
 337                }
 280338                if (_outcomes[i] == NavigationOperationRejection.None)
 262339                    _candidate = _overlayFoldWork.Candidate;
 340                else
 18341                    _candidate = _activeFoldSourceCandidate!;
 280342                _overlayFoldWork = null;
 280343                _activeFoldSourceCandidate = null;
 280344                _foldOperationIndex = i + 1;
 345            }
 1593346            _foldOperationIndex = i + 1;
 1593347            _superseded[i] = false;
 348        }
 349
 14655350        if (retainedWorkGuard != null
 14655351            && !retainedWorkGuard(
 14655352                checked(GetPositiveRetainedDelta(_candidate, published) + _coverageScratchBytes),
 14655353                GetPositivePersistentPageDelta(_candidate, published)))
 354        {
 21355            _candidate = published;
 86356            for (int i = 0; i < eligibleCount; i++)
 357            {
 22358                if (_outcomes[i] == NavigationOperationRejection.None)
 19359                    _outcomes[i] = NavigationOperationRejection.CapacityExceeded;
 360            }
 21361            ResetSupersedence();
 362        }
 14634363        else if (!AdvanceSupersedence(eligibleCount, maintenanceMeter))
 364        {
 116365            _sourceCandidateForDeferred ??= published;
 116366            _deferredCandidate = _candidate;
 116367            _candidate = published;
 116368            _deferredPrefixCount = eligibleCount;
 116369            return NavigationOperationFrameResult.Deferred;
 370        }
 371
 14539372        int changeCount = 0;
 105958373        for (int i = 0; i < eligibleCount; i++)
 374        {
 38440375            if (_outcomes[i] == NavigationOperationRejection.None)
 38369376                _changes[changeCount++] = _pending[i].ToFrameChange();
 377        }
 14539378        NavigationCandidatePublication publication = eligibleCount > 0
 14539379            ? publishCandidate(_candidate, frame, _changes, changeCount)
 14539380            : NavigationCandidatePublication.Published;
 14539381        if (publication == NavigationCandidatePublication.Deferred)
 382        {
 10861383            _sourceCandidateForDeferred ??= published;
 10861384            _deferredCandidate = _candidate;
 10861385            if (_deferredPrefixCount == 0)
 114386                _deferredPrefixCount = eligibleCount;
 10861387            _candidate = published;
 10861388            return NavigationOperationFrameResult.Deferred;
 389        }
 3678390        if (publication == NavigationCandidatePublication.PermanentCapacity)
 391        {
 176392            _candidate = published;
 706393            for (int i = 0; i < eligibleCount; i++)
 394            {
 177395                if (_outcomes[i] == NavigationOperationRejection.None)
 176396                    _outcomes[i] = NavigationOperationRejection.CapacityExceeded;
 397            }
 398        }
 399
 10536400        for (int i = 0; i < eligibleCount; i++)
 401        {
 1590402            PendingOperation operation = _pending[i];
 1590403            if (_outcomes[i] != NavigationOperationRejection.None)
 247404                operation.Receipt.CompleteRejected(_outcomes[i]);
 1343405            else if (_superseded[i])
 14406                operation.Receipt.CompleteSuperseded();
 407            else
 1329408                operation.Receipt.CompleteApplied(frame);
 409        }
 410
 3678411        RemovePrefix(eligibleCount);
 3678412        if (publication == NavigationCandidatePublication.Published)
 3502413            _candidate.ResetWorkCopiedPersistentOwnership();
 3678414        _deferredPrefixCount = 0;
 3678415        _foldOperationIndex = 0;
 3678416        _mapFoldWork = null;
 3678417        _overlayFoldWork = null;
 3678418        _sourceCandidateForDeferred = null;
 3678419        _deferredCandidate = null;
 3678420        _activeFoldSourceCandidate = null;
 3678421        ResetSupersedence();
 3678422        if (eligibleCount == 0)
 2337423            return NavigationOperationFrameResult.None;
 1341424        return publication == NavigationCandidatePublication.Published
 1341425            ? NavigationOperationFrameResult.Published
 1341426            : NavigationOperationFrameResult.Rejected;
 427    }
 428
 429    private bool Admit(PendingOperation operation)
 430    {
 1619431        if (!operation.Receipt.TryClaimAdmission())
 2432            return false;
 433
 1617434        NavigationOperationRejection rejection = GetAdmissionRejection(operation);
 1617435        bool advancesSequence = operation.OperationSequence > _sequenceHighWater;
 1617436        if (advancesSequence)
 437        {
 1614438            _sequenceHighWater = operation.OperationSequence;
 1614439            if (operation.EffectiveFrame > _effectiveFrameHighWater)
 1358440                _effectiveFrameHighWater = operation.EffectiveFrame;
 441        }
 442
 1617443        if (rejection != NavigationOperationRejection.None)
 444        {
 14445            operation.Receipt.CompleteRejected(rejection);
 14446            return false;
 447        }
 448
 1603449        _pending.Add(operation);
 1603450        _pendingDescriptorBytes += operation.DescriptorBytes;
 1603451        _pendingPreparedMapBytes += operation.PreparedMapBytes;
 1603452        return true;
 453    }
 454
 455    private NavigationOperationRejection GetAdmissionRejection(PendingOperation operation)
 456    {
 1617457        if (operation.OperationSequence == _sequenceHighWater)
 2458            return NavigationOperationRejection.DuplicateSequence;
 1615459        if (operation.OperationSequence < _sequenceHighWater)
 1460            return NavigationOperationRejection.RegressingSequence;
 1614461        if (operation.EffectiveFrame < _effectiveFrameHighWater)
 1462            return NavigationOperationRejection.RegressingEffectiveFrame;
 1613463        if (operation.EffectiveFrame <= _lastProcessedFrame)
 1464            return NavigationOperationRejection.LateEffectiveFrame;
 1612465        long fixedScratchBytes = GetFixedScratchBytes(_limits.MaxBatchItems);
 1612466        if (operation.DescriptorBytes > _limits.MaxBatchDescriptorBytes
 1612467            || (operation.Kind == PendingOperationKind.MapCommit
 1612468                && operation.PreparedMap!.Map.Cells.Count > _maxBakedCellsPerMap)
 1612469            || (operation.Kind == PendingOperationKind.MapCommit
 1612470                && operation.PreparedMap!.Map.TransitionRuleSpan.Length
 1612471                    > _limits.MaxTransitionRulesPerMap)
 1612472            || WouldExceed(fixedScratchBytes, operation.CoalescingScratchBytes, _limits.MaxBatchSortScratchBytes)
 1612473            || _pending.Count >= _limits.MaxPendingOperations
 1612474            || WouldExceed(_pendingDescriptorBytes, operation.DescriptorBytes, _limits.MaxPendingDescriptorBytes)
 1612475            || WouldExceed(_pendingPreparedMapBytes, operation.PreparedMapBytes, _limits.MaxPreparedMapBytes))
 476        {
 9477            return NavigationOperationRejection.CapacityExceeded;
 478        }
 479
 1603480        return NavigationOperationRejection.None;
 481    }
 482
 483    private bool AdvanceSupersedence(int eligibleCount, MaintenanceWorkMeter meter)
 484    {
 14634485        if (_supersedenceComplete)
 10854486            return true;
 3780487        if (!_supersedenceActive)
 488        {
 3664489            _mapOverwriters.Clear();
 3664490            _coveredCells.Clear();
 3664491            _coveredConnections.Clear();
 3664492            _coveredTransitions.Clear();
 3664493            _supersedenceIndex = eligibleCount - 1;
 3664494            _supersedenceMapIndex = 0;
 3664495            _supersedenceKind = 0;
 3664496            _supersedenceItemIndex = 0;
 3664497            _supersedenceCovered = true;
 3664498            _supersedenceActive = true;
 499        }
 5355500        while (_supersedenceIndex >= 0)
 501        {
 1691502            if (_outcomes[_supersedenceIndex] != NavigationOperationRejection.None)
 503            {
 49504                CompleteSupersedenceOperation();
 49505                continue;
 506            }
 1642507            PendingOperation operation = _pending[_supersedenceIndex];
 1642508            if (operation.IsMapOperation)
 509            {
 1317510                if (!meter.TryConsumeComponentNodes(1))
 45511                    return false;
 1272512                _superseded[_supersedenceIndex] = _mapOverwriters.Contains(operation.MapId!);
 1272513                if (operation.Kind == PendingOperationKind.MapRemove
 1272514                    || operation.ReplacementPolicy == OverlayReplacementPolicy.Clear)
 515                {
 1264516                    _mapOverwriters.Add(operation.MapId!);
 517                }
 1272518                CompleteSupersedenceOperation();
 1272519                continue;
 520            }
 521
 325522            ReadOnlySpan<NavigationMapOverlayDelta> maps =
 325523                operation.PreparedOverlay!.Transaction.MapSpan;
 596524            while (_supersedenceMapIndex < maps.Length)
 525            {
 342526                NavigationMapOverlayDelta map = maps[_supersedenceMapIndex];
 342527                if (_mapOverwriters.Contains(map.MapId))
 528                {
 1529                    _supersedenceMapIndex++;
 1530                    _supersedenceKind = 0;
 1531                    _supersedenceItemIndex = 0;
 1532                    continue;
 533                }
 1961534                while (_supersedenceKind < 6)
 535                {
 1691536                    int count = _supersedenceKind switch
 1691537                    {
 606538                        0 or 3 => map.Cells.Count,
 542539                        1 or 4 => map.Connections.Count,
 543540                        _ => map.Transitions.Count
 1691541                    };
 52451542                    while (_supersedenceItemIndex < count)
 543                    {
 50831544                        if (!meter.TryConsumeOverlaySlots(1))
 71545                            return false;
 50760546                        int index = _supersedenceItemIndex++;
 50760547                        if (_supersedenceKind < 3)
 548                        {
 25380549                            bool covered = _supersedenceKind switch
 25380550                            {
 17128551                                0 => _coveredCells.Contains(
 17128552                                    new NavigationCellAddress(map.MapId, map.Cells[index].Index)),
 4139553                                1 => _coveredConnections.Contains(
 4139554                                    new OverlayIdKey(map.MapId, map.Connections[index].Id)),
 4113555                                _ => _coveredTransitions.Contains(
 4113556                                    new OverlayIdKey(map.MapId, map.Transitions[index].Id))
 25380557                            };
 25380558                            _supersedenceCovered &= covered;
 559                        }
 25380560                        else if (_supersedenceKind == 3)
 561                        {
 17128562                            _coveredCells.Add(
 17128563                                new NavigationCellAddress(map.MapId, map.Cells[index].Index));
 564                        }
 8252565                        else if (_supersedenceKind == 4)
 4139566                            _coveredConnections.Add(new OverlayIdKey(map.MapId, map.Connections[index].Id));
 567                        else
 4113568                            _coveredTransitions.Add(new OverlayIdKey(map.MapId, map.Transitions[index].Id));
 569                    }
 1620570                    _supersedenceKind++;
 1620571                    _supersedenceItemIndex = 0;
 572                }
 270573                _supersedenceMapIndex++;
 270574                _supersedenceKind = 0;
 575            }
 254576            _superseded[_supersedenceIndex] = _supersedenceCovered;
 254577            CompleteSupersedenceOperation();
 578        }
 3664579        _supersedenceActive = false;
 3664580        _supersedenceComplete = true;
 3664581        return true;
 582    }
 583
 584    private void CompleteSupersedenceOperation()
 585    {
 1575586        _supersedenceIndex--;
 1575587        _supersedenceMapIndex = 0;
 1575588        _supersedenceKind = 0;
 1575589        _supersedenceItemIndex = 0;
 1575590        _supersedenceCovered = true;
 1575591        _supersedenceComplete = false;
 1575592    }
 593
 594    private void ResetSupersedence()
 595    {
 3725596        _supersedenceActive = false;
 3725597        _supersedenceComplete = false;
 3725598        _supersedenceIndex = -1;
 3725599        _supersedenceMapIndex = 0;
 3725600        _supersedenceKind = 0;
 3725601        _supersedenceItemIndex = 0;
 3725602        _supersedenceCovered = true;
 3725603    }
 604
 605    private static bool WouldExceed(long current, long increment, long maximum) =>
 90262606        increment > maximum - current;
 607
 608    private static long GetFixedScratchBytes(int maxBatchItems) =>
 20103609        BaseCoalescingScratchBytes + ((long)maxBatchItems * FixedScratchBytesPerOperation);
 610
 611    private long GetActiveAdditionalRetainedBytes()
 612    {
 53815613        NavigationOperationCandidate published = _sourceCandidateForDeferred ?? _candidate;
 53815614        if (_mapFoldWork != null)
 4641615            return GetAdditionalRetainedBytes(_mapFoldWork, published);
 49174616        if (_overlayFoldWork != null)
 284617            return GetAdditionalRetainedBytes(_overlayFoldWork, published);
 48890618        return _deferredCandidate == null
 48890619            ? 0
 48890620            : GetPositiveRetainedDelta(_deferredCandidate, published);
 621    }
 622
 623    private int GetActiveAdditionalPersistentPages()
 624    {
 54157625        NavigationOperationCandidate published = _sourceCandidateForDeferred ?? _candidate;
 54157626        if (_mapFoldWork != null)
 4643627            return GetAdditionalPersistentPages(_mapFoldWork, published);
 49514628        if (_overlayFoldWork != null)
 284629            return GetAdditionalPersistentPages(_overlayFoldWork, published);
 49230630        return _deferredCandidate == null
 49230631            ? 0
 49230632            : GetPositivePersistentPageDelta(_deferredCandidate, published);
 633    }
 634
 635    private static long GetAdditionalRetainedBytes(
 636        NavigationMapFoldWork work,
 9257637        NavigationOperationCandidate published) => checked(
 9257638        work.RetainedBytes
 9257639        + GetPositiveNonPayloadRetainedDelta(work.Candidate, published)
 9257640        + GetAdditionalExplicitPayloadBytes(work.Candidate, published)
 9257641        + GetAdditionalMapStatePayloadBytes(work.Candidate, published)
 9257642        + work.DisplacedExplicitPayloadBytes
 9257643        + work.DisplacedMapStatePayloadBytes);
 644
 645    private static int GetAdditionalPersistentPages(
 646        NavigationMapFoldWork work,
 9259647        NavigationOperationCandidate published) => checked(
 9259648        work.PersistentPageCount
 9259649        + GetPositiveNonPayloadPageDelta(work.Candidate, published)
 9259650        + GetAdditionalExplicitPayloadPages(work.Candidate, published)
 9259651        + GetAdditionalMapStatePayloadPages(work.Candidate, published)
 9259652        + work.DisplacedExplicitPayloadPages
 9259653        + work.DisplacedMapStatePayloadPages);
 654
 655    private static long GetAdditionalRetainedBytes(
 656        NavigationOverlayFoldWork work,
 870657        NavigationOperationCandidate published) => checked(
 870658        work.RetainedBytes
 870659        + GetPositiveNonPayloadRetainedDelta(work.Candidate, published)
 870660        + GetAdditionalExplicitPayloadBytes(work.Candidate, published)
 870661        + GetAdditionalMapStatePayloadBytes(work.Candidate, published)
 870662        + work.DisplacedExplicitPayloadBytes
 870663        + work.DisplacedMapStatePayloadBytes);
 664
 665    private static int GetAdditionalPersistentPages(
 666        NavigationOverlayFoldWork work,
 870667        NavigationOperationCandidate published) => checked(
 870668        work.PersistentPageCount
 870669        + GetPositiveNonPayloadPageDelta(work.Candidate, published)
 870670        + GetAdditionalExplicitPayloadPages(work.Candidate, published)
 870671        + GetAdditionalMapStatePayloadPages(work.Candidate, published)
 870672        + work.DisplacedExplicitPayloadPages
 870673        + work.DisplacedMapStatePayloadPages);
 674
 675    private static long GetAdditionalExplicitPayloadBytes(
 676        NavigationOperationCandidate candidate,
 62816677        NavigationOperationCandidate published) => Math.Max(
 62816678            0L,
 62816679            candidate.WorkOwnedExplicitPayloadBytes
 62816680            - published.WorkOwnedExplicitPayloadBytes);
 681
 682    private static int GetAdditionalExplicitPayloadPages(
 683        NavigationOperationCandidate candidate,
 63185684        NavigationOperationCandidate published) => Math.Max(
 63185685            0,
 63185686            candidate.WorkOwnedExplicitPayloadPages
 63185687            - published.WorkOwnedExplicitPayloadPages);
 688
 689    private static long GetAdditionalMapStatePayloadBytes(
 690        NavigationOperationCandidate candidate,
 62816691        NavigationOperationCandidate published) => Math.Max(
 62816692            0L,
 62816693            candidate.WorkOwnedMapStatePayloadBytes
 62816694            - published.WorkOwnedMapStatePayloadBytes);
 695
 696    private static int GetAdditionalMapStatePayloadPages(
 697        NavigationOperationCandidate candidate,
 63185698        NavigationOperationCandidate published) => Math.Max(
 63185699            0,
 63185700            candidate.WorkOwnedMapStatePayloadPages
 63185701            - published.WorkOwnedMapStatePayloadPages);
 702
 703    private static long GetPositiveNonPayloadRetainedDelta(
 704        NavigationOperationCandidate candidate,
 62816705        NavigationOperationCandidate source) => Math.Max(
 62816706            0L,
 62816707            candidate.NonPayloadRetainedBytes - source.NonPayloadRetainedBytes);
 708
 709    private static int GetPositiveNonPayloadPageDelta(
 710        NavigationOperationCandidate candidate,
 63185711        NavigationOperationCandidate source) => Math.Max(
 63185712            0,
 63185713            candidate.NonPayloadPersistentPageCount - source.NonPayloadPersistentPageCount);
 714
 715    private static long GetPositiveRetainedDelta(
 716        NavigationOperationCandidate candidate,
 717        NavigationOperationCandidate source) =>
 52689718        checked(
 52689719            GetPositiveNonPayloadRetainedDelta(candidate, source)
 52689720            + GetAdditionalExplicitPayloadBytes(candidate, source)
 52689721            + GetAdditionalMapStatePayloadBytes(candidate, source)
 52689722            + candidate.WorkCopiedPersistentBytes);
 723
 724    private static int GetPositivePersistentPageDelta(
 725        NavigationOperationCandidate candidate,
 726        NavigationOperationCandidate source) =>
 53056727        checked(
 53056728            GetPositiveNonPayloadPageDelta(candidate, source)
 53056729            + GetAdditionalExplicitPayloadPages(candidate, source)
 53056730            + GetAdditionalMapStatePayloadPages(candidate, source)
 53056731            + candidate.WorkCopiedPersistentPages);
 732
 3681733    private void RemovePrefix(int count) => RemoveRange(0, count);
 734
 735    private void RemoveRange(int index, int count)
 736    {
 3681737        if (count == 0)
 2337738            return;
 739
 5874740        for (int i = 0; i < count; i++)
 741        {
 1593742            PendingOperation operation = _pending[index + i];
 1593743            _pendingDescriptorBytes -= operation.DescriptorBytes;
 1593744            _pendingPreparedMapBytes -= operation.PreparedMapBytes;
 745        }
 746
 5874747        for (int i = 0; i < count; i++)
 1593748            _pending.RemoveAt(index);
 1344749    }
 750
 751    private enum PendingOperationKind
 752    {
 753        MapCommit,
 754        MapRemove,
 755        Overlay
 756    }
 757
 758    private readonly struct OverlayIdKey : IEquatable<OverlayIdKey>
 759    {
 760        internal OverlayIdKey(string mapId, string id)
 761        {
 16504762            MapId = mapId;
 16504763            Id = id;
 16504764        }
 765
 766        private string MapId { get; }
 767        private string Id { get; }
 768
 769        public bool Equals(OverlayIdKey other) =>
 8770            string.Equals(MapId, other.MapId, StringComparison.Ordinal)
 8771            & string.Equals(Id, other.Id, StringComparison.Ordinal);
 772
 773        public override int GetHashCode()
 774        {
 16504775            var comparer = SwiftHashTools.GetDeterministicStringEqualityComparer();
 16504776            return SwiftHashTools.CombineHashCodes(
 16504777                comparer.GetHashCode(MapId),
 16504778                comparer.GetHashCode(Id));
 779        }
 780    }
 781
 782    private readonly struct PendingOperation
 783    {
 784        private PendingOperation(
 785            PendingOperationKind kind,
 786            string? mapId,
 787            PreparedNavigationMap? preparedMap,
 788            PreparedNavigationOverlay? preparedOverlay,
 789            OverlayReplacementPolicy replacementPolicy,
 790            long operationSequence,
 791            int effectiveFrame,
 792            NavigationOperationReceipt receipt,
 793            long descriptorBytes,
 794            long preparedMapBytes,
 795            long coalescingScratchBytes)
 796        {
 1619797            Kind = kind;
 1619798            MapId = mapId;
 1619799            PreparedMap = preparedMap;
 1619800            PreparedOverlay = preparedOverlay;
 1619801            ReplacementPolicy = replacementPolicy;
 1619802            OperationSequence = operationSequence;
 1619803            EffectiveFrame = effectiveFrame;
 1619804            Receipt = receipt;
 1619805            DescriptorBytes = descriptorBytes;
 1619806            PreparedMapBytes = preparedMapBytes;
 1619807            CoalescingScratchBytes = coalescingScratchBytes;
 1619808        }
 809
 810        internal PendingOperationKind Kind { get; }
 811        internal string? MapId { get; }
 812        internal PreparedNavigationMap? PreparedMap { get; }
 813        internal PreparedNavigationOverlay? PreparedOverlay { get; }
 814        internal OverlayReplacementPolicy ReplacementPolicy { get; }
 815        internal long OperationSequence { get; }
 816        internal int EffectiveFrame { get; }
 817        internal NavigationOperationReceipt Receipt { get; }
 818        internal long DescriptorBytes { get; }
 819        internal long PreparedMapBytes { get; }
 820        internal long CoalescingScratchBytes { get; }
 1642821        internal bool IsMapOperation => Kind is PendingOperationKind.MapCommit or PendingOperationKind.MapRemove;
 822
 38369823        internal NavigationOperationFrameChange ToFrameChange() => Kind switch
 38369824        {
 37408825            PendingOperationKind.MapCommit => NavigationOperationFrameChange.MapCommit(
 37408826                PreparedMap!,
 37408827                ReplacementPolicy,
 37408828                OperationSequence),
 15829            PendingOperationKind.MapRemove => NavigationOperationFrameChange.MapRemove(
 15830                MapId!,
 15831                OperationSequence),
 946832            _ => NavigationOperationFrameChange.Overlay(
 946833                PreparedOverlay!,
 946834                OperationSequence)
 38369835        };
 836
 837        internal static PendingOperation ForMapCommit(NavigationMapCommitOperation operation) =>
 1311838            new(
 1311839                PendingOperationKind.MapCommit,
 1311840                operation.PreparedMap.Map.MapId,
 1311841                operation.PreparedMap,
 1311842                preparedOverlay: null,
 1311843                operation.OverlayReplacementPolicy,
 1311844                operation.OperationSequence,
 1311845                operation.EffectiveFrame,
 1311846                operation.Receipt,
 1311847                descriptorBytes: 64L + (operation.PreparedMap.Map.MapId.Length * sizeof(char)),
 1311848                preparedMapBytes: operation.PreparedMap.RetainedBytes,
 1311849                coalescingScratchBytes: MapCoverageScratchBytes);
 850
 851        internal static PendingOperation ForMapRemove(NavigationMapRemoveOperation operation) =>
 22852            new(
 22853                PendingOperationKind.MapRemove,
 22854                operation.MapId,
 22855                preparedMap: null,
 22856                preparedOverlay: null,
 22857                OverlayReplacementPolicy.PreserveAndRevalidate,
 22858                operation.OperationSequence,
 22859                operation.EffectiveFrame,
 22860                operation.Receipt,
 22861                descriptorBytes: 48L + (operation.MapId.Length * sizeof(char)),
 22862                preparedMapBytes: 0,
 22863                coalescingScratchBytes: MapCoverageScratchBytes);
 864
 865        internal static PendingOperation ForOverlay(NavigationOverlayCommitOperation operation) =>
 286866            new(
 286867                PendingOperationKind.Overlay,
 286868                mapId: null,
 286869                preparedMap: null,
 286870                operation.PreparedOverlay,
 286871                OverlayReplacementPolicy.PreserveAndRevalidate,
 286872                operation.OperationSequence,
 286873                operation.EffectiveFrame,
 286874                operation.Receipt,
 286875                operation.PreparedOverlay.DescriptorBytes,
 286876                preparedMapBytes: 0,
 286877                coalescingScratchBytes: GetOverlayCoverageScratchBytes(operation.PreparedOverlay));
 878
 879        private static long GetOverlayCoverageScratchBytes(PreparedNavigationOverlay overlay) =>
 286880            NavigationByteCount.SaturatingAdd(overlay.DescriptorBytes, overlay.DescriptorBytes);
 881
 882    }
 883}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(Trailblazer.Pathing.NavigationOperationLimits,System.Int32,System.Int32)
get_Candidate()
get_CoverageScratchBytes()
get_RetainedOperationWorkBytes()
get_RetainedOperationWorkPageCount()
get_RetainedOperationWorkCount()
RejectDeferredCapacity()
Reset()
Admit(Trailblazer.Pathing.NavigationMapCommitOperation)
Admit(Trailblazer.Pathing.NavigationMapRemoveOperation)
Admit(Trailblazer.Pathing.NavigationOverlayCommitOperation)
ProcessFrame(System.Int32)
ProcessFrame(System.Int32,Trailblazer.Pathing.NavigationCandidatePublisher,Trailblazer.Pathing.MaintenanceWorkMeter,Trailblazer.Pathing.NavigationRetainedWorkGuard)
Admit(Trailblazer.Pathing.NavigationOperationProcessor/PendingOperation)
GetAdmissionRejection(Trailblazer.Pathing.NavigationOperationProcessor/PendingOperation)
AdvanceSupersedence(System.Int32,Trailblazer.Pathing.MaintenanceWorkMeter)
CompleteSupersedenceOperation()
ResetSupersedence()
WouldExceed(System.Int64,System.Int64,System.Int64)
GetFixedScratchBytes(System.Int32)
GetActiveAdditionalRetainedBytes()
GetActiveAdditionalPersistentPages()
GetAdditionalRetainedBytes(Trailblazer.Pathing.NavigationMapFoldWork,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalPersistentPages(Trailblazer.Pathing.NavigationMapFoldWork,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalRetainedBytes(Trailblazer.Pathing.NavigationOverlayFoldWork,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalPersistentPages(Trailblazer.Pathing.NavigationOverlayFoldWork,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalExplicitPayloadBytes(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalExplicitPayloadPages(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalMapStatePayloadBytes(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetAdditionalMapStatePayloadPages(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetPositiveNonPayloadRetainedDelta(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetPositiveNonPayloadPageDelta(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetPositiveRetainedDelta(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
GetPositivePersistentPageDelta(Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.NavigationOperationCandidate)
RemovePrefix(System.Int32)
RemoveRange(System.Int32,System.Int32)
.ctor(System.String,System.String)
Equals(Trailblazer.Pathing.NavigationOperationProcessor/OverlayIdKey)
GetHashCode()
.ctor(Trailblazer.Pathing.NavigationOperationProcessor/PendingOperationKind,System.String,Trailblazer.Pathing.PreparedNavigationMap,Trailblazer.Pathing.PreparedNavigationOverlay,Trailblazer.Pathing.OverlayReplacementPolicy,System.Int64,System.Int32,Trailblazer.Pathing.NavigationOperationReceipt,System.Int64,System.Int64,System.Int64)
get_IsMapOperation()
ToFrameChange()
ForMapCommit(Trailblazer.Pathing.NavigationMapCommitOperation)
ForMapRemove(Trailblazer.Pathing.NavigationMapRemoveOperation)
ForOverlay(Trailblazer.Pathing.NavigationOverlayCommitOperation)
GetOverlayCoverageScratchBytes(Trailblazer.Pathing.PreparedNavigationOverlay)