Rash thoughts about .NET, C#, F# and Dynamics NAV.


"Every solution will only lead to new problems."

Thursday, 1. December 2016


Context matters

Filed under: Diverses,F# — Steffen Forkmann at 8:35 Uhr

[This article is part of the F# advent calendar 2016]

A couple of months ago I wrote a blog post called “Make failure great again” and this joke backfired on me. The post was meant as an introduction to the F# compiler project and showed in a simple scenario all the steps that are needed to get a Pull Request into the compiler.

Around the same time as the blog post I sent a Pull Request to the compiler project which is pretty similar to the one described in the post. In #1142 I extended it to give a better error message on the following snippet:

Before the change the compiler would just complain about the type error between the if and the corresponding else branch.

Wrong type in else branch

Newcomers from statement-based languages like C# might have a hard time to understand what’s going on.

After the change we would get something like the following:

Wrong type in else branch

This message now additionally explains that F# treats “if/then/else”-constructs as expressions and the return type of both branches must return the same.

Unfortunately reality is a bitch and it turned out my test cases were too narrow. Since the new error messages are already released in Visual Studio 2017 RC1, it didn’t take long for the following bug report to appear:

The compiler is now showing the following error:

Wrong type in else branch

Obviously this is not correct, but what exactly went wrong? In order to understand the problem we need to take a look at the principal change of the pull request.

This strange looking code is part of TypeChecker.fs and represents the part where F#’s compiler tries to type check “if/then/else”-constructs. It uses pattern mattching on the abstract syntax tree (line 1) to destructure the current expression and calls the the type checker with all sub-expressions recursively (look for TcExpr* calls).

In line 15 I added context information to the current type checker environment. This allows the type checker reporting engine to show a more concrete error message if a type check fails.

The new bug is that we actually type check recursively and that the context information is passed down into all sub-expressions. So basically every type error somewhere in a else branch will show this way too specific error message. Ouch.

So what we really want is to limit the context information only to the one type check of the result type. So I tried to replace line 15-17 with the following:

This code splits the type check in two parts. In line 1-2 we type check the else-branch with a fresh type variable and in line 4-5 we add the missing restriction that our if and else branches must have the same type. This actually works nicely and limits the error message to exactly the one type check that we want.

Fortunately red unit tests on the CI server catched the fact that I introduced a new problem. It took me a while to understand the problem, but it comes down to the fact the the type checker also acts as type inference algorithm. In contrast to C#’s var keyword where types are only inferred from the right side of an assignment the F# compiler also infers types from the context. By splitting the type check into 2 parts we didn’t pass captured type inference information (in overallTy) down into the recursive type check call and therefore some specific situations can’t be inferred anymore. Ouch.

I also forgot to pass the new type checker environment to the UnifyTypes call. This would probably have fixed all tests in the compiler code base, but since we would still change the order of type checking there might be cases that are still broken. So that’s a risk we clearly don’t want to take just for fancy error messages.

So what’s the correct solution then? We still need to limit the context to the last type check but we can’t split the check in this naive way.

One way to do that is to keep track from where the context information is coming. The F# compiler is already using a “range” type to specify locations in the source code.

This allows us to check if the range of reported error matches the range of the whole else-branch and report the corresponding error:

Case closed.

If you are interested in the details then take a look at #1827.

Sunday, 14. August 2016


Fable |> React – Running a F# Sudoku solver everywhere

Filed under: Diverses — Steffen Forkmann at 13:47 Uhr

A couple of years ago I was flying to Canada and was bored enought to write a Sudoku solver console app in F#. For some reason I was thinking about that today and thought that I should try to put that into a F# React Native app (see this blog post for an introduction).

So the solver code is this:

Sudoku on React Native

It turned out porting this code to React Native was pretty easy. I just copied the F# React Native demo app, added my solver code and created a React View with the data points and got this:

Sudoku solver on android

I find it really amazing that you can just take fairly complex code that was written against .NET Framework collection APIs and run it as JavaScript apps. Fable is mapping the .NET API calls into similar JavaScript API calls behind the scenes.

You can find the full source code at https://github.com/forki/SudokuApp.

Sudoku in the browser (via React)

As a the next step I took the same code and ported it to a React web app that runs in the browser:

Sudoku solver in the browser

You can find the full source code at https://github.com/forki/react-sudoku.

Sudoku in the browser (via VirtualDOM)

[Update] Tomas Jansson ported the sample to fable-virtualdom. Here is how he creates the text boxes:

You can find the full source code at https://github.com/fable-compiler/fable-virtualdom/tree/master/samples/sudoku.

Sudoku on electron

In order to come full circle I tried to put the Sudoku solver into a React app on the Electron shell. This gives me a cross-platform desktop app:

Sudoku solver desktop on Electron

You can find the full source code at https://github.com/forki/sudoku-electron.

Summary

I’m really amazed how easy Fable + React makes it for me to put existing F# code into the JavaScript ecosystem.

The same code is now running

  • as Console App on .NET,
  • as React Native app on Android and iOS,
  • in the browser on React,
  • in the browser on VirtualDOM,
  • and with Electron as Desktop app on all operating systems.

Friday, 12. August 2016


Fable |> AsyncStorage – Data access with F# on React Native

Filed under: Diverses — Steffen Forkmann at 12:55 Uhr

I my last two articles I introduced React Native app development with F# and showed how we can do HTTP calls with the Fetch API. I also mentioned briefly how to access the local storage of your phone in order to cache information. In this article I want to look a small bit deeper into this.

React Native provides a basic abstraction called AsyncStorage that works on Android and iOS. With the help of a package called fable-react-native-simple-store we can use it from F#:

As you can see all JavaScript promises calls are mapped into F# async computations and everything is statically typed. This makes it easy to integrate the local storage with other F# code.

DataStore internals

AsyncStorage is a simple, unencrypted, asynchronous, persistent, key-value storage system that is global to the app. It should be used instead of LocalStorage. [project site]

AsyncStorage only provides a very basic key-value store. With the help of fable-react-native-simple-store we get something that allows us to store objects in arrays separated by type:

This is still a very low level data storage API, but as the sample app shows it’s already useful for caching specific app data.

Wednesday, 10. August 2016


Fable |> Fetch – HTTP calls in JavaScript apps with F#

Filed under: F# — Steffen Forkmann at 12:09 Uhr

I my last article I introduced React Native app development with F# and mentioned briefly that we can do HTTP calls with the help of the very popular Fetch API.

Fetch provides a generic definition of Request and Response objects (and other things involved with network requests). This will allow them to be used wherever they are needed in the future, whether it’s for service workers, Cache API and other similar things that handle or modify requests and responses, or any kind of use case that might require you to generate your own responses programmatically. [project site]

Dave Thomas created a Fable bindings project called fable-fetch-import. This npm package allows us to use Fetch in JavaScript apps from F#.

Data access

Retrieving data from the web with Fetch is really easy. In the following snippet we just pull a bit of JSON from a HTTP resource and cast it to a custom type.

As you can see all JavaScript Promises are already mapped into F#’s async type which makes it really easy to use.

HTTP Post

If you want to post data to a HTTP resource you can do this like in the following sample:

Going further

If you need to do more complicated calls then take a look into the Fetch docs. Many of the properties and functions are already available in the Fable bindings. If not please create an issue at the Fable issue tracker and I will try to add it.

Saturday, 6. August 2016


Fable |> React Native – Native apps with F#

Filed under: .NET,F#,Informatik — Steffen Forkmann at 15:04 Uhr

TL;DR available at the bottom of the post.

“A React Native App is a Real Mobile App”

With React Native, you don’t build a “mobile web app”, an “HTML5 app”, or a “hybrid app”. You build a real mobile app that’s indistinguishable from an app built using Objective-C or Java. React Native uses the same fundamental UI building blocks as regular iOS and Android apps. You just put those building blocks together using JavaScript and React. [project site]

That doesn’t sound too bad, but why do we have to do it in JavaScript?

Well, this article shows that we don’t have to.

The nightwatch app

Consider you are working for some kind of Nightwatch and it’s getting dark and your watch is about to begin.

The nice people of your order gave you a phone and a new app. At the beginning of the night it downloads a list with locations that you have to check. Every location can be marked as OK or you can blow a virtual horn to trigger an alarm. The app also allows you to append an photo of the situation on the ground.

Since many of the locations that you will visit are far away from good internet connection the app stores everything locally on your phone. Once in a while it will sync with the nightwatch central.

So this could look a bit like this:

Nightwatch app

So now after embaressing myself and showing my design skills, let’s jump into the technical stuff.

Developing with F# in VS Code

The app was developed with F# in Visual Studio Code (with ionide and react native plugins). This development environment runs on all platforms, so you can use Windows, Linux or your Mac.

Hotloading F# code

As you can see we have a React Native app with automatic loading of compiled F# code.

The big difference to using JavaScript is that everything is statically typed – even the access to the JavaScript APIs. This gives you nice autocomplete features and depending on the concrete bindings you can even get documentation in the editor:

Autcomplete in F# code

Krzysztof Cieślak did really amazing work with the Ionide – this tooling works pretty well. Take a look at his blog to find out more about the awesomeness that he brings to the ecosystem. He also played an important part in getting React Native to work with F#.

Introducing Fable

Fable is the most important technology behind all of this. It was designed by Alfonso Garcia-Caro as a F# to JavaScript compiler and can do real magic in the browser. Take the time and watch the 10min intro. I can’t stress enough how well this open source project is managed. It’s a real pleasure to be part of it now.

In our case it bridges React Native APIs into F# and also compiles the F# code back to JavaScript whenever we save a file. The React Native framework is listening for the changes in the JavaScript files and swaps the code in the device simulator. There is a lot going on behind the scenes, but it’s already working surprisingly well.

Using JavaScript APIs

Since most of the React Native APIs are developed in JavaScript it’s important to bring these APIs over to F#. This is done as a community effort and the Fable project creates typed JavaScript bindings for many major JavaScript frameworks. This effort is comparable to DefinitelyTyped in the TypeScript world. There is even a tool that can help to convert TypeScript bindings to Fable bindings.

In our case the fable-import-react-native is the most important package. It provides typed bindings to most of the React Native APIs.

This snippet creates a View component in React Native and puts two buttons inside it.

Using F#

One nice benefit of this model is that we can use ordinary, statically typed F# code for our app. In the demo project you can find a small F# domain model:

If you are interested in learning the language then I recommend to look at website of the F# software foundation. For domain driven design in F# you can find excellent articles on a site called “F# for fun and profit“.

Access to native components

React Native allows you to access native phone components like the camera. Most of these APIs are written in a mix of Java/ObjectiveC and JavaScript. Given the Fable bindings are already present it’s super easy to access the same APIs from F#. In the following sample we access a nice ImagePicker via the fable-import-react-native-image-picker bindings:

This ImagePicker is distributed via a separate npm package, but it’s API feels like the rest of the React Native functions. We can provide some properties and a callback – and everything is statically typed so that we have autocompletion in VS Code.

Data storage

For most apps you want to have some local storage in order to cache information. React Native provides a basic abstraction called AsyncStorage that works on Android and iOS. With the help of a package called fable-react-native-simple-store we can use it from F#:

As you can see all function in this storage model are asynchronous and with the help of the async computation expressions they become really easy to use in F#.

Web access

Another advantage of React Native is the huge ecosystem you see on npm. In our app we want to retrieve a list with locations that we need to check. This list is just a bit of JSON on a http resource. With the help of a very popular JavaScript package called fetch and the corresponding fetch-bindings (written by Dave Thomas) we can write something like this:

So we see the same async model here and everything fits nicely together.

Project status

The project with the working title “Fable |> React Native” is currently considered “highly experimental”. APIs and JavaScript bindings are not complete and likely to break multiple times.

In general the Fable project is shaping things up for a v1.0 release. So sharing experiences, comments and bug reports with the Fable compiler and APIs is appreciated.

Debugging of the react native apps is currently only working in the generated JavaScript. With the next release of the VS Code react native extension we will probably be able to set breakpoints directly in the F# source.

That said, it already feels very very productive and if you are interested in this kind of mobile development then check out the sample project and follow how it develops over time. There is even a similar approach that allows you to use F# on fuse, so I think we will probably see a lot of choice in the future.

TL;DR for F# devs

With this model you can start to develop Android and iOS apps on the react native model while still keeping most of the type safety and tooling. Using fable gives you access to a huge ecosystem with JavaScript libraries and frameworks. Check out the sample project and follow the instructions in the Readme.

TL;DR for JavaScript devs

If you like creating apps with the React Native model, but it always felt a bit hard to maintain JavaScript, then this might be interesting for you. With this approach you can apply all your knowledge and use it from a excellent type safe language with amazing autocompleting tooling.

With one or two tricks you can even reuse many of the npm libraries that you know and love. Check out the sample project and follow the instructions in the Readme.

TL;DR for TypeScript devs

You have already left the path of plain JavaScript. Maybe you are ready to leave it a bit further and to investigate different languages like Elm or PureScript. If this is you then check out the sample project and follow the instructions in the Readme. It shows you how a language like F# can help you to work with JavaScript APIs.

TL;DR for C# devs

Sorry, nothing to see here.

Tags: , , ,

Monday, 25. April 2016


“Make failure great again” – a small journey into the F# compiler

Filed under: Diverses,F#,Informatik — Steffen Forkmann at 13:44 Uhr

Giving good error messages is very important for modern compilers. The language Elm is famous for giving excellent user-friendly error messages. Parts of the F# community decided to improve the F# compiler messages as well. We want to make that a community effort and hope many people join us and help to make the compiler emit better error messages.  Isaac Abraham is mainatining a list with possible targets, so if you are interested in helping then take a look at this list.

Unfortunately working on compilers it’s not exactly the easiest task. In this post I want to show you how I tried to improve one compiler warning and hope this helps others to get started.

The task for this post is to improve the compiler warning for the following code:

Currently the compiler shows the following:

Original compiler warning

According to issue #1109 we want to turn it into:

New descriptive compiler warning

As you can see the new message is giving the user more details about the specific situation and also refers to a common error of newcomers.

Please notice that this is probably not the final wording for this warning, but once we have finished this it will be easy to iterate on the concrete warning.

Getting started

The first thing to is to get the compiler code on your machine. I’m using Windows and Visual Studio 2015 here. So what you want to do is the following:

  • Fork https://github.com/Microsoft/visualfsharp on github
  • Start a “Developer command prompt for Visual Studio 2015” in admin mode
  • Run `git clone [your clone url]` and change into the new directory
  • Run `git remote add upstream https://github.com/Microsoft/visualfsharp.git`
  • Optionally: If you want to follow the exact steps from this post, then it makes sense to set your clone to the same commit where I started. You can do that by executing “git reset –hard 8a2e393999f440ea93769a288c37172d98db455a”
  • Run `build.cmd`

This last step will download the internet for you, so don’t be too surprised when you find the lastest “Game of Thrones” episode somewhere inside your packages folder.

Anyways, if everything works then the output should look like the following:

Build works from command line

If the build doesn’t work for you then read the DEVGUIDE very very carefully. If that doesn’t help then please open an issue in the Visual F# issue tracker.

Reproducing the compiler warning

If the build works from command line we should try to reproduce the error with our own freshly built compiler. Let’s open the solution in Visual Studio 2015, set the startup project to “FsiAnyCPU” and hit F5 to start a debug session in Visual Studio. If everything works we will see a F# Interactive Window and Visual Studio is in Debug mode:

Debug works in Visual Studio

Now we paste our code into the command line window:

Original compiler warning

Using the F# Interactive in debug mode is an easy way to do compiler debugging. There are other possibilities (like using fsc.exe), but the F# Interactive allows you to debug the compilation of single lines in isolation from the code above. It’s really neat.

Where to start with hacking

Since we now know how to reproduce the compiler warning, we want to make actual code changes. But where!?

Where??

An easy way to get started is by using the old error message as a search string. When we use Visual Studio’s solution-wide search and look for “This expression should have type” we find exactly two locations inside a file called FSStrings.resx file.

Searching for original compiler warning

So this gives us a new search string “UnitTypeExpected1”.

Searching for UnitTypeExpected1

This looks actually like we found something interesting in CompileOps.fs. Let set a breakpoint and see if it stops when we reproduce our warning:

Debugging

Cool, so this seems to be the place where the warning gets emitted. Now we need to find the place where the discriminated union case “UnitTypeExpected” is created. After another little search we are in TypeChecker.fs:

Type checker

We can try to set another breakpoint and see what happens in that code. The interesting part is the inner else part.

Baby

The code in there looks scary and cryptic at first, but it actually shows the power of using a ML dialect for building compilers. Inside this code the compiler already knows that we want to emit a warning. By pattern matching on the abstract syntax tree (AST) we decide if the left side of the expression is a property. In that case the compiler seem to emit a different warning (see also that code above from CompileOps.fs).

So after hitting the breakpoint and looking in the value of exprOpt I’m pretty sure we are in the right place:

Inspect AST

So somewhere inside that AST we can actually find our name x. Now we have all we need.

Making the code changes

It’s good practice to never make code changes on the master branch. So let’s create a feature branch with “git checkout -b assignment-warning”.

Now let’s start by adding our new compiler warning to FSStrings.resx:

Now we go back to TypeChecker.fs and try to come up with some pattern matching on the AST that finds our special case. After playing around a bit I found:

This doesn’t look super nice, but it follows one of the important rules from the contributor guide – “use similar style to nearby existing code”. We probably want to tidy this up later when initial code review is done. But in the beginning we should stay as close to the original as possible.

Since we decided to store additional data, this already tells us we need to extent the UnitTypeExpected type in TypeChecker.fsi and TypeChecker.fs. After that we can go to CompileOps.fs and use that data:

That’s basically all we need to do. Let’s fix the the remaining errors (don’t worry the compiler will show you all the places) and then reproduce the warning again:

New descriptive compiler warning

Wow. We did it. We actually changed the compiler. And it didn’t even hurt that much.

Compiler changed

Unit tests

Compiler tests (especially if you want to tests negative results like warnings or exceptions) can’t be easily done in standard unit tests. The F# team came up with a different approach where the test runner compiles a .fs file and you can use regular expressions to match against the compiler output.

In order to run the existing test suite call “build.cmd all”.

Are you afraid?

This will take a while, but after all tests are done we should see:

Test results

So good news is we didn’t break anything, but the bad news is that we don’t have tests covering our case. So let’s add one.

We create tests/fsharpqa/Source/Warnings/WarnIfPossibleAssignment.fs:

Now we need to include the test in a test suite. Since there isn’t a good fitting existing suite we need to create tests/fsharpqa/Source/Warnings/env.lst:

And we need to register this new suite in /tests/fsharpqa/Source/test.lst:

Now we can run the test with “src\RunTests.cmd release fsharpqa Misc01” (more details can be found in the TESTGUIDE):

Test failed

So at least we now know that our test gets executed 😉
The concrete test results can be found in a file called 258,259FSharpQA_Failures.log alongside our WarnIfPossibleAssignment.fs:

So it seems we cannot match the same line twice. For simplicitly of this blog post we will go with a reduced test:

Wrapping it up

After we ran “build.cmd all” again it’s now time for the final phase. Commit the changes locally and use “git push origin assignment-warning” to publish your code.
Now go to the Visual F# GitHub repo and create a pull request with an explanation of what you did and what you intended to fix. Often it’s also useful to include one or two screenshots.

Your PR will then go through code review process. Usually you will get a lot of questions and probably you need to change some things in your proposal. This process can take a while so bring a bit of patience.

Anyways, here is my PR for this change – wish me

Good luck!

Thursday, 31. March 2016


Introducing Paket’s caching feature – or how I fixed our broken builds

Filed under: .NET — Steffen Forkmann at 9:55 Uhr
The problem

Last week most of us heard that latest npm drama where “one developer broke Node, Babel and thousands of projects in 11 lines of JavaScript“. The reason for this huge impact was that all of these projects (even infrastructure critical projects like Node) relied on the fact that packages are available on npm until the end of time. But users are allowed to delete packages permanently. Oups!

In .NET/mono land things are slightly better. Users can’t delete packages from nuget.org, they are only allowed to “unlist”. Unlisted packages won’t be suggested for new installations, but are still available on the server so that builds won’t break. In most cases this is a good thing for users, but even on nuget.org packages can be removed permanently and this already affected some projects.

If you are using TeamCity as CI server and also as NuGet feed then things are looking bad as well. TeamCity’s cleanup task removes all artifacts from your projects – including NuGet packages. So if you forget to pin a build that generated an important NuGet package then TeamCity’s cleanup will eventually delete that package. This hit us a couple of times now and ironically also right now. 🙁

Paket caches to the rescue

For Paket v3 (currently in alpha) we implemented a solution for this problem. With this version we can configure additional caches which will automatically be used to store all external dependencies in a safe and controlled location.

This feature would have protected us, but in our case the damage was already done. The package was already “cleaned” from the TeamCity NuGet feed and most of our builds broke. So in order to fix this we did the following:

Et voilà: all builds on all TeamCity agents and developer machines became green again.

Did OK

https://frpiluleenligne.com

Monday, 21. March 2016


Property based testing in the real world – or how I made my package manager suck less

Filed under: C#,F#,Informatik — Steffen Forkmann at 16:57 Uhr

A couple of days ago I tried to fix a bug in the .NET/mono dependency manager “Paket“. The bug was a really strange edge case in Paket’s resolver algorithm that resulted in a false positive conflict (an overview about the algorithm can be found here).

In other words: Paket reported a version conflict where it should have reported a valid package resolution.

After some investigation I found that the bug was in some optimization code that tries to cut parts of the search tree. When I disabled that part, the resolver found a valid resolution, but was significantly slower. So after some further testing I came up with a fix that was fast and solved the issue.

But why didn’t we find that edge case before? And most importantly: do we have other bugs in the resolver?

Isaac Abraham suggested to investigate the resolver optimizations further and proposed to use property based testing for this (see Scott Wlaschin’s blog for amazing introduction material).

Problem formulation

In this post I want to evaluate if Paket’s package resolver works correct. Let’s start by clarifying some terms.

  • A “package” consists of a name, a version and a (possibly empty) list of dependencies. In this post we are only talking about meta data. The package contents are irrelevant.
  • A “dependency” is always referencing another package name and defines a version requirement (e.g. >= 2.0 or < 4.1).
  • The “package graph” is a list of packages and acts as a stub for a possible configuration of a package feed like nuget.org. It’s basically a collection of the meta data of all published packages.
  • A “resolver puzzle” consists of a package graph and a list of dependencies. In other words it defines a possible configuration of the package feed and a specific list of package requirements (basically what you would define in paket.dependencies).
  • A “resolution” is a list of packages that “solves” the resolver puzzle. This means all package requirements are satisfied and we don’t have more than one package for a every package name.

Our goal is to show that Paket’s resolver is returning a version conflict if and only if we can not find a package resolution via a brute-force algorithm. We do not compare resolutions, we just want to know if the optimization is missing some valid resolutions.

Generating test data

Property based testing is a stochastical test approach. The test framework (in this case we use FsCheck) generates lots of test cases with random data and tries to automatically falsify a given assumption about the algorithm. 

Usually FsCheck will just generate random, uniformly distributed data for whatever data type it sees. This is a very good default, but in our case this would result in 99% package graphs that have no resolution.

In order to create more sensible data and increasing the likelihood of finding real bugs we need to write our own generator functions.

Let’s consider a very small example and think about package names. If we would use the standard FsCheck data generator then it would generate completely random names including empty string, null and names that contain very special characters. While this is great for testing the validation part of Paket, we don’t really need this here. We just generate some valid package names:

As you can see we just generate non-negative integers and create the package name by prefix a “P”. Similarly we can create random but valid version numbers like that:

Here we just map a triplet of non-negative integers to a version of form major.minor.patch.

Now it’s easy to generate a list of packages with corresponding versions. Actually FsCheck can automatically generate a list of PackageName and Version pairs, but since it’s completely random it would generate a list where most packages have only one or two versions. The following custom generator creates a list of different versions for every package and flattens the result. This has a much bigger chance of creating interesting cases:

With a small helper function that creates random version requirements we can create a full package graph:

The last step is to create some package requirements to that graph that we want to resolve. This is basically what you would write into your paket.dependencies file.

Testing against brute-force algorithm

The following defines a FsCheck property that calls Paket’s resolver with a random puzzle. If the resolver finds a resolution, then we verify that this resolution is correct. If it can’t find a resolution we use a brute-force algorithm to verify that the puzzle indeed has no valid resolution:

This is testing the real resolver against a very naïve brute-force implementation. The brute-force version was relatively easy to write and has no smart optimizations:

And this point I reverted the fix in the optimization code and started the test to see what happens. FsCheck needed about 3s to come up with a random example where a valid resolution exists but Paket’s resolver didn’t find it. That was an amazing moment. Unfortunately the example was HUGE and very complicated to understand.

Shrinking

Most property based testing frameworks have a second important feature called “shrinkers”. While generators create random test data, shrinkers are used to simplify counter-examples and have type ‘a -> seq<‘a>. Given a value (our counter-example), it produces a sequence of new examples that are “smaller” than the given value. These new values are tested if they still falsify the given property. If they do a new shrinking process will be started that tries to reduce the new example even further.

There are two easy ways to create a new “smaller” graph. The first optios is to select a package from the graph and remove one of it’s dependencies and second option is to remove a package completely. The following code shows this:

In a similar way we can shrink a puzzle:

After running the test again FsCheck reported:

The ouput shows that FsCheck generated a random puzzle with 104 packages and reduced it to a sample with only 3 packages and 2 package requirements. This made it pretty easy to analyze what was going on in the optimization part of the resolver. The sample was even smaller than the one that was reported from the wild.

With the fix reapplied I rerun the tests and FsCheck reported another error:

So now FsCheck discovered a new, previously unknown bug in Paket’s resolver. The sample shows 2 packages and one of the packages is requiring a non-existing package.
This is trivial case and the brute-force algorihm is instantly finding a solution. So what is wrong in Paket’s resolver?
Again the answer is hidden in some performance optimization and the fix can be found here.

But this was not the end – the property based test spotted yet another counter-example so I fixed that as well.

Conclusion

It took me a while to build up property based testing for this complex scenario. Most of the time was needed to build custom generators and shrinkers, but I was able to reproduce a bug from the wild and also found two new bugs. I think this is a big success.