Skip to content

3. Records, arrays and the world

Everything in a match is held in one value of type World: every jet, every missile, every flare, the zone and the outcome. This chapter reads Adawars.Worlds, which defines it. Along the way it introduces the Ada feature that does the most work in the engine: types that carry rules with them.

A jet

engine/src/adawars-worlds.ads
   type Jet_State is (Flying, Destroyed);

   type Ammo is array (Weapon) of Natural range 0 .. Max_Loadout;

Ammo is an array with one count per weapon, each 0 to 20. A jet is a record of its state:

engine/src/adawars-worlds.ads
   type Jet is record
      State     : Jet_State;
      Pos       : Point;
      Heading   : Angle;
      Speed     : Airspeed;
      Throttle  : Throttle_Level;
      Hull      : Hull_Points;
      Remaining : Ammo;
      Fired     : Round_Count;
      Rearmed   : Round_Count;
...
   end record

Each field's type already rules out a lot: a jet cannot be outside the arena, flying faster than a boost, or carrying a negative number of missiles. But some rules involve more than one field. A jet is flying exactly when it has hull left. That is not a property of State or of Hull, but of the two together.

Predicates

Ada lets a type carry a rule like that, as a predicate:

engine/src/adawars-worlds.ads
   with
     Dynamic_Predicate =>
       (Jet.State = Flying) = (Jet.Hull > 0)
       and then (for all K in Weapon =>
                   Jet.Remaining (K) <= Weapons (K).Loadout
                   and then Jet.Rearmed (K) <= Max_Ticks
                   and then Jet.Reload (K) < Weapons (K).Rearm
                   and then Jet.Remaining (K) + Jet.Fired (K)
                            = Weapons (K).Loadout + Jet.Rearmed (K));

Inside the predicate, the type's name, Jet, stands for the value being checked. Read it as: for every jet,

  • it is flying if and only if its hull is above zero (comparing two Booleans with = means "if and only if");
  • and for every weapon, it carries no more than the loadout, and the ammunition adds up: rounds remaining plus rounds fired is the loadout plus rounds rearmed since. No missile appears from nowhere, and none vanishes.

A predicate is checked whenever a whole value of the type is created, assigned, converted or passed as a parameter. With checks enabled, a violation raises an exception at run time. In SPARK, the prover has to show that every jet the engine ever builds satisfies it. That is a much stronger statement than any number of tests: there is no sequence of inputs that leads to a jet with unaccounted-for missiles.

Dynamic and static

Dynamic_Predicate allows any Boolean expression. There is also Static_Predicate, limited to simple membership tests the compiler can reason about, such as Weekday in Mon .. Fri. The engine needs the dynamic kind.

A missile has a predicate too:

engine/src/adawars-worlds.ads
   --  A live missile always has fuel, and its age and remaining fuel add up
   --  to its weapon's endurance, so every missile expires.
   type Missile is record
      Active  : Boolean;
      Kind    : Weapon;
      Pos     : Point;
      Heading : Angle;
      Age     : Fuel_Ticks;
      Fuel    : Fuel_Ticks;
      Lock    : Target;
   end record
   with
     Dynamic_Predicate =>
       (if Missile.Active
        then Missile.Fuel > 0
             and then Missile.Age + Missile.Fuel
                      = Weapons (Missile.Kind).Fuel);

(if A then B), with no else, is true when A is false. It is how Ada writes "A implies B".

Unconstrained arrays

The number of players varies from match to match, so the arrays of jets cannot have a fixed length:

engine/src/adawars-worlds.ads
   type Jet_Array is array (Player_Id range <>) of Jet;

range <> (read "box") makes it an unconstrained array type: each Jet_Array value has its own bounds, within Player_Id. A function taking a Jet_Array works for any number of players, and asks the array for its bounds with Jets'First, Jets'Last or Jets'Range.

Missiles are a table: each player has a row of eight slots.

engine/src/adawars-worlds.ads
   --  A player's missile slots. A missile's owner is the row it is in, so
   --  every missile has a valid owner by construction.
   type Missile_Row is array (Slot) of Missile;

   type Missile_Table is array (Player_Id range <>) of Missile_Row;

Note the design choice in the comment. A missile has no Owner field that could hold a wrong value. Its owner is where it is stored.

Numbering things

A heat-seeker can lock onto a jet or onto a flare. Both are numbered in one range:

engine/src/adawars-worlds.ads
   subtype Target is Natural range 0 .. Max_Target;

   No_Target : constant Target := 0;

   subtype Jet_Target   is Target range 1 .. Max_Players;
   subtype Flare_Target is Target range Max_Players + 1 .. Max_Target;

   function Flare_Target_Of (P : Player_Id; S : Flare_Slot)
     return Flare_Target
   is (Max_Players + (P - 1) * Flare_Slots + S);

   function Flare_Owner (T : Flare_Target) return Player_Id is
     ((T - Max_Players - 1) / Flare_Slots + 1);

The subtypes split Target into three parts, and code can test which part a value is in with a membership test: T in Jet_Target. The functions convert between a flare target and its owner and slot. Their result subtypes are checked like any other: the prover shows that Flare_Owner really returns a Player_Id for every Flare_Target.

Variant records

A match is running, won by someone, or drawn. Only a won match has a winner:

engine/src/adawars-worlds.ads
   type Outcome_Kind is (Running, Won, Drawn);

   type Outcome (Kind : Outcome_Kind := Running) is record
      case Kind is
         when Won =>
            Winner : Player_Id;
         when Running | Drawn =>
            null;
      end case;
   end record;

Kind is a discriminant: a field that decides the record's shape. The case inside the record is a variant part. An Outcome whose Kind is Won has a Winner field. Any other Outcome has none, and reading Winner from it is an error (which the prover shows never happens). There is no "winner when nobody won" for code to misread.

The default, := Running, makes the discriminant changeable: a variable of type Outcome can be assigned an outcome of any kind.

The world

engine/src/adawars-worlds.ads
   type World (Players : Player_Count) is record
      Now      : Tick;
      Zone     : Zone_Radius;
      Jets     : Jet_Array (1 .. Players);
      Missiles : Missile_Table (1 .. Players);
      Flares   : Flare_Table (1 .. Players);
      --  The jet whose self-destruct, alone this tick, caught another jet;
      --  0 if none did. It decides who wins when no jet is left flying.
      Blaster  : Blaster_Id;
      Result   : Outcome;
   end record;

Here the discriminant, Players, sizes the arrays. A four-player world has exactly four jets, four rows of missiles and four rows of flares. They cannot disagree about how many players there are.

Who has won

The rule for the outcome is a function, and since it is an expression function, it is also the specification:

engine/src/adawars-worlds.ads
   function Decided
     (Now : Tick; Jets : Jet_Array; Blaster : Blaster_Id) return Outcome
   is (if Now < Max_Ticks and then Two_Flying (Jets) then (Kind => Running)
       elsif Has_Survivor (Jets) then (Kind => Won, Winner => Survivor (Jets))
       elsif Blaster in Jets'Range then (Kind => Won, Winner => Blaster)
       else (Kind => Drawn));

It is built from smaller definitions, each a quantified expression:

engine/src/adawars-worlds.ads
   function Two_Flying (Jets : Jet_Array) return Boolean is
     (for some P in Jets'Range =>
        Flying (Jets, P)
        and then (for some Q in Jets'Range =>
                    Q /= P and then Flying (Jets, Q)));

   function Sole_Survivor (Jets : Jet_Array; P : Player_Id) return Boolean is
     (Flying (Jets, P)
      and then (for all Q in Jets'Range =>
                  (if Q /= P then not Flying (Jets, Q))));

/= is "not equal". These read almost as the English they encode.

A world is valid when its recorded result is the one the rule gives:

engine/src/adawars-worlds.ads
   function Valid (W : World) return Boolean is
     (W.Result = Decided (W.Now, W.Jets, W.Blaster)
      and then Rearm_Bounded (W.Jets, Natural (W.Now)));

Chapter 7 shows that every tick of the game keeps the world valid. So the outcome the server reports is always the rule's outcome. No code anywhere can declare a winner by other means.

Building values

A new match is built with aggregates:

engine/src/adawars-worlds.adb
      W : constant World :=
        (Players  => Players,
         Now      => 0,
         Zone     => Zone_Start,
         Jets     => [for P in 1 .. Players => Spawned (Players, Rotation, P)],
         Missiles =>
           [for P in 1 .. Players => Missile_Row'[others => Inactive]],
         Flares   =>
           [for P in 1 .. Players => Flare_Row'[others => Spent_Flare]],
         Blaster  => No_Blaster,
         Result   => (Kind => Running));

[for P in 1 .. Players => ...] is an iterated component association: it builds an array by computing each element from its index. others => fills every remaining element with one value. Missile_Row'[...] is a qualified expression, which tells the compiler which array type the aggregate is.

And its contract:

engine/src/adawars-worlds.ads
   function New_World (Players : Player_Count; Rotation : Angle) return World
   with
     Post =>
       New_World'Result.Players = Players
       and then Valid (New_World'Result)
       and then New_World'Result.Result.Kind = Running
       and then New_World'Result.Now = 0;

Every match starts valid and running. GNATprove proves it, including every jet's predicate.

Try it

Break the ammunition accounting. When a jet fires, Fired takes one round off Remaining and adds one to Fired. Forget the second half:

Try: engine/src/adawars-simulation.ads
          Remaining => (J.Remaining with delta K => J.Remaining (K) - 1),
-         Fired     => (J.Fired with delta K => J.Fired (K) + 1),
          Cooldown  => Fire_Cooldown))

The jet that comes out no longer satisfies its predicate, and the prover finds it. (Don't worry about the with delta syntax; chapter 7 explains it.)

Expect: prove adawars-simulation.ads fails
predicate check might fail

Bypass the rule. A predicate is checked when a whole value is made or passed on, not each time one field is changed. Here a test sets a jet's hull to zero while leaving it flying, then asks for its heat:

Try: engine/tests/test_simulation.adb
 begin
    --  A new match.
    Check (Fresh.Result.Kind = Running, "new match runs");
+   declare
+      J : Jet := Fresh.Jets (1);
+   begin
+      J.Hull := 0;
+      Check (Heat (J) = 60, "a jet with no hull has heat");
+   end;

Tests are ordinary Ada, not proved, but they run with every check on. The moment the broken jet is passed to Heat, its predicate is checked and the test stops:

Expect: test fails
raised ADA.ASSERTIONS.ASSERTION_ERROR : Dynamic_Predicate failed at test_simulation.adb:73

Line 73 is the call to Heat, not the assignment above it. Setting one field is not checked; handing on the whole jet is.

Recap

  • A record groups fields; a predicate states a rule across them, checked on every whole value.
  • (if A then B) is implication; = on Booleans is "if and only if".
  • range <> declares arrays whose bounds vary; 'First, 'Last and 'Range ask for them.
  • A discriminant can choose a record's variant or size its arrays.
  • Iterated aggregates build arrays element by element.
  • Make wrong states unrepresentable: a missile's owner is where it is stored; a winner exists only in a won outcome.