On Thursday, 10 January 2013 at 20:11:38 UTC, Dmitry Olshansky wrote:
> You want to mixin a definition of a inner struct BitString into each bit array?

 That was the idea, yes.

> Or include all of functions of BitString to be mixed into BitArray?
>
> If the latter then:

 Well it seems like it should work, that it should include a silent pointer to the original BitArray (container) similar like delegates do for functions. Odd that it doesn't.  Bug?

 Seems with the problem on that, I'll do a different approach.

 BitArray(StorageType) {
   StorageType memory;

   //now we do memory.length =, and memory.rawBulk[] for direct access, may
   //add opIndex removing the need to know rawBulk at all
 }

 StorageType in this case should contain 'rawBulk', and the storage type handles the memory allocation, giving access to members no different than an array. I have two storage types i've written that hopefully handle all cases:

//storage types for BitArrays
struct Dynamic {
  size_t[] rawBulk;
  alias rawBulk this;
}

struct Fixed(int maxBits) {
  size_t[maxBits / (size_t.sizeof * 8)] rawBulk;
  int _length;    //fixed sizes are usually going to be rather small

  int length() @property const @safe pure nothrow {
      return _length;
  }
  void length(int setSize) @property const @safe pure nothrow {
      assert(setSize < rawBulk.length);
      _length = setSize;
  }
  void reserve(size_t resSize) {} //fixed
}

 Now when modifying memory referencing just treat memory as an array, access the raw data via rawBulk (likely will remove named access and go with opIndex). This removes the need for several workarounds I have currently. while trying to handle compact/allocated memory.

11-Jan-2013 00:33, Era Scarecrow пишет:
> On Thursday, 10 January 2013 at 20:11:38 UTC, Dmitry Olshansky wrote:
>> You want to mixin a definition of a inner struct BitString into each
>> bit array?
>
>   That was the idea, yes.
>
>> Or include all of functions of BitString to be mixed into BitArray?
>>
>> If the latter then:
>
>   Well it seems like it should work, that it should include a silent
> pointer to the original BitArray (container) similar like delegates do
> for functions. Odd that it doesn't.  Bug?

It's only for classes AFAIK. Inner structs of structs (LOL) don't have it.

>
>   Seems with the problem on that, I'll do a different approach.
>
>   BitArray(StorageType) {
>     StorageType memory;
>
>     //now we do memory.length =, and memory.rawBulk[] for direct access,
> may
>     //add opIndex removing the need to know rawBulk at all
>   }
>
>   StorageType in this case should contain 'rawBulk', and the storage
> type handles the memory allocation, giving access to members no
> different than an array. I have two storage types i've written that
> hopefully handle all cases:
>
> //storage types for BitArrays
> struct Dynamic {
>    size_t[] rawBulk;
>    alias rawBulk this;
> }
>
> struct Fixed(int maxBits) {
>    size_t[maxBits / (size_t.sizeof * 8)] rawBulk;
>    int _length;    //fixed sizes are usually going to be rather small
>
>    int length() @property const @safe pure nothrow {
>        return _length;
>    }
>    void length(int setSize) @property const @safe pure nothrow {
>        assert(setSize < rawBulk.length);
>        _length = setSize;
>    }
>    void reserve(size_t resSize) {} //fixed
> }
>
>   Now when modifying memory referencing just treat memory as an array,
> access the raw data via rawBulk (likely will remove named access and go
> with opIndex). This removes the need for several workarounds I have
> currently. while trying to handle compact/allocated memory.

Sounds good and seductively simple.

-- 
Dmitry Olshansky

On Thursday, 10 January 2013 at 21:37:22 UTC, Dmitry Olshansky wrote:
> It's only for classes AFAIK. Inner structs of structs (LOL) don't have it.

 Why not? I don't see a reason why not personally. Umm maybe I do... the outer struct becomes referenced to S2, so...

 struct S {
   int x;
   struct S2 {
     int getX(){return x;}
   }
   S2 s2;
 }

 S.S2 func(){
   S s;
   return s.s2;
 }

 auto x = func();
 writeln(x.getX()); //prints garbage? Or access violation.

 If func had used new on s, then it would have worked... Yeah I see the problem now. The only way that would work is if S2 is never allowed to be passed outside a function, and on copying the new hidden pointer is updated to the new location. That makes sense. Maybe something walter will consider.


> Sounds good and seductively simple.

 Yeah I hope so. We'll see, that's the design I'll go for. I'll let you know how it goes; Should at least simplify the code and remove the need for bitfields.

 Well some minor update. From the looks of how it is going to be set up, it is almost entirely a template. Consider you have BitArray!(Fixed!(1024)), vs BitArray!(Dynamic), in order for one to copy to the other template functions are needed. Override one of them, and now i have to define it to handle all slice and BitArrays as template functions too. not horrible, but has it's downsides.

 Also as for ranges/slices; Some need their contents const while others don't care. So..

//slice is also a range
struct BitArraySlice(BA, bool isConst){}


 Got a lot of work to do, so I wouldn't expect anything for a couple weeks.

 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.

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

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?

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

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

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.