Add constraint solver

GtkConstraintSolver is an implementation of the Cassowary constraint
solving algorithm:

  http://constraints.cs.washington.edu/cassowary/

The Cassowary method allows to incrementally solve a tableau of linear
equations, in the form of:

  x = y × coefficient + constant

with different weights, or strengths, applied to each one.

These equations can be used to describe constraints applied to a layout
of UI elements, which allows layout managers using the Cassowary method
to quickly, and efficiently, lay out widgets in complex relations
between themselves and their parent container.

9 files changed, 4905 insertions, 0 deletions

diff --git a/gtk/gtkconstraintexpression.c b/gtk/gtkconstraintexpression.c
new file mode 100644
index 0000000000..0e5db96b62
--- /dev/null
+++ b/gtk/gtkconstraintexpression.c
@@ -0,0 +1,1842 @@
+/* gtkconstraintexpression.c: Constraint expressions and variables
+ * Copyright 2019  GNOME Foundation
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Author: Emmanuele Bassi
+ */
+
+#include "config.h"
+
+#include "gtkconstraintexpressionprivate.h"
+#include "gtkconstraintsolverprivate.h"
+
+/* {{{ Variables */
+
+typedef enum {
+  GTK_CONSTRAINT_SYMBOL_DUMMY         = 'd',
+  GTK_CONSTRAINT_SYMBOL_OBJECTIVE     = 'o',
+  GTK_CONSTRAINT_SYMBOL_SLACK         = 'S',
+  GTK_CONSTRAINT_SYMBOL_REGULAR       = 'v'
+} GtkConstraintSymbolType;
+
+struct _GtkConstraintVariable
+{
+  guint64 _id;
+
+  GtkConstraintSymbolType _type;
+
+  /* Interned strings */
+  const char *name;
+  const char *prefix;
+
+  double value;
+
+  guint is_external : 1;
+  guint is_pivotable : 1;
+  guint is_restricted : 1;
+};
+
+/* Variables are sorted by a monotonic id */
+static guint64 gtk_constraint_variable_next_id;
+
+static void
+gtk_constraint_variable_init (GtkConstraintVariable *variable,
+                              const char *name)
+{
+  variable->_id = gtk_constraint_variable_next_id++;
+  variable->name = g_intern_string (name);
+  variable->prefix = NULL;
+  variable->value = 0.0;
+}
+
+/*< private >
+ * gtk_constraint_variable_new_dummy:
+ * @name: the name of the variable
+ *
+ * Allocates and initializes a new #GtkConstraintVariable for a "dummy"
+ * symbol. Dummy symbols are typically used as markers inside a solver,
+ * and will not be factored in the solution when pivoting the tableau
+ * of the constraint equations.
+ *
+ * Only #GtkConstraintSolver should use this function.
+ *
+ * Returns: a newly allocated #GtkConstraintVariable
+ */
+GtkConstraintVariable *
+gtk_constraint_variable_new_dummy (const char *name)
+{
+  GtkConstraintVariable *res = g_rc_box_new (GtkConstraintVariable);
+
+  gtk_constraint_variable_init (res, name);
+
+  res->_type = GTK_CONSTRAINT_SYMBOL_DUMMY;
+  res->is_external = FALSE;
+  res->is_pivotable = FALSE;
+  res->is_restricted = TRUE;
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_variable_new_objective:
+ * @name: the name of the variable
+ *
+ * Allocates and initializes a new #GtkConstraintVariable for an objective
+ * symbol. This is the constant value we wish to find as the result of the
+ * simplex optimization.
+ *
+ * Only #GtkConstraintSolver should use this function.
+ *
+ * Returns: a newly allocated #GtkConstraintVariable
+ */
+GtkConstraintVariable *
+gtk_constraint_variable_new_objective (const char *name)
+{
+  GtkConstraintVariable *res = g_rc_box_new (GtkConstraintVariable);
+
+  gtk_constraint_variable_init (res, name);
+
+  res->_type = GTK_CONSTRAINT_SYMBOL_OBJECTIVE;
+  res->is_external = FALSE;
+  res->is_pivotable = FALSE;
+  res->is_restricted = FALSE;
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_variable_new_slack:
+ * @name: the name of the variable
+ *
+ * Allocates and initializes a new #GtkConstraintVariable for a "slack"
+ * symbol. Slack variables are introduced inside the tableau to turn
+ * inequalities, like:
+ *
+ * |[
+ *   expr ≥ 0
+ * ]|
+ *
+ * Into equalities, like:
+ *
+ * |[
+ *   expr - slack = 0
+ * ]|
+ *
+ * Only #GtkConstraintSolver should use this function.
+ *
+ * Returns: a newly allocated #GtkConstraintVariable
+ */
+GtkConstraintVariable *
+gtk_constraint_variable_new_slack (const char *name)
+{
+  GtkConstraintVariable *res = g_rc_box_new (GtkConstraintVariable);
+
+  gtk_constraint_variable_init (res, name);
+
+  res->_type = GTK_CONSTRAINT_SYMBOL_SLACK;
+  res->is_external = FALSE;
+  res->is_pivotable = TRUE;
+  res->is_restricted = TRUE;
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_variable_new:
+ * @name: the name of the variable
+ *
+ * Allocates and initializes a new #GtkConstraintVariable for a regular
+ * symbol. All variables introduced by constraints are regular variables.
+ *
+ * Only #GtkConstraintSolver should use this function; a constraint layout
+ * manager should ask the #GtkConstraintSolver to create a variable, using
+ * gtk_constraint_solver_create_variable(), which will insert the variable
+ * in the solver's tableau.
+ *
+ * Returns: a newly allocated #GtkConstraintVariable
+ */
+GtkConstraintVariable *
+gtk_constraint_variable_new (const char *name)
+{
+  GtkConstraintVariable *res = g_rc_box_new (GtkConstraintVariable);
+
+  gtk_constraint_variable_init (res, name);
+
+  res->_type = GTK_CONSTRAINT_SYMBOL_REGULAR;
+  res->is_external = TRUE;
+  res->is_pivotable = FALSE;
+  res->is_restricted = FALSE;
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_variable_set_prefix:
+ * @variable: a #GtkConstraintVariable
+ * @prefix: a prefix string
+ *
+ * Sets the prefix to the @variable's name.
+ *
+ * This function is useful when debugging the variable contents.
+ */
+void
+gtk_constraint_variable_set_prefix (GtkConstraintVariable *variable,
+                                    const char *prefix)
+{
+  g_return_if_fail (variable != NULL);
+
+  variable->prefix = g_intern_string (prefix);
+}
+
+/*< private >
+ * gtk_constraint_variable_ref:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Acquires a reference to @variable.
+ *
+ * Returns: (transfer full): the given #GtkConstraintVariable, with its reference
+ *   count increased
+ */
+GtkConstraintVariable *
+gtk_constraint_variable_ref (GtkConstraintVariable *variable)
+{
+  g_return_val_if_fail (variable != NULL, NULL);
+
+  return g_rc_box_acquire (variable);
+}
+
+/*< private >
+ * gtk_constraint_variable_unref:
+ * @variable: (transfer full): a #GtkConstraintVariable
+ *
+ * Releases a reference to @variable.
+ */
+void
+gtk_constraint_variable_unref (GtkConstraintVariable *variable)
+{
+  g_return_if_fail (variable != NULL);
+
+  g_rc_box_release (variable);
+}
+
+/*< private >
+ * gtk_constraint_variable_set_value:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Sets the current value of a #GtkConstraintVariable.
+ */
+void
+gtk_constraint_variable_set_value (GtkConstraintVariable *variable,
+                                   double value)
+{
+  variable->value = value;
+}
+
+/*< private >
+ * gtk_constraint_variable_get_value:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Retrieves the current value of a #GtkConstraintVariable
+ *
+ * Returns: the value of the variable
+ */
+double
+gtk_constraint_variable_get_value (const GtkConstraintVariable *variable)
+{
+  return variable->value;
+}
+
+/*< private >
+ * gtk_constraint_variable_to_string:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Turns @variable into a string, for debugging purposes.
+ *
+ * Returns: (transfer full): a string with the contents of @variable
+ */
+char *
+gtk_constraint_variable_to_string (const GtkConstraintVariable *variable)
+{
+  GString *buf = g_string_new (NULL);
+
+  if (variable == NULL)
+    g_string_append (buf, "<null>");
+  else
+    {
+      switch (variable->_type)
+        {
+        case GTK_CONSTRAINT_SYMBOL_DUMMY:
+          g_string_append (buf, "(d)");
+          break;
+        case GTK_CONSTRAINT_SYMBOL_OBJECTIVE:
+          g_string_append (buf, "(O)");
+          break;
+        case GTK_CONSTRAINT_SYMBOL_SLACK:
+          g_string_append (buf, "(S)");
+          break;
+        case GTK_CONSTRAINT_SYMBOL_REGULAR:
+          break;
+
+        default:
+          g_assert_not_reached ();
+        }
+
+      g_string_append_c (buf, '[');
+
+      if (variable->prefix != NULL)
+        {
+          g_string_append (buf, variable->prefix);
+          g_string_append_c (buf, '.');
+        }
+
+      if (variable->name != NULL)
+        g_string_append (buf, variable->name);
+
+      if (variable->_type == GTK_CONSTRAINT_SYMBOL_REGULAR)
+        {
+          char dbl_buf[G_ASCII_DTOSTR_BUF_SIZE];
+
+          g_ascii_dtostr (dbl_buf, G_ASCII_DTOSTR_BUF_SIZE, variable->value);
+
+          g_string_append_c (buf, ':');
+          g_string_append (buf, dbl_buf);
+        }
+
+      g_string_append_c (buf, ']');
+    }
+
+  return g_string_free (buf, FALSE);
+}
+
+/*< private >
+ * gtk_constraint_variable_is_external:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Checks whether the @variable was introduced from outside the solver.
+ *
+ * Returns: %TRUE if the variable is external
+ */
+gboolean
+gtk_constraint_variable_is_external (const GtkConstraintVariable *variable)
+{
+  return variable->is_external;
+}
+
+/*< private >
+ * gtk_constraint_variable_is_pivotable:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Checks whether the @variable can be used as a pivot.
+ *
+ * Returns: %TRUE if the variable is pivotable
+ */
+gboolean
+gtk_constraint_variable_is_pivotable (const GtkConstraintVariable *variable)
+{
+  return variable->is_pivotable;
+}
+
+/*< private >
+ * gtk_constraint_variable_is_restricted:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Checks whether the @variable's use is restricted.
+ *
+ * Returns: %TRUE if the variable is restricted
+ */
+gboolean
+gtk_constraint_variable_is_restricted (const GtkConstraintVariable *variable)
+{
+  return variable->is_restricted;
+}
+
+/*< private >
+ * gtk_constraint_variable_is_dummy:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Checks whether the @variable is a dummy symbol.
+ *
+ * Returns: %TRUE if the variable is a dummy symbol
+ */
+gboolean
+gtk_constraint_variable_is_dummy (const GtkConstraintVariable *variable)
+{
+  return variable->_type == GTK_CONSTRAINT_SYMBOL_DUMMY;
+}
+
+/*< private >
+ * GtkConstraintVariableSet:
+ *
+ * A set of variables.
+ */
+struct _GtkConstraintVariableSet {
+  /* HashSet<Variable>, owns a reference */
+  GHashTable *set;
+
+  /* List<Variable>, used for iterating */
+  GList *ordered_set;
+
+  /* Age of the set, to guard against mutations while iterating */
+  gint64 age;
+};
+
+/*< private >
+ * gtk_constraint_variable_set_free:
+ * @set: a #GtkConstraintVariableSet
+ *
+ * Frees the resources associated to a #GtkConstraintVariableSet/
+ */
+void
+gtk_constraint_variable_set_free (GtkConstraintVariableSet *set)
+{
+  g_return_if_fail (set != NULL);
+
+  g_list_free (set->ordered_set);
+  g_hash_table_unref (set->set);
+
+  g_free (set);
+}
+
+/*< private >
+ * gtk_constraint_variable_set_new:
+ *
+ * Creates a new #GtkConstraintVariableSet.
+ *
+ * Returns: the newly created variable set
+ */
+GtkConstraintVariableSet *
+gtk_constraint_variable_set_new (void)
+{
+  GtkConstraintVariableSet *res = g_new (GtkConstraintVariableSet, 1);
+
+  res->set = g_hash_table_new_full (NULL, NULL,
+                                    (GDestroyNotify) gtk_constraint_variable_unref,
+                                    NULL);
+  res->ordered_set = NULL;
+
+  res->age = 0;
+
+  return res;
+}
+
+static int
+sort_by_variable_id (gconstpointer a,
+                     gconstpointer b)
+{
+  const GtkConstraintVariable *va = a, *vb = b;
+
+  if (va == vb)
+    return 0;
+
+  return va->_id - vb->_id;
+}
+
+/*< private >
+ * gtk_constraint_variable_set_add:
+ * @set: a #GtkConstraintVariableSet
+ * @variable: a #GtkConstraintVariable
+ *
+ * Adds @variable to the given @set, if the @variable is not already
+ * in it.
+ *
+ * The @set will acquire a reference on the @variable, and will release
+ * it after calling gtk_constraint_variable_set_remove(), or when the @set
+ * is freed.
+ *
+ * Returns: %TRUE if the variable was added to the set, and %FALSE otherwise
+ */
+gboolean
+gtk_constraint_variable_set_add (GtkConstraintVariableSet *set,
+                                 GtkConstraintVariable *variable)
+{
+  if (g_hash_table_contains (set->set, variable))
+    return FALSE;
+
+  g_hash_table_add (set->set, gtk_constraint_variable_ref (variable));
+
+  /* This is a tricky bit; the variables in the set must be ordered
+   * not by insertion, but by the incremental id of each variable,
+   * as that's the expected iteration order
+   */
+  set->ordered_set = g_list_insert_sorted (set->ordered_set, variable, sort_by_variable_id);
+
+  set->age += 1;
+
+  return TRUE;
+}
+
+/*< private >
+ * gtk_constraint_variable_set_remove:
+ * @set: a #GtkConstraintVariableSet
+ * @variable: a #GtkConstraintVariable
+ *
+ * Removes @variable from the @set.
+ *
+ * This function will release the reference on @variable held by the @set.
+ *
+ * Returns: %TRUE if the variable was removed from the set, and %FALSE
+ *   otherwise
+ */
+gboolean
+gtk_constraint_variable_set_remove (GtkConstraintVariableSet *set,
+                                    GtkConstraintVariable *variable)
+{
+  if (g_hash_table_contains (set->set, variable))
+    {
+      set->ordered_set = g_list_remove (set->ordered_set, variable);
+      g_hash_table_remove (set->set, variable);
+      set->age += 1;
+
+      return TRUE;
+    }
+
+  return FALSE;
+}
+
+/*< private >
+ * gtk_constraint_variable_set_size:
+ * @set: a #GtkConstraintVariableSet
+ *
+ * Retrieves the size of the @set.
+ *
+ * Returns: the number of variables in the set
+ */
+int
+gtk_constraint_variable_set_size (GtkConstraintVariableSet *set)
+{
+  return g_hash_table_size (set->set);
+}
+
+/*< private >
+ * GtkConstraintVariableSetIter:
+ *
+ * An iterator type for #GtkConstraintVariableSet.
+ */
+/* Keep in sync with GtkConstraintVariableSetIter */
+typedef struct {
+  GtkConstraintVariableSet *set;
+  GList *current;
+  gint64 age;
+} RealVariableSetIter;
+
+#define REAL_VARIABLE_SET_ITER(i)       ((RealVariableSetIter *) (i))
+
+/*< private >
+ * gtk_constraint_variable_set_iter_init:
+ * @iter: a #GtkConstraintVariableSetIter
+ * @set: the #GtkConstraintVariableSet to iterate
+ *
+ * Initializes @iter for iterating over @set.
+ */
+void
+gtk_constraint_variable_set_iter_init (GtkConstraintVariableSetIter *iter,
+                                       GtkConstraintVariableSet *set)
+{
+  RealVariableSetIter *riter = REAL_VARIABLE_SET_ITER (iter);
+
+  g_return_if_fail (iter != NULL);
+  g_return_if_fail (set != NULL);
+
+  riter->set = set;
+  riter->current = NULL;
+  riter->age = set->age;
+}
+
+/*< private >
+ * gtk_constraint_variable_set_iter_next:
+ * @iter: a #GtkConstraintVariableSetIter
+ * @variable_p: (out): the next variable in the set
+ *
+ * Advances the @iter to the next variable in the #GtkConstraintVariableSet.
+ *
+ * Returns: %TRUE if the iterator was advanced, and %FALSE otherwise
+ */
+gboolean
+gtk_constraint_variable_set_iter_next (GtkConstraintVariableSetIter *iter,
+                                       GtkConstraintVariable **variable_p)
+{
+  RealVariableSetIter *riter = REAL_VARIABLE_SET_ITER (iter);
+
+  g_return_val_if_fail (iter != NULL, FALSE);
+  g_return_val_if_fail (variable_p != NULL, FALSE);
+
+  g_assert (riter->age == riter->set->age);
+
+  if (riter->current == NULL)
+    riter->current = riter->set->ordered_set;
+  else
+    riter->current = riter->current->next;
+
+  if (riter->current != NULL)
+    *variable_p = riter->current->data;
+
+  return riter->current != NULL;
+}
+
+/*< private >
+ * gtk_constraint_variable_pair_new:
+ * @first: a #GtkConstraintVariable
+ * @second: a #GtkConstraintVariable
+ *
+ * Creates a new #GtkConstraintVariablePair, containint @first and @second.
+ *
+ * The #GtkConstraintVariablePair acquires a reference over the two
+ * given #GtkConstraintVariables.
+ *
+ * Returns: a new #GtkConstraintVariablePair
+ */
+GtkConstraintVariablePair *
+gtk_constraint_variable_pair_new (GtkConstraintVariable *first,
+                                  GtkConstraintVariable *second)
+{
+  GtkConstraintVariablePair *res = g_new (GtkConstraintVariablePair, 1);
+
+  res->first = gtk_constraint_variable_ref (first);
+  res->second = gtk_constraint_variable_ref (second);
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_variable_pair_free:
+ * @pair: a #GtkConstraintVariablePair
+ *
+ * Frees the resources associated by @pair.
+ */
+void
+gtk_constraint_variable_pair_free (GtkConstraintVariablePair *pair)
+{
+  g_clear_pointer (&pair->first, gtk_constraint_variable_unref);
+  g_clear_pointer (&pair->second, gtk_constraint_variable_unref);
+
+  g_free (pair);
+}
+
+/* }}} */
+
+/* {{{ Expressions */
+
+/*< private >
+ * Term:
+ * @variable: a #GtkConstraintVariable
+ * @coefficient: the coefficient applied to the @variable
+ * @next: the next term in the expression
+ * @prev: the previous term in the expression;
+ *
+ * A tuple of (@variable, @coefficient) in an equation.
+ *
+ * The term acquires a reference on the variable.
+ */
+typedef struct _Term Term;
+
+struct _Term {
+  GtkConstraintVariable *variable;
+  double coefficient;
+
+  Term *next;
+  Term *prev;
+};
+
+static Term *
+term_new (GtkConstraintVariable *variable,
+          double coefficient)
+{
+  Term *res = g_new (Term, 1);
+
+  res->variable = gtk_constraint_variable_ref (variable);
+  res->coefficient = coefficient;
+  res->next = res->prev = NULL;
+
+  return res;
+}
+
+static void
+term_free (gpointer data)
+{
+  Term *term = data;
+
+  if (term == NULL)
+    return;
+
+  gtk_constraint_variable_unref (term->variable);
+
+  g_free (term);
+}
+
+struct _GtkConstraintExpression
+{
+  double constant;
+
+  /* HashTable<Variable, Term>; the key is the term's variable,
+   * and the value is owned by the hash table
+   */
+  GHashTable *terms;
+
+  /* List of terms, in insertion order */
+  Term *first_term;
+  Term *last_term;
+
+  /* Used by GtkConstraintExpressionIter to guard against changes
+   * in the expression while iterating
+   */
+  gint64 age;
+};
+
+/*< private >
+ * gtk_constraint_expression_add_term:
+ * @self: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable
+ * @coefficient: a coefficient for @variable
+ *
+ * Adds a new term formed by (@variable, @coefficient) into a
+ * #GtkConstraintExpression.
+ *
+ * The @expression acquires a reference on @variable.
+ */
+static void
+gtk_constraint_expression_add_term (GtkConstraintExpression *self,
+                                    GtkConstraintVariable *variable,
+                                    double coefficient)
+{
+  Term *term;
+
+  if (self->terms == NULL)
+    {
+      g_assert (self->first_term == NULL && self->last_term == NULL);
+      self->terms = g_hash_table_new_full (NULL, NULL,
+                                           NULL,
+                                           term_free);
+    }
+
+  term = term_new (variable, coefficient);
+
+  g_hash_table_insert (self->terms, term->variable, term);
+
+  if (self->first_term == NULL)
+    self->first_term = term;
+
+  term->prev = self->last_term;
+
+  if (self->last_term != NULL)
+    self->last_term->next = term;
+
+  self->last_term = term;
+
+  /* Increase the age of the expression, so that we can catch
+   * mutations from within an iteration over the terms
+   */
+  self->age += 1;
+}
+
+static void
+gtk_constraint_expression_remove_term (GtkConstraintExpression *self,
+                                       GtkConstraintVariable *variable)
+{
+  Term *term, *iter;
+
+  if (self->terms == NULL)
+    return;
+
+  term = g_hash_table_lookup (self->terms, variable);
+  if (term == NULL)
+    return;
+
+  /* Keep the variable alive for the duration of the function */
+  gtk_constraint_variable_ref (variable);
+
+  iter = self->first_term;
+  while (iter != NULL)
+    {
+      Term *next = iter->next;
+      Term *prev = iter->prev;
+
+      if (iter == term)
+        {
+          if (prev != NULL)
+            prev->next = next;
+          if (next != NULL)
+            next->prev = prev;
+
+          if (iter == self->first_term)
+            self->first_term = next;
+          if (iter == self->last_term)
+            self->last_term = prev;
+
+          iter->next = NULL;
+          iter->prev = NULL;
+
+          break;
+        }
+
+      iter = next;
+    }
+
+  g_hash_table_remove (self->terms, variable);
+
+  gtk_constraint_variable_unref (variable);
+
+  self->age += 1;
+}
+
+/*< private >
+ * gtk_constraint_expression_new:
+ * @constant: a constant for the expression
+ *
+ * Creates a new #GtkConstraintExpression with the given @constant.
+ *
+ * Returns: (transfer full): the newly created expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_new (double constant)
+{
+  GtkConstraintExpression *res = g_rc_box_new (GtkConstraintExpression);
+
+  res->age = 0;
+  res->terms = NULL;
+  res->first_term = NULL;
+  res->last_term = NULL;
+  res->constant = constant;
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_expression_new_from_variable:
+ * @variable: a #GtkConstraintVariable
+ *
+ * Creates a new #GtkConstraintExpression with the given @variable.
+ *
+ * Returns: (transfer full): the newly created expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_new_from_variable (GtkConstraintVariable *variable)
+{
+  GtkConstraintExpression *res = gtk_constraint_expression_new (0.0);
+
+  gtk_constraint_expression_add_term (res, variable, 1.0);
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_expression_ref:
+ * @expression: a #GtkConstraintExpression
+ *
+ * Acquires a reference on @expression.
+ *
+ * Returns: (transfer full): the @expression, with its reference
+ *   count increased
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_ref (GtkConstraintExpression *expression)
+{
+  g_return_val_if_fail (expression != NULL, NULL);
+
+  return g_rc_box_acquire (expression);
+}
+
+static void
+gtk_constraint_expression_clear (gpointer data)
+{
+  GtkConstraintExpression *self = data;
+
+  g_clear_pointer (&self->terms, g_hash_table_unref);
+
+  self->age = 0;
+  self->constant = 0.0;
+  self->first_term = NULL;
+  self->last_term = NULL;
+}
+
+/*< private >
+ * gtk_constraint_expression_unref:
+ * @expression: (transfer full): a #GtkConstraintExpression
+ *
+ * Releases a reference on @expression.
+ */
+void
+gtk_constraint_expression_unref (GtkConstraintExpression *expression)
+{
+  g_rc_box_release_full (expression, gtk_constraint_expression_clear);
+}
+
+/*< private >
+ * gtk_constraint_expression_is_constant:
+ * @expression: a #GtkConstraintExpression
+ *
+ * Checks whether @expression is a constant value, with no variable terms.
+ *
+ * Returns: %TRUE if the @expression is a constant
+ */
+gboolean
+gtk_constraint_expression_is_constant (const GtkConstraintExpression *expression)
+{
+  return expression->terms == NULL;
+}
+
+/*< private >
+ * gtk_constraint_expression_set_constant:
+ * @expression: a #GtkConstraintExpression
+ * @constant: the value of the constant
+ *
+ * Sets the value of the constant part of @expression.
+ */
+void
+gtk_constraint_expression_set_constant (GtkConstraintExpression *expression,
+                                        double constant)
+{
+  g_return_if_fail (expression != NULL);
+
+  expression->constant = constant;
+}
+
+/*< private >
+ * gtk_constraint_expression_get_constant:
+ * @expression: a #GtkConstraintExpression
+ *
+ * Retrieves the constant value of @expression.
+ *
+ * Returns: the constant of @expression
+ */
+double
+gtk_constraint_expression_get_constant (const GtkConstraintExpression *expression)
+{
+  g_return_val_if_fail (expression != NULL, 0.0);
+
+  return expression->constant;
+}
+
+GtkConstraintExpression *
+gtk_constraint_expression_clone (GtkConstraintExpression *expression)
+{
+  GtkConstraintExpression *res;
+  Term *iter;
+
+  res = gtk_constraint_expression_new (expression->constant);
+
+  iter = expression->first_term;
+  while (iter != NULL)
+    {
+      gtk_constraint_expression_add_term (res, iter->variable, iter->coefficient);
+
+      iter = iter->next;
+    }
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_expression_add_variable:
+ * @expression: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable to add to @expression
+ * @coefficient: the coefficient of @variable
+ * @subject: (nullable): a #GtkConstraintVariable
+ * @solver: (nullable): a #GtkConstraintSolver
+ *
+ * Adds a `(@coefficient × @variable)` term to @expression.
+ *
+ * If @expression already contains a term for @variable, this function will
+ * update its coefficient.
+ *
+ * If @coefficient is 0 and @expression already contains a term for @variable,
+ * the term for @variable will be removed.
+ *
+ * This function will notify @solver if @variable is added or removed from
+ * the @expression.
+ */
+void
+gtk_constraint_expression_add_variable (GtkConstraintExpression *expression,
+                                        GtkConstraintVariable *variable,
+                                        double coefficient,
+                                        GtkConstraintVariable *subject,
+                                        GtkConstraintSolver *solver)
+{
+  /* If the expression already contains the variable, update the coefficient */
+  if (expression->terms != NULL)
+    {
+      Term *t = g_hash_table_lookup (expression->terms, variable);
+
+      if (t != NULL)
+        {
+          double new_coefficient = t->coefficient + coefficient;
+
+          /* Setting the coefficient to 0 will remove the variable */
+          if (G_APPROX_VALUE (new_coefficient, 0.0, 0.001))
+            {
+              /* Update the tableau if needed */
+              if (solver != NULL)
+                gtk_constraint_solver_note_removed_variable (solver, variable, subject);
+
+              gtk_constraint_expression_remove_term (expression, variable);
+
+              if (subject != NULL)
+                gtk_constraint_variable_unref (subject);
+            }
+          else
+            {
+              t->coefficient = new_coefficient;
+            }
+
+          return;
+        }
+    }
+
+  /* Otherwise, add the variable if the coefficient is non-zero */
+  if (!G_APPROX_VALUE (coefficient, 0.0, 0.001))
+    {
+      gtk_constraint_expression_add_term (expression, variable, coefficient);
+
+      if (solver != NULL)
+        gtk_constraint_solver_note_added_variable (solver, variable, subject);
+    }
+}
+
+/*< private >
+ * gtk_constraint_expression_remove_variable:
+ * @expression: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable
+ *
+ * Removes @variable from @expression.
+ */
+void
+gtk_constraint_expression_remove_variable (GtkConstraintExpression *expression,
+                                           GtkConstraintVariable *variable)
+{
+  g_return_if_fail (expression != NULL);
+  g_return_if_fail (variable != NULL);
+
+  gtk_constraint_expression_remove_term (expression, variable);
+}
+
+/*< private >
+ * gtk_constraint_expression_set_variable:
+ * @expression: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable
+ * @coefficient: a coefficient for @variable
+ *
+ * Sets the @coefficient for @variable inside an @expression.
+ *
+ * If the @expression does not contain a term for @variable, a new
+ * one will be added.
+ */
+void
+gtk_constraint_expression_set_variable (GtkConstraintExpression *expression,
+                                        GtkConstraintVariable *variable,
+                                        double coefficient)
+{
+  if (expression->terms != NULL)
+    {
+      Term *t = g_hash_table_lookup (expression->terms, variable);
+
+      if (t != NULL)
+        {
+          t->coefficient = coefficient;
+          return;
+        }
+    }
+
+  gtk_constraint_expression_add_term (expression, variable, coefficient);
+}
+
+/*< private >
+ * gtk_constraint_expression_add_expression:
+ * @a_expr: first operand
+ * @b_expr: second operand
+ * @n: the multiplication factor for @b_expr
+ * @subject: (nullable): a #GtkConstraintVariable
+ * @solver: (nullable): a #GtkConstraintSolver
+ *
+ * Adds `(@n × @b_expr)` to @a_expr.
+ *
+ * Typically, this function is used to turn two expressions in the
+ * form:
+ *
+ * |[
+ *   a.x + a.width = b.x + b.width
+ * ]|
+ *
+ * into a single expression:
+ *
+ * |[
+ *   a.x + a.width - b.x - b.width = 0
+ * ]|
+ *
+ * If @solver is not %NULL, this function will notify a #GtkConstraintSolver
+ * of every variable that was added or removed from @a_expr.
+ */
+void
+gtk_constraint_expression_add_expression (GtkConstraintExpression *a_expr,
+                                          GtkConstraintExpression *b_expr,
+                                          double n,
+                                          GtkConstraintVariable *subject,
+                                          GtkConstraintSolver *solver)
+{
+  Term *iter;
+
+  a_expr->constant += (n * b_expr->constant);
+
+  iter = b_expr->last_term;
+  while (iter != NULL)
+    {
+      Term *next = iter->prev;
+
+      gtk_constraint_expression_add_variable (a_expr,
+                                              iter->variable, n * iter->coefficient,
+                                              subject,
+                                              solver);
+
+      iter = next;
+    }
+}
+
+/*< private >
+ * gtk_constraint_expression_plus_constant:
+ * @expression: a #GtkConstraintExpression
+ * @constant: a constant value
+ *
+ * Adds a @constant value to the @expression.
+ *
+ * This is the equivalent of creating a new #GtkConstraintExpression for
+ * the @constant and calling gtk_constraint_expression_add_expression().
+ *
+ * Returns: the @expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_plus_constant (GtkConstraintExpression *expression,
+                                         double constant)
+{
+  GtkConstraintExpression *e;
+
+  e = gtk_constraint_expression_new (constant);
+  gtk_constraint_expression_add_expression (expression, e, 1.0, NULL, NULL);
+  gtk_constraint_expression_unref (e);
+
+  return expression;
+}
+
+/*< private >
+ * gtk_constraint_expression_minus_constant:
+ * @expression: a #GtkConstraintExpression
+ * @constant: a constant value
+ *
+ * Removes a @constant value from the @expression.
+ *
+ * This is the equivalent of creating a new #GtkConstraintExpression for
+ * the inverse of @constant and calling gtk_constraint_expression_add_expression().
+ *
+ * Returns: the @expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_minus_constant (GtkConstraintExpression *expression,
+                                          double constant)
+{
+  return gtk_constraint_expression_plus_constant (expression, constant * -1.0);
+}
+
+/*< private >
+ * gtk_constraint_expression_plus_variable:
+ * @expression: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable
+ *
+ * Adds a @variable to the @expression.
+ *
+ * Returns: the @expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_plus_variable (GtkConstraintExpression *expression,
+                                         GtkConstraintVariable *variable)
+{
+  GtkConstraintExpression *e;
+
+  e = gtk_constraint_expression_new_from_variable (variable);
+  gtk_constraint_expression_add_expression (expression, e, 1.0, NULL, NULL);
+  gtk_constraint_expression_unref (e);
+
+  return expression;
+}
+
+/*< private >
+ * gtk_constraint_expression_minus_variable:
+ * @expression: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable
+ *
+ * Subtracts a @variable from the @expression.
+ *
+ * Returns: the @expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_minus_variable (GtkConstraintExpression *expression,
+                                          GtkConstraintVariable *variable)
+{
+  GtkConstraintExpression *e;
+
+  e = gtk_constraint_expression_new_from_variable (variable);
+  gtk_constraint_expression_add_expression (expression, e, -1.0, NULL, NULL);
+  gtk_constraint_expression_unref (e);
+
+  return expression;
+}
+
+/*< private >
+ * gtk_constraint_expression_multiply_by:
+ * @expression: a #GtkConstraintExpression
+ * @factor: the multiplication factor
+ *
+ * Multiplies the constant part and the coefficient of all terms
+ * in @expression with the given @factor.
+ *
+ * Returns: the @expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_multiply_by (GtkConstraintExpression *expression,
+                                       double factor)
+{
+  GHashTableIter iter;
+  gpointer value_p;
+
+  expression->constant *= factor;
+
+  if (expression->terms == NULL)
+    return expression;
+
+  g_hash_table_iter_init (&iter, expression->terms);
+  while (g_hash_table_iter_next (&iter, NULL, &value_p))
+    {
+      Term *t = value_p;
+
+      t->coefficient *= factor;
+    }
+
+  return expression;
+}
+
+/*< private >
+ * gtk_constraint_expression_divide_by:
+ * @expression: a #GtkConstraintExpression
+ * @factor: the division factor
+ *
+ * Divides the constant part and the coefficient of all terms
+ * in @expression by the given @factor.
+ *
+ * Returns: the @expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_divide_by (GtkConstraintExpression *expression,
+                                     double factor)
+{
+  if (G_APPROX_VALUE (factor, 0.0, 0.001))
+    return expression;
+
+  return gtk_constraint_expression_multiply_by (expression, 1.0 / factor);
+}
+
+/*< private >
+ * gtk_constraint_expression_new_subject:
+ * @expression: a #GtkConstraintExpression
+ * @subject: a #GtkConstraintVariable part of @expression
+ *
+ * Modifies @expression to have a new @subject.
+ *
+ * A #GtkConstraintExpression is a linear expression in the form of
+ * `@expression = 0`. If @expression contains @subject, for instance:
+ *
+ * |[
+ *   c + (a × @subject) + (a1 × v1) + … + (an × vn) = 0
+ * ]|
+ *
+ * this function will make @subject the new subject of the expression:
+ *
+ * |[
+ *   subject = - (c / a) - ((a1 / a) × v1) - … - ((an / a) × vn) = 0
+ * ]|
+ *
+ * The term @subject is removed from the @expression.
+ *
+ * Returns: the reciprocal of the coefficient of @subject, so we
+ *   can use this function in gtk_constraint_expression_change_subject()
+ */
+double
+gtk_constraint_expression_new_subject (GtkConstraintExpression *expression,
+                                       GtkConstraintVariable *subject)
+{
+  double reciprocal = 1.0;
+  Term *term;
+
+  g_assert (!gtk_constraint_expression_is_constant (expression));
+
+  term = g_hash_table_lookup (expression->terms, subject);
+  g_assert (term != NULL);
+  g_assert (!G_APPROX_VALUE (term->coefficient, 0.0, 0.001));
+
+  reciprocal = 1.0 / term->coefficient;
+
+  gtk_constraint_expression_remove_term (expression, subject);
+  gtk_constraint_expression_multiply_by (expression, -reciprocal);
+
+  return reciprocal;
+}
+
+/*< private >
+ * gtk_constraint_expression_change_subject:
+ * @expression: a #GtkConstraintExpression
+ * @old_subject: the old subject #GtkConstraintVariable of @expression
+ * @new_subject: the new subject #GtkConstraintVariable of @expression
+ *
+ * Turns an @expression in the form of:
+ *
+ * |[
+ *   old_subject = c + (a × new_subject) + (a1 × v1) + … + (an × vn)
+ * ]|
+ *
+ * into the form of:
+ *
+ * |[
+ *   new_subject = -c / a + old_subject / a - ((a1 / a) × v1) - … - ((an / a) × vn)
+ * ]|
+ *
+ * Which means resolving @expression for @new_subject.
+ */
+void
+gtk_constraint_expression_change_subject (GtkConstraintExpression *expression,
+                                          GtkConstraintVariable *old_subject,
+                                          GtkConstraintVariable *new_subject)
+{
+  double reciprocal;
+
+  g_return_if_fail (expression != NULL);
+  g_return_if_fail (old_subject != NULL);
+  g_return_if_fail (new_subject != NULL);
+
+  reciprocal = gtk_constraint_expression_new_subject (expression, new_subject);
+  gtk_constraint_expression_set_variable (expression, old_subject, reciprocal);
+}
+
+/*< private >
+ * gtk_constraint_expression_get_coefficient:
+ * @expression: a #GtkConstraintExpression
+ * @variable: a #GtkConstraintVariable
+ *
+ * Retrieves the coefficient of the term for @variable inside @expression.
+ *
+ * Returns: the coefficient of @variable
+ */
+double
+gtk_constraint_expression_get_coefficient (GtkConstraintExpression *expression,
+                                           GtkConstraintVariable *variable)
+{
+  const Term *term;
+
+  g_return_val_if_fail (expression != NULL, 0.0);
+  g_return_val_if_fail (variable != NULL, 0.0);
+
+  if (expression->terms == NULL)
+    return 0.0;
+
+  term = g_hash_table_lookup (expression->terms, variable);
+  if (term == NULL)
+    return 0.0;
+
+  return term->coefficient;
+}
+
+/*< private >
+ * gtk_constraint_expression_substitute_out:
+ * @expression: a #GtkConstraintExpression
+ * @out_var: the variable to replace
+ * @expr: the expression used to replace @out_var
+ * @subject: (nullable): a #GtkConstraintVariable
+ * @solver: (nullable): a #GtkConstraintSolver
+ *
+ * Replaces every term containing @out_var inside @expression with @expr.
+ *
+ * If @solver is not %NULL, this function will notify the #GtkConstraintSolver
+ * for every variable added to or removed from @expression.
+ */
+void
+gtk_constraint_expression_substitute_out (GtkConstraintExpression *expression,
+                                          GtkConstraintVariable *out_var,
+                                          GtkConstraintExpression *expr,
+                                          GtkConstraintVariable *subject,
+                                          GtkConstraintSolver *solver)
+{
+  double multiplier;
+  Term *iter;
+
+  if (expression->terms == NULL)
+    return;
+
+  multiplier = gtk_constraint_expression_get_coefficient (expression, out_var);
+  gtk_constraint_expression_remove_term (expression, out_var);
+
+  expression->constant = expression->constant + multiplier * expr->constant;
+
+  iter = expr->first_term;
+  while (iter != NULL)
+    {
+      GtkConstraintVariable *clv = iter->variable;
+      double coeff = iter->coefficient;
+      Term *next = iter->next;
+
+      if (expression->terms != NULL &&
+          g_hash_table_contains (expression->terms, clv))
+        {
+          double old_coefficient = gtk_constraint_expression_get_coefficient (expression, clv);
+          double new_coefficient = old_coefficient + multiplier * coeff;
+
+          if (G_APPROX_VALUE (new_coefficient, 0.0, 0.001))
+            {
+              if (solver != NULL)
+                gtk_constraint_solver_note_removed_variable (solver, clv, subject);
+
+              gtk_constraint_expression_remove_term (expression, clv);
+            }
+          else
+            gtk_constraint_expression_set_variable (expression, clv, new_coefficient);
+        }
+      else
+        {
+          gtk_constraint_expression_set_variable (expression, clv, multiplier * coeff);
+
+          if (solver != NULL)
+            gtk_constraint_solver_note_added_variable (solver, clv, subject);
+        }
+
+      iter = next;
+    }
+}
+
+/*< private >
+ * gtk_constraint_expression_get_pivotable_variable:
+ * @expression: a #GtkConstraintExpression
+ *
+ * Retrieves the first #GtkConstraintVariable in @expression that
+ * is marked as pivotable.
+ *
+ * Returns: (transfer none) (nullable): a #GtkConstraintVariable
+ */
+GtkConstraintVariable *
+gtk_constraint_expression_get_pivotable_variable (GtkConstraintExpression *expression)
+{
+  Term *iter;
+
+  if (expression->terms == NULL)
+    {
+      g_critical ("Expression %p is a constant", expression);
+      return NULL;
+    }
+
+  iter = expression->first_term;
+  while (iter != NULL)
+    {
+      Term *next = iter->next;
+
+      if (gtk_constraint_variable_is_pivotable (iter->variable))
+        return iter->variable;
+
+      iter = next;
+    }
+
+  return NULL;
+}
+
+/*< private >
+ * gtk_constraint_expression_to_string:
+ * @expression: a #GtkConstraintExpression
+ *
+ * Creates a string containing @expression.
+ *
+ * This function is only useful for debugging.
+ *
+ * Returns: (transfer full): a string containing the given expression
+ */
+char *
+gtk_constraint_expression_to_string (const GtkConstraintExpression *expression)
+{
+  gboolean needs_plus = FALSE;
+  GString *buf;
+  Term *iter;
+
+  if (expression == NULL)
+    return g_strdup ("<null>");
+
+  buf = g_string_new (NULL);
+
+  if (!G_APPROX_VALUE (expression->constant, 0.0, 0.001))
+    {
+      g_string_append_printf (buf, "%g", expression->constant);
+
+      if (expression->terms != NULL)
+        needs_plus = TRUE;
+    }
+
+  if (expression->terms == NULL)
+    return g_string_free (buf, FALSE);
+
+  iter = expression->first_term;
+  while (iter != NULL)
+    {
+      char *str = gtk_constraint_variable_to_string (iter->variable);
+      Term *next = iter->next;
+
+      if (needs_plus)
+        g_string_append (buf, " + ");
+
+      if (G_APPROX_VALUE (iter->coefficient, 1.0, 0.001))
+        g_string_append_printf (buf, "%s", str);
+      else
+        g_string_append_printf (buf, "(%g * %s)", iter->coefficient, str);
+
+      g_free (str);
+
+      if (!needs_plus)
+        needs_plus = TRUE;
+
+      iter = next;
+    }
+
+  return g_string_free (buf, FALSE);
+}
+
+/* Keep in sync with GtkConstraintExpressionIter */
+typedef struct {
+  GtkConstraintExpression *expression;
+  Term *current;
+  gint64 age;
+} RealExpressionIter;
+
+#define REAL_EXPRESSION_ITER(i) ((RealExpressionIter *) (i))
+
+/*< private >
+ * gtk_constraint_expression_iter_init:
+ * @iter: a #GtkConstraintExpressionIter
+ * @expression: a #GtkConstraintExpression
+ *
+ * Initializes an iterator over @expression.
+ */
+void
+gtk_constraint_expression_iter_init (GtkConstraintExpressionIter *iter,
+                                     GtkConstraintExpression *expression)
+{
+  RealExpressionIter *riter = REAL_EXPRESSION_ITER (iter);
+
+  riter->expression = expression;
+  riter->current = NULL;
+  riter->age = expression->age;
+}
+
+/*< private >
+ * gtk_constraint_expression_iter_next:
+ * @iter: a valid #GtkConstraintExpressionIter
+ * @variable: (out): the variable of the next term
+ * @coefficient: (out): the coefficient of the next term
+ *
+ * Moves the given #GtkConstraintExpressionIter forwards to the next
+ * term in the expression, starting from the first term.
+ *
+ * Returns: %TRUE if the iterator was moved, and %FALSE if the iterator
+ *   has reached the end of the terms of the expression
+ */
+gboolean
+gtk_constraint_expression_iter_next (GtkConstraintExpressionIter *iter,
+                                     GtkConstraintVariable **variable,
+                                     double *coefficient)
+{
+  RealExpressionIter *riter = REAL_EXPRESSION_ITER (iter);
+
+  g_assert (riter->age == riter->expression->age);
+
+  if (riter->current == NULL)
+    riter->current = riter->expression->first_term;
+  else
+    riter->current = riter->current->next;
+
+  if (riter->current != NULL)
+    {
+      *coefficient = riter->current->coefficient;
+      *variable = riter->current->variable;
+    }
+
+  return riter->current != NULL;
+}
+
+/*< private >
+ * gtk_constraint_expression_iter_prev:
+ * @iter: a valid #GtkConstraintExpressionIter
+ * @variable: (out): the variable of the previous term
+ * @coefficient: (out): the coefficient of the previous term
+ *
+ * Moves the given #GtkConstraintExpressionIter backwards to the previous
+ * term in the expression, starting from the last term.
+ *
+ * Returns: %TRUE if the iterator was moved, and %FALSE if the iterator
+ *   has reached the beginning of the terms of the expression
+ */
+gboolean
+gtk_constraint_expression_iter_prev (GtkConstraintExpressionIter *iter,
+                                     GtkConstraintVariable **variable,
+                                     double *coefficient)
+{
+  RealExpressionIter *riter = REAL_EXPRESSION_ITER (iter);
+
+  g_assert (riter->age == riter->expression->age);
+
+  if (riter->current == NULL)
+    riter->current = riter->expression->last_term;
+  else
+    riter->current = riter->current->prev;
+
+  if (riter->current != NULL)
+    {
+      *coefficient = riter->current->coefficient;
+      *variable = riter->current->variable;
+    }
+
+  return riter->current != NULL;
+}
+
+typedef enum {
+  BUILDER_OP_NONE,
+  BUILDER_OP_PLUS,
+  BUILDER_OP_MINUS,
+  BUILDER_OP_MULTIPLY,
+  BUILDER_OP_DIVIDE
+} BuilderOpType;
+
+typedef struct
+{
+  GtkConstraintExpression *expression;
+  GtkConstraintSolver *solver;
+  int op;
+} RealExpressionBuilder;
+
+#define REAL_EXPRESSION_BUILDER(b) ((RealExpressionBuilder *) (b))
+
+/*< private >
+ * gtk_constraint_expression_builder_init:
+ * @builder: a #GtkConstraintExpressionBuilder
+ * @solver: a #GtkConstraintSolver
+ *
+ * Initializes the given #GtkConstraintExpressionBuilder for the
+ * given #GtkConstraintSolver.
+ *
+ * You can use the @builder to construct expressions to be added to the
+ * @solver, in the form of constraints.
+ *
+ * A typical use is:
+ *
+ * |[<!-- language="C" -->
+ *   GtkConstraintExpressionBuilder builder;
+ *
+ *   // "solver" is set in another part of the code
+ *   gtk_constraint_expression_builder_init (&builder, solver);
+ *
+ *   // "width" is set in another part of the code
+ *   gtk_constraint_expression_builder_term (&builder, width);
+ *   gtk_constraint_expression_builder_divide_by (&builder);
+ *   gtk_constraint_expression_builder_constant (&builder, 2.0);
+ *
+ *   // "left" is set in another part of the code
+ *   gtk_constraint_expression_builder_plus (&builder);
+ *   gtk_constraint_expression_builder_term (&builder, left);
+ *
+ *   // "expr" now contains the following expression:
+ *   //     width / 2.0 + left
+ *   GtkConstraintExpression *expr =
+ *     gtk_constraint_expression_builder_finish (&builder);
+ *
+ *   // The builder is inert, and can be re-used by calling
+ *   // gtk_constraint_expression_builder_init() again.
+ * ]|
+ */
+void
+gtk_constraint_expression_builder_init (GtkConstraintExpressionBuilder *builder,
+                                        GtkConstraintSolver *solver)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  rbuilder->solver = solver;
+  rbuilder->expression = gtk_constraint_expression_new (0);
+  rbuilder->op = BUILDER_OP_NONE;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_term:
+ * @builder: a #GtkConstraintExpressionBuilder
+ * @term: a #GtkConstraintVariable
+ *
+ * Adds a variable @term to the @builder.
+ */
+void
+gtk_constraint_expression_builder_term (GtkConstraintExpressionBuilder *builder,
+                                        GtkConstraintVariable *term)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+  GtkConstraintExpression *expr;
+
+  expr = gtk_constraint_expression_new_from_variable (term);
+
+  switch (rbuilder->op)
+    {
+    case BUILDER_OP_NONE:
+      g_clear_pointer (&rbuilder->expression, gtk_constraint_expression_unref);
+      rbuilder->expression = g_steal_pointer (&expr);
+      break;
+
+    case BUILDER_OP_PLUS:
+      gtk_constraint_expression_add_expression (rbuilder->expression,
+                                                expr, 1.0,
+                                                NULL,
+                                                NULL);
+      gtk_constraint_expression_unref (expr);
+      break;
+
+    case BUILDER_OP_MINUS:
+      gtk_constraint_expression_add_expression (rbuilder->expression,
+                                                expr, -1.0,
+                                                NULL,
+                                                NULL);
+      gtk_constraint_expression_unref (expr);
+      break;
+
+    default:
+      break;
+    }
+
+  rbuilder->op = BUILDER_OP_NONE;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_plus:
+ * @builder: a #GtkConstraintExpressionBuilder
+ *
+ * Adds a plus operator to the @builder.
+ */
+void
+gtk_constraint_expression_builder_plus (GtkConstraintExpressionBuilder *builder)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  rbuilder->op = BUILDER_OP_PLUS;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_minus:
+ * @builder: a #GtkConstraintExpressionBuilder
+ *
+ * Adds a minus operator to the @builder.
+ */
+void
+gtk_constraint_expression_builder_minus (GtkConstraintExpressionBuilder *builder)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  rbuilder->op = BUILDER_OP_MINUS;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_divide_by:
+ * @builder: a #GtkConstraintExpressionBuilder
+ *
+ * Adds a division operator to the @builder.
+ */
+void
+gtk_constraint_expression_builder_divide_by (GtkConstraintExpressionBuilder *builder)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  rbuilder->op = BUILDER_OP_DIVIDE;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_multiply_by:
+ * @builder: a #GtkConstraintExpressionBuilder
+ *
+ * Adds a multiplication operator to the @builder.
+ */
+void
+gtk_constraint_expression_builder_multiply_by (GtkConstraintExpressionBuilder *builder)
+
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  rbuilder->op = BUILDER_OP_MULTIPLY;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_constant:
+ * @builder: a #GtkConstraintExpressionBuilder
+ * @value: a constant value
+ *
+ * Adds a constant value to the @builder.
+ */
+void
+gtk_constraint_expression_builder_constant (GtkConstraintExpressionBuilder *builder,
+                                            double value)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  switch (rbuilder->op)
+    {
+    case BUILDER_OP_NONE:
+      gtk_constraint_expression_set_constant (rbuilder->expression, value);
+      break;
+
+    case BUILDER_OP_PLUS:
+      gtk_constraint_expression_plus_constant (rbuilder->expression, value);
+      break;
+
+    case BUILDER_OP_MINUS:
+      gtk_constraint_expression_minus_constant (rbuilder->expression, value);
+      break;
+
+    case BUILDER_OP_MULTIPLY:
+      gtk_constraint_expression_multiply_by (rbuilder->expression, value);
+      break;
+
+    case BUILDER_OP_DIVIDE:
+      gtk_constraint_expression_divide_by (rbuilder->expression, value);
+      break;
+
+    default:
+      break;
+    }
+
+  rbuilder->op = BUILDER_OP_NONE;
+}
+
+/*< private >
+ * gtk_constraint_expression_builder_finish:
+ * @builder: a #GtkConstraintExpressionBuilder
+ *
+ * Closes the given expression builder, and returns the expression.
+ *
+ * You can only call this function once.
+ *
+ * Returns: (transfer full): the built expression
+ */
+GtkConstraintExpression *
+gtk_constraint_expression_builder_finish (GtkConstraintExpressionBuilder *builder)
+{
+  RealExpressionBuilder *rbuilder = REAL_EXPRESSION_BUILDER (builder);
+
+  rbuilder->solver = NULL;
+  rbuilder->op = BUILDER_OP_NONE;
+
+  return g_steal_pointer (&rbuilder->expression);
+}
+
+/* }}} */
diff --git a/gtk/gtkconstraintexpressionprivate.h b/gtk/gtkconstraintexpressionprivate.h
new file mode 100644
index 0000000000..1d42d26883
--- /dev/null
+++ b/gtk/gtkconstraintexpressionprivate.h
@@ -0,0 +1,276 @@
+/* gtkconstraintequationprivate.h: Constraint expressions and variables
+ * Copyright 2019  GNOME Foundation
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Author: Emmanuele Bassi
+ */
+
+#pragma once
+
+#include "gtkconstrainttypesprivate.h"
+
+G_BEGIN_DECLS
+
+GtkConstraintVariable *
+gtk_constraint_variable_new (const char *name);
+
+GtkConstraintVariable *
+gtk_constraint_variable_new_dummy (const char *name);
+
+GtkConstraintVariable *
+gtk_constraint_variable_new_objective (const char *name);
+
+GtkConstraintVariable *
+gtk_constraint_variable_new_slack (const char *name);
+
+GtkConstraintVariable *
+gtk_constraint_variable_ref (GtkConstraintVariable *variable);
+
+void
+gtk_constraint_variable_unref (GtkConstraintVariable *variable);
+
+void
+gtk_constraint_variable_set_value (GtkConstraintVariable *variable,
+                                   double value);
+
+double
+gtk_constraint_variable_get_value (const GtkConstraintVariable *variable);
+
+void
+gtk_constraint_variable_set_prefix (GtkConstraintVariable *variable,
+                                    const char *prefix);
+
+char *
+gtk_constraint_variable_to_string (const GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_variable_is_external (const GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_variable_is_pivotable (const GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_variable_is_restricted (const GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_variable_is_dummy (const GtkConstraintVariable *variable);
+
+typedef struct {
+  GtkConstraintVariable *first;
+  GtkConstraintVariable *second;
+} GtkConstraintVariablePair;
+
+GtkConstraintVariablePair *
+gtk_constraint_variable_pair_new (GtkConstraintVariable *first,
+                                  GtkConstraintVariable *second);
+
+void
+gtk_constraint_variable_pair_free (GtkConstraintVariablePair *pair);
+
+typedef struct _GtkConstraintVariableSet        GtkConstraintVariableSet;
+
+GtkConstraintVariableSet *
+gtk_constraint_variable_set_new (void);
+
+void
+gtk_constraint_variable_set_free (GtkConstraintVariableSet *set);
+
+gboolean
+gtk_constraint_variable_set_add (GtkConstraintVariableSet *set,
+                                 GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_variable_set_remove (GtkConstraintVariableSet *set,
+                                    GtkConstraintVariable *variable);
+
+int
+gtk_constraint_variable_set_size (GtkConstraintVariableSet *set);
+
+typedef struct {
+  /*< private >*/
+  gpointer dummy1;
+  gpointer dummy2;
+  gint64 dummy3;
+} GtkConstraintVariableSetIter;
+
+void
+gtk_constraint_variable_set_iter_init (GtkConstraintVariableSetIter *iter,
+                                       GtkConstraintVariableSet *set);
+
+gboolean
+gtk_constraint_variable_set_iter_next (GtkConstraintVariableSetIter *iter,
+                                       GtkConstraintVariable **variable_p);
+
+GtkConstraintExpression *
+gtk_constraint_expression_new (double constant);
+
+GtkConstraintExpression *
+gtk_constraint_expression_new_from_variable (GtkConstraintVariable *variable);
+
+GtkConstraintExpression *
+gtk_constraint_expression_ref (GtkConstraintExpression *expression);
+
+void
+gtk_constraint_expression_unref (GtkConstraintExpression *expression);
+
+GtkConstraintExpression *
+gtk_constraint_expression_clone (GtkConstraintExpression *expression);
+
+void
+gtk_constraint_expression_set_constant (GtkConstraintExpression *expression,
+                                        double constant);
+double
+gtk_constraint_expression_get_constant (const GtkConstraintExpression *expression);
+
+gboolean
+gtk_constraint_expression_is_constant (const GtkConstraintExpression *expression);
+
+void
+gtk_constraint_expression_add_expression (GtkConstraintExpression *a_expr,
+                                          GtkConstraintExpression *b_expr,
+                                          double n,
+                                          GtkConstraintVariable *subject,
+                                          GtkConstraintSolver *solver);
+
+void
+gtk_constraint_expression_add_variable (GtkConstraintExpression *expression,
+                                        GtkConstraintVariable *variable,
+                                        double coefficient,
+                                        GtkConstraintVariable *subject,
+                                        GtkConstraintSolver *solver);
+
+void
+gtk_constraint_expression_remove_variable (GtkConstraintExpression *expression,
+                                           GtkConstraintVariable *variable);
+
+void
+gtk_constraint_expression_set_variable (GtkConstraintExpression *expression,
+                                        GtkConstraintVariable *variable,
+                                        double coefficient);
+
+double
+gtk_constraint_expression_get_coefficient (GtkConstraintExpression *expression,
+                                           GtkConstraintVariable *variable);
+
+char *
+gtk_constraint_expression_to_string (const GtkConstraintExpression *expression);
+
+double
+gtk_constraint_expression_new_subject (GtkConstraintExpression *expression,
+                                       GtkConstraintVariable *subject);
+
+void
+gtk_constraint_expression_change_subject (GtkConstraintExpression *expression,
+                                          GtkConstraintVariable *old_subject,
+                                          GtkConstraintVariable *new_subject);
+
+void
+gtk_constraint_expression_substitute_out (GtkConstraintExpression *expression,
+                                          GtkConstraintVariable *out_var,
+                                          GtkConstraintExpression *expr,
+                                          GtkConstraintVariable *subject,
+                                          GtkConstraintSolver *solver);
+
+GtkConstraintVariable *
+gtk_constraint_expression_get_pivotable_variable (GtkConstraintExpression *expression);
+
+GtkConstraintExpression *
+gtk_constraint_expression_plus_constant (GtkConstraintExpression *expression,
+                                         double constant);
+
+GtkConstraintExpression *
+gtk_constraint_expression_minus_constant (GtkConstraintExpression *expression,
+                                          double constant);
+
+GtkConstraintExpression *
+gtk_constraint_expression_plus_variable (GtkConstraintExpression *expression,
+                                         GtkConstraintVariable *variable);
+
+GtkConstraintExpression *
+gtk_constraint_expression_minus_variable (GtkConstraintExpression *expression,
+                                          GtkConstraintVariable *variable);
+
+GtkConstraintExpression *
+gtk_constraint_expression_multiply_by (GtkConstraintExpression *expression,
+                                       double factor);
+
+GtkConstraintExpression *
+gtk_constraint_expression_divide_by (GtkConstraintExpression *expression,
+                                     double factor);
+
+struct _GtkConstraintExpressionBuilder
+{
+  /*< private >*/
+  gpointer dummy1;
+  gpointer dummy2;
+  int dummy3;
+};
+
+void
+gtk_constraint_expression_builder_init (GtkConstraintExpressionBuilder *builder,
+                                        GtkConstraintSolver *solver);
+
+void
+gtk_constraint_expression_builder_term (GtkConstraintExpressionBuilder *builder,
+                                        GtkConstraintVariable *term);
+
+void
+gtk_constraint_expression_builder_plus (GtkConstraintExpressionBuilder *builder);
+
+void
+gtk_constraint_expression_builder_minus (GtkConstraintExpressionBuilder *builder);
+
+void
+gtk_constraint_expression_builder_divide_by (GtkConstraintExpressionBuilder *builder);
+
+void
+gtk_constraint_expression_builder_multiply_by (GtkConstraintExpressionBuilder *builder);
+
+void
+gtk_constraint_expression_builder_constant (GtkConstraintExpressionBuilder *builder,
+                                            double value);
+
+GtkConstraintExpression *
+gtk_constraint_expression_builder_finish (GtkConstraintExpressionBuilder *builder) G_GNUC_WARN_UNUSED_RESULT;
+
+/*< private >
+ * GtkConstraintExpressionIter:
+ *
+ * An iterator object for terms inside a #GtkConstraintExpression.
+ */
+typedef struct {
+  /*< private >*/
+  gpointer dummy1;
+  gpointer dummy2;
+  gint64 dummy3;
+} GtkConstraintExpressionIter;
+
+void
+gtk_constraint_expression_iter_init (GtkConstraintExpressionIter *iter,
+                                     GtkConstraintExpression *equation);
+
+gboolean
+gtk_constraint_expression_iter_next (GtkConstraintExpressionIter *iter,
+                                     GtkConstraintVariable **variable,
+                                     double *coefficient);
+
+gboolean
+gtk_constraint_expression_iter_prev (GtkConstraintExpressionIter *iter,
+                                     GtkConstraintVariable **variable,
+                                     double *coefficient);
+
+G_END_DECLS
diff --git a/gtk/gtkconstraintsolver.c b/gtk/gtkconstraintsolver.c
new file mode 100644
index 0000000000..411b006957
--- /dev/null
+++ b/gtk/gtkconstraintsolver.c
@@ -0,0 +1,2234 @@
+/* gtkconstraintsolver.c: Constraint solver based on the Cassowary method
+ * Copyright 2019  GNOME Foundation
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Author: Emmanuele Bassi
+ */
+
+/*< private >
+ * SECTION: gtkconstraintsolver
+ * @Title: GtkConstraintSolver
+ * @Short_description: An incremental solver for a tableau of linear equations
+ *
+ * GtkConstraintSolver is an object that encodes constraints into a tableau
+ * of linear equations and solves them, using an incremental optimization
+ * algorithm known as the "Cassowary Linear Arithmetic Constraint Solving
+ * Algorithm" (Badros, Borning & Stuckey 2001).
+ *
+ * Each constraint is expressed as a linear equation, whose terms are variables
+ * containing widget attributes like the width, height, or position; the simplex
+ * solver takes all the constraints and incrementally optimizes the tableau to
+ * replace known terms; additionally, the algorithm will try to assign a value
+ * to all remaining variables in order to satisfy the various constraints.
+ *
+ * Each constraint is given a "strength", which determines whether satisfying
+ * the constraint is required in order to solve the tableau or not.
+ *
+ * A typical example of GtkConstraintSolver use is solving the following
+ * system of constraints:
+ *
+ *  - [required] right = left + 10
+ *  - [required] right ≤ 100
+ *  - [required] middle = left + right / 2
+ *  - [required] left ≥ 0
+ *
+ * Once we create a GtkConstraintSolver instance, we need to create the
+ * various variables and expressions that represent the values we want to
+ * compute and the constraints we wish to impose on the solutions:
+ *
+ * |[
+ *   GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+ *
+ *   // Our variables
+ *   GtkConstraintVariable *left =
+ *     gtk_constraint_solver_create_variable (solver, NULL, "left", 0.0);
+ *   GtkConstraintVariable *middle =
+ *     gtk_constraint_solver_create_variable (solver, NULL, "middle", 0.0);
+ *   GtkConstraintVariable *right  =
+ *     gtk_constraint_solver_create_variable (solver, NULL, "right", 0.0);
+ *
+ *   // Our constraints
+ *   GtkConstraintExpressionBuilder builder;
+ *   GtkConstraintExpression *e;
+ *
+ *   // right = left + 10
+ *   gtk_constraint_expression_builder_init (&builder, solver);
+ *   gtk_constraint_expression_builder_term (&builder, left);
+ *   gtk_constraint_expression_builder_plus (&builder);
+ *   gtk_constraint_expression_builder_constant (&builder, 10.0);
+ *   e = gtk_constraint_expression_builder_finish (&builder);
+ *   gtk_constraint_solver_add_constraint (solver,
+ *                                         right, GTK_CONSTRAINT_RELATION_EQ, e,
+ *                                         GTK_CONSTRAINT_WEIGHT_REQUIRED);
+ *
+ *   // right ≤ 100
+ *   gtk_constraint_expression_builder_constant (&builder, 100.0);
+ *   e = gtk_constraint_expression_builder_finish (&builder);
+ *   gtk_constraint_solver_add_constraint (solver,
+ *                                         right, GTK_CONSTRAINT_RELATION_LE, e,
+ *                                         GTK_CONSTRAINT_WEIGHT_REQUIRED);
+ *
+ *   // middle = (left + right) / 2
+ *   gtk_constraint_expression_builder_term (&builder, left);
+ *   gtk_constraint_expression_builder_plus (&builder)
+ *   gtk_constraint_expression_builder_term (&builder, right);
+ *   gtk_constraint_expression_builder_divide_by (&builder);
+ *   gtk_constraint_expression_builder_constant (&builder, 2.0);
+ *   e = gtk_constraint_expression_builder_finish (&builder);
+ *   gtk_constraint_solver_add_constraint (solver
+ *                                         middle, GTK_CONSTRAINT_RELATION_EQ, e,
+ *                                         GTK_CONSTRAINT_WEIGHT_REQUIRED);
+ *
+ *   // left ≥ 0
+ *   gtk_constraint_expression_builder_constant (&builder, 0.0);
+ *   e = gtk_constraint_expression_builder_finish (&builder);
+ *   gtk_constraint_solver_add_constraint (solver,
+ *                                         left, GTK_CONSTRAINT_RELATION_GE, e,
+ *                                         GTK_CONSTRAINT_WEIGHT_REQUIRED);
+ * ]|
+ *
+ * Now that we have all our constraints in place, suppose we wish to find
+ * the values of `left` and `right` if we specify the value of `middle`. In
+ * order to do that, we need to add an additional "stay" constraint, i.e.
+ * a constraint that tells the solver to optimize for the solution that keeps
+ * the variable in place:
+ *
+ * |[
+ *   // Set the value first
+ *   gtk_constraint_variable_set_value (middle, 45.0);
+ *   // and then add the stay constraint, with a weak weight
+ *   gtk_constraint_solver_add_stay_variable (solver, middle, GTK_CONSTRAINT_WEIGHT_WEAK);
+ * ]|
+ *
+ * GtkConstraintSolver incrementally solves the system every time a constraint
+ * is added or removed, so it's possible to query the values of the variables
+ * immediately afterward:
+ *
+ * |[
+ *   double left_val = gtk_constraint_variable_get_value (left);
+ *   double right_val = gtk_constraint_variable_get_value (right);
+ *   double middle_val = gtk_constraint_variable_get_value (middle);
+ *
+ *   // These are the values computed by the solver:
+ *   g_assert_cmpfloat_with_epsilon (left_val, 40.0, 0.001);
+ *   g_assert_cmpfloat_with_epsilon (middle_val, 45.0, 0.001);
+ *   g_assert_cmpfloat_with_epsilon (right_val, 50.0, 0.001);
+ * ]|
+ *
+ * As you can see:
+ *
+ *  - the middle value hasn't changed
+ *  - the left value is ≥ 0
+ *  - the right value is ≤ 100
+ *  - the right value is left + 10
+ *  - the middle value is (left + right) / 2.0
+ *
+ * For more information about the Cassowary constraint solving algorithm and
+ * toolkit, see the following papers:
+ *
+ *  - Badros G & Borning A, 1998, 'Cassowary Linear Arithmetic Constraint
+ *    Solving Algorithm: Interface and Implementation', Technical Report
+ *    UW-CSE-98-06-04, June 1998 (revised July 1999)
+ *    https://constraints.cs.washington.edu/cassowary/cassowary-tr.pdf
+ *  - Badros G, Borning A & Stuckey P, 2001, 'Cassowary Linear Arithmetic
+ *    Constraint Solving Algorithm', ACM Transactions on Computer-Human
+ *    Interaction, vol. 8 no. 4, December 2001, pages 267-306
+ *    https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf
+ *
+ * The following implementation is based on these projects:
+ *
+ *  - the original [C++ implementation](https://sourceforge.net/projects/cassowary/)
+ *  - the JavaScript port [Cassowary.js](https://github.com/slightlyoff/cassowary.js)
+ *  - the Python port [Cassowary](https://github.com/pybee/cassowary)
+ */
+
+#include "config.h"
+
+#include "gtkconstraintsolverprivate.h"
+#include "gtkconstraintexpressionprivate.h"
+
+#include "gtkdebug.h"
+
+#include <glib.h>
+#include <string.h>
+#include <math.h>
+#include <float.h>
+
+struct _GtkConstraintRef
+{
+  /* The constraint's normal form inside the solver:
+   *
+   *   x - (y × coefficient + constant) = 0
+   *
+   * We only use equalities, and replace inequalities with slack
+   * variables.
+   */
+  GtkConstraintExpression *expression;
+
+  /* A constraint variable, only used by stay and edit constraints */
+  GtkConstraintVariable *variable;
+
+  /* The original relation used when creating the constraint */
+  GtkConstraintRelation relation;
+
+  /* The weight, or strength, of the constraint */
+  double weight;
+
+  GtkConstraintSolver *solver;
+
+  guint is_edit : 1;
+  guint is_stay : 1;
+};
+
+typedef struct {
+  GtkConstraintRef *constraint;
+
+  GtkConstraintVariable *eplus;
+  GtkConstraintVariable *eminus;
+
+  double prev_constant;
+} EditInfo;
+
+typedef struct {
+  GtkConstraintRef *constraint;
+} StayInfo;
+
+struct _GtkConstraintSolver
+{
+  GObject parent_instance;
+
+  /* HashTable<Variable, VariableSet>; owns keys and values */
+  GHashTable *columns;
+  /* HashTable<Variable, Expression>; owns keys and values */
+  GHashTable *rows;
+
+  /* Set<Variable>; does not own keys */
+  GHashTable *external_rows;
+  /* Set<Variable>; does not own keys */
+  GHashTable *external_parametric_vars;
+
+  /* Vec<Variable> */
+  GPtrArray *infeasible_rows;
+  /* Vec<VariablePair>; owns the pair */
+  GPtrArray *stay_error_vars;
+
+  /* HashTable<Constraint, VariableSet>; owns the set */
+  GHashTable *error_vars;
+  /* HashTable<Constraint, Variable> */
+  GHashTable *marker_vars;
+
+  /* HashTable<Variable, EditInfo>; does not own keys, but owns values */
+  GHashTable *edit_var_map;
+  /* HashTable<Variable, StayInfo>; does not own keys, but owns values */
+  GHashTable *stay_var_map;
+
+  GtkConstraintVariable *objective;
+
+  /* Set<Constraint>; owns the key */
+  GHashTable *constraints;
+
+  /* Counters */
+  int var_counter;
+  int slack_counter;
+  int artificial_counter;
+  int dummy_counter;
+  int optimize_count;
+  int freeze_count;
+
+  /* Bitfields; keep at the end */
+  guint auto_solve : 1;
+  guint needs_solving : 1;
+  guint in_edit_phase : 1;
+};
+
+static void gtk_constraint_ref_free (GtkConstraintRef *ref);
+static void edit_info_free (gpointer data);
+
+G_DEFINE_TYPE (GtkConstraintSolver, gtk_constraint_solver, G_TYPE_OBJECT)
+
+static void
+gtk_constraint_solver_finalize (GObject *gobject)
+{
+  GtkConstraintSolver *self = GTK_CONSTRAINT_SOLVER (gobject);
+
+  g_clear_pointer (&self->constraints, g_hash_table_unref);
+
+  g_clear_pointer (&self->stay_error_vars, g_ptr_array_unref);
+  g_clear_pointer (&self->infeasible_rows, g_ptr_array_unref);
+
+  g_clear_pointer (&self->external_rows, g_hash_table_unref);
+  g_clear_pointer (&self->external_parametric_vars, g_hash_table_unref);
+  g_clear_pointer (&self->error_vars, g_hash_table_unref);
+  g_clear_pointer (&self->marker_vars, g_hash_table_unref);
+  g_clear_pointer (&self->edit_var_map, g_hash_table_unref);
+  g_clear_pointer (&self->stay_var_map, g_hash_table_unref);
+
+  g_clear_pointer (&self->rows, g_hash_table_unref);
+  g_clear_pointer (&self->columns, g_hash_table_unref);
+
+  G_OBJECT_CLASS (gtk_constraint_solver_parent_class)->finalize (gobject);
+}
+
+static void
+gtk_constraint_solver_class_init (GtkConstraintSolverClass *klass)
+{
+  GObjectClass *gobject_class = G_OBJECT_CLASS (klass);
+
+  gobject_class->finalize = gtk_constraint_solver_finalize;
+}
+
+static void
+gtk_constraint_solver_init (GtkConstraintSolver *self)
+{
+  self->columns =
+    g_hash_table_new_full (NULL, NULL,
+                           (GDestroyNotify) gtk_constraint_variable_unref,
+                           (GDestroyNotify) gtk_constraint_variable_set_free);
+
+  self->rows =
+    g_hash_table_new_full (NULL, NULL,
+                           (GDestroyNotify) gtk_constraint_variable_unref,
+                           (GDestroyNotify) gtk_constraint_expression_unref);
+
+  self->external_rows = g_hash_table_new (NULL, NULL);
+
+  self->external_parametric_vars = g_hash_table_new (NULL, NULL);
+
+  self->infeasible_rows = g_ptr_array_new ();
+
+  self->stay_error_vars =
+    g_ptr_array_new_with_free_func ((GDestroyNotify) gtk_constraint_variable_pair_free);
+
+  self->error_vars =
+    g_hash_table_new_full (NULL, NULL,
+                           NULL,
+                           (GDestroyNotify) gtk_constraint_variable_set_free);
+
+  self->marker_vars = g_hash_table_new (NULL, NULL);
+
+  self->edit_var_map = g_hash_table_new_full (NULL, NULL,
+                                              NULL,
+                                              edit_info_free);
+
+  self->stay_var_map = g_hash_table_new_full (NULL, NULL,
+                                              NULL,
+                                              g_free);
+
+  /* The rows table owns the objective variable */
+  self->objective = gtk_constraint_variable_new_objective ("Z");
+  g_hash_table_insert (self->rows,
+                       self->objective,
+                       gtk_constraint_expression_new (0.0));
+
+  self->constraints =
+    g_hash_table_new_full (NULL, NULL,
+                           (GDestroyNotify) gtk_constraint_ref_free,
+                           NULL);
+
+  self->slack_counter = 0;
+  self->dummy_counter = 0;
+  self->artificial_counter = 0;
+  self->freeze_count = 0;
+
+  self->needs_solving = FALSE;
+  self->auto_solve = TRUE;
+}
+
+/* Symbolic weight thresholds
+ *
+ * Constraint weights live on a continuum, but we use thresholds for simplicity's
+ * sake, so we don't have to necessarily reason in terms of numeric values.
+ *
+ * The public API has a similar approach, where the symbolic constants are negative
+ * values, and positive values are explicit weights. We map those values into
+ * numeric values that the GtkConstraintSolver can plug into the linear equations
+ * tableau.
+ */
+#define GTK_CONSTRAINT_WEIGHT_REQUIRED  (make_weight (1000, 1000, 1000, 1))
+#define GTK_CONSTRAINT_WEIGHT_STRONG    (make_weight (   1,    0,    0, 1))
+#define GTK_CONSTRAINT_WEIGHT_MEDIUM    (make_weight (   0,    1,    0, 1))
+#define GTK_CONSTRAINT_WEIGHT_WEAK      (make_weight (   0,    0,    1, 1))
+
+G_GNUC_PURE
+static inline double
+make_weight (double a,
+             double b,
+             double c,
+             double w)
+{
+  double res = 0;
+
+  res += CLAMP (a * w, 0, 1000) * 1000000;
+  res += CLAMP (b * w, 0, 1000) * 1000;
+  res += CLAMP (c * w, 0, 1000);
+
+  return res;
+}
+
+static void
+gtk_constraint_ref_free (GtkConstraintRef *self)
+{
+  gtk_constraint_solver_remove_constraint (self->solver, self);
+
+  gtk_constraint_expression_unref (self->expression);
+
+  if (self->is_edit || self->is_stay)
+    {
+      g_assert (self->variable != NULL);
+      gtk_constraint_variable_unref (self->variable);
+    }
+
+  g_free (self);
+}
+
+static gboolean
+gtk_constraint_ref_is_inequality (const GtkConstraintRef *self)
+{
+  return self->relation != GTK_CONSTRAINT_RELATION_EQ;
+}
+
+static gboolean
+gtk_constraint_ref_is_required (const GtkConstraintRef *self)
+{
+  return self->weight >= GTK_CONSTRAINT_WEIGHT_REQUIRED;
+}
+
+static const char *relations[] = {
+  "<=",
+  "==",
+  ">=",
+};
+
+static const char *
+relation_to_string (GtkConstraintRelation r)
+{
+  return relations[r + 1];
+}
+
+static const char *
+weight_to_string (double s)
+{
+  if (s >= GTK_CONSTRAINT_WEIGHT_REQUIRED)
+    return "required";
+
+  if (s >= GTK_CONSTRAINT_WEIGHT_STRONG)
+    return "strong";
+
+  if (s >= GTK_CONSTRAINT_WEIGHT_MEDIUM)
+    return "medium";
+
+  return "weak";
+}
+
+static char *
+gtk_constraint_ref_to_string (const GtkConstraintRef *self)
+{
+  GString *buf = g_string_new (NULL);
+  char *str;
+
+  if (self->is_stay)
+    g_string_append (buf, "[stay]");
+  else if (self->is_edit)
+    g_string_append (buf, "[edit]");
+
+  str = gtk_constraint_expression_to_string (self->expression);
+  g_string_append (buf, str);
+  g_free (str);
+
+  g_string_append_c (buf, ' ');
+  g_string_append (buf, relation_to_string (self->relation));
+  g_string_append (buf, " 0.0");
+
+  g_string_append_printf (buf, " [weight:%s (%g)]",
+                          weight_to_string (self->weight),
+                          self->weight);
+
+  return g_string_free (buf, FALSE);
+}
+
+static GtkConstraintVariableSet *
+gtk_constraint_solver_get_column_set (GtkConstraintSolver *self,
+                                      GtkConstraintVariable *param_var)
+{
+  return g_hash_table_lookup (self->columns, param_var);
+}
+
+static gboolean
+gtk_constraint_solver_column_has_key (GtkConstraintSolver *self,
+                                      GtkConstraintVariable *subject)
+{
+  return g_hash_table_contains (self->columns, subject);
+}
+
+static void
+gtk_constraint_solver_insert_column_variable (GtkConstraintSolver *self,
+                                              GtkConstraintVariable *param_var,
+                                              GtkConstraintVariable *row_var)
+{
+  GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, param_var);
+
+  if (cset == NULL)
+    {
+      cset = gtk_constraint_variable_set_new ();
+      g_hash_table_insert (self->columns, gtk_constraint_variable_ref (param_var), cset);
+    }
+
+  if (row_var != NULL)
+    gtk_constraint_variable_set_add (cset, row_var);
+}
+
+static void
+gtk_constraint_solver_insert_error_variable (GtkConstraintSolver *self,
+                                             GtkConstraintRef *constraint,
+                                             GtkConstraintVariable *variable)
+{
+  GtkConstraintVariableSet *cset = g_hash_table_lookup (self->error_vars, constraint);
+
+  if (cset == NULL)
+    {
+      cset = gtk_constraint_variable_set_new ();
+      g_hash_table_insert (self->error_vars, constraint, cset);
+    }
+
+  gtk_constraint_variable_set_add (cset, variable);
+}
+
+static void
+gtk_constraint_solver_reset_stay_constants (GtkConstraintSolver *self)
+{
+  int i;
+
+  for (i = 0; i < self->stay_error_vars->len; i++)
+    {
+      GtkConstraintVariablePair *pair = g_ptr_array_index (self->stay_error_vars, i);
+      GtkConstraintExpression *expression;
+
+      expression = g_hash_table_lookup (self->rows, pair->first);
+
+      if (expression == NULL)
+        expression = g_hash_table_lookup (self->rows, pair->second);
+
+      if (expression != NULL)
+        gtk_constraint_expression_set_constant (expression, 0.0);
+    }
+}
+
+static void
+gtk_constraint_solver_set_external_variables (GtkConstraintSolver *self)
+{
+  GHashTableIter iter;
+  gpointer key_p;
+
+  g_hash_table_iter_init (&iter, self->external_parametric_vars);
+  while (g_hash_table_iter_next (&iter, &key_p, NULL))
+    {
+      GtkConstraintVariable *variable = key_p;
+
+      if (g_hash_table_contains (self->rows, variable))
+        continue;
+
+      gtk_constraint_variable_set_value (variable, 0.0);
+    }
+
+  g_hash_table_iter_init (&iter, self->external_rows);
+  while (g_hash_table_iter_next (&iter, &key_p, NULL))
+    {
+      GtkConstraintVariable *variable = key_p;
+      GtkConstraintExpression *expression;
+      double constant;
+
+      expression = g_hash_table_lookup (self->rows, variable);
+      constant = gtk_constraint_expression_get_constant (expression);
+
+      gtk_constraint_variable_set_value (variable, constant);
+    }
+
+  self->needs_solving = FALSE;
+}
+
+static void
+gtk_constraint_solver_add_row (GtkConstraintSolver *self,
+                               GtkConstraintVariable *variable,
+                               GtkConstraintExpression *expression)
+{
+  GtkConstraintExpressionIter iter;
+  GtkConstraintVariable *t_v;
+  double t_c;
+
+  g_hash_table_insert (self->rows,
+                       gtk_constraint_variable_ref (variable),
+                       gtk_constraint_expression_ref (expression));
+
+  gtk_constraint_expression_iter_init (&iter, expression);
+  while (gtk_constraint_expression_iter_next (&iter, &t_v, &t_c))
+    {
+      gtk_constraint_solver_insert_column_variable (self, t_v, variable);
+
+      if (gtk_constraint_variable_is_external (t_v))
+        g_hash_table_add (self->external_parametric_vars, t_v);
+    }
+
+  if (gtk_constraint_variable_is_external (variable))
+    g_hash_table_add (self->external_rows, variable);
+}
+
+static void
+gtk_constraint_solver_remove_column (GtkConstraintSolver *self,
+                                     GtkConstraintVariable *variable)
+{
+  GtkConstraintVariable *v;
+  GtkConstraintVariableSetIter iter;
+  GtkConstraintVariableSet *cset;
+
+  /* Take a reference on the variable, as we're going to remove it
+   * from various maps and we want to guarantee the pointer is
+   * valid until we leave this function
+   */
+  gtk_constraint_variable_ref (variable);
+
+  cset = g_hash_table_lookup (self->columns, variable);
+  if (cset == NULL)
+    goto out;
+
+  gtk_constraint_variable_set_iter_init (&iter, cset);
+  while (gtk_constraint_variable_set_iter_next (&iter, &v))
+    {
+      GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
+
+      gtk_constraint_expression_remove_variable (e, variable);
+    }
+
+  g_hash_table_remove (self->columns, variable);
+
+out:
+  if (gtk_constraint_variable_is_external (variable))
+    {
+      g_hash_table_remove (self->external_rows, variable);
+      g_hash_table_remove (self->external_parametric_vars, variable);
+    }
+
+  gtk_constraint_variable_unref (variable);
+}
+
+static GtkConstraintExpression *
+gtk_constraint_solver_remove_row (GtkConstraintSolver *self,
+                                  GtkConstraintVariable *variable,
+                                  gboolean free_res)
+{
+  GtkConstraintExpression *e;
+  GtkConstraintExpressionIter iter;
+  GtkConstraintVariable *t_v;
+  double t_c;
+
+  e = g_hash_table_lookup (self->rows, variable);
+  g_assert (e != NULL);
+
+  gtk_constraint_expression_ref (e);
+
+  gtk_constraint_expression_iter_init (&iter, e);
+  while (gtk_constraint_expression_iter_next (&iter, &t_v, &t_c))
+    {
+      GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, t_v);
+
+      if (cset != NULL)
+        gtk_constraint_variable_set_remove (cset, variable);
+    }
+
+  g_ptr_array_remove (self->infeasible_rows, variable);
+
+  if (gtk_constraint_variable_is_external (variable))
+    g_hash_table_remove (self->external_rows, variable);
+
+  g_hash_table_remove (self->rows, variable);
+
+  if (free_res)
+    {
+      gtk_constraint_expression_unref (e);
+      return NULL;
+    }
+
+  return e;
+}
+
+/*< private >
+ * gtk_constraint_solver_substitute_out:
+ * @self: a #GtkConstraintSolver
+ * @old_variable: a #GtkConstraintVariable
+ * @expression: a #GtkConstraintExpression
+ *
+ * Replaces @old_variable in every row of the tableau with @expression.
+ */
+static void
+gtk_constraint_solver_substitute_out (GtkConstraintSolver *self,
+                                      GtkConstraintVariable *old_variable,
+                                      GtkConstraintExpression *expression)
+{
+  GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, old_variable);
+  if (cset != NULL)
+    {
+      GtkConstraintVariableSetIter iter;
+      GtkConstraintVariable *v;
+
+      gtk_constraint_variable_set_iter_init (&iter, cset);
+      while (gtk_constraint_variable_set_iter_next (&iter, &v))
+        {
+          GtkConstraintExpression *row = g_hash_table_lookup (self->rows, v);
+
+          gtk_constraint_expression_substitute_out (row, old_variable, expression, v, self);
+
+          if (gtk_constraint_variable_is_restricted (v) &&
+              gtk_constraint_expression_get_constant (row) < 0)
+            g_ptr_array_add (self->infeasible_rows, v);
+        }
+    }
+
+  if (gtk_constraint_variable_is_external (old_variable))
+    {
+      g_hash_table_add (self->external_rows, old_variable);
+      g_hash_table_remove (self->external_parametric_vars, old_variable);
+    }
+
+  g_hash_table_remove (self->columns, old_variable);
+}
+
+/*< private >
+ * gtk_constraint_solver_pivot:
+ * @self: a #GtkConstraintSolver
+ * @entry_var: a #GtkConstraintVariable
+ * @exit_var: a #GtkConstraintVariable
+ *
+ * Pivots the #GtkConstraintSolver.
+ *
+ * This function will move @entry_var into the basis of the tableau,
+ * making it a basic variable; and move @exit_var out of the basis of
+ * the tableau, making it a parametric variable.
+ */
+static void
+gtk_constraint_solver_pivot (GtkConstraintSolver *self,
+                             GtkConstraintVariable *entry_var,
+                             GtkConstraintVariable *exit_var)
+{
+  GtkConstraintExpression *expr;
+
+  if (entry_var != NULL)
+    gtk_constraint_variable_ref (entry_var);
+  else
+    g_critical ("INTERNAL: invalid entry variable during pivot");
+
+  if (exit_var != NULL)
+    gtk_constraint_variable_ref (exit_var);
+  else
+    g_critical ("INTERNAL: invalid exit variable during pivot");
+
+  /* We keep a reference to the expression */
+  expr = gtk_constraint_solver_remove_row (self, exit_var, FALSE);
+
+  gtk_constraint_expression_change_subject (expr, exit_var, entry_var);
+  gtk_constraint_solver_substitute_out (self, entry_var, expr);
+
+  if (gtk_constraint_variable_is_external (entry_var))
+    g_hash_table_remove (self->external_parametric_vars, entry_var);
+
+  gtk_constraint_solver_add_row (self, entry_var, expr);
+
+  gtk_constraint_variable_unref (entry_var);
+  gtk_constraint_variable_unref (exit_var);
+  gtk_constraint_expression_unref (expr);
+}
+
+static void
+gtk_constraint_solver_optimize (GtkConstraintSolver *self,
+                                GtkConstraintVariable *z)
+{
+  GtkConstraintVariable *entry = NULL, *exit = NULL;
+  GtkConstraintExpression *z_row = g_hash_table_lookup (self->rows, z);
+
+#ifdef G_ENABLE_DEBUG
+  gint64 start_time = g_get_monotonic_time ();
+#endif
+
+  g_assert (z_row != NULL);
+
+  self->optimize_count += 1;
+
+#ifdef G_ENABLE_DEBUG
+  {
+    char *str;
+
+    str = gtk_constraint_variable_to_string (z);
+    g_debug ("optimize: %s\n", str);
+    g_free (str);
+  }
+#endif
+
+  while (TRUE)
+    {
+      GtkConstraintVariableSet *column_vars;
+      GtkConstraintVariableSetIter viter;
+      GtkConstraintExpressionIter eiter;
+      GtkConstraintVariable *t_v, *v;
+      double t_c;
+      double objective_coefficient = 0.0;
+      double min_ratio;
+      double r;
+
+      gtk_constraint_expression_iter_init (&eiter, z_row);
+      while (gtk_constraint_expression_iter_prev (&eiter, &t_v, &t_c))
+        {
+          if (gtk_constraint_variable_is_pivotable (t_v) && t_c < objective_coefficient)
+            {
+              entry = t_v;
+              objective_coefficient = t_c;
+              break;
+            }
+        }
+
+      if (objective_coefficient >= -1e-8)
+        break;
+
+      min_ratio = DBL_MAX;
+      r = 0;
+
+      column_vars = gtk_constraint_solver_get_column_set (self, entry);
+      gtk_constraint_variable_set_iter_init (&viter, column_vars);
+      while (gtk_constraint_variable_set_iter_next (&viter, &v))
+        {
+          if (gtk_constraint_variable_is_pivotable (v))
+            {
+              GtkConstraintExpression *expr = g_hash_table_lookup (self->rows, v);
+              double coeff = gtk_constraint_expression_get_coefficient (expr, entry);
+
+              if (coeff < 0.0)
+                {
+                  double constant = gtk_constraint_expression_get_constant (expr);
+
+                  r = -1.0 * constant / coeff;
+                  if (r < min_ratio)
+                    {
+                      min_ratio = r;
+                      exit = v;
+                    }
+                }
+            }
+        }
+
+      if (min_ratio == DBL_MAX)
+        {
+          g_debug ("Unbounded objective variable during optimization");
+          break;
+        }
+
+#ifdef G_ENABLE_DEBUG
+      {
+        char *entry_s = gtk_constraint_variable_to_string (entry);
+        char *exit_s = gtk_constraint_variable_to_string (exit);
+        g_debug ("pivot(entry: %s, exit: %s)", entry_s, exit_s);
+        g_free (entry_s);
+        g_free (exit_s);
+      }
+#endif
+
+      gtk_constraint_solver_pivot (self, entry, exit);
+    }
+
+#ifdef G_ENABLE_DEBUG
+  g_debug ("solver.optimize.time := %.3f ms (pass: %d)",
+           (float) (g_get_monotonic_time () - start_time) / 1000.f,
+           self->optimize_count);
+#endif
+}
+
+/*< private >
+ * gtk_constraint_solver_new_expression:
+ * @self: a #GtkConstraintSolver
+ * @constraint: a #GtkConstraintRef
+ * @eplus_p: (out) (optional): the positive error variable
+ * @eminus_p: (out) (optional): the negative error variable
+ * @prev_constant_p: the constant part of the @constraint's expression
+ *
+ * Creates a new expression for the @constraint, replacing
+ * any basic variable with their expressions, and normalizing
+ * the terms to avoid a negative constant.
+ *
+ * If the @constraint is not required, this function will add
+ * error variables with the appropriate weight to the tableau.
+ *
+ * Returns: (transfer full): the new expression for the constraint
+ */
+static GtkConstraintExpression *
+gtk_constraint_solver_new_expression (GtkConstraintSolver *self,
+                                      GtkConstraintRef *constraint,
+                                      GtkConstraintVariable **eplus_p,
+                                      GtkConstraintVariable **eminus_p,
+                                      double *prev_constant_p)
+{
+  GtkConstraintExpression *cn_expr = constraint->expression;
+  GtkConstraintExpression *expr;
+  GtkConstraintExpressionIter eiter;
+  GtkConstraintVariable *t_v;
+  double t_c;
+
+  if (eplus_p != NULL)
+    *eplus_p = NULL;
+  if (eminus_p != NULL)
+    *eminus_p = NULL;
+  if (prev_constant_p != NULL)
+    *prev_constant_p = 0.0;
+
+  expr = gtk_constraint_expression_new (gtk_constraint_expression_get_constant (cn_expr));
+
+  gtk_constraint_expression_iter_init (&eiter, cn_expr);
+  while (gtk_constraint_expression_iter_next (&eiter, &t_v, &t_c))
+    {
+      GtkConstraintExpression *e = g_hash_table_lookup (self->rows, t_v);
+
+      if (e == NULL)
+        gtk_constraint_expression_add_variable (expr, t_v, t_c, NULL, self);
+      else
+        gtk_constraint_expression_add_expression (expr, e, t_c, NULL, self);
+    }
+
+  if (gtk_constraint_ref_is_inequality (constraint))
+    {
+      GtkConstraintVariable *slack_var;
+
+      /* If the constraint is an inequality, we add a slack variable to
+       * turn it into an equality, e.g. from
+       *
+       *   expr ≥ 0
+       *
+       * to
+       *
+       *   expr - slack = 0
+       *
+       * Additionally, if the constraint is not required we add an
+       * error variable with the weight of the constraint:
+       *
+       *   expr - slack + error = 0
+       */
+      self->slack_counter += 1;
+
+      slack_var = gtk_constraint_variable_new_slack ("s");
+      gtk_constraint_expression_set_variable (expr, slack_var, -1.0);
+      gtk_constraint_variable_unref (slack_var);
+
+      g_hash_table_insert (self->marker_vars, constraint, slack_var);
+
+      if (!gtk_constraint_ref_is_required (constraint))
+        {
+          GtkConstraintExpression *z_row;
+          GtkConstraintVariable *eminus;
+
+          self->slack_counter += 1;
+
+          eminus = gtk_constraint_variable_new_slack ("em");
+          gtk_constraint_expression_set_variable (expr, eminus, 1.0);
+          gtk_constraint_variable_unref (eminus);
+
+          z_row = g_hash_table_lookup (self->rows, self->objective);
+          gtk_constraint_expression_set_variable (z_row, eminus, constraint->weight);
+
+          gtk_constraint_solver_insert_error_variable (self, constraint, eminus);
+          gtk_constraint_solver_note_added_variable (self, eminus, self->objective);
+          gtk_constraint_variable_unref (eminus);
+        }
+    }
+  else
+    {
+      GtkConstraintVariable *dummy_var;
+
+      if (gtk_constraint_ref_is_required (constraint))
+        {
+          /* If the constraint is required, we use a dummy marker variable;
+           * the dummy won't be allowed to enter the basis of the tableau
+           * when pivoting.
+           */
+          self->dummy_counter += 1;
+
+          dummy_var = gtk_constraint_variable_new_dummy ("dummy");
+
+          if (eplus_p != NULL)
+            *eplus_p = dummy_var;
+          if (eminus_p != NULL)
+            *eminus_p = dummy_var;
+          if (prev_constant_p != NULL)
+            *prev_constant_p = gtk_constraint_expression_get_constant (cn_expr);
+
+          gtk_constraint_expression_set_variable (expr, dummy_var, 1.0);
+          g_hash_table_insert (self->marker_vars, constraint, dummy_var);
+
+          gtk_constraint_variable_unref (dummy_var);
+        }
+      else
+        {
+          GtkConstraintVariable *eplus, *eminus;
+          GtkConstraintExpression *z_row;
+
+          /* Since the constraint is a non-required equality, we need to
+           * add error variables around it, i.e. turn it from:
+           *
+           *   expr = 0
+           *
+           * to:
+           *
+           *   expr - eplus + eminus = 0
+           */
+          self->slack_counter += 1;
+
+          eplus = gtk_constraint_variable_new_slack ("ep");
+          eminus = gtk_constraint_variable_new_slack ("em");
+
+          gtk_constraint_expression_set_variable (expr, eplus, -1.0);
+          gtk_constraint_expression_set_variable (expr, eminus, 1.0);
+
+          g_hash_table_insert (self->marker_vars, constraint, eplus);
+
+          z_row = g_hash_table_lookup (self->rows, self->objective);
+
+          gtk_constraint_expression_set_variable (z_row, eplus, constraint->weight);
+          gtk_constraint_expression_set_variable (z_row, eminus, constraint->weight);
+          gtk_constraint_solver_note_added_variable (self, eplus, self->objective);
+          gtk_constraint_solver_note_added_variable (self, eminus, self->objective);
+
+          gtk_constraint_solver_insert_error_variable (self, constraint, eplus);
+          gtk_constraint_solver_insert_error_variable (self, constraint, eminus);
+
+          if (constraint->is_stay)
+            {
+              g_ptr_array_add (self->stay_error_vars, gtk_constraint_variable_pair_new (eplus, eminus));
+            }
+          else if (constraint->is_edit)
+            {
+              if (eplus_p != NULL)
+                *eplus_p = eplus;
+              if (eminus_p != NULL)
+                *eminus_p = eminus;
+              if (prev_constant_p != NULL)
+                *prev_constant_p = gtk_constraint_expression_get_constant (cn_expr);
+            }
+
+          gtk_constraint_variable_unref (eplus);
+          gtk_constraint_variable_unref (eminus);
+        }
+    }
+
+  if (gtk_constraint_expression_get_constant (expr) < 0.0)
+    gtk_constraint_expression_multiply_by (expr, -1.0);
+
+  return expr;
+}
+
+static void
+gtk_constraint_solver_dual_optimize (GtkConstraintSolver *self)
+{
+  GtkConstraintExpression *z_row = g_hash_table_lookup (self->rows, self->objective);
+#ifdef G_ENABLE_DEBUG
+  gint64 start_time = g_get_monotonic_time ();
+#endif
+
+  /* We iterate until we don't have any more infeasible rows; the pivot()
+   * at the end of the loop iteration may add or remove infeasible rows
+   * as well
+   */
+  while (self->infeasible_rows->len != 0)
+    {
+      GtkConstraintVariable *entry_var, *exit_var, *t_v;
+      GtkConstraintExpressionIter eiter;
+      GtkConstraintExpression *expr;
+      double ratio, t_c;
+
+      /* Pop the last element of the array */
+      exit_var = g_ptr_array_index (self->infeasible_rows, self->infeasible_rows->len - 1);
+      g_ptr_array_set_size (self->infeasible_rows, self->infeasible_rows->len - 1);
+
+      expr = g_hash_table_lookup (self->rows, exit_var);
+      if (expr == NULL)
+        continue;
+
+      if (gtk_constraint_expression_get_constant (expr) >= 0.0)
+        continue;
+
+      ratio = DBL_MAX;
+      entry_var = NULL;
+
+      gtk_constraint_expression_iter_init (&eiter, expr);
+      while (gtk_constraint_expression_iter_next (&eiter, &t_v, &t_c))
+        {
+          if (t_c > 0.0 && gtk_constraint_variable_is_pivotable (t_v))
+            {
+              double zc = gtk_constraint_expression_get_coefficient (z_row, t_v);
+              double r = zc / t_c;
+
+              if (r < ratio)
+                {
+                  entry_var = t_v;
+                  ratio = r;
+                }
+            }
+        }
+
+      if (ratio == DBL_MAX)
+        g_critical ("INTERNAL: ratio == DBL_MAX in dual_optimize");
+
+      gtk_constraint_solver_pivot (self, entry_var, exit_var);
+    }
+
+#ifdef G_ENABLE_DEBUG
+  g_debug ("dual_optimize.time := %.3f ms",
+           (float) (g_get_monotonic_time () - start_time) / 1000.f);
+#endif
+}
+
+static void
+gtk_constraint_solver_delta_edit_constant (GtkConstraintSolver *self,
+                                           double delta,
+                                           GtkConstraintVariable *plus_error_var,
+                                           GtkConstraintVariable *minus_error_var)
+{
+  GtkConstraintExpression *plus_expr, *minus_expr;
+  GtkConstraintVariable *basic_var;
+  GtkConstraintVariableSet *column_set;
+  GtkConstraintVariableSetIter iter;
+
+  plus_expr = g_hash_table_lookup (self->rows, plus_error_var);
+  if (plus_expr != NULL)
+    {
+      double new_constant = gtk_constraint_expression_get_constant (plus_expr) + delta;
+
+      gtk_constraint_expression_set_constant (plus_expr, new_constant);
+
+      if (new_constant < 0.0)
+        g_ptr_array_add (self->infeasible_rows, plus_error_var);
+
+      return;
+    }
+
+  minus_expr = g_hash_table_lookup (self->rows, minus_error_var);
+  if (minus_expr != NULL)
+    {
+      double new_constant = gtk_constraint_expression_get_constant (minus_expr) - delta;
+
+      gtk_constraint_expression_set_constant (minus_expr, new_constant);
+
+      if (new_constant < 0.0)
+        g_ptr_array_add (self->infeasible_rows, minus_error_var);
+
+      return;
+    }
+
+  column_set = g_hash_table_lookup (self->columns, minus_error_var);
+  if (column_set == NULL)
+    {
+      g_critical ("INTERNAL: Columns are unset during delta edit");
+      return;
+    }
+
+  gtk_constraint_variable_set_iter_init (&iter, column_set);
+  while (gtk_constraint_variable_set_iter_next (&iter, &basic_var))
+    {
+      GtkConstraintExpression *expr;
+      double c, new_constant;
+
+      expr = g_hash_table_lookup (self->rows, basic_var);
+      c = gtk_constraint_expression_get_coefficient (expr, minus_error_var);
+
+      new_constant = gtk_constraint_expression_get_constant (expr) + (c * delta);
+      gtk_constraint_expression_set_constant (expr, new_constant);
+
+      if (gtk_constraint_variable_is_restricted (basic_var) && new_constant < 0.0)
+        g_ptr_array_add (self->infeasible_rows, basic_var);
+    }
+}
+
+static GtkConstraintVariable *
+gtk_constraint_solver_choose_subject (GtkConstraintSolver *self,
+                                      GtkConstraintExpression *expression)
+{
+  GtkConstraintExpressionIter eiter;
+  GtkConstraintVariable *subject = NULL;
+  GtkConstraintVariable *retval = NULL;
+  GtkConstraintVariable *t_v;
+  gboolean found_unrestricted = FALSE;
+  gboolean found_new_restricted = FALSE;
+  gboolean retval_found = FALSE;
+  double coeff = 0.0;
+  double t_c;
+
+  gtk_constraint_expression_iter_init (&eiter, expression);
+  while (gtk_constraint_expression_iter_prev (&eiter, &t_v, &t_c))
+    {
+      if (found_unrestricted)
+        {
+          if (!gtk_constraint_variable_is_restricted (t_v))
+            {
+              if (!g_hash_table_contains (self->columns, t_v))
+                {
+                  retval_found = TRUE;
+                  retval = t_v;
+                  break;
+                }
+            }
+        }
+      else
+        {
+          if (gtk_constraint_variable_is_restricted (t_v))
+            {
+              if (!found_new_restricted &&
+                  !gtk_constraint_variable_is_dummy (t_v) &&
+                  t_c < 0.0)
+                {
+                  GtkConstraintVariableSet *cset = g_hash_table_lookup (self->columns, t_v);
+
+                  if (cset == NULL ||
+                      (gtk_constraint_variable_set_size (cset) == 1 &&
+                       g_hash_table_contains (self->columns, self->objective)))
+                    {
+                      subject = t_v;
+                      found_new_restricted = TRUE;
+                    }
+                }
+            }
+          else
+            {
+              subject = t_v;
+              found_unrestricted = TRUE;
+            }
+        }
+    }
+
+  if (retval_found)
+    return retval;
+
+  if (subject != NULL)
+    return subject;
+
+  gtk_constraint_expression_iter_init (&eiter, expression);
+  while (gtk_constraint_expression_iter_prev (&eiter, &t_v, &t_c))
+    {
+      if (!gtk_constraint_variable_is_dummy (t_v))
+        return NULL;
+
+      if (!g_hash_table_contains (self->columns, t_v))
+        {
+          subject = t_v;
+          coeff = t_c;
+        }
+    }
+
+  if (!G_APPROX_VALUE (gtk_constraint_expression_get_constant (expression), 0.0, 0.001))
+    {
+      g_debug ("Unable to satisfy required constraint (choose_subject)");
+      return NULL;
+    }
+
+  if (coeff > 0)
+    gtk_constraint_expression_multiply_by (expression, -1.0);
+
+  return subject;
+}
+
+static gboolean
+gtk_constraint_solver_try_adding_directly (GtkConstraintSolver *self,
+                                           GtkConstraintExpression *expression)
+{
+  GtkConstraintVariable *subject;
+
+  subject = gtk_constraint_solver_choose_subject (self, expression);
+  if (subject == NULL)
+    return FALSE;
+
+  gtk_constraint_variable_ref (subject);
+
+  gtk_constraint_expression_new_subject (expression, subject);
+  if (gtk_constraint_solver_column_has_key (self, subject))
+    gtk_constraint_solver_substitute_out (self, subject, expression);
+
+  gtk_constraint_solver_add_row (self, subject, expression);
+
+  gtk_constraint_variable_unref (subject);
+
+  return TRUE;
+}
+
+static void
+gtk_constraint_solver_add_with_artificial_variable (GtkConstraintSolver *self,
+                                                    GtkConstraintExpression *expression)
+{
+  GtkConstraintVariable *av, *az;
+  GtkConstraintExpression *az_row;
+  GtkConstraintExpression *az_tableau_row;
+  GtkConstraintExpression *e;
+
+  av = gtk_constraint_variable_new_slack ("a");
+  self->artificial_counter += 1;
+
+  az = gtk_constraint_variable_new_objective ("az");
+
+  az_row = gtk_constraint_expression_clone (expression);
+
+  gtk_constraint_solver_add_row (self, az, az_row);
+  gtk_constraint_solver_add_row (self, av, expression);
+
+  gtk_constraint_expression_unref (az_row);
+  gtk_constraint_variable_unref (av);
+  gtk_constraint_variable_unref (az);
+
+  gtk_constraint_solver_optimize (self, az);
+
+  az_tableau_row = g_hash_table_lookup (self->rows, az);
+  if (!G_APPROX_VALUE (gtk_constraint_expression_get_constant (az_tableau_row), 0.0, 0.001))
+    {
+      char *str = gtk_constraint_expression_to_string (expression);
+
+      gtk_constraint_solver_remove_column (self, av);
+      gtk_constraint_solver_remove_row (self, az, TRUE);
+
+      g_debug ("Unable to satisfy a required constraint (add): %s", str);
+
+      g_free (str);
+
+      return;
+    }
+
+  e = g_hash_table_lookup (self->rows, av);
+  if (e != NULL)
+    {
+      GtkConstraintVariable *entry_var;
+
+      if (gtk_constraint_expression_is_constant (e))
+        {
+          gtk_constraint_solver_remove_row (self, av, TRUE);
+          gtk_constraint_solver_remove_row (self, az, TRUE);
+          return;
+        }
+
+      entry_var = gtk_constraint_expression_get_pivotable_variable (e);
+      if (entry_var == NULL)
+        return;
+
+      gtk_constraint_solver_pivot (self, entry_var, av);
+    }
+
+  g_assert (!g_hash_table_contains (self->rows, av));
+
+  gtk_constraint_solver_remove_column (self, av);
+  gtk_constraint_solver_remove_row (self, az, TRUE);
+}
+
+static void
+gtk_constraint_solver_add_constraint_internal (GtkConstraintSolver *self,
+                                               GtkConstraintRef *constraint)
+{
+  GtkConstraintExpression *expr;
+  GtkConstraintVariable *eplus;
+  GtkConstraintVariable *eminus;
+  double prev_constant;
+
+  expr = gtk_constraint_solver_new_expression (self, constraint,
+                                               &eplus,
+                                               &eminus,
+                                               &prev_constant);
+
+#ifdef G_ENABLE_DEBUG
+  {
+    char *expr_s = gtk_constraint_expression_to_string (expr);
+    char *ref_s = gtk_constraint_ref_to_string (constraint);
+
+    g_debug ("Adding constraint '%s' (normalized expression: '%s')\n", ref_s, expr_s);
+
+    g_free (ref_s);
+    g_free (expr_s);
+  }
+#endif
+
+  if (constraint->is_stay)
+    {
+      StayInfo *si = g_new (StayInfo, 1);
+
+      si->constraint = constraint;
+
+      g_hash_table_insert (self->stay_var_map, constraint->variable, si);
+    }
+  else if (constraint->is_edit)
+    {
+      EditInfo *ei = g_new (EditInfo, 1);
+
+      ei->constraint = constraint;
+      ei->eplus = eplus;
+      ei->eminus = eminus;
+      ei->prev_constant = prev_constant;
+
+      g_hash_table_insert (self->edit_var_map, constraint->variable, ei);
+    }
+
+  if (!gtk_constraint_solver_try_adding_directly (self, expr))
+    gtk_constraint_solver_add_with_artificial_variable (self, expr);
+
+  gtk_constraint_expression_unref (expr);
+
+  self->needs_solving = TRUE;
+
+  if (self->auto_solve)
+    {
+      gtk_constraint_solver_optimize (self, self->objective);
+      gtk_constraint_solver_set_external_variables (self);
+    }
+
+  constraint->solver = self;
+
+  g_hash_table_add (self->constraints, constraint);
+}
+
+/*< private >
+ * gtk_constraint_solver_new:
+ *
+ * Creates a new #GtkConstraintSolver instance.
+ *
+ * Returns: the newly created #GtkConstraintSolver
+ */
+GtkConstraintSolver *
+gtk_constraint_solver_new (void)
+{
+  return g_object_new (GTK_TYPE_CONSTRAINT_SOLVER, NULL);
+}
+
+/*< private >
+ * gtk_constraint_solver_freeze:
+ * @solver: a #GtkConstraintSolver
+ *
+ * Freezes the solver; any constraint addition or removal will not
+ * be automatically solved until gtk_constraint_solver_thaw() is
+ * called.
+ */
+void
+gtk_constraint_solver_freeze (GtkConstraintSolver *solver)
+{
+  g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
+
+  solver->freeze_count += 1;
+
+  if (solver->freeze_count > 0)
+    solver->auto_solve = FALSE;
+}
+
+/*< private >
+ * gtk_constraint_solver_thaw:
+ * @solver: a #GtkConstraintSolver
+ *
+ * Thaws a frozen #GtkConstraintSolver.
+ */
+void
+gtk_constraint_solver_thaw (GtkConstraintSolver *solver)
+{
+  g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
+  g_return_if_fail (solver->freeze_count == 0);
+
+  solver->freeze_count -= 1;
+
+  if (solver->freeze_count == 0)
+    {
+      solver->auto_solve = TRUE;
+      gtk_constraint_solver_resolve (solver);
+    }
+}
+
+/*< private >
+ * gtk_constraint_solver_note_added_variable:
+ * @self: a #GtkConstraintSolver
+ * @variable: a #GtkConstraintVariable
+ * @subject: a #GtkConstraintVariable
+ *
+ * Adds a new @variable into the tableau of a #GtkConstraintSolver.
+ *
+ * This function is typically called by #GtkConstraintExpression, and
+ * should never be directly called.
+ */
+void
+gtk_constraint_solver_note_added_variable (GtkConstraintSolver *self,
+                                           GtkConstraintVariable *variable,
+                                           GtkConstraintVariable *subject)
+{
+  if (subject != NULL)
+    gtk_constraint_solver_insert_column_variable (self, variable, subject);
+}
+
+/*< private >
+ * gtk_constraint_solver_note_removed_variable:
+ * @self: a #GtkConstraintSolver
+ * @variable: a #GtkConstraintVariable
+ * @subject: a #GtkConstraintVariable
+ *
+ * Removes a @variable from the tableau of a #GtkConstraintSolver.
+ *
+ * This function is typically called by #GtkConstraintExpression, and
+ * should never be directly called.
+ */
+void
+gtk_constraint_solver_note_removed_variable (GtkConstraintSolver *self,
+                                             GtkConstraintVariable *variable,
+                                             GtkConstraintVariable *subject)
+{
+  GtkConstraintVariableSet *set;
+
+  set = g_hash_table_lookup (self->columns, variable);
+  if (set != NULL && subject != NULL)
+    gtk_constraint_variable_set_remove (set, subject);
+}
+
+/*< private >
+ * gtk_constraint_solver_create_variable:
+ * @self: a #GtkConstraintSolver
+ * @prefix: (nullable): the prefix of the variable
+ * @name: (nullable): the name of the variable
+ * @value: the initial value of the variable
+ *
+ * Creates a new variable inside the @solver.
+ *
+ * Returns: (transfer full): the newly created variable
+ */
+GtkConstraintVariable *
+gtk_constraint_solver_create_variable (GtkConstraintSolver *self,
+                                       const char *prefix,
+                                       const char *name,
+                                       double value)
+{
+  GtkConstraintVariable *res;
+
+  res = gtk_constraint_variable_new (name);
+  gtk_constraint_variable_set_prefix (res, prefix);
+  gtk_constraint_variable_set_value (res, value);
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_solver_resolve:
+ * @solver: a #GtkConstraintSolver
+ *
+ * Resolves the constraints currently stored in @solver.
+ */
+void
+gtk_constraint_solver_resolve (GtkConstraintSolver *solver)
+{
+#ifdef G_ENABLE_DEBUG
+  gint64 start_time = g_get_monotonic_time ();
+#endif
+
+  g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
+
+  gtk_constraint_solver_dual_optimize (solver);
+  gtk_constraint_solver_set_external_variables (solver);
+
+  g_ptr_array_set_size (solver->infeasible_rows, 0);
+
+  gtk_constraint_solver_reset_stay_constants (solver);
+
+#ifdef G_ENABLE_DEBUG
+  g_debug ("resolve.time := %.3f ms",
+           (float) (g_get_monotonic_time () - start_time) / 1000.f);
+#endif
+
+  solver->needs_solving = FALSE;
+}
+
+/*< private >
+ * gtk_constraint_solver_add_constraint:
+ * @self: a #GtkConstraintSolver
+ * @variable: the subject of the constraint
+ * @relation: the relation of the constraint
+ * @expression: the expression of the constraint
+ * @strength: the weight of the constraint
+ *
+ * Adds a new constraint in the form of:
+ *
+ * |[
+ *   variable relation expression (strength)
+ * |]
+ *
+ * into the #GtkConstraintSolver.
+ *
+ * Returns: (transfer none): a reference to the newly created
+ *   constraint; you can use the reference to remove the
+ *   constraint from the solver
+ */
+GtkConstraintRef *
+gtk_constraint_solver_add_constraint (GtkConstraintSolver *self,
+                                      GtkConstraintVariable *variable,
+                                      GtkConstraintRelation relation,
+                                      GtkConstraintExpression *expression,
+                                      double strength)
+{
+  GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
+
+  res->solver = self;
+  res->weight = strength;
+  res->is_edit = FALSE;
+  res->is_stay = FALSE;
+  res->relation = relation;
+
+  if (expression == NULL)
+    res->expression = gtk_constraint_expression_new_from_variable (variable);
+  else
+    {
+      res->expression = expression;
+
+      if (variable != NULL)
+        {
+          switch (res->relation)
+            {
+            case GTK_CONSTRAINT_RELATION_EQ:
+              gtk_constraint_expression_add_variable (res->expression,
+                                                      variable, -1.0,
+                                                      NULL,
+                                                      self);
+              break;
+
+            case GTK_CONSTRAINT_RELATION_LE:
+              gtk_constraint_expression_add_variable (res->expression,
+                                                      variable, -1.0,
+                                                      NULL,
+                                                      self);
+              break;
+
+            case GTK_CONSTRAINT_RELATION_GE:
+              gtk_constraint_expression_multiply_by (res->expression, -1.0);
+              gtk_constraint_expression_add_variable (res->expression,
+                                                      variable, 1.0,
+                                                      NULL,
+                                                      self);
+              break;
+
+            default:
+              g_assert_not_reached ();
+            }
+        }
+    }
+
+  gtk_constraint_solver_add_constraint_internal (self, res);
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_solver_add_stay_variable:
+ * @self: a #GtkConstraintSolver
+ * @variable: a stay #GtkConstraintVariable
+ * @strength: the weight of the constraint
+ *
+ * Adds a constraint on a stay @variable with the given @strength.
+ *
+ * A stay variable is an "anchor" in the system: a variable that is
+ * supposed to stay at the same value.
+ *
+ * Returns: (transfer none): a reference to the newly created
+ *   constraint; you can use the reference to remove the
+ *   constraint from the solver
+ */
+GtkConstraintRef *
+gtk_constraint_solver_add_stay_variable (GtkConstraintSolver *self,
+                                         GtkConstraintVariable *variable,
+                                         double strength)
+{
+  GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
+
+  res->solver = self;
+  res->variable = gtk_constraint_variable_ref (variable);
+  res->relation = GTK_CONSTRAINT_RELATION_EQ;
+  res->weight = strength;
+  res->is_stay = TRUE;
+  res->is_edit = FALSE;
+
+  res->expression = gtk_constraint_expression_new (gtk_constraint_variable_get_value (res->variable));
+  gtk_constraint_expression_add_variable (res->expression,
+                                          res->variable, -1.0,
+                                          NULL,
+                                          self);
+
+#ifdef G_ENABLE_DEBUG
+  {
+    char *str = gtk_constraint_expression_to_string (res->expression);
+    g_debug ("Adding stay variable: %s", str);
+    g_free (str);
+  }
+#endif
+
+  gtk_constraint_solver_add_constraint_internal (self, res);
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_solver_remove_stay_variable:
+ * @self: a #GtkConstraintSolver
+ * @variable: a stay variable
+ *
+ * Removes the stay constraint associated to @variable.
+ *
+ * This is a convenience function for gtk_constraint_solver_remove_constraint().
+ */
+void
+gtk_constraint_solver_remove_stay_variable (GtkConstraintSolver *self,
+                                            GtkConstraintVariable *variable)
+{
+  StayInfo *si = g_hash_table_lookup (self->stay_var_map, variable);
+
+  if (si == NULL)
+    {
+      char *str = gtk_constraint_variable_to_string (variable);
+
+      g_critical ("Unknown stay variable '%s'", str);
+
+      g_free (str);
+
+      return;
+    }
+
+  gtk_constraint_solver_remove_constraint (self, si->constraint);
+}
+
+/*< private >
+ * gtk_constraint_solver_add_edit_variable:
+ * @self: a #GtkConstraintSolver
+ * @variable: an edit variable
+ * @strength: the strength of the constraint
+ *
+ * Adds an editable constraint to the @solver.
+ *
+ * Editable constraints can be used to suggest values to a
+ * #GtkConstraintSolver inside an edit phase, for instance: if
+ * you want to change the value of a variable without necessarily
+ * insert a new constraint every time.
+ *
+ * See also: gtk_constraint_solver_suggest_value()
+ *
+ * Returns: (transfer none): a reference to the newly added constraint
+ */
+GtkConstraintRef *
+gtk_constraint_solver_add_edit_variable (GtkConstraintSolver *self,
+                                         GtkConstraintVariable *variable,
+                                         double strength)
+{
+  GtkConstraintRef *res = g_new0 (GtkConstraintRef, 1);
+
+  res->solver = self;
+  res->variable = gtk_constraint_variable_ref (variable);
+  res->relation = GTK_CONSTRAINT_RELATION_EQ;
+  res->weight = strength;
+  res->is_stay = FALSE;
+  res->is_edit = TRUE;
+
+  res->expression = gtk_constraint_expression_new (gtk_constraint_variable_get_value (variable));
+  gtk_constraint_expression_add_variable (res->expression,
+                                          variable, -1.0,
+                                          NULL,
+                                          self);
+
+  gtk_constraint_solver_add_constraint_internal (self, res);
+
+  return res;
+}
+
+/*< private >
+ * gtk_constraint_solver_remove_edit_variable:
+ * @self: a #GtkConstraintSolver
+ * @variable: an edit variable
+ *
+ * Removes the edit constraint associated to @variable.
+ *
+ * This is a convenience function around gtk_constraint_solver_remove_constraint().
+ */
+void
+gtk_constraint_solver_remove_edit_variable (GtkConstraintSolver *self,
+                                            GtkConstraintVariable *variable)
+{
+  EditInfo *ei = g_hash_table_lookup (self->edit_var_map, variable);
+
+  if (ei == NULL)
+    {
+      char *str = gtk_constraint_variable_to_string (variable);
+
+      g_critical ("Unknown stay variable '%s'", str);
+
+      g_free (str);
+
+      return;
+    }
+
+  gtk_constraint_solver_remove_constraint (self, ei->constraint);
+}
+
+/*< private >
+ * gtk_constraint_solver_remove_constraint:
+ * @self: a #GtkConstraintSolver
+ * @constraint: a constraint reference
+ *
+ * Removes a @constraint from the @solver.
+ */
+void
+gtk_constraint_solver_remove_constraint (GtkConstraintSolver *self,
+                                         GtkConstraintRef *constraint)
+{
+  GtkConstraintExpression *z_row;
+  GtkConstraintVariable *marker;
+  GtkConstraintVariableSet *error_vars;
+  GtkConstraintVariableSetIter iter;
+
+  if (!g_hash_table_contains (self->constraints, constraint))
+    return;
+
+  self->needs_solving = TRUE;
+
+  gtk_constraint_solver_reset_stay_constants (self);
+
+  z_row = g_hash_table_lookup (self->rows, self->objective);
+  error_vars = g_hash_table_lookup (self->error_vars, constraint);
+
+  if (error_vars != NULL)
+    {
+      GtkConstraintVariable *v;
+
+      gtk_constraint_variable_set_iter_init (&iter, error_vars);
+      while (gtk_constraint_variable_set_iter_next (&iter, &v))
+        {
+          GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
+
+          if (e == NULL)
+            {
+              gtk_constraint_expression_add_variable (z_row,
+                                                      v,
+                                                      constraint->weight,
+                                                      self->objective,
+                                                      self);
+            }
+          else
+            {
+              gtk_constraint_expression_add_expression (z_row,
+                                                        e,
+                                                        constraint->weight,
+                                                        self->objective,
+                                                        self);
+            }
+        }
+    }
+
+  marker = g_hash_table_lookup (self->marker_vars, constraint);
+  if (marker == NULL)
+    {
+      g_critical ("Constraint %p not found", constraint);
+      return;
+    }
+
+  g_hash_table_remove (self->marker_vars, constraint);
+
+  if (g_hash_table_lookup (self->rows, marker) == NULL)
+    {
+      GtkConstraintVariableSet *set = g_hash_table_lookup (self->columns, marker);
+      GtkConstraintVariable *exit_var = NULL;
+      GtkConstraintVariable *v;
+      double min_ratio = 0;
+
+      if (set == NULL)
+        goto no_columns;
+
+      gtk_constraint_variable_set_iter_init (&iter, set);
+      while (gtk_constraint_variable_set_iter_next (&iter, &v))
+        {
+          if (gtk_constraint_variable_is_restricted (v))
+            {
+              GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
+              double coeff = gtk_constraint_expression_get_coefficient (e, marker);
+
+              if (coeff < 0.0)
+                {
+                  double r = -gtk_constraint_expression_get_constant (e) / coeff;
+
+                  if (exit_var == NULL ||
+                      r < min_ratio ||
+                      G_APPROX_VALUE (r, min_ratio, 0.0001))
+                    {
+                      min_ratio = r;
+                      exit_var = v;
+                    }
+                }
+            }
+        }
+
+      if (exit_var == NULL)
+        {
+          gtk_constraint_variable_set_iter_init (&iter, set);
+          while (gtk_constraint_variable_set_iter_next (&iter, &v))
+            {
+              if (gtk_constraint_variable_is_restricted (v))
+                {
+                  GtkConstraintExpression *e = g_hash_table_lookup (self->rows, v);
+                  double coeff = gtk_constraint_expression_get_coefficient (e, marker);
+                  double r = 0.0;
+
+                  if (!G_APPROX_VALUE (coeff, 0.0, 0.0001))
+                    r = gtk_constraint_expression_get_constant (e) / coeff;
+
+                  if (exit_var == NULL || r < min_ratio)
+                    {
+                      min_ratio = r;
+                      exit_var = v;
+                    }
+                }
+            }
+        }
+
+      if (exit_var == NULL)
+        {
+          if (gtk_constraint_variable_set_size (set) == 0)
+            gtk_constraint_solver_remove_column (self, marker);
+          else
+            {
+              gtk_constraint_variable_set_iter_init (&iter, set);
+              while (gtk_constraint_variable_set_iter_next (&iter, &v))
+                {
+                  if (v != self->objective)
+                    {
+                      exit_var = v;
+                      break;
+                    }
+                }
+            }
+        }
+
+      if (exit_var != NULL)
+        gtk_constraint_solver_pivot (self, marker, exit_var);
+    }
+
+no_columns:
+  if (g_hash_table_lookup (self->rows, marker) != NULL)
+    gtk_constraint_solver_remove_row (self, marker, TRUE);
+  else
+    gtk_constraint_variable_unref (marker);
+
+  if (error_vars != NULL)
+    {
+      GtkConstraintVariable *v;
+
+      gtk_constraint_variable_set_iter_init (&iter, error_vars);
+      while (gtk_constraint_variable_set_iter_next (&iter, &v))
+        {
+          if (v != marker)
+            gtk_constraint_solver_remove_column (self, v);
+        }
+    }
+
+  if (constraint->is_stay)
+    {
+      if (error_vars != NULL)
+        {
+          GPtrArray *remaining =
+            g_ptr_array_new_with_free_func ((GDestroyNotify) gtk_constraint_variable_pair_free);
+
+          int i = 0;
+
+          for (i = 0; i < self->stay_error_vars->len; i++)
+            {
+              GtkConstraintVariablePair *pair = g_ptr_array_index (self->stay_error_vars, i);
+              gboolean found = FALSE;
+
+              if (gtk_constraint_variable_set_remove (error_vars, pair->first))
+                found = TRUE;
+
+              if (gtk_constraint_variable_set_remove (error_vars, pair->second))
+                found = FALSE;
+
+              if (!found)
+                g_ptr_array_add (remaining, gtk_constraint_variable_pair_new (pair->first, pair->second));
+            }
+
+          g_clear_pointer (&self->stay_error_vars, g_ptr_array_unref);
+          self->stay_error_vars = remaining;
+        }
+
+      g_hash_table_remove (self->stay_var_map, constraint->variable);
+    }
+  else if (constraint->is_edit)
+    {
+      EditInfo *ei = g_hash_table_lookup (self->edit_var_map, constraint->variable);
+
+      gtk_constraint_solver_remove_column (self, ei->eminus);
+
+      g_hash_table_remove (self->edit_var_map, constraint->variable);
+    }
+
+  if (error_vars != NULL)
+    g_hash_table_remove (self->error_vars, constraint);
+
+  if (self->auto_solve)
+    {
+      gtk_constraint_solver_optimize (self, self->objective);
+      gtk_constraint_solver_set_external_variables (self);
+    }
+
+  g_hash_table_remove (self->constraints, constraint);
+}
+
+/*< private >
+ * gtk_constraint_solver_suggest_value:
+ * @self: a #GtkConstraintSolver
+ * @variable: a #GtkConstraintVariable
+ * @value: the suggested value for @variable
+ *
+ * Suggests a new @value for an edit @variable.
+ *
+ * The @variable must be an edit variable, and the solver must be
+ * in an edit phase.
+ */
+void
+gtk_constraint_solver_suggest_value (GtkConstraintSolver *self,
+                                     GtkConstraintVariable *variable,
+                                     double value)
+{
+  EditInfo *ei = g_hash_table_lookup (self->edit_var_map, variable);
+  if (ei == NULL)
+    {
+      g_critical ("Suggesting value '%g' but variable %p is not editable",
+                  value, variable);
+      return;
+    }
+
+  if (!self->in_edit_phase)
+    {
+      g_critical ("Suggesting value '%g' for variable '%p' but solver is "
+                  "not in an edit phase",
+                  value, variable);
+      return;
+    }
+
+  ei->prev_constant = value - ei->prev_constant;
+
+  gtk_constraint_solver_delta_edit_constant (self, ei->prev_constant, ei->eplus, ei->eminus);
+}
+
+/*< private >
+ * gtk_constraint_solver_has_stay_variable:
+ * @solver: a #GtkConstraintSolver
+ * @variable: a #GtkConstraintVariable
+ *
+ * Checks whether @variable is a stay variable.
+ *
+ * Returns: %TRUE if the variable is a stay variable
+ */
+gboolean
+gtk_constraint_solver_has_stay_variable (GtkConstraintSolver   *solver,
+                                         GtkConstraintVariable *variable)
+{
+  g_return_val_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver), FALSE);
+  g_return_val_if_fail (variable != NULL, FALSE);
+
+  return g_hash_table_contains (solver->stay_var_map, variable);
+}
+
+/*< private >
+ * gtk_constraint_solver_has_edit_variable:
+ * @solver: a #GtkConstraintSolver
+ * @variable: a #GtkConstraintVariable
+ *
+ * Checks whether @variable is an edit variable.
+ *
+ * Returns: %TRUE if the variable is an edit variable
+ */
+gboolean
+gtk_constraint_solver_has_edit_variable (GtkConstraintSolver   *solver,
+                                         GtkConstraintVariable *variable)
+{
+  g_return_val_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver), FALSE);
+  g_return_val_if_fail (variable != NULL, FALSE);
+
+  return g_hash_table_contains (solver->edit_var_map, variable);
+}
+
+/*< private >
+ * gtk_constraint_solver_begin_edit:
+ * @solver: a #GtkConstraintSolver
+ *
+ * Begins the edit phase for a constraint system.
+ *
+ * Typically, you need to add new edit constraints for a variable to the
+ * system, using gtk_constraint_solver_add_edit_variable(); then you
+ * call this function and suggest values for the edit variables, using
+ * gtk_constraint_solver_suggest_value(). After you suggested a value
+ * for all the variables you need to edit, you will need to call
+ * gtk_constraint_solver_resolve() to solve the system, and get the value
+ * of the various variables that you're interested in.
+ *
+ * Once you completed the edit phase, call gtk_constraint_solver_end_edit()
+ * to remove all the edit variables.
+ */
+void
+gtk_constraint_solver_begin_edit (GtkConstraintSolver *solver)
+{
+  g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
+
+  if (g_hash_table_size (solver->edit_var_map) == 0)
+    {
+      g_critical ("Solver %p does not have editable variables.", solver);
+      return;
+    }
+
+  g_ptr_array_set_size (solver->infeasible_rows, 0);
+  gtk_constraint_solver_reset_stay_constants (solver);
+
+  solver->in_edit_phase = TRUE;
+}
+
+static void
+edit_info_free (gpointer data)
+{
+  g_free (data);
+}
+
+/*< private >
+ * gtk_constraint_solver_end_edit:
+ * @solver: a #GtkConstraintSolver
+ *
+ * Ends the edit phase for a constraint system, and clears
+ * all the edit variables introduced.
+ */
+void
+gtk_constraint_solver_end_edit (GtkConstraintSolver *solver)
+{
+  solver->in_edit_phase = FALSE;
+
+  gtk_constraint_solver_resolve (solver);
+
+  g_hash_table_remove_all (solver->edit_var_map);
+}
+
+void
+gtk_constraint_solver_clear (GtkConstraintSolver *solver)
+{
+  g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
+
+  g_hash_table_remove_all (solver->constraints);
+  g_hash_table_remove_all (solver->external_rows);
+  g_hash_table_remove_all (solver->external_parametric_vars);
+  g_hash_table_remove_all (solver->error_vars);
+  g_hash_table_remove_all (solver->marker_vars);
+  g_hash_table_remove_all (solver->edit_var_map);
+  g_hash_table_remove_all (solver->stay_var_map);
+
+  g_ptr_array_set_size (solver->infeasible_rows, 0);
+  g_ptr_array_set_size (solver->stay_error_vars, 0);
+
+  g_hash_table_remove_all (solver->rows);
+  g_hash_table_remove_all (solver->columns);
+
+  /* The rows table owns the objective variable */
+  solver->objective = gtk_constraint_variable_new_objective ("Z");
+  g_hash_table_insert (solver->rows,
+                       solver->objective,
+                       gtk_constraint_expression_new (0.0));
+
+  solver->slack_counter = 0;
+  solver->dummy_counter = 0;
+  solver->artificial_counter = 0;
+  solver->freeze_count = 0;
+
+  solver->needs_solving = FALSE;
+  solver->auto_solve = TRUE;
+}
+
+char *
+gtk_constraint_solver_to_string (GtkConstraintSolver *solver)
+{
+  GString *buf = g_string_new (NULL);
+
+  g_string_append (buf, "Tableau info:\n");
+  g_string_append_printf (buf, "Rows: %d (= %d constraints)\n",
+                          g_hash_table_size (solver->rows),
+                          g_hash_table_size (solver->rows) - 1);
+  g_string_append_printf (buf, "Columns: %d\n",
+                          g_hash_table_size (solver->columns));
+  g_string_append_printf (buf, "Infeasible rows: %d\n",
+                          solver->infeasible_rows->len);
+  g_string_append_printf (buf, "External basic variables: %d\n",
+                          g_hash_table_size (solver->external_rows));
+  g_string_append_printf (buf, "External parametric variables: %d\n",
+                          g_hash_table_size (solver->external_parametric_vars));
+
+  g_string_append (buf, "Constraints:");
+  if (g_hash_table_size (solver->constraints) == 0)
+    g_string_append (buf, " <empty>\n");
+  else
+    {
+      GHashTableIter iter;
+      gpointer key_p;
+
+      g_string_append (buf, "\n");
+
+      g_hash_table_iter_init (&iter, solver->constraints);
+      while (g_hash_table_iter_next (&iter, &key_p, NULL))
+        {
+          char *ref = gtk_constraint_ref_to_string (key_p);
+
+          g_string_append_printf (buf, "  %s\n", ref);
+
+          g_free (ref);
+        }
+    }
+
+  g_string_append (buf, "Stay error vars:");
+  if (solver->stay_error_vars->len == 0)
+    g_string_append (buf, " <empty>\n");
+  else
+    {
+      g_string_append (buf, "\n");
+
+      for (int i = 0; i < solver->stay_error_vars->len; i++)
+        {
+          const GtkConstraintVariablePair *pair = g_ptr_array_index (solver->stay_error_vars, i);
+          char *first_s = gtk_constraint_variable_to_string (pair->first);
+          char *second_s = gtk_constraint_variable_to_string (pair->second);
+
+          g_string_append_printf (buf, "  (%s, %s)\n", first_s, second_s);
+
+          g_free (first_s);
+          g_free (second_s);
+        }
+    }
+
+  g_string_append (buf, "Edit var map:");
+  if (g_hash_table_size (solver->edit_var_map) == 0)
+    g_string_append (buf, " <empty>\n");
+  else
+    {
+      GHashTableIter iter;
+      gpointer key_p, value_p;
+
+      g_string_append (buf, "\n");
+
+      g_hash_table_iter_init (&iter, solver->edit_var_map);
+      while (g_hash_table_iter_next (&iter, &key_p, &value_p))
+        {
+          char *var = gtk_constraint_variable_to_string (key_p);
+          const EditInfo *ei = value_p;
+          char *c = gtk_constraint_ref_to_string (ei->constraint);
+
+          g_string_append_printf (buf, "  %s => %s\n", var, c);
+
+          g_free (var);
+          g_free (c);
+        }
+    }
+
+  return g_string_free (buf, FALSE);
+}
diff --git a/gtk/gtkconstraintsolverprivate.h b/gtk/gtkconstraintsolverprivate.h
new file mode 100644
index 0000000000..807b0b08d6
--- /dev/null
+++ b/gtk/gtkconstraintsolverprivate.h
@@ -0,0 +1,114 @@
+/* gtkconstraintsolverprivate.h: Constraint solver based on the Cassowary method
+ * Copyright 2019  GNOME Foundation
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Author: Emmanuele Bassi
+ */
+
+#pragma once
+
+#include "gtkconstrainttypesprivate.h"
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_CONSTRAINT_SOLVER (gtk_constraint_solver_get_type())
+
+G_DECLARE_FINAL_TYPE (GtkConstraintSolver, gtk_constraint_solver, GTK, CONSTRAINT_SOLVER, GObject)
+
+GtkConstraintSolver *
+gtk_constraint_solver_new (void);
+
+void
+gtk_constraint_solver_freeze (GtkConstraintSolver *solver);
+
+void
+gtk_constraint_solver_thaw (GtkConstraintSolver *solver);
+
+void
+gtk_constraint_solver_resolve (GtkConstraintSolver *solver);
+
+GtkConstraintVariable *
+gtk_constraint_solver_create_variable (GtkConstraintSolver *solver,
+                                       const char          *prefix,
+                                       const char          *name,
+                                       double               value);
+
+GtkConstraintRef *
+gtk_constraint_solver_add_constraint (GtkConstraintSolver     *solver,
+                                      GtkConstraintVariable   *variable,
+                                      GtkConstraintRelation    relation,
+                                      GtkConstraintExpression *expression,
+                                      double                   strength);
+
+void
+gtk_constraint_solver_remove_constraint (GtkConstraintSolver *solver,
+                                         GtkConstraintRef    *reference);
+
+GtkConstraintRef *
+gtk_constraint_solver_add_stay_variable (GtkConstraintSolver   *solver,
+                                         GtkConstraintVariable *variable,
+                                         double                 strength);
+
+void
+gtk_constraint_solver_remove_stay_variable (GtkConstraintSolver   *solver,
+                                            GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_solver_has_stay_variable (GtkConstraintSolver   *solver,
+                                         GtkConstraintVariable *variable);
+
+GtkConstraintRef *
+gtk_constraint_solver_add_edit_variable (GtkConstraintSolver   *solver,
+                                         GtkConstraintVariable *variable,
+                                         double                 strength);
+
+void
+gtk_constraint_solver_remove_edit_variable (GtkConstraintSolver   *solver,
+                                            GtkConstraintVariable *variable);
+
+gboolean
+gtk_constraint_solver_has_edit_variable (GtkConstraintSolver   *solver,
+                                         GtkConstraintVariable *variable);
+
+void
+gtk_constraint_solver_suggest_value (GtkConstraintSolver   *solver,
+                                     GtkConstraintVariable *variable,
+                                     double                 value);
+
+void
+gtk_constraint_solver_begin_edit (GtkConstraintSolver *solver);
+
+void
+gtk_constraint_solver_end_edit (GtkConstraintSolver *solver);
+
+void
+gtk_constraint_solver_note_added_variable (GtkConstraintSolver *self,
+                                           GtkConstraintVariable *variable,
+                                           GtkConstraintVariable *subject);
+
+void
+gtk_constraint_solver_note_removed_variable (GtkConstraintSolver *self,
+                                             GtkConstraintVariable *variable,
+                                             GtkConstraintVariable *subject);
+
+void
+gtk_constraint_solver_clear (GtkConstraintSolver *solver);
+
+char *
+gtk_constraint_solver_to_string (GtkConstraintSolver *solver);
+
+G_END_DECLS
diff --git a/gtk/gtkconstrainttypesprivate.h b/gtk/gtkconstrainttypesprivate.h
new file mode 100644
index 0000000000..052280ae98
--- /dev/null
+++ b/gtk/gtkconstrainttypesprivate.h
@@ -0,0 +1,50 @@
+/* gtkconstrainttypesprivate.h: Private types for the constraint solver
+ * Copyright 2019  GNOME Foundation
+ *
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Author: Emmanuele Bassi
+ */
+
+#pragma once
+
+#include <gtk/gtktypes.h>
+#include <gtk/gtkenums.h>
+
+G_BEGIN_DECLS
+
+typedef struct _GtkConstraintVariable           GtkConstraintVariable;
+typedef struct _GtkConstraintExpression         GtkConstraintExpression;
+typedef struct _GtkConstraintExpressionBuilder  GtkConstraintExpressionBuilder;
+
+/*< private >
+ * GtkConstraintRef:
+ *
+ * A reference to a constraint stored inside the solver; while #GtkConstraint
+ * represent the public API, a #GtkConstraintRef represents data stored inside
+ * the solver. A #GtkConstraintRef is completely opaque, and should only be
+ * used to remove a constraint from the solver.
+ */
+typedef struct _GtkConstraintRef                GtkConstraintRef;
+
+/*< private >
+ * GtkConstraintSolver:
+ *
+ * A simplex solver using the Cassowary constraint solving algorithm.
+ */
+typedef struct _GtkConstraintSolver             GtkConstraintSolver;
+
+G_END_DECLS
diff --git a/gtk/gtkenums.h b/gtk/gtkenums.h
index 6d1bf81295..468adcdc81 100644
--- a/gtk/gtkenums.h
+++ b/gtk/gtkenums.h
@@ -1053,4 +1053,18 @@ typedef enum {
   GTK_PICK_NON_TARGETABLE = 1 << 1
 } GtkPickFlags;
 
+/**
+ * GtkConstraintRelation:
+ * @GTK_CONSTRAINT_RELATION_EQ: Equal
+ * @GTK_CONSTRAINT_RELATION_LE: Less than, or equal
+ * @GTK_CONSTRAINT_RELATION_GE: Greater than, or equal
+ *
+ * The relation between two terms of a constraint.
+ */
+typedef enum {
+  GTK_CONSTRAINT_RELATION_LE = -1,
+  GTK_CONSTRAINT_RELATION_EQ = 0,
+  GTK_CONSTRAINT_RELATION_GE = 1
+} GtkConstraintRelation;
+
 #endif /* __GTK_ENUMS_H__ */
diff --git a/gtk/meson.build b/gtk/meson.build
index 0b271b6f50..b8cef8bb28 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -37,6 +37,8 @@ gtk_private_sources = files([
   'gtkcolorpickershell.c',
   'gtkcolorscale.c',
   'gtkcolorswatch.c',
+  'gtkconstraintexpression.c',
+  'gtkconstraintsolver.c',
   'gtkcssanimatedstyle.c',
   'gtkcssanimation.c',
   'gtkcssarrayvalue.c',
diff --git a/testsuite/gtk/constraint-solver.c b/testsuite/gtk/constraint-solver.c
new file mode 100644
index 0000000000..f09decbaa9
--- /dev/null
+++ b/testsuite/gtk/constraint-solver.c
@@ -0,0 +1,368 @@
+#include <locale.h>
+
+#include "../../gtk/gtkconstrainttypesprivate.h"
+#include "../../gtk/gtkconstraintsolverprivate.h"
+#include "../../gtk/gtkconstraintexpressionprivate.h"
+
+static void
+constraint_solver_simple (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 167.0);
+  GtkConstraintVariable *y = gtk_constraint_solver_create_variable (solver, NULL, "y", 2.0);
+
+  GtkConstraintExpression *e = gtk_constraint_expression_new_from_variable (y);
+
+  gtk_constraint_solver_add_constraint (solver,
+                                        x, GTK_CONSTRAINT_RELATION_EQ, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  double x_value = gtk_constraint_variable_get_value (x);
+  double y_value = gtk_constraint_variable_get_value (y);
+
+  g_assert_cmpfloat_with_epsilon (x_value, y_value, 0.001);
+  g_assert_cmpfloat_with_epsilon (x_value, 0.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (y_value, 0.0, 0.001);
+
+  gtk_constraint_variable_unref (y);
+  gtk_constraint_variable_unref (x);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_stay (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 5.0);
+  GtkConstraintVariable *y = gtk_constraint_solver_create_variable (solver, NULL, "y", 10.0);
+
+  gtk_constraint_solver_add_stay_variable (solver, x, GTK_CONSTRAINT_WEIGHT_WEAK);
+  gtk_constraint_solver_add_stay_variable (solver, y, GTK_CONSTRAINT_WEIGHT_WEAK);
+
+  double x_value = gtk_constraint_variable_get_value (x);
+  double y_value = gtk_constraint_variable_get_value (y);
+
+  g_assert_cmpfloat_with_epsilon (x_value, 5.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (y_value, 10.0, 0.001);
+
+  gtk_constraint_variable_unref (x);
+  gtk_constraint_variable_unref (y);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_variable_geq_constant (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 10.0);
+  GtkConstraintExpression *e = gtk_constraint_expression_new (100.0);
+
+  gtk_constraint_solver_add_constraint (solver,
+                                        x, GTK_CONSTRAINT_RELATION_GE, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  double x_value = gtk_constraint_variable_get_value (x);
+
+  g_assert_cmpfloat (x_value, >=, 100.0);
+
+  gtk_constraint_variable_unref (x);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_variable_leq_constant (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 100.0);
+  GtkConstraintExpression *e = gtk_constraint_expression_new (10.0);
+
+  gtk_constraint_solver_add_constraint (solver,
+                                        x, GTK_CONSTRAINT_RELATION_LE, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  double x_value = gtk_constraint_variable_get_value (x);
+
+  g_assert_cmpfloat (x_value, <=, 10.0);
+
+  gtk_constraint_variable_unref (x);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_variable_eq_constant (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 10.0);
+  GtkConstraintExpression *e = gtk_constraint_expression_new (100.0);
+
+  gtk_constraint_solver_add_constraint (solver,
+                                        x, GTK_CONSTRAINT_RELATION_EQ, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  double x_value = gtk_constraint_variable_get_value (x);
+
+  g_assert_cmpfloat_with_epsilon (x_value, 100.0, 0.001);
+
+  gtk_constraint_variable_unref (x);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_eq_with_stay (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 10.0);
+  GtkConstraintVariable *width = gtk_constraint_solver_create_variable (solver, NULL, "width", 10.0);
+  GtkConstraintVariable *right_min = gtk_constraint_solver_create_variable (solver, NULL, "rightMin", 100.0);
+
+  GtkConstraintExpressionBuilder builder;
+  gtk_constraint_expression_builder_init (&builder, solver);
+  gtk_constraint_expression_builder_term (&builder, x);
+  gtk_constraint_expression_builder_plus (&builder);
+  gtk_constraint_expression_builder_term (&builder, width);
+  GtkConstraintExpression *right = gtk_constraint_expression_builder_finish (&builder);
+
+  gtk_constraint_solver_add_stay_variable (solver, width, GTK_CONSTRAINT_WEIGHT_WEAK);
+  gtk_constraint_solver_add_stay_variable (solver, right_min, GTK_CONSTRAINT_WEIGHT_WEAK);
+  gtk_constraint_solver_add_constraint (solver,
+                                        right_min, GTK_CONSTRAINT_RELATION_EQ, right,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  double x_value = gtk_constraint_variable_get_value (x);
+  double width_value = gtk_constraint_variable_get_value (width);
+
+  g_assert_cmpfloat_with_epsilon (x_value, 90.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (width_value, 10.0, 0.001);
+
+  gtk_constraint_variable_unref (right_min);
+  gtk_constraint_variable_unref (width);
+  gtk_constraint_variable_unref (x);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_cassowary (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *x = gtk_constraint_solver_create_variable (solver, NULL, "x", 0.0);
+  GtkConstraintVariable *y = gtk_constraint_solver_create_variable (solver, NULL, "y", 0.0);
+
+  GtkConstraintExpression *e;
+
+  e = gtk_constraint_expression_new_from_variable (y);
+  gtk_constraint_solver_add_constraint (solver,
+                                        x, GTK_CONSTRAINT_RELATION_LE, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  e = gtk_constraint_expression_plus_constant (gtk_constraint_expression_new_from_variable (x), 3.0);
+  gtk_constraint_solver_add_constraint (solver,
+                                        y, GTK_CONSTRAINT_RELATION_EQ, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  e = gtk_constraint_expression_new (10.0);
+  gtk_constraint_solver_add_constraint (solver,
+                                        x, GTK_CONSTRAINT_RELATION_EQ, e,
+                                        GTK_CONSTRAINT_WEIGHT_WEAK);
+
+  e = gtk_constraint_expression_new (10.0);
+  gtk_constraint_solver_add_constraint (solver,
+                                        y, GTK_CONSTRAINT_RELATION_EQ, e,
+                                        GTK_CONSTRAINT_WEIGHT_WEAK);
+
+  double x_val = gtk_constraint_variable_get_value (x);
+  double y_val = gtk_constraint_variable_get_value (y);
+
+  g_test_message ("x = %g, y = %g", x_val, y_val);
+
+  /* The system is unstable and has two possible solutions we need to test */
+  g_assert_true ((G_APPROX_VALUE (x_val, 10.0, 1e-8) &&
+                  G_APPROX_VALUE (y_val, 13.0, 1e-8)) ||
+                 (G_APPROX_VALUE (x_val,  7.0, 1e-8) &&
+                  G_APPROX_VALUE (y_val, 10.0, 1e-8)));
+
+  gtk_constraint_variable_unref (x);
+  gtk_constraint_variable_unref (y);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_edit_var_required (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *a = gtk_constraint_solver_create_variable (solver, NULL, "a", 0.0);
+  gtk_constraint_solver_add_stay_variable (solver, a, GTK_CONSTRAINT_WEIGHT_STRONG);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (a), 0.0, 0.001);
+
+  gtk_constraint_solver_add_edit_variable (solver, a, GTK_CONSTRAINT_WEIGHT_REQUIRED);
+  gtk_constraint_solver_begin_edit (solver);
+  gtk_constraint_solver_suggest_value (solver, a, 2.0);
+  gtk_constraint_solver_resolve (solver);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (a), 2.0, 0.001);
+
+  gtk_constraint_solver_suggest_value (solver, a, 10.0);
+  gtk_constraint_solver_resolve (solver);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (a), 10.0, 0.001);
+
+  gtk_constraint_solver_end_edit (solver);
+
+  gtk_constraint_variable_unref (a);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_edit_var_suggest (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *a = gtk_constraint_solver_create_variable (solver, NULL, "a", 0.0);
+  GtkConstraintVariable *b = gtk_constraint_solver_create_variable (solver, NULL, "b", 0.0);
+
+  gtk_constraint_solver_add_stay_variable (solver, a, GTK_CONSTRAINT_WEIGHT_STRONG);
+
+  GtkConstraintExpression *e = gtk_constraint_expression_new_from_variable (b);
+  gtk_constraint_solver_add_constraint (solver,
+                                        a, GTK_CONSTRAINT_RELATION_EQ, e,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  gtk_constraint_solver_resolve (solver);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (a), 0.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (b), 0.0, 0.001);
+
+  gtk_constraint_solver_add_edit_variable (solver, a, GTK_CONSTRAINT_WEIGHT_REQUIRED);
+  gtk_constraint_solver_begin_edit (solver);
+
+  gtk_constraint_solver_suggest_value (solver, a, 2.0);
+  gtk_constraint_solver_resolve (solver);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (a), 2.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (b), 2.0, 0.001);
+
+  gtk_constraint_solver_suggest_value (solver, a, 10.0);
+  gtk_constraint_solver_resolve (solver);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (a), 10.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (b), 10.0, 0.001);
+
+  gtk_constraint_variable_unref (a);
+  gtk_constraint_variable_unref (b);
+
+  g_object_unref (solver);
+}
+
+static void
+constraint_solver_paper (void)
+{
+  GtkConstraintSolver *solver = gtk_constraint_solver_new ();
+
+  GtkConstraintVariable *left = gtk_constraint_solver_create_variable (solver, NULL, "left", 0.0);
+  GtkConstraintVariable *middle = gtk_constraint_solver_create_variable (solver, NULL, "middle", 0.0);
+  GtkConstraintVariable *right = gtk_constraint_solver_create_variable (solver, NULL, "right", 0.0);
+
+  GtkConstraintExpressionBuilder builder;
+  GtkConstraintExpression *expr;
+
+  gtk_constraint_expression_builder_init (&builder, solver);
+  gtk_constraint_expression_builder_term (&builder, left);
+  gtk_constraint_expression_builder_plus (&builder);
+  gtk_constraint_expression_builder_term (&builder, right);
+  gtk_constraint_expression_builder_divide_by (&builder);
+  gtk_constraint_expression_builder_constant (&builder, 2.0);
+  expr = gtk_constraint_expression_builder_finish (&builder);
+  gtk_constraint_solver_add_constraint (solver,
+                                        middle, GTK_CONSTRAINT_RELATION_EQ, expr,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  gtk_constraint_expression_builder_init (&builder, solver);
+  gtk_constraint_expression_builder_term (&builder, left);
+  gtk_constraint_expression_builder_plus (&builder);
+  gtk_constraint_expression_builder_constant (&builder, 10.0);
+  expr = gtk_constraint_expression_builder_finish (&builder);
+  gtk_constraint_solver_add_constraint (solver,
+                                        right, GTK_CONSTRAINT_RELATION_EQ, expr,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  expr = gtk_constraint_expression_new (100.0);
+  gtk_constraint_solver_add_constraint (solver,
+                                        right, GTK_CONSTRAINT_RELATION_LE, expr,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  expr = gtk_constraint_expression_new (0.0);
+  gtk_constraint_solver_add_constraint (solver,
+                                        left, GTK_CONSTRAINT_RELATION_GE, expr,
+                                        GTK_CONSTRAINT_WEIGHT_REQUIRED);
+
+  g_test_message ("Check constraints hold");
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (middle),
+                                  (gtk_constraint_variable_get_value (left) + gtk_constraint_variable_get_value (right)) / 2.0,
+                                  0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (right),
+                                  gtk_constraint_variable_get_value (left) + 10.0,
+                                  0.001);
+  g_assert_cmpfloat (gtk_constraint_variable_get_value (right), <=, 100.0);
+  g_assert_cmpfloat (gtk_constraint_variable_get_value (left), >=, 0.0);
+
+  gtk_constraint_variable_set_value (middle, 45.0);
+  gtk_constraint_solver_add_stay_variable (solver, middle, GTK_CONSTRAINT_WEIGHT_WEAK);
+
+  g_test_message ("Check constraints hold after setting middle");
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (middle),
+                                  (gtk_constraint_variable_get_value (left) + gtk_constraint_variable_get_value (right)) / 2.0,
+                                  0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (right),
+                                  gtk_constraint_variable_get_value (left) + 10.0,
+                                  0.001);
+  g_assert_cmpfloat (gtk_constraint_variable_get_value (right), <=, 100.0);
+  g_assert_cmpfloat (gtk_constraint_variable_get_value (left), >=, 0.0);
+
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (left), 40.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (middle), 45.0, 0.001);
+  g_assert_cmpfloat_with_epsilon (gtk_constraint_variable_get_value (right), 50.0, 0.001);
+
+  gtk_constraint_variable_unref (left);
+  gtk_constraint_variable_unref (middle);
+  gtk_constraint_variable_unref (right);
+
+  g_object_unref (solver);
+}
+
+int
+main (int argc, char *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+  setlocale (LC_ALL, "C");
+
+  g_test_add_func ("/constraint-solver/paper", constraint_solver_paper);
+  g_test_add_func ("/constraint-solver/simple", constraint_solver_simple);
+  g_test_add_func ("/constraint-solver/constant/eq", constraint_solver_variable_eq_constant);
+  g_test_add_func ("/constraint-solver/constant/ge", constraint_solver_variable_geq_constant);
+  g_test_add_func ("/constraint-solver/constant/le", constraint_solver_variable_leq_constant);
+  g_test_add_func ("/constraint-solver/stay/simple", constraint_solver_stay);
+  g_test_add_func ("/constraint-solver/stay/eq", constraint_solver_eq_with_stay);
+  g_test_add_func ("/constraint-solver/cassowary", constraint_solver_cassowary);
+  g_test_add_func ("/constraint-solver/edit/required", constraint_solver_edit_var_required);
+  g_test_add_func ("/constraint-solver/edit/suggest", constraint_solver_edit_var_suggest);
+
+  return g_test_run ();
+}
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index afa5c3c7dd..b02d3f51ce 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -17,6 +17,11 @@ tests = [
   ['builderparser'],
   ['cellarea'],
   ['check-icon-names'],
+  ['constraint-solver', [
+      '../../gtk/gtkconstraintsolver.c',
+      '../../gtk/gtkconstraintexpression.c',
+    ], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']
+  ],
   ['cssprovider'],
   ['rbtree-crash', ['../../gtk/gtkrbtree.c'], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']],
   ['defaultvalue'],