Автоматическое выравнивание кода

Доброго времени суток.

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

• Подсветка синтаксиса
• Использование отступов
• Вертикальное выравнивание

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

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

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

В связи с этим я решил искать собственный метод для решения задачи.

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

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

// from 
f(a, b + c)
g(b + c, a)
	
// to
f(a, b + c   )
g(   b + c, a)

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

Очевидно, что простым увеличением веса для пары (запятая, запятая) проблему не решить, так как сами параметры функции могут быть сколь угодно большими и, следовательно, иметь сколь угодно большой вес.

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

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

Более того, в тексте программ могут встречаться места, выравнивать которые ни в коем случае нельзя. К ним можно отнести строковые константы и комментарии. Разные языки по разному распознают комментарии, так например СС++ использует \, а Ruby и Python #. Поэтому единственным способом повышения универсальности является использование метода быстрого описания синтаксиса языка.

Грамматика

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

Структура, полученная из предыдущего примера:

	f
	(
			a
		,
			b
			+
			c
	)
	
	g
	(
			b
			+
			c
		,
			a
	)

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

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

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

Грамматика, применяемая для построения показанной выше структуры, может быть описана в форме Бэкуса-Наура следующим образом:

	main ::= expr
	
	expr ::= expr p 
	         | p 
	         | expr ',' expr
	
	p    ::= '(' expr ')' 
	         |'(' ')' 
	         | any_token_except(',', ')', '(') 

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

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

	expr ::= expr ',' expr
	p    ::= '(' expr ')'

В ходе разработки была реализован LR-0 парсер, использующий описание грамматики для построения дерева выражения. Описание алгоритма построения парсера выходит за рамки данной статьи, более подробно с ним можно ознакомиться в книге: Ахо, Лам, Сети, Ульман — Компиляторы. Принципы, технологии, инструменты.

Сравнение

После получения дерева выражения необходимо производить выравнивание токенов с учетом их похожести. Похожая задача возникает в генетике при изучении генома. Выравнивание последовательностей — метод, основанный на размещении двух или более последовательностей мономеров ДНК, РНК или белков друг под другом таким образом, чтобы легко увидеть сходные участки в этих последовательностях[wiki].

Один из способов для решения этой задачи в биоинформатике — применение динамического программирования, его я и взял за основу для задачи выравнивания токенов.

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

def match(x,y,i,j)
		if(@cache[[i,j]] != nil) then
			return @cache[[i,j]][0];
		end

		if x.size == i then
			@cache[[i,j]] = [0, 3];
			return 0;
		end
		if y.size == j then
			@cache[[i,j]] = [0, 3];
			return 0;
		end

		value = [];
		value[0] = x[i].cmp(y[j]) + match(x,y,i+1,j+1)
		value[1] = match(x, y, i  ,j+1)
		value[2] = match(x, y, i+1,j  )

		max_value = 0;
		max_index = 0;
		index = 0;
		value.each{
			|x|
			if x > max_value then
				max_value = x;
				max_index = index; 
			end
			index += 1;
		}
		@cache[[i,j]] = [max_value, max_index];
		return max_value;
	end

	def get_pairs(x,y, start = 0)
		@cache = {};
		match(x, y, start, start);
		pairs = [];
		i = j = start;
		curr  = @cache[[i,j]][1]
		while curr != 3
			case curr
			when 0 then
				pairs += [[i,j]] if x[i].cmp(y[j]) > Float::EPSILON
				i+=1;
				j+=1;
			when 1 then
				j+=1;	
			when 2 then
				i+=1;	
			end
			curr = @cache[[i,j]][1]
		end
		return [@cache[[start, start]][0], pairs];
	end

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

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

Выделение токенов

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

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

В частности, схожесть идентификаторов определяется как отношение расстояния Левенштейна между идентификаторами к длине максимального из них.

Значения по-умолчанию в этом случае следующие:

	Правило                 Схожесть
	
	Совпадают значения      1
	Совпадают типы          max(Levenshtein_dist / max_length, 0.1)
	Ничего не совпадает     0

Определение минимального отступа между токенами

Хорошим стилем программирования считается простановка отступов в некоторых конструкциях языка.
К таким случаям можно отнести простановку пробелов после запятой в аргументах функции, пробелы вокруг операторов сравнения и т.п…

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

	f (a, b)
	
	//VS
	
	f(a, b)

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

Текущая реализация

На момент написания статьи программа реализована как плагин к редактору Sublime Text 3. Среди особенностей следует отметить следующие:

• Выравнивание выделенных строк с помощью «горячих» клавиш;
• Защита от выравнивания строк с разными отступом. (Предполагается, что перед выравниванием строк отступы проставлены корректно.);
• Поддержка разных вариантов грамматики, выделения токенов и иерархии типов в зависимости от используемого языка;
• На момент написания статьи реализована пока только специализация для языка Cи 99-го стандарта и java.
• Исходный код написан на Ruby, открыт и доступен на GitHub

Среди планов на будущее хотелось бы отметить следующее:

• Расширение списка специализированных грамматик;
• Определение максимального числа пробелов при выравнивании на основе машинного обучения.
• Возможность добавления строк в обучающее множество с помощью «горячих» клавиш.

Примеры полученных результатов

	switch (state)                                
	{                                            
	    case State.QLD: city = "Brisbane"; break; 
	    case State.WA: city = "Perth"; break;     
	    case State.NSW: city = "Sydney"; break;   
	    default: city = "???"; break;             
	}   
	
	// To
	switch (state)                                
	{
	    case State.QLD:city = "Brisbane"; break;
	    case State.WA :city = "Perth"   ; break;
	    case State.NSW:city = "Sydney"  ; break;
	    default       :city = "???"     ; break;
	}    

	// From
	types[:space] = nil;
	types[:quote] = nil;
	types[:regexp] = nil;
	types[:id] = nil;
	types[:spchar] = nil;
	
	// To
	
	types[:space ] = nil;
	types[:quote ] = nil;
	types[:regexp] = nil;
	types[:id    ] = nil;
	types[:spchar] = nil;

	// From
	long int a = 2;
	long long double b = 1;
	const int doubl = 4; 
	
	// To
	long  int         a     = 2;
	long  long double b     = 1;
	const int         doubl = 4;

Спасибо за внимание.

Автор: generall

Источник