Crate xdy

Expand description

§xDy: Once-and-for-all dice expression compiler

xDy is an extremely fast dice expression compiler that can be used to generate pseudorandom numbers. It is designed for use within a variety of applications, such as role-playing games (RPGs) and simulations, but also suits other applications that must introduce controlled randomness or generate specific probability distributions. It is written in Rust for maximum performance, safety, and portability.

§Overview

xDy compiles dice expressions into reusable functions that can be applied to user-supplied pseudorandom number generators (pRNGs) to simulate dice rolls. Functions may define formal parameters or bind values supplied through an environment. A six-pass optimizing compiler produces efficient code for each dice expression, so the resulting functions can be used to generate dice rolls with minimal overhead. The generated code targets a dedicated intermediate representation (IR) that is designed specifically for dice expressions. An efficient evaluator interprets the IR to produce the final result.

Beyond generating just a final tally, xDy also provides detailed information about the individual dice rolls that contributed to the total. So 3D6 + 1D8 might produce a total of 18, but it also tells you that the six-sided dice produced [3, 5, 4] and the eight-sided die produced 6.

xDy also provides analytical capabilities. xDy can compute the bounds and probability distribution of a dice expression. For example, xDy can determine that 3D6 + 1D8 has a minimum value of 4, has a maximum value of 26, and puts the probability of rolling a 10 at 0.125 (27/216). Probability distributions can be computed serially or in parallel (with the parallel-histogram feature). For static dice expressions, xDy can calculate the total number of outcomes without iterating through the state space.

§Language features

xDy aims to achieve sufficient expressiveness to cover the gamut of use cases established by popular RPG systems. The following features are supported:

Constants: -1, 0, 1, 2, 3, …
Standard dice, e.g., xDy for all x and y: 1D6, 2D8, 3D10, 4D17, …
Custom dice, e.g., Fudge dice: 1D[-1, 0, 1], 2D[-1, 0, 1, 3, 5], 3D[1, 1, 2, 3, 5, 8], …
Arithmetic
- Negation: -1, -1D4, …
- Addition: 1 + 1, 1 + 1D4, 1D6 + 1D8, …
- Subtraction: 3 - 2, 1 - 1D4, 1D6 - 1D8, …
- Multiplication: 2 * 3, 2 * 1D4, 2D6 * 1D8, …
- Division: 6 / 2, 6 / 1D4, 1D6 / 1D8, …
- Modulus: 6 % 2, 6 % 1D4, 1D6 % 1D8, …
- Exponentiation: 2 ^ 3, 2 ^ 1D4, 2D6 ^ 1D8, …
Grouping: (1 + 2) * 3, 1 + (2 * 3D4), (3 * 2)D5, 4D(5 - 2), …
Drop lowest: 1D6 drop lowest 1, 2D8 drop lowest 2, …
Drop highest: 1D6 drop highest 1, 2D8 drop highest 2, …
Formal parameters: x: 1D6 + {x}, y: 1D6 + {y}, x, y: {x}D{y}, …
Environmental variables: 1D6 + {x}, 1D6 + {y}, {x}D{y}, …
Dynamic expressions: 3D(2D6), x: ({x}D3)D8, …

Environmental variables permit background state to be associated with an evaluator, while formal parameters permit dynamic state to be passed into each evaluation. Both features can be used to parameterize dice expressions and make them more flexible. Environmental variables could easily cover, for example, the attributes and skills of a character in an RPG, while formal parameters could cover the situational modifiers applied to a particular roll.

§Examples

§One-shot evaluation

Rolling one standard six-sided die:

use xdy::evaluate;
use rand::rng;

let result = evaluate("1d6", vec![], vec![], &mut rng()).unwrap();

assert!(1 <= result.result && result.result <= 6);
assert!(result.records.len() == 1);
assert!(result.records[0].results.len() == 1);
assert!(1 <= result.records[0].results[0] && result.records[0].results[0] <= 6);

Rolling a variable number of dice, using an argument named x to supply the number of dice to roll:

use xdy::evaluate;
use rand::rng;

let result = evaluate("x: {x}D6", vec![3], vec![], &mut rng()).unwrap();

assert!(3 <= result.result && result.result <= 18);
assert!(result.records.len() == 1);
assert!(result.records[0].results.len() == 3);
assert!(1 <= result.records[0].results[0] && result.records[0].results[0] <= 6);
assert!(1 <= result.records[0].results[1] && result.records[0].results[1] <= 6);
assert!(1 <= result.records[0].results[2] && result.records[0].results[2] <= 6);

Rolling a variable number of dice, using an external variable named x to supply the number of dice to roll:

use xdy::evaluate;
use rand::rng;

let result =
    evaluate("{x}D6", vec![], vec![("x", 3)], &mut rng()).unwrap();

assert!(3 <= result.result && result.result <= 18);
assert!(result.records.len() == 1);
assert!(result.records[0].results.len() == 3);
assert!(1 <= result.records[0].results[0] && result.records[0].results[0] <= 6);
assert!(1 <= result.records[0].results[1] && result.records[0].results[1] <= 6);
assert!(1 <= result.records[0].results[2] && result.records[0].results[2] <= 6);

Evaluating an arithmetic expression involving different types of dice:

use xdy::evaluate;
use rand::rng;

let result = evaluate("1d6 + 2d8 - 1d10", vec![], vec![], &mut rng()).unwrap();

assert!(-7 <= result.result && result.result <= 21);
assert!(result.records.len() == 3);
assert!(result.records[0].results.len() == 1);
assert!(result.records[1].results.len() == 2);
assert!(result.records[2].results.len() == 1);
assert!(1 <= result.records[0].results[0] && result.records[0].results[0] <= 6);
assert!(1 <= result.records[1].results[0] && result.records[1].results[0] <= 8);
assert!(1 <= result.records[1].results[1] && result.records[1].results[1] <= 8);
assert!(
    1 <= result.records[2].results[0]
        && result.records[2].results[0] <= 10
);

§Repeated evaluation

Compiling and optimizing a dice expression and evaluating it multiple times:

use xdy::{compile, Evaluator};
use rand::rng;

let function = compile("3D6")?;
let mut evaluator = Evaluator::new(function);
let results = (0..10)
    .flat_map(|_| evaluator.evaluate(vec![], &mut rng()))
    .collect::<Vec<_>>();

assert!(results.len() == 10);
assert!(results.iter().all(|result| 3 <= result.result && result.result <= 18));

Compiling and optimizing a dice expression with formal parameters and evaluating it multiple times with different arguments:

use xdy::{compile, Evaluator};
use rand::rng;

let function = compile("x: 1D6 + {x}")?;
let mut evaluator = Evaluator::new(function);
let results = (0..10)
   .flat_map(|x| evaluator.evaluate(vec![x], &mut rng()))
   .collect::<Vec<_>>();

assert!(results.len() == 10);
(0..10).for_each(|i| {
   let x = i as i32;
   assert!(1 + x <= results[i].result && results[i].result <= 6 + x);
});

Compiling and optimizing a dice expression with environmental variables and evaluating it multiple times:

use xdy::{compile, Evaluator};
use rand::rng;

let function = compile("1D6 + {x}")?;
let mut evaluator = Evaluator::new(function);
evaluator.bind("x", 3)?;
let results = (0..10)
   .flat_map(|x| evaluator.evaluate(vec![], &mut rng()))
   .collect::<Vec<_>>();

assert!(results.len() == 10);
assert!(
    results.iter().all(|result| 4 <= result.result && result.result <= 9)
);

§Performance

xDy is very fast. Consider the following dice expression, where x = 5, y = 2, and z = 2:

x, y, z: {x}D[-1, 0, 1, 3, 5] drop lowest {y} drop highest {z}

This dice expression involves argument binding, custom dice, and dropping values: roll 5 custom dice, each with faces [-1, 0, 1, 3, 5], drop the 2 lowest results, and drop the 2 highest results, leaving only 1 die. On a 2023 MacBook Pro, xDy compiled and optimized this expression with mean time 22.664 µs and evaluated it with mean time 216.89 ns. Furthermore, the serial probability distribution calculation took mean time 394.85 µs and the parallel calculation took mean time 291.46 µs.

xDy provides a six-pass optimizer that rewrites IR into more efficient forms. The optimizer folds constant expressions, performs strength-reducing operations, eliminates common subexpressions, eliminates dead code, and coalesces registers. The optimizer can also reorder commutative operations and operands to improve opportunities for constant folding and strength reduction. The optimizer runs all passes repeatedly, in predefined order, until a fixed point is reached. The optimizer is designed to be fast and effective, but it can be disabled if desired.

§Safety

xDy is designed to be well-behaved for all inputs. Dice expression values are i32 and all arithmetic operations saturate on overflow or underflow. Neither the compiler nor evaluator should panic or cause undefined behavior, even for invalid dice expressions and inputs, though client misuse of vector results can lead to panics. unsafe code is limited to the tree-sitter dependency, and pertains exclusively to foreign function interfaces (FFIs) that are not exposed to users of the main crate.

§Cargo features

xDy provides several optional features that can be enabled or disabled in your Cargo.toml:

parallel-histogram: Enables parallel computation of probability distributions. This feature requires the rayon crate, and is enabled by default.
serde: Implements the Serialize and Deserialize traits for various types. This feature requires the serde crate, and is enabled by default.

Modules§

parallel: Parallel implementation of the histogram builder
serial: Serial implementation of the histogram builder

Structs§

Add: Instruction: Add two values together, saturating on overflow.
Bounds: The bounds of a function, as computed by a bounds evaluator.
Compiler: A compiler for the dice syntax tree, capable of walking the syntax tree and generating intermediate representation (IR) code. The IR code represents the body of a single function.
DependencyAnalyzer: Analyzes the dependencies between instructions.
Div: Instruction: Divide one value by another, saturating on overflow. Treat division by zero as zero.
DropHighest: Instruction: Drop the highest dice from a rolling record. This simply involves marking the highest dice as dropped, so that they are not included in the sum computed by SumRollingRecord. A negative count will put back highest dice that were previously dropped. The number of dice to drop is clamped to the number of dice in the record.
DropLowest: Instruction: Drop the lowest dice from a rolling record. This simply involves marking the lowest dice as dropped, so that they are not included in the sum computed by SumRollingRecord. A negative count will put back lowest dice that were previously dropped. The number of dice to drop is clamped to the number of dice in the record.
Evaluation: The result of a dice expression evaluation. The result includes the final value of the expression and the rolling records of the dice subexpressions.
EvaluationBounds: The bounds of a function evaluation.
EvaluationState: The complete machine state of a histogram builder during execution. Each state serves as a continuation of the machine, and may be used to resume execution. The machine is suspended after every range or die roll, which only occur inside RollRange, RollStandardDice, and RollCustomDice instructions.
Evaluator: A dice expression evaluator. The evaluator uses a client-supplied pseudo-random number to generate the results of dice rolls.
Exp: Instruction: Compute the exponentiation of one value by another, saturating on overflow.
Function: A function in the intermediate representation. This is the output of a compiler.
Histogram: A histogram of the outcomes of a dice expression, as a map from outcomes to counts. Counts are u64 to allow for large numbers of outcomes, and protected from overflow only by their enormous size.
Immediate: An immediate constant value.
Mod: Instruction: Compute the remainder of dividing one value by another, saturating on overflow. Treat division by zero as zero.
Mul: Instruction: Multiply two values together, saturating on overflow.
Neg: Instruction: Compute the negation of a value, saturating on overflow.
Passes: A set of optimization passes. An optimizer applies a set of passes to a function until a fixed point is reached.
ProgramCounter: A program counter, which references an instruction in a compiled function. As there are no control flow instructions in the dice language, the program counter is not really an addressing mode, per se, but is still useful for various tools.
RegisterIndex: The index of a register in the frame’s register set.
Return: Instruction: Return a value from the function.
RollCustomDice: Instruction: Roll a set of custom dice.
RollRange: Instruction: Roll an inclusive range.
RollStandardDice: Instruction: Roll a set of standard dice.
RollingRecord: A record of a roll of dice. The record includes the results of each die in a set of dice. RollStandardDice and RollCustomDice both populate a RollingRecord in the frame’s rolling record set.
RollingRecordIndex: The index of a rolling record in the frame’s rolling record set.
StandardOptimizer: The standard optimizer applies the specified standard optimization passes to a function. The passes are applied in sequence, and the optimizer continues to apply passes until no further changes are made to the function.
Sub: Instruction: Subtract one value from another, saturating on overflow.
SumRollingRecord: Instruction: Compute the result of a rolling record, ignoring any dice marked as dropped by DropLowest or DropHighest. The summation is clamped to the range of an i32.

Enums§

AddressingMode: The addressing mode for instructions. An addressing mode specifies how to access the operand of an instruction. The operand can be an immediate constant or a register. Registers are identified by their index into the frame’s register set.
CompilationError: An error that may occur during the evaluation of a dice expression.
EvaluationError: An error that may occur during the evaluation of a dice expression. Note that evaluation itself never causes an error, but setup may fail.
Instruction: An instruction in the intermediate representation of the dice language.
Pass: A standard optimization. Each pass applies a single optimization to a function. Each pass is represented as a single bit in a bitfield of passes. The passes are performed by the standard optimizer in definition order.
RollingRecordKind: The kind of rolling record.

Traits§

CanAllocate: Provides the ability to allocate a new instance of the receiver. This is useful for generating new register and rolling record indices.
CanVisitInstructions: Provides the ability to apply a visitor.
CanVisitSyntaxTree: Provides the ability to apply a visitor.
HistogramBuilder: A builder for histograms of the outcomes of dice expressions.
InstructionVisitor: A visitor for instructions in the intermediate representation of the dice language.
Optimizer: An optimizer performs a specific optimization on a function. It might be one of the standard optimization passes or some custom client-provided optimization.
SyntaxTreeVisitor: A visitor for the syntax tree produced by the dice language parser. Each method visits a specific type of node in the syntax tree, and is responsible for visiting any interesting children of that node.

Functions§

add: Computes the sum of the two operands, saturating on overflow. This serves as the definition of the addition operation in the dice expression language.
compile: Compile an alleged dice expression into a function. Optimize the function using the standard optimizer.
compile_unoptimized: Compile an alleged dice expression into a function. Do not optimize the function.
div: Computes the quotient of the first operand divided by the second operand, saturating on overflow. Division by zero is treated as zero. This serves as the definition of the division operation in the dice expression language.
evaluate: Evaluate the dice expression using the given arguments, environment, and pseudo-random number generator (pRNG). Missing external variables default to zero during evaluation, but all parameters must be bound. Optimize the function using the standard optimizer.
evaluate_unoptimized: Evaluate the dice expression using the given arguments, environment, and pseudo-random number generator (pRNG). Missing external variables default to zero during evaluation, but all parameters must be bound. Do not optimize the function before evaluation.
exp: Raises the first operand to the power of the second operand, saturating on overflow. Produces correct answers for base 0 or 1 even for negative exponents, otherwise treats x^y when y<0 as 0. This serves as the definition of exponentiation in the dice expression language.
mod: Computes the remainder of the first operand divided by the second operand, saturating on overflow. This serves as the definition of the remainder operation in the dice expression language.
mul: Computes the product of the two operands, saturating on overflow. This serves as the definition of the multiplication operation in the dice expression language.
neg: Computes the negation of the operand, saturating on overflow. This serves as the definition of the negation operation throughout the library.
roll_custom_dice: Generate a custom dice roll, using the same algorithm as the evaluator. If count≤0, then no dice are rolled. If faces is empty, then the result of each die is 0.
roll_range: Generate a value within the specified range, using the same algorithm as the evaluator. If the range is empty (i.e., end<start), then the result is 0.
roll_standard_dice: Generate a standard dice roll, using the same algorithm as the evaluator. If count≤0, then no dice are rolled. If faces≤0, then the result of each die is 0.
sub: Computes the difference of the two operands, saturating on overflow. This serves as the definition of the subtraction operation in the dice expression language.

Crate xdyCopy item path