Replying to
@rtzoeller@hachyderm.io
@rtzoeller Thank you very much!
Remote
Sminez 
@sminez@hachyderm.io
mastodon
4.6.6
Innes Anderson-Morrison
Thoughts and ideas (some better than others) from a software engineer and photographer with ADHD.
Based in the UK working as a staff engineer for Apollo GraphQL
(he/him)
0
Followers
0
Following
21
Posts
Joined November 07, 2022
GitHub:
Personal Site:
Photography:
Posts
Replying to
@sminez@hachyderm.io
OK, I now have a blog post up that attempts to explain what this structural regular expressions stuff is and why it can be a lot of fun to play around with
https://www.sminez.dev/match-it-again-sam/
If you find the kinds of things being discussed in this thread interesting then you should give it a read and see what you think!
#rust #rustlang
Replying to
@Mara@hachyderm.io
@Mara Awesome! 🎉
Do you have a link the PR(s) that landed this? I'd love to see what the changes look like 😄
So, I made a thing: https://github.com/sminez/structex
Structural regular expressions for Rust inspired by @robpike@hachyderm.io's 1987 paper that I was talking about a few weeks ago, but as a generic engine that you can
a) back by the regex engine of your choice
b) define what actions to apply to each match in your own code, rather than hard coding things in the engine
https://crates.io/crates/structex
As an example of how you can use this I put together a couple of hacky demos of what grep and sed look like with this setup:
https://github.com/sminez/structex/tree/main/examples/sgrep
https://github.com/sminez/structex/tree/main/examples/ssed
I've also just updated ad to replace its engine with the one from this crate 😄
I'm planning on writing a blog post about this over the next week or so when I have time so if this all seems completely bonkers / opaque then hopefully it'll make a little more sense there(!)
Replying to
@oac@fosstodon.org
@oac@fosstodon.org @jbert@hachyderm.io sounds fun! I have an idea for how to do stream based but it relies on using my own regex engine and won't work for the regex crate as that needs to match against a &str. (Which isn't great as my engine is suuuuuuuper slow 😅)
I've tried to take a look at how @burntsushi@programming.dev handles matching against stdin in multiline mode with ripgrep but there is a LOT going on in that crate so I'm going to need to make a pot of coffee and spend an afternoon just reading through the source (and fantastic comments) to figure out how its done.
If I can get the regex crate to tell me that it has a potential match when it reaches the end of its input and hold that state rather than failing the match, I could buffer and feed it lines as they come through. I'm pretty sure that's not supported in "regex" itself but it might be possible with one of the underlying crates? I've not checked that yet though 👀
Replying to
@sminez@hachyderm.io
@jbert@hachyderm.io @oac@fosstodon.org Oh, and Oliver: I'll definitely be writing up all of this nonsense in a blog post when I've tidied it up a bit 😅
Pretty sure I can get this set up to work as a structex grep, sed and _maybe_ awk, but proper awk would require a full scripting language so maybe that's one for another time...!
Hooking this in to ad is then just a case of wrapping this in an outer parser that handles the address expressions for setting the initial dot I think 🤞
Replying to
@sminez@hachyderm.io
@jbert@hachyderm.io OK, still very much a work in progress but I've pushed it up to crates.io in order to nab the "structex" name while I finish things off.
https://github.com/sminez/structex
This example shows how to use it alongside something like handlebars in order to get string templated printing working as an action 😄
https://github.com/sminez/structex/blob/main/examples/fancy_impl_blocks.rs
It's only had minimal testing so far and I suspect there's a bunch of things that don't work quite right but I think as a proof of concept it gets the idea across?
The idea is to split the problem into two parts in order to avoid a bunch of issues with how actions interleave with the regex search:
- Apply the structural regular expression terms to an input in order to locate sub-strings. Each match may then be assigned a tag with optional content that will be emitted along with matches when they are found.
- Consume that stream of tagged matches and handle the actions as needed.
I have some more ideas on making the construction of a structex more robust (setting allowed tags etc) which I'll add once I've sorted out the testing and docs.
(@oac@fosstodon.org you might find this fun as well!)
Replying to
@sminez@hachyderm.io
@jbert@hachyderm.io since writing this I've been driving home from Scotland and stuck in traffic for 4 hours so I've had some time to think. I've realised that you can split the problem up in a different way to get a library that should support writing a variety of structural regular expression based systems. I have an API in mind so I'll take a stab at sketching it out when I have some free time over the next few days 👀
Replying to
@sminez@hachyderm.io
@jbert@hachyderm.io OK, found an example of what I'm talking about. This is VERY contrived and the output below is showing some debugging prints that fire when match actions are being collected followed by the final output when things are run in order.
The input text is this:
A bar baz B
C baz bar D
And this is the script:
, x/ba\w/ {
g/r/ /[A-Z]/ p/>$0<\n/;
v/r/ -/[A-Z]/ p/<$0>\n/;
}
Output:
ADD ACTION: Action { kind: Print, template: 0 } -> "B"
ADD ACTION: Action { kind: Print, template: 1 } -> "A"
ADD ACTION: Action { kind: Print, template: 1 } -> "C"
ADD ACTION: Action { kind: Print, template: 0 } -> "D"
>B<
>D<
The original matches being found by "x/ba\w/" are sequential within the file, but the group branches are searching forward or backward from that initial position based on what was matched.
It is (of course) fully valid to say that this sort of thing shouldn't be supported 😅
Replying to
@jbert@hachyderm.io
@jbert@hachyderm.io yeah the "if you know all the matching which needs to happen on a chunk" part is what I'm going back and forth on but the more I think about it the more I'm suspecting that I'm making things more complicated than they need to be.
My worry is that it would be possible to write a group that produced match positions out of order once you account for extending the current "dot" forward and backward (covered in the paper). That said, I've not actually written such a structex so I need to check to see if that's even possible. If it's not then the design you're outlining should work I think? I have some thoughts on an implementation I'd like to try but I want to make sure I'm not just digging a hole for myself before I try it out(!)
Replying to
@sminez@hachyderm.io
@jbert@hachyderm.io I haven't tried implementing it yet, but I suspect that you could handle this by running parallel groups in a similar way to how traditional regex engines handle alternations: so each group is running the underlying regex search for the next match in parallel and whichever matches first is run, and since overlapping matches are disallowed we know that we start the next search from the end of whatever we just matched.
Given that the initial implementation of this (both in Sam and my own use case in ad) is for a text editor where we know we have the full (finite) input, its a lot simpler to handle things in two passes.
Replying to
@jbert@hachyderm.io
@jbert@hachyderm.io not nonsense at all!
The problem is when you have parallel actions that would trigger on the output produced by one another. This is the simplest example of the problem:
, {
x/Alice/ c/Bob/;
x/Bob/ c/Alice/;
}
"Replace all occurrences of "Alice" with "Bob", replace all occurrences of "Bob" with "Alice".
You need to know which "Bob"s are from the original input and which came from being replacing an "Alice", otherwise everything will end up as "Bob".
You can get around this by interleaving the execution of each branch but the combinatorics of that quickly get fiddly if you have compound expressions. Breaking things into two passes (locate all matches, apply actions) ends up being a lot easier.
Replying to
@oac@fosstodon.org
@oac@fosstodon.org @cliffordheath@mastodon.social @robpike@hachyderm.io the no overlapping matches part is so you can determine an ordering that you can apply the match actions in where applying the action for each match at most results in applying a delta to subsequent ones. If you allow overlap then depending on the nature of a previous action you can end up invalidating the behaviour of subsequent ones.
Currently in my new implementation I'm storing matches and actions in a btree map as they are found, and then iterating over that map once all matches are found to apply the actions. In the streaming case I think you'd still need to do this when you have a parallel group but could switch to eager evaluation outside of that. With some smarter analysis in the compilation phase it shouldn't be too hard to chunk the program up into regions that do / don't support eager evaluation and then provide feedback to the user as to where they'll end up buffering input to process things.
Replying to
@cliffordheath@mastodon.social
@cliffordheath@mastodon.social @robpike@hachyderm.io in my engine patterns can't match one another's output as all matches are resolved first before any actions (edits / printing) take place.
The paper also calls out that matches must not overlap which I currently don't have a nice solution for other than a runtime error. I've been chatting to my friend @oac@fosstodon.org about how to handle execution on streams and I _think_ that so long as you're not extending matches backwards you should be able to easily determine when you can drop previous input and when actions can be applied. Parallel groups still require evaluating all matches before any actions can be taken though, which is unfortunate but I suspect unavoidable?
Replying to
@cliffordheath@mastodon.social
@cliffordheath@mastodon.social @robpike@hachyderm.io sounds fun! I'm primarily focused on text editing / searching so that's a little different form what I'm looking at. What sort of pattern matching / extraction are you doing on files like GIFs?
Replying to
@sminez@hachyderm.io
And if you want to add a little sarcasm into the mix, this script will conditionally replace 'friend' with '"friend"' on lines that mention Dave:
, {
x/Alice/c/Bob/;
x/Bob/c/Alice/;
X g/Dave/ x/friends/ c/"friends"/;
}
This time we end up with:
'Bob and Alice are friends with Claire and
Alice and Bob are "friends" with Dave.'
Replying to
@sminez@hachyderm.io
For anyone not familiar with the parallel execution idea: the following script swaps all occurrences of "Alice" and "Bob" (something that involves replacing one of the strings with an intermediate value using traditional regex based search and replace approaches):
, {
x/Alice/ c/Bob/;
x/Bob/ c/Alice/;
}
With the following input:
'Alice and Bob are friends with Claire and
Bob and Alice are friends with Dave.'
We end up with:
'Bob and Alice are friends with Claire and
Alice and Bob are friends with Dave.'
Replying to
@sminez@hachyderm.io
The in-progress PR for the rewrite is here: https://github.com/sminez/ad/pull/156
I need to add a _lot_ more tests and sort out the error reporting but for now its a decent start I think.
Ideally I'd like to be able to run "structex" scripts from the command line over streaming inputs but I still have the same limitation that I think the original Sam / Sam helper scripts had which is that the full input needs to be read prior to execution which is...not ideal. You could avoid that if you got rid of the parallel execution semantics of groups but that's a _really_ nice feature of the engine that I'd like to keep, so maybe my hopes of ending up with the "awk of the future" as Rob originally proposed are a pipe dream?
I've spent the last few days overhauling my structural regular expression engine that is inspired by @robpike@hachyderm.io 's 1987 paper (available here: http://doc.cat-v.org/bell_labs/structural_regexps/) and Sam/Acme editors.
This time round I'm correctly handling the parallel execution side of things which is fun, but I'm also thinking about how to add a few extensions to the original system to address some of the issues called out in the paper.
I know about the "Vis" editor, but other than that and my own "ad" does anyone know of implementations outside of plan9's Sam and Acme? I'm still surprised that this concept didn't catch on more as it's incredibly useful.
Replying to
@sminez@hachyderm.io
I've not got any docs in place for anything yet, and there are almost certainly going to be multiple things changing before I can call this ready to release into the wild but for anyone curious this is what writing your main.rs ends up looking like:
https://github.com/sminez/penrosx/blob/develop/examples/demo.rs
Quick update on where I'm at with https://github.com/sminez/penrosx
The new backend is significantly tidied up compared to what I had back in April and running from the new trait merged into the main Penrose crate a few weeks ago. The ffi layer has been torn apart and rewritten and I've got scratchpads working now after wiring in the ability to query properties from windows.
There's still a bunch of things that need sorting out but I think it's now at a point where folks interested in taking it for a spin can see what they think! 😄