Cancellation Tokens

[JoeCooper]

Please have a look at how I've done this.

I've added cancellation tokens with default tokens as default parameters.

Then, I've added a cancellation token parameter to the algorithm base. I understand this is not intended as a public interface and it does not, therefore, offer a default parameter.

At each stage I've amended the unit tests to compile, however I do not have a plan for unit testing the cancellation tokens themselves.

You might notice at this point most code is not observing the tokens. According to Microsoft's guidelines, a method is not required to act on the token's state, and it is specifically not advised to abort after the primary workload has completed.

With the interfaces in order, various persons can then add code to observe the tokens in strategic points.

My third commit here ("Observe cancellation token in SearchClosestEdge") evaluates the cancellation token (with .ThrowIfCancellationRequested) at the start of two loop bodies in HilbertExtensions.SearchClosestEdge. This is because these loops are where the bulk of the time is spent in the default Router's TryResolve implementation.

If I have time (unconfirmed) I would like to go find a good spot to check for cancellation in Router.TryCalculateRaw, but we should sync up first.

[JoeCooper]

Hey, thanks for having a look through this. At a glance, it looks like you’re right on all points. Furthermore if you or anyone claims to use a given method from outside Itinero, than unless a default parameter is provided, it is a breaking change and therefore incorrect. When I’m in the office on Tuesday I’ll put in a new commit.

Sent from my iPad

On 30 Mar 2018, at 14:46, Joe Amenta notifications@github.com wrote:

@airbreather requested changes on this pull request.

I understand not adding a default to the AlgorithmBase.DoRun(CancellationToken) method, but why not the public IAlgorithm.Run(CancellationToken) and AlgorithmBase.Run(CancellationToken) methods? When I was actively experimenting with Itinero, I would regularly find myself going a layer down from the static helper methods to re-connect the different pieces for various reasons. It feels awkward having to make all such situations explicitly tell it (in their source code anyway) that they don't care about cancellation.

especially if all it takes to it that way is adding defaults on exactly those two lines One note about default parameters... using them like this instead of adding overloads is fine for source compatibility, but will break binary compatibility (i.e., downstream consumers will have to target the new library and recompile). I don't know how much binary compatibility matters at this stage, but I wanted to make sure to bring it up.

I also saw a few public static methods where a default was not added (called out on line comments)... not sure if that was intentional, but I didn't see any notes about them.

Regarding usage of ThrowIfCancellationRequested(), it looks like a good start to me in the place you added it. I agree with not adding too much of it right away before syncing up.

In src/Itinero/Algorithms/AlgorithmBase.cs:

@@ -79,19 +80,19 @@ public void CheckHasRunAndHasSucceeded() ///

/// Runs the algorithm. ///

• public void Run()
• public void Run(CancellationToken cancellationToken) This one feels like it can have a default, eh? See also: comment in IAlgorithm.

In src/Itinero/Algorithms/Contracted/Dual/RouterExtensions.cs:

@@ -32,7 +33,7 @@ internal static class RouterExtensions /// Calculates a many-to-many weight matrix using a dual edge-based graph. /// internal static Result<T[][]> CalculateManyToMany(this ContractedDb contractedDb, RouterDb routerDb, Profile profile, WeightHandler weightHandler,

• RouterPoint[] sources, RouterPoint[] targets, T max) where T : struct
• RouterPoint[] sources, RouterPoint[] targets, T max, CancellationToken cancellationToken = new CancellationToken()) where T : struct In case we have access to C# 7.1 features, CancellationToken cancellationToken = default is less verbose and repetitive.

I think you can do this all at once with a find/replace "CancellationToken cancellationToken = new CancellationToken()" to that, and then repeat for the places where you used "CancellationToken token = new CancellationToken()".

In src/Itinero/Algorithms/IAlgorithm.cs:

@@ -42,7 +44,7 @@ bool HasSucceeded ///

/// Runs the algorithm. ///

• void Run();
• void Run(CancellationToken cancellationToken); This feels like it could accept a default too... see also: comment in AlgorithmBase.

If you do this (and the counterpart in AlgorithmBase) then I think you can find-replace ".Run(new CancellationToken())" with ".Run()" and shrink the diff down a lot at the end there.

In src/Itinero/Algorithms/Matrices/WeightMatrixAlgorithm.cs:

@@ -104,6 +105,12 @@ protected sealed override void DoRun() this.HasSucceeded = true; }

• // Whereas the sample presents this class as a public interface, I have provided this wrapper. This would probably be unnecessary if Run had a default.

In src/Itinero/Algorithms/Routes/CompleteRouteBuilder.cs:

@@ -470,36 +470,36 @@ private void AppendRoute(Route route, IAttributeCollection shortcutMeta) ///

/// Builds a route. ///

• public static Route Build(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, EdgePath path)
• public static Route Build(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, EdgePath path, CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/CompleteRouteBuilder.cs:

     }

     /// <summary>
     /// Builds a route.
     /// </summary>

• public static Result TryBuild(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, EdgePath path)
• public static Result TryBuild(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, EdgePath path, CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/CompleteRouteBuilder.cs:

     }

     /// <summary>
     /// Builds a route.
     /// </summary>

• public static Route Build(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, List path)
• public static Route Build(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, List path, CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/CompleteRouteBuilder.cs:

     }

     /// <summary>
     /// Builds a route.
     /// </summary>

• public static Result TryBuild(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, List path)
• public static Result TryBuild(RouterDb db, Profile profile, RouterPoint source, RouterPoint target, List path, CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/FastRouteBuilder.cs:

@@ -391,37 +392,40 @@ private Speed GetSpeedFor(ushort profileId) ///

/// Builds a route. ///

• public static Route Build(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, RouterPoint source, RouterPoint target, EdgePath path)
• public static Route Build(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, RouterPoint source, RouterPoint target, EdgePath path,
• CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/FastRouteBuilder.cs:

     }

     /// <summary>
     /// Builds a route.
     /// </summary>

• public static Result TryBuild(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, RouterPoint source, RouterPoint target, EdgePath path)
• public static Result TryBuild(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, RouterPoint source, RouterPoint target, EdgePath path,
• CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/FastRouteBuilder.cs:

     }

     /// <summary>
     /// Builds a route.
     /// </summary>

• public static Route Build(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, RouterPoint source, RouterPoint target, List path)
• public static Route Build(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, RouterPoint source, RouterPoint target, List path,
• CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Routes/FastRouteBuilder.cs:

     }

     /// <summary>
     /// Builds a route.
     /// </summary>
     public static Result<Route> TryBuild(RouterDb db, Profile profile, Func<ushort, Profiles.Factor> getFactor, 

• RouterPoint source, RouterPoint target, List path)
• RouterPoint source, RouterPoint target, List path, CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Search/Hilbert/HilbertExtensions.cs:

@@ -634,7 +635,8 @@ public static long Distance(this RoutingNetwork graph, int n, uint vertex) /// /// public static uint SearchClosestEdge(this GeometricGraph graph, float latitude, float longitude,

• float latitudeOffset, float longitudeOffset, float maxDistanceMeter, Func<GeometricEdge, bool> isOk)
• float latitudeOffset, float longitudeOffset, float maxDistanceMeter, Func<GeometricEdge, bool> isOk,
• CancellationToken cancellationToken) Missed defaulting here?

In src/Itinero/Algorithms/Shortcuts/RouterDbExtensions.cs:

@@ -30,7 +31,7 @@ public static class RouterDbExtensions ///

/// Adds multiple shortcut db's at the same time. ///

• public static void AddShortcuts(this RouterDb routerDb, params ShortcutSpecs[] shortcutSpecs)
• public static void AddShortcuts(this RouterDb routerDb, CancellationToken cancellationToken = new CancellationToken(), params ShortcutSpecs[] shortcutSpecs) I'm not in love with how this makes the callers look... maybe this is one of those cases where it makes sense to add an overload with the cancellation token at the cost of the cancellation-aware overload's shortcutSpecs not being params?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[JoeCooper]

@airbreather I've changed a bit based on your comments, although I'm putting off using default until @xivk confirms we can use C# 7.1 in this project. What do you think about the interface in Shortcuts/RouterDbExtensions now?

[airbreather]

What do you think about the interface in Shortcuts/RouterDbExtensions now?

Hmm, this works just fine for me:

        /// <summary>
        /// Adds multiple shortcut db's at the same time.
        /// </summary>
        public static void AddShortcuts(this RouterDb routerDb, params ShortcutSpecs[] shortcutSpecs) => AddShortcuts(routerDb, shortcutSpecs, new CancellationToken());

        /// <summary>
        /// Adds multiple shortcut db's at the same time.
        /// </summary>
        public static void AddShortcuts(this RouterDb routerDb, ShortcutSpecs[] shortcutSpecs, CancellationToken cancellationToken = new CancellationToken())
        {

[JoeCooper]

That's nice. I didn't know you could do that. I'll stick that in there now.

[airbreather]

That looks good now.

One thing to point out is that now the only two files under the test folder that need to change are:

• test\Itinero.Test\RouterMock.cs
• test\Itinero.Test\Algorithms\Search\MockResolver.cs

It appears that all other changes under test\ could be reverted... I determined this by doing a mass find/replace of Run(new CancellationToken()) to Run(), then comparing the test\ folder to what it was before, and observing that the only remaining changes outside those two files were in the using blocks.

[JoeCooper]

I'll evaluate that now. Thanks for reminding me about that and checking.

[JoeCooper]

I've gone ahead and reverted the changes to the unit tests.

[airbreather]

If you merge JoeCooper/routing#1, then the number of files touched in this PR should go back down, such that after this PR gets merged, all those files don't show this as their last change...

I did a little trick to revert all of them at once:

1. Check out original version
2. Copy test folder off
3. Check out your branch
4. Replace the test folder with the copy
5. Undo changes to the two I identified above
6. Commit and push to my fork

[airbreather]

This looks fine to me now :+1:.

The C# 7.1 default vs. new CancellationToken() thing would be nice to have, but it's functionally identical and it could happen later anyway.

[JoeCooper]

It does tell me explicitly that the project is not configured to use 7.1, but if @xivk allows it than we're good to go on that point too.

[JoeCooper]

Oh, you can approve the PR? I didn't realize you had that relationship to the project. Can you approve a move to 7.1?

[airbreather]

Approval just means I reviewed it and I'm OK with it. I don't have commit / merge privileges or anything. I did leave some commentary on #156 endorsing this approach, so I thought it only appropriate that I give feedback on the implementation.

[JoeCooper]

All clear.

[airbreather]

For example, one thing I mentioned during my review was overloads vs. default parameters... I'm OK with this myself, but that's only because I don't have any backwards compatibility concerns (my company still isn't using Itinero yet)... @xivk may have other opinions, heh.

[JoeCooper]

Yes, that makes sense. I brought them up in the issue thread because default parameters break the ABI, but Ben decided this was acceptable.

[xivk]

I'm on holiday this week, sorry... I'll have a look at all this next week.

Thanks for the work done on this already!

[JoeCooper]

I was out for a week. For various reasons I might not have an opportunity to add more cancellation tests, but if the interfaces are updated, others can add them on their own critical paths on an as needed basis and the feature will accumulate over time.

[xivk]

OK I left some obsolete comments above, I should have read everything first.

This looks really good, it has minimal impact and adds a valuable feature. Thanks a lot!

About the C# 7.1, let's go for it.

About the binary compat issue, what would it take to guarantee this? I guess replacing defaults with overloads everywhere? Most usecases I know of don't upgrade without rebuilding so I don't think it's a big issue but perhaps something to aim for in the future? How do other (well-managed) .NET packages handle this?

[airbreather]

@xivk can we use this C# 7.1 feature?

I think so, any downside to using C# 7.1 features at this point? I guess it stops people from using older VS versions?

Yeah, using C# 7.1 features pretty much just makes it so it won't build in VS2017 15.2 and below. You also have to enable it specifically by putting <LangVersion>X</LangVersion> into a PropertyGroup in the .csproj file where you want to use the stuff, where X is one of:

1. latest (assuming you're on a new enough VS2017 version)
2. 7.1 (VS2017 15.3 and above)
3. 7.2 (VS2017 15.5 and above)
4. 7.3 (VS2017 15.7 and above, still in preview at the time of writing)

At work, I've advised that we use an explicit version number instead of latest, because it kills builds much earlier and offers a more helpful message if the compiler doesn't support that version instead of just a generic syntax error. YMMV.

About the binary compat issue, what would it take to guarantee this? I guess replacing defaults with overloads everywhere? Most usecases I know of don't upgrade without rebuilding so I don't think it's a big issue but perhaps something to aim for in the future? How do other (well-managed) .NET packages handle this?

As far as I know, yes, adding overloads is the way to go for this kind of change to ensure both binary and source compatibility. Adding optional parameters feels like it can be a pretty hard breaking change since it can cascade downstream: assuming perfect NuGet version specs, then in the best case, any packages depending on Itinero that have their own downstream dependents would have to mark their own packages as depending on "pre-CancellationToken" (maximum) or "post-CancellationToken" (higher minimum) versions of Itinero to ensure that applications can't break things simply by bumping up their own version of Itinero, so the default-parameter approach is technically not semver-compliant if this happens before a major version bump (1.x to 2.x).

[JoeCooper]

Yes that’s right, binary compatibility is necessary for binaries deployed through NuGet that depend on Itinero. The correct way to handle this must be overloads, then. When I did this, that did not occur to me.

I will find some time this week to make another commit.

On 15 Apr 2018, at 15:49, Joe Amenta notifications@github.com wrote:

@xivk can we use this C# 7.1 feature?

I think so, any downside to using C# 7.1 features at this point? I guess it stops people from using older VS versions?

Yeah, using C# 7.1 features pretty much just makes it so it won't build in VS2017 15.2 and below. You also have to enable it specifically by putting X into a PropertyGroup in the .csproj file where you want to use the stuff, where X is one of:

latest (assuming you're on a new enough VS2017 version) 7.1 (VS2017 15.3 and above) 7.2 (VS2017 15.5 and above) 7.3 (VS2017 15.7 and above, still in preview at the time of writing) At work, I've advised that we use an explicit version number instead of latest, because it kills builds much earlier and offers a more helpful message if the compiler doesn't support that version instead of just a generic syntax error. YMMV.

About the binary compat issue, what would it take to guarantee this? I guess replacing defaults with overloads everywhere? Most usecases I know of don't upgrade without rebuilding so I don't think it's a big issue but perhaps something to aim for in the future? How do other (well-managed) .NET packages handle this?

As far as I know, yes, adding overloads is the way to go for this kind of change to ensure both binary and source compatibility. Adding optional parameters feels like it can be a pretty hard breaking change since it can cascade downstream: assuming perfect NuGet version specs, then in the best case, any packages depending on Itinero that have their own downstream dependents would have to mark their own packages as depending on "pre-CancellationToken" (maximum) or "post-CancellationToken" (higher minimum) versions of Itinero to ensure that applications can't break things simply by bumping up their own version of Itinero, so the default-parameter approach is technically not semver-compliant if this happens before a major version bump (1.x to 2.x).

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[airbreather]

The correct way to handle this must be overloads, then. When I did this, that did not occur to me.

I will find some time this week to make another commit.

I can pick this up... I don't think there's a sane way to avoid breaking external stuff that adds their own subclasses of AlgorithmBase, but everything else should be easy enough (just tedious, which I'm fine with, since I have some time to kill).

Edit: same for subclasses of other things like RouterBase and implementations of interfaces like IUnimodalInstructionGenerator.

[airbreather]

Hmm, right, that brings up an interesting problem: some of the static methods have their own optional parameters other than CancellationToken, e.g.:

public static void SplitLongEdges(this RouterDb db, Action<uint> newVertex = null, CancellationToken cancellationToken = new CancellationToken())

It can't tack on a required CancellationToken at the end while still keeping optional values for those other parameters. So those other optional parameters would become required when calling the method with a CancellationToken overload.

I'm going to go with having callers give explicit values when using a CancellationToken overload for 1.x, with the idea that 2.x can make this specific thing nicer.

[airbreather]

My branch cancellation-overloads is more-or-less the size of the approach that uses overloads instead of optional parameters... I still need to do a bit of self-review on it.

That feels like too much code just to ensure binary compatibility, though.

[xivk]

That feels like too much code just to ensure binary compatibility, though.

I feel like that all the time when adding new features, the technical debt keeps growing. That's why a v2 is long overdue.

That being said the cancellation-overloads branch looks good, if we can bring that in then this is done.

[airbreather]

I've made a few updates and created JoeCooper/routing#2... once @JoeCooper merges that into his branch, this PR should automatically update to have the overloads instead of the optional parameters.

[JoeCooper]

I've merged in the updates from @airbreather. Sorry it took a while. April has been an absolute clusterfrack. I'm back in the office though.

[JoeCooper]

Merged again.

[airbreather]

:+1: this looks good to me now.

[xivk]

Thanks @JoeCooper @airbreather :+1:

[JoeCooper]

Thanks everyone

On 3 May 2018, at 21:31, Ben Abelshausen notifications@github.com wrote:

Thanks @JoeCooper @airbreather 👍

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.