Linq.Expression.Optimizer

Lightweight optimizer of System.Linq.Expression expressions. Just basic boolean algebra and reductions, constant and tuple/anonymous type eliminations. For side-effect-free Expressions. No compilation-subjective optimizations. This is meant to be used with expressions that are not compiled but transferred to other domains.

Supported frameworks: Net 3.5, Net 4.5-... (and Mono), .NET Standard 1.6 (so also .NET Core)

Supported optimizations

Example as a quote. There are various other cases also.

• Replace constants comparisons: 3 < 4 -> true
• Remove anonymous types: new AnonymousObject(Item1 = x, Item2 = "").Item1 --> x
• Cut not used condition: if false then x else y -> y
• Remove not: not(false) -> true
• Binary tree balancing: a or (b or (c or (d or (e or (f or (g or h)))))) -> ((a or b) or (c or d)) or ((e or f) or (g or h))
• Captured closure constant ("free variable") evaluation: y = 3 and (y + x) -> (3 + x)
• Execute simple math: 5 * 3 -> 15
• Boolean algebra reductions:
  • gather (x or y) and (x or z) -> x or (y and z)
  • identity false or y -> y
  • annihilate true or x -> true
  • absorb x and (x or y) -> x
  • idempotence y or y -> y
  • complement x and not(x) -> false
  • doubleNegation not(not(y)) -> y
  • deMorgan not(x) and not(y) -> not(x or y)

Background

This is a side-track from SQLProvider, excellent tool that is kind of OR-mapper with auto-generated objects, so it compiles any databases to .NET-language, and works fast on design time in Visual Studio or other editors.

But I needed better SQL-queries. So this optimises .NET LINQ-expressions. These expressions were not meant to be compiled, so Nessos LinqOptimizer was not the right tool. I thought that .NET would optimize these automatically, but no.

Read the Getting started tutorial to learn more.

Documentation: http://thorium.github.io/Linq.Expression.Optimizer

Tests

tests/Linq.Expression.Optimizer.Tests is the example-based suite over LINQ queries. tests/Linq.Expression.Optimizer.PropertyTests is an FsCheck suite over random expression trees (booleans, integers, doubles with NaN, nullable integers and strings over ten parameters, in the shapes every reduction rule is written for): the optimized tree compiles to the same function as the original on a grid of inputs, optimizing never throws, optimizing twice is optimizing once, the tree never grows, and every reduction rule fires on some generated tree. An exception the original would throw (x / 0, null.Length) may disappear when the subtree that threw it is optimized away - the library is for side-effect-free expressions - but a value never changes and no new exception appears.

Maintainer(s)

• @thorium

If you want more optimizations, please feel free to send PRs!