How Auto-Layout and Constraint layout work

Both Apple’s AutoLayout and Google’s new Constraint layout systems are based on the Casowary algorithm. Speaking with one of the Apple engineers that implemented AutoLayout for Apple, he told me that they chose this particular algorithm because of its ability to update a set of constraints independently without having to update every constraint on the view, something especially useful for mobile layouts where the user can move objects with their finger.

The original paper, re-published in 2002, details a linear arithmetic constraint solving algorithm that allows the user to specify linear equality and inequality constraints, that are either required or a preference. The constraint with the highest strength dominates constraints with a lower strength.

I assume you’ve used AutoLayout or Constraint layout before, and understand the concepts like constraint priority and content hugging and compression resistance priority – these are all things detailed in the Cassowary algorithm. There are four ways that constraint strengths can be compared:

One: A local comparator – Compare on a constraint-by-constraint basis

Two: A global comparator – Take some aggregate measure of the unsatisfied constraints of a given strength

Three: A predicate comparator: Whether we’re concerned only with whether a constraint is   satisfied or not

Four: A metric comparator: How nearly satisfied a constraint is using an error function

Constraints can be expressed purely through linear programming. Let’s take a look at how the algorithm works by actually graphing a set of constraints.

Imagine I want to constraint a UITextField and a UILabel horizontally. Like the following:

interfaceTo do this, I need to define a few constraints. Let’s say:

1. The text field must be at least twice the size of the button

2. The text field and the button must not exceed 300 points

3. The button must be at least 50 points wide

These three constraints are totally satisfiable with the Cassowary algorithm. We can start to graph these to get an idea of how the algorithm works. Let graph numbers 1 and 3:

graph_1What we’ve got here is two constraints set. Everything in the light red tint satisfies the set constraints. If we tried to build the interface now, the algorithm is going to encounter a problem whereby the constraints aren’t fully set. Because we’ve said the text field must be at least as wide as the width of the button * 2, we’ve created a maximisation function that has no upper limit. So the algorithm will see it’s at y = 100, x = 50, which satisfies the two constraints we’ve set. But we defined a maximisation function, the algorithm will try to grow the y axis as much as it can. So it’ll get to y = 250, x = 125, which still satisfies the two set constraints. And it’ll keep going: y = 1500, x = 750? Still satisfies and it can go bigger so it will. y = 1,500,000,000, x = 7,500,000,000? Still satisfies the constraints, etc. It could go on forever. Luckily, the cassowary algorithm accounts for this possibility and prevents a situation like this by adding in its own constraint to set an upper limit. So we need one more constraint to constraint the upper bound. That’s where UITextField + UIButton <= 300 comes in:

graph_2Now we’ve added that final constraint, what will happen is that the UITextField >= 2UIButton constant will continue to be maximised until it gets to the point where maximising it further will break the UITextField + UIButton <= 300 constraint. So now we get the final results of y = 200, x = 100, which satisfies all three constraints. Notice also how the result is in the left corner of that triangle – most of the times the best fit for a set of given constraints will be in one of the corners like this.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s