2
\$\begingroup\$

I'm in the process of implementing a fully generic service to filter out entries (of any type), which are contained in a ICollection. As it is generic, without any constraints, the properties must be accessed through reflection. I'm not fully happy with the performance, even though it respects the minimum response times.

Here's the definition:

public interface IPowerSearchService
{
    /// <summary>
    /// Gets the filtered entries by applying the rules defined by <see cref="expression" /> to the items received in <see cref="collection" />.
    /// </summary>
    /// <typeparam name="T">The type of the object/interface to filter.</typeparam>
    /// <param name="collection">The collection containg all items.</param>
    /// <param name="expression">The expression.</param>
    /// <returns>All items respecting the <see cref="expression"/>.</returns>
    IEnumerable<T> GetFilteredEntries<T>(ICollection<T> collection, IPowerSearchExpressionNode expression);
}

Note that there is no constraint whatsover for T.

With interfaces:

public interface IPowerSearchExpressionNode
{
    IPowerSearchConditionBase Left { get; set; }

    IPowerSearchConditionBase Right { get; set; }

    PowerSearchOperator Operator { get; set; }
}

public interface IPowerSearchConditionBase
{
    bool IsLeaf { get; }
}

public interface IPowerSearchConditionLeaf: IPowerSearchConditionBase
{
    PowerSearchOperation Operation { get; }

    string FieldName { get; }

    object Value { get; }
}

public interface IPowerSearchConditionExpression: IPowerSearchConditionBase
{
    IPowerSearchExpressionNode Expression { get; }
}

and implementations:

internal class PowerSearchExpressionNode : IPowerSearchExpressionNode
{
    public IPowerSearchConditionBase Left { get; set; }

    public IPowerSearchConditionBase Right { get; set; }

    public PowerSearchOperator Operator { get; set; }
}

internal abstract class PowerSearchConditionBase : IPowerSearchConditionBase
{
    protected PowerSearchConditionBase(bool isLeaf)
    {
        IsLeaf = isLeaf;
    }

    public bool IsLeaf { get; }
}

internal class PowerSearchConditionLeaf : PowerSearchConditionBase, IPowerSearchConditionLeaf
{
    public PowerSearchConditionLeaf()
        : base(true) { }

    public PowerSearchOperation Operation { get; set; }

    public string FieldName { get; set; }

    public object Value { get; set; }
}

internal class PowerSearchConditionExpression : PowerSearchConditionBase, IPowerSearchConditionExpression
{
    public PowerSearchConditionExpression()
        : base(false) { }

    public IPowerSearchExpressionNode Expression { get; set; }
}

[Flags]
public enum PowerSearchOperation
{
    Is = 0,
    IsNot = 1,
    Contains = 2,
    DoesNotContain = 4,
    StartsWith = 8,
    DoesNotStartWith = 16
}

[Flags]
public enum PowerSearchOperator
{
    Or = 0,
    And = 1
}

Full implementation of PowerSearchService:

public class PowerSearchService : IPowerSearchService
{
    private readonly IDictionary<PropertyCacheKey, PropertyInfo> _propertiesCache = new ConcurrentDictionary<PropertyCacheKey, PropertyInfo>();

    public IEnumerable<T> GetFilteredEntries<T>(ICollection<T> collection, IPowerSearchExpressionNode expression)
    {
        var leftResult = GetFilteredEntries(collection, expression.Left);
        var rightResult = GetFilteredEntries(collection, expression.Right);

        // Do NOT consider the operator if either the left or right condition are null
        if (expression.Left == null)
        {
            return rightResult;
        }

        if (expression.Right == null)
        {
            return leftResult;
        }

        switch (expression.Operator)
        {
            case PowerSearchOperator.And:
                return leftResult.Intersect(rightResult);

            case PowerSearchOperator.Or:
                return leftResult.Union(rightResult);

            default:
                throw new NotSupportedException($"Operator {expression.Operator} is not supported for power search expressions not being leafs.");
        }
    }

    private IEnumerable<T> GetFilteredEntries<T>(ICollection<T> collection, IPowerSearchConditionBase condition)
    {
        // How it works:
        //  1) Return an empty list if the condition is null
        //  2) Return the matching results if we have a leaf condition
        //  3) Do a recursive call if we have an expression condition
        return condition == null
                   ? Enumerable.Empty<T>()
                   : condition.IsLeaf
                       ? collection.Where(p => MatchesCondition((IPowerSearchConditionLeaf) condition, p))
                       : GetFilteredEntries(collection, ((IPowerSearchConditionExpression) condition).Expression);
    }

    private bool MatchesCondition<T>(IPowerSearchConditionLeaf condition, T obj)
    {
        var entityValues = GetPropertyValues(obj, condition.FieldName).Distinct();
        return entityValues.Any(entityValue => MatchesSingleContition(condition, entityValue));
    }

    [SuppressMessage("ReSharper", "MergeCastWithTypeCheck")]
    [SuppressMessage("ReSharper", "PossibleNullReferenceException")]
    [SuppressMessage("ReSharper", "AssignNullToNotNullAttribute")]
    private bool MatchesSingleContition(IPowerSearchConditionLeaf condition, object obj)
    {
        var searchValue = condition.Value;

        var entityStringValue = obj as string;
        var searchStringValue = searchValue as string;

        switch (condition.Operation)
        {
            case PowerSearchOperation.Contains:
                ThrowNotSupportedExceptionIfNotString(searchValue, PowerSearchOperation.Contains);
                return entityStringValue != null && CultureInfo.InvariantCulture.CompareInfo.IndexOf(entityStringValue, searchStringValue, CompareOptions.IgnoreCase) >= 0;

            case PowerSearchOperation.DoesNotContain:
                ThrowNotSupportedExceptionIfNotString(searchValue, PowerSearchOperation.Contains);
                return entityStringValue == null || CultureInfo.InvariantCulture.CompareInfo.IndexOf(entityStringValue, searchStringValue, CompareOptions.IgnoreCase) < 0;

            case PowerSearchOperation.Is:
                if (entityStringValue != null && searchStringValue != null)
                {
                    return searchStringValue.Equals(entityStringValue, StringComparison.InvariantCultureIgnoreCase);
                }

                return searchValue != null && searchValue.Equals(obj);

            case PowerSearchOperation.IsNot:
                if (entityStringValue != null && searchStringValue != null)
                {
                    return !searchStringValue.Equals(entityStringValue, StringComparison.InvariantCultureIgnoreCase);
                }

                return searchValue == null || !searchValue.Equals(obj);

            case PowerSearchOperation.StartsWith:
                ThrowNotSupportedExceptionIfNotString(searchStringValue, PowerSearchOperation.StartsWith);
                return entityStringValue != null && entityStringValue.StartsWith(searchStringValue, StringComparison.InvariantCultureIgnoreCase);

            case PowerSearchOperation.DoesNotStartWith:
                ThrowNotSupportedExceptionIfNotString(searchStringValue, PowerSearchOperation.DoesNotStartWith);
                return entityStringValue == null || !entityStringValue.StartsWith(searchStringValue, StringComparison.InvariantCultureIgnoreCase);

            default:
                throw new NotSupportedException($"PowerSearchOperation {condition.Operation} is not supported");
        }
    }

    private IEnumerable<object> GetPropertyValues(object src, string propertyName)
    {
        if (src == null)
        {
            throw new ArgumentException("Value cannot be null.", nameof(src));
        }

        if (propertyName == null)
        {
            throw new ArgumentException("Value cannot be null.", nameof(propertyName));
        }

        while (true)
        {
            if (propertyName.Contains("."))
            {
                var propertyNameElements = propertyName.Split(new[] {'.'}, 2);

                // Replace src by a list, in order to use all values of a property being contained in a enumerable
                if (src is IEnumerable srcEnumerable)
                {
                    var tmpSrc = new List<object>();

                    foreach (var element in srcEnumerable)
                    {
                        var propertyValue = GetPropertyValues(element, propertyNameElements[0]);
                        tmpSrc.AddRange(propertyValue.Where(pv => pv != null));
                    }

                    src = tmpSrc;
                }
                else
                {
                    // Use the single property value
                    src = GetPropertyValues(src, propertyNameElements[0]);
                }

                propertyName = propertyNameElements[1];
            }
            else
            {
                // Support a src being a list (enumerable)
                if (src is IEnumerable srcEnumerable)
                {
                    foreach (var element in srcEnumerable)
                    {
                        // The elements contained in a enumerable can be objects or enumerabels; forward them correctly.
                        yield return element is IEnumerable
                                         ? GetPropertyValues(element, propertyName)
                                         : GetPropertyValue(element, propertyName);
                    }

                    break;
                }

                // Handle properties having a value
                yield return GetPropertyValue(src, propertyName);
                break;
            }
        }
    }

    private object GetPropertyValue(object src, string propertyName)
    {
        var propertyCacheKey = new PropertyCacheKey(src.GetType(), propertyName);

        if (!_propertiesCache.TryGetValue(propertyCacheKey, out var propertyInfo))
        {
            var srcType = src.GetType();
            propertyInfo = srcType.GetProperty(propertyName);

            if (propertyInfo == null)
            {
                throw new NotSupportedException($"The property {propertyName} does not exist for type {srcType.Name}");
            }

            _propertiesCache.Add(propertyCacheKey, propertyInfo);
        }

        return propertyInfo.GetValue(src, null);
    }

    private void ThrowNotSupportedExceptionIfNotString(object value, PowerSearchOperation operation)
    {
        if (!(value is string))
        {
            throw new NotSupportedException($"{operation} is only supported for values of type {nameof(String)}. Type was {value?.GetType()}");
        }
    }

    [SuppressMessage("ReSharper", "MemberCanBePrivate.Local")]
    private class PropertyCacheKey
    {
        public PropertyCacheKey(Type type, string propetyName)
        {
            Type = type;
            PropetyName = propetyName;
        }

        private bool Equals(PropertyCacheKey other) => Type == other.Type && PropetyName == other.PropetyName;

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != this.GetType()) return false;
            return Equals((PropertyCacheKey) obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return ((Type != null ? Type.GetHashCode() : 0) * 397) ^ (PropetyName != null ? PropetyName.GetHashCode() : 0);
            }
        }

        public Type Type { get; }

        public string PropetyName { get; }
    }
}

A profiling session with JetBrains dotTrace shows following: enter image description here

The above result has been generated with following console test app. If useful I can also include the Product class along with the other required classes.

public class Program
{
    private const int NbTestProducts = 500000;

    public static void Main(string[] args)
    {
        // Arrange
        var products = GetTestProducts().ToList();
        var powerSearchService = new PowerSearchService();

        const string productNameSearchValue = "uct-1";

        IPowerSearchExpressionNode expression = new PowerSearchExpressionNode
                                                {
                                                    Left = new PowerSearchConditionLeaf
                                                           {
                                                               FieldName = nameof(Product.Name),
                                                               Value = productNameSearchValue,
                                                               Operation = PowerSearchOperation.Contains
                                                           },
                                                    Operator = PowerSearchOperator.Or,
                                                    Right = new PowerSearchConditionExpression
                                                            {
                                                                Expression = new PowerSearchExpressionNode
                                                                             {
                                                                                 Left = new PowerSearchConditionLeaf
                                                                                        {
                                                                                            Operation = PowerSearchOperation.StartsWith,
                                                                                            FieldName = $"{nameof(Product.Type)}.{nameof(ProductType.Name)}",
                                                                                            Value = "Type-3"
                                                                                        },
                                                                                 Operator = PowerSearchOperator.Or,
                                                                                 Right = new PowerSearchConditionLeaf
                                                                                         {
                                                                                             Operation = PowerSearchOperation.StartsWith,
                                                                                             FieldName = $"{nameof(Product.Substances)}.{nameof(Substance.Name)}",
                                                                                             Value = "stance-4-5"
                                                                                         }
                                                                             }
                                                            }
                                                };

        // Act
        var stopwatch = new Stopwatch();
        stopwatch.Start();

        var filteredProducts = powerSearchService.GetFilteredEntries(products, expression)
                                                 .ToList();

        stopwatch.Stop();

        var resume = $"Found {filteredProducts.Count} products out of {products.Count} in {stopwatch.ElapsedMilliseconds}ms:";

        // Show result in console
        System.Console.WriteLine(resume);
        //filteredProducts.ForEach(System.Console.WriteLine);

        // Log result in file
        //File.WriteAllText($"filteredProducts-{DateTime.Now:yyyy-MM-ddTHH-mm-ss}.txt", resume + Environment.NewLine + string.Join(Environment.NewLine, filteredProducts));

        //System.Console.ReadKey();
    }

    private static IEnumerable<Product> GetTestProducts()
    {
        for (var i = 0; i < NbTestProducts; i++)
        {
            yield return new Product
                         {
                             Name = $"Product-{i}",
                             Type = new ProductType
                                    {
                                        Name = $"Type-{i}"
                                    },
                             Substances =
                             {
                                 new Substance {Name = $"Substance-1-{i}"},
                                 new Substance {Name = $"Substance-2-{i}"},
                                 new Substance {Name = $"Substance-3-{i}"},
                                 new Substance {Name = $"Substance-4-{i}"},
                                 new Substance {Name = $"Substance-5-{i}"},
                                 new Substance {Name = $"Substance-6-{i}"}
                             }
                         };
        }
    }
}

Do you see any possibilities to optimize execution?

\$\endgroup\$
  • \$\begingroup\$ Can you post PowerSearchOperation also you are missing the interfaces for Conditional classes and ExpressionNode. \$\endgroup\$ – CharlesNRice Jan 30 at 14:48
  • \$\begingroup\$ @CharlesNRice Sure, I've added a new interfaces section (including the missing interfaces) and added the missing enums to the implementations block \$\endgroup\$ – Philippe Jan 30 at 14:57
  • \$\begingroup\$ Have you tried delegates Fun<T> or Predicate<T> or Expression<T> ? i think you can make use of them in your implementation to minimize use of Reflection. \$\endgroup\$ – iSR5 Jan 31 at 11:32
  • \$\begingroup\$ @iSR5 No I haven't. How do you think they might be useful? \$\endgroup\$ – Philippe Jan 31 at 13:35
  • \$\begingroup\$ I started to review this awhile ago but then felt like I was just recreating dynamic linq. Might be worth looking into that. \$\endgroup\$ – CharlesNRice Feb 12 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.