Автор Гілка: frawk — аналог AWK написаний на Rust з використанням LLVM 12  (Прочитано 393 раз)

Відсутній Володимир Лісівка

  • Адміністратор ЩОДО
  • Видавець
  • *****
  • дописів: 3646
  • Карма: +6/-0
  • Програміст
frawk — це аналог AWK, але з підтримкою екранованих полів у CSV та TSV. Багато функцій є реалізовані, але є відмінності. Більшість розширень gawk не є реалізованими. Багато скриптів для AWK працюють без змін, але не всі. Frawk значно швидший за Python чи AWK, а також підтримує розпаралелення роботи на кілька процесорів. На відміну від AWK, frawk використовує агресивну буферизацію, а не працює порядково, і тому не підходить для інтерактивних сценаріїв.

Сторінка проєкту: https://github.com/ezrosent/frawk
« Змінено: 2022-02-15 16:51:30 від Володимир Лісівка »
[Fedora Linux]

Відсутній Володимир Лісівка

  • Адміністратор ЩОДО
  • Видавець
  • *****
  • дописів: 3646
  • Карма: +6/-0
  • Програміст
# Огляд frawk

*Цей документ передбачає деякі базові знання з Awk. Я виявив, що [Awk за 20 хвилин](https://ferd.ca/awk-in-20-minutes.html)
є надійним вступом, тоді як [**сторінка Гримуара**](https://www.grymoire.com/Unix/Awk.html)
містить більше деталей. Відповідно до загальноприйнятої практики, я був
непослідовним у цьому репо з тим, як я використовую великі літери в
«AWK».*

Мій примірник [книги про AWK](https://en.wikipedia.org/wiki/The_AWK_Programming_Language)
починається з простого повідомлення:

> Користувачі комп'ютерів витрачають багато часу, виконуючи прості
> механічні маніпуляції з даними — змінюючи формат даних,
> перевіряючи їх достовірність, знаходячи елементи з певною властивістю,
> додаючи числа, друкуючи звіти тощо\... Awk — це мова програмування,
> яка дозволяє виконувати такі завдання за допомогою дуже коротких
> програм.

Сьогодні я вважаю, що цей діагноз вірний: я проводжу багато часу,
займаючись дрібним текстом. Незважаючи на всі його недоліки як мови, я
вважаю, що Awk є дуже цінним інструментом, коли така «коротка програма»
є бажаною. Я написав frawk, щоб мати можливість писати програми Awk за
інших обставин. Це не означає, що я хочу, щоб frawk був версією Awk з
функціями вищого рівня; Я ціную, що Awk рідко уникає лабораторії
однорядкових програм і не має бажання писати великі програми мовою,
подібною до Awk.

Frawk усуває два основних недоліки, які я знайшов у Awk.

1.  Відсутність підтримки структурованих вхідних даних у форматі CSV.

2.  Іноді — невдала продуктивність.

Ми можемо взяти кожен з них по черзі, а потім перейти до того, як
реалізується frawk. Перш ніж заглибитися в бур'яни, я хочу пояснити, що
моєю головною метою при запуску цього проекту було дізнатися щось нове:
я хотів написати невеликий компілятор, я хотів дізнатися про LLVM і
хотів зробити базовий статичний аналіз. З цього приводу frawk мав
неперевершений успіх.

**Frawk** все ще неповний. Я виявив, що
цього достатньо для моїх повсякденних сценаріїв, але деякі
функції Awk ще не реалізовані, і реалізація, ймовірно, набагато менш
стабільна, ніж ті, які ви знаєте і любите. Якщо відкинути ці
застереження, ось чому я думаю, що frawk цікавий.

## Трохи структуровані дані

Frawk з опцією `-i csv` буде належним чином аналізувати та екранувати
дані CSV. У цьому розділі пояснюється, чому це цінно.

Awk обробляє дані рядок за рядком, розбиваючи за допомогою «роздільника
записів», який (по суті) є регулярним виразом. Це означає, що написати
сценарій досить легко:

```awk
awk - F',' ' NR > 1 { SUM += $2 } END { print SUM }'
```

підсумувати другий стовпець у файлі, де поля завжди розмежовують комами.
Наступне введення дасть `6`.

    Item,Quantity
    Carrot,2
    Banana,4

Однак сценарій дасть неправильний результат, якщо вхідним є файл CSV з
вбудованими комами в деяких полях, наприклад:

    Item,Quantity
    Carrot,2
    "The Deluge: The Great War, America and the Remaking of the Global Order, 1916-1931", 3
    Banana,4

У цьому випадку другим полем третього рядка буде текст «Америка та
перебудова глобального порядку», який буде мовчки примусово приведений
до числа 0, тим самим нічого не вносячи в загальну суму та занижуючи
суму на 3.

Іншими словами, стандартний синтаксис посилань у Awk на стовпці за
допомогою `$1`, `$n`, тощо, може не працювати, якщо вхідним є
екранований файл CSV. На практиці я виявив, що не можу довіряти Awk у
роботі з великим файлом CSV, де я не можу вручну перевірити, чи немає в
полях вбудованого «`,`». Але frawk з опцією `-i csv` буде належним
чином аналізувати та екранувати дані CSV. Awk — це досить виразна
мова, якою можна було б розібрати CSV вручну, але це громіздко й
неефективно.

## Ефективність та спеціально створені інструменти

frawk часто набагато швидший, ніж такі утиліти, як
[gawk](https://www.gnu.org/software/gawk/) і [mawk](https://invisible-island.net/mawk/), під час аналізу великих файлів даних або виконання особливо
інтенсивних обчислень. Основними причинами вищої продуктивності frawk є:

1.  frawk визначає типи для своїх змінних, тому він вирішує, які змінні
    є числами, а які рядками, перш ніж запустити програму. Це може
    прискорити арифметику в жорстких циклах, а також усуває
    розгалуження, коли справа доходить до виконання примусу між рядками
    та числами. frawk досягає цього, зберігаючи майже всю семантику Awk:
    єдині помилки типу, які дає frawk, це також помилки типу в Awk.

2.  Той факт, що frawk створює типізоване подання, дозволяє йому
    генерувати досить простий CLIF або LLVM IR, а потім JIT цей IR для
    машинного коду під час виконання. Це дозволяє уникнути накладних
    витрат на перекладач ціною кількох мілісекунд часу під час запуску.
    frawk надає інтерпретатор байт-коду (увімкнений за допомогою
    параметра `-Binterp`) для менших скриптів і для допомоги в
    тестуванні.

3.  frawk використовує деякі досить новітні методи [ефективної перевірки UTF-8](https://github.com/lemire/fastvalidate-utf-8),
    [аналізу CSV](https://github.com/geofflangdale/simdcsv)
    та [розбору чисел з плаваючою комою](https://github.com/lemire/fast_double_parser).
    Крім того, він використовує високоякісні реалізації [регулярних виразів](https://github.com/rust-lang/regex)
    і [стандартних колекцій](https://github.com/rust-lang/hashbrown), а також кілька інших корисних бібліотек від спільноти Rust.

Той факт, що в існуючих реалізаціях Awk, як правило, не вистачає великої
підтримки CSV, у поєднанні з слабкою продуктивністю на більших наборах
даних у порівнянні з такою мовою, як Rust, означало, що розробники
вдалися до створення спеціальних інструментів для обробки файлів CSV і
TSV. Такі інструменти, як [xsv](https://github.com/BurntSushi/xsv) і
[tsv-utils](https://github.com/eBay/tsv-utils),
чудові; якщо ви ще не перевірили їх і помічаєте, що обробляєте великі
обсяги табличних даних, варто потрохи їх переглянути. Але хоча ці
інструменти швидкі, вони не є повною заміною Awk. Вони не забезпечують
повноцінної мови програмування, і виконувати з ними навіть помірно
складні операції може бути громіздко.

Я виявив, що навіть для коротких програм frawk працює порівняно з xsv
для даних CSV і в 2-3 рази швидше для даних TSV порівняно з tsv-utils.
frawk може виконувати запити, подібні до tsv-utils, до даних CSV за
значно менший час, ніж `csv2tsv` може
конвертувати дані в TSV. Я думаю, що це досить хороший компроміс, якщо
ви хочете виконати операцію вищого рівня, яку ці та інші інструменти не
підтримують. Перегляньте документ із [контрольними показниками](https://github.com/ezrosent/frawk/blob/master/info/performance.md),
щоб отримати жорсткі цифри щодо цього.

## Структура frawk

frawk структурований як звичайний компілятор та інтерпретатор. За
допомогою вихідного коду frawk аналізує його, перетворює на кілька
проміжних уявлень, генерує код нижнього рівня та виконує його.

1.  [Лексер](https://github.com/ezrosent/frawk/blob/master/src/lexer.rs)
    токенізує вихідний код frawk.

2.  Синтаксичний аналізатор створює абстрактне синтаксичне дерево (
    [AST](https://github.com/ezrosent/frawk/blob/master/src/ast.rs)
    ) з потоку маркерів.

3.  AST перетворюється на нетипований контрольний потоковий графік (
    [CFG](https://github.com/ezrosent/frawk/blob/master/src/cfg.rs)
    ). Ми виконуємо [перетворення](https://github.com/ezrosent/frawk/blob/master/src/dom.rs)
    [SSA](https://en.wikipedia.org/wiki/Static_single_assignment_form)
    на цьому CFG.

4.  З CFG у формі SSA [алгоритм
    висновку](https://github.com/ezrosent/frawk/blob/master/src/types.rs)
    призначає типи всім змінним у програмі.

5.  Враховуючи нетипований CFG і результати алгоритму висновку, ми
    можемо створити типізований CFG з явними інструкціями байт-коду. (Це відбувається [тут](https://github.com/ezrosent/frawk/blob/master/src/compile.rs) .)

6.  Звідти код опускається до однієї з (a) [байт-інструкцій](https://github.com/ezrosent/frawk/blob/master/src/bytecode.rs)-коду,
    які можна [інтерпретувати](https://github.com/ezrosent/frawk/blob/master/src/interp.rs)
    безпосередньо, (b) [LLVM-IR](https://github.com/ezrosent/frawk/blob/master/src/codegen/llvm/mod.rs),
    який компілюється JIT і потім запускається, або (c)
    [cranelift](https://github.com/ezrosent/frawk/blob/master/src/codegen/clif.rs).

Більшість із цього є досить стандартним. Перші кілька кроків можна
знайти (наприклад) у [Книзі тигрів](https://www.cs.princeton.edu/~appel/modern/ml/).
Я використав це як основне посилання, а також читав про альтернативи
алгоритму Ленгауера-Тарьяна для побудови SSA, які були опубліковані
після «Книги тигрів».

Ви можете переглянути текстове представлення нетипізованого CFG,
передавши прапор `--dump-cfg` у frawk. Байт-код і LLVM можна
переглянути за допомогою параметрів `--dump-bytecode` і `--dump-llvm`.
Останній буде оптимізований; `-O0`. Перехід приблизно покаже LLVM,
створений frawk.

Щоб уникнути тривалого часу компіляції та складних збірок, код LLVM і
Cranelift виконує виклики функцій у той самий час виконання, яке
використовується для інтерпретації інструкцій байт-коду. Переміщення
більшої частини коду часу виконання в згенерований код під час
складання, ймовірно, призведе до швидшої програми, оскільки це дасть
LLVM (і меншою мірою, Cranelift) більше можливостей для вбудовування й
оптимізації викликів під час виконання. Поточний підхід допомагає
скоротити час складання, а налаштувати збірку просто.

### Статичний аналіз

Я прочитав чудову книгу *[Static Program Analysis](https://cs.au.dk/~amoeller/spa/)*,
створюючи frawk. Серед іншого, він показав мені, що багато
властивостей програми можна апроксимувати як рішення (потенційно
рекурсивних!) рівнянь, визначених у відповідному частковому порядку,
якщо функції, що визначають ці рівняння, є [монотонними](https://en.wikipedia.org/wiki/Monotonic_function%23Monotonicity_in_order_theory).
Крім того, можна розв'язати ці рівняння, пропустивши їх через прості
мережі [в стилі розповсюдження](https://www.youtube.com/watch?v%3Ds2dknG7KryQ),
поки їх значення не перестануть змінюватися. Основними прикладами цього є:

-   Виведені [типи](https://github.com/ezrosent/frawk/blob/master/src/types.rs)
    для змінних frawk. Щоб дізнатися більше про виведення типу,
    перегляньте [цей документ](https://github.com/ezrosent/frawk/blob/master/info/types.md).

-   [Висновок, які стовпці не потрібно
    аналізувати.](https://github.com/ezrosent/frawk/blob/master/src/pushdown.rs)

-   Визначення , на [які глобальні змінні](https://github.com/ezrosent/frawk/blob/0cf6bd7554ba14193f32337ea54bd1a8f1401f1f/src/compile.rs#L694)
    посилається функція, і функції, які вона викликає.

-   [Виключення](https://github.com/ezrosent/frawk/blob/master/src/input_taint.rs)
    потенційно небезпечних викликів оболонки.

Все це було реалізовано за допомогою дуже корисної бібліотеки [petgraph](https://github.com/petgraph/petgraph).

## Відмінності від AWK

структура і мова frawk запозичені майже оптом з Awk; використання frawk
дуже схоже на використання mawk, nawk або gawk. frawk також підтримує
багато складніших функцій Awk для реалізації, наприклад printf, і
визначені користувачем функції. Хоча багато поширених ідіом від Awk
підтримуються у frawk, деякі функції відсутні, а інші надають тонко
несумісну семантику. Будь ласка, подайте запит на функцію, якщо певний
елемент поведінки, на який ви покладаєтесь, відсутній; ніщо в реалізації
frawk не перешкоджає можливостям стандартної мови Awk, хоча деякі можуть
бути проблемними для реалізації.

Цей список відмінностей не є вичерпним. Зокрема, я не був би здивований,
якщо б виявив, що в парсері frawk є помилки.

### Чого не вистачає

-   За замовчуванням frawk використовує бібліотеку
    [ryu](https://github.com/dtolnay/ryu)
    для друку чисел з плаваючою комою, а не змінну `CONVFMT`. Явна зміна
    точності виводу з плаваючою комою вимагає відповідного виклику
    `printf `або `sprintf`.

-   `next`, або `nextfile` підтримуються у frawk, але їх можна
    викликати лише з основного циклу. Я не зустрічав жодного сценарію
    Awk, який використовує будь-яку з цих команд всередині функції, і це
    велике спрощення просто заборонити цей випадок. Знову ж таки, дайте
    мені знати, чи це важливий для вас варіант використання.

-   Багато розширень з gawk (наприклад, спільні процеси, багатовимірні
    масиви) також не реалізовані. Більшість «книжкових» вбудованих
    функцій і команд awk на даний момент підтримуються, але, будь ласка,
    повідомте про проблему, якщо ви помітили якісь прогалини.

-   Хоча це ніколи не пробували, я щиро сумніваюся, що frawk буде
    працювати добре — або взагалі — на 32-розрядній платформі. Я
    підозрюю, що він буде працювати набагато повільніше на 64-розрядній
    архітектурі без x86.

### Що нового

-   frawk підтримує параметри командного рядка, які розбивають усі
    вхідні дані (незалежно від значення `-i csv`) відповідно до
    форматів CSV та TSV, призначаючи необробленому рядку та N-му полю в
    поточному рядку, повністю екрановані. Існує також еквівалентна
    функція для вихідних CSV-екранованих рядків (увімкнено за
    допомогою). `-i tsv FS RS $0 $N -o csv -o tsv`

-   frawk має вбудовану функцію `join_fields`, яка створює рядок
    певного діапазону вхідних стовпців.

-   frawk надає функцію `int` для перетворення скалярного значення в
    ціле число, а також функцію `hex` для перетворення шістнадцяткового
    рядка в ціле число. Він також підтримує шістнадцяткові числові
    літери.

-   Для сценаріїв, які запускаються з одним із параметрів `icsv`,
    `itsv`, сценаріїв, які розбиваються лише пробілами, або сценаріїв,
    які використовують лише один однобайтовий запис і роздільник полів,
    frawk підтримує [паралельне](https://github.com/ezrosent/frawk/blob/master/info/parallelism.md)
    виконання сценарію .

-   Далі побітові оператори `gawk `підтримуються через вбудовані
    модулі `and`, `or`, `compl`, `lshift`, `rshift `і `xor`.
    Frawk також підтримує `rshiftl` — логічний зсув вправо. На
    відміну від `gawk`, функції `and`, `or` і `xor` не є змінними.

-   Функції frawk можуть повертати масиви, виклики функцій можуть
    зʼявлятися в позиції масиву для циклу for-each.

-   За допомогою прапорця `-H` frawk аналізує перший рядок введення (без
    оновлення `NR` або `FNR`) і заповнює вбудовану змінну `FI` вмістом
    полів у першому рядку, що відповідає їхньому індексу. Отже, у
    сценарії, який аналізує файл із полем під назвою «count» у стовпці
    6, вираз `$FI["count"]`поводиться як `$6`. Реалізація цієї функції у
    frawk добре поєднується з аналізом проекції.

### Чим відрізняється

Жодна з цих відмінностей не є фундаментальною для підходу frawk; без них
*можна* обійтися, за певну ціну. Повідомте мені, якщо ви виявите більше
розбіжностей або виявите, що наведене нижче є серйозною перешкодою:

-   *Синтаксис регулярних* виразів frawk наразі використовує синтаксис
    [регулярних](https://docs.rs/regex/1.3.7/regex/)
    виразів Rust. Це схоже, але не тотожне, до синтаксису регулярного
    виразу Awk. Я розглядав можливість впровадження власного механізму
    регулярних виразів або компіляції регулярних виразів Awk у регулярні
    вирази rust; це просто не те, що я встиг зробити.

-   *Порівняння рядків.* Порівняння одного рядка з іншим завжди
    використовує лексикографічне впорядкування. Порівнюючи два рядки,
    Awk спочатку перевіряє, чи обидва рядки є числами, а потім порівнює
    їх чисельно, якщо вони є. Я вважаю цю семантику досить
    неінтуїтивною: з одного боку, це означає, що два «рівних» рядки
    можуть хешувати різні значення в масиві. Це також означає, що досить
    важко чітко вибрати лексикографічне порівняння. З іншого боку,
    вибрати числове порівняння досить легко: просто додайте один з
    операндів до 0. Щоб зберегти деякі ідіоми, frawk приводить усі
    операнди до чисел, якщо один з їхніх операндів є числом; це зберігає
    звичайний варіант використання (наприклад) фільтрації числового
    стовпця за числовою константою. Я виявив, що ця семантика є більш
    передбачуваною, а також більш простою у реалізації.

-   *Нульові значення та точки з\'єднання.* Нульові значення у frawk
    іноді можуть бути приведені до цілих чисел. Наприклад
    `if (0) { x = 5 }; printf "[%s]", x;`, буде друкувати `[]` в
    Awk і друкуватиме `[0]` у frawk. Це основна причина, з якої підхід
    frawk до типів може «протікати» в реальні програми.

-   *UTF-8* frawk може приймати довільні байти, але регулярні вирази та
    printf підтримують UTF-8. frawk не перевіряє введення за
    замовчуванням, але прапорець `--utf8 `дозволяє ефективну перевірку
    UTF-8 для всіх введених даних.

-   *Пакетування пакетів frawk* для читання та запису даних досить
    агресивне в порівнянні з більшістю реалізацій Awk, з якими я
    стикався. Це робиться в основному з міркувань продуктивності і
    відображає передбачуваний випадок використання «пакетних» сценаріїв
    обробки даних.

-   frawk підтримує створення підоболонки через синтаксис
    `<string> | getline`, або `print[f] ... | <string>,` а також вбудовану
    функцію `system`. Наскільки я розумію, подібні функції (де довільний
    рядок передається оптом в оболонку) вважаються антишаблонами, і [в деяких мовах](https://www.python.org/dev/peps/pep-0324/%23id14)
    їх визнали застарілими, оскільки вони полегшують несанкціонованому
    введенню користувача в оману, щоб перетворити його дані в
    підоболонку, та потенційно робити з машиною користувача недобрі чи
    небажані дії. Щоб пом'якшити це, frawk реалізує [статичний аналіз](https://github.com/ezrosent/frawk/blob/master/src/input_taint.rs)
    дір, який суттєво обмежує набір рядків, які можна передати в
    оболонку. frawk також забезпечує обхід для випадків, коли вхідні
    дані є довіреними або аналіз є занадто консервативним: Прапорець
    `-A` виключає користувачів із аналізу дір. Я відкритий для відгуків
    щодо розширення або модифікації цієї функції.

« Змінено: 2022-02-16 23:40:32 від Володимир Лісівка »
[Fedora Linux]