Прожарка java.lang.String

Давайте абьюзить баг в java.lang.String, который позволит делать очень странные строки. Мы сделаем "Hello World", который не начинается с "Hello" и покажем, что не все пустые строки равны между собой. Научимся прожаривать строки в чужих классах.

Введение. Эквививалентность строк.

Прежде, чем мы начнем, давайте взглянем, как две строки из JDK оказываются равны между собой.

Почему "foo".equals("fox") == false?

Потому, что строки сравниваются символ за символом, и третий символ здесь различается.

Почему "foo".equals("foo") == true?

Может показаться, что в этом случае строки тоже сравниваются побуквенно. Но строковые литералы интернируются. Когда ты пишешь одинаковые строки в тексте одной и той же программы, о них уже нельзя думать как о дополнительных экземплярах с тем же самым содержимым. Это экземпляр в точности одной и той же строки. Первое, что делает String.equals — проверку вида if (this == anObject) { return true; }. Оно даже не смотрит на содержимое!

Почему "foo!".equals("foo⁉") == false?

Начиная с JDK 9 (JEP 254: Compact Strings), String внутри использует массив байтов. "foo!" содержит только простые символы, с кодом менее 256. Поэтому, класс String под капотом кодирует такие значения с использованием кодировки latin-1, используя по байту на каждый символ. "foo⁉" содержит специальный символ (⁉), которого нет в кодировке latin-1, поэтому он кодирует всю строку в в UTF-16, по два байта на символ. Поле String.coder следит, какая из двух кодировок используется в каждом конкретном случае. Сравнивая две строки с разными значениями coder, метод String.equals всегда возвращает false. Он тоже не смотрит на содержимое строк. Если одна строка может быть преобразована в latin-1, а вторая - не может, очевидно, они не могут быть одинаковыми. Или могут?

Заметка: compact strings можно выключить, но они включены по-умолчанию. В этой статье подразумевается, что эта фича включена.

Создаем сломанную строку

Как создаются строки? Как класс java.lang.String выбирает, использовать ли latin-1?

Строки можно создавать множеством способов, но мы здесь посмотрим на конструктор класса String, который принимает в качестве аргумента char[]. Вначале, он пытается закодировать символы в latin-1 через StringUTF16.compress. Если не получается, тогда возвращается null и конструктор откатывается к использованию UTF-16. Взглянем на упрощённую версию того, как это реализовано. В целях улучшения читабельности, здесь убраны все бесполезные переходы, проверки и аргументы из настоящей реализации, которая расположена здесь и здесь.

/**
 * Allocates a new {@code String} so that it represents the sequence of
 * characters currently contained in the character array argument. The
 * contents of the character array are copied; subsequent modification of
 * the character array does not affect the newly created string.
 */
public String(char value[]) {
  byte[] val = StringUTF16.compress(value);
  if (val != null) {
    this.value = val;
    this.coder = LATIN1;
    return;
  }
  this.coder = UTF16;
  this.value = StringUTF16.toBytes(value);
}

В этом коде есть баг. Он не всегда следует предположениям, на которых построен String.equals, и которые мы обсуждали выше. Вглядитесь в эт от код.

Джавадок говорит, что "последующие модификации массива символов не влияют на новую созданную строку". Но как насчет одновременных (конкурентных) модификаций? В этом конструкторе String есть гонки (race condition). Содержимое поля value может измениться во время как мы бросили попытку кодировать в latin-1, и перешли на UTF-16. В этом случае мы получаем строку, которая содержит символы в latin-1, закодированные как UTF-16. Эти гонки можно активировать следующим кодом:

/**
 * Берет строку в latin-1, и создает копию,
 * некорректно перекодированную в UTF-16.
 */
static String breakIt(String original) {
  if (original.chars().max().orElseThrow() > 256) {
    throw new IllegalArgumentException(
        "Can only break latin-1 Strings");
  }
  char[] chars = original.toCharArray();
  // В отдельном потоке, будем менять первый символ туда-сюда,
  // между чем-то, представимым в latin-1, и не представимым в ней.
  Thread thread = new Thread(() -> {
    while (!Thread.interrupted()) {
      chars[0] ^= 256;
    }
  });
  thread.start();
  // В то же самое время, будем звать конструктор строки,
  // пока не попадём в ситуацию гонок.
  while (true) {
    String s = new String(chars);
    if (s.charAt(0) < 256 && !original.equals(s)) {
      thread.interrupt();
      return s;
    }
  }
}

Поломанные таким образом строки обладают рядом интересных свойств, например:

String a = "foo";
String b = breakIt(a);

// Они не равны между собой
System.out.println(a.equals(b));
// => false

// Последовательности символов в них совпадают
System.out.println(Arrays.equals(a.toCharArray(),
b.toCharArray()));
// => true

// compareTo считает их равными (даже несмотря на то,
// что джавадок явно говорит: "compareTo возвращает 0
// в точности тогда, когда метод equals(Object) вернул бы true")
System.out.println(a.compareTo(b));
// => 0

// У них одинаковая длина, и одна из них 
// начинается с другой (startsWith), но не наоборот.
// Потому что, в случае нормальных несломанных строк,
// строка в latin-1 не может начинаться с подстроки, 
// которой нельзя представить в latin-1.
System.out.println(a.length() == b.length());
// => true
System.out.println(b.startsWith(a));
// => true
System.out.println(a.startsWith(b));
// => false

Всё это немного странно. Обычно, ты не ожидаешь такого поведения от фундаментального Java-класса.

Прожарка кошки сквозь стену

Если вытащить из микроволновки магнетрон, можно ли сквозь стену прожарить кошку соседа?

По крайней мере, в Java мы можем прожарить строку в чужом классе!

class OtherClass {
  static void startWithHello() {
    System.out.println("hello world".startsWith("hello"));
  }
}

Если написать подобный код, то IDEA напишет предупреждение вида Результат выполнения '"hello world".startsWith("hello")' всегда равен 'true'. Вроде бы, у этого кода нет никаких входных параметров, но мы всё ещё можем заставить его вернуть false. Для этого, нужно внедрить в него сломанную строку "hello" с помощью интернирования. Мы сломаем строку, содержащую "hello" до того, как любой другой код успеет явно или неявно интернировать её, и интернируем сразу сломанную версию. В дальнейшем, все литералы "hello" в JVM окажутся сломанными.

breakIt("hell".concat("o")).intern();
OtherClass.startWithHello(); 

Челленж для самых изобретательных

Использя метод breakIt, для любой строки в latin-1 можно создать эквивалентную, но отличающуюся строку. Но это не работает для пустой строки! Потому что пустая строка не содержит символов, на которых можно было бы вызвать ситуацию гонок. Тем не менее, сломанную пустую строку всё ещё возможно получить. Доказательство этого факта остается в виде упражнения для читателя.

Конкретно: можете ли вы создать объект класса java.lang.String, для которого выражение s.isEmpty() && !s.equals("") будет равно true. Никакого читерства: для решения задачи вы можете использовать только публичное API, то есть, нельзя использовать .setAccessible для доступа к приватному коду, использовать инструментирование, и всё в таком духе.

Если вы нашли решение этой задачи, напишите его в комментариях к этому посту. А когда-нибудь в очередном Java-дайджесте мы напишем правильное решение (и обновим эту статью).

Если вам нравятся Java-новости, подписывайтесь на мою телегу @JavaWatch. Там же есть чатик, в котором всё это можно обсудить.

Статья написана при поддержке Axiom JDK (российского дистрибутива Java) и моего бара Failover Bar. Меняйте вашу джаву на проде на Axiom JDK, переходите на свежие версии JDK с исправленными багами, и приходите отмечать это в барчик!