Bounded lists and strings

This extends #181 with the ability to embed bounded strings or lists directly within other structures while maintaining the variable length property.

Some environments require avoiding all memory allocations at runtime. This happens typically in either small embedded environments or safety related products.

To achieve this in a call returning a string or list/vector you typically combine a fixed size buffer with a length indicator into a containing data structure, e.g. see heapless::String or boost::static_string.

Thus I propose to optionally extend the fixed size buffers of #181 as implemented in #384 with a preceding length indicator. This length indicator could be of type u8 for strings/vectors below 256 elements, u16 below 64k and u32 otherwise. Unused elements in the buffer should be considered uninitialized (MaybeUninit in Rust).

This addresses the problem described in my recent comment in #383 .

I propose the WIT syntax string<..32> or list<u32, ..16>, the binary format would need a new type for bounded strings, lists could use a negative len specifier in 0x67 (see #384 ) or a different defvaltype.

This is a good idea and I've been considering it too. Assuming we add the readable-/writable-buffer types proposed at the end of #369, are there current use cases you're looking at that would benefit from this over the buffer types? Most use cases I can think of could alternatively use readable-/writable-buffer types just as well, although I can imagine some more complex hypothetical scenarios that couldn't.

Whether lazy value lowering can support returning into pre-allocated buffers equally well is a good question.

I know that if caller and callee share the same maximum size the string/list can never overflow the provided buffer on the callee side, simplifying the code considerably.

But what really sold me to this solution is the ease of use on the caller API side. E.g. f: func() -> string<..16>; can be used as let value = f(); (value being of type heapless::String<16> instead of separately providing a buffer and handling overflow. I simply have no idea how to call lazy value lifting in Rust or C++ with the same elegance.

Yes, good point; bounded lists/strings would have the ideal source bindings for languages with facilities for inline allocation.

In the motivation given in your first post, you mentioned the common pattern in C-style APIs of transferring an arbitrary-sized value by repeatedly calling a function and transferring it out chunk at a time. But for that specific case, I would think the writable-buffer type would be the better choice in that it both: (1) gives the caller control of the buffer size (instead of fixing it in the WIT once and for all), (2) provides a pointer to the linear memory up-front as a parameter which, depending on the host implementation, may remove a copy.

However, that's not the only use case for bounded lists/strings, so I mostly wanted to ask, for prioritization reasons, if you had other specific use cases in mind (in WASI or other WIT interfaces you're looking at).

My primary motivation for working on this is the (functional safety) requirement of deterministic execution time. The most straightforward solution is with dedicated pre-allocated buffers provided by the caller.

Return value optimization can enable this even via the very friendly return notation (which internally maps to an output parameter for non atomic types).

I feel with #384 ready (and having its own merit) and this being just a small extension this would be the lowest hanging fruit, given that stream and writable-buffer feel much less possible to finalize within this year.

Right, doing this as a small addition to #384 makes sense and I think the feature makes sense in general. In terms of scheduling/prioritization, you're right that stream will take a while, but I had been thinking that maybe it'd make sense to work on readable/writable buffers as the very next thing. That being said, fixed+bounded-length lists are definitely the smaller/simpler feature and so we could have them ready somewhat sooner -- but I wonder whether the (embedded and other) use cases that want "caller-supplied buffers" will be satisfied or will simply immediately turn to wanting readable/writable buffers.

And just, concretely, if we did have bounded-length lists, but not yet buffers, to avoid realloc with read, we'd need something like:

  read: func(n: u64) -> result<list<u8; ..128>>;

and I wonder if that hard-coded constant (whatever we choose) will seem too ad hoc and imminently-meant-to-be-deprecated to actually ship as a whole WASI release, knowing that what read really wants is:

  read: func(buf: writable-buffer<u8>) -> result;

OTOH, depending on the timings involved, it could be practically worth it to ship the former before the latter. ¯\_(ツ)_/¯

To be honest I never had adding limits to WASI in mind when I thought of this feature, but more specialized custom WIT interfaces which are fully controlled by the runtime designer (or used between two components where the interface can be unilaterally defined by a single party).

I get that this intention defeats the purpose of a generic standardized interface, which is exactly what WASI is about. But for now bounded lists seem the best option for user friendly zero allocation interfaces.

I see, thanks for explaining. Given that #181 was primarily waiting for implementation feedback before merging and this is a relatively small addition, and you've helpfully created #384 as a rebase of #181, would you like to also add this idea to #384? Given both options, perhaps the WAT syntax we want is (list u8 (eq 4)) and (list u8 (lt 4)) for list<u8; 4> and list<u8; ..4> resp.

Oh, wow, this sounded like a small thing to do, but I found that the following things make it really large:

definitions.py has no way to create dummy data or read over data, so lift_flat and lower_flat for bounded types ended up much more laborious
String encoding creates a challenge to flat argument passing, I settled for utf8 or utf16 values per argument, latin1+utf16 makes the length indicator more complex (I chose it to define utf16 elements and multiplied the length indicator by four to handle the double amount of possible entries in case of latin1 and have an extra high bit for the tag)

Also I went for an additional byte in the 0x67 encoding to distinguish between fixed lists, bounded lists and bounded strings.

You can find the current prototype at https://github.com/cpetig/component-model/tree/bounded-lists .
I will continue the work, but it will take longer than originally expected.

Oh right, I forgot to get back to strings. Because of the encoding issues, I think perhaps we should not attempt to extend strings. Instead, if an API wants to do this bounded-size thing, it can just pick a particular encoding (as part of the API's contract) and use a list<u8; ..N>. Otherwise, we'd need string<..K>, where K is necessarily the number of Unicode Scalar Values, to imply a K*4-byte buffer which would be a lot more wasteful than a UTF-8-specialized list<u8; ..K>, which simply implies a K-byte buffer.

I don't think there is a perfect solution for strings due to encoding variation, but taking the maximum length as the number of u8s in utf8 and number of u16s in any of the two utf16 encodings, there is still some possibility of overflow when recoding between components - but the bound has an easy to understand meaning and if both components have the same encoding the bound is identical, so no overflow is possible in the more common case.

At least this was the most sensible solution I came up with.

In addition to an upper bound, could we also add a lower bound, like list<u8, 1..255>?

Sounds reasonable to me.

@badeend

I understand that from a contract design standpoint a lower bound makes sense, but I can't come up with a practical example where it would be beneficial. @badeend Do you have a specific case in mind?

(different from the obvious lower bound of 1 for lists?)

Indeed to indicate a list may not be empty:

https://github.com/WebAssembly/wasi-io/blob/285a31442f687a5ceee86044f9f2b0a9e2beae21/wit/poll.wit#L34C4-L46C57

    /// This function traps if either:
    /// - the list is empty, or:
    /// - the list contains more elements than can be indexed with a `u32` value.
    ///
    /// A timeout can be implemented by adding a pollable from the
    /// wasi-clocks API to the list.
    ///
    /// This function does not return a `result`; polling in itself does not
    /// do any I/O so it doesn't fail. If any of the I/O sources identified by
    /// the pollables has an error, it is indicated by marking the source as
    /// being ready for I/O.
    @since(version = 0.2.0)
    poll: func(in: list<borrow<pollable>>) -> list<u32>;

Better expressed as:

    poll: func(in: list<borrow<pollable>, 1..>) -> list<u32>;
// or even:
    poll: func(in: list<borrow<pollable>, 1..4294967295>) -> list<u32>;
// :P

https://github.com/badeend/wasi-sockets/blob/8f3b082e6ead0eebbcedf10d8a06d16dffbaa68d/wit/tls.wit#L30-L35

    /// Application-Layer Protocol Negotiation (ALPN) protocol ID.
    ///
    /// ALPN IDs are between 1 and 255 bytes long. Typically, they represent the
    /// binary encoding of an ASCII string (e.g. `[0x68 0x32]` for `"h2"`),
    /// though this is not required.
    type alpn-id = list<u8>;

Better expressed as:

    type alpn-id = list<u8, 1..255>;

Totally appreciate that fixed size lists have been merged!
I believe these bounded lists list<T, ..N> could be another great addition towards avoiding some allocations and intent-explicit interface definitions.

Although it seems like just a minor addition of a length value at first glance, we cannot easily emulate this even with fixed size lists.
In some numeric applications, unpopulated elements could possibly be set NaN or zero in a fixed size list.
Generally, one would have to write something like tuple<list<option<T>, N>, u32> - a completely unwieldy type in WIT and source languages, lacking length consistency enforcement on binding level.
With bounded lists we could generate bindings with idiomatic Rust types like &[T] / heapless::Vec or arrayvec::ArrayVec.

I've read through some conversations about caller provided buffers and related concepts - and bounded size lists seem like a much lower bar. Maybe we can have the bounded list as regular container/data type for the time being and offer caller provided buffers as a more optimized/expert approach later?

I would volunteer to join implementation efforts if/once there is consensus and WIT syntax is accepted.

I would volunteer to join implementation efforts if/once there is consensus and WIT syntax is accepted.

I think the existing syntax "consensus" is:

Dynamic: list<T>/(list t)
Fixed Size: list<T, N>/(list t n)
(new) Bounded, potentially empty: list<T, ..N> or list<T, 0..N> - or should we go for list<T, 0, N> instead? I guess (list t (0 n)) is the only reasonable wat syntax.
(new) Bounded, at least one element: list<T, 1..N> or list<T, 1, N>
(new) Dynamic, with guaranteed minimum length: list<T, 1..> (I can't come up with a good syntax for the comma variant). (list t (1 none))?

I have the feeling that a higher minimum length than 1 is rarely needed, so this would add five new binary types (string_0_N, string_1_N, list_0_N, list_1_N, list_1).

For bounded strings, I haven't sensed any good consensus on the interpretation of the bound. I now think that a more meaningful limit is (always 2 byte aligned, even number of) bytes, not characters, although this means that values could become un-representable when re-encoded between components, but at least data structures don't change size depending on encoding.

To be honest, list<T, ..N> is my favorite notation and introducing a lower bound does feel weird:

at first glance list<T, 1..N>, one might think the range are indices (i.e. source language arrays would start at 1)
this would probably be the first (explicit) occurence of WIT bindings enforcing contracts (list shall have no less than x items at runtime).
... well maybe transcoding strings can be viewed as a contract check while doing the work
... and discriminant matching
but those are quite implicit.

Maybe the lower bound is better introduced at a point when there is consenus to add more runtime checks throughout, so that bounded lists do not appear overengineered compared to other parts. Brings back memories of Pascal subrange types (type TDiceRoll = 1 .. 6;)

About bounded strings, I did not quite get the reason for 2-byte alignment? We could define string<..N> such that N is the number of guaranteed available codepoints? In particular, string<N> and string<..N> could be sugar for list<char, N> and list<char, ..N> where a WIT char is 32-bit fixed-width. Not compact but at least deterministic and intelligible. Also matches [char; N] in Rust.
Bindings would probably want to represent this not as a plain [char; N] but arrayvec::ArrayString<4*N> to get a much more versatile &str (USVs are 1..4 bytes).

Drive-by comment: Bounds (both lower and upper) are primarily semantic constraints. But IIUC, the purpose of the component type system is to describe representations, not semantics. A fixed length can easily be argued to be a representation aspect (e.g. distinguishing static vs dynamic data structures), but bounds much less so.

To be honest, list<T, ..N> is my favorite notation and introducing a lower bound does feel weird:

It would be possible to standardize list<T, ..N> first and add the rest once we found a consensus on a syntax. I feel strings open an even larger can of worms and thus should be de-prioritized.

For a wat syntax (list s32 (le 8)) looks like a reasonable suggestion.

About bounded strings, I did not quite get the reason for 2-byte alignment?

That idea kept the encoding option, so utf16 strings would be two byte aligned and should have an equal number of bytes. I like the list<char, ..32> compromise, although it clearly wastes space.

Fully agree. If there is need, strings can be added another day. Once fixed and bounded length lists are both there one could still add strings as a specialization with T=char with lower innovation effort, or, there may be better ideas by that time.

Drive-by comment: Bounds (both lower and upper) are primarily semantic constraints. But IIUC, the purpose of the component type system is to describe representations, not semantics. A fixed length can easily be argued to be a representation aspect (e.g. distinguishing static vs dynamic data structures), but bounds much less so.

Sorry, it took me some time to understand the question. Indeed I am aiming for a representation which works without allocation and can be stored in line (e.g. inside a struct or contiguous memory region). The storage is reserved and wastes a lot of space and isn't cache friendly, but this is common design for functional safety. This is mostly to map existing solutions to WIT without going full into flat representation in shared memory buffers (which is also bounded but cache friendly), see #398 for the more complex solution.

@cpetig

Syntax list<T, ..N> is as good as anything and I would really wish for it to land. With fixed-size lists accepted this seems well in reach, too. This has been open more than 18 months without too much debate.

@cpetig maybe this could make further progress if you resurrected your prototype at https://github.com/cpetig/component-model/tree/bounded-lists (minus the bounded strings, maybe binary encoding adjusted) and created a PR

Just created the PR from a rebase of cpetig's original prototype with minor modifications and less the bounded strings.

@cpetig

@cpetig, sorry for the late response. I'm afraid I still don't quite see the justification for adding bounded lists. I understand that they are for pre-allocation, but it seems to me that is conflating abstract value representations with lifting/lowering concerns. Concretely, such a list is not functionally different from a variable list, and will contain the same dynamic information. The type encodes some additional semantic meta-property about its expected length, but that bound could just as well be out-of-band knowledge.

The way I see this, it is just a special case of wanting a non-canonical lifting/lowering for variable-length lists. But there are plenty of use cases that would urgently want non-canonical liftings/lowerings, for all sorts of types, and clearly, they can't all be built in as separate "canonical" types. Making an exception and privilege for this specific case by elevating it feels like cutting corners. The correct solution would be the ability to define custom lowerings, which IIUC is a long-term goal anyway.

@rossberg

@cpetig, sorry for the late response. I'm afraid I still don't quite see the justification for adding bounded lists. I understand that they are for pre-allocation, but it seems to me that is conflating abstract value representations with lifting/lowering concerns. Concretely, such a list is not functionally different from a variable list, and will contain the same dynamic information. The type encodes some additional semantic meta-property about its expected length, but that bound could just as well be out-of-band knowledge.

The way I see this, it is just a special case of wanting a non-canonical lifting/lowering for variable-length lists. But there are plenty of use cases that would urgently want non-canonical liftings/lowerings, for all sorts of types, and clearly, they can't all be built in as separate "canonical" types. Making an exception and privilege for this specific case by elevating it feels like cutting corners. The correct solution would be the ability to define custom lowerings, which IIUC is a long-term goal anyway.

@rossberg also sorry for the late response. This simply got lost. The main motivation for this datatype is to satisfy functional safety requirements on response time determinism - or more concisely: No dynamic memory.

As the normal list data type requires cabi_realloc on one end and free on the other, in-lineable data types like tuples are a better choice. I agree that there are other ways to achieve this (shared memory or lazy lifting) - but we have been looking for a close equivalent of a heapless vector (Rust) or boost's static_vector https://www.boost.org/doc/libs/1_63_0/doc/html/boost/container/static_vector.html . The data is stored in-line and some elements remain uninitialized. You can modify cabi_realloc to allocate from a fixed pool, but this still leaves the question on where to specify the maximum length - here WIT is the most straightforward place, and then avoiding the cabi_realloc call becomes an option (by using a tuple like in-line storage).

#640 contains a lot of details on how this maps to a proper ABI, together with an open question.

@cpetig

@cpetig, yes, I understand the use case. However, my concern remains unchanged: there is nothing particular special about this use case, and you could come up with many others in a similar boat. Obviously, the type system cannot support all of them directly.

The key criterion for what to elevate to the type system itself should be this: whether it changes the contents of the underlying abstract data representation. That, for a related example, is the case for a fixed size list, because its data does not need to include the size value.

A maximum size OTOH does not at all affect the actual content of the data, compared to an ordinary variable-length list. It only affects how lowering operates, for some clients. As such, support for it does not belong into the (language-neutral) component type system, but into the lifting/lowering layer. Currently, that only supports canonical lowerings, so such a solution would have to wait until that is generalised — just like all other non-canonical cases, of which there are plenty.

The maximum static size would be part of the semantic constraints on the data, which, like all other semantic constraints, is not reflected in the type system but agreed upon by some out-of-band means. From an operational perspective, I fail to see why this needs to be treated specially either.

The key criterion for what to elevate to the type system itself should be this: whether it changes the contents of the underlying abstract data representation.

I think that's a bit too strict; I think we could also motivate types if they offer significantly better language bindings or more-efficient ABI for a meaningful set of languages or APIs.

That being said, thinking about the root problem we're trying to solve here with bounded lists with the benefit of the last 2 years, I'm now questioning whether bounded buffers are really the best way to get caller-supplied buffers in the ABI. In particular, whereas the length of a fixed-length list often comes from the domain and thus often has a single "right" length, it seems like the bound in a bounded-length list is, in all the cases I can imagine, an arbitrary choice where it doesn't seem appropriate to bake the constant bound into the WIT interface for all time. Instead, it seems like a better idea to make the buffer size caller-supplied argument (like in most C APIs). To achieve this, it seems like there are two better options:

As part of our next iteration of the ABI, in addition to adding lazy lowering to handle the general case, I've been thinking that, for the common case of an import returning a small string or list that's not itself nested inside a list (so result<string>, but not list<string>), we could, as a pure ABI detail, allow caller-supplied buffers that dynamically avoid the lazy-value-index allocation when the caller-supplied buffer is big enough.
Add new {readable,writable}-buffer<T> WIT types as discussed in Caller provided buffers question #369. This is the "power user" option that gives the caller the guarantee of no dynamic allocation and the WIT author the ability to define fancy iovec-style operations, but at the cost of having to add and use a new WIT type that has much worse language bindings than list/string in basically every language other than C.

Navigation Menu

Repository navigation

Bounded lists and strings #385

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Bounded lists and strings #385

Description

Activity

lukewagner commented on Aug 14, 2024

cpetig commented on Aug 15, 2024

lukewagner commented on Aug 15, 2024

cpetig commented on Aug 15, 2024

lukewagner commented on Aug 15, 2024

cpetig commented on Aug 15, 2024

lukewagner commented on Aug 16, 2024

cpetig commented on Aug 18, 2024

lukewagner commented on Aug 19, 2024

cpetig commented on Aug 20, 2024

badeend commented on Aug 29, 2024

lukewagner commented on Aug 29, 2024

cpetig commented on Aug 30, 2024

badeend commented on Sep 3, 2024

flelchuk commented on Jan 10, 2026

cpetig commented on Jan 12, 2026

flelchuk commented on Jan 13, 2026

rossberg commented on Jan 13, 2026

cpetig commented on Jan 15, 2026

flelchuk commented on Jan 19, 2026

cpetig commented on Mar 10, 2026

Felix-El commented on Mar 27, 2026

Felix-El commented on Apr 20, 2026

rossberg commented on Apr 22, 2026

cpetig commented on Sep 28, 2026

rossberg commented on Oct 9, 2026

lukewagner commented on Oct 13, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions