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)>),
}

struct Parser {
    chars: Vec<char>,
    pos: usize,
}

impl Parser {
    fn new(input: &str) -> Self {
        Self {
            chars: input.chars().collect(),
            pos: 0,
        }
    }

    fn parse(mut self) -> Result<Json, String> {
        let value = self.value()?;
        self.ws();
        if self.pos == self.chars.len() {
            Ok(value)
        } else {
            Err(format!("unexpected character at {}", self.pos))
        }
    }

    fn value(&mut self) -> Result<Json, String> {
        self.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(c) => Err(format!("unexpected '{}' at {}", c, self.pos)),
            None => Err("unexpected end of input".into()),
        }
    }

    fn literal(&mut self, text: &str, value: Json) -> Result<Json, String> {
        for expected in text.chars() {
            if self.bump() != Some(expected) {
                return Err(format!("expected {}", text));
            }
        }
        Ok(value)
    }

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

        let mut items = Vec::new();
        if self.peek() == Some(']') {
            self.bump();
            return Ok(Json::Array(items));
        }

        loop {
            items.push(self.value()?);
            self.ws();
            match self.bump() {
                Some(',') => continue,
                Some(']') => return Ok(Json::Array(items)),
                _ => return Err(format!("expected ',' or ']' at {}", self.pos)),
            }
        }
    }

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

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

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

            self.ws();
            match self.bump() {
                Some(',') => continue,
                Some('}') => return Ok(Json::Object(pairs)),
                _ => return Err(format!("expected ',' or '}}' at {}", self.pos)),
            }
        }
    }

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

        while let Some(c) = self.bump() {
            match c {
                '"' => return Ok(out),
                '\\' => out.push(self.escape()?),
                c if c <= '\u{1f}' => return Err("control character in string".into()),
                c => out.push(c),
            }
        }

        Err("unterminated string".into())
    }

    fn escape(&mut self) -> Result<char, String> {
        match self.bump() {
            Some('"') => Ok('"'),
            Some('\\') => Ok('\\'),
            Some('/') => Ok('/'),
            Some('b') => Ok('\u{08}'),
            Some('f') => Ok('\u{0c}'),
            Some('n') => Ok('\n'),
            Some('r') => Ok('\r'),
            Some('t') => Ok('\t'),
            Some('u') => self.unicode_escape(),
            _ => Err(format!("bad escape at {}", self.pos)),
        }
    }

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

        // Combine UTF-16 surrogate pairs when they appear in escaped form.
        if (0xD800..=0xDBFF).contains(&first) {
            if self.bump() != Some('\\') || self.bump() != Some('u') {
                return Err("missing low surrogate".into());
            }
            let second = self.hex4()?;
            if !(0xDC00..=0xDFFF).contains(&second) {
                return Err("invalid low surrogate".into());
            }
            let code = 0x10000 + (((first - 0xD800) << 10) | (second - 0xDC00));
            char::from_u32(code).ok_or_else(|| "invalid unicode escape".into())
        } else {
            char::from_u32(first).ok_or_else(|| "invalid unicode escape".into())
        }
    }

    fn hex4(&mut self) -> Result<u32, String> {
        let mut n = 0;
        for _ in 0..4 {
            n = n * 16
                + self
                    .bump()
                    .and_then(|c| c.to_digit(16))
                    .ok_or_else(|| "expected four hex digits".to_string())?;
        }
        Ok(n)
    }

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

        if self.peek() == Some('-') {
            self.bump();
        }

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

        if self.peek() == Some('.') {
            self.bump();
            if !matches!(self.peek(), Some('0'..='9')) {
                return Err(format!("bad fraction at {}", self.pos));
            }
            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(format!("bad exponent at {}", self.pos));
            }
            while matches!(self.peek(), Some('0'..='9')) {
                self.bump();
            }
        }

        Ok(Json::Number(self.chars[start..self.pos].iter().collect()))
    }

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

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

    fn peek(&self) -> Option<char> {
        self.chars.get(self.pos).copied()
    }

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

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

fn write_json(json: &Json, indent: usize, out: &mut String) {
    match json {
        Json::Null => out.push_str("null"),
        Json::Bool(v) => out.push_str(if *v { "true" } else { "false" }),
        Json::Number(n) => out.push_str(n),
        Json::String(s) => write_string(s, out),
        Json::Array(items) => {
            if items.is_empty() {
                out.push_str("[]");
                return;
            }

            out.push('[');
            for (i, item) in items.iter().enumerate() {
                out.push('\n');
                spaces(indent + 2, out);
                write_json(item, indent + 2, out);
                if i + 1 != items.len() {
                    out.push(',');
                }
            }
            out.push('\n');
            spaces(indent, out);
            out.push(']');
        }
        Json::Object(pairs) => {
            if pairs.is_empty() {
                out.push_str("{}");
                return;
            }

            out.push('{');
            for (i, (key, value)) in pairs.iter().enumerate() {
                out.push('\n');
                spaces(indent + 2, out);
                write_string(key, out);
                out.push_str(": ");
                write_json(value, indent + 2, out);
                if i + 1 != pairs.len() {
                    out.push(',');
                }
            }
            out.push('\n');
            spaces(indent, out);
            out.push('}');
        }
    }
}

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{08}' => out.push_str("\\b"),
            '\u{0c}' => out.push_str("\\f"),
            c if c <= '\u{1f}' => out.push_str(&format!("\\u{:04x}", c as u32)),
            c => out.push(c),
        }
    }
    out.push('"');
}

fn spaces(count: usize, out: &mut String) {
    for _ in 0..count {
        out.push(' ');
    }
}

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::pretty_print;

    #[test]
    fn pretty_prints_nested_values() {
        let input = r#"{"ok":true,"items":[1,null,"two\nlines"]}"#;
        let expected = "{\n  \"ok\": true,\n  \"items\": [\n    1,\n    null,\n    \"two\\nlines\"\n  ]\n}";
        assert_eq!(pretty_print(input).unwrap(), expected);
    }

    #[test]
    fn rejects_trailing_input() {
        assert!(pretty_print(r#"{"a":1} false"#).is_err());
    }
}