RustでRefCellとRcを組み合わせて自己参照のパーサーを実装する
Rustのパーサーコンビネータ実装中、多次元配列のパーサコンビネータにて自分自身を再起的に呼び出せる必要がありそうなので調べていたが、後から配列パーサーのインスタンス生成時に渡したパーサーのvector変更を後から変更する方法で困っていたところ以下のドキュメントでRefCellとRcを組み合わせることで可能ということで試してみました。
https://doc.rust-jp.rs/book-ja/ch15-05-interior-mutability.html
先にcharパーサーとandパーサーの実装は以下のようになり、ここで作ったパーサーを配列パーサに渡せるようにします。
use std::cell::RefCell; use std::rc::Rc; type Parse<'a> = dyn Fn(&'a str, usize) -> (bool, usize) + 'a; pub struct Parser<'a> { pub parse: Rc<Parse<'a>> } impl <'a>Parser<'a> { pub fn new<F>(parse: F) -> Parser<'a> where F: Fn(&'a str, usize) -> (bool, usize)+ 'a {Parser { parse: Rc::new(parse)}} fn parse(&self,input: &'a str, loc: usize ) -> (bool, usize) { (self.parse)(input, loc) } } fn char_parser<'a>(c: char) -> Parser<'a> { Parser::new(move |input, loc| { match input.chars().nth(loc) { Some(d) if c == d => (true, loc + 1), _ => (false, loc) } }) } fn and_parser<'a>(parser1: Parser<'a>, parser2: Parser<'a>) -> Parser<'a> { Parser::new(move |input, loc| { match parser1.parse(input, loc) { (true, loc) => parser2.parse(input, loc), (false, loc) => (false, loc) } }) }
それから配列パーサの実装は以下のようになります。
fn array_parser<'a>(parsers: Vec<Parser<'a>>) -> Rc<RefCell<Parser<'a>>> { fn dummy_parer<'b>() -> Parser<'b>{ Parser::new(|_,loc| (false, loc)) } // 一旦ダミーを入れて初期化 let array_parser_item = Rc::new(RefCell::new(dummy_parer())); let mut parser_items = parsers.into_iter() .map(|a| Rc::new(RefCell::new(a))) .collect::<Vec<Rc<RefCell<Parser<'a>>>>>(); parser_items.push(Rc::clone(&array_parser_item)); fn parser_gen<'a>(paser_items: Vec<Rc<RefCell<Parser<'a>>>>) -> Parser<'a> { let left_parser = char_parser('['); let right_parser = char_parser(']'); let comma_parser = char_parser(','); Parser::new(move|input, loc| { match left_parser.parse(input, loc) { (true, loc) => { let mut cur_loc = loc; let mut first = true; let mut is_ng = false; loop { if(!first) { match comma_parser.parse(input, cur_loc) { (true, loc) => cur_loc = loc, (false, loc) => break } } let mut find = false; for p in paser_items.iter() { match p.borrow().parse(input, cur_loc) { (true, loc) => { find = true; cur_loc = loc; break; }, _ => {} } } first = false; is_ng = !(!first && find); if(!find) { break; } } if (!is_ng) { right_parser.parse(input, cur_loc) } else { (false, cur_loc) } }, (false, loc) => (false, loc) } }) } let array_parsre = parser_gen(parser_items); *array_parser_item.borrow_mut() = array_parsre; array_parser_item }
ポイントとしはVectorの中身をRc<RefCell
// 一旦ダミーを入れて初期化 let array_parser_item = Rc::new(RefCell::new(dummy_parer())); let mut parser_items = parsers.into_iter() .map(|a| Rc::new(RefCell::new(a))) .collect::<Vec<Rc<RefCell<Parser<'a>>>>>(); parser_items.push(Rc::clone(&array_parser_item));
それから配列のパーサー生成後、borrow_mut()でRefCellの参照先を変更します。
let array_parsre = parser_gen(parser_items); *array_parser_item.borrow_mut() = array_parsre;
テストコードにて正しく動作することが確認できます。
#[test] fn test_array_parser() { let a_parser = char_parser('a'); let b_parser = char_parser('b'); let cd_parser = and_parser(char_parser('c'), char_parser('d')); let parser = array_parser(vec![a_parser, b_parser, cd_parser]); assert_eq!((true, 16), parser.borrow().parse("[a,b,[a,[cd]],b]", 0)); assert_eq!((false, 7), parser.borrow().parse("[a,b,a,ef,b]", 0)); assert_eq!((false, 7), parser.borrow().parse("[a,b,a,[,b]", 0)); }
なぜこのようにRc, RefCellを組み合わせているかというと以下のような特徴があるからになります。 Rc: Refference Countにより複数の所有者を持てるが、そのデータが不変であることを保証する RefCell: 保持するデータに対して単独の所有者を補償しており変更可能。Boxも同様に単独の所有者を補償するが違いとしてはBoxはコンパイル時のチェックするが、RefCellは実行時にチェックし違反があったらpanicする。
RefCellのコンパイル時チェックについて、Rust By Exampleでは以下のようにMokMessengerのsendの実装で説明しており、ここでは単独所有者を実装者自身で補償しているが
https://doc.rust-jp.rs/book-ja/ch15-05-interior-mutability.html
pub trait Messenger { fn send(&self, msg: &str); } struct MockMessenger { sent_messages: RefCell<Vec<String>>, } impl MockMessenger { fn new() -> MockMessenger { MockMessenger { sent_messages: RefCell::new(vec![]) } } } impl Messenger for MockMessenger { fn send(&self, message: &str) { self.sent_messages.borrow_mut().push(String::from(message)); } }
以下のように複数所有者の実装でもコンパイル自体は通り、実行時にpanicで終了という動きになる。
impl Messenger for MockMessenger { fn send(&self, message: &str) { let mut one_borrow = self.sent_messages.borrow_mut(); let mut two_borrow = self.sent_messages.borrow_mut(); one_borrow.push(String::from(message)); two_borrow.push(String::from(message)); } }
もしBoxを使ってやろうとした場合、sendの呼び出し元自体をmutableにする必要があるのでBoxとRefCellの違いとして大元をmutableにするか、局所部分の所有権を実装者自身で補償するのかというのがあるので、それが使い分けのポイントになるかと思います。
pub trait Messenger2 { fn send(&mut self, msg: &str); } struct MockMessenger2 { sent_messages: Box<Vec<String>>, } impl MockMessenger2 { fn new() -> MockMessenger2 { MockMessenger2 { sent_messages: Box::new(vec![]) } } } impl Messenger2 for MockMessenger2 { fn send(&mut self, message: &str) { self.sent_messages.push(String::from(message)); } }
マルチスレッドで同様のことをする場合、Arc, Mutexを利用するのですがMockMessenger全体でロックの場合は、以下のようになるかと思います。lockの粒度を細かくする場合はsent_messages自体をArc<Mutex<Vec
#[test] fn test_arc_mutex() { use std::thread; use std::sync::{Arc, Mutex}; use std::time::Duration; let arc_mock_messenger = Arc::new(Mutex::new(MockMessenger::new())); let ref1 = Arc::clone(&arc_mock_messenger); let ref2 = Arc::clone(&arc_mock_messenger); let ref3 = Arc::clone(&arc_mock_messenger); let th1 = thread::spawn(move || { thread::sleep(Duration::from_secs(2)); ref1.lock().unwrap().send("abc"); }); let th2 = thread::spawn(move || { thread::sleep(Duration::from_secs(1)); ref2.lock().unwrap().send("def"); }); th1.join().unwrap(); th2.join().unwrap(); thread::spawn(move || { ref3.lock().unwrap().print(); }); }