generic arrays

R

Roedy Green

Why does Java have a problem with:

// You cannot use "new" to allocate an array of T where T is a generic
type, e.g. <T>.
// Recall that even if it did, it would still allocate an array of
Objects at run time.
T[] things = new T[10];


Why does it not just generate the code for:

Object[] things = new Object[10];
 
J

Joshua Cranmer

Roedy said:
Why does Java have a problem with:

// You cannot use "new" to allocate an array of T where T is a generic
type, e.g. <T>.
// Recall that even if it did, it would still allocate an array of
Objects at run time.
T[] things = new T[10];

The short answer:
Generics in Java, at present, is almost entirely a compile-time hack.
Anything which would have to be passed down into runtime cannot be done
without warning (e.g., casting, instanceof, new).
Why does it not just generate the code for:

Object[] things = new Object[10];

We were promised that things would be an array of T's. Communication
into the outside world would pass the runtime array store check (i.e.,
the array is initialized as an Object[]) but would violate the type safety.

public class GenericTest<T> {
private T[] array;

public GenericTest(int count) {
array = new T[count];
}

public void set(int place, T x) {
array[place] = x;
}

public T get(int place) {
return array[place];
}

public void malicious(Object insertee) {
Object[] evil = (Object[])array;
evil[0] = insertee;
}

public static void main(String... args) {
GenericTest<String> test = new GenericTest<String>(1);
test.malicious(new Object());
System.out.println(test.get(0) instanceof String);
}
}

Should new arrays be legal, this code would be forced to run with
unexpected output. The array is of type Object[], so inserting an Object
does not cause an ArrayStoreException when it should--it needs to be of
type T.

The process by which this issue would be fixed is called
reification--pushing generics down to the level of runtime, probably
with the addition of a few instructions to the JVM (anewarray, new, and
similar instructions having variants that pop classes from the stack is
my bet). It is also, IMO, the most needed change to Java.
 
R

Roedy Green

It is also, IMO, the most needed change to Java.

What sort of changes would happen to the syntax? The problem now is
generics are so complicated they are more likely to introduce rather
than catch errors as soon as you start fiddling with ? extends etc.
 
M

Mike Schilling

Roedy said:
Why does Java have a problem with:

// You cannot use "new" to allocate an array of T where T is a
generic
type, e.g. <T>.
// Recall that even if it did, it would still allocate an array of
Objects at run time.
T[] things = new T[10];


Why does it not just generate the code for:

Object[] things = new Object[10];

You can do

T[] things = (T[])new Object[10];

(ArrayList.java does this.) I don't mind being reminded that T[] is a
lie.
 
R

Roedy Green

T[] things = (T[])new Object[10];

I still get a warning when I do that.
"unchecked cast".

I guess the problem is it can't really do anything to check.

Also (String[]) new Object[10]; would always fail.

There is the complicating matter of an Object[] where all elts are
strings and String[] when all elts are Strings.
 
M

Mike Schilling

Roedy said:
T[] things = (T[])new Object[10];

I still get a warning when I do that.
"unchecked cast".

Yup. No way around that. Using an array generically is inherently
unsafe.
I guess the problem is it can't really do anything to check.

Also (String[]) new Object[10]; would always fail.

There is the complicating matter of an Object[] where all elts are
strings and String[] when all elts are Strings.

All true. What exactly is it that you're trying to do? If it's
return an array of the correct element type to the caller, you'd have
to do something like pass the class type in and use reflection to
create the array.
 
O

Owen Jacobson

Roedy said:
  T[] things = (T[])new Object[10];
I still get a warning when I do that.
"unchecked cast".

Yup.  No way around that.  Using an array generically is inherently
unsafe.


I guess the problem is it can't really do anything to check.
Also  (String[]) new Object[10]; would always fail.
There is the complicating matter of an Object[] where all elts are
strings and String[] when all elts are Strings.

All true.  What exactly is it that you're trying to do?  If it's
return an array of the correct element type to the caller, you'd have
to do something like pass the class type in and use reflection to
create the array.

Wild guess: Roedy's implementing a library of sort algorithms, using
generics (or adapting an existing one to be "generics correct" for
some value of "correct") and is trying to implement a non-in-place
merge sort.

And therefore needs to be able to create holding arrays of the same
element type as the input array.

Roedy: have you thought about cloning the array you're passed and then
blanking it? You might also want to look at the source for
ArrayList.toArray(Object[]), which uses some reflective monkeying to
create an array "sufficiently large" and of the same element type as
the passed array, if the passed array is not large enough to hold the
list.

-o
 
O

Owen Jacobson

Roedy: have you thought about cloning the array you're passed and then
blanking it?  You might also want to look at the source for
ArrayList.toArray(Object[]), which uses some reflective monkeying to
create an array "sufficiently large" and of the same element type as
the passed array, if the passed array is not large enough to hold the
list.

Excuse the self-followup, here.

You cannot completely avoid casts, but you can use casts that are
verifiably correct. Consider:

String[] args = new String[0]; // No element to query.

Class<? extends String[]> c = args.getClass ();
Class<?> elt = c.getComponentType ();

We know from reading the code that elt is really String.class (which
is of type Class<String>), but the depicted bounds are the most strict
bounds available without casts through the Reflection API. It gets
better.

Object newArr = java.lang.reflect.Array.newInstance (elt, 8);

newArr is actually a String[], which we can verify by inspection or by
reflection, and you can cast the object to String[] and use it as one
from there on.

The same is true if we replace String throughout with T, which is a
generic type in this scope.

Part of the problem is that there is no type relationship between
String[] and String that can be expressed using generics type
constraints.

For completeness, here is a tested class which, given an array,
creates another array of the same element type and returns it as a T[]
rather than an Object[].

package com.unreasonent;

import java.lang.reflect.Array;

public class Arrays {
private Arrays () {
assert (false);
}

public static <T> Class<?> getElementClass (T[] array) {
return array.getClass ().getComponentType ();
}

@SuppressWarnings("unchecked")
public static <T> T[] createArrayLike (T[] original, int length) {
Class<?> eltType = getElementClass (original);
return (T[]) Array.newInstance (eltType, length);
}
}

-o
 
J

Joshua Cranmer

Roedy said:
What sort of changes would happen to the syntax?

AFAIK, none. The proposal I am thinking of would merely allow a generic
type (e.g. `T') wherever a class type is normally allowed (new T,
instanceof T, (T), etc.).
> The problem now is
generics are so complicated they are more likely to introduce rather
than catch errors as soon as you start fiddling with ? extends etc.

I have heard that wildcards were added very late in the generics problem
so that many of the usage and style issues were not fully worked out
before the release of Java 5. The moral of the story is to make sure all
features are thoroughly tested before decision time comes around.
 
L

Lew

Joshua said:
I have heard that wildcards were added very late in the generics problem
so that many of the usage and style issues were not fully worked out
before the release of Java 5. The moral of the story is to make sure all
features are thoroughly tested before decision time comes around.

Wildcards, and more generally covariant and contravariant generic types, were
in the white papers on which the whole generics scheme was built, though, and
from the very beginning.
 
R

Roedy Green

What exactly is it that you're trying to do?
I am doing a sort and I need an aux array of pointers to the things to
sort. Ideally it would be declared as String[] when I was sorting
String and Orange[] when I was sorting Oranges.
 
R

Roedy Green

Wild guess: Roedy's implementing a library of sort algorithms, using
generics (or adapting an existing one to be "generics correct" for
some value of "correct") and is trying to implement a non-in-place
merge sort.

And therefore needs to be able to create holding arrays of the same
element type as the input array.

You got it. You can see how well I have done
http://mindprod.com/products.html#SHELLSORT
http://mindprod.com/products.html#RADIXSORT
http://mindprod.com/products.html#HEAPSORT
http://mindprod.com/products.html#QUICKSORT

The code WORKS fine, it just bugs me to have a warning. I could use
annotations to suppress it, but that is cheating. It seems to there
should be a way to do this cleanly.

When I was a kid I used to sell mimeographed cheat sheets for five
cents each to my fellow students. I created mindless algorithms to
solve various sorts of problems. The teachers would plug them for me.
I composed them for math, physics, chemistry, genetics...

I would, as an adult, like to cook one up for generics. But first I
have to properly understand it myself. It is still pretty foggy,
despite quite a bit of reading.
 
R

Roedy Green

Roedy: have you thought about cloning the array you're passed and then
blanking it?

I thought of that, but have not yet tried it. I have many messy
little projects on my plate all half done.

It smells a bit too strongly of kludge. I can get the object that
way. But can I get the reference?
 
L

Lew

Roedy said:
I would, as an adult, like to cook one up for generics. But first I
have to properly understand it myself. It is still pretty foggy,
despite quite a bit of reading.

The fault, dear Brutus, lies not in our stars but in our Sun - that is, the
Java language monarchs, when they implemented generics as compile-time only.
This forced compromises in the mental model of generics. This also causes
"reification of generics" to be a very hot topic in Java.

If you regard "unchecked" warnings as manifestations of the core hack, you
might find your mental model easier to build.

There are games you can play with things like a Class <SomeType> as a
run-time-type marker to ease the pain of generics. Elimination of unchecked
warnings is often (not, I think still, always) possible with a rococo
assemblage of Class<? extends Whatever> and holder classes with generic methods.
 
M

Mike Schilling

Roedy said:
You got it. You can see how well I have done
http://mindprod.com/products.html#SHELLSORT
http://mindprod.com/products.html#RADIXSORT
http://mindprod.com/products.html#HEAPSORT
http://mindprod.com/products.html#QUICKSORT

The code WORKS fine, it just bugs me to have a warning. I could use
annotations to suppress it, but that is cheating. It seems to there
should be a way to do this cleanly.

But there isn't. And if it's any consolation to you,
java/util/ArrayList.java compiles with a warning too (or perhaps these
days it uses the annotation to remove it.)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,007
Latest member
obedient dusk

Latest Threads

Top