# Тестовое задание

## Аутлайн глобальных объектов в исходном коде Python

### Описание

Если вы пользуетесь продвинутым редактором кода (например, VSCode), вы наверняка встречали вкладку Outline. В этой вкладке отображается структура открытого файла: определенные в нем классы, функции и т.д. Вот пример, как это выглядит в редакторе VSCode с открытым Python-файлом:


В файле определены три функции (`ls`, `ping_server`, `load_file`), внутри которых используются переменные с указанными именами.

Определить такой аутлайн можно на этапе синтаксического анализа исходного кода. На этом этапе входящий код превращается в поток токенов, которые затем выстраиваются в абстрактное синтаксическое дерево (**AST**). В процессе обхода этого дерева можно найти нужные глобальные объекты и определить их свойства. Подробнее про синтаксический анализ можно почитать, например, в книге *Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты*.

Существуют разные подходы к реализации синтаксического анализа. Один из таких подходов — использование универсального инструмента для описания т.н. грамматики языка, который умеет генерировать код разборщика по этой грамматике. Подробнее про формальные грамматики и языки можно прочитать, например, в книге *Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования*.

Один из таких инструментов — [ANTLR](https://www.antlr.org/). С его помощью можно описать грамматику вашего языка программирования (или любого другого формата данных), а затем сгенерировать код разборщика этого языка, который по входному файлу строит AST. Как использовать ANTLR достаточно подробно описано в его [документации](https://github.com/antlr/antlr4/blob/master/doc/index.md).

### Задание

Вам предлагается написать программу, которая будет собирать *упрощенные* аутлайны для исходного кода на Python. На вход программе подается список Python-файлов. На выходе программа должна записать в некоторую базу данных информацию об этих файлах — для каждой глобальной функции или класса:

* имя исходного файла
* тип объекта (функция/класс)
* имя объекта
* отступ начала и отступ конца определения объекта в файле

Обратите внимание: речь идет только о *глобальных* объектах, доступных из корня модуля. Функции/классы, определенные внутри другого определения, рассматривать не нужно.

Ваша программа может быть написана на любом языке программирования. Для построения AST-а исходного кода предлагается использовать ANTLR. Он поддерживает генерацию в различные языки программирования: С++, Python, Java, [и др.](https://github.com/antlr/antlr4/blob/master/doc/targets.md). В качестве выходной базы данных можно также использовать любое удобное вам решение (будет ещё лучше, если вы аргументируете этот выбор), например: SQLite, PostgreSQL, Redis, MongoDB, и т.д. Но уделять особое внимание базе данных в этом задании не стоит.

### Дополнительное задание

Если вы успешно справились с первой частью и хотите больше развлечений, вам предлагается реализовать тоже самое, но с использованием инструмента [Kaitai Struct](https://kaitai.io/) для синтаксического разбора исходников. Этот инструмент также поддерживает большое число языков программирования.
В конце вам предлагается сравнить эти два решения: какое на ваш взгляд лучше и почему, какие плюсы и минусы обнаруживаются у инструментов в рамках этой задачи.

### Подсказки

* Самостоятельно описывать всю грамматику языка Python — это долго. Слава Богу, ANTLR весьма распространенный инструмент!
* Из личного опыта: рантайм ANTLR для Python весьма дружелюбный, в отличае от рантайма для C++ (второй может и не собраться вовсе). Выбор остается за вами.

## Теоретические знания

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

* структуры данных и алгоритмы на них
* теория формальных языков (грамматики, автоматы)
* теория графов (виды и свойства, представления, алгоритмы)
* теория групп (основные понятия и утверждения)
* архитектура компьютера (процессор, регистры, ABI, память)
* операционные системы (процессы, потоки, синхронизация, IPC, Linux)

Список источников, который может быть полезен:

* Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования.
* Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты.
* Таненбаум Э. Архитектура компьютера.
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ.
* Google