On 3/23/12 3:23 PM, Timon Gehr wrote:
> On 03/23/2012 09:05 PM, Andrei Alexandrescu wrote:
>> On 3/23/12 2:28 PM, Timon Gehr wrote:
>>> On 03/23/2012 08:06 PM, Andrei Alexandrescu wrote:
>>>>
>>>> Casting is very different from to, and useless for your purposes. You
>>>> must use to.
>>>>
>>>>
>>>> Andrei
>>>
>>> druntime mustn't depend on Phobos, and I don't see why it is necessary.
>>> What kind of functionality do you want to provide that depends on
>>> std.conv.to ?
>>
>> Casting from char[] to string is not what you want, and .idup is
>> specific to arrays. There must be one coherent method of "truely"
>> converting across types, and std.conv.to is the closest I can think of.
>>
>> Andrei
>
> This will statically allow looking up an int in a T[string].

No, because of the other rules.

Andrei

On 03/23/2012 09:43 PM, Andrei Alexandrescu wrote:
> On 3/23/12 3:23 PM, Timon Gehr wrote:
>> On 03/23/2012 09:05 PM, Andrei Alexandrescu wrote:
>>> On 3/23/12 2:28 PM, Timon Gehr wrote:
>>>> On 03/23/2012 08:06 PM, Andrei Alexandrescu wrote:
>>>>>
>>>>> Casting is very different from to, and useless for your purposes. You
>>>>> must use to.
>>>>>
>>>>>
>>>>> Andrei
>>>>
>>>> druntime mustn't depend on Phobos, and I don't see why it is necessary.
>>>> What kind of functionality do you want to provide that depends on
>>>> std.conv.to ?
>>>
>>> Casting from char[] to string is not what you want, and .idup is
>>> specific to arrays. There must be one coherent method of "truely"
>>> converting across types, and std.conv.to is the closest I can think of.
>>>
>>> Andrei
>>
>> This will statically allow looking up an int in a T[string].
>
> No, because of the other rules.
>
> Andrei

I see. An alternative solution (one that does not make AAs depend on Phobos and is more slick) would be to use the const qualified key type for lookup (that is what const is for) and to have immutable keys for stores. For types that define .idup, there would be another overload of opIndexAssign that can take a const qualified key.

On 03/23/2012 10:07 PM, Timon Gehr wrote:
>
> I see. An alternative solution (one that does not make AAs depend on
> Phobos and is more slick) would be to use the const qualified key type
> for lookup (that is what const is for) and to have immutable keys for
> stores. For types that define .idup, there would be another overload of
> opIndexAssign that can take a const qualified key.

Proof of concept:

// ctfe-able simple and stupid replace
string replace(string str, string from, string to){
	string r = "";
	foreach(i; 0..str.length){
		if(i+from.length<=str.length &&
		   str[i..i+from.length]==from){
			r~=to;
			i+=from.length-1;
		}else r~=str[i];
	}
	return r;
}

template getConstQual(T){ // hack
	static if(is(T==string)) alias const(char)[] getConstQual;
	else alias const(typeof(mixin(`(`~T.stringof.
	  replace("immutable","const")~`).init`))) getConstQual;
}

int numidup = 0;

struct AA(Key, Value) if(is(Key:immutable(Key))){
	Value[Key] payload;
	auto opIndex(getConstQual!Key k){return payload[cast(immutable)k];}
	auto opIndexAssign(Value v, Key k){return payload[cast(immutable)k]=v;}
	static if(is(typeof(getConstQual!Key.init.idup))){
		auto opIndexAssign(Value v, getConstQual!Key k){
			if(auto p = (cast(immutable)k) in payload) return *p=v;
			numidup++;
			return payload[k.idup]=v;
		}
	}
}

void main() {
	AA!(string, int) aa;
	aa["123"] = 123;
	char[3] ch = "123";
	assert(aa[ch] == 123);
	ch[1]='3';
	assert(numidup == 0);
	aa[ch]=133;
	assert(numidup == 1);
	assert(aa["133"]==133);
	ch[0]='3';
	assert(aa["133"]==133);
	assert(numidup == 1);
}

On Fri, Mar 23, 2012 at 10:53:10PM +0100, Timon Gehr wrote:
> On 03/23/2012 10:07 PM, Timon Gehr wrote:
> >
> >I see. An alternative solution (one that does not make AAs depend on Phobos and is more slick) would be to use the const qualified key type for lookup (that is what const is for) and to have immutable keys for stores. For types that define .idup, there would be another overload of opIndexAssign that can take a const qualified key.
> 
> Proof of concept:
[...]

Hmm. I decided that perhaps the full-fledged std.conv.to is a bit of an overkill, so I revised the AA code to compromise between needing std.conv.to and still deliver what Andrei wants.

Basically, I have a template that defines AA key compatibility, where compatibility means that given an AA with key type Key and a key k of type K, k is considered compatible if:

- k==K.init is valid (i.e. they can be compared);
- (At least) one of the following holds:
   - is(immutable(K) == immutable(Key))
   - is(typeof(k.idup) == Key)
   - Key is a static array of length N, and k[0..N] is valid.
   - is(K : Key)

For the first case (is(immutable(K)==immutable(Key)), which means K and
Key have the "same representation") and the second case (K.idup yields
Key), we can basically assume that K.toHash() is consistent with
Key.toHash(). When creating a new entry, we just assign K to Key, or
K.idup to Key as necessary.

For the third case, we can just slice the input array when comparing or assigning to a new entry (this will throw an Error if the input array has the wrong length). I decided to be permissive and compute the hash on the entire array, if the length doesn't match it will fail anyway, so it's OK to lookup an array of mismatching length in an AA with static array keys, as long as you don't try to store the key into it.

Lastly, if is(K : Key) holds but none of the others do, then convert the key before computing the hash:

	Key key = k;	// implicit conversion
	return key.toHash();

This ensures the int->double conversion works correctly. Creating a new entry can just use straight assignment, due to the implicit conversion.

I've added these changes on github in a branch:

	https://github.com/quickfur/New-AA-implementation/tree/keyconv

Andrei, please try it out and see if it works on the cases you have in mind. :-)


T

-- 
Try to keep an open mind, but not so open your brain falls out. -- theboz

On 03/24/2012 01:20 AM, H. S. Teoh wrote:
> On Fri, Mar 23, 2012 at 10:53:10PM +0100, Timon Gehr wrote:
>> On 03/23/2012 10:07 PM, Timon Gehr wrote:
>>>
>>> I see. An alternative solution (one that does not make AAs depend on
>>> Phobos and is more slick) would be to use the const qualified key type
>>> for lookup (that is what const is for) and to have immutable keys for
>>> stores. For types that define .idup, there would be another overload of
>>> opIndexAssign that can take a const qualified key.
>>
>> Proof of concept:
> [...]
>
> Hmm. I decided that perhaps the full-fledged std.conv.to is a bit of an
> overkill, so I revised the AA code to compromise between needing
> std.conv.to and still deliver what Andrei wants.
>
> Basically, I have a template that defines AA key compatibility, where
> compatibility means that given an AA with key type Key and a key k of
> type K, k is considered compatible if:
>
> - k==K.init is valid (i.e. they can be compared);
> - (At least) one of the following holds:
>     - is(immutable(K) == immutable(Key))
>     - is(typeof(k.idup) == Key)
>     - Key is a static array of length N, and k[0..N] is valid.
>     - is(K : Key)
>
> For the first case (is(immutable(K)==immutable(Key)), which means K and
> Key have the "same representation") and the second case (K.idup yields
> Key), we can basically assume that K.toHash() is consistent with
> Key.toHash(). When creating a new entry, we just assign K to Key, or
> K.idup to Key as necessary.
>
> For the third case, we can just slice the input array when comparing or
> assigning to a new entry (this will throw an Error if the input array
> has the wrong length). I decided to be permissive and compute the hash
> on the entire array, if the length doesn't match it will fail anyway, so
> it's OK to lookup an array of mismatching length in an AA with static
> array keys, as long as you don't try to store the key into it.
>
> Lastly, if is(K : Key) holds but none of the others do, then convert the
> key before computing the hash:
>
> 	Key key = k;	// implicit conversion
> 	return key.toHash();
>
> This ensures the int->double conversion works correctly. Creating a new
> entry can just use straight assignment, due to the implicit conversion.
>
> I've added these changes on github in a branch:
>
> 	https://github.com/quickfur/New-AA-implementation/tree/keyconv
>
> Andrei, please try it out and see if it works on the cases you have in
> mind. :-)
>
>
> T
>

This solution creates unnecessary template bloat for every implicit conversion, duplicates compiler logic, and I think it does not work correctly because of other issues. I have refined my proof of concept.

Consider this:

template getConstQual(T){
	static if(is(T _ == immutable(U),U)) alias const(getConstQual!U) r;
	else static if(is(T _ == const(U),U)) alias const(getConstQual!U) r;
	else static if(is(T _ == inout(U),U)) alias const(getConstQual!U) r;
	else static if(is(T _ == shared(U),U)) alias const(getConstQual!U) r;
	else static if(is(T _ == U[],U)) alias const(getConstQual!U[]) r;
	else static if(is(T _ == U*,U)) alias const(getConstQual!U*) r;
	else alias const(T) r;
	alias r getConstQual;
}

struct AA(Key, Value) if(is(Key==immutable(Key))){
	Value[Key] payload;
	auto opIndex(getConstQual!Key k){return payload[cast(immutable)k];}
	auto opIndexAssign(Value v, Key k){return payload[cast(immutable)k]=v;}
	static if(is(typeof(getConstQual!Key.init.idup):Key)){
		auto opIndexAssign(Value v, getConstQual!Key k){
			if(auto p = (cast(immutable)k) in payload) return *p=v;
			return this[k.idup]=v;
		}
	}
}
template AA(Key, Value) if(!is(Key==immutable(Key))&&is(Key:immutable(Key))){
	alias AA!(immutable(Key), Value) AA;
}


void main() {
	AA!(immutable(double)[], int) aa;
	aa[[1.0,2.0,3.0]]=2; // works, with no .idup!
	aa[[1,2,3]]=2;       // ditto
	AA!(dstring,int) ab;
	ab["123"]=2;         // just works
	char[3] c= "123";
	AA!(short,int) ac;
	ac[2]=2;             // so does this
}

This nicely resolves all the implementation problems you have encountered/will encounter, because it does not rely on IFTI. I think you should follow this strategy.

On 03/24/2012 12:34 PM, Timon Gehr wrote:
> else static if(is(T _ == shared(U),U)) alias const(getConstQual!U) r;

should be

else static if(is(T _ == shared(U),U)) alias shared(const(getConstQual!U)) r;

But it does not matter for the AA implementation because it only uses getConstQual with immutable key types.

On 03/24/2012 12:34 PM, Timon Gehr wrote:
>      static if(is(typeof(getConstQual!Key.init.idup):Key)){

Better:

static if(is(typeof(getConstQual!Key.init.idup):Key) && !is(getConstQual!Key: Key)){

On Sat, Mar 24, 2012 at 12:34:56PM +0100, Timon Gehr wrote:
> On 03/24/2012 01:20 AM, H. S. Teoh wrote:
[...]
> >Hmm. I decided that perhaps the full-fledged std.conv.to is a bit of an overkill, so I revised the AA code to compromise between needing std.conv.to and still deliver what Andrei wants.
[...]
> This solution creates unnecessary template bloat for every implicit conversion, duplicates compiler logic, and I think it does not work correctly because of other issues. I have refined my proof of concept.
[...]

OK, I'll make a branch and give it a try.


> This nicely resolves all the implementation problems you have encountered/will encounter, because it does not rely on IFTI. I think you should follow this strategy.
[...]

Good idea, IFTI's limitations have been giving me a lot of woes recently.


T

-- 
Claiming that your operating system is the best in the world because more people use it is like saying McDonalds makes the best food in the world. -- Carl B. Constantine

On Sat, Mar 24, 2012 at 12:34:56PM +0100, Timon Gehr wrote: [...]
> This solution creates unnecessary template bloat for every implicit conversion, duplicates compiler logic, and I think it does not work correctly because of other issues. I have refined my proof of concept.
[...]

OK, I've implemented your changes in a branch, but found the following problems:

- Doesn't work with const AA/array keys, e.g.
    AA!(string[const int[]]) aa;
    AA!(string[const AA!(int[int])]) meta;
  (The AA!() template is basically just syntactic sugar that uses
  reflection to map "real" AA types into AssociativeArray templates,
  courtesy of Andrej Mitovic.)

- Doesn't work with static array keys with dynamic array lookups.

But I think I like your approach better. Creating a new template instantiation for every implicit conversion leads to lots of code bloat, and also breaks in many places due to bugs in IFTI. Using non-template methods takes advantage of the compiler's implicit conversions, and where necessary we can just add overloads for stuff like .idup, and probably slicing for the static array key case.

One concern, though: wouldn't cast(immutable) break immutable
guarantees? For example:

	class C {
		int x;
		hash_t toHash() { ... }
	}

	AA!(int[C]) aa;
	auto c = new C;
	c.x = 123;
	const d = c;	// convert mutable C to const(C)
	aa[d] = 123;	// const(C) casted into immutable(C)
	c.x = 321;	// uh-oh: immutability broken


T

-- 
I'm still trying to find a pun for "punishment"...

On 03/24/2012 05:14 PM, H. S. Teoh wrote:
> On Sat, Mar 24, 2012 at 12:34:56PM +0100, Timon Gehr wrote:
> [...]
>> This solution creates unnecessary template bloat for every implicit
>> conversion, duplicates compiler logic, and I think it does not work
>> correctly because of other issues. I have refined my proof of
>> concept.
> [...]
>
> OK, I've implemented your changes in a branch, but found the following
> problems:
>
> - Doesn't work with const AA/array keys, e.g.
>      AA!(string[const int[]]) aa;
>      AA!(string[const AA!(int[int])]) meta;
>    (The AA!() template is basically just syntactic sugar that uses
>    reflection to map "real" AA types into AssociativeArray templates,
>    courtesy of Andrej Mitovic.)
>

I assumed the key type needs to be immutable. If you want to allow instantiation with non-immutable key type, this should do it:

template AA(Key, Value) if(!is(Key==immutable(Key))){
    alias AA!(immutable(Key), Value) AA;
}

> - Doesn't work with static array keys with dynamic array lookups.
>

Doesn't that need some extra logic in order to be efficient anyway? You could detect static array keys and provide appropriate overloads in a static if declaration.

> But I think I like your approach better. Creating a new template
> instantiation for every implicit conversion leads to lots of code bloat,
> and also breaks in many places due to bugs in IFTI. Using non-template
> methods takes advantage of the compiler's implicit conversions, and
> where necessary we can just add overloads for stuff like .idup, and
> probably slicing for the static array key case.
>

This sounds good.

> One concern, though: wouldn't cast(immutable) break immutable
> guarantees? For example:
>
> 	class C {
> 		int x;
> 		hash_t toHash() { ... }
> 	}
>
> 	AA!(int[C]) aa;
> 	auto c = new C;
> 	c.x = 123;
> 	const d = c;	// convert mutable C to const(C)
> 	aa[d] = 123;	// const(C) casted into immutable(C)
> 	c.x = 321;	// uh-oh: immutability broken
>
>
> T
>

cast(immutable) is only there to make it compile with built-in AAs. Your code should not need to perform it?