<?php
/**
 * Bounded PHP data-flow analysis.
 *
 * @package LocalGuardScanner
 */

namespace LocalGuardScanner\Detection\Php;

/**
 * Proves a small set of dangerous flows without executing inspected code.
 */
final class PhpDataFlowAnalyzer {
	const TAG_REQUEST   = 1;
	const TAG_DECODED   = 2;
	const MAX_VARIABLES = 2048;

	/**
	 * @param string $content PHP source.
	 * @return array{decoder_execution:bool,request_controlled_path:bool,request_executable_write:bool,request_write:bool}
	 */
	public function analyze( $content ) {
		$result = array(
			'decoder_execution'        => false,
			'request_controlled_path'  => false,
			'request_executable_write' => false,
			'request_write'            => false,
		);
		if ( ! PhpSource::has_open_tag( $content ) ) {
			return $result;
		}
		$tokens = token_get_all( $content );
		foreach ( $this->split_scopes( $tokens ) as $scope ) {
			$scope_result                       = $this->analyze_scope( $scope );
			$result['decoder_execution']        = $result['decoder_execution'] || $scope_result['decoder_execution'];
			$result['request_controlled_path']  = $result['request_controlled_path'] || $scope_result['request_controlled_path'];
			$result['request_executable_write'] = $result['request_executable_write'] || $scope_result['request_executable_write'];
			$result['request_write']            = $result['request_controlled_path'] || $result['request_executable_write'];
		}
		return $result;
	}

	/**
	 * @param array<int,mixed> $tokens Raw PHP tokens.
	 * @return array<int,array<int,mixed>>
	 */
	private function split_scopes( array $tokens ) {
		$current  = array();
		$children = array();
		$count    = count( $tokens );
		for ( $index = 0; $index < $count; ++$index ) {
			$token = $tokens[ $index ];
			if ( ! is_array( $token ) || T_FUNCTION !== $token[0] ) {
				$current[] = $token;
				continue;
			}
			$open = $this->find_text( $tokens, $index + 1, '{' );
			if ( null === $open ) {
				$current[] = $token;
				continue;
			}
			$close = $this->matching_delimiter( $tokens, $open, '{', '}' );
			if ( null === $close ) {
				$current[] = $token;
				continue;
			}
			$body     = array_slice( $tokens, $open + 1, $close - $open - 1 );
			$children = array_merge( $children, $this->split_scopes( $body ) );
			$index    = $close;
		}
		array_unshift( $children, $current );
		return $children;
	}

	/**
	 * @param array<int,mixed> $raw_tokens Scope tokens.
	 * @return array{decoder_execution:bool,request_controlled_path:bool,request_executable_write:bool,request_write:bool}
	 */
	private function analyze_scope( array $raw_tokens ) {
		$tokens    = $this->compact( $raw_tokens );
		$variables = array();
		$paths     = array();
		$handles   = array();
		$result    = array(
			'decoder_execution'        => false,
			'request_controlled_path'  => false,
			'request_executable_write' => false,
			'request_write'            => false,
		);
		$count     = count( $tokens );
		for ( $index = 0; $index < $count; ++$index ) {
			$token = $tokens[ $index ];
			if ( $this->is_id( $token, T_VARIABLE ) ) {
				$assignment = $this->assignment_at( $tokens, $index );
				if ( null !== $assignment ) {
					$expression = array_slice( $tokens, $assignment['expression_start'], $assignment['expression_end'] - $assignment['expression_start'] );
					$name       = $this->variable_name( $token );
					$tags       = $this->expression_tags( $expression, $variables );
					if ( $assignment['element'] ) {
						$variables[ $name ] = isset( $variables[ $name ] ) ? $variables[ $name ] | $tags : $tags;
					} else {
						$variables[ $name ] = $tags;
					}
					$paths[ $name ] = $this->path_info( $expression, $variables, $paths );
					$call_name      = $this->expression_call_name( $expression );
					if ( 'fopen' === $call_name ) {
						$arguments = $this->call_arguments_from_expression( $expression );
						if ( isset( $arguments[0] ) ) {
							$handles[ $name ] = $this->path_info( $arguments[0], $variables, $paths );
						}
					} else {
						unset( $handles[ $name ] );
					}
					if ( count( $variables ) > self::MAX_VARIABLES ) {
						break;
					}
				}
			}

			if ( $this->is_id( $token, T_EVAL ) || $this->is_id( $token, T_INCLUDE ) || $this->is_id( $token, T_INCLUDE_ONCE ) || $this->is_id( $token, T_REQUIRE ) || $this->is_id( $token, T_REQUIRE_ONCE ) ) {
				$expression = $this->language_construct_expression( $tokens, $index + 1 );
				if ( self::TAG_DECODED & $this->expression_tags( $expression, $variables ) ) {
					$result['decoder_execution'] = true;
				}
			}

			if ( ! $this->is_id( $token, T_STRING ) || ! isset( $tokens[ $index + 1 ] ) || '(' !== $this->text( $tokens[ $index + 1 ] ) || $this->is_method_call( $tokens, $index ) ) {
				continue;
			}
			$name      = strtolower( $token[1] );
			$arguments = $this->call_arguments( $tokens, $index + 1 );
			if ( 'file_put_contents' === $name && isset( $arguments[0], $arguments[1] ) ) {
				$path      = $this->path_info( $arguments[0], $variables, $paths );
				$data_tags = $this->expression_tags( $arguments[1], $variables );
				if ( $path['request'] ) {
					$result['request_controlled_path'] = true;
				}
				if ( true === $path['executable'] && ( self::TAG_REQUEST & $data_tags ) ) {
					$result['request_executable_write'] = true;
				}
			} elseif ( 'fopen' === $name && isset( $arguments[0] ) ) {
				$path = $this->path_info( $arguments[0], $variables, $paths );
				if ( $path['request'] ) {
					$result['request_controlled_path'] = true;
				}
			} elseif ( 'move_uploaded_file' === $name && isset( $arguments[0], $arguments[1] ) ) {
				$source_tags = $this->expression_tags( $arguments[0], $variables );
				$path        = $this->path_info( $arguments[1], $variables, $paths );
				if ( self::TAG_REQUEST & $source_tags ) {
					if ( $path['request'] ) {
						$result['request_controlled_path'] = true;
					}
					if ( false !== $path['executable'] ) {
						$result['request_executable_write'] = true;
					}
				}
			} elseif ( 'fwrite' === $name && isset( $arguments[0], $arguments[1] ) ) {
				$handle_name = $this->single_variable_name( $arguments[0] );
				$handle      = null !== $handle_name && isset( $handles[ $handle_name ] ) ? $handles[ $handle_name ] : array(
					'request'    => false,
					'executable' => null,
				);
				$data_tags   = $this->expression_tags( $arguments[1], $variables );
				if ( $handle['request'] ) {
					$result['request_controlled_path'] = true;
				}
				if ( true === $handle['executable'] && ( self::TAG_REQUEST & $data_tags ) ) {
					$result['request_executable_write'] = true;
				}
			}
		}
		$result['request_write'] = $result['request_controlled_path'] || $result['request_executable_write'];
		return $result;
	}

	/**
	 * @param array<int,mixed> $tokens Tokens.
	 * @param int              $index Variable position.
	 * @return array{element:bool,expression_start:int,expression_end:int}|null
	 */
	private function assignment_at( array $tokens, $index ) {
		$cursor  = $index + 1;
		$element = false;
		$count   = count( $tokens );
		while ( $cursor < $count && '[' === $this->text( $tokens[ $cursor ] ) ) {
			$close = $this->matching_delimiter( $tokens, $cursor, '[', ']' );
			if ( null === $close ) {
				return null;
			}
			$element = true;
			$cursor  = $close + 1;
		}
		if ( ! isset( $tokens[ $cursor ] ) || '=' !== $this->text( $tokens[ $cursor ] ) ) {
			return null;
		}
		$end = $this->expression_end( $tokens, $cursor + 1 );
		return array(
			'element'          => $element,
			'expression_start' => $cursor + 1,
			'expression_end'   => $end,
		);
	}

	/**
	 * @param array<int,mixed>  $expression Expression tokens.
	 * @param array<string,int> $variables Variable tags.
	 * @return int
	 */
	private function expression_tags( array $expression, array $variables ) {
		$tags  = 0;
		$count = count( $expression );
		for ( $index = 0; $index < $count; ++$index ) {
			$token = $expression[ $index ];
			if ( $this->is_id( $token, T_VARIABLE ) ) {
				$name = $this->variable_name( $token );
				if ( in_array( $name, array( '_GET', '_POST', '_REQUEST', '_COOKIE', '_FILES' ), true ) ) {
					$tags |= self::TAG_REQUEST;
				} elseif ( isset( $variables[ $name ] ) ) {
					$tags |= $variables[ $name ];
				}
			}
			if ( $this->is_id( $token, T_STRING ) && isset( $expression[ $index + 1 ] ) && '(' === $this->text( $expression[ $index + 1 ] ) && in_array( strtolower( $token[1] ), array( 'base64_decode', 'gzinflate', 'gzuncompress', 'str_rot13' ), true ) ) {
				$tags |= self::TAG_DECODED;
			}
		}
		return $tags;
	}

	/**
	 * @param array<int,mixed>                    $expression Expression tokens.
	 * @param array<string,int>                   $variables Variable tags.
	 * @param array<string,array<string,mixed>>   $paths Known variable paths.
	 * @return array{request:bool,executable:bool|null}
	 */
	private function path_info( array $expression, array $variables, array $paths ) {
		$tags       = $this->expression_tags( $expression, $variables );
		$executable = null;
		for ( $index = count( $expression ) - 1; $index >= 0; --$index ) {
			$token = $expression[ $index ];
			if ( $this->is_id( $token, T_CONSTANT_ENCAPSED_STRING ) ) {
				$value      = $this->string_literal( $token[1] );
				$executable = $this->literal_executable_status( $value );
				break;
			}
			if ( $this->is_id( $token, T_VARIABLE ) ) {
				$name = $this->variable_name( $token );
				if ( isset( $paths[ $name ] ) ) {
					$executable = $paths[ $name ]['executable'];
				}
				break;
			}
		}
		return array(
			'request'    => (bool) ( self::TAG_REQUEST & $tags ),
			'executable' => $executable,
		);
	}

	/**
	 * @param string $value Path-like literal.
	 * @return bool|null
	 */
	private function literal_executable_status( $value ) {
		$value = preg_replace( '/[?#].*$/', '', $value );
		if ( preg_match( '/\.(?:php\d*|phtml|phar)$/i', $value ) ) {
			return true;
		}
		$basename = basename( str_replace( '\\', '/', $value ) );
		if ( '' !== $basename && '.' !== $basename && '..' !== $basename && '/' !== substr( $value, -1 ) ) {
			return false;
		}
		return null;
	}

	/**
	 * @param array<int,mixed> $expression Expression.
	 * @return string|null
	 */
	private function expression_call_name( array $expression ) {
		return isset( $expression[0], $expression[1] ) && $this->is_id( $expression[0], T_STRING ) && '(' === $this->text( $expression[1] ) ? strtolower( $expression[0][1] ) : null;
	}

	/**
	 * @param array<int,mixed> $expression Expression.
	 * @return array<int,array<int,mixed>>
	 */
	private function call_arguments_from_expression( array $expression ) {
		return isset( $expression[1] ) && '(' === $this->text( $expression[1] ) ? $this->call_arguments( $expression, 1 ) : array();
	}

	/**
	 * @param array<int,mixed> $tokens     Tokens.
	 * @param int              $open_index Opening parenthesis position.
	 * @return array<int,array<int,mixed>>
	 */
	private function call_arguments( array $tokens, $open_index ) {
		$close = $this->matching_delimiter( $tokens, $open_index, '(', ')' );
		if ( null === $close ) {
			return array();
		}
		$arguments = array();
		$current   = array();
		$depth     = 0;
		for ( $index = $open_index + 1; $index < $close; ++$index ) {
			$text = $this->text( $tokens[ $index ] );
			if ( in_array( $text, array( '(', '[', '{' ), true ) ) {
				++$depth;
			} elseif ( in_array( $text, array( ')', ']', '}' ), true ) ) {
				--$depth;
			}
			if ( ',' === $text && 0 === $depth ) {
				$arguments[] = $current;
				$current     = array();
				continue;
			}
			$current[] = $tokens[ $index ];
		}
		if ( ! empty( $current ) ) {
			$arguments[] = $current;
		}
		return $arguments;
	}

	/**
	 * @param array<int,mixed> $tokens Tokens.
	 * @param int              $start  Expression start.
	 * @return array<int,mixed>
	 */
	private function language_construct_expression( array $tokens, $start ) {
		if ( isset( $tokens[ $start ] ) && '(' === $this->text( $tokens[ $start ] ) ) {
			$arguments = $this->call_arguments( $tokens, $start );
			return isset( $arguments[0] ) ? $arguments[0] : array();
		}
		$end = $this->expression_end( $tokens, $start );
		return array_slice( $tokens, $start, $end - $start );
	}

	/**
	 * @param array<int,mixed> $tokens Tokens.
	 * @param int              $start  Expression start.
	 * @return int
	 */
	private function expression_end( array $tokens, $start ) {
		$depth = 0;
		$count = count( $tokens );
		for ( $index = $start; $index < $count; ++$index ) {
			$text = $this->text( $tokens[ $index ] );
			if ( in_array( $text, array( '(', '[', '{' ), true ) ) {
				++$depth;
			} elseif ( in_array( $text, array( ')', ']', '}' ), true ) ) {
				$depth = max( 0, $depth - 1 );
			} elseif ( ';' === $text && 0 === $depth ) {
				return $index;
			}
		}
		return $count;
	}

	/**
	 * @param array<int,mixed> $expression Expression.
	 * @return string|null
	 */
	private function single_variable_name( array $expression ) {
		return 1 === count( $expression ) && $this->is_id( $expression[0], T_VARIABLE ) ? $this->variable_name( $expression[0] ) : null;
	}

	/**
	 * @param array<int,mixed> $tokens Tokens.
	 * @param int              $index  Function token position.
	 * @return bool
	 */
	private function is_method_call( array $tokens, $index ) {
		if ( $index < 1 || ! is_array( $tokens[ $index - 1 ] ) ) {
			return false;
		}
		return in_array( $tokens[ $index - 1 ][0], array( T_OBJECT_OPERATOR, T_DOUBLE_COLON ), true );
	}

	/**
	 * @param array<int,mixed> $tokens Tokens.
	 * @return array<int,mixed>
	 */
	private function compact( array $tokens ) {
		return array_values(
			array_filter(
				$tokens,
				function ( $token ) {
					return ! is_array( $token ) || ! in_array( $token[0], array( T_WHITESPACE, T_COMMENT, T_DOC_COMMENT, T_OPEN_TAG, T_CLOSE_TAG ), true );
				}
			)
		);
	}

	/**
	 * @param array<int,mixed> $tokens Tokens.
	 * @param int              $start  Search start.
	 * @param string           $wanted Wanted token text.
	 * @return int|null
	 */
	private function find_text( array $tokens, $start, $wanted ) {
		$count = count( $tokens );
		for ( $index = $start; $index < $count; ++$index ) {
			if ( $wanted === $this->text( $tokens[ $index ] ) ) {
				return $index;
			}
			if ( ';' === $this->text( $tokens[ $index ] ) ) {
				return null;
			}
		}
		return null;
	}

	/**
	 * @param array<int,mixed> $tokens     Tokens.
	 * @param int              $open_index Opening delimiter position.
	 * @param string           $open       Opening delimiter.
	 * @param string           $close      Closing delimiter.
	 * @return int|null
	 */
	private function matching_delimiter( array $tokens, $open_index, $open, $close ) {
		$depth = 0;
		$count = count( $tokens );
		for ( $index = $open_index; $index < $count; ++$index ) {
			$text = $this->text( $tokens[ $index ] );
			if ( $open === $text ) {
				++$depth;
			} elseif ( $close === $text ) {
				--$depth;
				if ( 0 === $depth ) {
					return $index;
				}
			}
		}
		return null;
	}

	/**
	 * @param mixed $token Token.
	 * @param int   $id    Token ID.
	 * @return bool
	 */
	private function is_id( $token, $id ) {
		return is_array( $token ) && $id === $token[0];
	}

	/**
	 * @param mixed $token Token.
	 * @return string
	 */
	private function text( $token ) {
		return is_array( $token ) ? $token[1] : (string) $token;
	}

	/**
	 * @param mixed $token Variable token.
	 * @return string
	 */
	private function variable_name( $token ) {
		return ltrim( $token[1], '$' );
	}

	/**
	 * @param string $text Quoted literal token.
	 * @return string
	 */
	private function string_literal( $text ) {
		return strlen( $text ) >= 2 ? substr( $text, 1, -1 ) : '';
	}
}
