Общий алгоритм генерации конечного автомата для yield - История изменений

Mikst: /* Новый способ генерации конечного автомата */

2016-07-07T12:01:22Z

Новый способ генерации конечного автомата

← Предыдущая версия		Версия от 15:01, 7 июля 2016
Строка 154:		Строка 154:
	end		end
	</source>		</source>

			При этом способе решается проблема автовывода типов: все помеченные как auto_type переменные получают свои значения в операторе присваивания по тексту раньше чем используются в правой части

	=== Код генерации конечного автомата ===		=== Код генерации конечного автомата ===

Mikst: /* Новый способ генерации конечного автомата */

2016-07-07T11:59:31Z

Новый способ генерации конечного автомата

@@ Строка 153: / Строка 153: @@
    lb#1:
 end
 </source>

Mikst: /* Старый способ генерации конечного автомата */

2016-07-07T11:58:39Z

Старый способ генерации конечного автомата

@@ Строка 122: / Строка 122: @@
      Result := False
      exit;
 end
 </source>

Mikst: /* Пример */

2016-07-07T11:55:42Z

Пример

← Предыдущая версия		Версия от 14:55, 7 июля 2016
Строка 50:		Строка 50:
	end		end
	</source>		</source>

			==== Старый способ генерации конечного автомата ====
	В результате генерации конечного автомата получаем старым методом с case получаем следующий код:		В результате генерации конечного автомата получаем старым методом с case получаем следующий код:
	<source lang="Delphi">		<source lang="Delphi">

Mikst: /* Пример */

2016-07-06T08:24:14Z

Пример

← Предыдущая версия		Версия от 11:24, 6 июля 2016
Строка 91:		Строка 91:
	</source>		</source>

	Здесь хорошо видно, что количество состояний на один больше количества yield		Здесь хорошо видно, что количество состояний на один больше количества 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>

Mikst: /* Общий алгоритм */

2016-07-06T08:14:31Z

Общий алгоритм

← Предыдущая версия		Версия от 11:14, 6 июля 2016
Строка 23:		Строка 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

Mikst: /* Общий алгоритм */

2016-07-06T08:07:53Z

Общий алгоритм

← Предыдущая версия		Версия от 11:07, 6 июля 2016
Строка 12:		Строка 12:
	===Общий алгоритм===		===Общий алгоритм===
	1. Количество yield равно количеству состояний плюс нулевое состояние		1. Количество yield равно количеству состояний плюс нулевое состояние

	2. Сформировать в начале секцию переходов с помощью if		2. Сформировать в начале секцию переходов с помощью if

	3. После секции переходов помечать меткой текущего состояния и от текущего места до yield переносить код. Код yield expr заменить на		3. После секции переходов помечать меткой текущего состояния и от текущего места до yield переносить код. Код yield expr заменить на
	<source lang="Delphi">		<source lang="Delphi">

Mikst в 08:07, 6 июля 2016

2016-07-06T08:07:29Z

← Предыдущая версия		Версия от 11:07, 6 июля 2016
Строка 9:		Строка 9:

	Кроме того, тесты показали, что код с вложенными if в PascalABC.NET работает быстрее кода с case.		Кроме того, тесты показали, что код с вложенными if в PascalABC.NET работает быстрее кода с case.

			===Общий алгоритм===
			1. Количество yield равно количеству состояний плюс нулевое состояние
			2. Сформировать в начале секцию переходов с помощью if
			3. После секции переходов помечать меткой текущего состояния и от текущего места до yield переносить код. Код yield expr заменить на
			<source lang="Delphi">
			current := <yielded-value>
			state := <next-state>
			Result := true
			exit
			</source>
			4. В заключительном состоянии в конце Result := False. Или сделать это в начале алгоритма

Mikst: Новая страница: «Конечный автомат генерируется по коду тела функции, содержащей yield, после Lowering. Вначале …»

2016-07-06T07:02:04Z

Новая страница: «Конечный автомат генерируется по коду тела функции, содержащей yield, после Lowering. Вначале …»

Новая страница

Конечный автомат генерируется по коду тела функции, содержащей yield, после Lowering.

Вначале был реализован алгоритм как в C# - с помощью case (switch) по состояниям.
Этот алгоритм включал в себя некоторую сложность: при наличии меток после lowering часть кода после метки приходилось выносить за case и организовывалась сложная логика переходов.

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

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

Кроме того, тесты показали, что код с вложенными if в PascalABC.NET работает быстрее кода с case.