Общий алгоритм генерации конечного автомата для 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));
        }
    }