parse.rs

//! JSON を読んで値の木を作る。
//!
//! 受け付けるのは RFC 8259 の JSON だけで、コメントや末尾のカンマはエラーにする。
//! 壊れていれば、見つけた位置の行と列を Error に入れて返す。

use crate::Error;
use crate::value::Value;
use std::borrow::Cow;


/// 入れ子の深さの上限。原型の jsonfmt と同じにしている
const MAX_DEPTH: usize = 128;

/// エラーの文言に出す、未知の語の長さの上限
const WORD_SHOWN: usize = 20;


/// JSON 全体を読む。値の前後には空白しか置けない。
pub fn parse(source: &str) -> Result<Value<'_>, Error> {
	let mut parser = Parser {
		source,
		bytes: source.as_bytes(),
		index: 0,
	};

	parser.skip_whitespace();
	if parser.peek().is_none() {
		return Err(parser.error(parser.index, "入力が空です".to_string()));
	}

	let value = parser.parse_value(0)?;
	parser.skip_whitespace();
	if parser.peek().is_some() {
		return Err(parser.unexpected(|found| format!("値の後ろに余計な {} があります", found)));
	}
	Ok(value)
}


struct Parser<'a> {
	source: &'a str,
	bytes: &'a [u8],
	index: usize,
}

impl<'a> Parser<'a> {
	fn peek(&self) -> Option<u8> {
		self.bytes.get(self.index).copied()
	}

	fn skip_whitespace(&mut self) {
		let rest = &self.bytes[self.index..];
		self.index += rest
			.iter()
			.position(|&byte| !matches!(byte, b' ' | b'\t' | b'\n' | b'\r'))
			.unwrap_or(rest.len());
	}

	fn skip_digits(&mut self) {
		let rest = &self.bytes[self.index..];
		self.index += rest.iter().position(|byte| !byte.is_ascii_digit()).unwrap_or(rest.len());
	}

	/// 文字列の中で、そのまま写せる部分を読み飛ばす。止まるのは " と \ と制御文字の上
	fn skip_plain(&mut self) {
		let rest = &self.bytes[self.index..];
		self.index += rest
			.iter()
			.position(|&byte| byte == b'"' || byte == b'\\' || byte < 0x20)
			.unwrap_or(rest.len());
	}

	/// depth は、いま読んでいる値を包んでいる配列とオブジェクトの数
	fn parse_value(&mut self, depth: usize) -> Result<Value<'a>, Error> {
		match self.peek() {
			Some(b'{') => self.parse_object(depth + 1),
			Some(b'[') => self.parse_array(depth + 1),
			Some(b'"') => Ok(Value::String(self.parse_string()?)),
			Some(b'-' | b'0'..=b'9') => Ok(Value::Number(self.parse_number()?)),
			Some(byte) if byte.is_ascii_alphabetic() => self.parse_word(),
			_ => Err(self.unexpected(|found| format!("値が必要なところに {} があります", found))),
		}
	}

	fn parse_array(&mut self, depth: usize) -> Result<Value<'a>, Error> {
		self.check_depth(depth)?;
		self.index += 1;
		let mut items = Vec::new();

		self.skip_whitespace();
		if self.peek() == Some(b']') {
			self.index += 1;
			return Ok(Value::Array(items));
		}

		loop {
			items.push(self.parse_value(depth)?);
			self.skip_whitespace();
			match self.peek() {
				Some(b',') => {
					self.index += 1;
					self.skip_whitespace();
				}
				Some(b']') => {
					self.index += 1;
					return Ok(Value::Array(items));
				}
				_ => {
					return Err(self.unexpected(|found| {
						format!("配列の要素の後ろに {} があります。, か ] が必要です", found)
					}));
				}
			}
		}
	}

	fn parse_object(&mut self, depth: usize) -> Result<Value<'a>, Error> {
		self.check_depth(depth)?;
		self.index += 1;
		let mut members = Vec::new();

		self.skip_whitespace();
		if self.peek() == Some(b'}') {
			self.index += 1;
			return Ok(Value::Object(members));
		}

		loop {
			if self.peek() != Some(b'"') {
				return Err(self.unexpected(|found| format!("キーが必要なところに {} があります", found)));
			}
			let key = self.parse_string()?;

			self.skip_whitespace();
			if self.peek() != Some(b':') {
				return Err(self.unexpected(|found| format!("キーの後ろに {} があります。: が必要です", found)));
			}
			self.index += 1;
			self.skip_whitespace();

			let value = self.parse_value(depth)?;
			members.push((key, value));

			self.skip_whitespace();
			match self.peek() {
				Some(b',') => {
					self.index += 1;
					self.skip_whitespace();
				}
				Some(b'}') => {
					self.index += 1;
					return Ok(Value::Object(members));
				}
				_ => {
					return Err(self.unexpected(|found| {
						format!("オブジェクトの値の後ろに {} があります。, か }} が必要です", found)
					}));
				}
			}
		}
	}

	fn check_depth(&self, depth: usize) -> Result<(), Error> {
		if depth > MAX_DEPTH {
			return Err(self.error(self.index, format!("入れ子が深すぎます。{} 段までです", MAX_DEPTH)));
		}
		Ok(())
	}

	/// 文字列を読み、エスケープを解いて返す。いまの位置は開きの " にある
	fn parse_string(&mut self) -> Result<Cow<'a, str>, Error> {
		let open = self.index;
		self.index += 1;
		let start = self.index;
		self.skip_plain();

		// エスケープがなければ、新しい String を作らずに入力をそのまま指す
		if self.peek() == Some(b'"') {
			let text = &self.source[start..self.index];
			self.index += 1;
			return Ok(Cow::Borrowed(text));
		}

		let mut text = String::from(&self.source[start..self.index]);
		loop {
			match self.peek() {
				Some(b'"') => {
					self.index += 1;
					return Ok(Cow::Owned(text));
				}
				Some(b'\\') => self.parse_escape(open, &mut text)?,
				Some(byte) => {
					let message = format!("文字列の中に制御文字 U+{:04X} がそのまま入っています", byte);
					return Err(self.error(self.index, message));
				}
				None => return Err(self.error(open, "文字列が閉じていません".to_string())),
			}

			// 止まるのは ASCII の上だけなので、start と index はいつも文字の境目にある
			let start = self.index;
			self.skip_plain();
			text.push_str(&self.source[start..self.index]);
		}
	}

	/// \ から始まるエスケープを 1 つ読み、解いた文字を text に足す。open は文字列の開きの位置
	fn parse_escape(&mut self, open: usize, text: &mut String) -> Result<(), Error> {
		let start = self.index;
		self.index += 1;

		let character = match self.peek() {
			Some(b'"') => '"',
			Some(b'\\') => '\\',
			Some(b'/') => '/',
			Some(b'b') => '\u{08}',
			Some(b'f') => '\u{0c}',
			Some(b'n') => '\n',
			Some(b'r') => '\r',
			Some(b't') => '\t',
			Some(b'u') => {
				self.index += 1;
				text.push(self.parse_unicode(start)?);
				return Ok(());
			}
			Some(_) => {
				let found = self.source[self.index..].chars().next().map(describe).unwrap_or_default();
				return Err(self.error(start, format!("\\ の後ろに {} は置けません", found)));
			}
			None => return Err(self.error(open, "文字列が閉じていません".to_string())),
		};

		self.index += 1;
		text.push(character);
		Ok(())
	}

	/// \u の後ろを読む。サロゲートペアなら、続く \uXXXX も読んで 1 文字にする。start は \ の位置
	fn parse_unicode(&mut self, start: usize) -> Result<char, Error> {
		let first = self.parse_hex(start)?;
		let mut code = first;

		if (0xD800..=0xDBFF).contains(&first) && self.bytes[self.index..].starts_with(b"\\u") {
			let second_start = self.index;
			self.index += 2;
			let second = self.parse_hex(second_start)?;
			if (0xDC00..=0xDFFF).contains(&second) {
				code = 0x10000 + ((first - 0xD800) << 10) + (second - 0xDC00);
			}
		}

		// 対にならなかったサロゲートは文字にならない
		char::from_u32(code)
			.ok_or_else(|| self.error(start, format!("対になっていないサロゲート \\u{:04X} です", first)))
	}

	/// 16 進数 4 桁を読む。start はエラーのときに指す \ の位置
	fn parse_hex(&mut self, start: usize) -> Result<u32, Error> {
		let mut code = 0;
		for _ in 0..4 {
			let Some(digit) = self.peek().and_then(|byte| (byte as char).to_digit(16)) else {
				return Err(self.error(start, "\\u の後ろには 16 進数 4 桁が必要です".to_string()));
			};
			code = code * 16 + digit;
			self.index += 1;
		}
		Ok(code)
	}

	/// 数値を読み、入力の字面をそのまま返す
	fn parse_number(&mut self) -> Result<&'a str, Error> {
		let start = self.index;
		if self.peek() == Some(b'-') {
			self.index += 1;
		}

		match self.peek() {
			Some(b'0') => {
				self.index += 1;
				if let Some(b'0'..=b'9') = self.peek() {
					return Err(self.error(start, "数値の先頭に余計な 0 があります".to_string()));
				}
			}
			Some(b'1'..=b'9') => self.skip_digits(),
			_ => return Err(self.error(start, "- の後ろに数字がありません".to_string())),
		}

		if self.peek() == Some(b'.') {
			self.index += 1;
			if !matches!(self.peek(), Some(b'0'..=b'9')) {
				return Err(self.error(start, "小数点の後ろに数字がありません".to_string()));
			}
			self.skip_digits();
		}

		if let Some(b'e' | b'E') = self.peek() {
			self.index += 1;
			if let Some(b'+' | b'-') = self.peek() {
				self.index += 1;
			}
			if !matches!(self.peek(), Some(b'0'..=b'9')) {
				return Err(self.error(start, "指数の後ろに数字がありません".to_string()));
			}
			self.skip_digits();
		}

		Ok(&self.source[start..self.index])
	}

	/// true、false、null を読む。それ以外の語はエラーにする
	fn parse_word(&mut self) -> Result<Value<'a>, Error> {
		let start = self.index;
		let mut end = start;
		while end < self.bytes.len() && self.bytes[end].is_ascii_alphanumeric() {
			end += 1;
		}

		let value = match &self.source[start..end] {
			"true" => Value::Bool(true),
			"false" => Value::Bool(false),
			"null" => Value::Null,
			word => {
				// 長い語をそのまま出すと文言がいくらでも長くなるので、先頭だけにする。語は ASCII だけでできている
				let shown = if word.len() > WORD_SHOWN { format!("{}...", &word[..WORD_SHOWN]) } else { word.to_string() };
				return Err(self.error(start, format!("{} は JSON の値ではありません", shown)));
			}
		};
		self.index = end;
		Ok(value)
	}

	/// いまの位置の文字を message に渡してエラーにする。入力が終わっていれば、途中で終わったエラーにする
	fn unexpected(&self, message: impl FnOnce(String) -> String) -> Error {
		match self.source[self.index..].chars().next() {
			Some(character) => self.error(self.index, message(describe(character))),
			None => self.error(self.index, "JSON が途中で終わっています".to_string()),
		}
	}

	/// index の位置を行と列に直して Error を作る
	fn error(&self, index: usize, message: String) -> Error {
		let before = &self.source[..index];
		let line = before.matches('\n').count() + 1;
		let line_start = before.rfind('\n').map_or(0, |position| position + 1);
		let column = before[line_start..].chars().count() + 1;
		Error { line, column, message }
	}
}


/// エラーの文言に入れるときの文字の書き方。
///
/// 制御文字、見えない文字、表示の向きを変える文字は、端末の表示を崩すので U+XXXX にする。
/// ASCII 以外でどれがそうかは、Rust の escape_debug がエスケープするかどうかで決める。
fn describe(character: char) -> String {
	let visible = matches!(character, ' '..='~') || character.escape_debug().next() != Some('\\');
	if visible {
		format!("'{}'", character)
	} else {
		format!("U+{:04X}", character as u32)
	}
}