Skip to content
← Back

src/analysis/outer_span_filter.ghul

1
@@IF.dotnet()
2
3
namespace Analysis is
4
use Collections.LIST
5
use Collections.List
6
7
use Source.LOCATION
8
9
// Drops every span that properly contains another span in the same
10
// set, keeping the innermost ones.
11
//
12
// A desugared expression records its use at the whole original source
13
// span. That is what hover wants and what a semantic token must not
14
// be: one token covering a run of identifiers and operators instead
15
// of one token for each of them.
16
//
17
// Ordering, not comparison, is what makes this affordable. Sorted by
18
// start ascending and end descending, every span a given span could
19
// contain sits somewhere after it, so a single sweep carrying the
20
// smallest end seen so far answers the question for all of them at
21
// once. Comparing every pair instead costs the square of the file's
22
// recorded uses, which on a few thousand lines is most of a second.
23
class OUTER_SPAN_FILTER is
24
init() is si
25
26
apply[T](items: List[T], location_of: (T) -> LOCATION) -> LIST[T] is
27
let ordered = LIST[T](items)
28
29
ordered.sort(
30
(left: T, right: T) -> int =>
31
let l = location_of(left) in
32
let r = location_of(right) in
33
if l.start != r.start then
34
l.start - r.start
35
else
36
r.end - l.end
37
fi
38
)
39
40
let count = ordered.count
41
42
// smallest_end_from[i] is the smallest end among the spans at
43
// i and after it, built back to front and then turned round.
44
let smallest_end_from = LIST[int](count)
45
46
let smallest mut = 0
47
let back mut = count - 1
48
49
while back >= 0 do
50
let end = location_of(ordered[back]).end
51
52
if back == count - 1 \/ end < smallest then
53
smallest = end
54
fi
55
56
smallest_end_from.add(smallest)
57
58
back = back - 1
59
od
60
61
smallest_end_from.reverse()
62
63
let result = LIST[T]()
64
65
// Spans that start at the same place need their own pass:
66
// sorted widest first, each is a candidate container for the
67
// ones behind it in its own group as well as for everything
68
// in the groups that follow.
69
let group_start mut = 0
70
71
while group_start < count do
72
let start = location_of(ordered[group_start]).start
73
74
let group_end mut = group_start
75
76
while
77
group_end + 1 < count /\
78
location_of(ordered[group_end + 1]).start == start
79
do
80
group_end = group_end + 1
81
od
82
83
let smallest_in_group = location_of(ordered[group_end]).end
84
85
let has_later_group = group_end + 1 < count
86
87
let smallest_after =
88
if has_later_group then
89
smallest_end_from[group_end + 1]
90
else
91
0
92
fi
93
94
for i in group_start::group_end do
95
let end = location_of(ordered[i]).end
96
97
let contains_another =
98
smallest_in_group < end \/
99
(has_later_group /\ smallest_after <= end)
100
101
if !contains_another then
102
result.add(ordered[i])
103
fi
104
od
105
106
group_start = group_end + 1
107
od
108
109
return result
110
si
111
si
112
si