Proving My Compiler Code Incorrect With Alloy

Disclaimer: although “my compiler code” makes for a enjoyable title, I don’t
declare unique credit score for any of the C++ code within the Chapel compiler that
I point out on this publish. The code is “mine” within the sense that I used to be
debugging adjustments I used to be making, and maybe additionally within the sense that I used to be
working with it.

I work as a compiler developer on the Chapel crew.
Not too long ago, whereas considering via a change to some code, I caught myself
making needs: “if solely I might have a pc verify this property for
me”. Having sooner or later seen Hillel Wayne’s post
in regards to the launch of Alloy 6, I believed I’d give it
a go. On this publish, I describe my expertise making use of Alloy to an actual a part of
the Chapel compiler. I’d by no means touched Alloy earlier than this, so be warned: this
is what I got here up with by myself try, and I could be doing one thing
pretty foolish by the requirements of “actual” Alloy customers.

The Drawback at Hand

One of many issues {that a} language like Chapel has to do is known as decision,
which is the method of determining what every identifier, like x, refers to,
and what its sort is. Even the primary a part of that’s fairly difficult, what
with private and non-private variables, strategies (which will be declared exterior
of their receiver sort in Chapel), and extra…

Scope decision in Chapel is additional difficult by the truth that the identical
scope would possibly should be searched a number of occasions, in numerous contexts. Let
me begin with just a few examples for example what I imply. Right here’s the primary
program:

module M {
    class C {}

    // A daily process (not a way)
    proc foo() {}

    // A technique on C.
    proc C.foo() {}

    // One other technique on C.
    proc C.doSomething() {
        foo();
    }
}

In the event you don’t know Chapel (and also you most likely don’t!) this program already deserves a good
little bit of rationalization. I’ve collapsed it for the sake of visible readability; really feel
free to develop the beneath part to study extra in regards to the language options
utilized in this system above.

The attention-grabbing a part of the snippet is the physique of the doSomething technique.
It has a name to foo: however which foo is it referring to? There are two:
the common process (non-method) foo, declared on line 5, and the
technique C.foo declared on line 8. In Chapel, the foundations dictate that when
such a state of affairs arises, and a becoming technique is discovered, the strategy is
most well-liked to the non-method. Within the rewritten model of the Chapel compiler,
titled Dyno, this disambiguation is achieved by first looking the scopes
seen from the category C for strategies solely. On this specific instance,
the 2 scopes searched can be:

1. The within of sophistication C. The category itself doesn’t outline any strategies, so
   nothing is discovered.
2. The module during which C is outlined (M on this case). This module does
   have a way, the one on line 8, in order that one is returned.

Provided that strategies aren’t discovered are non-methods thought of. On this state of affairs,
the search order can be as follows:

1. The within of C.doSomething can be searched. doSomething doesn’t declare
   something, so the search will come up empty.
2. The module during which C.doSomething is outlined (M once more) can be searched. This time,
   each strategies and non-methods can be thought of. Since we’re contemplating
   a hypothetical state of affairs during which the strategy C.foo isn’t there (in any other case
   it could’ve been discovered earlier), the one factor that can be discovered will
   be the non-method foo.

Discover that we’ve already needed to search the module M twice, searching for
various things every time. First, we had been searching for solely strategies, however
later, we had been searching for something. Nonetheless, this isn’t as difficult as
issues can get. The simplifying facet of this program is that each doSomething
and C are outlined contained in the module M, and due to this fact have entry to its
non-public strategies and procedures. If we extracted C.doSomething into its
personal separate module, this system would appear like this.

module M1 {
    class C {}

    // A daily process (not a way)
    proc foo() {}

    // A technique on C.
    proc C.foo() {}
}
module M2 {
    use tremendous.M1;

    // One other technique on C.
    proc C.doSomething() {
        foo();
    }
}

Since doSomething is now in one other module, it may well’t simply entry the foos from
M1 willy-nilly. There are just a few methods to get the issues that had been declared in one other module out
and make use of them. I opted for a use assertion, which, in its easiest kind,
simply brings all of the declarations contained in the used module into the present scope. Thus,
the use assertion on line 11 would carry all issues declared in M1 into
the scope inside M2. There’s a catch, although. Since M2 shouldn’t be declared
inside M1, a use assertion will be unable to herald non-public symbols
from M1 (they’re non-public for a cause!). So, this time, when looking the scope
for M1, we should search just for public symbols. That’s one other,
completely different approach of looking M1. Thus far, we’ve seen three:

• Search M1 for any image.
• Search M1 for strategies solely.
• Search M1 for public symbols solely.

Dyno introduces extra methods to look inside a scope, together with combos of
search sorts, similar to trying just for public strategies. To signify the varied
search configurations, the Dyno crew got here up with utilizing a bitfield of flags,
every of which indicated a vital situation for a logo to be returned. A
bitfield with flags set for 2 properties (like “public” and “technique”) requires
that each such properties be discovered on every image that’s returned from a scope.
This led to C++ code alongside the strains of:

auto allPublicSymbols = Flags::PUBLIC;
auto allPublicMethods = Flags::PUBLIC | Flags::METHOD;

It additionally turned out handy so as to add damaging variations of every flag
(NOT_PUBLIC for personal symbols, NOT_METHOD for normal outdated procedures
and different definitions, and so forth. So, another doable flag combos
embody:

auto allNonMethods = Flags::NOT_METHOD;
auto privateMethods = Flags::NOT_PUBLIC | Flags::METHOD;

Given these flags, there are some conditions during which checking a scope a
second time is redundant, in that it’s assured to seek out no extra
symbols. For example, if you happen to search a scope for all public symbols, and
then subsequently seek for all public strategies, you’ll solely discover
duplicates – in spite of everything, all public strategies are public symbols. Most
typically, this happens when a second search has all of the flags from a
earlier search, and perhaps extra. In math lingo, if the set of flags checked
the primary time is a subset of the set of flags checked the second time,
it’s assured to not discover something new.

In Dyno, we wish to keep away from extra work once we can. To take action, we observe
which scopes have already been searched, and keep away from looking them once more.
Since what comes up from a search is dependent upon the flags, we retailer the flags
alongside the scopes we’ve checked. If we discover that the previously-checked
bitfield is a subset of the present bitset, we simply skip the search.

However then, what if it isn’t a subset? One other concern right here is avoiding
duplicate outcomes (it’s simpler to verify for duplicate definitions if you happen to
know a logo is barely returned from a search as soon as). So, one other characteristic of
Dyno’s scope search is a further bitfield of what to exclude, which we
set to be the earlier search’s filter. So if the primary search regarded for
symbols matching description $A$, and the second search is meant to
search for symbols matching description $B$, then actually we do a search
for $A land lnot B$.

Maintain on, why do you want a complete one other bitfield? There are already negated
variations of every flag out there. Cannot you simply add these to the filter?

Good query. The distinction is slightly bit difficult. If we simply negated
every flag, we might flip an expression like $A land B$

One final thing: what occurs if there have been two earlier searches? What we
want is to to by some means mix the 2 filters into one. Taking a cue from
a earlier instance, during which “public” was adopted by “public strategies”, we
can observe that for the reason that second search has extra flags, it’s extra
restrictive, and thus assured to not discover something. So we attempt to create
the least restrictive bitfield doable, by taking an intersection of the
flags used.

Truly, that final level shouldn’t be fairly right in each doable case
(taking the intersection shouldn’t be at all times the proper factor to do).
Nonetheless, operating the code via our take a look at suite, we didn’t discover any
circumstances during which it misbehaved. So, noting the potential subject in a remark,
we moved on to different issues.

That’s, till I made a decision that it was time so as to add one other doable flag to
the bitfield. At that time, sitting and attempting to cause in regards to the
doable circumstances, I noticed that it could be a lot nicer to explain this
mathematically, and have a mannequin checker generate outlandish situations for
me.

Modeling Flags and Bitsets in Alloy

Flags are represented on the C++ facet as an enum (with customized indexing so
as to make every flag be precisely one bit). I checked, and it regarded like
Alloy had an enum characteristic, too! I began off by making an enum of the
flags I wished to play with.

enum Flag {Methodology, MethodOrField, Public}

We haven’t seen the MethodOrField flag, however it’s an necessary one. It
seems that it’s far more frequent to search for something that could possibly be
a part of a category, quite than simply its strategies. This flag is itself an “or”
of two properties (one thing being a way and one thing being a category
area). Observe that this isn’t the identical as having two flags, Methodology and
Area, and at all times together with them collectively (as a result of that will be an
“and”, not an “or”).

Discover additionally that the checklist of flags doesn’t embody the damaging variations.
Because the damaging variations are one-for-one with the optimistic ones, I
as a substitute selected to signify bitfields as merely two units: one set of
“optimistic” flags, during which the presence of e.g. Methodology signifies that the
METHOD flag was set, and one set of “damaging” flags, during which the
presence of Methodology signifies that NOT_METHOD was set. This fashion, I’m
assured that there’s a optimistic and damaging model of every flag,
routinely. Right here’s how I wrote that in Alloy.

sig Bitfield {
    , positiveFlags: set Flag
    , negativeFlags: set Flag
}

This definition (a signature in Alloy phrases) specifies what a bitfield is
like, however not any operations on it. My subsequent order of enterprise is to outline
some frequent performance on bitfields. Alloy is all about
relations and
predicates,
so for all of those, I needed to successfully write one thing that checks if
some situation holds for some arguments. This might sound summary; as an
instance, right here’s bitfieldEmpty, which checks {that a} bitfield has no flags
set.

pred bitfieldEmpty[b: Bitfield] {
    #b.positiveFlags = 0 and #b.negativeFlags = 0
}

The # operator in Alloy is used to verify the dimensions of a set. So, to verify
if a bitfield is empty, I merely verify if there are neither optimistic nor
damaging flags. Most likely probably the most uncommon facet of this piece of code is
that equality is written as =, versus == like in commonest
languages. It’s because, like I mentioned, Alloy is all about relations and
predicates, and under no circumstances about crucial manipulation of knowledge. So,
there’s no want to order = for task.

The subsequent step from here’s a predicate that accepts two arguments,
bitfieldEqual. As its title suggests, this predicate accepts two
bitfields, and makes positive they’ve precisely the identical flags set.

pred bitfieldEqual[b1: Bitfield, b2: Bitfield] {
    b1.positiveFlags = b2.positiveFlags and b1.negativeFlags = b2.negativeFlags
}

Thus far, this has been fairly just like simply writing boolean capabilities in a
language like C++. Nonetheless, the similarity is barely superficial. A simple approach
to see that’s to attempt to decide the intersection of two bitfields –
that’s the operation we can be having to mannequin, for the reason that Dyno
implementation makes use of & to mix filter units. In a language like C++, you
would possibly write a perform like the next, during which you settle for two bitfield
arguments and return a brand new bitfield.

Bitfield intersection(Bitfield b1, Bitfield b2) { /* ... */ }

Nonetheless, in Alloy, you’ll be able to’t create a brand new bitfield, nor return one thing
from a pred that isn’t a boolean. As a substitute, you describe how the inputs
can be associated to the output. So, to mannequin a binary perform, you find yourself
with a three-parameter predicate: two inputs, and one output. However how
does the output of a bitfield intersection connect with the 2 operands
being intersected? Properly, its two flag units can be intersections of the
flag units of the inputs!

pred bitfieldIntersection[b1: Bitfield, b2: Bitfield, b3: Bitfield] {
    b3.positiveFlags = b1.positiveFlags & b2.positiveFlags
    b3.negativeFlags = b1.negativeFlags & b2.negativeFlags
}

Subsequent, let’s discuss what flags do. They’re used to incorporate and
exclude symbols based mostly on sure properties. One property is being a
technique: a METHOD flag requires this property, whereas a NOT_METHOD flag
ensures {that a} image doesn’t have it. One other property is being a public
definition: if a logo isn’t public, it’ll be ignored by searches with the
PUBLIC flag set. Identical to a bitfield can have a number of flags, a logo
can have a number of properties (e.g., a public technique). Not like our bitfields,
although, we gained’t be modeling symbols as having each optimistic and damaging
properties. That’s to say, we gained’t have a “not public” property: the
absence of the “public” property can be sufficient to make one thing non-public.
Right here’s the Alloy definition for every part I simply mentioned:

enum Property { PMethod, PField, PPublic }

sig Image {
    properties: set Property
}

Now, we will specify how flags in a bitfield relate to properties on a
image. We will accomplish that by saying which flags match which properties. The
Methodology flag, for example, can be glad by the PMethod property.
The MethodOrField flag is extra lenient, and can be glad by both
PMethod or PField. Right here’s a predicate flagMatchesProperty that
encodes all of the flag-property combos:

pred flagMatchesProperty[flag: Flag, property: Property] {
    (flag = Methodology and property = PMethod) or
    (flag = MethodOrField and (property = PMethod or property = PField)) or
    (flag = Public and property = PPublic)
}

A bitfield matching a logo is slightly bit extra difficult. Mentioned
informally, the situation for a bitfield matching a logo is twofold:

• Each single optimistic flag, like METHOD, should be glad by a
  property on the image.
• Not one of the damaging flags, like NOT_METHOD, should be glad by a
  property on the image (that’s to say, if Methodology is within the damaging
  flags set, then the image should not have PMethod property). It’s extra
  conveniently to formulate this – equivalently – as follows: for every
  damaging flag, there should not be a property that satisfies it.

Every of the above two situations interprets fairly actually into Alloy:

pred bitfieldMatchesProperties[bitfield: Bitfield, symbol: Symbol]  some property: image.properties 

We will learn line 73 as “for every flag in a bitfield’s optimistic flags, there
should be some property within the image that matches it”. Equally, line 74
will be learn out loud as “for every flag within the damaging flags, no property
within the image should match it”.

We’ve written a good bit of Alloy. In the event you’re something like me, you is perhaps
getting a bit twitchy: how will we even verify that any of this works? For
this, we’ll have to run our mannequin. We are going to give Alloy a declare, and ask
it to discover a state of affairs during which that declare holds true. The best declare
is “there exists a bitfield”.

bitfieldExists: run {
    some Bitfield
}

Executing this mannequin yields a fairly attention-grabbing bitfield: one during which each single flag is about – each the optimistic and damaging variations.

That’s slightly bit ridiculous: this bitfield won’t ever match something!
You possibly can’t be and never be a way on the identical time, for example. For for a
extra attention-grabbing instance, let’s ask for a bitfield that matches some
image.

matchingBitfieldExists: run  bitfieldMatchesProperties[bitfield, symbol]

The output right here is fairly attention-grabbing too. Alloy finds a logo and a
bitfield that matches it, however they’re each empty. In impact, it mentioned:
“if you happen to don’t specify any filters, any non-public definition will match”. Truthful
sufficient, after all, however a curious departure from the earlier maximalist
“put in all of the flags!” strategy.

Let’s attempt nudge it in direction of a extra attention-grabbing case. I’m going to ask for a
filter with one optimistic and one damaging flag, and a logo with two
properties.

matchingBitfieldExists2: run {
    some bitfield : Bitfield, image : Image {
        #bitfield.positiveFlags = 1
        #bitfield.negativeFlags = 1
        #image.properties = 2
        bitfieldMatchesProperties[bitfield, symbol]
    }
}

The outcomes are extra attention-grabbing this time: we get a filter for personal
strategies, and a non-public image that was… each a area and a way?

We by no means informed Alloy {that a} image can’t be each a area and a way. It
had no thought what the flags meant, simply that they exist.
To let Alloy know what we do – that the 2 properties are incompatible –
we will use a reality. To me, probably the most pure approach of phrasing that is “there
isn’t a logo that has each the strategy and area properties”. Alas,
Alloy doesn’t have a by no means key phrase; it solely has at all times. So I decide as a substitute
for an alternate formulation: “there are at all times zero symbols which are
each strategies and fields”. In Alloy, the declare appears to be like like this:

reality "technique and area are incompatible" {
    at all times no image: Image | {
        PMethod in image.properties and PField in image.properties
    }
}

Re-running the instance program with this reality, Alloy spits out a filter for
public non-method symbols, and a logo that’s a public area. Public
fields additionally aren’t a factor in Chapel (all fields in a category are publicly
readable within the present model of the language). Maybe it’s time for
one other reality.

reality "public and area are incompatible" {
    at all times no image: Image | {
        PPublic in image.properties and PField in image.properties
    }
}

However now, Alloy fails to provide you with something in any respect. That is smart: by
proscribing the search to a logo with two properties, and making PField
incompatible with the opposite two doable properties, we’ve assured that
our image could be a public technique. However then, we additionally required a damaging
flag within the filter; nevertheless, all of the flags within the checklist match a public
technique, so making any of them damaging would assure that our image
wouldn’t be discovered. Let’s change the instance up a bit to solely ask for
optimistic flags.

matchingBitfieldExists3: run {
    some bitfield : Bitfield, image : Image {
        #bitfield.positiveFlags = 2
        #image.properties = 2
        bitfieldMatchesProperties[bitfield, symbol]
    }
}

This time, Alloy offers us a logo that’s a public technique, and a filter
that solely appears to be like for public strategies. Truthful sufficient.

Exploring Attainable Search Configurations

So now we’ve a descriptioin of filters and symbols in scopes. The subsequent factor
on the itinerary is modeling how the filters (embody and exclude) are
configured throughout scope search in Dyno. For this, let’s check out the
C++ code in Dyno.

I’ll be utilizing the department that I used to be engaged on on the time of attempting to
apply Alloy. First, right here’s the code in C++ that defines the varied flags
I’d be working with (although I’ve omitted flags that aren’t at the moment
used within the implementation).

  enum {
    /** Public */
    PUBLIC = 1,
    /** Not public (aka non-public) */
    NOT_PUBLIC = 2,
    /** A technique or area declaration */
    METHOD_FIELD = 4,
    /** One thing aside from (a way or area declaration) */
    NOT_METHOD_FIELD = 8,
    /** A technique declaration */
    METHOD = 64,
    /** One thing aside from a way declaration */
    NOT_METHOD = 128,
  };

These are the flags that we mannequin utilizing a Bitset: PUBLIC,
METHOD_FIELD, and METHOD are modeled utilizing positiveFlags, and
NOT_PUBLIC, NOT_METHOD_FIELD, and NOT_METHOD are modeled utilizing
negativeFlags. There are a variety of flags right here, and it’s not arduous to
think about that some mixture of those flags will trigger issues in our
system (notably once we know it’s an approximation). Nonetheless, the
flags aren’t used arbitrarily; actually, it wasn’t too arduous to trace down the
most necessary place within the code the place bitsets are constructed.

  IdAndFlags::Flags curFilter = 0;
  /* ... some unrelated code ... */
  if (skipPrivateVisibilities) = IdAndFlags::PUBLIC;
  
  if (onlyMethodsFields) = IdAndFlags::METHOD_FIELD;
   else if (!includeMethods && receiverScopes.empty()) = IdAndFlags::NOT_METHOD;
  

The above code converts the present search parameters into Bitfield
flags. For example, if a use assertion is being processed that doesn’t
have entry to personal fields, skipPrivateVisibilities can be set.
Then again, if the calling code didn’t explicitly ask for strategies,
and if there’s no technique receiver, then the final situation can be true.
These numerous situations are transformed into bits and utilized to
curFilter. Then, curFilter is used for trying up symbols in a scope.

It’s not too arduous to mannequin this by simply trying on the code, and
enumerating the chances. The primary if assertion can both be true
or false, after which the following if–else chain creates three
prospects in every case: both METHOD_FIELD is about, or NOT_METHOD,
or nothing.

Nonetheless, I envisioned this situation to presumably develop in complexity as extra
search configurations turned vital (in that, the NOT_METHOD choice
was an addition in my new department). I due to this fact selected to mannequin the doable
Bitfield values extra faithfully, by mimicking the crucial C++ code.

Wait, one thing sounds off. Simply earlier, you mentioned Alloy “is under no circumstances about
crucial manipulation of knowledge”. However now, we’ll mimic plain
crucial C++ code?

Alloy the programming language remains to be not crucial. Nonetheless, we will
mannequin crucial conduct in Alloy. The way in which I see it, doing so
requires us to enterprise a tiny bit into the realm of semantics
for programming languages, particularly for crucial languages. This
“enterprise” may be very minimal although, and you actually need not know a lot
about semantics to know it.

Alright. How does one mannequin crucial conduct in Alloy?

On to that subsequent.

The important piece of perception to modeling an crucial language, although
it sounds slightly bit tautological, is that statements are all about
manipulating state. For instance, state could possibly be the worth of a variable.
In the event you begin with the variable x storing the quantity 6, after which execute
the assertion x = x * 7, the ultimate worth of x can be 42. Thus, state
has modified. To place this in phrases Alloy would perceive – relations and
units – an announcement connects (relates) states earlier than it’s executed to states
after it’s executed. In our specific instance, the connection would
between the state x = 6 and the state x = 42. Within the case of including the
PUBLIC to curFilter, as on line 917 within the above code block, we might
state the connection as follows:

addBitfieldFlag[bitfieldBefore, bitfieldAfter, Public]

The above code states that bitfieldAfter (the state after line 917) is
the identical Bitfield as bitfieldBefore (the state earlier than line 917), besides
that the Public flag has been added to it.

Issues are slightly extra difficult in terms of modeling the entire
if-statement on line 916. If we wished to be very exact, we’d have to
encode the opposite variables (similar to skipPrivateVisibilities), how they’re
set, and what values are doable. Nonetheless, for the sake of conserving the
scope of this mannequin manageable in the interim, I’m content material to do
one thing easier – that’s, acknowledge that the code on line 917 could or
could not run. If it does run, our earlier addBitfieldFlag would be the
right restriction on the earlier than and after states. Nonetheless, if it doesn’t,
the state shouldn’t change in any respect. Subsequently, we will mannequin strains 916
via 918 as follows (discover the or):

addBitfieldFlag[bitfieldBefore, bitfieldAfter, Public] or
bitfieldEqual[bitfieldBefore, bitfieldAfter]

The subsequent factor to notice is that there are two if statements one after one other.
The state “after” the primary assertion is one and the identical because the state
“earlier than” the second assertion. Utilizing arrows to signify the “before-after”
relationship created by every assertion, we will visualize the entire
state of affairs as follows:

$$\text{preliminary state}\stackrel{\text{first assertion}}{\Rightarrow }\text{center state}\stackrel{\text{second assertion}}{\Rightarrow }\text{closing state}$$

textual content{preliminary state} xRightarrow{textual content{first assertion}} textual content{center state} xRightarrow{textual content{second assertion}} textual content{closing state}

preliminary statefirst assertion​center statesecond assertion​closing state

We’ll write our Alloy code to match:

/* First if assertion */
addBitfieldFlag[bitfieldBefore, bitfieldMiddle, Public] or
bitfieldEqual[bitfieldBefore, bitfieldMiddle]

/* ... one thing connecting bitfieldMiddle and bitfieldAfter ... */

From right here, we will deal with the second if/else chain in the identical approach we
did the primary if-statement: by making all three outcomes of the chain be
doable, and creating an or of all of them.

/* First if assertion */
addBitfieldFlag[bitfieldBefore, bitfieldMiddle, Public] or
bitfieldEqual[bitfieldBefore, bitfieldMiddle]

/* Second if assertion */
addBitfieldFlag[bitfieldMiddle, bitfieldAfter, MethodOrField] or
addBitfieldFlagNeg[bitfieldMiddle, bitfieldAfter, Method] or
bitfieldEqual[bitfieldMiddle, bitfieldAfter]

In order that helps mannequin the related Dyno code. Nonetheless, what we actually need is
an Alloy predicate that classifies doable outcomes of the piece of code:
is a specific mixture of flags doable or not? Right here’s the piece of
Alloy that does so:

pred possibleState[filterState: FilterState] {
    some initialState: FilterState {
        // Every lookup in scope begins with empty filter flags
        bitfieldEmpty[initialState.curFilter]

        // The intermediate states (bitfieldMiddle) are used for sequencing of operations.
        some bitfieldMiddle : Bitfield {
            // Add "Public" relying on skipPrivateVisibilities
            addBitfieldFlag[initialState.curFilter, bitfieldMiddle, Public] or
            bitfieldEqual[initialState.curFilter, bitfieldMiddle]

            // If it is a technique receiver, add technique or area restriction
            addBitfieldFlag[bitfieldMiddle, filterState.curFilter, MethodOrField] or
            // if it isn't a receiver, filter to non-methods (could possibly be overridden)
            // addBitfieldFlagNeg[bitfieldMiddle, filterState.curFilter, Method] or
            // Possibly strategies aren't being curFilterd however it's not a receiver, so no change.
            bitfieldEqual[bitfieldMiddle, filterState.curFilter]
        }
    }
}

The FilterState on the primary line (and elsewhere, actually), is new. I’m
attempting to be express in regards to the state on this specific computation. Its
definition may be very easy: at the moment, the one state we care about is the
Bitfield comparable to curFilter within the C++ code above.

sig FilterState {
    , curFilter: Bitfield
}

There’s not far more to the predicate. It says, in English, {that a} state
filterState is feasible if, ranging from an empty preliminary state
initialState, the mannequin of our C++ code can find yourself with its specific
set of flags within the curFilter bitfield.

Modeling Search State

Subsequent, I wanted to mannequin the conduct the I described earlier: trying to find
$A land lnot B$

Dyno applied this roughly as follows:

1. It saved a mapping of (searched scope → search bitfield). Initially, this
   mapping was empty.
2. When a scope was looked for the primary time, its curFilter / search
   bitfield was saved into the mapping.
3. When a scope was searched after that, the previously-stored flags within the
   mapping had been excluded (that’s the $Alandlnot B$

We’ll simplify the mannequin by getting rid of the mapping, and contemplating
solely a single scope that’s searched many occasions. We’ll signify the saved
flags as a area discovered, which can be one among two issues: both a
Bitfield representing the previously-stored search configuration, or a
NotSet sentinel worth, representing a scope that hasn’t been searched
but. The Alloy code:

one sig SearchState {
    , var discovered: Bitfield + NotSet
}

The NotSet sentinel worth is outlined in a quite simple approach:

Each of those signatures use a brand new key phrase, one. This key phrase signifies that
there’s solely a single occasion of each NotSet and SearchState in our
mannequin. That is in distinction to a signature like Bitfield, which permits
a number of bitfields to exist on the identical time. I ended up with a fairly
easy predicate that applied the “retailer if not set, intersect if set”
conduct in Alloy:

pred updateOrSet[toSet: Bitfield + NotSet, setTo: FilterState] {
    (toSet in NotSet and toSet' = setTo.curFilter) or
    (toSet not in NotSet and replace[toSet, setTo])
}

In the event you look intently, this predicate makes use of a characteristic of Alloy we haven’t
actually seen: its potential to cause about time by dipping into temporal logic.
Discover that the predicate is written not simply when it comes to toSet, but additionally
toSet'. The tick (which I personally learn as “prime”) signifies that what
we’re speaking about shouldn’t be the present worth of toSet, however its worth at
the subsequent second in time.

The primary line of the predicate represents the second merchandise from the checklist
above: if a scope hasn’t been searched earlier than (represented by the current
worth of toSet being NotSet) the long run worth (represented by toSet')
is simply the present filter / bitfield. The second line handles the third merchandise
from the checklist, updating a previously-set filter based mostly on new flags. I outlined
a further predicate to assist with this:

pred replace[toSet: Bitfield + NotSet, setTo: FilterState] {
    toSet' in Bitfield and bitfieldIntersection[toSet, setTo.curFilter, toSet']
}

What this predicate says is that on the subsequent second, the worth of toSet
can be equal to its current worth intersected with curFilter. I additionally had
to specify that the long run worth of toSet, will nonetheless be a
Bitfield after the step, and wouldn’t revert to a NotSet.

With the updateOrSet predicate in hand, we will truly specify how our
mannequin will evolve. To take action, we first have to specify the preliminary
situations. Particularly, our scope will begin out not having been
searched; its flags can be NotSet.

pred replace[toSet: Bitfield + NotSet, setTo: FilterState] {
    toSet' in Bitfield and bitfieldIntersection[toSet, setTo.curFilter, toSet']
}

Subsequent, we should specify that our SearchState adjustments in a really specific
approach: every step, the code invokes a search, and the state is modified to
document that the search occurred. Every search is described through curFilter
in a filterState. We need to be sure that curFilter is an affordable
filter (that’s, it’s a mixture of flags that may truly come up within the
C++ program). To make sure this, we will use the possibleState predicate from
earlier. From there, the updateOrSet predicate can be utilized to specify
that this step’s curFilter is saved, both as-is (if no searches
occurred beforehand) or as an intersection (if this isn’t the primary
search). The entire reality comparable to that is beneath:

reality step {
    at all times {
        // Mannequin {that a} new doLookupInScope might've occurred, with any mixture of flags.
        all searchState: SearchState {
            some fs: FilterState {
                // It is a doable mixture of lookup flags
                possibleState[fs]

                // If a search has been carried out earlier than, take the intersection; in any other case,
                // simply insert the present filter flags.
                updateOrSet[searchState.found, fs]
            }
        }
    }
}

Asking for Counterexamples

As we’ve already seen, Alloy works by discovering examples: combos of
numerous variables that match our necessities. It gained’t be adequate to
ask Alloy for an instance of our code doing what we anticipate: if the code
malfunctions 9 occasions out of ten, Alloy will nonetheless discover us the one case
during which it really works. It gained’t inform us a lot.

As a substitute, we’ve to ask it to discover a counterexample: a case which does
not work. If Alloy succeeds find such an instance, the code we’re
modeling has a bug. In fact, to make all this work, it is advisable to know what
to ask. There’s no strategy to inform Alloy, “discover me a bug” – we should be extra
particular. I needed to concentrate on bugs I used to be most apprehensive about.

If the saved mixture of flags (in discovered) evolves into a foul
configuration, issues can go unsuitable in two methods. The primary is that we’ll
by some means exclude symbols from the lookup that shouldn’t have been excluded.
In different phrases, can previous searches break future searches?

I got here up with the next Alloy (counter)instance to mannequin this
state of affairs. It’s slightly bit lengthy; there are feedback there to elucidate what
it does, and I’ll undergo beneath.

counterexampleNotFound: run {
    all searchState: SearchState {
        // a approach that subsequent outcomes of looking will miss issues.
        ultimately some image: Image,
                        fs: FilterState, fsBroken: FilterState,
                        exclude1: Bitfield, exclude2: Bitfield {
            // Some search (fs) will trigger a transition / modification of the search state...
            possibleState[fs]
            updateOrSet[searchState.found, fs]
            excludeBitfield[searchState.found, exclude1]
            // Such {that a} later, legitimate search... (fsBroken)
            possibleState[fsBroken]
            excludeBitfield[searchState.found', exclude2]

            // Will enable for a logo ...
            // ... which are unnoticed of the unique search...
            not bitfieldMatchesProperties[searchState.found, symbol]
            // ... and out of the present search
            not (bitfieldMatchesProperties[fs.curFilter, symbol] and never bitfieldMatchesProperties[exclude1, symbol])
            // However could be matched by the damaged search...
            bitfieldMatchesProperties[fsBroken.curFilter, symbol]
            // ... to not be matched by a search with the brand new state:
            not (bitfieldMatchesProperties[fsBroken.curFilter, symbol] and never bitfieldMatchesProperties[exclude2, symbol])
        }
    }
}

This instance asks that sooner or later in time, issues “go unsuitable”. In
specific, will there by a logo (image) that hasn’t been discovered but,
such {that a} seek for a specific filter (fs) will break the system,
making a subsequent search fsBroken not discover image though it
ought to have?

The possibleState, updateOrSet, and excludeBitfield
strains encode the truth that a search occurred for fs. This should be a sound
search, and the search state should be modified appropriately. Moreover,
on the time this search takes place, to make the $lnot B$ portion of
the algorithm work, the bitfield exclude1 can be set based mostly on the
earlier search state.

The subsequent two strains, possibleState and excludeBitfield, set the stage for
the damaged search: fsBroken is a one other legitimate search, and on the time it
occurs, the bitfield exclude2 is about based mostly on earlier search state.
Since fsBroken happens after fs, its “earlier search state” is definitely
the state after fs, so we use discovered' as a substitute of discovered.

Lastly, the following 4 strains of code describe the problem: the image
in query has not been discovered earlier than fs, and nor will it’s discovered by
fs. Meaning to date, it hasn’t been reported to the consumer.
Subsequently, if the image matches fsBroken, it should be reported: we haven’t
seen it but, and right here we’re being requested for one thing matching the image’s
description! Nonetheless, as per the final line of code, trying to find
fsBroken along with the suitable set of exclude flags, we nonetheless
don’t discover image. That’s an issue!

Sadly, Alloy finds a mannequin that satisfies this constraint. There
are a variety of transferring components, so the output is a bit tough to learn. I did
my finest to wash it up by turning off some arrows. Our system is spanning
a number of “moments” in time, so a single image gained’t describe the bug
completely. Right here’s the diagram Alloy outputs for the primary state:

We will get quite a bit out of this determine. First, the symbol-to-be-lost is a
non-public technique (it doesn’t have the PPublic property, and it does have
the PMethod property). Additionally, Alloy instantly offers away what fs and
fsBroken can be: ultimately, when the consumer searches for all
non-methods (negativeFlags: Methodology are the giveaway there), their
subsequent seek for something will fail to provide you with our non-public
technique, though it ought to. To assemble extra particulars about this damaged
case, we will take a look at the state that follows the preliminary one.

The primary distinction is that discovered has modified from NotSet (as a result of no
searches occurred) to FilterState1. This means that the primary search
was for all Public symbols (which our technique shouldn’t be). There is just one
extra state after this:

Within the above diagram, discovered has modified as soon as once more, this time to an empty
bitfield. It is a legitimate conduct for our system. Recall that fs was a
seek for non-methods, and that the intersection of NOT_METHOD and PUBLIC
is empty. Thus, discovered can be set to the empty bitfield, which
(incorrectly) signifies that each one symbols have been looked for! After
this, any search would fail: fsBroken doesn’t have any flags set, and
nonetheless, nothing is reported.

Now, this doesn’t definitively show the compiler is damaged: it’s doable
that there isn’t a state of affairs during which three searches like this (PUBLIC,
then NOT_METHOD, then something) will happen in follow. Nonetheless, this
gave the “motif” for reproducing the bug. All I needed to do was discover a
real-life case that matched the counterexample.

It was slightly simpler to discover a reproducer for the same counterexample,
truly. By inspection, I seen that the identical bug would happen if the
second search was for METHOD_OR_FIELD, and never for NOT_METHOD. I used to be
in a position to provide you with a (pretty convoluted) instance of Chapel code that
triggered the problem. I embody it right here as a curiosity; there’s no have to
perceive how precisely it really works.

module TopLevel {
  module XContainerUser {
    public use TopLevel.XContainer; // Will seek for public, to no avail.
  }
  module XContainer {
    non-public var x: int;
    document R {} // R is in the identical scope as x so it will not set public
    module MethodHaver {
      use TopLevel.XContainerUser;
      use TopLevel.XContainer;
      proc R.foo() {
        var y = x;
      }
    }
  }
}

Alas, the two-bitfield system isn’t just an approximation, it malfunctions
in follow. I submitted a PR to repair the problem.