Viết Reminder Parser dùng Rust

Khi dùng Google Calendar hoặc Reminder.app của macOS, mình rất thích chức năng tạo nhanh một event bằng cách nhập vào nội dung một cách tự nhiên như khi đang nói, ví dụ:

get hair cut at 10am every Sunday

hoặc là

doctor appointment at 1pm on Monday

Khi nhận được input như này, một event mới sẽ được tạo ra với ngày và giờ tương ứng, còn nội dung của event sẽ là phần text mở đầu, ví dụ "get hair cut", hoặc "doctor appointment".

Thường thì cái gì mình thích, mình sẽ tìm cách clone lại, chức năng này cũng ko ngoại lệ.

Vì bài viết này là phần tiếp theo của bài viết trước, chúng ta sẽ tiếp tục dùng Rust và Nom. Recommend các bạn đọc kĩ phần trước, và chuẩn bị những kiến thức cơ bản của Rust, nhất là về Result, Option, cargo test, trước khi đọc tiếp bài này.

Các bạn cũng có thể tham khảo code implementation hoàn chỉnh tại Github trước khi bắt đầu: https://github.com/huytd/reminder-parser

Phân tích cú pháp

Đây không phải là cú pháp mà Google Calendar hay Reminder.app sử dụng, nhưng đây sẽ là cú pháp chúng ta sẽ dùng trong bài viết này, đơn giản là vì nó... đơn giản

Cấu trúc của một event input là một tổ hợp của nhiều token như sau:

Trong đó:

<event-text> là nội dung của event cần tạo.
<time> là thời gian diễn ra event, có thể nhập thời gian ở 2 dạng: at 10pm hoặc 11:32. Từ khóa "at" có thể được bỏ đi, phần meridiem indicator ("am" hoặc "pm") cũng là optional.

Một token <time> sẽ có dạng:
```
time = ?"at" + hour + ?(":" + minutes) + ?("am"|"pm")
```
Nếu chỉ có giá trị giờ (hour) mà không có phút (minutes) thì mặc định sẽ là 00 phút.
<repeat> và <date>: Hai token này đi chung với nhau vì đôi lúc, những event sẽ lặp lại định kỳ (ví dụ nhắc trả bill hàng tháng, ví dụ every 15th), cũng có thể chỉ diễn ra một lần (on Monday), giá trị on hoặc every sẽ được dùng để xác định token <repeat>.
```
date = ?("on"|"every") + date
```

Để cho đơn giản thì chúng ta sẽ tạm bỏ qua việc xác thực nội dung nhập vào, nên những case như thế này vẫn sẽ được chấp nhận:

32:42 pm
hoặc
24:59

Trên thực tế, validation cũng không phải là nhiệm vụ của parser.

Thuật toán parse event

Vậy ta sẽ parse nội dung như thế nào sau khi đã xác định được 3 thành phần trên?

Thuật toán parse của chúng ta sẽ duyệt từng kí tự từ đầu đến cuối string, và tìm cách parse ra từng token.

Chạy từ đầu input cho đến trước khi ta gặp phần tử đầu tiên của một <time> token, lưu tất cả kí tự đã gặp lại:

Tiếp theo, khi bắt gặp phần tử đầu tiên của <time> token (là chữ "at"), cho đến cuối (là khi đọc được phần meridiem indicator "am" hoặc "pm") ta sẽ bắt đầu quá tình parse <time> token.

Sau khi xác định xong <time> token, đi tiếp và nếu gặp "on" hoặc "every", ta sẽ bắt đầu parse <date> token.

Sau khi đã xác định được <time> token và <date> token, thì phần nội dung chúng ta đã lưu lại từ đầu chính là <event-text>. Đến lúc này ta hoàn tất quá trình parse.

Implementation

Xác định xong cú pháp và thuật toán là coi như giải quyết xong 75% bài toán rồi, ~~95% còn lại nằm ở việc đánh nhau với Rust~~ bây giờ ta implement thôi.

Việc đầu tiên là define ra cấu trúc dữ liệu cho kết quả sau khi parse, ta sẽ gọi nó là ReminderEvent:

struct ReminderEvent<'a> {
    text: String,
    date: ReminderDate<'a>,
    time: ReminderTime<'a>
}

Trường text là nội dung của event, kiểu dữ liệu cho date và time lần lượt sẽ là:

struct ReminderDate<'a> {
    content: &'a str,
    repeated: bool
}

struct ReminderTime<'a> {
    hour: &'a str,
    minute: &'a str,
    meridiem: bool
}

Một ReminderDate sẽ chứa content là một chuỗi thô chưa qua xử lý, ví dụ như "Tuesday", "14/12". Bao giờ cần xài thì parse tiếp sau, trong bài viết này mình sẽ lưu raw. Nếu đây là một event diễn ra định kì (có chữ "every" khi parse date), thì trường repeated sẽ là true.

Một ReminderTime chứa các giá trị giờ / phút dưới dạng chuỗi thô, giá trị meridiem indicator sẽ được lưu trong trường meridiem, vì nó có thể có, có thể không tồn tại trong input, mặc định sẽ là true cho "am", và false cho "pm".

Vì các giá trị raw được lưu dưới dạng string slice &str, tham chiếu trực tiếp từ input, bản thân Rust compiler không tự suy ra được lifetime cho các giá trị này, nên ta phải tự annotate bằng <'a>.

Tiếp theo, kế hoạch thực hiện sẽ là:

Viết hàm parse ReminderTime
Viết hàm parse ReminderDate
Sau đó kết hợp 2 hàm này để viết hàm parse ReminderEvent

Hàm parse `ReminderTime`

Ở bài trước ta đã biết, một parser dùng Nom sẽ có dạng fn(&str) -> IResult, hàm parse_time của chúng ta cũng sẽ có dạng như thế:

fn parse_time(input: &str) -> IResult<&str, ReminderTime> {
    // tbd
}

Trước khi bắt tay vào code, mình có thói quen viết trước một vài test case, để khi implement chúng ta sẽ biết được mình có đi đúng hướng hay không. "Má, chém gió vl! " — Bình luận từ đồng nghiệp của tác giả Đây là một thói quen tốt, các bạn cũng nên làm như vậy, tốn time chút nhưng hiệu quả.

#[test]
fn test_parse_time() {
    let test_times = [
        ("at 11:00", Ok(("11", "00", true))),
        ("at 10pm", Ok(("10", "00", false))),
        ("at 12:13 am", Ok(("12", "13", true))),
        ("13:42pm", Ok(("13", "42", false))),
        ("15:30", Ok(("15", "30", true))),
        ("at 5", Ok(("5", "00", true))),
        ("32:412", Ok(("32", "412", true))),
        ("at 32:281am", Ok(("32", "281", true))),
        ("at 32pm", Ok(("32", "00", false))),
        ("night time", Err(())),
        ("at night", Err(())),
    ];

    for test_case in test_times {
        let result = parse_time(test_case.0);
        if test_case.1.is_ok() {
            let (_, actual) = result.unwrap();
            let expected = test_case.1.unwrap();
            assert_eq!(actual.hour, expected.0);
            assert_eq!(actual.minute, expected.1);
            assert_eq!(actual.meridiem, expected.2);
        } else {
            assert!(result.is_err());
        }
    }
}

Trong hàm test_parse_time() ở trên, ta tạo một mảng test_times chứa tập các tuple dạng (input, expected_result). Trong đó, các input là các string mà trên thực tế sẽ được nhập vào từ phía user, expected_result là một giá trị kiểu Result, nếu nó là giá trị Ok(...) có nghĩa là input này parse được, còn giá trị Err() là trường hợp lỗi. Mỗi giá trị Ok(...) sẽ có dạng (hour, minute, meridiem). Trong vòng lặp tiếp theo của hàm test, ta duyệt qua từng test case, lấy ra giá trị thực tế actual từ parser (kiểu ReminderTime) và so sánh nó với từng giá trị trong tuple test.

Phương pháp này không có gì mới, bên Golang gọi là table driven testing.

Có test rồi thì ta có thể implement được rồi, quay lại hàm parse_time, việc đầu tiên là dùng các combinator của nom để đọc input, nhắc lại cú pháp của <time> token:

time = ?"at" + hour + ?(":" + minutes) + ?("am"|"pm")

Trước khi đi vào giải thích, đây là hàm parse_time hoàn chỉnh:

fn parse_time(input: &str) -> IResult<&str, ReminderTime> {
    let (remain, (_, _, hour, opt_min, _, am)) = tuple((
        opt(tag("at")),
        multispace0,
        digit1,
        opt(tuple((tag(":"), digit1))),
        multispace0,
        opt(alt((tag("am"), tag("pm")))),
    ))
    .parse(input)?;

    let (_, minute) = opt_min.unwrap_or(("", "00"));
    let meridiem = am == Some("am") || am == None;

    Ok((remain, ReminderTime { hour, minute, meridiem }))
}

Để đọc chuỗi "at", ta có thể dùng hàm tag() của nom, vì "at" có thể có hoặc không xuất hiện trong input, ta dùng hàm opt() để cho nom biết nó là một giá trị optional.

opt(tag("at"))

Tiếp sau "at" là một hoặc nhiều kí tự space, ta dùng multispace0 để xác định nó. Sau đó là hour, cấu thành từ một hoặc nhiều kí tự số, ta dùng digit1 để parse.

Phần giá trị phút minute, thường sẽ đi sau hour, cách nhau bằng một kí tự ':', nó cũng là optional.

opt(tuple(tag(":"), digit1))

Tiếp theo lại là một mớ khoảng trắng nếu có, tiếp tục dùng multispace0.

Cuối cùng là phần meridiem indicator, có thể có hoặc không, ta dùng hàm alt() để parse lấy một trong 2 giá trị tag("am") và tag("pm").

opt(alt((tag("am"), tag("pm"))))

Các giá trị sau khi parse được lưu vào một tuple, mỗi phần tử của tuple sẽ được gán với một biến, lần lượt là remain, hour, opt_min, am. Trong đó remain là phần chuỗi còn sót lại sau quá trình parse.

Vì phần minute là một giá trị optional, kiểu Option, ta cần một bước hậu xử lý để nếu nó là None thì mặc định nó thành giá trị "00".

let (_, minute) = opt_min.unwrap_or(("", "00"));

Tương tự, giá trị am cũng là optional, nhưng ta sẽ có 2 trường hợp: Hoặc nó là Some("am"), hoặc nó là None, nếu đúng thì giá trị meridiem của kết quả trả về sẽ là true, ngược lại nó là false.

let meridiem = am == Some("am") || am == None;

Cuối cùng, nếu mọi thứ ok hết, ta tạo ra một object ReminderTime từ các giá trị đã được xử lý ở trên, và trả về kết quả.

Chạy thử hàm test, ta sẽ thấy mọi thứ đều pass hết, lý do không phải vì test lụi, mà là vì chúng ta code xịn, chả có mấy khi, cứ tự tin lên.

running 1 test
test test_parse_time ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Hàm parse `ReminderDate`

Tiếp theo là hàm parse parse_date, như trên, ta cũng bắt đầu bằng:

fn parse_date(input: &str) -> IResult<&str, ReminderDate> {
}

Và tiếp theo là viết hàm test_parse_date():

#[test]
fn test_parse_date() {
    let test_cases: [(&str, Result<(&str, bool), ()>); 8] = [
        (" every Sunday", Ok(("Sunday", true))),
        ("every Monday", Ok(("Monday", true))),
        ("on Tuesday ", Ok(("Tuesday", false))),
        ("tomorrow", Ok(("tomorrow", false))),
        ("today", Ok(("today", false))),
        ("on 08/25", Ok(("08/25", false))),
        ("every 3rd", Ok(("3rd", true))),
        ("", Ok(("today", false)))
    ];

    for test_case in test_cases {
        let result = parse_date(test_case.0);
        if test_case.1.is_ok() {
            let (_, actual) = result.unwrap();
            let expected = test_case.1.unwrap();
            assert_eq!(actual.content, expected.0);
            assert_eq!(actual.repeated, expected.1);
        } else {
            assert!(result.is_err());
        }
    }
}

Khỏi cần giải thích dài dòng, cơ bản vì mình lười viết, nên để phần này cho các bạn tự suy luận

Implement đầy đủ của hàm parse_date như sau:

fn parse_date(input: &str) -> IResult<&str, ReminderDate> {
    let (remain, (_, opt_repeat, _, date)) = tuple((
        multispace0,
        opt(alt((value(true, tag("every")), value(false, tag("on"))))),
        multispace0,
        rest
    ))
    .parse(input)?;

    let repeated = opt_repeat.unwrap_or(false);
    let content = if date.trim().is_empty() { "today" } else { date.trim() };

    Ok((remain, ReminderDate { content, repeated }))
}

Như đã viết ở trên, cú pháp của <date> token là:

date = ?("on"|"every") + date

Khá đơn giản, vì phần <date> nằm sau phần <time> token, hai phần này ngăn cách với nhau bằng một hoặc nhiều khoảng trắng, ta dùng multispace0 để parse các khoảng trắng này.

Tiếp theo, để vì nội dung mở đầu của <date> là "on" hoặc "every", thay vì lấy luôn giá trị raw của chúng dưới dạng string, ta có thể map các giá trị này thành một giá trị kiểu boolean, và dùng luôn giá trị đó để xác định thuộc tính repeated của <date> token. Ta dùng hàm value() để map giá trị "on" thành false, và "every" thành true. Vì phần "on" || "every" là optional, ta wrap biểu thức trên bằng opt().

opt(alt((value(true, tag("every")), value(false, tag("on")))))

Sau đó là bước hậu xử lý, giá trị repeat sau khi parse sẽ có 2 trường hợp: Some(true|false) hoặc None, nếu giá trị trả về là None, ta có thể mặc định nó thành false.

Phần còn lại của input sẽ là phần ReminderDate.content, chúng ta chỉ việc lấy ra dưới dạng raw string, xài rest combinator để lấy toàn bộ ra. Nếu phần content là một chuỗi rỗng (empty), thì ta sẽ mặc định nó thành "today".

Cuối cùng là khởi tạo object ReminderDate rồi trả về kết quả.

Lại tiếp tục chạy test để thấy khả năng code thần sầu của tác giả:

running 1 test
test test_parse_date ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 1 filtered out; finished in 0.00s

Như vậy, chúng ta đã hoàn thành 2 building block quan trọng đó là parse_time() và parse_date() để xác định được <time> và <date> token. Bước cuối cùng là kết hợp 2 parser này và parse nội dung input hoàn chỉnh.

Hàm parse `ReminderEvent`

Xem lại cú pháp của một input event hoàn chỉnh:

<event-text> <time> <repeat> <date>

Đến đây hẳn các bạn cũng đoán được logic của hàm parse_event(), nhưng mà khoan đã, việc đầu tiên là define ra cái hàm:

fn parse_event(input: &str) -> IResult<&str, ReminderEvent> {
}

Và viết test:

#[test]
fn test_parse_event() {
    let test_events: [(&str, Result<(&str, &str, &str, bool, &str, bool), ()>); 10] = [
        ("go feed the fish at 10am", Ok(("go feed the fish", "10", "00", true, "today", false))),
        ("feed the fish at 10:00am", Ok(("feed the fish", "10", "00", true, "today", false))),
        ("walk the dog 10:00am today", Ok(("walk the dog", "10", "00", true, "today", false))),
        ("feed the cat at 4 tomorrow", Ok(("feed the cat", "4", "00", true, "tomorrow", false))),
        ("get haircut at 14:24 pm", Ok(("get haircut", "14", "24", false, "today", false))),
        ("credit card pay at 8am", Ok(("credit card pay", "8", "00", true, "today", false))),
        ("credit card pay at 8:00 every 20th", Ok(("credit card pay", "8", "00", true, "20th", true))),
        ("cafe with Justin at Ginza at 6 on 08/23", Ok(("cafe with Justin at Ginza", "6", "00", true, "08/23", false))),
        ("pick up books at library at 10am every Sunday", Ok(("pick up books at library", "10", "00", true, "Sunday", true))),
        ("lorem ipsum doro tata", Err(()))
    ];

    for test_case in test_events {
        let result = parse_event(test_case.0);
        if test_case.1.is_ok() {
            let (_, actual) = result.unwrap();
            let expected = test_case.1.unwrap();
            assert_eq!(actual.text, expected.0);
            assert_eq!(actual.time.hour, expected.1);
            assert_eq!(actual.time.minute, expected.2);
            assert_eq!(actual.time.meridiem, expected.3);
            assert_eq!(actual.date.content, expected.4);
            assert_eq!(actual.date.repeated, expected.5);
        } else {
            assert!(result.is_err());
        }
    }
}

Mảng test_events chứa các tuple có cấu trúc dạng:

(input, Result<(event_text, hour, minute, meridiem, date, repeated)>)

Trong đó input là nội dung event input sẽ được nhập vào từ user, và các field trong Result sẽ là các field tương ứng của object ReminderEvent, ReminderTime và ReminderDate.

Bằng việc kết hợp các hàm parse_time() và parse_date(), ta có thể implement hàm parse_event() một cách rất đơn giản:

fn parse_event(input: &str) -> IResult<&str, ReminderEvent> {
    let (input, (vtask, (time, date))) =
        many_till(anychar, pair(parse_time, parse_date)).parse(input)?;
    let text = vtask
        .iter()
        .map(|c| c.to_string())
        .collect::<Vec<String>>()
        .join("")
        .trim()
        .to_string();
    Ok((input, ReminderEvent { text, time, date }))
}

Ta dùng combinator tên là many_till(anychar, ...) để lấy tất cả các kí tự xuất hiện trong input, cho đến khi parse được <time> hay <date> token.

Giá trị trả về của many_till là một vector chứa nhiều kí tự Vec<char>, việc còn lại chỉ là join() chúng lại để thu về một giá trị kiểu String.

Cuối cùng, chạy lại toàn bộ test:

running 3 tests
test test_parse_date ... ok
test test_parse_time ... ok
test test_parse_event ... ok

test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Như vậy chúng ta đã hoàn thành việc build một parser hết sức đơn giản, để parse một input event dưới dạng ngôn ngữ tự nhiên thành một data struct hoàn chỉnh. Từ đây ta có thể xây dựng được những ứng dụng triệu đô, dư sức cạnh tranh với Google Calendar hay Reminder.app (tự tin không ai đánh thuế mà).

Input:

"write new blog post at 9am every 14th Dec"

Output:

ReminderEvent{
   text: "write new blog post",
   date: ReminderDate{
      content: "14th Dec",
      repeated: true
   },
   time: ReminderTime{
      hour: "9",
      minute: "00",
      meridiem: true
   }
}

Hy vọng vẫn có bạn đọc xuống được đến tận đây mà không drop giữa chừng và hy vọng bài viết này giúp các bạn hiểu rõ hơn về Nom Parser, cũng như kĩ thuật Parser Combination. Lần tới, khi cần parse một nội dung gì đó, thay vì đâm đầu vào sử dụng RegEx, hãy thử chậm lại một tí và sử dụng Nom hay một thư viện Parser Combination nào đó để build, mình nghĩ ngoài đồng nghiệp ra, thì chính bạn trong tương lai sẽ rất cảm kích cái quyết định đó của bản thân. Chúc các bạn may mắn

Hẹn gặp lại các bạn trong các bài viết tiếp theo.