Poor performance with nested oneOf/allOf and multiple properties

[Amy Sutedja]

Environment

OS: MacOS

Version: 0.23.2

Steps to Reproduce

1. Download the attached OpenAPI spec. (This is a minimal repro case derived from the Splunk Cloud Services public beta.)

2. Compare the file to itself, and time the length of the operation on the command line:

   time openapi-diff splunk-catalog-openapi-perf.yaml splunk-catalog-openapi-perf.yaml

3. Notice the timing result.

4. Uncomment lines 23-41 of the spec and save it.
5. Repeat steps 2 and 3.

Expected

Without lines 23-41, the spec takes ~ 7 seconds to produce a diff.

With lines 23-41, the spec takes ~120 seconds to produce a diff.

Actual

The spec should be able to produce a diff for an arbitrary spec in a reasonable amount of time, where “reasonable” is within ~30 seconds.

[Ben Sayers]

I’ll look into why specifically your schema is having performance issues when I get a chance, however from your description my immediate suspicion is you might be running into the limitations of our schema diffing approach. The following is from the keyword support docs of the json-schema-diff library we are using to find differences in request and response bodies:

‌

https://bitbucket.org/atlassian/json-schema-diff/src/master/KEYWORDS.md

Limitions in the oneOf support

Nesting oneOf keywords inside each other requires an exponentially increasing amount of logical operations in order to calculate the difference. It is expected that the tool will become unusuably slow when given schemas containing many levels of nested oneOf keywords, for example:

{
    "oneOf": [
        {
            "oneOf": [
                {
                    "oneOf": [
                        { 
                            "oneOf": [...] 
                        },
                        ...
                    ]
                },
                ...
            ]
        },
        ...
    ]
}

During testing we've found the tool becomes unusable at around 4 levels of nesting, however your milage may vary.