Attoparsec, инкрементальный парсинг и баги

[metaclass]

Убил наверно дня 4 на поиск бага в простейшем парсере.
Вводная: есть девайс, который непрерывно пишет данные вида:
Start
ConvertData
Sensor=0
... some uninteresting data
Value=23.4
... some uninteresting data
Sensor=1
... some uninteresting data
Value=23.5
... some uninteresting data
ADC
Channel=0
Value=345
Start
..далее все повторяется

Это дело читается енумератором и подается на парсер, завернутый в enumeratee. Парсер сделан на основе attoparsec, в основном, по той причине, что он легко конвертируется в iteratee-enumeratee.
Ключевой момент с этим парсером в том, что он умеет инкрементальный парсинг. Т.е. я подаю ему данные по кускам, он возвращает continuation, если ему недостаточно данных для продолжения работы. Именно поэтому он хорошо интегрируется с пакетом enumerator. Кроме того, мне упорно мерещится, что этот парсер сам по себе является реализацией Iteratees, т.к. их типы данных почти изоморфны друг другу.
Парсер состоит из двух уровней: первый разбирает поток в последовательность значений DeviceMsgs с двумя конструкторами:

 data DeviceMsg = 
      Header BS.ByteString 
    | KeyValue BS.ByteString BS.ByteString
    deriving (Show,Eq)

Ссылка на код парсера: parseDeviceMsg
Второй уровень парсера анализирует последовательность уже DeviceMsg. Там имеется парсер последовательности "[Sensor/пропустить ненужные данные/Value/пропустить ненужные данные]"
И вот конкретно парсер для пропуска ненужных данных "skipMany isNotValue" ломается с грохотом и треском, если:
1) подавать данные не одной строкой, а по частям, при этом разбиение на части происходит перед или внутри строки Value
2) не добавить в парсер DeviceMsg пропуск whitespace после сообщения (строка с комментарием bugfix в исходнике по ссылке.

Т.е. суть бага: если парсеру "skipMany isNotValue" подавать данные с разбиением на границе не-срабатывания isNotValue (т.е. там где этот парсер должен закончить свою работу) - он не может сделать backtracking на позицию "до не-срабатывания isNotValue". Но только в том случае, если isNotValue не ждет в конце себя whitespace.

Чтобы выделить и найти ошибку, пришлось по очереди:
0)на каждом шаге обкуриваться исходниками Control.Applicative, Data.Attoparsec и прочего )
1)запилить неисчислимые количества traceShow во все углы программы
2)заменить чтение из ком-порта на подачу данных из файла
3)вычитать из девайса строки ровно в той последовательности кусков в которой их выдает enumerator и сделать из этого список
4)сделать функцию которая инкрементально кормит списком аттопарсековые парсеры.
5)сделать функцию которая берет строку и индекс в ней, разбивает ее на список из двух строк "до индекса" и "после индекса", подает их на парсер и проверяет - сломалось или нет. Это все делается в цикле по индексу от 0 до конца строки. Это показало что валится, если строка разбита в районе Value.
6)Сделать тестовый список, гарантированно ломающий инкрементальный парсинг
7)Уменьшать список и его парсеры, добиваясь, чтобы баг c разницей результатов парсинга [l1,l2] и [BS.append l1 l2] все равно проявлялся.
8)Свести баг парсера к вызову skipMany isNotValue
9)Начать модифицировать парсер parseDeviceMsg в попытке понять "что здесь воще творится?".
10) Добавить к нему "skipWhile isSpace_w8" посмотреть что все заработало, нихера не понять.

В общем, я формального способа понять, почему в одном варианте оно работает, в другом нет - не знаю. Вижу что проблема в backtracking+инкрементальный парсинг, но внутренности attoparsec, например - это ад из cps и адовых техник оптимизации.
Я даже не знаю, можно ли это вообще хотя бы в теории запустить под отладчиком.
Разве что отладчик будет рисовать граф и его редуцировать пошагово.
И да, "если прога на хаскеле компилируется - это не значит что она работает".

Comments

Не понимаю я вас

[plumqqz.livejournal.com]

— А давайте вприсядку трахаться!
— Зачем?
— И напляшемся и наипемся!

Re: Не понимаю я вас

[metaclass.livejournal.com]

Ну, как-то так:)

Вот поэтому я обычно пишу свои парсеры

[schegloff.livejournal.com]

Все же четыре дня на отладку чужих глюков - многовато. Я так на каждую стороннюю библиотеку смотрю как сапер на мину.

Бездны сатаниские!

[plumqqz.livejournal.com]

Надеюсь, в продакшн вы эту сумрачную гимнастику сумрачного ума не тащите? :-)

Re: Бездны сатаниские!

[metaclass.livejournal.com]

Тащу и буду тащить :)
Пока руководство не убедит меня, что этого делать не надо.

Re: Вот поэтому я обычно пишу свои парсеры

[metaclass.livejournal.com]

Я не уверен что глюки чужие. Проблема в том, что в данном случае вообще невозможно понять, где они.

Поосторожнее бы надо

[plumqqz.livejournal.com]

Карму ведь себе портите.

[necropsih.livejournal.com]

вот бы минитуториал или хотя бы пинок в сторону документации по этому чуду, а то то что я у Brian O'Sullivan видел мне понять attoparsec не помогло

[metaclass.livejournal.com]

Ага, с документацией и объяснением происходящего кромешный ад.

[berezovsky.livejournal.com]

Упс

[schegloff.livejournal.com]

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

[awson.livejournal.com]

И вот конкретно парсер для пропуска ненужных данных "skipMany isNotValue" ломается с грохотом и треском

А как выглядит isNotValue? И что значит "ломается с грохотом и треском"?

[metaclass.livejournal.com]

isNotValue - берет одно сообщение из parseDeviceMsg, потом, если оно имеет вид KeyValue "Value" _ -> fail иначе return ()
Т.е. парсер, ничего не возвращающий, но успешно отрабатывающий только в случае, если пришло не сообщение Value=...

[gds.livejournal.com]

это же х-ь, там всё должно быть понятно по типам111

Замечание от К.О.

[trueblacker.livejournal.com]

  1 attoParsec = 3.08568025 centimeters

[eminglorion.livejournal.com]

Это баг аттопарсека. Вот что происходит:

1. skipWhile isSpace_w8 пропускает пробелы и в какой-то момент запрашивает часть символов из Value=1, эти символы идут в добавку (которая Added)
2. работает парсер вида a <|> b, где a успешно отработает, тогда из определения (<|>) видим, что вся добавка, которую мы получили до входа в a будет отброшена.
3. дальше по списку идёт испорченная добавка, а результате восстанавливаем неправильное состояние.

Вот мой код и пример как вопроизвести проблему:

isNot = do
  skipWhile (== ' ')
  val <- A.takeWhile1 (notIsSpaceOrEqual) <|> fail ""
  when (val == "Value") $ fail "Something"
  return ()

myParser :: Parser ()
myParser = skipMany isNot

*Atto> foldl feed (parse myParser "") $ map B.singleton "Value =1 Value2"
Done "alue =1 Value2" ()
*Atto> foldl feed (parse myParser "") $ "Va" : map B.singleton "lue =1 Value2"
Done "lue =1 Value2" ()

Тут я вижу два варианта: 1. убрать skipWhile isSpace_w8 перед (<|>); 2. использовать безоткатные парсеры (задача позволяет).

[eminglorion.livejournal.com]

Добью ещё пример, чтоб убедительнее:

isNot = do
  val <- A.takeWhile1 (notIsSpaceOrEqual) <|> fail ""
  skipWhile (== ' ') <|> fail ""
  when (val == "Value") $ fail "Something"
  return ()

*Atto> foldl feed (parse myParser "") $ map B.singleton "Value =1 Value2"
Done "=1 Value2" ()

[metaclass.livejournal.com]

Да, вот и я думаю, не перестать ли извращаться с аттопарсеком и сделать влоб и проще :)

[awson.livejournal.com]

Удивительно. Я сам аттопарсеком пользоваться даже не пытался, но, вроде, всякие веб-фреймворки его используют. Поверить, что этот баг себя не проявил в сколько-нибудь нетривиальном парсере очень трудно. Т.е. должно быть известно, что инкрементальный аттопарсек не работает, и следует использовать только неинкрементальный? Я заглянул в код аттопарсека и не увидел там никаких указаний на это.

Но позвольте — как же он служил в очистке? (C)

[awson.livejournal.com]

Нужно писать багрепорт. На этот баг *должны* были наткнуться раньше, следовательно наткнулись, но (что скорее всего) так и не изолировали и/или поленились написать багрепорт. Поэтому он все еще здесь. Анализ eminglorion'a очень ценен и не должен пропасть.

Re: Бездны сатаниские!

[idispatch.livejournal.com]

потом товарищ уволится, или его наконец уволят, сей говнокод выкинут к ебеней матери и вменяемый программист перепишет обычным scanf'ом за пару часов, и спокойно пойдет на обед. код будет работать на порядки быстрее и занимать меньше будет, любой другой программист поймет и сможет поддерживать.
к чему вся эта рекурсивная самоебля?

Re: Бездны сатаниские!

[metaclass.livejournal.com]

Этот код не выкинут, он для домашней метеостанции :)
А на работе я предусмотрительно ничего не делаю, чтобы другие потом могли понять.

[eminglorion.livejournal.com]

> но, вроде, всякие веб-фреймворки его используют.

Если взглянуть на attoparsec, то можно заметить, что он состоит из двух частей (условно): Data.Attoparsec и Data.Attoparsec.Combinator. Проблемы возникли с комбинаторной частью, которая одновременно самая медленная в attoparsec (поэтому её не рекомендуют использовать в документации к attoparsec).

Парсеры из Data.Attoparsec (т.е. takeWhile, skipWhile, scan и прочие) это такие продвинутые итераторы написанные вручную: они быстрые, смотрят только на один символ вперёд. Отсюда два следствия: 1) обычно их и используют; 2) у них нет проблем с возвратом при инкрементальном разборе.

> Т.е. должно быть известно, что инкрементальный аттопарсек не работает

Вполне возможно, что об этом и не знают, нужно писать автору.

[eminglorion.livejournal.com]

> (поэтому её не рекомендуют использовать в документации к attoparsec)

Хотел сказать, что в документации к attoparsec не рекомендуют использовать комбинаторы:

Use the ByteString-oriented parsers whenever possible, e.g. takeWhile1 instead of many1 anyWord8. There is about a factor of 100 difference in performance between the two kinds of parser.

Re: Бездны сатаниские!

[geovit.livejournal.com]

На работе можно сделать генератор своих прог на хаскеле :-). И класть в репы нормальный код. Не?

[aamonster.livejournal.com]

Выкинуть каку, однозначно.
Если код на функциональном языке менее прозрачен, чем на императивном - нахрена он такой нужен? Так что "ад из cps и адовых техник оптимизации" использовать нельзя, лучше взять какой-нибудь нормальный генератор парсеров, выдающий код на C.

[kurilka.livejournal.com]

генераторы парсеров есть и не под це и неплохо работающие, ваш КО

Re: Бездны сатаниские!

[metaclass.livejournal.com]

Уже :)

[aamonster.livejournal.com]

1. Неважно под что, лишь бы стабильно работало.
2. Те, что под це -
2.1. хорошо обкатаны
2.2. дают шустрый код на выходе

Re: Бездны сатаниские!

[kkirsanov.livejournal.com]

А если жена Code Review учинит?

Re: Бездны сатаниские!

[metaclass.livejournal.com]

Если она этому сможет учинить code review - я смогу спокойно лечь в больничку на анализы на годик-второй :)

Re: Бездны сатаниские!

[cp-poster.livejournal.com]

Ну перепеши, пару часов это не много даже для такого, без сомнения, высокооплачиваемого специалиста как ты. Челендж аццептед?

[aleksey khudyakov (from livejournal.com)]

А у меня всё работает. Можно полны текст программы с импортами?

[eminglorion.livejournal.com]

http://hpaste.org/54413

Re: Бездны сатаниские!

[idispatch.livejournal.com]

don't see the challenge here to start with

Re: Бездны сатаниские!

[idispatch.livejournal.com]

> А на работе я предусмотрительно ничего не делаю, чтобы другие потом могли понять.

загадочные уходят в первую очередь. из опыта.