Stephan Sokolow's Blog

The Story

Late last night, I stumbled upon a rather clever hack in one of my Rust projects.

I’d been working on an iterator which implements grapheme-aware CamelCase word-splitting when I decided to do some cleanup and ran cargo clippy rather than the much quicker cargo test I’d been using to iterate on it.

Not-surprisingly, given how much I’ve been letting myself get carried away with my hobby projects and “coding while half-asleep”, it popped up some warnings, but this is the one which started things off:

warning: this loop could be written as a `for` loop
 --> src/util/naming/camelcase.rs:260:9
 |
260 | / while let Some((byte_offset, grapheme)) = self.in_iter.next() {
261 | | // Extract the base `char` so `classify_char` can call things like `is_uppercase`
262 | | let base = grapheme.chars().nth(0).expect("non-empty grapheme cluster");
263 | |
... |
280 | | }
281 | | }
    | |_________^ help: try `for (byte_offset, grapheme) in self.in_iter { .. }`
    |
    = note: #[warn(while_let_on_iterator)] on by default
    = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#while_let_on_iterator

Sounds reasonable, so I tried the suggested syntax and got a new error:

error[E0507]: cannot move out of borrowed content
 --> src/util/naming/camelcase.rs:260:40
 |
260 | for (byte_offset, grapheme) in self.in_iter {
 | ^^^^ cannot move out of borrowed content

Well, I may be tired out of my mind, but I recognized what that error meant in theory, so I tried adding &.

error[E0277]: the trait bound `&unicode_segmentation::GraphemeIndices<'_>: std::iter::Iterator` is not satisfied
   --> game_launcher_core/src/util/naming/camelcase.rs:262:9
    |
262 | / for (byte_offset, grapheme) in &(self.in_iter) {
263 | | // Extract the base `char` so `classify_char` can call things like `is_uppercase`
264 | | let base = grapheme.chars().nth(0).expect("non-empty grapheme cluster");
265 | |
... |
282 | | }
283 | | }
    | |_________^ the trait `std::iter::Iterator` is not implemented for `&unicode_segmentation::GraphemeIndices<'_>`
    |
    = note: `&unicode_segmentation::GraphemeIndices<'_>` is not an iterator; maybe try calling `.iter()` or a similar method
    = note: required by `std::iter::IntoIterator::into_iter`

Now, my tiredness bit me. It never occurred to me that a unicode_segmentation::GraphemeIndices needs to be mutably bound to work, nor that “not implemented for &” said nothing about whether it was implemented for &mut.

Completely stumped, I popped over to  #rust where, after blindly trying several helpful suggestions, I finally tried &mut self.in_iter.

That would normally have worked… except for one small problem:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
   --> game_launcher_core/src/util/naming/camelcase.rs:277:40
    |
262 |         for (byte_offset, grapheme) in &mut self.in_iter {
    |                                             ------------ first mutable borrow occurs here
...
277 |                 CCaseAction::Skip => { self._next_word(byte_offset, true) },
    |                                        ^^^^ second mutable borrow occurs here
...
283 |         }
    |         - first borrow ends here

error[E0499]: cannot borrow `*self` as mutable more than once at a time
   --> game_launcher_core/src/util/naming/camelcase.rs:278:45
    |
262 |         for (byte_offset, grapheme) in &mut self.in_iter {
    |                                             ------------ first mutable borrow occurs here
...
278 |                 CCaseAction::StartWord => { self._next_word(byte_offset, false) },
    |                                             ^^^^ second mutable borrow occurs here
...
283 |         }
    |         - first borrow ends here

error[E0499]: cannot borrow `*self` as mutable more than once at a time
   --> game_launcher_core/src/util/naming/camelcase.rs:279:54
    |
262 |         for (byte_offset, grapheme) in &mut self.in_iter {
    |                                             ------------ first mutable borrow occurs here
...
279 |                 CCaseAction::AlreadyStartedWord => { self._next_word(prev_offset, false) },
    |                                                      ^^^^ second mutable borrow occurs here
...
283 |         }
    |         - first borrow ends here

The code calls &mut self methods inside the loop body and, because the loop returns before exhausting the iterator, I can’t mem::replace it out of the binding.

In short, I had stumbled upon the one way to do this, on my first try, completely by accident, and, were it not for a naïve Clippy lint, I would have never realized how special  this syntax is.

It was around that point that the wheel-bound hamster powering my brain woke up long enough for me to start making the connections and ask the last few questions necessary for it to all make sense…

The Reasoning

The problem here is a collision between two characteristics of Rust’s design:

1. for works via the IntoIterator trait, which means that, as far as the compiler knows, releasing and re-borrowing the resulting iterator would discard the iteration state and start over. (ie. There’s no magic in the compiler to to recognize when it’s already got an iterator.)
2. My self._next_word takes a mutable borrow over all of &self …which will fail if for is still holding a reference to one of its members.

The clever trick behind while let Some(...) = self.in_iter.next() is that it bypasses IntoIterator. As such, the compiler can be certain that self.in_iter won’t go away between iterations, and can release the borrow.

As a result, you’re left with something that functions like a for loop, but only holds onto the item which the iterator returned, leaving self free to be borrowed, in its entirety, by all and sundry.

So, there you have it. If you’re writing a struct which holds onto an iterator and your for loop is making things difficult by blocking method calls, try bypassing IntoIterator. Get an iterator manually, then reformulate your loop to use while let Some(...) instead.

If Clippy complains, add #[allow(while_let_on_iterator)] and get on with your day.

P.S. Don’t worry about the “coding while half-asleep” part. I write my unit test suites and audit/refactor the previous day’s work while wide-awake and alert. 😉

I’ve been working to port the brains of my game launcher experiment from Python to Rust for easier refactoring and to eventually offer language bindings other than Python itself and, at the moment, I’m working on the “filename to title” heuristic, because that’s got the best unit test suite.

Surprise, surprise. The biggest time-sink has been redesigning things where the Python version uses regular expressions with lookbehind and lookahead expressions.

Well, the CamelCase-processing regular expression faked me out. If you search for answers, it seems every language is using some variation of this regex:

r'((?<=[a-z])[A-Z]|(?<!\A)[A-Z](?=[a-z]))'

…and, since Rust’s Regex crate uses a DFA to avoid pathological performance, this wasn’t an option.

I wasted an afternoon trying to implement such a parser manually before it occurred to me that you don’t actually need lookahead/lookbehind to parse camelcase!

It seems that someone originally wrote that regex with the goal of getting accurate string indexes for the starts of words, then everyone else copy-pasted and translated it without recognizing that it was stricter than necessary.

UPDATE: There is one situation where the lack of lookahead has to be worked around which I somehow overlooked… any situation where you need to insert a space before and after the same character. (ie. words like “I” and “A” in the middle of a phrase.) The solution there is just to run the regex twice.

So, if you just want to insert spaces (without duplicating ones that are already there), and you want to enhance the algorithm to handle numbers and ampersands reasonably and you want it to work in Rust’s regex engine, here’s how you do it:

r"([a-z&])([&A-Z0-9])|([^ ])([A-Z][a-z])|([0-9])([a-z])"

…and then use this as your replacement string:

"${1}${3}${5} ${2}${4}${6}"

It passes every test in my unit test suite for CamelCase splitting and improves the accuracy score on the integration test corpus for the filename_to_name function which relies on it.

UPDATE #2: I got to playing with the Regex crate’s support for unicode character classes and I have two things to report:

First, you actually do need a fourth pair of capture groups to split “A&b” because of the “ampersand, followed by lowercase” situation.

Second, for anyone who wants it, here’s a fully commented Rust regexp which will process CamelCase written using any mix of what the Unicode database considers to be letters (lowercase, uppercase, or titlecase), numbers (decimal digits, letters, or other), and the four different kinds of ampersands I was able to find:

r"(?x)
 # == Ampersand (definitely end) followed by anything not already whitespace ==
 # ('Ampersand' or 'Small Ampersand', or 'Fullwidth Ampersand' or...
 # 'Heavy Ampersand Ornament')
 ([\x{26}\x{FE60}\x{FF06}\x{1F674}])
 # (Something not 'Separator, Space')
 (\P{Zs})

 # == OR ==
 |

 # == Lower/titlecase (possible end) followed by upper/titlecase/number (possible start) ==
 # ('Letter, Lowercase' or 'Letter, Titlecase', 'Ampersand' or 'Small Ampersand', or...
 # 'Fullwidth Ampersand' or 'Heavy Ampersand Ornament')
 ([\p{Ll}\p{Lt}])
 # ('Letter, Uppercase' or 'Number, Decimal Digit' or 'Number, Letter' or...
 # 'Number, Other' or 'Ampersand' or 'Small Ampersand' or...
 # 'Fullwidth Ampersand' or 'Heavy Ampersand Ornament')
 ([\p{Lu}\p{Lt}\p{Nd}\p{Nl}\p{No}])

 # == OR ==
 |

 # == Number followed by an un-capitalized word ==
 # ('Number, Decimal Digit' or 'Number, Letter' or 'Number, Other')
 ([\p{Nd}\p{Nl}\p{No}])
 # ('Letter, Lowercase')
 (\p{Ll})

 # == OR ==
 |

 # == Anything not whitespace, followed by ampersand or unambiguous beginnings of word ==
 # (Something not 'Separator, Space')
 (\P{Zs})
 # ('Letter, Titlecase' or ['Letter, Uppercase' followed by 'Letter, Lowercase'] or...
 # 'Ampersand' or 'Small Ampersand' or 'Fullwidth Ampersand' or ...
 # 'Heavy Ampersand Ornament')
 (\p{Lt} | \p{Lu}\p{Ll} | [\x{26}\x{FE60}\x{FF06}\x{1F674}])
 "

…and…

"${1}${3}${5}${7} ${2}${4}${6}${8}"

Before you get scared, it’s actually just the Unicode version of the tiny regexp with a ton of explanatory comments and a little more ampersand matching. It’s very simple once you throw out the comments and understand the structure.

The regular expression matches any of four situations where a space should be inserted:

• An ampersand followed by anything that isn’t whitespace (this is the one I split out)
• A lowercase or titlecase (upper+lower in one character) letter followed by an uppercase/titlecase letter or a number.
• A number followed by an un-capitalized letter.
• Anything not whitespace, followed by an ampersand, titlecase letter, or <UPPER><lower> pair.

Once you ignore the comments, most of the verbosity comes from having to combine multiple unicode character literals or classes to say things like…

• “any ampersand” ([\x{26}\x{FE60}\x{FF06}\x{1F674}])
• “any type of number” ([\p{Nd}\p{Nl}\p{No}])

The advantage is that, because it delegates the lower-level details to the Unicode lookup tables for everything but the ampersands, any failure should result from the language being so alien that the concept of CamelCase itself is difficult to apply to it.

UPDATE #3: Replace chained OR tokens with compound character classes where possible for minor cache pressure savings in the regexp engine.

It’s still a heavy regexp (I was chatting with burntsushi on IRC when the idea occurred to me and, if anyone should have the expertise to judge that, it’s the author of the Regex crate), but it meets my needs, it’s easy to tweak as I further refine my heuristic guesser, and if I ever need something more performant, writing this has taught me enough about the problem that I should be able to write a manual solution.

UPDATE 2024-03-14: Just use xremap. It can remap or keybind things at the evdev level with only/except device filtering and, if you’re on X11 or supported Wayland compositors, it also supports applying only/except application filtering for your remaps/keybinds.

UPDATE 2021-04-18: There’s now a tool for reprogramming several models of these footswitches, so consider this just a fallback for if yours isn’t supported.

Well, I have a Chinese USB foot pedal that I picked up on eBay for $11 CA to play around with but, for ages, it’s been worth bupkiss because it’s mapped to the “b” key on the keyboard and I was too busy to look into how to remap a key on just one device on Linux… that ends here and now.

Try 1: Remapping in XKB

The most obvious solution would be to remap the thing by applying a custom X11 keyboard layout to just the one device. (ie. Redefine how keycodes from evdev map to X11 keysyms.)

OK, doesn’t seem too hard and, Google to the rescue, someone even wrote some example code for it. (See also: XKB Remapping)

The gist is:

1. Use xinput list to find the ID for the device you want to limit the remapping to
2. Use setxkbmap -device <the ID> -print to dump the keymap
3. Write a custom supplemental XKB keymap which redefines the key in question
4. sed the dumped keymap to append the supplemental keymap to the stack of what gets applied.
5. Use xkbcomp to re-apply it.

…but, no matter what I tried, I couldn’t get my Ubuntu 14.04 LTS system to acknowledge the change.

Verdict: Failure on *buntu 14.04 LTS

Try 2: Remapping in XKB (hackier but more foolproof)

I was getting errors from the previous version and I didn’t know whether any of them were spurious, so I decided to try the old “hacky but foolproof” standby described in this ArchWiki page … dump the keymap, hand-edit the stupid thing, and then re-apply it.

xkbcomp -i <the ID> $DISPLAY ~/out.xkb
vim ~/out.xkb
xkbcomp -i <the ID> ~/out.xkb $DISPLAY

First, let me caution you that it has to be -i ID and not -iID. The latter form doesn’t work.

That said, it ran without complaint and even showed the expected results when I re-dumped the keymap fresh from the X server… it just had no effect.

(I think it might be because, when you look at the USB HID descriptor that evtest dumps on startup, the stupid pedal announces that it’s a 162-key keyboard, plus a mouse with scroll wheel, all in one device, which causes xinput list to file it as a mouse rather than a keyboard.)

Verdict: Failure on *buntu 14.04 LTS

(Naturally, I didn’t continue on to research how to make it survive restarts.)

Try 3: Remapping via udev

OK, no big deal. My ATi Remote Wonder II didn’t need remapping because it sent keycodes that were already mapped to the XF86AudioPlay and XF86AudioPause keysyms. Let’s drop below X11 and redefine how the kernel maps hardware scan codes from the pedal to evdev keycodes.

Now, since we need to redefine it for only one input device, that means we can’t use the setkeycodes command, so udev it is. (Besides, I’ve heard that setkeycodes doesn’t work with USB devices.)

According to these StackExchange answers [1] [2] and these ArchWiki pages [1] [2], I need to put together a definition like this, and store it at /etc/udev/hwdb.d/some-unique-name.hwdb, then refresh the database:

keyboard:input:b0003v0C45p7403*
 KEYBOARD_KEY_70005=playpause

Oh, and make sure you only indent the second line one space. More will cause a silent failure and the first guide I read not only didn’t mention that, but actually used two spaces in the example!

To keep things simple, here’s the overview of the process:

1. Create something in the above format as a /etc/udev/hwdb.d/whatever.hwdb file.
2. The numbers in the file are as follows:
   1. The b0003 means “Bus type: USB”
   2. The v0c45 and p7403 are the USB vendor and product IDs from lsusb
   3. The 70005 is the MSC_SCAN value from pressing the pedal while evtest is listening.
   4. The playpause is the kernel-internal name for the desired keycode. They’re defined in a header I don’t seem to have (linux/input-event-codes.h) but the ArchWiki pages have a link to an online list of them.
3. After putting the file in place, run sudo udevadm hwdb --update (older systems) or sudo systemd-hwdb update (newer systems) to merge it into the hardware database.
4. Finally, either reboot your system or run sudo udevadm trigger to apply the changes. (Un-plugging and re-plugging the thing may also work)

…so, did it work? Well… no. It turns out *buntu 14.04 is using the last version of udev before that feature was added (14.04 has udev 204 and it needs 205 or higher).

(Also, note that whether you use the keyboard: prefix or the evdev: prefix will depend on the udev version you use. I tried both, but this site explains what to use for which version.)

Verdict: Failure on *buntu 14.04 LTS

NOTE: This AskUbuntu answer that I found after hacking together my own solution suggests that it might actually be possible, but that 14.04 includes a version of udev with some funny requirements for applying the changes.

Try 4: Remapping via udev (the old way)

*sigh* Ok, so we can’t use the clean, easy solution everyone’s listing because 14.04 is too old… so what’s the old solution?

Well, according to this page and this AskUbuntu answer, versions of udev up to and including 204 do key remapping by using the old familiar udev rules.d system and a helper utility named /lib/udev/keymap. Cool.

To paraphrase Jurassic Park, “It’s a rules.d system, I know this.” (From fixing permissions on various devices, to getting my Chinese NES controller adapter to announce itself as a joystick, I have a fair bit of experience writing rules.d files.)

OK, so I write this /etc/udev/keymaps/microdia-foot-switch file, using the same values from the previous attempt:

0x70005 playpause

…and this /etc/udev/rules.d/99-microdia-foot-switch.rules file:

ACTION!="remove", SUBSYSTEMS=="usb", ENV{ID_VENDOR_ID}=="0c45", ENV{ID_MODEL_ID}=="7403", RUN+="keymap $name /etc/udev/keymaps/microdia-foot-switch"

…and unplug and replug the foot pedal… and nothing happens. I check `dmesg` and whadda ya know, `/lib/udev/keymap` isn’t installed.

(NOTE: While it didn’t affect me, your distro may have a bug in keymap which forces you to use the keycode itself instead of the playpause name alias for it. If you happen to have another device which can emit the target keycode, you can use sudo showkey --keycodes to get it really easily.)

So, anyway, I pop over to packages.ubuntu.com to search up the package to install… and it turns out it was in udev in Precise and got pulled (with no replacement) in Trusty… way to jump the gun, guys!

Of course, this isn’t the only botch in 14.04 (it also shipped with a buggy version of Geeqie), so this is old-hat.

1. Pop over to the precise-updates version of the udev package on packages.ubuntu.com, scroll to the bottom, and download whichever architecture matches your hardware. (Probably amd64, in this day and age)
2. Open it up with file-roller (because it’s smart enough to hide the fact that a .deb is an archive containing more archives) and copy out /lib/udev/keymap.
3. sudo cp keymap /lib/udev/keymap && chmod +x /lib/udev/keymap

Now, try unplugging and re-plugging the thing again and it should work.

Verdict: Success on *buntu 14.04 LTS

…but wait, there’s more!

While evtest and xev were showing the right keysym, my Audacious Media Player wasn’t listening to the resulting XF86AudioPlay presses.

Apparently, not all XF86AudioPlays are created equal, because adding a second mapping from “Pause/Resume” to XF86AudioPlay by stepping on the pedal fixed it.

(My hypothesis is that, while Audacious is displaying the keysym names, it’s binding using the underlying keycodes and the one from my ATi Remote Wonder II began life as a play keypress while the one from the pedal began life as playpause.)