search

dhall-lang / dhall-lang

Maintainable configuration files
https://dhall-lang.org
BSD 3-Clause "New" or "Revised" License
4.22k stars 172 forks source link

Should import resolution sort record fields? #1197

Open travisbrown opened 3 years ago

travisbrown commented 3 years ago

I was just updating Dhall for Java after #1190, which turned up a bug in our test setup: we had been normalising after resolving imports in the import tests, so the fixes in #1190 for e.g. AlternativeWithVariable broke our tests.

After fixing our test setup, there's one test that's newly failing, and I'm not sure whether it's a bug in our implementation or in the tests (or in the standard). It's import/success/unit/MixImportModes, where the input looks like this:

{ n = ../../data/simple.dhall, txt = ../../data/simple.dhall as Text, loc = ../../data/simple.dhall as Location }

And the expected result like this:

{ loc = < Environment: Text | Local: Text | Missing | Remote: Text >.Local "./dhall-lang/tests/import/data/simple.dhall", n = 3, txt = "3\n" }

Our import tests no longer normalise after resolving, and our import resolution implementation doesn't sort the expression where imports are being resolved, so the test fails, since it maintains the original order.

Is import resolution supposed to sort record fields? Is there some other reason MixImportModesB.dhall is sorted? It's been a while since I've spent any time looking at the import resolution section of the standard so I might be missing something.

Nadrieril commented 3 years ago

I think the reason is to allow implementations to use an unsorted collection (like a hashmap) to store the contents of a record

travisbrown commented 3 years ago

@Nadrieril That seems reasonable. Should we specify it in imports.md, though, since it's as much a matter of "requiring" a sort as of "allowing" an unsorted representation? Unless the test comparisons are supposed to ignore field order? I don't think that's the case but don't remember for sure.

Nadrieril commented 3 years ago

Hm, either would be a fine solution. I'd prefer mentioning that comparisons ignore order because it leaves more choice to implementors. The only place where we really require sorting is the CBOR encoding

sjakobi commented 3 years ago

Sorting the fields is a part of β-normalizing record types and values: https://github.com/dhall-lang/dhall-lang/blob/master/standard/beta-normalization.md#records

I don't think it should be a required part of import resolution – I think the field order in tests/import/success/unit/MixImportModesB.dhall should simply be fixed.

Regarding specifying that the import tests may ignore the field order, I think that's a reasonable idea.

Gabriella439 commented 3 years ago

I would also be fine removing β-normalization from the import process (for imports not protected by a semantic integrity check). The mandatory normalization has actually ended up being counter-productive for large packages like dhall-kubernetes which have very large normal forms.