//! This crate contains an implementation of the Cassowary constraint solving algorithm, based upon the work by | |
//! G.J. Badros et al. in 2001. This algorithm is designed primarily for use constraining elements in user interfaces. | |
//! Constraints are linear combinations of the problem variables. The notable features of Cassowary that make it | |
//! ideal for user interfaces are that it is incremental (i.e. you can add and remove constraints at runtime | |
//! and it will perform the minimum work to update the result) and that the constraints can be violated if | |
//! necessary, | |
//! with the order in which they are violated specified by setting a "strength" for each constraint. | |
//! This allows the solution to gracefully degrade, which is useful for when a | |
//! user interface needs to compromise on its constraints in order to still be able to display something. | |
//! | |
//! ## Constraint syntax | |
//! | |
//! This crate aims to provide syntax for describing linear constraints as naturally as possible, within | |
//! the limitations of Rust's type system. Generally you can write constraints as you would naturally, however | |
//! the operator symbol (for greater-than, less-than, equals) is replaced with an instance of the | |
//! `WeightedRelation` enum wrapped in "pipe brackets". | |
//! | |
//! For example, for the constraint | |
//! `(a + b) * 2 + c >= d + 1` with strength `s`, the code to use is | |
//! | |
//! ```ignore | |
//! (a + b) * 2.0 + c |GE(s)| d + 1.0 | |
//! ``` | |
//! | |
//! # A simple example | |
//! | |
//! Imagine a layout consisting of two elements laid out horizontally. For small window widths the elements | |
//! should compress to fit, but if there is enough space they should display at their preferred widths. The | |
//! first element will align to the left, and the second to the right. For this example we will ignore | |
//! vertical layout. | |
//! | |
//! First we need to include the relevant parts of `cassowary`: | |
//! | |
//! ``` | |
//! use cassowary::{ Solver, Variable }; | |
//! use cassowary::WeightedRelation::*; | |
//! use cassowary::strength::{ WEAK, MEDIUM, STRONG, REQUIRED }; | |
//! ``` | |
//! | |
//! And we'll construct some conveniences for pretty printing (which should hopefully be self-explanatory): | |
//! | |
//! ```ignore | |
//! use std::collections::HashMap; | |
//! let mut names = HashMap::new(); | |
//! fn print_changes(names: &HashMap<Variable, &'static str>, changes: &[(Variable, f64)]) { | |
//! println!("Changes:"); | |
//! for &(ref var, ref val) in changes { | |
//! println!("{}: {}", names[var], val); | |
//! } | |
//! } | |
//! ``` | |
//! | |
//! Let's define the variables required - the left and right edges of the elements, and the width of the window. | |
//! | |
//! ```ignore | |
//! let window_width = Variable::new(); | |
//! names.insert(window_width, "window_width"); | |
//! | |
//! struct Element { | |
//! left: Variable, | |
//! right: Variable | |
//! } | |
//! let box1 = Element { | |
//! left: Variable::new(), | |
//! right: Variable::new() | |
//! }; | |
//! names.insert(box1.left, "box1.left"); | |
//! names.insert(box1.right, "box1.right"); | |
//! | |
//! let box2 = Element { | |
//! left: Variable::new(), | |
//! right: Variable::new() | |
//! }; | |
//! names.insert(box2.left, "box2.left"); | |
//! names.insert(box2.right, "box2.right"); | |
//! ``` | |
//! | |
//! Now to set up the solver and constraints. | |
//! | |
//! ```ignore | |
//! let mut solver = Solver::new(); | |
//! solver.add_constraints(&[window_width |GE(REQUIRED)| 0.0, // positive window width | |
//! box1.left |EQ(REQUIRED)| 0.0, // left align | |
//! box2.right |EQ(REQUIRED)| window_width, // right align | |
//! box2.left |GE(REQUIRED)| box1.right, // no overlap | |
//! // positive widths | |
//! box1.left |LE(REQUIRED)| box1.right, | |
//! box2.left |LE(REQUIRED)| box2.right, | |
//! // preferred widths: | |
//! box1.right - box1.left |EQ(WEAK)| 50.0, | |
//! box2.right - box2.left |EQ(WEAK)| 100.0]).unwrap(); | |
//! ``` | |
//! | |
//! The window width is currently free to take any positive value. Let's constrain it to a particular value. | |
//! Since for this example we will repeatedly change the window width, it is most efficient to use an | |
//! "edit variable", instead of repeatedly removing and adding constraints (note that for efficiency | |
//! reasons we cannot edit a normal constraint that has been added to the solver). | |
//! | |
//! ```ignore | |
//! solver.add_edit_variable(window_width, STRONG).unwrap(); | |
//! solver.suggest_value(window_width, 300.0).unwrap(); | |
//! ``` | |
//! | |
//! This value of 300 is enough to fit both boxes in with room to spare, so let's check that this is the case. | |
//! We can fetch a list of changes to the values of variables in the solver. Using the pretty printer defined | |
//! earlier we can see what values our variables now hold. | |
//! | |
//! ```ignore | |
//! print_changes(&names, solver.fetch_changes()); | |
//! ``` | |
//! | |
//! This should print (in a possibly different order): | |
//! | |
//! ```ignore | |
//! Changes: | |
//! window_width: 300 | |
//! box1.right: 50 | |
//! box2.left: 200 | |
//! box2.right: 300 | |
//! ``` | |
//! | |
//! Note that the value of `box1.left` is not mentioned. This is because `solver.fetch_changes` only lists | |
//! *changes* to variables, and since each variable starts in the solver with a value of zero, any values that | |
//! have not changed from zero will not be reported. | |
//! | |
//! Now let's try compressing the window so that the boxes can't take up their preferred widths. | |
//! | |
//! ```ignore | |
//! solver.suggest_value(window_width, 75.0); | |
//! print_changes(&names, solver.fetch_changes); | |
//! ``` | |
//! | |
//! Now the solver can't satisfy all of the constraints. It will pick at least one of the weakest constraints to | |
//! violate. In this case it will be one or both of the preferred widths. For efficiency reasons this is picked | |
//! nondeterministically, so there are two possible results. This could be | |
//! | |
//! ```ignore | |
//! Changes: | |
//! window_width: 75 | |
//! box1.right: 0 | |
//! box2.left: 0 | |
//! box2.right: 75 | |
//! ``` | |
//! | |
//! or | |
//! | |
//! ```ignore | |
//! Changes: | |
//! window_width: 75 | |
//! box2.left: 50 | |
//! box2.right: 75 | |
//! ``` | |
//! | |
//! Due to the nature of the algorithm, "in-between" solutions, although just as valid, are not picked. | |
//! | |
//! In a user interface this is not likely a result we would prefer. The solution is to add another constraint | |
//! to control the behaviour when the preferred widths cannot both be satisfied. In this example we are going | |
//! to constrain the boxes to try to maintain a ratio between their widths. | |
//! | |
//! ``` | |
//! # use cassowary::{ Solver, Variable }; | |
//! # use cassowary::WeightedRelation::*; | |
//! # use cassowary::strength::{ WEAK, MEDIUM, STRONG, REQUIRED }; | |
//! # | |
//! # use std::collections::HashMap; | |
//! # let mut names = HashMap::new(); | |
//! # fn print_changes(names: &HashMap<Variable, &'static str>, changes: &[(Variable, f64)]) { | |
//! # println!("Changes:"); | |
//! # for &(ref var, ref val) in changes { | |
//! # println!("{}: {}", names[var], val); | |
//! # } | |
//! # } | |
//! # | |
//! # let window_width = Variable::new(); | |
//! # names.insert(window_width, "window_width"); | |
//! # struct Element { | |
//! # left: Variable, | |
//! # right: Variable | |
//! # } | |
//! # let box1 = Element { | |
//! # left: Variable::new(), | |
//! # right: Variable::new() | |
//! # }; | |
//! # names.insert(box1.left, "box1.left"); | |
//! # names.insert(box1.right, "box1.right"); | |
//! # let box2 = Element { | |
//! # left: Variable::new(), | |
//! # right: Variable::new() | |
//! # }; | |
//! # names.insert(box2.left, "box2.left"); | |
//! # names.insert(box2.right, "box2.right"); | |
//! # let mut solver = Solver::new(); | |
//! # solver.add_constraints(&[window_width |GE(REQUIRED)| 0.0, // positive window width | |
//! # box1.left |EQ(REQUIRED)| 0.0, // left align | |
//! # box2.right |EQ(REQUIRED)| window_width, // right align | |
//! # box2.left |GE(REQUIRED)| box1.right, // no overlap | |
//! # // positive widths | |
//! # box1.left |LE(REQUIRED)| box1.right, | |
//! # box2.left |LE(REQUIRED)| box2.right, | |
//! # // preferred widths: | |
//! # box1.right - box1.left |EQ(WEAK)| 50.0, | |
//! # box2.right - box2.left |EQ(WEAK)| 100.0]).unwrap(); | |
//! # solver.add_edit_variable(window_width, STRONG).unwrap(); | |
//! # solver.suggest_value(window_width, 300.0).unwrap(); | |
//! # print_changes(&names, solver.fetch_changes()); | |
//! # solver.suggest_value(window_width, 75.0); | |
//! # print_changes(&names, solver.fetch_changes()); | |
//! solver.add_constraint( | |
//! (box1.right - box1.left) / 50.0 |EQ(MEDIUM)| (box2.right - box2.left) / 100.0 | |
//! ).unwrap(); | |
//! print_changes(&names, solver.fetch_changes()); | |
//! ``` | |
//! | |
//! Now the result gives values that maintain the ratio between the sizes of the two boxes: | |
//! | |
//! ```ignore | |
//! Changes: | |
//! box1.right: 25 | |
//! box2.left: 25 | |
//! ``` | |
//! | |
//! This example may have appeared somewhat contrived, but hopefully it shows the power of the cassowary | |
//! algorithm for laying out user interfaces. | |
//! | |
//! One thing that this example exposes is that this crate is a rather low level library. It does not have | |
//! any inherent knowledge of user interfaces, directions or boxes. Thus for use in a user interface this | |
//! crate should ideally be wrapped by a higher level API, which is outside the scope of this crate. | |
use std::sync::Arc; | |
use std::collections::HashMap; | |
use std::collections::hash_map::{Entry}; | |
mod solver_impl; | |
mod operators; | |
static VARIABLE_ID: ::std::sync::atomic::AtomicUsize = ::std::sync::atomic::ATOMIC_USIZE_INIT; | |
/// Identifies a variable for the constraint solver. | |
/// Each new variable is unique in the view of the solver, but copying or cloning the variable produces | |
/// a copy of the same variable. | |
#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)] | |
pub struct Variable(usize); | |
impl Variable { | |
/// Produces a new unique variable for use in constraint solving. | |
pub fn new() -> Variable { | |
Variable(VARIABLE_ID.fetch_add(1, ::std::sync::atomic::Ordering::Relaxed)) | |
} | |
} | |
/// A variable and a coefficient to multiply that variable by. This is a sub-expression in | |
/// a constraint equation. | |
#[derive(Copy, Clone, Debug)] | |
pub struct Term { | |
pub variable: Variable, | |
pub coefficient: f64 | |
} | |
impl Term { | |
/// Construct a new Term from a variable and a coefficient. | |
fn new(variable: Variable, coefficient: f64) -> Term { | |
Term { | |
variable: variable, | |
coefficient: coefficient | |
} | |
} | |
} | |
/// An expression that can be the left hand or right hand side of a constraint equation. | |
/// It is a linear combination of variables, i.e. a sum of variables weighted by coefficients, plus an optional constant. | |
#[derive(Clone, Debug)] | |
pub struct Expression { | |
pub terms: Vec<Term>, | |
pub constant: f64 | |
} | |
impl Expression { | |
/// Constructs an expression of the form _n_, where n is a constant real number, not a variable. | |
pub fn from_constant(v: f64) -> Expression { | |
Expression { | |
terms: Vec::new(), | |
constant: v | |
} | |
} | |
/// Constructs an expression from a single term. Forms an expression of the form _n x_ | |
/// where n is the coefficient, and x is the variable. | |
pub fn from_term(term: Term) -> Expression { | |
Expression { | |
terms: vec![term], | |
constant: 0.0 | |
} | |
} | |
/// General constructor. Each `Term` in `terms` is part of the sum forming the expression, as well as `constant`. | |
pub fn new(terms: Vec<Term>, constant: f64) -> Expression { | |
Expression { | |
terms: terms, | |
constant: constant | |
} | |
} | |
/// Mutates this expression by multiplying it by minus one. | |
pub fn negate(&mut self) { | |
self.constant = -self.constant; | |
for t in &mut self.terms { | |
*t = -*t; | |
} | |
} | |
} | |
impl From<f64> for Expression { | |
fn from(v: f64) -> Expression { | |
Expression::from_constant(v) | |
} | |
} | |
impl From<Variable> for Expression { | |
fn from(v: Variable) -> Expression { | |
Expression::from_term(Term::new(v, 1.0)) | |
} | |
} | |
impl From<Term> for Expression { | |
fn from(t: Term) -> Expression { | |
Expression::from_term(t) | |
} | |
} | |
/// Contains useful constants and functions for producing strengths for use in the constraint solver. | |
/// Each constraint added to the solver has an associated strength specifying the precedence the solver should | |
/// impose when choosing which constraints to enforce. It will try to enforce all constraints, but if that | |
/// is impossible the lowest strength constraints are the first to be violated. | |
/// | |
/// Strengths are simply real numbers. The strongest legal strength is 1,001,001,000.0. The weakest is 0.0. | |
/// For convenience constants are declared for commonly used strengths. These are `REQUIRED`, `STRONG`, | |
/// `MEDIUM` and `WEAK`. Feel free to multiply these by other values to get intermediate strengths. | |
/// Note that the solver will clip given strengths to the legal range. | |
/// | |
/// `REQUIRED` signifies a constraint that cannot be violated under any circumstance. Use this special strength | |
/// sparingly, as the solver will fail completely if it find that not all of the `REQUIRED` constraints | |
/// can be satisfied. The other strengths represent fallible constraints. These should be the most | |
/// commonly used strenghts for use cases where violating a constraint is acceptable or even desired. | |
/// | |
/// The solver will try to get as close to satisfying the constraints it violates as possible, strongest first. | |
/// This behaviour can be used (for example) to provide a "default" value for a variable should no other | |
/// stronger constraints be put upon it. | |
pub mod strength { | |
/// Create a constraint as a linear combination of STRONG, MEDIUM and WEAK strengths, corresponding to `a` | |
/// `b` and `c` respectively. The result is further multiplied by `w`. | |
pub fn create(a: f64, b: f64, c: f64, w: f64) -> f64 { | |
(a * w).max(0.0).min(1000.0) * 1_000_000.0 + | |
(b * w).max(0.0).min(1000.0) * 1000.0 + | |
(c * w).max(0.0).min(1000.0) | |
} | |
pub const REQUIRED: f64 = 1_001_001_000.0; | |
pub const STRONG: f64 = 1_000_000.0; | |
pub const MEDIUM: f64 = 1_000.0; | |
pub const WEAK: f64 = 1.0; | |
/// Clips a strength value to the legal range | |
pub fn clip(s: f64) -> f64 { | |
s.min(REQUIRED).max(0.0) | |
} | |
} | |
/// The possible relations that a constraint can specify. | |
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)] | |
pub enum RelationalOperator { | |
/// `<=` | |
LessOrEqual, | |
/// `==` | |
Equal, | |
/// `>=` | |
GreaterOrEqual | |
} | |
impl std::fmt::Display for RelationalOperator { | |
fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result { | |
match *self { | |
RelationalOperator::LessOrEqual => write!(fmt, "<=") ?, | |
RelationalOperator::Equal => write!(fmt, "==") ?, | |
RelationalOperator::GreaterOrEqual => write!(fmt, ">=") ?, | |
}; | |
Ok(()) | |
} | |
} | |
#[derive(Debug)] | |
struct ConstraintData { | |
expression: Expression, | |
strength: f64, | |
op: RelationalOperator | |
} | |
/// A constraint, consisting of an equation governed by an expression and a relational operator, | |
/// and an associated strength. | |
#[derive(Clone, Debug)] | |
pub struct Constraint(Arc<ConstraintData>); | |
impl Constraint { | |
/// Construct a new constraint from an expression, a relational operator and a strength. | |
/// This corresponds to the equation `e op 0.0`, e.g. `x + y >= 0.0`. For equations with a non-zero | |
/// right hand side, subtract it from the equation to give a zero right hand side. | |
pub fn new(e: Expression, op: RelationalOperator, strength: f64) -> Constraint { | |
Constraint(Arc::new(ConstraintData { | |
expression: e, | |
op: op, | |
strength: strength | |
})) | |
} | |
/// The expression of the left hand side of the constraint equation. | |
pub fn expr(&self) -> &Expression { | |
&self.0.expression | |
} | |
/// The relational operator governing the constraint. | |
pub fn op(&self) -> RelationalOperator { | |
self.0.op | |
} | |
/// The strength of the constraint that the solver will use. | |
pub fn strength(&self) -> f64 { | |
self.0.strength | |
} | |
} | |
impl ::std::hash::Hash for Constraint { | |
fn hash<H: ::std::hash::Hasher>(&self, hasher: &mut H) { | |
use ::std::ops::Deref; | |
hasher.write_usize(self.0.deref() as *const _ as usize); | |
} | |
} | |
impl PartialEq for Constraint { | |
fn eq(&self, other: &Constraint) -> bool { | |
use ::std::ops::Deref; | |
self.0.deref() as *const _ == other.0.deref() as *const _ | |
} | |
} | |
impl Eq for Constraint {} | |
/// This is part of the syntactic sugar used for specifying constraints. This enum should be used as part of a | |
/// constraint expression. See the module documentation for more information. | |
pub enum WeightedRelation { | |
/// `==` | |
EQ(f64), | |
/// `<=` | |
LE(f64), | |
/// `>=` | |
GE(f64) | |
} | |
impl From<WeightedRelation> for (RelationalOperator, f64) { | |
fn from(r: WeightedRelation) -> (RelationalOperator, f64) { | |
use WeightedRelation::*; | |
match r { | |
EQ(s) => (RelationalOperator::Equal, s), | |
LE(s) => (RelationalOperator::LessOrEqual, s), | |
GE(s) => (RelationalOperator::GreaterOrEqual, s), | |
} | |
} | |
} | |
/// This is an intermediate type used in the syntactic sugar for specifying constraints. You should not use it | |
/// directly. | |
pub struct PartialConstraint(Expression, WeightedRelation); | |
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |
enum SymbolType { | |
Invalid, | |
External, | |
Slack, | |
Error, | |
Dummy | |
} | |
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |
struct Symbol(usize, SymbolType); | |
impl Symbol { | |
fn invalid() -> Symbol { Symbol(0, SymbolType::Invalid) } | |
fn type_(&self) -> SymbolType { self.1 } | |
} | |
#[derive(Clone)] | |
struct Row { | |
cells: HashMap<Symbol, f64>, | |
constant: f64 | |
} | |
fn near_zero(value: f64) -> bool { | |
const EPS: f64 = 1E-8; | |
if value < 0.0 { | |
-value < EPS | |
} else { | |
value < EPS | |
} | |
} | |
impl Row { | |
fn new(constant: f64) -> Row { | |
Row { | |
cells: HashMap::new(), | |
constant: constant | |
} | |
} | |
fn add(&mut self, v: f64) -> f64 { | |
self.constant += v; | |
self.constant | |
} | |
fn insert_symbol(&mut self, s: Symbol, coefficient: f64) { | |
match self.cells.entry(s) { | |
Entry::Vacant(entry) => if !near_zero(coefficient) { | |
entry.insert(coefficient); | |
}, | |
Entry::Occupied(mut entry) => { | |
*entry.get_mut() += coefficient; | |
if near_zero(*entry.get_mut()) { | |
entry.remove(); | |
} | |
} | |
} | |
} | |
fn insert_row(&mut self, other: &Row, coefficient: f64) -> bool { | |
let constant_diff = other.constant * coefficient; | |
self.constant += constant_diff; | |
for (s, v) in &other.cells { | |
self.insert_symbol(*s, v * coefficient); | |
} | |
constant_diff != 0.0 | |
} | |
fn remove(&mut self, s: Symbol) { | |
self.cells.remove(&s); | |
} | |
fn reverse_sign(&mut self) { | |
self.constant = -self.constant; | |
for (_, v) in &mut self.cells { | |
*v = -*v; | |
} | |
} | |
fn solve_for_symbol(&mut self, s: Symbol) { | |
let coeff = -1.0 / match self.cells.entry(s) { | |
Entry::Occupied(entry) => entry.remove(), | |
Entry::Vacant(_) => unreachable!() | |
}; | |
self.constant *= coeff; | |
for (_, v) in &mut self.cells { | |
*v *= coeff; | |
} | |
} | |
fn solve_for_symbols(&mut self, lhs: Symbol, rhs: Symbol) { | |
self.insert_symbol(lhs, -1.0); | |
self.solve_for_symbol(rhs); | |
} | |
fn coefficient_for(&self, s: Symbol) -> f64 { | |
self.cells.get(&s).cloned().unwrap_or(0.0) | |
} | |
fn substitute(&mut self, s: Symbol, row: &Row) -> bool { | |
if let Some(coeff) = self.cells.remove(&s) { | |
self.insert_row(row, coeff) | |
} else { | |
false | |
} | |
} | |
} | |
/// The possible error conditions that `Solver::add_constraint` can fail with. | |
#[derive(Debug, Copy, Clone)] | |
pub enum AddConstraintError { | |
/// The constraint specified has already been added to the solver. | |
DuplicateConstraint, | |
/// The constraint is required, but it is unsatisfiable in conjunction with the existing constraints. | |
UnsatisfiableConstraint, | |
/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies | |
/// additional details as a string. | |
InternalSolverError(&'static str) | |
} | |
/// The possible error conditions that `Solver::remove_constraint` can fail with. | |
#[derive(Debug, Copy, Clone)] | |
pub enum RemoveConstraintError { | |
/// The constraint specified was not already in the solver, so cannot be removed. | |
UnknownConstraint, | |
/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies | |
/// additional details as a string. | |
InternalSolverError(&'static str) | |
} | |
/// The possible error conditions that `Solver::add_edit_variable` can fail with. | |
#[derive(Debug, Copy, Clone)] | |
pub enum AddEditVariableError { | |
/// The specified variable is already marked as an edit variable in the solver. | |
DuplicateEditVariable, | |
/// The specified strength was `REQUIRED`. This is illegal for edit variable strengths. | |
BadRequiredStrength | |
} | |
/// The possible error conditions that `Solver::remove_edit_variable` can fail with. | |
#[derive(Debug, Copy, Clone)] | |
pub enum RemoveEditVariableError { | |
/// The specified variable was not an edit variable in the solver, so cannot be removed. | |
UnknownEditVariable, | |
/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies | |
/// additional details as a string. | |
InternalSolverError(&'static str) | |
} | |
/// The possible error conditions that `Solver::suggest_value` can fail with. | |
#[derive(Debug, Copy, Clone)] | |
pub enum SuggestValueError { | |
/// The specified variable was not an edit variable in the solver, so cannot have its value suggested. | |
UnknownEditVariable, | |
/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies | |
/// additional details as a string. | |
InternalSolverError(&'static str) | |
} | |
#[derive(Debug, Copy, Clone)] | |
struct InternalSolverError(&'static str); | |
pub use solver_impl::Solver; |