Implement MessageFormat

[sffc]

I couldn't find an issue to track the ICU4X implementation of MessageFormat, so I'm making one now.

We should implement MF2 syntax, of course, but we also will likely want to support MF1 syntax, at least as a conversion step.

@zbraniecki @mihnita

Hello @sffc , is there a recent plan to implement this?

[sffc]

@echeran is going to look into this in Q3.

@sffc @echeran Thank you! Please keep me in the loop since this is the main feature we are looking for from your library!

[jiyuntu]

Btw I deleted my work account and merged it to my personal account, so now the author of my past comments is ghost. I'll follow up using this new account (we still care about this feature!), and you can reach out to me via chat, email, anything just like before.

[sffc]

@echeran design doc: https://docs.google.com/document/d/1X5qiEK1swGYMblwbBcOu1HkiZUbL4yhnekVyzPPQo-o/edit?tab=t.0#heading=h.r76nofm7sof

WG discussion:

• @sffc As a general framework, enums are smaller and faster than trait objects.
• @zbraniecki I think the MF data model is a perfect example of the architecture I've been pursuing in ICU4X for a long time, which is that you have a reference AST and a runtime AST, and those ASTs are different. I think we're in a position to add a DSL for MF tooling in the future. You're instead looking at a data model for the runtime execution of MessageFormat. But, neither of these examples are optimal for "serialize, deserialize" which is what tools want to do. So "format" and "edit" are different use cases. But, there is likely some overlap between the two data models.
• @zbraniecki Have you look at fluent rs?
• @echeran Not completely
• @zbraniecki Ok, because fluent rs is an implementation of a syntax similar to MF2, including a serializer, etc.

https://github.com/projectfluent/fluent-rs/blob/main/fluent-syntax/src/ast/mod.rs

https://github.com/projectfluent/fluent-rs/tree/main/fluent-syntax/src/parser

https://github.com/projectfluent/fluent-rs/blob/main/fluent-syntax/src/serializer.rs

https://github.com/projectfluent/fluent-rs/tree/main/fluent-bundle/src/resolver

• @zbraniecki We spent multiple years with Manish and Stas making sure this is performant. So I think we should look at something like that. What you might find is that Manish designed a model in it that accomodates what I think you will encounter in MF2: a customer may want to add custom functions.
• @Manishearth About enums vs traits: enums are generallky better, but traits let people implement their own thing. So we could potentially make an enum where one variant is a trait object; you don't hit the branch unless you are actually using this. And it's best with a trait object if you can borrow and avoid the destructor (dyn Drop). We could even feature-gate.
• @hsivonen We should probably invite Eemeli to review this. Do you have an idea of when this would be in a stage for Eemeli to review this?
• @echeran Maybe another week so I can think about APIs for it.
• @zbraniecki If you want to look at the lessons learned from writing the Fluent parser and resolver, so that it handles both roles of reference and runtime, the trick Manish came up with is a slice: you generalize everything over a slice.

https://github.com/projectfluent/fluent-rs/blob/main/fluent-syntax/src/parser/slice.rs

Here's how we do customer attached functions - https://github.com/projectfluent/fluent-rs/blob/main/fluent-bundle/src/entry.rs#L13

• @Manishearth It's been a while since I worked on this, like 7 years. We could apply some of these principles, but things have changed and we might tailor the choices to what works best for ICU4X.
• @zbraniecki I agree
• @zbraniecki My main point is that I think you should design this so that it works well for the tooling ecosystem.
• @echeran It makes sense that in Java, you'd use interfaces with dynamic dispatch, but that's not what Rust is optimized for. And the line of "is the user customizing this or not" seems good.
• @echeran As far as the Fluent way of doing things: I don't know if we need an enum variant for custom items in general; we need them for functions. It seems you don't need the enum if you have the trait.
• @echeran I'm focused on the runtime part of it. Manipulating the AST is nice to have. I have questions about that, which veers off the main focus.
• @Manishearth Functions are the main point of customizability. I don't think AST manipulation is that good... the performance... the ease of working with enums in Rust ends up better here. About the functions, you could keep a global function ID in the enum and avoid the dynamic dispatch / trait object entirely.
• @sffc There are a few ways we can do custom functions. All trait, enum with trait, global registry, function pointer. We should continue to iterate on that.
• @zbraniecki I think it's worth looking at how Fluent solved custom functions. It is a good starting point. By my recollection, we spent the most time going back and forth on slices. There are questions about how to represent escaped Unicode sequences.
• @sffc It may be worth exploring whether we can flatten the attributes and options into the main vec of parts. For example, pub enum Expression can get an Option and Attribute variant that mean, "add this option or attribute to the previous function". Then we can use ZeroVec<Part>, and Vec<Part> has a very cheap Drop impl. These are concrete implementation benefits, but they should be weighed against the tradeoffs.
• @zbraniecki I don't think we should complicate the model or be non-Rusty.
• @sffc I push back on that. I don't think my flattened model is non-Rusty. It diverges from MF 2.0, so it is not useful as a reference AST.
• @zbraniecki I think the trifecta is functionality, maintenance, and performance. We can make performance optizations and measure them with the great tooling we have in Rust.
• @sffc We have a lot of experience doing measurements over the last 5 years and we know the things that have the biggest impacts on performance. Those things include avoiding trait objects, avoiding drop impls, avoiding branching, avoiding runtime allocations. So I think we should just go straight to the solution rather than spending engineering cycles measuring every little thing.
• @zbraniecki I disagree with that because I think the performance characteristics of MF are different than the performance characteristics of e.g. datetime data.

[Manishearth]

I didn't say much during the actual discussion and had to drop at the end of the meeting, but on the topic of the AST structure in broad strokes I lean towards Zibi's position: the performance characteristics of MF are going to be different from things like datetime, and attribute-like things are not a thing we've had to deal with in datetime, we have lengths and those are stored with the fields.

I do not think it is a given that flattening attributes will be a win here, because it will complicate everything else. It's less about Rustiness and more just about what is most efficient for processing, and I'm not convinced that a flattened model will be efficient.

That said, flattening attributes simplifies a lot of things about writing easy zerovec impls.

Those things include avoiding trait objects, avoiding drop impls, avoiding branching, avoiding runtime allocations.

A non-flattened model does not imply any of these things IMO. Zerovec is powerful enough to support both a flattened and a non-flattened data model. The non-flattened one is a bit harder to do but possible.

[sffc]

Flattening produces substantially smaller and faster Drop impls. With nesting, you have to iterate over the whole message every time you Drop. I've seen this before in other components.

This principle applies as much to MF as to any other component. I'm especially concerned about MF code size because it can bloat quickly.

It also makes ZeroVec impls easier, which may not be as applicable to MF.

[sffc]

Evidence for my claim:

Program 1:

#![crate_type = "cdylib"]

#[no_mangle]
pub fn drop_vec_of_usize(v: Vec<usize>) -> usize {
    std::hint::black_box(v).capacity()
}

ASM: 18 instructions. No loop or branching except for a single je that checks if the vec is empty.

Program 2:

#![crate_type = "cdylib"]

use smallvec::SmallVec;

#[no_mangle]
pub fn drop_vec_of_smallvec(v: Vec<SmallVec<[u8; 4]>>) -> usize {
    std::hint::black_box(v).capacity()
}

ASM: 44 instructions. Includes a loop over every element. Lots of branching with je.

https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=33c414ac172d1a4826d249a73ea9899f