Java Generics: method signature for (deep copy of) generic Maps

Question

I have a few Maps that themselves again may contain Maps (of any type). I wrote a method with the signature:

public static <K,V> HashMap<K,V> deepCopyHashMap(HashMap<K,V> s);

However, I would now like to generalize this code to support Maps in general, but still return an object of the same type as the argument. So instead of:

public static <K,V> HashMap<K,V> deepCopyHashMap(HashMap<K,V> s);
public static <K,V> CheckedMap<K,V> deepCopyCheckedMap(CheckedMap<K,V> s);
public static <K,V> TreeMap<K,V> deepCopyTreeMap(TreeMap<K,V> s);
...
etc.

I would like something like this:

public static <K,V, M extends Map<K,V>> M<K,V> deepCopyMap(M<K,V> s);

However, this gives me:

Multiple markers at this line
- The type M is not generic; it cannot be parameterized with arguments <K, 
 V>
- The type M is not generic; it cannot be parameterized with arguments <K, 
 V>

How do I properly declare the method signature and still return an object of the correct type (without using reflection internally)?

For this project adding more dependencies is really not an option, so I would prefer a solution that does not rely on external libraries. Also, I have looked into the Cloneable interface, however with it being only a marker interface (with no implementation for Maps in general) it is not of much use to me.

---

Edit: For reference, this is my code for deep-copying nested HashMaps (code works properly):

public static <K,V> HashMap<K,V> deepCopyHashMap(HashMap<K,V> source){
    HashMap<K,V> result = new HashMap<K, V>();
    for(Map.Entry<K, V> entry : source.entrySet()){
        K k = entry.getKey();
        V v = entry.getValue();
        if(k instanceof HashMap<?,?>){
            k = (K) deepCopyHashMap((HashMap<?,?>) k);
        }
        if(v instanceof HashMap<?,?>){
            v = (V) deepCopyHashMap((HashMap<?,?>) v);
        }
        result.put(k, v);
    }
    return result;
}

---

Edit: Solutions

1. This is not an ideal solution.. It will fail if the there is no default constructor for the runtime type of the nested Map. I have tested it with nested HashMaps and the runtime type is correctly copied.

   @SuppressWarnings("unchecked")
   public static <K,V, M extends Map<K,V>> M deepCopyMap(M source) throws InstantiationException, IllegalAccessException{
       M result = (M) source.getClass().newInstance();
       for(Map.Entry<K, V> entry : source.entrySet()){
           K k = entry.getKey();
           V v = entry.getValue();
           if(k instanceof Map<?,?>){
               k = (K) deepCopyMap((Map<?,?>) k);
           }
           if(v instanceof Map<?,?>){
               v = (V) deepCopyMap((Map<?,?>) v);
           }
           result.put(k, v);
       }
       return result;
   }
   

2. This is much safer, but all the known types need to be listed explicitly:

   @SuppressWarnings("unchecked")
   public static <K,V, M extends Map<K,V>> M deepCopyMap(M source){
       M result;
       if(source instanceof HashMap){
           result = (M) new HashMap<K,V>();
       } else {
           //fail
       }
       // etc. add more types here
       for(Map.Entry<K, V> entry : source.entrySet()){
           K k = entry.getKey();
           V v = entry.getValue();
           if(k instanceof Map<?,?>){
               k = (K) deepCopyMap((Map<?,?>) k);
           }
           if(v instanceof Map<?,?>){
               v = (V) deepCopyMap((Map<?,?>) v);
           }
           result.put(k, v);
       }
       return result;
   }
   

Answer 1

Generic type parameters cannot be themself generic. Just drop the generic definition for M:

public static <K, V, M extends Map<K, V>> M deepCopyMap(M s);

The generic definition M<K, V> you stated is already implicit since the compiler must ensure that M extends Map<K, V> is true. Therefore, a definition M<K, V> is redundant.

As for creating a copy inside of the method it gets more complicated. Generic types improve type safety for the users of a generic method. However, inside the method you are just as clueless as if you used a non-generic method which took a raw Map as its argument. (You could of course further restict the generic types.)

After all, I would not recommend you the approach you suggest. You are suggesting the user of your API that you could deeply clone any type of Map that is provided as the method's argument. However, you cannot. Map is a public interface and anybody can implement it. At run time you might be ask to create a deep clone map that is unknown to you and you will not be able to. Look at this implementation:

@SupressWarnings("unchecked")
public static <K, V, M extends Map<K, V>> M deepCopyMap(M s) {
    Map map;
    if(s.getClass() == HashMap.class) {
      map = new HashMap();
    } else if(s.getClass == LinkedHashMap.class) {
      map = new LinkedHashMap();
    } else {
      throw new RuntimeException("unknown map type " + s.getClass());
    }
    for(Map.Entry<K, V> entry : source.entrySet()) {
        K k = entry.getKey();
        V v = entry.getValue();
        if(k instanceof Map) {
          map.put(k, deepCopyMap((Map) k));
        } else {
          result.put(k, v);
        }
    }
    return (M) map;
}

This is not very transperent to the user and will most likely throw an exception if the map contains some user type map. The fact that the compiler will warn you about almost anything in this method is a good sign for that this is a bad idea.

Instead, I would actually recommend you the overloading approach where you only offer deep clones for known types. If you however discover a nested map that you cannot create at run time, you have to throw a run time exception. The kind of type safety you are looking for is hard to achieve. Additionally, I would make it an implicit part of the contract that you cannot use nested maps where the map types are not within a specified group of Map implementations.

On a side note: Without restricting M and V, there is no point in defining these parameters since you do not know anything about these parameters. Simply use a wildcard ?.