Grcov report - engine.rs

1

use crate::{helpers::one_or_select, Commands, Rule, Update};

2

use uniplate::Uniplate;

3

4

/// Exhaustively rewrites a tree using a set of transformation rules.

5

///

6

/// Rewriting is complete when all rules have been attempted with no change. Rules may be organised

7

/// into groups to control the order in which they are attempted.

8

///

9

/// # Rule Groups

10

/// If all rules are treated equally, those which apply higher in the tree will take precedence

11

/// because of the left-most outer-most traversal order of the engine.

12

///

13

/// This can cause problems if a rule which should ideally be applied early (e.g. evaluating

14

/// constant expressions) is left until later.

15

///

16

/// To solve this, rules can be organised into different collections in the `groups` argument.

17

/// The engine will apply rules in an earlier group to the entire tree before trying later groups.

18

/// That is, no rule is attempted if a rule in an earlier group is applicable to any part of the

19

/// tree.

20

///

21

/// # Selector Functions

22

///

23

/// If multiple rules in the same group are applicable to an expression, the user-defined

24

/// selector function is used to choose one. This function is given an iterator over pairs of

25

/// rules and the engine-created [`Update`] values which contain their modifications to the tree.

26

///

27

/// Some useful selector functions are available in the [`helpers`](crate::helpers) module. One

28

/// common function is [`select_first`](crate::helpers::select_first), which simply returns the

29

/// first applicable rule.

30

///

31

/// # Example

32

/// ```rust

33

1

/// use tree_morph::{prelude::*, helpers::select_panic};

34

/// use uniplate::derive::Uniplate;

35

///

36

/// // A simple language of multiplied and squared constant expressions

37

/// #[derive(Debug, Clone, PartialEq, Eq, Uniplate)]

38

/// #[uniplate()]

39

/// enum Expr {

40

///     Val(i32),

41

///     Mul(Box<Expr>, Box<Expr>),

42

///     Sqr(Box<Expr>),

43

/// }

44

///

45

/// // a * b ~> (value of) a * b, where 'a' and 'b' are literal values

46

/// fn rule_eval_mul(cmds: &mut Commands<Expr, i32>, subtree: &Expr, meta: &i32) -> Option<Expr> {

47

14

///     cmds.mut_meta(|m| *m += 1);

48

14

///

49

///     if let Expr::Mul(a, b) = subtree {

50

14

///         if let (Expr::Val(a_v), Expr::Val(b_v)) = (a.as_ref(), b.as_ref()) {

51

7

///             return Some(Expr::Val(a_v * b_v));

52

5

///         }

53

2

///     }

54

7

///     None

55

9

/// }

56

14

///

57

/// // e ^ 2 ~> e * e, where e is an expression

58

/// // If this rule is applied before the sub-expression is fully evaluated, duplicate work

59

/// // will be done on the resulting two identical sub-expressions.

60

/// fn rule_expand_sqr(cmds: &mut Commands<Expr, i32>, subtree: &Expr, meta: &i32) -> Option<Expr> {

61

10

///     cmds.mut_meta(|m| *m += 1);

62

10

///

63

///     if let Expr::Sqr(expr) = subtree {

64

10

///         return Some(Expr::Mul(

65

2

///             Box::new(*expr.clone()),

66

2

///             Box::new(*expr.clone())

67

2

///         ));

68

2

///     }

69

8

///     None

70

8

/// }

71

10

///

72

/// // (1 * 2) ^ 2

73

/// let expr = Expr::Sqr(

74

1

///     Box::new(Expr::Mul(

75

1

///         Box::new(Expr::Val(1)),

76

1

///         Box::new(Expr::Val(2))

77

1

///     ))

78

1

/// );

79

1

///

80

1

/// // Try with both rules in the same group, keeping track of the number of rule applications

81

1

/// let (result, num_applications) = morph(

82

1

///     vec![rule_fns![rule_eval_mul, rule_expand_sqr]],

83

1

///     select_panic,

84

1

///     expr.clone(),

85

1

///     0

86

1

/// );

87

1

/// assert_eq!(result, Expr::Val(4));

88

1

/// assert_eq!(num_applications, 4); // The `Sqr` is expanded first, causing duplicate work

89

1

///

90

/// // Move the evaluation rule to an earlier group

91

/// let (result, num_applications) = morph(

92

1

///     vec![rule_fns![rule_eval_mul], rule_fns![rule_expand_sqr]],

93

1

///     select_panic,

94

1

///     expr.clone(),

95

1

///     0

96

1

/// );

97

1

/// assert_eq!(result, Expr::Val(4));

98

1

/// assert_eq!(num_applications, 3); // Now the sub-expression (1 * 2) is evaluated first

99

1

/// ```

100

25

pub fn morph<T, M, R>(

101

26

    groups: Vec<Vec<R>>,

102

26

    select: impl Fn(&T, &mut dyn Iterator<Item = (&R, Update<T, M>)>) -> Option<Update<T, M>>,

103

26

    tree: T,

104

26

    meta: M,

105

26

) -> (T, M)

106

26

where

107

26

    T: Uniplate,

108

26

    R: Rule<T, M>,

109

26

110

26

    let transforms: Vec<_> = groups

111

26

        .iter()

112

34

        .map(|group| {

113

87

            |subtree: &T, meta: &M| {

114

                let applicable = &mut group.iter().filter_map(|rule| {

115

114

                    let mut commands = Commands::new();

116

114

                    let new_tree = rule.apply(&mut commands, &subtree, &meta)?;

117

34

                    Some((

118

34

                        rule,

119

34

                        Update {

120

34

                            new_subtree: new_tree,

121

34

                            commands,

122

34

},

123

34

))

124

114

});

125

87

                one_or_select(&select, subtree, applicable)

126

87

127

34

})

128

26

        .collect();

129

26

    morph_impl(transforms, tree, meta)

130

26

131

132

/// This implements the core rewriting logic for the engine.

133

///

134

/// Iterate over rule groups and apply each one to the tree. If any changes are

135

/// made, restart with the first rule group.

136

26

fn morph_impl<T: Uniplate, M>(

137

26

    transforms: Vec<impl Fn(&T, &M) -> Option<Update<T, M>>>,

138

26

    mut tree: T,

139

26

    mut meta: M,

140

26

) -> (T, M) {

141

26

    let mut new_tree = tree;

142

143

    'main: loop {

144

58

        tree = new_tree;

145

69

        for transform in transforms.iter() {

146

            // Try each transform on the entire tree before moving to the next

147

87

            for (node, ctx) in tree.contexts() {

148

87

                if let Some(mut update) = transform(&node, &meta) {

149

32

                    let whole_tree = ctx(update.new_subtree);

150

32

                    (new_tree, meta) = update.commands.apply(whole_tree, meta);

151

32

152

32

                    // Restart with the first transform every time a change is made

153

32

                    continue 'main;

154

55

155

156

157

        // All transforms were attempted without change

158

26

        break;

159

26

160

26

    (tree, meta)

161

26