use std::fmt;
use std::io::{self, Read};

#[derive(Debug, Clone, PartialEq)]
enum Json {
    Null,
    Bool(bool),
    Number(String),
    String(String),
    Array(Vec<Json>),
    Object(Vec<(String, Json)>),
}

#[derive(Debug, Clone, PartialEq)]
struct JsonError {
    pos: usize,
    message: String,
}

impl JsonError {
    fn new(pos: usize, message: impl Into<String>) -> Self {
        Self {
            pos,
            message: message.into(),
        }
    }
}

impl fmt::Display for JsonError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} at byte {}", self.message, self.pos)
    }
}

struct Parser<'a> {
    input: &'a str,
    pos: usize,
}

impl<'a> Parser<'a> {
    fn new(input: &'a str) -> Self {
        Self { input, pos: 0 }
    }

    fn parse(mut self) -> Result<Json, JsonError> {
        self.skip_ws();
        let value = self.value()?;
        self.skip_ws();

        if self.pos == self.input.len() {
            Ok(value)
        } else {
            Err(self.error("trailing characters"))
        }
    }

    fn value(&mut self) -> Result<Json, JsonError> {
        self.skip_ws();

        match self.peek() {
            Some('n') => self.literal("null", Json::Null),
            Some('t') => self.literal("true", Json::Bool(true)),
            Some('f') => self.literal("false", Json::Bool(false)),
            Some('"') => Ok(Json::String(self.string()?)),
            Some('[') => self.array(),
            Some('{') => self.object(),
            Some('-') | Some('0'..='9') => self.number(),
            Some(_) => Err(self.error("expected JSON value")),
            None => Err(self.error("unexpected end of input")),
        }
    }

    fn literal(&mut self, text: &str, value: Json) -> Result<Json, JsonError> {
        if self.input[self.pos..].starts_with(text) {
            self.pos += text.len();
            Ok(value)
        } else {
            Err(self.error(format!("expected `{text}`")))
        }
    }

    fn array(&mut self) -> Result<Json, JsonError> {
        self.expect('[')?;
        self.skip_ws();

        let mut values = Vec::new();
        if self.consume(']') {
            return Ok(Json::Array(values));
        }

        loop {
            values.push(self.value()?);
            self.skip_ws();

            if self.consume(']') {
                break;
            }

            self.expect(',')?;
        }

        Ok(Json::Array(values))
    }

    fn object(&mut self) -> Result<Json, JsonError> {
        self.expect('{')?;
        self.skip_ws();

        let mut pairs = Vec::new();
        if self.consume('}') {
            return Ok(Json::Object(pairs));
        }

        loop {
            self.skip_ws();
            if self.peek() != Some('"') {
                return Err(self.error("expected object key"));
            }

            let key = self.string()?;
            self.skip_ws();
            self.expect(':')?;
            let value = self.value()?;
            pairs.push((key, value));
            self.skip_ws();

            if self.consume('}') {
                break;
            }

            self.expect(',')?;
        }

        Ok(Json::Object(pairs))
    }

    fn number(&mut self) -> Result<Json, JsonError> {
        let start = self.pos;

        self.consume('-');

        match self.peek() {
            Some('0') => {
                self.bump();
            }
            Some('1'..='9') => {
                self.bump();
                while matches!(self.peek(), Some('0'..='9')) {
                    self.bump();
                }
            }
            _ => return Err(self.error("invalid number")),
        }

        if self.consume('.') {
            if !matches!(self.peek(), Some('0'..='9')) {
                return Err(self.error("expected digit after decimal point"));
            }

            while matches!(self.peek(), Some('0'..='9')) {
                self.bump();
            }
        }

        if matches!(self.peek(), Some('e') | Some('E')) {
            self.bump();
            if matches!(self.peek(), Some('+') | Some('-')) {
                self.bump();
            }

            if !matches!(self.peek(), Some('0'..='9')) {
                return Err(self.error("expected exponent digits"));
            }

            while matches!(self.peek(), Some('0'..='9')) {
                self.bump();
            }
        }

        Ok(Json::Number(self.input[start..self.pos].to_string()))
    }

    fn string(&mut self) -> Result<String, JsonError> {
        self.expect('"')?;
        let mut out = String::new();

        loop {
            let c = self
                .bump()
                .ok_or_else(|| self.error("unterminated string"))?;

            match c {
                '"' => return Ok(out),
                '\\' => out.push(self.escape()?),
                '\u{0000}'..='\u{001F}' => {
                    return Err(self.error("unescaped control character in string"));
                }
                _ => out.push(c),
            }
        }
    }

    fn escape(&mut self) -> Result<char, JsonError> {
        match self.bump() {
            Some('"') => Ok('"'),
            Some('\\') => Ok('\\'),
            Some('/') => Ok('/'),
            Some('b') => Ok('\u{0008}'),
            Some('f') => Ok('\u{000C}'),
            Some('n') => Ok('\n'),
            Some('r') => Ok('\r'),
            Some('t') => Ok('\t'),
            Some('u') => self.unicode_escape(),
            Some(_) => Err(self.error("invalid string escape")),
            None => Err(self.error("unterminated escape")),
        }
    }

    fn unicode_escape(&mut self) -> Result<char, JsonError> {
        let first = self.hex_quad()?;

        let scalar = if (0xD800..=0xDBFF).contains(&first) {
            if self.bump() != Some('\\') || self.bump() != Some('u') {
                return Err(self.error("expected low surrogate"));
            }

            let second = self.hex_quad()?;
            if !(0xDC00..=0xDFFF).contains(&second) {
                return Err(self.error("invalid low surrogate"));
            }

            0x10000 + (((first - 0xD800) << 10) | (second - 0xDC00))
        } else if (0xDC00..=0xDFFF).contains(&first) {
            return Err(self.error("unexpected low surrogate"));
        } else {
            first
        };

        char::from_u32(scalar).ok_or_else(|| self.error("invalid unicode scalar"))
    }

    fn hex_quad(&mut self) -> Result<u32, JsonError> {
        let mut n = 0;

        for _ in 0..4 {
            let c = self
                .bump()
                .ok_or_else(|| self.error("incomplete unicode escape"))?;
            n = (n << 4)
                | c.to_digit(16)
                    .ok_or_else(|| self.error("invalid unicode escape"))?;
        }

        Ok(n)
    }

    fn skip_ws(&mut self) {
        while matches!(self.peek(), Some(' ' | '\n' | '\r' | '\t')) {
            self.bump();
        }
    }

    fn expect(&mut self, expected: char) -> Result<(), JsonError> {
        if self.consume(expected) {
            Ok(())
        } else {
            Err(self.error(format!("expected `{expected}`")))
        }
    }

    fn consume(&mut self, expected: char) -> bool {
        if self.peek() == Some(expected) {
            self.bump();
            true
        } else {
            false
        }
    }

    fn peek(&self) -> Option<char> {
        self.input[self.pos..].chars().next()
    }

    fn bump(&mut self) -> Option<char> {
        let c = self.peek()?;
        self.pos += c.len_utf8();
        Some(c)
    }

    fn error(&self, message: impl Into<String>) -> JsonError {
        JsonError::new(self.pos, message)
    }
}

fn pretty_print(input: &str) -> Result<String, JsonError> {
    let value = Parser::new(input).parse()?;
    let mut out = String::new();
    write_json(&value, 0, 2, &mut out);
    Ok(out)
}

fn write_json(value: &Json, depth: usize, step: usize, out: &mut String) {
    match value {
        Json::Null => out.push_str("null"),
        Json::Bool(true) => out.push_str("true"),
        Json::Bool(false) => out.push_str("false"),
        Json::Number(n) => out.push_str(n),
        Json::String(s) => write_string(s, out),
        Json::Array(values) => write_array(values, depth, step, out),
        Json::Object(pairs) => write_object(pairs, depth, step, out),
    }
}

fn write_array(values: &[Json], depth: usize, step: usize, out: &mut String) {
    if values.is_empty() {
        out.push_str("[]");
        return;
    }

    out.push('[');
    for (i, value) in values.iter().enumerate() {
        out.push('\n');
        indent(depth + step, out);
        write_json(value, depth + step, step, out);

        if i + 1 != values.len() {
            out.push(',');
        }
    }
    out.push('\n');
    indent(depth, out);
    out.push(']');
}

fn write_object(pairs: &[(String, Json)], depth: usize, step: usize, out: &mut String) {
    if pairs.is_empty() {
        out.push_str("{}");
        return;
    }

    out.push('{');
    for (i, (key, value)) in pairs.iter().enumerate() {
        out.push('\n');
        indent(depth + step, out);
        write_string(key, out);
        out.push_str(": ");
        write_json(value, depth + step, step, out);

        if i + 1 != pairs.len() {
            out.push(',');
        }
    }
    out.push('\n');
    indent(depth, out);
    out.push('}');
}

// Re-escape strings so the output is always valid JSON.
fn write_string(s: &str, out: &mut String) {
    out.push('"');

    for c in s.chars() {
        match c {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            '\u{0008}' => out.push_str("\\b"),
            '\u{000C}' => out.push_str("\\f"),
            '\u{0000}'..='\u{001F}' => out.push_str(&format!("\\u{:04x}", c as u32)),
            _ => out.push(c),
        }
    }

    out.push('"');
}

fn indent(n: usize, out: &mut String) {
    out.extend(std::iter::repeat(' ').take(n));
}

fn main() {
    let mut input = String::new();

    if let Err(err) = io::stdin().read_to_string(&mut input) {
        eprintln!("read error: {err}");
        std::process::exit(1);
    }

    match pretty_print(&input) {
        Ok(output) => println!("{output}"),
        Err(err) => {
            eprintln!("json error: {err}");
            std::process::exit(1);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn prints_nested_json() {
        let input = r#"{"name":"Ada","ok":true,"items":[1,null,{"x":2}]}"#;
        let expected = r#"{
  "name": "Ada",
  "ok": true,
  "items": [
    1,
    null,
    {
      "x": 2
    }
  ]
}"#;

        assert_eq!(pretty_print(input).unwrap(), expected);
    }

    #[test]
    fn handles_escapes_and_unicode() {
        let input = r#"{"text":"line\n\u263a","quote":"\""}"#;
        let expected = "{\n  \"text\": \"line\\n☺\",\n  \"quote\": \"\\\"\"\n}";

        assert_eq!(pretty_print(input).unwrap(), expected);
    }
}