Общий алгоритм генерации конечного автомата для yield
Конечный автомат генерируется по коду тела функции, содержащей yield, после Lowering.
Вначале был реализован алгоритм как в C# - с помощью case (switch) по состояниям. Этот алгоритм включал в себя некоторую сложность: при наличии меток после lowering часть кода после метки приходилось выносить за case и организовывалась сложная логика переходов.
Последней каплей стал автовывод типов с узлами auto_type - присваивания для автовывода должны быть записаны в естественном порядке.
Поэтому было решено заменить case на блок вложенных if в начале с переходами по меткам. Этот способ по генерации кода оказывается проще и равномернее: если внутри кода встречается своя метка, то это никак не надло специально обрабатывать.
Кроме того, тесты показали, что код с вложенными if в PascalABC.NET работает быстрее кода с case.
Общий алгоритм
1. Количество yield равно количеству состояний плюс нулевое состояние
2. Сформировать в начале секцию переходов с помощью if
3. После секции переходов помечать меткой текущего состояния и от текущего места до yield переносить код. Код yield expr заменить на
current := <yielded-value>
state := <next-state>
Result := true
exit
4. В заключительном состоянии в конце Result := False. Или сделать это в начале алгоритма
Пример
Функция
function f<T>(a: array of T): sequence of T;
begin
foreach var x in a do
yield x;
end;
после Loweringа заменяется на следующую:
function <yield_helper_locals_type_detector>f<T>(a: array of T): sequence of T;
label lb#1,lb#2;
begin
var $coll$1: IEnumerable<yield_unknown_foreach_type>;
$coll$1 := a
var $enumerator$1 := $coll$1.GetEnumerator();
lb#2:
if not $enumerator$1.MoveNext() then
goto lb#1
var $x1 := $enumerator$1.Current;
yield $x1
goto lb#2
lb#1:
end
Старый способ генерации конечного автомата
В результате генерации конечного автомата получаем старым методом с case получаем следующий код:
type
clyield#1 = class(IEnumerable<T>,IEnumerator<T>)
public_modifer
<$coll$1>MethodLocalVariable__1: IEnumerable<yield_unknown_foreach_type>;
<$enumerator$1>MethodLocalVariable__2: yield_unknown_expression_type;
<$x1>MethodLocalVariable__3: yield_unknown_expression_type;
<>MethodFormalParam__a: array of T;
<>1__state: integer;
<>2__current: T;
...
function MoveNext(): boolean;
label lb#1,lb#2;
begin
case <>1__state of
0:
begin
<$coll$1>MethodLocalVariable__1 := <>MethodFormalParam__a
<$enumerator$1>MethodLocalVariable__2 := <$coll$1>MethodLocalVariable__1.GetEnumerator()
goto lb#2
end
1:
begin
goto lb#2
goto lb#1
exit
end
end;
lb#2:
if not <$enumerator$1>MethodLocalVariable__2.MoveNext() then
goto lb#1
<$x1>MethodLocalVariable__3 := <$enumerator$1>MethodLocalVariable__2.Current
<>2__current := <$x1>MethodLocalVariable__3
<>1__state := 1
Result := True
exit
lb#1:
end
Здесь хорошо видно, что количество состояний на один больше количества yield.
Новым методом получается следующий код:
function MoveNext(): boolean;
label lb#1,lb#2,lbstate#0,lbstate#1;
begin
Result := False;
if <>1__state = 0 then
goto lbstate#0;
if <>1__state = 1 then
goto lbstate#1;
lbstate#0:
<$coll$1>MethodLocalVariable__1 := <>MethodFormalParam__a
<$enumerator$1>MethodLocalVariable__2 := <$coll$1>MethodLocalVariable__1.GetEnumerator()
lb#2:
if not <$enumerator$1>MethodLocalVariable__2.MoveNext() then
goto lb#1
<$x1>MethodLocalVariable__3 := <$enumerator$1>MethodLocalVariable__2.Current
<>2__current := <$x1>MethodLocalVariable__3
<>1__state := 1
Result := True
exit
lbstate#1:
goto lb#2;
lb#1:
Result := False
exit;
end
Новый способ генерации конечного автомата
При новом способе код получается проще и чище. Мы приводим только код MoveNext()
function MoveNext(): boolean;
label lb#1,lb#2;
label lbstate#0,lbstate#1;
begin
Result := False
if <>1__state = 0 then
goto lbstate#0
else
goto lbstate#1
lbstate#0:
<$coll$1>MethodLocalVariable__1 := <>MethodFormalParam__a
<$enumerator$1>MethodLocalVariable__2 := <$coll$1>MethodLocalVariable__1.GetEnumerator()
lb#2:
if not <$enumerator$1>MethodLocalVariable__2.MoveNext() then
goto lb#1
<$x1>MethodLocalVariable__3 := <$enumerator$1>MethodLocalVariable__2.Current
<>2__current := <$x1>MethodLocalVariable__3
<>1__state := 1
Result := True
exit
lbstate#1:
goto lb#2
lb#1:
end
При этом способе решается проблема автовывода типов: все помеченные как auto_type переменные получают свои значения в операторе присваивания по тексту раньше чем используются в правой части
Код генерации конечного автомата
class ConstructFiniteAutomata
{
public statement_list res = new statement_list(); // сюда писать результат
statement_list stl; // это исходные операторы тела функции
declarations defs; // это декларации функции - для добавления меток
int curState = 0;
public ConstructFiniteAutomata(block bl)
{
this.stl = bl.program_code;
defs = bl.defs;
}
public void Process(statement st)
{
if (st is yield_node)
{
var yn = st as yield_node;
curState += 1;
res.AddMany(
new assign(YieldConsts.Current, yn.ex),
new assign(YieldConsts.State, curState),
new assign("Result", true),
new procedure_call("exit"),
new labeled_statement(YieldConsts.LabelStatePrefix+curState.ToString())
);
}
else if (st is labeled_statement)
{
var ls = st as labeled_statement;
res.Add(new labeled_statement(ls.label_name));
Process(ls.to_statement);
}
else
{
res.Add(st);
}
}
public void Transform()
{
res.Add(new labeled_statement(YieldConsts.LabelStatePrefix+curState.ToString()));
foreach (var st in stl.subnodes)
Process(st);
// добавим метки состояний
var idseq = Enumerable.Range(0, curState + 1).Select(i => new ident("lbstate#" + i.ToString()));
var idl = new ident_list(idseq.ToList());
defs.Add(new label_definitions(idl));
statement ifgoto = new goto_statement(YieldConsts.LabelStatePrefix + curState.ToString());
for (var i = curState - 1; i >= 0; i--)
ifgoto = new if_node(new bin_expr(new ident(YieldConsts.State), new int32_const(i), Operators.Equal),
new goto_statement(YieldConsts.LabelStatePrefix + i.ToString()),
ifgoto
);
res.AddFirst(ifgoto);
res.AddFirst(new assign("Result", false));
}
}