Общий алгоритм генерации конечного автомата для yield: различия между версиями
Mikst (обсуждение | вклад) Нет описания правки |
Mikst (обсуждение | вклад) |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 12: | Строка 12: | ||
===Общий алгоритм=== | ===Общий алгоритм=== | ||
1. Количество yield равно количеству состояний плюс нулевое состояние | 1. Количество yield равно количеству состояний плюс нулевое состояние | ||
2. Сформировать в начале секцию переходов с помощью if | 2. Сформировать в начале секцию переходов с помощью if | ||
3. После секции переходов помечать меткой текущего состояния и от текущего места до yield переносить код. Код yield expr заменить на | 3. После секции переходов помечать меткой текущего состояния и от текущего места до yield переносить код. Код yield expr заменить на | ||
<source lang="Delphi"> | <source lang="Delphi"> | ||
Строка 21: | Строка 23: | ||
</source> | </source> | ||
4. В заключительном состоянии в конце Result := False. Или сделать это в начале алгоритма | 4. В заключительном состоянии в конце Result := False. Или сделать это в начале алгоритма | ||
===Пример=== | |||
Функция | |||
<source lang="Delphi"> | |||
function f<T>(a: array of T): sequence of T; | |||
begin | |||
foreach var x in a do | |||
yield x; | |||
end; | |||
</source> | |||
после Loweringа заменяется на следующую: | |||
<source lang="Delphi"> | |||
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 | |||
</source> | |||
==== Старый способ генерации конечного автомата ==== | |||
В результате генерации конечного автомата получаем старым методом с case получаем следующий код: | |||
<source lang="Delphi"> | |||
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 | |||
</source> | |||
Здесь хорошо видно, что количество состояний на один больше количества yield. | |||
Новым методом получается следующий код: | |||
<source lang="Delphi"> | |||
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 | |||
</source> | |||
==== Новый способ генерации конечного автомата ==== | |||
При новом способе код получается проще и чище. Мы приводим только код MoveNext() | |||
<source lang="Delphi"> | |||
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 | |||
</source> | |||
При этом способе решается проблема автовывода типов: все помеченные как auto_type переменные получают свои значения в операторе присваивания по тексту раньше чем используются в правой части | |||
=== Код генерации конечного автомата === | |||
<source lang="CSharp"> | |||
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)); | |||
} | |||
} | |||
</source> |
Текущая версия от 15:01, 7 июля 2016
Конечный автомат генерируется по коду тела функции, содержащей 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));
}
}