< Summary

Class:Itinero.Network.Tiles.Standalone.Writer.RoutingNetworkWriterExtensions
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Tiles/Standalone/Writer/RoutingNetworkWriterExtensions.cs
Covered lines:125
Uncovered lines:16
Coverable lines:141
Total lines:313
Line coverage:88.6% (125 of 141)
Covered branches:41
Total branches:52
Branch coverage:78.8% (41 of 52)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
AddStandaloneTile(...)100%10100%
RegisterInternalEdges(...)100%10100%
get_GlobalEdgeId()100%1100%
get_IsIncoming()100%1100%
get_Vertex()100%1100%
get_Attributes()100%1100%
get_EdgeTypeId()100%1100%
get_OtherVertex()100%1100%
ClaimBoundaryCrossings(...)100%4100%
CreateBoundaryEdge(...)100%4100%
ResolveRestrictions(...)100%4100%
TryResolveRestriction(...)31.25%1652.94%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/Tiles/Standalone/Writer/RoutingNetworkWriterExtensions.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Diagnostics;
 4using System.Linq;
 5using Itinero.Data;
 6using Itinero.Network.Tiles.Standalone.Global;
 7using Itinero.Network.Writer;
 8
 9namespace Itinero.Network.Tiles.Standalone.Writer;
 10
 11/// <summary>
 12/// Extension methods related to writing standalone tiles to a network.
 13/// </summary>
 14public static class RoutingNetworkWriterExtensions
 15{
 16    /// <summary>
 17    /// Per-thread scratch for the global edge ids one insert registers.
 18    /// </summary>
 19    [ThreadStatic]
 20    private static List<GlobalEdgeId>? ArrivedEdges;
 21
 22
 23    /// <summary>
 24    /// Adds a tile in the form of a standalone tile to the network.
 25    /// </summary>
 26    /// <param name="writer">The writer to write to.</param>
 27    /// <param name="tile">The tile to add.</param>
 28    /// <param name="globalIdSet">The global id set.</param>
 29    /// <remarks>
 30    /// One lock acquisition for the whole insert, not one per edge.
 31    ///
 32    /// Three phases:
 33    ///
 34    /// <list type="number">
 35    /// <item><b>Claim, unlocked.</b> Register the tile's internal edges' global ids and claim the
 36    /// boundary crossings whose other half has arrived. A standalone tile arrives with its internal
 37    /// edges already encoded, so nothing here writes tile data — it fills concurrent dictionaries.
 38    /// Doing it before any lock is what makes the next step possible.</item>
 39    /// <item><b>Write, grouped by neighbour.</b> Create the matched boundary edges holding this
 40    /// tile's stripe and one partner's, taken together and ordered, all of that partner's
 41    /// crossings at once. Each edge is created exactly
 42    /// once — only the tile that won the claim in step 1 builds it — and writing it puts an entry
 43    /// in both tiles, which is how a cross-tile edge is represented.</item>
 44    /// <item><b>Restrictions.</b> Separate, and locking themselves, because a restriction names
 45    /// edges in tiles that cannot be predicted from the tile being inserted.</item>
 46    /// </list>
 47    /// </remarks>
 48    public static void AddStandaloneTile(this RoutingNetworkWriter writer, StandaloneNetworkTile tile,
 49        GlobalNetworkManager globalIdSet)
 192850    {
 51        // ---- install first, under this tile's stripe alone ----
 52        // Before anything is claimable. A crossing this tile records becomes visible to the tile
 53        // on the other side, which will immediately want this tile's vertices to build the edge —
 54        // so the tile has to be in the network before its halves are published. Claiming first and
 55        // installing later fails with "vertex not found" on the other thread.
 192856        using (writer.LockTiles(stackalloc[] { tile.TileId }))
 192857        {
 192858            writer.AddTile(tile.NetworkTile);
 192859        }
 60
 61        // ---- phase 1: no tile writes, no locks ----
 62        // Reused per thread rather than allocated per insert: ~346 ids per tile is a 5KB list
 63        // every time, on a path where GC already shows up. Gating the collection on "is anything
 64        // pending" instead looked cheaper and was wrong — a restriction parked by another thread
 65        // mid-insert then waits for the sweep, which made resolution depend on how many tiles
 66        // happen to follow. ConcurrentInsert_ManyTilesWithBoundaryCrossings_MatchesSerialInsert
 67        // fails on that.
 68        //
 69        // Safe to reuse: the list never outlives this call. RetryPendingRestrictionsFor reads it
 70        // synchronously, and nothing here inserts a tile re-entrantly on the same thread.
 192871        var arrived = ArrivedEdges ??= new List<GlobalEdgeId>(512);
 192872        arrived.Clear();
 73
 74        // 2.6M map entries per cold block against ~200k reads, and its only consumer is turn
 75        // restriction resolution — routing never reads this map, since the global id a client sees
 76        // comes from the edge's own attributes. Skipping it entirely was measured (+7.1% cold) and
 77        // is NOT an option: it silently drops turn restrictions that name an interior edge.
 192878        RegisterInternalEdges(tile, globalIdSet, arrived);
 192879        var crossings = ClaimBoundaryCrossings(tile, globalIdSet);
 80        // ---- phase 2: every tile this insert writes, locked once ----
 81        // Grouped by partner tile: one acquisition per NEIGHBOUR, not per crossing and not one
 82        // covering every partner at once.
 83        //
 84        // Both extremes are bad here. Locking this tile plus all of its partners for the whole
 85        // batch holds up to nine stripes at once, and the inserts running concurrently are
 86        // precisely the ones that share boundaries — VertexTouched loads a tile together with its
 87        // eight neighbours, BoxTouched loads a whole box — so every insert collides with every
 88        // other. Locking per crossing keeps holds short but pays an acquisition for each of the
 89        // many ways that cross a single boundary.
 90        //
 91        // A tile has at most eight neighbours and usually fewer, so grouping bounds the
 92        // acquisitions by neighbours while keeping each hold to two stripes.
 205293        crossings.Sort(static (x, y) => x.OtherVertex.TileId.CompareTo(y.OtherVertex.TileId));
 192894        var start = 0;
 373095        while (start < crossings.Count)
 180296        {
 180297            var partner = crossings[start].OtherVertex.TileId;
 180298            var end = start;
 540699            while (end < crossings.Count && crossings[end].OtherVertex.TileId == partner) end++;
 100
 1802101            using (writer.LockTiles(stackalloc[] { tile.TileId, partner }))
 1802102            {
 7208103                for (var i = start; i < end; i++)
 1802104                {
 1802105                    CreateBoundaryEdge(writer, globalIdSet, crossings[i]);
 1802106                    arrived.Add(crossings[i].GlobalEdgeId);
 1802107                }
 1802108            }
 109
 1802110            start = end;
 1802111        }
 112
 113        // ---- phase 3: restrictions ----
 1928114        ResolveRestrictions(writer, tile, globalIdSet, arrived);
 115
 116        // Give back the headroom geometric growth took. The growth is what makes the appends above
 117        // linear; the slack is what would otherwise stay resident for the life of the process, and
 118        // that reaches even the hot regime, which does no inserts at all.
 1928119        writer.TrimTile(tile.TileId);
 1928120    }
 121
 122    /// <summary>
 123    /// Registers every internal edge's GlobalEdgeId → EdgeId mapping, collecting the ids it wrote.
 124    /// </summary>
 125    /// <remarks>
 126    /// The collected ids are what a pending restriction can be waiting for, so they drive the
 127    /// targeted retry instead of a full pass over the pending list.
 128    /// </remarks>
 129    private static int RegisterInternalEdges(StandaloneNetworkTile tile, GlobalNetworkManager globalIdSet,
 130        List<GlobalEdgeId> arrived)
 1928131    {
 1928132        var registered = 0;
 1928133        var tileEnumerator = new NetworkTileEnumerator();
 1928134        tileEnumerator.MoveTo(tile.NetworkTile);
 1928135        var tileId = tile.TileId;
 15108136        for (uint v = 0; v < tile.NetworkTile.VertexCount; v++)
 5626137        {
 5626138            var vertexId = new VertexId(tileId, v);
 5626139            if (!tileEnumerator.MoveTo(vertexId)) continue;
 140
 13022141            while (tileEnumerator.MoveNext())
 7396142            {
 143                // only process forward edges to avoid double registration.
 11094144                if (!tileEnumerator.Forward) continue;
 145
 3698146                var globalEdgeId = tileEnumerator.GlobalEdgeId;
 3698147                if (globalEdgeId != null)
 3698148                {
 3698149                    globalIdSet.EdgeIdSet.Set(globalEdgeId.Value, tileEnumerator.EdgeId);
 150
 3698151                    arrived.Add(globalEdgeId.Value);
 3698152                    registered++;
 3698153                }
 3698154            }
 5626155        }
 156
 1928157        return registered;
 1928158    }
 159
 160    /// One half of a boundary crossing matched with the other, ready to become an edge.
 161    private readonly record struct MatchedCrossing(
 5406162        GlobalEdgeId GlobalEdgeId,
 3604163        bool IsIncoming,
 1802164        VertexId Vertex,
 1802165        (string key, string value)[] Attributes,
 1802166        uint EdgeTypeId,
 5778167        VertexId OtherVertex);
 168
 169    /// <summary>
 170    /// Claims the crossings whose other half has already arrived, recording the rest.
 171    /// </summary>
 172    /// <remarks>
 173    /// Returns the matches instead of creating the edges here, so that no tile lock is taken
 174    /// while still walking the tile — which is what keeps phase 1 free of any lock ordering.
 175    /// </remarks>
 176    private static List<MatchedCrossing> ClaimBoundaryCrossings(StandaloneNetworkTile tile,
 177        GlobalNetworkManager globalIdSet)
 1928178    {
 1928179        var matched = new List<MatchedCrossing>();
 13112180        foreach (var (isIncoming, globalEdgeId, vertex, attributes, edgeTypeId) in tile.GetBoundaryCrossings())
 3664181        {
 182            // Materialised before the claim: the stored half outlives this tile's enumerator, and
 183            // the claim may hand it to the other tile's thread at any moment.
 3664184            var ownAttributes = attributes.ToArray();
 185
 186            // Claim-or-record in one step. Reading, then creating the edge, then removing would
 187            // let two tiles each see the other's half and each create the edge; the claim makes
 188            // exactly one of them the winner.
 3664189            if (globalIdSet.TryClaimBoundaryCrossing(globalEdgeId,
 3664190                    (vertex, ownAttributes, edgeTypeId, isIncoming), out var pending))
 1802191            {
 1802192                matched.Add(new MatchedCrossing(globalEdgeId, isIncoming, vertex, ownAttributes,
 1802193                    edgeTypeId, pending.vertex));
 1802194            }
 195
 196            // No else: when the claim fails this tile's half has already been recorded by the
 197            // same call, and the other tile will find it.
 3664198        }
 199
 1928200        return matched;
 1928201    }
 202
 203    /// <summary>
 204    /// Creates one boundary edge. Caller holds the locks for both tiles.
 205    /// </summary>
 206    private static void CreateBoundaryEdge(RoutingNetworkWriter writer, GlobalNetworkManager globalIdSet,
 207        MatchedCrossing crossing)
 1802208    {
 209        // isIncoming=true: vertex is at way tail, other is at way head.
 1802210        var tail = crossing.IsIncoming ? crossing.Vertex : crossing.OtherVertex;
 1802211        var head = crossing.IsIncoming ? crossing.OtherVertex : crossing.Vertex;
 212
 1802213        var length = writer.ComputeEdgeLength(tail, head);
 1802214        var newEdge = writer.AddEdge(tail, head, null, crossing.Attributes,
 1802215            crossing.EdgeTypeId, length, crossing.GlobalEdgeId);
 216
 217        // register boundary edge's GlobalEdgeId → EdgeId mapping.
 1802218        globalIdSet.EdgeIdSet.Set(crossing.GlobalEdgeId, newEdge);
 1802219    }
 220
 221    /// Resolves this tile's restrictions, then retries everything still pending.
 222    private static void ResolveRestrictions(RoutingNetworkWriter writer, StandaloneNetworkTile tile,
 223        GlobalNetworkManager globalIdSet, IReadOnlyList<GlobalEdgeId> arrived)
 1928224    {
 1928225        var seen = 0;
 1928226        var parked = 0;
 7644227        foreach (var (edges, isProhibitory, turnCostTypeId, restrictionAttributes) in tile.GetGlobalRestrictions())
 930228        {
 930229            var globalRestriction = new GlobalRestriction(
 1860230                edges.Select(e => e.globalEdgeId),
 930231                isProhibitory,
 930232                restrictionAttributes.ToArray());
 233
 930234            seen++;
 930235            if (!TryResolveRestriction(globalRestriction, globalIdSet, writer))
 576236            {
 576237                parked++;
 576238                globalIdSet.AddPendingRestriction(globalRestriction);
 576239            }
 930240        }
 241
 242        // Retry only the restrictions waiting for an edge this insert added. A full pass here
 243        // re-examined every pending restriction on every insert - 535,147 examinations for 2,335
 244        // resolutions over one cold block.
 1928245        globalIdSet.RetryPendingRestrictionsFor(arrived,
 3408246            r => TryResolveRestriction(r, globalIdSet, writer));
 1928247    }
 248
 249    private static bool TryResolveRestriction(GlobalRestriction globalRestriction,
 250        GlobalNetworkManager globalIdSet, RoutingNetworkWriter writer)
 2410251    {
 252        // try to resolve all GlobalEdgeIds to EdgeIds.
 2410253        if (!globalRestriction.TryBuildNetworkRestriction(GetEdge, out var networkRestriction))
 1480254            return false;
 255
 930256        if (networkRestriction!.Count < 2) return true;
 257
 258        // get last edge and determine turn cost vertex.
 930259        var last = networkRestriction[^1];
 930260        var edgeEnumerator = writer.GetEdgeEnumerator();
 930261        if (!edgeEnumerator.MoveTo(last.edge, last.forward))
 0262            return false;
 930263        var turnCostVertex = edgeEnumerator.Tail;
 264
 930265        var secondToLast = networkRestriction[^2];
 266
 930267        if (networkRestriction.IsProhibitory)
 930268        {
 269            // prohibitory: add a single cost entry forbidding this specific turn.
 930270            var costs = new uint[,] { { 0, 1 }, { 0, 0 } };
 930271            writer.AddTurnCosts(turnCostVertex, networkRestriction.Attributes,
 930272                [secondToLast.edge, last.edge], costs,
 930273                networkRestriction.Take(networkRestriction.Count - 2).Select(x => x.edge));
 274
 930275        }
 276        else
 0277        {
 278            // mandatory: add cost for every *other* edge at the vertex.
 0279            if (!edgeEnumerator.MoveTo(secondToLast.edge, secondToLast.forward))
 0280                return false;
 0281            var to = edgeEnumerator.Head;
 282
 0283            edgeEnumerator.MoveTo(to);
 0284            while (edgeEnumerator.MoveNext())
 0285            {
 0286                if (edgeEnumerator.EdgeId == secondToLast.edge ||
 0287                    edgeEnumerator.EdgeId == last.edge) continue;
 288
 0289                var costs = new uint[,] { { 0, 1 }, { 0, 0 } };
 0290                writer.AddTurnCosts(turnCostVertex, networkRestriction.Attributes,
 0291                    [secondToLast.edge, edgeEnumerator.EdgeId], costs,
 0292                    networkRestriction.Take(networkRestriction.Count - 2).Select(x => x.edge));
 0293            }
 0294        }
 295
 930296        return true;
 297
 298        (EdgeId edge, bool forward)? GetEdge(GlobalEdgeId geid, bool isFirst)
 4135299        {
 300            // exact match short-circuit (cheap check before walking).
 4135301            if (globalIdSet.EdgeIdSet.TryGet(geid, out var edgeId))
 11302                return (edgeId, true);
 4124303            if (globalIdSet.EdgeIdSet.TryGet(geid.GetInverted(), out edgeId))
 13304                return (edgeId, false);
 305
 306            // walk from the chain-anchor end; first edge anchors at Head, every
 307            // subsequent edge anchors at Tail (chain invariant: previous.Head ==
 308            // current.Tail).
 4111309            return GlobalRestrictionExtensions.WalkFromAnchor(geid, isFirst,
 4111310                globalIdSet.EdgeIdSet.TryGet);
 4135311        }
 2410312    }
 313}