bool pattern_matcher::match(std::string const& line) const {
bool once = true; // need to try at least once, because even zero length input might match
for (auto seq = character_sequence(line); !seq.is_eol() || once; seq.advance(), once = false) {
if (match_all(m_, seq))
return true;
}
return false;
}
Jez Higgins
Freelance software grandad
software created
extended or repaired
Follow me on Twitter
Applications, Libraries, Code
Talks & Presentations
Tuesday 11 January 2022 The Forest Road Reader, No 2.67 : STinC++ - Chapter Five Wrap Up
STinC++ rewrites the programs in Software Tools in Pascal using C++
The bulk of chapter five was introducing and describing regular expressions. Regexes are ubiquitous these days, but you’d still struggle to find an introduction that’s as clear as that in Software Tools in Pascal. Kernighan and Plauger are both good writers individually, but together they’ve got some kind of superpower. Introducing regexes is all very well, but the point of chapter five is implemented a regular expression engine, and that was really good fun.
I don’t have a strong computer science background. I trained in electronic engineering and came into software sort of by accident. I have been doing this for getting on for 30 years, so I’ve picked up a few things along the way but I have a generally utilitarian approach. I probably could invert a tree, but I’d look for a library function first.[1] Anyway, I learned a whole lot building my little regex library, and like last chapter’s sort algorithms, unsophisticated as my implementation is, writing it is something I would never have otherwise written. It’s given me an appreciation of regexes I didn’t have before. In my code, for instance, I can see a couple of pretty obvious optimisations, mainly handling the no-match case. The Kleene star implementation is greedy, but I know how a non-greedy version would drop right in. I can see how the code could be extended to support capture groups. It’s a whole new little arena that’s opened up for me. Thanks Brian, thanks Bill.[2]
It helped cement some C++ for me too. There are always things you know, but perhaps not consciously or with full understanding. I knew, in an abstract kind of way, that C++ lambda functions have value semantics. However, since I’d pretty much always used lambdas functions as arguments to functions that where declared right at the call site. I hadn’t appreciated that they enabled, for example, runtime polymorphic behaviour in value objects. As the code compiles a regular expression into a pattern_matcher object, it’s building a std::vector of matcher objects. Each of those matcher objects can have different behaviour - matching the start of a line, a single character, one of a set of characters, or whatever. "Classically", if I’d written this code 10 years ago say, at the very least I’d have a base class, possibly abstract, and then a series of leaf classes to describe the different behaviours. Inside the pattern_matcher we’d have a list of pointers, there’d be a whole lot of memory management, and we’d all be a bit nervous. Today, we can, thanks to lambda functions and std::function, do that all with value objects. There’s no explicit memory handling, no worries about lifetime management, the code is compact and to the point. It’s fantastic.
In my write-ups of find and compare I quoted only a little bit of Kernighan and Plauger’s Pascal. As the problems we’re working on get that bit bigger, the C++ I’m writing is further and further away from the Pascal they wrote and comparisons between the two are less and less useful. We’ve established, for instance, that Kernighan and Plauger are hampered by Pascal’s lack of a proper string type, and there’s not much point in saying it again. The biggerproblems they present naturally have a bigger solution space, and C++ (or your current language of choice) lets us explore that solution space much more freely.
Two programs for chapter five, but only one coming up in chapter six, Editing. It’s going to be a bit of job, and I think I’m going to have to find a new way to write about it too. I hope you’ll follow along with me.
1. Assuming there are any because I can’t think of reason why you’d want to invert a tree.
2. PJ Plauger is wildly known as Bill.
Tagged code, and software-tools-in-c++
Sunday 02 January 2022 The Forest Road Reader, No 2.66 : STinC++ - change
STinC++ rewrites the programs in Software Tools in Pascal using C++
Back at the end of the summer, I described find, a tool for searching text using simple regular expressions. That was quite a chunky little project, involving describing the regular expression syntax, implementing the various matchers, coping with the complication that is the Kleene star, parsing out the pattern to build the matcher, and finally putting all together to search the input text.
With find complete, Kernighan and Plauger move breezily on
Now that we know how to identify patterns in text, let’s consider a useful tool for making selective changes…
PROGRAM |
|
USAGE |
|
FUNCTION |
The replacement string
|
EXAMPLE |
To parenthesize all sums and differences of identifiers:
|
From finding to changing
Well this seems straightforward enough. We’ve just built a little regular expression matcher which can find a pattern in an input line. If we extend that slightly to tell us where it matched, then everything should more or less drop out.
The body of our existing find function is a simple loop. It tries to match the pattern to the start of the line, and to each subsequent position in turn until we either get a match or run off the end.
The business of looping over the characters in line is wrapped up in character_sequence. When we match the pattern, the character_sequence already knows where we are in the line, so extending the match and match_all functions to return that information to us is straightforward.
match_location pattern_matcher::find(std::string const& line) const {
bool once = true; // need to try at least once, because even zero length input might match
for (auto seq = character_sequence(line); !seq.is_eol() || once; seq.advance(), once = false) {
auto match = match_all(m_, seq);
if (match.match)
return match;
}
return not_found;
}
bool pattern_matcher::match(std::string const& line) const {
return find(line).match;
}Our change program wants to replace all occurrences of a pattern, so we need one further small refinement to the find function - an offset from the start of the line.
match_location pattern_matcher::find(std::string const& line, size_type offset) const {
bool once = true; // need to try at least once, because even zero length input might match
for (auto seq = character_sequence(line, offset); !seq.is_eol() || once; seq.advance(), once = false) {
auto match = match_all(m_, seq);
if (match.match)
return match;
}
return not_found;
}With the match location available, it should be the work of moments to drop the replacement in. Right? Wrong!
"I think you’ll find it’s a little bit more complicated than that"
In the code above, there’s already a little bit of special handling for zero-width matches - patterns which match not on characters, but on the spaces in between characters. The beginning of line pattern, %, matches before the first character, the end of line pattern, $, matches after the last character. Both will also match an empty line.
But what about A*, zero or more letter As? Where does that match against, say, 1234? Bleeding everywhere, that’s where. It matches before 1, and also after 1. It matches before 2 as well. After 1 and before 2 are, of course, the same location, and similarly after 2 and before 3 are the same location, and so on.
In the change routine, accommodating zero-width matches, particularly taking into account that a call to find may return the same match location as the previous call, it turns out, is what we call a right pain in the arse. It took a reasonable amount of back and forth to get right. It kept feeling like we needed just another flag to account for this special case, or to show we needed to do something again just this once. The gory details are all in the Git repository, but this extract gives you a flavour.
Date: Thu Dec 9 20:43:09 2021 +0000 special handling for terminal-only patterns (%|$) I’m not super keen to do this, but it turned out we were not matching a naked $ with the existing set up. It’s always going to be a bit weird, and just pulling out terminal-only patterns seems neater than trying to futz with the core loop. As a minor side-effect, not that youd notice, quicker too. |
Date: Thu Dec 9 20:49:09 2021 +0000 replace $ only patterns |
Date: Thu Dec 9 21:30:52 2021 +0000 extend find and match functions to take an offset allows us to test the pattern against any part of the line, rather than just the whole line at a time. This is obviously particularly relevant for % anchored matches |
Date: Thu Dec 9 21:33:06 2021 +0000 rework change to deal with (%|$) zero width matches |
Date: Thu Dec 9 22:03:43 2021 +0000 correct terminal-only matching with non-zero offset |
Date: Thu Dec 9 22:04:42 2021 +0000 handle zero-width non-terminal matches - need to give them one more go applying change a* - to 12345 gives -1-2-3-4-5- The a* pattern matches before each character and at the end of the line. This is not exactly what you immediately expect, but try s/a*/-/g in sed and prepare to be slightly discombobulated. |
Date: Thu Dec 9 22:47:37 2021 +0000 if we immediately match in the same location, don’t replace again eg applying change a* - to abc gives -b-c- |
Hell of an evening, I’ll tell you.
Soft Landing
The whole business made me quite sad for a little while, but good tests and repeated gentle refactoring got the code, and me, to a comfortable place. Here’s the main loop which finds the matches and inserts the replacement:
void apply_change(
stiX::pattern_matcher const& matcher,
stiX::replacement const& replacement,
std::string_view line,
std::ostream& out
) {
size_type offset = 0;
size_type last_match = -1;
for (auto state = replacement_state(); !state.completed(); state.next(at_end(offset, line))) {
auto loc = matcher.find(line, offset);
if (!loc.match)
break;
if (last_match != loc.from || !loc.zero_width) {
auto up_to_match = line.substr(offset, loc.from - offset);
out << up_to_match;
replacement.apply(line.substr(loc.from, loc.to - loc.from), out);
}
offset = loc.to;
last_match = loc.to;
if (loc.zero_width && not_at_end(offset, line)) {
out << line[loc.from];
offset = loc.from+1;
}
}
out << line.substr(offset) << '\n';
}There’s still a bit of state management going on, but it’s fairly well under control. It took some thinking, but the special case for zero width matches is contained in one place, the loop condition is wrapped up in a little object and there are no nested if statements.
The changes to the pattern matcher were, in the end, not large and didn’t change the overall shape of that part of the code. With the details of where and when to insert the new text, the replacement did, as I’d expected, pretty much just drop out.
So much of the work code we produce is compromised by time, scope, by any or all of a hundred other factors, and while we can be pleased with it, it also sometimes be a little unfulfilling, disappointing even. While I would never expect someone to write code in their own time, on their own account, there is a pleasure to be had from nurdling around with hermetic little problems like this.
Thanks Chums
Of course, looking at apply_change again two weeks after I declared it 'finished', there are further changes I’d like to make. I was doing the best I could at the time, so I’m not beating myself up about it. I’m just seeing it differently today. That function’s about twice as long as I’m usually comfortable with for a start, so at the very least I’d cut that down.
Maybe I’ll do that now.
Happy New Year, friends - I hope you find comfort in your code too.
References
-
string_view - in the middle of this I realised I didn’t need to construct and copy strings around, I could just use a
string_view. Must make a conscious effort to keep on using it in the future. -
sed, the grown-up program
changecould be one day if we just kept going.
Source Code
The full source code, with tests and what-not, for change, indeed the whole project, is available in the stiX GitHub repository.
Endnotes
This whole endeavour relies on Software Tools in Pascal and Software Tools, both by Brian W Kernighan and PJ Plauger. I love these books and commend them to you. They are both still in print, but new copies are, frankly, ridiculously expensive. Happily, there are plenty of second-hand copies around, or you can borrow them from The Internet Archive using the links above.
For this project I’ve been using JetBrain’s CLion, which I liked enough to buy and twice renew a license for. I use it all the time now.
The test harness I’m using is Catch. I’ve been aware of Catch pretty much since it was first released, but this project is the first time really getting in and using it. I like it, and it is my first choice for future work.
Tagged code, and software-tools-in-c++
Thursday 14 October 2021 Talk: Down To The Metal
Down to the Metal: How does the text we type turn into the computer actually doing things
My friends at Norfolk Developers were kind enough to host/indulge me in giving another talk. This session covers how programming language interpreters and compilers go about turning the code we’ve written into some action the computer takes.
Originally I’d expected to give this talk to a JavaScript user group and consequently, while this isn’t a particularly code-heavy talk, wanted to give code examples in JavaScript. However, I didn’t want to use JavaScript as the example language that gets parsed out and evaluated. It would have been a load more work and the talk would have been more complicated for it. I could have gone with something Lisp-y, like a little Scheme implementation, but the all those brackets are sort of off-putting. I remembered a talk my friend Andy Balaam had given a few years ago, covering similar ground, for which he’d developed his own little language. I asked if I could use it in my session, and he willingly agreed.
Cell is a deliberately small language, which can be implemented in pretty tiny amount of code. It’s not so small as to be without interest though, and you can do proper programmey things with it. The bank account sample code, for instance, is quite astonishingly dense involving calling a function that defines a function which is then immediately evaluated to return another function which manipulates variables captured in the local scope. Amazing stuff. The Cell library’s pairs and lists are also remarkable pieces of work, building out Lisp style arbitrary data structures from the smallest building blocks.
It’s a fun little project to work on, and I hope I did it at least some justice in my talk.
Bonus Content!
-
How to write a programming language - the talk Andy wrote Cell to illustrate.
-
Want something chunkier? Crafting Interpreters is an impressively thorough treatment of the topic.
-
Journey Into Space: How I read an article by one of the original signatories of the manifesto for agile software development, and accidentally ended up writing a version of Asteroids for my phone - the previous NorDev talk I referenced right at the start of this one.
Tagged talk, nordev, code, and cell