Test "component diamond" is failing on MacOS

[ckyang0225]

I installed cps-config on MacOS and ran ninja -C builddir test.
All tests passed however only component diamond generated reversed order result:

▶ 4/4 - component diamond           FAIL
4/4 pkg-config compatibility        FAIL            0.08s   19/20 subtests passed
>>> CPS_PATH=/Users/cyang571/src/cps-config/tests/cases ASAN_OPTIONS=halt_on_error=1:abort_on_error=1:print_summary=1 MALLOC_PERTURB_=161 UBSAN_OPTIONS=halt_on_error=1:abort_on_error=1:print_summary=1:print_stacktrace=1 /opt/homebrew/bin/python /Users/cyang571/src/cps-config/builddir/../tests/runner.py ./cps-config tests/cases.toml
――――――――――――――――――――――――――――――――――――――――――――――― ✀  ―――――――――――――――――――――――――――――――――――――――――――――――
stderr:
component diamond:
  returncode: 0
  stdout:   -I/opt/include -I/something
  expected: -I/something -I/opt/include
  stderr:
  command: ./cps-config diamond --cflags-only-I

I'm not sure if this problem only happen in MacOS, however the expected result -I/something -I/opt/include makes more sense for me, while it follows the "requires" order:

## Quoted from diamond.cps
needs-components1 -> multiple-components -> sample3 -> /something
needs-components2 -> multiple-components -> sample2 -> /opt/include

Does it make sense to find some way to guarantee the order of "requires"?

[bretbrownjr]

Nice find!

It looks like the test assertions are too specific. Probably a hash table is ordering differently, resulting in a different iteration order, which is allowable behavior.

The tests have the defect, I expect. They should be looking for these entries existing in an unordered set of results.

[dcbaker]

Is it really safe to be unordered? I assumed that the order is significant, because that's (IIUC) what pkg-config assumes.

[bretbrownjr]

I don't know about unsafe as such, but that's a good point.

Topologically sorting nodes is a partial sort, meaning some ordering differences are acceptable. Environments have bugs that break because of a different but valid topological sort.

In my experience, this is usually because of a missing dependency somewhere, and adding the ability to override the build solution to add extra edges between components should allow most issues to be worked around until patches to relevant packages can be applied.

But I'll defer to experience if that's still too much of an adoption hurdle.

As far as I can tell, pkg-config does topological sorting and resolves "ties" in partial sorting ambiguities with the original ordering provided to the pkg-config command. One way to model this is by using a binary tree data structure and ordering the direct children of the root node by the order they were provided in.

[ckyang0225]

Thanks @bretbrownjr @dcbaker detailed and prompt response.
It sounds reasonable that making this test more flexible to allow unordered set of results, since the topologically sort may not guarantee the order of same-level nodes of the diamond tree.
Let me find some way to make this test more flexible then.