Grcov report - mock

1

#![allow(dead_code)]

2

3

use merc_explore::LPS;

4

use merc_explore::Summand;

5

use merc_utilities::MercError;

6

7

/// Action label produced by a transition: the label of the firing summand.

8

pub(crate) type Label = u32;

9

10

/// A reachable state, as a vector of coordinate values.

11

pub(crate) type State = Vec<usize>;

12

13

/// A single transition over state vectors, `(source, label, target)`.

14

pub(crate) type Edge = (State, Label, State);

15

16

/// A mock [`LPS`] over numbered state vectors of fixed dimension.

17

///

18

/// Each summand is a guarded increment: a conjunction of strict-`<` inequality

19

/// guards on individual coordinates and an effect that, when every guard holds,

20

/// adds a value to a set of coordinates.

21

#[derive(Clone)]

22

pub(crate) struct MockLps {

23

    initial: State,

24

    summands: Vec<MockSummand>,

25

26

27

impl MockLps {

28

    /// Builds an LPS from an initial vector and a set of summands.

29

40

    pub(crate) fn new(initial: State, summands: Vec<MockSummand>) -> MockLps {

30

40

        MockLps { initial, summands }

31

40

32

33

    /// A `d`-dimensional grid: one increment-summand per coordinate `i`, guarded

34

    /// by the single inequality `state[i] < bounds[i]`.

35

27

    pub(crate) fn grid(bounds: &[usize]) -> MockLps {

36

27

        let summands = (0..bounds.len())

37

54

            .map(|i| MockSummand::new(i as Label, vec![(i, bounds[i])], vec![i]))

38

27

            .collect();

39

27

        MockLps::new(vec![0; bounds.len()], summands)

40

27

41

42

    /// A `d`-dimensional grid whose coordinate-`i` summand, instead of a fixed

43

    /// `+1`, adds any value in `0..=steps[i]`, fanning out into several

44

    /// successors per state. The `steps` give a different `k` for every state

45

    /// parameter; a `steps[i]` of `0` makes that summand a guarded self-loop.

46

13

    pub(crate) fn grid_with_steps(bounds: &[usize], steps: &[usize]) -> MockLps {

47

13

        assert_eq!(bounds.len(), steps.len(), "one step bound per coordinate");

48

13

        let summands = (0..bounds.len())

49

25

            .map(|i| MockSummand::with_step(i as Label, vec![(i, bounds[i])], i, steps[i]))

50

13

            .collect();

51

13

        MockLps::new(vec![0; bounds.len()], summands)

52

13

53

54

    /// A grid extended with a "diagonal" summand whose guard is a conjunction of

55

    /// two inequalities and whose effect increments both coordinates at once.

56

    /// Requires at least two dimensions.

57

8

    pub(crate) fn grid_with_diagonal(bounds: &[usize]) -> MockLps {

58

8

        assert!(bounds.len() >= 2, "diagonal needs at least two dimensions");

59

8

        let mut lps = MockLps::grid(bounds);

60

8

        lps.summands.push(MockSummand::new(

61

8

            bounds.len() as Label,

62

8

            vec![(0, bounds[0]), (1, bounds[1])],

63

8

            vec![0, 1],

64

));

65

8

lps

66

8

67

68

69

/// A guarded-increment summand of [`MockLps`].

70

#[derive(Clone)]

71

pub(crate) struct MockSummand {

72

    label: Label,

73

    /// Conjunction of guards, each requiring `state[pos] < bound`.

74

    guards: Vec<(usize, usize)>,

75

    /// Effect: per written coordinate, the inclusive `(pos, lo, hi)` interval of

76

    /// values added to it when every guard holds. The cartesian product of these

77

    /// intervals enumerates the successors.

78

    increments: Vec<(usize, usize, usize)>,

79

    read_positions: Vec<usize>,

80

    write_positions: Vec<usize>,

81

82

83

impl MockSummand {

84

    /// Creates a summand that adds one to each listed coordinate, producing a

85

    /// single successor per state.

86

62

    pub(crate) fn new(label: Label, guards: Vec<(usize, usize)>, increments: Vec<usize>) -> MockSummand {

87

70

        let increments = increments.into_iter().map(|pos| (pos, 1, 1)).collect();

88

62

        MockSummand::with_intervals(label, guards, increments)

89

62

90

91

    /// Creates a summand that adds any value in `0..=step` to `pos`, producing

92

    /// `step + 1` successors per state.

93

25

    pub(crate) fn with_step(label: Label, guards: Vec<(usize, usize)>, pos: usize, step: usize) -> MockSummand {

94

25

        MockSummand::with_intervals(label, guards, vec![(pos, 0, step)])

95

25

96

97

    /// Creates a summand from its guard conjunction and per-coordinate delta

98

    /// intervals, deriving the read/write position sets the cache contract

99

    /// requires.

100

87

    pub(crate) fn with_intervals(

101

87

        label: Label,

102

87

        guards: Vec<(usize, usize)>,

103

87

        increments: Vec<(usize, usize, usize)>,

104

87

    ) -> MockSummand {

105

        // The result depends on every guarded coordinate and, because the

106

        // effect is a relative increment, on every written coordinate too.

107

87

        let mut read_positions: Vec<usize> = guards

108

87

            .iter()

109

87

            .map(|&(pos, _)| pos)

110

87

            .chain(increments.iter().map(|&(pos, _, _)| pos))

111

87

            .collect();

112

87

        read_positions.sort_unstable();

113

87

        read_positions.dedup();

114

115

87

        let mut write_positions: Vec<usize> = increments.iter().map(|&(pos, _, _)| pos).collect();

116

87

        write_positions.sort_unstable();

117

87

        write_positions.dedup();

118

119

87

        MockSummand {

120

87

            label,

121

87

            guards,

122

87

            increments,

123

87

            read_positions,

124

87

            write_positions,

125

87

126

87

127

128

3389

    fn fires(&self, state: &[usize]) -> bool {

129

3761

        self.guards.iter().all(|&(pos, bound)| state[pos] < bound)

130

3389

131

132

133

/// Per-thread scratch for [`MockSummand::enumerate`]: the next-state buffer.

134

#[derive(Default)]

135

pub(crate) struct MockContext {

136

    next: State,

137

138

139

impl LPS for MockLps {

140

    type Value = usize;

141

    type Label = Label;

142

    type StateInfo = State;

143

    type Summand = MockSummand;

144

145

94

    fn initial_state(&self) -> State {

146

94

        self.initial.clone()

147

94

148

149

1757

    fn summands(&self) -> &[MockSummand] {

150

1757

        &self.summands

151

1757

152

153

178

    fn create_context(&self) -> MockContext {

154

178

        MockContext::default()

155

178

156

157

1377

    fn prepare<'a>(&'a self, _context: &mut MockContext, _state: &'a [usize]) -> impl Iterator<Item = usize> + 'a {

158

1377

        0..self.summands.len()

159

1377

160

161

1377

    fn state_info(&self, state: &[usize]) -> State {

162

        // Surface the live state vector so tests can map dense indices back to

163

        // the concrete vectors the drivers assign them.

164

1377

        state.to_vec()

165

1377

166

167

168

impl Summand for MockSummand {

169

    type Value = usize;

170

    type Label = Label;

171

    type Context = MockContext;

172

173

3389

    fn enumerate<F>(&self, context: &mut MockContext, state: &[usize], mut report: F) -> Result<(), MercError>

174

3389

    where

175

3389

        F: FnMut(&Label, &[usize]) -> Result<(), MercError>,

176

177

3389

        if !self.fires(state) {

178

1106

            return Ok(());

179

2283

180

181

        // Mixed-radix odometer over the inclusive delta intervals: each setting

182

        // of `deltas` is one point of the cartesian product, hence one successor.

183

2283

        let mut deltas: Vec<usize> = self.increments.iter().map(|&(_, lo, _)| lo).collect();

184

        loop {

185

2737

            context.next.clear();

186

2737

            context.next.extend_from_slice(state);

187

3016

            for (&(pos, _, _), &delta) in self.increments.iter().zip(&deltas) {

188

3016

                context.next[pos] += delta;

189

3016

190

2737

            report(&self.label, &context.next)?;

191

192

            // Advance the rightmost digit that has not reached its upper bound,

193

            // resetting the digits to its right; stop once all are saturated.

194

2735

            let mut digit = self.increments.len();

195

            loop {

196

5295

                if digit == 0 {

197

2281

                    return Ok(());

198

3014

199

3014

                digit -= 1;

200

3014

                let (_, _, hi) = self.increments[digit];

201

3014

                if deltas[digit] < hi {

202

454

                    deltas[digit] += 1;

203

454

                    for (slot, &(_, lo, _)) in deltas[digit + 1..].iter_mut().zip(&self.increments[digit + 1..]) {

204

                        *slot = lo;

205

206

454

                    break;

207

2560

208

209

210

3389

211

212

40

    fn read_positions(&self) -> &[usize] {

213

40

        &self.read_positions

214

40

215

216

40

    fn write_positions(&self) -> &[usize] {

217

40

        &self.write_positions

218

40

219