Вправа: Розбір Protobuf

У цій вправі ви створите синтаксичний аналізатор для бінарного кодування protobuf. Не хвилюйтеся, це простіше, ніж здається! Це ілюструє загальну схему синтаксичного аналізу, передаючи зрізи даних. Самі дані ніколи не копіюються.

Повноцінний розбір повідомлення protobuf вимагає знання типів полів, проіндексованих за номерами полів. Зазвичай ця інформація міститься у файлі proto. У цій вправі ми закодуємо цю інформацію у оператори match у функціях, які викликаються для кожного поля.

Ми використаємо наступний proto:

message PhoneNumber {
  optional string number = 1;
  optional string type = 2;
}

message Person {
  optional string name = 1;
  optional int32 id = 2;
  repeated PhoneNumber phones = 3;
}

Messages

A proto message is encoded as a series of fields, one after the next. Each is implemented as a "tag" followed by the value. The tag contains a field number (e.g., 2 for the id field of a Person message) and a wire type defining how the payload should be determined from the byte stream. These are combined into a single integer, as decoded in unpack_tag below.

Varint

Integers, including the tag, are represented with a variable-length encoding called VARINT. Luckily, parse_varint is defined for you below.

Wire Types

Proto defines several wire types, only two of which are used in this exercise.

The Varint wire type contains a single varint, and is used to encode proto values of type int32 such as Person.id.

The Len wire type contains a length expressed as a varint, followed by a payload of that number of bytes. This is used to encode proto values of type string such as Person.name. It is also used to encode proto values containing sub-messages such as Person.phones, where the payload contains an encoding of the sub-message.

Вправа

The given code also defines callbacks to handle Person and PhoneNumber fields, and to parse a message into a series of calls to those callbacks.

Вам залишається реалізувати функцію parse_field та трейт ProtoMessage для Person та PhoneNumber.

/// wire type як він приходить по дроту.
enum WireType {
    /// Varint WireType вказує на те, що значення є одним VARINT.
    Varint,
    // The I64 WireType indicates that the value is precisely 8 bytes in
    // little-endian order containing a 64-bit signed integer or double type.
    //I64,  -- not needed for this exercise
    /// The Len WireType indicates that the value is a length represented as a
    /// VARINT followed by exactly that number of bytes.
    Len,
    // Тип WireType I32 вказує на те, що значення - це рівно 4 байти в
    // little-endian порядку, що містять 32-бітне ціле число зі знаком або тип з плаваючою комою.
    //I32,  -- не потрібно для цієї вправи
}

#[derive(Debug)]
/// Значення поля, введене на основі wire type.
enum FieldValue<'a> {
    Varint(u64),
    //I64(i64),  -- не потрібно для цієї вправи
    Len(&'a [u8]),
    //I32(i32),  -- не потрібно для цієї вправи
}

#[derive(Debug)]
/// Поле, що містить номер поля та його значення.
struct Field<'a> {
    field_num: u64,
    value: FieldValue<'a>,
}

trait ProtoMessage<'a>: Default {
    fn add_field(&mut self, field: Field<'a>);
}

impl From<u64> for WireType {
    fn from(value: u64) -> Self {
        match value {
            0 => WireType::Varint,
            //1 => WireType::I64,  -- не потрібно для цієї вправи
            2 => WireType::Len,
            //5 => WireType::I32,  -- не потрібно для цієї вправи
            _ => panic!("Неправильний wire type: {value}"),
        }
    }
}

impl<'a> FieldValue<'a> {
    fn as_str(&self) -> &'a str {
        let FieldValue::Len(data) = self else {
            panic!("Очікуваний рядок має бути полем `Len`");
        };
        std::str::from_utf8(data).expect("Неправильний рядок")
    }

    fn as_bytes(&self) -> &'a [u8] {
        let FieldValue::Len(data) = self else {
            panic!("Очікувані байти мають бути полем `Len`");
        };
        data
    }

    fn as_u64(&self) -> u64 {
        let FieldValue::Varint(value) = self else {
            panic!("Очікувалося, що `u64` буде полем `Varint`");
        };
        *value
    }
}

/// Розбір VARINT з поверненням розібраного значення та решти байтів.
fn parse_varint(data: &[u8]) -> (u64, &[u8]) {
    for i in 0..7 {
        let Some(b) = data.get(i) else {
            panic!("Недостатньо байт для varint");
        };
        if b & 0x80 == 0 {
            // Це останній байт VARINT, тому перетворюємо його
            // в u64 і повертаємо.
            let mut value = 0u64;
            for b in data[..=i].iter().rev() {
                value = (value << 7) | (b & 0x7f) as u64;
            }
            return (value, &data[i + 1..]);
        }
    }

    // Більше 7 байт є неприпустимим.
    panic!("Забагато байт для varint");
}

/// Перетворити тег у номер поля та WireType.
fn unpack_tag(tag: u64) -> (u64, WireType) {
    let field_num = tag >> 3;
    let wire_type = WireType::from(tag & 0x7);
    (field_num, wire_type)
}


/// Розбір поля з поверненням залишку байтів
fn parse_field(data: &[u8]) -> (Field, &[u8]) {
    let (tag, remainder) = parse_varint(data);
    let (field_num, wire_type) = unpack_tag(tag);
    let (fieldvalue, remainder) = match wire_type {
        _ => todo!("На основі wire type побудуйте Field, використовуючи стільки байт, скільки потрібно.")
    };
    todo!("Повернути поле та всі невикористані байти.")
}

/// Розбір повідомлення за заданими даними, викликаючи `T::add_field` для кожного поля в
/// повідомленні.
///
/// Споживаються всі вхідні дані.
fn parse_message<'a, T: ProtoMessage<'a>>(mut data: &'a [u8]) -> T {
    let mut result = T::default();
    while !data.is_empty() {
        let parsed = parse_field(data);
        result.add_field(parsed.0);
        data = parsed.1;
    }
    result
}

#[derive(Debug, Default)]
struct PhoneNumber<'a> {
    number: &'a str,
    type_: &'a str,
}

#[derive(Debug, Default)]
struct Person<'a> {
    name: &'a str,
    id: u64,
    phone: Vec<PhoneNumber<'a>>,
}

// TODO: Реалізувати ProtoMessage для Person та PhoneNumber.

fn main() {
    let person_id: Person = parse_message(&[0x10, 0x2a]);
    assert_eq!(person_id, Person { name: "", id: 42, phone: vec![] });

    let person_name: Person = parse_message(&[
        0x0a, 0x0e, 0x62, 0x65, 0x61, 0x75, 0x74, 0x69, 0x66, 0x75, 0x6c, 0x20,
        0x6e, 0x61, 0x6d, 0x65,
    ]);
    assert_eq!(person_name, Person { name: "beautiful name", id: 0, phone: vec![] });

    let person_name_id: Person =
        parse_message(&[0x0a, 0x04, 0x45, 0x76, 0x61, 0x6e, 0x10, 0x16]);
    assert_eq!(person_name_id, Person { name: "Evan", id: 22, phone: vec![] });

    let phone: Person = parse_message(&[
        0x0a, 0x00, 0x10, 0x00, 0x1a, 0x16, 0x0a, 0x0e, 0x2b, 0x31, 0x32, 0x33,
        0x34, 0x2d, 0x37, 0x37, 0x37, 0x2d, 0x39, 0x30, 0x39, 0x30, 0x12, 0x04,
        0x68, 0x6f, 0x6d, 0x65,
    ]);
    assert_eq!(
        phone,
        Person {
            name: "",
            id: 0,
            phone: vec![PhoneNumber { number: "+1234-777-9090", type_: "home" },],
        }
    );

    // Put that all together into a single parse.
    let person: Person = parse_message(&[
        0x0a, 0x07, 0x6d, 0x61, 0x78, 0x77, 0x65, 0x6c, 0x6c, 0x10, 0x2a, 0x1a,
        0x16, 0x0a, 0x0e, 0x2b, 0x31, 0x32, 0x30, 0x32, 0x2d, 0x35, 0x35, 0x35,
        0x2d, 0x31, 0x32, 0x31, 0x32, 0x12, 0x04, 0x68, 0x6f, 0x6d, 0x65, 0x1a,
        0x18, 0x0a, 0x0e, 0x2b, 0x31, 0x38, 0x30, 0x30, 0x2d, 0x38, 0x36, 0x37,
        0x2d, 0x35, 0x33, 0x30, 0x38, 0x12, 0x06, 0x6d, 0x6f, 0x62, 0x69, 0x6c,
        0x65,
    ]);
    assert_eq!(
        person,
        Person {
            name: "maxwell",
            id: 42,
            phone: vec![
                PhoneNumber { number: "+1202-555-1212", type_: "home" },
                PhoneNumber { number: "+1800-867-5308", type_: "mobile" },
            ]
        }
    );
}