6 July 2015

Пишем LINQ на JavaScript с нуля

JavaScript
From Sandbox

Зачем


Однажды при разработке компонента графика для веб-браузера мы столкнулись с проблемой обработки последовательностей на JavaScript.

C# разработчики уже много лет пользуются методами расширения для обработки последовательностей. И хотя данная технология не лишена подводных камней, она позволяет во многих случаях избежать утомительного написания рутинного кода по обработке массивов, списков и т.д.

Естественно, хотелось бы иметь аналогичные возможности и на JavaScript.

На данный момент существует немало реализаций LINQ для JavaScript, например, linq.js, $linq. Эти реализации предоставляют широкие возможности, сравнимые с реализацией на C#. Обратной стороной является немалый размер кода, из которого в конкретном приложении может использоваться лишь небольшая часть. Например, нам необходима лишь функция distinct, а мы вынуждены добавлять килобайты кода third-party библиотеки.

Опять же, любопытно разобраться, как же конкретная библиотека работает, а разбирать исходный код большой библиотеки зачастую утомительно. Или в нашем случае у нас уже есть своя библиотека для JavaScript и мы лишь хотим её компактно дополнить функционалом работы с последовательностями.

Насколько пригоден JavaScript для реализации


Определимся с элементами JavaScript, которые необходимы для реализации задуманого. У нас есть массивы, есть лямбда-функции, есть объекты, возможно наследование с некоторыми оговорками. Мы хотим выполнять операции, представленные лямбда-функциями над данными, содержащимися в массивах и эти операции мы хотим сгруппировать в объекте. Всё в порядке.

Попробуем сами


Начнём с определения необходимых сущностей.
Очевидно, что для работы с последовательностями самым базовым объектом является итератор. Всё, что от него нужно, это три метода:
  • moveNext() перемещает указатель на следующий элемент и возвращает true в случае успеха и false, если следующего элемента нет (достигнут конец последовательности);
  • current() возвращает текущий элемент либо null, если такого элемента нет (достигнут конец последовательности);
  • reset() перемещает указатель на первый элемент последовательности.

Значит, нам нужен метод, конструирующий итератор из базовой последовательности (например, из массива JS).

Далее нам нужен объект, который будет содержать набор методов для работы с множествами (where, select и т.д.). Поскольку больше хотелось иметь название, отражающее суть функционала, чем “намекать” на аналоги, было выбрано слово Walkable (суть такой, по элементам которого можно “ходить”/итерироваться). Каждый метод этого объекта должен возвращать тоже объект Walkable, чтобы поддерживать возможность объединять несколько вызовов в одной цепочке (другими словами, чтобы можно было передавать результат исполнения предыдущего метода на вход следующему).

Во-вторых, нам нужен источник данных. Не хотелось бы ограничиваться встроенным массивом JS в качестве единственного источника. Вот здесь нам и пригодится упомянутый выше итератор. Всё, что нам нужно от последовательности, это единственный метод, возвращающий итератор (конечно, каждый раз новый экземпляр, чтобы его можно было использовать, не изменяя состояние других итераторов). На следующем шаге к такому объекту можно “подмешать” методы Walkable и в итоге над результатом можно вызывать любые методы Walkable и каскадировать их в произвольные цепочки.

Проиллюстрируем теорию кодом. Вот метод, создающий объект Walkable из массива JS:

var arrayWalkable = function(arr) {
      var walker = function() { .// внутрення функция-конструктор итератора
        var idx = -1; // состояние итератора
        // далее классические методы итератора
        this.reset = function() { idx = -1; };
        this.moveNext = function() { return (++idx < arr.length); };
        this.current = function() { return (idx < 0 || idx >= arr.length) ? null : arr[idx]; }; 
      };
      // создаём обёртку над массивом, возвращающую итератор
      var walkable = { getWalker: function() { return new walker(); },};
      // расширяем обёртку методами объекта Walkable
      // WAVE.extend - базовая функция нашей библиотеки, при желании можно реализовать/скопировать         
      //свою
      WAVE.extend(walkable, WAVE.Walkable); 
      return walkable;
    }

Далее займёмся собственно объектом Walkable. Он должен содержать методы работы с последовательностями, каждый из которых должен возвращать в свою очеред новый объект Walkable.

Итак, реализуем объект Walkable и самый популярный метод where. Поскольку мы выбрали walkable в качестве названия, то и все методы расширения мы называем с буквы “w”:

wWhere: function(filter) {
                	var srcWalkable = this;
                	var walkable = {
                  	  getWalker: function() {
                      	    var walker = srcWalkable.getWalker();
                    	    return {
                      	      reset: function() { walker.reset(); },
                      	      moveNext: function() {
                        	  while (walker.moveNext()) {
                          	    var has = filter(walker.current());
                          	    if (has) return true;
                        	  }
                        	  return false;
                      	      },
                      	      current: function() { return walker.current(); }
                    	    };
                  	  }  
                	}
                	WAVE.extend(walkable, WAVE.Walkable);
                	return walkable;
    	}, //wWhere

В качестве аргумента для wWhere принимаем функцию filter, которая в свою очередь принимает на вход элемент последовательности и возвращает true или false (включать или нет элемент в результат). Далее запоминаем this в переменной srcWalkable (классический приём в JS).

На следующем шаге по аналогии с вышеописанным методом arrayWalkable определяем базовый объект walkable с ключевым методом getWalker. При каждом вызове получаем новый итератор текущего объекта, чтобы не влиять на другие итераторы. И возвращаем объект.

Затем переопределяем в соответствии с логикой операции where методы итератора:
  • reset: просто вызывает reset источника последовательности (например, это может быть объект, произведённый методом WAVE.arrayWalkable, описанным выше;
  • moveNext: вызывает moveNext источника последовательности, пока не найдёт элемент, удовлетворяющий критерию filter, либо пока не достигнет конца исходной последовательности;
  • current: вызывает current источника последовательности.

Пример использования


В качестве простейших примеров использования можно привести фрагменты юнит-тестов.

Продемонстрируем работу самого итератора и Walkable:

Легко видеть, что такой дизайн позволяет выстраивать произвольные функции, возвращающие Walkable, в цепочки произвольной длинны.

По аналогии с wWhere реализуются остальные функции нашей библиотеки, например, wSelect, wDistinct и т.д.

function() {
          var a = [1, 2, 3, 4, 5]; 

          var aw = WAVE.arrayWalkable(a);

          var walker = aw.getWalker(), i=0;
          while(walker.moveNext()) {
            assertTrue(a[i] === walker.current());
            i++;
          }

          assertFalse(walker.moveNext());
          assertTrue(null === walker.current());
     }

Теперь используем wWhere, выстроив их в цепочку:

function() {
          var a = [1, 2, 3, 4, 5]; 

          var aw = WAVE.arrayWalkable(a);
          var wWhere1 = aw.wWhere(function(e) { return e > 1; });
          var wWhere2 = wWhere1.wWhere(function(e) { return e < 5; });
          var result2 = wWhere2.wToArray();

          for(var i in result2) log(result2[i]);

          assertTrue( 3 === result2.length);
     }

В коде использованы функции-обёртки для тестирование, включённые в wv.js.

Выводы


Реализация собственной LINQ-подобной библиотеки на JavaScript не является сложной задачей и каждый желающий с минимальными знаниями программирования может с ней справиться.

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

Исходный код библиотеки может быть получен тут, юнит-тесты находятся тут.
П.С:
Решил добавить полный список функций Walkable:
wSelect, wSelectMany, wWhere, wAt, wFirst, wFirstIdx, wCount, wDistinct, wConcat, wExcept, wGroup, wGroupIntoObject, wGroupIntoArray, wGroupAggregate, wOrder, wTake, wTakeWhile, wSkip, wAny, wAll, wMin, wMax, wAggregate, wSum, wEqual, wToArray, wEach, wWMA (moving average), wHarmonicFrequencyFilter (наш собственный фильтр, концепция зарекомендовала себя отлично, например, здесь), wConstLinearSampling, wSineGen, wSawGen, wSquareGen, wRandomGen,
Tags: NFX Wave Unistack javascript
Hubs: JavaScript
+1
8.9k 47
Comments 72
Ads