コンテンツにスキップ

意味的な差分と 3-way マージ(設計)

状態: 採用済みの設計。実装済み(マージドライバ、resolve、マージ後の確認、意味的な差分、履歴パネル)。

目的

git で管理しているプロジェクトを、ソフトウェアと同じようにブランチに分けて、マージできるようにします。マージはバイト列ではなく設計の上で行います。 2 人(あるいは 2 つのエージェント)が 2 つのブランチで別々のセル、あるいは 1 つのセルの別々のオブジェクトを変更すると、git が両方の変更を 1 つの設計にまとめます。 まとめられないものはオブジェクトごとに報告し、まとめた結果がどちらのブランチでも確認されていないセルは、DRC / LVS の対象として一覧にします。

要点は差分よりマージです。差分は「何が変わったか」を示し、マージは独立した変更から新しい設計を作ります。 changeset はすでに Undine の中でこの方法で合流しています(その間に先へ進んだ設計に、オブジェクトの id で適用する)。この設計は、git のブランチにも同じ規則を与えます。

目的ではないもの: 独自のバージョン管理システム(保存、転送、履歴は git のまま)、RTL のマージ(テキストなので git の行単位のマージ)、 GitHub の Web 上のマージで動くドライバ(GitHub はドライバを実行しません。その場合は「バイナリの衝突」になりますが、起きるのは両方が同じセルのファイルを変えたときだけです)。

扱いやすくしているもの

Undine はセルとビューごとに 1 つのファイルを保存します(libs/<lib>/<cell>.sch、.sym、.oas、.netlist.yaml、.intent.yaml)。 git はファイル単位で比べてマージするので、別々のセルを変えた 2 つのブランチはマージドライバまで届きません。git が変えた側のファイルをそのまま取ります。 ドライバが動くのは、両方が変えたファイルだけです。

もう半分は「同一性」です。マージは、ours と theirs のどのオブジェクトがベースの「同じ」オブジェクトかを知る必要があります:

ビュー オブジェクト 同一性
回路図、シンボル インスタンス name(名前の変更は、操作ログと同じくシンボルと配置で対応付ける)。名前のないものはその値
ワイヤ その値: 端点(向きは問わない)とプロパティ
テキスト その値: 文字列、位置、回転、大きさ、プロパティ
図形(レイヤごとの線、矩形、多角形、円弧) コレクション全体: ピンの矩形がシンボルのピンの順序を決めるため
K、G、V/S/E/F レコード 属性ごと(K)、ブロック全体(その他)
レイアウト 図形 その値: レイヤ、種類、形状、プロパティ。変更した図形は「消えた図形と加わった図形」
undine_inst の名前を持つインスタンス 名前
名前のないインスタンス その値: 子セル、変換、配列、プロパティ
メタ情報(PCell のパラメータなど) 名前
netlist ビュー ポート、インスタンス、コードブロック、保留中の接続 名前 / inst.pin
設計の意図 ポート、電源、項目、ビューの項目 名前 / 項目の id
操作ログ 記録 共通部分の後ろでの位置(ログは追記のみ)

GDS / OASIS の図形には id がなく、Undine も作りません。操作ログのレイアウトの効果と同じく、図形はその形状そのものです。 そのため、レイアウトはレイヤごとの図形の多重集合になり、両方の側が別々の場所を編集した場合、その 3-way マージは厳密に決まります:

各図形 s について:  n(s) = ours(s) + theirs(s) - base(s)   (一方がベースの数のままなら、もう一方の数)

1 つのセルの中でも、別々の図形への編集は、対応付けの推測なしにまとまります。両方が同じ場所を編集した場合は、後で述べる領域で決めます。

規則

すべての値(属性、配置、図形の数、図形のコレクション全体)に 1 つの規則を使います:

base ours theirs 結果
b b t t
b o b o
b x x x(両方が同じ変更をした)
b o t 衝突: ours を残し、theirs を報告する

「ない」も値です。一方で追加したオブジェクトは ない → v、一方で削除したものは v → ない です。一方で削除し、もう一方で変更したものは衝突(削除と変更)です。

まとめた値が必ず「誰かが書いた値」になるように、粒度を選んでいます:

  • インスタンスの配置(x、y、回転、反転。レイアウトのインスタンスでは変換と配列)は 1 つの値です。 ours が右へ、theirs が上へ動かしたら、誰も行っていない斜めの移動ではなく、衝突です。
  • インスタンスのプロパティはプロパティごとにまとめます。同じトランジスタで ours が W を、theirs が L を変えたら、両方が入ります。
  • シンボルの図形のコレクションはそれぞれ 1 つの値(ピンの順序)、K レコードは属性ごとです。
  • 設計の意図の項目はフィールドごと、serves は集合としてまとめます。

順序: オブジェクトは ours での位置を保ちます。theirs だけが加えたものは、theirs でその前にあり、結果にも残っている最も近いオブジェクトの後ろに入れます(それがなければ先頭)。 ただし、見た目だけではない順序が 1 つあります。回路図のポートのインスタンス(ipin、opin、iopin)の順序は、サブサーキットのピンの順序です。 そのため、この並びは独立した 1 つの値として扱います。一方がポートの並べ替え、追加、削除をしたらその側を取り、両方が別々に変えたら衝突(ports)です。

同一性だけでは分からない衝突: 領域

値そのものが同一性であるオブジェクト(レイアウトの図形、名前のないレイアウトと回路図のインスタンス、回路図のワイヤとテキスト)は、変更できず、置き換えるしかありません。 編集は「消えたオブジェクト」と「加わったオブジェクト」になります。同じオブジェクトへの 2 つの編集は、消えた 1 つのオブジェクトと別々の 2 つの置き換えになり、 オブジェクトごとの数だけでは両方が残ります(移動したコンタクトが 2 つ、両側の新しい端点につながったネット、相手の移動で取り消された削除)。 そこでこれらは領域ごとにまとめます。変わったオブジェクト(どちらかの側が消したもの、加えたもの)をまとめ、次の場合に同じ領域とします:

  • 接している: 同じレイヤでバウンディングボックスが接するレイアウトの図形。端点が相手の上にあるか、交差するワイヤ。同じ位置のインスタンスやテキスト(レイアウトのインスタンスの子はゴーストセルなので、分かるのは位置だけです)
  • または、ある側が消したオブジェクトのコピーを、同じ側が加えた(同じ図形、位置以外は同じインスタンスやテキスト、同じ向きと長さのワイヤ)。最も近い消したものと 1 対 1 で組にします。距離に関係なく「移動」です。

領域ごとに: 一方の側だけが変えたか、両方が同じように変えたら、その側の版を取ります。両方が別々に変えたら 1 つの衝突 (shape:<cell>:<layer>:<最初に消えた図形>、inst:<cell>:<...>、wire:<最初に消えたワイヤ>)で、領域全体について決めます。 取った側の版を領域のすべてのオブジェクトに使います(解決で theirs を選ばない限り ours)。衝突には、誰が何をしたか(「両方が変更した」「ours が削除し、theirs が変更した」「両方が追加した」)と、 それぞれの側がそこで消したもの、加えたものを示します。

これは意図して保守的な読み方で、git が行に対して行うのと同じです。両方が同じ編集をし、一方がそれに接する追加もした場合は衝突です (git も、同じ行の変更に加えて一方がその隣に行を足すと衝突にします)。両方が加えた図形が互いに接する場合も衝突です(2 つのネットが描き込まれてつながる)。 同じものを消しながら描いたコピーは、その移動とみなします。別の場所への追加や、別々の場所の編集はまとまります。

一方だけが加えた(または移動した、入れ替えた)、同じ子セル(またはシンボル)の名前付きインスタンスが、もう一方のものと同じ位置にある場合は警告です。同じデバイスを 2 回置いている可能性があります。

マージが成功しても証明されないこと

衝突なくまとまったマージが、正しい設計とは限りません。それを決めるのは changeset と同じく DRC、LVS、スペックです。 undine merge-check は確認すべきセルを一覧にします。セルの階層(自分のビューと、レイアウトと回路図で配置しているすべてのセルのビュー)のまとめた内容が、 どちらの側とも一致しないセルが対象です。これは、ちょうど「誰も確認していない組み合わせ」の集合です。 一方の側からそのまま取ったセルは、その側の確認結果をそのまま使えます。まとめたセルの上にあるセルは使えません。

ビューごとの扱い

  • 回路図、シンボル(.sch、.sym): Xschem のモデルとして読み、インスタンス、ワイヤ、テキスト、図形のコレクション、K / G / V / S / E / F レコードに上の規則を使います。 書き出しはエディタと同じライタです。まとめたモデルが一方の側と同じなら、その側のバイト列をそのまま残します。
  • レイアウト(.oas、1 つのセルと、その子をゴーストセルとして持つ): KLayout で読みます。図形はレイヤごとに領域で、インスタンスは名前か値、メタ情報は名前で扱います。 書き出しはレイアウトの保存と同じ方法で、ゴーストセルはまとめたインスタンスの子です。
  • netlist ビュー(.netlist.yaml): 回路図から作られ、次に Undine が読むときに、まとめた回路図から読み直されます。ほかにない情報は保留中の接続(pending)だけなので、 これはピンごとにまとめます。一方が保留中の接続としてつないだピンを、もう一方が別のネットに描いた場合は衝突です(そのままでは黙って回路図が勝つため)。 ある側でピンが「描かれた」とみなすのは、その側に保留中の接続がなく、ネットが孤立した名前なしのネット(そのピンだけの net)でなく、ベースですでに描かれていなかった場合です。 それ以外の違いは回路図に従い、衝突としては報告しません(そのことを 1 つの警告で伝えます)。
  • 設計の意図(.intent.yaml): ポートと電源は名前ごと、メモはテキスト(行単位のマージ)、項目はフィールドごとで、serves は集合としてまとめます。 項目の同一性は、追加したときに作られて変わることのない uid です。読める id(c3)は名前にすぎません。id は順番に割り当てるので、両方が c3 を加えることはよくあります。 その場合は両方の項目を残し、theirs のものを次の空いている id に改名します。serves は同一性の集合としてまとめるので、 id がどう変わっても参照はついていきます(このマージでも、後のマージでも。もう一方のブランチがまだ c3 と呼んでいる項目は uid で対応付けます)。 cherry-pick した項目は uid を保つので、2 つになることはありません。uid ができる前に書かれた項目は id で対応付け、以前の推測(theirs の衝突した追加を改番する、 以前のマージの改番に従う)を使います。新しい id は使われている最大の番号の次から割り当てます(削除した id を再び使いません)。
  • 操作ログ(history/<lib>.jsonl): 両方の共通部分の後ろの記録を、ours、番号を振り直した theirs(of の参照も合わせる)、merge の記録、の順に並べます。 それぞれの側の操作は、ベースと共有する部分より後ろの記録なので、cherry-pick では選んだコミットの操作だけが入ります。 Undo / Redo の履歴は merge の記録で止まります。マージ前の編集を、相手側の編集の上から取り消すことはしません。 レイアウトの編集は、セルのファイルに保存されるまでログの中の未保存の記録です。まとめたセルのファイルは両方の側の保存済みのファイルをまとめたものなので、 merge の記録を保存とみなします。ある側の未保存の記録が残るのは、もう一方の側がレイアウトを変えていない場合だけです(まとめたファイルはその側のファイルになるため)。 このとき merge の記録がそれを一覧にし("replay": [seq ...])、Undine はライブラリを開くときに再生します。 両方の側がレイアウトを変え、どちらかに未保存の編集がある場合は、ログが衝突になります(layout-journal)。各ブランチでレイアウトを保存してコミットし、マージし直してください (この衝突を解決すると、未保存の編集は捨てられます)。git-setup が入れる pre-commit フックは、ステージした操作ログに未保存のレイアウトの編集があるコミットを拒否するので、 これが起きるのはフックを通らなかったコミットのときだけです。
  • project.json と undine.lock(vcs/depmerge.py、packages.ja.md の段階 4)は、 JSON としてエントリ単位で、どの値にも同じ規則でマージします: project.json の libraries と indexes はエントリごと、 trusted は集合として、ほかのキーは 1 つの値として(pdk、name)。lock の libraries と packages はエントリごと、 tools はツールごと、ほかのキーは 1 つの値として(format、pdk)。別々の依存を加えた 2 つのブランチは、どちらの順でも きれいにマージされます。1 つのエントリを違うように変えた 2 つは、そこで衝突します(library ip、locked package amp。 ours を残します)。マージしたファイルは Undine が書くとおりの形で書きます。changeset の採用では続いて、マージした lock が マージした project.json の求めるものをまだ固定しているかを、2 つのファイルだけから(git もネットワークも使わずに)確かめます: プロジェクト自身のファイルになかった問題があれば、undine.lock の衝突として採用を拒否します(after merging project.json and undine.lock: ...)。Undine の外の git merge はこの確認をしません: lib status が報告します。
  • それ以外(RTL、changeset の記録)は git に任せます。

git との統合

undine git-setup PROJECT(これまでもプロジェクトを git リポジトリにする方法でした)が、マージドライバも登録します:

.gitattributes   *.sch *.sym *.oas *.netlist.yaml *.intent.yaml history/*.jsonl project.json undine.lock
                 merge=undine
.git/config      merge.undine.driver = <python> -P -m undine merge-driver %O %A %B %P
                 merge.undine.recursive = undine-base
                 merge.undine-base.driver = <python> -P -m undine merge-driver --virtual-base %O %A %B %P

git はドライバをリポジトリの最上位のディレクトリで実行します。-P はそのディレクトリを Python のモジュールの検索パスから外すので、 そこにコミットされたファイル(yaml.py など)がマージの途中で実行されることはありません(-P のない Python 3.10 では、-c の前処理で外します)。 git-setup は pre-commit フック(undine precommit)も入れます。ステージした操作ログに未保存のレイアウトの編集があるコミットを拒否します。 これらはすべて git のローカルな設定なので、クローンごとに git-setup を実行し直してください。

criss-cross マージ(2 つのブランチが互いをマージした後のマージ)にはマージベースが複数あり、git はまず merge.undine.recursive が指すドライバで、 それらを 1 つの仮想的なベースにまとめます。そこでの衝突は、ベースどうしの共通のベースの値を取ります。ours を残すと一方のブランチの解決がベースになり、 マージがもう一方の解決を黙って採ってしまうためです。古い値と比べれば両方の解決が変更として見え、マージがその衝突を報告します。 きれいにまとまった部分はそのまま残します。取るべきベースの値がない衝突(1 つの名前で加えた 2 つのインスタンス、読めないファイル)では、 git がバイナリのファイルにするのと同じく、古いベース全体を使います。

ドライバはまとめたファイルを %A に書いて 0 で終わります。衝突があるときは、手元で最良の結果(衝突ごとに ours を残したもの)を書いて 1 で終わり、 git はそのファイルを衝突として扱います。どちらの場合も報告(両方の値を含む衝突、警告、まとめた内容、マージした blob。まとめられなかったときはそのエラーで、 ファイルは ours のままです)を 2 つの名前で書きます: このマージ自身の .git/undine-merge/<path>.<key>.json(key は base、ours、theirs の blob のハッシュ)と、 そのファイルの最新の .git/undine-merge/<path>.json です。そのため、後で同じファイルをもう一度マージしても(操作ログはほぼ毎回そうなります)、 前のマージの報告は残ります。報告はマージしたクローンの中にだけあります。

解決: git は衝突したファイルのベース、ours、theirs をインデックスに残します(ステージ 1、2、3)。 undine resolve PATH [--theirs ID ...] [--ours ID ...] はそれらをもう一度マージし、指定した衝突は指定した側を取って、ファイルと報告を書きます。 解決済みにするのは、いつもどおり git add PATH です。

undine merge-check [DIR](プロジェクトのディレクトリ。マージ、cherry-pick、rebase の途中、またはマージコミットに対して --commit C で): まだ残っている衝突、警告、確認すべきセル(上記)を示します。確認すべきセルにはそれぞれ理由が付きます: 自分のファイルをマージした。 ファイルは一方の側のものだが、その下のセルがその側のとおりではない。ファイルも下のセルも一方の側のものだが、配置しているものが別のセルを指すようになった。 パスは、git や undine resolve と同じく、リポジトリの最上位からです。マージコミットの確認すべきセルは、コミットだけから計算します(どのクローンでも使えます)。 警告は、blob でそのマージのものと分かる報告から取ります。ここに報告のないファイル(別のクローンでマージしたもの、ドライバを実行しない git の octopus 戦略でマージしたもの)は、そのことを示します。 rebase や複数のコミットの cherry-pick の途中では、git が止まったコミットだけが対象です。それより前のコミットの警告は、マージしたときに表示されています。

Undine が動いている間にも、ファイルは変わります: git はマージしたファイルを書き、checkout、pull、rebase はファイルを置き換えます。サーバーの回路図、シンボル、 ネットリスト、設計意図のエディタは、操作のたびにファイルを読み、リクエストの間には何も持たないので、編集は git が書いた内容に対して行われます。 ライブラリのレイアウトはメモリにあり、未保存の編集はログの中のジャーナルです。レイアウトは、読んだ、または保存したセルのファイルそれぞれの指紋(更新時刻、 大きさ、inode)とログのジャーナルを覚えておき、1 秒に 1 回まで、また保存の前には必ず比べます。未保存の編集がなければ、ファイルを読み直します (ライブラリを開くときと同じく、git が持ってきたジャーナルも再生します)。未保存の編集があれば、それをファイルにまとめることはしません: レイアウトを古くなったもの(stale)とし(履歴パネルと状態の stale がそれを示します)、編集を捨てて読み直すまで保存を断ります。保存すると、 git が書いたファイルの上に元のままのセルを書いてしまうためです。読み直しは、"args": {"reload": true} を付けたレイアウトの save の記録として残ります。 ジャーナルを読むもの(再生、ログのマージ、pre-commit フック)はどれもレイアウトの保存で止まるので、捨てた編集が再び適用されることはなく、 Undo もそこで止まります。自分の保存や編集はディスク上の変化とはみなさず、同じ内容のまま触れただけのファイル(stash と pop)も衝突にはしません。

undine diff OLD NEW(2 つのファイル)と undine diff --rev A [B](プロジェクトの 2 つのコミット): マージと同じ同一性を使った、意味的な差分です。 レイアウトでは、構造の差分(図形、インスタンス、メタ情報)と形状の差分(セル自身の図形の、レイヤごとの XOR)の両方を示します。 多角形を同じ領域を覆う 2 つの矩形に置き換えるのは、構造の変更で、形状の変更ではありません。配置したセルは XOR に展開しません(セルのファイルにはゴーストセルとしてしかないため)。 そのため、インスタンスの移動は、インスタンスの変更 1 つで、XOR の面積はありません。

まだ扱わないもの

  • Undine がレイアウトを開いている間のマージやチェックアウトに、未保存のレイアウトの編集は引き継がれません。読み直すと捨てられます(ログには残ります)。 git を実行する前にレイアウトを保存してください。
  • ブラウザが全体を持っているテキスト(エディタで開いている RTL のファイル、YAML で編集する設計意図)は、持っているまま保存され、 ファイルが読んだときのままかどうかは確かめません。git がファイルを変えた後に保存すると、git が書いた内容を上書きします。
  • Web UI から始めるマージ(ブランチ、レイアウト上に描く衝突の印)は、このエンジンを使う予定です。履歴パネルはマージの衝突、それを解決するコマンド、 確認すべきセルを示し、マージそのものは git で行います。
  • ファイルをまたいだ整合性(一方で回路図のインスタンスの名前を、もう一方でレイアウトのインスタンスを変えた、など)は、マージではなく LVS が確認します。