Imports System.Linq.Expressions

Public Class QueryableTerraServerData(Of TData)
    Implements IOrderedQueryable(Of TData)

#Region "Private members"

    Private _provider As TerraServerQueryProvider
    Private _expression As Expression

#End Region

#Region "Constructors"

    ''' <summary>
    ''' This constructor is called by the client to create the data source.
    ''' </summary>
    Public Sub New()
        Me._provider = New TerraServerQueryProvider()
        Me._expression = Expression.Constant(Me)
    End Sub

    ''' <summary>
    ''' This constructor is called by Provider.CreateQuery().
    ''' </summary>
    ''' <param name="_expression"></param>
    Public Sub New(ByVal _provider As TerraServerQueryProvider, ByVal _expression As Expression)

        If _provider Is Nothing Then
            Throw New ArgumentNullException("provider")
        End If

        If _expression Is Nothing Then
            Throw New ArgumentNullException("expression")
        End If

        If Not GetType(IQueryable(Of TData)).IsAssignableFrom(_expression.Type) Then
            Throw New ArgumentOutOfRangeException("expression")
        End If

        Me._provider = _provider
        Me._expression = _expression
    End Sub

#End Region

#Region "Properties"

    Public ReadOnly Property ElementType() As Type _
        Implements IQueryable(Of TData).ElementType
        Get
            Return GetType(TData)
        End Get
    End Property

    Public ReadOnly Property Expression() As Expression _
        Implements IQueryable(Of TData).Expression
        Get
            Return _expression
        End Get
    End Property

    Public ReadOnly Property Provider() As IQueryProvider _
        Implements IQueryable(Of TData).Provider
        Get
            Return _provider
        End Get
    End Property

#End Region

#Region "Enumerators"

    Public Function GetGenericEnumerator() As IEnumerator(Of TData) _
        Implements IEnumerable(Of TData).GetEnumerator

        Return (Me.Provider.Execute(Of IEnumerable(Of TData))(Me._expression)).GetEnumerator()
    End Function

    Public Function GetEnumerator() As IEnumerator _
        Implements IEnumerable.GetEnumerator

        Return (Me.Provider.Execute(Of IEnumerable)(Me._expression)).GetEnumerator()
    End Function

#End Region

End Class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    public class QueryableTerraServerData<TData> : IOrderedQueryable<TData>
    {
        #region Constructors
        /// <summary>
        /// This constructor is called by the client to create the data source.
        /// </summary>
        public QueryableTerraServerData()
        {
            Provider = new TerraServerQueryProvider();
            Expression = Expression.Constant(this);
        }

        /// <summary>
        /// This constructor is called by Provider.CreateQuery().
        /// </summary>
        /// <param name="expression"></param>
        public QueryableTerraServerData(TerraServerQueryProvider provider, Expression expression)
        {
            if (provider == null)
            {
                throw new ArgumentNullException("provider");
            }

            if (expression == null)
            {
                throw new ArgumentNullException("expression");
            }

            if (!typeof(IQueryable<TData>).IsAssignableFrom(expression.Type))
            {
                throw new ArgumentOutOfRangeException("expression");
            }

            Provider = provider;
            Expression = expression;
        }
        #endregion

        #region Properties

        public IQueryProvider Provider { get; private set; }
        public Expression Expression { get; private set; }

        public Type ElementType
        {
            get { return typeof(TData); }
        }

        #endregion

        #region Enumerators
        public IEnumerator<TData> GetEnumerator()
        {
            return (Provider.Execute<IEnumerable<TData>>(Expression)).GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return (Provider.Execute<System.Collections.IEnumerable>(Expression)).GetEnumerator();
        }
        #endregion
    }
}

Imports System.Linq.Expressions
Imports System.Reflection

Public Class TerraServerQueryProvider
    Implements IQueryProvider

    Public Function CreateQuery(ByVal expression As Expression) As IQueryable _
        Implements IQueryProvider.CreateQuery

        Dim elementType As Type = TypeSystem.GetElementType(expression.Type)

        Try
            Dim qType = GetType(QueryableTerraServerData(Of )).MakeGenericType(elementType)
            Dim args = New Object() {Me, expression}
            Dim instance = Activator.CreateInstance(qType, args)

            Return CType(instance, IQueryable)
        Catch tie As TargetInvocationException
            Throw tie.InnerException
        End Try
    End Function

    ' Queryable's collection-returning standard query operators call this method.
    Public Function CreateQuery(Of TResult)(ByVal expression As Expression) As IQueryable(Of TResult) _
        Implements IQueryProvider.CreateQuery

        Return New QueryableTerraServerData(Of TResult)(Me, expression)
    End Function

    Public Function Execute(ByVal expression As Expression) As Object _
        Implements IQueryProvider.Execute

        Return TerraServerQueryContext.Execute(expression, False)
    End Function

    ' Queryable's "single value" standard query operators call this method.
    ' It is also called from QueryableTerraServerData.GetEnumerator().
    Public Function Execute(Of TResult)(ByVal expression As Expression) As TResult _
        Implements IQueryProvider.Execute

        Dim IsEnumerable As Boolean = (GetType(TResult).Name = "IEnumerable`1")

        Dim result = TerraServerQueryContext.Execute(expression, IsEnumerable)
        Return CType(result, TResult)
    End Function
End Class

using System;
using System.Linq;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    public class TerraServerQueryProvider : IQueryProvider
    {
        public IQueryable CreateQuery(Expression expression)
        {
            Type elementType = TypeSystem.GetElementType(expression.Type);
            try
            {
                return (IQueryable)Activator.CreateInstance(typeof(QueryableTerraServerData<>).MakeGenericType(elementType), new object[] { this, expression });
            }
            catch (System.Reflection.TargetInvocationException tie)
            {
                throw tie.InnerException;
            }
        }

        // Queryable's collection-returning standard query operators call this method.
        public IQueryable<TResult> CreateQuery<TResult>(Expression expression)
        {
            return new QueryableTerraServerData<TResult>(this, expression);
        }

        public object Execute(Expression expression)
        {
            return TerraServerQueryContext.Execute(expression, false);
        }

        // Queryable's "single value" standard query operators call this method.
        // It is also called from QueryableTerraServerData.GetEnumerator().
        public TResult Execute<TResult>(Expression expression)
        {
            bool IsEnumerable = (typeof(TResult).Name == "IEnumerable`1");

            return (TResult)TerraServerQueryContext.Execute(expression, IsEnumerable);
        }
    }
}

Public Class Place
    ' Properties.
    Private _Name As String
    Private _State As String
    Private _PlaceType As PlaceType

    Public Property Name() As String
        Get
            Return _Name
        End Get
        Private Set(ByVal value As String)
            _Name = value
        End Set
    End Property

    Public Property State() As String
        Get
            Return _State
        End Get
        Private Set(ByVal value As String)
            _State = value
        End Set
    End Property

    Public Property PlaceType() As PlaceType
        Get
            Return _PlaceType
        End Get
        Private Set(ByVal value As PlaceType)
            _PlaceType = value
        End Set
    End Property

    ' Constructor.
    Friend Sub New(ByVal name As String, _
                   ByVal state As String, _
                   ByVal placeType As TerraServerReference.PlaceType)

        Me.Name = name
        Me.State = state
        Me.PlaceType = CType(placeType, PlaceType)
    End Sub
End Class

Public Enum PlaceType
    Unknown
    AirRailStation
    BayGulf
    CapePeninsula
    CityTown
    HillMountain
    Island
    Lake
    OtherLandFeature
    OtherWaterFeature
    ParkBeach
    PointOfInterest
    River
End Enum

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LinqToTerraServerProvider
{
    public class Place
    {
        // Properties.
        public string Name { get; private set; }
        public string State { get; private set; }
        public PlaceType PlaceType { get; private set; }

        // Constructor.
        internal Place(string name,
                        string state,
                        LinqToTerraServerProvider.TerraServerReference.PlaceType placeType)
        {
            Name = name;
            State = state;
            PlaceType = (PlaceType)placeType;
        }
    }

    public enum PlaceType
    {
        Unknown,
        AirRailStation,
        BayGulf,
        CapePeninsula,
        CityTown,
        HillMountain,
        Island,
        Lake,
        OtherLandFeature,
        OtherWaterFeature,
        ParkBeach,
        PointOfInterest,
        River
    }
}

Imports System.Linq.Expressions

Public Class TerraServerQueryContext

    ' Executes the expression tree that is passed to it.
    Friend Shared Function Execute(ByVal expr As Expression, _
                                   ByVal IsEnumerable As Boolean) As Object

        ' The expression must represent a query over the data source.
        If Not IsQueryOverDataSource(expr) Then
            Throw New InvalidProgramException("No query over the data source was specified.")
        End If

        ' Find the call to Where() and get the lambda expression predicate.
        Dim whereFinder As New InnermostWhereFinder()
        Dim whereExpression As MethodCallExpression = _
            whereFinder.GetInnermostWhere(expr)
        Dim lambdaExpr As LambdaExpression
        lambdaExpr = CType(CType(whereExpression.Arguments(1), UnaryExpression).Operand, LambdaExpression)

        ' Send the lambda expression through the partial evaluator.
        lambdaExpr = CType(Evaluator.PartialEval(lambdaExpr), LambdaExpression)

        ' Get the place name(s) to query the Web service with.
        Dim lf As New LocationFinder(lambdaExpr.Body)
        Dim locations As List(Of String) = lf.Locations
        If locations.Count = 0 Then
            Dim s = "You must specify at least one place name in your query."
            Throw New InvalidQueryException(s)
        End If

        ' Call the Web service and get the results.
        Dim places() = WebServiceHelper.GetPlacesFromTerraServer(locations)

        ' Copy the IEnumerable places to an IQueryable.
        Dim queryablePlaces = places.AsQueryable()

        ' Copy the expression tree that was passed in, changing only the first
        ' argument of the innermost MethodCallExpression.
        Dim treeCopier As New ExpressionTreeModifier(queryablePlaces)
        Dim newExpressionTree = treeCopier.CopyAndModify(expr)

        ' This step creates an IQueryable that executes by replacing 
        ' Queryable methods with Enumerable methods.
        If (IsEnumerable) Then
            Return queryablePlaces.Provider.CreateQuery(newExpressionTree)
        Else
            Return queryablePlaces.Provider.Execute(newExpressionTree)
        End If
    End Function

    Private Shared Function IsQueryOverDataSource(ByVal expression As Expression) As Boolean
        ' If expression represents an unqueried IQueryable data source instance,
        ' expression is of type ConstantExpression, not MethodCallExpression.
        Return (TypeOf expression Is MethodCallExpression)
    End Function
End Class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    class TerraServerQueryContext
    {
        // Executes the expression tree that is passed to it.
        internal static object Execute(Expression expression, bool IsEnumerable)
        {
            // The expression must represent a query over the data source.
            if (!IsQueryOverDataSource(expression))
                throw new InvalidProgramException("No query over the data source was specified.");

            // Find the call to Where() and get the lambda expression predicate.
            InnermostWhereFinder whereFinder = new InnermostWhereFinder();
            MethodCallExpression whereExpression = whereFinder.GetInnermostWhere(expression);
            LambdaExpression lambdaExpression = (LambdaExpression)((UnaryExpression)(whereExpression.Arguments[1])).Operand;

            // Send the lambda expression through the partial evaluator.
            lambdaExpression = (LambdaExpression)Evaluator.PartialEval(lambdaExpression);

            // Get the place name(s) to query the Web service with.
            LocationFinder lf = new LocationFinder(lambdaExpression.Body);
            List<string> locations = lf.Locations;
            if (locations.Count == 0)
                throw new InvalidQueryException("You must specify at least one place name in your query.");

            // Call the Web service and get the results.
            Place[] places = WebServiceHelper.GetPlacesFromTerraServer(locations);

            // Copy the IEnumerable places to an IQueryable.
            IQueryable<Place> queryablePlaces = places.AsQueryable<Place>();

            // Copy the expression tree that was passed in, changing only the first
            // argument of the innermost MethodCallExpression.
            ExpressionTreeModifier treeCopier = new ExpressionTreeModifier(queryablePlaces);
            Expression newExpressionTree = treeCopier.CopyAndModify(expression);

            // This step creates an IQueryable that executes by replacing Queryable methods with Enumerable methods.
            if (IsEnumerable)
                return queryablePlaces.Provider.CreateQuery(newExpressionTree);
            else
                return queryablePlaces.Provider.Execute(newExpressionTree);
        }

        private static bool IsQueryOverDataSource(Expression expression)
        {
            // If expression represents an unqueried IQueryable data source instance,
            // expression is of type ConstantExpression, not MethodCallExpression.
            return (expression is MethodCallExpression);
        }
    }
}

Imports System.Collections.Generic
Imports LinqToTerraServerProvider.TerraServerReference

Friend Module WebServiceHelper
    Private numResults As Integer = 200
    Private mustHaveImage As Boolean = False

    Friend Function GetPlacesFromTerraServer(ByVal locations As List(Of String)) As Place()
        ' Limit the total number of Web service calls.
        If locations.Count > 5 Then
            Dim s = "This query requires more than five separate calls to the Web service. Please decrease the number of places."
            Throw New InvalidQueryException(s)
        End If

        Dim allPlaces As New List(Of Place)

        ' For each location, call the Web service method to get data.
        For Each location In locations
            Dim places = CallGetPlaceListMethod(location)
            allPlaces.AddRange(places)
        Next

        Return allPlaces.ToArray()
    End Function

    Private Function CallGetPlaceListMethod(ByVal location As String) As Place()

        Dim client As New TerraServiceSoapClient()
        Dim placeFacts() As PlaceFacts

        Try
            ' Call the Web service method "GetPlaceList".
            placeFacts = client.GetPlaceList(location, numResults, mustHaveImage)

            ' If we get exactly 'numResults' results, they are probably truncated.
            If (placeFacts.Length = numResults) Then
                Dim s = "The results have been truncated by the Web service and would not be complete. Please try a different query."
                Throw New Exception(s)
            End If

            ' Create Place objects from the PlaceFacts objects returned by the Web service.
            Dim places(placeFacts.Length - 1) As Place
            For i = 0 To placeFacts.Length - 1
                places(i) = New Place(placeFacts(i).Place.City, _
                                      placeFacts(i).Place.State, _
                                      placeFacts(i).PlaceTypeId)
            Next

            ' Close the WCF client.
            client.Close()

            Return places
        Catch timeoutException As TimeoutException
            client.Abort()
            Throw
        Catch communicationException As System.ServiceModel.CommunicationException
            client.Abort()
            Throw
        End Try
    End Function
End Module

using System;
using System.Collections.Generic;
using LinqToTerraServerProvider.TerraServerReference;

namespace LinqToTerraServerProvider
{
    internal static class WebServiceHelper
    {
        private static int numResults = 200;
        private static bool mustHaveImage = false;

        internal static Place[] GetPlacesFromTerraServer(List<string> locations)
        {
            // Limit the total number of Web service calls.
            if (locations.Count > 5)
                throw new InvalidQueryException("This query requires more than five separate calls to the Web service. Please decrease the number of locations in your query.");

            List<Place> allPlaces = new List<Place>();

            // For each location, call the Web service method to get data.
            foreach (string location in locations)
            {
                Place[] places = CallGetPlaceListMethod(location);
                allPlaces.AddRange(places);
            }

            return allPlaces.ToArray();
        }

        private static Place[] CallGetPlaceListMethod(string location)
        {
            TerraServiceSoapClient client = new TerraServiceSoapClient();
            PlaceFacts[] placeFacts = null;

            try
            {
                // Call the Web service method "GetPlaceList".
                placeFacts = client.GetPlaceList(location, numResults, mustHaveImage);

                // If there are exactly 'numResults' results, they are probably truncated.
                if (placeFacts.Length == numResults)
                    throw new Exception("The results have been truncated by the Web service and would not be complete. Please try a different query.");

                // Create Place objects from the PlaceFacts objects returned by the Web service.
                Place[] places = new Place[placeFacts.Length];
                for (int i = 0; i < placeFacts.Length; i++)
                {
                    places[i] = new Place(
                        placeFacts[i].Place.City,
                        placeFacts[i].Place.State,
                        placeFacts[i].PlaceTypeId);
                }

                // Close the WCF client.
                client.Close();

                return places;
            }
            catch (TimeoutException timeoutException)
            {
                client.Abort();
                throw;
            }
            catch (System.ServiceModel.CommunicationException communicationException)
            {
                client.Abort();
                throw;
            }
        }
    }
}

Imports System.Linq.Expressions
Imports ETH = LinqToTerraServerProvider.ExpressionTreeHelpers

Friend Class LocationFinder
    Inherits ExpressionVisitor

    Private _expression As Expression
    Private _locations As List(Of String)

    Public Sub New(ByVal exp As Expression)
        Me._expression = exp
    End Sub

    Public ReadOnly Property Locations() As List(Of String)
        Get
            If _locations Is Nothing Then
                _locations = New List(Of String)()
                Me.Visit(Me._expression)
            End If
            Return Me._locations
        End Get
    End Property

    Protected Overrides Function VisitBinary(ByVal be As BinaryExpression) As Expression
        ' Handles Visual Basic String semantics.
        be = ETH.ConvertVBStringCompare(be)

        If be.NodeType = ExpressionType.Equal Then
            If (ETH.IsMemberEqualsValueExpression(be, GetType(Place), "Name")) Then
                _locations.Add(ETH.GetValueFromEqualsExpression(be, GetType(Place), "Name"))
                Return be
            ElseIf (ETH.IsMemberEqualsValueExpression(be, GetType(Place), "State")) Then
                _locations.Add(ETH.GetValueFromEqualsExpression(be, GetType(Place), "State"))
                Return be
            Else
                Return MyBase.VisitBinary(be)
            End If
        Else
            Return MyBase.VisitBinary(be)
        End If
    End Function
End Class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    internal class LocationFinder : ExpressionVisitor
    {
        private Expression expression;
        private List<string> locations;

        public LocationFinder(Expression exp)
        {
            this.expression = exp;
        }

        public List<string> Locations
        {
            get
            {
                if (locations == null)
                {
                    locations = new List<string>();
                    this.Visit(this.expression);
                }
                return this.locations;
            }
        }

        protected override Expression VisitBinary(BinaryExpression be)
        {
            if (be.NodeType == ExpressionType.Equal)
            {
                if (ExpressionTreeHelpers.IsMemberEqualsValueExpression(be, typeof(Place), "Name"))
                {
                    locations.Add(ExpressionTreeHelpers.GetValueFromEqualsExpression(be, typeof(Place), "Name"));
                    return be;
                }
                else if (ExpressionTreeHelpers.IsMemberEqualsValueExpression(be, typeof(Place), "State"))
                {
                    locations.Add(ExpressionTreeHelpers.GetValueFromEqualsExpression(be, typeof(Place), "State"));
                    return be;
                }
                else
                    return base.VisitBinary(be);
            }
            else
                return base.VisitBinary(be);
        }
    }
}

Imports System.Linq.Expressions

Friend Class ExpressionTreeModifier
    Inherits ExpressionVisitor

    Private queryablePlaces As IQueryable(Of Place)

    Friend Sub New(ByVal places As IQueryable(Of Place))
        Me.queryablePlaces = places
    End Sub

    Friend Function CopyAndModify(ByVal expression As Expression) As Expression
        Return Me.Visit(expression)
    End Function

    Protected Overrides Function VisitConstant(ByVal c As ConstantExpression) As Expression
        ' Replace the constant QueryableTerraServerData arg with the queryable Place collection.
        If c.Type Is GetType(QueryableTerraServerData(Of Place)) Then
            Return Expression.Constant(Me.queryablePlaces)
        Else
            Return c
        End If
    End Function
End Class

using System;
using System.Linq;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    internal class ExpressionTreeModifier : ExpressionVisitor
    {
        private IQueryable<Place> queryablePlaces;

        internal ExpressionTreeModifier(IQueryable<Place> places)
        {
            this.queryablePlaces = places;
        }

        internal Expression CopyAndModify(Expression expression)
        {
            return this.Visit(expression);
        }

        protected override Expression VisitConstant(ConstantExpression c)
        {
            // Replace the constant QueryableTerraServerData arg with the queryable Place collection.
            if (c.Type == typeof(QueryableTerraServerData<Place>))
                return Expression.Constant(this.queryablePlaces);
            else
                return c;
        }
    }
}

Imports System.Linq.Expressions

Public Module Evaluator
    ''' <summary>Performs evaluation and replacement of independent sub-trees</summary>
    ''' <param name="expr">The root of the expression tree.</param>
    ''' <param name="fnCanBeEvaluated">A function that decides whether a given expression node can be part of the local function.</param>
    ''' <returns>A new tree with sub-trees evaluated and replaced.</returns>
    Public Function PartialEval(ByVal expr As Expression, _
                                ByVal fnCanBeEvaluated As Func(Of Expression, Boolean)) _
                                      As Expression

        Return New SubtreeEvaluator(New Nominator(fnCanBeEvaluated).Nominate(expr)).Eval(expr)
    End Function

    ''' <summary>
    ''' Performs evaluation and replacement of independent sub-trees
    ''' </summary>
    ''' <param name="expression">The root of the expression tree.</param>
    ''' <returns>A new tree with sub-trees evaluated and replaced.</returns>
    Public Function PartialEval(ByVal expression As Expression) As Expression
        Return PartialEval(expression, AddressOf Evaluator.CanBeEvaluatedLocally)
    End Function

    Private Function CanBeEvaluatedLocally(ByVal expression As Expression) As Boolean
        Return expression.NodeType <> ExpressionType.Parameter
    End Function

    ''' <summary>
    ''' Evaluates and replaces sub-trees when first candidate is reached (top-down)
    ''' </summary>
    Class SubtreeEvaluator
        Inherits ExpressionVisitor

        Private candidates As HashSet(Of Expression)

        Friend Sub New(ByVal candidates As HashSet(Of Expression))
            Me.candidates = candidates
        End Sub

        Friend Function Eval(ByVal exp As Expression) As Expression
            Return Me.Visit(exp)
        End Function

        Protected Overrides Function Visit(ByVal exp As Expression) As Expression
            If exp Is Nothing Then
                Return Nothing
            ElseIf Me.candidates.Contains(exp) Then
                Return Me.Evaluate(exp)
            End If

            Return MyBase.Visit(exp)
        End Function

        Private Function Evaluate(ByVal e As Expression) As Expression
            If e.NodeType = ExpressionType.Constant Then
                Return e
            End If

            Dim lambda = Expression.Lambda(e)
            Dim fn As [Delegate] = lambda.Compile()

            Return Expression.Constant(fn.DynamicInvoke(Nothing), e.Type)
        End Function
    End Class


    ''' <summary>
    ''' Performs bottom-up analysis to determine which nodes can possibly
    ''' be part of an evaluated sub-tree.
    ''' </summary>
    Class Nominator
        Inherits ExpressionVisitor

        Private fnCanBeEvaluated As Func(Of Expression, Boolean)
        Private candidates As HashSet(Of Expression)
        Private cannotBeEvaluated As Boolean

        Friend Sub New(ByVal fnCanBeEvaluated As Func(Of Expression, Boolean))
            Me.fnCanBeEvaluated = fnCanBeEvaluated
        End Sub

        Friend Function Nominate(ByVal expr As Expression) As HashSet(Of Expression)
            Me.candidates = New HashSet(Of Expression)()
            Me.Visit(expr)

            Return Me.candidates
        End Function

        Protected Overrides Function Visit(ByVal expr As Expression) As Expression
            If expr IsNot Nothing Then

                Dim saveCannotBeEvaluated = Me.cannotBeEvaluated
                Me.cannotBeEvaluated = False

                MyBase.Visit(expr)

                If Not Me.cannotBeEvaluated Then
                    If Me.fnCanBeEvaluated(expr) Then
                        Me.candidates.Add(expr)
                    Else
                        Me.cannotBeEvaluated = True
                    End If
                End If

                Me.cannotBeEvaluated = Me.cannotBeEvaluated Or _
                                       saveCannotBeEvaluated
            End If

            Return expr
        End Function
    End Class
End Module

using System;
using System.Collections.Generic;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    public static class Evaluator
    {
        /// <summary>
        /// Performs evaluation & replacement of independent sub-trees
        /// </summary>
        /// <param name="expression">The root of the expression tree.</param>
        /// <param name="fnCanBeEvaluated">A function that decides whether a given expression node can be part of the local function.</param>
        /// <returns>A new tree with sub-trees evaluated and replaced.</returns>
        public static Expression PartialEval(Expression expression, Func<Expression, bool> fnCanBeEvaluated)
        {
            return new SubtreeEvaluator(new Nominator(fnCanBeEvaluated).Nominate(expression)).Eval(expression);
        }

        /// <summary>
        /// Performs evaluation & replacement of independent sub-trees
        /// </summary>
        /// <param name="expression">The root of the expression tree.</param>
        /// <returns>A new tree with sub-trees evaluated and replaced.</returns>
        public static Expression PartialEval(Expression expression)
        {
            return PartialEval(expression, Evaluator.CanBeEvaluatedLocally);
        }

        private static bool CanBeEvaluatedLocally(Expression expression)
        {
            return expression.NodeType != ExpressionType.Parameter;
        }

        /// <summary>
        /// Evaluates & replaces sub-trees when first candidate is reached (top-down)
        /// </summary>
        class SubtreeEvaluator : ExpressionVisitor
        {
            HashSet<Expression> candidates;

            internal SubtreeEvaluator(HashSet<Expression> candidates)
            {
                this.candidates = candidates;
            }

            internal Expression Eval(Expression exp)
            {
                return this.Visit(exp);
            }

            protected override Expression Visit(Expression exp)
            {
                if (exp == null)
                {
                    return null;
                }
                if (this.candidates.Contains(exp))
                {
                    return this.Evaluate(exp);
                }
                return base.Visit(exp);
            }

            private Expression Evaluate(Expression e)
            {
                if (e.NodeType == ExpressionType.Constant)
                {
                    return e;
                }
                LambdaExpression lambda = Expression.Lambda(e);
                Delegate fn = lambda.Compile();
                return Expression.Constant(fn.DynamicInvoke(null), e.Type);
            }
        }

        /// <summary>
        /// Performs bottom-up analysis to determine which nodes can possibly
        /// be part of an evaluated sub-tree.
        /// </summary>
        class Nominator : ExpressionVisitor
        {
            Func<Expression, bool> fnCanBeEvaluated;
            HashSet<Expression> candidates;
            bool cannotBeEvaluated;

            internal Nominator(Func<Expression, bool> fnCanBeEvaluated)
            {
                this.fnCanBeEvaluated = fnCanBeEvaluated;
            }

            internal HashSet<Expression> Nominate(Expression expression)
            {
                this.candidates = new HashSet<Expression>();
                this.Visit(expression);
                return this.candidates;
            }

            protected override Expression Visit(Expression expression)
            {
                if (expression != null)
                {
                    bool saveCannotBeEvaluated = this.cannotBeEvaluated;
                    this.cannotBeEvaluated = false;
                    base.Visit(expression);
                    if (!this.cannotBeEvaluated)
                    {
                        if (this.fnCanBeEvaluated(expression))
                        {
                            this.candidates.Add(expression);
                        }
                        else
                        {
                            this.cannotBeEvaluated = true;
                        }
                    }
                    this.cannotBeEvaluated |= saveCannotBeEvaluated;
                }
                return expression;
            }
        }
    }
}

Imports System.Collections.Generic

Friend Module TypeSystem

    Friend Function GetElementType(ByVal seqType As Type) As Type
        Dim ienum As Type = FindIEnumerable(seqType)

        If ienum Is Nothing Then
            Return seqType
        End If

        Return ienum.GetGenericArguments()(0)
    End Function

    Private Function FindIEnumerable(ByVal seqType As Type) As Type

        If seqType Is Nothing Or seqType Is GetType(String) Then
            Return Nothing
        End If

        If (seqType.IsArray) Then
            Return GetType(IEnumerable(Of )).MakeGenericType(seqType.GetElementType())
        End If

        If (seqType.IsGenericType) Then
            For Each arg As Type In seqType.GetGenericArguments()
                Dim ienum As Type = GetType(IEnumerable(Of )).MakeGenericType(arg)

                If (ienum.IsAssignableFrom(seqType)) Then
                    Return ienum
                End If
            Next
        End If

        Dim ifaces As Type() = seqType.GetInterfaces()

        If ifaces IsNot Nothing And ifaces.Length > 0 Then
            For Each iface As Type In ifaces
                Dim ienum As Type = FindIEnumerable(iface)

                If (ienum IsNot Nothing) Then
                    Return ienum
                End If
            Next
        End If

        If seqType.BaseType IsNot Nothing And _
           seqType.BaseType IsNot GetType(Object) Then

            Return FindIEnumerable(seqType.BaseType)
        End If

        Return Nothing
    End Function
End Module

using System;
using System.Collections.Generic;

namespace LinqToTerraServerProvider
{
    internal static class TypeSystem
    {
        internal static Type GetElementType(Type seqType)
        {
            Type ienum = FindIEnumerable(seqType);
            if (ienum == null) return seqType;
            return ienum.GetGenericArguments()[0];
        }

        private static Type FindIEnumerable(Type seqType)
        {
            if (seqType == null || seqType == typeof(string))
                return null;

            if (seqType.IsArray)
                return typeof(IEnumerable<>).MakeGenericType(seqType.GetElementType());

            if (seqType.IsGenericType)
            {
                foreach (Type arg in seqType.GetGenericArguments())
                {
                    Type ienum = typeof(IEnumerable<>).MakeGenericType(arg);
                    if (ienum.IsAssignableFrom(seqType))
                    {
                        return ienum;
                    }
                }
            }

            Type[] ifaces = seqType.GetInterfaces();
            if (ifaces != null && ifaces.Length > 0)
            {
                foreach (Type iface in ifaces)
                {
                    Type ienum = FindIEnumerable(iface);
                    if (ienum != null) return ienum;
                }
            }

            if (seqType.BaseType != null && seqType.BaseType != typeof(object))
            {
                return FindIEnumerable(seqType.BaseType);
            }

            return null;
        }
    }
}

Imports System.Linq.Expressions

Friend Class ExpressionTreeHelpers
    ' Visual Basic encodes string comparisons as a method call to
    ' Microsoft.VisualBasic.CompilerServices.Operators.CompareString.
    ' This method will convert the method call into a binary operation instead.
    ' Note that this makes the string comparison case sensitive.
    Friend Shared Function ConvertVBStringCompare(ByVal exp As BinaryExpression) As BinaryExpression

        If exp.Left.NodeType = ExpressionType.Call Then
            Dim compareStringCall = CType(exp.Left, MethodCallExpression)

            If compareStringCall.Method.DeclaringType.FullName = _
                "Microsoft.VisualBasic.CompilerServices.Operators" AndAlso _
                compareStringCall.Method.Name = "CompareString" Then

                Dim arg1 = compareStringCall.Arguments(0)
                Dim arg2 = compareStringCall.Arguments(1)

                Select Case exp.NodeType
                    Case ExpressionType.LessThan
                        Return Expression.LessThan(arg1, arg2)
                    Case ExpressionType.LessThanOrEqual
                        Return Expression.GreaterThan(arg1, arg2)
                    Case ExpressionType.GreaterThan
                        Return Expression.GreaterThan(arg1, arg2)
                    Case ExpressionType.GreaterThanOrEqual
                        Return Expression.GreaterThanOrEqual(arg1, arg2)
                    Case Else
                        Return Expression.Equal(arg1, arg2)
                End Select
            End If
        End If
        Return exp
    End Function

    Friend Shared Function IsMemberEqualsValueExpression(ByVal exp As Expression, _
                                                         ByVal declaringType As Type, _
                                                         ByVal memberName As String) As Boolean

        If exp.NodeType <> ExpressionType.Equal Then
            Return False
        End If

        Dim be = CType(exp, BinaryExpression)

        ' Assert.
        If IsSpecificMemberExpression(be.Left, declaringType, memberName) AndAlso _
           IsSpecificMemberExpression(be.Right, declaringType, memberName) Then

            Throw New Exception("Cannot have 'member' = 'member' in an expression!")
        End If

        Return IsSpecificMemberExpression(be.Left, declaringType, memberName) OrElse _
               IsSpecificMemberExpression(be.Right, declaringType, memberName)
    End Function


    Friend Shared Function IsSpecificMemberExpression(ByVal exp As Expression, _
                                                      ByVal declaringType As Type, _
                                                      ByVal memberName As String) As Boolean

        Return (TypeOf exp Is MemberExpression) AndAlso _
               (CType(exp, MemberExpression).Member.DeclaringType Is declaringType) AndAlso _
               (CType(exp, MemberExpression).Member.Name = memberName)
    End Function


    Friend Shared Function GetValueFromEqualsExpression(ByVal be As BinaryExpression, _
                                                        ByVal memberDeclaringType As Type, _
                                                        ByVal memberName As String) As String

        If be.NodeType <> ExpressionType.Equal Then
            Throw New Exception("There is a bug in this program.")
        End If

        If be.Left.NodeType = ExpressionType.MemberAccess Then
            Dim mEx = CType(be.Left, MemberExpression)

            If mEx.Member.DeclaringType Is memberDeclaringType AndAlso _
               mEx.Member.Name = memberName Then
                Return GetValueFromExpression(be.Right)
            End If
        ElseIf be.Right.NodeType = ExpressionType.MemberAccess Then
            Dim mEx = CType(be.Right, MemberExpression)

            If mEx.Member.DeclaringType Is memberDeclaringType AndAlso _
               mEx.Member.Name = memberName Then
                Return GetValueFromExpression(be.Left)
            End If
        End If

        ' We should have returned by now.
        Throw New Exception("There is a bug in this program.")
    End Function

    Friend Shared Function GetValueFromExpression(ByVal expr As expression) As String
        If expr.NodeType = ExpressionType.Constant Then
            Return CStr(CType(expr, ConstantExpression).Value)
        Else
            Dim s = "The expression type {0} is not supported to obtain a value."
            Throw New InvalidQueryException(String.Format(s, expr.NodeType))
        End If
    End Function
End Class

using System;
using System.Linq.Expressions;

namespace LinqToTerraServerProvider
{
    internal class ExpressionTreeHelpers
    {
        internal static bool IsMemberEqualsValueExpression(Expression exp, Type declaringType, string memberName)
        {
            if (exp.NodeType != ExpressionType.Equal)
                return false;

            BinaryExpression be = (BinaryExpression)exp;

            // Assert.
            if (ExpressionTreeHelpers.IsSpecificMemberExpression(be.Left, declaringType, memberName) &&
                ExpressionTreeHelpers.IsSpecificMemberExpression(be.Right, declaringType, memberName))
                throw new Exception("Cannot have 'member' == 'member' in an expression!");

            return (ExpressionTreeHelpers.IsSpecificMemberExpression(be.Left, declaringType, memberName) ||
                ExpressionTreeHelpers.IsSpecificMemberExpression(be.Right, declaringType, memberName));
        }

        internal static bool IsSpecificMemberExpression(Expression exp, Type declaringType, string memberName)
        {
            return ((exp is MemberExpression) &&
                (((MemberExpression)exp).Member.DeclaringType == declaringType) &&
                (((MemberExpression)exp).Member.Name == memberName));
        }

        internal static string GetValueFromEqualsExpression(BinaryExpression be, Type memberDeclaringType, string memberName)
        {
            if (be.NodeType != ExpressionType.Equal)
                throw new Exception("There is a bug in this program.");

            if (be.Left.NodeType == ExpressionType.MemberAccess)
            {
                MemberExpression me = (MemberExpression)be.Left;

                if (me.Member.DeclaringType == memberDeclaringType && me.Member.Name == memberName)
                {
                    return GetValueFromExpression(be.Right);
                }
            }
            else if (be.Right.NodeType == ExpressionType.MemberAccess)
            {
                MemberExpression me = (MemberExpression)be.Right;

                if (me.Member.DeclaringType == memberDeclaringType && me.Member.Name == memberName)
                {
                    return GetValueFromExpression(be.Left);
                }
            }

            // We should have returned by now.
            throw new Exception("There is a bug in this program.");
        }

        internal static string GetValueFromExpression(Expression expression)
        {
            if (expression.NodeType == ExpressionType.Constant)
                return (string)(((ConstantExpression)expression).Value);
            else
                throw new InvalidQueryException(
                    String.Format("The expression type {0} is not supported to obtain a value.", expression.NodeType));
        }
    }
}

Public Class InvalidQueryException
    Inherits Exception

    Private _message As String

    Public Sub New(ByVal message As String)
        Me._message = message & " "
    End Sub

    Public Overrides ReadOnly Property Message() As String
        Get
            Return "The client query is invalid: " & _message
        End Get
    End Property
End Class

using System;

namespace LinqToTerraServerProvider
{
    class InvalidQueryException : System.Exception
    {
        private string message;

        public InvalidQueryException(string message)
        {
            this.message = message + " ";
        }

        public override string Message
        {
            get
            {
                return "The client query is invalid: " + message;
            }
        }
    }
}