regast-core 0.1.0

Parse-tree matching backends for regast
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

use std::cmp::Ordering;

use crate::{Disambiguation, IrId, IrKind, IrPool, Value};

pub(crate) fn compare_values(
    pool: &IrPool,
    root: IrId,
    left: &Value,
    right: &Value,
    disambiguation: Disambiguation,
) -> Ordering {
    if disambiguation == Disambiguation::Posix {
        let length = left.byte_len().cmp(&right.byte_len());
        if length != Ordering::Equal {
            return length;
        }
    } else if prefers_empty(pool, root) {
        let length = left.byte_len().cmp(&right.byte_len()).reverse();
        if length != Ordering::Equal {
            return length;
        }
    } else if matches!(pool.kind(root), IrKind::Alt(_, _, _, false)) {
        let length = left.byte_len().cmp(&right.byte_len());
        if length != Ordering::Equal {
            return length;
        }
    }

    match (pool.kind(root), left, right) {
        (IrKind::One | IrKind::Anchor(..) | IrKind::Class(..), ..) => Ordering::Equal,
        (IrKind::Alt(left_ir, _, _, _), Value::Left(left), Value::Left(right)) => {
            compare_values(pool, *left_ir, left, right, disambiguation)
        }
        (IrKind::Alt(_, right_ir, _, _), Value::Right(left), Value::Right(right)) => {
            compare_values(pool, *right_ir, left, right, disambiguation)
        }
        (IrKind::Alt(..), Value::Left(_), Value::Right(_)) => Ordering::Greater,
        (IrKind::Alt(..), Value::Right(_), Value::Left(_)) => Ordering::Less,
        (IrKind::Seq(left_ir, right_ir, _), Value::Seq(ll, lr), Value::Seq(rl, rr)) => {
            compare_values(pool, *left_ir, ll, rl, disambiguation)
                .then_with(|| compare_values(pool, *right_ir, lr, rr, disambiguation))
        }
        (IrKind::Star(inner, _, greedy), Value::Stars(left), Value::Stars(right)) => {
            compare_repetitions(pool, *inner, left, right, disambiguation, *greedy)
        }
        (IrKind::Zero, ..) => unreachable!("zero has no values"),
        _ => unreachable!("values must be typed by the compared IR"),
    }
}

fn compare_repetitions(
    pool: &IrPool,
    inner: IrId,
    left: &[Value],
    right: &[Value],
    disambiguation: Disambiguation,
    greedy: bool,
) -> Ordering {
    if disambiguation == Disambiguation::Greedy {
        let length = total_length(left).cmp(&total_length(right));
        if length != Ordering::Equal {
            return if greedy { length } else { length.reverse() };
        }
    }

    for (left, right) in left.iter().zip(right) {
        let order = compare_values(pool, inner, left, right, disambiguation);
        if order != Ordering::Equal {
            return order;
        }
    }
    left.len().cmp(&right.len())
}

fn total_length(values: &[Value]) -> usize {
    values.iter().map(Value::byte_len).sum()
}

fn prefers_empty(pool: &IrPool, root: IrId) -> bool {
    match pool.kind(root) {
        IrKind::One => true,
        IrKind::Star(_, _, greedy) => !greedy,
        IrKind::Alt(left, right, _, true) => {
            if nullable(pool, *left) {
                prefers_empty(pool, *left)
            } else {
                prefers_empty(pool, *right)
            }
        }
        IrKind::Seq(left, right, _) => prefers_empty(pool, *left) && prefers_empty(pool, *right),
        IrKind::Zero | IrKind::Anchor(..) | IrKind::Class(..) | IrKind::Alt(..) => false,
    }
}

fn nullable(pool: &IrPool, root: IrId) -> bool {
    match pool.kind(root) {
        IrKind::One | IrKind::Star(..) => true,
        IrKind::Alt(left, right, ..) => nullable(pool, *left) || nullable(pool, *right),
        IrKind::Seq(left, right, _) => nullable(pool, *left) && nullable(pool, *right),
        IrKind::Zero | IrKind::Anchor(..) | IrKind::Class(..) => false,
    }
}