| 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 | * 差分（ツリーの変更、行の差分、git diffの形式） |
| 42 | */ |
| 43 | final class Diff { |
| 44 | /** これより大きいファイルは行の差分を出さない */ |
| 45 | public const MAX_BYTES = 2097152; |
| 46 | /** 編集距離の上限（超えたら全部の置き換えとする） */ |
| 47 | private const MAX_D = 3000; |
| 48 | |
| 49 | /** |
| 50 | * 2つのツリーの違い |
| 51 | * |
| 52 | * @param string|null $a 元のツリー（nullなら空） |
| 53 | * @param string|null $b 新しいツリー（nullなら空） |
| 54 | * @param bool $renames 同じ内容の削除と追加を名前の変更（R）にする |
| 55 | * @return array ['status' => A・D・M・T・R, 'old' => [mode, path, id]|null, 'new' => [mode, path, id]|null]（パスの順） |
| 56 | */ |
| 57 | public static function trees(Repository $repo, ?string $a, ?string $b, bool $renames = true): array { |
| 58 | $out = []; |
| 59 | self::walk($repo, $a, $b, '', $out); |
| 60 | if ($renames) { |
| 61 | $added = []; |
| 62 | foreach ($out as $i => $c) if ($c['status'] === 'A') $added[$c['new'][2]][] = $i; |
| 63 | foreach ($out as $i => $c) { |
| 64 | if ($c['status'] !== 'D' || empty($added[$c['old'][2]])) continue; |
| 65 | $j = array_shift($added[$c['old'][2]]); |
| 66 | $out[$j] = ['status' => 'R', 'old' => $c['old'], 'new' => $out[$j]['new']]; |
| 67 | unset($out[$i]); |
| 68 | } |
| 69 | } |
| 70 | $out = array_values($out); |
| 71 | usort($out, fn($x, $y) => strcmp(($x['new'] ?? $x['old'])[1], ($y['new'] ?? $y['old'])[1])); |
| 72 | return $out; |
| 73 | } |
| 74 | |
| 75 | private static function walk(Repository $repo, ?string $a, ?string $b, string $prefix, array &$out): void { |
| 76 | if ($a === $b) return; |
| 77 | $ea = []; |
| 78 | $eb = []; |
| 79 | foreach ($a !== null ? $repo->tree($a)->entries : [] as $e) $ea[$e[1]] = $e; |
| 80 | foreach ($b !== null ? $repo->tree($b)->entries : [] as $e) $eb[$e[1]] = $e; |
| 81 | $names = array_unique(array_merge(array_keys($ea), array_keys($eb))); |
| 82 | sort($names, SORT_STRING); |
| 83 | foreach ($names as $name) { |
| 84 | $x = $ea[$name] ?? null; |
| 85 | $y = $eb[$name] ?? null; |
| 86 | $path = $prefix.$name; |
| 87 | $xd = $x !== null && $x[0] === Tree::DIR; |
| 88 | $yd = $y !== null && $y[0] === Tree::DIR; |
| 89 | if ($xd || $yd) { |
| 90 | self::walk($repo, $xd ? $x[2] : null, $yd ? $y[2] : null, $path.'/', $out); |
| 91 | if ($x !== null && !$xd) $out[] = ['status' => 'D', 'old' => [$x[0], $path, $x[2]], 'new' => null]; |
| 92 | if ($y !== null && !$yd) $out[] = ['status' => 'A', 'old' => null, 'new' => [$y[0], $path, $y[2]]]; |
| 93 | continue; |
| 94 | } |
| 95 | if ($x === null) $out[] = ['status' => 'A', 'old' => null, 'new' => [$y[0], $path, $y[2]]]; |
| 96 | else if ($y === null) $out[] = ['status' => 'D', 'old' => [$x[0], $path, $x[2]], 'new' => null]; |
| 97 | else if ($x[2] !== $y[2] || $x[0] !== $y[0]) { |
| 98 | $type = fn($m) => $m === Tree::LINK ? 'l' : ($m === Tree::SUBMODULE ? 's' : 'f'); |
| 99 | $out[] = ['status' => $type($x[0]) === $type($y[0]) ? 'M' : 'T', 'old' => [$x[0], $path, $x[2]], 'new' => [$y[0], $path, $y[2]]]; |
| 100 | } |
| 101 | } |
| 102 | } |
| 103 | |
| 104 | /** バイナリか（最初の8000バイトにNULが有る） */ |
| 105 | public static function isBinary(string $s): bool { |
| 106 | return str_contains(substr($s, 0, 8000), "\0"); |
| 107 | } |
| 108 | |
| 109 | /** 行に分ける（改行は含まない） */ |
| 110 | public static function split(string $s): array { |
| 111 | if ($s === '') return []; |
| 112 | $lines = explode("\n", $s); |
| 113 | if (end($lines) === '') array_pop($lines); |
| 114 | return $lines; |
| 115 | } |
| 116 | |
| 117 | /** |
| 118 | * 行の対応（Myersのアルゴリズム） |
| 119 | * |
| 120 | * @return array [元の行の番号, 新しい行の番号]の配列（同じ行、0から） |
| 121 | */ |
| 122 | public static function match(array $a, array $b): array { |
| 123 | $n = count($a); |
| 124 | $m = count($b); |
| 125 | // 前と後ろの同じ部分 |
| 126 | $pre = 0; |
| 127 | while ($pre < $n && $pre < $m && $a[$pre] === $b[$pre]) $pre++; |
| 128 | $suf = 0; |
| 129 | while ($suf < $n - $pre && $suf < $m - $pre && $a[$n - 1 - $suf] === $b[$m - 1 - $suf]) $suf++; |
| 130 | $pairs = []; |
| 131 | for ($i = 0; $i < $pre; $i++) $pairs[] = [$i, $i]; |
| 132 | $A = array_slice($a, $pre, $n - $pre - $suf); |
| 133 | $B = array_slice($b, $pre, $m - $pre - $suf); |
| 134 | foreach (self::myers($A, $B) as [$i, $j]) $pairs[] = [$i + $pre, $j + $pre]; |
| 135 | for ($k = $suf; $k > 0; $k--) $pairs[] = [$n - $k, $m - $k]; |
| 136 | return $pairs; |
| 137 | } |
| 138 | |
| 139 | private static function myers(array $a, array $b): array { |
| 140 | if ($a === [] || $b === []) return []; |
| 141 | // 相手に無い行は必ず変更なので除く（xdiffと同じ）。行は番号にする |
| 142 | $ids = []; |
| 143 | $inB = []; |
| 144 | foreach ($b as $l) $inB[$l] = true; |
| 145 | $inA = []; |
| 146 | foreach ($a as $l) $inA[$l] = true; |
| 147 | $A = []; |
| 148 | $mapA = []; |
| 149 | foreach ($a as $i => $l) if (isset($inB[$l])) { |
| 150 | $A[] = $ids[$l] ??= count($ids); |
| 151 | $mapA[] = $i; |
| 152 | } |
| 153 | $B = []; |
| 154 | $mapB = []; |
| 155 | foreach ($b as $j => $l) if (isset($inA[$l])) { |
| 156 | $B[] = $ids[$l] ??= count($ids); |
| 157 | $mapB[] = $j; |
| 158 | } |
| 159 | $n = count($A); |
| 160 | $m = count($B); |
| 161 | if ($n === 0 || $m === 0) return []; |
| 162 | // 各ステップのVは詰めた文字列で持つ（メモリを節約） |
| 163 | $v = [1 => 0]; |
| 164 | $trace = []; |
| 165 | $found = false; |
| 166 | $limit = min($n + $m, self::MAX_D); |
| 167 | for ($d = 0; $d <= $limit; $d++) { |
| 168 | $trace[] = pack('N*', ...array_map(fn($k) => ($v[$k] ?? 0) + 1, range(-$d - 1, $d + 1))); |
| 169 | for ($k = -$d; $k <= $d; $k += 2) { |
| 170 | if ($k === -$d || ($k !== $d && ($v[$k - 1] ?? -1) < ($v[$k + 1] ?? -1))) $x = $v[$k + 1] ?? 0; |
| 171 | else $x = ($v[$k - 1] ?? 0) + 1; |
| 172 | $y = $x - $k; |
| 173 | while ($x < $n && $y < $m && $A[$x] === $B[$y]) { |
| 174 | $x++; |
| 175 | $y++; |
| 176 | } |
| 177 | $v[$k] = $x; |
| 178 | if ($x >= $n && $y >= $m) { |
| 179 | $found = true; |
| 180 | break 2; |
| 181 | } |
| 182 | } |
| 183 | } |
| 184 | if (!$found) return []; |
| 185 | $get = function(int $d, int $k) use (&$trace): int { |
| 186 | // k = -d-1 … d+1（0は「無い」） |
| 187 | $i = $k + $d + 1; |
| 188 | if ($i < 0 || $i > 2 * $d + 2) return -1; |
| 189 | return unpack('N', $trace[$d], $i * 4)[1] - 1; |
| 190 | }; |
| 191 | $pairs = []; |
| 192 | $x = $n; |
| 193 | $y = $m; |
| 194 | for ($d = count($trace) - 1; $d >= 0; $d--) { |
| 195 | $k = $x - $y; |
| 196 | $down = $k === -$d || ($k !== $d && $get($d, $k - 1) < $get($d, $k + 1)); |
| 197 | $pk = $down ? $k + 1 : $k - 1; |
| 198 | $px = max(0, $get($d, $pk)); |
| 199 | $py = $px - $pk; |
| 200 | while ($x > $px && $y > $py) { |
| 201 | $x--; |
| 202 | $y--; |
| 203 | $pairs[] = [$mapA[$x], $mapB[$y]]; |
| 204 | } |
| 205 | if ($d > 0) { |
| 206 | $x = $px; |
| 207 | $y = $py; |
| 208 | } |
| 209 | } |
| 210 | return array_reverse($pairs); |
| 211 | } |
| 212 | |
| 213 | /** |
| 214 | * 行の差分のハンク |
| 215 | * |
| 216 | * @return array ['oldStart', 'oldLines', 'newStart', 'newLines', 'lines' => [[' '|'-'|'+', 行]]]（番号は1から） |
| 217 | */ |
| 218 | public static function hunks(array $a, array $b, int $context = 3): array { |
| 219 | // 編集の列（' '、'-'、'+'） |
| 220 | $ops = []; |
| 221 | $i = 0; |
| 222 | $j = 0; |
| 223 | foreach (array_merge(self::match($a, $b), [[count($a), count($b)]]) as [$x, $y]) { |
| 224 | while ($i < $x) $ops[] = ['-', $i++, null]; |
| 225 | while ($j < $y) $ops[] = ['+', null, $j++]; |
| 226 | if ($x < count($a)) $ops[] = [' ', $i++, $j++]; |
| 227 | } |
| 228 | $hunks = []; |
| 229 | $n = count($ops); |
| 230 | $k = 0; |
| 231 | while ($k < $n) { |
| 232 | while ($k < $n && $ops[$k][0] === ' ') $k++; |
| 233 | if ($k >= $n) break; |
| 234 | $start = max(0, $k - $context); |
| 235 | // 変更の間の同じ行が2*context以下なら同じハンク |
| 236 | $end = $k; |
| 237 | while (true) { |
| 238 | while ($end < $n && $ops[$end][0] !== ' ') $end++; |
| 239 | $same = $end; |
| 240 | while ($same < $n && $ops[$same][0] === ' ') $same++; |
| 241 | if ($same < $n && $same - $end <= 2 * $context) { |
| 242 | $end = $same; |
| 243 | continue; |
| 244 | } |
| 245 | $end = min($n, $end + $context); |
| 246 | break; |
| 247 | } |
| 248 | $h = ['oldStart' => 0, 'oldLines' => 0, 'newStart' => 0, 'newLines' => 0, 'lines' => []]; |
| 249 | $oldStart = null; |
| 250 | $newStart = null; |
| 251 | for ($p = $start; $p < $end; $p++) { |
| 252 | [$op, $x, $y] = $ops[$p]; |
| 253 | if ($x !== null) { |
| 254 | $oldStart ??= $x; |
| 255 | $h['oldLines']++; |
| 256 | } |
| 257 | if ($y !== null) { |
| 258 | $newStart ??= $y; |
| 259 | $h['newLines']++; |
| 260 | } |
| 261 | $h['lines'][] = [$op, $op === '+' ? $b[$y] : $a[$x]]; |
| 262 | } |
| 263 | // 行が無い側の番号はgitと同じ（直前の行） |
| 264 | $h['oldStart'] = $oldStart !== null ? $oldStart + 1 : self::before($ops, $start, 1); |
| 265 | $h['newStart'] = $newStart !== null ? $newStart + 1 : self::before($ops, $start, 2); |
| 266 | $hunks[] = $h; |
| 267 | $k = $end; |
| 268 | } |
| 269 | return $hunks; |
| 270 | } |
| 271 | |
| 272 | private static function before(array $ops, int $pos, int $side): int { |
| 273 | for ($p = $pos - 1; $p >= 0; $p--) if ($ops[$p][$side] !== null) return $ops[$p][$side] + 1; |
| 274 | return 0; |
| 275 | } |
| 276 | |
| 277 | /** |
| 278 | * git diffの形式 |
| 279 | * |
| 280 | * @param string|null $a 元のコミット・ツリー（nullなら空） |
| 281 | * @param string|null $b 新しいコミット・ツリー |
| 282 | */ |
| 283 | public static function unified(Repository $repo, ?string $a, ?string $b, int $context = 3, bool $quotePath = true): string { |
| 284 | $q = fn(string $prefix, string $path) => self::quote($prefix.$path, $quotePath); |
| 285 | $ta = $a === null ? null : $repo->treeOf($a); |
| 286 | $tb = $b === null ? null : $repo->treeOf($b); |
| 287 | $out = ''; |
| 288 | $short = fn(?string $id) => substr($id ?? $repo->zeroId(), 0, 7); |
| 289 | foreach (self::trees($repo, $ta, $tb) as $c) { |
| 290 | [$om, $op, $oid] = $c['old'] ?? [null, null, null]; |
| 291 | [$nm, $np, $nid] = $c['new'] ?? [null, null, null]; |
| 292 | $pa = $op ?? $np; |
| 293 | $pb = $np ?? $op; |
| 294 | $out .= 'diff --git '.$q('a/', $pa).' '.$q('b/', $pb)."\n"; |
| 295 | if ($c['status'] === 'A') $out .= "new file mode {$nm}\n"; |
| 296 | if ($c['status'] === 'D') $out .= "deleted file mode {$om}\n"; |
| 297 | if ($c['status'] === 'T' || ($c['status'] === 'M' && $om !== $nm)) $out .= "old mode {$om}\nnew mode {$nm}\n"; |
| 298 | if ($c['status'] === 'R') $out .= "similarity index 100%\nrename from ".self::quote($op, $quotePath)."\nrename to ".self::quote($np, $quotePath)."\n"; |
| 299 | if ($c['status'] === 'R' || $oid === $nid) continue; |
| 300 | $out .= 'index '.$short($oid).'..'.$short($nid).($c['status'] === 'M' && $om === $nm ? " {$nm}" : '')."\n"; |
| 301 | $old = $oid !== null && $om !== Tree::SUBMODULE ? $repo->blob($oid) : ($om === Tree::SUBMODULE ? "Subproject commit {$oid}\n" : ''); |
| 302 | $new = $nid !== null && $nm !== Tree::SUBMODULE ? $repo->blob($nid) : ($nm === Tree::SUBMODULE ? "Subproject commit {$nid}\n" : ''); |
| 303 | if (self::isBinary($old) || self::isBinary($new)) { |
| 304 | $out .= 'Binary files '.($oid !== null ? $q('a/', $pa) : '/dev/null').' and '.($nid !== null ? $q('b/', $pb) : '/dev/null')." differ\n"; |
| 305 | continue; |
| 306 | } |
| 307 | $out .= '--- '.($oid !== null ? $q('a/', $pa) : '/dev/null')."\n".'+++ '.($nid !== null ? $q('b/', $pb) : '/dev/null')."\n"; |
| 308 | $out .= self::format($old, $new, $context); |
| 309 | } |
| 310 | return $out; |
| 311 | } |
| 312 | |
| 313 | /** |
| 314 | * パスの引用（gitのcore.quotePath。制御文字・「"」・「\」と、$nonAsciiならASCII以外を8進数に） |
| 315 | */ |
| 316 | public static function quote(string $path, bool $nonAscii = true): string { |
| 317 | if (!preg_match($nonAscii ? '/[\x00-\x1f"\\\\\x7f-\xff]/' : '/[\x00-\x1f"\\\\\x7f]/', $path)) return $path; |
| 318 | $out = '"'; |
| 319 | $map = ["\x07" => '\a', "\x08" => '\b', "\t" => '\t', "\n" => '\n', "\x0b" => '\v', "\x0c" => '\f', "\r" => '\r', '"' => '\"', '\\' => '\\\\']; |
| 320 | for ($i = 0, $n = strlen($path); $i < $n; $i++) { |
| 321 | $c = $path[$i]; |
| 322 | $o = ord($c); |
| 323 | if (isset($map[$c])) $out .= $map[$c]; |
| 324 | else if ($o < 0x20 || $o === 0x7f || ($nonAscii && $o >= 0x80)) $out .= sprintf('\\%03o', $o); |
| 325 | else $out .= $c; |
| 326 | } |
| 327 | return $out.'"'; |
| 328 | } |
| 329 | |
| 330 | /** 2つの文字列の差分（「@@」から） */ |
| 331 | public static function format(string $old, string $new, int $context = 3): string { |
| 332 | $a = self::split($old); |
| 333 | $b = self::split($new); |
| 334 | $noNlA = $old !== '' && !str_ends_with($old, "\n"); |
| 335 | $noNlB = $new !== '' && !str_ends_with($new, "\n"); |
| 336 | // 最後の行の改行の有無が違えば別の行 |
| 337 | if ($noNlA && $noNlB === false && $a !== []) $a[count($a) - 1] .= "\0"; |
| 338 | if ($noNlB && $noNlA === false && $b !== []) $b[count($b) - 1] .= "\0"; |
| 339 | $out = ''; |
| 340 | foreach (self::hunks($a, $b, $context) as $h) { |
| 341 | $range = fn($s, $l) => $l === 1 ? "{$s}" : "{$s},{$l}"; |
| 342 | // 関数の名前（gitの既定：英字・「_」・「$」で始まる前の行） |
| 343 | $func = ''; |
| 344 | for ($p = $h['oldStart'] - 2; $p >= 0; $p--) { |
| 345 | if (preg_match('/^[A-Za-z_$]/', $a[$p])) { |
| 346 | $func = ' '.rtrim(substr(rtrim($a[$p], "\0"), 0, 80)); |
| 347 | break; |
| 348 | } |
| 349 | } |
| 350 | $out .= '@@ -'.$range($h['oldStart'], $h['oldLines']).' +'.$range($h['newStart'], $h['newLines'])." @@{$func}\n"; |
| 351 | $ia = 0; |
| 352 | $ib = 0; |
| 353 | foreach ($h['lines'] as [$op, $line]) { |
| 354 | $out .= $op.rtrim($line, "\0")."\n"; |
| 355 | $lastA = $op !== '+' && $h['oldStart'] - 1 + $ia++ === count($a) - 1; |
| 356 | $lastB = $op !== '-' && $h['newStart'] - 1 + $ib++ === count($b) - 1; |
| 357 | if (($op === '-' && $lastA && $noNlA) || ($op === '+' && $lastB && $noNlB) || ($op === ' ' && (($lastA && $noNlA) || ($lastB && $noNlB)))) { |
| 358 | $out .= "\\ No newline at end of file\n"; |
| 359 | } |
| 360 | } |
| 361 | } |
| 362 | return $out; |
| 363 | } |
| 364 | } |