Skip to content

Latest commit

 

History

History
149 lines (113 loc) · 5.18 KB

CHANGELOG.md

File metadata and controls

149 lines (113 loc) · 5.18 KB

Changes

Unreleased - ReleaseDate

Added

  • The BackoffScheduler is now more flexible.
  • EGraph::pre_union allows inspection of unions, which can be useful for debugging.
  • The dot printer is now more flexible.

Changed

  • EGraph::add_expr now proceeds linearly through the given RecExpr, which should be faster and include all e-nodes from the expression.
  • Rewrite now has public searcher and applier fields and no long_name.
  • (#61) Rebuilding is much improved! The new algorithm's congruence closure part is closer to Downey, Sethi, Tarjan, and the analysis data propagation is more precise with respect to merging. Overall, the algorithm is simpler, easier to reason about, and more than twice as fast!

0.6.0 - 2020-07-16

Added

  • Id is now a struct not a type alias. This should help prevent some bugs.
  • Runner hooks allow you to modify the Runner each iteration and stop early if you want.
  • Added a way to lookup an e-node without adding it.
  • define_language! now support variants with data and children.
  • Added a tutorial in the documentation!

Fixed

  • Fixed a bug when making Patterns from RecExprs.
  • Improved the RecExpr API.

0.5.0 - 2020-06-22

Added

  • egg now provides Symbols, a simple interned string that users can (and should) use in their Languages.
  • egg will now warn you when you try to use Rewrites with the same name.
  • Rewrite creation will now fail if the searcher doesn't bind the right variables.
  • The rewrite! macro supports bidirectional rewrites now.
  • define_language! now supports variable numbers of children with Box<[Id]>.

Fixed

  • The rewrite! macro builds conditional rewrites in the correct order now.

0.4.1 - 2020-05-26

Added

  • Added various Debug and Display impls.

Fixed

  • Fixed the way applications were counted by the Runner.

0.4.0 - 2020-05-21

Added

  • The rebuilding algorithm is now precise meaning it avoid a lot of unnecessary work. This leads to across the board speedup by up to 2x.
  • Language elements are now much more compact, leading to speed ups across the board.

Changed

  • Replaced Metadata with Analysis, which can hold egraph-global data as well as per-eclass data.
  • Fix: An eclass's metadata will now get updated by congruence. (commit)
  • The BackoffScheduler will now fast-forward if all rules are banned. (commit)
  • Improve benchmark reporting (commit)
  • The egraph now skips irrelevant eclasses while searching for a ~40% search speed up. (PR)

0.3.0 - 2020-02-27

Added

  • Runner can now be configured with user-defined RewriteSchedulers and IterationData.

Changed

  • Reworked the Runner API. It's now a generic struct instead of a trait.
  • Patterns are now compiled into a small virtual machine bytecode inspired by this paper. This gets about a 40% speed up.

0.2.0 - 2020-02-19

Added

  • A dumb little benchmarking system called egg_bench that can help benchmark tests.
  • String interning for Vars (née QuestionMarkNames). This speeds up things by ~35%.
  • Add a configurable time limit to SimpleRunner

Changed

  • Renamed WildMap to Subst, QuestionMarkName to Var.

Removed

  • Multi-matching patterns (ex: ?a...). They were a hack and undocumented. If we can come up with better way to do it, then we can put them back.

0.1.2 - 2020-02-14

This release completes the documentation (at least every public item is documented).

Changed

  • Replaced Pattern::{from_expr, to_expr} with From and TryFrom implementations.

0.1.1 - 2020-02-13

Added

  • A lot of documentation

Changed

  • The graphviz visualization now looks a lot better; enode argument come out from the "correct" position based on which argument they are.

0.1.0 - 2020-02-11

This is egg's first real release!

Hard to make a changelog on the first release, since basically everything has changed! But hopefully things will be a little more stable from here on out since the API is a lot nicer.