React has managed to be successful at scale thanks to the fact that it makes finding the root cause of bugs easier through various mechanisms that I explain in this talk.

I was reading about text layout algorithms when I found a striking parallel with Google Plus image layout algorithm. This blog article explains how to find the best line breaks for the image layout.

Line Breaking Algorithm

"Breaking Paragraphs into Lines" article written in 1980 by Donald Knuth and Michael Plass explain how to find the best line breaks in order to make justified text look pretty. The goal is to find where to put line breaks on this paragraph:

In olden times when wishing still helped one, there lived a king
whose daughters were all beautiful; and the youngest was so
beautiful that the sun itself, which has seen so much, was aston-
ished whenever it shone in her face. Close by the kingโ€™s castle lay
a great dark forest, and under an old lime-tree in the forest was
a well, and when the day was very warm, the kingโ€™s child went
out into the forest and sat down by the side of the cool fountain;
and when she was bored she took a golden ball, and threw it up
on high and caught it; and this ball was her favorite plaything.

The first thing to notice is that you cannot break everywhere. In bold, are all the words that can be end of lines while maintaining the constraint of reasonably stretching white spaces in the line.

The first line only has two allowed words while the line before last line has seven. However, the seven are not allowed at the same time, each of them depend on the previous breaks configuration. You can draw a graph that shows all the possible breaks configurations.

graph-knuth

Each transition in this graph represents a line of text (between two breaks). If you can give a fitness value to each line, then you can apply a shortest path algorithm on the graph to find the best breaks configuration. The rest of the article studies a flexible fitness framework that covers all major text layout constraints, but that will not be of any help for our problem.

Parallel with Image Layout

Let's say we want to layout the following five images:

There are many ways to split the images into lines. Here is an exhaustive list of the lines we can have for our five images:

 1
 12      2
 123     23     3
 1234    234    34    4
 12345   2345   345   45

And, we need to link the lines such that they form 12345 at the end. For example 1-2-3-4-5, 12345, 123-4-5 ... I've drawn the full graph so you get an idea of what it looks like:

Like in the line breaking algorithm for text, not all the break positions are wanted. Having only one image would make it way too big, having more than three would make them too small. So we're going to remove them from the graph.

By disallowing some lines, some nodes are now unreachable, trimming down the graph as well. In our example, we are left with only two valid layouts: 123-45 and 12-345.

possible

Cost Metrics

I found it very hard to visually evaluate two layouts. Most of the time, you can easily spot extreme things you don't want such as a giant image or too many small ones. Then, the goal of the cost metric is to minimize the number of those occurrences.

Max height

The first approach tries to respect the constraints of the first-fit heuristic: as soon as the height goes below a threshold, we display the images. We therefore have a MAX_HEIGHT constant that no line can go above.

Because the graph is acyclic, we can use Dijkstra shortest path algorithm to find the longest path (Proof), we just have to return negative costs.

function cost(images, i, j) {
  var height = compute_height(images, i, j);
  if (height > MAX_HEIGHT) { return null; }
 
  // Maximize the number of breaks
  return -1;
  // Maximize the total height
  return -height;
  // Maximize the average image height
  return -(height * (j - i));
}

Target Height

The other approach is to have a target height per line and try to have all the lines as close as possible to the target. The function should return 0 when the line is exactly the size of the target line.

We can write several versions that are going to weight errors differently. You can have a greater variance with a more precise mean, or the opposite. You can prefer being a bit bigger than smaller ...

function cost(images, i, j) {
  var height = compute_height(images, i, j);
 
  // Minimize the total height difference from the target
  return Math.abs(TARGET_HEIGHT - height);
 
  // Minimize the difference to the target and
  // penalize more harshly big differences
  return Math.pow(TARGET_HEIGHT - height, 2);
 
  // Minimize the difference area from the target
  var diff = 0;
  for (; i < = j; ++i) {
    var ratio = images[i].width / images[i].height;
    var target_area = TARGET_HEIGHT * TARGET_HEIGHT * ratio;
    var area = height * height * ratio;
 
    diff += Math.abs(target_area - area);
  }
  return diff;
}

Conclusion

Check-out the first-fit demo versus best break demo (using cost = (target_height - height)^2)

Thanks to an unrelated reading, I've been able to draw a parallel between text display and image layout. Who would have thought that graph theory would be involved there too ๐Ÿ™‚

We can now find the best layout at a cheap cost (nearly-linear with the number of images if you only allow a small number of possible breaks per line). The cost metric allow you to easily disallow patterns you find bad looking.

In this talk I give an overview of the big categories of image layout algorithms with examples for each of them and present criterias to look at when evaluating them.

I'm implementing a layout algorithm in C and want to let the user specify a callback to compute the height based on the width.

Using function pointers, we can provide the callback:

typedef struct {
  float (*measure)(float width);
} layout_node_t;
 
void layout(layout_node_t *node) {
  float width = 10;
  float height = node->measure(width);
}

It works well if we have a function measure that only uses global variables:

float measure(float width) {
  return width * 2;
}
 
int main() {
  layout_node_t node;
  node.measure = measure;
  layout(&node);
}

However, I would like my measure function to take some dynamic input. For example in order to measure an image, you need to take its aspect ratio into account. In JavaScript, I would write the following:

var aspect_ratio = 1.5;
node.measure = function mesure_image(width) {
  return width * aspect_ratio;
}

Unfortunately, C doesn't support closures. I haven't been able to find a way to get a function pointer alone somehow hold some state. The best trade-off I found was to have a void * metadata in the struct and pass it along with the function call. (Thanks Scott and Felix for the help!)

typedef struct {
  float (*measure)(void *context, float width);
  void *measure_context;
} layout_node_t;
 
void layout(layout_node_t *node) {
  float width = 10;
  float height = node->measure(node->measure_context, width);
}

The void * value lets us put anything we want in it. So, with some casting we are able to simulate a closure and write our measure_image function ๐Ÿ™‚

float measure_image(void *context, float width) {
  float aspect_ratio = *(float *)context;
  return width / aspect_ratio;
}
 
int main() {
  layout_node_t node;
  node.measure = measure_image;
  float aspect_ratio = 1.5;
  node.measure_context = (void *)&aspect_ratio;
  layout(&node);
}

To compute the height of the image we use a float, but in order to handle text, we can pass a const char * instead. It works as well!

float measure_text(void *content, float width) {
  const char *text = (const char *)content;
  float line_height = 11;
  return ceil(strlen(text) / width) * line_height;
}
 
int main() {
  layout_node_t node;
  node.measure = measure_text;
  node.measure_context = (void *)"this is some super long text";
  layout(&node);
}

This solves the use case pretty well, which is remarkable since C doesn't support closure. The downside is that we are losing all the type information, have to do a lot of type casting and renaming.

PHP and JavaScript are both renowned to be languages with a lot of quirks. However two major initiatives on both sides, Hack for PHP and ES6 for JavaScript made the languages much better and modern. In this article I'm going to show all the ES6 features that are also in Hack.

Arrow Function

Both languages adopted the same shorter way to write functions. On JavaScript side, the main advantage is the automatic binding of this and for PHP it removes the need to declare all the variables you want to use from outside. ES6, Hack.

// JavaScript
var odds = evens.map(v => v + 1);
var nums = evens.map((v, i) => v + i);
nums.filter(v => {
  if (v % 5 === 0) {
    console.log(v);
    return true;
  }
  return false;
});
// Hack
$odds = array_map($v ==> $v + 1, $evens);
$nums = array_map(($v, $i) ==> $v + $i, $evens);
array_filter($nums, $v ==> {
  if ($v % 5 === 0) {
    echo $v;
    return true;
  }
  return false;
});

Class

JavaScript finally gets a class abstraction with ES6. It is however the bare minimal one to be useful, you cannot define constants, protected/private methods, traits ... PHP on this side is much better, without any Hack addition. ES6, PHP5.

// JavaScript
class SkinnedMesh extends THREE.Mesh {
  constructor(geometry, materials) {
    super(geometry, materials);
    this.idMatrix = SkinnedMesh.defaultMatrix();
    this.bones = [];
  }
  update(camera) {
    super.update();
  }
  static defaultMatrix() {
    return new THREE.Matrix4();
  }
}
// Hack
class SkinnedMesh extends THREE\Mesh {
  public function constructor($geometry, $materials) {
    parent::__construct($geometry, $materials);
    $this->idMatrix = SkinnedMesh::defaultMatrix();
    $this->bones = array();
  }
  public function update($camera) {
    parent::update();
  }
  static private function defaultMatrix() {
    return new THREE\Matrix4();
  }
}

Enhanced Object Literal

One long standing issue with object literals in JavaScript is the inability to use an expression as a key. This is fixed with the bracket notation in ES6. PHP 5.4 introduced a short notation for arrays as well. ES6, PHP.

// JavaScript
var obj = { [Math.random()]: true };
// Hack
$obj = [rand() => true];

Template Strings

Multiline strings and variable interpolations are something that have always been possible in PHP, yet they only start to work in ES6! ES6, PHP.

// JavaScript
var multiline = `In JavaScript this is
 not legal.`
var name = 'Bob',
    time = 'today';
`Hello ${name}, how are you ${time}?`
// Hack
$multiline = 'In PHP this is
 legal.';
$name = 'Bob';
$time = 'today';
"Hello $name, how are you $time?";

Default Arguments

It was possible to write default arguments in JavaScript but ES6 adds proper support for it right in the function declaration. Guess what, PHP had support for it all along. ES6, PHP.

// JavaScript
function f(x, y=12) {
  return x + y;
}
f(3) === 15;
f(2, 10) === 12;
// Hack
function f($x, $y=12) {
  return $x + $y;
}
f(3) === 15;
f(2, 10) === 12;

Iterator + for of

JavaScript has two ways to iterate on collections, either

for (var i = 0; i < array.length; ++i) { var element = array[i]; /* ... */ }
for (var key in object) { var element = object[key]; /* ... */ }

ES6 is now introducing a unified way to do iteration, that PHP always had, as well as a way to write custom collections via the iterator pattern, introduced in PHP5. ES6, PHP, PHP5.

// JavaScript
var fibonacci = {
  [Symbol.iterator]: function() {
    var previous = 0;
    var current = 1;
    return {
      next: function() {
        var new_previous = current; 
        current += previous; 
        previous = new_previous; 
 
 
        return {
          value: current,
 
 
          done: false
        }
      }
    }
  }
}
 
 
 
 
 
for (var n of fibonacci) {
  if (n > 1000) break;
  console.log(n);
}
// Hack
class Fibonacci implements Iterator<int> { 
  private $key = 0;    
  private $previous = 1;
  private $current = 0;
 
  public function next() { 
      $new_previous = $this->current; 
      $this->current += $this->previous; 
      $this->previous = $new_previous; 
      $this->key++; 
  } 
  public function current() { 
      return $this->current; 
  } 
  public function valid() { 
      return true; 
  } 
  public function key() { 
      return $this->key; 
  } 
  public function rewind() { 
      $this->previous = 1; 
      $this->current = 0; 
      $this->key = 0; 
  } 
}
foreach (new Fibonacci() as $n) { 
  if ($n > 1000) break; 
  echo $n; 
}

Generators

Python pioneered generators as another tool to manage control flow. It has originally been designed and promoted as an easier way to write iterators, but really shined as a better way to write asynchronous operations than callbacks. ES6, PHP5.

// JavaScript
var fibonacci = {
  [Symbol.iterator]: function*() {
    var previous = 1;
    var current = 0;
    for (;;) {
      var new_previous = current; 
      current += previous; 
      previous = new_previous; 
      yield current;
    }
  }
}
for (var n of fibonacci) {
  if (n > 1000) break;
  console.log(n);
}
// Hack
 
function fibonacci() {
  $previous = 1;
  $current = 0;
  for (;;) {
    $new_previous = $current; 
    $current += $previous; 
    $previous = $new_previous; 
    yield $current;
  }
}
 
foreach (fibonacci() as $n) { 
  if ($n > 1000) break; 
  echo $n; 
}

ES7 Async Await

C# introduced the concept of async/await combination to deal with asynchronous programming. The underlying implementation is very similar to generators but has proper syntax support. It is an addition of Hack on-top of PHP. ES7, Hack.

// JavaScript
async function chainAnimationsAsync(element, animations) {
  var result = null;
  try {
    for (var animation in animations) {
      result = await animation(element);
    }
  } catch (e) { /* ignore and keep going */ }
  return result;
}
// Hack
async function chainAnimationsAsync($element, $animations) {
  $result = null;
  try {
    foreach ($animations as $animation) {
      $result = await animation($element);
    }
  } catch (Exception $e) { /* ignore and keep going */ }
  return $result;
}

Map + Set

Both JavaScript and PHP are notorious for attempting to fit all the collection use cases into a single general purpose type. Both ES6 and Hack bring to the table proper support for Map and Set. ES6, Hack

// JavaScript
var s = new Set();
s.add('hello').add('goodbye').add('hello');
s.size === 2;
s.has('hello') === true;
 
var m = new Map();
m.set('hello', 42);
m.get('hello') === 42;
// Hack
$s = new Set();
$s->add('hello')->add('goodbye')->add('hello');
$s->count() === 2;
$s->contains('hello') === true;
 
$m = new Map();
$m->set('hello', 42);
$m->get('hello') === 42;

TypeScript

Last but not least, both languages are getting gradual typing. TypeScript, Hack.

// JavaScript
class Greeter<T> {
  greeting: T;
  constructor(message: T) {
    this.greeting = message;
  }
  greet() {
    return this.greeting;
  }
}
 
var greeter = new Greeter<string>("Hello, world");
console.log(greeter->greet());
// Hack
class Greeter<T> {
 
  public function __construct(private T $greeting) {}
 
 
  public function greet() {
    return $this->greeting;
  }
}
 
$greeter = new Greeter("Hello, world");
echo $greeter->greet();

Conclusion

With ES6 and Hack efforts, JavaScript and PHP are becoming languages with modern features. If you tried them 5 years ago, you should take another look, they are not as crappy as they once were ๐Ÿ™‚