Skip to content

Instantly share code, notes, and snippets.

@ainame

ainame/memo.md Secret

Last active July 18, 2023 01:38
Show Gist options
  • Save ainame/edeedf3754c04959e2483e8b9bfbe3d3 to your computer and use it in GitHub Desktop.
Save ainame/edeedf3754c04959e2483e8b9bfbe3d3 to your computer and use it in GitHub Desktop.
Download ZIP
2022/08/02 わいわいswiftc用資料 https://iosdiscord.connpass.com/event/252856/
Raw
memo.md

apple/swift-experimental-string-processing ソースコードリーディング

経緯

元同僚（😭）の @giginet 氏のリモート送別会中に雑談でSwift 5.7の正規表現の話をしていたらじゃあわいわいSwiftcでソースコードリーディング会やってくださいよ〜ということで何となく参加が決まった。 時差の問題があるため、わいわいswiftcは初参加だしSwiftのコンパイラーについてもほとんど何も知らないので弱々人材なのでお手柔らかにお願いします。

今日やること・目標

apple/swift-experimental-string-processingというリポジトリについて何が起こっているのかを紹介。コードリーディング会なので途中から各自読みつつ考えたことなどを議論してもらいながら進められたら良いと思う。自分が答えられるかどうかはわからないけど随時どんどん突っ込んでもらいわいわいしていきましょう。

Swift5.7でのRegexの実装に少し詳しくなって、このイベント以降参加者自身でコードを読み進められるような状態になるのが目標。 関連する仕様やそこそこ複雑な技術・実装が多いので100％完全理解するのはこの会では諦める。特にUnicodeの仕様や正規表現のマッチングエンジンの実装方法そのものなどは大変。

自己紹介

普段はCookpad limitedというクックパッド株式会社の子会社の英国支店で働いていて、アプリの機能開発をしたりCI/CDや各種自動化だったり、 基盤寄りの仕事をしている。オフィスはロンドンではなくブリストルという地方都市ですが結構良いところ。 アプリの機能開発・基盤系のポジション両方で募集中なので、興味がある方は@ainameまでDM or Meetyからカジュアル雑談しましょう。

準備

  • Xcode 14 betaをダウンロードしてunxip
  • swift.orgから5.7のsnapshotをダウンロードしてXcode 14 betaで使えるようにする https://www.swift.org/download/
  • git clone https://github.com/apple/swift-experimental-string-processing.git
  • swift/releases/5.7ブランチをチェックアウト
  • 適当にMonterey上で実行して遊ぶだけならsnapshotを入れてiOS simulator(iOS 16)上で実行すれば良い（？他に良いやり方があれば教えてください）

Screenshot 2022-08-01 at 12 00 20

Screenshot 2022-08-01 at 11 24 04

  • プロジェクトの全部のターゲットをコンパイルをするためにはmacOSをVentura betaにあげると良い(Xcode 13が使えなくなるので注意)

WWDC

Swift 5.7の新しい正規表現について何も知らないよという人は以下のWWDCのセッションを見る

swift-evolution

apple/swift-experimental-string-processingの各種実装を理解するために以下のswift-evolutionのproposalsを先に目を通しておくと便利。 (この辺の話をまとめてiOSDCで話そうと考えています。)

apple/swift-experimental-string-processingでいろいろなアプローチを試した結果がswift-evolutionのproposalsに至ったのだと推測しています。

README.md

Declarative String Processing for Swift

An early experimental general-purpose pattern matching engine for Swift.

と書いてある。最初期は宣言的な文字列処理をするためのパターンマッチングエンジンというところから始まっているのが分かる。 https://forums.swift.org/t/declarative-string-processing-overview/52459

Integration with Swift

_RegexParser and _StringProcessing are specially integrated modules that are built as part of apple/swift. Specifically, _RegexParser contains the parser for regular expression literals and is built both as part of the compiler and as a core library. _CUnicode and _StringProcessing are built together as a core library named _StringProcessing.

_RegexParserと_StringProcessingは特別にapple/swiftに統合されていて特に_RegexParserはコアライブラリだけではなく正規表現リテラルをパースするためのコンパイラーとしても組み込まれている。 _CUnicodeは_StringProcessingの一部としてコアライブラリに組み込まれている。

Module Swift toolchain component
_RegexParser SwiftCompilerSources/Sources/_RegexParser and stdlib/public/_RegexParser
_CUnicode stdlib/public/_StringProcessing
_StringProcessing stdlib/public/_StringProcessing

Branching scheme

  • mainで開発されている
  • apple/swiftに統合していくためにapple/swiftのmainやrelease/5.7に対応するブランチも存在している

Package.swift

実際のライブラリ部分だけではなく動作確認やベンチマーク用のスクリプトのターゲットも含まれている。

Libraries

  • _RegexParser
  • _CUnicode
  • _StringProcessing
  • RegexTests
  • RegexBuilderTests
  • MatchingEngineTests

Scripts

  • VariadicsGenerator
  • PatternConverter
  • RegexTester

Exercises

Exercises are tasks that various approaches or conformers can tackle. The idea is to support naive, hand-written, regex, PEG, consumer, and arbitrary 3rd party libraries to demonstrate their approaches and "compete" with each other.

This particular formulation is a straw-person and we may rearchitect it a bit.

開発初期段階でいろんな文字列処理の手法を比較するために作られたターゲット。 もう使われていなさそう。

https://github.com/apple/swift-experimental-string-processing/commit/c29c360020de58fb6474fd247bb1964a6626c94c

  • Exercises
  • ExercisesTests

ディレクトリ構成

SPM準拠のSourcesとTestsの構成 + swift-evolutionのためのdraftなどが入っているDocumentation 、ちょっとしたPythonのスクリプトが入っているUtils。 あとCMakeでビルド出来るようになっている。

% tree -d -L 2 .
.
├── CMakeFiles
│   └── 3.22.2
├── Documentation
│   └── Evolution
├── Sources
│   ├── Exercises
│   ├── PatternConverter
│   ├── RegexBenchmark
│   ├── RegexBuilder
│   ├── TestSupport
│   ├── VariadicsGenerator
│   ├── _CUnicode
│   ├── _RegexParser
│   └── _StringProcessing
├── Tests
│   ├── ExercisesTests
│   ├── MatchingEngineTests
│   ├── Prototypes
│   ├── PrototypesTests
│   ├── RegexBuilderTests
│   ├── RegexTests
│   └── UnicodeTests
└── Utils
    └── gen-unicode-data

Documentation

swift-evolutionからリンクされている.mdファイルがあったりドラフトが置かれていたりするが、BigPicture.mdというファイルが初期コミットで書かれていて当時の意気込みなどが伺える。 https://github.com/apple/swift-experimental-string-processing/blob/swift/release/5.7/Documentation/BigPicture.md

Introduction

I've been finding it helpful to think of our long-term goal as making Swift awesome at string processing, data processing, and "event processing" (working title, suggestions welcome). These are not rigid or clear-cut distinct domains (they actually blend together in extremity) so much as they are 3 interesting "regions" in this design space. Thinking about these regions helps clarify what tasks we're enabling and helps push us towards more general solutions.

Each of these regions share technical fundamentals, but present novel performance and API design challenges. I hope that keeping the big picture in mind will help guide the design process towards pragmatic trade-offs and robust solutions.

By "string processing" (at least in the context of this document), I mean processing with the Unicode-rich semantics of Swift's String and Character types. By "data processing", I mean efficient processing done at a binary semantics level, even if such data happens to be viewable as text. By "event processing" (working title, suggestions welcome), I mean being able to detect and respond to patterns over ephemeral "events" issued from an asynchronous source.

We want to be able to compose, layer, and even interweave different kinds of processing together. And, we want these areas to be library-extensible, so that libraries can provide custom behavior through custom protocol conformances. For example, custom String interpolation is extended by libraries for logging, sanitizing, templating, and many other applications. Similarly, there are myriad formulations of pattern matching and we want to enable libraries to provide powerful new abstractions.

一番最初期には正規表現(Regex)という単語が含まれていなかったのでリポジトリ名の通り本当に文字列処理全般を改善するのが狙いだったように見える。 以下の3つの挑戦的なエリアで改善を目指している。俺の考えた最強の文字列処理みたいになっている。

  • String processing
  • Data processing
  • Event processing

String processing

Unicode-richなSwiftのStringに基づいた文字列処理、例えばextended grapheme clusters(複数のUnicodeのcode pointで構成されている文字など)が正しく扱えるとか。

例:

Matching "🧟‍♀️" using . wildcard Matched Remaining content
String 🧟‍♀️ ""
String.UnicodeScalarView U+1F9DF U+200D U+2640
String.UTF8View F0 9F A7 9F E2 80 8D E2 99 80

また文字列処理をライブラリで拡張しやすいようにprotocolを提供したり、パーサーをcomposableにすることで例えばFoundationのFormatterのFormatStyleみたいなものでローカライズの対応が出来るようにしたり。

さらにCollectionに基づく文字列処理も一般化も狙いたい（String/SubstringはBidirectionalCollectionなので）と言っているが、今のところ実現はしてなさそう。

Data processing

String processingの話とは逆に、目に見える文字列としての文字列処理とデータの処理は異なる。例えばCSVファイルの中にU+0301(アクセント記号)だけの列があったとする

... , U+301 , ...

U+0301はextended grapheme clustersとして前の文字列にアクセント記号として見た目上結合するのでただの文字列として処理するならば結合した1文字として扱うべきだが、 CSVファイルのData processingとしては,はfield separatorとして扱われるべきという話。

irb(main):004:0> "X\u{0301}"
=> "X́"
irb(main):005:0> ",\u{0301}"
=> ",́"

Swiftの文字列処理ではこのbinary semantics-levelとSwiftのStringのsemanticsでのパースを提供できるようにしたい。他の例では JSONのパース処理は全体をbinary semanctics-levelでパースしてDictionaryに変換するが、コンテンツはStringのsemanticsで取り扱うなど。

またAsyncSequenceをソースとして扱うような場合にBacktrackingなどの挙動の制限や、Collectionの処理をどのようにあつかpeek/consume patternなどが適用できるのかどうか。いろいろ考えることが増え、Event processingという考えに至っている。

Event processing

例えばサーバーが任意のユーザーの入力が事前に承認されているかどうかをチェックして承認されていた場合のみ正しく処理して、そうでない場合は任意のフックを呼び出してサーバーを停止してセキュリティレポートを作成するなど、非同期のAPIに対しての設計上の挑戦があると言っているが、具体的に何か現時点で実装されているのかどうかは良くわかりませんでした（by ainame）。

Developer experience

Parser combinatorのような関数を呼び出したり組み合わせたりしてコードをただ書くだけのような体験を提供したい→ Regex Builderが出来た？

_CUnicode

apple/swiftにおけるICUへの依存を無くすための実装をこのリポジトリでの開発向けに重複して持っていてapple/swiftに統合されるときには重複がなくなっているのかも？（推測） apple/swift内では同じようなコードがC++で実装されているがこちらはC。

  • 関連issues
  • ICU（NSRegularExpressionで使われている）は正準等価（Canonical Equivalent）での文字列比較に対応していないためSwiftのStringのモデルと異なるという課題があった
  • ICUにはUCD（Unicode Character Database）というデータが含まれていて良い感じにアクセス出来るインターフェイスがあるがそれをSwift向けに最適化したデータとしてScriptData.hにハードコーディングしてある

_RegexParser

_ RegexリテラルのParser。コンパイラーからとランタイムのRegexのinitializerで使われている。 https://github.com/apple/swift/blob/main/stdlib/public/RegexParser/CMakeLists.txt

public struct Source {
  var input: Input // prototype上では一旦 typealias Input = String となっている
  var bounds: Range<Input.Index>
}

_StringProcessing

struct Regex<Output>やマッチングのロジックなどが実装されているメイン箇所。 https://github.com/apple/swift/blob/main/stdlib/public/StringProcessing/CMakeLists.txt

% tree -L 1 Sources/_StringProcessing
Sources/_StringProcessing
├── Algorithms
├── ByteCodeGen.swift
├── CMakeLists.txt
├── Capture.swift
├── Compiler.swift
├── ConsumerInterface.swift
├── Engine
├── Executor.swift
├── MatchingOptions.swift
├── PrintAsPattern.swift
├── Regex
├── Unicode
├── Utility
└── _CharacterClassModel.swift
% tree -L 1 Sources/_StringProcessing/Algorithms
Sources/_StringProcessing/Algorithms
├── Algorithms # Collectionのextension
├── Consumers  #
├── Matching
└── Searchers

正規表現の表現周り

マッチングエンジン周り

正規表現のマッチングエンジンは大きく分けるとDFA（決定性有限オートマトン）型とVM型に分かれるらしくSwiftは後者のVM型での実装。 https://qiita.com/yyu/items/84b1a00459408d1a7321 https://qiita.com/reonyanarticle/items/bc2e683fad476ec17310

DFA型にすべきかかどうかなどの議論はswift-evolutionでも軽く言及されていてcode sizeの面でVM型のbytecodeにした方がサイズが小さく済むので良いと言われている(?)。 ただし最適化はfuture workとされている。 https://github.com/apple/swift-evolution/blob/0823dc6fc678e3a91a812a49b1830f61abc2e04a/proposals/0350-regex-type-overview.md#future-work-static-optimization-and-compilation

  func _match(
    _ input: String,
    in subjectBounds: Range<String.Index>,
    mode: MatchMode = .wholeString
  ) throws -> Regex<Output>.Match? {
    let executor = Executor(program: regex.program.loweredProgram)
    return try executor.match(input, in: subjectBounds, mode)
  }

Algorithms

SE-0357 https://github.com/apple/swift-evolution/blob/main/proposals/0357-regex-string-processing-algorithms.md で提案されているCollectionの 各種メソッドにおける正規表現の利用などの実装が https://github.com/apple/swift-experimental-string-processing/blob/swift/release/5.7/Sources/_StringProcessing/Algorithms に実装されている。

let bool = "Hello World!".contains(/Hello .*!*/) // => true

Collectionに対してはSearcherを経由してRegexを実行することで、操作に応じて最適なアルゴリズムで検索処理を呼び出せるようになっているように見える。 https://github.com/apple/swift-evolution/blob/main/proposals/0357-regex-string-processing-algorithms.md#string-and-collection-algorithm-additions

RegexBuilder

Result builderを使ったDSL。SwiftのRegexではRegex.OutputがTupleで表現されているがCaputreの数だけTuple内の型が必要になる。 それによってResult Builder実装に必要なbuildBlockメソッドに必要なgenericsの型の数の組み合わせが爆発してしまう。 SE-0348によってResult Builderの実装が楽になっている。

自前でマッチングエンジンを実装しているためTryCaptureやCaptureに渡せるtransform引数のclosureがIntstruction.Payloadに格納されて closure内でnilを返した時にbacktrackを起こせるようになっている。

https://github.com/apple/swift-experimental-string-processing/blob/swift/release/5.7/Sources/_StringProcessing/Engine/Processor.swift#L561-L571

@stzn さんの日本語での解説(翻訳?) https://github.com/stzn/SwiftPodcast/blob/main/episodes/Swift%20buildPartialBlock%E3%81%A7Result%20Builder%E3%81%AE%E3%83%9C%E3%82%A4%E3%83%A9%E3%83%BC%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%E5%89%8A%E6%B8%9B.md

おわり

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment