Grcov report - aterm

1

#![forbid(unsafe_code)]

2

3

use std::fmt;

4

5

use merc_utilities::MercError;

6

use merc_utilities::debug_trace;

7

8

use crate::ATerm;

9

use crate::Symbol;

10

use crate::Term;

11

use crate::storage::ThreadTermPool;

12

13

/// This can be used to construct an [ATerm] from a given input of (inductive) type I

14

/// without using recursion, as such avoiding system stack overflows. See [TermBuilder::evaluate]

15

/// for more details.

16

#[derive(Default)]

17

pub struct TermBuilder<I, C> {

18

    // The stack of terms

19

    terms: Vec<Option<ATerm>>,

20

    configs: Vec<Config<I, C>>,

21

22

23

/// Applies the given function to every subterm of the given term using the [TermBuilder].

24

///     function(subterm) returns:

25

///         None   , in which case subterm is kept and it is recursed into its argments.

26

///         Some(x), in which case subterm is replaced by x.

27

pub fn apply<F>(tp: &ThreadTermPool, t: &ATerm, function: &F) -> ATerm

28

where

29

    F: Fn(&ThreadTermPool, &ATerm) -> Option<ATerm>,

30

31

    let mut builder = TermBuilder::<ATerm, Symbol>::new();

32

33

    builder

34

        .evaluate(

35

tp,

36

            t.clone(),

37

            |tp, args, t| match function(tp, &t) {

38

                Some(result) => Ok(Yield::Term(result)),

39

                None => {

40

                    for arg in t.arguments() {

41

                        args.push(arg.protect());

42

43

44

                    Ok(Yield::Construct(t.get_head_symbol().protect()))

45

46

},

47

            |tp, symbol, args| Ok(tp.create_term_iter(&symbol, args)),

48

49

        .unwrap()

50

51

52

impl<I: fmt::Debug, C: fmt::Debug> TermBuilder<I, C> {

53

15289

    pub fn new() -> TermBuilder<I, C> {

54

15289

        TermBuilder {

55

15289

            terms: vec![],

56

15289

            configs: vec![],

57

15289

58

15289

59

60

    /// This can be used to construct a term from a given input of (inductive)

61

    /// type I, without using the system stack, i.e. recursion.

62

///

63

    /// The `transformer` function is applied to every instance I, which can

64

    /// generate more inputs using a so-called argument stack and some

65

    /// instance C that is used to construct the result term. Alternatively, it

66

    /// yields a result term directly.

67

///

68

    /// The `construct` function takes an instance C and the arguments pushed to

69

    /// stack where the transformer was applied for every input pushed onto the

70

    /// stack previously.

71

///

72

    /// # Example

73

///

74

    /// A simple example could be to transform a term into another term using a

75

    /// function `f : ATerm -> Option<ATerm>`. Then `I` will be ATerm since that is

76

    /// the input, and `C` will be the Symbol from which we can construct the

77

    /// recursive term.

78

///

79

    /// `transformer` takes the input and applies f(input). Then either we

80

    /// return Yield(x) when f returns some term, or Construct(head(input)) with

81

    /// the arguments of the input term pushed to stack.

82

///

83

    /// `construct` simply constructs the term from the symbol and the arguments

84

    /// on the stack.

85

15289

    pub fn evaluate<F, G>(

86

15289

        &mut self,

87

15289

        tp: &ThreadTermPool,

88

15289

        input: I,

89

15289

        transformer: F,

90

15289

        construct: G,

91

15289

    ) -> Result<ATerm, MercError>

92

15289

    where

93

15289

        F: Fn(&ThreadTermPool, &mut ArgStack<I, C>, I) -> Result<Yield<C>, MercError>,

94

15289

        // We need impl<Iterator<Item=&ATerm>> here, but that is not possible.

95

15289

        G: Fn(&ThreadTermPool, C, std::iter::Flatten<std::slice::Iter<Option<ATerm>>>) -> Result<ATerm, MercError>,

96

97

15289

        debug_trace!("Transforming {:?}", input);

98

15289

        self.terms.push(None);

99

15289

        self.configs.push(Config::Apply(input, 0));

100

101

143464

        while let Some(config) = self.configs.pop() {

102

128175

            match config {

103

81853

                Config::Apply(input, result) => {

104

                    // Applies the given function to this input, and obtain a number of symbol and arguments.

105

81853

                    let top_of_stack = self.configs.len();

106

81853

                    let mut args = ArgStack::new(&mut self.terms, &mut self.configs);

107

108

81853

                    match transformer(tp, &mut args, input)? {

109

46322

                        Yield::Construct(input) => {

110

46322

                            // This occurs before the other constructs.

111

46322

                            let arity = args.len();

112

46322

                            self.configs.reserve(1);

113

46322

                            self.configs

114

46322

                                .insert(top_of_stack, Config::Construct(input, arity, result));

115

46322

116

35531

                        Yield::Term(term) => {

117

35531

                            self.terms[result] = Some(term);

118

35531

119

120

121

46322

                Config::Construct(input, arity, result) => {

122

46322

                    let arguments = self.terms[self.terms.len() - arity..].iter().flatten();

123

124

46322

                    self.terms[result] = Some(construct(tp, input, arguments)?);

125

126

                    // Remove elements from the stack.

127

46322

                    self.terms.drain(self.terms.len() - arity..);

128

129

130

131

128175

            debug_trace!("{:?}", self);

132

133

134

15289

        debug_assert!(self.terms.len() == 1, "Expect exactly one term on the result stack");

135

136

15289

        Ok(self

137

15289

            .terms

138

15289

            .pop()

139

15289

            .expect("There should be at last one result")

140

15289

            .expect("The result should be Some"))

141

15289

142

143

144

enum Config<I, C> {

145

    Apply(I, usize),

146

    Construct(C, usize, usize),

147

148

149

pub enum Yield<C> {

150

    Term(ATerm),  // Yield this term as is.

151

    Construct(C), // Yield f(args) for every arg push to the argument stack, with the transformer applied to it.

152

153

154

/// This struct defines a local argument stack on the global stack.

155

pub struct ArgStack<'a, I, C> {

156

    terms: &'a mut Vec<Option<ATerm>>,

157

    configs: &'a mut Vec<Config<I, C>>,

158

    top_of_stack: usize,

159

160

161

impl<'a, I, C> ArgStack<'a, I, C> {

162

81853

    fn new(terms: &'a mut Vec<Option<ATerm>>, configs: &'a mut Vec<Config<I, C>>) -> ArgStack<'a, I, C> {

163

81853

        let top_of_stack = terms.len();

164

81853

        ArgStack {

165

81853

            terms,

166

81853

            configs,

167

81853

            top_of_stack,

168

81853

169

81853

170

171

    /// Returns the amount of arguments added.

172

46322

    fn len(&self) -> usize {

173

46322

        self.terms.len() - self.top_of_stack

174

46322

175

176

    /// Adds the term to the argument stack, will construct construct(C, args...) with the transformer applied to arguments.

177

66564

    pub fn push(&mut self, input: I) {

178

66564

        self.configs.push(Config::Apply(input, self.terms.len()));

179

66564

        self.terms.push(None);

180

66564

181

182

183

impl<I: fmt::Debug, C: fmt::Debug> fmt::Debug for TermBuilder<I, C> {

184

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

185

        writeln!(f, "Terms: [")?;

186

        for (i, term) in self.terms.iter().enumerate() {

187

            writeln!(f, "{i}\t{term:?}")?;

188

189

        writeln!(f, "]")?;

190

191

        writeln!(f, "Configs: [")?;

192

        for config in &self.configs {

193

            writeln!(f, "\t{config:?}")?;

194

195

        write!(f, "]")

196

197

198

199

impl<I: fmt::Debug, C: fmt::Debug> fmt::Debug for Config<I, C> {

200

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

201

        match self {

202

            Config::Apply(x, result) => write!(f, "Apply({x:?}, {result})"),

203

            Config::Construct(symbol, arity, result) => {

204

                write!(f, "Construct({symbol:?}, {arity}, {result})")

205

206

207

208