|
I think it's that you're trying to use self while it's borrowed (which it is because you're borrowing one of its fields). Can you pull out the node as a value whose lifetime isn't dependent on self, so that self can be un-borrowed by the time you want to call a method on it?
|
#
¿
Aug 19, 2016 06:43
|
|
|
|
| # ¿ May 5, 2024 06:38 |
|
|
In order to appease the borrow-checker, you're going to have to prove that your recursive call can't invalidate nodes or visit the same node re-entrantly. So first you should think: how do I know that that's actually true? And then you should think: how on earth can I convince a relatively simple scope-based static analysis that that's true? If your graph is really arbitrary, your node references are probably reference-counted (or externally owned?), and you probably have some sort of visited set to prevent re-entrance. That visited set is what gives you correctness here, and it makes sense that it should be the thing offering you a mutable reference when it proves that you're not accessing a node re-entrantly. Its internals will probably need to be unsafe to make that work. If this is really a tree, with child nodes held with unique ownership at different places in the tree, then the basic problem is that there's no reason your arbitrary method call on self couldn't invalidate the node's children. Maybe you can just pass the index of the node down to the call instead of trying to pass a reference. The other approach, perhaps more promising, is to try to set up your memoization caches so that they can be modified given just an immutable borrow of a node. I'm pretty sure there are library types designed for that.
|
|
#
¿
Aug 19, 2016 07:20
|
|
|
A memcpy into a bool should be well-defined, assuming the source holds a valid bool value. Something like 2 would not be a valid bool value. If you have a single payload, and its representation has what we call in Swift "extra inhabitants" — bit patterns that aren't considered legal values — then you can use those inhabitants for the other cases, so that representations of the payload are exactly representations of the enum. That works for both shared and exclusive access without any impositions on the ABI. For example, if the single payload is a pointer, there are a large number of bit-representations that can be assumed to not be legal (at least in a sufficiently high-level language). The most obvious is 0, the null pointer, but it's probably reasonable to say 1, 2, etc. are also available, up to at least a page; and if the pointer has to be aligned, then everything not aligned is available, too. If you have multiple payloads, even of the same type, that isn't good enough; you really need spare bits in the representation to store a discriminator between those cases. If the ABI for the payload type says that those spare bits have to have some expected value, then you might be in trouble. For example, if you have an enum with two cases that are 2-byte aligned pointers, you can theoretically use the low bit to distinguish cases, but clients handed a pointer will expect those bits to be zero. Now, if everything accessing the case knows exactly what it's working with, then you can be arbitrarily smart about these things; you just generate code to ignore/set the discrimination bits whenever you have an access. Unfortunately, Rust allows you form a reference to a payload and pass it off as a normal reference. Unless we're going to specialize everything that might get that reference — in general not possible — then we really need the reference to refer to memory that follows the normal ABI for the payload type. If we know that we have exclusive access to the enum, then we can form this reference by clearing the discrimination bits and then putting them back when we're done. That might be inefficient, but it would work. But Rust lets you make a shared reference to the payload from a shared reference to the enum, and there could be other references to the enum, so no dice. If the lifetime of the payload reference can be shorter than the lifetime of the enum, then we can just copy to a temporary with the bits cleared and make a reference to that. But that's not the rule in Rust, so no dice again. You can make it part of the ABI for the payload type that you ignore and preserve spare bits. That might be a huge penalty, though. In our pointer example, we'd have to mask on every load of a reference to a pointer, and we'd have to mask when storing a value as well. For bool, we'd have to make sure we always touched exactly the low bit; we couldn't just load the bool and compare it against zero. So probably you're stuck with using a separate tag discriminator. I don't know how close to this ideal Rust gets. I know Swift has limits to its logic that fall well short of it.
|
|
#
¿
Sep 25, 2016 01:15
|
|
|
limaCAT posted:I am just reading this excellently written article about parser combinators in Rust. I have reached the part where the author explains that "types are becoming complicated" and then goes into explaining a lenghty refactoring using Box to avoid making type generation explode at compilation time. I am just wondering: what's the mechanism that makes rustc try to expand traits and make compilation time explode? Is there any way to visualize it (maybe via a log that's invoked by a compilation time parameter)? Is that tied to the compilation time guarantees? I know nothing about this specific library, but to guess: the implementation type of a parser either is or is not erased. If it’s erased, then at every step you have a Parser that parses a T, and that’s all you know; now combinators just take an arbitrary Parser<T>, which is a concrete type which presumably has to have a concrete layout, so producing it for a particular parser implementation might require allocation. If it’s not erased, then at every step you have a type P that implements a Parser that produces a T; now combinators have to be parameterized over that type P, which means that the result of applying a ton of combinators basically fully reflects the tree of combinator applications and so grows with the size of the expression. (As I understand it, in Rust this cost can be largely ameliorated with opaque trait types.) A very similar question comes up with closures, which show up all the time in combinator parsers. It would be extremely Rust-like for a library to not use type erasure at any stage unless you ask it to.
|
|
#
¿
Jul 27, 2019 02:14
|
|