search

for-GET / jesse

jesse (JSon Schema Erlang) is an implementation of a JSON Schema validator for Erlang.
https://github.com/for-get/jesse
Apache License 2.0
124 stars 64 forks source link

Use conversion to sets to check uniqueItems (performance improvement) #116

Closed germanblanco closed 2 years ago

germanblanco commented 2 years ago

This pull request addresses https://github.com/for-GET/jesse/issues/115

The current implementation of the check for uniqueItems condition in a JSON array seems to be inefficient, with an implementation that has approximately O(n^2) complexity on the number of elements in the array.

This proposal is to change the implementation by using a conversion to a set of the array under uniqueItems condition, and in this way eliminating duplicates efficiently. In order to do this, the format for JSON objects within the array is normalized to Erlang maps.

Implementation of normalization and is_equal is moved to jesse_lib.

germanblanco commented 2 years ago

There was an issue with the macro and OTP releases 20 and lower. I hope it is fixed now.

germanblanco commented 2 years ago

Some issues with CI. Seems latest version of proper requires at least OTP-20. I think the options are:

  • Use older version of proper
  • Create a separate rebar.config profile and make CI to only run proper on OTP >= 20
  • Drop support for OTP-19 (need confirmation from @andreineculau for that)

I think the easiest thing is to use Proper version 1.2.0 for OTP >= 20 and 1.4.0 otherwise. I am going to assume that you mean to crete "rebar.OTPXX.config" files for each release as there are now rebar3.OTPXX files and use links for those releases that are the same, right? i am going to go ahead and try to change the Makefile in that direction.

seriyps commented 2 years ago

Merged. Thank you for your contribution and patience =)