| 1 | <?php |
| 2 | /************************************************************* |
| 3 | # 076 License |
| 4 | |
| 5 | Copyright (c) テクニカル諏訪子 |
| 6 | |
| 7 | Permission is hereby granted to any person obtaining a copy of the software |
| 8 | Little Beast (the "Software") to use, modify, merge, copy, publish, distribute, |
| 9 | sublicense, and/or sell copies of the Software, subject to the following conditions: |
| 10 | |
| 11 | 1. **Origin Attribution**: |
| 12 | - You must not misrepresent the origin of the Software; you must not claim |
| 13 | you created the original Software. |
| 14 | - If the Software is used in a product, you must either: |
| 15 | a. Provide clear attribution in the product's documentation, user interface, |
| 16 | or other visible areas, **OR** |
| 17 | b. Pay the original developers a fee they specify in writing. |
| 18 | 2. **Usage Restriction**: |
| 19 | - The Software, or any derivative works, dependencies, or libraries |
| 20 | incorporating it, must not be used for censorship or to suppress freedom of |
| 21 | speech, expression, or creativity. Prohibited uses include, but are not |
| 22 | limited to: |
| 23 | - Censorship of so-called "hate speech", visuals, non-mainstream opinions, |
| 24 | ideas, or objective reality. |
| 25 | - Tools or systems designed to restrict access to information or |
| 26 | artistic works. |
| 27 | 3. **Notice Preservation**: |
| 28 | - This license and the above copyright notice must remain intact in all copies |
| 29 | of the source code. |
| 30 | |
| 31 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
| 32 | INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A |
| 33 | PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| 34 | HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF |
| 35 | CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE |
| 36 | OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 37 | */ |
| 38 | namespace Std\Lib\Git; |
| 39 | |
| 40 | /** |
| 41 | * 3方向のマージ（行とツリー） |
| 42 | * |
| 43 | * 行：共通の祖先からの両方の変更を合わせる（diff3）。重なるか隣り合う変更が違えばコンフリクト（gitと同じ）。 |
| 44 | * ツリー：片方だけの変更はそのまま、両方が変えたファイルは行でマージする。 |
| 45 | * 削除と変更、ファイルとディレクトリ、バイナリ、シンボリックリンク等の両方の変更はコンフリクト。 |
| 46 | */ |
| 47 | final class Merge { |
| 48 | /** |
| 49 | * 行のマージ（行は改行を含む） |
| 50 | * |
| 51 | * @return array lines（コンフリクトはマーカー付き）、conflicts（コンフリクトの数） |
| 52 | */ |
| 53 | public static function lines(array $base, array $ours, array $theirs, string $ourName = 'ours', string $theirName = 'theirs'): array { |
| 54 | $changes = []; |
| 55 | foreach (self::changes($base, $ours) as $c) $changes[] = $c + [4 => 'o']; |
| 56 | foreach (self::changes($base, $theirs) as $c) $changes[] = $c + [4 => 't']; |
| 57 | usort($changes, fn($a, $b) => [$a[0], $a[1]] <=> [$b[0], $b[1]]); |
| 58 | $out = []; |
| 59 | $conflicts = 0; |
| 60 | $pos = 0; |
| 61 | $n = count($changes); |
| 62 | for ($i = 0; $i < $n;) { |
| 63 | // 重なる・隣り合う変更をまとめる |
| 64 | $group = [$changes[$i]]; |
| 65 | $start = $changes[$i][0]; |
| 66 | $end = $changes[$i][1]; |
| 67 | for ($i++; $i < $n && $changes[$i][0] <= $end; $i++) { |
| 68 | $group[] = $changes[$i]; |
| 69 | $end = max($end, $changes[$i][1]); |
| 70 | } |
| 71 | for ($k = $pos; $k < $start; $k++) $out[] = $base[$k]; |
| 72 | $o = array_values(array_filter($group, fn($c) => $c[4] === 'o')); |
| 73 | $t = array_values(array_filter($group, fn($c) => $c[4] === 't')); |
| 74 | if (empty($t)) { |
| 75 | array_push($out, ...self::region($o, $start, $end, $ours)); |
| 76 | } else if (empty($o)) { |
| 77 | array_push($out, ...self::region($t, $start, $end, $theirs)); |
| 78 | } else { |
| 79 | $a = self::region($o, $start, $end, $ours); |
| 80 | $b = self::region($t, $start, $end, $theirs); |
| 81 | if ($a === $b) { |
| 82 | array_push($out, ...$a); |
| 83 | } else { |
| 84 | $conflicts++; |
| 85 | $eol = fn(array $l) => $l !== [] && !str_ends_with((string)end($l), "\n") ? ["\n"] : []; |
| 86 | array_push($out, "<<<<<<< {$ourName}\n", ...$a, ...$eol($a)); |
| 87 | array_push($out, "=======\n", ...$b, ...$eol($b)); |
| 88 | $out[] = ">>>>>>> {$theirName}\n"; |
| 89 | } |
| 90 | } |
| 91 | $pos = $end; |
| 92 | } |
| 93 | for ($k = $pos; $k < count($base); $k++) $out[] = $base[$k]; |
| 94 | return ['lines' => $out, 'conflicts' => $conflicts]; |
| 95 | } |
| 96 | |
| 97 | /** 文字列を行に分ける（改行を含む） */ |
| 98 | public static function split(string $s): array { |
| 99 | return $s === '' ? [] : preg_split('/(?<=\n)/', $s, -1, PREG_SPLIT_NO_EMPTY); |
| 100 | } |
| 101 | |
| 102 | /** |
| 103 | * ファイルの内容のマージ |
| 104 | * |
| 105 | * @return string|null コンフリクトやバイナリならnull |
| 106 | */ |
| 107 | public static function text(string $base, string $ours, string $theirs): ?string { |
| 108 | if ($ours === $theirs) return $ours; |
| 109 | if ($base === $ours) return $theirs; |
| 110 | if ($base === $theirs) return $ours; |
| 111 | if (Diff::isBinary($base) || Diff::isBinary($ours) || Diff::isBinary($theirs)) return null; |
| 112 | if (strlen($base) + strlen($ours) + strlen($theirs) > 3 * Diff::MAX_BYTES) return null; |
| 113 | $r = self::lines(self::split($base), self::split($ours), self::split($theirs)); |
| 114 | return $r['conflicts'] === 0 ? implode('', $r['lines']) : null; |
| 115 | } |
| 116 | |
| 117 | /** |
| 118 | * ツリーのマージ |
| 119 | * |
| 120 | * @param string|null $base 共通の祖先のツリー（無ければnull） |
| 121 | * @return array tree（新しいツリーのID、コンフリクトが有ればnull）、conflicts（パスの配列） |
| 122 | */ |
| 123 | public static function trees(Repository $repo, ?string $base, string $ours, string $theirs): array { |
| 124 | $conflicts = []; |
| 125 | $tree = self::mergeTree($repo, $base, $ours, $theirs, '', $conflicts); |
| 126 | return ['tree' => empty($conflicts) ? ($tree ?? $repo->writeTree([])) : null, 'conflicts' => $conflicts]; |
| 127 | } |
| 128 | |
| 129 | /** |
| 130 | * コミットを他のコミットの上に当てる（cherry-pick） |
| 131 | * |
| 132 | * @return string|null 新しいツリー、コンフリクトならnull |
| 133 | */ |
| 134 | public static function pick(Repository $repo, string $commit, string $onto): ?string { |
| 135 | $c = $repo->commit($commit); |
| 136 | $parent = $c->parents[0] ?? null; |
| 137 | $r = self::trees($repo, $parent !== null ? $repo->commit($parent)->tree : null, $repo->commit($onto)->tree, $c->tree); |
| 138 | return $r['tree']; |
| 139 | } |
| 140 | |
| 141 | //////// 内部 |
| 142 | |
| 143 | /** 変更（[元の始め, 元の終わり, 新しい始め, 新しい終わり]、終わりは含まない） */ |
| 144 | private static function changes(array $a, array $b): array { |
| 145 | $out = []; |
| 146 | $pi = 0; |
| 147 | $pj = 0; |
| 148 | foreach (array_merge(Diff::match($a, $b), [[count($a), count($b)]]) as [$i, $j]) { |
| 149 | if ($i > $pi || $j > $pj) $out[] = [$pi, $i, $pj, $j]; |
| 150 | $pi = $i + 1; |
| 151 | $pj = $j + 1; |
| 152 | } |
| 153 | return $out; |
| 154 | } |
| 155 | |
| 156 | /** 元の[start, end)に当たる片方の行 */ |
| 157 | private static function region(array $changes, int $start, int $end, array $lines): array { |
| 158 | $first = $changes[0]; |
| 159 | $last = end($changes); |
| 160 | $from = $first[2] - ($first[0] - $start); |
| 161 | $to = $last[3] + ($end - $last[1]); |
| 162 | return array_slice($lines, $from, $to - $from); |
| 163 | } |
| 164 | |
| 165 | /** @return string|null 空ならnull */ |
| 166 | private static function mergeTree(Repository $repo, ?string $base, ?string $ours, ?string $theirs, string $prefix, array &$conflicts): ?string { |
| 167 | if ($ours === $theirs) return $ours; |
| 168 | if ($base === $ours) return $theirs; |
| 169 | if ($base === $theirs) return $ours; |
| 170 | $entries = fn(?string $t) => $t === null ? [] : array_column($repo->tree($t)->entries, null, 1); |
| 171 | $b = $entries($base); |
| 172 | $o = $entries($ours); |
| 173 | $t = $entries($theirs); |
| 174 | $out = []; |
| 175 | foreach (array_unique(array_merge(array_keys($b), array_keys($o), array_keys($t))) as $name) { |
| 176 | $name = (string)$name; |
| 177 | $be = $b[$name] ?? null; |
| 178 | $oe = $o[$name] ?? null; |
| 179 | $te = $t[$name] ?? null; |
| 180 | $path = $prefix.$name; |
| 181 | if ($oe === $te) $e = $oe; |
| 182 | else if ($be === $oe) $e = $te; |
| 183 | else if ($be === $te) $e = $oe; |
| 184 | else $e = self::mergeEntry($repo, $be, $oe, $te, $path, $conflicts); |
| 185 | if ($e !== null) $out[] = $e; |
| 186 | } |
| 187 | return empty($out) ? null : $repo->writeTree($out); |
| 188 | } |
| 189 | |
| 190 | /** 両方が変えたエントリー（[mode, name, id]又はnull） */ |
| 191 | private static function mergeEntry(Repository $repo, ?array $be, ?array $oe, ?array $te, string $path, array &$conflicts): ?array { |
| 192 | $isDir = fn(?array $e) => $e !== null && $e[0] === Tree::DIR; |
| 193 | $isFile = fn(?array $e) => $e !== null && ($e[0] === Tree::FILE || $e[0] === Tree::EXEC); |
| 194 | // 両方ディレクトリ |
| 195 | if ($isDir($oe) && $isDir($te)) { |
| 196 | $id = self::mergeTree($repo, $isDir($be) ? $be[2] : null, $oe[2], $te[2], $path.'/', $conflicts); |
| 197 | return $id === null ? null : [Tree::DIR, $oe[1], $id]; |
| 198 | } |
| 199 | // 両方普通のファイル（追加・追加も） |
| 200 | if ($isFile($oe) && $isFile($te) && ($be === null || $isFile($be))) { |
| 201 | $text = self::text($be !== null ? $repo->blob($be[2]) : '', $repo->blob($oe[2]), $repo->blob($te[2])); |
| 202 | if ($text === null) { |
| 203 | $conflicts[] = $path; |
| 204 | return $oe; |
| 205 | } |
| 206 | // 実行権限は変えた方 |
| 207 | $mode = $be !== null && $oe[0] === $be[0] ? $te[0] : $oe[0]; |
| 208 | if ($be === null && $oe[0] !== $te[0]) { |
| 209 | $conflicts[] = $path; |
| 210 | return $oe; |
| 211 | } |
| 212 | return [$mode, $oe[1], $repo->writeBlob($text)]; |
| 213 | } |
| 214 | // 削除と変更、種類の違い等 |
| 215 | $conflicts[] = $path; |
| 216 | return $oe ?? $te; |
| 217 | } |
| 218 | } |