Одним днем возникла необходимость добавить в проект генерацию коротких css классов и id элементов в html верстке. Основные причины были следующие:

• Усложнить жизнь парсерам и блокировщикам рекламы (они зачастую на имена классов опираются).

• Уменьшить размер html страниц.

• И чтобы все было как у Google, шутка ????

Очевидно, что минификация классов и id полностью не защитит от парсеров, как говорится, лучшая защита от парсинга – удалить страницу из интернета. Но данный подход может отбить охоту у вчерашних студентов с фриланс биржи зарабатывать на парсинге, или защитить от универсальных ботов-парсеров.

Другая проблема в том, что благодаря BEM подходу многие классы в верстке имеют довольно длинное название, и если на странице много элементов с такими классами, то страница становится довольно «жирной». Да, gzip и его аналоги, благодаря rle и другим алгоритмам, сжимают повторяющиеся элементы, но зачем создавать работу компрессору, если можно отдавать меньшего размера html... JavaScript и CSS код все равно обычно минифицируют, даже если используются компрессоры.

Какие требования у нас к генератору минифицированных классов и id:

• Получившийся идентификатор должен начинаться с букв, а не с цифр.

• Длина идентификатора должна быть максимально короткой.

• Отсутствие коллизий.

• Генератор не должен зависеть от специфичного окружения (доступ к DNS, mac- адресу, криптография и т.д.), чтобы можно было его использовать в браузере или в любом другом окружении, где может исполняться js.

• Алгоритм должен быть «легкий» в исполнении, чтобы не создавать нагрузку на процесс, который рендерит html.

Идентификаторы должны начинаться с букв или других разрешенных символов, потому что css не поддерживает классы, которые начинаются с цифр:

.123red {
  color: blue;
}

/* Стили не будут применены!*/
<div class="123red">Hello world!!!</div>

О разрешенных символах для css классов и id можно почитать здесь. Это применимо и для id для элементов html верстки. Есть, конечно, способы как извернуться, чтобы обойти это ограничение, но это либо не удобно, либо бьет по скорости работы ваших селекторов для классов. Но все равно сохраняется проблема взаимодействия с классами и id, которые начинаются с чисел, через javascript на странице. Например:

// OK
document.getElementById('1'); 
// OK
document.getElementsByClassName('1'); 


// Failed to execute 'querySelector' on 'Document': '#1' is not a valid selector.
document.querySelector('#1');
// Failed to execute 'querySelector' on 'Document': '.1' is not a valid selector.
document.querySelector('.1'); 

Для того чтобы починить работу с querySelector и querySelectorAll можно применить CSS.escape.

// OK
document.querySelector('#'+CSS.escape('1'));

// OK
document.querySelector('.'+CSS.escape('1'));

Но вряд ли сторонние javascript библиотеки используют CSS.escape для id и классов, которые вы им передаете при их вызове.

Какие реализации приходят в голову первым делом:

• uuid сразу нет, всегда размером 36 символов и может начинаться с цифр: 00112233-4455-6677-8899-aabbccddeeff

• nanoid уже лучше, благодаря тому, что можно задавать алфавит и длину сгенеренной строки. Но размер полученной строки всегда статичный, а его реализация использует модуль crypto

Хотелось чего-то легкого и простого, и на самом деле решение есть, оно лежит на поверхности.

Алгоритм

Мы каждый день имеем дело с системами исчисления по работе или в обычной жизни. Как правило, с десятичной и реже с шестнадцатеричной и двоичной. Представим, что мы не знаем, как работает +1, и нам надо разработать алгоритм для получения следующего числа. В начале у нас будет всего один разряд со значением 0 и цифры 0-9 (база), затем мы будем брать следующее значение для этого разряда, пока не дойдем до последней цифры 9. Более старших разрядов у числа не имеется, поэтому мы добавим слева, еще один разряд со значением 1, а все более младшие разряды обнулим (в данном случае он единственный). И опять будем работать с самым младшим разрядом (самая правая цифра). На этот раз, когда самый младший разряд станет равен 9 (число 19) у нас имеется более старший разряд, который имеет следующее значение 2. А младший разряд, аналогично, переводим в 0. В результате получается число 20. И так можно продолжать до бесконечности.

Теперь надо этот алгоритм переложить на нашу задачу, где у нас базой будет набор букв. Возьмем для примера в качестве базы: a,b,c. В начале у нас будет один разряд и мы будем итерироваться по нему, в результате получим список: a, b, c. Когда мы дойдем до с, то в строке не будет иметься более старшего разряда, и следовательно, необходимо добавить новый разряд с начальным значением a, а младший разряд сбросить в начальное значение (тоже a). И снова будем итерироваться по самому младшему разряду, в результате получим список: aa, ab, ac. Теперь, когда мы дошли до ac, у нас есть более старший разряд для которого мы берем следующее значение b, а младший сбрасываем в a, т.е. получаем ba. И так до бесконечности...

Реализация

Для реализации алгоритма нам потребуется создать вспомогательный класс, который реализует одновременно что-то вроде связного списка и хэш структуры для нашего алфавита.

class LinkList {
  constructor(list) {
    this._hash = {};
    list.forEach((el, i) => {
      this._hash[el] = list[i+1] || null;
    });
    this._headEl = list[0];
  }

  getHead() {
    return this._headEl;
  }

  hasNext(el) {
    return Boolean(this._hash[el]);
  }

  next(el) {
    return this._hash[el];
  }
}

const linkList = new LinkList(['a', 'b', 'c']);
// --> a
console.log(linkList.getHead());
// --> true
console.log(linkList.hasNext('a'));
// --> false
console.log(linkList.hasNext('c'));
// --> b
console.log(linkList.next('a'));

Затем начнем реализовывать сам класс для генерации идентификаторов на базе алфавита:

class Generator {
  constructor(alphabet) {
    this._linkList = new LinkList(alphabet);
    this._list = [];
    this._pos = 0;
  }


  next() {
    const linkList = this._linkList;

    const value = this._list[this._pos];
    if (linkList.hasNext(value)) {
      this._list[this._pos] = linkList.next(value);
      return this._toString();
    } else {
      this._addLetter();
      return this._toString();
    }
  }

  _addLetter() {
    const linkList = this._linkList;
    this._list.unshift(linkList.getHead());
    this._list.forEach((el, i) => {
      if (i === 0) {
        return;
      }
      this._list[i] = linkList.getHead();
    });
    this._pos = this._list.length - 1;
  }

  _toString() {
    return this._list.join('');
  }
}

const generator = new Generator(['a', 'b', 'c' ]);
// --> a
console.log(generator.next());
// --> b
console.log(generator.next());
// --> c
console.log(generator.next());
// --> aa
console.log(generator.next());
// --> ab
console.log(generator.next());
// --> ac
console.log(generator.next());
// --> aaa -- Ошибка, должно быть "ba"
console.log(generator.next());

В конструкторе мы инициализируем наш _linkList на базе переданного алфавита, а так же создаем _link - массив букв, из которых будет формироваться строка, _pos - позиция в массиве _link или другими словами, текущий разряд. Метод _toString формирует из массива строку. Метод next занимается генерацией следующей строки: если текущий разряд имеет следующее значение из алфавита, то обновляем текущий разряд и возвращаем строчку, иначе с помощью метода _addLetter добавляем новую букву в массив. Метод _addLetter добавляет в начало массива первую букву из нашего алфавита, младшие разряды так же сбрасывает к начальной букве, а также в качестве позиции выбирает самый младший разряд.

Как видим в текущей реализации ошибка, после ac должно быть ba, а не aaa. Это связано с тем, что мы не обрабатываем ситуацию с наличием более старших разрядов, для которых можно взять следующее значение. Исправим это:

class Generator {
  constructor(alphabet) {
    this._linkList = new Link_list(alphabet);
    this._list = [];
    this._pos = 0;
  }


  next() {
    const linkList = this._linkList;

    const value = this._list[this._pos];
    if (linkList.hasNext(value)) {
      this._list[this._pos] = linkList.next(value);
      return this._toString();
    } else if (!linkList.hasNext(value) && this._list[this._pos - 1]) { 
      const pos = this._findPos();
      if (pos === null) {
        this._addLetter();
        return this._toString();
      }
      this._list.forEach((_, i) => {
        if (i <= pos) { 
          return;
        }
        this._list[i] = linkList.getHead();
      });
      this._list[pos] = linkList.next(this._list[pos]);
      this._pos = this._list.length - 1;
      return this._toString();
    } else {
      this._addLetter();
      return this._toString();
    }
  }

  _addLetter() {
    const linkList = this._linkList;
    this._list.unshift(linkList.getHead());
    this._list.forEach((el, i) => {
      if (i === 0) {
        return;
      }
      this._list[i] = linkList.getHead();
    });
    this._pos = this._list.length - 1;
  }

  _findPos() {
    let pos = this._pos;
    while (pos >= 0) {
      const val = this._list[pos];
      if (this._linkList.hasNext(val)) {
        return pos;
      }
      pos--;
    }
    return null;
  }

  _toString() {
    return this._list.join('');
  }
}

const generator = new Generator(['a', 'b', 'c', ]);
// --> a
console.log(generator.next());
// --> b
console.log(generator.next());
// --> c
console.log(generator.next());
// --> aa
console.log(generator.next());
// --> ab
console.log(generator.next());
// --> ac
console.log(generator.next());
// --> ba
console.log(generator.next());
// --> bb
console.log(generator.next());
// --> bc
console.log(generator.next());

Теперь в методе _next мы проверяем, что для текущего разряда нет следующего значения, но при этом имеются более старшие разряды. Затем с помощью функции _findPos, мы находим разряд, для которого есть следующее значение, и возвращаем позицию. Затем пробегаемся по всем разрядам, которые младше найденного и сбрасываем их к начальной букве, и выставляем текущую позицию в самый младший разряд. В случае, если подходящий разряд не удалось найти, то добавляем новый разряд с помощью _addLetter.

Вот теперь реализация работает правильно.

Пример, как будут выглядеть строки при 88 вызовах и алфавите из 4 букв:

describe('[Generator.js]', function () {
  let generator;

  beforeAll(() => {
    generator = new Generator(['a', 'b', 'c', 'd']);
  });

 

  test.each([
    ['a'], ['b'], ['c'], ['d'],
    ['aa'], ['ab'], ['ac'], ['ad'],
    ['ba'], ['bb'], ['bc'], ['bd'],
    ['ca'], ['cb'], ['cc'], ['cd'],
    ['da'], ['db'], ['dc'], ['dd'],
    ['aaa'], ['aab'], ['aac'], ['aad'],
    ['aba'], ['abb'], ['abc'], ['abd'],
    ['aca'], ['acb'], ['acc'], ['acd'],
    ['ada'], ['adb'], ['adc'], ['add'],
    ['baa'], ['bab'], ['bac'], ['bad'],
    ['bba'], ['bbb'], ['bbc'], ['bbd'],
    ['bca'], ['bcb'], ['bcc'], ['bcd'],
    ['bda'], ['bdb'], ['bdc'], ['bdd'],
    ['caa'], ['cab'], ['cac'], ['cad'],
    ['cba'], ['cbb'], ['cbc'], ['cbd'],
    ['cca'], ['ccb'], ['ccc'], ['ccd'],
    ['cda'], ['cdb'], ['cdc'], ['cdd'],
    ['daa'], ['dab'], ['dac'], ['dad'],
    ['dba'], ['dbb'], ['dbc'], ['dbd'],
    ['dca'], ['dcb'], ['dcc'], ['dcd'],
    ['dda'], ['ddb'], ['ddc'], ['ddd'],
    ['aaaa'], ['aaab'], ['aaac'], ['aaad'],
  ])('generate', expected => {
    expect(generator.next()).toBe(expected);
  });

});

Как видно из вызовов, длина строки растет постепенно, и чем больше размер базы (алфавита), тем медленнее она будет расти. Если база короткая и при этом мы используем глобальный генератор, то через некоторое время мы получим длинные строки. Но в моем случае это не так, у каждого пользователя в течении его сессии на сайте создается свой генератор, который генерит значения для css классов и id элементов, и длина строки очень редко, когда выходила за 2-3 символа. Но, например, для алфавита в 52 буквы ( abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ) требуется сгенерить 2.5 миллиона идентификаторов, чтобы длина строки достигла 5 символов. Это довольно большое количество и длина строки все равно сильно короче большинства исходных классов. В целом алгоритм довольно легковесный и при этом коллизий никогда не будет, его наверняка можно использовать еще для каких-то целей.

Если кого-то заинтересовала данная реализация, то я оформил ее в виде npm пакета. Пакет также имеет дополнительные возможности:

• Кэшировать идентификаторы по заданному ключу. Например, на вход полноценное имя класса, а на выход фиксированный короткий идентификатор.

• Пропускать идентификаторы из black list. Например, Google Analytics использует короткое id ga . Мы можем пропускать такое значение во избежания конфликта.

• Задавать префикс для всех идентификаторов.

• Запрещать начинаться идентификаторам с определенных символов. Это удобно для того чтобы увеличить алфавит и тем самым иметь возможность увеличить кол-во коротких идентификаторов, но при этом решить проблему, что css классы и id не могут начинаться с цифр. Пример генератора с алфавитом из букв и цифр: new Generator('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789', { notStartsWith: '0123456789' }); но при этом с запретом на генерацию идентификатора начинающихся с цифр. Тогда для того чтобы достигнуть длины строки в 5 символов, надо будет сгенерить 87 403 780 миллионов идентификаторов.