Problems with commutative OR in SPDX expressions

[mirkootter]

Describe the bug

• Scan result contains both "MIT OR Apache-2.0" and "Apache-2.0 OR MIT"
• I have the following license choice:

  - given: "Apache-2.0 OR MIT"
  - choice: "MIT"
  

• Sometimes it works, sometimes the "effectiveLicense" explodes, i.e. I get a very long SPDX-OR-expression

Analysis

The problem is quite obvious in the code. SpdxCompoundExpression have a special equality operator (and hash function) that is order invariant. Therefore, expressions A OR B and B OR A are treated as equal. Therefore, the order does not matter - for the majority of the code, at least.

The effective license is constructed as set over all found license expressions. In my case, both Apache-2.0 OR MIT and MIT OR Apache-2.0 are found, but only one of them makes it into the set. It is probably undefined behaviour which one, or at least should be treated as such, because it is not very reliable.

So far, this looks fine. However, the license choices use string search/replace (see https://github.com/oss-review-toolkit/ort/blob/68.0.0/utils/spdx/src/main/kotlin/SpdxExpression.kt#L351). Here, it very much makes a difference.

In my case, MIT OR Apache-2.0 made it into the effective license. The expression Apache-2.0 OR MIT from the license choice is a valid subexpression, but does not occur in the stringified expression.

As a consequence, the second path is chosen, which essentially rebuilds the effective license as a (very big) OR-expression, connecting all validChoices(). In my case, there are more than one license choices, so the effective license grows exponentially.

[sschuberth]

Thanks for the analysis @mirkootter!

Seems like I had this on my radar at some point as I just rediscovered my sschuberth/spdx-fix-license-choice branch, but then had to drop the ball on that and forgot about it...

[daniel-kr]

I have the same problem. @mirkootter Have you found any workaround for this that could be used until it is fixed? At first, I thought that one must just find the "correct" order of the given: statement. But then I recognized that this "correct" order is different for different packages. This means that one would need to define license choices per package instead of globally. That is the only workaround that comes to my mind. Maybe you found a better one.

[daniel-kr]

@sschuberth Do you have an idea when this could be fixed? Can I help with the fix somehow?

[sschuberth]

Can I help with the fix somehow?

If you want, you could take up my above-mentioned branch and fix any remaining issues. But I have to admit that I do not even remember whether if was more of a PoC (and thus a completely different fix might be required), or whether the basic idea to solve the issue is sound, and just requires some minor tweaking, maybe.

[mirkootter]

Can't we just "fix" the ToString operation, i.e. make it order invariant, for example by sorting the individual substrings? I guess that probably affects many tests which may test against hardcoded string representations, and I haven't tried, but I guess it should work.

@daniel-kr : We do it per package. If you want a global solution, have you considered not usong "given" at all? If you only specify what you want to choose, it should also work. You can give a preference order.

[sschuberth]

Can't we just "fix" the ToString operation, i.e. make it order invariant, for example by sorting the individual substrings?

That's what I tried first as well, but it soon turned out that getting those substrings (for example, licenses and their exception must not be split) is getting quite hard, so it's probably safer / easier to work with the actual expressions.

[daniel-kr]

have you considered not usong "given" at all? If you only specify what you want to choose, it should also work. You can give a preference order.

@mirkootter I don't get this. AFAIK, you cannot omit the "given" in a license choice configuration, can you? You can omit the "given" in a license finding curation configuration but this is not what we want here, right? Or are you using license finding curation configuration as a workaround for the license choice issue?

[mirkootter]

I must admit that I did not try it myself, but it very much looks optional in the source code:

https://github.com/oss-review-toolkit/ort/blob/68.0.0/utils/spdx/src/main/kotlin/SpdxExpression.kt#L195

[sschuberth]

it very much looks optional in the source code:

Correct, it's also documented here:

Without a 'given', the 'choice' is applied to the effective license expression if it is a valid choice.

[daniel-kr]

OK, didn't know that. But still, it would not work for global choices, right? Because the chance that the choices matches all license expressions of all packages and projects is very low. Still an option for package license choices.