View mode: basic / threaded / horizontal-split · Log in · Help
March 23, 2012
Re: Implicit conversions for AA keys
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
March 23, 2012
Re: Implicit conversions for AA keys
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.
March 23, 2012
Re: Implicit conversions for AA keys
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);
}
March 24, 2012
Re: Implicit conversions for AA keys
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
March 24, 2012
Re: Implicit conversions for AA keys
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.
March 24, 2012
Re: Implicit conversions for AA keys
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.
March 24, 2012
Re: Implicit conversions for AA keys
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)){
March 24, 2012
Re: Implicit conversions for AA keys
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
March 24, 2012
Re: Implicit conversions for AA keys
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"...
March 24, 2012
Re: Implicit conversions for AA keys
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?
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home