Code Monkey home page Code Monkey logo

cassowary.js's Introduction

Cassowary JS

Cassowary is an algorithm that computes flexible, responsive layouts quickly without resorting to piles of imperative code. Just describe the preferred relationships between values, noting which constraints are more important than others, and Cassowary figures out an optimal solution based on the current inputs. When the inputs or constraints change, Cassowary is particularly efficient at computing a new answer quickly based on the last-known solution. These properties together make it ideal for use in layout systems -- indeed, it's the algorithm at the center of Apple's new Auto Layout system for iOS & OS X.

This repo hosts an improved version of Greg Badros's port of the Cassowary hierarchial constraint toolkit to JavaScript.

This version dramatically improves the performance of the original translation, removes external library dependencies, and improves hackability. The solver core can now be used inside web workers, at the command line, and directly in modern browsers.

For civil discussion of this port and constraint-based UIs, join the Overconstrained mailing list.

License

Cassowary JS is licensed under the [Apache 2.0 license] (http://www.apache.org/licenses/LICENSE-2.0).

Constraint Solver? Say What?

Constraint solvers are iterative algorithms that work towards ever more ideal solutions, often using some variant of Dantzig's simplex method. They are primarily of interest in situations where it's possible to easily set up a set of rules which you would like a solution to adhere to, but when it is very difficult to consider all of the possible solutions yourself.

Cassowary and other hierarchial constraint toolkits add a unique mechanism for deciding between sets of rules that might conflict in determining which of a set of possible solutions are "better". By allowing constraint authors to specify weights for the constraints, the toolkit can decide in terms of stronger constraints over weaker ones, allowing for more optimal solutions. These sorts of situations arise all the time in UI programming; e.g.: "I'd like this to be it's natural width, but only if that's smaller than 600px, and never let it get smaller than 200px". Constraint solvers offer a way out of the primordial mess of nasty conditionals and brittle invalidations.

If all of this sounds like it's either deeply esoteric or painfully academic, you might start by boning up on what optimizers like this do and what they're good for. I recommend John W. Chinneck's "Practical Optimization: A Gentle Introduction" and the Cassowary paper that got me into all of this: "Constraint Cascading Style Sheets for the Web"

Getting Started Under Node

Cassowary is distributed as an NPM package and can be added as a dependency or used under node in the usual way. Using Cassowary under node is as simple as:

// The entire API is exported by the cassowary object
var c = require("cassowary");

var solver = new c.SimplexSolver();
var x = new c.Variable({ value: 167 });
var y = new c.Variable({ value: 2 });
var eq = new c.Equation(x, new c.Expression(y));
solver.addConstraint(eq);
// ...

The current low (sub 0.1) version number reflects the instability of the API. Also, note that the NPM package includes no tests or demos. For those, clone the github repo.

To make an NPM package from sources, clone the github repo, follow the below instructions for installing dependencies, and run make dist. This is the same process the maintainers use to package NPM releases.

Getting Started From Source

This repo pulls in other Git repositories through submodules and pulls in intern for testing via npm. After cloning the repo, run:

$ git submodule update --init
$ npm install
...

To run the tests, point your thorougly modern browser at tests/unittests.html?config=tests/intern and view the console. You can also check out demos/quad/quaddemo.html.

Running tests from the command line requires Node. Once you've installed Node, run:

$ npm test

> [email protected] test /Users/bitpshr/Projects/cassowary.js
> node node_modules/intern/client.js config=tests/intern

Defaulting to "console" reporter

...

121/122 tests passed

If you have a working make, a Makefile is provided with a test target that does the same thing. The Makefile also provides a make build target which generates a new minified bin/c.js binary out of the files in src/. It requires Python and isn't something you should need to do manually as it's not reqired to run tests or use the solver. The checked-in binary should always be up-to-date (or at some checkpoint which is known-good), so use it in your projects instead of the source versions.

Supported Runtimes

This refactoring currently runs in:

  • Chrome
  • Firefox 9+
  • Opera 11+
  • Safari 5+
  • IE 9+
  • Command-line:
    • V8 (d8 shell)
    • JSC (built into OS X)
    • Rhino (Java) js.jar included in checkout

This is an unapologetically modern reinterpretation optimized for size, low complexity, and speed. It will not work on old versions of IE.

Configuration

// Log general debugging information
c.debug = [ false || true ]; // default false
// Detailed logging
c.trace = [ false || true ]; // default false
// Verbose logging
c.verbose = [ false || true ]; // default false
// Logging of tableau additions
c.traceAdded = [ false || true ]; // default false
// Logging of ...?
c.GC = [ false || true ]; // default false

Current Build Status

Binary versions of the solver that work in both the browser and under node are available in the bin/ directory and are updated frequently. Tests are run on each commit via Travis CI:

Build Status

Pull requests that do not include tests or break the build will be denied or reverted, respectively.

cassowary.js's People

Contributors

alexbirkett avatar asolove avatar bergie avatar bitpshr avatar cacaodev avatar d4tocchini avatar devongovett avatar jba-zen avatar linzhp avatar neonstalwart avatar pdubroy avatar phae avatar ruby0x1 avatar slightlyoff avatar whummer avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

cassowary.js's Issues

MIT/BSD License

I think dual-licensing the project as LGPL / MIT or BSD would allow more developers to use it.
I just spoke with Greg Badros and he's open to using another license.

Allow restricted external variables

Currently, restricted variables (non negative) are only allowed internally but not when using the api.
In a UI environment, elements are generally defined by 4 variables and half of them are expected to be non negative (width and height).
It would be easier for developers to just declare these variables as restricted rather than adding v>=0 constraints for all the variables.

Project status?

Hi guys, I notice there's been a small bit of activity lately so I wanted to check back in.

I have a couple of open PRs that haven't seen any activity so I've been stuck working off of my own local branch with a bunch of fixes. I know maintaining open source projects is hard, I appreciate all the work in here so far, and I am definitely not complaining for having access to such an awesome code base: thanks for everything!

But I now have a project that could use disjunction support and some of the refactoring mentioned in previous issues. I would like to follow normal etiquette and propose things here, get feedback, have someone code review, etc., but not if no one else is going to have time to give feedback and merge back into this master. So let me know if someone with write access here is interested in taking on those kinds of code reviews and I'll let you know when I have something to share.

Thanks again!

edit vars with required strength

Add edit vars with required strength, like so:

solver.addEditVar(x, c.Strength.required)

always throws Uncaught TypeError: Cannot read property 'hashCode' of undefined: HashTable.js:38

canvas renderer example fails

When trying to run the demos/css/canvas-renderer.html example, the JS crashes.

Uncaught TypeError: undefined is not a function in layout.js:868

Build obtained through npm install is not up to date

I think some modifications/bug fixes made to cassowary were not published to npm.
Therefore the build on the github repo (version 0.0.2) does not correspond to the build that gets downloaded through npm (also version 0.0.2). The npm version does not benefit from the latest bug fixes.

Simple Demo Fails

The deficit below remains at 0 after the balance constraint is applied. I must be doing something incorrectly. Is there something I am missing here?

var spending = new c.Variable({value: 3598});
var revenue = new c.Variable({value: 2328});
var deficit = new c.Variable({value: 0});

var balance = new c.Equation(
    c.minus(spending, revenue),
    deficit,
    c.Strength.required, 0);

console.log('Spending', spending);
console.log('Revenue', revenue);

console.log('Deficit Before', deficit);
solver.addConstraint(balance);
console.log('Deficit After', deficit);

Even copying this test:
https://github.com/slightlyoff/cassowary.js/blob/master/tests/End-To-End-test.js#L20-L31

Will fail, running the unit tests do not fail, but using c.js from bin is where this is happening

I should clarify, from the unit test above:

var solver = new c.SimplexSolver();

var x = new c.Variable({ value: 167 });
var y = new c.Variable({ value: 2 });
var eq = new c.Equation(x, new c.Expression(y));

solver.addConstraint(eq);
console.log(x.value, y.value)

x.value will be 0
y.value will be 0

Maybe that is indeed the correct value and I just understand it wrong?

It looks like I need to: solver.addStay(x); and I will get x and y to be 167. I guess that makes sense in an equal situation. One of the 2 sides of the equality needs to take precedence, I suppose the addStay() does that?

If no stay is added why are the variables zero'd?

[Demo: CSS] Simplify TextBox

Today's TextBox class inherits from Inline, meaning it generates far too many constraints and c.Variable instances. Create a simplified constraint and variable set instead.

Mutable constant, Strength&weight in Constraint.

Currently, the only way to change the strength or constant in a Constraint is to replace a constraint with a new one with new values.

In a constraint-based UI, the only way to change the size or position of an element is to change the constant of the constraint managing the layout. This is why changing a constant should be simple and efficient.

FYI, set_constant is implemented in a branch of rhea : https://github.com/Nocte-/rhea/blob/0.3/rhea/simplex_solver.cpp#L188

Performance Benchmarks

I noticed your comment on Greg Badro's blog stating you saw a 2x speed boost from the original js port. Awesome! Do you have any tests that demonstrate this, jsperf or whatever? Did you see a general speed boost or for particular cases? Is the performance boost to just from removing external libraries?

Easier debugging support

It should be possible at every point to determine what constraints determined the value for a particular Variable once a solution is found. The API for this might be something like:

c.extend(c.Variable.prototype, {
   get constraininedBy() {
       return [ /*c.LinearExpression*/ ... ];
   },
   get unconstrainedBy() {
       return [ /*c.LinearExpression*/ ... ];
   },
});

Variable change notification support

The common use-case for Cassowary-based systems is for the solver to run in an incremental mode, moving to a new solution from an existing good solution. In interactive apps, the initial new values may be provided, but it's up to the solver to efficiently find new values for other affected variables. The updated values often need to be fed back into a UI framework to perform on-screen updates.

Cassowary should provide an (optional) facility for notifying observers of variables who values have changed, perhaps as a Map()/HashMap().

Rework Solver Core

The core of the solver (SimplexSolver.js and Tableau.js) are the crux of finally eliminating the last traces of the custom hash table implementation. Re-writing the solver core to be idiomatic, modern JS that's fully documented is something we should do sooner-rather-than later. It'll also give us the chance to implement Marriot, Moulder, Stukckey, and Borning's disjunctive constraint additions.

Expression with x^2

Why can't cassowary solve equations with squares? I'm guessing it has something to do with it being a nonlinear function...? I am a beginner to constraint solvers.

var c = require('cassowary');

var solver = new c.SimplexSolver();
var x = new c.Variable();
var squared = c.times(x, x);
var constraint = new c.Equation(squared, 25);
solver.add(constraint);
console.log(x.value);

Results in:

(c.NonExpression) The resulting expression would be non

LinearInequality constructor should handle more argument combinations

it seems that the c.LinearInequality doesn't accept a c.LinearExpression as first parameter in constructor if the third parameter is a number

so given the following coffeescript abbreviated setup:

required = c.Strength.required

x = new c.Variable(10)      
w = new c.Variable(10) # width         
r = new c.LinearExpression(x).plus(w) # right

the following x >= 20 test works as expected:

test1.solver.addConstraint new c.LinearInequality(x, c.GEQ, 20) 
alert x.value() # expects and gets 20

the following r == 100 test also works as expected:

test2.solver.addStay w
test2.solver.addConstraint new c.LinearEquation(r, 100, required) 
alert x.value() # expects and gets 90

but the following r >= 100 test throws an error:

test3.solver.addStay w
test3.solver.addConstraint new c.LinearInequality(r, c.GEQ, 100, required) 
alert x.value() # expects 90... 
# throws error: "Constraint.js:43Uncaught TypeError: Object 1 has no method 'isRequired"

i'm assuming, just as we can use c.expressions, numbers or c.variables on either side of an c.equation, we should be able to do the same with c.inequalities...

it appears to be the way the arguments are handled in the C.LinearInequality.initialize function...

[DEMO: Panels] Fix element subclassing in c.inherit() to work in Gecko

We currently rely on some proto magic with regards to existing DOM elements to provide the illusion of subclassing HTML elements. Combined with Mutation Observers, this allows us to fake HTML subclassing in the panels demo. We need a way to do the imperative part of this in Gecko (perhaps by routing through the parser first?)

Rework Solver

Re-build the solver core and associated classes for better readability, performance, and hackability,

[Demo: CSS] Implement Stacking Context Pass

Z-index and other forms of paint-order control are currently unimplemented. Add a processing pass to the block/box lists to correctly order boxes for painting both globally and locally

[Demo: CSS] Disable autoSolve

The current demo is incredibly slow due to the number of solves that are triggered by the addition of each individual constraint. Disabling autoSolve, however, causes our constraints to generate incorrect results today. Investigate why, add stays where necessary, and turn off autoSolve to improve demo performance.

Can't add edit variables with "required" strength

If and attempt is made to add edit vars with the "required" strength an Error: (c.InternalError) Constraint not found in removeEditVarsTo exception occurs.

See test case in pull request #59

I don't understand enough about cassowary internals to fix this. Any help appreciated.

Create new API shim

Once we have a general direction for the new API, build a shim layer to use while we transition off the old one. Once the shim is in place, the API is agreed, and all of our demo/test code uses it, remove the old API.

RequiredFailure Error should show all the constraints unable to satisfy

Currently, when you try to add a required constraints that conflicts with a required constraint already in the solver, the solver just throws a c.RequiredFailure with the message "A required constraint cannot be satisfied".

It would be useful to have additional information. Something like "Unable to satisfy simultaneously the following constraints : [constraintYouTryToAdd, constraintInTheSolver]"

Remove polymorphism

The Variable and Expression constructors are infected with some pretty horrible polymorphic detection code. These might have been good choices for C++ and Java, but this style of use plays badly in JS and should be removed.

Leaking 'exports' into global

When including in a project that also has amd components, exports is getting added to window which prevents modules that check for both commonJS and AMD fail if they look for the existence of exports as does PIXI.js (see gss/engine#47).

Also causing problems when loading GSS with Require.js

Source of problem:

// For Node...not that I'm bitter. No no, not at all. Not me. Never...
if (typeof require == "function" &&
    typeof module != "undefined" &&
    typeof load == "undefined") {
  scope.exports = c;
}
// ...well, hardly ever.

Wrong optimisation

Hello,

consider the following problem: maximise P = 3x + 4y subject to:

x + y ≤ 4
2x + y ≤ 5
x ≥ 0, y ≥ 0

the maximum P=16 can be obtained with: x = 0, y = 4

The same linear optimisation in cassowary:

var c = require('cassowary');
var solver = new c.SimplexSolver();

var p = new c.Variable({name: 'p'})
  , x = new c.Variable({name: 'x'})
  , y = new c.Variable({name: 'y'});

solver.addConstraint(new c.Equation(p, c.plus(c.times(x, 3), c.times(y, 4))));
solver.addConstraint(new c.Inequality(c.plus(x, y), c.LEQ, 4));
solver.addConstraint(new c.Inequality(c.plus(c.times(x, 2), y), c.LEQ, 5));

solver.addConstraint(new c.Inequality(x, c.GEQ, 0));
solver.addConstraint(new c.Inequality(y, c.GEQ, 0));

solver.optimize(p);

console.log('p: ', p) //15
console.log('x: ', x) //1
console.log('y: ', y) //3

results in P=15, x=1, y=3, which is not the optimum solution. Any idea on what I'm doing wrong?

Thanks
Daniele

Fix perf regression from isNaN check.

In 72aaec5, a fix for FF support, we introduce an isNaN() check that slows the main perf demo by nearly 100%. Need to understand why NaN was being passed from the CSS demo in the first place and either remove the check or figure out how to optimize away its impact.

making it easier to debug

I was trying to figure out how to update the value of a stay so I thought I'd require the ../cassowary/src/c.js or ../cassowary/index.js. I added cassowary.js as a submodule and the paths are working fine. The only problem is that webpack doesn't understand the module pattern that's being used. I was thinking of refactoring the modules and using browserify or webpack as the build system. Thoughts?

Also, how does one update the value of a stay?

Linear(.*) -> $1

Since Cassowary only supports linear equality/inequality relationships, having to type "Linear" in front of everything is entirely redundant.

Rename all classes (and uses) like:

  • c.LinearExpression -> c.Expression
  • c.LinearEquation -> c.Equation
  • c.LinearInequality -> c.Inequality
  • c.LinaerConstraint -> c.Constraint

QuadDemo Mouse EventHandlers

As inherited fromt the Greg's original code, the quaddemo has a little bug with the mouse event handlers. if u start dragging one of the db's, but mouseup outside of the canvas and then continue to click the same db, it throws an error and the constraints no longer work.

here's a quick fix of QuadDemo.initEvents that just adds the mouseup to the document (not the canvas) only after a mousedown:

initEvents: function() {
    var that = this;

    mouseupHandler = function(ev) { that.mouseup(ev);
      document.removeEventListener('mouseup', mouseupHandler); }

    this.canvas.addEventListener('mousedown', 
                                 function(ev) { that.mousedown(ev);                                   
                                   document.addEventListener('mouseup', mouseupHandler, false);                                   
                                   },
                                 false);

    this.canvas.addEventListener('mousemove', 
                                 function(ev) { that.mousemove(ev) },
                                 false);
    this.canvas.addEventListener('touchstart', 
                                 function(ev) { that.touchstart(ev) },
                                 false);
    this.canvas.addEventListener('touchend', 
                                 function(ev) { that.touchend(ev) },
                                 false);
    this.canvas.addEventListener('touchmove', 
                                 function(ev) { that.touchmove(ev) },
                                 false);
  },

I was discussing the awesomeness of constraint based layouts to some colleagues, and they were tweaking with the demo and naturally dragging and pulling wildly... the layout kept locking up, not yet familiar with constraints, they thought it was expected behavior...

Use Harmony Maps where possible

Move HashTable.js to use Map when possible. We'll need a wrapper for Map at first since the current Straw Man implemented by FF and V8 don't support any sort of iteration.

I'm working on getting forEach(), et al added to the draft in addition to generator-based iteration. Once that's in V8, also remove the wrapper class.

Code and comments disagree

Lines 758-768 of SimplexSolver.js read like this:

      // Find the most negative coefficient in the objective function (ignoring
      // the non-pivotable dummy variables). If all coefficients are positive
      // we're done
      terms.escapingEach(function(v, c) {
        if (v.isPivotable && c < objectiveCoeff) {
          objectiveCoeff = c;
          entryVar = v;
          // Break on success
          return { brk: 1 };
        }
      }, this);

Unless I'm misreading the code, this find the first negative coefficient and then breaks, not the most negative coefficient.

Build Process

Go JS all the way, so cut out python for minifying, maybe use Grunt? Any objections?

Changing a variable coefficient

Hello,

I found 2 methods to change a variable coefficient but both of them are problematic:

1- Using Expression.setVariable. The problem: the coefficient of the variable within the expression seems to be correctly updated but not within the tableau. Is it normal?

A simple example to illustrate the problem:

var solver = new SimplexSolver();
solver.autoSolve = false;

var x = new Variable({ name: 'x', value: 5 });

var myExpression = new Expression(x, 2);
var myConstraint1 = new Inequality(myExpression, GEQ, 5);
var myConstraint2 = new Inequality(myExpression, LEQ, 5);

solver.addConstraint(myConstraint1);
solver.addConstraint(myConstraint2);

console.log(myExpression.toString()); // 2*5
myExpression.setVariable(x, 1);
console.log(myExpression.toString()); // 1*5

solver.resolve();

// At this point x should be equal to 5 if the expression was correctly updated
console.log(x); // x = 2.5

2 - By removing and re-adding constraints. The problem: it gives really poor performance. e.g 2ms to remove and add back a single constraint on a 15 row by 10 columns tableau although it takes 0.05ms to solve it!.

Is there a more friendly and reliable way to cheaply do that coefficient change operation? (I tried to dive in the code but could not figure out what to do!)

Note: I am using cassowary to implement a complex responsive UI and I plan on implementing a branch and cut algorithm based on cassowary in order to solve problems that include integer variables. Therefore I am searching for an efficient way to dynamically change cut constraints.

[Demo: CSS] Implement <table> modes

Table elements create several exclusive layout modes, some of which are based on replaced content resolution. Implement support for these modes in Block::generate() or some subclass implementation.

Documentation

Is there documentation or a list of API methods somewhere? I'm not sure how to get started. The Getting started under Node section of the README hints at how to use this library, but it does not give a full example or list the available methods.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.