【BNode】工具篇1：表达式树构建器ExprBuilder

仓库

仓库链接：ExprBuilder: 一个用来更方便地创建表达式树的工具。

前言

之前我提到过要重置节点编辑器，新的节点编辑器参照Blender的节点系统进行开发，所以我命名为BNode（Blender-like Node）。但工作量已经远远超出了我的预期，所以我打算用一系列文章来记录开发过程，在整理思路的同时也能作为一个不那么正规的说明文档。

工具本身也随着项目需求不断更新，所以本文章的内容也随时可能会被修改以和项目开发进度保持一致。

用途和设计思路

在BNode项目的编辑器环境下，经常需要用到各种反射工具，同时我也需要一个比Emit.ILGenerator更简单易用的方法生成工具，所以我看上了表达式树（Expression）。表达式语句可以像积木一样搭建起来，然后编译成委托使用，比直接使用反射的性能要好一些。

但是构建表达式树的过程既不直观也不轻松，我需要一个工具来简化一下构建过程。它是为开发效率服务的，本身性能并不会比硬写表达式树更好。我将其命名为ExprBuilder，虽然之后我发现Blender中也有同名的工具，但是和此工具并无关系。

由UNeko给出最初的框架设计思路和实现：用列表缓存将要用到的所有参数/变量，然后提供参数/变量的声明/赋值方法，以及If、While等基础语句操作方法。

AI给出的实现一般都是不可用的，但是大致思路并没有什么问题。接下来再由我进行进一步设计和完善。思路和做旧版节点编辑器的差不多：思考我自己想要什么样的使用方式，然后去实现它。

ExprBuilder包含两个部分：参数/变量、表达式列表。

参数/变量

参数或变量的类型都是ParameterExpression，各自使用一个List存起来就可以了。参数和变量的作用不一样：参数是方法中需要传入的部分，而变量则是方法中临时用到的值。在构建表达式树时，首先需要声明变量。在写好几个表达式语句后，用Expression.Block把几句表达式包装成一句表达式块，变量在这个时候传入。表达式块可以作为If、While等操作的参数。表达式块也可以用Expression.Lambda进一步包装成Lambda表达式，参数则在这个时候传入。

如果用伪代码表示的话，就类似于这样：

//Block包装为Lambda时需要传入参数ParameterExpression a,b，表示a,b的作用域限定在整个Lambda内
int Max(int a,int b)
//Block就类似于一对花括号{}（作用域），包装Block时需要传入变量ParameterExpression max，表示变量的作用域限定在此花括号范围内
{
    int max;
    if(a>b)
    {
        //在哪个Block传入变量就像是在哪个范围开头声明变量，因此只需要传入一次就好，不需要在每一个Block都传入
        //如果本层Block和外层Block都传入了同一个变量，则会重新创建同名变量，这一般是不符合预期的
        int max ;//这是不对的！这个max的作用域只在if内部
        max = a;//这里会用到是作用域在if内部的max
    }
    else{ max = b;}
    return max;
}

结合另一个伪代码的例子可以更好地理解表达式块（Block）的作用

int Max(int a,int b);
{//此Block什么也没有传入
    if(a>b){ int max = a;}//此Block传入了ParameterExpression max
    else{ int max = b;}//此Block也传入了ParameterExpression max
    return max;//会报错，因为此Block作用域内不存在变量max
}

需要注意的是，参数/变量的声明语句是不包含在Block内的。另外，变量必须在赋值后才能使用。

参数/变量的声明和赋值方法参考如下：

        public ExprBuilder AddParameter(Type type, out ParameterExpression parameter, string name)
        {
            parameter = Expression.Parameter(type, name);
            _parameters.Add(parameter);
            return this;
        }
        public ExprBuilder DeclareVariable(Type type, out ParameterExpression variable, string name, Expression value = null)
        {
            variable = Expression.Variable(type, name);
            _variables.Add(variable);
            if (value == null) return this;
            return Assign(variable, value);
        }
        public ExprBuilder Assign(Expression target, Expression value)
        {
            if (value == null)
            {
                //报错
                return this;
            }
            var assign = Expression.Assign(target, value);
            _expressions.Add(assign);
            //设置为最后一条有返回值的表达式
            _lastValueExpression = target;
            return this;
        }

表达式列表

可以简单地用List<Expression>去存储表达式语句。这个列表在转为Block时传入。

在封装为Lambda表达式，或着用作If和While之前，需要把数个表达式语句合并为一整个块。但存在一种特殊情况，就是ExprBuilder内不包含任何语句，这时返回默认值。

        protected internal Expression ToSingleExpression(Type defaultReturnType, out Expression returnValue)
        {
            //本项目中，如果没有手动Return，则默认返回最后一条有返回值的表达式，如果也不存在则返回指定类型的默认值
            returnValue = GetOrDefaultReturnValue(defaultReturnType);
            if (_expressions.Count == 0) return returnValue;
            //只要有语句就必须包裹，防止有未包含的变量（例如单句赋值语句）
            return Expression.Block(_variables, _expressions);
        }

对于If和While语句，因为需要创建子Block，所以会临时生成其他ExprBuilder。其中，While语句需要用到Break和Continue标签，所以子ExprBuilder还会储存这两个标签（如果有），以继续传承到While语句的子块中。

        public ExprBuilder If(Expression condition, Action<ExprBuilder> thenBranch, Action<ExprBuilder> elseBranch = null)
        {
            //创建新ExprBuilder时传入自身，以传承一些信息（如标签）
            var thenBuilder = new ExprBuilder(this);
            thenBranch?.Invoke(thenBuilder);
            var thenExpr = thenBuilder.ToSingleExpression(typeof(void), out var thenReturn);
            bool thenHasReturn = !ExpressionUtility.IsNullOrEmpty(thenReturn);
            bool hasElseBranch = elseBranch != null;

            if (hasElseBranch)
            {
                var elseBuilder = new ExprBuilder(this);
                elseBranch.Invoke(elseBuilder);
                var elseExpr = elseBuilder.ToSingleExpression(typeof(void), out var elseReturn);
                //Condition是?:运算符表达式，可能有返回值
                var ifExpr = Expression.Condition(condition, thenExpr, elseExpr);
                bool elseHasReturn = !ExpressionUtility.IsNullOrEmpty(elseReturn);
                //如果两个分支都有返回值，才将此Condition设为最后一条有返回值的表达式
                bool hasReturn = thenHasReturn && elseHasReturn;
                //AddExpr就是简单地往列表里加入此句。AddExprForLast还额外将_lastValueExpression设为此句
                return hasReturn ? AddExprForLast(ifExpr) : AddExpr(ifExpr);
            }
            else
            {
                //IfThen表达式没有返回值
                var ifExpr = Expression.IfThen(condition, thenExpr);
                return AddExpr(ifExpr);
            }
        }
        public ExprBuilder While(Expression condition, Action<ExprBuilder> body = null, LabelTarget breakLabel = null, LabelTarget continueLabel = null)
        {
            // 生成唯一标签名防止冲突
            var labelPrefix = $"While_{Guid.NewGuid():N}";
            breakLabel ??= Expression.Label($"{labelPrefix}_break");
            continueLabel ??= Expression.Label($"{labelPrefix}_continue");

            var bodyBuilder = new ExprBuilder(this);
            bodyBuilder._breakLabel = breakLabel;
            bodyBuilder._continueLabel = continueLabel;

            body?.Invoke(bodyBuilder);
            var bodyBlock = bodyBuilder.ToSingleExpression(typeof(void));
            //标准的while(condition)
            var loopBody = Expression.Block(
                Expression.IfThen(Expression.Not(condition), Expression.Break(breakLabel)),
                bodyBlock);
            var loop = Expression.Loop(loopBody, breakLabel, continueLabel);
            //Loop语句没有返回值
            return AddExpr(loop);
        }
        public ExprBuilder Break()
        {
            if (_breakLabel == null)
            {
                //报错，本块没有跳出标签
                return this;
            }
            return AddExpr(Expression.Break(_breakLabel));
        }
        public ExprBuilder Continue()
        {
            if (_continueLabel == null)
            {
                //报错，本块没有跳出标签
                return this;
            }
            return AddExpr(Expression.Continue(_continueLabel));
        }

接下来是方法的调用。这里先介绍基础的方法调用，它用起来类似于反射的调用方法，需要先根据名称和参数类型等找到对应的MethodInfo，使用起来较为麻烦。

        protected internal ExprBuilder CallMethod(Type type, string methodName, bool isStatic, Expression instance = null, Type[] genericArgs = null, params Expression[] args)
        {
            if (!isStatic && instance == null)
            {
                //报错，因为非静态方法必须有一个执行对象
                return this;
            }
            var validArgs = args.Where(e => e != null).ToArray();
            var method = ...;//根据提供的信息找到对应的MethodInfo
            var call = Expression.Call(instance, method, validArgs);
            return method.ReturnType == typeof(void) ? AddExpr(call) : AddExprForLast(call);
        }

以上就是一个最基础的构建工具包含的内容，包含了参数/变量的声明/赋值，方法调用和If/While控制流。

需要注意的是，Expression.Block默认将块内最后一条语句的返回值设为返回值。因此，如果最后一句表达式没有返回值的话，就需要根据情况特殊处理。本项目中，通过手动执行Return以指定返回值（也就是把某个表达式直接加到列表最后）。另外，如果没有手动Return，将返回最后一条有返回值的表达式。

在构建完成之后，编译为委托之前，还需要将所有表达式转为一个Lambda表达式。这个过程很简单，注意下验证就可以了。

        //这个方法只推荐用于测试，其编译出来的委托就是Delegate类型
        public LambdaExpression Lambda()
        {
            var body = this.ToSingleExpression(typeof(void));
            return Expression.Lambda(body, _parameters);
        }
        //Expression<TDelegate>是LambdaExpression的子类
        public Expression<TDelegate> Lambda<TDelegate>() where TDelegate : Delegate
        {
            var delegateMethod = typeof(TDelegate).GetMethod("Invoke");
            var delegateParams = delegateMethod.GetParameters();

            if (_parameters.Count != delegateParams.Length)
            {
                //报错：目标委托和该ExprBuilder内的参数数量不匹配
                return null;
            }
            for (int i = 0; i < _parameters.Count; i++)
            {
                if (_parameters[i].Type != delegateParams[i].ParameterType)
                {
                    //报错：目标委托和该ExprBuilder内的某个参数类型不匹配
                    return null;
                }
            }
            var body = ToSingleExpression(delegateMethod.ReturnType);
            return Expression.Lambda<TDelegate>(body, _parameters);
        }

引入Lambda

如果到此为止，这个构建工具看似已经可用了，但其实并没有比直接写表达式树方便多少。因为实际使用时，大部分语句都是在调用方法，而用Expression.Call去调用实在是太麻烦了。

为了使用lambda，只需要引入以下方法：

        public InvocationExpression BuildInvoke<D>(Expression<D> expression, params Expression[] args) where D : Delegate
        {
            if (args.Length != expression.Parameters.Count())
            {
                //报错，因为参数数量不匹配
                return null;
            }
            //使用Expression.Invoke，它可能有返回值
            var invokeLambda = Expression.Invoke(expression, Array.AsReadOnly(args));
            return invokeLambda;
        }
        public ExprBuilder Invoke<D>(Expression<D> expression, params Expression[] args) where D : Delegate
        {
            var invokeLambda = BuildInvoke(expression, args);
            return expression.ReturnType == typeof(void) ? AddExpr(invokeLambda) : AddExprForLast(invokeLambda);
        }

你可能注意到，我把Invoke拆成了两个方法。因为某些情况下，并不希望把Invoke表达式本身也加入到表达式列表中。例如，使用一个Invoke<Func<T>>为某个变量赋值。在旧版本中，我把Invoke加入到表达式列表，然后再使用Assign赋值，指定为最后一条有效表达式。这实际上类似于Func();variable = Func();直接导致方法被调用了两次。一种解决方案是提供一个赋值方法，可以自动删去前一句，但这相当具有破坏性，我没有采用。

引入ExpressionVisitor

ExpressionVisitor是C#提供的一个访问工具，它使用Visit(Expression)去遍历一个表达式树。首先通过Visit方法作为入口，Visit方法内部会判断节点类型去调用对应的VisitXXX方法。接下来VisitXXX会遍历相应的子节点，再对各个子节点调用Visit方法。重复这一过程，直到每个节点都被触及。

通过写一个子类去override ExpressionVisitor内部的各种VisitXXX方法，可以实现自定义的访问器。在VisitXXX内部可以做验证，可以返回修改后的新节点等等。

引入ExpressionVisitor并不是必须的，在本项目中的主要用于各个参数类型的自动适配和调试，例如支持在需要float的地方传入int或着object等。

使用示例

使用ExprBuilder去创建一个生成对象的工具。

对于原先需要new的对象，如果只知道其type和各参数的泛型类型是无法new出来的（例如无参构造和多个类型使用相同的构造参数情况下），而使用type.GetConstructor(…).Invoke(…)或着Activator.CreateInstance(…)就要慢上许多。

使用ExprBuilder构建一个New的委托：

            internal static ExprBuilder InitBuilderWithGenericParam<TResult>(Type constructType, Type[] paramTypes, Expression<Func<TResult, TResult>> func = null)
            {
                var exprBuilder = ExprBuilderUtility.GetBuilder();//直接new一个也行
                Expression value;
                //值类型的零参构造需要特殊处理（没有ConstructInfo）
                if (paramTypes == null || paramTypes.Length == 0 && constructType.IsValueType)
                {
                    value = constructType.New();
                }
                else
                {
                    var cons = TryGetCache(constructType, paramTypes);//获取对应的ConstructorInfo，需要自己实现
                    exprBuilder.AddParameters(paramTypes);
                    value = cons.New(exprBuilder.PInfo.Parameters());
                }
                if (constructType != typeof(TResult)) value = value.EnsureConvert<TResult>();//装箱拆箱等操作
                exprBuilder.DeclareVariable<TResult>(out var result,"result",value);
                if (func != null) exprBuilder.Assign(result, func.Invoke(result));
                return exprBuilder;
            }
            public static Func<TResult> Create<TResult>(Type realConstructType = null, Expression<Func<TResult, TResult>> func=null)
            {
                var paramTypes = Type.EmptyTypes;
                realConstructType ??= typeof(TResult);
                var exprBuilder = InitBuilderWithGenericParam<TResult>(realConstructType, paramTypes, func);
                return exprBuilder.Func<TResult>().Compile();
            }
            public static Func<T1, TResult> Create<T1, TResult>(Type realConstructType = null, Expression<Func<TResult, TResult>> func = null)
            {
                var paramTypes = new[] { typeof(T1) };
                realConstructType ??= typeof(TResult);
                var exprBuilder = InitBuilderWithGenericParam<TResult>(realConstructType, paramTypes, func);
                return exprBuilder.Func<T1, TResult>().Compile(); ;
            }
            //省略更多泛型参数版本

对于原先使用Constructor，也就是知道其type和各参数的type的情况下，希望得到一个更快的生成方式。

            public static Func<object[], TResult> ConstructCreate<TResult>(Type realConstructType, Type[] paramTypes = null, Expression<Func<TResult, TResult>> func = null)
            {
                realConstructType ??= typeof(TResult);
                var exprBuilder = ExprBuilderUtility.GetBuilder();
                exprBuilder.AddParameter<object[]>(out var inParas, "inParas");
                Expression value;
                if (paramTypes == null || (paramTypes.Length == 0 && realConstructType.IsValueType))
                {
                    value = realConstructType.New();
                }
                else
                {
                    var cons = TryGetCache(realConstructType, paramTypes);
                    exprBuilder.DeclareVariables(paramTypes, out var vs, i => inParas.ArrayAccess(i).EnsureConvert(paramTypes[i]));
                    value = cons.New(vs);
                }
                if (realConstructType != typeof(TResult)) value = value.EnsureConvert<TResult>();
                exprBuilder.DeclareVariable<TResult>(out var result, "result", value);
                if (func != null) exprBuilder.Assign(result, func.Invoke(result));
                return exprBuilder.Func<object[], TResult>().Compile();
            }

对于原先使用Activator，也就是只知道其type和给定参数的情况下，希望得到一个更快的生成方式。

            public static Func<object[], TResult> ActivatorCreate<TResult>(Type realConstructType = null, Expression<Func<TResult, TResult>> func = null)
            {
                realConstructType ??= typeof(TResult);
                var hasDefaultConstructor = realConstructType.IsValueType;

                var exprBuilder = ExprBuilderUtility.GetBuilder();
                exprBuilder.AddParameter<object[]>(out var inParas, "inParas");
                exprBuilder.DeclareVariable<TResult>(out var result,"result") ;

                if (hasDefaultConstructor)
                {
                    //值类型多一步判断
                    exprBuilder.If(inParas.Property("Length").Equal(0),
                        then =>
                        {
                            Expression value = realConstructType.New();
                            if(realConstructType!=typeof(TResult)) value = value.EnsureConvert<TResult>();
                            then.Assign(result, value);
                        },
                        ele =>
                        {
                            var invoke = ele.BuildInvokeFunc<object[], TResult>(objs => (TResult)TryGetCache(realConstructType, objs).Invoke(objs), inParas);
                            ele.Assign(result, invoke);
                        });
                }
                else
                {
                    var invoke = exprBuilder.BuildInvokeFunc<object[], TResult>(objs => (TResult)TryGetCache(realConstructType, objs).Invoke(objs), inParas);
                    exprBuilder.Assign(result, invoke);
                }
                if (func != null) exprBuilder.Assign(result, func.Invoke(result));

                return exprBuilder.Func<object[], TResult>().Compile();
            }

其实还可以扩展一个更有趣的生成方式，把Type也作为委托的参数之一，这样只需要生成一次委托，就可以到处使用了，我把它叫做为Universal。

            public static Func<Type, object[], object> UniversalCreate(Expression<Func<object, object>> func = null)
            {
                var exprBuilder = ExprBuilderUtility.GetBuilder();
                exprBuilder.AddParameter<Type>(out var constructType, "constructType");
                exprBuilder.AddParameter<object[]>(out var inParas, "inParas");

                var invoke = exprBuilder.BuildInvokeFunc<Type, bool>(t => t.IsValueType, constructType);
                exprBuilder.DeclareVariable<bool>(out var hasDefaultConstructor, "hasDefaultConstructor", invoke);
                exprBuilder.DeclareVariable<object>(out var result, "result");
                exprBuilder.If(inParas.Property("Length").Equal(0).And(hasDefaultConstructor),
                    then =>
                    {
                        var b = then.BuildInvokeFunc<Type, object>(type => Expression.Lambda<Func<object>>(type.New().EnsureConvert<object>(null), then.PInfo.Parameters()).Compile().Invoke(), constructType);
                        then.Assign(result, b);
                    },
                    ele =>
                    {
                        var b = ele.BuildInvokeFunc<Type, object[], object>((type, objs) => TryGetCache(type, objs).Invoke(objs), constructType, inParas);
                        ele.Assign(result, b);
                    });
                if (func != null) exprBuilder.Assign(result, func.Invoke(result));
                return exprBuilder.Func<Type, object[], object>().Compile();
             }

测试一下性能如何。对于类Mu(int a, string b, bool c)，分别使用以下方法获取委托并生成十万个对象（使用循环，确保每次创建的初始值都不一样）。对于原生的New、Construct和Activator方法则不使用委托，直接调用相应代码。

Create<int,string,bool>(type);

ConstructCreate(type,new Type[] { typeof(int), typeof(string), typeof(bool) });

ActivatorCreate(type);

UniversalCreate();

对比两个红圈里的耗时，发现此工具基本满足所有需求。注意，以上计时不包括初次编译委托（每个大约20ms），因此在大量创建对象时比较有用。编译时间是使用表达式树无法避免的问题，没有银弹。