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

#[derive(Debug, PartialEq)]
enum Json {
    Scalar(String),
    Array(Vec<Json>),
    Object(Vec<(String, Json)>),
}

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, String> {
        let value = self.parse_value()?;
        self.skip_whitespace();
        if self.pos != self.input.len() {
            return Err(format!("unexpected input at byte {}", self.pos));
        }
        Ok(value)
    }

    fn parse_value(&mut self) -> Result<Json, String> {
        self.skip_whitespace();
        match self.peek() {
            Some(b'{') => self.parse_object(),
            Some(b'[') => self.parse_array(),
            Some(b'"') => self.parse_string().map(Json::Scalar),
            Some(b'-' | b'0'..=b'9') => self.parse_number().map(Json::Scalar),
            Some(b't') => self.parse_literal("true"),
            Some(b'f') => self.parse_literal("false"),
            Some(b'n') => self.parse_literal("null"),
            Some(_) => Err(format!("unexpected character at byte {}", self.pos)),
            None => Err("unexpected end of input".into()),
        }
    }

    fn parse_array(&mut self) -> Result<Json, String> {
        self.pos += 1;
        self.skip_whitespace();

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

        loop {
            values.push(self.parse_value()?);
            self.skip_whitespace();

            if self.consume(b']') {
                break;
            }
            if !self.consume(b',') {
                return Err(format!("expected ',' or ']' at byte {}", self.pos));
            }
        }

        Ok(Json::Array(values))
    }

    fn parse_object(&mut self) -> Result<Json, String> {
        self.pos += 1;
        self.skip_whitespace();

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

        loop {
            self.skip_whitespace();
            if self.peek() != Some(b'"') {
                return Err(format!("expected string key at byte {}", self.pos));
            }
            let key = self.parse_string()?;

            self.skip_whitespace();
            if !self.consume(b':') {
                return Err(format!("expected ':' at byte {}", self.pos));
            }

            fields.push((key, self.parse_value()?));
            self.skip_whitespace();

            if self.consume(b'}') {
                break;
            }
            if !self.consume(b',') {
                return Err(format!("expected ',' or '}}' at byte {}", self.pos));
            }
        }

        Ok(Json::Object(fields))
    }

    // Strings are kept as their original JSON lexemes, preserving escapes exactly.
    fn parse_string(&mut self) -> Result<String, String> {
        let start = self.pos;
        self.pos += 1;

        while let Some(byte) = self.peek() {
            match byte {
                b'"' => {
                    self.pos += 1;
                    return Ok(self.input[start..self.pos].to_owned());
                }
                b'\\' => {
                    self.pos += 1;
                    match self.peek() {
                        Some(b'"' | b'\\' | b'/' | b'b' | b'f' | b'n' | b'r' | b't') => {
                            self.pos += 1;
                        }
                        Some(b'u') => {
                            self.pos += 1;
                            for _ in 0..4 {
                                match self.peek() {
                                    Some(b'0'..=b'9' | b'a'..=b'f' | b'A'..=b'F') => {
                                        self.pos += 1;
                                    }
                                    _ => {
                                        return Err(format!(
                                            "invalid Unicode escape at byte {}",
                                            self.pos
                                        ));
                                    }
                                }
                            }
                        }
                        _ => return Err(format!("invalid escape at byte {}", self.pos)),
                    }
                }
                0x00..=0x1f => {
                    return Err(format!("control character in string at byte {}", self.pos));
                }
                _ => self.pos += 1,
            }
        }

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

    fn parse_number(&mut self) -> Result<String, String> {
        let start = self.pos;
        self.consume(b'-');

        match self.peek() {
            Some(b'0') => {
                self.pos += 1;
                if matches!(self.peek(), Some(b'0'..=b'9')) {
                    return Err(format!("leading zero at byte {}", self.pos));
                }
            }
            Some(b'1'..=b'9') => {
                self.pos += 1;
                while matches!(self.peek(), Some(b'0'..=b'9')) {
                    self.pos += 1;
                }
            }
            _ => return Err(format!("invalid number at byte {}", self.pos)),
        }

        if self.consume(b'.') {
            let fraction_start = self.pos;
            while matches!(self.peek(), Some(b'0'..=b'9')) {
                self.pos += 1;
            }
            if self.pos == fraction_start {
                return Err(format!("missing fractional digits at byte {}", self.pos));
            }
        }

        if matches!(self.peek(), Some(b'e' | b'E')) {
            self.pos += 1;
            if matches!(self.peek(), Some(b'+' | b'-')) {
                self.pos += 1;
            }

            let exponent_start = self.pos;
            while matches!(self.peek(), Some(b'0'..=b'9')) {
                self.pos += 1;
            }
            if self.pos == exponent_start {
                return Err(format!("missing exponent digits at byte {}", self.pos));
            }
        }

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

    fn parse_literal(&mut self, literal: &str) -> Result<Json, String> {
        if self.input[self.pos..].starts_with(literal) {
            self.pos += literal.len();
            Ok(Json::Scalar(literal.to_owned()))
        } else {
            Err(format!("invalid literal at byte {}", self.pos))
        }
    }

    fn skip_whitespace(&mut self) {
        while matches!(self.peek(), Some(b' ' | b'\n' | b'\r' | b'\t')) {
            self.pos += 1;
        }
    }

    fn peek(&self) -> Option<u8> {
        self.input.as_bytes().get(self.pos).copied()
    }

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

fn write_pretty(value: &Json, depth: usize, output: &mut String) {
    let indent = |level: usize, out: &mut String| {
        for _ in 0..level * 2 {
            out.push(' ');
        }
    };

    match value {
        Json::Scalar(text) => output.push_str(text),
        Json::Array(values) if values.is_empty() => output.push_str("[]"),
        Json::Object(fields) if fields.is_empty() => output.push_str("{}"),
        Json::Array(values) => {
            output.push_str("[\n");
            for (index, item) in values.iter().enumerate() {
                indent(depth + 1, output);
                write_pretty(item, depth + 1, output);
                if index + 1 != values.len() {
                    output.push(',');
                }
                output.push('\n');
            }
            indent(depth, output);
            output.push(']');
        }
        Json::Object(fields) => {
            output.push_str("{\n");
            for (index, (key, value)) in fields.iter().enumerate() {
                indent(depth + 1, output);
                output.push_str(key);
                output.push_str(": ");
                write_pretty(value, depth + 1, output);
                if index + 1 != fields.len() {
                    output.push(',');
                }
                output.push('\n');
            }
            indent(depth, output);
            output.push('}');
        }
    }
}

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

fn main() {
    let mut input = String::new();
    if let Err(error) = io::stdin().read_to_string(&mut input) {
        eprintln!("failed to read input: {error}");
        std::process::exit(1);
    }

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

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

    #[test]
    fn formats_nested_values() {
        let input = r#"{"name":"Ada","items":[1,true,null,{}]}"#;
        let expected = r#"{
  "name": "Ada",
  "items": [
    1,
    true,
    null,
    {}
  ]
}"#;
        assert_eq!(pretty_print(input).unwrap(), expected);
    }

    #[test]
    fn rejects_trailing_commas() {
        assert!(pretty_print(r#"{"x":1,}"#).is_err());
        assert!(pretty_print("[1,2,]").is_err());
    }
}