<?php
/**
 * Results aggregation.
 *
 * Reports per-variant impressions, conversions, conversion rate and
 * revenue, flags the leading variant by raw rate, and checks that the
 * traffic split is what was planned (a sample ratio mismatch means the
 * setup is broken, so a leader it shows cannot be trusted).
 *
 * @package ImproveAB
 */

defined( 'ABSPATH' ) || exit;

/**
 * Computes the figures shown on the results screen.
 */
class ImproveAB_Stats {

	/**
	 * This request's split map (split_map()), or null before it is read.
	 *
	 * @var array|null
	 */
	private static $split_memo = null;


	const MIN_VISITORS_PER_VARIANT = 100;

	/**
	 * The traffic split check looks only once this many visitors have been
	 * counted in total: below it, even a lopsided split is within chance.
	 */
	const SPLIT_MIN_VISITORS = 100;

	/**
	 * The split is off when a gap between the planned and the counted split
	 * this large happens by chance less than once in a thousand tests. It is
	 * decided on the exact p: a table of critical values rounded to three
	 * decimals drew the line a little to either side of p = 0.001, so a split
	 * could be called off while its own p read 0.00100002.
	 */
	const SPLIT_ALPHA = 0.001;

	/**
	 * The check covers up to ten versions (the plugin allows six).
	 */
	const SPLIT_MAX_DF = 9;

	/**
	 * Below this many expected visitors for some version the chance is
	 * worked out exactly instead of from the chi-square approximation, which
	 * can be far off there, the more so the smaller a version's share: a
	 * correct split could be called off far more often than once in a
	 * thousand looks. Above it the approximation errs by a few hundredths
	 * of the chance, and the exact sums would grow with the visitors.
	 */
	const SPLIT_EXACT_BELOW = 1000;

	/**
	 * Two outcomes this close in probability count as equally likely in the
	 * exact two-sided chance (one part in ten million, as R's binom.test).
	 */
	const SPLIT_TIE = 1e-7;

	/**
	 * Build the per-variant results and an overall verdict.
	 *
	 * @param array  $test       Hydrated test (with variants).
	 * @param array  $results    Map keyed by variant_key with impressions/conversions/revenue.
	 * @param string $segment    The device class $results cover, or '' for every
	 *                           device: the split check counts the same visitors.
	 * @return array
	 */
	public static function analyze( $test, $results, $segment = '' ) {
		$settings     = class_exists( 'ImproveAB_Settings' ) ? ImproveAB_Settings::get() : array();
		$min_visitors = isset( $settings['min_visitors'] ) ? (int) $settings['min_visitors'] : self::MIN_VISITORS_PER_VARIANT;

		$control_key = 'default';
		$variants    = array();
		$total_imp   = 0;
		$min_imp     = null;
		$total_rev   = 0.0;
		$best_key    = $control_key;
		$best_rate   = -1.0;

		foreach ( $test['variants'] as $v ) {
			$k   = $v['variant_key'];
			$row = self::row( $results, $k );
			$total_imp += $row['impressions'];
			$min_imp    = ( null === $min_imp ) ? $row['impressions'] : min( $min_imp, $row['impressions'] );
			$total_rev += $row['revenue'];

			$rate = $row['impressions'] > 0 ? ( $row['conversions'] / $row['impressions'] ) : 0.0;
			$rpv  = $row['impressions'] > 0 ? ( $row['revenue'] / $row['impressions'] ) : 0.0;

			$variants[] = array(
				'key'         => $k,
				'label'       => $v['label'],
				'impressions' => $row['impressions'],
				'conversions' => $row['conversions'],
				'revenue'     => round( $row['revenue'], 2 ),
				'rpv'         => round( $rpv, 2 ),
				'rate'        => self::percent( $row['conversions'], $row['impressions'] ),
				'is_control'  => ( $control_key === $k ),
				'uplift'      => null,
				'sufficient'  => false,
			);

			if ( $rate > $best_rate ) {
				$best_rate = $rate;
				$best_key  = $k;
			}
		}

		$counts = array();
		foreach ( $variants as $item ) {
			$counts[ $item['key'] ] = $item['impressions'];
		}
		// Once a started test's split check starts over, only the visitors
		// counted since are held to the split: the ones before were assigned
		// by the code that ran then. The figures above still count every
		// visitor.
		$since = ImproveAB_Tests::split_since( $test );
		if ( '' !== $since && ! empty( $test['id'] ) ) {
			$counts = ImproveAB_Tests::split_counts( (int) $test['id'], $since, $segment );
		}
		$split = self::split_check( $test, $counts, $since );
		$srm   = ( null !== $split && $split['off'] );

		// A split that is off comes first: the setup is broken, so the
		// numbers below it cannot say which version is better.
		// "Minimum visitors per variant": every variant must reach it, not the total.
		if ( $srm ) {
			$state = 'srm';
		} else {
			$state = ( null === $min_imp || $min_imp < $min_visitors ) ? 'collecting' : 'no_winner';
		}

		$analysis = array(
			'variants'   => $variants,
			'revenue'    => round( $total_rev, 2 ),
			'verdict'    => array(
				'state'  => $state,
				'winner' => '',
				'best'   => $best_key,
				'srm'    => $srm,
			),
			// The planned against the counted split, and the chance of a gap
			// this size (null below SPLIT_MIN_VISITORS). See split_check().
			'split'      => $split,
			'thresholds' => array(
				'min_visitors'    => $min_visitors,
			),
		);

		return $analysis;
	}

	/**
	 * The traffic split check (a sample ratio mismatch test): compares the
	 * visitors each version was counted with against the split the test
	 * planned, with a chi-square goodness of fit, or exactly where some
	 * version expects fewer than SPLIT_EXACT_BELOW visitors (see below).
	 * A gap this unlikely (p < 0.001) is not bad luck: a class on only
	 * one version, a cache or a redirect serving one version to everyone,
	 * or a version that breaks before it is counted. It runs for every
	 * test, because it needs only the visitor counts and a leader shown over a
	 * broken split misleads.
	 *
	 * @param array  $test   Test with its variants.
	 * @param array  $counts Map of variant_key => visitors counted.
	 * @param string $since  When the counts start, for a test whose split
	 *                       check started over (UTC); '' for every
	 *                       visitor.
	 * @return array|null Null when there are fewer than two variants or too
	 *                    few visitors to tell; else `off` (bool), `p` (the
	 *                    chance of a gap at least this large by chance),
	 *                    `chi`, `df`, `total`, `since` (the start of the
	 *                    counts, or null for every visitor) and `variants`:
	 *                    variant_key => { planned (share, 0 to 1), expected,
	 *                    seen, short }. `short` marks the one version
	 *                    furthest under its share when the split is off.
	 */
	public static function split_check( $test, $counts, $since = '' ) {
		$keys = array();
		foreach ( isset( $test['variants'] ) ? (array) $test['variants'] : array() as $v ) {
			if ( isset( $v['variant_key'] ) ) {
				$keys[] = (string) $v['variant_key'];
			}
		}
		$df = count( $keys ) - 1;
		if ( $df < 1 || $df > self::SPLIT_MAX_DF ) {
			return null;
		}

		$total = 0;
		foreach ( $keys as $k ) {
			$total += isset( $counts[ $k ] ) ? max( 0, (int) $counts[ $k ] ) : 0;
		}
		if ( $total < self::SPLIT_MIN_VISITORS ) {
			return null;
		}

		// Every version is planned the same share.
		$planned = array_fill_keys( $keys, 1 );
		$total_w = array_sum( $planned );
		if ( $total_w <= 0 ) {
			return null;
		}

		$chi      = 0.0;
		$rows     = array();
		$shortest = '';
		$lowest   = 0.0;
		$least    = null;
		$live     = array();
		foreach ( $keys as $k ) {
			$share    = $planned[ $k ] / $total_w;
			$expected = $total * $share;
			$seen     = isset( $counts[ $k ] ) ? max( 0, (int) $counts[ $k ] ) : 0;
			if ( $expected > 0 ) {
				$chi     += ( ( $seen - $expected ) * ( $seen - $expected ) ) / $expected;
				$residual = ( $seen - $expected ) / sqrt( $expected );
				if ( $residual < $lowest ) {
					$lowest   = $residual;
					$shortest = $k;
				}
				$least      = null === $least ? $expected : min( $least, $expected );
				$live[ $k ] = array( $share, $seen );
			}
			$rows[ $k ] = array(
				'planned'  => round( $share, 4 ),
				'expected' => (int) round( $expected ),
				'seen'     => $seen,
				'short'    => false,
			);
		}

		// The chance of a gap at least this large. The chi-square
		// approximation holds once every version expects SPLIT_EXACT_BELOW
		// visitors; below that it is exact: for two versions the two-sided
		// binomial chance, for more the smallest of each version's own
		// binomial chance times the number of versions (a bound that never
		// understates the chance, so a correct split is called off at most
		// once in a thousand looks, whatever its shares).
		if ( null !== $least && $least < self::SPLIT_EXACT_BELOW && count( $live ) >= 2 ) {
			if ( 2 === count( $live ) ) {
				$last = end( $live );
				$p    = self::binomial_p( $total, $last[0], $last[1] );
			} else {
				$p = 1.0;
				foreach ( $live as $one ) {
					$p = min( $p, self::binomial_p( $total, $one[0], $one[1] ) );
				}
				$p = min( 1.0, count( $live ) * $p );
			}
		} else {
			$p = self::chi_square_p( $chi, $df );
		}
		$off = ( $p < self::SPLIT_ALPHA );
		if ( $off && '' !== $shortest ) {
			$rows[ $shortest ]['short'] = true;
		}

		return array(
			'off'      => $off,
			'p'        => $p,
			'chi'      => round( $chi, 3 ),
			'df'       => $df,
			'total'    => $total,
			'since'    => '' !== (string) $since ? (string) $since : null,
			'variants' => $rows,
		);
	}

	/**
	 * The chance of a chi-square value at least this large by chance alone
	 * (the upper tail), exact for whole degrees of freedom: a finite series
	 * for even ones, the complementary error function plus a series for odd
	 * ones. It decides whether the split is off, so erfc() is the full
	 * precision one (within 1e-10 of the exact tail).
	 *
	 * @param float $chi Chi-square statistic.
	 * @param int   $df  Degrees of freedom (1 or more).
	 * @return float
	 */
	private static function chi_square_p( $chi, $df ) {
		if ( $chi <= 0 ) {
			return 1.0;
		}
		$half = $chi / 2;
		if ( 0 === $df % 2 ) {
			$term = 1.0;
			$sum  = 1.0;
			for ( $i = 1; $i < $df / 2; $i++ ) {
				$term *= $half / $i;
				$sum  += $term;
			}
			return max( 0.0, min( 1.0, exp( -$half ) * $sum ) );
		}
		$erfc = self::erfc( sqrt( $half ) );
		$sum  = 0.0;
		$term = sqrt( 2 * $chi / M_PI );
		for ( $i = 1; $i <= ( $df - 1 ) / 2; $i++ ) {
			$sum  += $term;
			$term *= $chi / ( 2 * $i + 1 );
		}
		return max( 0.0, min( 1.0, $erfc + exp( -$half ) * $sum ) );
	}

	/**
	 * The complementary error function for x >= 0, to about 1e-14 relative.
	 * Below x^2 = 1.5 (where erfc is still above 0.08) from the series
	 * erf(x) = 2x e^(-x^2) / sqrt(pi) * sum (2x^2)^n / (1 * 3 * ... * (2n + 1)),
	 * whose terms are all positive; above it from the continued fraction of
	 * the upper incomplete gamma Q(1/2, x^2) (modified Lentz), which keeps
	 * its relative precision far out in the tail. The rational approximation
	 * used before was off by up to 1.2e-7 relative.
	 *
	 * @param float $x Argument, 0 or more.
	 * @return float
	 */
	private static function erfc( $x ) {
		$y = $x * $x;
		if ( $y < 1.5 ) {
			$term = 1.0;
			$sum  = 1.0;
			for ( $n = 1; $n < 60 && $term > 1e-17 * $sum; $n++ ) {
				$term *= 2 * $y / ( 2 * $n + 1 );
				$sum  += $term;
			}
			return 1 - 2 / sqrt( M_PI ) * $x * exp( -$y ) * $sum;
		}
		$tiny = 1e-300;
		$b    = $y + 0.5;
		$c    = 1 / $tiny;
		$d    = 1 / $b;
		$h    = $d;
		for ( $i = 1; $i < 300; $i++ ) {
			$an  = -$i * ( $i - 0.5 );
			$b  += 2;
			$d   = $an * $d + $b;
			$d   = ( abs( $d ) < $tiny ) ? $tiny : $d;
			$c   = $b + $an / $c;
			$c   = ( abs( $c ) < $tiny ) ? $tiny : $c;
			$d   = 1 / $d;
			$del = $d * $c;
			$h  *= $del;
			if ( abs( $del - 1 ) < 1e-16 ) {
				break;
			}
		}
		return exp( -$y ) * $x / sqrt( M_PI ) * $h;
	}

	/**
	 * A count as a percentage of another, to two decimals, rounded half away
	 * from zero from the counts themselves: 100 * c / n is one correctly
	 * rounded division, so an exact half (23 / 160 = 14.375%) is a half and
	 * reads 14.38 here as in the chart, the CSV and both summaries. Rounding
	 * the product of the rate and 100 read 14.37 on PHP 8.4 and later, whose
	 * round() no longer pre-rounds.
	 *
	 * @param int $count Conversions.
	 * @param int $of    Visitors.
	 * @return float
	 */
	public static function percent( $count, $of ) {
		return $of > 0 ? round( 100 * (int) $count / (int) $of, 2 ) : 0.0;
	}

	/**
	 * The exact two-sided chance of a version's count under its planned
	 * share: the sum of every outcome at most as likely as the one seen
	 * (within SPLIT_TIE). Summed term by term outward from the most likely
	 * count, each term from the one before by its ratio, so no factorial is
	 * ever taken; terms past e^-60 of what they add to are dropped. Used only
	 * below SPLIT_EXACT_BELOW expected visitors, where the sum is short.
	 *
	 * @param int   $n     Visitors in all.
	 * @param float $share The version's planned share, above 0 and below 1.
	 * @param int   $x     The visitors the version was counted with.
	 * @return float
	 */
	private static function binomial_p( $n, $share, $x ) {
		$n = (int) $n;
		$x = max( 0, min( $n, (int) $x ) );
		if ( $share <= 0 ) {
			return $x > 0 ? 0.0 : 1.0;
		}
		if ( $share >= 1 ) {
			return $x < $n ? 0.0 : 1.0;
		}
		$odds = log( $share ) - log( 1 - $share );
		$mode = (int) floor( ( $n + 1 ) * $share );
		$mode = max( 0, min( $n, $mode ) );
		// Log-probabilities relative to the mode's: from the mode out to the
		// observed count first, so its own is known before the tails are summed.
		$step = static function ( $j, $up ) use ( $n, $odds ) {
			// log P(j + 1) - log P(j), or the reverse step down from j.
			return $up ? log( ( $n - $j ) / ( $j + 1 ) ) + $odds : -log( ( $n - $j + 1 ) / $j ) - $odds;
		};
		// Far enough out, no outcome as unlikely matters at a double's
		// precision: the chance is nothing. Every step away from the mode
		// only makes a count less likely, so the walk stops there: a badly
		// broken split of a million visitors put the count seen hundreds of
		// thousands of steps out, and walking all of them cost up to 120 ms
		// a check for the same 0.
		$lx = 0.0;
		if ( $x > $mode ) {
			for ( $j = $mode; $j < $x; $j++ ) {
				$lx += $step( $j, true );
				if ( $lx < -745 ) {
					return 0.0;
				}
			}
		} else {
			for ( $j = $mode; $j > $x; $j-- ) {
				$lx += $step( $j, false );
				if ( $lx < -745 ) {
					return 0.0;
				}
			}
		}
		$cut   = $lx + log( 1 + self::SPLIT_TIE );
		$total = 1.0;
		$tail  = ( 0.0 <= $cut ) ? 1.0 : 0.0;
		foreach ( array( true, false ) as $up ) {
			$l = 0.0;
			$j = $mode;
			while ( $up ? $j < $n : $j > 0 ) {
				$l     += $step( $j, $up );
				$j     += $up ? 1 : -1;
				$t      = exp( $l );
				$total += $t;
				if ( $l <= $cut ) {
					$tail += $t;
				}
				// Past the observed count on this side and far below both the
				// mode and the smallest term the tail holds: the rest adds
				// nothing.
				$past = $up ? $j > max( $mode, $x ) : $j < min( $mode, $x );
				if ( $past && $l < -60 && $l < $cut - 60 ) {
					break;
				}
			}
		}
		return max( 0.0, min( 1.0, $tail / $total ) );
	}

	/**
	 * Whether a running or paused test's traffic split is off: the "Split
	 * off" tag in the tests list, the admin-bar menu and the dashboard
	 * widget. Answered from one cached map of every such test (split_map()),
	 * so a list of any length costs nothing per test.
	 *
	 * @param array $test Test row (hydrated or from a list); only `id` is read.
	 * @return bool
	 */
	public static function split_off( $test ) {
		$id = ( is_array( $test ) && isset( $test['id'] ) ) ? (int) $test['id'] : 0;
		if ( $id <= 0 ) {
			return false;
		}
		$map = self::split_map();
		return ! empty( $map[ $id ] );
	}

	/**
	 * The ids of the running and paused tests whose split is off, as a map
	 * of id => true. Built from ImproveAB_Tests::live_split_counts() (three
	 * queries, and one more for each moment a split check restarted at) and
	 * cached for five minutes, or longer when that was slow:
	 * a broken split stays broken far longer than that, and a status change,
	 * a restarted split check or a deletion starts it again (the data generation,
	 * ImproveAB_Tests::flush_data()); a rename or a note leaves it. Tagged
	 * with that generation read before the counts, so a map read just before
	 * such a change and stored after it is never served, and with the build,
	 * so a map another build of the plugin stored is never served either.
	 *
	 * @return array
	 */
	private static function split_map() {
		if ( null !== self::$split_memo ) {
			return self::$split_memo;
		}
		$gen    = ImproveAB_Tests::data_gen() . '|' . IMPROVEAB_BUILD;
		$cached = wp_cache_get( 'split_map', ImproveAB_Tests::CACHE_GROUP );
		if ( false === $cached ) {
			$cached = get_transient( 'improveab_split_map' );
		}
		if ( is_array( $cached ) && isset( $cached['g'] ) && array_key_exists( 'v', $cached ) && is_array( $cached['v'] ) && $gen === $cached['g'] ) {
			self::$split_memo = $cached['v'];
			return $cached['v'];
		}

		$start = microtime( true );
		$live  = ImproveAB_Tests::live_split_counts();
		if ( null === $live ) {
			// A failed read is not cached for other requests (the next one
			// may well succeed), but it is for the rest of this one: a list
			// would otherwise repeat the failing scan once per test.
			self::$split_memo = array();
			return array();
		}
		$map = array();
		foreach ( $live as $id => $row ) {
			$check = self::split_check( $row['test'], $row['counts'] );
			if ( null !== $check && $check['off'] ) {
				$map[ (int) $id ] = true;
			}
		}

		$ttl = (int) min( 15 * MINUTE_IN_SECONDS, max( 5 * MINUTE_IN_SECONDS, ceil( ( microtime( true ) - $start ) * 120 ) ) );
		wp_cache_set( 'split_map', array( 'g' => $gen, 'v' => $map ), ImproveAB_Tests::CACHE_GROUP, $ttl );
		set_transient( 'improveab_split_map', array( 'g' => $gen, 'v' => $map ), $ttl );
		self::$split_memo = $map;
		return $map;
	}

	/**
	 * Forget this request's copy of the split map; ImproveAB_Tests::flush_cache()
	 * calls it beside clearing the stored one, so a write earlier in the same
	 * request is seen.
	 */
	public static function forget_split_map() {
		self::$split_memo = null;
	}

	/**
	 * Normalize a results row.
	 *
	 * @param array  $results Results map.
	 * @param string $key     Variant key.
	 * @return array
	 */
	private static function row( $results, $key ) {
		if ( isset( $results[ $key ] ) ) {
			return array(
				'impressions' => (int) $results[ $key ]['impressions'],
				'conversions' => (int) $results[ $key ]['conversions'],
				'revenue'     => (float) $results[ $key ]['revenue'],
			);
		}
		return array( 'impressions' => 0, 'conversions' => 0, 'revenue' => 0.0 );
	}
}