Mate - Object Graph Language

Mate is an object graph language implementation that allows you to define grammars representing software system structures and generate valid object instances from those grammars. To know more about Mate:

• Mate Language
• Mate Grammar Examples
• How Mate Works
• Derivation Model
• Object Graph Fuzzing
• Object Graph Parsing
• Object Graph Type Validation
• Dynamic Grammar Generation by Test Suites

Architecture Overview

Mate is built on a systematic, grammar-driven framework that decouples structural definitions from object instances or Mate definitions, enabling the generation of complex, state-consistent object graphs. It employs a feedback-oriented derivation process, in which the object grammar productions are iteratively refined using any metric.

With Mate, you can:

• Declare your own Object Graph Grammars
• Generate valid object instances from a grammar and historical reward ( Monte Carlo Tree Search )
• Mate Object Graphs derivations visualization
• Propagate rewards through the derivation tree to improve future generations
• Parse and validate object graphs against your Mate grammar
• Generate Mate Object graph Grammar definitions from test object suites

Quick Start

Metacello new
    baseline: 'Mate';
    repository: 'github://FedeLoch/Mate:main';
    onConflictUseIncoming;
    load.

The default group loads the Mate package only. The paper experiments live in the Mate-Experiments package, and loading the experiments group also loads Moose and Ume:

Metacello new
    baseline: 'Mate';
    repository: 'github://FedeLoch/Mate:main';
    onConflictUseIncoming;
    load: 'experiments'.

Examples

Person Object Graph Grammar:

Person -> { age: Age }
Age -> { value: SmallInteger }

Generating Person instances:

grammar := MatePersonGrammar new.
person := grammar gen: Person.

person age.  "=> a SmallInteger, biased toward boundary values such as 0, -1 or SmallInteger maxVal"

Player Object Graph Grammar:

Player -> {
  name: ByteString,
  characterClass: Warrior | Rogue | Mage,
  level: { type: SmallInteger, between: 0 and: 99 },
  missingExperienceForNextLevel: { type: SmallInteger, greaterThan: 0 }
}

Generating player instances:

grammar := MatePlayerGrammar new.
player := grammar gen: Player.

player name.            "=> 'xyz123'"
player characterClass.  "=> a Warrior"
player level.           "=> 47 (always 0-99)"
player missingExperienceForNextLevel.  "=> always > 0"

greaterThan: and lessThan: exclude the bound, atLeast:, atMost: and between:and: include it.

Bloc Element Object Graph Grammar

BlElement -> {
  children: BlChildrenArray,
  parent: { refType: BlElement },
  visuals: (BlCustomVisuals | BlDefaultVisuals),
  constraints: BlLayoutCommonConstraints,
  selfReferences: { children.array[ .parent ] }
}

BlChildrenArray -> { 
  array: { type: [ BlElement ], sizeBetween: 0 and: 10 }
}

BlCustomVisuals -> { 
  background: (BlPaintBackground | BlTransparentBackground),
  geometry: (BlRectangleGeometry | BlEllipseGeometry | BlTriangleGeometry),
  clipChildren: Boolean,
}

BlLayoutCommonConstraints -> {
  position: Point,
  vertical: BlLayoutCommonConstraintsAxis,
  horizontal: BlLayoutCommonConstraintsAxis
}

BlLayoutCommonConstraintsAxis -> {
  resizer: BlLayoutExactResizer
}

BlLayoutExactResizer -> {
  size: { type: SmallFloat64, between: 100 and: 1000 }
}

BlPaintBackground -> {
  paint: BlColorPaint
}

BlColorPaint -> {
  color: Color
}

BlTriangleGeometry -> {
  orientation: { oneOf: { #top . #right . #left . #bottom } }
}

Generating Bloc Element instances:

grammar := MateBlocGrammar new.
element := grammar gen: BlElement.

Object Graph Derivation Visualization

grammar := MateBlocGrammar new.
derivationTree := grammar gen: BlElement from: MateContext new.
derivationTree render

Fuzzing Backpropagation

Propagate rewards through the derivation tree to improve future generations:

grammar := MatePlayerGrammar new.
derivationTree := grammar gen: Player from: MateContext new.
player := derivationTree instance.

"Propagating feedback for future generations"
grammar backpropagate: derivationTree improvement: 42.

Mate Language Reference

"Comments are written between double quotes"
Example -> {
  count: SmallInteger,
  ratio: { type: Float, between: -0.5 and: 1.5e2 },
  positive: { type: SmallInteger, greaterThan: 0 },
  limit: { type: SmallInteger, atLeast: 1, atMost: 10 },
  code: { type: SmallInteger, in: [ 200, 404, 500 ] },
  label: ByteString?,
  optionalCount: { type: SmallInteger, atLeast: 0, nullable: true },
  shape: (BlEllipseGeometry | BlTriangleGeometry)?,
  kind: { oneOf: { #small . #large . 'text' . 42 . -1 . true . nil } },
  species: OrderedCollection class | Set class,
  items: { type: [ SmallInteger | ByteString ], sizeBetween: 0 and: 5 },
  pair: { type: [ Point ], size: 2 },
  children: { type: [ Example ], collection: OrderedCollection, sizeBetween: 0 and: 3 },
  owner: { refType: Example },
  low: SmallInteger,
  high: SmallInteger,
  selfReferences: { children[ .owner ] },
  invariants: { low <= high }
}

Construct	Meaning
A | B	Union of types, flattened and printed in alphabetical order
T? / nullable: true	The field may be generated as nil (see nilProbability:)
between: a and: b, atLeast:, atMost:	Inclusive numeric bounds
greaterThan:, lessThan:	Exclusive numeric bounds
in: [ ... ]	The value is one of the listed literals
oneOf: { ... }	The field is one of the listed literals (symbols, strings, numbers, booleans, nil, classes)
[ T ] with sizeBetween: a and: b or size: n	Array of T; without a size it defaults to sizeBetween: 0 and: 10
collection: OrderedCollection	Generate the elements into this collection class (Array, OrderedCollection, Set, IdentitySet or Bag) through withAll: instead of an Array
refType: T	Reference filled by a selfReferences path, not generated
X class, X classTrait	Metaclass types
invariants: { a <= b }	A relation between two numeric fields of the same object (<, <=, =, >, >=); generation retries or repairs the fields until it holds, and validation rejects objects that break it

Identifiers may contain letters, digits and _. Numbers may be negative and use decimals or exponents. Malformed input raises an error that includes the position where parsing failed.

Type aliases

An alias gives a name to a type or to a whole field description, so you write it once and use it in many fields:

Geometry = BlRectangleGeometry | BlEllipseGeometry | BlTriangleGeometry
Shape = Geometry | BlPolygonGeometry
Level = { type: SmallInteger, between: 0 and: 99 }
Tags = { type: [ ByteSymbol ], sizeBetween: 0 and: 5 }

BlCustomVisuals -> { geometry: Geometry, clipChildren: Boolean }
Player -> { level: Level, maxLevel: Level, bonus: Level?, tags: Tags }
Canvas -> { shapes: { type: [ Shape ], sizeBetween: 0 and: 10 }, selected: (Shape | Player)? }

• An alias is written Name = definition, with no ->. It can be defined before or after the rules that use it.
• A type alias (a class or a union) can be used wherever a type is expected: as a field type, inside a union, or as the element type of a collection.
• A field alias (a { ... } description with constraints, a collection or a oneOf) can only be used as the whole type of a field.
• A field can make either kind nullable with ?; the alias definition itself cannot be nullable.
• Aliases can use other aliases. An alias that ends up defined in terms of itself is an error.
• An alias cannot have the name of an existing class, and cannot be defined twice.
• Aliases only exist in the grammar: generation and validation see the types they stand for. Each use gets its own copy, so every field keeps its own rewards and visit counts during guided fuzzing.
• mateDefinition writes the aliases first, sorted by name, keeps their names in the rules, and its output parses back into the same grammar.

Fuzzing

Reproducible generation

Every generator draws from a single random generator owned by the grammar, so a seed replays the same sequence of objects:

grammar := MatePlayerGrammar new.
grammar seed: 1234.
players := (1 to: 100) collect: [ :i | grammar gen: Player ].

Built-in values

Built-in generators are biased toward values that tend to expose bugs, and always respect the declared class and constraints:

Type	Generated values
SmallInteger, LargePositiveInteger, LargeNegativeInteger	Boundary values (0, ±1, powers of two, 32/64-bit limits, minVal/maxVal, constraint bounds), small values, and uniform values over the whole range
Float, SmallFloat64, BoxedFloat64	0.0, -0.0, ±1.0, fmax, denormals, NaN and ±infinity (only for classes that can hold them), constraint bounds and their neighbours, and values across many magnitudes
ByteString, WideString, ByteSymbol, Character	Empty, short and long strings with letters, digits, punctuation, control bytes and (for WideString) Unicode characters
Point, Color, Boolean, Object, UndefinedObject	Random instances

Depth limit and nullable fields

Generation stops recursing at maxDerivationHeight (12 by default). At the limit, a field whose type could recurse into an object that is already being built takes a non-recursive option of its type if it has one, otherwise it is set to nil; other fields are generated as usual. Nullable fields are set to nil with probability nilProbability (0.1 by default):

grammar generator maxDerivationHeight: 6; nilProbability: 0.2.

Detecting generation that does not terminate

Every call to gen:, gen:from: or genVariant: checks two bounds while it builds the graph, and signals MateGenerationLoop (an Error) as soon as one is exceeded:

• Object budget: at most maxObjects objects and collections per generation (1,000,000 by default). This catches graphs that explode and recursion that runs away.
• Nesting bound: objects nested deeper than maxNesting. By default it is maxDerivationHeight plus two levels per declaration, the deepest a terminating generation can go, so a loop is reported long before the object budget runs out.

grammar generator maxObjects: 50000; maxNesting: 40.

[ grammar gen: BlElement ]
	on: MateGenerationLoop
	do: [ :error | error messageText ].
"=> 'Generation of BlElement does not terminate: objects are nested more than 40 levels deep. Last steps: ... > BlElement > BlChildrenArray > array > BlElement'"

The error also answers rootType, objectCount and path (the declarations being built when it stopped). The generator is ready for the next generation afterwards.

Coverage

grammar explorationPercentage.          "coverage of the declarations reachable from the grammar's own types"
grammar explorationPercentageFrom: Player.  "coverage of the declarations reachable from Player"

Object Graph Validation

parse: checks an object graph against the grammar and returns its derivation tree. It raises an error when a field has the wrong type, an array has the wrong size, a value violates a constraint, or a selfReferences path does not hold. It never modifies the object, accepts subclasses of declared types, and terminates on cyclic graphs.

grammar := MatePlayerGrammar new.
grammar parse: (Player new name: 'Fede'; level: 42; characterClass: Rogue new; missingExperienceForNextLevel: 1).

grammar parse: (Player new name: 'Fede'; level: 500; characterClass: Rogue new; missingExperienceForNextLevel: 1).
"=> Error: Value 500 of type SmallInteger violates MateConstraint( min: 0 max: 99)"

Inferring Grammars from Objects

Mate offers two levels of inference.

Types only

grammar := MateOGGrammar fromObjects: { player1 . player2 . player3 }.
grammar mateDefinition.

This merges the observed classes of each field into unions, merges array element types and size ranges (empty arrays add no evidence), records Booleans as Boolean, and records fields that hold classes as oneOf choices. The output of mateDefinition is sorted by type name and parses back into the same grammar.

Types, constraints and relationships

grammar := MateOGGrammar inferFrom: players.
grammar := MateOGGrammar inferFromTest: PlayerTest.

inferFromTest: runs each test and observes the objects held in its instance variables plus its return value, so it works best when tests keep the objects they build in instance variables; objects that only live in local variables are not seen.

inferFrom: walks every instance by identity, collects statistics for each field and the links between objects, and keeps only the constraints that every instance satisfies and that have enough supporting observations. From 30 sample players it produces:

Player -> {
	name: ByteString,
	characterClass: Mage | Rogue | Warrior,
	level: { type: SmallInteger, between: 3 and: 90 },
	missingExperienceForNextLevel: { type: SmallInteger, between: 10 and: 300 },
	invariants: { level < missingExperienceForNextLevel }
}

And from a few trees whose children point back to their parent:

MateTreeNode -> {
	label: { oneOf: { #a . #b . #c } },
	children: { type: [ MateTreeNode ], collection: OrderedCollection, sizeBetween: 0 and: 2 },
	parent: { refType: MateTreeNode },
	selfReferences: { children[ .parent ] }
}

What it infers:

Family	Inferred as
Field types	unions of the observed classes, Boolean for booleans
Nullability	T? when a field is sometimes nil
Numeric ranges	between:and: with enough observations, otherwise only the sign (greaterThan: 0 or atLeast: 0)
Enumerations	oneOf: for symbols, strings and characters with few distinct values seen many times, and for fields that hold classes
Collections	element types (including nil when collections have empty slots), the collection class (Array, OrderedCollection, Set, IdentitySet, Bag) and size ranges, observed through their elements rather than their private slots. Collections of plain values keep their observed minimum size (a polygon needs its vertices); collections of objects always allow 0 elements, so recursive structures can end
Back-references	paths of up to three steps where an object always reaches itself, such as children[ .parent ] or Bloc's children.array[ .parent ]; the closing field becomes a refType. When two objects point at each other (an element and its event dispatcher), only the direction that starts from the object nearer the observed roots is kept, so generation, which builds graphs from the root down, creates both objects. A path found for one class is shared with the other classes of its hierarchy where it also holds, and an inherited closing field (such as parent) gets one reference type for the whole hierarchy
Invariants	<, <= or = between numeric fields of the same object, unless the ranges already imply them

Every decision is recorded, including the rejected ones, so you can review them:

inferrer := MateGrammarInferrer new
	minimumSupport: 20;
	maxEnumerationSize: 5;
	maxPathLength: 3;
	maxRelationshipSamples: 200;
	observeAll: players;
	yourself.

grammar := inferrer grammar.
inferrer report.
"[rejected] Player.name enumeration: 30 distinct values in 30 observations (support 30)
 [accepted] Player.level range: between: 3 and: 90 (support 30)
 [accepted] Player invariant: level < missingExperienceForNextLevel (support 30)"

The report also flags objects that are shared by several others: generated graphs hold separate copies of them, because the grammar language does not express sharing yet.

To keep the grammar about your domain rather than everything your objects reach (event handlers, announcers, weak message sends), limit how far observation goes:

inferrer := MateGrammarInferrer new
	maxDepth: 4;
	observeAll: elements;
	yourself.

The given objects are at depth 0, and each field or collection element adds one level. Observation is breadth-first, so every object is reached through its shortest path. Set maxDepth: before observeAll:. Classes found only beyond the limit get no declaration. A field that only holds such classes is left out of the grammar and reported as #depthLimit: generated objects keep the value new gives it. A field that also holds classes observed closer to the roots is kept, with only those classes in its type.

Back-reference candidates are first tested on a sample of each class's instances (maxRelationshipSamples:, 200 by default) and then verified on all of them, so large inputs such as benchmark scenes with thousands of elements stay fast without accepting a reference that only holds on the sample.

What inference cannot know

• Accidental truths. Inference keeps every constraint the sample satisfies. In the example above, level < missingExperienceForNextLevel holds only because of how the sample players were built. Review the report, raise minimumSupport, or feed more varied instances.
• What was never observed. A union option, a nil or a size that never appears in the sample will not be in the grammar.
• Constraints that come from behavior. Caches that must match computed values, hashed layouts, or objects that are only valid after some method has run are not visible in snapshots.
• Arbitrary functions and external state. Checksums, encodings, valid source code, files, sockets or globals are out of reach.
• Unsupported values. Fields holding blocks, methods, processes or other unsupported objects are skipped and reported. Dictionaries are still described through their slots.

See docs/constraint-inference.md for the design behind this.