• Dafny coding guidelines follow C#, not Rust. So, we name the function SlowAdd not slow_add (although either will run).
• Dafny supports subtypes. For instance, any int that could be shown to be non-negative can be a nat.
• Project is := and equality is == . (There isn’t any = .)
• Function parameters, for instance, x and y above, are immutable.
• Dafny uses ensures and invariant statements to confirm the code at compile-type. It then removes these statements to complete compiling.
• The green check mark shows that this code verifies. Dafny’s VS Code extension will, by default, constantly attempt to validate each method. This adds an almost gambling-like excitement to working with Dafny. In the instance above, if I make y an int quite than a nat, then validation should and can fail. (Are you able to work out why?) Dafny will mark my function with a red X and tell me “This postcondition won't hold: r == x + y”.
• Dafny knows a number of the mathematics of integers, arrays, sets, maps, sequences, etc. This often allows it to complete the last details of validation by itself.

Now that you realize about Dafny, it is best to let it find out about your algorithm.

The range-set-blaze crate represents sets of integers as sorted, disjoint ranges. For instance, this list of three ranges:

100..=2_393,
20_303..=30_239_000,
501_000_013..=501_000_016

represents a set of 30,220,996 integers.

In Rust, the RangeSetBlaze struct represents this data structure internally with a regular BTreeMap. Recall that a BTreeMap represents an inventory of key/value pairs, sorted by key. Here, our keys are the ranges’ starts (for instance, 100, 20_303, 501_000_013) and the values are the ranges’ inclusive ends (for instance, 2_393, 30_239_000, 501_000_016. RangeSetBlaze stores the list with a BTreeMap quite than a vec to make key look up more cache friendly.

RangeSetBlaze will depend on BTreeMap, so must we implement BTreeMap in Dafny? Happily, no. We will, as a substitute, use Dafny’s vec-like seq data type. This substitution works because BTreeMap, vec, and seq can all represent sorted lists — just with different efficiencies. For the aim of formal verification, we only care about correctness and might ignore efficiency.

RangeSetBlaze requires the list of ranges be sorted and disjoint. How do we are saying “sorted and disjoint” in Dafny? We will say it via this ghost predicate (and related code):

ghost predicate ValidSeq(sequence: seq) sequence
type IntRange = (int, int)
type NeIntRange = x: IntRange | !IsEmpty(x) witness (0,0)
function IsEmpty(r: IntRange): bool
{
r.0 > r.1
}

A predicate is one other name for a technique that returns bool. A ghost method (or predicate) is one which can only be used for validation, not for running the ultimate code.

At a high level, the ValidSeq predicate takes as input a sequence of non-empty integer ranges. It then tests that the beginning values are sorted and that the ranges don’t touch. Specifically,

• An IntRange is a tuple of two int values.
• An IntRange IsEmpty exactly when its start is larger than its end. (This follows Rust’s convention.)
• A NeIntRange (non-empty integer range) is an IntRange that will not be empty, for instance, (0,0). [All our ranges are end inclusive.]
• This expression tests that the beginning values are sorted:

forall i:nat, j:nat | i < j < |sequence| :: sequence[i].0 < sequence[j].0

It might probably be read as “for all natural numbers i and j — such that i is lower than j and j is lower than the length of the sequence — test that the beginning value at index i is lower than the beginning value as index j”.

Aside: Note that a Rust BTreeMap doesn’t support (random-access) indexing but here we’re using such indexing. That is OK because ValidSeq is a ghost predicate and so will only be used for validation.

• This expression tests that the ranges are disjoint:

forall i:nat, j:nat | i < j < |sequence| :: !Touch(sequence[i], sequence[j])

It might probably be read as “for all natural numbers i and j — such that i is lower than j and j is lower than the length of the sequence — test that the range at index i doesn’t touch the range at index j. But what’s Touch?

We’ll define Touch on two-levels. On a mathematical level, a spread i is alleged to the touch a spread j if there exists an integer i0 in range i and an integer j0 in range j such that i0 and j0 are inside a distance of one among one another. On an efficient programming level, we wish to avoid definitions depending on “there exists”. Here’s a Dafny predicate that’s each mathematical and efficient:

predicate Touch(i: NeIntRange, j: NeIntRange)
ensures Touch(i, j) == exists i0, j0 ::
Incorporates(i, i0) && Incorporates(j, j0) && -1 <= i0 - j0 <= 1
{
assert Incorporates(i, i.0) && Incorporates(i, i.1) && Incorporates(j, j.0) && Incorporates(j, j.1);
if i.1 < j.0 then
assert  (-1 <= i.1 - j.0 <= 1) == (i.1+1 == j.0);
i.1+1 == j.0
else if j.1 < i.0 then
assert (-1 <= j.1 - i.0 <= 1) == (j.1+1 == i.0);
j.1+1 == i.0
else
var k0 := Max(i.0, j.0);
assert Incorporates(i, k0) && Incorporates(j, k0);
true
}
function Incorporates(r: IntRange, i: int): bool
{
r.0 <= i && i <= r.1
}
function Max(a: int, b: int): int
{
if a < b then b else a
}

Some points of interest:

• Touch will not be a ghost. In other words, we are able to use it in each regular code and validation code.
• The assert statements help Dafny prove that the regular code meets the mathematical ensures statement.
• For efficiency, the Dafny prover validates the inside a method individually from its outside. Only the ensures (and the yet-to-be-seen, requires) statements cross this border. In contrast to a method, a Dafny function is transparent to the validator. (I believe of it as inlining code with respect to validation.)

With concepts reminiscent of ValidSeq and Touch defined, we next move onto specifying what our algorithm is purported to do.

Ultimately, I would like to prove that my specific Rust algorithm for inserting a latest range right into a RangeSetBlaze is correct. Before we do this, nevertheless, let’s define what “correct” range insertion is.

method InternalAdd(xs: seq, a: IntRange) returns (rs: seq)
requires ValidSeq(xs)
ensures ValidSeq(rs)
ensures SeqToSet(rs) == SeqToSet(xs) + RangeToSet(a)
{
if IsEmpty(a)
{
rs := xs;
}
else
{
assume false; // cheat for now
}
}

This says that InternalAdd is a technique that takes xs, a sequence of non-empty integer ranges, and a, an integer range (that might be empty). The strategy outputs rs, a latest sequence of non-empty integer ranges.

We want to say that xs and rs should be sorted and disjoint. That is definitely done with the ValidSeq’s within the requires and first ensures.

We also have to say that rs incorporates the correct stuff. Is this difficult? It will not be. We just say that the set of integers in rs must equal the set of integers in xs unioned with the integers in a.

Aside: In Dafny, “+” when applied to sets is “union”.

The set of integers in a spread is:

ghost function RangeToSet(pair: IntRange): set
{
set i {:autotriggers false} | pair.0 <= i <= pair.1 :: i
}

And the set of integers in a sequence of non-empty ranges could be define inductively (that’s, recursively):

ghost function SeqToSet(sequence: seq): set
decreases |sequence|
requires ValidSeq(sequence)
{
if |sequence| == 0 then {}
else if |sequence| == 1 then RangeToSet(sequence[0])
else RangeToSet(sequence[0]) + SeqToSet(sequence[1..])
}

Some points of interest:

• The road: assume false; // cheat for now makes validation work even when it really shouldn’t. We use it as a short lived placeholder.
• We make RangeToSet and SeqToSet ghosts to stop us from using them in regular code. We make them functions (as a substitute of methods) to inline them with respect to validation.
• Because Dafny knows rather a lot about creating and manipulating sets and sequences, we regularly profit by utilizing sets and sequences in our specification.
• Even when our regular code uses loops as a substitute of recursion, our validation code will often use recursive-like induction.
• The {:autotriggers false} pertains to avoiding a warning message. For more information see this Stack Overflow answer by Prof. James Wilcox.

We now have a proper specification of InternalAdd. I find this specification short and intuitive. But what in case you need assistance determining a specification or other Dafny code?

The important forum for Dafny questions is Stack Overflow. To my surprise, I actually received much useful help there.

I like to recommend starting your query’s title with “Dafny:”. Also, remember to tag your query with dafny and, perhaps, formal-verification.

Aside: On the positioning, you possibly can see my 11 questions and Divyanshu Ranjan’s 48 Dafny-related answers.

As an open-source project on GitHub, Dafny also hosts GitHub Discussions and Issues.

The Dafny community is small but seems obsessed with helping users and improving the project.

With help at hand, we must next find an algorithm that meets the specification.

As a novice to formal verification, I made a decision to postpone work on the true internal_add utilized in my Rust code. As an alternative, I began work on an InternalAdd algorithm that I hoped can be easier to validate. I ended up with this:

method InternalAdd(xs: seq, a: IntRange) returns (rs: seq)
requires ValidSeq(xs)
ensures ValidSeq(rs)
ensures SeqToSet(rs) == SeqToSet(xs) + RangeToSet(a)
{
if IsEmpty(a)
{
rs := xs;
}
else
{
var notTouching, merged := PartitionAndMerge(xs, a);
var indexAfter := NoTouchIndexAfter(notTouching, merged);
rs := InsertAt(notTouching, [merged], indexAfter);
}
}

The concept is that if range a is empty, we return the input sequence unchanged. Otherwise, we divide the work into three steps, which we are able to validate independently. Step one, PartitionAndMerge, returns:

• notTouching, a sequence of ranges that don’t touch range a, and
• merged, a single range created from a and every little thing it touches.

Here is an example input and output:

InternalAdd next finds where to insert merged and, finally, inserts it.

Here is the code for PartitionAndMerge:

method PartitionAndMerge(xs: seq, a: NeIntRange) returns (notTouching: seq, merged: NeIntRange)
requires ValidSeq(xs)
ensures ValidSeq(notTouching)
ensures RangeToSet(merged) >= RangeToSet(a)
ensures forall range | range in notTouching :: !Touch(range, merged)
ensures SeqToSet(xs) + RangeToSet(a) == SeqToSet(notTouching) + RangeToSet(merged)
{
// Split into touching and never touching seqs
var touching: seq;
touching, notTouching := Partition(a, xs);
// Merge the touching seq into one range with our original range
merged := UnionSeq(a, touching);
}

This says that PartitionAndMerge requires that xs be a sound sequence of non-empty integer ranges and that a be a non-empty integer range. It ensures that nonTouching is one other valid sequence of non-empty integer ranges. It ensures that the integers in range merged are a superset of those in range a. It ensures that no range in notTouching touches range merged. And eventually, it ensures that the integers in xs and a are the exact same because the integers in notTouching and merged.

PartitionAndMerge also divides the work, this time into two steps (Partition and UnionSeq) that could be validated independently. Those steps proceed to subdivide their work. Where does it end? Let’s have a look at one example.

The strategy UnionSeq calls UnionRange which merges two ranges:

function UnionRange(x: IntRange, y: IntRange): IntRange
requires IsEmpty(x) || IsEmpty(y) || Touch(x, y)
ensures RangeToSet(x) + RangeToSet(y) == RangeToSet(UnionRange(x,y))
{
if IsEmpty(x) then y
else if IsEmpty(y) then x
else (Min(x.0, y.0), Max(x.1, y.1))
}

The UnionRange code handles the empty cases after which returns the minimum bounding range. (The minimum bounding range is the range from the smaller of the 2 starts to the larger of the 2 ends.) But how can this be correct? Normally, a minimum bounding range of two ranges might include extra integers. We’d get something greater than the union of the inputs, like so:

The code is correct since it requires that the 2 input ranges touch or are empty. This ensures that the union of the integers in range x with the integers in range y are precisely the integers within the output range.

At compile time, Dafny proves this function correct. Beyond that, it proves that every little thing that calls this function provides inputs which might be empty or touching.

I believe of this as a generalization of Rust’s borrow checker. At compile-time Rust checks that we’re secure from many memory errors. At compile time, verification systems, reminiscent of Dafny, can prove almost arbitrary properties. In fact, as we’re seeing, this ability comes at the associated fee of complexity.

The total code for this verified algorithm is about 200 lines, organized into a couple of dozen methods and functions.

This rule shows that we are able to confirm an algorithm for InternalAdd, however it will not be the algorithm I utilized in Rust. We are going to turn to that next.