6 ms·
A byte string library for Rust
- rwmj 4y agoPlease don't design bit/byte string libraries until you understand how Erlang handles them, because that language has by far the best support. https://www.erlang.org/doc/programming_examples/bit_syntax.html https://www.erlang.org/doc/programming_examples/bit_syntax.h... Here's my OCaml library influenced heavily by Erlang: https://bitstring.software/examples/ https://bitstring.software/examples/
- brobinson 4y agoI think the author of ripgrep knows a thing or two about processing bits and bytes.
- CodesInChaos 4y agoYour links seems to use string as a synonym of sequence. The linked crate is about strings which represent text, and many of them assume that the encoding is a superset of ASCII, and some ever assume it's potentially invalid UTF-8. So I don't see how your links are relevant here.
- rwmj 4y agoIt deals with both bits and byte strings, and as it's implemented as a set of compile-time macros there's no overhead as long as the compiler can easily see that the string is byte-aligned.
- lifthrasiir 4y agoYou have solved a different problem. The OP benchmarks grep and wc as motivating examples; how does your library (and the Erlang design in general) help in such cases?
- speed_spread 4y agoIt feels like you didn't read the linked article and are only using the title to plug your lib. Without discussing the relative merits of your work, _you_ might have to learn a thing or two about self-promotion opportunities. Step 1: "understand what people are talking about before participating". Amazingly, this actually applies to all conversations.
- burntsushi 4y agoCan you say what is specifically wrong with bstr (while tying it to real world use cases) instead of trying to tell me what I do or don't understand?
- zozbot234 4y agoMuch of it has seemingly no reason for being specialized to u8, especially the needle/haystack search example that takes up much of the blogpost. Even the "replacing invalid UTF-8 with the generic replacement character" part could simply be factored out as an iterator adapter on u8's.
- burntsushi 4y agoI think that would be an interesting API design to explore, absolutely. I think you'll have a lot of issues making it fast though. There is a fair bit of SIMD going on under the hoods in both the substring routines and the UTF-8 validation routines, for example. Building APIs based around iterator adapters that munch one byte at a time are difficult to square with SIMD optimizations that want to operate on a whole bunch of bytes at a time. Consider, for example, how you might use a routine like memchr[1] if all of your public APIs are generic iterator adapters. And then once you get into things like regex engines, modifying them to work on Iterator<Item=u8> is a highly non-trivial affair. It is of course possible to write a regex engine that works on such things, but it's going to be limited in performance or capabilities. The way to make regexes and streaming work together is probably something more like Iterator<Item=&[u8]> (which is perhaps roughly analogous to what Hyperscan does). You really want blocks of bytes, not one-byte-at-a-time. [1]: https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memchr/x86/sse2.rs#L16 https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07b...
- gpm 4y agoUTF-8 by definition is a sequence of u8's, what would you like it to be generic over, and how would that help anyone!?
- gliptic 4y agoIt's specialized to &[u8] in order to supply optimized implementations.
- Dr_Emann 4y agoHonestly feels like a very, very different use case from utf8-ish strings, at a quick read?
- bsder 4y agoThis library isn't about bit packing--it's mostly about optimizing text and presumably "ripgrep" which the author is also the creator of. However, I do agree that Erlang's Bit Syntax is, by far, the best handling I've ever seen for slicing and dicing bits and bytes at the very lowest level.
- throwawaymaths 4y agoErlang's bit syntax is actually kind of broken: See if you can guess correctly what this produces: <<1:5, 2:4, 0xFFOO:15, "foo":binary>>
- rkangel 4y agoThe correct answer to this is actually "syntax error" because your `0xFFOO:15` has got two letter O's in it and anyway 0xFF00 isn't valid erlang (no hex literals). If you mean this equivalent bit of Elixir, then I got it right: <<1::5, 2::4, 0xFFOO::15, "foo"::binary>> I think it's all good and sensible, except that "0xFF00::15" should raise an error. The bit syntax silently masks out some stuff which can hide some errors.
- throwawaymaths 4y agoYeah, sorry typing on phone. Ok. Maybe I'm just dumb. But I was really surprised that the bit order goes from msbit to lsbit (while the byte order goes from lsbyte to msbyte). Since the 15 bit element crosses over the byte boundary (and overflows it) the arrangement -- 00s in byte 1 and 0x80 0x3F in bytes 2 and 3... is not obvious, to me). In particular this makes it tricky to reinterpret packed structs coming from c, when using NIFs Specifically, what I would have wanted, was lsb-msb in bytes, and an overflow error, or syntax in the descriptor modifier that is required if you might overflow. Or, this would all be solved if we used an RTL layouts like the divine one intended.
- rkangel 4y agoThe important thing to remember, it's just a sequence of bits (and if that's a multiple of 8 then you can look at it as a sequence of bytes instead). Byte boundaries are just a way of looking at the result. You get the bits in the order you ask for in the expression, and then it encodes each valuee as you ask. Note that the default encoding is big endian, so the value 0xFF00 comes out as the bit sequence 1111111100000000 wherever it is. Now converting from a C-struct you absolutely do have to think about byte order, but erlang has you there too. Let's say you've got this: #pragma pack(1) struct { uint16_t a; uint8_t b; uint8_t c; uint32_t d; }; Then all you do is: <<a::16-native, b::8, c::8, d::32-native>> = my_block_of_data And then all of your values (a, b, c, d) will be correct. As I said above, erlang defaults to encoding/decoding each value as big-endian (e.g. <<0xFF00::16>> is equivalent to <<0xFF00::16-big>>. This is the default because big endian is used for the vast majority of comms protocols (in that context it's also called 'network byte order'). When interpreting values in memory though it can be either, depending on your processor (although mostly -little these days). Using -native as yoru endianness means "use big or little as appropriate for my processor". It's also a good signal that you're interpreting something from memory (as supposed to a protocol).
- vlmutolo 4y agoI've been using this library in production to handle doing operations on domain names and it's been incredible. It's one of those things that's so easy to use it almost starts to seem simple. Like of course we need a library that looks just like this. It's obvious in hindsight, which speaks to great design. It's especially helpful that the library doesn't require you to opt into its own dedicated types, and instead defines extension methods on existing types. Thanks, Andrew!
- burntsushi 4y ago> It's especially helpful that the library doesn't require you to opt into its own dedicated types, and instead defines extension methods on existing types. Fun fact: bstr 0.1 went the route of defining its own dedicated types! See: https://docs.rs/bstr/0.1.4/bstr/ https://docs.rs/bstr/0.1.4/bstr/ But it did indeed quickly prove to be pretty annoying. Because you still really want to use &[u8] in places because it's so ubiquitous. But to get access to the byte string methods, you had to explicitly convert it to another type. The reason why I went that route initially was so you'd always get the good Debug impl. But it ended up not being worth it sadly. This issue discusses it a bit more: https://github.com/BurntSushi/bstr/issues/5 https://github.com/BurntSushi/bstr/issues/5
- epilys 4y agoThis should be in the standard library, but maybe I'm biased. In implementing ascii/utf8 plain text protocols like IMAP/SMTP just like the grep/ripgrep example in the article, I've had to limit myself to u8 slices just because the occasional byte might make a grapheme invalid.
- burntsushi 4y agoYeah people say this enough that I added a section about it to the blog: https://blog.burntsushi.net/bstr/#should-byte-strings-be-added-to-std https://blog.burntsushi.net/bstr/#should-byte-strings-be-add...
- 4y ago
- db48x 4y agoThat is exactly what I need for one of my long–neglected projects. Thank you!
- gwbas1c 4y agoI've always wanted something similar in C#. By convention, byte arrays are used for handling arbitrary blobs; but they are mutable and don't have the same kind of support that strings have. C# strings are immutable and have lots of supporting methods.
- rednab 4y agoThese days C# has Span<byte> ¹) and ReadOnlySpan<byte> ²) which has a whole bunch of string-like methods, but the version of C# it requires might be newer than you're happy with. ¹) https://docs.microsoft.com/en-us/dotnet/api/system.span-1 https://docs.microsoft.com/en-us/dotnet/api/system.span-1 ²) https://docs.microsoft.com/en-us/dotnet/api/system.readonlyspan-1 https://docs.microsoft.com/en-us/dotnet/api/system.readonlys...
- gwbas1c 4y ago> but the version of C# it requires might be newer than you're happy with Oh, that's a solvable problem. Thanks!
- jjice 4y agoBurntsushi is a serious power contributor to the Rust ecosystem. Obviously ripgrep and the regex crate are top tier. Big thank you from someone who uses your work regularly :) Also really cool to see more and more rust crates releasing their 1.0 versions. I feel like one of the big jumps for Rust (for me at least) will be when critical non-stdlib libraries are all 1.0 and there's less "which one do I choose". I understand competition is good in situations (more so opinionated frameworks) but I do love that I don't think about what regex library to choose since there's one obvious winner with tons of community support and resources.
- m12k 4y ago> I understand competition is good in situations But also, consolidation at a given layer of an ecosystem allows that layer to be treated as a foundation so the next layer on top of it can be where the competition happens instead
- bowsamic 4y agoI don't think always that's a good thing. Every ecosystem I've seen that happen in has just bred an army of lazy developers who rely on libraries for basically everything.
- xxpor 4y agoThat's not being lazy, it's being sane. Nothing's worse than screwing up something basic that should have been handled by a library. Leftpad might be on the too many libraries end, but that's an extreme example.
- bowsamic 4y agoI don't agree with the assertion that programmers should defer programming to others whenever possible
- vladvasiliu 4y ago
- Fiahil 4y ago> Should byte strings be added to std? > Some folks have expressed a desire for bstr or something like it to be put into the standard library. I’m not sure how I feel about wholesale adopting bstr as it is. bstr is somewhat opinionated in that it provides several Unicode operations (like grapheme, word and sentence segmentation), for example, that std has deliberately chosen to leave to the crate ecosystem. Yes, ok, but could we -at least- have the same Debug impl bstr has ? I'd love to be able to print "human-readable" Vec<u8> :')
- burntsushi 4y agoThat's what the very next paragraph addresses haha. So the Debug impl for Vec<u8> is just the Debug impl for Vec<T>. Doing otherwise means specializing for Vec<u8>, and it's not totally clear to me that it makes sense to do that. Doing it effectively requires assuming that a Vec<u8> everywhere is UTF-8 or close to it. I do mention that we could add a '[u8]::debug_utf8()' method that returns a type with a nice Debug impl for byte strings. Kind of like how we have 'Path::display()', but for the Display impl. But that is kind of annoying in a way that doesn't really apply to Display impls. It's very common to derive(Debug), and if the debug impl is only accessible via a method, then derive(Debug) doesn't work. So then you have to write your Debug impl by hand, which is... annoying. Anyway, point is, it's just not totally straight-forward to bring bstr into std. As I said in the blog, I think the highest value thing that could be brought into std is substring search that works on &[u8].
- dhosek 4y agoI’ve toyed with seeing about adding a feature to finl_unicode to extend or replace the bstr implementations of segmentation, etc. but I don’t need it so I probably won’t. You’re welcome to steal my code though. (And hi from reddit-land!)
- fanf2 4y agoI am curious how bstr relates to OsString. Is the difference that OsString can be WTF16 on Windows?
- chungy 4y agoOne thing I noticed in the middle, when concatenating Rust files for a demonstration: > Note also that the files are sorted before concatenating, so that the result is guaranteed to be deterministic. No locale was defined and the example sort command used cannot be considered deterministic. The results could vary wildly on different systems just through the locale alone! Two solutions: define the locale ("LC_ALL=C" before the command should be sufficient), or use the -V flag on sort.
- burntsushi 4y agoOoo, nice catch! Fixed: https://github.com/BurntSushi/blog/commit/a1b0e40cbfd293310b9c2aef0426b8e5cd32b7ca https://github.com/BurntSushi/blog/commit/a1b0e40cbfd293310b...
- chungy 4y agoAwesome :)
- Xeoncross 4y agoIf you haven't read https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ yet, then IDK what you're doing with your life.
- baq 4y agoas usual a reminder that ripgrep is the grep tool. if you're using vscode's Find in Files, you're using ripgrep.