Search code examples
algorithmgraphqlprismaprisma-graphql

Algorithm to filter data structure AND/OR/NOT (similar to GraphQL implementation)

I want to implement a data structure that allows for powerful filtering within my application.

The closest implementation I've found is from Prisma https://www.prisma.io/docs/1.27/prisma-graphql-api/reference/queries-qwe1/#combining-multiple-filters (which is actually from GraphQL specification, for what I understand)

Example:

{
  OR: [
    {
      AND: [
        { title_in: ["My biggest Adventure", "My latest Hobbies"] }
        { published: true }
      ]
    }
    { id: "cixnen24p33lo0143bexvr52n" }
  ]
}

The idea is to compare a context against the filters and see if it's a match.

In the above example, the "context" would be an object with the id, title and published fields.

I'm looking for an algorithm that would perform the comparison and resolve whether it's a match or not.

As I'm not looking at reinventing the wheel (especially that it's a complex algorithm IMHO, as AND/OR/NOT conditions can be nested), I wonder if that particular algorithm already exists, or is based on some standards (as we can find that particular data structure on several apps, such as Prisma, PipeDrive and other).

I'm looking for documentation, implementation examples or even open source implementations. (I'm using JS)

Solution

  • We couldn't find a solution that matched our requirements, so built our own and released it as OSS (MIT).

    https://github.com/UnlyEd/conditions-matcher

    Compares a given context with a filter (a set of conditions) and resolves whether the context validates the filter. Strongly inspired by GraphQL filters.