Grcov report - alias.rs

1

use std::collections::HashMap;

2

use std::ops::ControlFlow;

3

4

use merc_collections::BlockIndex;

5

use merc_collections::BlockPartition;

6

use merc_collections::Graph;

7

use merc_collections::scc_decomposition;

8

use merc_syntax::DefId;

9

use merc_syntax::SortExpression;

10

use merc_syntax::UntypedDataSpecification;

11

use merc_syntax::visit_sort_expr;

12

use merc_utilities::TagIndex;

13

14

/// Returns true iff there is a cycle in the alias declarations.

15

3

pub fn has_alias_cycle(spec: &UntypedDataSpecification) -> Result<(), Vec<DefId>> {

16

    // A mapping that keeps track of the relation between sorts.

17

3

    let mut mapping: HashMap<DefId, Vec<DefId>> = HashMap::new();

18

19

5

    for sort_decl in &spec.sort_declarations {

20

5

        if let Some(alias) = &sort_decl.expr {

21

3

            let mut visited = Vec::new();

22

23

3

            visit_sort_expr::<(), _>(alias, |sort| {

24

3

                if let SortExpression::Resolved(_, id) = sort {

25

3

                    visited.push(*id);

26

3

27

28

3

                ControlFlow::Continue(())

29

3

});

30

31

3

            mapping.insert(sort_decl.id.expect("Name must have been resolved"), visited);

32

2

33

34

35

3

    let scc_partition =

36

3

        BlockPartition::<()>::from_indexed_partition(&scc_decomposition(&SortGraph { mapping }, |_, _, _| true));

37

38

3

    for block in (0..scc_partition.len()).map(BlockIndex::new) {

39

1

        if scc_partition.block(block).len() > 1 {

40

3

            return Err(scc_partition.iter_block(block).map(|id| DefId::new(id)).collect());

41

42

43

2

    Ok(())

44

3

45

46

/// A graph structure representing the alias declarations in a data

47

/// specification. The vertices are the sorts, and there is an edge from sort A

48

/// to sort B if B is contained in the alias of A, i.e. `A -> B` if `A = List(B)`.

49

struct SortGraph {

50

    mapping: HashMap<DefId, Vec<DefId>>,

51

52

53

/// A unique type for the sorts.

54

pub struct SortTag;

55

56

/// The index type for a sort.

57

pub type SortIndex = TagIndex<usize, SortTag>;

58

59

impl Graph for SortGraph {

60

    type VertexIndex = SortIndex;

61

62

    type LabelIndex = ();

63

64

18

    fn num_of_vertices(&self) -> usize {

65

24

        self.mapping.keys().map(|id| **id).max().map_or(0, |max_id| max_id + 1)

66

18

67

68

9

    fn iter_vertices(&self) -> impl Iterator<Item = Self::VertexIndex> {

69

9

        (0..self.num_of_vertices()).map(SortIndex::new)

70

9

71

72

3

    fn outgoing_edges(&self, vertex: Self::VertexIndex) -> impl Iterator<Item = (Self::LabelIndex, Self::VertexIndex)> {

73

3

        self.mapping

74

3

            .get(&DefId::new(*vertex))

75

3

            .into_iter()

76

3

            .flat_map(|targets| targets.iter())

77

3

            .map(|id| ((), SortIndex::new(**id)))

78

3

79

80

81

#[cfg(test)]

82

mod tests {

83

    use merc_syntax::UntypedDataSpecification;

84

85

    use crate::DataSpecification;

86

    use crate::WellTypedError;

87

88

    #[test]

89

1

    fn test_trivial_alias_cycle() {

90

1

        let spec = UntypedDataSpecification::parse(

91

1

            "sort S = T;

92

1

            T = U;

93

1

            U = S;",

94

95

1

        .unwrap();

96

97

1

        match DataSpecification::from_untyped(spec) {

98

1

            Err(WellTypedError::AliasCycle { sorts })

99

1

                if sorts == vec!["S".to_string(), "T".to_string(), "U".to_string()] => {}

100

            Err(other) => panic!("Unexpected error {:?}", other),

101

            _ => panic!("Expected from_untyped to fail"),

102

103

1

104