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