two to the fifth

• improve HMap api (add mapValues and ++) #41 #42
• fix a minor binary incompatibility #44
• some stack safety improvements #27

See full changes: v0.3.1...v0.3.2

thanks to @non, @johnynek @alexeygorobets

Deterministic evaluation

This is a minor fix to make sure we apply rules to the graph in a deterministic order, so that applying rules is a pure function with respect to equality on the nodes.

Better Ids, more serializable

This is slightly binary incompatible and has the following changes:

1. Make sure Id[T] is never equal for two different instances.
2. Give a Long rather than Int sequence number to each Id, which is only used for toString.
3. Due to the above, Dag no longer needs to know the nextId.
4. add Serializable to all the types.
5. improve the Literal hashCode/equals code a bit more.

Make fanOut fast

fanOut is not an uncommon operation in rules and can be computed for the whole graph as fast as we were computing one value. We lazily memoize it now so we can evaluate more quickly.

Learn to write fast Dag == methods

This release adds:

1. a depth method on DAG to compute the max depth from a source node a given node is in the graph.
2. RefPair: a tuple2 that uses reference equality for equality.
3. a Non-exponential (in fact linear) memoized equality for Literal[N, T] which unfortunately should be copied on your Dags N[T]. If you don't have an efficient equality, and the naive case class equality can be exponentially expensive for Dags that have fan-in, then running rules can be exponentially slow.

Fix the hashcodes

This is mostly a bugfix release, but also a performance improvement. v0.2.3 had a critical error in one of the new equality method on Literal.

In addition to that, we are better about caching the mapping of Expr nodes into the underlying Dag node type.

Memoize The Hashcodes

Some profiling has showed the Literal hashCode to be pretty expensive on graphs that fork and join a lot (very non-tree dags that use a lot of binary nodes).

Here we memoize Literal. Users should also memoize the hashCode of the nodes in their AST especially binary or variadic nodes.

Be robust to nesting rules

0.2.1 and under had a bug that if a rule translates a node to something that includes the node (even if the rule eventually converges so it should be okay). This bug is fixed and we also added a few convenience method

• #16 fix issue with nesting rules.
• #17 add some convenience methods to Dag.

Variadic Madness

• improve test coverage: #12
• add a variadic node: #13 which allows ASTs that have nodes that accept a variable number of arguments

Just Dag

We have improved the performance and simplified the API somewhat. We removed the simple graph class DependantGraph and instead replicated all that functionality into Dag. We added a Cache[K, V] which is a snapshot-able (immutable Map[K, V] backed) cache which is useful in memoizing recursive graph transformations on DAGs.

Changes

• #7 the main change: rename ExpressionDag to Dag, add Cache as an analog to HCache, move DependantGraph to a test, since all functionality is subsumed by Dag.
• #9 add Dag.applySeq to apply a Seq[Rule[N]] sequentially, which is commonly what you want.

More Testing

• #5 Fix a bug with isRoot, performance related bugs.
• #8 more tests for HMap (100% coverage)