<?php
/**
 * The ledger of deletions the plugin itself made.
 *
 * @package ActivityLog404
 */

namespace ActivityLog404\Chain;

defined( 'ABSPATH' ) || exit;

/**
 * Retention and the archive's prune delete rows on purpose, and a chain that
 * called every deletion tampering would be useless the day after its first
 * purge. So each deletion the plugin makes is recorded, before the DELETE
 * runs, as a cut: the chain hash of the row that stood just before the run
 * (`from`) and the chain hash of the last row removed (`to`). The row after
 * the run carries `to` as its `chain_prev`, so a verifier that finds a link
 * not matching its predecessor asks whether a recorded cut bridges exactly
 * that gap. A deletion nobody recorded bridges nothing and is reported.
 *
 * A cut can only be written by whoever holds the key (the list is signed as
 * a whole), so deleting rows by hand and then "recording" the deletion
 * is not available to a database-only attacker.
 *
 * Adjacent cuts merge (the second run starts where the first ended), so the
 * ordinary case, a daily purge off the front of the log, stays ONE cut for
 * the life of the site. Scattered cuts (the archive pruning a month out of
 * the middle) each add an entry up to LIMIT; past it the oldest entry is
 * dropped, and the verifier would report the gap it once bridged. That takes
 * a thousand separate mid-log deletions (docs/tamper-evident-chain.md).
 */
final class Cuts {

	/** Most cuts kept. */
	public const LIMIT = 1000;

	/**
	 * Add a cut, merging with whatever it touches.
	 *
	 * @param array<int, array{from: string, to: string}> $cuts Existing cuts.
	 * @param string                                      $from Chain hash of the row before the removed run.
	 * @param string                                      $to   Chain hash of the last removed row.
	 * @return array<int, array{from: string, to: string}>
	 */
	public static function add( array $cuts, string $from, string $to ): array {
		$cuts[] = array(
			'from' => $from,
			'to'   => $to,
		);

		// Merge until nothing joins: a new cut can bridge two older ones.
		do {
			$merged = false;
			$count  = count( $cuts );

			for ( $i = 0; $i < $count && ! $merged; $i++ ) {
				for ( $j = 0; $j < $count; $j++ ) {
					if ( $i === $j || $cuts[ $i ]['to'] !== $cuts[ $j ]['from'] ) {
						continue;
					}

					// $i ends where $j begins: one run.
					$cuts[ $i ]['to'] = $cuts[ $j ]['to'];
					unset( $cuts[ $j ] );
					$cuts   = array_values( $cuts );
					$merged = true;
					break;
				}
			}
		} while ( $merged );

		if ( count( $cuts ) > self::LIMIT ) {
			$cuts = array_slice( $cuts, -self::LIMIT );
		}

		return $cuts;
	}

	/**
	 * Every chain hash a gap after `$from` may legitimately end at: `$from`
	 * itself and everything a chain of recorded cuts leads to.
	 *
	 * @param array<int, array{from: string, to: string}> $cuts Recorded cuts.
	 * @param string                                      $from The hash of the surviving row before the gap.
	 * @return array<string, true> Hash => true.
	 */
	public static function reachable( array $cuts, string $from ): array {
		$seen  = array( $from => true );
		$queue = array( $from );

		while ( array() !== $queue ) {
			$at = array_pop( $queue );

			foreach ( $cuts as $cut ) {
				if ( $cut['from'] === $at && ! isset( $seen[ $cut['to'] ] ) ) {
					$seen[ $cut['to'] ] = true;
					$queue[]            = $cut['to'];
				}
			}
		}

		return $seen;
	}

	/**
	 * The runs a deletion removes, from the rows it removes.
	 *
	 * Two consecutive removed rows are one run exactly when the second's
	 * `chain_prev` is the first's `chain_hash`: if a surviving row stood
	 * between them the link would name that row instead. So the runs can be
	 * read off the doomed rows alone, in id order, without looking at the
	 * rows that stay.
	 *
	 * @param array<int, array{prev: string, hash: string}> $doomed Sealed rows being removed, id ascending.
	 * @return array<int, array{from: string, to: string}>
	 */
	public static function runs( array $doomed ): array {
		$runs = array();
		$open = null;

		foreach ( $doomed as $row ) {
			$open = self::feed( $open, $runs, $row['prev'], $row['hash'] );
		}

		if ( null !== $open ) {
			$runs[] = $open;
		}

		return $runs;
	}

	/**
	 * One removed row, fed to a stream of them: extends the open run when it
	 * continues it, otherwise closes the run into `$runs` and opens a new
	 * one. The caller closes the last open run itself. Exists so a purge of
	 * a million rows is read in batches without holding them all.
	 *
	 * @param array{from: string, to: string}|null          $open  The open run.
	 * @param array<int, array{from: string, to: string}>   $runs  Closed runs, appended to.
	 * @param string                                        $prev  The row's chain_prev.
	 * @param string                                        $hash  The row's chain_hash.
	 * @return array{from: string, to: string} The open run.
	 */
	public static function feed( ?array $open, array &$runs, string $prev, string $hash ): array {
		if ( null !== $open && $prev === $open['to'] ) {
			$open['to'] = $hash;
			return $open;
		}

		if ( null !== $open ) {
			$runs[] = $open;
		}

		return array(
			'from' => $prev,
			'to'   => $hash,
		);
	}

	/**
	 * A canonical string of a cut list, for signing.
	 *
	 * @param int                                         $floor Rows at or below this id are before the current chain.
	 * @param array<int, array{from: string, to: string}> $cuts  Cuts.
	 */
	public static function canonical( int $floor, array $cuts ): string {
		$out = 'floor=' . $floor;
		foreach ( $cuts as $cut ) {
			$out .= ';' . $cut['from'] . '>' . $cut['to'];
		}
		return $out;
	}
}