[gtk/wip/ebassi/constraint-layout: 1/5] Add constraint solver
- From: Emmanuele Bassi <ebassi src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/ebassi/constraint-layout: 1/5] Add constraint solver
- Date: Fri, 3 May 2019 16:09:48 +0000 (UTC)
commit 93f495989d4735ba620939843b5c311d0791048d
Author: Emmanuele Bassi <ebassi gnome org>
Date: Tue Apr 9 14:05:48 2019 +0100
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.
gtk/gtkconstraintexpression.c | 1829 +++++++++++++++++++++++++++++
gtk/gtkconstraintexpressionprivate.h | 276 +++++
gtk/gtkconstraintsolver.c | 2085 ++++++++++++++++++++++++++++++++++
gtk/gtkconstraintsolverprivate.h | 108 ++
gtk/gtkconstrainttypesprivate.h | 50 +
gtk/gtkenums.h | 14 +
gtk/meson.build | 2 +
7 files changed, 4364 insertions(+)
---
diff --git a/gtk/gtkconstraintexpression.c b/gtk/gtkconstraintexpression.c
new file mode 100644
index 0000000000..bb050b4e14
--- /dev/null
+++ b/gtk/gtkconstraintexpression.c
@@ -0,0 +1,1829 @@
+/* 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);
+
+ term->prev = self->last_term;
+
+ if (self->first_term == NULL)
+ self->first_term = 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)
+ {
+ prev->next = next;
+ next->prev = 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 = 0.0;
+
+ 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);
+}
+
+/*< 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_added_variable (solver, variable, subject);
+
+ gtk_constraint_expression_remove_term (expression, variable);
+ }
+ 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;
+ double old_coefficient;
+
+ old_coefficient = gtk_constraint_expression_get_coefficient (expression, clv);
+
+ if (expression->terms != NULL &&
+ g_hash_table_contains (expression->terms, 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..5d89c5118e
--- /dev/null
+++ b/gtk/gtkconstraintsolver.c
@@ -0,0 +1,2085 @@
+/* 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>; owns keys */
+ GHashTable *external_rows;
+ /* Set<Variable>; owns 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);
+
+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->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->constraints, g_hash_table_unref);
+
+ /* The columns need to be deleted last, for reference counting */
+ 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_full (NULL, NULL,
+ (GDestroyNotify) gtk_constraint_variable_unref,
+ NULL);
+
+ self->infeasible_rows = g_ptr_array_new ();
+
+ self->external_parametric_vars =
+ g_hash_table_new_full (NULL, NULL,
+ (GDestroyNotify) gtk_constraint_variable_unref,
+ NULL);
+
+ 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,
+ g_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_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;
+}
+
+#ifdef G_ENABLE_DEBUG
+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);
+}
+#endif /* G_ENABLE_DEBUG */
+
+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,
+ gtk_constraint_variable_ref (t_v));
+ }
+
+ if (gtk_constraint_variable_is_external (variable))
+ g_hash_table_add (self->external_rows, gtk_constraint_variable_ref (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_variable_ref (variable);
+
+ 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);
+
+ gtk_constraint_variable_unref (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, gtk_constraint_variable_ref (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;
+
+ g_return_if_fail (entry_var != NULL);
+ g_return_if_fail (exit_var != NULL);
+
+ gtk_constraint_variable_ref (entry_var);
+ gtk_constraint_variable_ref (exit_var);
+
+ 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 (fabs (objective_coefficient) >= -DBL_EPSILON)
+ 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;
+ }
+
+ 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 EMEUS_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");
+
+ if (entry_var != NULL)
+ gtk_constraint_solver_pivot (self, entry_var, exit_var);
+ }
+
+#ifdef EMEUS_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;
+ 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))
+ return t_v;
+ }
+ }
+ 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 (subject != NULL)
+ return retval;
+
+ 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);
+ 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);
+
+ GTK_NOTE (LAYOUT, g_print ("Adding constraint '%s' (normalized expression: '%s')",
+ 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);
+
+ self->needs_solving = TRUE;
+
+ if (self->auto_solve)
+ {
+ gtk_constraint_solver_optimize (self, self->objective);
+ gtk_constraint_solver_set_external_variables (self);
+ }
+
+ gtk_constraint_expression_unref (expr);
+
+ 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)
+{
+ g_return_if_fail (GTK_IS_CONSTRAINT_SOLVER (solver));
+
+#ifdef G_ENABLE_DEBUG
+ gint64 start_time = g_get_monotonic_time ();
+#endif
+
+ 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 = gtk_constraint_expression_ref (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);
+
+ 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;
+}
+
+/*< 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);
+}
diff --git a/gtk/gtkconstraintsolverprivate.h b/gtk/gtkconstraintsolverprivate.h
new file mode 100644
index 0000000000..61e0856bd3
--- /dev/null
+++ b/gtk/gtkconstraintsolverprivate.h
@@ -0,0 +1,108 @@
+/* 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);
+
+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 d18f3f995d..c253fa6bba 100644
--- a/gtk/gtkenums.h
+++ b/gtk/gtkenums.h
@@ -1036,4 +1036,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 76fef838f5..e062be9eef 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -36,6 +36,8 @@ gtk_private_sources = files([
'gtkcolorpickershell.c',
'gtkcolorscale.c',
'gtkcolorswatch.c',
+ 'gtkconstraintexpression.c',
+ 'gtkconstraintsolver.c',
'gtkcssanimatedstyle.c',
'gtkcssanimation.c',
'gtkcssarrayvalue.c',
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
