Нет ничего хуже ностальгирующих людей

Пишем парсер на PEG.js для своего языка запросов

Метки: PEG, graphql

Вдохновившись красотой GraphQL решил в новом проекте реализовать свой язык запросов для получения данных, который:

  1. Работал бы не с графовой базой данных как с графом
  2. Позволял бы объединять запросы при инициализации страницы в один.

Фэйсбуковский GraphQL выглядит примерно так:

{
    Viewer {
        firstName,
        lastName,
        email,

        friends.first(10) {
            cursor,
            node {
                name,
                age > 18
            }
        }
    }
}
  • Viewer — Название сущности, на самом деле можно было записать как то так: User(${request.currentUserId})
  • Список полей которые нам нужно получить
    • friends — массив пользователей — друзей человека
    • .first(10) — получить первые 10
      • cursor — сущность для перемещений по списку (запрос дополнительных, не входящих в первые 10, элементов) друзей в разные стороны
      • node — описание полей (и условий) каких друзей получить хотим (в данном случае первых 10, у которых возраст больше 18).

Собственно задача: разобрать этот текстовый формат в структуру, с которой можно уже работать как с обычным объектом в джаваскрипте.

Можно конечно попробовать написать регулярное выражение, но это боль и унижение. Так что лучше (и на самом деле сильно проще) — сгенерировать парсер, с помощью формального описания. Я не специалист в написании парсеров, и может делаю что то не оптимально, но написать небольшой парсер на самом деле намного проще, чем большое регулярное выражение.

Парсер сгенерировать по формальному описанию можно с помощью разных форм описаний, но я предпочитаю PEG как самый простой способ описать парсер (хотя и не самый оптимальный, как по памяти так и по времени исполнения0.

PEG парсеры — парсеры которые разбирают входную строку на "токены" по определенным программистом "правилам". Сначала описывается точка (правило) входа, в ней должно быть указано, по каким правилам можно найти "токены" внутри, у каждого правила описываются подправила, в том числе правило внутри себя может указывать на само себя, образуя рекурсию (осторожно, рекурсия!). В описании каждого "правила" может быть описана трансформация над полученными данными.

Для реализации буду использовать PEG.js.

Пример #1

Проверить что в строке находится целочисленное число, и только число, вернуть его, в виде Number(string):

start  
  = number

number  
  = value:$('0' / [1-9]([0-9]*)) {return Number(value)}

Правило start — входная точка, откуда начинается разбор строки. Указано, что внутри может быть только 1 токен, удовлетворяющий правилу number.

Правило number — описывает, что число может либо быть нулем, либо начинаться с одной из цифр в промежутке [1..9] и содержать в себе от 0 до бесконечности цифр в промежутке [0..9].

Разберем на части это правило, что я тут понаписал:

  1. value: — название переменной, в которой будет хранится то, что удовлетворяет правилу, которое написано далее.
  2. $ — обозначение того, что нужно вернуть саму строку, а не её вхождения. Т.е. number = [1-9]+ вернет массив символов, где каждый из символов является цифрой, которая входит в промежуток [1..9], а number = $[1-9]+ вернет строку, вместо массива символов.
  3. Круглые скобки — как и в других языках обозначают группировку, в данном случае группировку правил.
  4. '0' обозначение, что нужно найти именно символ 0
  5. Слэш значит, что нужно пытаться удовлетворить правило до слэша, если не получится, то попробовать правило следующее после слэша
  6. Синтаксис самих выражений почти полностью соответсвует синтаксису регулярных выражений, но, например, нету таких вещей как \s (символы пробела, табуляции, переносов строк и т.п.), \w (слово), \d (цифра).
  7. "Под правила" могут быть разделены пробелом или слэшом. Слэш описан выше, а пробел означает найти сначала то, что до пробела, а потом обязательно найти то что в следующем "под правиле".

За подробным описанием синтаксиса обратитесь в документацию PEG.js.

Пример #2

Найти массив чисел (записанных в формате JSON).

start  
  = '[' head:numbers* tail:number ']' {return head.concat([tail])}

number  
  = value:$('0' / [1-9]([0-9]*)) {return Number(value)}

numbers  
  = numberValueWithoutComma:number ',' {
    return numberValueWithoutComma
  }

Как видите, находить связанные скобки очень просто, можно чуть усложнить, ради вложенных связанных скобок, и попробовать получить массив массивов чисел:

start  
  = '[' head:arrays* tail:array ']' {return head.concat([tail])}

array  
  = '[' head:numbers* tail:number ']' {return head.concat([tail])}

arrays  
  = arrayValueWithoutComma:array ',' {
    return arrayValueWithoutComma
  }

number  
  = value:$('0' / [1-9]([0-9]*)) {return Number(value)}

numbers  
  = numberValueWithoutComma:number ',' {
    return numberValueWithoutComma
  }

Надо заметить один момент важный: подправила надо писать в порядке от большего к меньшему. Например если написать number = [0-9]+ / [0-9]+[A-z]* будет находится только первое все время. Так же надо не забывать что пробельные символы и переносы строк надо хэндлить самим, и фильтровать их в результате — тоже.

Этих знаний и умений нам хватит что бы написать парсер для упрощенной версии аналога GraphQL, который позволит указывать фильтры по полям и список полей сущности, в том числе вложенные.

Реализация

Для начала нам надо найти скобочки, название сущности и скобочки, обозначающие содержимое сущности:

start  
  = '{' entities:pair+ '}' {return entities;}

pair  
  = name:entity '{' fields:fields '}' {return {
    entityName: name,
    fields: fields
  };}

entity  
  = $([A-Z][A-z0-9]*)

fields  
  = head:(fieldWithComma)* tail:field? {
    if (!tail) {
       return head;
    }
    return head.concat([tail]);
  }

field  
  = $([A-z0-9_-]+)

fieldWithComma  
  = field:field ',' {return field;}

Это сможет распарсить например:{Viewer{name,email}}, но не сможет тоже самое с пробелами и переносами строк. Чтож, исправим ситуацию! Для начала объявим правило для пробельных символов:

whitespace  
  = [ \t\r\n]* {return null;}

И вставим его везде где могут быть пробелы!

start  
  = openBracer entities:pair+ closedBracer {return entities;}

pair  
  = name:entity openBracer fields:fields closedBracer {return {
    entityName: name,
    fields: fields
  };}

entity  
  = whitespace entityName:$([A-Z][A-z0-9]*) whitespace {return entityName;}

fields  
  = head:fieldWithComma* tail:field? {
    if (!tail) {
       return head;
    }
    return head.concat([tail]);
  }

field  
  = whitespace result:$([A-z0-9_-]+) whitespace {return result;}

fieldWithComma  
  = field:field whitespace ',' {return field;}

whitespace  
  = [ \t\r\n]* {return null;}

openBracer  
  = whitespace '{' whitespace

closedBracer  
  = whitespace '}' whitespace

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

Теперь хотелось бы добавить поддержку вложенных структур, для этого придется разделить и расширить правило field

fieldName  
  = whitespace result:$([A-z0-9_-]+) whitespace {return result;}

field  
  = name:fieldName nestedFields:subNode? {
    var result = {
      field: name
    };

    if (nestedFields) {
      result.nestedFields = nestedFields;
    }

    return result;
  }

subNode  
  = openBracer fields:fields closedBracer {
    return fields;
  }

А для того, что бы создать возможность делать условия по полям, надо всего лишь сделать что бы искалось одно из двух, или вложенные поля, или условия.

Результативное описание парсера:

start  
  = openBracer entities:pair+ closedBracer {return entities;}

pair  
  = name:entity openBracer fields:fields closedBracer {return {
    entityName: name,
    fields: fields
  };}

entity  
  = whitespace entityName:$([A-Z][A-z0-9]*) whitespace {return entityName;}

fields  
  = head:fieldWithComma* tail:field? {
    if (!tail) {
       return head;
    }
    return head.concat([tail]);
  }

subNode  
  = openBracer fields:fields closedBracer {
    return fields;
  }

fieldWithComma  
  = field:field whitespace ',' {return field;}

fieldName  
  = whitespace result:$([A-z0-9_-]+) whitespace {return result;}

field  
  = name:fieldName fieldValue:conditionOrSubNode? {
    fieldValue = fieldValue || {};
    fieldValue.field = name
    return fieldValue;
  }

conditionOrSubNode  
  = field:(subNode / condition) {
    if (Array.isArray(field)) {
      return {
        nested: field
      };
    }

    return {
      condition: field
    };
  }

condition  
  = operator:operator operand:operand {
    var condition = {};
    condition[operator] = operand;
    return condition;
  }

operator  
  = whitespace operator:([><=] / '!=') whitespace {
    return operator;
  }

operand  
  = whitespace value:(number / string) whitespace {return value;}

number  
  = value:('0' / integer) {return Number(value);}

integer  
  = $([1-9][0-9]*)

string  
  = "'" value:($[^']*) "'" {return value || '';}

whitespace  
  = [ \t\r\n]* {return null;}

openBracer  
  = whitespace '{' whitespace

closedBracer  
  = whitespace '}' whitespace

Если его использовать, то вот такой "запрос":

{
    User {
       id > 3,
       email
    }

    Page {
       name = 'mainpage',
       someNestedFields {
          subRoute, id
       }
    }
}

превратится в:

[
   {
      "entityName": "User",
      "fields": [
         {
            "condition": {
               ">": 3
            },
            "field": "id"
         },
         {
            "field": "email"
         }
      ]
   },
   {
      "entityName": "Page",
      "fields": [
         {
            "condition": {
               "=": "mainpage"
            },
            "field": "name"
         },
         {
            "nested": [
               {
                  "field": "subRoute"
               },
               {
                  "field": "id"
               }
            ],
            "field": "someNestedFields"
         }
      ]
   }
]

А это превратить например в mongodb запросы — очень просто. В один из следующих разов напишу как лучше всего итерировать по таким объектам и преобразовывать их в нужные вещи.