Предупреждение о связанных переменных в образцах

[Mazdaywik]

Проблема

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

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

Решение

Ну, очевидно нужно отлавливать такие случаи и выдавать на них предупреждение. Причём указывать можно непосредственно на переменную — переменные в дереве у Checker.ref’а имеют координаты.

Засада

Засада в том, что повторная переменная может быть намеренной частью алгоритма. Например:

refal-5-lambda/src/compiler/OptTree.ref

Lines 51 to 68 in 1058511

	DoOptTree {
	0 t.OptDrive s.OptSpec s.OptAutoMarkup e.AST = 0 e.AST;
	s.Cycles t.OptDrive s.OptSpec s.OptAutoMarkup e.AST
	= <Log-AST ('Pass ' <Symb s.Cycles> ' (before Auto markup)') e.AST> : e.AST^
	= e.AST : e.OriginAST
	= <OptTree-AutoMarkup s.OptAutoMarkup e.AST> : e.AST^
	= <Dec s.Cycles> : s.Cycles^
	= <DriveSpecLoop s.Cycles t.OptDrive s.OptSpec e.AST> : s.Cycles^ e.AST^
	= e.AST
	: {
	e.OriginAST = s.Cycles e.OriginAST;
	e.AST^ = <DoOptTree s.Cycles t.OptDrive s.OptSpec s.OptAutoMarkup e.AST>;
	}
	}

refal-5-lambda/src/compiler/OptTree.ref

Lines 82 to 94 in 1058511

	DoDriveSpecLoop {
	0 t.OptDrive s.OptSpec e.AST = 0 e.AST;
	s.Cycles t.OptDrive s.OptSpec e.AST
	= e.AST : e.OriginAST
	= <DriveLoop s.Cycles t.OptDrive e.AST> : s.Cycles^ e.AST^
	= <SpecPass s.Cycles s.OptSpec e.AST> : s.Cycles^ e.AST^
	= e.AST
	: {
	e.OriginAST = s.Cycles e.OriginAST;
	e.AST^ = <DoDriveSpecLoop s.Cycles t.OptDrive s.OptSpec e.AST>;
	}
	}

refal-5-lambda/src/compiler/OptTree.ref

Lines 105 to 119 in 1058511

	DoDriveLoop {
	0 t.OptDrive e.AST = 0 e.AST;
	s.Cycles t.OptDrive e.AST
	= <Log-AST ('Pass ' <Symb s.Cycles> ' (before Drive)') e.AST> : e.AST^
	= e.AST : e.OriginAST
	= <ExpandClosures e.AST> : e.AST^
	= <OptTree-Drive t.OptDrive e.AST> : e.AST^
	= <Dec s.Cycles> : s.Cycles^
	= e.AST
	: {
	e.OriginAST = s.Cycles e.OriginAST;
	e.AST^ = <DoDriveLoop s.Cycles t.OptDrive e.AST>;
	};
	}

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

Повторная переменная может быть ключом при ассоциативном поиске (по открытой переменной), а значит, тоже является частью алгоритма.

Наиболее консервативной (но и наиболее слабой) эвристикой можно рассматривать повторные переменные в присваиваниях с жёсткими образцами. Но этого мало. Нужны более тонкие эвристики для блоков и вложенных функций.

[Mazdaywik]

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

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

[Mazdaywik]

Полный список коммитов в хронологическом порядке:

1. 42b5512 (см. выше),
2. a21d2d9 (см. выше),
3. dc1765a (но тут исходный файл портировался с классического Рефала-5),
4. ca96a72 (ошибка вызывала проблемы производительности),
5. 689a7f9,
6. 2fa8dd6 (функция IsIdentTail в самом конце диффа),
7. 9fac618,
8. 5032ffc,
9. 857a2d7 (файл Desugaring.sref),
10. 6b4a0cc,
11. d63583c (файл src/lexgen/Parser.sref, функция ParseSetDescr).

Поиск осуществлялся в логе, полученном командой:

git log -p --word-diff-regex=[^[:space:]]

Искалась строчка {+^+}, коммиты с найденной строчкой (и не являющиеся случайными ложными вхождениями) перечислены выше.

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

[Mazdaywik]

Подготовка «белого списка»

Есть 11 примеров ошибок, которые сразу не выявились и закоммитились. Разумеется, таких ошибок на самом деле было больше, только они выявлялись сразу и исправлялись.

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

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

На первом этапе исследований нужно будет детектировать все связанные переменные в образцах присваиваний, блоков и вложенных функций, чтобы понять, чем наполнить «белый список».

Подавление предупреждений

Допустим, компилятор выявил связанную переменную в образце, показал на неё программисту. Программист смотрит и говорит: «Спасибо компилятор, я именно это и имел ввиду», т.к. там действительно должна быть повторная переменная (как в случае с синтаксическими деревьями в заглавном посте).

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

Предлагается такой способ — комментарий /* same */, который ставится в той же строчке. Комментарий распознаётся лексическим анализатором, он выдаёт токен-подавитель (TkSuppressor), который помещается в список ошибок. Список ошибок при печати удаляет предупреждение -Wrepeat-variable (так мы его назовём) в тех же номерах строк, что и комментарий-подавитель.

В принципе, можно предусмотреть общую форму подавителей вида /* SUPPRESS: -Wwarning-name */, подавляющую любое предупреждение в данной строке. Но для данного случая удобнее использовать специальный комментарий /* same */ (без учёта регистра и пробельных символов).

Подавление предупреждений вынесено в отдельную задачу #345.

[Mazdaywik]

Неплохая задача для курсовой работы по компиляторам или ВКР.

[Mazdaywik]

А, впрочем, можно предложить её и на летнюю практику.

[Mazdaywik]

Только что написал:

RemoveReferenceTagFromChildren {
  (Func (e.Name) Children (e.Children))
    = <Map
        {
          (INDIRECT) = /* пропускаем */;
          (s._ e.Name) = (e.Name);
        }
        e.Children
      >
    : e.Children^
    = (Func (e.Name) Children (e.Children));
}

И радостно получил ошибку! Потому что переменная e.Name внутри вложенной функции совпадает с e.Name снаружи.

[Mazdaywik]

Ещё была проблема:

    = <Map &MakeGraphNode e.AST> : e.Graph
    = <Map &RemoveReferenceTagFromChildren e.Graph> : e.Graph^

    = <MapAccum &UnsuffixedFunctions () e.Graph> : (e.Roots) e.Graph

В последнем присваивании должно быть e.Graph^. Но это не ошибка, т.к. функция UnsuffixedFuncions граф не меняла — MapAccum использовался как раз для избежания копирования. А вместо этого происходило и копирование, и сравнение на равенство.