thorium / linq.expression.optimizer

System.Linq.Expression expressions optimizer. http://thorium.github.io/Linq.Expression.Optimizer

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 domain.

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, excelent 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 optimses .NET LINQ-expressions. These expressions were not ment 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

Maintainer(s)

• @thorium

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

linq.expression.optimizer's Issues

Rename to Linq.Expression.Optimiser?

Describe the bug

A possible spelling mistake in the product name.

To Reproduce

Install en-UK language pack, and spell-check the project name.

Expected behaviour

No red line should appear.

invalid reference in package for net45 version

Description

Repro steps

I have legacy solution with webforms, blazor and multitarget net48/netstandard21 projects. WebForms project version don't use optimizer yet, but have indirectly reference to it. When i add Swashbuckle to WebForms project it dosn't start at all.

1. Create multitarget net48/netstandard21 project.

2. Add Linq.Expression.Optimizer package to it.

3. Create WebForms project.

4. Add reference to first project.

5. Add reference to Swashbuckle package (it have reference to WebActivatorEx package).

You don't need actually use Linq.Expression.Optimizer or Swashbuckle

Expected behavior

Web site started succesfully,

Actual behavior

bin folder contains FSarp.Core version 4.4.1
Exception on start:
[FileLoadException: Could not load file or assembly 'FSharp.Core, Version=4.5.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies. The located assembly's manifest definition does not match the assembly reference. (Exception from HRESULT: 0x80131040)]
System.ModuleHandle.ResolveType(RuntimeModule module, Int32 typeToken, IntPtr* typeInstArgs, Int32 typeInstCount, IntPtr* methodInstArgs, Int32 methodInstCount, ObjectHandleOnStack type) +0
System.ModuleHandle.ResolveTypeHandleInternal(RuntimeModule module, Int32 typeToken, RuntimeTypeHandle[] typeInstantiationContext, RuntimeTypeHandle[] methodInstantiationContext) +197
System.Reflection.RuntimeModule.ResolveType(Int32 metadataToken, Type[] genericTypeArguments, Type[] genericMethodArguments) +166
System.Reflection.CustomAttribute.FilterCustomAttributeRecord(CustomAttributeRecord caRecord, MetadataImport scope, Assembly& lastAptcaOkAssembly, RuntimeModule decoratedModule, MetadataToken decoratedToken, RuntimeType attributeFilterType, Boolean mustBeInheritable, Object[] attributes, IList derivedAttributes, RuntimeType& attributeType, IRuntimeMethodInfo& ctor, Boolean& ctorHasParameters, Boolean& isVarArg) +156
System.Reflection.CustomAttribute.GetCustomAttributes(RuntimeModule decoratedModule, Int32 decoratedMetadataToken, Int32 pcaCount, RuntimeType attributeFilterType, Boolean mustBeInheritable, IList derivedAttributes, Boolean isDecoratedTargetSecurityTransparent) +612
System.Reflection.CustomAttribute.GetCustomAttributes(RuntimeAssembly assembly, RuntimeType caType) +149
WebActivatorEx.AssemblyExtensions.GetActivationAttributes(Assembly assembly) +164
WebActivatorEx.ActivationManager.RunActivationMethods(Boolean designerMode) +321
WebActivatorEx.ActivationManager.RunPreStartMethods(Boolean designerMode) +55
WebActivatorEx.ActivationManager.Run() +74

[InvalidOperationException: The pre-application start initialization method Run on type WebActivatorEx.ActivationManager threw an exception with the following error message: Could not load file or assembly 'FSharp.Core, Version=4.5.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies. The located assembly's manifest definition does not match the assembly reference. (Exception from HRESULT: 0x80131040).]
System.Web.Compilation.BuildManager.InvokePreStartInitMethodsCore(ICollection1 methods, Func1 setHostingEnvironmentCultures) +890
System.Web.Compilation.BuildManager.InvokePreStartInitMethods(ICollection`1 methods) +167
System.Web.Compilation.BuildManager.CallPreStartInitMethods(String preStartInitListPath, Boolean& isRefAssemblyLoaded) +133
System.Web.Compilation.BuildManager.ExecutePreAppStart() +178
System.Web.Hosting.HostingEnvironment.Initialize(ApplicationManager appManager, IApplicationHost appHost, IConfigMapPathFactory configMapPathFactory, HostingEnvironmentParameters hostingParameters, PolicyLevel policyLevel, Exception appDomainCreationException) +746

[HttpException (0x80004005): The pre-application start initialization method Run on type WebActivatorEx.ActivationManager threw an exception with the following error message: Could not load file or assembly 'FSharp.Core, Version=4.5.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies. The located assembly's manifest definition does not match the assembly reference. (Exception from HRESULT: 0x80131040).]
System.Web.HttpRuntime.FirstRequestInit(HttpContext context) +552
System.Web.HttpRuntime.EnsureFirstRequestInit(HttpContext context) +122
System.Web.HttpRuntime.ProcessRequestNotificationPrivate(IIS7WorkerRequest wr, HttpContext context) +737

Version Information: Microsoft .NET Framework Version:4.0.30319; ASP.NET Version:4.8.4210.0

Known workarounds

Add FSharp.Core 4.5.4 package to WebFroms project

[Feature Request] Generic Type parameter for Expression in visit method

Description

It would be nice if the visit method got a generic type overload, so I don't have to cast the expression returned.

return (Expression<Func<Models.Organisation.EducationEvent, bool>>)ExpressionOptimizer.visit(expression);

Not sure how it would look in F# but something like this in C#

public Expression<T> visit<T>(Expression<T> expression)

Unable to use NuGet this in a Microsoft.NETCore.App

Description

Unable to use this in a Microsoft.NETCore.App project.

Repro steps

When adding Linq.Expression.Optimizer
to https://github.com/StefH/QueryInterceptor.Core/tree/master/test/QueryInterceptor.Core.ConsoleApp

And adding
ExpressionOptimizer.visit; to the Main(), you get error message like:

Also two references:

The problem is that the netcoreapp1.0 folder in the NuGet contains two dll's.
Only the Linq.Expression.Optimizer.netcoreApp.dll should be there.

So the NuGet needs fixing.

BTW : I still think that my proposal to build the projects according to my PR (#2) is still a better idea to structure the projects and generate the NuGets.

Warning NU1603 Linq.Expression.Optimizer 1.0.9 depends on FSharp.Core (>= 4.2.0 && < 5.0.0) but FSharp.Core 4.2.0 was not found.

Description

After adding your NuGet package VS complains about unresolvable dependencies to a non existing FSharp.Core version.

Repro steps

Add NuGet package to a new style C# project:

    <PackageReference Include="Linq.Expression.Optimizer" Version="1.0.9">
      <PrivateAssets>All</PrivateAssets>
    </PackageReference>

Expected behavior

No warnings or errors.

Actual behavior

A soft warning NU1603:

Linq.Expression.Optimizer 1.0.9 depends on FSharp.Core (>= 4.2.0 && < 5.0.0) but FSharp.Core 4.2.0 was not found. An approximate best match of FSharp.Core 4.2.1 was resolved.

Known workarounds

Warning disappears when referencing a valid FSharp.Core version manually -- just adding <NoWarn>NU1603</NoWarn> to the PackageReference does not help.

    <PackageReference Include="FSharp.Core" Version="4.2.3">
      <PrivateAssets>All</PrivateAssets>
    </PackageReference>

.Any() in WHERE-statement results in no optimization

Description

A simple Entity Framework query with a Any(...) statement in the WHERE statement results in no optimizations being performed. Excluding the Any(...) part results in optimizations being performed.

Repro steps

Have the simple EF query:

var onlyX = true;

var query =
(
from st in Context.S.AsExpandable()
join la in Context.L on st.LId equals la.LId
where
(
!onlyX ||
(onlyX && la.LId == 3)
) &&
Context.SL.Any(sl => sl.SId== st.SId && sl.UId == null)
select new
{
st.SId,
la.LId
}
);

Expected behavior

Expected the following query

var query =
(
from st in Context.S.AsExpandable()
join la in Context.L on st.LId equals la.LId
where
(
la.LId == 3
) &&
Context.SL.Any(sl => sl.SId== st.SId && sl.UId == null)
select new
{
st.SId,
la.LId
}
);

Actual behavior

The query is left un-optimized.

Removing the "Context.SL.Any(sl => sl.SId== st.SId && sl.UId == null)" statement from the query causes the query to be optimized.

Known workarounds

None.

Related information

Linq.Expression.Optimizer NuGet package 1.0.12 (latest at the time of writing).
LinqKit.EntityFramework NuGet package v1.1.16 (latest at the time of writing).

.NET Standard version seem to target an older version of FSharp.Core

Description

The .NET framework version seems to target the 5.x release but the .standard project is still at (a mixed) 4.x version. 4.x depends on some older versions of System.Runtime.Extensions (and others) which gives problems with newer pinned version (to avoid some related CVEs)

Repro steps

Please provide the steps required to reproduce the problem

1. Install package in modern .NET 7 application that also pins some of the System.* assemblies to 6.x (or later) branches.

Expected behavior

It will resolve packages and install properly

Actual behavior

It gives many many errors like these:

SomeInternalProject -> Linq.Expression.Optimizer 1.0.15 -> FSharp.Core 4.1.18 -> System.Net.Requests 4.0.11 -> System.Net.Http 4.1.0 -> System.IO.FileSystem 4.0.1 -> runtime.win.System.IO.FileSystem 4.3.0 -> System.Threading.Tasks (>= 4.3.0) 
SomeInternalProject  -> Linq.Expression.Optimizer 1.0.15 -> FSharp.Core 4.1.18 -> System.Threading.Tasks (>= 4.0.11)

Also building the *.standard.fsproj project gives me:

repos\Linq.Expression.Optimizer\src\Linq.Expression.Optimizer.standard\Linq.Expression.Optimizer.standard.fsproj : warning NU1504: Duplicate 'PackageReference' items found. Remove the duplicate items or use the Update functionality to ensure a consistent restore behavior. The duplicate 'PackageReference' items are: FSharp.Core 4.2.3, FSharp.Core 4.5.2.

Known workarounds

Forking this library I suppose and figuring out a way to get all the references updated to something newer,

Related information

• Operating system: Windows
• Branch: 1.0.15
• .NET Runtime, CoreCLR or Mono Version: .NET 7.0

EDIT:
The CVEs are: (All in System.Net.Http and/or NETStandard.Library:1.6.1)

CVE-2017-0248

CVE-2017-0249

CVE-2018-8292

CVE-2017-0256

So maybe a .NET standard 2.0 target will allow newer version to be used. (System.Net.Http 4.3.2 or later)

Please bring back support for .NETStandard 1.6

Description

Not able to use library in a .NETStandard,Version=v1.6 project.

Repro steps

Please provide the steps required to reproduce the problem

1. Create a NETStandard Library in VS2017 and change the csproj to:

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <TargetFramework>netstandard1.6</TargetFramework>
  </PropertyGroup>

</Project>

Expected behavior

Should work

Actual behavior

Error message like:

Package Linq.Expression.Optimizer 1.0.8 is not compatible with netstandard1.6 (.NETStandard,Version=v1.6). Package Linq.Expression.Optimizer 1.0.8 supports:

• net35 (.NETFramework,Version=v3.5)
• net45 (.NETFramework,Version=v4.5)
• netcoreapp1.1 (.NETCoreApp,Version=v1.1)
  One or more packages are incompatible with .NETStandard,Version=v1.6.
  Package restore failed. Rolling back package changes for 'ClassLibrary1'.

Actually you can drop support for NETCoreApp 1.1 because when your library is compatible with NETStandard 1.6, it's also compatible with NETCoreApp 1.x.

On the newest version of entity framework core it throws errors

Description

If you try to optimize a query on a DbSet it throws:

System.Exception : encountered unknown LINQ expression: Extension [Microsoft.EntityFrameworkCore.Query.EntityQueryRootExpression]

or

System.Exception : encountered unknown LINQ expression: Extension [Microsoft.EntityFrameworkCore.Query.QueryRootExpression]

both at:

ExpressionOptimizer.visitchilds(Expression e)
ExpressionOptimizer.visit'(Expression exp)
ExpressionOptimizer.visitchilds(Expression e)
ExpressionOptimizer.visit'(Expression exp)
ExpressionOptimizer.visit(Expression exp)
IQueryProvider.CreateQuery[TElement](Expression expression)
ExpandableIncludableQueryProvider`1.CreateQuery[TElement](Expression expression)

Repro steps

.NET 7, EF Core 7, One simple Table with DbSet and a Query on it.
Used LinqKit to inject the optimizer into the IQueryable.

scottksmith95/LINQKit#172

Not optimizing constants near parameters

Description

I used NCalc2 to parse string to Expression

Repro steps

Console.WriteLine(expression);
Console.WriteLine(optimizedExpr);
this yields:

for expression "x+2+2+2"
initial: (((ctx.x + Convert(2, Double)) + Convert(2, Double)) + Convert(2, Double))
optimized: (((ctx.x + Convert(2, Double)) + Convert(2, Double)) + Convert(2, Double))
Should be: (ctx.x + Convert(6, Double))

for expression "x+(2+2+2)"
initial: (ctx.x + Convert(((2 + 2) + 2), Double))
optimized: (ctx.x + Convert(6, Double))
Should be: This is fine!

Expected behavior

Both of them must be able to shorten expression

Known workarounds

add parentheses

Related information

• Windows, webasm
• net.8

Boolean expression reduction (help wanted)

Hi,
I am trying to simplify boolean expressions, that I think it might be achieved with the "binary tree balancing" feature but I am not able to do it based in your examples...

I am looking for something like:

Original: X = AB + A!C

Reduction X = A*(B + !C)

Can you tell me if it is possible and how to do it?

Thanks
Renato Martins

1.0.19 causes FSharp.CoreFile not found exception

Description

Just recently updated to 1.0.19 and got the following runtime error, I noticed the library now relies on FSharp.Core 8 but the paket.template still references 6.0.7

Could not load file or assembly 'FSharp.Core, Version=8.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a'. The system cannot find the file specified.

Reverting to previous version resolves the issue.

Probably need to build a new version now?

Inlined reference values break expression semantics

Description

Inlined reference values break expression semantics

Repro steps

e => !x.HasValue || x.Value < e.Something;

Expected behavior

x.HasValue gets evaluated first on the expression

Actual behavior

It changes the order of the comparisons, resulting in a NullReferenceException

Known workarounds

No

[Feature request] Simplify null == null and null != null

Description

I'm buildning a library of Select Expressions for our product and have found that I would like to do something like this:

internal static class MapperDTO
{
    internal static Expression<Func<Subject, EducationEvent, PeriodData, MyDTO>> ToDTO =>
        (subject, educationEvent, periodData) => new MyDTO
        {
            FolkbokforingskommunName = periodData == null ? subject.Folkbokforingskommun.Name : periodData.Municipality.Name,
        };
}

This is then Invoked and Expanded with LinqKit and passed down to Entity Framework.

Expression<Func<EducationEvent, MyDTO>> mapper = 
    educationEvent => MapperForDTO.ToDTO.Invoke(educationEvent.Subject, educationEvent, null);

Obviously this does not work since null is not allowed for non-static parameters (even static?) but I have looked at the expression tree and this does create an IIF condition that looks like this:

IIF(null == null, subject.Folkbokforingskommun.Name, null.Municipality.Name)

Would it be much work to eliminate the IIF and just replace it with the correct branching?