• 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 also be a nat.
• Task is := and equality is == . (There isn’t a = .)
• 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, repeatedly 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 reasonably 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 few 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’s 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 a listing 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 reasonably than a vec to make key look up more cache friendly.

RangeSetBlaze depends upon BTreeMap, so must we implement BTreeMap in Dafny? Happily, no. We are able to, 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 are able to 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 bigger than its end. (This follows Rust’s convention.)
• A NeIntRange (non-empty integer range) is an IntRange that isn’t 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 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 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 variety i is claimed to the touch a variety 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 in every of 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 isn’t 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 resembling ValidSeq and Touch defined, we next move onto specifying what our algorithm is speculated to do.

Ultimately, I would like to prove that my specific Rust algorithm for inserting a brand new range right into a RangeSetBlaze is correct. Before we do this, nonetheless, 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 may very well be empty). The tactic outputs rs, a brand new sequence of non-empty integer ranges.

We’d like to say that xs and rs have to be sorted and disjoint. That is well 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 isn’t. 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 variety 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 so much about creating and manipulating sets and sequences, we regularly profit through the use of 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 should you need assistance determining a specification or other Dafny code?

The primary 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, make sure you tag your query with dafny and, perhaps, formal-verification.

Aside: On the location, you’ll be able to 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 keen about 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 actual internal_add utilized in my Rust code. As a substitute, I began work on an InternalAdd algorithm that I hoped could 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 thought 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 legitimate 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 at last, 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 take a look at one example.

The tactic 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? Generally, a minimum bounding range of two ranges might include extra integers. We would 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 are 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, resembling Dafny, can prove almost arbitrary properties. After all, 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, but it surely isn’t the algorithm I utilized in Rust. We’ll turn to that next.