この記事は、42 Tokyo Advent Calendar 2022 の17日目の記事です

16日目の記事: stack1つでチューリング完全なやや難解言語 yasl (by @snara-42 さん)
18日目の記事: ＜AA木じゃねぇ　木のAAさ＞ (by @corvvs さん)

こんにちは。42Tokyo 2022年4月入学の@t0rです
入試(Piscine)を受けたのが2021年12月だったので、もう1年経ってるんですよね。時が経つのは早い…

0. 42Tokyo #とは

42 Tokyo（フォーティーツー）は、フランス発のエンジニア養成機関です。
フランス・パリをはじめ、世界各国に教育を展開しています。
完全無料で、革新的なカリキュラムを学習可能。
プログラミングを学びたい世界中の学生たちが、
今この瞬間も42でスキルを磨いています。
(引用元: https://42tokyo.jp/)

ということで、無料で「プログラミングを学ぶ場」を提供してくれる、素晴らしい学校です。
「パッと稼げるようになりたい！」という人向けのスクールではなくて、「少し深く、そして広く学びたい」という人向けのスクールなのと、加えてコードレビューを生徒同士で行うので、合う人合わない人はかなり分かれるかもしれません。

42Tokyoでは、入学者を絶賛募集中です。
興味のある方は、ぜひこちらよりお申し込みください。
(注: 入学までに、オンライン試験や六本木にあるキャンパスの見学、オフライン試験があります)

1. 今回の記事は?

TL;DR

42には、C言語でprintfを再実装する課題がある。
そして、C#にはConsole.WriteLineメソッドなどで、フォーマットを指定して文字列を出力する機能がある。
→→→ C#でフォーマットが指定された文字列を生成する処理を再実装してみよう!

みなさん、C言語でプログラムを書いたことはありますか? printf系の関数、使ったことありますか?
たぶん、Cを使ったことがある人の99%は「printf系の関数を使ったことがある」と答えるんじゃないかと思います。(いやまぁ勘で言ってるので割合は違うかもしれませんが)

42では、特に本科の初期段階で様々な関数を再実装します。そして、再実装した関数群は後の課題で使いまくります。
そして、42では printf関数が使えません!
正確には、printf関数を自分で再実装して使用することになります。

ところで、C# (正確には.NET)にも「フォーマットを指定して文字列を出力する機能」があることはみなさんご存知ですか?
Console.WriteLineだったり、String.Formatだったり、色々あります。

ちなみに、C#の言語仕様的には、String interpolation (文字列補完)という機能があります。
とはいえ、これはString.FormatだったりString.Concatだったりに置換されるので、実質的にそれらと同等と考えることができます。 (参考: String interpolation using $ | Microsoft Learn)

そこで、今回は「42でやるprintfの再実装みたく、C#でString.Formatの再実装をしてみよう！」と考えて、ちょっと記事を書いてみました。

2. 制約条件

42のコーディング規約は、かなり厳しいです。いやまぁもっと厳しいところもあるかもしれませんが。
42のコーディング規約「Norm」はGitHubから誰でも見ることができるので、興味のある方はぜひご覧ください

じゃあ、C#でもNormに沿って……!! とは思ったんですが、流石に言語仕様が違う以上それは厳しく…

今回は、42で使用するC標準がC89であることから、これを曲解して「とにかく古い環境でも使えるようにしよう！」と考え、以下の制約を設定しようとしました。

C# 1.0を使用する
.NET Framwork 1.1でビルドできるようにする

但し、私のメインの開発環境がMacなのと、いまからnet11の開発環境を構築するのはあまりに手間だったので、一部修正して、以下の制約を用いることにしました

C# 1.0を使用する
- 但し、.NET Standard1.0ではC#1.0だとエラーが出るため、C#2.0を使用する
.NET Framework 1.1と.NET Standard 1.0でビルドできるようにする
以上の制約は、テストプロジェクトには適用しない
- テストプロジェクトは流石に勘弁してください… 42でもNormに沿ったテストプロジェクトとかそんなないだろうし…

なお、今回は例外まで完全互換にはしないことにします。流石にそれは面倒すぎるので…

C# 1.0と.NET Standardを組み合わせた際に起こること

.../obj/Debug/netstandard1.0/.NETStandard,Version=v1.0.AssemblyAttributes.cs(12,12): Error CS8022: Feature 'namespace alias qualifier' is not available in C# 1. Please use language version 2 or greater. (CS8022) (string.Format)

ということで、自動生成されるコードにC#2.0からサポートの::演算子が入っている都合上、C#1.0ではコンパイルできなくなっています。

https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/operators/namespace-alias-qualifier

3. 今回のコード

今回のコードはGitHubにホストしています。
流石に改修するつもりは無いのでArchiveにしてますが、Forkして改造する等は全然OKです。ライセンスはCC0を設定したので、ご自由にどうぞ。

(プロジェクトを作成する)

パパっと

% dotnet new sln -n string.Format
The template "Solution File" was created successfully.
% dotnet new classlib -n string.Format -f netstandard1.0 --langVersion 2.0 --no-restore
The template "Class Library" was created successfully.
% dotnet sln add string.Format
Project `string.Format/string.Format.csproj` added to the solution.

4. 仕様の把握

まずは、Microsoft Learnを確認してみましょう。最初に.NET Framework 1.1でのString.Formatメソッドです。

全部で5個のメソッドが並んでいます。

次に、最新の.NET7.0のものを見てみましょう。

全部で8個のメソッドが並んでいます。
net11時代と比較すると、IFormatProviderを第一引数に取って、可変長引数にならない範囲のメソッドが追加されていますね。

これだけの違いなので、今回はNET7.0のメソッド群を作ろうと思います。

次に、フォーマットの指定方法を確認してみましょう。

上記ページの「Format item syntax」より、指定は次のような構成で行うことがわかります。

{index[,alignment][:formatString]}

indexはそのまま引数の場所ですね。
alignmentは文字列の最低長指定です。例えば、"{12,3}"とすると、" 12"(左に半角スペース一つ)、"{1.2,-5}"とすると、"1.2 "(右に半角スペース二つ)になります。
formatStringは、引数で指定した各インスタンスの出力フォーマットを指定する文字列です。DateTimeとかでよく使いますね。

また、フォーマット指定ではない中括弧を表現するため、中括弧のエスケープも定義されています。例えば、"{{"と入力すると、"{"と出力されます。

最後に、処理順もきちんと定義されています。

5. 実装の方針

仕様を把握したので、実装の方針を考えます。

今回は、次の図のような流れで処理を行なっていきます。

(図の書き方合ってるかな…?)

6. 実装していく

あとは単純作業です。

なお、今回はnet11でビルドできねばな都合上、List<T>型を使用できません (List<T>はnet20からの対応)
その代わり、net11ではArrayListというものを使用できますが、object型からのキャストは正直不安なので、今回は単純な配列を使用することにします。

ここからは、「フォーマット指定部分 (とEscaped Brace)」のことをFormatItemSegmentと呼ぶことにします。(FormatItemSegment.cs)
また、FormatItemSegmentが表現する意味…というか、そこを解析した結果をFormatItemInfoと呼ぶことにします。(FormatItemInfo.cs)

6.1. FormatItemSegmentの数を数える

MyStringFormatter.cs#L11-L61

MyStringFormatter.cs#L11-L61

internal static int CountFormatItemAndEscapingBrace(string format)
{
	int numOfFormatItemAndEscapingBrace = 0;


	int indexOfFormatItemBeginBrace = INDEX_NO_VALUE;
	for (int i = 0; i < format.Length; i++)
	{
		if (format[i] == OPEN_BRACE)
		{
			// FormatItem開始位置の記録が初期位置なら、このBraceがFormatItemの開始を意味するかもしれない
			// 直前にOpenBraceが存在したなら、それはOpenBraceのエスケープ
			// FormatItem内にBraceは存在できないため、エラー
			if (indexOfFormatItemBeginBrace == INDEX_NO_VALUE)
				indexOfFormatItemBeginBrace = i;
			else if (indexOfFormatItemBeginBrace == (i - 1))
			{
				numOfFormatItemAndEscapingBrace++;
				indexOfFormatItemBeginBrace = INDEX_NO_VALUE;
			}
			else
				throw new FormatException("Brace cannot use in the Format item");
		}
		else if (format[i] == CLOSE_BRACE)
		{
			if (indexOfFormatItemBeginBrace == INDEX_NO_VALUE)
			{
				// FormatItemが開始していないのに終了しようとした
				// (Close Braceのエスケープではなかった)
				if (i == (format.Length - 1) || format[i + 1] != CLOSE_BRACE)
					throw new FormatException("Invalid Location Brace");


				i++;
				numOfFormatItemAndEscapingBrace++;
			}
			else
			{
				// このClose BraceはFormat Itemの終了を表すものなので、
				// カウンタのインクリメントと開始位置記録の初期化を行う
				numOfFormatItemAndEscapingBrace++;
				indexOfFormatItemBeginBrace = INDEX_NO_VALUE;
			}
		}
	}


	if (indexOfFormatItemBeginBrace != INDEX_NO_VALUE)
	{
		throw new FormatException("Brace not Closing");
	}


	return numOfFormatItemAndEscapingBrace;
}

何度も何度も走査するのは無駄なので、ここでついでに「中括弧の使い方」まわりのエラーチェックも行なっています。

6.2. FormatItemSegmentを生成する

MyStringFormatter.cs#L63-L101

MyStringFormatter.cs#L63-L101

internal static FormatItemSegment[] GetFormatItemSegments(string format, int numOfFormatItemAndEscapingBrace)
{
	// `CountFormatItem`にて
	FormatItemSegment[] segments = new FormatItemSegment[numOfFormatItemAndEscapingBrace];
	int segmentIndex = 0;


	int indexOfFormatItemBeginBrace = INDEX_NO_VALUE;
	for (int i = 0; i < format.Length; i++)
	{
		if (format[i] == OPEN_BRACE)
		{
			// エスケープされたBrace
			if (format[i + 1] == OPEN_BRACE)
			{
				segments[segmentIndex++] = new FormatItemSegment(i, 2);
				i++;
				continue;
			}


			indexOfFormatItemBeginBrace = i;
		}
		else if (format[i] == CLOSE_BRACE)
		{
			// エスケープされたBrace
			if (indexOfFormatItemBeginBrace == INDEX_NO_VALUE)
			{
				segments[segmentIndex++] = new FormatItemSegment(i, 2);
				i++;
			}
			else
			{
				segments[segmentIndex++] = new FormatItemSegment(indexOfFormatItemBeginBrace, i - indexOfFormatItemBeginBrace + 1);
				indexOfFormatItemBeginBrace = INDEX_NO_VALUE;
			}
		}
	}


	return segments;
}

先ほど数を数えた段階で既に中括弧まわりのエラーは取り除かれているので、ここではエラー解析を行なっていません。

6.3. FormatItemInfoを生成する

FormatItemInfo.cs#L29-L106

FormatItemInfo.cs#L29-L106

public FormatItemInfo(string format, FormatItemSegment segment)
{
	if (segment.Length == 2)
	{
		char char1 = format[segment.StartIndex];
		char char2 = format[segment.StartIndex + 1];


		if (char1 == OPEN_BRACE && char2 == OPEN_BRACE)
			this.ArgumentIndex = ARG_INDEX_MEANING_OF_ESCAPE_OPEN_BRACE;
		else if (char1 == CLOSE_BRACE && char2 == CLOSE_BRACE)
			this.ArgumentIndex = ARG_INDEX_MEANING_OF_ESCAPE_CLOSE_BRACE;
		else
			throw new ArgumentException("the string is not escaping a brace");


		return;
	}


	bool isIndexAlreadyParsed = false;
	bool isAlignmentAlreadyParsed = false;


	// 始まりと終わりの括弧は除いて解析する
	int startIndex = segment.StartIndex + 1;
	int closeBraceIndex = segment.StartIndex + segment.Length - 1;


	int currentComponentStartIndex = startIndex;


	for (int i = startIndex; i < closeBraceIndex; i++)
	{
		char currentChar = format[i];
		if (!isIndexAlreadyParsed)
		{
			if (currentChar == ALIGNMENT_SEPARATE_CHAR || currentChar == FORMAT_STRING_SEPARATE_CHAR)
			{
				isIndexAlreadyParsed = true;
				this.ArgumentIndex = int.Parse(format.Substring(currentComponentStartIndex, i - currentComponentStartIndex));
				currentComponentStartIndex = i + 1;


				if (currentChar == FORMAT_STRING_SEPARATE_CHAR)
				{
					isAlignmentAlreadyParsed = true;
					break;
				}
			}
			else if (!char.IsDigit(currentChar))
				throw new FormatException("You must use only digit in the `ArgumentIndex` segment");
		}
		else if (currentChar == FORMAT_STRING_SEPARATE_CHAR)
		{
			isAlignmentAlreadyParsed = true;
			if (currentComponentStartIndex == i)
				throw new FormatException("Alignment must have one value (You must put a number after a comma)");


			this.Alignment = int.Parse(format.Substring(currentComponentStartIndex, i - currentComponentStartIndex));
			currentComponentStartIndex = i + 1;
			break;
		}
	}


	if (currentComponentStartIndex != closeBraceIndex)
	{
		string unparsedString = format.Substring(currentComponentStartIndex, closeBraceIndex - currentComponentStartIndex);


		if (!isIndexAlreadyParsed)
		{
			this.ArgumentIndex = int.Parse(unparsedString);
		}
		else if (!isAlignmentAlreadyParsed)
		{
			this.Alignment = int.Parse(unparsedString);
		}
		else
		{
			this.FormatString = unparsedString;
		}
	}
	else if (!isAlignmentAlreadyParsed)
		throw new FormatException("Alignment must have one value (You must put a number after a comma)");
}

少し長くなりすぎましたが、FormatItemSegmentを用いて、渡された文字列を解析し、解析結果をインスタンスフィールドに記録しています。

本当はインターフェイス経由で中括弧を表すものと通常のものを分けた方が良いんだろうなぁとか思いながら、面倒だったのでこのまま実装しました。

6.4. 渡された引数を、解析して得たフォーマットを用いて文字列化する

FormatItemInfo.cs#L108-L246

FormatItemInfo.cs#L108-L246

private string ApplyAlignment(string str)
{
	int absAlignment = Math.Abs(this.Alignment);


	return this.Alignment < 0
		? str.PadRight(absAlignment)
		: str.PadLeft(absAlignment);
}


// Alignmentはまだ適用しない
internal string ObjToString(object obj, IFormatProvider formatProvider)
{
	if (obj == null)
		return string.Empty;


	if (IsAssignableTo(obj, typeof(ICustomFormatter)))
	{
		ICustomFormatter customFormatter = (ICustomFormatter)obj;


		string result = customFormatter.Format(this.FormatString, obj, formatProvider);


		if (result != null)
			return result;
	}


	if (IsAssignableTo(obj, typeof(IFormattable)))
	{
		IFormattable formattable = (IFormattable)obj;


		string result = formattable.ToString(this.FormatString, formatProvider);


		if (result != null)
			return result;
	}


	string toStringResult = obj.ToString();


	return toStringResult == null ? string.Empty : toStringResult;
}


static bool IsAssignableTo(object obj, Type typeToAssignTo)
{
#if NETSTANDARD2_0_OR_GREATER || NETFRAMEWORK
	return typeToAssignTo.IsAssignableFrom(obj.GetType());
#else
	return typeToAssignTo.GetTypeInfo().IsAssignableFrom(obj.GetType().GetTypeInfo());
#endif
}


#region Format
public string Format(object arg0)
{
	return FormatWithFormatProvider(null, arg0);
}
public string Format(object arg0, object arg1)
{
	return FormatWithFormatProvider(null, arg0, arg1);
}
public string Format(object arg0, object arg1, object arg2)
{
	return FormatWithFormatProvider(null, arg0, arg1, arg2);
}
public string Format(object[] args)
{
	return FormatWithFormatProvider(null, args);
}


public string FormatWithFormatProvider(IFormatProvider formatProvider, object arg0)
{
	switch (this.ArgumentIndex)
	{
		case ARG_INDEX_MEANING_OF_ESCAPE_OPEN_BRACE:
			return OPEN_BRACE_STR;
		case ARG_INDEX_MEANING_OF_ESCAPE_CLOSE_BRACE:
			return CLOSE_BRACE_STR;


		case 0:
			return ApplyAlignment(ObjToString(arg0, formatProvider));


		default:
			throw new IndexOutOfRangeException("The specified Index is out of range of the given arguments");
	}
}
public string FormatWithFormatProvider(IFormatProvider formatProvider, object arg0, object arg1)
{
	switch (this.ArgumentIndex)
	{
		case ARG_INDEX_MEANING_OF_ESCAPE_OPEN_BRACE:
			return OPEN_BRACE_STR;
		case ARG_INDEX_MEANING_OF_ESCAPE_CLOSE_BRACE:
			return CLOSE_BRACE_STR;


		case 0:
			return ApplyAlignment(ObjToString(arg0, formatProvider));
		case 1:
			return ApplyAlignment(ObjToString(arg1, formatProvider));


		default:
			throw new IndexOutOfRangeException("The specified Index is out of range of the given arguments");
	}
}
public string FormatWithFormatProvider(IFormatProvider formatProvider, object arg0, object arg1, object arg2)
{
	switch (this.ArgumentIndex)
	{
		case ARG_INDEX_MEANING_OF_ESCAPE_OPEN_BRACE:
			return OPEN_BRACE_STR;
		case ARG_INDEX_MEANING_OF_ESCAPE_CLOSE_BRACE:
			return CLOSE_BRACE_STR;


		case 0:
			return ApplyAlignment(ObjToString(arg0, formatProvider));
		case 1:
			return ApplyAlignment(ObjToString(arg1, formatProvider));
		case 2:
			return ApplyAlignment(ObjToString(arg2, formatProvider));


		default:
			throw new IndexOutOfRangeException("The specified Index is out of range of the given arguments");
	}
}


public string FormatWithFormatProvider(IFormatProvider formatProvider, object[] args)
{
	switch (this.ArgumentIndex)
	{
		case ARG_INDEX_MEANING_OF_ESCAPE_OPEN_BRACE:
			return OPEN_BRACE_STR;
		case ARG_INDEX_MEANING_OF_ESCAPE_CLOSE_BRACE:
			return CLOSE_BRACE_STR;


		default:
			if (args.Length <= this.ArgumentIndex)
				throw new IndexOutOfRangeException("The specified Index is out of range of the given arguments");


			return ApplyAlignment(ObjToString(args[this.ArgumentIndex], formatProvider));
	}
}
#endregion

前半半分が、解析して得られたフォーマットと渡されたインスタンスを用いて部分文字列を生成する処理ですね。

フォーマットの適用にあたり、ICustomFormatterやIFormattableを実装しているかのチェックが必要になります。(参考: Composite formatting | Microsoft Learn
しかし、as演算子やis演算子はC# 1.0時点では使用できないので、リフレクションを用いて型判定を実装しています。
また、リフレクションを用いた型判定にあたり、net11で使用できるメソッドがnetstandard1.0では使用できないということがあり、IsAssignableToメソッドを用意してそこで差異を吸収しています。

後半半分が、引数の個数別の部分文字列生成処理です。
もう少し良い実装方法があるような気はしましたが、面倒だったのでコピペ x 3にしました。

6.5. 文字列を結合する

MyStringFormatter.cs#L129-L175

MyStringFormatter.cs#L129-L175

internal int GetOutputLength(string[] formatItemStrings)
{
	int sumOfFormatItemStringLength = 0;
	foreach (string v in formatItemStrings)
		sumOfFormatItemStringLength += v.Length;


	return GivenFormatStr.Length - SumOfFormatItemSegmentLength + sumOfFormatItemStringLength;
}

internal string Concat(string[] formatItemStrings)
{
	int outputLength = GetOutputLength(formatItemStrings);
	char[] output = new char[outputLength];


	int lastIndexOfFormatStr = 0;
	int lastIndexOfOutputArray = 0;
	for (int i = 0; i < FormatItemSegmentArray.Length; i++)
	{
		FormatItemSegment currentSeg = FormatItemSegmentArray[i];
		if (lastIndexOfFormatStr != currentSeg.StartIndex)
		{
			// 直前までは単なる文字列だった
			// => その文字列を単純にoutputにcopyする


			int length = currentSeg.StartIndex - lastIndexOfFormatStr;
			GivenFormatStr.CopyTo(lastIndexOfFormatStr, output, lastIndexOfOutputArray, length);
			lastIndexOfOutputArray += length;
		}


		string strToCopy = formatItemStrings[i];
		strToCopy.CopyTo(0, output, lastIndexOfOutputArray, strToCopy.Length);


		lastIndexOfFormatStr = currentSeg.StartIndex + currentSeg.Length;
		lastIndexOfOutputArray += strToCopy.Length;
	}


	FormatItemSegment lastSeg = FormatItemSegmentArray[FormatItemSegmentArray.Length - 1];
	int nextIndexOfLastSeg = lastSeg.StartIndex + lastSeg.Length;
	if (GivenFormatStr.Length != nextIndexOfLastSeg)
	{
		// 最後のSegmentの後にまだ文字が存在する
		int length = GivenFormatStr.Length - nextIndexOfLastSeg;
		GivenFormatStr.CopyTo(nextIndexOfLastSeg, output, lastIndexOfOutputArray, length);
	}


	return new string(output);
}

先ほどは部分文字列の生成でstringを生成していました。しかし、stringは結合時に新しいインスタンスを生成してしまうため、多くの文字列を結合したいとなった際、メモリ使用量やメモリ確保コストが問題になる可能性があります。

これを回避するにはStringBuilderを使用するのが良いんでしょうけど、どうせなので今回はこれを使わずに実装しました。

string型とchar[]型は親和性が高い(?)ので、まず最終的な出力サイズを計算し、その分のchar配列を生成し、先ほど生成した部分文字列と、FormatItem以外の部分を順番にコピーしていき、そして最後にchar配列をstring型に変換して返しています。

…ん? stringのコンストラクタにchar[]を渡すとchar[]のコピーがstring内で保持されるから結局メモリ消費量は2倍…?

7. テスト

全てのケースを網羅しているわけではありませんが、とりあえずテストプロジェクトに色々実装してみました。

8. さいごに

C#はいいぞ💪