Gson changes the order of PriorityQueue in java when using new Gson().toJson(priorityQueue)

[wincelee]

Gson version 2.9.1

Java / Android version

Java 17
IntelliJ IDEA 2023.1 (Ultimate Edition)
Build #IU-231.8109.175, built on March 28, 2023
Runtime version: 17.0.6+10-b829.5 aarch64
VM: OpenJDK 64-Bit Server VM by JetBrains s.r.o.
macOS 13.0.1
GC: G1 Young Generation, G1 Old Generation
Memory: 4096M
Cores: 8

Used tools

• Apache Maven 3.8.6 (84538c9988a25aec085021c365c560670ad80f63)
• Gradle 8.0

Description

When i am printing a PriorityQueue using new Gson().toJson(priorityQueue) i get the order of the integers not in the correct way

Expected behavior

PrintingFromWhileLoop: 1
PrintingFromWhileLoop: 2
PrintingFromWhileLoop: 3
PrintingFromWhileLoop: 4
PrintingFromWhileLoop: 5
PrintingFromWhileLoop: 9

Actual behavior

MyPriorityQueueWithoutPrettyPrint: [1,2,5,4,3,9]

Reproduction steps

Queue mQueue = new PriorityQueue<>();
mQueue.offer(4);
mQueue.offer(2);
mQueue.offer(9);
mQueue.offer(1);
mQueue.offer(3);
mQueue.offer(5);

https://github.com/wincelee/MyLeetCodes/blob/c8c5e569dc8fec99070f68c568cc786833faaa6e/src/main/java/leet_code_quizes/easy/GsonPriorityQueueBug.java

[eamonnmcmanus]

I think it's probably worth registering a TypeAdapter if you want to be able to serialize and deserialize a PriorityQueue in a particular way.

[Marcono1234]

Interestingly Gson even has a unit test for PriorityQueue:

gson/gson/src/test/java/com/google/gson/functional/CollectionTest.java

Lines 138 to 148 in 43396e4

	@Test
	public void testPriorityQueue() {
	Type type = new TypeToken<PriorityQueue<Integer>>(){}.getType();
	PriorityQueue<Integer> queue = gson.fromJson("[10, 20, 22]", type);
	assertThat(queue.size()).isEqualTo(3);
	String json = gson.toJson(queue);
	assertThat(queue.remove()).isEqualTo(10);
	assertThat(queue.remove()).isEqualTo(20);
	assertThat(queue.remove()).isEqualTo(22);
	assertThat(json).isEqualTo("[10,20,22]");
	}

However, this test seems to be flawed because the values in the input JSON data are already sorted. If you provide instead "[22, 10, 20]" the test fails because the PriorityQueue seems to store them in a different order internally then.

To provide a bit more context on the current Gson behavior: Gson does not have a dedicated adapter for PriorityQueue at the moment. Therefore it uses the general Collection adapter to read and write PriorityQueue instances. The problem is that the iteration order of PriorityQueue is unspecified, as mentioned by its documentation:

The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

This is also not a problem specific to Gson, see this Stack Overflow question about PriorityQueue iteration order.

So as Éamonn mentioned above, you will have to write a custom TypeAdapter or maybe even a TypeAdapterFactory, for example:

class PriorityQueueAdapterFactory implements TypeAdapterFactory {
  public static final PriorityQueueAdapterFactory INSTANCE = new PriorityQueueAdapterFactory();

  private PriorityQueueAdapterFactory() { }

  @Override
  public <T> TypeAdapter<T> create(Gson gson, TypeToken<T> typeToken) {
    Class<?> rawType = typeToken.getRawType();

    // Only handle PriorityQueue, let other factories handle all other types
    if (rawType != PriorityQueue.class) {
      return null;
    }

    Type type = typeToken.getType();
    Type elementType;

    // If raw type without type argument choose Object as element type (and let Gson
    // get actual runtime type)
    if (type instanceof Class<?>) {
      elementType = Object.class;
    } else {
      ParameterizedType parameterizedType = (ParameterizedType) type;
      // Get the element type argument, for example `String` for `PriorityQueue<String>`
      elementType = parameterizedType.getActualTypeArguments()[0];
    }
  
    @SuppressWarnings("unchecked")
    final TypeAdapter<Object> elementAdapter = (TypeAdapter<Object>) gson.getAdapter(TypeToken.get(elementType));
  
    @SuppressWarnings("unchecked")
    TypeAdapter<T> r = (TypeAdapter<T>) new TypeAdapter<PriorityQueue<Object>>() {
      @Override
      public void write(JsonWriter out, PriorityQueue<Object> value) throws IOException {
        if (value == null) {
          out.nullValue();
          return;
        }
  
        // Custom Comparator is unsupported because it would otherwise have to be serialized as well
        if (value.comparator() != null) {
          throw new IllegalArgumentException("Custom Comparator is not supported");
        }
  
        // Must manually sort elements because iteration order is unspecified
        Object[] elements = value.toArray();
        Arrays.sort(elements);

        out.beginArray();
        for (Object element : elements) {
          elementAdapter.write(out, element);
        }
        out.endArray();
      }

      @Override
      public PriorityQueue<Object> read(JsonReader in) throws IOException {
        if (in.peek() == JsonToken.NULL) {
          in.nextNull();
          return null;
        }

        PriorityQueue<Object> queue = new PriorityQueue<>();

        in.beginArray();
        while (in.hasNext()) {
          Object element = elementAdapter.read(in);
          queue.add(element);
        }
        in.endArray();

        return queue;
      }
    };

    return r;
  }
}

(Have not extensively tested this yet)

And then register it like this:

Gson gson = new GsonBuilder()
  .registerTypeAdapterFactory(PriorityQueueAdapterFactory.INSTANCE)
  .create();

However, as you might have noticed in the adapter code above this is not so efficient because it has to store all elements in an array and sort them before being able to write them to JSON. With all other solutions, such as calling poll(), you would modify the provided queue, which is probably undesired.
Also, to keep serialization and deserialization symmetric the solution above rejects queues with custom comparator, because otherwise you would also have to somehow serialize and deserialize the comparator as well.

You could use the adapter factory shown above, or maybe the better solution would be to switch to a regular List instead of a PriorityQueue if possible.

@eamonnmcmanus, do you think it is worth considering adding explicit support for PriorityQueue? Currently I don't think it is, given that this might be a somewhat rare corner case and because as shown above the implementation for it would be limited and inefficient.

[eamonnmcmanus]

I think probably a much simpler TypeAdapter would be possible, that just delegates to the existing adapters for collections or arrays, via an intermediate sorted array? Not very efficient, but anyway we're not going to have a highly efficient solution.

This might be a candidate for gson/extras, both as a general example of how to do delegation and as something to point people to when this question arises.

I am not very keen on the idea of adding a PriorityQueue adapter by default, both because it is perhaps surprisingly inefficient and because I think it's fairly likely that it would change behaviour for at least some existing code.

[Marcono1234]

I think probably a much simpler TypeAdapter would be possible, that just delegates to the existing adapters for collections or arrays, via an intermediate sorted array?

For delegation you would normally use TypeAdapterFactory though because TypeAdapter has no access to the Gson instance (or maybe I am misunderstanding you). Otherwise you would have to create a new Gson instance in the adapter, which then does not have the same configuration, e.g. lenientness setting.

Directly trying to serialize the array probably works but there might be some subtle differences regarding which types are used. If you want to preserve the original element type you would have to create from a parameterized type representing PriorityQueue<X> a generic array type representing X[] and pass that to Gson.getAdapter when fetching the delegate. If you omit the type (or use the runtime type) the behavior of Gson's internal TypeAdapterRuntimeTypeWrapper might differ.

[eamonnmcmanus]

I might not have thought this through completely, but anyway we would necessarily be talking about a TypeAdapterFactory, right? So it can apply to any PriorityQueue<Foo>. And then can't it "just" delegate to get a TypeAdapter for List<Foo> and copy the toArray() into a List<Foo>?

I see that the MultisetTypeAdapterFactory example in the documentation for TypeAdapterFactory doesn't do this, but couldn't it?

[Marcono1234]

we would necessarily be talking about a TypeAdapterFactory, right?

Yes I think so; otherwise you cannot really perform delegation to my knowledge (except with JsonSerializer and JsonDeserializer).

---

And then can't it "just" delegate to get a TypeAdapter for List<Foo> and copy the toArray() into a List<Foo>?

That would actually be an option; the delegate adapters don't have to be the same for serialization and deserialization (as long as they behave identically). But then it would have to construct a ParameterizedType representing List<Foo> when calling Gson.getAdapter (can be created with TypeToken.getParameterized or getArray for Foo[]), and not just List.class. Otherwise there might be subtle differences in TypeAdapterRuntimeTypeWrapper behavior mentioned above; mainly for something like List<Foo<Bar>> I think, see TypeAdapterRuntimeTypeWrapper.getRuntimeTypeIfMoreSpecific.

For deserialization it would have also been possible to delegate to the default Gson adapter for PriorityQueue, because deserialization seems to work as expected.

But at that point I thought it was easier and more transparent (showing that serialization and deserialization behave identically) to implement this serialization and deserialization logic manually.

---

I see that the MultisetTypeAdapterFactory example in the documentation for TypeAdapterFactory doesn't do this, but couldn't it?

The factory serializes the set in the format [<count1>, <element1>, <count2>, <element2>, ...]. So delegation would not really be possible unless you use List<Object> as type and lose all type information about the elements.

For what it is worth, the MultisetTypeAdapterFactory in that example is rather limited. It only works for a parameterized Multiset, so when you serialize you must specify the type (toJson(multiset, type)); just calling for example gson.toJson(ImmutableMultiset.of("a", "b", "b")) will not use the factory. But extending it to cover also any Multiset implementation would probably be out of scope for this example because it would require custom logic for deserializing ImmutableMultiset.