Re: BitArray new design - slice problems

[Dmitry Olshansky]

19-Jan-2013 11:14, Era Scarecrow пишет:

On Friday, 18 January 2013 at 16:42:04 UTC, Dmitry Olshansky wrote:

Slices should have a pointer and length so they can check range (in
debug builds), alternatively just a pointer to storage that nows the
range.


  So write an alternate opIndex...


I think slice ops could be made @safe if the primitives for bulk
transfer and opIndex in the Storage are @trusted.

If we just mark all of opSlice on Fixed-sized one as @system then it
should be good enough. In other words (I'm lost in terminology):



snip


The idea is to make code responsible for the root of unsafety to be
@system everything else then can be @safe or @trusted(where compiler
can't see it).


  Hmmm okay... Somehow this seemed so much more complex than it's put here.


I think that the most of slice ops can be @safe/@trusted. It's the
process of taking a slice out of stack-based container that is not
@safe. The one taking a slice out of GC-based one is @safe.


  And depending on if it is fixed or dynamic will determine if the slice
is @system or @safe... Makes sense. That sets me straight.


  So for the slice/range, what all should it support? I've tried to have
it support (or foward) opBinary, opBinaryAssign, comparing, slicing,
copying, as well as inputRange, bidirectional, opIndex  opIndex assign,
opDollar and length. If it should support a much smaller sub-set I'll
need to know; Could greatly affect how it is written.



opBinaryAssign -- opOpAssign. opSlice/opSlice assign.
In any case it seems to me that (I think you already did this trick 
before) you can reuse a lot of code by making an operator string a 
template parameter (for functions that implement  =, |=, =, ^=, and 
therefore ^, |, ) and use string mixins.


Other then this - don't forget the '~' _unary_ operator as it makes a 
lot of sense for bit-vectors. Now since slices don't support '~' 
concatenation it won't look so bad. Worst case:


auto ba = BitArray(...);
auopt slice = ba[...];
ba ~= ~slice;

And it's not much of problem.
--
Dmitry Olshansky

Re: BitArray new design - slice problems

[Dmitry Olshansky]

18-Jan-2013 01:49, Era Scarecrow пишет:

On Thursday, 17 January 2013 at 19:36:34 UTC, Dmitry Olshansky wrote:

I'm thinking that a opSlice of stack-allocated must be @system and a
heap allocated can be @safe.


  That's just a small part of the problem. With the new design, 90% of
it can be safe; Just the actual slice buffer when you request it (with
Fixed storage) would be @system,and slices (having a pointer)


Slices should have a pointer and length so they can check range (in 
debug builds), alternatively just a pointer to storage that nows the range.


 But

@safe code can't call @system code which means that the current design
(convert to slices before operations) it all has to all be @system.



I think slice ops could be made @safe if the primitives for bulk 
transfer and opIndex in the Storage are @trusted.


If we just mark all of opSlice on Fixed-sized one as @system then it 
should be good enough.In other words (I'm lost in terminology):


FixedBitArray!(1024) fixed;
auto slice = fixed[0..100]; //this is @system
slice[10..20] = slice[20..30]; //this is @safe
foreach(bool x; slice[0..10])  //this is @safe
{... }

The idea is to make code responsible for the root of unsafety to be 
@system everything else then can be @safe or @trusted(where compiler 
can't see it).



  Guess once it's debugged the entire thing can be @trusted and only
certain things can be marked @system instead.


I think that the most of slice ops can be @safe/@trusted. It's the 
process of taking a slice out of stack-based container that is not 
@safe. The one taking a slice out of GC-based one is @safe.


--
Dmitry Olshansky

Re: BitArray new design - slice problems

[Dmitry Olshansky]

17-Jan-2013 07:53, Era Scarecrow пишет:

  Well got a few curious problems. Slicing doesn't seem it wants to work
as a separate type and can cause problems.

  Let's take an example. Say our slice is..

   struct BitArraySlice {
 BitArray* ba;
 ulong start, end;
   }

  Now how much does it depend on the bitarray that it's pointing to? If
it is a wrapper then we have a problem with range checks which should be
legal.

   BitArray x = BitArray(100); //100 elements

   auto sl = x[50 .. 100];
   x.length = 50;


Well, the slice was invalidated by shrinking an array. I don't expect 
the below to work.



   sl[0] = true; //out of range! BitArray valid from 0-49, not 50-100



The good part is that error can be detected easily. In c++ for instance 
it typically isn't.


The harder problem is what to do when the original BitArray goes out of 
scope. I guess in case of storage allocated on heap it should work but 
if on the stack it shouldn't (and can't).



  That much is sorta easy to fix with a separate opIndex (and fixed
sizes), but it's possible to re-slice the dynamic array to make it
smaller. So even if we have opIndex allow out of ranges...

   struct BitArray {
 size_t[] store; //storage
 ubyte start, end;
   }

   BitArray x = BitArray(100); //100 elements
   auto sl = x[50 .. 100];

   //likely does x.store[] = x.store[0 .. 2];
   //due to compact 1 byte offsets to determine end of bitarray.
   x.length = 50;

   sl[0] = true; //ok, 0-64 valid on 32bit machines
   sl[32] = true; //out of range! 82 past not within 0-63



That's why it's far better to allow slices to be invalidated depending 
on the length parameter of BitArray pointed by. Compact array do weird 
things in the previous version too.




  So let's take the slice and give it the address of the storage
instead, other than it could point to a local variable it will work; But
now I have basically two definitions of bitarray, one that can be a
range/slice while the other that manages the memory and binary operators.

   struct BitArraySlice {
 //same as BitArray now, what advantage does this give?
 size_t[] store;
 ulong start, end;
   }

  Seems like making the slices a separate entity is going to cause more
problems (Not that they can't be solved but the advantages seem
smaller); Plus there's issues trying to get immutable/idup working.



Slices are ranges and thus are converted to array via std.array.array, 
nothing to invent or re-implement.



  Thoughts? Feedback? I'm about ready to drop this and resume my
previous version and enhance it with recent experiences.


Feel free to do it how you see it. It's just that I think the semantics 
of the previous version can't be improved to a consistent state.


--
Dmitry Olshansky

Re: BitArray new design - slice problems

[Era Scarecrow]

On Thursday, 17 January 2013 at 18:12:28 UTC, Dmitry Olshansky 
wrote:
Well, the slice was invalidated by shrinking an array. I don't 
expect the below to work.


 It just seems like shrinking/expanding the array should still 
work, perhaps I'm thinking of them too much like a normal array 
slice. If this is acceptable behavior then okay, but the 
increased complexity may not be worth it.


The good part is that error can be detected easily. In c++ for 
instance it typically isn't.



The harder problem is what to do when the original BitArray 
goes out of scope. I guess in case of storage allocated on heap 
it should work but if on the stack it shouldn't (and can't).


 Passing back the BitArray in either form is valid, as dynamic 
stays valid and a full binary copy stays valid. The slices on the 
other hand won't be valid unless it's on the heap.




  sl[0] = true; //ok, 0-64 valid on 32bit machines
  sl[32] = true; //out of range! 82 not within 0-63


That's why it's far better to allow slices to be invalidated 
depending on the length parameter of BitArray pointed by. 
Compact array do weird things in the previous version too.


 Hmmm...

So let's take the slice and give it the address of the storage 
instead, other than it could point to a local variable it will 
work; But now I have basically two definitions of bitarray, 
one that can be a range/slice while the other that manages the 
memory and binary operators.


Seems like making the slices a separate entity is going to 
cause more problems (Not that they can't be solved but the 
advantages seem smaller); Plus there's issues trying to get 
immutable/idup working.




Slices are ranges and thus are converted to array via 
std.array.array, nothing to invent or re-implement.


 Thoughts? Feedback? I'm about ready to drop this and resume 
my previous version and enhance it with recent experiences.


Feel free to do it how you see it. It's just that I think the 
semantics of the previous version can't be improved to a 
consistent state.


 Sure they can, drop the compact part of it and leave it fully 
dynamic (or vise-verse). But that would make some people unhappy; 
On the other hand we could go hybrid where I take the new storage 
implementations and allow template versions based on needs, 
remove the compact related stuff, but then it's almost back to 
the separate slice design. Hmmm...


 Should the slices be 'use at your own risk' when you tamper with 
the original BitArray? How else should it be?

Re: BitArray new design - slice problems

[Dmitry Olshansky]

17-Jan-2013 22:34, Era Scarecrow пишет:



 Thoughts? Feedback? I'm about ready to drop this and resume my
previous version and enhance it with recent experiences.


Feel free to do it how you see it. It's just that I think the
semantics of the previous version can't be improved to a consistent
state.


  Sure they can, drop the compact part of it and leave it fully dynamic
(or vise-verse). But that would make some people unhappy; On the other
hand we could go hybrid where I take the new storage implementations and
allow template versions based on needs, remove the compact related
stuff, but then it's almost back to the separate slice design. Hmmm...

  Should the slices be 'use at your own risk' when you tamper with the
original BitArray? How else should it be?


I'm thinking that a opSlice of stack-allocated must be @system and a 
heap allocated can be @safe.


Possibly there are better ways to handle this.

--
Dmitry Olshansky

Re: BitArray new design - slice problems

[H. S. Teoh]

On Thu, Jan 17, 2013 at 11:36:33PM +0400, Dmitry Olshansky wrote:
[...]
 I'm thinking that a opSlice of stack-allocated must be @system and a
 heap allocated can be @safe.
[...]

Related: http://d.puremagic.com/issues/show_bug.cgi?id=8838


T

-- 
Who told you to swim in Crocodile Lake without life insurance??

Re: BitArray new design - slice problems

[Era Scarecrow]

On Thursday, 17 January 2013 at 19:36:34 UTC, Dmitry Olshansky 
wrote:
I'm thinking that a opSlice of stack-allocated must be @system 
and a heap allocated can be @safe.


 That's just a small part of the problem. With the new design, 
90% of it can be safe; Just the actual slice buffer when you 
request it (with Fixed storage) would be @system, and slices 
(having a pointer). But @safe code can't call @system code which 
means that the current design (convert to slices before 
operations) it all has to all be @system.


 Guess once it's debugged the entire thing can be @trusted and 
only certain things can be marked @system instead.

BitArray new design - slice problems

[Era Scarecrow]

 Well got a few curious problems. Slicing doesn't seem it wants 
to work as a separate type and can cause problems.


 Let's take an example. Say our slice is..

  struct BitArraySlice {
BitArray* ba;
ulong start, end;
  }

 Now how much does it depend on the bitarray that it's pointing 
to? If it is a wrapper then we have a problem with range checks 
which should be legal.


  BitArray x = BitArray(100); //100 elements

  auto sl = x[50 .. 100];
  x.length = 50;
  sl[0] = true; //out of range! BitArray valid from 0-49, not 
50-100


 That much is sorta easy to fix with a separate opIndex (and 
fixed sizes), but it's possible to re-slice the dynamic array to 
make it smaller. So even if we have opIndex allow out of ranges...


  struct BitArray {
size_t[] store; //storage
ubyte start, end;
  }

  BitArray x = BitArray(100); //100 elements
  auto sl = x[50 .. 100];

  //likely does x.store[] = x.store[0 .. 2];
  //due to compact 1 byte offsets to determine end of bitarray.
  x.length = 50;

  sl[0] = true; //ok, 0-64 valid on 32bit machines
  sl[32] = true; //out of range! 82 past not within 0-63


 So let's take the slice and give it the address of the storage 
instead, other than it could point to a local variable it will 
work; But now I have basically two definitions of bitarray, one 
that can be a range/slice while the other that manages the memory 
and binary operators.


  struct BitArraySlice {
//same as BitArray now, what advantage does this give?
size_t[] store;
ulong start, end;
  }

 Seems like making the slices a separate entity is going to cause 
more problems (Not that they can't be solved but the advantages 
seem smaller); Plus there's issues trying to get immutable/idup 
working.


 Thoughts? Feedback? I'm about ready to drop this and resume my 
previous version and enhance it with recent experiences.