There should be a way to get the type from a AST expression. While initially this was done using unique identifiers, I have a new idea.
Instead of 'id's on AST, instead use their source position data! It is unique between AST nodes (of the same kind) and already exists, so no need to make AST structs larger. When synthesising expression AST it can use the position/span as a key for assigning a type value. A span is equivalent to a Range<u32>
, so will work with anything that can convert to it. And any AST formats given to Ezno will have position information.
Retrieving these types is useful when doing optimisations after the type synthesis.
And they are also used for retrieving data in the LSP...
Finding a type mapping through looking in a range
In the LSP, a hover request sends a position in the source. A novel way of mapping positions would be HashMap<Span, TypeId>
, however when trying to search data it would have to iterate through each key in the map. While it would be per source LSP it still might be a costly iteration. Instead I am thinking of a data structure which keys values not based on if they match of the range but instead in the range. For example in the following there are several ranges.
Type x + y + 2
3 -
5 -
5 -
8 -----
10 ---------
Given a scalar index is should be able to find the closest mapping.
A quick prototype of the data structure
Here is what I came up with to solve the problem
use std::collections::BTreeMap;
use std::fmt::Debug;
use std::ops::Range;
#[derive(Debug)]
pub struct RangeMap<T> {
entries: BTreeMap<u32, Vec<(u32, T)>>,
}
impl<T> RangeMap<T> {
pub fn new() -> Self {
Self {
entries: Default::default(),
}
}
pub fn push(&mut self, range: Range<u32>, item: T) {
if let Some(existing) = self.entries.get_mut(&range.start) {
existing.push((range.end, item));
} else {
self.entries.insert(range.start, vec![(range.end, item)]);
}
}
pub fn get(&self, point: u32) -> Option<&T> {
self.entries
.range(0..(point + 1))
.rev()
.find_map(|(_, v)| v.iter().find_map(|(e, v)| (*e > point).then_some(v)))
}
pub fn get_exact(&self, range: Range<u32>) -> Option<&T> {
self.entries
.get(&range.start)
.and_then(|v| v.iter().find_map(|(e, v)| (*e == range.end).then_some(v)))
}
}
After writing this I found btree-range-map, but think it is more complicated than above
Note this works because while they can intersect, any intersections are encapsulated (no overhangs).
$$
S_1 \cap S_2 \neq \emptyset \implies S_1 \subset S_2 \vee S_2 \subset S_1
$$