I'm a fairly inexperienced Rust programmer and have definitely felt your pain, particularly with regard to lifetimes being lexical. And just now I tried to implement a solution to this using entry(...).or_insert_with which doesn't compose with error handling. Definitely lots of sharp edges that I hope this year's rust roadmap will address.

On the bright side it is possible to implement a pretty elegant solution to this particular problem:

#![feature(lookup_host)]

use std::collections::HashMap;
use std::collections::hash_map::Entry;
use std::io::Result;
use std::net::SocketAddr;

#[derive(Debug)]
struct DnsLookupCache {
    cache: HashMap<String, Vec<SocketAddr>>,
}

impl DnsLookupCache {
    fn new() -> DnsLookupCache {
        DnsLookupCache {
            cache: HashMap::new(),
        }
    }

    fn lookup(&mut self, host: &str) -> Result<&Vec<SocketAddr>> {
        match self.cache.entry(host.to_owned()) {
            Entry::Occupied(e) => Ok(e.into_mut()),
            Entry::Vacant(e)   => Ok(e.insert(do_lookup(host)?))
        }
    }
}

fn do_lookup(host: &str) -> Result<Vec<SocketAddr>> {
    Ok(std::net::lookup_host(host)?.collect())
}

It won’t compile, because we have both immutable borrow (on line 17) and a mutable one (on line 25 & 26).

This is a pretty well known annoyance, and your frustration with it is pretty well warranted. The borrow checker should understand that in line 25 the borrow is unaccessible, but it just can't reason about the code so well just yet. This is more due to the execution of the borrow checker, than it is due to it's design. There is a lot of perfectly valid cases that the borrow checker rejects because it can't reason about the code well enough, but the work on that is, as far as I know, underway.

A workaround is to just do a boolean check without storing any references:

    fn lookup(&mut self, host: &str) -> std::io::Result<&Vec<SocketAddr>> {
        if self.cache.get(host).is_none() {
            let hosts = std::net::lookup_host(host)?.collect();
            
            self.cache.insert(host.to_owned(), hosts);
        }
        
        Ok(self.cache.get(host).expect("Must have a value now"))
    }

This is suboptimal since you always do a lookup twice, even on cache hit. There are other ways around it using hash_map.entry(key).or_insert_with(func) for this particular case, but they have other drawbacks (key has to be an owned String, can't return io errors from within closures).

Random notes:

• Using .collect() to get a vector out of an iterator is shorter, easier and more idiomatic (and potentially faster since the iterator can figure out how big of a vector to allocate).
• String is already heap allocated, no need for Box<String>, it just creates an extra layer of indirection.
• It's preferable to use &str in function signatures when taking references to strings. &String will automagically turn into &str in that case, and should the caller only have &str to begin with, they don't have to allocate an intermediate String to get a reference to it.

TLDR: Probably wait till borrow checker matures and try again.

"mutate the buffer in multiple places at the same time" --> Rust won't let you unless you use some concurrecy technique. channel, mutex, or single mutable ref

On Windows Rust is debuggable in Visual Studio, on other platforms you can use GDB or LLDB. VS cannot properly display all types but it is better then nothing.

@Oren Eini: Could you show us the the full source of your trie implementation, please? That would allow the community to help with the particular problems.

I've enjoyed reading about your experiments with Rust. I've toyed with D language a bit and would love to see you try it and blog your experience with it in a similar experiment. (dlang.org) -- I'm not affiliated with it in any way. Just a curious observer. Thanks.

I haven't really started playing with Rust yet, but isn't your requirement to write to the buffer in multiple locations exactly what "unsafe" is for? Rust is supposed to give you a lot of protection from accidentally mutating code in multiple places, but "unsafe" Rust lets you ignore those constraints when they don't make sense.

I think that Rust want you to create an interface for this, and then you can use unsafe from behind the scenes to operate directly on memory. Trying to change a memory buffer seems like an good fit for unsafe :-).

Hi!

A small correction: you can build/run the Rust project in IntelliJ Rust, you need to create a run configuration manually, or use contextual Ctrl+Shift+F10 shortcut. The UI about make project and SDKs is mightily confusing at the moment, because these are specifics of Java language support, which we don't use in the plugin.

This is explained more thoroughly in the docs and FAQ.

We don't have a debugger support yet though :)

Surprised you didn't mention Atom + Tokamak. It has, by far, the best experience as a Rust IDE. It has much superior editing, linting, and support for sub-second clippy linting in ways that VS Code cannot compare, although it doesn't feature intellisense support in autocompletion. It's much easier to set up than VS Code, and the multi-cursor support works a lot better.

Also, the phrase "fighting the borrow checker" is a little harsh. It's more accurate to say that you're just learning to dance with the borrow checker. It's a temporary phase that lasts about a week, and at most two weeks, especially if you're trying to do something this complex right off the bat. You can write your software in a way that avoids the need to get two mutable borrows at the same time. I don't have your full source code so I can't show you how for that scenario though.

You are doing a number of odd things with your code though, such as boxing a String, which is pointless because a String is just an alias for a Vec<u8>, which is already boxed. Boxing a String just turns it into box of a box of bytes. It's also odd to take an &String as an input parameter instead of an &str because an &String is basically a reference to a reference of values, basically you're doing &String(Vec<u8>) instead of &[u8] as you get with an &str. Clippy should warn about this and many other issues in your source code that aren't idiomatic, so I'd highly recommend developing with Clippy as your linter of choice.

This is something you should ask for help with, and it would be even better if you provide the full source code to your issue in the first screenshot. I'm sure we can find out what's going wrong with the way you're structuring the code. You should never have two mutable borrows to the same object.

You still get code completion suggestions provided by racer without intellisense. Intellisense just makes it easier to complete by typing shortcuts instead of needing to match from left right. I'd take the lack of intellisense over the severe lack of editing capabilities in VS Code any day though. IE: copying a block of code from one indent to another completely breaks formatting in VS Code, but Atom automatically corrects the indents so it's perfect when you paste.

As for multi-cursor, you'll start using it once you know what it is. It is one of the things that makes me highly productive when programming. There are two ways that you can create multiple cursors. The first is by holding Ctrl and using the up and down keys to duplicate your cursor. When you start typing, or deleting, each cursor will apply the same action. The second way to create them is to highly a section of text and press Ctrl + D to highlight the next occurrence. Each time you press Ctrl + D, another cursor will be created with the next occurrence highlighting. You can then modify all regions at the same time.

The problem I have with VS Code's implementation of multi-cursor editing is that it isn't case-sensitive, which is complete nonsense for a code editor. If you highlight a word typed as string and press Ctrl + D a few times, chances are that it will also highlight occurrences of String. I've no idea why Microsoft chose that behavior.

As for Clippy, clippy is the name of a tool written in Rust for extending the available lints that Rust has to offer. Because it's basically a compiler plugin, you need to use a nightly compiler to compile/install it. Although it's pretty easy to install with Cargo.

cargo +nightly install clippy

A list of lints provided by Clippy can be found here. You will need to tell your IDE to use clippy for linting though in order to use it. If you've looked at the lint settings, you may have seen a clippy option before. Any time you update your nightly version of Rust, you'll need to remember to update Clippy too, at least until Clippy starts getting shipped as a component via Rustup.

I'll look at the code later.

My mistake, it's Alt + Shift + Up/Down, not Ctrl.

Just taking a quick peek at some of your C++ code, I notice the use of "stdext::make_checked_array_iterator()", which I'll take as an indicator that you're considering memory safety to be important here. You may want to consider using SaferCPlusPlus¹. It allows you to achieve a more complete degree of safety by replacing potentially unsafe C/C++ elements (esp. pointers and arrays) with fast, compatible memory safe substitutes.

For example, instead of

char _buffer[BUFFER_SIZE];

in modern C++ you might prefer

std::array<char, BUFFER_SIZE> _buffer;

And SaferCPlusPlus provides a compatible, memory safe version of std::array<>

mse::mstd::array<char, BUFFER_SIZE> _buffer;

This array, for example, is not just bounds checked, but its iterators catch "use-after-free" bugs as well.

SaferCPlusPlus may be a good alternative if you're looking for memory safety sans GC, but you'd rather not deal with the Rust borrow checker.

Rust lets you have multiple mutable references. Check out Cell and RefCell: http://manishearth.github.io/blog/2015/05/27/wrapper-types-in-rust-choosing-your-guarantees/ or if you're comfortable, feel free to use UnsafeCell.

I also struggled for a long time, fighting the compiler. I haven't found a resource that serves as the Rust equivalent of "Functional Programming in Scala" where it ends a high-attrition compiler-war with a deep dive and set of exercises. Anyone know of one?

Yeah, I think Visual Studio's security checks have always been problematic in that way. Their recommended "safe" elements are often non-portable and either unnecessary where you're not concerned about the safety issue, or inadequate where you are.

Imo safety is a big part of Rust's value proposition. When safety is not a concern, a lot of Rust's inconveniences can seem kind of pointless. When (memory) safety is of concern, as far as I can tell, SaferCPlusPlus is really the only (non-GC) solution comparable to Rust in terms of safety ¹ and performance. That may change if/when the "C++ Core Guidelines Lifetime Safety checker" ² achieves the ability to detect all memory bugs with a reasonable rate of false positives. Some are skeptical that will happen anytime soon.

Oren,

I'd like to try to help you with your code. Could you perhaps elaborate on why you want to store your trie in a buffer? Is the intent to be able to read the bytes from somewhere and then quickly read the trie without any explicit deserialization step?

As far as I can tell, both your C++ and Rust code have a lot of undefined behavior. In particular, you frequently cast from char * to a pointer to a type with a stricter alignment than char, and then you dereference that pointer. (A violation of the "strict aliasing" rule.) I see this happening in your C++ code: https://github.com/ayende/trie-cpp/blob/master/trie/trie.cpp#L238 and in your Rust code in Trie::new: https://gist.github.com/ayende/13dc2d15563ba04638d2e5c223e4bbe4 --- From where I'm standing, this is the crux of your use of unsafe.

As an additional note, your code does not need alloc, libc or RawVec at all. You should just use a Vec. (Was there any particular Rust documentation that led you to using RawVec?)

If the byte buffer is not a necessary design requirement, then I'd expect your Trie data structure to have a very different representation. (Perhaps a Vec<Node> or similar.) If you do want to pack bytes into a buffer, then you'll probably need an explicit deserialization step. I do this just fine in my fst crate, which encodes a trie-like data structure to a buffer. (The only unsafe it uses is for accessing a memory map.)

I'd be happy to answer any questions you might have! In particular, I know I would love to hear some feedback from you on how we might improve Rust. In particular, what led you to the design you chose?

To add to Andrew's comment, Rust currently doesn't have an abstraction for "vec with heap header", but it would be nice to have one in the crates ecosystem -- I might write this over the weekend. This pattern is more common in C code and doesn't always make sense in Rust, but might be useful. In this case I think putting the header on the stack next to the vec is the easiest path to victory.

Most of the issues here arise from attempting to use programming paradigms from C/C++ in Rust, the code very much looks like "C in Rust syntax". Rust is a systems language, but that doesn't necessarily mean that code will look like C/C++. In this case just using Vec like Andrew mentioned would lead to a safe implementation without any performance differences AFAICT.

Recently on HN there was a discussion on this based around the referenced blog post ( https://blog.ntpsec.org/2017/01/18/rust-vs-go.html )

see :- https://news.ycombinator.com/item?id=13430108

That was brutal, please give Nim a try!

Oren,

If you look at my fst crate, you'll see that it works with mmap directly, and none of the code that reads or writes to the buffer uses unsafe directly. It's simply not necessary. There is a lot more explicit deserialization/serialization (because it does fairly extreme byte packing). Here's the specific code responsible for reading/writing the bytes: https://github.com/BurntSushi/fst/blob/master/src/raw/node.rs --- A similar data structure with similar byte packing is used inside of Lucene.

AFAIK, the fix to your strict aliasing problem is to use memcpy.

As for Vec, if you do vec![0u8; 32], then you get a Vec<u8> of length 32 filled with zeroes.

• Andrew

Oren,

The data is right there in the node with type &[u8]: https://github.com/BurntSushi/fst/blob/master/src/raw/node.rs#L18 --- The &[u8] is taken directly from an mmap. You can follow the progression thusly:

1. Nodes are created here, from the entire &[u8] slice: https://github.com/BurntSushi/fst/blob/master/src/raw/node.rs#L51
2. The first root node is created here, using self.data where selfis Fst: https://github.com/BurntSushi/fst/blob/master/src/raw/mod.rs#L537
3. The data member on Fsthas type FstData, which can contain static data, an owned Vec, a shared Vec or a memory map: https://github.com/BurntSushi/fst/blob/master/src/raw/mod.rs#L956

The end result is that the fst crate can mmap an FST and answer queries directly from memory. It never builds a separate intermediate in memory data structure (like a Vec<Node>). Everything comes from &[u8] as it's needed. You can see for instance where it unpacks the next transition directly from memory here: https://github.com/BurntSushi/fst/blob/master/src/raw/node.rs#L573-L583

Oren,

It is via io::Read, but note that &[u8] satisfies io::Read.

Trying to work with that using this approach is a recipe for madness.

It's not madness, it's necessary if you want to make the most use of the memory available. Tries and finite state machines require excessive bit packing for memory efficiency. Consider that, for example, in FSTs, the vast majority of all nodes will be represented by a single byte. So you need some sort of explicit decompression step. Of course, this gives up some CPU time for reading the data.

But working with the struct pointer directly is extremely easy.

But it's not portable and you need to memcpy the data to avoid undefined behavior. (I'm talking about Rust and C++ here, I don't know what the story is in C#.) But yes, memcpy will require use of unsafe. I'll try to take a look at your interview challenge and code something up for you in Rust using as little unsafe as I can, now that I know more about your requirements.

nwydo over on /r/rust/ said something which I really think deserves to be shared here.

Ayende's struggle is real, these frustrations are perfectly valid. Sadly, they managed to stumble upon a handful of known pain points in Rust all at once:

1. Lexical borrowck: Niko talks about precisely this issue on his blog.
2. entry would be less efficient since it requires always cloning (which would be fixed by RFC 1769
3. entry would require an explicit match on VacantEntry due to lookup_host returning a Result preventing its use in or_insert_with (this issue is common in the sense of ? error-handling breaking in the face of closure-oriented APIs).
4. Needing unstable API-s to solve what seems like an easy problem (like DNS lookup).

I think dismissing these complaints would be irresponsible. Furthermore, I think I'd also give up (at least temporarily) on learning a language if I got unlucky and managed to stumble on a lot of its issues in quick succession like that. So I have a lot of empathy for Ayende and I can't wait for us to solve all these issues this year.

For those who don't follow things, let me clarify that non-lexical borrow scopes (point 1) have been on the roadmap for a while... it's just that they were blocked on a rework of the compiler internals (implementing MIR, the middle-level intermediate representation) that just finished recently. Now, we're just waiting for the borrow checker to be ported from the HIR to the MIR.

Also, your site returns error 500 if the user clicks "Post Comment" with 3rd-party Google requests blocked by a tool like NoScript or uMatrix to block 3rd-party requests to Google by default.

Given that the lone "Human?" looked so much like a button, I tried clicking it and, when it did nothing, just continued on with Post Comment, so you might want to add some sort of check that either displays a "Please enable Google javascript" below "Human?" or produces a more useful error message if the CAPTCHA JavaScript didn't run.

Gah! Somehow, two different revisions of that "site returns error 500" paragraph got munged together and I didn't notice before I clicked Post Comment.

Did you ever try Go? I expect the same tooling problems there.

Go and Rust are new languages and (still) niche languages. The amount of money invested into tooling must be <1% of the money that went into C#, Java, C++.

Many developers overestimate the influence of the language and disregard tooling, libraries, documentation, help on the web and hiring. I certainly made that mistake.

As far as I'm concerned pretty much all niche languages are not useful to use for almost anything for that reason.

Oren, I understand that. I was trying to explain why the fst code is written that way after you called it "madness." There are production databases (like Lucene) that use precisely the same approach.

AFAIK, your C++ code still has lots of undefined behavior. The code violates the strict aliasing rule in numerous places (which is orthogonal to alignment issues). Namely, while you can cast a struct to a char*, you can't cast a char* back to a struct. I know of two workarounds: you either need to memcpy or you need to cast through a union.

I think you can use a union. I think you'd have to change, e.g.,

struct trie_header_info
{
    short next_alloc;
    short used_size;
    short items_count;
    short reserved;
};

to

struct _trie_header_info
{
    short next_alloc;
    short used_size;
    short items_count;
    short reserved;
};
union trie_header_info
{
        _trie_header_info info;
        char* buffer;
}

And then you can cast through the union.

Interestingly, I don't think the strict aliasing rule applies in Rust, but I'm not 100% on that.

To avoid strict aliasing violations, you would have to write directly through the union whenever you access fields of the struct (i.e. foo->info.used_size); you're not allowed to dereference a pointer to the struct, no matter what method you use to obtain that pointer. This is because the conflict is between the "effective type" (C standard) or "dynamic type" (C++ standard) of the object (memory), on one hand, and the type of a pointer used for access, on the other. (There is usually no way to change the effective type; in C you can do so for malloced memory only, but that language doesn't appear in the C++ standard.) To quote the C++ standard:

If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined:

• the dynamic type of the object,
• [...]
• an aggregate or union type that includes one of the aforementioned types among its elements or non- static data members (including, recursively, an element or non-static data member of a subaggregate or contained union),
• [...]
• a char or unsigned char type.

An alternative is to use memcpy, which counts as a char-typed access. (This doesn't have to involve copying the whole struct, by the way; wrapper functions that memcpy a single integer at a time work and will optimize into regular load/stores.)

Of course, a third option is to just ignore the undefined behavior and hope the compiler doesn't do anything too clever. It probably won't.

And yes, strict aliasing rules do not apply to Rust, which doesn't need to rely on type-based aliasing analysis for performance, since the behavior of references already guarantees that most memory can't be changed behind the compiler's back.

Strict aliasing in C++ applies to everything except char*. It is allowed to alias anything and you can reinterpret_cast between it and any other type. I'd quote the standard but I'm too lazy at the moment.