Request for pre-review: std.serialization/orange

[Jacob Carlborg]

On 2011-10-04 07:21, Robert Jacques wrote:
> That putting isSliceOf in the public API, implies its usage by the
> archiver.

Ok, then I'll remove it.

>> 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?

> // 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.

> Can a pointer point to the interior of an object? To an element of an
> array?

Yes, have a look at: 
https://github.com/jacob-carlborg/orange/blob/master/tests/Pointer.d

Not sure about the array part though, but I think so. Each element of an 
array is serialized just like all the other types.

>> I can see if I this memory chunk approach can be used instead. How will
>> this be used with the balanced tree, could you give a simple example?
>
> Well, balanced trees need a comparison function so:
>
> struct Node {
> void* head; // Start of the memory chunk
> void* tail; // End of the memory chunk
> bool hasAliases; // True if there are more than one reference to this chunk
> //... Other meta-data, i.e. ID,
>
> int opCmp(const ref Node b) {
> if( tail < b.head) return -1;
> if(b.tail < head) return 1;
> return 0;
> }
> }
>
> On equality / assignment, one just has to combine the heads and tail
> with min/max, respectively, and update hasAliases, etc. The difficulty
> is when a new node 'bridges the gap' between two existing nodes. This
> has to handled explicitly as part of the tree re-balancing, but you may
> want to consider making the merging of nodes part of the comparison
> operator for simplicity/efficiency:
>
> head = min(head,b.head);
> tail = max(tail,b.tail);
> hasAliases = true;
>
> After pruning, updating meta-data, etc, the aliased memory chunk for any
> given pointer can be found using a separate comparison operator:
>
> int opCmp(const ref void* b) {
> if(tail < b ) return -1;
> if(b < head) return 1;
> return 0;
> }
>
> // Which you'd probably use like:
>
> if( auto node = arr.ptr in setOfAliases ) {
> auto offset = arr.ptr - node.head;
> //...
> } else {//...
>
>
> So at the pseudo-code level, it would be something like:
>
> foreach(obj; [objects,pointers,arrays]) {
> auto node = Node(obj);
> setOfAliases.insert(node);
> // Convert obj into an intermediate form
> }
>
> setOfAliases.pruneUnaliasedNodes;
> setOfAliases.postProcessMetadata; // i.e. assign unique alias ID, etc
>
> foreach(obj; [objects,pointers,arrays]) {
> if( auto node = arr.ptr in setOfAliases ) {
> auto offset = arr.ptr - node.head;
> // Perform an aliased archival
> } else {
> // Perform an unaliased archival
> }
> }
>
> I hope that helped, though I'm not sure if I really answered your
> question or not.

Yes, I think it at least helped somewhat. The thing is that I'm not very 
familiar with using trees like these.

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

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 
?

-- 
/Jacob Carlborg