<?php
/**
 * Tam Rank™ regex redirect guard
 *
 * Regex redirects run on template_redirect, so a pattern a user typed is
 * evaluated on requests. That makes an unchecked pattern two things at once: a
 * denial-of-service risk against the site's own visitors (catastrophic
 * backtracking), and a wp.org review risk.
 *
 * Everything a user types therefore passes through validate() BEFORE it is
 * stored, and compile() is the only place a stored pattern becomes a real PCRE:
 *
 *  1. Length limit. A pattern longer than MAX_LENGTH is refused.
 *  2. No delimiters, no modifiers. The user types the bare pattern; we add the
 *     delimiter ourselves at compile time and escape any delimiter character
 *     inside the pattern. A pattern that looks like "/foo/e" is refused with an
 *     explanation instead of being silently mangled — the `e` modifier can
 *     never reach preg_match() this way.
 *  3. Nested quantifiers. The classic catastrophic shapes — (a+)+, (a*)*,
 *     (a|a)+ and friends — are refused outright.
 *  4. Compile test. @preg_match() against a probe string; false means the
 *     pattern does not compile and it is refused.
 *  5. Backtracking probe. The compiled pattern is run against adversarial input
 *     under a deliberately low pcre.backtrack_limit. If PCRE gives up, the
 *     pattern is refused.
 *
 * And at request time, match() lowers pcre.backtrack_limit again, so anything
 * that still slipped through fails fast instead of hanging the page.
 *
 * @package TamRank
 */

if (!defined('ABSPATH')) {
    exit;
}

class TamRank_Redirect_Regex
{
    /** Delimiter we add ourselves. Never supplied by the user. */
    const DELIMITER = '#';

    /** Maximum pattern length, in characters. */
    const MAX_LENGTH = 200;

    /** Backtrack limit used for the save-time probe and for every live match. */
    const BACKTRACK_LIMIT = 100000;

    /**
     * Strings the save-time probe runs the pattern against.
     *
     * The long repeated runs are what make a catastrophically backtracking
     * pattern blow past the backtrack limit.
     */
    private static function probe_strings()
    {
        return array(
            '/tamrank-regex-probe',
            '/' . str_repeat('a', 60) . '!',
            '/' . str_repeat('ab', 40) . '!',
            '/' . str_repeat('1', 60) . 'x',
            '/' . str_repeat('a-', 40) . '/x',
        );
    }

    /**
     * Validate a raw, user-typed pattern.
     *
     * @param string $pattern Raw pattern as typed, without delimiters.
     * @return true|WP_Error true when the pattern is safe to store.
     */
    public static function validate($pattern)
    {
        $pattern = (string) $pattern;

        if (trim($pattern) === '') {
            return new WP_Error(
                'regex_empty',
                tamrank__('regex_error_empty', 'Enter a pattern.')
            );
        }

        // 1. Length.
        $length = function_exists('mb_strlen') ? mb_strlen($pattern) : strlen($pattern);
        if ($length > self::MAX_LENGTH) {
            return new WP_Error(
                'regex_too_long',
                sprintf(
                    /* translators: %d is the maximum number of characters allowed in a regex pattern. */
                    tamrank__('regex_error_too_long', 'This pattern is too long. Keep it under %d characters.'),
                    self::MAX_LENGTH
                )
            );
        }

        // Null bytes and newlines have no place in a URL pattern.
        if (strpbrk($pattern, "\0\r\n") !== false) {
            return new WP_Error(
                'regex_control_chars',
                tamrank__('regex_error_control_chars', 'This pattern contains characters that are not allowed.')
            );
        }

        // 2. Delimiters + modifiers. We add the delimiter ourselves, so a
        //    pattern that arrives wrapped in one is a misunderstanding at best
        //    and an attempt to append modifiers at worst.
        if (preg_match('#^\s*([/~!@%\#|])(.*)\1([a-zA-Z]*)\s*$#s', $pattern, $m)) {
            $delimiter = $m[1];
            $inside    = isset($m[2]) ? $m[2] : '';
            $modifiers = isset($m[3]) ? $m[3] : '';

            if (stripos($modifiers, 'e') !== false) {
                return new WP_Error(
                    'regex_e_modifier',
                    tamrank__('regex_error_e_modifier', 'The e modifier is not allowed: it would let the pattern run PHP code. Enter the pattern without slashes and without modifiers.')
                );
            }

            // A wrapped pattern *without* modifiers used to pass this check
            // silently and then compile to "#/^/blog/(.*)$/#i" — a pattern
            // that can never match a request path. The row looks fine in the
            // table and the redirect simply never fires.
            //
            // Refusing every start==end pair would be too blunt in the other
            // direction: "/foo/(.*)/" is an ordinary path pattern that just
            // happens to open and close with a slash, and refusing it costs a
            // real path its redirect. So only refuse on a real wrap signal:
            // a delimiter character that never bookends a URL path, or a
            // slash wrap whose inside is itself an anchored pattern.
            $is_wrap = $modifiers !== ''
                || $delimiter !== '/'
                || (isset($inside[0]) && $inside[0] === '^')
                || preg_match('/(?<!\\\\)\$$/', $inside);

            if ($is_wrap) {
                return new WP_Error(
                    'regex_modifiers',
                    tamrank__('regex_error_modifiers', 'Enter the pattern without slashes and without modifiers. TamRank adds those itself and always matches case-insensitively.')
                );
            }
        }

        // A bare "e" modifier attempt can also arrive without a closing
        // delimiter, e.g. "/foo/e" caught above, or "foo#e" — the delimiter
        // escaping in compile() neutralises those, but say so explicitly.
        if (preg_match('#[/~!@%\#|]e\s*$#', $pattern)) {
            return new WP_Error(
                'regex_e_modifier',
                tamrank__('regex_error_e_modifier', 'The e modifier is not allowed: it would let the pattern run PHP code. Enter the pattern without slashes and without modifiers.')
            );
        }

        // 3. Nested quantifiers — the catastrophic-backtracking classic.
        if (self::has_nested_quantifier($pattern)) {
            return new WP_Error(
                'regex_nested_quantifier',
                tamrank__('regex_error_nested_quantifier', 'This pattern has a repeat inside a repeat, such as (a+)+. On some URLs that can lock up your site, so it is refused. Rewrite it without the nested repeat.')
            );
        }

        // 4. Compile test.
        $compiled = self::compile($pattern);
        $probe    = self::probe_strings();

        // phpcs:ignore WordPress.PHP.NoSilencedErrors.Discouraged -- a malformed user pattern must be caught, not surfaced as a PHP warning.
        if (@preg_match($compiled, $probe[0]) === false) {
            return new WP_Error(
                'regex_invalid',
                tamrank__('regex_error_invalid', 'This is not a valid pattern. Check the brackets and the escaping.')
            );
        }

        // 5. Backtracking probe under a deliberately low limit.
        $previous = ini_get('pcre.backtrack_limit');
        // phpcs:ignore WordPress.PHP.IniSet.Risky, Squiz.PHP.DiscouragedFunctions.Discouraged -- deliberately lowering PCRE's backtrack budget so a hostile pattern fails here instead of on the front end; restored immediately below.
        @ini_set('pcre.backtrack_limit', (string) self::BACKTRACK_LIMIT);

        $blew_up = false;
        foreach ($probe as $subject) {
            // phpcs:ignore WordPress.PHP.NoSilencedErrors.Discouraged -- see above.
            @preg_match($compiled, $subject);
            if (preg_last_error() !== PREG_NO_ERROR) {
                $blew_up = true;
                break;
            }
        }

        if ($previous !== false) {
            // phpcs:ignore WordPress.PHP.IniSet.Risky, Squiz.PHP.DiscouragedFunctions.Discouraged -- restoring the value read a few lines up.
            @ini_set('pcre.backtrack_limit', (string) $previous);
        }

        if ($blew_up) {
            return new WP_Error(
                'regex_backtracking',
                tamrank__('regex_error_backtracking', 'This pattern needs far too many steps on a normal URL and would slow your site down. Make it more specific.')
            );
        }

        return true;
    }

    /**
     * Heuristic: does this pattern repeat something that already repeats?
     *
     * Catches (a+)+, (a*)*, (a+)*, (\d+)+, ([a-z]+)*, (a|a)+ and the {n,} forms.
     * Deliberately blunt: a false positive costs the user a rewrite, a false
     * negative can cost them their site.
     *
     * @param string $pattern
     * @return bool
     */
    public static function has_nested_quantifier($pattern)
    {
        $len   = strlen($pattern);
        $stack = array();

        for ($i = 0; $i < $len; $i++) {
            $ch = $pattern[$i];

            if ($ch === '\\') {
                $i++; // Skip the escaped character.
                continue;
            }

            if ($ch === '(') {
                $stack[] = $i;
                continue;
            }

            if ($ch === ')' && !empty($stack)) {
                $start = array_pop($stack);
                $body  = substr($pattern, $start + 1, $i - $start - 1);

                // Is this group itself quantified with an unbounded repeat?
                $after = substr($pattern, $i + 1);
                if (!preg_match('/^(?:[*+]|\{\s*\d*\s*,\s*\d*\s*\})/', $after)) {
                    continue;
                }

                // Does the body contain a repeat or an alternation of its own?
                if (self::body_repeats($body)) {
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * Does a group body itself contain an unbounded repeat or an alternation?
     *
     * @param string $body
     * @return bool
     */
    private static function body_repeats($body)
    {
        $len = strlen($body);
        for ($i = 0; $i < $len; $i++) {
            $ch = $body[$i];
            if ($ch === '\\') {
                $i++;
                continue;
            }
            if ($ch === '*' || $ch === '+' || $ch === '|') {
                return true;
            }
            if ($ch === '{' && preg_match('/^\{\s*\d*\s*,\s*\d*\s*\}/', substr($body, $i))) {
                return true;
            }
        }
        return false;
    }

    /**
     * Does a source that arrived as an *exact* match look like a regex?
     *
     * A pattern stored with match_type = exact is dead on arrival: the path
     * cleaner prefixes it with a slash ("^/blog/(.*)$" becomes "/^/blog/(.*)$"),
     * and no visitor ever requests that literal string. The row looks
     * plausible in the table, so the mistake surfaces only once the traffic is
     * already gone. This is what catches it at save time.
     *
     * Deliberately the mirror image of has_nested_quantifier(): there a false
     * positive costs a rewrite, here it costs a real path its redirect. So a
     * signal only counts when a literal URL path essentially never contains
     * it. A bare +, ?, *, a dot, a parenthesis or a $ inside the path are all
     * normal in real URLs and are not signals on their own.
     *
     * @param string $source Source as the user typed it, before path cleaning.
     * @return bool True when this is far more likely a pattern than a path.
     */
    public static function looks_like_pattern($source)
    {
        $source = trim((string) $source);

        if ($source === '') {
            return false;
        }

        // Strong signals: one is enough. None of these occur in a real path.
        $strong = array(
            '/^\^/',                       // anchored at the start: ^/blog/...
            '/(?<!\\\\)\.[*+]/',           // .* or .+
            '/\\\\[dDwWsSbB]/',            // \d \w \s \b character escapes
            '/\([^)]*\|[^)]*\)/',          // an alternation inside a group: (news|blog)
            '/\{\s*\d*\s*,\s*\d*\s*\}/',   // a counted quantifier: {2,} {1,3}
            '/[)\]]\s*[*+]/',              // a quantified group or class: (...)+ [...]*
            '/\(\?[:=!]/',                 // (?: (?= (?!
            // A character class with a range or an escape in it: [a-z] [0-9] [\d]
            '/\[\^?[^\]]*(?:[0-9A-Za-z]-[0-9A-Za-z]|\\\\[dDwWsS])[^\]]*\]/',
        );

        foreach ($strong as $signal) {
            if (preg_match($signal, $source)) {
                return true;
            }
        }

        // Weak signals: each one alone happens in real paths, two together
        // does not.
        $weak = 0;

        if (preg_match('/(?<!\\\\)\$$/', $source)) {
            $weak++; // anchored at the end
        }
        if (preg_match('/\(.*\)/', $source)) {
            $weak++; // a group
        }
        if (strpos($source, '\\') !== false) {
            $weak++; // a backslash is not a path character
        }
        if (strpos(substr($source, 1), '^') !== false) {
            $weak++; // a caret somewhere other than the start
        }

        return $weak >= 2;
    }

    /**
     * Turn a stored pattern into a real PCRE.
     *
     * The delimiter is ours, and every unescaped occurrence of it inside the
     * pattern is escaped, so a stored pattern can never close the delimiter and
     * append its own modifiers.
     *
     * @param string $pattern Stored pattern, without delimiters.
     * @return string Compiled PCRE.
     */
    public static function compile($pattern)
    {
        return self::DELIMITER . self::escape_delimiter((string) $pattern) . self::DELIMITER . 'i';
    }

    /**
     * Escape every unescaped delimiter character in a pattern.
     *
     * Done with a single pass rather than a regex, so the "is this backslash
     * itself escaped" case is obviously correct.
     *
     * @param string $pattern
     * @return string
     */
    public static function escape_delimiter($pattern)
    {
        $out = '';
        $len = strlen($pattern);

        for ($i = 0; $i < $len; $i++) {
            $ch = $pattern[$i];

            if ($ch === '\\' && $i + 1 < $len) {
                // Keep the escape sequence as-is, including "\\".
                $out .= $ch . $pattern[$i + 1];
                $i++;
                continue;
            }

            if ($ch === self::DELIMITER) {
                $out .= '\\' . self::DELIMITER;
                continue;
            }

            $out .= $ch;
        }

        return $out;
    }

    /**
     * Match a stored pattern against a request path, under a bounded backtrack budget.
     *
     * @param string $pattern Stored pattern, without delimiters.
     * @param string $subject Request path.
     * @return array|false Capture groups on a match, false on no match / any PCRE error.
     */
    public static function match($pattern, $subject)
    {
        $compiled = self::compile($pattern);

        $previous = ini_get('pcre.backtrack_limit');
        // phpcs:ignore WordPress.PHP.IniSet.Risky, Squiz.PHP.DiscouragedFunctions.Discouraged -- bounding PCRE's backtrack budget for a user-supplied pattern that runs on every request; restored below.
        @ini_set('pcre.backtrack_limit', (string) self::BACKTRACK_LIMIT);

        $matches = array();
        // phpcs:ignore WordPress.PHP.NoSilencedErrors.Discouraged -- a bad stored pattern must not surface as a PHP warning on the front end.
        $result = @preg_match($compiled, $subject, $matches);
        $error  = preg_last_error();

        if ($previous !== false) {
            // phpcs:ignore WordPress.PHP.IniSet.Risky, Squiz.PHP.DiscouragedFunctions.Discouraged -- restoring the value read a few lines up.
            @ini_set('pcre.backtrack_limit', (string) $previous);
        }

        if ($result !== 1 || $error !== PREG_NO_ERROR) {
            return false;
        }

        return $matches;
    }

    /**
     * Build one request path that this pattern would match.
     *
     * The save-time loop check needs a concrete example to reason about: a
     * target full of $1..$9 says nothing until something has been substituted
     * into it. This builds that example straight from the pattern.
     *
     * Deliberately timid. Every construct it does not fully understand — a
     * lookaround, a backreference, an escape that is not a plain character
     * class — makes it give up and return null, and a null means the caller
     * simply does not judge the rule. The result is also matched against the
     * real pattern before anything is concluded from it, so a sample that does
     * not actually match can never cost a user their redirect.
     *
     * @param string $pattern Stored pattern, without delimiters.
     * @return string|null A path the pattern matches, or null when none could be built.
     */
    public static function sample_subject($pattern)
    {
        $pattern = (string) $pattern;
        if ($pattern === '') {
            return null;
        }

        // Anchors carry no characters of their own.
        if ($pattern[0] === '^') {
            $pattern = substr($pattern, 1);
        }
        if (preg_match('/(?<!\\\\)\$$/', $pattern)) {
            $pattern = substr($pattern, 0, -1);
        }

        return self::sample_from($pattern);
    }

    /**
     * The sample builder. Walks the pattern piece by piece and recurses into
     * groups; returns null the moment it meets something it cannot represent.
     *
     * @param string $body Pattern body, without anchors.
     * @return string|null
     */
    private static function sample_from($body)
    {
        // An alternation offers several shapes; the first is representative.
        $branch = self::first_alternative($body);
        if ($branch === null) {
            return null;
        }

        $len = strlen($branch);
        $out = '';
        $i   = 0;

        while ($i < $len) {
            $ch    = $branch[$i];
            $piece = null;

            if ($ch === '\\') {
                if ($i + 1 >= $len) {
                    return null;
                }
                $piece = self::sample_escape($branch[$i + 1]);
                $i    += 2;
            } elseif ($ch === '(') {
                $close = self::matching_paren($branch, $i);
                if ($close === -1) {
                    return null;
                }
                $inner = substr($branch, $i + 1, $close - $i - 1);
                if (isset($inner[0]) && $inner[0] === '?') {
                    // Non-capturing is just a group; a lookaround is not a
                    // stretch of text at all and cannot be sampled.
                    if (strpos($inner, '?:') !== 0) {
                        return null;
                    }
                    $inner = substr($inner, 2);
                }
                $piece = self::sample_from($inner);
                $i     = $close + 1;
            } elseif ($ch === '[') {
                $close = self::closing_bracket($branch, $i);
                if ($close === -1) {
                    return null;
                }
                $piece = self::sample_class(substr($branch, $i + 1, $close - $i - 1));
                $i     = $close + 1;
            } elseif ($ch === '.') {
                $piece = 'a';
                $i++;
            } elseif (strpos('*+?{|)]^$', $ch) !== false) {
                // A quantifier with nothing in front of it, or a construct that
                // should have been consumed above. Do not guess.
                return null;
            } else {
                $piece = $ch;
                $i++;
            }

            if ($piece === null) {
                return null;
            }

            // The quantifier that may follow this piece. One repetition is the
            // most representative sample, so * and ? are treated as "once":
            // a capture that is empty says less about a loop than one with
            // something in it, and the verification pass catches it either way.
            $repeat = 1;
            if ($i < $len) {
                $q = $branch[$i];
                if ($q === '*' || $q === '?' || $q === '+') {
                    $i++;
                } elseif ($q === '{') {
                    $close = strpos($branch, '}', $i);
                    if ($close === false) {
                        return null;
                    }
                    $spec = substr($branch, $i + 1, $close - $i - 1);
                    if (!preg_match('/^\s*(\d*)\s*(?:,\s*\d*\s*)?$/', $spec, $m)) {
                        return null;
                    }
                    $repeat = ($m[1] === '') ? 1 : max(1, min(8, (int) $m[1]));
                    $i      = $close + 1;
                }
                // A lazy or possessive marker right after the quantifier.
                if ($i < $len && ($branch[$i] === '?' || $branch[$i] === '+')) {
                    $i++;
                }
            }

            $out .= str_repeat($piece, $repeat);
        }

        return $out;
    }

    /**
     * The first top-level alternative of a pattern body.
     *
     * @param string $body
     * @return string|null Null when the body opens with a '|' and there is
     *                     nothing to take.
     */
    private static function first_alternative($body)
    {
        $len   = strlen($body);
        $depth = 0;

        for ($i = 0; $i < $len; $i++) {
            $ch = $body[$i];

            if ($ch === '\\') {
                $i++;
                continue;
            }
            if ($ch === '[') {
                $close = self::closing_bracket($body, $i);
                if ($close === -1) {
                    return null;
                }
                $i = $close;
                continue;
            }
            if ($ch === '(') {
                $depth++;
                continue;
            }
            if ($ch === ')') {
                $depth--;
                continue;
            }
            if ($ch === '|' && $depth === 0) {
                return ($i === 0) ? null : substr($body, 0, $i);
            }
        }

        return $body;
    }

    /**
     * One character that satisfies an escape sequence.
     *
     * @param string $escaped The character after the backslash.
     * @return string|null Null for everything that is not a plain character.
     */
    private static function sample_escape($escaped)
    {
        $known = array(
            'd' => '5',
            'D' => 'a',
            'w' => 'a',
            'W' => '-',
            's' => ' ',
            'S' => 'a',
        );

        if (isset($known[$escaped])) {
            return $known[$escaped];
        }

        // An escaped metacharacter stands for itself. Anything else — \b, \A,
        // a backreference, \x41, \p{L} — is not a single literal character.
        if (strpos('.+*?()[]{}|/\\-^$#', $escaped) !== false) {
            return $escaped;
        }

        return null;
    }

    /**
     * One character that a character class accepts.
     *
     * Answered by asking PCRE itself rather than by parsing the class, so
     * ranges, negation and nested escapes all behave exactly as they will at
     * request time.
     *
     * @param string $inner Class body, without the surrounding brackets.
     * @return string|null Null when none of the candidates fit.
     */
    private static function sample_class($inner)
    {
        $class = self::DELIMITER . '^[' . self::escape_delimiter($inner) . ']$' . self::DELIMITER;

        foreach (array('a', 'b', '1', '2', 'x', 'z', '-', '_', '.', '/') as $candidate) {
            // phpcs:ignore WordPress.PHP.NoSilencedErrors.Discouraged -- a class we cannot compile is answered with null, not with a warning.
            if (@preg_match($class, $candidate) === 1) {
                return $candidate;
            }
        }

        return null;
    }

    /**
     * Index of the ')' that closes the '(' at $open.
     *
     * @param string $s
     * @param int    $open
     * @return int Index, or -1 when the group is never closed.
     */
    private static function matching_paren($s, $open)
    {
        $len   = strlen($s);
        $depth = 0;

        for ($i = $open; $i < $len; $i++) {
            $ch = $s[$i];

            if ($ch === '\\') {
                $i++;
                continue;
            }
            if ($ch === '[') {
                $close = self::closing_bracket($s, $i);
                if ($close === -1) {
                    return -1;
                }
                $i = $close;
                continue;
            }
            if ($ch === '(') {
                $depth++;
                continue;
            }
            if ($ch === ')') {
                $depth--;
                if ($depth === 0) {
                    return $i;
                }
            }
        }

        return -1;
    }

    /**
     * Index of the ']' that closes the '[' at $open.
     *
     * A ']' straight after the opening bracket (or after its negation caret)
     * is a literal, exactly as PCRE reads it.
     *
     * @param string $s
     * @param int    $open
     * @return int Index, or -1 when the class is never closed.
     */
    private static function closing_bracket($s, $open)
    {
        $len = strlen($s);
        $i   = $open + 1;

        if ($i < $len && $s[$i] === '^') {
            $i++;
        }
        if ($i < $len && $s[$i] === ']') {
            $i++;
        }

        for (; $i < $len; $i++) {
            if ($s[$i] === '\\') {
                $i++;
                continue;
            }
            if ($s[$i] === ']') {
                return $i;
            }
        }

        return -1;
    }

    /**
     * Substitute $1..$9 backreferences in a target URL.
     *
     * Each captured group is stripped of control characters first.
     *
     * A capture is NOT limited to the path: a target of "https://$1" makes the
     * substitution produce the host as well, which is exactly how the open
     * redirect got in. The rule that keeps that harmless lives in
     * handle_redirects(), which whitelists the host from the target as it was
     * CONFIGURED, from before this substitution, so wp_safe_redirect() refuses
     * a host the visitor supplied. Nothing here may be relied on to bound what
     * a capture can reach.
     *
     * @param string $target  Target URL, may contain $1..$9.
     * @param array  $matches Capture groups from match().
     * @return string
     */
    public static function apply_backreferences($target, $matches)
    {
        $target = (string) $target;
        if (strpos($target, '$') === false) {
            return $target;
        }

        $replacements = array();
        for ($i = 9; $i >= 1; $i--) {
            $value = isset($matches[$i]) ? (string) $matches[$i] : '';
            // Strip control characters and anything that could split the URL.
            $value = preg_replace('/[\x00-\x1F\x7F\s]+/u', '', $value);
            $replacements['$' . $i] = (string) $value;
        }

        return strtr($target, $replacements);
    }
}
