Note also that AbsPathBuf wraps Utf8PathBuf, not PathBuf. Utf8PathBuf is itself a custom, "parsed" type refinement from the camino crate. Regular paths in the Rust standard library aren't guaranteed to be valid UTF-8, so they cannot be easily converted to a String (which has to be valid UTF-8 in Rust); camino::Utf8PathBuf establishes validity on construction, and can then be converted to a string with just:
Well, I'm glad it's only rust-analyzer. As an amateur archivist and "someone with a collection, but not a collector", my filesystem contains various mojibake'd filenames I haven't had time to find the correct iconv conversion for (and corrupted dates from old DOS disks that somehow got their metadata corrupted while the files still pass validation) and I really don't like it when tools die because they can't handle valid-under-POSIX paths.
It's presumably the fault of the language server protocol which sends our paths as URIs in JSON. So you need some way to encode mojibake in a valid UTF-8 string.
Sort-of. By design, rust-analyzer isn't an LSP server. It is a library, which exposes structured API. LSP is just one way to "serialize" the results, so nothing LSP specific should leak into rust-analyzer proper. If LSP can't represent something, it's LSP's problem!
But where JSON leaks in a more fundamental way is that the interface to the build system, cargo metadata, or rust-project.json, is JSON based. I think we still could do the pedantically correct thing there (and we used to!), but if upstream cargo-metadata uses utf8 paths, that's not necessarily the most important windmill to die on.
I forget what it was called, but there is such an encoding that I ran across recently.
I'd already been doing my own mojibake-encoding for storing them in JSON by taking advantage of the fact that \0 (NUL) is defined as valid in JSON strings by the JSON spec, but not in POSIX paths, to use it as an escape character meaning "the following codepoint in the range 0 to 255 should be interpreted as a raw byte".
(I initially tested something like a dozen JSON implementations in a bunch of (admittedly non-C) languages and the only one I found that didn't handle nulls in strings properly was PHPs... and I think they've fixed that since then.)
That way, the encoding of all previously allowed paths remains unchanged. Full backwards compatibility.
I forget what it was called, but there is such an encoding that I ran across recently.
I see you've found it in the other thread, but Raku (aka Perl 6) has their own solution using "NFG synthetics" to handle non-UTF-8-compatible byte-sequences, which you may also find interesting
Sure, but AFAIK the lsp server (i.e. Rust analyzer) just receives paths from the lsp client (i.e. the text editor). So the server only has to deal with UTF-8 paths.
WTF-8 is UTF-8 plus the ability to encode unpaired surrogates. That's useful if you'd really like to work with UTF-8 but you can't because you have to handle input that's potentially truncated UTF-16 (or UCS-2).
It won't help you here because WTF-8, being a superset, is not generally valid UTF-8 and so can't be used in conforming JSON strings.
No, that's a variation on UTF-8. I'm talking about a scheme that operated at a layer of abstraction more akin to percent encoding or base64 and was described, either explicitly or by the focus of its example uses, as being for allowing non-UTF8 bytes to be stored/transmitted in UTF-8-only channels.
...and I'm having a helluva time finding it again. All I remember is that, some time within the last couple of months, I ran into it being mentioned by acronym and hyperlinked in a spec or proposal for implementing something else, and that I had a "Huh. So someone already did it." moment because it struck me as one of those "Well-known, and made by someone much more important than me, but I'd never known about it" things like BSON or base85.
(And I apparently didn't do a good enough job of adding extra keywords for words I might think of it by when bookmarking it.)
EDIT: Found it. I was thinking of the bytecode alliance's "ARF strings" (ARF being short for "Alternative Representation for Filenames") and my browser history says I encountered it on 2026-07-14. (I do still intend to go with my solution since you need \0 either way but, with my scheme, paths which are UTF-8-clean pass through the encode/decode stage unchanged.)
rust-analyzer used to be pretty pedantic in distinguishing "makefile" path, as written in the source code (which must be utf8) from the OS path where the root of the project is located. We use at-style representation where every path (even an absolute!) is anchored to the context where that path makes sense. I think we dropped non-utf8 parts after cargo?
I don't think it's a big mistake either way (though I consider utf8-only paths to be a mistake for systems software). My mind on this topic changed significantly after I learned that cargo was panicking on non-utf8 paths in command line arguments for years, without anyone noticing. I used to feel much stronger before that. I will be convinced to switch to team utf8-only once that is enforced by popular file systems!
I wonder why NonEmpty is defined like that, with the head element stored separately from the rest of the vec. It means you have to reallocate + copy the entire vec in the constructor and you can't take a slice of all the elements. It also inflates the size of NonEmpty.
It would be good enough to assert the non-emptiness of the underlying vec in the constructor and retain the vec as-is. It would also simplify the implementation considerably, especially sort which does an extra binary search and two O(n) operations after the actual sort.
The original "Parse, don't validate" was written in Haskell. The type of NonEmpty was data NonEmpty a = a :| [a]. The Haskell list type is a linked list, so converting from a NonEmpty a -> [a] would just be cons'ing the head to the rest of the list, a trivial operation. This was lost in the translation from Haskell to Rust and from linked lists to vectors
I don't believe that it's all that important that the original was written in Haskell or that the representation of NonEmpty was based off of linked-lists, because the original piece was not concerned with performance, rather correctness. However, in its translation to Rust it does feel a bit less idiomatic.
The whole idea is "make invalid state impossible to represent". The head element cannot be empty, therefore constructing the type is enough to prove the collection is non empty.
Doing it your way is possible but requires the programmer who implemented it to have done so in a bug free way.
It means you have to reallocate + copy the entire vec in the constructor
IIRC the compilation process can optimize away some of that. Depending on how it is used.
It would be interesting to see a comparison to see the real world differences. Also there might be implementations with more efficient implementations out there.
Yes, but that could still be done at construction time. The signature of new is already new(t: T), so you can only construct with one element. It already makes states irrepresentable by expressing them in your API (which new does here).
It's also a little bit odd that the library does have a from_vec function that does construct a NonEmpty out of a vector. It may fail (because the vector can be empty), but if it doesn't, it's expensive: In that case, it removes the head from the vector, leading to the tail being copied left in memory - that operation can't be avoided.
The whole game of that type is already that the internal vector needs to be hidden, so why not just have it work as an assertion?
It is however a very cheap type if there is a high chance that your collection only holds one element, but there could be more. But that's not NonEmpty, that's something else.
The signature of new is already new(t: T), so you can only construct with one element. It already makes states irrepresentable by expressing them in your API (which new does here).
This would follow "Parse, Don't Validate" in that "information is preserved" of the value's validity by the fact of its having been constructed, but — although I prefer your design of the type — it does not follow "Making illegal states unrepresentable", a different principle that relies on the structure of the type, as this article's NonEmpty does, rather than on a validating constructor function as PDV does.
But the illegal state is now unrepresentable from the consumer's perspective - there is no way of constructing the assertion-based NonEmpty with an empty vec, therefore the illegal state cannot be represented in their software.
Sure, they have to rely on the correctness of the underlying abstraction, but that's broadly true of any abstraction, including raw ADTs.
MISU is a higher, stricter level of relying on the type system to ensure value validity than PDV. I find PDV more practical and preferable, generally, but I think we might as well keep the two terms distinct.
I think here we run into issues of definition, and given there's no clear, rigorous definition of the two principles (there's a handful of blog posts, but even those tend to use slightly different descriptions and examples), I think there's not much value in being too precise here.
For me, the interesting question is one of encapsulation. Let's say I define an API NonEmpty that represents exclusively a non-empty list with no possibility to construct an empty NonEmpty value or to bypass the API in any way. Let's say we're using Rust's visibility system, so there is really no way for the consumer of this API to see what the underlying data looks like. Given this, is the underlying memory layout important for the encapsulation? That is, as a consumer, does it matter whether the internals of this module use ADTs or merely prevents construction of invalid values at runtime?
I think it doesn't matter. Assuming there is no observable difference, then the downstream consumer can now accurately make some set of illegal states unrepresentable. Which seems sufficiently useful to me.
I like that paradigm in general, but I think it's not more valuable than all other goals. Concerns about performance, API design or, in this case, both can make it a good tradeoff to choose a representation that allows some invalid states.
I think it's similar to database normalization: It's generally a good idea, but you can consciously make a choice to denormalize specific things as an optimization.
Another example is Vec itself: It is internally represented as pointer, length and capacity. length > capacity is always invalid, so one could argue it would be better to store pointer, length and "spare capacity" (=capacity - length) instead. But the representation is the way it is for reasons of simplicity and performance. There is some risk of bugs, but there are other things you can do to prevent those, up to and including formal verification.
I like that paradigm in general, but I think it's not more valuable than all other goals. Concerns about performance
My position here is: if it's worth optimizing it is worth benchmarking (and searching for alternative implementations). I did a lot of perf work in Ruby and a major pet peeve of mine is someone doing a drive by "but X is faster" and not bothering to bench it. Which is what I suggested earlier.
I agree abstractly "design might not justify a performance tradeoff" but you CAN quantify the perf tradeoff. And that's the zeroth step of making something faster. Skipping this step means chasing perf that isn't there (sometimes). Or wasting time micro optimizing something that is fast enough for a given use case.
When it is worth it: it is VERY satisfying to be able to quantify exactly how much.
There is some risk of bugs, but there are other things you can do to prevent those, up to and including formal verification.
It's all about costs and benefits. Formal verification is costly. I'm getting a signal from multiple commenters "it is worth doing" yet it isn't worth benchmarking (as they aren't doing it).
Details and context matters. If the use case is calling first() in a hot loop but only constructing once it could be faster than a naive vec only implementation.
I trust it is faster, but want verification and quantization as well before talking tradeoffs.
I'm also talking to myself here as I am new to optimizing rust code and I don't have a strong sense of what the compiler will or won't do. cc @skade
I generally agree, but i think this is making the case for the simpler implementation in posix-utils that I linked above. The NonEmpty-Implementation presented in the post is overly convoluted for proving non-emptyness and has unintuitive characteristics. The implemention in posix-utils behaves like vec.
However, formal verification of those properties is easy. Use types :).
This is indeed the posix-util implementation, shortened. Note it doesn't do the NonZero thing on len, which one could call a missed opportunity, but also, NonZeroUsize is a bit unwieldy to use.
Is quite literally a implementation that mostly uses the type system to:
Prove the vector is constructed with 1 element at minimum
Never gets emptied
Uses that information to actually allow the first item to be accessed without a returned Option
Of course it has a hole in the sense that we're not proving the absence of an operation that empties the vector,
Now, on optimisation: We can see a very obvious optimisation point. (the unwrap in "first"). If the compiler can follow that there's definitely an item there, it can remove the bounds check (the "unwrap" here).
This reasoning is actually harder than in the NonEmpty type presented in the blog post: there, the head is a field that is definitely always there.
struct NonEmpty<T> {
head: T,
tail: Vec<T>,
}
However, the cost is definitely that just by reading the type (again) is that T and Vec<T> are in different allocations (the Rust vector is very straight forward there - if it allocates, it allocates on the heap). NonEmpty though can he moved independently. So the first element must always be in a different allocation than the Vector, most likely on the stack. Very unlikely that there will be any optimisation of the compiler going on. Again, because all of these things can be read out of the types.
So while I agree with your philosophy that this probably doesn't matter if you don't bother measuring - there's a lot you can already conclude just by reading the types.
I agree abstractly "design might not justify a performance tradeoff" but you CAN quantify the perf tradeoff. And that's the zeroth step of making something faster. Skipping this step means chasing perf that isn't there (sometimes). Or wasting time micro optimizing something that is fast enough for a given use case.
*nod* For Rust projects where I want them to be faster, my strategy is:
Run a release-mode build against a representative data corpus (ideally the production corpus) using cargo flamegraph
Poke around the resulting flamegraph until I find something that looks like the lowest hanging fruit relative to the anticipated speed-up
Make the change and verify using hyperfine before and after the change
Repeat until program becomes fast enough or I run out of things I know how to optimize without hurting maintainability too much
(eg. I have a chatlog parser I've been meaning to finish writing the unified data representation for, where I did that to optimize the individual format parsers against the entire corpus they're meant to parse, with the intent being that I can re-parse the entire corpus in under 300ms on an Athlon II X2 270 from 2011... which was the last pre-SSE4.2/AVX generation of those.)
The whole idea is "make invalid state impossible to represent". The head element cannot be empty, therefore constructing the type is enough to prove the collection is non empty.
Doing it your way is possible but requires the programmer who implemented it to have done so in a bug free way.
It means you have to reallocate + copy the entire vec in the constructor
IIRC the compilation process can optimize away some of that. Depending on how it is used.
It would be interesting to see a comparison to see the real world differences. Also there might be implementations with more efficient implementations out there.
It's nice, but I always wish that Rust had a mechanism to designate any single value of a type as the niche in a purely mechanical way.
The niche value for e.g. NonZero<u64> is 0, so Option<NonZero<u64>> is actually the same size as u64, with Nothing using the niche 0's bit pattern. I'd love to be able to designate any one specific bitpattern of any type T as the niche and generate my own NotThisOneValue<T> on the fly, with the same optimization available as for NonZero.
While we're at it: Types can have way more than one niche. bool has 254, for starters. Option<Option<Option<bool>>> is still just one byte in size. I'd love to have this sort of thing in a user-controlled way.
You can imagine some pretty funny stuff, like declaring the return type for Linux syscalls to be Result<NonNegative<i32>, Negative<i32>> and then it's still just 4 bytes but works with ?.
Last time I looked, that was how NonZero was implemented internally. There was an API-unstable #[rustc_layout_scalar_valid_range_start(1)] hanging off its definition and it's implemented that way because, as it was explained to me, rustc is smart enough to coalesce niches so that things like Result<Option<Option<Foo>>, Option<E>> can stuff all the discriminants into a single value.
That is correct, though the definition has actually been updated to use the (not-yet-stable) feature which ekuber's sibling comment alludes to.
For example, the new definition for NonZeroU32 is morally equivalent to struct NonZeroU32(u32 is 1..), where u32 is 1.. means the type of u32s which match the pattern 1... And the compiler has already been taught that such an integer pattern type has a niche.
The general syntax is <type> is <pattern> and is called pattern types.
I mean dependent types let you construct much richer types and so you can apply the pattern in more places, but "parse don't validate" is a design philosophy not a typesystem feature so it's applicable in any language really.
The thing is in dependent type languages the line between parsing and validation is pretty blurred. Because validating something gives you a proof of that thing which you can carry directly into the type.
In other words it would looks like you are doing validation, but because you can use the validation to refine the type, it counts a parsing.
To help illustrate this point, I can give an example in Lean 4.
The type of indices for some list xs : List α is Fin xs.length, which is the type of numbers in the range 0, 1, 2, ..., xs.length - 1. But Fin xs.length is literally represented as a pair of some natural number i : Nat and a proof of i < xs.length (which looks like a validation).
Then, when you have an unknown k : Nat and do a "validation" like k < xs.length, Lean 4 gives you the proof back:
if h : k < xs.length
then ... -- Validation succeeded, now I can construct an element `Fin.mk k h` which is a "parsed" number and a valid index for `xs`.
else ... -- Validation/parsing failed.
NB Lean 4 has a number of conveniences for list indexing, it's not all this fiddly to use in practice.
Languages without dependent types can get a similar effect with what the Haskell community calls "smart constructors", but to me it feels different when you can do the validation externally (if h : k < xs.length) and then pass along proof that you did.
I have trouble implementing it in dynamically typed languages. Given user input, I go through and extract what I will need downstream, throwing errors as I detect them. Then, I use those values without having to validate them again later on.
But this is only safe until I make a future change in the parsing code. At that point, I have to run the code end-to-end (through all its branches) to be sure downstream code works ok. Other than unit tests, I haven't found a way to get the structural safety given by the type system described in the Parse, Don't Validate article.
So perhaps it is applicable in any language, but it sure feels like I'm missing out on a lot of the benefits.
There are dynamically typed languages that let you define an interface that doesn't expose the internals.
That's all you need to implement a parser, where the parsed value can't have been constructed outside of the parser.
But this is only safe until I make a future change in the parsing code.
If downstream code depends on details of the parsed object that the interface didn't guarantee, this signals a bug in the data type (or it's docs) or the consumer, regardless of whether validation or parsing was used. That can happen in Haskell too, for example you could have code that diverges (infinite recursion) when given certain values that are perfectly valid according to the type system.
Here's a section of the REPO_INVARIANTS I provide to agents and other folks working in shared repositories:
| ENG-004 | Fail loudly with actionable context at the source; do not add silent `except` blocks or swallowed `Result` values. | Review |
| ENG-005 | Distinguish recoverable domain errors (return typed error values) from invariant violations (assert and crash with diagnostics). | Review |
| ENG-006 | Parse external data into typed containers at the system boundary; validate once on the way in and trust the types inside. | Review |
| ENG-007 | Keep retained state immutable; store snapshots in fields, module- and class-level bindings, closures, and caches, never aliased mutable objects. | Review |
| ENG-008 | Keep business logic in pure, deterministic functions; confine I/O, logging, and state mutation to a thin imperative shell. | Review |
| ENG-009 | Model data so illegal states are unrepresentable; dispatch over closed sum types exhaustively with no silent catch-all. | Review |
| ENG-010 | Wrap third-party dependencies behind domain-specific interfaces rather than threading their APIs through the codebase. | Review |
Yes, I was thinking about how to do this with dependent types. There's the classic "vector with attached length" type, but you want the get_configuration_directories function to be able to return vectors of arbitrary (non-zero) length.
So maybe you'd return a vector and a function (len(v) = 0) -> !, i.e. a guarantee that it is unreachable to construct a witness to (len(v) = 0). And then the return type of first(v) looks like Result<T, (len(v) = 0)>, so if you get the Err case, you can then plug the witness into the returned guarantee function to eliminate the empty branch.
ssokolow | 21 hours ago
Well, I'm glad it's only
rust-analyzer. As an amateur archivist and "someone with a collection, but not a collector", my filesystem contains various mojibake'd filenames I haven't had time to find the correct iconv conversion for (and corrupted dates from old DOS disks that somehow got their metadata corrupted while the files still pass validation) and I really don't like it when tools die because they can't handle valid-under-POSIX paths.foonathan | 15 hours ago
It's presumably the fault of the language server protocol which sends our paths as URIs in JSON. So you need some way to encode mojibake in a valid UTF-8 string.
matklad | 9 hours ago
Sort-of. By design, rust-analyzer isn't an LSP server. It is a library, which exposes structured API. LSP is just one way to "serialize" the results, so nothing LSP specific should leak into rust-analyzer proper. If LSP can't represent something, it's LSP's problem!
But where JSON leaks in a more fundamental way is that the interface to the build system,
cargo metadata, orrust-project.json, is JSON based. I think we still could do the pedantically correct thing there (and we used to!), but if upstreamcargo-metadatauses utf8 paths, that's not necessarily the most important windmill to die on.ssokolow | 15 hours ago
I forget what it was called, but there is such an encoding that I ran across recently.
I'd already been doing my own mojibake-encoding for storing them in JSON by taking advantage of the fact that
\0(NUL) is defined as valid in JSON strings by the JSON spec, but not in POSIX paths, to use it as an escape character meaning "the following codepoint in the range 0 to 255 should be interpreted as a raw byte".(I initially tested something like a dozen JSON implementations in a bunch of (admittedly non-C) languages and the only one I found that didn't handle nulls in strings properly was PHPs... and I think they've fixed that since then.)
That way, the encoding of all previously allowed paths remains unchanged. Full backwards compatibility.
dutchie | 9 hours ago
I see you've found it in the other thread, but Raku (aka Perl 6) has their own solution using "NFG synthetics" to handle non-UTF-8-compatible byte-sequences, which you may also find interesting
https://docs.raku.org/language/unicode#UTF8-C8
foonathan | 14 hours ago
Sure, but AFAIK the lsp server (i.e. Rust analyzer) just receives paths from the lsp client (i.e. the text editor). So the server only has to deal with UTF-8 paths.
ssokolow | 11 hours ago
Fair point. No matter what the scheme, you can only communicate what both sides agree on how to represent.
mxey | 12 hours ago
WTF-8?
muvlon | 11 hours ago
WTF-8 is UTF-8 plus the ability to encode unpaired surrogates. That's useful if you'd really like to work with UTF-8 but you can't because you have to handle input that's potentially truncated UTF-16 (or UCS-2).
It won't help you here because WTF-8, being a superset, is not generally valid UTF-8 and so can't be used in conforming JSON strings.
ssokolow | 11 hours ago
No, that's a variation on UTF-8. I'm talking about a scheme that operated at a layer of abstraction more akin to percent encoding or base64 and was described, either explicitly or by the focus of its example uses, as being for allowing non-UTF8 bytes to be stored/transmitted in UTF-8-only channels.
...and I'm having a helluva time finding it again. All I remember is that, some time within the last couple of months, I ran into it being mentioned by acronym and hyperlinked in a spec or proposal for implementing something else, and that I had a "Huh. So someone already did it." moment because it struck me as one of those "Well-known, and made by someone much more important than me, but I'd never known about it" things like BSON or base85.
(And I apparently didn't do a good enough job of adding extra keywords for words I might think of it by when bookmarking it.)
EDIT: Found it. I was thinking of the bytecode alliance's "ARF strings" (ARF being short for "Alternative Representation for Filenames") and my browser history says I encountered it on 2026-07-14. (I do still intend to go with my solution since you need
\0either way but, with my scheme, paths which are UTF-8-clean pass through the encode/decode stage unchanged.)matklad | 10 hours ago
For posterity, I am personally not a huge fan of cargo&rust-analyzer going with utf-8 paths: https://github.com/oli-obk/cargo_metadata/pull/152#issuecomment-788111817
rust-analyzer used to be pretty pedantic in distinguishing "makefile" path, as written in the source code (which must be utf8) from the OS path where the root of the project is located. We use
at-style representation where every path (even an absolute!) is anchored to the context where that path makes sense. I think we dropped non-utf8 parts after cargo?I don't think it's a big mistake either way (though I consider utf8-only paths to be a mistake for systems software). My mind on this topic changed significantly after I learned that cargo was panicking on non-utf8 paths in command line arguments for years, without anyone noticing. I used to feel much stronger before that. I will be convinced to switch to team utf8-only once that is enforced by popular file systems!
madsmtm | 4 hours ago
It's enforced by APFS iirc, which I guess falls under the umbrella of "popular file system" (though not really useful on non-macOS).
hailey | 17 hours ago
I wonder why NonEmpty is defined like that, with the head element stored separately from the rest of the vec. It means you have to reallocate + copy the entire vec in the constructor and you can't take a slice of all the elements. It also inflates the size of NonEmpty.
It would be good enough to assert the non-emptiness of the underlying vec in the constructor and retain the vec as-is. It would also simplify the implementation considerably, especially
sortwhich does an extra binary search and two O(n) operations after the actual sort.nickgirardo | 5 hours ago
The original "Parse, don't validate" was written in Haskell. The type of
NonEmptywasdata NonEmpty a = a :| [a]. The Haskell list type is a linked list, so converting from aNonEmpty a -> [a]would just be cons'ing the head to the rest of the list, a trivial operation. This was lost in the translation from Haskell to Rust and from linked lists to vectorsI don't believe that it's all that important that the original was written in Haskell or that the representation of
NonEmptywas based off of linked-lists, because the original piece was not concerned with performance, rather correctness. However, in its translation to Rust it does feel a bit less idiomatic.schneems | 16 hours ago
The whole idea is "make invalid state impossible to represent". The head element cannot be empty, therefore constructing the type is enough to prove the collection is non empty.
Doing it your way is possible but requires the programmer who implemented it to have done so in a bug free way.
IIRC the compilation process can optimize away some of that. Depending on how it is used.
It would be interesting to see a comparison to see the real world differences. Also there might be implementations with more efficient implementations out there.
skade | 11 hours ago
Yes, but that could still be done at construction time. The signature of new is already
new(t: T), so you can only construct with one element. It already makes states irrepresentable by expressing them in your API (whichnewdoes here).It's also a little bit odd that the library does have a from_vec function that does construct a NonEmpty out of a vector. It may fail (because the vector can be empty), but if it doesn't, it's expensive: In that case, it removes the head from the vector, leading to the tail being copied left in memory - that operation can't be avoided.
The whole game of that type is already that the internal vector needs to be hidden, so why not just have it work as an assertion?
It is however a very cheap type if there is a high chance that your collection only holds one element, but there could be more. But that's not
NonEmpty, that's something else.Indeed, the linked posix-util implements NonEmpty without the head stored seperately.
For that reason, it forwards all vec methods except pop, which has weird semantics in the NonEmpty crate (pop stops early...).
5d22b | 4 hours ago
This would follow "Parse, Don't Validate" in that "information is preserved" of the value's validity by the fact of its having been constructed, but — although I prefer your design of the type — it does not follow "Making illegal states unrepresentable", a different principle that relies on the structure of the type, as this article's
NonEmptydoes, rather than on a validating constructor function as PDV does.Johz | 4 hours ago
But the illegal state is now unrepresentable from the consumer's perspective - there is no way of constructing the assertion-based
NonEmptywith an empty vec, therefore the illegal state cannot be represented in their software.Sure, they have to rely on the correctness of the underlying abstraction, but that's broadly true of any abstraction, including raw ADTs.
5d22b | an hour ago
MISU is a higher, stricter level of relying on the type system to ensure value validity than PDV. I find PDV more practical and preferable, generally, but I think we might as well keep the two terms distinct.
Johz | 59 minutes ago
I think here we run into issues of definition, and given there's no clear, rigorous definition of the two principles (there's a handful of blog posts, but even those tend to use slightly different descriptions and examples), I think there's not much value in being too precise here.
For me, the interesting question is one of encapsulation. Let's say I define an API
NonEmptythat represents exclusively a non-empty list with no possibility to construct an emptyNonEmptyvalue or to bypass the API in any way. Let's say we're using Rust's visibility system, so there is really no way for the consumer of this API to see what the underlying data looks like. Given this, is the underlying memory layout important for the encapsulation? That is, as a consumer, does it matter whether the internals of this module use ADTs or merely prevents construction of invalid values at runtime?I think it doesn't matter. Assuming there is no observable difference, then the downstream consumer can now accurately make some set of illegal states unrepresentable. Which seems sufficiently useful to me.
muvlon | 11 hours ago
I like that paradigm in general, but I think it's not more valuable than all other goals. Concerns about performance, API design or, in this case, both can make it a good tradeoff to choose a representation that allows some invalid states.
I think it's similar to database normalization: It's generally a good idea, but you can consciously make a choice to denormalize specific things as an optimization.
Another example is
Vecitself: It is internally represented as pointer, length and capacity. length > capacity is always invalid, so one could argue it would be better to store pointer, length and "spare capacity" (=capacity - length) instead. But the representation is the way it is for reasons of simplicity and performance. There is some risk of bugs, but there are other things you can do to prevent those, up to and including formal verification.schneems | 8 hours ago
My position here is: if it's worth optimizing it is worth benchmarking (and searching for alternative implementations). I did a lot of perf work in Ruby and a major pet peeve of mine is someone doing a drive by "but X is faster" and not bothering to bench it. Which is what I suggested earlier.
I agree abstractly "design might not justify a performance tradeoff" but you CAN quantify the perf tradeoff. And that's the zeroth step of making something faster. Skipping this step means chasing perf that isn't there (sometimes). Or wasting time micro optimizing something that is fast enough for a given use case.
When it is worth it: it is VERY satisfying to be able to quantify exactly how much.
It's all about costs and benefits. Formal verification is costly. I'm getting a signal from multiple commenters "it is worth doing" yet it isn't worth benchmarking (as they aren't doing it).
Details and context matters. If the use case is calling first() in a hot loop but only constructing once it could be faster than a naive vec only implementation.
I trust it is faster, but want verification and quantization as well before talking tradeoffs.
I'm also talking to myself here as I am new to optimizing rust code and I don't have a strong sense of what the compiler will or won't do. cc @skade
skade | 7 hours ago
I generally agree, but i think this is making the case for the simpler implementation in posix-utils that I linked above. The NonEmpty-Implementation presented in the post is overly convoluted for proving non-emptyness and has unintuitive characteristics. The implemention in posix-utils behaves like vec.
However, formal verification of those properties is easy. Use types :).
This is indeed the posix-util implementation, shortened. Note it doesn't do the NonZero thing on len, which one could call a missed opportunity, but also, NonZeroUsize is a bit unwieldy to use.
Is quite literally a implementation that mostly uses the type system to:
OptionNow, on optimisation: We can see a very obvious optimisation point. (the unwrap in "first"). If the compiler can follow that there's definitely an item there, it can remove the bounds check (the "unwrap" here).
This reasoning is actually harder than in the NonEmpty type presented in the blog post: there, the head is a field that is definitely always there.
However, the cost is definitely that just by reading the type (again) is that T and Vec<T> are in different allocations (the Rust vector is very straight forward there - if it allocates, it allocates on the heap). NonEmpty though can he moved independently. So the first element must always be in a different allocation than the Vector, most likely on the stack. Very unlikely that there will be any optimisation of the compiler going on. Again, because all of these things can be read out of the types.
So while I agree with your philosophy that this probably doesn't matter if you don't bother measuring - there's a lot you can already conclude just by reading the types.
ssokolow | 7 hours ago
*nod* For Rust projects where I want them to be faster, my strategy is:
cargo flamegraph(eg. I have a chatlog parser I've been meaning to finish writing the unified data representation for, where I did that to optimize the individual format parsers against the entire corpus they're meant to parse, with the intent being that I can re-parse the entire corpus in under 300ms on an Athlon II X2 270 from 2011... which was the last pre-SSE4.2/AVX generation of those.)
It's a pretty comfortable way to do it.
hyperpape | an hour ago
Doesn’t this trade one invalid state for a different one, where length + spare_capacity overflows?
schneems | 16 hours ago
The whole idea is "make invalid state impossible to represent". The head element cannot be empty, therefore constructing the type is enough to prove the collection is non empty.
Doing it your way is possible but requires the programmer who implemented it to have done so in a bug free way.
IIRC the compilation process can optimize away some of that. Depending on how it is used.
It would be interesting to see a comparison to see the real world differences. Also there might be implementations with more efficient implementations out there.
orgnizedmess | 11 hours ago
TIL
NonZero, I have a few fields in my project that could benefit from it!gspr | 7 hours ago
It's nice, but I always wish that Rust had a mechanism to designate any single value of a type as the niche in a purely mechanical way.
The niche value for e.g. NonZero<u64> is 0, so Option<NonZero<u64>> is actually the same size as u64, with Nothing using the niche 0's bit pattern. I'd love to be able to designate any one specific bitpattern of any type T as the niche and generate my own NotThisOneValue<T> on the fly, with the same optimization available as for NonZero.
muvlon | 4 hours ago
While we're at it: Types can have way more than one niche.
boolhas 254, for starters.Option<Option<Option<bool>>>is still just one byte in size. I'd love to have this sort of thing in a user-controlled way.You can imagine some pretty funny stuff, like declaring the return type for Linux syscalls to be
Result<NonNegative<i32>, Negative<i32>>and then it's still just 4 bytes but works with?.ekuber | 7 hours ago
People are working on it. It will take a while to land on stable, but it is on peoples radars.
gspr | 6 hours ago
Lovely to hear this! Thanks!
ssokolow | 7 hours ago
Last time I looked, that was how
NonZerowas implemented internally. There was an API-unstable#[rustc_layout_scalar_valid_range_start(1)]hanging off its definition and it's implemented that way because, as it was explained to me, rustc is smart enough to coalesce niches so that things likeResult<Option<Option<Foo>>, Option<E>>can stuff all the discriminants into a single value.tsion | 4 hours ago
That is correct, though the definition has actually been updated to use the (not-yet-stable) feature which ekuber's sibling comment alludes to.
For example, the new definition for
NonZeroU32is morally equivalent tostruct NonZeroU32(u32 is 1..), whereu32 is 1..means the type ofu32s which match the pattern1... And the compiler has already been taught that such an integer pattern type has a niche.The general syntax is
<type> is <pattern>and is called pattern types.yshui | 13 hours ago
"Parse, don't validate" is just poor man's dependent types (well, kind of. don't come after me).
dxo | 8 hours ago
I mean dependent types let you construct much richer types and so you can apply the pattern in more places, but "parse don't validate" is a design philosophy not a typesystem feature so it's applicable in any language really.
yshui | 6 hours ago
The thing is in dependent type languages the line between parsing and validation is pretty blurred. Because validating something gives you a proof of that thing which you can carry directly into the type.
In other words it would looks like you are doing validation, but because you can use the validation to refine the type, it counts a parsing.
tsion | 4 hours ago
To help illustrate this point, I can give an example in Lean 4.
The type of indices for some list
xs : List αisFin xs.length, which is the type of numbers in the range0, 1, 2, ..., xs.length - 1. ButFin xs.lengthis literally represented as a pair of some natural numberi : Natand a proof ofi < xs.length(which looks like a validation).Then, when you have an unknown
k : Natand do a "validation" likek < xs.length, Lean 4 gives you the proof back:NB Lean 4 has a number of conveniences for list indexing, it's not all this fiddly to use in practice.
Languages without dependent types can get a similar effect with what the Haskell community calls "smart constructors", but to me it feels different when you can do the validation externally (
if h : k < xs.length) and then pass along proof that you did.ryan-duve | 7 hours ago
I have trouble implementing it in dynamically typed languages. Given user input, I go through and extract what I will need downstream, throwing errors as I detect them. Then, I use those values without having to validate them again later on.
But this is only safe until I make a future change in the parsing code. At that point, I have to run the code end-to-end (through all its branches) to be sure downstream code works ok. Other than unit tests, I haven't found a way to get the structural safety given by the type system described in the Parse, Don't Validate article.
So perhaps it is applicable in any language, but it sure feels like I'm missing out on a lot of the benefits.
janus | 2 hours ago
There are dynamically typed languages that let you define an interface that doesn't expose the internals.
That's all you need to implement a parser, where the parsed value can't have been constructed outside of the parser.
If downstream code depends on details of the parsed object that the interface didn't guarantee, this signals a bug in the data type (or it's docs) or the consumer, regardless of whether validation or parsing was used. That can happen in Haskell too, for example you could have code that diverges (infinite recursion) when given certain values that are perfectly valid according to the type system.
jfb | 7 hours ago
I mean, it makes sense in Python, which is nobody's idea of a good type system.
jfb | 7 hours ago
Here's a section of the REPO_INVARIANTS I provide to agents and other folks working in shared repositories:
cyberia | 10 hours ago
Yes, I was thinking about how to do this with dependent types. There's the classic "vector with attached length" type, but you want the
get_configuration_directoriesfunction to be able to return vectors of arbitrary (non-zero) length.So maybe you'd return a vector and a function
(len(v) = 0) -> !, i.e. a guarantee that it is unreachable to construct a witness to(len(v) = 0). And then the return type offirst(v)looks likeResult<T, (len(v) = 0)>, so if you get theErrcase, you can then plug the witness into the returned guarantee function to eliminate the empty branch.