Safe and efficient dynamic multi-criteria array filtering javascript

Question

I have a situation, where I need to filter an array using dynamic filter (and sometimes also complex filter criteria).

I have extended the Array class to add a method for this. This works fine, as long as I can specify straightforward filter criteria like {gender: "m"} and I can of course and some of these criteria.

What I would like to do in addition, though, is to specify more complex filter criteria, basically a dynamic callback function for the Array.prototype.filter() method. I can get this to work with eval(), but the performance is horrible and "Don't use eval()" is written all over the internet.

Do you have any suggestions how to solve this? Any suggestion to safely and efficiently pre-compile the complex filter string like ("key1==key2 || (last=="Smith" && gender=="m")

    <script>

    var People = [
        { first: 'Peter', last: 'Henderson', key1:0, gender: "m", key2:0  },
        { first: 'Paul', last: 'Paulson', key1: 10, gender: "m", key2:10   },
        { first: 'Mary', last: 'Miller', key1: 2, gender: "f", key2:0 },
        { first: 'Mary', last: 'Smith', key1: 3 , gender: "f" , key2:3  },
        { first: 'Peter', last: 'Smith' , key1: 4, gender: "m", key2:0 }
    ];
    console.log(People);
    var newPeople = MyArray.from(People).filterBy("@key1 == @key2");
    console.log(newPeople);
    newPeople = MyArray.from(People).filterBy({gender: "m", last:"Smith"});
    console.log(newPeople);
    </script>

classs MyArray extends Array {
  filterBy(argument) {
    return  this.filter(function(el){
      if (typeof argument == "object") {
        // object with key/parameter pairs for filtering:
        // {key1: 0, gender: "m"}
        for (let key in argument) {
          if (argument[key] !== el[key]) return false;
        };
        return true;
      } else if (typeof argument == "string") {
        // string with logical expression with key names @-escaped, e.g.
        // @gender == 'm' && @key1 == @key2
        let expression = argument.split("@").join("el.")
        return eval(expression);
      }
    });
  }
}

Why not just... use People.filter(person => person.key1 === person.key2 || (person.last === "Smith" && person.gender === "m"));? Why do you need an entire extension to Array for something that's already there? — Niet the Dark Absol
– Niet the Dark Absol, Commented Jun 12, 2020 at 13:12
As @NiettheDarkAbsol suggests, this is probably not the best way to approach this. Regardless of how sophisticated your filtering predicate is, it can ultimately be transformed into a function of type A -> Boolean, where A is the type of elements in the array. Then you can pass this function into the standard filter method to obtain an appropriately filtered array. — user1726343
– user1726343, Commented Jun 12, 2020 at 13:18
Hello -- maybe I can't see the forest for the trees here ... but the right hand assignment in your arrow function person.key1 === person.key2 || (person.last === "Smith" && person.gender === "m") would have to be dynamic. Can I build it as a var and hand it over to the .filter method? — Dirk Albrecht
– Dirk Albrecht, Commented Jun 12, 2020 at 13:21
Thanks @NiettheDarkAbsol for pointing in the direction of complexity reduction. I guess my question here boils down to whether is is possible to specify a complex filtering predicate at "runtime" based on user input and then package it in a function? — Dirk Albrecht
– Dirk Albrecht, Commented Jun 12, 2020 at 14:08
@DirkAlbrecht Yes, such a thing is almost certainly possible. If you can edit your question to specify in more detail what the actual predicate is, someone can help you construct it. — user1726343
– user1726343, Commented Jun 14, 2020 at 1:57

score 3 · Accepted Answer · 2022-10-31 06:28:27Z

One way to think about this is that you wish to implement a language of filtering operations. Like any language, this language can be reified into an abstract syntax tree, so that it can be passed around and obtained dynamically.

Based on the single example in your question ("key1==key2 || (last=="Smith" && gender=="m"), let's say you want for your language to support conjunction, disjunction, and equality assertions involving literal values and the fields of the input.

While it isn't strictly necessary, it's often convenient to model the AST of a language as an algebraic data type. There's many libraries for this out there, here is how things look with one:

const { adt, match } = require("@masaeedu/adt")

// First, we build a language of references and predicates
const ref = adt({
  lit: ["some literal value"],
  key: ["the name of some field"]
})
const { lit, key } = ref

const predicate = adt({
  and: ["predicate", "predicate"],
  or: ["predicate", "predicate"],
  equals: ["ref", "ref"]
})

const { and, or, equals } = predicate

// Then we construct an expression in this language
// NB: you could also use a parsing library to parse this out of a string
const yourpredicate =
  or (equals (key ("key1")) (key ("key2")))
     (and (equals (key ("last")) (lit ("Smith")))
          (equals (key ("gender")) (lit ("m"))))

console.log(yourpredicate)
/* =>
{
  label: "or",
  values: [
    {
      label: "equals",
      values: [
        { label: "key", values: ["key1"] },
        { label: "key", values: ["key2"] }
      ]
    },
    {
      label: "and",
      values: [
        {
          label: "equals",
          values: [
            { label: "key", values: ["last"] },
            { label: "lit", values: ["Smith"] }
          ]
        },
        {
          label: "equals",
          values: [
            { label: "key", values: ["gender"] },
            { label: "lit", values: ["m"] }
          ]
        }
      ]
    }
  ]
}
*/

// Then we interpret our language into an actual predicate on some value
const resolve = ref.match({
  lit: v => _ => v,
  key: k => a => a[k]
})

const interpret = predicate.match({
  and: f => g => a => interpret(f)(a) && interpret(g)(a),
  or: f => g => a => interpret(f)(a) || interpret(g)(a),
  equals: r1 => r2 => a => resolve(r1)(a) === resolve(r2)(a)
})

const inputs = [
  { key1: "foo", key2: "bar", last: "Smith", gender: "m" },
  { key1: "foo", key2: "foo", last: "Hurpenglurper", gender: "m" },
  { key1: "foo", key2: "bar", last: "Hurpenglurper", gender: "m" }
]

const p = interpret(yourpredicate)

console.log(inputs.map(p))
// =>
// [true, true, false]

You can run the example and play around with it here: https://runkit.com/masaeedu/reified-predicates

I'd be interested to know if there are any large well supported libraries fro achieving language filtering operations?
@AnthonyPhan The features you want in your language of predicates is typically highly contingent on your business logic, so I'm not sure it's very easy to find general purpose solutions. That said, you might have some success using something like JSON schema or other similar schema languages to construct predicates over arbitrary JSON.

Collectives™ on Stack Overflow

Safe and efficient dynamic multi-criteria array filtering javascript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related