DeserializeOwned prevents deserialization into structs with lifetime bounds

[sezna]

First of all, thanks for this great crate. It has been serving me very well and I am a big fan.

I am trying to deserialize a struct I just serialized, just a basic round-trip. The struct, to be specific, is this one. You'll notice the lifetimes and Cow<'a, str>s in the nested structs. Serialization works fine, but deserialization does not.

implementation of `_IMPL_DESERIALIZE_FOR_EdiConvertToRequest::_serde::Deserialize` is not general enough
   --> src/main.rs:102:28
    |
102 |           DataFormat::Xml => quick_xml::de::from_str(&req.data)?,
    |                              ^^^^^^^^^^^^^^^^^^^^^^^ implementation of `_IMPL_DESERIALIZE_FOR_EdiConvertToRequest::_serde::Deserialize` is not general enough
    | 
   ::: /home/alex/.cargo/registry/src/github.com-1ecc6299db9ec823/serde-1.0.104/src/de/mod.rs:531:1
    |
531 | / pub trait Deserialize<'de>: Sized {
532 | |     /// Deserialize this value from the given Serde deserializer.
533 | |     ///
534 | |     /// See the [Implementing `Deserialize`][impl-deserialize] section of the
...   |
569 | |     }
570 | | }
    | |_- trait `_IMPL_DESERIALIZE_FOR_EdiConvertToRequest::_serde::Deserialize` defined here
    |
    = note: `edi::edi_document::EdiDocument<'_, '_>` must implement `_IMPL_DESERIALIZE_FOR_EdiConvertToRequest::_serde::Deserialize<'0>`, for any lifetime `'0`...
    = note: ...but `edi::edi_document::EdiDocument<'_, '_>` actually implements `_IMPL_DESERIALIZE_FOR_EdiConvertToRequest::_serde::Deserialize<'1>`, for some specific lifetime `'1`

Following the guidance on this SO post, I think changing this crate's Deserialize definition to one like serde_json's would work. Note that I am able to successfully deserialize this struct back from JSON without issue, it is just the XML that isn't working.

I report this as an issue because as far as I can tell, there is no workaround besides forking the crate that defines the struct and making everything it contains owned.

[tafia]

Thanks for the issue. Serde is really complicated to implement properly (at least for me). I've tried using DeserializeOwned as well (the whole quick-xml library, apart from the serialization actually tries hard not to allocate if possible. Unfortunately I didn't manage to make it work.
This is a known issue on my side and I'd be happy to receive some help. Sorry for that

[andreivasiliu]

This is fundamentally impossible given the Reader's current implementation, because the reader never really borrows from the input, but rather it copies into a buffer and borrows from that.

Right now the deserializer just makes buffers by itself and throws them away with every element (which by the way is a big opportunity for optimization, the capacity should be reused). But I think users would be happy even to borrow from that buffer, if from_str could be changed so that it takes a user's buffer, and the deserialized object borrows from that...

...which is also fundamentally impossible given the Reader's current implementation, because the Vec buffer can't be re-borrowed while previous events (or other fields in a deserializer's case) still borrow from it.

To illustrate what I mean, this won't compile:

    let mut reader = quick_xml::Reader::from_str(xml);
    let mut buffer = Vec::new();

    let event1 = reader.read_event(&mut buffer);  // event1 borrows buffer
    let event2 = reader.read_event(&mut buffer);  // wants to write more into the buffer
    println!("The events: {:?} {:?}", event1, event2);

If lifetimes weren't a thing, this should semantically be correct, and work just fine. Because theoretically, even if there are previous references into the buffer, I should be able to modify it as long as the only thing I'm doing is appending onto it (never modifying old data), and the memory only grows and is never moved. That's not the case with Vec (it moves all previous data if the OS cannot resize in-place).

One solution I can think of is the bytes crate, which provides exactly what we need... you can write things to it, then "split off" the first segment and get a tail end you can keep writing to, that reuses the capacity whenever possible. It's a heavy object (I think I saw Mutexes in there), so using it will need a lot of benchmarking, but it might be worth looking into. It provides a BufMut trait that's also implemented for Vec, so making .read_event take a &mut dyn BufMut instead of &mut Vec might keep things mostly backwards compatible for users.

I'll try to see if I can wrap my head around it some more and if it's feasible to use.

Another solution is to redesign the reader so that it supports borrowing from the input and not use an intermediary buffer. This won't work for e.g. BufRead (the input data is ephemeral), so it'll need to be optional somehow.

[tafia]

Yes indeed this is the current limitation. Bytes might work.

I wanted to ship a semi-working version first and work out the performance issue later.

I'd be awesome if you can figure something, I am not working specifically at improving performance on this at the moment.

[andreivasiliu]

If I wanted to deserialize this:

<a>Some &quot;escaped&quote; text</a>

...into this struct:

struct A<'a> {
    a: &'a str,  // Or, or &[u8], etc
}

...what would I expect to find in a? The escaped, or unescaped version?

1. Unescaped: The current implementation makes a new string (owned Cow) and stores the unescaped string there, which would disappear during deserialization, so this &str would have nothing to borrow from. I could make another variant of unescape(raw) which takes the user's buffer, a range of escaped text in that buffer, and appends the unescaped one onto the same buffer... this means re-indexing (and bounds-checking) a heck of a lot more often, but we also allocate less.
2. Escaped: This wouldn't survive a round-trip, which is likely surprising (and a round-trip of an alien struct seems to be what the OP asked for). Would be very easy to implement though.
3. Disallowed: Make it panic with: "Deserializing into &'str is not supported, please deserialize into Cow or BytesText instead", and provide a Deserialize implementation for BytesText (or something similar).

I like 1. Would it be acceptable?

[andreivasiliu]

Tried bytes, doesn't seem to work. It allows me to split off small parts of it, but during deserialization I'm forced to throw them away, or store them in yet another user-given Vec... which just brings all the old problems back.

I found appendlist, it also allows keeping references while pushing at the end, and the way it's implemented is really nice. But it only supports pushing single elements, and I need slices, so it doesn't work... although if all else fails, I could just implement slice support into it.

With that said, I realized that what I'm looking for is probably an arena allocator, and typed-arena looks suitable (edit: nope, I was wrong, will have to keep searching).

With a trait, I can make it work for both the old-style &mut Vec as well as for an &Arena.

Proof of concept:

fn test_append() {
    // Arena allows multiple references
    let buffer = Arena::new();
    let event1 = read_event(&buffer);
    let event2 = read_event(&buffer); // allowed!
    println!("Arena-backed events: {:?}, {:?}", event1, event2);

    // Old-style Vec still works, but only one at a time
    let mut buffer = Vec::new();
    let event1 = read_event(&mut buffer);
    println!("Vec-backed event: {:?}", event1);
}

trait BytesBuffer<'a> {
    fn extend_and_slice(self, bytes: &[u8]) -> &'a [u8];
}

impl<'a> BytesBuffer<'a> for &'a Arena<u8> {
    fn extend_and_slice(self, bytes: &[u8]) -> &'a [u8] {
        self.alloc_extend(bytes.iter().copied())
    }
}

impl<'a> BytesBuffer<'a> for &'a mut Vec<u8> {
    fn extend_and_slice(self, bytes: &[u8]) -> &'a [u8] {
        self.extend_from_slice(bytes);
        &self[self.len() - bytes.len()..]
    }
}

fn read_event<'a>(buffer: impl BytesBuffer<'a>) -> &'a [u8] {
    buffer.extend_and_slice(b"Hello")
}

Edit: I'm looking at read_until_elem now and see that this isn't a good solution either, it puts things progressively into the buffer, rather than all at once. So I need an arena allocator that can resize the last element before locking it in.

[andreivasiliu]

Found an arena allocator that can resize the last element efficiently: bumpalo. I'll need to rethink the trait though.

Now that I realized it technically reads the whole input in order, byte by byte, into the buffer, I'm also thinking of a redesign using something like buffered-reader as an input, which removes the need of a buffer in the first place, and would truly be zero-copy.

However, the lifetime of the returned events would be tied to the quick-xml reader. This might not be an issue, since all the other methods you'd want to call on it (e.g. .decode()) only take immutable references. I guess I could also externalize the input reader from the quick-xml reader's struct completely though, which would fix that.

Because the BufferedReader trait is also implemented for a plain &[u8], and it just pretend-reads things from it, this might also make events with references directly into the input possible. Since the reference is only immutable, this means it might be possible to call .read_event() multiple times, which is what I'd need for a borrowing deserializer.

[andreivasiliu]

So I found a way to parametrize the lifetime of where the events borrow from:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=984915153b61f720b4314a49a0d8a6f2

And the external API should not change much, if at all, but I'm not sure yet. I think it's also forward compatible with adding BufferedReader as a possible input type too.

I'll need to rewrite read_until/read_elem_until into the new trait, and it looks like @tafia is doing all sorts of changes to those in 259ab4b so I'll wait a bit.

[sezna]

Hey, thanks for tackling this issue. The caveat of the escaped strings in this particular deserialization format is indeed a tricky one.

I wouldn't be surprised if the lifetimes end up being tied to the quick-xml reader, and in all honesty that sounds like an intuitive and fair tradeoff. However, your final playground does seem like the most "proper" solution, parameterizing on the lifetimes. That's a really nice find, being able to distinguish the implementations like that.

[andreivasiliu]

It turns out serde_json can't handle escaping either, so I'll probably just mimic that behavior. It fails at runtime, which is a bit weird, but might be better than nothing. Deserializing into Cow should always work though, and should be recommended in the documentation.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=3914076ef7e25451402c85bfc743db58

[andreivasiliu]

Seems my approach doesn't work, some of the code hits a limitation with NLL.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=97da64b8eab45de9784001372546f128

Example is read_until_open, which can return either text, or if after all whitespace was stripped there's nothing left, the next element (which requires another read, but only sometimes).

The issue is described here:
http://smallcultfollowing.com/babysteps/blog/2018/06/15/mir-based-borrow-check-nll-status-update/#polonius

So I might have to wait until Polonius (aka NLL++) arrives, or figure out a way to go around that somehow.

[andreivasiliu]

Managed to make some progress, and I now have a version of .read_event() that can be called multiple times in a row:

fn main() -> Result<()> {
    let xml = "<one>hello</one><two>world</two>";
    let mut reader = Reader::from_str(xml);

    let event1 = reader.read_event_unbuffered()?;
    let event2 = reader.read_event_unbuffered()?;  // works!

    println!("Events: {:?}, {:?}", event1, event2);
    Ok(())
}

Opened a PR (still unfinished and unpolished): #208

Next up is figuring out how to tackle the actual deserializer, I have no idea what a proof of concept would look like yet.

[tafia]

Thanks a lot for your work @andreivasiliu this is REALLY appreciated even if I am very late to answer.

[Mingun]

Was implemented in #290