ImmutableTable.row and ImmutableTable.column do not respect row/column comparators

[laszlo-k-13]

When creating an ImmutableTable using a row and/or column comparator, Map views returned by the row and column methods do not use the given comparator to find a row/column by key, and also return ImmutableMaps that do not rely on the specified row/column comparator for finding entries. This is true whether the map is created directly via ImmutableTable.copyOf or ImmutableTable.Builder.

Specifically, it doesn't seem possible to create an ImmutableTable copy of a RowSortedTable crafted to use case-insensitive row and column keys in such a way as to preserve the case-insensitive behaviour in the copy (which works fine in the mutable original).

Test:

    @Test
    void testImmutableTableWithComparators() {
        var testTarget = ImmutableTable.<String, String, String>builder()
                .orderRowsBy(String.CASE_INSENSITIVE_ORDER)
                .orderColumnsBy(String.CASE_INSENSITIVE_ORDER)
                .put("a", "b", "c")
                .build();
        var rowA = testTarget.row("A");
        assertThat("rowA is " + rowA, rowA.containsKey("B"));
    }

Result:

java.lang.AssertionError: rowA is {}

Similarly, changing the penultimate line to

        var rowA = testTarget.row("a");

leads to

java.lang.AssertionError: rowA is {b=c}

[cpovirk]

While I am not sure whether we'll ever change this, since...

• The current behavior appears to have been intentional -- though we probably didn't review it widely.
• We typically don't go to much effort to make our collections work with comparators that aren't consistent with equals. (See, e.g., some docs for ImmutableSortedSet.)
• Change brings its own risks.

...that doesn't change the fact that the behavior is poorly documented, surprising, and inconsistent with some of our other collections. So we would ideally at least document it better.

Currently, the docs say:

However, if orderRowsBy or orderColumnsBy is called, the views are sorted by the supplied comparators.

That isn't wrong, since the views are in fact sorted. But it certainly could be read as implying that we'd produce a SortedMap for the views, that that SortedMap would respect the Comparator when it conflicts with equals, and that the Table itself would have similar behavior.

On the one hand, that's a lot for a reader to infer. On the other hand, I think we do behave that way for methods with similarly sparse documentation, like ImmutableMultimap.Builder.orderKeysBy. (Or even see ImmutableSortedSet.orderedBy. Or even consider the entire class name Ordering, which is used for more than just specifying the order to use.) And even if the docs for both methods were clear about their behavior, it's pretty unfortunate for such similar methods to have different behavior.

Sorry for the confusing state that we've put everything in. In general, I'd recommend against comparators that are inconsistent with equals, but our documentation around these methods is poorer than we'd like.

[laszlo-k-13]

On the one hand, that's a lot for a reader to infer. On the other hand, I think we do behave that way for methods with similarly sparse documentation, like ImmutableMultimap.Builder.orderKeysBy. (Or even see ImmutableSortedSet.orderedBy. Or even consider the entire class name Ordering, which is used for more than just specifying the order to use.) And even if the docs for both methods were clear about their behavior, it's pretty unfortunate for such similar methods to have different behavior.

That's a perfectly fair assessment. To be honest my expectation that this would work had less to do with the documentation (I did notice that it only talked about iteration order, which is not exactly what I was after) and more with the fact that all of the other Immutable collections, as far as I've used them, behave so that any test of this form passes:

  @Test
  void testImmutableThing() {
      MutableThing mutable = ...;
      ImmutableThing immutable = ImmutableThing.copyOf(mutable);
      var mutableResult = getSomethingFrom(mutable);
      var immutableResult = getSomethingFrom(immutable);
      assertThat(immutableResult, equalTo(mutableResult));
  }

Which seems to be the general idea behind the entire immutable collections package: that you should be able to use them instead of the mutable ones, and gain protection against inadvertent modification, thread safety, a smaller memory footprint, and better performance. Or indeed that you should get used to the practice of defensively making immutable copies of things without having to think twice. (It even says "copyOf is smarter than you think"!)
Whereas in my case, someone before me used a RowSortedTable with CI row and column keys, which does work as expected, but making an immutable copy of it (mainly for thread safety purposes) broke a number of tests and left me scratching my head.

Admittedly this kind of perfect functional equivalence is a leaky abstraction (there's already the well-documented exception of null values, for example) and support for certain unusual cases might require undue effort or could even be outright infeasible. I was hoping that this particular case would prove reasonably feasible as even TreeMap and TreeSet have fully supported the quirk of a comparator that's inconsistent with equals since, if memory serves, JDK 7 (and everyone, including Sun/Oracle's own examples, had been using String.CASE_INSENSITIVE_ORDER with them happily even before that). And of course, the fact that the collection I was copying supported it and came from the same library reinforced my hopes that the copy would support it, too.

Unfortunately for me, what I'm working on has to be case-insensitive, so I haven't got the choice of coming up with a comparator that is consistent with equals.

[cpovirk]

Also all fair, thanks. We would definitely like for the immutable collections to be drop-in replacements that come with as few asterisks as possible.

To drill in on one small thing: The specific APIs of the form ImmutableThing.copyOf drop comparators in general (e.g., ImmtuableSortedMap.copyOf). So I think we already fail the strictest form of your test for that reason. (I do think that's the behavior we want, though I'm sure it's caused problems, too....) But your point holds for the main thing we've been talking about, which is that of specifying the comparator (and yet seeing it used differently than the analogous JDK APIs).

[cpovirk]

Belatedly: Setting aside how surprising this behavior is, you can create an ImmutableTable with case-insensitive keys. To do so, you'd have to wrap your keys into Equivalence.Wrapper<String> objects. You might use something like Equivalence.onResultOf(Ascii::toLowerCase), or you might want more sophisticated comparisons (possibly an Equivalence subclass that delegates to CASE_INSENSITIVE_ORDER).

The downside is that it's easy to accidentally call table.get(string, otherString) instead of table.get(equivalence.wrap(string), equivalence.wrap(otherString)). You'd probably want to wrap the Table in an API that does this automatically. (This is also a case in which Error Prone can help, this time with its CollectionIncompatibleType analysis. I suspect that IntelliJ and surely other tools catch this kind of mistake, too. It's just unfortunate that it's possible in the first place.)

[mvanhorn]

Implemented in PR #8259 - added javadoc to orderRowsBy/orderColumnsBy clarifying that comparators affect ordering only, not lookup semantics.