[msgpack][JIRA] Created: (MSGPACK-81) Cannot serialize class with circular references

[Andrej Mitrovic (JIRA)]

Cannot serialize class with circular references
-----------------------------------------------

Key: MSGPACK-81
URL: http://jira.msgpack.org/browse/MSGPACK-81
Project: MessagePack
Issue Type: Bug
Components: D
Environment: DMD 2.060
Reporter: Andrej Mitrovic
Assignee: FURUHASHI Sadayuki


{code}
import msgpack;

class Foo
{
int x;
Bar obj;
}

class Bar
{
int x;
Foo obj;
}

void main()
{
auto foo = new Foo();
auto bar = new Bar();
foo.obj = bar;
bar.obj = foo;
ubyte[] data = msgpack.pack(foo);
}
{code}

This creates a stack overflow.

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

[Andrej Mitrovic (JIRA)]

[ http://jira.msgpack.org/browse/MSGPACK-81?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=10502#comment-10502 ]

Andrej Mitrovic commented on MSGPACK-81:
----------------------------------------

Ok I can see a comment in msgpack-d that it's not supported. I have a branch that implements a workaround, however it can't be compatible with the MessagePack protocol because it introduces a new header (essentially a tag that marks a field as being a reference to an object). And I'm not sure if it would work with streaming.

[Masahiro Nakagawa (JIRA)]

[ http://jira.msgpack.org/browse/MSGPACK-81?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=10503#comment-10503 ]

Masahiro Nakagawa commented on MSGPACK-81:
------------------------------------------

Hi Andrej,

> Ok I can see a comment in msgpack-d that it's not supported

Yes. Some serialization protocols don't support circular reference, e.g. MessagePack, JSON, Thrift and etc. This is important for fast / compact format and easy implementation. No circular reference almost never seems to be an issue in many production environments.
On the other hand, language specified serialization often supports its feature, e.g. Ruby, Java, C#'s DataContractSerializer and D's Orange. But those protocols can't communicate other languages and generally slow...
If you want circular reference support, you should choose trade-off. Of course, extending msgpack internally is another resolution :)

In addition, MessagePack doesn't consider circular reference support now.

[Andrej Mitrovic (JIRA)]

[ http://jira.msgpack.org/browse/MSGPACK-81?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=10504#comment-10504 ]

Andrej Mitrovic commented on MSGPACK-81:
----------------------------------------

Yeah, compatibility would be broken. But it seems fairly easy to implement: https://github.com/AndrejMitrovic/msgpack-d/tree/ClassRefs

It will come in handy for me for offline use.

All that's needed is a counter that creates sequential IDs (based on the order in which the objects are serialized) and a hashmap that holds key:address->value:ID of objects which are serialized. When an object reference is found which is in this hashmap it means it has already been serialized, so the packer retrieves the ID and stores a header and the ID instead of storing the object again.

So for example in this code:

{code}
import msgpack;

class A { A a; B b; C c; }
class B { A a; B b; C c; }
class C { A a; B b; C c; }

void main()
{
A a = new A;
B b = new B;
C c = new C;
a.a = a; a.b = b; a.c = c;
b.a = a; b.b = b; b.c = c;
c.a = a; c.b = b; c.c = c;

ubyte[] data = msgpack.pack(a);
writeln(data);
}
{code}

In the current implementation the byte array would never be completed:

[93 93 93 93...] -> stack overflow

In the new implementation I use a new header "0xFA", followed by either 4 or 8 bytes (32bit/64bit) denoting the ID.

Some samples:
https://github.com/AndrejMitrovic/msgpack-d/blob/ClassRefs/example/circular_class.d
https://github.com/AndrejMitrovic/msgpack-d/blob/ClassRefs/example/circular_class_2.d

I haven't implemented it for pointers yet, just class references.