tl;dr — Test first saves time. Also a dice
expression calculator.
The setup
Larry Wall famously
remarked, "the three great virtues of a programmer: laziness,
impatience, and hubris." A skill earned by good programmers is knowing
when to favor which virtue. I failed while writing a parser for "dice
expressions" ala Dungeons &
Dragons. (Example: "3d6 + 1" means roll 3 6-sided dice, sum
the results and add 1.)
The parser is straight-forward using the
popular ANTLR4 tools:
grammar DiceExpression;
expr: left=expr op=('*' | '/') right=expr #opExpr
| left=expr op=('+' | '-') right=expr #opExpr
| '(' group=expr ')' #groupExpr
| van=('adv' | 'dis')? number=NUMBER? sides=SIDES #diceExpr
| number=NUMBER #numberExpr
;
dice: number=NUMBER? sides=SIDES;
NUMBER: '1'..'9' '0'..'9'*;
SIDES: 'd' ('4' | '6' | '8' | '10' | '12' | '20' | '100')
{ setText(getText().substring(1)); };
WS: [ \t]+ -> skip;
The grammar supports a 5th Edition feature, Advantage/Disadvantage—where
you get to roll twice and pick the better/worse result—, with the
keywords adv/dis. A less-5th
Edition-specific grammar would leave out that term from "#diceExpr".
Enter the rube
All tests pass: good! Then I thought, "What about whitespace in dice rolls
or with adv/dis?" I was concerned with expressions such as "1 +disd6" or
"3 d4". Surely those are invalid, but I don't check for them. So I began
adding explicit whitespace parsing in the #diceExpr rule.
Mistake!
Several of my tests failed for perfectly good dice expressions.
Okay, so I reverted my grammar changes. To understand what was going on, I
added tests I should have started with before editing (lines marked
"FAIL"):
@RunWith(Parameterized.class)
public final class DiceExpressionTest {
@Parameters(name = "{index}: '{0}'")
public static Collection<Object> parameters() {
return asList(args("1", true),
args("d6", true),
args("3d6", true),
args("1+3d6", true),
args("adv d6", true),
args("dis 3d6", true),
args("disd6", false), // FAIL
args("1 + 3 d6", false)); // FAIL
}
private final ExpectedException thrown = ExpectedException.none();
@Parameter(0)
public String in;
@Parameter(1)
public boolean ok;
@Test
public void shouldParse() {
if (!ok)
thrown.expect(ParseCancellationException.class);
// Just check parsing works, ignore results
DiceExpression.valueOf(in).evalWith(Roll.die());
}
private static Object[] args(final Object... args) {
return args;
}
}
And ... the "FAIL" tests pass with the original grammar. This got me to
thinking more about how ANTLR works. It is a lexer/parser. The lexer grabs
strings from the input and hands them to the parser to figure out. The
lexer has no brains, it's an expert at chopping up input. (Great post on
this.)
The cases I worried about? The lexer does not know how to chop up the first
one ("disd6"): it matches no token pattern. The parser does not understand
the tokens in the second one ("1 + 3 d6"): it expects an arithmetic
operator between "3" and "d6". My grammar already did the right thing.
Had I started with tests for these cases, instead of jumping right to
coding, I would have not spent time messing with whitespace in the
grammar. Coding first cost time rather than saved it.
Enlightenment by coding Kōan
Write tests first! No, really. Even when you "know" the
solution, write tests first. There are many ways it saves time in the long
run, it helps you think about your API, and it can save time in the short
run. My dice expression example is not unique: test-first avoids unneeded
work.
Epilogue
What does the dice expression implementation look like?
public final class DiceExpression {
private final ExprContext expression;
@Nonnull
public static DiceExpression valueOf(@Nonnull final String expression) {
final DiceExpressionLexer lexer = new DiceExpressionLexer(
new ANTLRInputStream(expression));
final DiceExpressionParser parser = new DiceExpressionParser(
new CommonTokenStream(lexer));
parser.setErrorHandler(new BailErrorStrategy());
return new DiceExpression(parser.expr());
}
private DiceExpression(final ExprContext expression) {
this.expression = expression;
}
public int evalWith(final Roll roll) {
return expression.accept(new EvalWithVisitor(roll));
}
private static final class EvalWithVisitor
extends DiceExpressionBaseVisitor<Integer> {
private final Roll roll;
public EvalWithVisitor(final Roll roll) {
this.roll = roll;
}
@Override
public Integer visitOpExpr(final OpExprContext ctx) {
final int left = visit(ctx.left);
final int right = visit(ctx.right);
switch (ctx.op.getText().charAt(0)) {
case '+': return left + right;
case '-': return left - right;
case '*': return left * right;
case '/': return left / right;
}
throw new ArithmeticException(
"Unknown operator: " + ctx.getText());
}
@Override
public Integer visitGroupExpr(final GroupExprContext ctx) {
return visit(ctx.group);
}
@Override
public Integer visitDiceExpr(final DiceExprContext ctx) {
return Dice.valueOf(ctx).evalWith(roll);
}
@Override
public Integer visitNumberExpr(final NumberExprContext ctx) {
return Integer.valueOf(ctx.number.getText());
}
}
}
And Dice, overly complicated until I can think through
Advantage/Disadvantage further:
public class Dice
implements Comparable<Dice> {
@FunctionalInterface
public interface Roll {
int roll(final int sides);
static Roll die() {
final Random random = new Random();
return sides -> random.nextInt(sides) + 1;
}
}
public enum Advantage {
DIS(2, Math::min),
NONE(1, (a, b) -> a),
ADV(2, Math::max);
private final int rolls;
private final IntBinaryOperator op;
Advantage(final int rolls, final IntBinaryOperator op) {
this.rolls = rolls;
this.op = op;
}
public final int evalWith(final Roll roll, final Dice dice) {
return range(0, rolls).
map(n -> dice.rollWith(roll)).
reduce(op).
getAsInt();
}
public final String toString(final Dice dice) {
switch (this) {
case NONE:
return dice.stringOf();
default:
return name().toLowerCase() + ' ' + dice.stringOf();
}
}
}
private final Optional<Integer> number;
private final int sides;
private final Advantage advantage;
@Nonnull
public static Dice valueOf(@Nonnull final String expression) {
final DiceExpressionLexer lexer = new DiceExpressionLexer(
new ANTLRInputStream(expression));
final DiceExpressionParser parser = new DiceExpressionParser(
new CommonTokenStream(lexer));
parser.setErrorHandler(new BailErrorStrategy());
return valueOf((DiceExprContext) parser.expr());
}
@Nonnull
static Dice valueOf(@Nonnull final DiceExprContext ctx) {
final Optional<Integer> number = Optional.ofNullable(ctx.number).
map(Token::getText).
map(Integer::valueOf);
final Integer sides = Integer.valueOf(ctx.sides.getText());
final Advantage advantage = Optional.ofNullable(ctx.van).
map(Token::getText).
map(String::toUpperCase).
map(Advantage::valueOf).
orElse(NONE);
return new Dice(number, sides, advantage);
}
public Dice(@Nonnull final Optional<Integer> number, final int sides,
final Advantage advantage) {
this.number = number;
this.sides = sides;
this.advantage = advantage;
}
public Dice(@Nullable final Integer number, final int sides,
final Advantage advantage) {
this(Optional.ofNullable(number), sides, advantage);
}
public Dice(@Nullable final Integer number, final int sides) {
this(Optional.ofNullable(number), sides, NONE);
}
public int number() {
return number.orElse(1);
}
public int sides() {
return sides;
}
public Advantage advantage() {
return advantage;
}
public int evalWith(final Roll roll) {
return advantage.evalWith(roll, this);
}
protected int rollWith(final Roll roll) {
return rangeClosed(1, number()).
map(ignored -> roll.roll(sides())).
sum();
}
@Override
public int compareTo(@Nonnull final Dice that) {
// Sort by roll average - adv/dis messes this up though
final int compare = Integer.compare(number() + (sides() + 1),
that.number() * (that.sides() + 1));
return 0 == compare ? advantage().compareTo(that.advantage())
: compare;
}
@Override
public String toString() {
return advantage.toString(this);
}
protected String stringOf() {
return number.
map(number -> number + "d" + sides()).
orElse("d" + sides());
}
@Override
public boolean equals(final Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
final Dice that = (Dice) o;
return sides() == that.sides() && number() == that.number()
&& advantage() == that.advantage();
}
@Override
public int hashCode() {
return 31 * (31 * sides() + number()) * advantage().hashCode();
}
}
UPDATE: If you wonder about the parser visitor, you have to
explicitly enable it in ANTLR4 (even though it is recommended over tree
rewriting). Use the command line flag, or in Maven
<plugin>
<groupId>org.antlr</groupId>
<artifactId>antlr4-maven-plugin</artifactId>
<version>${antlr4.version}</version>
<configuration>
<visitor>true</visitor>
</configuration>
<executions>
<execution>
<id>antlr4</id>
<goals>
<goal>antlr4</goal>
</goals>
</execution>
</executions>
</plugin>
