Make structs use the user defined order for mapping to witness indices

[kevaundray]

Problem

Currently in Noir, when a user defines the following struct:

struct Foo {
   a : Field,
   b : Field,
}

Under the hood, we are sorting them by alphabetical order and mapping witness indices to the sorted order.

For example:

a -> WitnessIndex(1)
b -> WitnessIndex(2)

If we were to define the struct by switching its fields:

struct Foo {
   b : Field,
   a : Field,
}

Then the mapping would still be:

a -> WitnessIndex(1)
b -> WitnessIndex(2)

This is a problem for the usecase where the Noir program is being fed into a VM circuit and it expects certain values at certain public indices. The workaround that we have seen for this is users prepending the field_name to force a particular ordering.

---

It is clear that we need to have a user defined ordering, but then the question is whether we should allow users to pick between a user defined ordering and the alphabetical ordering via some attribute or whether we should go for one ordering.

Proposed solution

Preamble

In Rust, we have #[repr(C)] which is similar to a "user defined ordering".

The default is for Rust to decide which ordering internally and it does this so that the compiler can re-arrange and pack the field in the most efficient way.

Proposal

I think we require some more research on this, as its clear that for contract syntax, it would be good to have user defined mapping as the default, but for non-contract semantics, I do not know whether this is also the case.

For me, it seemed like making alphabetical ordering the default and needing users to do

#[repr(user_defined)]
struct Foo {
   b : Field,
   a : Field,
}

Seemed like a viable solution, however @TomAFrench and @zac-williamson have made good points to user-defined being the default and also to the fact that if we re-arrange the arguments in the main function, then this also changes the mapping.

We could then alternatively do:

#[repr(alphabetically_sorted)]
struct Foo {
   b : Field,
   a : Field,
}

The above signifying that user-defined mapping is the default and one needs to specifically say that they want their struct to be alphabetically ordered.

Alternatives considered

No response

Additional context

Before landing a PR:

• Note, we can only specify that our own struct is user-defined/alphabtically sorted. If i depend on a library that is doing user defined mapping and I need alphabetically sorted mapping, this is okay. BUT note that if that library changes their fields, they need to be aware that it is a breaking change.

• I'd like to get some feedback from @Cheethas and Lasse

No response

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[jfecher]

There's been some discussion on slack since the creation of this issue. It seemed to me the consensus was that following the user defined ordering was a better default than the alphabetical ordering. Since there is not much of a usecase for the alphabetical ordering (it is a leakage from the internal detail of us storing fields in a BTreeMap), I don't think we need an annotation either.

[guipublic]

Why can't we change the VM circuit to use alphabetical order?

[jfecher]

This is primarily an issue when generating function signatures for contracts. In these, users would have to match the order the struct fields are specified in the contract, and may need to do the reverse of ordering the struct fields such that they match a desired contract API. The later is not possible if struct fields are always ordered alphabetically, and the former is easier (according to the offsite) if struct field order matches the order they were defined in.