use std::env;
use std::fmt::{self, Write as _};
use std::io::{self, Read};
use std::process;

#[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,
}

type JsonResult<T> = Result<T, JsonError>;

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) -> JsonResult<Json> {
        self.skip_ws();
        let value = self.value()?;
        self.skip_ws();

        if self.peek().is_some() {
            Err(self.error("trailing characters"))
        } else {
            Ok(value)
        }
    }

    fn value(&mut self) -> JsonResult<Json> {
        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('"') => self.string().map(Json::String),
            Some('[') => self.array(),
            Some('{') => self.object(),
            Some('-' | '0'..='9') => self.number().map(Json::Number),
            Some(c) => Err(self.error(format!("unexpected character '{c}'"))),
            None => Err(self.error("unexpected end of input")),
        }
    }

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

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

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

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

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

            self.expect(',')?;
        }

        Ok(Json::Array(values))
    }

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

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

        loop {
            self.skip_ws();
            let key = self.string()?;

            self.skip_ws();
            self.expect(':')?;

            let value = self.value()?;
            pairs.push((key, value));

            self.skip_ws();
            if self.take_if('}') {
                break;
            }

            self.expect(',')?;
        }

        Ok(Json::Object(pairs))
    }

    fn string(&mut self) -> JsonResult<String> {
        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()?),
                c if c <= '\u{1f}' => return Err(self.error("control character in string")),
                c => out.push(c),
            }
        }
    }

    fn escape(&mut self) -> JsonResult<char> {
        match self.bump().ok_or_else(|| self.error("unterminated escape"))? {
            '"' => Ok('"'),
            '\\' => Ok('\\'),
            '/' => Ok('/'),
            'b' => Ok('\u{08}'),
            'f' => Ok('\u{0c}'),
            'n' => Ok('\n'),
            'r' => Ok('\r'),
            't' => Ok('\t'),
            'u' => self.unicode_escape(),
            c => Err(self.error(format!("invalid escape '\\{c}'"))),
        }
    }

    fn unicode_escape(&mut self) -> JsonResult<char> {
        let first = self.hex4()?;

        // Decode UTF-16 surrogate pairs when present.
        let code = if (0xd800..=0xdbff).contains(&first) {
            let saved = self.pos;
            if self.bump() != Some('\\') || self.bump() != Some('u') {
                return Err(self.at(saved, "missing low surrogate"));
            }

            let second = self.hex4()?;
            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(code).ok_or_else(|| self.error("invalid unicode scalar"))
    }

    fn hex4(&mut self) -> JsonResult<u32> {
        let start = self.pos;
        let mut value = 0;

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

        Ok(value)
    }

    fn number(&mut self) -> JsonResult<String> {
        let start = self.pos;

        self.take_if('-');

        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.take_if('.') {
            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' | 'E')) {
            self.bump();
            self.take_if('+') || self.take_if('-');

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

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

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

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

    fn expect(&mut self, expected: char) -> JsonResult<()> {
        match self.bump() {
            Some(c) if c == expected => Ok(()),
            _ => Err(self.error(format!("expected '{expected}'"))),
        }
    }

    fn take_if(&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 {
        self.at(self.pos, message)
    }

    fn at(&self, pos: usize, message: impl Into<String>) -> JsonError {
        JsonError {
            pos,
            message: message.into(),
        }
    }
}

fn pretty_print(value: &Json) -> String {
    let mut out = String::new();
    write_pretty(value, 0, &mut out).expect("writing to a string cannot fail");
    out
}

fn write_pretty(value: &Json, depth: usize, out: &mut String) -> fmt::Result {
    match value {
        Json::Null => out.push_str("null"),
        Json::Bool(value) => out.push_str(if *value { "true" } else { "false" }),
        Json::Number(value) => out.push_str(value),
        Json::String(value) => write_string(value, out)?,
        Json::Array(values) => {
            if values.is_empty() {
                out.push_str("[]");
            } else {
                out.push_str("[\n");
                for (i, value) in values.iter().enumerate() {
                    indent(depth + 1, out);
                    write_pretty(value, depth + 1, out)?;
                    if i + 1 != values.len() {
                        out.push(',');
                    }
                    out.push('\n');
                }
                indent(depth, out);
                out.push(']');
            }
        }
        Json::Object(pairs) => {
            if pairs.is_empty() {
                out.push_str("{}");
            } else {
                out.push_str("{\n");
                for (i, (key, value)) in pairs.iter().enumerate() {
                    indent(depth + 1, out);
                    write_string(key, out)?;
                    out.push_str(": ");
                    write_pretty(value, depth + 1, out)?;
                    if i + 1 != pairs.len() {
                        out.push(',');
                    }
                    out.push('\n');
                }
                indent(depth, out);
                out.push('}');
            }
        }
    }

    Ok(())
}

fn write_string(value: &str, out: &mut String) -> fmt::Result {
    out.push('"');

    for c in value.chars() {
        match c {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\u{08}' => out.push_str("\\b"),
            '\u{0c}' => out.push_str("\\f"),
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            c if c <= '\u{1f}' => write!(out, "\\u{:04x}", c as u32)?,
            c => out.push(c),
        }
    }

    out.push('"');
    Ok(())
}

fn indent(depth: usize, out: &mut String) {
    for _ in 0..depth {
        out.push_str("  ");
    }
}

fn run() -> Result<(), String> {
    let mut input = String::new();
    io::stdin()
        .read_to_string(&mut input)
        .map_err(|err| format!("failed to read stdin: {err}"))?;

    let json = Parser::new(&input)
        .parse()
        .map_err(|err| format!("JSON parse error at byte {}: {}", err.pos, err.message))?;

    println!("{}", pretty_print(&json));
    Ok(())
}

fn main() {
    if let Err(err) = run() {
        eprintln!("{err}");
        process::exit(1);
    }

    // Avoid surprising unused-argument warnings in simple `rustc` builds.
    let _ = env::args_os;
}

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

    fn format(input: &str) -> String {
        let json = Parser::new(input).parse().unwrap();
        pretty_print(&json)
    }

    #[test]
    fn pretty_prints_nested_json() {
        let input = r#"{"name":"Ada","nums":[1,true,null,{"x":-2.5e+3}],"empty":[]}"#;
        let expected = r#"{
  "name": "Ada",
  "nums": [
    1,
    true,
    null,
    {
      "x": -2.5e+3
    }
  ],
  "empty": []
}"#;

        assert_eq!(format(input), expected);
    }

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

        assert_eq!(format(input), expected);
    }

    #[test]
    fn rejects_trailing_characters() {
        assert!(Parser::new("true false").parse().is_err());
    }
}