Cassowary Constraint Solver in JavaScript

As a longtime-recovering academic, I still occasionally feel the urge to make the work I did for my Ph.D. back in the '90s matter more in the real world.  Recently, I had the chance to use two different and unrelated pieces of my research together.... as any fellow technologist knows, that makes doing the work way more than twice as fun!

One of the projects I found a new use for is JavaML – work I did in 1999. For my grad school career, JavaML was perhaps most notable because it was done right before I finished my Ph.D. but was not included in my thesis at all... quite literally, I went to my advisor one week before the submission deadline and said "I'm gonna disappear for a week while I work on this cool idea, ok?" Luckily, that paper was accepted to WWW in 2000 which was hosted in Amsterdam. Yes, the choice of conference was somewhat influenced by its being hosted in the Netherlands, but also because the project idea was grounded in something I knew the WWW community would be excited about: the use of web standards applied to developer, language, and compiler tooling. Specifically, my idea was appealingly simple: convert Java source code into XML so that one could use XML tools such as XSLT, SAX parsers, DOM trees, and more, to write code transformations  and analysis and querying tools. The primary challenge was the exact design of the XML schema for the Java AST.  That piece was critical in making downstream tools powerful and easy to build.  As with all of my work, I backed the theory with an implementation that I built using IBM's then state-of-the-art Java compiler. All told, that JavaML paper turned out well, I made a cool poster for UW's industrial affiliates one year and I had a working implementation that had plenty of reasonably compelling examples. And I had a fun visit to Amsterdam... But never did I myself use the tools I built for anything practical. Until a couple weeks ago....

The other prior research I dusted off in my latest personal project is the Cassowary Constraint Solving Toolkit. That work and its applications made up the bulk of my PhD thesis. In a nutshell, Cassowary is a library and framework for expressing linear arithmetic equality and inequality relationships among variables and solving systems of those relationships incrementally and in real time. Most of my work involved applying the incremental solver to graphical applications such as the Scheme Constraints Window Manager or the Cascading Style Sheet engine in web browsers and Scalable Vector Graphics renderers, but other researchers used it for satisfiability engines and resource planning, and more. For many years, I used Cassowary daily in the Scheme Constraints Window Manager, but it never achieved widespread use on the web. In part this is because it needed to be built into the browser... although I made the Cassowary toolkit available in C++, Java, Smalltalk, Python, and Scheme, none of those languages were easy to demonstrate over the web.

A few weeks ago, I realized something both obvious and important. We all know that JavaScript implementations have improved leaps and bounds over the last decade. IE6 was a disaster to work with in large part because the JavaScript implementation was good enough only for the tiny little scripts that defined JavaScript in the 90s. Today, Chrome and its V8 engine along with similar advances in Safari  (Nitro) and Firefox (TraceMonkey) make JavaScript performance scream. That meant that I could run Cassowary natively in the browser with good performance if only I had a JavaScript implementation. (Or, more properly, ECMAScript.)

Thus, my plan was hatched: given that I wrote a Java implementation of Cassowary, I would use JavaML to serialize that code into its XML representation. Back in 2000, I wrote an XSLT-based converter to go back from JavaML's XML representation to plaintext Java source code (in fact, round-tripping between those representations was my unit test as I was building JavaML). For this project, I'd change that converter to, instead of outputting Java source code, transliterate language constructs and generate a close-to-correct JavaScript plaintext representation of the program. Then, after some editing and debugging, I'd end up with a complete JavaScript implementation of the solver enabling me and others to explore the use of constraints for layout or other functionality within rich, modern AJAX web applications. In case you're impatient, here's the bounded quadrilateral demo in JavaScript. The full JavaScript implementation of Cassowary is available via CVS at Sourceforge with the rest of the Cassowary distribution.

Let me go through that last paragraph in slow motion. First, I took my Java implementation of Cassowary which has code like this:

public String toString()
    { 
      StringBuffer bstr = new StringBuffer("[");
      for (int i = 0; i < _values.length-1; i++) {
        bstr.append(_values[i]);
        bstr.append(",");
      }
      // ...
      return bstr.toString();
    }

after running it through my Jikes-JavaML tool, I get JavaML XML code like this:

<method name="toString" visibility="public" id="meth-3340">
  <type name="String"/>
  <formal-arguments/>
  <statements>

    <!-- StringBuffer bstr = new StringBuffer("[") -->

    <local-variable name="bstr" id="locvar-11045"> 
      <type name="StringBuffer"/>
      <new><type name="StringBuffer"/><arguments>
           <literal-string length="1">[</literal-string></arguments></new>
    </local-variable>
    <loop kind="for">
      <init> <!-- int i = 0 -->
        <local-variable name="i" id="locvar-11050">
            <type name="int" primitive="true"/>
            <literal-number kind="integer" value="0"/></local-variable>
      </init>
      <test>
        <binary-expr op="lt">  <!-- i < _values.length - 1 -->
          <var-ref name="i" idref="locvar-11050"/>
          <binary-expr op="-">
            <field-access field="length"><var-ref name="_values"/></field-access>
            <literal-number kind="integer" value="1"/>
          </binary-expr>
        </binary-expr>
      </test>
      <update> <!-- i++ -->
        <unary-expr op="++" post="true">
            <var-ref name="i" idref="locvar-11050"/>
        </unary-expr>
      </update>
      <statements>
        <send message="append"> <!-- bstr.append(_values[i]) -->
          <target><var-ref name="bstr"/></target>
          <arguments><array-ref><base>
                <var-ref name="_values"/></base><offset>
                <var-ref name="i"/></offset></array-ref>
          </arguments>
        </send>
        <send message="append"> <!-- bstr.append(",") -->
          <target><var-ref name="bstr"/></target>
          <arguments><literal-string length="1">,</literal-string></arguments>
        </send>
      </statements>
    </loop>
    <!-- ... ... -->
    <return> <!-- return bstr.toString() -->
      <send message="toString">
        <target><var-ref name="bstr" idref="locvar-11045"/></target>
        <arguments/>
      </send>
    </return>
  </statements>
</method>

Note that I specifically designed features of the JavaML representation to support edges (via id/idref pairs) between uses of variables and their declarations (which include their static types). That means that I can convert the above XML into JavaScript, essentially transliterating from Java to JavaScript, in a type-aware way using XSLT and template precedence rules to specialize rewrites based on details of the AST. For example, these rules make sure that StringBuffer.append and .toString method invocations result in the appropriate JavaScript constructs of "+=" and a no-op, respectively:

<xsl:template
    match="send[@message='append'][id(./target/var-ref/@idref)/type/@name='StringBuffer']">
  <xsl:apply-templates select="target"/>
  <xsl:text> += </xsl:text>
  <xsl:apply-templates select="arguments/*"/>
</xsl:template>


(The above template matches send elements with message attributes of 'append' that also have the target/var-ref/@idref pointing to a declaration that has a type element with name attribute of 'StringBuffer'.  I.e., apply this rule to all sends of the "append" message to variables with static type "StringBuffer".)


<xsl:template 
    match="send[@message='toString'][id(./target/var-ref/@idref)/type/@name='StringBuffer'][not(arguments/*)]">
  <xsl:apply-templates select="target"/>
</xsl:template>

Those rules applied to the JavaML representation of the Java source code then result in this JavaScript:

  toString: function() {
    var bstr = "[";
    for (var i = 0; i < this._values.length-1; i++) {
      bstr += this._values[i];
      bstr += ",";
    }
    // ...
    return bstr;
  },

In this case, the converted code is perfect and ready to execute.  The actual process was a bit more laborious, involving iterating on specializing the XSLT transformation for each subsequently more complex Java source program in the full library and hand-editing the output to fix the places where it was not worth my while to make the XSLT smarter (and finding a few bugs in Jikes-JavaML and my XSLT transformations along the way).  I also had to make several choices of libraries and JavaScript langauge extensions as dependencies to the converted JavaScript.  For a simple object-oriented framework, I used the server-side MooTools, and for a true hashtable and hashset (i.e., one that can have arbitrary objects as keys, not just strings), I used jshashtable and jshashset (with some minor modifications to support an escapingEach mechanism to allow break and non-local returns since the algorithm uses those patterns throughout).

After about three weekend days of working on this, I ironed out the last of the (known) bugs (which turned out to be an error in my Java implementation that I'd fixed in the C++ implementation years ago).  Then I implemented the previously-mentioned bounded quadrilateral demo in JavaScript, learned about Touch events on iOS devices and made the demo work on my iPad and iPad2.

I hope developers out there are able to find creative uses of the constraint solver on their web pages and applications.  And maybe someone will improve the JavaScript implementation with something that truly looks and feels like JavaScript (rather than Java hiding behind a JavaScript surface syntax)!  Until then, I may port to JavaScript the string expression parser to make it easier to specify constraints just by writing something like "x + width < screen_width".  The dynamic expressiveness of JavaScript should be a huge help in experimenting with tighter integration with the rest of the environment, similar to my Scheme implementation and the way it interacted with the Scwm Window Manager.