Shaping Inputs with Constraints

Shaping Inputs with Constraints#

The Limits of Grammars#

So far, all the operations we have performed on our data were syntax-oriented - that is, we could shape the format and structure of our values, but not their semantics - that is, their actual meaning. Consider our Person/Age dataset from the previous section. What would we do if we want the “age” in a specific range? Or we want it to be odd? Or we want the age to be distributed in a certain way?

All of this refers to context-free grammars, which are the ones Fandango uses.

Some of these can be obtained by altering the grammar - limiting the age to two digits at most, for instance, will keep the value below 100 - but others cannot. Properties that cannot be expressed in a grammar are called semantic properties - in contrast to syntactical properties, which is precisely what grammars are good for.

Specifying Constraints#

Fandango solves this problem through a pretty unique feature: It allows users to specify constraints which inputs have to satisfy. These thus narrow down the set of possible inputs.

Constraints are predicates over grammar symbols. Essentially, you write a Boolean expression, using grammar symbols (in <...>) to refer to individual elements of the input.

As an example, consider this Fandango constraint:

int(<age>) < 50

This constraint takes the <age> element from the input and converts it into an integer (all symbols are strings in the first place). Inputs are produced only if the resulting value is less than 50.

We can add such constraints to any .fan file, say the persons.fan file from the previous section. Constraints are preceded by a keyword where. So the line we add reads

where int(<age>) < 50

and the full persons.fan file reads

<start> ::= <person_name> "," <age>
<person_name> ::= <first_name> " " <last_name>
<first_name> ::= <name>
<last_name> ::= <name>
<name> ::= <ascii_uppercase_letter><ascii_lowercase_letter>+
<age> ::= <digit>+
where int(<age>) < 50

If we do this and run Fandango, we obtain a new set of inputs:

$ fandango fuzz -f persons.fan -n 10

Qc Oiz,39
Nlmw Tkxpse,5
Izlhbz Zdjzv,1
Hve Efzde,2
Xllm Fkh,022
Fx Eorxv,42
Oxtmf Wc,9
Ukaitp Ubylv,0
Mhhsej Qnlya,0
Bdvzyd Bswje,37

We see that all persons produced now indeed have an age of less than 50. Even if an age begins with 0, it still represents a number below 50.

The language Fandango uses to express constraints is Python, so you can make use of arbitrary Python expressions. For instance, we can use Python Boolean operators (and, or, not) to request values in a range of 25-45:

Interestingly, having symbols in <...> does not conflict with the rest of Python syntax. Be sure, though, to leave spaces around < and > operators to avoid confusion.

25 <= int(<age>) and int(<age>) <= 45

and we obtain these inputs:

Vlotcw Rb,042
Ugnie Oum,039
Drnmuy Cay,43
Cqay Sedlyo,43
Oar Atkv,41
Shnzct Akaos,30

Jqgb Sedlyo,43
Vblvjs Oum,039
Drnmuy Cay,30
Shnzct Akaos,43

Start with persons.fan and add a constraint such that we generate people whose age is a multiple of 7, as in

Vanbq Odol,0
Ezvtgg Uzksq,0
Nqosc Ovszar,0
Vda Ohha,0
Ejtbd Tmg,56
Mg Pdnbd,0
Qwmsh Bc,98
Je Iw,0
Lhp Ghecmj,0
Mjuctd Zqrbq,0

(Hint: The modulo operator in Python is %).

Solution

This is not too hard. Simply add

where int(<age>) % 7 == 0

as a constraint.

Constraints and `DerivationTree` types#

Whenever Fandango evaluates a constraint, such as

int(<age>) > 20

the type of <age> is actually not a string, but a DerivationTree object - a tree representing the structure of the output.. For now, you can use DerivationTree objects almost as if they were strings:

You can convert them to other basic data types with (int(<age>), float(<age>), str(<age>))
You can invoke string methods on them (`.startswith(‘0’))
You can compare them against each other (<age_1> == <age_2>) as well as against other strings (<age> != "19")
You can print them, using implicit string conversions (print(<age>), which invokes <age>.__str__())

One thing you cannot do, though, is passing them directly as arguments to functions that do not expect a DerivationTree type. This applies to the vast majority of Python functions.

Important

If you want to pass a symbol as a function argument, convert it to the proper type (int(<age>), float(<age>), str(<age>)) first. Otherwise, you will likely raise an internal error in that very function.

Important

On symbols, the [...] operator operates differently from strings - it returns a subtree (a substring) of the produced output: <name>[0] returns the <first_name> element, not the first character. If you want to access a character (or a range of characters) of a symbol, convert it into a string first, as in str(<name>)[0].

We will learn more about derivation trees, DerivationTree types, and their operators in Accessing Input Elements.

Constraints on the Command Line#

If you want to experiment with constraints, keeping on editing .fan files is a bit cumbersome. As an alternative, Fandango also allows to specify constraints on the command line. This is done with the -c (constraint) option, followed by the constraint expression (typically in quotes).

Starting with the original persons.fan, we can thus apply age constraints as follows:

$ fandango fuzz -f persons.fan -n 10 -c '25 <= int(<age>) and int(<age>) <= 45'

Constraints can be given multiple times, so the above can also be obtained as

$ fandango fuzz -f persons.fan -n 10 -c '25 <= int(<age>)' -c 'int(<age>) <= 45'

Important

On the command line, always put constraints in single quotes ('...'), as the angle brackets might otherwise be interpreted as I/O redirection.

When do constraints belong in a .fan file, and when on the command line? As a rule of thumb:

If a constraint is necessary for obtaining valid input files (i.e. if the inputs would not be accepted otherwise), it belongs into the .fan file.
If a constraint is optional, for instance for shaping inputs towards a particular goal, then it can also go on the command line.

How Fandango Solves Constraints#

How does Fandango obtain these inputs? In a nutshell, Fandango is an evolutionary test generator:

It first uses the grammar to generate a population of inputs.
It then checks which individual inputs are closest in fulfilling the given constraints. For instance, for a constraint int(<X>) == 100, an input where <X> has a value of 90 is closer to fulfillment than one with value of, say 20.

Selecting the best inputs is also known as “survival of the fittest”

The best inputs are selected, the others are discarded.
Fandango then generates new offspring by mutating the remaining inputs, recomputing parts according to grammar rules. It can also exchange parts with those from other inputs; this is called crossover.
Fandango then repeats Steps 2-4 until all inputs satisfy the constraints.

All of this happens within Fandango, which runs through these steps with high speed. The -v option (verbose) produces some info on how the algorithm progresses:

$ fandango -v fuzz -f persons.fan -n 10 -c 'int(<age>) % 7 == 0'

fandango:INFO: ---------- Parsing FANDANGO content ----------
fandango:INFO: <stdlib>: loading cached spec from /home/runner/.cache/fandango/9268aff94d034cf8a1951e11902d6244784141c3abfc9f6283c9e5b684505438.pickle
fandango:INFO: persons.fan: loading cached spec from /home/runner/.cache/fandango/d199031ea3b3c2b5abf8a88f6f034c226ab726c7fa9e2313f26046521334f5c8.pickle
fandango:INFO: <string>: loading cached spec from /home/runner/.cache/fandango/f2a18b683b211b7a5a5592fd0a43a49d3ca23e32b9ebf8a4e42ad7b6474c74ea.pickle
fandango:INFO: int(<age>) % 7 == 0: loading cached spec from /home/runner/.cache/fandango/aedac1242c05687dbb18b4fc00dc96d416b9f8a1a98ee9161ede9d724f13d6fb.pickle
fandango:INFO: File mode: text
fandango:INFO: ---------- Initializing base population ----------
fandango:INFO: ---------- Initializing FANDANGO algorithm ---------- 
fandango:INFO: Generating (additional) initial population (size: 100)...

fandango:INFO: Initial population generated in 0.13 seconds
fandango:INFO: ---------- Done initializing base population ----------
fandango:INFO: Generating 10 solutions
fandango:INFO: ---------- Generating  for 500 generations----------
Nmzl Bcbtu,0
Fopo Elqx,0
Xfh Rxu,0
Ydrp Lpk,0
Htrb Bod,0
Ruuora Pyere,7
Fhk Doiq,0
Uytlx Ghozp,0
Ten Ivai,0
Urxo Ttyv,35
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0000.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0001.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0002.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0003.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0004.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0005.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0006.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0007.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0008.txt'
fandango:INFO: Parsing '/tmp/tmpmsnh377a/fandango-0009.txt'

Note

The -v option comes right after fandango (and not after fandango fuzz), as -v affects all commands (and not just fuzz).

Soft Constraints and Optimization#

So far, we have seen constraints that have to be satisfied for Fandango to produce a string. On top, Fandango also supports so-called “soft” constraints that Fandango aims to satisfy as good as it can. These “soft” constraints come in two forms:

maximizing constraints: These constraints specify an expression whose value should be as high as possible
minimizing constraints: These constraints specify an expression whose value should be as low as possible.

Such soft constraints are specified

on the command line, using --maximizing EXPR and --minimizing EXPR, respectively; or
in the .fan file, introducing them with minimizing and maximizing (instead of where), respectively.

If, for instance, you want Fandango to maximize the <age> field, you write

$ fandango fuzz -f persons.fan --maximize 'int(<age>)'

Whxuw Ghhfmm,20
Lyr Noq,043
Gui Odlmn,7937
Wy Pusauu,52845
Zn Ncc,92409

Qc Mfpcmu,93813

Omkicjks Hhu,839628
Tnwsgtta Rfsq,1142176
Mjk Maj,6439635

Pc Spjmfldx,7137641

Conversely, minimizing the <age> field yields

$ fandango fuzz -f persons.fan --maximize 'int(<age>)'

Pzcx Yhvtny,1
Elxfre Erk,1
Elxfre Cx,1
Mcbee Ewkbq,0

Es Svcoao,0

Ddfvlo Wprdcsj,0
Jujqvrg Yggpti,0

Jykrf Xx,0

Es Ziwrot,0
Xdegzjiyp Gkhr,0

Alternatively, you could also add to the .fan file:

maximizing int(<age>)

or

minimizing int(<age>)

respectively.

To express optional goals (i.e., real “soft” constraints), simply use a Boolean expressions as the expressions for --maximize or --minimize. Then, Fandango will aim to maximize (or minimize) its value.

Note

Remember that in Python True is equivalent to 1, and False is equivalent to 0; therefore, “maximizing” a Boolean value means that Fandango will aim to solve it.

Here is an example of a “soft” Boolean constraints, aiming to obtain names that start with “F”:

$ fandango fuzz -f persons.fan --maximize '<name>.startswith("A")' -n 10

Yy Wtrn,46680
Xmtxq Bhhvt,585
Tuzpv Pyclkp,60
Gpzq Cbd,50
Da Vbhq,5899
Rbugh Xmg,9633
Iz Cobk,83
Tfc Jviv,038
Ztyvb Hff,5
Qrk Jyygoq,86

As you see, “soft” constraints are truly optional :-)

When Constraints Cannot be Solved#

Normally, Fandango continues evolving the population until all inputs satisfy the constraints. Some constraints, however, may be difficult or even impossible to solve. After a maximum number of generations (which can be set using -N), Fandango stops and produces the inputs it has generated so far. We can see this if we specify False as a constraint:

$ fandango -v fuzz -f persons.fan -n 10 -c 'False' -N 50

fandango:INFO: ---------- Parsing FANDANGO content ----------
fandango:INFO: <stdlib>: loading cached spec from /home/runner/.cache/fandango/9268aff94d034cf8a1951e11902d6244784141c3abfc9f6283c9e5b684505438.pickle
fandango:INFO: persons.fan: loading cached spec from /home/runner/.cache/fandango/d199031ea3b3c2b5abf8a88f6f034c226ab726c7fa9e2313f26046521334f5c8.pickle
fandango:INFO: <string>: loading cached spec from /home/runner/.cache/fandango/f2a18b683b211b7a5a5592fd0a43a49d3ca23e32b9ebf8a4e42ad7b6474c74ea.pickle

fandango:INFO: False: saving spec to cache /home/runner/.cache/fandango/852280ca9d7d792967d9a8c27b6aee7545a48c626d9318c89824b481990a6cb2.pickle
fandango:INFO: File mode: text
fandango:INFO: ---------- Initializing base population ----------
fandango:INFO: ---------- Initializing FANDANGO algorithm ---------- 
fandango:INFO: Generating (additional) initial population (size: 100)...

fandango:INFO: Initial population generated in 0.07 seconds
fandango:INFO: ---------- Done initializing base population ----------
fandango:INFO: Generating 10 solutions
fandango:INFO: ---------- Generating  for 50 generations----------
fandango:INFO: Generation 1 - Average Fitness: 0.02

fandango:INFO: Generation 1: Increasing mutation rate from 0.20 to 0.22
fandango:INFO: Generation 1: Increasing crossover rate from 0.80 to 0.84
fandango:INFO: Generation 1: Increasing MAX_REPETITION from 5 to 7
fandango:INFO: Generation 1: Increasing Fuzzing Budget from 50 to 75
fandango:INFO: Generation 1 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100

fandango:INFO: Generation 2 - Average Fitness: 0.02

fandango:INFO: Generation 2: Increasing mutation rate from 0.22 to 0.24
fandango:INFO: Generation 2: Increasing crossover rate from 0.84 to 0.88
fandango:INFO: Generation 2: Increasing MAX_REPETITION from 7 to 10
fandango:INFO: Generation 2: Increasing Fuzzing Budget from 75 to 112
fandango:INFO: Generation 2 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 3 - Average Fitness: 0.02

fandango:INFO: Generation 3: Increasing mutation rate from 0.24 to 0.27
fandango:INFO: Generation 3: Increasing crossover rate from 0.88 to 0.90
fandango:INFO: Generation 3: Increasing MAX_REPETITION from 10 to 15
fandango:INFO: Generation 3: Increasing Fuzzing Budget from 112 to 168
fandango:INFO: Generation 3 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 4 - Average Fitness: 0.02

fandango:INFO: Generation 4: Increasing mutation rate from 0.27 to 0.29
fandango:INFO: Generation 4: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 4: Increasing MAX_REPETITION from 15 to 22
fandango:INFO: Generation 4: Increasing Fuzzing Budget from 168 to 200
fandango:INFO: Generation 4 stats -- Best fitness: 0.02, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 5 - Average Fitness: 0.01

fandango:INFO: Generation 5: Increasing mutation rate from 0.29 to 0.32
fandango:INFO: Generation 5: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 5: Increasing MAX_REPETITION from 22 to 33
fandango:INFO: Generation 5 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 6 - Average Fitness: 0.01

fandango:INFO: Generation 6: Increasing mutation rate from 0.32 to 0.35
fandango:INFO: Generation 6: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 6: Increasing MAX_REPETITION from 33 to 49
fandango:INFO: Generation 6 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 7 - Average Fitness: 0.01

fandango:INFO: Generation 7: Increasing mutation rate from 0.35 to 0.39
fandango:INFO: Generation 7: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 7: Increasing MAX_REPETITION from 49 to 73
fandango:INFO: Generation 7 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 8 - Average Fitness: 0.01

fandango:INFO: Generation 8: Increasing mutation rate from 0.39 to 0.43
fandango:INFO: Generation 8: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 8: Increasing MAX_REPETITION from 73 to 109
fandango:INFO: Generation 8 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 9 - Average Fitness: 0.02

fandango:INFO: Generation 9: Increasing mutation rate from 0.43 to 0.47
fandango:INFO: Generation 9: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 9: Increasing MAX_REPETITION from 109 to 163
fandango:INFO: Generation 9 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 10 - Average Fitness: 0.02

fandango:INFO: Generation 10: Increasing mutation rate from 0.47 to 0.52
fandango:INFO: Generation 10: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 10: Increasing MAX_REPETITION from 163 to 244
fandango:INFO: Generation 10 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 11 - Average Fitness: 0.02

fandango:INFO: Generation 11: Increasing mutation rate from 0.52 to 0.57
fandango:INFO: Generation 11: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 11: Increasing MAX_REPETITION from 244 to 366
fandango:INFO: Generation 11 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 12 - Average Fitness: 0.02

fandango:INFO: Generation 12: Increasing mutation rate from 0.57 to 0.63
fandango:INFO: Generation 12: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 12: Increasing MAX_REPETITION from 366 to 549

fandango:INFO: Generation 12 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 13 - Average Fitness: 0.02

fandango:INFO: Generation 13: Increasing mutation rate from 0.63 to 0.69
fandango:INFO: Generation 13: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 13: Increasing MAX_REPETITION from 549 to 823
fandango:INFO: Generation 13 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100

fandango:INFO: Generation 14 - Average Fitness: 0.02

fandango:INFO: Generation 14: Increasing mutation rate from 0.69 to 0.76
fandango:INFO: Generation 14: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 14: Increasing MAX_REPETITION from 823 to 1234
fandango:INFO: Generation 14 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 15 - Average Fitness: 0.02

fandango:INFO: Generation 15: Increasing mutation rate from 0.76 to 0.84
fandango:INFO: Generation 15: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 15: Increasing MAX_REPETITION from 1234 to 1851
fandango:INFO: Generation 15 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 16 - Average Fitness: 0.02

fandango:INFO: Generation 16: Increasing mutation rate from 0.84 to 0.92
fandango:INFO: Generation 16: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 16: Increasing MAX_REPETITION from 1851 to 2776
fandango:INFO: Generation 16 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 17 - Average Fitness: 0.02

fandango:INFO: Generation 17: Increasing mutation rate from 0.92 to 1.00
fandango:INFO: Generation 17: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 17: Increasing MAX_REPETITION from 2776 to 4164
fandango:INFO: Generation 17 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 18 - Average Fitness: 0.02

fandango:INFO: Generation 18: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 18: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 18: Increasing MAX_REPETITION from 4164 to 6246
fandango:INFO: Generation 18 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 19 - Average Fitness: 0.02

fandango:INFO: Generation 19: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 19: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 19: Increasing MAX_REPETITION from 6246 to 9369

fandango:INFO: Generation 19 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 20 - Average Fitness: 0.02

fandango:INFO: Generation 20: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 20: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 20: Increasing MAX_REPETITION from 9369 to 14053
fandango:INFO: Generation 20 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 21 - Average Fitness: 0.02

fandango:INFO: Generation 21: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 21: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 21: Increasing MAX_REPETITION from 14053 to 21079
fandango:INFO: Generation 21 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 22 - Average Fitness: 0.02

fandango:INFO: Generation 22: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 22: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 22: Increasing MAX_REPETITION from 21079 to 31618
fandango:INFO: Generation 22 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 23 - Average Fitness: 0.02

fandango:INFO: Generation 23: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 23: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 23: Increasing MAX_REPETITION from 31618 to 47427
fandango:INFO: Generation 23 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 24 - Average Fitness: 0.02

fandango:INFO: Generation 24: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 24: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 24: Increasing MAX_REPETITION from 47427 to 71140

fandango:INFO: Generation 24 stats -- Best fitness: 0.02, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 25 - Average Fitness: 0.01

fandango:INFO: Generation 25: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 25: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 25: Increasing MAX_REPETITION from 71140 to 106710
fandango:INFO: Generation 25 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 26 - Average Fitness: 0.02

fandango:INFO: Generation 26: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 26: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 26: Increasing MAX_REPETITION from 106710 to 160065
fandango:INFO: Generation 26 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 27 - Average Fitness: 0.02

fandango:INFO: Generation 27: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 27: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 27: Increasing MAX_REPETITION from 160065 to 240097
fandango:INFO: Generation 27 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 28 - Average Fitness: 0.02

fandango:INFO: Generation 28: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 28: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 28: Increasing MAX_REPETITION from 240097 to 360145

fandango:INFO: Generation 28 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 29 - Average Fitness: 0.02

fandango:INFO: Generation 29: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 29: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 29: Increasing MAX_REPETITION from 360145 to 540217
fandango:INFO: Generation 29 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 30 - Average Fitness: 0.02

fandango:INFO: Generation 30: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 30: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 30: Increasing MAX_REPETITION from 540217 to 810325
fandango:INFO: Generation 30 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 31 - Average Fitness: 0.02

fandango:INFO: Generation 31: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 31: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 31: Increasing MAX_REPETITION from 810325 to 1215487
fandango:INFO: Generation 31 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 32 - Average Fitness: 0.02

fandango:INFO: Generation 32: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 32: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 32: Increasing MAX_REPETITION from 1215487 to 1823230
fandango:INFO: Generation 32 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 33 - Average Fitness: 0.02

fandango:INFO: Generation 33: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 33: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 33: Increasing MAX_REPETITION from 1823230 to 2734845

fandango:INFO: Generation 33 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 34 - Average Fitness: 0.02

fandango:INFO: Generation 34: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 34: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 34: Increasing MAX_REPETITION from 2734845 to 4102267
fandango:INFO: Generation 34 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 35 - Average Fitness: 0.02

fandango:INFO: Generation 35: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 35: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 35: Increasing MAX_REPETITION from 4102267 to 6153400
fandango:INFO: Generation 35 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 36 - Average Fitness: 0.02

fandango:INFO: Generation 36: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 36: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 36: Increasing MAX_REPETITION from 6153400 to 9230100
fandango:INFO: Generation 36 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 37 - Average Fitness: 0.02

fandango:INFO: Generation 37: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 37: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 37: Increasing MAX_REPETITION from 9230100 to 13845150
fandango:INFO: Generation 37 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 38 - Average Fitness: 0.02

fandango:INFO: Generation 38: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 38: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 38: Increasing MAX_REPETITION from 13845150 to 20767725
fandango:INFO: Generation 38 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 39 - Average Fitness: 0.02

fandango:INFO: Generation 39: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 39: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 39: Increasing MAX_REPETITION from 20767725 to 31151587
fandango:INFO: Generation 39 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 40 - Average Fitness: 0.01

fandango:INFO: Generation 40: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 40: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 40: Increasing MAX_REPETITION from 31151587 to 46727380
fandango:INFO: Generation 40 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 41 - Average Fitness: 0.02

fandango:INFO: Generation 41: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 41: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 41: Increasing MAX_REPETITION from 46727380 to 70091070
fandango:INFO: Generation 41 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 42 - Average Fitness: 0.02

fandango:INFO: Generation 42: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 42: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 42: Increasing MAX_REPETITION from 70091070 to 105136605
fandango:INFO: Generation 42 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 43 - Average Fitness: 0.02

fandango:INFO: Generation 43: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 43: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 43: Increasing MAX_REPETITION from 105136605 to 157704907
fandango:INFO: Generation 43 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 44 - Average Fitness: 0.02

fandango:INFO: Generation 44: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 44: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 44: Increasing MAX_REPETITION from 157704907 to 236557360
fandango:INFO: Generation 44 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 45 - Average Fitness: 0.02

fandango:INFO: Generation 45: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 45: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 45: Increasing MAX_REPETITION from 236557360 to 354836040
fandango:INFO: Generation 45 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 46 - Average Fitness: 0.02

fandango:INFO: Generation 46: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 46: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 46: Increasing MAX_REPETITION from 354836040 to 532254060
fandango:INFO: Generation 46 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 47 - Average Fitness: 0.02

fandango:INFO: Generation 47: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 47: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 47: Increasing MAX_REPETITION from 532254060 to 798381090
fandango:INFO: Generation 47 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 48 - Average Fitness: 0.02

fandango:INFO: Generation 48: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 48: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 48: Increasing MAX_REPETITION from 798381090 to 1197571635
fandango:INFO: Generation 48 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 49 - Average Fitness: 0.01

fandango:INFO: Generation 49: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 49: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 49: Increasing MAX_REPETITION from 1197571635 to 1796357452
fandango:INFO: Generation 49 stats -- Best fitness: 0.02, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 50 - Average Fitness: 0.01

fandango:INFO: Generation 50: Increasing mutation rate from 1.00 to 1.00
fandango:INFO: Generation 50: Increasing crossover rate from 0.90 to 0.90
fandango:INFO: Generation 50: Increasing MAX_REPETITION from 1796357452 to 2694536178
fandango:INFO: Generation 50 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Average fitness of population: 0.02
fandango:INFO: ---------- Done generating  for 50 generations----------
fandango:INFO: Time taken: 14.68 seconds
fandango:ERROR: Population did not converge to a perfect population
fandango:ERROR: Only found 0 perfect solutions, instead of the required 10

As you see, Fandango produces a population of zero. Of course, if the constraint is False, then there can be no success.

Tip

Fandango has a --best-effort option that allows you to still output the final population.

Shaping Inputs with Constraints

Contents

Shaping Inputs with Constraints#

The Limits of Grammars#

Specifying Constraints#

Constraints and DerivationTree types#

Constraints on the Command Line#

How Fandango Solves Constraints#

Soft Constraints and Optimization#

When Constraints Cannot be Solved#

Constraints and `DerivationTree` types#