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¶
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:
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:
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:
-- 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:
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.
-- 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:
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:
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¶
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:
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:
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:
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:
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:
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:
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.)
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:
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:
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,'Lastand'Rangeask 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.