[Feature Request] Position-Aware Parsing

[bhavyakukkar]

I require the EDN tree to have span information associated with each node. I started working on this feature already in a fork, but I cannot find a "clean" enough solution and was hoping to hear your advice if you have any, in case you are interested in merging such a feature.

1. Adding a span field to each enum variant of Edn makes the use of the Edn's impls function slightly annoying since they are not designed to be aware of spans.
   examples/get-nth.rs:15:

     edn
   -    .get(&Edn::Key("foo"))?
   -    .get(&Edn::Symbol("猫"))?
   -    .get(&Edn::Map(BTreeMap::from([(Edn::Key("foo"), Edn::Key("bar"))])))?
   +    .get(&Edn::Key("foo", new_span()))?
   +    .get(&Edn::Symbol("猫", new_span()))?
   +    .get(&Edn::Map(
   +      BTreeMap::from([(Edn::Key("foo", new_span()), Edn::Key("bar", new_span()))]),
   +      new_span(),
   +    ))?
       .nth(2)

   Already added a manual Hash impl so hash of Edn doesn't depend on spans

2. If each of the atom variants held a raw string-slice like Key, Symbol & Str do, it would be possible to produce a better spanned tree from the implementor's side by reverse-engineering it using <*const str>::addr, thought its a hacky solution for something that could be provided by the library

Is having two different enums, Edn and EdnSpanned feasible? In this case the Edn impl functions would remain on Edn, but the parser would produce EdnSpanneds.

[Grinkers]

Could you describe the use case? I'm not quite sure what the span is supposed to do. A clojure equivalent would also be fine. I'm a little confused because EDN nodes are always unidirectional and repeated data ends up as separate nodes (a simple tree).

That being said, what I would be happy to do is create a new namespace parser or something like that. I put everything in the edn namespace for now because that's what is stable/specified. I was eventually going to do this because I want to be able to read other things too, like metadata.

[bhavyakukkar]

By spans I just mean the context in the source string given to the parser, i.e. the line, column & ptr corresponding to where that Edn node started & finished parsing; your Walker already records this anyway and also returns it during an error, thus adding span information was quite an easy thing to do.

A span attached to each node would just be an additional (Pos, Pos) where:

struct Pos {
  line: usize,
  column: usize,
  ptr: usize
}

Sorry, I should have been more clear about what I meant by span, for some reason the term is obvious to me but looking around it might not be a very common term after all and also means other things

[Grinkers]

Got it. I was thinking of spanning in terms of graph theory.

This is also something I would like to have too. Given something like this

;; <- this is line 41
(defn foo [a b c]
  (+ a b))

I want to be able to print something like

Warning: unused variable: `c`
42:  (defn foo [a b c]
                    ^ help: blah blah

I don't have an elegant idea right now, but my gut feeling says to

#[cfg(feature = "unstable")]
pub mod parse;
#[cfg(not(feature = "unstable"))]
mod parse;

I think there's quite good test coverage for EDN, and this would allow experimentation without introducing breaking changes. I'm not sure of the different cases. Like in the above, it should be line 42, not line 1 (if the &str is starting from line 42, the internal parser will see line 1).

If you have any ideas or want to take a try, contributions are very welcome.

[bhavyakukkar]

Like in the above, it should be line 42, not line 1 (if the &str is starting from line 42, the internal parser will see line 1).

I think the best solution to this is to have read (and thus parse) accept a more opaque type that both holds a string-slice and bookkeeps how much of the string-slice has been "read" (edit: along with line & column data of-course)

pub fn parse(edn: &mut SourceReader) -> Result<Edn<'_>, Error>

It seems like the clojure implementation does the same using a bare IPushbackReader but extracting line & column data in case the reader is also a LineNumberingPushbackReader:

		if(r instanceof LineNumberingPushbackReader)
			{
			line = ((LineNumberingPushbackReader) r).getLineNumber();
			column = ((LineNumberingPushbackReader) r).getColumnNumber()-1;
			}

(source of LineNumberingPushbackReader)

Let me know if this is a good place to start. As for spans associated with each node, maybe we can consider starting that after this has been done.

[Grinkers]

I think we can afford to just extend the parser to include the span data. This isn't pub, so we just need to store the position data as it creates the context. If you want, I would welcome a PR. Or I'll eventually get to it.

clojure-reader/src/parse.rs

Lines 23 to 26 in 2215989

	ptr: usize,
	column: usize,
	line: usize,
	stack: Vec<ParseContext<'e>>,

clojure-reader/src/parse.rs

Lines 197 to 205 in 2215989

	enum ParseContext<'e> {
	Top,
	Vector(Vec<Edn<'e>>),
	List(Vec<Edn<'e>>),
	Map(BTreeMap<Edn<'e>, Edn<'e>>, Option<Edn<'e>>),
	Set(BTreeSet<Edn<'e>>),
	Tag(&'e str),
	Discard,
	}

My first attempt would be something like this (don't treat this as gospel, just my first idea):

// lib.rs, opt-in feature while exploring ideas/apis 
#[cfg(feature = "unstable")]
pub mod parse;
#[cfg(not(feature = "unstable"))]
mod parse;

// parse.rs 

// expose internal structures, data, traits, etc. 
// this can be context aware, take a SourceReader, parse things EDN doesn't specify
pub fn parse(data: SomeTypeOrTrait) -> Parsed { ... }

// previously `parse`, now renamed.
pub fn parse_as_edn(data: SomeTypeOrTrait) -> Result<(Edn<'_>, &str), Error> {
  parse(data)?.into()?
}

[bhavyakukkar]

Working on it!