Размещено на http: //www. allbest. ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет компьютерных наук

Департамент программной инженерии

Выпускная квалификационная работа

по направлению подготовки 09.03.04 «Программная инженерия»

на тему «Приложение для переназначения клавиатурных сочетаний для Linux»

Научный руководитель: канд. техн. наук, доцент

Доцент образовательной программы С.Л. Макаров

Выполнил: студент группы БПИ161

4 курса бакалавриата А.В. Анюров

образовательной программы «Программная инженерия»

Москва 2020



Реферат

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

Данная работа призвана предоставить мощную и расширяемую среду для конфигурации пользовательского ввода и автоматизации рутинных действий для пользователей Linux.

Задачами работы являются:

1. Проектирование скриптового языка, который будет использоваться в процессе конфигурации пользователями;

2. Проектирование и разработка интерпретатора скриптового языка;

3. Проектирование и разработка стандартной библиотеки;

4. Проектирование протокола взаимодействия между серверной и клиентской частями приложения;

5. Проектирование и разработка серверной части приложения;

6. Проектирование и разработка консольного клиента;

7. Проектирование и разработка графического клиента;

8. Публикация разработанного приложения.

Ключевые слова: переназначение клавиш, комбинаторный парсинг, интерпретация, автоматизация, evdev, Lisp, Linux.

Работа содержит 74 страницы, 3 главы, пять приложений, 19 использованных источников, 25 листингов, 10 рисунков, 6 таблиц.



Abstract

Nowadays, as Linux popularity is rising for desktop users the total amount of applications, daemons and utilities written for Linux is increasing as well. Therefore, even beginner users have a need to configure a large number of applications, execute a lot of different commands and invoke scripts in their daily routine. In addition, certain users struggle with inconsistencies between their typing habits, keyboards, and low-level system configuration files, which leads to unproductive workflow.

This paper proposes the project of an application that helps its users to construct a more coherent workflow through introduction an environment that allows remapping of key chord sequences into necessary actions and execute code written in the embedded scripting language.

The tasks of the work are:

1. Designing the embedded scripting language that can be used by the users for the configuration of their workflow;

2. Designing and development of the interpreter of the embedded scripting language;

3. Designing and development of the standard library of the embedded scripting language;

4. Designing the communication protocol between server and console and graphical clients;

5. Designing and development of the server part of the application;

6. Designing and development of the console client;

7. Designing and development of the graphical client;

8. Publication of the application.

Keywords - keyboard remapping, combinatory parsing, code interpretation, automation, evdev, Lisp, Linux. The paper contains 74 pages, 3 chapters, 19 references, five appendices, 25 listings, 10 illustrations, 6 tables.



Содержание

Резюме

Abstract

• Основные определения, обозначения
• Введение
• Глава 1. Обзор и анализ источников, аналогов, выборов методов решения задач
• 1.1 Обзор и анализ источников
• 1.2 Анализ приложений со сходной функциональностью
• 1.3 Выбор методов решения задач
• Глава 2. Используемые методы, модели и инструменты
• 2.1 Теоретическая информация
• 2.1.1 Устройство жизненного цикла событий ввода в ОС Linux
• 2.1.2 Механизм Mutex
• 2.1.3 Механизм Channel
• 2.1.4 Конечный автомат
• 2.1.5 Комбинаторный парсинг
• 2.1.6 Лексическая область видимости
• 2.1.7 Сборка мусора
• 2.1.8 Прототипное наследование
• 2.1.9 Паттерн Arena
• 2.2 Использованные инструменты
• 2.2.1 Язык программирования Rust
• 2.2.2 Язык программирования TypeScript
• 2.2.3 Google Protocol Buffers
• 2.2.4 Node.js
• 2.2.5 Vue.js
• 2.2.6 Electron
• 2.2.7 WebSocket
• 2.2.8 IDE
• Глава 3. Техническая реализация
• 3.1 Архитектура приложения
• 3.2 Скриптовый язык
• 3.2.1 Описание синтаксиса скриптового языка
• 3.2.2 Реализация парсера на языке программирования Rust

3.2.2.1 Парсер логических значений

3.2.2.2 Парсер целочисленных значений

3.2.2.3 Парсер значений чисел с плавающей точкой

3.2.2.4 Парсер строк

3.2.2.5 Парсер символов

3.2.2.6 Парсер ключевых слов

3.2.2.7 Парсер литералов объектов

3.2.2.8 Парсер литералов объектов-паттернов

3.2.2.9 Парсер элементов с префиксом

3.2.2.10 Парсер s-выражений

3.2.2.11 Парсер объявления сокращенной функции

3.2.2.12 Парсер синтаксиса разделенных объектов

3.2.2.13 Парсер элемента

• 3.3 Интерпретатор
• 3.3.1 Типы данных
• 3.3.2 Функции
• 3.3.3 Внутреннее устройство
• 3.3.4 Реализация на языке Rust
• 3.4 Стандартная библиотека
• 3.5 Цикл событий
• 3.6 Протокол взаимодействия
• 3.7 Консольный клиент
• 3.8 Графический клиент
• Заключение
• Список использованных источников


Основные определения, обозначения

Клавиша - часть клавиатуры, нажатие на которую провоцирует возникновение событий клавиатуры в операционной системе.

Событие клавиатуры - структура данных, содержащая информацию о нажатии клавиши, отпускании клавиши, удержании клавиши, синхронизации состояния клавиши в операционной системе.

Клавиатурное сочетание - множество одновременно нажатых клавиш.

Модификатор - часть клавиатурного сочетания. Клавиатурное сочетание не может состоять только из модификаторов.

Обычная клавиша - часть клавиатурного сочетания. Клавиатурное сочетание может состоять только из одной обычной клавиши, но не может содержать ноль или более одной обычной клавиши.

Последовательность клавиатурных сочетаний - упорядоченный во времени набор клавиатурных сочетаний.

Действие - нечто, что совершается операционной системой или приложением после нажатия клавиатурного сочетания.

Карта клавиатурных сочетаний - отображение последовательностей клавиатурных сочетаний в действия.

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

Комбинатор парсеров - функция возвращающая парсер. В комбинатор парсеров могут передаваться как парсеры, так и аргументы, не являющиеся парсерами.

Комбинаторный парсер - техника, при которой с использованием комбинаторов парсеров и набора примитивных парсеров, последовательно конструируется парсер, способный разобрать последовательность текстовых символов, удовлетворяющую некоторой грамматике языка.

Лексема - структура, описывающая базовый конструкт языка.

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

Синтаксический анализ - процесс сопоставления последовательности лексем грамматике языка, для которого производится синтаксический анализ. В результате синтаксического анализа создается иерархическая структура, представляющая, как последовательность текстовых символов сопоставляется грамматике языка.

Интерпретация - процесс проведения построчного лексического анализа, синтаксического анализа, выполнения исходного кода.

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

Считыватель - часть интерпретатора, производящую отображение результатов разбора в значения интерпретатора.

Вычислитель - часть интерпретатора, производящая отображение значений интерпретатора, в другие значения, согласно правилам вычисления.

Сборка мусора - техника автоматического управления памятью, призванная освободить память, выделенную под недостижимые объекты.

Ядро Linux - открытое, монолитное, Unix-подобное ядро операционной системы.

Linux - семейство Unix-подобных операционных систем, использующих ядро Linux.

Lisp - семейство языков программирования, вдохновленных языком программирования, разработанном Джоном Маккарти в начале 1960-х годов в Массачусетским технологическом институте.

Атом - последовательность текстовых символов, не разделенная внутри пробелом.

S-выражение - способ представление данных в виде списка. S-выражение состоит из атома, или последовательности из открывающей скобки, последовательности вложенных s-выражений, разделенных пробелами, и закрывающей скобки.

Символ - структура данных, представляющая последовательность текстовых символов.

Cons ячейка - структура данных, представляющая упорядоченную пару из двух значений.

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

Lisp-2 языки - подмножество Lisp языков, в которых в лексических окружения с каждым символом может быть связано ровно два значения. Одно из них называется значением переменной, другое - значением функции.



Введение

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

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

Первая категория пользователей состоит из уверенных пользователей ОС семейства Linux, которые испытывают неудобства от того, что не существует программных решений, которое в полной мере удовлетворит потребности пользователей этой категории. Пользователи этой категории имеют сразу несколько клавиатур, которые имеют разную пространственную и функциональную конфигурацию. В совершенстве освоив метод слепой печати, эти пользователи хотят в полной мере реализовать потенциал использования в работе сразу нескольких клавиатур. Другим фактором, которое причиняет неудобства пользователям этой категории - это абсолютное отсутствие функционала по определению новых модификаторов клавиатурных сочетаний. Конечно, в силу собственной продвинутости, эти пользователи уже как-то обошли эти неудобства путем использования уже существующих утилит, но, из-за недостаточной мощи этих утилит, значительная часть их требований все еще не удовлетворено. Приложение, которое планируется разработать в рамках выпускной квалификационной работы, позволяет своим пользователям конфигурировать ввод сразу нескольких клавиатур, вводить дополнительные модификаторы нажатий клавиатурных сочетаний, осуществлять переназначение последовательностей клавиатурных сочетаний, что удовлетворит многие из потребностей пользователей этой категории.

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

Третья категория пользователей состоит из пользователей нестандартных клавиатур. Эти клавиатуры могут иметь дополнительные клавиши, клавиши, расположенные на стандартных местах, но при их нажатиях, генерирующих нестандартные коды клавиш, или и вовсе состоять только из таких клавиш. В силу недостаточной распространенности пользователей Linux в качестве основной системы, многие из таких клавиатур лишены всякой поддержки в ОС Linux. В результате, из-за невозможности использования этих клавиатур, пользователи этой категории испытывают неудобства. Разрабатываемое приложение, позволяя конфигурировать ввод таких клавиатур, удовлетворит потребности пользователей этой категории.

Цель работы - Разработка приложения, предоставляющего мощное, расширяемое, простое в использовании программное окружение, которое предоставляет гибкие возможности для конфигурации пользовательского ввода и автоматизации рабочего окружения.

Задачи работы:

1. Проектирование скриптового языка, который будет использоваться для конфигурации приложения;

2. Проектирование и разработка интерпретатора скриптового языка;

3. Проектирование и разработка стандартной библиотеки;

4. Проектирование протокола взаимодействия между серверной и клиентской частями приложения;

5. Проектирование и разработка серверной части приложения;

6. Проектирование и разработка консольного клиента

7. Проектирование и разработка графического клиента;

8. Публикация разработанного приложения.

Оставшаяся часть работы состоит из следующих частей:

· В главе 1 приводится обзор источников, анализ приложений, имеющих схожую функциональность с разрабатываемым и использованные во время разработки методы;

· В главе 2 содержится описанию методов, технологий и паттернов разработки, использованных во время разработки;

· В главе 3 содержится подробное описание разработанного приложения;

· В заключении подведены результаты работы и описан план дальнейшей работы над выпускной квалификационной работой.

Приложения содержат техническую документацию, оформленную в соответствии с ЕСПД:

· Приложение А содержит техническое задание на разработку приложения;

· Приложение Б содержит руководство оператора;

· Приложение В содержит программу и методику испытаний;

· Приложение Г содержит текст программы;

· Приложение Д содержит описание языка.



Глава 1. Обзор и анализ источников, аналогов, выборов методов решения задач

пользовательский ввод программирование автоматизация

В данной главе осуществляется обзор и анализ источников, аналогов и выборов методов решения задач.

1.1 Обзор и анализ источников

Linux - семейство операционных систем, основанных на ядре Linux - монолитного, открытого, unix-подобного ядра операционной системы, разработанного в сентябре 1991 года Линусом Торвальдсом [1]. Удовлетворив в свое время потребности GNU сообщества в ядре операционной системы, ядро Linux быстро обрело популярность, и, в наше время используется во множестве устройств от суперкомпьютеров до смартфонов, носимой электроники [2].

В момент загрузки ОС, ядро Linux осуществляет построение файловой системы. Согласно философии Unix - «Все есть файл», взаимодействие с устройствами также осуществляется через файловые дескрипторы. Таким образом, во время построения файловой системы, ядро Linux считывает параметры устройств, создавая для каждого устройства набор файлов в файловой системе, через которые можно взаимодействовать с ними.

Подсистема ввода Linux состоит из набора драйверов, которые взаимодействуют с устройствами напрямую, и набора модулей, которые пересылают события ввода, которые делают события доступными для чтения ядром и пользовательскими приложениями [3].

Lisp - семейство языков программирования, основанных на представлении программы в виде последовательности символических выражений, вдохновленных работой Джона Маккарти «Recursive Functions of Symbolic Expressions and Their Computation by Machine», изданной в апреле 1960 года в Массачусетском технологическом институте [4, 5].

Будучи языком одновременно простым и выразительным, первоначально разработанный язык Lisp послужил источником множества диалектов и других языков программирования, таких как, JavaScript, Lua, Python и многих других [6].

Комбинаторный парсинг - техника, с помощью которой производится последовательная генерация все более сложных парсеров из набора уже существующих парсеров путем их комбинирования с помощью комбинаторов парсеров [7].

Сборка мусора - механизм автоматического управления памятью, в которой, в определенные моменты времени осуществляется освобождение памяти от объектов, которые стали недоступны. Впервые, сборка мусора была предложена Джоном Маккарти в 1960-х годах [5].

Интерпретаторы Lisp традиционно разделяются на 2 составляющие: считыватель и вычислитель. Считыватель производит трансляцию потока текстовых символов в конструкты языка, вычислитель производит вычисление считанных конструктов языка согласно заложенным в него правилам вычисления [8].

Язык программирования Rust является современным языком программирования, используемого для системного программирования в число главных преимуществ которого входит фокусировка на безопасности разработанных приложения, скорости исполнения и простоты разработки многопоточных программ [9, 10].

Язык программирования JavaScript является одним из самых используемых языков программирования, способный исполняться на самых разных платформах от веб-браузеров до серверов и встроенных устройств [11, 12]. Язык имеет очень богатую инфраструктуру, развитое сообщество, и предлагает отличные возможности для построения богатого пользовательского интерфейса [13].

Electron - технология для построения кроссплатформенных приложений с использованием JavaScript, HTML, CSS, позволяющая абстрагироваться от низкоуровневой работы с пользовательским интерфейсом и сфокусироваться на действительно важных аспектах приложения [14].

Vue.js является прогрессивным фреймворком для построения пользовательского интерфейса. Vue.js предоставляет богатые возможности, являясь при этом простым для освоения, выразительным и расширяемым фреймворком [15].

Node.js является асинхронной событийно-ориентированно средой исполнения кода, написанного на языке JavaScript, спроектированной для разработки масштабируемых веб-приложений [16].

Npm является менеджером пакетов языка программирования JavaScript. Npm является стандартным менеджером пакетов среды Node.js. Npm состоит из утилиты командной строки и онлайн базы данных, содержащей сами пакеты [13].

1.2 Анализ приложений со сходной функциональностью

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

· Поддержка Linux (Характеристика 1);

· Открытость (Характеристика 2);

· Поддержка работы с любыми клавиатурами (Характеристика 3);

· Приложение предоставляет возможность написания конфигурационных скриптов (Характеристика 4);

· Приложение позволяет осуществлять переназначение последовательностей клавиатурных сочетаний (Характеристика 5);

· Приложение способно различать события, пришедшие от разных клавиатур (Характеристика 6);

· Приложение имеет графический интерфейс (Характеристика 7);

· Приложение позволяет вводить новые модификаторы клавиатурных сочетаний (Характеристика 8);

· Поддержка Xorg (Характеристика 9);

· Поддержка Wayland (Характеристика 10).

На таблице 1 приведена сравнительная характеристика приложений. Для удобства, каждой возможности поставлен в соответствие номер характеристика, и указаны номера характеристик в первой строке столбцов.

Таблица 1 Сравнительная характеристика аналогов

Название	Х. 1	Х.2	Х. 3	Х. 4	Х. 5	Х. 6	Х. 7	Х. 8	X. 9	X. 10
Razer Synapse	-	-	-	-	-	-	+	-	-	-
Corsair iCUE	-	-	-	-	-	-	+	-	-	-
Logitech SetPoint	-	-	-	-	-	-	-	-	-	-
Auto hot key	-	+	-	+	-	-	+	-	-	-
KeyTweak	-	+	-	-	-	-	+	-	-	-
SharpKeys	-	-	-	-	-	-	+	-	-	-
openrazer	+	+	-	-	-	-	+	-	+	-
solaar	+	+	-	-	-	-	+	-	+	-
ckb	+	+	-	-	-	-	+	-	+	-
ckb-next	+	+	-	-	-	-	+	-	+	-
xmodmap	+	+	-	-+	-	-	-	-	+	-
xkb	+	+	-	-+	-	-	-	-	+	-
keyboardlayouteditor	+	+	-	-	-	-	+	-	+	-
xkeysnail	+	+	-	+	+	-	-	-	+	-
autokey	+	+	-	+	-	-	+	-	+	-
Xbindkeys	+	+	-	-+	-	-	-	-	+	-
Xdotool	+	+	-	-+	-	-	-	-	+	-

Приложение со схожей функциональностью можно разделить на несколько категорий:

1. Проприетарные решения, поставляемые компаниями - производителями устройств;

2. Их свободные аналоги под Linux;

3. Приложения для автоматизации рабочего процесса;

4. Утилиты для переназначения клавиш под Linux.

Приложения первой категории предоставляют богатые возможности по конфигурации устройств, интуитивный и богатый пользовательский интерфейс. Однако, они не способны функционировать на ОС семейства Linux, поддерживают только устройства, выпущенные компаниями - производителями и предоставляют скудные возможности по автоматизации рабочего процесса.

Приложения второй категории способны функционировать на ОС семейства Linux, однако имеют менее интуитивный пользовательский интерфейс, также не предоставляют возможности по поддержке сторонних устройств, имеют скудные возможности по автоматизации рабочего процесса, не предоставляют возможности написания скриптов.

Приложения третьей категории предоставляют богатые скриптовые языки, позволяющие автоматизировать рутинные операции, однако, не все из них поддерживают ОС Linux, и, ни одно из них не поддерживает работу с устройствами напрямую.

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

Таким образом, на момент написания этих строк, аналогов разрабатываемому приложению выявлено не было.



1.3 Выбор методов решения задач

Для разработки приложения используется клиент-серверная архитектура, состоящая из сервера, консольного клиента, графического клиента. Сервер ответственен за:

· Считывание событий ввода;

· Переназначение последовательностей клавиатурных сочетаний;

· Сопоставление последовательностей клавиатурных сочетаний, введенных пользователем ранее определенной карте клавиатурных сочетаний;

· Выполнение действий, которые сопоставлены ранее определенной карте клавиатурных сочетаний;

· Установление соединения с клиентами;

· Чтение команд из установленного соединения;

· Выполнение команд, считанных из установленного соединения;

· Формирование результатов исполненных команд и их отправка клиентам;

· Запуск цикла событий.

Консольный клиент состоит из цикла REPL, из которого консольный клиент считывает команды для отправки серверу для их исполнения.

Графический клиент предоставляет графический интерфейс для более удобного переназначения клавиатурных сочетаний.

Один из возможных типов команд сервера - исполнение кода на специально разработанном скриптовом языке. За интерпретацию кода отвечает разработанный интерпретатор.

Интерпретация кода состоит из нескольких этапов:

1. Разбиение кода на лексемы и последующее построение иерархической структуры данных, представляющую ранее обработанный код;

2. Осуществление отображения иерархической структуры данных, полученной на предыдущем этапе, в внутренние значения интерпретатора;

3. Поэлементное вычисление значений, полученных на предыдущем этапе, согласно правилам вычисления, заложенным в интерпретатор.

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

Второй этап осуществляется с помощью последовательного рекурсивного прохода по иерархической структуре данных. На этом этапе осуществляется отображение этой структуры данных во внутренние значения интерпретатора.

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

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

Сервер запускает интерпретатор в цикле событий (Event loop). Цикл событий состоит из последовательной интерпретации кода на скриптовом языке, считывании последовательностей клавиатурных сочетаний, последующего исполнения действий, если введенная пользователем последовательность клавиатурных сочетаний содержится в карте последовательностей клавиатурных сочетаний и сборки мусора.

Помимо запуска цикла событий, сервер осуществляет установление соединения с клиентами. Протокол взаимодействия разработан с помощью технологии Google Protocol Buffers, сообщения которого передаются с помощью протокола WebSocket.

Поскольку, в приложении используется несколько потоков, для обеспечения корректности состояния, распределенных между ними, необходимо использовать средства синхронизации, такие как Mutex или Channel.

Для разработки интерпретатора, сервера и консольного клиента использовался язык программирования Rust. Для разработки графического клиента использовался язык программирования TypeScript, библиотеки Vue, Vuex и Vue-router.



Глава 2. Используемые методы, модели и инструменты

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

2.1 Теоретическая информация

2.1.1 Устройство жизненного цикла событий ввода в ОС Linux

В момент загрузки ОС, ядро Linux осуществляет построение файловой системы. Согласно философии Unix - «Все есть файл», взаимодействие с устройствами также осуществляется через файловые дескрипторы. Таким образом, во время построения файловой системы, ядро Linux считывает параметры устройств, создавая для каждого устройства набор файлов в файловой системе, через которые можно взаимодействовать с ними.

Подсистема ввода Linux состоит из набора драйверов, которые взаимодействуют с устройствами напрямую, и набора модулей, которые пересылают события ввода, которые делают события доступными для чтения ядром и приложениями.

В Linux существуют 4 таких модуля:

· Evdev;

· Keyboard;

· Mousedev;

· Joydev.

Модуль evdev осуществляет перенаправление событий ввода, сгенерированных ядром Linux, в процессе обработки событий, пришедших с устройств ввода. События ввода можно считывать через чтение файлов с именами “/dev/input/eventX”, где X является неотрицательным целым числом.

Модуль keyboard осуществляет считывание событий клавиатуры и перенаправление событий ввода в виртуальные терминалы.

Модуль mousedev существует для поддержки старых приложений, которые считывают события ввода мышей и других указывающих устройств. События ввода можно считывать с помощью файлов “/dev/input/mouseX”, где X является неотрицательным целым числом. Каждому указывающему устройству соответствует свой файл. Помимо этих файлов, события ввода указывающих устройств можно считывать через файл “/dev/input/mice”, который представляет все указывающие устройства. С его помощью, можно считывать события ввода всех указывающих устройств. Даже, если не зарегистрировано ни одного указывающего устройств, “/dev/input/mice” будет создан, и его все так же можно использовать для чтения событий, но в этом случае, событий ввода сгенерировано не будет.

Модуль joydev осуществляет чтения событий ввода джойстиков и их перенаправление для чтения ядром или приложениями. События ввода можно считывать через файлы “/dev/input/jsX”, где X является неотрицательным целым числом.

Помимо модулей обработки событий ввода, в Linux существует модуль uinput, с помощью которого, приложения могут создавать виртуальные устройства ввода, и эмулировать события ввода путем записи событий ввода в файл “/dev/input/uinput”.

Событие ввода представляется структурой из четырех полей:

· Точное время генерации события ввода;

· Тип события;

· Код события;

· Значение события.

Существует несколько типов событий:

· EV_SYN имеющее значение "0x00". Событие синхронизации. Используется для разделение других событий ввода;

· EV_KEY имеющее значение "0x01". Используется для представления изменений состояния клавиатур, клавиш, кнопок;

· EV_REL имеющее значение "0x02". Используется для представления значений изменения положения объекта на плоскости OXY;

· EV_ABS имеющее значение "0x03". Используется для представления значений положения объекта на плоскости OXY;

· EV_MSC имеющее значение "0x04". Используется для представления других типов входных данных;

· EV_SW имеющее значение "0x05". Используется для представления изменения состояния бинарных переключателей;

· EV_LED имеющее значение "0x11". Используется для включения/выключения подсветки;

· EV_SND имеющее значение "0x12". Используется для передачи звука устройствам;

· EV_REP имеющее значение "0x14". Используется для автоповторяющих устройств;

· EV_FF имеющее значение "0x15". Используется для передачи команд принудительной обратной связи;

· EV_PWR имеющее значение "0x16". Специальный тип событий, использующийся для работы с кнопками питания;

· EV_FF_STATUS имеющее значение " 0x17". Используется для чтения ответов на команды принудительной обратной связи.

События синхронизации могут иметь следующие коды:

· SYN_REPORT имеющее значение "0". Используется для синхронизации и группировки нескольких событий в набор событий, произошедших в единый момент времени;

· SYN_CONFIG имеющее значение "1";

· SYN_MT_REPORT имеющее значение "2". Используется для синхронизации и разделения событий ввода сенсорных экранов;

· SYN_DROPPED имеющее значение "3". Используется в качестве индикатора переполнения буфера в очереди сообщений. Все события, до события SYN_DROPPED должны игнорироваться, также должны игнорировать все события до следующего события SYN_REPORT. После этого, считыватель должен заново синхронизироваться с состоянием устройства.

Код событий EV_KEY представляет клавишу. Значение событий EV_KEY равно 1, когда клавиша зажата, и 0, когда клавиша отжата. Некоторые коды событий EV_KEY имеют специальное назначение:

· BTN_TOOL_FINGER, BTN_TOOL_DOUBLE_TAP, BTN_TOOL_TRIPLETAP, BTN_TOOL_QUADTAP, BTN_TOUCH - эти события используются для работы с сенсорными экранами.

Код событий EV_REL представляет собой ось, относительно которой произошло относительное изменение координаты. Значение событий EV_REL является значением того, насколько изменилась координата. Следующие коды событий EV_REL имеют специальное значение:

· REL_WHEEL, REL_HWHEEL - представляют собой события прокрутки вертикальных и горизонтальных колесиков мыши.

Код событий EV_ABS обозначают свойство, абсолютное значение которого передает событие. Значение событий EV_ABS обозначает абсолютное значение свойства. Следующие коды событий имеют специальное значение:

· ABS_DISTANCE, ABS_MT - используются для работы с сенсорными экранами

Код событий EV_SW представляет собой сущность, переключение которой представляет событие.

Код событий EV_MSC означает свойство, значений которого отражает событие. Следующие коды событий имеют специальное значение:

· MSC_TIMESTAMP - используются для представление количества микросекунд прошедшего с момента последнего сброса.

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

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

2. Генерируется событие EV_SYN, имеющее код SYN_REPORT.

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

4. Генерируется событие EV_SYN, имеющее код SYN_REPORT.

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

В случае, если пользователь зажал клавишу, и отжал ее по истечению некоторого промежутка времени, последовательность событий может иметь следующий вид:

1. Генерируется событие EV_KEY, содержащее в качестве кода идентификатор зажатой клавиши, содержащее значение 1.

2. Генерируется событие EV_SYN, имеющее код SYN_REPORT.

3. Генерируется событие EV_KEY, содержащее в качестве кода идентификатор зажатой клавиши, содержащее значение 1.

4. Генерируется событие EV_SYN, имеющее код SYN_REPORT.

5. Генерируется событие EV_KEY, содержащее в качестве кода идентификатор зажатой клавиши, содержащее значение 0.

6. Генерируется событие EV_SYN, имеющее код SYN_REPORT.

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

Для чтения событий ввода необходимо выполнить последовательность шагов:

1. Открыть для чтения файл “/dev/input/eventX”, где X - целое неотрицательное число;

2. Для захвата всех событий ввода устройства, необходимо осуществить вызов системного вызова ioctl с параметром EVIOCGRAB и истинным значением;

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

События, записываемые в виртуальное устройство ввода, созданное с помощью модуля uinput, имеют тот же формат, что и события, сгенерированные модулем evdev.

Для создания виртуального устройства, необходимо выполнить последовательность шагов:

1. Открыть файл “/dev/input/uinput” для записи в неблокирующем режиме;

2. Для генерации событий EV_KEY, с помощью системного вызова ioctl необходимо установить значение EV_KEY поля UI_SET_EVBIT в 1 для файлового дескриптора, полученного на шаге 1;

3. Для генерации событий EV_REL, с помощью системного вызова ioctl необходимо установить значение EV_REL поля UI_SET_EVBIT в 1 для файлового дескриптора, полученного на шаге 1;

4. Для генерации событий EV_KEY с кодом <KEY_X>, где <KEY_X> - код события ввода некоторой клавиши, с помощью системного вызова ioctl необходимо установить значение <KEY_X> структуры UI_SET_KEYBIT в 1;

5. Для генерации событий EV_REL с кодом <REL_X>, где <REL_X> - код события относительного изменения свойства, с помощью системного вызова ioctl необходимо установить значение <REL_X> поля UI_SET_RELBIT в 1;

6. Для генерации событий EV_ABS с кодом <ABS_X>, где <ABS_X> - код события абсолютного изменения свойства, с помощью системного вызова ioctl необходимо установить значение <ABS_X> поля UI_SET_ABSBIT в 1;

7. После этого, необходимо заполнить структуру uinput_user_dev, с необходимыми параметрами устройства;

8. Затем, записав структуру в файл “/dev/input/uinput”, нужно создать виртуальное устройства ввода с помощью системного вызова ioctl;

9. После этого, можно генерировать события ввода, с типами и кодами, которые были установлены на шагах 2-6 с помощью записи в файловый дескриптор, полученный на шаге 1.

Приложение осуществляет считывание событий ввода из файлов “/dev/input/eventX”. Также, приложение осуществляет конструирование виртуального устройства ввода, с помощью которого, оно эмулирует нажатия клавиш.

2.1.2 Механизм Mutex

Mutex является техникой, используемой в разработке многопоточных приложений. В случае, если несколько потоков имеют доступ к некоторому объекту, существует возможность гонки данных (Data race). Условия гонки данных следующие:

1. По крайней мере два потока имеют доступ к объекту;

2. По крайней мере один из этих потоков имеет возможность изменять состояние объекта;

3. Не используются средства синхронизации, которые устраняют возможность возникновения гонки данных.

Один из способов устранения гонки данных - использование механизма Mutex. Использование сводится к тому, что вокруг объекта создается обертка, которая предотвращает конкурентный доступ к объекту более чем одного потока.

Для разработки приложения использовался механизма Mutex, реализующий стратегию отравления (Mutex poisoning). Поток может иметь доступ к охраняемому объекту только в случае, если объект Mutex не отравлен. Когда поток запрашивает доступ у объекта Mutex, если Mutex не отравлен, то поток получает доступ, а объект Mutex отравляется. Когда поток более не нуждается в доступе к объекту, он сообщает объекту Mutex, что он более не нуждается в объекте, и объект Mutex перестает быть отравленным. Если поток запрашивает доступ у отравленного объекта Mutex, то выполнение потока приостанавливается до тех пор, пока объект Mutex не перестает быть отравленным.

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

2.1.3 Механизм Channel

Механизм Channel является паттерном в разработке многопоточных приложений. Channel используется для синхронизации выполнения двух потоков. Channel является FIFO очередью, состоящей из одного или более отправителей сообщений и ровно одного получателя сообщений.

В случае двух потоков, один из них получает в пользование отправитель сообщений (Sender), другой получает в пользование приемник сообщений (Receiver). Первый поток в процессе своей работы отправляет сообщения, второй в процессе своей работы ожидает сообщения, отправленные первым потоком.

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

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

2.1.4 Конечный автомат

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

· Конечное непустое множество символов - алфавит;

· Конечное непустое множество состояний;

· Начальное состояние, являющееся элементам множества состояний;

· Отображение множества пар (состояние, символ) в множество состояний;

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

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

· Имеет в качестве алфавита множество всех возможных клавиатурных сочетаний;

· Имеет множество состояний, состоящее из:

o Начальное состояние;

o Промежуточные состояния;

o Состояния действий.

· Начальное состояние является начальным состоянием из множества состояний;

· Функция отображения осуществляет отображение следующего введенного пользователем клавиатурного сочетания и текущего состояния автомата в состояние автомата следующим образом:

1. Если последовательность перехода состояния автомата удовлетворяют части заданной пользователем последовательности клавиатурных сочетаний, и следующее введенное клавиатурное сочетание удовлетворяет остатку какого-либо введенного пользователем клавиатурного сочетания, то осуществляется переход в это состояние;

1. Если это не так, то осуществляется переход в начальное состояние;

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

· Пустое множество финальных состояний.

2.1.5 Комбинаторный парсинг

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

Примеры примитивных парсеров:

· Парсер символа “3”, возвращает успех, если первый символ переданной парсеру последовательности является “3”, иначе возвращается ошибка;

· Парсер последовательности символов “head”, возвращает успех, если переданная последовательность начинается на “head”, иначе возвращается ошибка.

Комбинатор парсеров является функцией, возвращающей парсеры. Комбинаторы могут принимать аргументы, которые могут являться парсерами. Примеры комбинаторов парсеров:

· Комбинатор tag, принимающий последовательность символов, возвращающий парсер, который возвращает успех, если переданная этому парсеру последовательность символов начинается на последовательность символов, переданную комбинатору. Иначе, возвращается ошибка;

· Комбинатор map, принимающий парсер, который в случае успеха возвращает значение типа A и функцию, которая отображает значения типа A в значение типа B. Для этих двух аргументов, комбинатор map возвращает парсер, который возвращает в случае успешного разбора переданным парсером, отображенное значение результата успешного разбора типа B;

· Комбинатор many1, принимающий парсер, который в случае успеха возвращает значение типа A. Комбинатор many1, возвращает парсер, который применяет переданный комбинатору парсер до тех пор, пока этот парсер не вернет ошибку. Результаты применения переданного парсера собираются в массив результатов и возвращаются сконструированным парсером. В случае, если переданный парсер вернул ошибку при первом его применении, сконструированный парсер возвращает ошибку;

· Комбинатор alt, который принимает набор парсеров. Комбинатор, возвращает парсер, который последовательно применяет переданные комбинатору парсеры до тех пор, пока один из парсеров не вернет успех. Если один из парсеров вернул успех, то сконструированный парсер возвращает этот результат. В случае, если ни один из переданных парсеров не вернул успех, сконструированный парсер возвращает ошибку.

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



2.1.6 Лексическая область видимости

Разработанный интерпретатор реализует лексическую область видимости. Переменные интерпретатора хранятся в специальных структурах, называемые лексическими окружениями. Лексическое окружение хранит набор пар (символ, значение). Лексические окружения имеют иерархию - каждое лексическое окружения, кроме глобального, имеет родителя. Когда вычисляется значение переменной, оно возвращается из ближайшего лексического окружения. Если в ближайшем лексическом окружении переменной не оказалось, осуществляется поиск переменной по цепочке родителей, вплоть до глобального лексического окружения.

Существует другой подход, называемый динамической областью видимости. Наиболее явно различие между динамической и лексической зоной видимости проявляется при использовании функций. Если есть функция, вычисляющая значение свободной переменной, в языках, реализующих лексическую область видимости, значение вычисляется в том окружении, в котором была создана функция. В языках, реализующих динамическую зону видимости, значение свободной переменной вычисляется в том окружении, в котором функция была вызвана.

2.1.7 Сборка мусора

Разработанный интерпретатор реализует стратегию автоматического управления памятью, которая называется сборкой мусора. В реализации механизма сборки мусора, используется понятие достижимости. Для заданного лексического окружения, объект достижим, если есть возможность получить на него ссылку из заданного лексического окружения. Во время сборки мусора, недостижимые объекты помечаются сборщиком, затем, после прохода по объектам, память для недостижимых объектов освобождается.



2.1.8 Прототипное наследование

Форма организации объектно-ориентированного программирования, в которой переиспользование функциональности осуществляется путем использования уже существующих объектов - прототипов. Каждый объект может иметь ссылку на прототип, из которого объект может производить переиспользование частей его функциональности

Если при попытке получить значение объекта или вызвать его метод, запрашиваемое значение или метод не найден в самом объекте, то осуществляется запрос значения или метода у его прототипа. Если же поиск не увенчался успехом и у прототипа объекта, осуществляется запрос у его прототипа и т.д. Последовательность таких ссылок объекта на прототипы называется цепочкой прототипов (Prototype chain).

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

2.1.9 Паттерн Arena

Паттерн Arena, специфичный для языков программирования, использующих RAII (Resource acquisition is initialization), служит для решения проблемы циклических зависимостей. Компилятор языка Rust запрещает наличие в коде прямых циклических зависимостей. Использование паттерна Arena позволяет обойти это ограничение.

Идея паттерна, следующая - вместо работы с множеством объектов, имеющих ссылки друг на друга, производится работа лишь с одним объектом - хранящим коллекцию объектов. Все ссылки объектов заменяются целочисленным значением - идентификаторами объекта внутри коллекции. Все методы, которые так или иначе используют ссылки объектов друг на друга, реализуются не для самих объектов, а для объекта Arena. В этих методах, вместо ссылок на объекты, передаются идентификаторы объектов внутри коллекции.

2.2 Использованные инструменты

В данном разделе описываются инструменты, использованные во время разработки.

2.2.1 Язык программирования Rust

Rust - мультипарадигменный язык программирования, фокусирующийся на скорости работы и разработки безопасного кода. Rust предоставляет гарантии отсутствия гонок данных через механизм RAII (Resource Acquisition Is Initialization), гарантирующий, что код, способный привести к гонкам данных, не будет допущен до компиляции анализатором кода. Без использования unsafe-кода и заведомо небезопасных компонентов стандартной библиотеки.

В Rust имеются следующие основные типы данных:

· Логические значения: true или false;

· Целые значения:

o i8, i16, i32, i64 - 8, 16, 32, 64 - битные целые значения со знаком соответственно;

o u8, u16, u32, u64 - 8, 16, 32, 64 - битные целые значения без знака соответственно;

· Значения с плавающей точкой: f32, f64;

· Строки - являются валидными последовательностями UTF-8 символов;

В Rust имеются возможности комбинации существующих типов данных в новые путем объявления структур.

В Rust существуют три типа структур: обычные структуры, именованные кортежи и unit-структуры. На листинге 1 приведены примеры объявления структур.

// unit-структура

struct Nil;

// Именованный кортеж

struct Pair(i32, i32);

// Структура с двумя полями

struct Point {

x: f32,

y: f32,

}

Листинг 1: Примеры объявления структур в Rust

В Rust помимо структур, имеются перечисления. Перечисления состоят из последовательностей деклараций альтернатив - значение типа перечисления в любой момент времени, может быть только одной из альтернатив. Альтернативы могут быть как юнит-структурами, так и именованными кортежами. На листинге 2 приведен пример объявления перечисления.

enum ExecutionResult {

TwoSolutions(i32, i32),

OneSolution(i32),

NoSolutions

}



Листинг 2: Пример объявления перечисления в Rust

Также, язык предоставляет стандартную библиотеку, имеющую реализации механизмов Channel и Mutex.

2.2.2 Язык программирования TypeScript

Язык программирования TypeScript является типизированным надмножеством языка программирования JavaScript. В отличие от JavaScript, в TypeScript для каждой переменной возможно указывать его тип, что позволяет на этапе компиляции в JavaScript отлавливать некоторые ошибки, связанные с некорректным использованием типов данных.

Помимо этого, язык предоставляет следующие возможности:

· Возможность объявления интерфейсов - описаний структуры объектов, в которых описываются какие свойства должны быть в объекте, чтобы объект удовлетворял интерфейсу и какие типы должны иметь свойства объекта;

· Возможность написания обобщенного кода с использованием дженериков;

· Возможность определения перечислений;

· Возможность использования типов-сумм (Sum Type), и т.д.