Grcov report - dependency

1

use std::fmt;

2

3

use log::trace;

4

5

/// Represents a dependency graph between variables used in symbolic transition relations.

6

pub struct DependencyGraph {

7

    /// The list of relations in the dependency graph.

8

    relations: Vec<Relation>,

9

10

    /// The number of vertices

11

    num_of_vertices: usize,

12

13

14

impl DependencyGraph {

15

    /// Creates a new dependency graph from the given relations.

16

1

    pub fn new(relations: Vec<Relation>) -> Self {

17

1

        let num_of_vertices = relations

18

1

            .iter()

19

10

            .flat_map(|rel| rel.read_vars.iter().chain(rel.write_vars.iter()))

20

1

            .copied()

21

1

            .max()

22

1

            .map_or(0, |max_index| max_index + 1);

23

24

1

        DependencyGraph {

25

1

            relations,

26

1

            num_of_vertices,

27

1

28

1

29

30

    /// Restrict the dependency graph to the given vertices, and reorder them according to the given order.

31

    pub fn reorder(&self, vertices: &[usize]) -> Self {

32

        let mut new_relations = Vec::with_capacity(self.relations.len());

33

34

        for relation in &self.relations {

35

            let mut new_read_vars: Vec<usize> = relation

36

                .read_vars()

37

                .filter_map(|var| vertices.iter().position(|&v| v == var))

38

                .collect();

39

40

            let mut new_write_vars: Vec<usize> = relation

41

                .write_vars()

42

                .filter_map(|var| vertices.iter().position(|&v| v == var))

43

                .collect();

44

45

            new_read_vars.sort_unstable();

46

            new_write_vars.sort_unstable();

47

48

            if !new_read_vars.is_empty() || !new_write_vars.is_empty() {

49

                new_relations.push(Relation::new(new_read_vars, new_write_vars));

50

51

52

53

        DependencyGraph::new(new_relations)

54

55

56

    /// Returns the number of vertices in the dependency graph.

57

    pub fn num_of_vertices(&self) -> usize {

58

        self.num_of_vertices

59

60

61

    /// Number of relations in the dependency graph.

62

    pub fn num_of_relations(&self) -> usize {

63

        self.relations.len()

64

65

66

    /// Returns an iterator over the relations in the dependency graph.

67

    pub fn relations(&self) -> impl Iterator<Item = &Relation> {

68

        self.relations.iter()

69

70

71

    /// Returns the total span of all relations in the dependency graph.

72

    pub fn total_span(&self) -> usize {

73

        self.relations.iter().map(|rel| rel.span()).sum()

74

75

76

77

impl fmt::Debug for DependencyGraph {

78

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

79

        writeln!(

80

f,

81

            "graph with {} vertices, and {} hyper-edges",

82

            self.num_of_vertices,

83

            self.relations.len()

84

)?;

85

        for (i, relation) in self.relations.iter().enumerate() {

86

            writeln!(f, "  {}: {:?}", i, relation)?;

87

88

        Ok(())

89

90

91

92

/// A single relation in the dependency graph containing read and write

93

/// dependencies onto variables, given by their indices.

94

pub struct Relation {

95

    read_vars: Vec<usize>,

96

    write_vars: Vec<usize>,

97

98

99

impl Relation {

100

    /// Create a new relation or hyper-edge.

101

    pub fn new(read_vars: Vec<usize>, write_vars: Vec<usize>) -> Self {

102

        Relation { read_vars, write_vars }

103

104

105

    /// Returns an iterator over the read variables in this relation.

106

    pub fn read_vars(&self) -> impl Iterator<Item = usize> + '_ {

107

        self.read_vars.iter().copied()

108

109

110

    /// Returns an iterator over the write variables in this relation.

111

    pub fn write_vars(&self) -> impl Iterator<Item = usize> + '_ {

112

        self.write_vars.iter().copied()

113

114

115

    /// Returns the span of the relation, i.e., the range between the minimum and maximum

116

    /// variable indices used by this relation.

117

    pub fn span(&self) -> usize {

118

        let min_read = self.read_vars.iter().min().copied().unwrap_or(usize::MAX);

119

        let max_read = self.read_vars.iter().max().copied().unwrap_or(0);

120

        let min_write = self.write_vars.iter().min().copied().unwrap_or(usize::MAX);

121

        let max_write = self.write_vars.iter().max().copied().unwrap_or(0);

122

123

        let min_var = min_read.min(min_write);

124

        let max_var = max_read.max(max_write);

125

126

        if max_var >= min_var { max_var - min_var + 1 } else { 0 }

127

128

129

130

impl fmt::Debug for Relation {

131

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

132

        write!(f, "{:?} -> {:?}", self.read_vars, self.write_vars)

133

134

135

136

/// Parses a dependency graph as output by the `--info` option of both

137

/// [lpreach](https://mcrl2.org/web/user_manual/tools/release/lpsreach.html) and

138

/// [pbessolvesymbolic](https://mcrl2.org/web/user_manual/tools/release/pbessolvesymbolic.html).

139

1

pub fn parse_compacted_dependency_graph(input: &str) -> DependencyGraph {

140

1

    trace!("Parsing dependency graph:\n{}", input);

141

1

    let mut relations = Vec::new();

142

143

10

    for line in input.lines() {

144

10

        if line == "read/write patterns compacted" {

145

            continue;

146

10

147

148

        // Keep only pattern characters, ignoring indices/whitespace

149

131

        let pattern: Vec<char> = line.chars().filter(|c| matches!(c, '+' | '-' | 'r' | 'w')).collect();

150

151

10

        if pattern.is_empty() {

152

            continue;

153

10

154

155

10

        let mut read_vars = Vec::new();

156

10

        let mut write_vars = Vec::new();

157

158

110

        for (col, ch) in pattern.into_iter().enumerate() {

159

110

            match ch {

160

26

                '+' => {

161

26

                    read_vars.push(col);

162

26

                    write_vars.push(col);

163

26

164

3

                'r' => read_vars.push(col),

165

10

                'w' => write_vars.push(col),

166

71

                '-' => {}

167

                _ => {}

168

169

170

171

10

        relations.push(Relation { read_vars, write_vars });

172

173

174

1

    DependencyGraph::new(relations)

175

1

176

177

#[cfg(test)]

178

mod tests {

179

    use crate::parse_compacted_dependency_graph;

180

181

    #[test]

182

1

    fn test_parse_abp_dependency_graph() {

183

1

        let input = "1 +w---------

184

1

2 ---+++-----

185

1

3 ------++---

186

1

4 --------++-

187

1

5 ------+w+w+

188

1

6 ---+ww--+w-

189

1

7 ---+++--+wr

190

1

8 +-----+w---

191

1

9 +rr+ww-----

192

1

10 +++---++---";

193

194

1

        let graph = parse_compacted_dependency_graph(input);

195

196

1

        assert_eq!(graph.relations.len(), 10);

197

1

198