< Summary

Information
Class: Trailblazer.Pathing.NavigationTransitionRefreshWork
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationTransitionRefreshWork.cs
Line coverage
100%
Covered lines: 592
Uncovered lines: 0
Coverable lines: 592
Total lines: 1014
Line coverage: 100%
Branch coverage
100%
Covered branches: 295
Total branches: 295
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_Pages()100%11100%
get_Rules()100%11100%
get_RetainedBytes()100%22100%
get_PersistentPageCount()100%44100%
Advance(...)100%1010100%
CaptureAffectedSources(...)100%1212100%
RefreshDefinitions(...)100%1717100%
AdvancePriorPageDiscovery(...)100%1616100%
AdvanceNextPageCount(...)100%1414100%
AdvancePagePreparation(...)100%44100%
AdvanceNextPageFill(...)100%1414100%
AdvancePageSeal(...)100%88100%
TryAdvanceEffectiveDefinition(...)100%1010100%
TryGetRetainedPrior(...)100%44100%
GetOrAddPage(...)100%88100%
GetPage(...)100%11100%
TryGetCurrentPageState(...)100%44100%
AdvancePageCursor()100%11100%
ResetPageCursor()100%11100%
CompleteDefinitionPhase()100%11100%
ClearPendingDefinition()100%11100%
ClearPageBuildScratch()100%11100%
AddWorkingBuffers(...)100%11100%
ReleaseWorkingBuffers(...)100%11100%
OwnPublishedPageRoot(...)100%88100%
RefreshRules(...)100%2626100%
CreatePublished(...)100%44100%
GetArrayBytes(...)100%22100%
.ctor(...)100%11100%
AppendOutgoing(...)100%11100%
AppendIncoming(...)100%11100%
AdvancePreparation(...)100%5252100%
AdvanceSeal(...)100%2424100%
CreatePage(...)100%11100%
ReleaseFinalBuffers(...)100%11100%
get_WorkingBufferBytes()100%11100%
get_WorkingBufferPages()100%11100%
get_FinalArrayBytes()100%11100%
get_FinalArrayPages()100%11100%
get_SortScratchBytes()100%44100%
get_SortScratchPages()100%11100%
Compare(...)100%11100%
Compare(...)100%11100%
Initialize(...)100%11100%
Advance(...)100%2424100%
Release()100%11100%
.ctor(...)100%44100%
AdvanceOne(...)100%2020100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationTransitionRefreshWork.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationTransitionRefreshWork.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;
 9
 10namespace Trailblazer.Pathing;
 11
 12/// <summary>Refreshes affected explicit-transition pages and the bounded rule table.</summary>
 13internal sealed class NavigationTransitionRefreshWork
 14{
 15    private const long FixedRetainedBytes = 536L;
 16    private readonly NavigationWorldGraph _source;
 17    private readonly NavigationWorldGraph _candidate;
 18    private readonly NavigationOperationCandidate? _operationCandidate;
 19    private readonly PersistentStringMap<bool> _changedMaps;
 20    private readonly bool _rebuildRules;
 21    private readonly long _version;
 299822    private PersistentStringMap<bool> _affectedSources = PersistentStringMap<bool>.Empty;
 299823    private PersistentStringMap<PersistentIntMap<PageBuildState>> _pageBuilds =
 299824        PersistentStringMap<PersistentIntMap<PageBuildState>>.Empty;
 25    private long _pageBuildInnerBytes;
 26    private int _pageBuildInnerPages;
 27    private int _pageBuildStateCount;
 28    private NavigationTransitionPageRoot _pages;
 29    private NavigationTransitionRuleTable _rules;
 30    private int _changedMapOrdinal;
 299831    private int _incomingOrdinal = -1;
 32    private int _definitionPhase;
 33    private int _definitionSourceOrdinal;
 34    private EffectiveTransitionCursor _definitionCursor;
 35    private bool _definitionCursorActive;
 36    private string? _pendingOwnerMapId;
 37    private TraversalTransitionDefinition _pendingDefinition;
 38    private NavigationPublishedTransition _pendingTransition;
 299839    private int _pendingPlacementStage = -1;
 40    private int _pageMapOrdinal;
 41    private int _pageOrdinal;
 42    private long _workingBufferBytes;
 43    private int _workingBufferPages;
 44    private long _publicationOwnedBytes;
 45    private int _publicationOwnedPages;
 46    private bool _publicationRootOwned;
 47    private string? _publicationRootMapId;
 48    private int _ruleCountMapOrdinal;
 49    private int _ruleCount;
 50    private TraversalTransitionRule[]? _ruleBuffer;
 51    private int[]? _ruleOrdinals;
 52    private int _ruleOutputOrdinal;
 53    private int _ruleScanMapOrdinal;
 299854    private int _ruleBestMapOrdinal = -1;
 55    private bool _ruleScanActive;
 56    private bool _ruleContentEqual;
 57
 299858    internal NavigationTransitionRefreshWork(
 299859        NavigationWorldGraph source,
 299860        NavigationWorldGraph candidate,
 299861        NavigationOperationCandidate? operationCandidate,
 299862        PersistentStringMap<bool> changedMaps,
 299863        bool rebuildRules,
 299864        long version)
 65    {
 299866        _source = source;
 299867        _candidate = candidate;
 299868        _operationCandidate = operationCandidate;
 299869        _changedMaps = changedMaps;
 299870        _rebuildRules = rebuildRules;
 299871        _version = version;
 299872        _pages = source.TransitionPages;
 299873        _rules = source.TransitionRules;
 299874    }
 75
 76    internal bool IsComplete { get; private set; }
 77
 300378    internal NavigationTransitionPageRoot Pages => _pages;
 79
 299280    internal NavigationTransitionRuleTable Rules => _rules;
 81
 27205882    internal long RetainedBytes => checked(
 27205883        FixedRetainedBytes
 27205884        + _affectedSources.RetainedBytes
 27205885        + _pageBuilds.RetainedBytes
 27205886        + _pageBuildInnerBytes
 27205887        + ((long)_pageBuildStateCount * PageBuildState.BaseRetainedBytes)
 27205888        + _workingBufferBytes
 27205889        + (_ruleOrdinals == null ? 0L : GetArrayBytes(_ruleOrdinals.Length, sizeof(int)))
 27205890        + _publicationOwnedBytes);
 91
 27240792    internal int PersistentPageCount => checked(
 27240793        1
 27240794        + _affectedSources.PersistentNodeCount
 27240795        + _pageBuilds.PersistentNodeCount
 27240796        + _pageBuildInnerPages
 27240797        + _pageBuildStateCount
 27240798        + _workingBufferPages
 27240799        + (_ruleOrdinals == null || _ruleOrdinals.Length == 0 ? 0 : 1)
 272407100        + _publicationOwnedPages);
 101
 102    internal bool Advance(MaintenanceWorkMeter meter)
 103    {
 8225104        if (IsComplete)
 2738105            return true;
 5487106        if (!CaptureAffectedSources(meter))
 509107            return false;
 4978108        if (!RefreshDefinitions(meter))
 1504109            return false;
 3474110        if (_rebuildRules && !RefreshRules(meter))
 480111            return false;
 2994112        IsComplete = true;
 2994113        return true;
 114    }
 115
 116    private bool CaptureAffectedSources(MaintenanceWorkMeter meter)
 117    {
 8274118        while (_changedMapOrdinal < _changedMaps.Count)
 119        {
 3296120            string mapId = _changedMaps.GetKeyAt(_changedMapOrdinal);
 3296121            if (_incomingOrdinal < 0)
 122            {
 3295123                if (!meter.TryConsumeComponentNodes(1))
 508124                    return false;
 2787125                _affectedSources = _affectedSources.Set(mapId, true);
 2787126                _incomingOrdinal = 0;
 127            }
 2788128            int incomingCount = _operationCandidate?.GetIncomingSourceCount(mapId) ?? 0;
 2928129            while (_incomingOrdinal < incomingCount)
 130            {
 141131                if (!meter.TryConsumeDependencyEntries(1))
 1132                    return false;
 140133                _affectedSources = _affectedSources.Set(
 140134                    _operationCandidate!.GetIncomingSource(mapId, _incomingOrdinal++),
 140135                    true);
 136            }
 2787137            _changedMapOrdinal++;
 2787138            _incomingOrdinal = -1;
 139        }
 4978140        return true;
 141    }
 142
 143    private bool RefreshDefinitions(MaintenanceWorkMeter meter)
 144    {
 19954145        while (_definitionPhase < 5)
 146        {
 16480147            switch (_definitionPhase)
 148            {
 149                case 0:
 3137150                    if (!AdvancePriorPageDiscovery(meter))
 141151                        return false;
 2996152                    CompleteDefinitionPhase();
 2996153                    break;
 154                case 1:
 3422155                    if (!AdvanceNextPageCount(meter))
 426156                        return false;
 2996157                    CompleteDefinitionPhase();
 2996158                    break;
 159                case 2:
 3037160                    if (!AdvancePagePreparation(meter))
 42161                        return false;
 2995162                    ResetPageCursor();
 2995163                    _definitionPhase++;
 2995164                    break;
 165                case 3:
 3475166                    if (!AdvanceNextPageFill(meter))
 480167                        return false;
 2995168                    CompleteDefinitionPhase();
 2995169                    break;
 170                default:
 3409171                    if (!AdvancePageSeal(meter))
 415172                        return false;
 2994173                    ClearPageBuildScratch();
 2994174                    _definitionPhase++;
 175                    break;
 176            }
 177        }
 3474178        return true;
 179    }
 180
 181    private bool AdvancePriorPageDiscovery(MaintenanceWorkMeter meter)
 182    {
 4203183        while (true)
 184        {
 7342185            if (_pendingPlacementStage < 0)
 186            {
 7340187                if (!TryAdvanceEffectiveDefinition(_source, meter))
 188                {
 3135189                    return !_definitionCursorActive
 3135190                        && _definitionSourceOrdinal >= _affectedSources.Count;
 191                }
 4205192                if (!TryGetRetainedPrior(
 4205193                        _pendingOwnerMapId!,
 4205194                        _pendingDefinition,
 4205195                        out _pendingTransition))
 196                {
 2197                    ClearPendingDefinition();
 2198                    continue;
 199                }
 4203200                _pendingPlacementStage = 0;
 201            }
 4205202            if (_pendingPlacementStage == 0)
 203            {
 4204204                if (!meter.TryConsumeDependencyEntries(1))
 1205                    return false;
 4203206                GetOrAddPage(_pendingTransition.SourcePage);
 4203207                _pendingPlacementStage = 1;
 208            }
 4204209            if (_pendingTransition.DestinationPage.HasValue)
 210            {
 4199211                if (!meter.TryConsumeDependencyEntries(1))
 1212                    return false;
 4198213                GetOrAddPage(_pendingTransition.DestinationPage.Value);
 214            }
 4203215            ClearPendingDefinition();
 216        }
 217    }
 218
 219    private bool AdvanceNextPageCount(MaintenanceWorkMeter meter)
 220    {
 8414221        while (true)
 222        {
 11836223            if (_pendingPlacementStage < 0)
 224            {
 11773225                if (!TryAdvanceEffectiveDefinition(_candidate, meter))
 226                {
 3359227                    return !_definitionCursorActive
 3359228                        && _definitionSourceOrdinal >= _affectedSources.Count;
 229                }
 8414230                _pendingTransition = CreatePublished(
 8414231                    _candidate,
 8414232                    _pendingOwnerMapId!,
 8414233                    _pendingDefinition);
 8414234                _pendingPlacementStage = 0;
 235            }
 8477236            if (_pendingPlacementStage == 0)
 237            {
 8445238                if (!meter.TryConsumeDependencyEntries(1))
 31239                    return false;
 8414240                GetOrAddPage(_pendingTransition.SourcePage).NewOutgoingCount++;
 8414241                _pendingPlacementStage = 1;
 242            }
 8446243            if (_pendingTransition.DestinationPage.HasValue)
 244            {
 8440245                if (!meter.TryConsumeDependencyEntries(1))
 32246                    return false;
 8408247                GetOrAddPage(_pendingTransition.DestinationPage.Value).NewIncomingCount++;
 248            }
 8414249            ClearPendingDefinition();
 250        }
 251    }
 252
 253    private bool AdvancePagePreparation(MaintenanceWorkMeter meter)
 254    {
 3347255        while (TryGetCurrentPageState(out PageBuildState state))
 256        {
 352257            bool complete = state.AdvancePreparation(
 352258                _affectedSources,
 352259                meter,
 352260                out long addedBytes,
 352261                out int addedPages);
 352262            AddWorkingBuffers(addedBytes, addedPages);
 352263            if (!complete)
 42264                return false;
 310265            AdvancePageCursor();
 310266        }
 2995267        return true;
 268    }
 269
 270    private bool AdvanceNextPageFill(MaintenanceWorkMeter meter)
 271    {
 8413272        while (true)
 273        {
 11888274            if (_pendingPlacementStage < 0)
 275            {
 11810276                if (!TryAdvanceEffectiveDefinition(_candidate, meter))
 277                {
 3397278                    return !_definitionCursorActive
 3397279                        && _definitionSourceOrdinal >= _affectedSources.Count;
 280                }
 8413281                _pendingTransition = CreatePublished(
 8413282                    _candidate,
 8413283                    _pendingOwnerMapId!,
 8413284                    _pendingDefinition);
 8413285                _pendingPlacementStage = 0;
 286            }
 8491287            if (_pendingPlacementStage == 0)
 288            {
 8452289                if (!meter.TryConsumeExplicitEdges(1))
 39290                    return false;
 8413291                GetPage(_pendingTransition.SourcePage).AppendOutgoing(_pendingTransition);
 8413292                _pendingPlacementStage = 1;
 293            }
 8452294            if (_pendingTransition.DestinationPage.HasValue)
 295            {
 8446296                if (!meter.TryConsumeExplicitEdges(1))
 39297                    return false;
 8407298                GetPage(_pendingTransition.DestinationPage.Value).AppendIncoming(
 8407299                    new NavigationIncomingTransitionRef(_pendingTransition));
 300            }
 8413301            ClearPendingDefinition();
 302        }
 303    }
 304
 305    private bool AdvancePageSeal(MaintenanceWorkMeter meter)
 306    {
 3718307        while (TryGetCurrentPageState(out PageBuildState state))
 308        {
 724309            bool complete = state.AdvanceSeal(
 724310                meter,
 724311                out bool changed,
 724312                out long releasedWorkingBytes,
 724313                out int releasedWorkingPages);
 724314            ReleaseWorkingBuffers(releasedWorkingBytes, releasedWorkingPages);
 724315            if (!complete)
 412316                return false;
 312317            if (changed)
 318            {
 169319                if (!meter.TryConsumeComponentNodes(1))
 3320                    return false;
 166321                NavigationTransitionPage page = state.CreatePage(_version);
 166322                _pages = _pages.Set(page, out int copiedNodes, out long copiedBytes);
 166323                OwnPublishedPageRoot(state.Address.MapId, page, copiedNodes, copiedBytes);
 324            }
 309325            state.ReleaseFinalBuffers(
 309326                out releasedWorkingBytes,
 309327                out releasedWorkingPages);
 309328            ReleaseWorkingBuffers(releasedWorkingBytes, releasedWorkingPages);
 309329            AdvancePageCursor();
 309330        }
 2994331        return true;
 332    }
 333
 334    private bool TryAdvanceEffectiveDefinition(
 335        NavigationWorldGraph graph,
 336        MaintenanceWorkMeter meter)
 337    {
 39406338        while (_definitionSourceOrdinal < _affectedSources.Count)
 339        {
 30419340            string ownerMapId = _affectedSources.GetKeyAt(_definitionSourceOrdinal);
 30419341            if (!_definitionCursorActive)
 342            {
 8374343                graph.TryGetMap(ownerMapId, out NavigationMapInstance? instance);
 8374344                _definitionCursor = new EffectiveTransitionCursor(instance);
 8374345                _definitionCursorActive = true;
 346            }
 30419347            if (!meter.TryConsumeExplicitEdges(1))
 904348                return false;
 29515349            bool hasValue = _definitionCursor.AdvanceOne(
 29515350                out TraversalTransitionDefinition definition,
 29515351                out bool complete);
 29515352            if (complete)
 353            {
 8374354                _definitionCursorActive = false;
 8374355                _definitionSourceOrdinal++;
 8374356                continue;
 357            }
 21141358            if (hasValue)
 359            {
 21032360                _pendingOwnerMapId = ownerMapId;
 21032361                _pendingDefinition = definition;
 21032362                return true;
 363            }
 364        }
 8987365        return false;
 366    }
 367
 368    private bool TryGetRetainedPrior(
 369        string ownerMapId,
 370        TraversalTransitionDefinition definition,
 371        out NavigationPublishedTransition transition)
 372    {
 4205373        NavigationPublishedTransition located = CreatePublished(
 4205374            _source,
 4205375            ownerMapId,
 4205376            definition);
 4205377        if (_pages.TryGet(located.SourcePage, out NavigationTransitionPage page)
 4205378            && page.TryGetOutgoing(located.Owner, out transition))
 379        {
 4203380            return true;
 381        }
 2382        transition = default;
 2383        return false;
 384    }
 385
 386    private PageBuildState GetOrAddPage(NavigationTransitionPageAddress address)
 387    {
 25223388        bool hadMap = _pageBuilds.TryGetValue(
 25223389            address.MapId,
 25223390            out PersistentIntMap<PageBuildState> map);
 25223391        map ??= PersistentIntMap<PageBuildState>.Empty;
 25223392        if (map.TryGetValue(address.PageIndex, out PageBuildState state))
 24911393            return state;
 312394        _pages.TryGet(address, out NavigationTransitionPage prior);
 312395        state = new PageBuildState(address, prior);
 312396        long priorInnerBytes = hadMap ? map.RetainedBytes : 0L;
 312397        int priorInnerPages = hadMap ? map.PersistentNodeCount : 0;
 312398        map = map.Set(address.PageIndex, state);
 312399        _pageBuilds = _pageBuilds.Set(address.MapId, map);
 312400        _pageBuildInnerBytes = checked(
 312401            _pageBuildInnerBytes - priorInnerBytes + map.RetainedBytes);
 312402        _pageBuildInnerPages = checked(
 312403            _pageBuildInnerPages - priorInnerPages + map.PersistentNodeCount);
 312404        _pageBuildStateCount++;
 312405        return state;
 406    }
 407
 408    private PageBuildState GetPage(NavigationTransitionPageAddress address)
 409    {
 16820410        _pageBuilds.TryGetValue(address.MapId, out PersistentIntMap<PageBuildState> map);
 16820411        map.TryGetValue(address.PageIndex, out PageBuildState state);
 16820412        return state;
 413    }
 414
 415    private bool TryGetCurrentPageState(out PageBuildState state)
 416    {
 7422417        while (_pageMapOrdinal < _pageBuilds.Count)
 418        {
 1433419            PersistentIntMap<PageBuildState> map = _pageBuilds.GetValueAt(_pageMapOrdinal);
 1433420            if (_pageOrdinal < map.Count)
 421            {
 1076422                state = map.GetValueAt(_pageOrdinal);
 1076423                return true;
 424            }
 357425            _pageMapOrdinal++;
 357426            _pageOrdinal = 0;
 427        }
 5989428        state = null!;
 5989429        return false;
 430    }
 431
 619432    private void AdvancePageCursor() => _pageOrdinal++;
 433
 434    private void ResetPageCursor()
 435    {
 5989436        _pageMapOrdinal = 0;
 5989437        _pageOrdinal = 0;
 5989438    }
 439
 440    private void CompleteDefinitionPhase()
 441    {
 8987442        _definitionPhase++;
 8987443        _definitionSourceOrdinal = 0;
 8987444        _definitionCursorActive = false;
 8987445        ClearPendingDefinition();
 8987446    }
 447
 448    private void ClearPendingDefinition()
 449    {
 30019450        _pendingOwnerMapId = null;
 30019451        _pendingDefinition = default;
 30019452        _pendingTransition = default;
 30019453        _pendingPlacementStage = -1;
 30019454    }
 455
 456    private void ClearPageBuildScratch()
 457    {
 2994458        _pageBuilds = PersistentStringMap<PersistentIntMap<PageBuildState>>.Empty;
 2994459        _pageBuildInnerBytes = 0;
 2994460        _pageBuildInnerPages = 0;
 2994461        _pageBuildStateCount = 0;
 2994462        ResetPageCursor();
 2994463    }
 464
 465    private void AddWorkingBuffers(long bytes, int pages)
 466    {
 1301467        _workingBufferBytes = checked(_workingBufferBytes + bytes);
 1301468        _workingBufferPages = checked(_workingBufferPages + pages);
 1301469    }
 470
 471    private void ReleaseWorkingBuffers(long bytes, int pages)
 472    {
 1982473        _workingBufferBytes = checked(_workingBufferBytes - bytes);
 1982474        _workingBufferPages = checked(_workingBufferPages - pages);
 1982475    }
 476
 477    private void OwnPublishedPageRoot(
 478        string mapId,
 479        NavigationTransitionPage page,
 480        int copiedNodes,
 481        long copiedBytes)
 482    {
 166483        if (!_publicationRootOwned)
 484        {
 91485            _publicationRootOwned = true;
 91486            _publicationOwnedBytes = checked(_publicationOwnedBytes + 88L);
 91487            _publicationOwnedPages++;
 488        }
 166489        if (!string.Equals(_publicationRootMapId, mapId, StringComparison.Ordinal))
 490        {
 101491            _publicationRootMapId = mapId;
 101492            _publicationOwnedBytes = checked(_publicationOwnedBytes + 32L);
 493        }
 166494        _publicationOwnedBytes = checked(
 166495            _publicationOwnedBytes
 166496            + copiedBytes
 166497            + (page.IsEmpty ? 0L : page.RetainedBytes));
 166498        _publicationOwnedPages = checked(
 166499            _publicationOwnedPages
 166500            + copiedNodes
 166501            + (page.IsEmpty ? 0 : page.PersistentPageCount));
 166502    }
 503
 504    private bool RefreshRules(MaintenanceWorkMeter meter)
 505    {
 11243506        while (_ruleCountMapOrdinal < _candidate.MapCount)
 507        {
 10286508            if (!meter.TryConsumeComponentNodes(1))
 472509                return false;
 9814510            _ruleCount = checked(
 9814511                _ruleCount
 9814512                + _candidate.GetInstance(_ruleCountMapOrdinal++).Map.TransitionRuleSpan.Length);
 513        }
 957514        if (_ruleBuffer == null)
 515        {
 949516            _ruleBuffer = new TraversalTransitionRule[_ruleCount];
 949517            _ruleOrdinals = new int[_candidate.MapCount];
 949518            _ruleContentEqual = _rules.Count == _ruleCount;
 949519            AddWorkingBuffers(
 949520                GetArrayBytes(_ruleBuffer.Length, NavigationTransitionRuleTable.RecordRetainedBytes),
 949521                _ruleBuffer.Length == 0 ? 0 : 1);
 522        }
 1012523        while (_ruleOutputOrdinal < _ruleBuffer.Length)
 524        {
 63525            if (!_ruleScanActive)
 526            {
 55527                _ruleScanMapOrdinal = 0;
 55528                _ruleBestMapOrdinal = -1;
 55529                _ruleScanActive = true;
 530            }
 138531            while (_ruleScanMapOrdinal < _candidate.MapCount)
 532            {
 83533                if (!meter.TryConsumeDependencyEntries(1))
 8534                    return false;
 75535                int mapOrdinal = _ruleScanMapOrdinal++;
 75536                ReadOnlySpan<TraversalTransitionRule> rules =
 75537                    _candidate.GetInstance(mapOrdinal).Map.TransitionRuleSpan;
 75538                if (_ruleOrdinals![mapOrdinal] >= rules.Length)
 539                    continue;
 61540                if (_ruleBestMapOrdinal < 0)
 541                {
 55542                    _ruleBestMapOrdinal = mapOrdinal;
 55543                    continue;
 544                }
 6545                TraversalTransitionRule candidate = rules[_ruleOrdinals[mapOrdinal]];
 6546                ReadOnlySpan<TraversalTransitionRule> bestRules =
 6547                    _candidate.GetInstance(_ruleBestMapOrdinal).Map.TransitionRuleSpan;
 6548                TraversalTransitionRule best = bestRules[_ruleOrdinals[_ruleBestMapOrdinal]];
 6549                int comparison = string.CompareOrdinal(candidate.Id, best.Id);
 550                System.Diagnostics.Debug.Assert(comparison != 0,
 551                    "Map folding rejects duplicate global transition-rule ownership.");
 6552                if (comparison < 0)
 4553                    _ruleBestMapOrdinal = mapOrdinal;
 554            }
 55555            TraversalTransitionRule rule = _candidate.GetInstance(_ruleBestMapOrdinal)
 55556                .Map.TransitionRuleSpan[_ruleOrdinals![_ruleBestMapOrdinal]++];
 55557            _ruleBuffer[_ruleOutputOrdinal] = rule;
 55558            if (_ruleContentEqual && !_rules[_ruleOutputOrdinal].Equals(rule))
 3559                _ruleContentEqual = false;
 55560            _ruleOutputOrdinal++;
 55561            _ruleScanActive = false;
 562        }
 949563        long bufferBytes = GetArrayBytes(
 949564            _ruleBuffer.Length,
 949565            NavigationTransitionRuleTable.RecordRetainedBytes);
 949566        int bufferPages = _ruleBuffer.Length == 0 ? 0 : 1;
 949567        ReleaseWorkingBuffers(bufferBytes, bufferPages);
 949568        if (_ruleContentEqual)
 905569            _ruleBuffer = null;
 570        else
 571        {
 44572            _rules = new NavigationTransitionRuleTable(_ruleBuffer, _version);
 44573            _publicationOwnedBytes = checked(
 44574                _publicationOwnedBytes
 44575                + NavigationTransitionRuleTable.BaseRetainedBytes
 44576                + bufferBytes);
 44577            _publicationOwnedPages = checked(
 44578                _publicationOwnedPages + _rules.PersistentPageCount);
 579        }
 949580        _ruleOrdinals = null;
 949581        return true;
 582    }
 583
 584    private static NavigationPublishedTransition CreatePublished(
 585        NavigationWorldGraph graph,
 586        string ownerMapId,
 587        TraversalTransitionDefinition definition)
 588    {
 21032589        bool foundOwner = graph.TryGetMap(ownerMapId, out NavigationMapInstance source);
 590        System.Diagnostics.Debug.Assert(foundOwner,
 591            "Effective transition cursors enumerate definitions from an owned map.");
 21032592        bool foundSource = source.TryGetSlot(definition.SourceIndex, out int sourceSlot);
 593        System.Diagnostics.Debug.Assert(foundSource,
 594            "Published transition definitions retain their validated local source cell.");
 21032595        var sourcePage = new NavigationTransitionPageAddress(
 21032596            ownerMapId,
 21032597            sourceSlot / NavigationSemanticPage.SlotCount);
 21032598        NavigationTransitionPageAddress? destinationPage = null;
 21032599        if (graph.TryGetMap(definition.Destination.MapId, out NavigationMapInstance destination)
 21032600            && destination.TryGetSlot(definition.Destination.Index, out int destinationSlot))
 601        {
 21016602            destinationPage = new NavigationTransitionPageAddress(
 21016603                definition.Destination.MapId,
 21016604                destinationSlot / NavigationSemanticPage.SlotCount);
 605        }
 21032606        return new NavigationPublishedTransition(
 21032607            ownerMapId,
 21032608            definition,
 21032609            sourcePage,
 21032610            destinationPage);
 611    }
 612
 1906613    private static long GetArrayBytes(int count, long elementBytes) => count == 0
 1906614        ? 0L
 1906615        : checked(24L + ((long)count * elementBytes));
 616
 617    private sealed class PageBuildState
 618    {
 619        internal const long BaseRetainedBytes = 240L;
 620        private readonly NavigationTransitionPage? _prior;
 312621        private NavigationPublishedTransition[] _outgoing =
 312622            Array.Empty<NavigationPublishedTransition>();
 312623        private NavigationIncomingTransitionRef[] _incoming =
 312624            Array.Empty<NavigationIncomingTransitionRef>();
 625        private NavigationPublishedTransition[]? _outgoingScratch;
 626        private NavigationIncomingTransitionRef[]? _incomingScratch;
 627        private MergeSortWork<NavigationPublishedTransition, OutgoingComparer> _outgoingSort;
 628        private MergeSortWork<NavigationIncomingTransitionRef, IncomingComparer> _incomingSort;
 629        private int _prepareStage;
 630        private int _prepareOrdinal;
 631        private int _retainedOutgoingCount;
 632        private int _retainedIncomingCount;
 633        private int _outgoingFill;
 634        private int _incomingFill;
 635        private int _sealStage;
 636        private int _compareOrdinal;
 637        private bool _sameContent;
 638
 312639        internal PageBuildState(
 312640            NavigationTransitionPageAddress address,
 312641            NavigationTransitionPage? prior)
 642        {
 312643            Address = address;
 312644            _prior = prior;
 312645        }
 646
 647        internal NavigationTransitionPageAddress Address { get; }
 648
 649        internal int NewOutgoingCount { get; set; }
 650
 651        internal int NewIncomingCount { get; set; }
 652
 653        internal void AppendOutgoing(NavigationPublishedTransition transition) =>
 8413654            _outgoing[_outgoingFill++] = transition;
 655
 656        internal void AppendIncoming(NavigationIncomingTransitionRef incoming) =>
 8407657            _incoming[_incomingFill++] = incoming;
 658
 659        internal bool AdvancePreparation(
 660            PersistentStringMap<bool> affectedSources,
 661            MaintenanceWorkMeter meter,
 662            out long addedBytes,
 663            out int addedPages)
 664        {
 352665            addedBytes = 0;
 352666            addedPages = 0;
 1904667            while (_prepareStage < 5)
 668            {
 1594669                if (_prepareStage == 0)
 670                {
 320671                    int count = _prior?.OutgoingCount ?? 0;
 4524672                    while (_prepareOrdinal < count)
 673                    {
 4213674                        if (!meter.TryConsumeExplicitEdges(1))
 9675                            return false;
 4204676                        if (!affectedSources.ContainsKey(
 4204677                                _prior!.GetOutgoingAt(_prepareOrdinal++).Owner.MapId))
 678                        {
 1679                            _retainedOutgoingCount++;
 680                        }
 681                    }
 311682                    _prepareStage++;
 311683                    _prepareOrdinal = 0;
 684                }
 1274685                else if (_prepareStage == 1)
 686                {
 321687                    int count = _prior?.IncomingCount ?? 0;
 4521688                    while (_prepareOrdinal < count)
 689                    {
 4210690                        if (!meter.TryConsumeExplicitEdges(1))
 10691                            return false;
 4200692                        if (!affectedSources.ContainsKey(
 4200693                                _prior!.GetIncomingAt(_prepareOrdinal++).Owner.MapId))
 694                        {
 2695                            _retainedIncomingCount++;
 696                        }
 697                    }
 311698                    _prepareStage++;
 311699                    _prepareOrdinal = 0;
 700                }
 953701                else if (_prepareStage == 2)
 702                {
 314703                    if (!meter.TryConsumeComponentNodes(1))
 4704                        return false;
 310705                    int outgoingLength = checked(_retainedOutgoingCount + NewOutgoingCount);
 310706                    int incomingLength = checked(_retainedIncomingCount + NewIncomingCount);
 310707                    _outgoing = outgoingLength == 0
 310708                        ? Array.Empty<NavigationPublishedTransition>()
 310709                        : new NavigationPublishedTransition[outgoingLength];
 310710                    _incoming = incomingLength == 0
 310711                        ? Array.Empty<NavigationIncomingTransitionRef>()
 310712                        : new NavigationIncomingTransitionRef[incomingLength];
 310713                    _outgoingScratch = outgoingLength > 1
 310714                        ? new NavigationPublishedTransition[outgoingLength]
 310715                        : null;
 310716                    _incomingScratch = incomingLength > 1
 310717                        ? new NavigationIncomingTransitionRef[incomingLength]
 310718                        : null;
 310719                    _outgoingSort.Initialize(_outgoing, _outgoingScratch);
 310720                    _incomingSort.Initialize(_incoming, _incomingScratch);
 310721                    addedBytes = WorkingBufferBytes;
 310722                    addedPages = WorkingBufferPages;
 310723                    _prepareStage++;
 724                }
 639725                else if (_prepareStage == 3)
 726                {
 319727                    int count = _prior?.OutgoingCount ?? 0;
 4522728                    while (_prepareOrdinal < count)
 729                    {
 4212730                        if (!meter.TryConsumeExplicitEdges(1))
 9731                            return false;
 4203732                        NavigationPublishedTransition transition =
 4203733                            _prior!.GetOutgoingAt(_prepareOrdinal++);
 4203734                        if (!affectedSources.ContainsKey(transition.Owner.MapId))
 1735                            _outgoing[_outgoingFill++] = transition;
 736                    }
 310737                    _prepareStage++;
 310738                    _prepareOrdinal = 0;
 739                }
 740                else
 741                {
 320742                    int count = _prior?.IncomingCount ?? 0;
 4520743                    while (_prepareOrdinal < count)
 744                    {
 4210745                        if (!meter.TryConsumeExplicitEdges(1))
 10746                            return false;
 4200747                        NavigationIncomingTransitionRef incoming =
 4200748                            _prior!.GetIncomingAt(_prepareOrdinal++);
 4200749                        if (!affectedSources.ContainsKey(incoming.Owner.MapId))
 2750                            _incoming[_incomingFill++] = incoming;
 751                    }
 310752                    _prepareStage++;
 753                }
 754            }
 310755            return true;
 756        }
 757
 758        internal bool AdvanceSeal(
 759            MaintenanceWorkMeter meter,
 760            out bool changed,
 761            out long releasedWorkingBytes,
 762            out int releasedWorkingPages)
 763        {
 724764            changed = false;
 724765            releasedWorkingBytes = 0;
 724766            releasedWorkingPages = 0;
 724767            if (_sealStage == 0)
 768            {
 714769                if (!_outgoingSort.Advance(meter) || !_incomingSort.Advance(meter))
 404770                    return false;
 310771                releasedWorkingBytes = SortScratchBytes;
 310772                releasedWorkingPages = SortScratchPages;
 310773                _outgoingScratch = null;
 310774                _incomingScratch = null;
 310775                _outgoingSort.Release();
 310776                _incomingSort.Release();
 310777                _sameContent = _prior != null
 310778                    && _prior.OutgoingCount == _outgoing.Length
 310779                    && _prior.IncomingCount == _incoming.Length;
 310780                _sealStage++;
 781            }
 320782            if (_sealStage == 1 && _sameContent)
 783            {
 158784                int total = checked(_outgoing.Length + _incoming.Length);
 8522785                while (_compareOrdinal < total)
 786                {
 8379787                    if (!meter.TryConsumeExplicitEdges(1))
 8788                        return false;
 8371789                    bool equal = _compareOrdinal < _outgoing.Length
 8371790                        ? _prior!.GetOutgoingAt(_compareOrdinal).Equals(
 8371791                            _outgoing[_compareOrdinal])
 8371792                        : _prior!.GetIncomingAt(_compareOrdinal - _outgoing.Length).Equals(
 8371793                            _incoming[_compareOrdinal - _outgoing.Length]);
 8371794                    _compareOrdinal++;
 8371795                    if (!equal)
 796                    {
 7797                        _sameContent = false;
 7798                        break;
 799                    }
 800                }
 150801                _sealStage++;
 802            }
 162803            else if (_sealStage == 1)
 160804                _sealStage++;
 312805            changed = !_sameContent;
 312806            return true;
 807        }
 808
 809        internal NavigationTransitionPage CreatePage(long version) =>
 166810            new(Address, version, _outgoing, _incoming);
 811
 812        internal void ReleaseFinalBuffers(out long bytes, out int pages)
 813        {
 309814            bytes = FinalArrayBytes;
 309815            pages = FinalArrayPages;
 309816            _outgoing = Array.Empty<NavigationPublishedTransition>();
 309817            _incoming = Array.Empty<NavigationIncomingTransitionRef>();
 309818        }
 819
 310820        private long WorkingBufferBytes => checked(FinalArrayBytes + SortScratchBytes);
 821
 310822        private int WorkingBufferPages => checked(FinalArrayPages + SortScratchPages);
 823
 619824        private long FinalArrayBytes => checked(
 619825            NavigationTransitionPage.GetArrayBytes(
 619826                _outgoing.Length,
 619827                NavigationTransitionPage.OutgoingRecordBytes)
 619828            + NavigationTransitionPage.GetArrayBytes(
 619829                _incoming.Length,
 619830                NavigationTransitionPage.IncomingRecordBytes));
 831
 832        private int FinalArrayPages =>
 619833            (_outgoing.Length == 0 ? 0 : 1) + (_incoming.Length == 0 ? 0 : 1);
 834
 620835        private long SortScratchBytes => checked(
 620836            NavigationTransitionPage.GetArrayBytes(
 620837                _outgoingScratch?.Length ?? 0,
 620838                NavigationTransitionPage.OutgoingRecordBytes)
 620839            + NavigationTransitionPage.GetArrayBytes(
 620840                _incomingScratch?.Length ?? 0,
 620841                NavigationTransitionPage.IncomingRecordBytes));
 842
 843        private int SortScratchPages =>
 620844            (_outgoingScratch == null ? 0 : 1) + (_incomingScratch == null ? 0 : 1);
 845    }
 846
 847    private interface ITransitionRecordComparer<T>
 848    {
 849        int Compare(T left, T right);
 850    }
 851
 852    private readonly struct OutgoingComparer : ITransitionRecordComparer<NavigationPublishedTransition>
 853    {
 854        public int Compare(
 855            NavigationPublishedTransition left,
 856            NavigationPublishedTransition right) =>
 24702857            NavigationTransitionPage.CompareOutgoing(left, right);
 858    }
 859
 860    private readonly struct IncomingComparer : ITransitionRecordComparer<NavigationIncomingTransitionRef>
 861    {
 862        public int Compare(
 863            NavigationIncomingTransitionRef left,
 864            NavigationIncomingTransitionRef right) =>
 24694865            NavigationTransitionPage.CompareIncoming(left, right);
 866    }
 867
 868    private struct MergeSortWork<T, TComparer>
 869        where TComparer : struct, ITransitionRecordComparer<T>
 870    {
 871        private T[]? _values;
 872        private T[]? _source;
 873        private T[]? _destination;
 874        private int _width;
 875        private int _left;
 876        private int _middle;
 877        private int _right;
 878        private int _sourceLeft;
 879        private int _sourceRight;
 880        private int _destinationOrdinal;
 881        private bool _runActive;
 882
 883        internal void Initialize(T[] values, T[]? scratch)
 884        {
 620885            _values = values;
 620886            _source = values;
 620887            _destination = scratch;
 620888            _width = 1;
 620889            _left = 0;
 620890        }
 891
 892        internal bool Advance(MaintenanceWorkMeter meter)
 893        {
 894            System.Diagnostics.Debug.Assert(_values != null,
 895                "Transition page sorting is initialized during page preparation.");
 1228896            if (_values!.Length < 2)
 324897                return true;
 904898            var comparer = default(TComparer);
 17190899            while (_width < _values.Length)
 900            {
 16616901                if (!_runActive)
 902                {
 16286903                    _middle = Math.Min(_left + _width, _values.Length);
 16286904                    _right = Math.Min(_left + (_width * 2), _values.Length);
 16286905                    _sourceLeft = _left;
 16286906                    _sourceRight = _middle;
 16286907                    _destinationOrdinal = _left;
 16286908                    _runActive = true;
 909                }
 115396910                while (_destinationOrdinal < _right)
 911                {
 99110912                    if (!meter.TryConsumeExplicitEdges(1))
 330913                        return false;
 98780914                    T[] source = _source!;
 98780915                    T[] destination = _destination!;
 98780916                    bool takeLeft = _sourceRight >= _right
 98780917                        || (_sourceLeft < _middle
 98780918                            && comparer.Compare(
 98780919                                source[_sourceLeft],
 98780920                                source[_sourceRight]) <= 0);
 98780921                    destination[_destinationOrdinal++] = takeLeft
 98780922                        ? source[_sourceLeft++]
 98780923                        : source[_sourceRight++];
 924                }
 16286925                _runActive = false;
 16286926                _left = _right;
 16286927                if (_left < _values.Length)
 928                    continue;
 1617929                T[] priorSource = _source!;
 1617930                _source = _destination;
 1617931                _destination = priorSource;
 1617932                _width = _width > _values.Length / 2
 1617933                    ? _values.Length
 1617934                    : _width * 2;
 1617935                _left = 0;
 936            }
 574937            if (!ReferenceEquals(_source, _values))
 938            {
 455939                while (_left < _values.Length)
 940                {
 224941                    if (!meter.TryConsumeExplicitEdges(1))
 74942                        return false;
 150943                    _values[_left] = _source![_left];
 150944                    _left++;
 945                }
 946            }
 500947            return true;
 948        }
 949
 950        internal void Release()
 951        {
 620952            _values = null;
 620953            _source = null;
 620954            _destination = null;
 620955        }
 956    }
 957
 958    private struct EffectiveTransitionCursor
 959    {
 960        private readonly NavigationMap? _map;
 961        private readonly NavigationMapOverlayState? _overlay;
 962        private int _bakedOrdinal;
 963        private int _overlayOrdinal;
 964
 965        internal EffectiveTransitionCursor(NavigationMapInstance? instance)
 966        {
 8374967            _map = instance?.Map;
 8374968            _overlay = instance?.Overlay;
 8374969            _bakedOrdinal = 0;
 8374970            _overlayOrdinal = 0;
 8374971        }
 972
 973        internal bool AdvanceOne(
 974            out TraversalTransitionDefinition definition,
 975            out bool complete)
 976        {
 29515977            ReadOnlySpan<TraversalTransitionDefinition> baked = _map == null
 29515978                ? ReadOnlySpan<TraversalTransitionDefinition>.Empty
 29515979                : _map.TransitionSpan;
 29515980            int overlayCount = _overlay?.TransitionCount ?? 0;
 29515981            if (_bakedOrdinal >= baked.Length && _overlayOrdinal >= overlayCount)
 982            {
 8374983                definition = default;
 8374984                complete = true;
 8374985                return false;
 986            }
 21141987            TraversalTransitionOverlayOperation overlay = _overlayOrdinal < overlayCount
 21141988                ? _overlay!.GetTransitionAt(_overlayOrdinal)
 21141989                : default;
 21141990            int comparison = _bakedOrdinal >= baked.Length
 21141991                ? 1
 21141992                : _overlayOrdinal >= overlayCount
 21141993                    ? -1
 21141994                    : string.CompareOrdinal(baked[_bakedOrdinal].Id, overlay.Id);
 21141995            if (comparison < 0)
 996            {
 499997                definition = baked[_bakedOrdinal++];
 499998                complete = false;
 499999                return true;
 1000            }
 206421001            if (comparison == 0)
 121002                _bakedOrdinal++;
 206421003            _overlayOrdinal++;
 206421004            complete = false;
 206421005            if (overlay.Kind == TraversalTransitionOverlayOperationKind.Upsert)
 1006            {
 205331007                definition = overlay.Transition;
 205331008                return true;
 1009            }
 1091010            definition = default;
 1091011            return false;
 1012        }
 1013    }
 1014}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(Trailblazer.Pathing.NavigationWorldGraph,Trailblazer.Pathing.NavigationWorldGraph,Trailblazer.Pathing.NavigationOperationCandidate,Trailblazer.Pathing.PersistentStringMap`1<System.Boolean>,System.Boolean,System.Int64)
get_Pages()
get_Rules()
get_RetainedBytes()
get_PersistentPageCount()
Advance(Trailblazer.Pathing.MaintenanceWorkMeter)
CaptureAffectedSources(Trailblazer.Pathing.MaintenanceWorkMeter)
RefreshDefinitions(Trailblazer.Pathing.MaintenanceWorkMeter)
AdvancePriorPageDiscovery(Trailblazer.Pathing.MaintenanceWorkMeter)
AdvanceNextPageCount(Trailblazer.Pathing.MaintenanceWorkMeter)
AdvancePagePreparation(Trailblazer.Pathing.MaintenanceWorkMeter)
AdvanceNextPageFill(Trailblazer.Pathing.MaintenanceWorkMeter)
AdvancePageSeal(Trailblazer.Pathing.MaintenanceWorkMeter)
TryAdvanceEffectiveDefinition(Trailblazer.Pathing.NavigationWorldGraph,Trailblazer.Pathing.MaintenanceWorkMeter)
TryGetRetainedPrior(System.String,Trailblazer.Pathing.TraversalTransitionDefinition,Trailblazer.Pathing.NavigationPublishedTransition&)
GetOrAddPage(Trailblazer.Pathing.NavigationTransitionPageAddress)
GetPage(Trailblazer.Pathing.NavigationTransitionPageAddress)
TryGetCurrentPageState(Trailblazer.Pathing.NavigationTransitionRefreshWork/PageBuildState&)
AdvancePageCursor()
ResetPageCursor()
CompleteDefinitionPhase()
ClearPendingDefinition()
ClearPageBuildScratch()
AddWorkingBuffers(System.Int64,System.Int32)
ReleaseWorkingBuffers(System.Int64,System.Int32)
OwnPublishedPageRoot(System.String,Trailblazer.Pathing.NavigationTransitionPage,System.Int32,System.Int64)
RefreshRules(Trailblazer.Pathing.MaintenanceWorkMeter)
CreatePublished(Trailblazer.Pathing.NavigationWorldGraph,System.String,Trailblazer.Pathing.TraversalTransitionDefinition)
GetArrayBytes(System.Int32,System.Int64)
.ctor(Trailblazer.Pathing.NavigationTransitionPageAddress,Trailblazer.Pathing.NavigationTransitionPage)
AppendOutgoing(Trailblazer.Pathing.NavigationPublishedTransition)
AppendIncoming(Trailblazer.Pathing.NavigationIncomingTransitionRef)
AdvancePreparation(Trailblazer.Pathing.PersistentStringMap`1<System.Boolean>,Trailblazer.Pathing.MaintenanceWorkMeter,System.Int64&,System.Int32&)
AdvanceSeal(Trailblazer.Pathing.MaintenanceWorkMeter,System.Boolean&,System.Int64&,System.Int32&)
CreatePage(System.Int64)
ReleaseFinalBuffers(System.Int64&,System.Int32&)
get_WorkingBufferBytes()
get_WorkingBufferPages()
get_FinalArrayBytes()
get_FinalArrayPages()
get_SortScratchBytes()
get_SortScratchPages()
Compare(Trailblazer.Pathing.NavigationPublishedTransition,Trailblazer.Pathing.NavigationPublishedTransition)
Compare(Trailblazer.Pathing.NavigationIncomingTransitionRef,Trailblazer.Pathing.NavigationIncomingTransitionRef)
Initialize(T[],T[])
Advance(Trailblazer.Pathing.MaintenanceWorkMeter)
Release()
.ctor(Trailblazer.Pathing.NavigationMapInstance)
AdvanceOne(Trailblazer.Pathing.TraversalTransitionDefinition&,System.Boolean&)