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 reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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

-- 
Lawyer: (n.) An innocence-vending machine, the effectiveness of which
depends on how much money is inserted.
Mar 23 2012
parent reply 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
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Mar 23, 2012 at 07:18:05PM +0100, Timon Gehr wrote:

 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.




[...]

 
 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)


Sorry, I didn't understand that... which other overload?



 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.


Excellent idea! I didn't think about using qualifier collapsing to check
for representation equivalence. Thanks! :-)

I think this issue is now solvable: if a key is implicitly convertible
to the AA key but it's *not* equivalent, then convert it first.
Otherwise, convert it later via .idup or some analogous mechanism.

	template isEquiv(T,U) {
		enum isEquiv = is(immutable(T)==immutable(U));
	}
	...
	static if (is(InputKey : Key) && !isEquiv!(InputKey,Key))
		// convert now
	else
		// convert later


T

-- 
The irony is that Bill Gates claims to be making a stable operating
system and Linus Torvalds claims to be trying to take over the world. --
Anonymous
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


[snip]

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 "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Mar 23, 2012 at 01:31:28PM -0500, Andrei Alexandrescu wrote:
[...]

 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.


How do we check at compile time whether the hash function resolves to
the same entity?



 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. :-/


T

-- 
"A man's wife has more power over him than the state has." -- Ralph Emerson
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 "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
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 next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
Mar 24 2012
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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"...
Mar 24 2012
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 reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Mar 23, 2012 at 02:06:15PM -0500, Andrei Alexandrescu wrote:
[...]

 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.


OK. Would the following be enough?

	template isEquiv(T,U) {
		enum isEquiv = is(immutable(T)==immutable(U));
	}


[...]

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.


[...]

Wouldn't that require moving std.conv into druntime?  And std.conv does
depend on std.traits as well...


T

-- 
Without outlines, life would be pointless.
Mar 23 2012
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