<?php

/**
 * This is the part of the wikitext parser which handles automatic paragraphs
 * and conversion of start-of-line prefixes to HTML lists.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 * http://www.gnu.org/copyleft/gpl.html
 *
 * @file
 * @ingroup Parser
 * @internal
 */

namespace MediaWiki\Parser;

use LogicException;
use StringUtils;

class BlockLevelPass {
	/** @var bool */
	private $DTopen = false;
	/** @var bool */
	private $inPre = false;
	/** @var string */
	private $lastParagraph = '';
	/** @var bool */
	private $lineStart;
	/** @var string */
	private $text;

	# State constants for the definition list colon extraction
	private const COLON_STATE_TEXT = 0;
	private const COLON_STATE_TAG = 1;
	private const COLON_STATE_TAGSTART = 2;
	private const COLON_STATE_CLOSETAG = 3;
	private const COLON_STATE_TAGSLASH = 4;
	private const COLON_STATE_COMMENT = 5;
	private const COLON_STATE_COMMENTDASH = 6;
	private const COLON_STATE_COMMENTDASHDASH = 7;
	private const COLON_STATE_LC = 8;

	/**
	 * Make lists from lines starting with ':', '*', '#', etc.
	 *
	 * @param string $text
	 * @param bool $lineStart Whether or not this is at the start of a line.
	 * @return string The lists rendered as HTML
	 * @internal
	 */
	public static function doBlockLevels( $text, $lineStart ) {
		$pass = new self( $text, $lineStart );
		return $pass->execute();
	}

	/**
	 * @param string $text
	 * @param bool $lineStart
	 */
	private function __construct( $text, $lineStart ) {
		$this->text = $text;
		$this->lineStart = $lineStart;
	}

	/**
	 * @return bool
	 */
	private function hasOpenParagraph() {
		return $this->lastParagraph !== '';
	}

	/**
	 * If a pre or p is open, return the corresponding close tag and update
	 * the state. If no tag is open, return an empty string.
	 * @param bool $atTheEnd Omit trailing newline if we've reached the end.
	 * @return string
	 */
	private function closeParagraph( $atTheEnd = false ) {
		$result = '';
		if ( $this->hasOpenParagraph() ) {
			$result = '</' . $this->lastParagraph . '>';
			if ( !$atTheEnd ) {
				$result .= "\n";
			}
		}
		$this->inPre = false;
		$this->lastParagraph = '';
		return $result;
	}

	/**
	 * getCommon() returns the length of the longest common substring
	 * of both arguments, starting at the beginning of both.
	 *
	 * @param string $st1
	 * @param string $st2
	 *
	 * @return int
	 */
	private function getCommon( $st1, $st2 ) {
		$shorter = min( strlen( $st1 ), strlen( $st2 ) );

		for ( $i = 0; $i < $shorter; ++$i ) {
			if ( $st1[$i] !== $st2[$i] ) {
				break;
			}
		}
		return $i;
	}

	/**
	 * Open the list item element identified by the prefix character.
	 *
	 * @param string $char
	 *
	 * @return string
	 */
	private function openList( $char ) {
		$result = $this->closeParagraph();

		if ( $char === '*' ) {
			$result .= "<ul><li>";
		} elseif ( $char === '#' ) {
			$result .= "<ol><li>";
		} elseif ( $char === ':' ) {
			$result .= "<dl><dd>";
		} elseif ( $char === ';' ) {
			$result .= "<dl><dt>";
			$this->DTopen = true;
		} else {
			$result = '<!-- ERR 1 -->';
		}

		return $result;
	}

	/**
	 * Close the current list item and open the next one.
	 * @param string $char
	 *
	 * @return string
	 */
	private function nextItem( $char ) {
		if ( $char === '*' || $char === '#' ) {
			return "</li>\n<li>";
		} elseif ( $char === ':' || $char === ';' ) {
			$close = "</dd>\n";
			if ( $this->DTopen ) {
				$close = "</dt>\n";
			}
			if ( $char === ';' ) {
				$this->DTopen = true;
				return $close . '<dt>';
			} else {
				$this->DTopen = false;
				return $close . '<dd>';
			}
		}
		return '<!-- ERR 2 -->';
	}

	/**
	 * Close the current list item identified by the prefix character.
	 * @param string $char
	 *
	 * @return string
	 */
	private function closeList( $char ) {
		if ( $char === '*' ) {
			$text = "</li></ul>";
		} elseif ( $char === '#' ) {
			$text = "</li></ol>";
		} elseif ( $char === ':' ) {
			if ( $this->DTopen ) {
				$this->DTopen = false;
				$text = "</dt></dl>";
			} else {
				$text = "</dd></dl>";
			}
		} else {
			return '<!-- ERR 3 -->';
		}
		return $text;
	}

	/**
	 * Execute the pass.
	 * @return string
	 */
	private function execute() {
		$text = $this->text;
		# Parsing through the text line by line.  The main thing
		# happening here is handling of block-level elements p, pre,
		# and making lists from lines starting with * # : etc.
		$textLines = StringUtils::explode( "\n", $text );

		$lastPrefix = $output = '';
		$this->DTopen = $inBlockElem = false;
		$prefixLength = 0;
		$pendingPTag = false;
		$inBlockquote = false;

		for ( $textLines->rewind(); $textLines->valid(); ) {
			$inputLine = $textLines->current();
			$textLines->next();
			$notLastLine = $textLines->valid();

			# Fix up $lineStart
			if ( !$this->lineStart ) {
				$output .= $inputLine;
				$this->lineStart = true;
				continue;
			}
			# * = ul
			# # = ol
			# ; = dt
			# : = dd

			$lastPrefixLength = strlen( $lastPrefix );
			$preCloseMatch = preg_match( '/<\\/pre/i', $inputLine );
			$preOpenMatch = preg_match( '/<pre/i', $inputLine );
			# If not in a <pre> element, scan for and figure out what prefixes are there.
			if ( !$this->inPre ) {
				# Multiple prefixes may abut each other for nested lists.
				$prefixLength = strspn( $inputLine, '*#:;' );
				$prefix = substr( $inputLine, 0, $prefixLength );

				# eh?
				# ; and : are both from definition-lists, so they're equivalent
				#  for the purposes of determining whether or not we need to open/close
				#  elements.
				$prefix2 = str_replace( ';', ':', $prefix );
				$t = substr( $inputLine, $prefixLength );
				$this->inPre = (bool)$preOpenMatch;
			} else {
				# Don't interpret any other prefixes in preformatted text
				$prefixLength = 0;
				$prefix = $prefix2 = '';
				$t = $inputLine;
			}

			# List generation
			if ( $prefixLength && $lastPrefix === $prefix2 ) {
				# Same as the last item, so no need to deal with nesting or opening stuff
				$output .= $this->nextItem( substr( $prefix, -1 ) );
				$pendingPTag = false;

				if ( substr( $prefix, -1 ) === ';' ) {
					# The one nasty exception: definition lists work like this:
					# ; title : definition text
					# So we check for : in the remainder text to split up the
					# title and definition, without b0rking links.
					$term = $t2 = '';
					if ( $this->findColonNoLinks( $t, $term, $t2 ) !== false ) {
						$t = $t2;
						// Trim whitespace in list items
						$output .= trim( $term ) . $this->nextItem( ':' );
					}
				}
			} elseif ( $prefixLength || $lastPrefixLength ) {
				# We need to open or close prefixes, or both.

				# Either open or close a level...
				$commonPrefixLength = $this->getCommon( $prefix, $lastPrefix );
				$pendingPTag = false;

				# Close all the prefixes which aren't shared.
				while ( $commonPrefixLength < $lastPrefixLength ) {
					// @phan-suppress-next-line PhanTypeInvalidDimOffset
					$output .= $this->closeList( $lastPrefix[$lastPrefixLength - 1] );
					--$lastPrefixLength;
				}

				# Continue the current prefix if appropriate.
				if ( $prefixLength <= $commonPrefixLength && $commonPrefixLength > 0 ) {
					$output .= $this->nextItem( $prefix[$commonPrefixLength - 1] );
				}

				# Close an open <dt> if we have a <dd> (":") starting on this line
				if ( $this->DTopen && $commonPrefixLength > 0 && $prefix[$commonPrefixLength - 1] === ':' ) {
					$output .= $this->nextItem( ':' );
				}

				# Open prefixes where appropriate.
				if ( $lastPrefix && $prefixLength > $commonPrefixLength ) {
					$output .= "\n";
				}
				while ( $prefixLength > $commonPrefixLength ) {
					$char = $prefix[$commonPrefixLength];
					$output .= $this->openList( $char );

					if ( $char === ';' ) {
						# @todo FIXME: This is dupe of code above
						if ( $this->findColonNoLinks( $t, $term, $t2 ) !== false ) {
							$t = $t2;
							// Trim whitespace in list items
							$output .= trim( $term ) . $this->nextItem( ':' );
						}
					}
					++$commonPrefixLength;
				}
				if ( !$prefixLength && $lastPrefix ) {
					$output .= "\n";
				}
				$lastPrefix = $prefix2;
			}

			# If we have no prefixes, go to paragraph mode.
			if ( $prefixLength == 0 ) {
				# No prefix (not in list)--go to paragraph mode
				# @todo consider using a stack for nestable elements like span, table and div

				// P-wrapping and indent-pre are suppressed inside, not outside
				$blockElems = 'table|h1|h2|h3|h4|h5|h6|pre|p|ul|ol|dl';
				// P-wrapping and indent-pre are suppressed outside, not inside
				$antiBlockElems = 'td|th';

				$openMatch = preg_match(
					'/<('
						. "({$blockElems})|\\/({$antiBlockElems})|"
						// Always suppresses
						. '\\/?(tr|caption|dt|dd|li)'
						. ')\\b/iS',
					$t
				);
				$closeMatch = preg_match(
					'/<('
						. "\\/({$blockElems})|({$antiBlockElems})|"
						// Never suppresses
						. '\\/?(center|blockquote|div|hr|mw:|aside|figure)|'
						// Used as Parser::TOC_PLACEHOLDER
						. 'meta property="mw:'
						. ')\\b/iS',
					$t
				);

				// Any match closes the paragraph, but only when `!$closeMatch`
				// do we enter block mode.  The oddities with table rows and
				// cells are to avoid paragraph wrapping in interstitial spaces
				// leading to fostered content.

				if ( $openMatch || $closeMatch ) {
					$pendingPTag = false;
					// Only close the paragraph if we're not inside a <pre> tag, or if
					// that <pre> tag has just been opened
					if ( !$this->inPre || $preOpenMatch ) {
						// @todo T7718: paragraph closed
						$output .= $this->closeParagraph();
					}
					if ( $preOpenMatch && !$preCloseMatch ) {
						$this->inPre = true;
					}
					$bqOffset = 0;
					while ( preg_match( '/<(\\/?)blockquote[\s>]/i', $t,
						$bqMatch, PREG_OFFSET_CAPTURE, $bqOffset )
					) {
						$inBlockquote = !$bqMatch[1][0]; // is this a close tag?
						$bqOffset = $bqMatch[0][1] + strlen( $bqMatch[0][0] );
					}
					$inBlockElem = !$closeMatch;
				} elseif ( !$inBlockElem && !$this->inPre ) {
					if ( substr( $t, 0, 1 ) == ' '
						&& ( $this->lastParagraph === 'pre' || trim( $t ) != '' )
						&& !$inBlockquote
					) {
						# pre
						if ( $this->lastParagraph !== 'pre' ) {
							$pendingPTag = false;
							$output .= $this->closeParagraph() . '<pre>';
							$this->lastParagraph = 'pre';
						}
						$t = substr( $t, 1 );
					} elseif ( preg_match( '/^(?:<style\\b[^>]*>.*?<\\/style>\s*|<link\\b[^>]*>\s*)+$/iS', $t ) ) {
						# T186965: <style> or <link> by itself on a line shouldn't open or close paragraphs.
						# But it should clear $pendingPTag.
						if ( $pendingPTag ) {
							$output .= $this->closeParagraph();
							$pendingPTag = false;
						}
					} else {
						# paragraph
						if ( trim( $t ) === '' ) {
							if ( $pendingPTag ) {
								$output .= $pendingPTag . '<br />';
								$pendingPTag = false;
								$this->lastParagraph = 'p';
							} elseif ( $this->lastParagraph !== 'p' ) {
								$output .= $this->closeParagraph();
								$pendingPTag = '<p>';
							} else {
								$pendingPTag = '</p><p>';
							}
						} elseif ( $pendingPTag ) {
							$output .= $pendingPTag;
							$pendingPTag = false;
							$this->lastParagraph = 'p';
						} elseif ( $this->lastParagraph !== 'p' ) {
							$output .= $this->closeParagraph() . '<p>';
							$this->lastParagraph = 'p';
						}
					}
				}
			}
			# somewhere above we forget to get out of pre block (T2785)
			if ( $preCloseMatch && $this->inPre ) {
				$this->inPre = false;
			}
			if ( $pendingPTag === false ) {
				if ( $prefixLength === 0 ) {
					$output .= $t;
					// Add a newline if there's an open paragraph
					// or we've yet to reach the last line.
					if ( $notLastLine || $this->hasOpenParagraph() ) {
						$output .= "\n";
					}
				} else {
					// Trim whitespace in list items
					$output .= trim( $t );
				}
			}
		}
		while ( $prefixLength ) {
			// @phan-suppress-next-line PhanTypeArraySuspicious $prefix set if $prefixLength is set
			$output .= $this->closeList( $prefix2[$prefixLength - 1] );
			--$prefixLength;
			// Note that a paragraph is only ever opened when `prefixLength`
			// is zero, but we'll choose to be overly cautious.
			if ( !$prefixLength && $this->hasOpenParagraph() ) {
				$output .= "\n";
			}
		}
		$output .= $this->closeParagraph( true );
		return $output;
	}

	/**
	 * Split up a string on ':', ignoring any occurrences inside tags
	 * to prevent illegal overlapping.
	 *
	 * @param string $str The string to split
	 * @param string &$before Set to everything before the ':'
	 * @param string &$after Set to everything after the ':'
	 * @return int|false The position of the ':', or false if none found
	 */
	private function findColonNoLinks( $str, &$before, &$after ) {
		if ( !preg_match( '/:|<|-\{/', $str, $m, PREG_OFFSET_CAPTURE ) ) {
			# Nothing to find!
			return false;
		}

		if ( $m[0][0] === ':' ) {
			# Easy; no tag nesting to worry about
			$colonPos = $m[0][1];
			$before = substr( $str, 0, $colonPos );
			$after = substr( $str, $colonPos + 1 );
			return $colonPos;
		}

		# Ugly state machine to walk through avoiding tags.
		$state = self::COLON_STATE_TEXT;
		$ltLevel = 0;
		$lcLevel = 0;
		$len = strlen( $str );
		for ( $i = $m[0][1]; $i < $len; $i++ ) {
			$c = $str[$i];

			switch ( $state ) {
				case self::COLON_STATE_TEXT:
					switch ( $c ) {
						case "<":
							# Could be either a <start> tag or an </end> tag
							$state = self::COLON_STATE_TAGSTART;
							break;
						case ":":
							if ( $ltLevel === 0 ) {
								# We found it!
								$before = substr( $str, 0, $i );
								$after = substr( $str, $i + 1 );
								return $i;
							}
							# Embedded in a tag; don't break it.
							break;
						default:
							# Skip ahead looking for something interesting
							if ( !preg_match( '/:|<|-\{/', $str, $m, PREG_OFFSET_CAPTURE, $i ) ) {
								# Nothing else interesting
								return false;
							}
							if ( $m[0][0] === '-{' ) {
								$state = self::COLON_STATE_LC;
								$lcLevel++;
								$i = $m[0][1] + 1;
							} else {
								# Skip ahead to next interesting character.
								$i = $m[0][1] - 1;
							}
							break;
					}
					break;
				case self::COLON_STATE_LC:
					# In language converter markup -{ ... }-
					if ( !preg_match( '/-\{|\}-/', $str, $m, PREG_OFFSET_CAPTURE, $i ) ) {
						# Nothing else interesting to find; abort!
						# We're nested in language converter markup, but there
						# are no close tags left.  Abort!
						break 2;
					}
					if ( $m[0][0] === '-{' ) {
						$i = $m[0][1] + 1;
						$lcLevel++;
					} elseif ( $m[0][0] === '}-' ) {
						$i = $m[0][1] + 1;
						$lcLevel--;
						if ( $lcLevel === 0 ) {
							$state = self::COLON_STATE_TEXT;
						}
					}
					break;
				case self::COLON_STATE_TAG:
					# In a <tag>
					switch ( $c ) {
						case ">":
							$ltLevel++;
							$state = self::COLON_STATE_TEXT;
							break;
						case "/":
							# Slash may be followed by >?
							$state = self::COLON_STATE_TAGSLASH;
							break;
						default:
							# ignore
					}
					break;
				case self::COLON_STATE_TAGSTART:
					switch ( $c ) {
						case "/":
							$state = self::COLON_STATE_CLOSETAG;
							break;
						case "!":
							$state = self::COLON_STATE_COMMENT;
							break;
						case ">":
							# Illegal early close? This shouldn't happen D:
							$state = self::COLON_STATE_TEXT;
							break;
						default:
							$state = self::COLON_STATE_TAG;
					}
					break;
				case self::COLON_STATE_CLOSETAG:
					# In a </tag>
					if ( $c === ">" ) {
						if ( $ltLevel > 0 ) {
							$ltLevel--;
						} else {
							# ignore the excess close tag, but keep looking for
							# colons. (This matches Parsoid behavior.)
							wfDebug( __METHOD__ . ": Invalid input; too many close tags" );
						}
						$state = self::COLON_STATE_TEXT;
					}
					break;
				case self::COLON_STATE_TAGSLASH:
					if ( $c === ">" ) {
						# Yes, a self-closed tag <blah/>
						$state = self::COLON_STATE_TEXT;
					} else {
						# Probably we're jumping the gun, and this is an attribute
						$state = self::COLON_STATE_TAG;
					}
					break;
				case self::COLON_STATE_COMMENT:
					if ( $c === "-" ) {
						$state = self::COLON_STATE_COMMENTDASH;
					}
					break;
				case self::COLON_STATE_COMMENTDASH:
					if ( $c === "-" ) {
						$state = self::COLON_STATE_COMMENTDASHDASH;
					} else {
						$state = self::COLON_STATE_COMMENT;
					}
					break;
				case self::COLON_STATE_COMMENTDASHDASH:
					if ( $c === ">" ) {
						$state = self::COLON_STATE_TEXT;
					} else {
						$state = self::COLON_STATE_COMMENT;
					}
					break;
				default:
					throw new LogicException( "State machine error in " . __METHOD__ );
			}
		}
		if ( $ltLevel > 0 || $lcLevel > 0 ) {
			wfDebug(
				__METHOD__ . ": Invalid input; not enough close tags " .
				"(level $ltLevel/$lcLevel, state $state)"
			);
		}
		return false;
	}
}

/** @deprecated class alias since 1.43 */
class_alias( BlockLevelPass::class, 'BlockLevelPass' );