location_info 0.1.0-alpha-1

/*!
A library defining a type for wrapping values in their corresponding source code location, and
conveniently creating and transforming these without loosing track of the location.

## Setup

The crate is generic over your compiler's source code location representation, and for
convenience it is probably a good idea to create a type alias for your particluar type.
For example, if representing your locations as a file ID along with a byte range, you would
write
```
use location_info::{Location};

// Define the location type
#[derive(Clone)]
pub struct Span(usize, std::ops::Range<u64>);

impl Location for Span {
    fn nowhere() -> Self {
        // Here users of our compiler should never encounter thigns without valid
        // source mapping, so we'll use a dummy value.
        Span(0, 0..0)
    }
    
    fn between(Self(start_file, start_range): &Self, Self(end_file, end_range): &Self) -> Self {
        assert!(start_file == end_file); // A location spanning multiple files is weird
        Span(*start_file, start_range.start.min(end_range.start) .. start_range.end.max(end_range.end))
    }
}

// Avoid having to specify the other generic parameter in your compiler
type Loc<T> = location_info::Loc<T, Span>;
```

It can also be helpful to implement `From<T>` for your Location type for Ts which
you will often convert into locations. For example, tokens in your parser:

```
# pub struct Span(usize, std::ops::Range<u64>);

enum TokenKind {
    // ...
}
struct Token {
    kind: TokenKind,
    file: usize,
    offset: std::ops::Range<u64>
}

impl From<&Token> for Span {
    fn from(tok: &Token) -> Span {
        Span(tok.file, tok.offset.clone())
    }
}
```

## Usage

To use the crate, wrap the values you want to track the source location of in `Loc<T>`. For
example, an AST node for function heads might look like

```
# #[derive(Clone)]
# struct Empty;
# impl location_info::Location for Empty {
#     fn nowhere() -> Self { Empty }
#     fn between(_: &Self, _: &Self) -> Self { Empty }
# }
# type Loc<T> = location_info::Loc<T, ()>;
struct Identifier(String);
struct FnHead {
    fn_keyword: Loc<()>,
    name: Loc<Identifier>,
    args: Loc<Vec<Loc<Identifier>>>
}
```

Attaching location info is done using the methods in [WithLocation].

```
use location_info::WithLocation;
# use location_info::{Location};
# 
# // Define the location type
# #[derive(Clone)]
# pub struct Span(usize, std::ops::Range<u64>);
# 
# impl Location for Span {
#     fn nowhere() -> Self {
#         // Here users of our compiler should never encounter thigns without valid
#         // source mapping, so we'll use a dummy value.
#         Span(0, 0..0)
#     }
#     
#     fn between(Self(start_file, start_range): &Self, Self(end_file, end_range): &Self) -> Self {
#         assert!(start_file == end_file); // A location spanning multiple files is weird
#         Span(*start_file, start_range.start.min(end_range.start) .. start_range.end.max(end_range.end))
#     }
# }
# 
# // Avoid having to specify the other generic parameter in your compiler
# type Loc<T> = location_info::Loc<T, Span>;
enum TokenKind {
    Fn,
    Identifier(String),
    OpenParen,
    CloseParen,
}

# struct Token {
#     kind: TokenKind,
#     file: usize,
#     offset: std::ops::Range<u64>
# }
# 
# impl From<&Token> for Span {
#     fn from(tok: &Token) -> Span {
#         Span(tok.file, tok.offset.clone())
#     }
# }
# 
# type Result<T> = std::result::Result<T, ()>;
# #[derive(Clone)]
# struct Empty;
# impl location_info::Location for Empty {
#     fn nowhere() -> Self { Empty }
#     fn between(_: &Self, _: &Self) -> Self { Empty }
# }
# #[derive(Clone)]
# struct Identifier(String);
# struct FnHead {
#     fn_keyword: Loc<()>,
#     name: Loc<Identifier>,
#     args: Loc<Vec<Loc<Identifier>>>
# }
# fn parse_ident(tokens: &mut impl Iterator<Item=Token>) -> Result<Loc<Identifier>> {
#     Ok(Identifier(String::new()).nowhere())
# }
# fn parse_fn_keyword(tokens: &mut impl Iterator<Item=Token>) -> Result<Token> {
#     Ok(tokens.next().unwrap())
# }
# fn parse_open_paren(tokens: &mut impl Iterator<Item=Token>) -> Result<Token> {
#     Ok(tokens.next().unwrap())
# }
# fn parse_close_paren(tokens: &mut impl Iterator<Item=Token>) -> Result<Token> {
#     Ok(tokens.next().unwrap())
# }
fn parse_fn_head(tokens: &mut impl Iterator<Item=Token>) -> Result<Loc<FnHead>> {
    let fn_keyword = parse_fn_keyword(tokens)?;
    let name = parse_ident(tokens)?;

    let open_paren = parse_open_paren(tokens)?;
    let mut args_raw = vec![];
    while let ident @ Loc{inner: Identifier(_), ..} = parse_ident(tokens)? {
        args_raw.push(ident);
    }
    let close_paren = parse_close_paren(tokens)?;
    // The span of the argument list is the span between open_paren and close_paren
    let args = args_raw.between(&open_paren, &close_paren);

    Ok(
        FnHead {
            // We don't want the token, just a Loc<()>, those can be created
            // with ().at(...)
            fn_keyword: ().at(&fn_keyword),
            name,
            args
        }.between(&fn_keyword, &close_paren)
    )
}
```

### Mapping

After location info has been created, it is often useful to be able to transform
the internal struct, for example when lowering from one IR to another. The [Loc] struct
has several functions mapping over the contained value.


*/

use serde::{Deserialize, Serialize};

/// Trait to implement for types representing a source code location
pub trait Location: Clone {
    /// Create a Location which does not correspond to a source code location.
    /// Depending on how the lbirary is used in a compiler, this can either be a placeholder
    /// value, in which case encountering a `nowhere` when reporting an error
    /// is probably an error, or if source locations can be missing it should be an actual
    /// marker.
    fn nowhere() -> Self;

    /// Create a location that spans `start` to `end`. For example, this is used
    /// when creating a loc spanning a parenthesised expression from the start
    /// and end parens.
    /// ```notest
    /// ( ... stuff ... )`
    /// ^               ^
    /// start           end
    /// ^^^^^^^^^^^^^^^^^ <- between
    /// ```
    fn between(start: &Self, end: &Self) -> Self;
}

pub trait WithLocation<L: Location>: Sized {
    /// Wrap `Self` in a location
    fn at(self, span: impl Into<L>) -> Loc<Self, L>
    where
        Self: Sized,
    {
        Loc::new(self, span.into())
    }

    /// Creates a new Loc at the same source code location as another Loc
    fn at_loc<T: Sized>(self, loc: &Loc<T, L>) -> Loc<Self, L> {
        Loc::new(self, loc.loc.clone())
    }

    /// Create a location that spans `start` and `end`
    fn between(self, start: impl Into<L>, end: impl Into<L>) -> Loc<Self, L> {
        Loc::new(self, L::between(&start.into(), &end.into()))
    }

    /// Create a location that spans `start` and `end`
    fn between_locs<T, Y>(self, start: &Loc<T, L>, end: &Loc<Y, L>) -> Loc<Self, L> {
        Loc::new(self, L::between(&start.loc, &end.loc))
    }

    /// Create a Location which does not correspond to a source code location.
    /// Depending on how the lbirary is used in a compiler, this can either be a placeholder
    /// value, in which case encountering a `nowhere` when reporting an error
    /// is probably an error, or if source locations can be missing it should be an actual
    /// marker.
    fn nowhere(self) -> Loc<Self, L>
    where
        Self: Sized,
    {
        self.at(L::nowhere())
    }
}

// Impl WithLocation for any types
impl<T, L> WithLocation<L> for T where L: Clone + Location {}

/// A value wrapped along with a corresponding source code location.
///
/// Typically, Locs should be created using the `WithLocation` trait.
///
/// **NOTE** This type is designed to be transparent, i.e. it behaves as `T` in many cases. In
/// particular, comparisons such as Hash, PartialEq, PartialOrd, etc. completely ignore the location
/// and only compare T.
///
/// In addition, the type implements `Deref<Target=T>` which means that `Loc<T>` can be passed
/// directly to functions which expect `&T`
#[derive(Clone, Copy, Serialize, Deserialize)]
pub struct Loc<T, L> {
    pub inner: T,
    pub loc: L,
}

impl<T, L> Loc<T, L>
where
    L: Location,
{
    pub fn new(inner: T, loc: L) -> Self {
        Self { inner, loc }
    }

    /// Create a Location which does not correspond to a source code location.
    /// Depending on how the lbirary is used in a compiler, this can either be a placeholder
    /// value, in which case encountering a `nowhere` when reporting an error
    /// is probably an error, or if source locations can be missing it should be an actual
    /// marker.
    pub fn nowhere(inner: T) -> Self {
        Self::new(inner, L::nowhere())
    }

    /// Remove the location info
    pub fn strip(self) -> T {
        self.inner
    }

    /// Get a reference to the underlying value
    pub fn strip_ref(&self) -> &T {
        &self.inner
    }

    /// Split into self and the location
    pub fn separate(self) -> (Self, L) {
        let loc = self.loc.clone();
        (self, loc)
    }

    pub fn separate_loc(self) -> (Self, Loc<(), L>) {
        let loc = self.loc();
        (self, loc)
    }

    pub fn split(self) -> (T, L) {
        (self.inner, self.loc)
    }
    pub fn split_ref(&self) -> (&T, L) {
        let loc = self.loc.clone();
        (&self.inner, loc)
    }
    pub fn split_loc(self) -> (T, Loc<(), L>) {
        let loc = self.loc();
        (self.inner, loc)
    }
    pub fn split_loc_ref(&self) -> (&T, Loc<(), L>) {
        let loc = self.loc();
        (&self.inner, loc)
    }

    pub fn map<Y>(self, mut op: impl FnMut(T) -> Y) -> Loc<Y, L> {
        Loc {
            inner: op(self.inner),
            loc: self.loc,
        }
    }
    pub fn map_ref<Y>(&self, mut op: impl FnMut(&T) -> Y) -> Loc<Y, L> {
        let loc = self.loc.clone();
        Loc {
            inner: op(&self.inner),
            loc,
        }
    }
    pub fn try_map_ref<Y, E, F>(&self, mut op: F) -> Result<Loc<Y, L>, E>
    where
        F: FnMut(&T) -> Result<Y, E>,
    {
        let loc = self.loc.clone();
        Ok(Loc {
            inner: op(&self.inner)?,
            loc,
        })
    }

    pub fn loc(&self) -> Loc<(), L> {
        let loc = self.loc.clone();
        Loc { inner: (), loc }
    }
}

impl<T, L, E> Loc<Result<T, E>, L>
where
    L: Location,
{
    pub fn map_err<E2>(self, err_fn: impl Fn(E, Loc<(), L>) -> E2) -> Result<Loc<T, L>, E2> {
        match self.inner {
            Ok(inner) => Ok(Loc {
                inner,
                loc: self.loc,
            }),
            Err(e) => Err(err_fn(e, ().at(self.loc))),
        }
    }
}

impl<T, L> PartialEq for Loc<T, L>
where
    T: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        self.inner == other.inner
    }
}

impl<T, L> PartialOrd for Loc<T, L>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.inner.partial_cmp(&other.inner)
    }
}
impl<T, L> Ord for Loc<T, L>
where
    T: Ord,
{
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.inner.cmp(&other.inner)
    }
}

impl<T, L> Eq for Loc<T, L> where T: Eq {}

impl<T, L> std::fmt::Display for Loc<T, L>
where
    T: std::fmt::Display,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.inner)
    }
}

impl<T, L> std::hash::Hash for Loc<T, L>
where
    T: std::hash::Hash,
{
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.inner.hash(state)
    }
}

impl<T, L> std::fmt::Debug for Loc<T, L>
where
    T: std::fmt::Debug,
    L: std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "l({:?})[{:?}]", self.loc, self.inner)
    }
}

impl<T, L> std::ops::Deref for Loc<T, L> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}
impl<T, L> std::ops::DerefMut for Loc<T, L> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.inner
    }
}