I seem to have found the underlying cause of the failures of sort and associative arrays to work 'properly' with struct or class types.

Currently, the implementations are rather down and dirty, and rely on TypeInfo.  The problems with it are:
- no TypeInfo is automatically generated for struct types, leading to the linker errors
- class types just use the functions of TypeInfo_C, which in turn use Object.opEquals(Object) and Object.opCmp(Object) rather than self-specific versions.

But for any type, the behaviour of sort and AAs ought to be consistent with the behaviour of the comparison operators, at least whenever the types involved are the same.

I therefore suggest that we do away with the current implementations using TypeInfo and rewrite them to use templates.  This should be easy to do, as it only means translating existing algorithms into the D template system.  This means that we can use the type's comparison operators directly, and so the correct comparison is always carried out.

This raises a few questions.  When this is done, how much of TypeInfo is really still needed?  The very fact that sort and AAs are currently implemented in terms of TypeInfo seems to reflect the fact (?) that templates were a more recent addition to the language.  Obviously we still need TypeInfo itself for such things as typeid and hence variadic functions.  But can we sensibly deprecate (if not remove) TypeInfo.equals and TypeInfo.compare?

This would enable us to deprecate the Object.opCmp(Object) wart, and then to hook up separate AA implementations for comparable and non-comparable key types.  It would also enable the compiler to catch attempts to compare incomparable objects, something that C++ manages without difficulty, and Java manages to an extent.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

"Stewart Gordon" <smjg_1998@yahoo.com> wrote in message news:ccbd2c$1m30$1@digitaldaemon.com...
> I seem to have found the underlying cause of the failures of sort and associative arrays to work 'properly' with struct or class types.
>
> Currently, the implementations are rather down and dirty, and rely on
> TypeInfo.  The problems with it are:
> - no TypeInfo is automatically generated for struct types, leading to
> the linker errors
> - class types just use the functions of TypeInfo_C, which in turn use
> Object.opEquals(Object) and Object.opCmp(Object) rather than
> self-specific versions.
>
> But for any type, the behaviour of sort and AAs ought to be consistent with the behaviour of the comparison operators, at least whenever the types involved are the same.
>
> I therefore suggest that we do away with the current implementations using TypeInfo and rewrite them to use templates.  This should be easy to do, as it only means translating existing algorithms into the D template system.  This means that we can use the type's comparison operators directly, and so the correct comparison is always carried out.
>
> This raises a few questions.  When this is done, how much of TypeInfo is really still needed?  The very fact that sort and AAs are currently implemented in terms of TypeInfo seems to reflect the fact (?) that templates were a more recent addition to the language.  Obviously we still need TypeInfo itself for such things as typeid and hence variadic functions.  But can we sensibly deprecate (if not remove) TypeInfo.equals and TypeInfo.compare?
>
> This would enable us to deprecate the Object.opCmp(Object) wart, and then to hook up separate AA implementations for comparable and non-comparable key types.  It would also enable the compiler to catch attempts to compare incomparable objects, something that C++ manages without difficulty, and Java manages to an extent.

I want to be unable to compare uncomparable objects too!

>
> Stewart.
>
> --
> My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:

> I seem to have found the underlying cause of the failures of sort and associative arrays to work 'properly' with struct or class types.
> 
> Currently, the implementations are rather down and dirty, and rely on
> TypeInfo.  The problems with it are:
> - no TypeInfo is automatically generated for struct types, leading to
> the linker errors
> - class types just use the functions of TypeInfo_C, which in turn use
> Object.opEquals(Object) and Object.opCmp(Object) rather than
> self-specific versions.
> 
> But for any type, the behaviour of sort and AAs ought to be consistent with the behaviour of the comparison operators, at least whenever the types involved are the same.
> 
> I therefore suggest that we do away with the current implementations using TypeInfo and rewrite them to use templates.  This should be easy to do, as it only means translating existing algorithms into the D template system.  This means that we can use the type's comparison operators directly, and so the correct comparison is always carried out.
> 
> This raises a few questions.  When this is done, how much of TypeInfo is really still needed?  The very fact that sort and AAs are currently implemented in terms of TypeInfo seems to reflect the fact (?) that templates were a more recent addition to the language.  Obviously we still need TypeInfo itself for such things as typeid and hence variadic functions.  But can we sensibly deprecate (if not remove) TypeInfo.equals and TypeInfo.compare?
> 
> This would enable us to deprecate the Object.opCmp(Object) wart, and then to hook up separate AA implementations for comparable and non-comparable key types.  It would also enable the compiler to catch attempts to compare incomparable objects, something that C++ manages without difficulty, and Java manages to an extent.
> 
> Stewart.
> 


Not a bad idea.
Off the top of my head one difference would be on code size - not that the
AA or sorting algorithms are very big. Is D (or the linker or whatever)
smart enough to use only one version of a template when the types are
reference types? One benefit of TypeInfo is that it factors out the
"dynamic" part of the algorithm nicely.
I wonder if there is a performance benefit to using templates, too, since
the hashing and comparisons can be inlined.

So if I understand you correctly if Foo is some class then writing something like

 int[Foo] x;
 x[y] = 10;

would translate to

 _AA!(int,Foo).T x;
 *(_AA!(int,Foo).get(x,y)) = 10;

where _AA is

 template _AA(Value_T, Key_T) {
   struct aaA { ... plug in aaA from src/phobos/internal/aaA.d }
   typedef aaA*[] T;
   Value_T* get(T x, Key_T y) {
     ... plug in code from src/phobos/internal/aaA.d
         but replace calls to key TypeInfo with Key_T
   }
 }