Faster parsing by changing source location representation

[expipiplus1]

I noticed that the documentation for megaparsec says that getSourcePos "is not cheap, do not call it e.g. on matching of every token, that's a bad idea".

We currently call this twice for every expression. I wonder if it would be possible to change the source position representation in the parser to be a token (character) offset instead, which is very cheap (getOffset). If the user has requested a parse without source positions then this is discarded, else it's transformed into full line and column representation (sufficient laziness could even make this automatic, the location translation isn't even performed until the pretty error message needs to be printed for example).

This would also benefit downstream users who actually want the character offset and who currently have to reconstruct this from the line and column position!

Defining getSourcePos = pure (SourcePos "" (mkPos 0) (mkPos 0)) does speed things up significantly:

[layus]

That's a neat improvement :-). How much work does this represent ?

[expipiplus1]

I suspect that given the very pleasing type of expressions in hnix it shouldn't be too much trouble at all.

• Very easy to switch to the character offsets, just changing a handful of lines in the parser.
• Writing a function to convert these to line/col representation, would just be a recursive traversal of the expression tree keeping state of where we are in the file.

I think writing tests would probably be the most time-consuming part :D

Not sure if there are any performance penalties lurking where I haven't thought about though.

[Anton-Latukha]

In #1026 I also note that the current Pos type produces in Expr.Types 10 orphan instances, notification on which currently suppressed.

[Anton-Latukha]

What do you think about https://hackage.haskell.org/package/monoid-subclasses-1.1.2/docs/Data-Monoid-Instances-Positioned.html.

[Anton-Latukha]

Or just use: https://hackage.haskell.org/package/megaparsec-9.0.1/docs/Text-Megaparsec.html#v:PosState

[expipiplus1]

Yeah, the latter might be good, but it's still calculating line/col offsets strictly which might be the slow bit.

…

On Sat, 22 Jan 2022, 5:37 am Anton Latukha, ***@***.***> wrote: Or just use: https://hackage.haskell.org/package/megaparsec-9.0.1/docs/Text-Megaparsec.html#v:PosState — Reply to this email directly, view it on GitHub <#746 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGRJXEG6VYHQTVY4DX24EDUXHGXVANCNFSM4TGI6NAA> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you authored the thread.Message ID: ***@***.***>