Vjeux

URLON.stringify() suffer from a problem, when passed an object that contains a cycle, it will never stop. This article shows 3 techniques in order to detect if an object is cyclical.

Edit the object: Mark

In order to detect a cycle in an object, the method we learn at school is to mark each visited node. When doing a traversal, if we encounter an already marked node, then it is cyclic.

This method alters an object we don't own. It is a dangerous practice and has many side effects.

• How do we find a unique mark key? I chose to use Math.random but it has a slight chance of giving the wrong result and removing this key from the object!
• Adding a new key then deleting it makes the object memory size change. Therefore there are great chances of introducing memory copy and at the end of the process, memory holes because of the attribute deletion.
• It does not work with Sealed objects and Proxies.

function isCyclic (obj) {
  var seenObjects = [];
  var mark = String(Math.random());
 
  function detect (obj) {
    if (typeof obj === 'object') {
      if (mark in obj) {
        return false;
      }
      obj[mark] = true;
      seenObjects.push(obj);
      for (var key in obj) {
        if (obj.hasOwnProperty(key) && !detect(obj[key])) {
          return false;
        }
      }
    }
    return true;
  }
 
  var result = detect(obj);
 
  for (var i = 0; i < seenObjects.length; ++i) {
    delete seenObjects[i][mark];
  }
 
  return result;
}

Keep the mark in a separate data structure

Obviously, we want to avoid editing the object, but what solutions do we have? The only one I found is keeping the visited nodes in an array. Then using indexOf, we can detect if we already visited the node.

However, this is a O(n²) process where the previous one was O(n).

function isCyclic (obj) {
  var seenObjects = [];
 
  function detect (obj) {
    if (typeof obj === 'object') {
      if (seenObjects.indexOf(obj) !== -1) {
        return true;
      }
      seenObjects.push(obj);
      for (var key in obj) {
        if (obj.hasOwnProperty(key) && detect(obj[key])) {
          return true;
        }
      }
    }
    return false;
  }
 
  return detect(obj);
}

Use native JSON.stringify

The last technique is a bit hacky. When implemented by the browser, JSON.stringify will throw an error if the object happens to be cyclic. It requires a recent browser and feels wrong.

function isCyclic (obj) {
  var isNativeJSON = typeof JSON !== 'undefined' && JSON.stringify.toString().match(/\{ \[native code\] \}$/);
  if (!isNativeJSON) {
    throw 'Native JSON.stringify is not available, can\'t use this technique.';
  }
  try {
    JSON.stringify(obj);
    return true;
  } catch (e) {
    return false;
  }
}

Conclusion

The conclusion is a bit sad, none of the techniques above are satisfying. In order to make a pure-Javascript and efficient version of cycle detection, it would require an Object hash-map, which we don't currently have.

If you are interested, the code source is on github and there's a jsperf that compares the 3 techniques.

Related Work

If you need to store and load circular structures, use Douglas Crockford decycle & retrocycle functions.

I am in the process of rewriting MMO-Champion Tables and I want a generic way to manage the hash part of the URL (#table__search_results_item=4%3A-slot). I no longer want to write a new parser every time I want to add a new widget.

Why JSON is not suited for URLs

JSON uses characters that are not widely known in the URL. For example, having the double quote character in the URL sucks for HTML embedding. As well, Many of the automated URL insertion will fail at highlighting the whole URL.

MSN Messenger trying to automatically URLify: See the missing last three }.

http://website.com/#{"table":{"achievement":{"column":"instance","ascending":true}}}

As a user, I am also really disturbed when I see this URL. This does not feel like a normal URL. I am a bit suspicious.

A strong requirement for an URL is its small size. JSON representation can be further compressed by removing extra quotes and ending characters such as " and }.

URLON

This is why I made URLON, a new Object Notation intended to be used in URLs. It makes use of URL friendly characters such as = : @ _ &. It is shorter than JSON and should no longer scare your users 🙂

Put some random JSON / URLON / Rison in one of the boxes to see the other notations update.

JSON:

{"table":{"achievement":{"column":"instance","ascending":true}}}

URLON:

Rison:

A reference implementation is available:

It is also available on NPM:

 npm install URLON

var URLON = require('URLON');
console.log(URLON.stringify({URLON: 'works'}));
// _URLON=works

JSON / URLON Comparison

Object

An object starts with an underscore _. All the fields are separated by ampersand & and terminated by a semicolon ;. It makes it feel really url'ish. Note that trailing semicolons can safely be removed.

• JSON: {"first": "value", "second": "value"}
• URLON: _first=value&second=value

String

A string just starts with an equal sign =. A string stop as soon as it reaches a reserved keyword (= : @ _ &). You can escape a character a slash before /.

• JSON: "string"
• URLON: =string

Number, Boolean and null

Sadly, we have to distinguish between Strings and Numbers/Booleans/null. Therefore I chose to use a colon : for those instead.

Array

An array starts with a arobas @ and elements are separated by comma @. The prefix typing does not really fit well with the Array syntax. If you can find something better, I'm open to your suggestions 🙂

• JSON: [1, "vjeux", 3]
• URLON: @:1@=vjeux@:3

URLON / Query String

Query String is a standard for encoding structured data in a URL context. It is implemented natively in PHP and Ruby. However, I strongly believe that URLON is better for several reasons:

• Query String are not typed: Every atomic value is a string. This makes it less expressive than JSON and less easy to work with as numbers and booleans are common in urls.
• Query Strings are big. For every leaf node, the whole identifier is being written, this is a waste of space.

The following example from the PHP Documentation compares JSON, Query String and URLON.

JSON

{
  "user": {
    "name": "Bob Smith",
    "age": 47,
    "sex": "M",
    "dob": "5-12-1956"
  },
  "pastimes": ["golf", "opera", "poker", "rap"],
  "children": {
    "bobby": {
      "age": 12,
      "sex": "M"
    },
    "sally": {
      "age": 8,
      "sex": "F"
    }
  }
}

Minified JSON

{"user":{"name":"Bob Smith","age":47,"sex":"M","dob":"5-12-1956"},"pastimes":
["golf","opera","poker","rap"],"children":{"bobby":{"age":12,"sex":"M"},
"sally":{"age":8,"sex":"F"}}}

Query String

user[name]=Bob+Smith&user[age]=47&user[sex]=M&user[dob]=5-12-1956&pastimes[0]=golf
&pastimes[1]=opera&pastimes[2]=poker&pastimes[3]=rap&children[bobby][age]=12
&children[bobby][sex]=M&children[sally][age]=8&children[sally][sex]=F

URLON

_user_name=Bob%20Smith&age:47&sex=M&dob=5-12-1956;&pastimes@=golf@=opera
@=poker@=rap;&children_bobby_age:12&sex=M;&sally_age:8&sex=F

Rison

(user:(name:'Bob Smith',age:47,sex:M,dob:'5-12-1956'),pastimes:!(golf,opera
,poker,rap),children:(bobby:(age:12,sex:M),sally:(age:8,sex:F)))

Rison is a tiny-bit longer than URLON but is easier to read. However it does not feel like it's part of an URL to me. It is also common for automatic linking to break on parenthesis ( or ), meaning that we are back with the same issues as JSON.

Please, feel free to give your ideas in the comments 🙂

I've always found CSS positioning with both float and position: absolute/relative hard to work with. I want to introduce to you an alternative way borrowed from the World of Warcraft Interface: Anchors.

Anchor

The concept is extremely simple. You can tell where you want the element to be, relative to another. For example, top left of this blog's main content is 10px right relative to the top right of the menu.

<frame name="Content">
  <anchor point="TOP LEFT" relativeTo="Menu" relativePoint="TOP RIGHT" x="10" />
</frame>

• Allowed points:
   TOP LEFT ,  TOP   , TOP RIGHT
       LEFT , CENTER , RIGHT
BOTTOM LEFT , BOTTOM , BOTTOM RIGHT
• Default Values:
  • point, relativePoint: TOP LEFT.
  • relativeTo: Parent of the element.
  • x, y: 0.

Demo

I've made a quick implementation of this behavior in HTML using data-attribute. Check the Javascript tab to see the 35 lines of CoffeeScript that makes the following code work:

<!-- In order to put the sidebar centered at the right of the frame:
  Sidebar.left = Frame.right                                          -->
<div id="sidebar" data-anchor="left, #frame, right"></div>
 
<!-- In order to put the chat at the top right of the screen:
  Chat.topRight = HTML.topRight + {x: -10, y: 10}                       -->
<div id="chat" data-anchor="top right, html, top right, -10, 10"></div>

Limitations

Static

The current code works well for static elements. As there isn't any event for DOM move/resize, the position will not be updated if anything moves 🙁

It might be possible to achieve the same effect by setting properly the position: absolute/relative and top/bottom/right/left CSS properties. I'd be really interested to know if you try to tackle this challenge 🙂

CSS Attribute

It would be more semantically correct to add an anchor CSS attribute instead of an HTML data attribute. However, it's not possible to access the value of a custom CSS property.

#sidebar {
  anchor: bottom left #frame top right 10px 0;
}

Multiple Anchors

World of Warcraft supports multiple anchors. For example if you anchor both the left and right sides, then the width of the element is going to be updated accordingly.

At school we've been studying Lie Algebra and we were asked to make a 3D representation of a Lie Group. We chose to represent Julia Set in the Quaternion domain.

We were really impressed to see that it was possible to generate many different forms given such a simple equation. Feel free to share links with some cool settings in the comments 🙂

The demo has been written in WebGL using ThreeJS.

A bit of Mathematics

Les ensembles de Julia sont des fractales définies par une suite de récurrence \(z_{n+1} = z^{2}_{n} + r\). Avec \(r\) une constante. Si, pour un \(z_{0}\) fixé, \((z_{n})\) converge alors \(z_{0}\) est dans l'ensemble de Julia.

Les ensembles de Julia peuvent être représentés en 2 dimensions en prenant \(r \in \mathbb{C}\) ou alors en 4 dimensions en prenant \(r \in \mathbb{H}\). \(\mathbb{H}\) étant l'ensemble des quaternions. Les quaternions sont des nombres hypercomplexes de la forme: \[a + i \times b + j \times c + k \times d \ \ \ \ \ \ (a, b, c, d) \in \mathbb{R}\] Avec \(i\), \(j\), \(k\) des racines complexes de l'unité, c'est-à-dire: \(i^{2} = j^{2} = k^{2} = ijk = 1\).

Afin d'obtenir une représentation dans un espace à quatre dimensions on représente chaque point de cet espace par un quaternion. À \(r\) fixé on obtient l'ensemble de Julia correspondant en testant la convergence de
\((z_{n})\) pour tous les points de l'espace.

Dans notre démonstration les coefficients de la constante sont modifiables via les curseurs \(a\), \(b\), \(c\) et \(d\). Pour obtenir une représentation en 3D il est nécessaire de réaliser une coupe de l'ensemble de Julia par un hyperplan. Dans la pratique cela signifie que nous assignons une valeur constante à un même coefficient pour tous les quaternions. On assimile alors les 3 coefficients restants aux axes \(x\), \(y\) et \(z\) d'un repère 3D.

Dans notre démonstration on peut choisir quel coefficient fixer et modifier sa valeur avec le curseur Hyperplane. Une fois un coefficient fixé on fait ensuite varier \(x\), \(y\), et \(z\). Par exemple si on a fixé le coefficient de \(k\) à \(W\), la valeur initiale de la suite est donc: \(z_{0} = x + i \times y + j \times z + k \times W\).

Le point \((x, y, z)\) est alors dans l'ensemble de Julia si après un nombre fixé d'itérations la valeur de la suite n'a pas dépassé un certain seuil. Dans notre démonstration, nous avons choisi d'effectuer 10 itérations.

In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances.

Common pattern

In order to test if the key is already in the cache, the usual pattern is to use key in cache. This leads to the following code:

function cachedValue(key) {
  if (key in cache) {
    return cache[key];
  } else {
    var result;
    /* generate result */
    return cache[key] = result;
  }
}

Ideal cache lookup

The expensive operation with a cache is to traverse the data structure in order to find the position where the element should be. In the previous code, there are three independent lookups: key in cache and 2x cache[key].

In order to improve performance, the ideal would be to make that expensive lookup once, and do the test/get/set directly at that position.

function cachedValue(key) {
  var position = cache.lookup(key);
  if (cache.has(position)) {
    return cache.get(position);
  } else {
    var result;
    /* generate result */
    cache.set(position, result);
  }
}

Javascript Workaround

However, there is no API to directly manipulate the lookup and position. We have to find workarounds.

We remark that cache[key] will either return the value or undefined if not present in the cache. The belonging test no longer requires a full lookup, you only have to compare the value with undefined.

function cachedValue(key) {
  var result = cache[key];
  if (result === undefined) {
    /* generate result */
    cache[key] = result;
  }
  return result;
}

There is only one drawback: it is no longer possible to use undefined as a value in your cache.

Without temporary

If the result can be generated inline and your cache will never contains falsy values, you can use a shorter version. It should not impact performance however.

function cachedValue(key) {
  return cache[key] || (cache[key] = /* generate result */);
}

Conclusion

There are still two lookups done in case of a cache miss. If you find a way to factor the code in a way that removes it, I'm really interested in knowing 🙂

At the time of writing, the described technique is faster on all the tested browsers. As performance in browser rapidly evolve, check out the jsPerf entry before you decide to use it in your application.