gambit_parser/
lib.rs

1//! A library for parsing [gambit extensive form
2//! game](https://gambitproject.readthedocs.io/en/v16.0.2/formats.html) (`.efg`) files
3//!
4//! Ths library produces an [ExtensiveFormGame], which can then be easily used to model an
5//! extensive form game.
6//!
7//! In order to minimize memory consumption, this stores references to the underlying string where
8//! possible. One side effect is that this is a borrowed struct, and any quoted labels will still
9//! have escape sequences in them in the form of [EscapedStr]s.
10//!
11//! This also tries to represent the file as it's structured, so if a name is attached to an
12//! infoset on one node, this won't propogate the name to other nodes with the same infoset.
13#![warn(missing_docs)]
14
15mod multiset;
16mod unescaped;
17
18use multiset::BTreeMultiSet;
19use nom::{
20    branch::alt,
21    bytes::complete::{escaped, tag},
22    character::complete::{char, digit0, digit1, multispace0, multispace1, none_of, one_of, u64},
23    combinator::{all_consuming, map, opt},
24    error::{ErrorKind, ParseError},
25    multi::separated_list1,
26    sequence::{delimited, pair, preceded, separated_pair, terminated, tuple},
27    IResult, Parser,
28};
29use num::rational::BigRational;
30use num::{BigInt, One, Zero};
31use std::collections::hash_map::Entry;
32use std::collections::HashMap;
33use std::error::Error as StdError;
34use std::fmt::{Display, Error as FmtError, Formatter};
35pub use unescaped::{EscapedStr, Unescaped};
36
37/// A full extensive form game
38///
39/// This can be parsed from a [str] reference using [ExtensiveFormGame::try_from_str] or using the
40/// [TryFrom] / [TryInto] traits. It implements [Display] for formatting.
41///
42/// # Example
43///
44/// ```
45/// # use gambit_parser::ExtensiveFormGame;
46/// let gambit = r#"EFG 2 R "" { "1" "2" } t "" 1 { 1 2 }"#;
47/// let game: ExtensiveFormGame<'_> = gambit.try_into().unwrap();
48/// let output = game.to_string();
49/// ```
50#[derive(Debug, PartialEq, Clone)]
51pub struct ExtensiveFormGame<'a> {
52    name: &'a EscapedStr,
53    player_names: Box<[&'a EscapedStr]>,
54    comment: Option<&'a EscapedStr>,
55    root: Node<'a>,
56}
57
58impl<'a> ExtensiveFormGame<'a> {
59    /// The name of the game
60    pub fn name(&self) -> &'a EscapedStr {
61        self.name
62    }
63
64    /// Names for every player, in order
65    pub fn player_names(&self) -> &[&'a EscapedStr] {
66        &self.player_names
67    }
68
69    /// An optional game comment
70    pub fn comment(&self) -> Option<&'a EscapedStr> {
71        self.comment
72    }
73
74    /// The root node of the game tree
75    pub fn root(&self) -> &Node<'a> {
76        &self.root
77    }
78}
79
80impl<'a> Display for ExtensiveFormGame<'a> {
81    fn fmt(&self, out: &mut Formatter<'_>) -> Result<(), FmtError> {
82        write!(out, "EFG 2 R \"{}\" {{ ", self.name.as_raw_str())?;
83        for name in self.player_names.iter() {
84            write!(out, "\"{}\" ", name.as_raw_str())?;
85        }
86        writeln!(out, "}}")?;
87        if let Some(comment) = self.comment {
88            writeln!(out, "\"{}\"", comment)?;
89        }
90        writeln!(out, "{}", self.root)
91    }
92}
93
94/// An error that happens while trying to turn a string into an [ExtensiveFormGame]
95#[derive(Debug)]
96#[non_exhaustive]
97pub enum Error<'a> {
98    /// A problem with parsing
99    ///
100    /// This will show the remainder of the string where the parse error occured
101    Parse(&'a str),
102    /// A problem validating the tree after parsing
103    Validation(ValidationError),
104}
105
106impl<'a> Display for Error<'a> {
107    fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), FmtError> {
108        match self {
109            Error::Parse(rem) => write!(fmt, "error parsing game at: '{}'", rem),
110            Error::Validation(err) => write!(fmt, "invalid efg: {}", err),
111        }
112    }
113}
114
115impl<'a> StdError for Error<'a> {}
116
117/// An error that results from something invalid about the parsed extensive form game
118#[derive(Debug, PartialEq, Eq)]
119#[non_exhaustive]
120pub enum ValidationError {
121    /// The probabilities of actions associated with a chance node don't sum to one
122    ChanceNotDistribution,
123    /// A players number wasn't between one and the number of players
124    InvalidPlayerNum,
125    /// An infoset had different names attached to it
126    NonMatchingInfosetNames,
127    /// An infoset had different sets of associated actions
128    NonMatchingInfosetActions,
129    /// There was payoff data associated with the null (0) outcome
130    NullOutcomePayoffs,
131    /// The number of specified payoffs did not match the number of players
132    InvalidNumberOfPayoffs,
133    /// An outcome had different names attached to it
134    NonMatchingOutcomeNames,
135    /// An outcome had different associated payoffs
136    NonMatchingOutcomePayoffs,
137    /// An outcomes was defined without payoffs
138    NoOutcomePayoffs,
139}
140
141impl Display for ValidationError {
142    fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), FmtError> {
143        write!(fmt, "{:?}", self)
144    }
145}
146
147impl<'a> From<ValidationError> for Error<'a> {
148    fn from(err: ValidationError) -> Self {
149        Error::Validation(err)
150    }
151}
152
153impl<'a> From<nom::Err<nom::error::Error<&'a str>>> for Error<'a> {
154    fn from(err: nom::Err<nom::error::Error<&'a str>>) -> Self {
155        match err {
156            nom::Err::Incomplete(_) => panic!("internal error: incomplete parsing"),
157            nom::Err::Error(err) => Error::Parse(err.input),
158            nom::Err::Failure(err) => Error::Parse(err.input),
159        }
160    }
161}
162
163impl<'a> ExtensiveFormGame<'a> {
164    /// Try to parse a game from a string
165    ///
166    /// This is identical to `ExtensiveFormGame::try_from` or `"...".try_into()`.
167    pub fn try_from_str(input: &'a str) -> Result<Self, Error<'a>> {
168        let (_, game) = all_consuming(efg)(input)?;
169        game.validate()?;
170        Ok(game)
171    }
172
173    fn validate(&self) -> Result<(), ValidationError> {
174        let num_players = self.player_names.len();
175        let mut chance_infosets = HashMap::new();
176        let mut player_infosets = vec![HashMap::new(); num_players].into_boxed_slice();
177        let mut outcomes = HashMap::new();
178        let mut queue = vec![&self.root];
179        while let Some(node) = queue.pop() {
180            match node {
181                Node::Chance(chance) => {
182                    let total: BigRational = chance.actions.iter().map(|(_, prob, _)| prob).sum();
183                    if total != BigRational::one() {
184                        return Err(ValidationError::ChanceNotDistribution);
185                    }
186
187                    Self::validate_infoset(
188                        chance.infoset,
189                        chance.infoset_name,
190                        chance.actions.iter().map(|(a, p, _)| (a, p)).collect(),
191                        &mut chance_infosets,
192                    )?;
193
194                    self.validate_outcome(
195                        chance.outcome,
196                        None,
197                        chance.outcome_payoffs.as_deref(),
198                        &mut outcomes,
199                    )?;
200
201                    queue.extend(chance.actions.iter().map(|(_, _, next)| next));
202                }
203                Node::Player(player) => {
204                    if !(1..=num_players).contains(&player.player_num) {
205                        return Err(ValidationError::InvalidPlayerNum);
206                    }
207
208                    Self::validate_infoset(
209                        player.infoset,
210                        player.infoset_name,
211                        player.actions.iter().map(|(action, _)| action).collect(),
212                        &mut player_infosets[player.player_num - 1],
213                    )?;
214
215                    self.validate_outcome(
216                        player.outcome,
217                        player.outcome_name,
218                        player.outcome_payoffs.as_deref(),
219                        &mut outcomes,
220                    )?;
221
222                    queue.extend(player.actions.iter().map(|(_, next)| next));
223                }
224                Node::Terminal(term) => {
225                    self.validate_outcome(
226                        term.outcome,
227                        term.outcome_name,
228                        Some(&term.outcome_payoffs),
229                        &mut outcomes,
230                    )?;
231                }
232            }
233        }
234
235        for (_, (_, pays)) in outcomes {
236            if pays.is_none() {
237                return Err(ValidationError::NoOutcomePayoffs);
238            }
239        }
240
241        Ok(())
242    }
243
244    fn validate_infoset<T: Eq>(
245        infoset: u64,
246        infoset_name: Option<&'a EscapedStr>,
247        actions: BTreeMultiSet<T>,
248        infosets: &mut HashMap<u64, (Option<&'a EscapedStr>, BTreeMultiSet<T>)>,
249    ) -> Result<(), ValidationError> {
250        match infosets.entry(infoset) {
251            Entry::Vacant(ent) => {
252                ent.insert((infoset_name, actions));
253            }
254            Entry::Occupied(mut ent) => {
255                let (name, acts) = ent.get_mut();
256                match (name, infoset_name) {
257                    (Some(old), Some(new)) if old != &new => {
258                        return Err(ValidationError::NonMatchingInfosetNames)
259                    }
260                    (old @ None, Some(new)) => {
261                        *old = Some(new);
262                    }
263                    _ => (),
264                };
265                if acts != &actions {
266                    return Err(ValidationError::NonMatchingInfosetActions);
267                }
268            }
269        }
270        Ok(())
271    }
272
273    fn validate_outcome<'b>(
274        &self,
275        outcome: u64,
276        outcome_name: Option<&'a EscapedStr>,
277        outcome_payoffs: Option<&'b [BigRational]>,
278        outcomes: &mut HashMap<u64, (Option<&'a EscapedStr>, Option<&'b [BigRational]>)>,
279    ) -> Result<(), ValidationError> {
280        if outcome == 0 {
281            if outcome_payoffs.is_some() {
282                return Err(ValidationError::NullOutcomePayoffs);
283            }
284        } else {
285            match outcomes.entry(outcome) {
286                Entry::Vacant(ent) => match outcome_payoffs {
287                    Some(pays) => {
288                        if pays.len() == self.player_names.len() {
289                            ent.insert((outcome_name, Some(pays)));
290                        } else {
291                            return Err(ValidationError::InvalidNumberOfPayoffs);
292                        }
293                    }
294                    None => {
295                        ent.insert((outcome_name, None));
296                    }
297                },
298                Entry::Occupied(mut ent) => {
299                    let (name, payoffs) = ent.get_mut();
300                    match (name, outcome_name) {
301                        (Some(old), Some(new)) if old != &new => {
302                            return Err(ValidationError::NonMatchingOutcomeNames);
303                        }
304                        (old @ None, Some(new)) => {
305                            *old = Some(new);
306                        }
307                        _ => (),
308                    };
309                    match (payoffs, outcome_payoffs) {
310                        (Some(old), Some(new)) if old != &new => {
311                            return Err(ValidationError::NonMatchingOutcomePayoffs);
312                        }
313                        (old @ None, Some(new)) => {
314                            *old = Some(new);
315                        }
316                        _ => (),
317                    }
318                }
319            }
320        }
321        Ok(())
322    }
323}
324
325impl<'a> TryFrom<&'a str> for ExtensiveFormGame<'a> {
326    type Error = Error<'a>;
327
328    fn try_from(input: &'a str) -> Result<Self, Self::Error> {
329        Self::try_from_str(input)
330    }
331}
332
333/// An arbitrary node in the game tree
334#[derive(Debug, PartialEq, Clone)]
335pub enum Node<'a> {
336    /// A chance node
337    Chance(Chance<'a>),
338    /// A player node
339    Player(Player<'a>),
340    /// A terminal node
341    Terminal(Terminal<'a>),
342}
343
344impl<'a> Display for Node<'a> {
345    fn fmt(&self, out: &mut Formatter<'_>) -> Result<(), FmtError> {
346        let mut queue = vec![self];
347        while let Some(node) = queue.pop() {
348            match node {
349                Node::Chance(chance) => {
350                    queue.extend(chance.actions.iter().rev().map(|(_, _, next)| next));
351                    write!(out, "\nc {}", chance)?
352                }
353                Node::Player(player) => {
354                    queue.extend(player.actions.iter().rev().map(|(_, next)| next));
355                    write!(out, "\np {}", player)?
356                }
357                Node::Terminal(terminal) => write!(out, "\nt {}", terminal)?,
358            }
359        }
360        Ok(())
361    }
362}
363
364/// A chance node
365///
366/// A chance node represents a point in the game where things advance randomly, or alternatively,
367/// where "nature" takes a turn.
368#[derive(Debug, PartialEq, Clone)]
369pub struct Chance<'a> {
370    name: &'a EscapedStr,
371    infoset: u64,
372    infoset_name: Option<&'a EscapedStr>,
373    actions: Box<[(&'a EscapedStr, BigRational, Node<'a>)]>,
374    outcome: u64,
375    outcome_payoffs: Option<Box<[BigRational]>>,
376}
377
378impl<'a> Chance<'a> {
379    /// The name of the node
380    pub fn name(&self) -> &'a EscapedStr {
381        self.name
382    }
383
384    /// The if of the node's infoset
385    pub fn infoset(&self) -> u64 {
386        self.infoset
387    }
388
389    /// The infoset's name
390    ///
391    /// Note that just because this infoset doesn't have a name attached, doesn't mean that the
392    /// same id doesn't have a name attached at a different node.
393    pub fn infoset_name(&self) -> Option<&'a EscapedStr> {
394        self.infoset_name
395    }
396
397    /// All possible outcomes with names and probabilities
398    pub fn actions(&self) -> &[(&'a EscapedStr, BigRational, Node<'a>)] {
399        &self.actions
400    }
401
402    /// The outcome id
403    pub fn outcome(&self) -> u64 {
404        self.outcome
405    }
406
407    /// Outcome payoffs for this node
408    ///
409    /// Outcome payoffs are added to every players' payoffs for traversing through this node. Note
410    /// that if these are missing, they be defined at another node sharing the same outcome.
411    pub fn outcome_payoffs(&self) -> Option<&[BigRational]> {
412        self.outcome_payoffs.as_deref()
413    }
414}
415
416impl<'a> Display for Chance<'a> {
417    fn fmt(&self, out: &mut Formatter<'_>) -> Result<(), FmtError> {
418        write!(out, "\"{}\" {}", self.name.as_raw_str(), self.infoset)?;
419        if let Some(name) = self.infoset_name {
420            write!(out, " \"{}\"", name.as_raw_str())?;
421        }
422        write!(out, " {{ ")?;
423        for (action, prob, _) in self.actions.iter() {
424            write!(out, "\"{}\" {} ", action, prob)?;
425        }
426        write!(out, "}} {}", self.outcome)?;
427        if let Some(payoffs) = &self.outcome_payoffs {
428            write!(out, " {{ ")?;
429            for payoff in payoffs.iter() {
430                write!(out, "{} ", payoff)?;
431            }
432            write!(out, "}}")?;
433        }
434        Ok(())
435    }
436}
437
438/// A player node in the game tree
439///
440/// A player node represents a place where one of the players chooses what happens next.
441#[derive(Debug, PartialEq, Clone)]
442pub struct Player<'a> {
443    name: &'a EscapedStr,
444    player_num: usize,
445    infoset: u64,
446    infoset_name: Option<&'a EscapedStr>,
447    actions: Box<[(&'a EscapedStr, Node<'a>)]>,
448    outcome: u64,
449    outcome_name: Option<&'a EscapedStr>,
450    outcome_payoffs: Option<Box<[BigRational]>>,
451}
452
453impl<'a> Player<'a> {
454    /// The name of the node
455    pub fn name(&self) -> &'a EscapedStr {
456        self.name
457    }
458
459    /// The player acting at this node
460    ///
461    /// This will always be between 1 and the number of players.
462    pub fn player_num(&self) -> usize {
463        self.player_num
464    }
465
466    /// The infoset id for this node and player
467    pub fn infoset(&self) -> u64 {
468        self.infoset
469    }
470
471    /// The infoset's name
472    ///
473    /// If the name is omitted, it may be defined on a different node.
474    pub fn infoset_name(&self) -> Option<&'a EscapedStr> {
475        self.infoset_name
476    }
477
478    /// All the actions a player can take with names
479    pub fn actions(&self) -> &[(&'a EscapedStr, Node<'a>)] {
480        &self.actions
481    }
482
483    /// The outcome id
484    pub fn outcome(&self) -> u64 {
485        self.outcome
486    }
487
488    /// The name of the outcome
489    ///
490    /// If omitted it may still be defined on another node.
491    pub fn outcome_name(&self) -> Option<&'a EscapedStr> {
492        self.outcome_name
493    }
494
495    /// Payoffs associated with the outcome
496    ///
497    /// If ommited they may be defined on another node.
498    pub fn outcome_payoffs(&self) -> Option<&[BigRational]> {
499        self.outcome_payoffs.as_deref()
500    }
501}
502
503impl<'a> Display for Player<'a> {
504    fn fmt(&self, out: &mut Formatter<'_>) -> Result<(), FmtError> {
505        write!(
506            out,
507            "\"{}\" {} {}",
508            self.name.as_raw_str(),
509            self.player_num,
510            self.infoset
511        )?;
512        if let Some(name) = self.infoset_name {
513            write!(out, " \"{}\"", name.as_raw_str())?;
514        }
515        write!(out, " {{ ")?;
516        for (action, _) in self.actions.iter() {
517            write!(out, "\"{}\" ", action)?;
518        }
519        write!(out, "}} {}", self.outcome)?;
520        if let Some(name) = self.outcome_name {
521            write!(out, " \"{}\"", name.as_raw_str())?;
522        }
523        if let Some(payoffs) = &self.outcome_payoffs {
524            write!(out, " {{ ")?;
525            for payoff in payoffs.iter() {
526                write!(out, "{} ", payoff)?;
527            }
528            write!(out, "}}")?;
529        }
530        Ok(())
531    }
532}
533
534/// A terminal node represents the end of a game
535///
536/// Terminal nodes simple assign payoffs to every player in the game
537#[derive(Debug, PartialEq, Eq, Clone)]
538pub struct Terminal<'a> {
539    name: &'a EscapedStr,
540    outcome: u64,
541    outcome_name: Option<&'a EscapedStr>,
542    outcome_payoffs: Box<[BigRational]>,
543}
544
545impl<'a> Terminal<'a> {
546    /// The name of this node
547    pub fn name(&self) -> &'a EscapedStr {
548        self.name
549    }
550
551    /// The outcome id
552    pub fn outcome(&self) -> u64 {
553        self.outcome
554    }
555
556    /// The name of this outcome
557    ///
558    /// Note that if omitted it may be specified on a different node with the same outcome.
559    pub fn outcome_name(&self) -> Option<&'a EscapedStr> {
560        self.outcome_name
561    }
562
563    /// The payoffs to every player
564    pub fn outcome_payoffs(&self) -> &[BigRational] {
565        &self.outcome_payoffs
566    }
567}
568
569impl<'a> Display for Terminal<'a> {
570    fn fmt(&self, out: &mut Formatter<'_>) -> Result<(), FmtError> {
571        write!(out, "\"{}\" {}", self.name.as_raw_str(), self.outcome)?;
572        if let Some(name) = self.outcome_name {
573            write!(out, " \"{}\"", name.as_raw_str())?;
574        }
575        write!(out, " {{ ")?;
576        for payoff in self.outcome_payoffs.iter() {
577            write!(out, "{} ", payoff)?;
578        }
579        write!(out, "}}")
580    }
581}
582
583fn negate(input: &str) -> IResult<&str, bool> {
584    let (input, res) = opt(one_of("+-"))(input)?;
585    Ok((input, res == Some('-')))
586}
587
588fn fail(input: &str) -> nom::Err<nom::error::Error<&str>> {
589    nom::Err::Error(nom::error::Error::new(input, ErrorKind::Fail))
590}
591
592fn big_float(input: &str) -> IResult<&str, BigRational> {
593    let (res_input, (main_neg, (int, dec), exp)) = tuple((
594        negate,
595        alt((
596            pair(
597                digit1,
598                map(opt(preceded(char('.'), digit0)), Option::unwrap_or_default),
599            ),
600            separated_pair(digit0, char('.'), digit1),
601        )),
602        opt(preceded(one_of("eE"), pair(negate, digit1))),
603    ))(input)?;
604    let mut res = if int.is_empty() {
605        BigRational::zero()
606    } else {
607        BigRational::from_integer(int.parse().unwrap())
608    };
609    if !dec.is_empty() {
610        let pow: u32 = dec.len().try_into().map_err(|_| fail(input))?;
611        res += BigRational::new(dec.parse().unwrap(), BigInt::from(10).pow(pow));
612    };
613    if let Some((neg, exp)) = exp {
614        let exp: i32 = exp.parse().map_err(|_| fail(input))?;
615        res *= BigRational::from_integer(10.into()).pow(if neg { -exp } else { exp });
616    };
617    if main_neg {
618        res = -res;
619    };
620    Ok((res_input, res))
621}
622
623fn big_rational(input: &str) -> IResult<&str, BigRational> {
624    let (input, (num, denom)) = pair(big_float, opt(preceded(char('/'), big_float)))(input)?;
625    Ok((
626        input,
627        match denom {
628            Some(denom) => num / denom,
629            None => num,
630        },
631    ))
632}
633
634fn label(input: &str) -> IResult<&str, &EscapedStr> {
635    map(
636        delimited(
637            char('"'),
638            alt((escaped(none_of("\\\""), '\\', one_of("\\\"")), tag(""))),
639            char('"'),
640        ),
641        EscapedStr::new,
642    )(input)
643}
644
645fn spacelist<'a, O, E, F>(f: F) -> impl FnMut(&'a str) -> IResult<&'a str, Vec<O>, E>
646where
647    F: Parser<&'a str, O, E>,
648    E: ParseError<&'a str>,
649{
650    delimited(
651        pair(char('{'), multispace1),
652        separated_list1(multispace1, f),
653        pair(multispace1, char('}')),
654    )
655}
656
657fn commalist<'a, O, E, F>(f: F) -> impl FnMut(&'a str) -> IResult<&'a str, Vec<O>, E>
658where
659    F: Parser<&'a str, O, E>,
660    E: ParseError<&'a str>,
661{
662    delimited(
663        pair(char('{'), multispace1),
664        separated_list1(pair(opt(char(',')), multispace1), f),
665        pair(multispace1, char('}')),
666    )
667}
668
669fn node(input: &str) -> IResult<&str, Node<'_>> {
670    let (input, style) = preceded(multispace1, one_of("cpt"))(input)?;
671    match style {
672        'c' => {
673            let (input, chance) = chance(input)?;
674            Ok((input, Node::Chance(chance)))
675        }
676        'p' => {
677            let (input, play) = player(input)?;
678            Ok((input, Node::Player(play)))
679        }
680        't' => {
681            let (input, term) = terminal(input)?;
682            Ok((input, Node::Terminal(term)))
683        }
684        _ => panic!(),
685    }
686}
687
688fn chance(input: &str) -> IResult<&str, Chance<'_>> {
689    let (mut input, (name, infoset, infoset_name, action_probs, outcome, outcome_payoffs)) =
690        tuple((
691            preceded(multispace1, label),
692            preceded(multispace1, u64),
693            opt(preceded(multispace1, label)),
694            preceded(
695                multispace1,
696                spacelist(separated_pair(label, multispace1, big_rational)),
697            ),
698            preceded(multispace1, u64),
699            opt(preceded(multispace1, commalist(big_rational))),
700        ))(input)?;
701    let mut actions = Vec::with_capacity(action_probs.len());
702    for (name, prob) in action_probs {
703        let (next_inp, next) = node(input)?;
704        input = next_inp;
705        actions.push((name, prob, next));
706    }
707    Ok((
708        input,
709        Chance {
710            name,
711            infoset,
712            infoset_name,
713            actions: actions.into(),
714            outcome,
715            outcome_payoffs: outcome_payoffs.map(|p| p.into()),
716        },
717    ))
718}
719
720fn player(input: &str) -> IResult<&str, Player<'_>> {
721    let (
722        mut res_input,
723        (
724            name,
725            player_num,
726            infoset,
727            infoset_name,
728            action_names,
729            outcome,
730            outcome_name,
731            outcome_payoffs,
732        ),
733    ) = tuple((
734        preceded(multispace1, label),
735        preceded(multispace1, u64),
736        preceded(multispace1, u64),
737        opt(preceded(multispace1, label)),
738        preceded(multispace1, spacelist(label)),
739        preceded(multispace1, u64),
740        opt(preceded(multispace1, label)),
741        opt(preceded(multispace1, commalist(big_rational))),
742    ))(input)?;
743    let player_num = player_num.try_into().map_err(|_| fail(input))?;
744    let mut actions = Vec::with_capacity(action_names.len());
745    for name in action_names {
746        let (next_inp, next) = node(res_input)?;
747        res_input = next_inp;
748        actions.push((name, next));
749    }
750    Ok((
751        res_input,
752        Player {
753            name,
754            player_num,
755            infoset,
756            infoset_name,
757            actions: actions.into(),
758            outcome,
759            outcome_name,
760            outcome_payoffs: outcome_payoffs.map(|p| p.into()),
761        },
762    ))
763}
764
765fn terminal(input: &str) -> IResult<&str, Terminal<'_>> {
766    let (input, (name, outcome, outcome_name, payoffs)) = tuple((
767        preceded(multispace1, label),
768        preceded(multispace1, u64),
769        opt(preceded(multispace1, label)),
770        preceded(multispace1, commalist(big_rational)),
771    ))(input)?;
772    Ok((
773        input,
774        Terminal {
775            name,
776            outcome,
777            outcome_name,
778            outcome_payoffs: payoffs.into(),
779        },
780    ))
781}
782
783fn efg(input: &str) -> IResult<&str, ExtensiveFormGame<'_>> {
784    let (input, (name, player_names, comment, root)) = tuple((
785        preceded(
786            tuple((
787                multispace0,
788                tag("EFG"),
789                multispace1,
790                tag("2"),
791                multispace1,
792                tag("R"),
793                multispace1,
794            )),
795            label,
796        ),
797        preceded(multispace1, spacelist(label)),
798        opt(preceded(multispace1, label)),
799        terminated(node, multispace0),
800    ))(input)?;
801    Ok((
802        input,
803        ExtensiveFormGame {
804            name,
805            player_names: player_names.into(),
806            comment,
807            root,
808        },
809    ))
810}
811
812#[cfg(test)]
813mod tests {
814    use super::{Chance, EscapedStr, ExtensiveFormGame, Node, Player, Terminal, ValidationError};
815    use num::rational::BigRational;
816    use num::{One, Zero};
817
818    fn new_game<'a>(
819        name: &'a str,
820        player_names: impl IntoIterator<Item = &'a str>,
821        comment: Option<&'a str>,
822        root: Node<'a>,
823    ) -> ExtensiveFormGame<'a> {
824        ExtensiveFormGame {
825            name: EscapedStr::new(name),
826            player_names: player_names.into_iter().map(EscapedStr::new).collect(),
827            comment: comment.map(EscapedStr::new),
828            root,
829        }
830    }
831
832    fn new_chance<'a>(
833        name: &'a str,
834        infoset: u64,
835        infoset_name: Option<&'a str>,
836        actions: impl IntoIterator<Item = (&'a str, BigRational, Node<'a>)>,
837        outcome: u64,
838        outcome_payoffs: Option<Box<[BigRational]>>,
839    ) -> Chance<'a> {
840        Chance {
841            name: EscapedStr::new(name),
842            infoset,
843            infoset_name: infoset_name.map(EscapedStr::new),
844            actions: actions
845                .into_iter()
846                .map(|(name, prob, node)| (EscapedStr::new(name), prob, node))
847                .collect(),
848            outcome,
849            outcome_payoffs,
850        }
851    }
852
853    fn new_player<'a>(
854        name: &'a str,
855        player_num: usize,
856        infoset: u64,
857        infoset_name: Option<&'a str>,
858        actions: impl IntoIterator<Item = (&'a str, Node<'a>)>,
859        outcome: u64,
860        outcome_name: Option<&'a str>,
861        outcome_payoffs: Option<Box<[BigRational]>>,
862    ) -> Player<'a> {
863        Player {
864            name: EscapedStr::new(name),
865            player_num,
866            infoset,
867            infoset_name: infoset_name.map(EscapedStr::new),
868            actions: actions
869                .into_iter()
870                .map(|(name, node)| (EscapedStr::new(name), node))
871                .collect(),
872            outcome,
873            outcome_name: outcome_name.map(EscapedStr::new),
874            outcome_payoffs,
875        }
876    }
877
878    fn new_terminal<'a>(
879        name: &'a str,
880        outcome: u64,
881        outcome_name: Option<&'a str>,
882        outcome_payoffs: impl Into<Box<[BigRational]>>,
883    ) -> Terminal<'a> {
884        Terminal {
885            name: EscapedStr::new(name),
886            outcome,
887            outcome_name: outcome_name.map(EscapedStr::new),
888            outcome_payoffs: outcome_payoffs.into(),
889        }
890    }
891
892    #[test]
893    fn test_big_float() {
894        let (input, num) = super::big_float("3 ").unwrap();
895        assert_eq!(input, " ");
896        assert_eq!(num, BigRational::from_integer(3.into()));
897
898        let (input, num) = super::big_float("-2. ").unwrap();
899        assert_eq!(input, " ");
900        assert_eq!(num, BigRational::from_integer((-2).into()));
901
902        let (input, num) = super::big_float("+.56 ").unwrap();
903        assert_eq!(input, " ");
904        assert_eq!(num, BigRational::new(56.into(), 100.into()));
905
906        let (input, num) = super::big_float("3.14e-1 ").unwrap();
907        assert_eq!(input, " ");
908        assert_eq!(num, BigRational::new(314.into(), 1000.into()));
909    }
910
911    #[test]
912    fn test_big_rational() {
913        let (input, num) = super::big_rational("3 ").unwrap();
914        assert_eq!(input, " ");
915        assert_eq!(num, BigRational::from_integer(3.into()));
916
917        let (input, num) = super::big_rational("99/100 ").unwrap();
918        assert_eq!(input, " ");
919        assert_eq!(num, BigRational::new(99.into(), 100.into()));
920
921        let (input, num) = super::big_rational(".1e3/+1.e2 ").unwrap();
922        assert_eq!(input, " ");
923        assert_eq!(num, BigRational::one());
924    }
925
926    #[test]
927    fn test_label() {
928        let (input, label) = super::label(r#""" "#).unwrap();
929        assert_eq!(input, " ");
930        assert_eq!(label.as_raw_str(), "");
931
932        let (input, label) = super::label(r#""normal" "#).unwrap();
933        assert_eq!(input, " ");
934        assert_eq!(label.as_raw_str(), "normal");
935
936        let (input, label) = super::label(r#""esca\"ped" "#).unwrap();
937        assert_eq!(input, " ");
938        assert_eq!(label.as_raw_str(), "esca\\\"ped");
939    }
940
941    #[test]
942    fn test_terminal() {
943        let (input, term) =
944            super::terminal(r#" "name" 1 "outcome name" { 10.000000 2.000000 }"#).unwrap();
945        let expected = new_terminal(
946            "name",
947            1,
948            Some("outcome name"),
949            [
950                BigRational::from_integer(10.into()),
951                BigRational::from_integer(2.into()),
952            ],
953        );
954        assert_eq!(input, "");
955        assert_eq!(term, expected);
956        assert_eq!(expected.to_string(), r#""name" 1 "outcome name" { 10 2 }"#);
957
958        let (input, term) = super::terminal(r#" "" 2 { -1, 4/6 }"#).unwrap();
959        let expected = new_terminal(
960            "",
961            2,
962            None,
963            [
964                BigRational::from_integer((-1).into()),
965                BigRational::new(4.into(), 6.into()),
966            ],
967        );
968        assert_eq!(input, "");
969        assert_eq!(term, expected);
970        assert_eq!(expected.to_string(), r#""" 2 { -1 2/3 }"#);
971    }
972
973    #[test]
974    fn test_player() {
975        let (input, player) = super::player(
976            r#" "name" 1 2 "infoset name" { "action" } 0
977            t "" 1 { 10 }"#,
978        )
979        .unwrap();
980        let expected = new_player(
981            "name",
982            1,
983            2,
984            Some("infoset name"),
985            [(
986                "action",
987                Node::Terminal(new_terminal(
988                    "",
989                    1,
990                    None,
991                    [BigRational::from_integer(10.into())],
992                )),
993            )],
994            0,
995            None,
996            None,
997        );
998        assert_eq!(input, "");
999        assert_eq!(player, expected);
1000        assert_eq!(
1001            expected.to_string(),
1002            r#""name" 1 2 "infoset name" { "action" } 0"#
1003        );
1004
1005        let (input, player) = super::player(
1006            r#" "" 2 3 { "" } 1 "outcome name" { -4.5, 6.7 }
1007            t "" 1 { 10 }"#,
1008        )
1009        .unwrap();
1010        let expected = new_player(
1011            "",
1012            2,
1013            3,
1014            None,
1015            [(
1016                "",
1017                Node::Terminal(new_terminal(
1018                    "",
1019                    1,
1020                    None,
1021                    [BigRational::from_integer(10.into())],
1022                )),
1023            )],
1024            1,
1025            Some("outcome name"),
1026            Some(
1027                [
1028                    BigRational::new((-45).into(), 10.into()),
1029                    BigRational::new(67.into(), 10.into()),
1030                ]
1031                .into(),
1032            ),
1033        );
1034        assert_eq!(input, "");
1035        assert_eq!(player, expected);
1036        assert_eq!(
1037            expected.to_string(),
1038            r#""" 2 3 { "" } 1 "outcome name" { -9/2 67/10 }"#
1039        );
1040    }
1041
1042    #[test]
1043    fn test_chance() {
1044        let (input, chance) = super::chance(
1045            r#" "name" 1 "infoset name" { "action" 1/2 } 0
1046            t "" 1 { 10 }"#,
1047        )
1048        .unwrap();
1049        let expected = new_chance(
1050            "name",
1051            1,
1052            Some("infoset name"),
1053            [(
1054                "action",
1055                BigRational::new(1.into(), 2.into()),
1056                Node::Terminal(new_terminal(
1057                    "",
1058                    1,
1059                    None,
1060                    [BigRational::from_integer(10.into())],
1061                )),
1062            )],
1063            0,
1064            None,
1065        );
1066        assert_eq!(input, "");
1067        assert_eq!(chance, expected);
1068        assert_eq!(
1069            expected.to_string(),
1070            r#""name" 1 "infoset name" { "action" 1/2 } 0"#
1071        );
1072
1073        let (input, chance) = super::chance(
1074            r#" "" 2 { "" 1 } 4 { 0.1, 4 }
1075            t "" 1 { 10 }"#,
1076        )
1077        .unwrap();
1078        let expected = new_chance(
1079            "",
1080            2,
1081            None,
1082            [(
1083                "",
1084                BigRational::from_integer(1.into()),
1085                Node::Terminal(new_terminal(
1086                    "",
1087                    1,
1088                    None,
1089                    [BigRational::from_integer(10.into())],
1090                )),
1091            )],
1092            4,
1093            Some(
1094                [
1095                    BigRational::new(1.into(), 10.into()),
1096                    BigRational::from_integer(4.into()),
1097                ]
1098                .into(),
1099            ),
1100        );
1101        assert_eq!(input, "");
1102        assert_eq!(chance, expected);
1103        assert_eq!(expected.to_string(), r#""" 2 { "" 1 } 4 { 1/10 4 }"#);
1104    }
1105
1106    #[test]
1107    fn simple_test() {
1108        let game_str = r#"
1109        EFG 2 R "General Bayes game, one stage" { "Player 1" "Player 2" }
1110        "A single stage General Bayes Game"
1111
1112        c "ROOT" 1 "(0,1)" { "1G" 0.500000 "1B" 0.500000 } 0
1113        p "" 1 1 "(1,1)" { "H" "L" } 0
1114        t "" 1 "Outcome 1" { 10.000000 2.000000 }
1115        t "" 2 "Outcome 2" { 0.000000 10.000000 }
1116        p "" 2 1 "(2,1)" { "h" "l" } 0
1117        t "" 3 "Outcome 3" { 2.000000 4.000000 }
1118        t "" 4 "Outcome 4" { 4.000000 0.000000 }
1119        "#;
1120        let (input, efg) = super::efg(game_str).unwrap();
1121        let expected = new_game(
1122            "General Bayes game, one stage",
1123            ["Player 1", "Player 2"],
1124            Some("A single stage General Bayes Game"),
1125            Node::Chance(new_chance(
1126                "ROOT",
1127                1,
1128                Some("(0,1)"),
1129                [
1130                    (
1131                        "1G",
1132                        BigRational::new(1.into(), 2.into()),
1133                        Node::Player(new_player(
1134                            "",
1135                            1,
1136                            1,
1137                            Some("(1,1)"),
1138                            [
1139                                (
1140                                    "H",
1141                                    Node::Terminal(new_terminal(
1142                                        "",
1143                                        1,
1144                                        Some("Outcome 1"),
1145                                        [
1146                                            BigRational::from_integer(10.into()),
1147                                            BigRational::from_integer(2.into()),
1148                                        ],
1149                                    )),
1150                                ),
1151                                (
1152                                    "L",
1153                                    Node::Terminal(new_terminal(
1154                                        "",
1155                                        2,
1156                                        Some("Outcome 2"),
1157                                        [
1158                                            BigRational::from_integer(0.into()),
1159                                            BigRational::from_integer(10.into()),
1160                                        ],
1161                                    )),
1162                                ),
1163                            ],
1164                            0,
1165                            None,
1166                            None,
1167                        )),
1168                    ),
1169                    (
1170                        "1B",
1171                        BigRational::new(1.into(), 2.into()),
1172                        Node::Player(new_player(
1173                            "",
1174                            2,
1175                            1,
1176                            Some("(2,1)"),
1177                            [
1178                                (
1179                                    "h",
1180                                    Node::Terminal(new_terminal(
1181                                        "",
1182                                        3,
1183                                        Some("Outcome 3"),
1184                                        [
1185                                            BigRational::from_integer(2.into()),
1186                                            BigRational::from_integer(4.into()),
1187                                        ],
1188                                    )),
1189                                ),
1190                                (
1191                                    "l",
1192                                    Node::Terminal(new_terminal(
1193                                        "",
1194                                        4,
1195                                        Some("Outcome 4"),
1196                                        [
1197                                            BigRational::from_integer(4.into()),
1198                                            BigRational::from_integer(0.into()),
1199                                        ],
1200                                    )),
1201                                ),
1202                            ],
1203                            0,
1204                            None,
1205                            None,
1206                        )),
1207                    ),
1208                ],
1209                0,
1210                None,
1211            )),
1212        );
1213        assert_eq!(input, "");
1214        assert_eq!(efg, expected);
1215        assert_eq!(
1216            expected.to_string(),
1217            r#"EFG 2 R "General Bayes game, one stage" { "Player 1" "Player 2" }
1218"A single stage General Bayes Game"
1219
1220c "ROOT" 1 "(0,1)" { "1G" 1/2 "1B" 1/2 } 0
1221p "" 1 1 "(1,1)" { "H" "L" } 0
1222t "" 1 "Outcome 1" { 10 2 }
1223t "" 2 "Outcome 2" { 0 10 }
1224p "" 2 1 "(2,1)" { "h" "l" } 0
1225t "" 3 "Outcome 3" { 2 4 }
1226t "" 4 "Outcome 4" { 4 0 }
1227"#
1228        );
1229    }
1230
1231    fn empty_game<'a>(
1232        player_names: impl IntoIterator<Item = &'a str>,
1233        root: Node<'a>,
1234    ) -> ExtensiveFormGame<'a> {
1235        ExtensiveFormGame {
1236            name: EscapedStr::new(""),
1237            player_names: player_names.into_iter().map(EscapedStr::new).collect(),
1238            comment: None,
1239            root,
1240        }
1241    }
1242
1243    #[test]
1244    fn not_distribution() {
1245        let game = empty_game(
1246            ["1", "2"],
1247            Node::Chance(new_chance(
1248                "",
1249                1,
1250                None,
1251                [(
1252                    "",
1253                    BigRational::new(9.into(), 10.into()),
1254                    Node::Terminal(new_terminal("", 1, None, vec![BigRational::zero(); 2])),
1255                )],
1256                0,
1257                None,
1258            )),
1259        );
1260        assert_eq!(
1261            game.validate().unwrap_err(),
1262            ValidationError::ChanceNotDistribution
1263        );
1264    }
1265
1266    #[test]
1267    fn invalid_player_num() {
1268        let game = empty_game(
1269            ["1", "2"],
1270            Node::Player(new_player("", 3, 1, None, [], 0, None, None)),
1271        );
1272        assert_eq!(
1273            game.validate().unwrap_err(),
1274            ValidationError::InvalidPlayerNum
1275        );
1276    }
1277
1278    #[test]
1279    fn invalid_infoset_names() {
1280        let game = empty_game(
1281            ["1", "2"],
1282            Node::Player(new_player(
1283                "",
1284                1,
1285                1,
1286                Some("a"),
1287                [(
1288                    "",
1289                    Node::Player(new_player("", 1, 1, Some("b"), [], 0, None, None)),
1290                )],
1291                0,
1292                None,
1293                None,
1294            )),
1295        );
1296        assert_eq!(
1297            game.validate().unwrap_err(),
1298            ValidationError::NonMatchingInfosetNames
1299        );
1300    }
1301
1302    #[test]
1303    fn invalid_chance_infoset_names() {
1304        let game = empty_game(
1305            ["1", "2"],
1306            Node::Chance(new_chance(
1307                "",
1308                1,
1309                Some("a"),
1310                [(
1311                    "",
1312                    BigRational::one(),
1313                    Node::Chance(new_chance(
1314                        "",
1315                        1,
1316                        Some("b"),
1317                        [(
1318                            "",
1319                            BigRational::one(),
1320                            Node::Terminal(new_terminal("", 1, None, vec![BigRational::zero(); 2])),
1321                        )],
1322                        0,
1323                        None,
1324                    )),
1325                )],
1326                0,
1327                None,
1328            )),
1329        );
1330        assert_eq!(
1331            game.validate().unwrap_err(),
1332            ValidationError::NonMatchingInfosetNames
1333        );
1334    }
1335
1336    #[test]
1337    fn invalid_infoset_actions() {
1338        let game = empty_game(
1339            ["1", "2"],
1340            Node::Player(new_player(
1341                "",
1342                1,
1343                1,
1344                None,
1345                [(
1346                    "",
1347                    Node::Player(new_player("", 1, 1, None, [], 0, None, None)),
1348                )],
1349                0,
1350                None,
1351                None,
1352            )),
1353        );
1354        assert_eq!(
1355            game.validate().unwrap_err(),
1356            ValidationError::NonMatchingInfosetActions
1357        );
1358    }
1359
1360    #[test]
1361    fn invalid_chance_infoset_actions() {
1362        let game = empty_game(
1363            ["1", "2"],
1364            Node::Chance(new_chance(
1365                "",
1366                1,
1367                None,
1368                [(
1369                    "",
1370                    BigRational::one(),
1371                    Node::Chance(new_chance(
1372                        "",
1373                        1,
1374                        None,
1375                        [(
1376                            "a",
1377                            BigRational::one(),
1378                            Node::Terminal(new_terminal("", 0, None, vec![BigRational::zero(); 2])),
1379                        )],
1380                        0,
1381                        None,
1382                    )),
1383                )],
1384                0,
1385                None,
1386            )),
1387        );
1388        assert_eq!(
1389            game.validate().unwrap_err(),
1390            ValidationError::NonMatchingInfosetActions
1391        );
1392    }
1393
1394    #[test]
1395    fn null_outcome_payoffs() {
1396        let game = empty_game(
1397            ["1", "2"],
1398            Node::Player(new_player(
1399                "",
1400                1,
1401                1,
1402                None,
1403                [],
1404                0,
1405                None,
1406                Some(vec![BigRational::zero(); 2].into()),
1407            )),
1408        );
1409        assert_eq!(
1410            game.validate().unwrap_err(),
1411            ValidationError::NullOutcomePayoffs
1412        );
1413    }
1414
1415    #[test]
1416    fn invalid_payoff_number() {
1417        let game = empty_game(
1418            ["1", "2"],
1419            Node::Terminal(new_terminal("", 1, None, [BigRational::zero()])),
1420        );
1421        assert_eq!(
1422            game.validate().unwrap_err(),
1423            ValidationError::InvalidNumberOfPayoffs
1424        );
1425    }
1426
1427    #[test]
1428    fn non_matching_outcome_names() {
1429        let game = empty_game(
1430            ["1", "2"],
1431            Node::Player(new_player(
1432                "",
1433                1,
1434                1,
1435                None,
1436                [(
1437                    "",
1438                    Node::Player(new_player("", 1, 2, None, [], 1, Some("a"), None)),
1439                )],
1440                1,
1441                Some("b"),
1442                None,
1443            )),
1444        );
1445        assert_eq!(
1446            game.validate().unwrap_err(),
1447            ValidationError::NonMatchingOutcomeNames
1448        );
1449    }
1450
1451    #[test]
1452    fn non_matching_outcome_payoffs() {
1453        let game = empty_game(
1454            ["1", "2"],
1455            Node::Player(new_player(
1456                "",
1457                1,
1458                1,
1459                None,
1460                [(
1461                    "",
1462                    Node::Player(new_player(
1463                        "",
1464                        1,
1465                        2,
1466                        None,
1467                        [],
1468                        1,
1469                        None,
1470                        Some(vec![BigRational::one(); 2].into()),
1471                    )),
1472                )],
1473                1,
1474                None,
1475                Some(vec![BigRational::zero(); 2].into()),
1476            )),
1477        );
1478        assert_eq!(
1479            game.validate().unwrap_err(),
1480            ValidationError::NonMatchingOutcomePayoffs
1481        );
1482    }
1483
1484    #[test]
1485    fn no_outcome_payoffs() {
1486        let game = empty_game(
1487            ["1", "2"],
1488            Node::Player(new_player("", 1, 1, None, [], 1, None, None)),
1489        );
1490        assert_eq!(
1491            game.validate().unwrap_err(),
1492            ValidationError::NoOutcomePayoffs
1493        );
1494    }
1495}
gambit_parser/lib.rs

gambit_parser/
lib.rs
