www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Implicit conversions for AA keys

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
Currently my AA implementation supports automatic key conversion (as
suggested by Andrei), for example:

	AA!(string,int) aa;
	char[] key = "abc".dup;
	aa[key] = 1;		// automatically converts char[] to
				// string via .idup

The way this is implemented is by allowing any input key type that can
implicitly convert to the actual key type, or types that can be
converted via .idup or slicing (to support using dynamic arrays for
static array keys). While this is all nice and general, it is also *too*
general:

	AA!(double,int) aa;
	int x = 1;
	aa[x] = 1;		// <---PROBLEM

The catch here is that int implicitly converts to double, *but* the
underlying representation is different, so int.toHash() !=
double.toHash(). But currently the above code compiles, but computes the
wrong hash value for the key, so that aa[1u] and aa[1.0f] are distinct
entries, which is nonsensical.

So the question is, how to restrict input key types so that we only
allow input keys that have the same representation as the AA key type?

A more advanced solution is to perform representation conversions (e.g.,
int -> double) first, and *then* compute the hash, and *then* use .idup
or slicing if the input key needs to be duplicated (in the first example
above, the char[] is not .idup'd until a new entry actually needs to be
created).

However, I don't know how to check for such cases using
function/template signature constraints, besides hard-coding all known
conversions (which is ugly, fragile, and hard to maintain). IOW, if
is(InputType : KeyType) is true, then how do I tell whether the implicit
conversion involves a representation conversion, or merely a const
conversion (e.g., immutable->const or unqualified->const)?


T

-- 
This is a tpyo.
Mar 23 2012
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
Why do you not just do the conversion and then compute the hash, even if 
the representation is the same?
Mar 23 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/23/2012 07:10 PM, H. S. Teoh wrote:
 On Fri, Mar 23, 2012 at 07:01:46PM +0100, Timon Gehr wrote:
 Why do you not just do the conversion and then compute the hash, even
 if the representation is the same?

Because Andrei says that the .idup shouldn't be performed unless it's necessary (e.g., you should be able to lookup char[] in a string-keyed AA without incurring the overhead of an .idup each time). The conversion is not needed if the hash computation doesn't change and we don't need to create a new entry. T

That does not apply to your example with double and int. (I'd argue that actually the other overload should be chosen in that case, because the conversion is implicit) For implicit .idup, one solution would be to compare immutable(Key) and immutable(T). If they are the same, then the representation is the same.
Mar 23 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/23/12 12:54 PM, H. S. Teoh wrote:
 Currently my AA implementation supports automatic key conversion (as
 suggested by Andrei), for example:

 	AA!(string,int) aa;
 	char[] key = "abc".dup;
 	aa[key] = 1;		// automatically converts char[] to
 				// string via .idup

 The way this is implemented is by allowing any input key type that can
 implicitly convert to the actual key type, or types that can be
 converted via .idup or slicing (to support using dynamic arrays for
 static array keys). While this is all nice and general, it is also *too*
 general:

 	AA!(double,int) aa;
 	int x = 1;
 	aa[x] = 1;		//<---PROBLEM

Let's see what requirements need to be satisfied by []. Say k is a value of the key type and x is a value being looked up. First, we need to be able to evaluate k == x. So the types must be comparable. Second, we need if x == k, then hash(k) == hash(x). This is tricky in general, but let's say we can approximate to the compile-time requirement that the hash function resolves to the same entity for both typeof(x) and typeof(k). This would rule out e.g. int and double but would leave char[] and string. To include int and double correctly, we'd amend the second rule as follows. If typeof(x) converts implicitly to typeof(k), then use hash(cast(typeof(k)) x) instead of hash(x). This makes it possible to look up for an int in a hash of doubles, but not vice versa, which is great. These two are sufficient for lookup. For store, we also need the third rule, which is to!(typeof(k))(x) must compile and run. Andrei
Mar 23 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/23/12 1:48 PM, H. S. Teoh wrote:
 How do we check at compile time whether the hash function resolves to
 the same entity?

int fun(T)(T x) { return 42; } void main() { static assert(&fun!int != &fun!double); } This actually reveals a compiler bug: Assertion failed: (d->purity != PUREfwdref), function typeMerge, file cast.c, line 1909. A cast would be needed anyway because they have different types, too. Anyway upon more thinking maybe this is too restrictive a rule. It won't catch e.g. functions that are, in fact, identical, but come from distinct instantiations. So perhaps you need some conservative approximation, i.e. look if the two types are qualified versions of the same type and then assume they hash the same.
 To include int and double correctly, we'd amend the second rule as
 follows. If typeof(x) converts implicitly to typeof(k), then use
 hash(cast(typeof(k)) x) instead of hash(x). This makes it possible
 to look up for an int in a hash of doubles, but not vice versa,
 which is great.

OK.
 These two are sufficient for lookup. For store, we also need the
 third rule, which is to!(typeof(k))(x) must compile and run.

Isn't this already required by the hash lookup? Or is casting different from to!X, in which case it might be messy to import the relevant parts of phobos into druntime. :-/

Casting is very different from to, and useless for your purposes. You must use to. Andrei
Mar 23 2012
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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 ?
Mar 23 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 23 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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]. I don't think that is desirable. I even think implicit .idup may be overkill.
Mar 23 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 23 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Mar 23 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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); }
Mar 23 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Mar 24 2012
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Mar 24 2012
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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)){
Mar 24 2012
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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?
Mar 24 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/23/12 2:30 PM, H. S. Teoh wrote:
 Wouldn't that require moving std.conv into druntime?  And std.conv does
 depend on std.traits as well...

Not sure how it's best to address this. Andrei
Mar 23 2012