1
\$\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\$
5
  • \$\begingroup\$ Can you post PowerSearchOperation also you are missing the interfaces for Conditional classes and ExpressionNode. \$\endgroup\$ Jan 30, 2020 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, 2020 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, 2020 at 11:32
  • \$\begingroup\$ @iSR5 No I haven't. How do you think they might be useful? \$\endgroup\$
    – Philippe
    Jan 31, 2020 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\$ Feb 12, 2020 at 14:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.