Request for pre-review: std.serialization/orange

[Robert Jacques]

On Tue, 04 Oct 2011 03:22:35 -0400, Jacob Carlborg <doob at me.com> wrote:
> On 2011-10-04 07:21, Robert Jacques wrote:

[snip]

>>> Actually it does not need to be part of the public API when I think
>>> about it. I can move it into Serializer. Array would still need to be
>>> public since both Serailzer and Archive need access to it and the
>>> package attribute doesn't work very well.
>>
>> Regarding design, I agree, although I'd go one further and define Array
>> as a public type inside the Serializer class. However, this concept of
>> an 'Array' is fundamentally flawed. Consider:
>>
>> auto c = a[1..3];
>>
>> auto cArr = Array(c.ptr,c.length,4);
>>
>> assert(!cArr.isSliceOf(bArr));
>> assert(!bArr.isSliceOf(cArr));
>
> Any suggestion how to fix this, how to properly detect if an array is a
> slice of some other array?

Well, there are two problems. First, there is an API issue: When you pass an aliased array to the archiver, you must pass both an array and a slice of that array.
Second, is detection. The comparison operator I suggested below covers this issue. Just remember that with a loop based approach, you can't terminate the search early: you have to check all existing arrays for possible matches.

>> // and
>>
>> b ~= 5;
>>
>> bArr = Array(b.ptr, b.length, 4);
>>
>> assert(!bArr.isSliceOf(aArr));
>
> Appending to "b" will reallocate "b" making it a regular array and not a
> slice:
>
> b ~= 5;
> b[] = 100;
> assert(a == [0, 1, 2, 3, 4]);
>
> "a" is not modified and the assert passes.

I'm sorry, you're right. In my mind b extended to the end of the a array, for some reason. However, if you do define b to extend to the end of the a array, then it can append without allocating:

	auto a = [0, 1, 2, 3, 4];
	auto b = a[2 .. $];
	b ~= 5;
	assert(b[0]==2);
	a[2] = 10;
	assert(b[0]==10);

So please don't dismiss this point.

[snip]

> Would this something similar to:
> https://github.com/jacob-carlborg/orange/blob/master/orange/serialization/Serializer.d#L1520
> ?

I'm not sure, that routine seems to be filtering pointers between those with aliases and those without aliases, which would be similar in effect to:

if( auto node = arr.ptr in setOfAliases ) {} else {}

> What is the advantage with using a tree? Is the advantage that you loop
> over the elements once in the pseudo-code compared to that I loop over
> them twice, as in:
> https://github.com/jacob-carlborg/orange/blob/master/orange/serialization/Serializer.d#L1495
> ?

Primarily, it's O(N logN) vs O(N^2). Also, it solves the isSliceOf problem we discussed above and puts arrays and objects into the same framework, as objects containing fixed sized arrays can have slices.