Grcov report - reduce.rs

1

use crate::{Commands, Reduction, Rule};

2

use uniplate::Uniplate;

3

4

// TODO: (Felix) dirty/clean optimisation: replace tree with a custom tree structure,

5

//               which contains the original tree and adds metadata fields?

6

7

// TODO: (Felix) add logging via `log` crate; possibly need tree type to be Debug?

8

//               could be a crate feature?

9

10

// TODO: (Felix) add "control" rules; e.g. ignore a subtree to a certain depth?

11

//               test by ignoring everything once a metadata field is set? e.g. "reduce until contains X"

12

13

/// Exhaustively reduce a tree using a given transformation function.

14

///

15

/// The transformation function is called on each node in the tree (in left-most, outer-most order) along with

16

/// the metadata and a `Commands` object for side-effects.

17

///

18

/// - When the transformation function returns `Some(new_node)` for some node, that node is replaced with `new_node`.

19

///     Any side-effects are then applied at the root of the tree and the traversal begins again.

20

/// - Once the transformation function returns `None` for all nodes, the reduction is complete.

21

///

22

/// The `Commands` object is used to apply side-effects after a transformation is made.

23

/// This can be used to update metadata or perform arbitrary transformations on the entire tree,

24

/// which are reflected in the next traversal iteration.

25

///

26

/// # Parameters

27

/// - `transform`: A function which takes a mutable reference to a `Commands` object, a reference to the current node, and a reference to the metadata.

28

///               The function should return `Some(new_node)` if the node was transformed, or `None` otherwise.

29

/// - `tree`: The tree to reduce.

30

/// - `meta`: Metadata to be passed to the transformation function. This persists across all transformations.

31

///

32

/// # Returns

33

/// A tuple containing the reduced tree and the final metadata.

34

13

pub fn reduce<T, M, F>(transform: F, mut tree: T, mut meta: M) -> (T, M)

35

13

where

36

13

    T: Uniplate,

37

13

    F: Fn(&mut Commands<T, M>, &T, &M) -> Option<T>,

38

13

39

    // Apply the transformation to the tree until no more changes are made

40

35

    while let Some(mut reduction) = reduce_iteration(&transform, &tree, &meta) {

41

22

        // Apply reduction side-effects

42

22

        (tree, meta) = reduction.commands.apply(reduction.new_tree, meta);

43

22

44

13

    (tree, meta)

45

13

46

47

58

fn reduce_iteration<T, M, F>(transform: &F, subtree: &T, meta: &M) -> Option<Reduction<T, M>>

48

58

where

49

58

    T: Uniplate,

50

58

    F: Fn(&mut Commands<T, M>, &T, &M) -> Option<T>,

51

58

52

58

    // Try to apply the transformation to the current node

53

58

    let reduction = Reduction::apply_transform(transform, subtree, meta);

54

58

    if reduction.is_some() {

55

22

        return reduction;

56

36

57

36

58

36

    // Try to call the transformation on the children of the current node

59

36

    // If successful, return the new subtree

60

36

    let mut children = subtree.children();

61

36

    for c in children.iter_mut() {

62

23

        if let Some(reduction) = reduce_iteration(transform, c, meta) {

63

13

            *c = reduction.new_tree;

64

13

            return Some(Reduction {

65

13

                new_tree: subtree.with_children(children),

66

13

                ..reduction

67

13

});

68

10

69

70

71

23

    None

72

58

73

74

/// Exhaustively reduce a tree by applying the given rules at each node.

75

///

76

/// Rules are applied in the order they are given. If multiple rules can be applied to a node,

77

/// the `select` function is used to choose which rule to apply.

78

///

79

/// `Reduction`s encapsulate the result of applying a rule at a given node, holding the resulting node

80

/// and any side-effects. An iterator of these objects (along with the rule they result from)

81

/// is given to the `select` function, and the one returned is applied to the tree as in the `reduce` function.

82

///

83

/// # Parameters

84

/// - `rules`: A slice of rules to apply to the tree.

85

/// - `select`: A function which takes the current node and an iterator of rule-`Reduction` pairs and returns the selected `Reduction`.

86

/// - `tree`: The tree to reduce.

87

/// - `meta`: Metadata to be passed to the transformation function. This persists across all transformations.

88

///

89

/// # Returns

90

/// A tuple containing the reduced tree and the final metadata.

91

6

pub fn reduce_with_rules<T, M, R, S>(rules: &[R], select: S, tree: T, meta: M) -> (T, M)

92

6

where

93

6

    T: Uniplate,

94

6

    R: Rule<T, M>,

95

6

    S: Fn(&T, &mut dyn Iterator<Item = (&R, Reduction<T, M>)>) -> Option<Reduction<T, M>>,

96

6

97

6

    reduce(

98

37

        |commands, subtree, meta| {

99

37

            let selection = select(

100

37

                subtree,

101

164

                &mut rules.iter().filter_map(|rule| {

102

164

                    Reduction::apply_transform(|c, t, m| rule.apply(c, t, m), subtree, meta)

103

164

                        .map(|r| (rule, r))

104

164

}),

105

37

);

106

37

            selection.map(|r| {

107

14

                // Ensure commands used by the engine are the ones resulting from this reduction

108

14

                *commands = r.commands;

109

14

                r.new_tree

110

37

})

111

37

},

112

6

        tree,

113

6

        meta,

114

6

115

6