Subtleties of search-and-replace in Emacs

The search/replace mechanism in Emacs is a beautiful thing, full of subtleties.

It is pretty clear that its design has been honed to an edge by about 20 years of heavy use. You might not think there could be much to it, but a lot of apps that have come along since then could learn something from some of its features:

Incremental search. (isearch, or "find as you type") This has gained traction elsewhere in recent years. To search, press C-s and start typing; C-s again takes you to successive matches. Emacs highlights all the matches that are visible:

You can save quite a bit of typing this way because you can stop as soon as you've typed a prefix that uniquely identifies the text you're looking for.

In addition, the search UI is in the minibuffer, instead of in a separate dialog that covers part of your document.

Firefox, Chrome, and gedit all have fairly similar features; however, they only expose bare-bones search functionality through them. OpenOffice and most word processors bring up a big and jarring dialog.

Yanking from the document. This is like auto-completion for your searches. Suppose you're looking for all instances of "tag.artist" in your document. Press C-s and start typing...

Now you notice that the word following the highlighted match is exactly what you were looking for. Just press C-w to pull the next word into your query:

Then pressing C-s searches for subsequent occurrences of tag.artist. If you think this is useful, just think about how awesome it is when you need to search for superLongIdentifierNames in Java code.

You can also yank just the next character from the document, or everything up to the end of the line. Type C-h k C-s in Emacs to learn more.

Case replacement. If you have the text

Eat foo for breakfast!
Foo is the best medicine.
VOTE FOO FOR PRESIDENT

and replace (M-x query-replace or M-%) "foo" with "bar", what do you get? Exactly what you expect:

Eat bar for breakfast!
Bar is the best medicine.
VOTE BAR FOR PRESIDENT

This is clearly what you want most of the time, at least when you're editing prose. Gedit and OpenOffice don't do this (and Chrome and Firefox don't have a "replace" feature).

(What happens, you ask, if you're editing code, or anything else where case sensitivity is critical? Emacs's heuristic is to only turn on these smart replacements when your query and replacement text are both all lowercase. You can also manually toggle case-sensitivity in searching with M-c. For what it's worth, I've never noticed a false positive when editing code.)

Cycling behavior. Many programs do a poor job of letting you know when your search has wrapped around to the beginning of the document. In Firefox, I often find that I can inadvertently cycle through looking at all the search results two or three times before I realize what I've done.

After the last match in a document, Gedit and Chrome wrap around to the beginning silently. Firefox wraps around and concurrently displays a notification in the search UI. The problem is that if your attention is focused on the document content—as it probably is if you're scanning the individual matches—it's easy to miss the cues that tell you the search has wrapped around (e.g. Firefox's notification, or the scroll bar jumping back). You can end up back at the beginning of the document without realizing it.

At the other end of the spectrum, OpenOffice brings up a big and jarring dialog asking you "Yes/No" whether you want to continue searching at the beginning. Not so great, either.

How does Emacs deal with this? When you've reached the last match for a query in the buffer, pressing C-s does nothing, except raising a quiet notification that there are no remaining matches:

If you press C-s again, however, the search wraps back around to the beginning of the buffer.

That is, at the last match, C-s is not initially met with an immediate jump to a new match (as it usually is); Emacs gives just enough "pushback" to ensure that the user is aware when the search has wrapped, even if they're not paying any attention to the application chrome (minibuffer and scroll bars)! Very cool.

Displaying failed searches. When you type something that doesn't have a match, Emacs brings you to the maximal matching prefix of whatever you typed, and highlights the part of your query that wasn't found:

This kind of feedback gives you a good idea of whether or not you made a typo/error in your search: if you did, it often appears near the point where the text stopped matching.

If you only get all-or-nothing feedback telling you "no matches were found," then you are sort of groping around in the dark as you try to figure out what went wrong.

Search as a method for navigation. Perhaps the killer feature of isearch in Emacs is that you can use it as the primary method for moving around in a document, essentially replacing most of the functions of the PgUp/PgDn keys and the scroll bar in other applications.

Part of this has to do with the fact that the search UI is so lightweight (no dialog boxes!). However, isearch in Emacs is also cool because it facilitates many use cases:

• During a search, you can press C-g to cancel and return to where you started. This is handy if you just wanted to search for something in order to get a quick glance at it.
• …However, if you do indeed want to stop at the current match, press RET. Perhaps you want to make some quick edits or do some more extensive reading at that spot. But when you're done with that, you can press C-x C-x to return to where you originally were, because Emacs has set the mark to the place where you started.
• …Or, you can just continue editing there with no intention of returning to your original position.

Gedit and OpenOffice really only support that very last use case. You can hold your existing spot in a document with the cursor, but then you're limited to looking around with the scrollbars, which is cumbersome. Or you can use the Find feature or otherwise move the cursor, but then you've lost your original position.

Emacs is like your very own personal assistant: it remembers things so you don't have to.

Conclusion

I haven't mentioned many of the miscellaneous keyboard-accessible commands and options available from within isearch and query-replace. These are well worth your time to learn, although they are quite self-explanatory if you read the integrated help:

• For options available in isearch, type C-h k C-s.
• For options available in query-replace, type C-h at a query-replace prompt.

I'd sum up some of the more generalizable design principles behind search-and-replace in Emacs as follows:

• Reduce extraneous typing.
• Stay out of the user's way whenever possible.
• However, alert the user with immediate and useful feedback whenever necessary.

Manipulating Picasa Web Albums programmatically

I was pleased to find out that the Picasa Web Albums API makes it quite easy to programmatically upload and download photos from Picasaweb. So any desktop app that manipulates photos or graphics can easily be extended so that it can interact with web albums. The possibilities are manifold… below is some code that demonstrates a couple of the basic capabilities.

Like everything else on Ubuntu/Debian, you only need about 15 seconds to obtain all you need to get started with this. Just install the python-gdata package:

$ sudo aptitude install python-gdata

Uploading albums to Picasaweb

The following function creates a new Picasaweb album from a sequence of photos and associated captions.

#!/usr/bin/python
import gdata.photos.service
import os.path

def create_new_album(album_title, email, password, photos):
    """
    Creates a new Picasa Web Album with the specified images.

    album_title: title of album, e.g. "Spring Break 2009"
    email: Google account name, e.g. yourname@gmail.com
    password: Google account password
    photos: sequence of tuples where each entry is (filename, caption)
            e.g. [("/tmp/photo0001.jpg", "A huge turtle"), ...]
    """
    # Authenticate to Picasa Web Albums.
    gd_client = gdata.photos.service.PhotosService()
    gd_client.email = email
    gd_client.password = password
    gd_client.source = 'MyPhotoUploader' # Fill in the name of your program here.
    gd_client.ProgrammaticLogin()

    # Create the album.
    album = gd_client.InsertAlbum(title = album_title, summary = '')
    album_url = '/data/feed/api/user/%s/albumid/%s' % \
        (album.user.text, album.gphoto_id.text)

    # Insert the photos.
    for filename, caption in file_info:
        gd_client.InsertPhotoSimple(
            album_or_uri=album_url,
            title=os.path.basename(filename), # This shows up as 'Filename' on Picasaweb
            summary=caption,
            filename_or_handle=filename,
            content_type="image/jpeg")

Downloading albums from Picasaweb

Normally you can't download entire albums directly from the web (unless you have the Picasa client software installed). You can however use the API for this purpose (the parts in blue below are the core, non-interactive part of the program):

#!/usr/bin/python
#
# This interactive script prompts the user for an album to download.

import gdata.photos.service
import urllib

def main():
    "Downloads a Picasa Web Album of the user's choice to the current directory."
    gd_client = gdata.photos.service.PhotosService()
    username = raw_input("Username? ")            # Prompt for a Google account username.
    print_album_names(gd_client, username)        # Enumerate the albums owned by that account.
    album_id = raw_input("Album ID? ")            # Prompt for an album ID.
    download_album(gd_client, username, album_id) # Download the corresponding album!

def print_album_names(gd_client, username):
    "Enumerates the albums owned by USERNAME."
    albums = gd_client.GetUserFeed(user = username)
    for album in albums.entry:
        print '%-30s (%3d photos) id = %s' % \
            (album.title.text, int(album.numphotos.text), album.gphoto_id.text)

def download_album(gd_client, username, album_id):
    "Downloads all the photos in the album ALBUM_ID owned by USERNAME."
    photos = gd_client.GetFeed('/data/feed/api/user/%s/albumid/%s?kind=photo'
                               % (username, album_id))
    for photo in photos.entry:
        download_file(photo.content.src)

def download_file(url):
    "Download the data at URL to the current directory."
    basename = url[url.rindex('/') + 1:]  # Figure out a good name for the downloaded file.
    print "Downloading %s" % (basename,)
    urllib.urlretrieve(url, basename)

if __name__ == '__main__':
    main()

More info

Picasaweb API developer's guide (Python client). From that page you can also find more about bindings for .NET, Java, and PHP.

I hereby release the code in this post into the public domain.

With a partner like Apple, who needs competitors?

Apple's contempt for iPhone users and developers keeps pushing the limits of credulity. It is exemplified by its response to the FCC inquiry into the Google Voice app:

FCC: Why did Apple reject the Google Voice application for iPhone and remove related third-party applications from its App Store?

Apple: Contrary to published reports, Apple has not rejected the Google Voice application, and continues to study it. The application has not been approved because, as submitted for review, it appears to alter the iPhone's distinctive user experience by replacing the iPhone's core mobile telephone functionality and Apple user interface with its own user interface for telephone calls, text messaging and voicemail. Apple spent a lot of time and effort developing this distinct and innovative way to seamlessly deliver core functionality of the iPhone.

At first glance what Apple has written doesn't even appear to be an answer to the question. Apple has, surprisingly, not claimed that it's protecting users—from harm, or from confusing apps. It only alludes to the fact that it has previously cited "duplicating existing functionality" (read: competing with Apple) as grounds for rejection.

Now, it is Apple's platform to mold as they wish; if consumers get a gratis dialer app either way, what's the harm? Why would Apple object to third-party developers making the iPhone better? Apple recognizes that it can't constrain them from subsequently bringing equivalent functionality to Android or WebOS or whatnot. What if there comes a day when the most commonly used apps (dialer, browser, etc.) have feature parity cross-platform? Who would buy an iPhone then? Many people, to be sure, just not quite as many as before.

But instead of staying competitive by making great software, Apple is doing pretty much the opposite. It is trying to forestall competition the only way it knows how: by crippling the iPhone's software—barring entire classes of applications—to obfuscate comparison between its products and competitors'. The result? There's a whole world of apps now that the iPhone just won't run, to say nothing of the apps that never get written because development is such a crapshoot. Users have to pay the cost for Apple's decisions every day now.

To add insult to injury, Apple is eager to remind everyone just how much "time and effort" its engineers spent on the iPhone's dialer. Does Apple think so little of its users that it considers its own good intentions justification enough to override users' requests? This isn't elementary school. You do not get points for "effort."

This madness is even codified in the iPhone SDK developer agreement. Native apps are forbidden from carrying out instructions on behalf of users ("executable code" or "interpreted code"), [1] lest users actually get to choose what they want to do. From an engineering standpoint, code is everywhere—web browsers, office programs, anything with macros, even calculators all have "interpreted code" at the core of their functionality. It is striking that Apple actually mandates that apps subvert their users instead of empowering them.

This situation is rather surreal.

Apple does not even try to hide its contempt for its customers. The iPhone is a device that only allows choosing from a circumscribed set of carefully enumerated functions. Apple only thinly veils the fact that it despises third-party developers, who are ostensibly its "partners". If you develop for the iPhone, you have to deal with a company that believes it has more to gain from hindering you than from helping you.

I am not suggesting that Apple's behavior is illegal, or even incomprehensible (the shareholders must love it)—merely abhorrent. We choose the world we want to live in, and this is not something I want to be a part of, not when there are so many worthy alternatives.

Yet, Apple's candor is nothing if not refreshing. Most companies don't openly talk about the mechanics of their anti-competitive practices. They speak of protecting consumers from confusion, or keeping prices low. Not Apple. There is no dissembling here. Apple freely admits that it will do whatever it takes to keep competitors from getting a foothold, no matter the cost to its own customers. When we consider that fact, it seems that the App Store is not the opaque and inscrutable system that many have claimed it is. What Apple has done has been no more, and no less, than what it has said it would do.

[1] 3.3.2 An Application may not itself install or launch other executable code by any means[...]. No interpreted code may be downloaded and used in an Application except for code that is interpreted and run by Apple's Published APIs and built- in interpreter(s).

You will have to see Wikileaks(!) for the full agreement.

Modifying SSH port forwardings mid-session

I frequently use SSH port forwarding to access services on computers I'm connected to (e.g. VNC, web servers, Zeya). For example,

ssh -L 8001:localhost:8080 foobar

connects port 8001 on my local machine to whatever service is running on foobar port 8080.

Sometimes I'll discover mid-session that I wish to connect to a new service I've just started up remotely, or that I forgot to add the -L flag for some service I wanted. I could always just disconnect, add the appropriate port forwardings, and reconnect.

However, I just learned that SSH also supports some escape sequences, one of which lets you break out to a command line, where you can change port forwardings mid-session without disconnecting.

With the default settings, type ~C at the beginning of your session or after a newline. You'll see a command prompt:

ssh>

At this prompt, you can add additional forwardings using the same syntax that ssh accepts:

• Local forwarding to remote service: -L local_port:hostname:hostport
• Remote forwarding to local service: -R remote_port:hostname:hostport
• Dynamic forwarding, e.g. for SOCKS: -D port

Further reading:

• More about escapes from the ssh man page. (Escapes provide access to some nifty other features, too.)
• Reverse SSH (Tricks for making port forwarding even more useful.)

Assorted notes

Many random notes (some for my own reference), each of which is too short to warrant a full blog post:

Emacs

It had always bothered me, just a little, that C-v and M-v, in addition to scrolling, move the cursor to the bottom or top of the screen. This has the odd effect that C-v M-v is not a no-op. Turns out that setting the variable scroll-preserve-screen-position appropriately can fix this. (via emacs-devel)

Chrome

• Have you ever wondered why running Firefox instances get broken when new versions are installed? On GNU/Linux systems the package manager, which runs as root, pays no mind to what non-root users are doing. Some apps, like Firefox, run into major trouble because they'll load additional files after startup that can't be mixed and matched with the previous versions (this isn't really a problem for programs that are essentially just one binary). Chrome acquires immunity to this with its Zygote mode, which basically means do not load anything from disk after startup. A simple idea, but it takes some work to follow through with it.
• Among visitors to this blog, Chrome is the second most popular browser, with a 9.5% share! Chrome leads IE (6.6%), Safari (5.9%), and Opera (4.3%), and trails only Firefox (72.6%). You can sort of see what a non-representative sample of web users happens across this blog.

Unix/Ubuntu

• Soundconverter (aptitude install soundconverter) is a handy GTK/GNOME program for converting (transcoding) audio between formats. It is easy to use, transfers all the music metadata, and seems to take full advantage of multicore processors. (I use it to downsample my music, mostly in FLAC, to Ogg or MP3 for use on portable devices.)

• When using find with xargs, xargs will get tripped up by filenames with spaces (it will treat each space-delimited component as a different argument). You can get around this by changing the delimiter in both find and xargs to \0 instead of space, as follows:

  find . -iname '*.tmp' -print0 | xargs -0 rm

  You can usually achieve the same effect with find ... -exec but I can never remember how to use it.

HTML, HTML5

Some things I picked up while working on Zeya:

• Making a frame-like layout with CSS

• HTML5 audio/video APIs as implemented in Firefox. The audio/video APIs provide nearly all the features you'd need for a music player. Just add chrome!

• Detecting HTML5 features (from Dive Into HTML5)

• One cool feature in HTML5 that you may not have heard of (because it's not quite as earth-shattering as video, canvas, or local storage) is "placeholder text" for text boxes.

  

  (The text goes away when you focus the input and/or type something in it.)

  It's a feature that (I assume, at least) people have been using Javascript hacks to implement for a long time.

Git for researchers

In my previous job—as a grad student, doing computational/biomedical research—I used Git to manage my projects.

For small projects, people usually treat CVS/SVN as checkpointing tools—tools to get you back to a known good state when you've screwed up. Git, however, provides a whole new vocabulary you can use to talk about creating, altering, composing, combining, splitting, undoing, and otherwise manipulating changes to code (commits). It helps you get stuff done faster every day, not just when you mess up.

Here are a couple of reflections and "lessons learned" on really using VCS to your advantage in a research environment, where some of the rules of thumb are a bit different from those in industry.

(They seem so stunningly obvious now that I've committed them to writing, but they seemed much less so when I first articulated them to myself.)

Retaining history, all of it. I have found git merge -s ours to be very handy. It produces a merge commit and merge topology, tying in the history of the other branch, but without applying any of the changes produced in that branch.

Typically, if a feature doesn't pan out, you delete the corresponding branch and destroy all evidence that you tried. But in exploratory or research contexts, the details of your failed experiments can be quite important. You might need to revisit some past state in order to perform further investigation. Or maybe you want to obtain some numbers for a paper or presentation.

Graphically: imagine you have a "successful" branch feature1 and a "failed" branch feature2 (left). You don't want to git branch -D feature2, since that could cause its history to be lost. If you instead git merge -s ours feature2, you get a topology where the states from both branches appear in your git log (right), but the state at the tip is the same as that at feature1.

* ddddddd (refs/heads/feature1) * ccccccc * bbbbbbb | * 2222222 (refs/heads/feature2) | * 1111111 |/ * aaaaaaa

* eeeeeee "Merge branch 'feature2'." |\ * | ddddddd (refs/heads/feature1) * | ccccccc * | bbbbbbb | * 2222222 (refs/heads/feature2) | * 1111111 |/ * aaaaaaa

This kind of setup makes tracking your progress super easy. My git log basically becomes the scaffolding for my research notebook. I have bare-bones notes like the following:

Commit 2222222: this change did not improve quality at all. Furthermore it runs much slower, probably because blah blah blah blah. See full output in /home/phil/logs/2222222.

The great thing is that now every result (whether a success or a failure) has, attached to it, a commit name: a pointer to the exact code that generated that result. If I hadn't had complete change history so easily available, I would have spent half of my time second-guessing results I'd already obtained.

This application also demonstrates the strengths of DVCS versus CVCS. Research and software development do not happen in a clean linear way. There is lots of backtracking, and sometimes you cannot expect to work effectively with a VCS whose basic model is "one damn commit after another."

Summary: 90% of everything ends in failure. Keeping your failure history (as well as your success history) around is something that is underemphasized.

Long-lived branches vs. refactoring. If you know what you're going to do in advance, then it's not called research. In my work, what I ended up writing on a day-to-day basis depended more on experimentation and testing than on planning and specs. Here's some sample code for illustrative purposes:

# (1)
def my_function(a, b):
   foo = random_sample() # Random heuristic
   something(foo)
   ...

I want to find out how the following code stacks up against (1). Does it perform better? Is it faster?

# (2)
def my_function(a, b):
   foo = shortest_path(a, b) # A better(?) heuristic
   something(foo)
   ...

In reality we might be evaluating alternative heuristics (as here), different numeric parameters, alternative algorithms, or an alternative data source (e.g., training vs. testing data).

Sometimes, when there are a number of alternatives, the right thing to do is to refactor to parameterize the code, for example,

# (3)
def my_function(a, b, heuristic = 'shortest_path'):
   if heuristic == 'random':
       foo = random_sample()
   elif heuristic == 'shortest_path':
       foo = shortest_path(a, b)
   else:
       foo = ... # Additional logic...
   something(foo)
   ...

But every parameterization increases complexity. The new argument is something you have to think about every time you or someone else tries to read your code. Your function is longer, leaks more implementation details, and provides less abstraction. So you don't want to go down this route unless it's necessary. If one choice is a clear winner, and every invocation is going to pass the same argument, then the extra generality you introduced is a liability, not an asset. To do that refactoring can be a lot of work without much reward.

So you want to run and evaluate the alternatives before refactoring. People who find themselves in this situation often write code like this:

# (4)
def my_function(a, b):
   foo = random_sample()
   ## Uncomment the next line if blah blah blah
   # foo = shortest_path(a, b)
   something(foo)
   ...

which is convenient to write, but setting all the switches by hand whenever you want to run it is rather error-prone, especially if the difference is more complicated than one line.

Branching saves the day by letting your tools manage what you were doing by hand in (4). You can compare alternatives like (1) and (2) above against each other if you keep them in parallel branches (granted, you can't select between the alternatives at runtime, but that may be OK). Maintenance is a breeze: with git merge it's easy to maintain multiple parallel source trees, differing by just that one line, for as long as you please. And because you're committing every merge commit, your results are 100% reproducible (if you were messing with your files by hand, in order to reproduce a code state you would have to not only specify a commit name, but also what lines you had commented and uncommented).

After branching, you can mull it over and obtain data on all the alternatives. When you've made your decision, you either drop one implementation and end up with (1) or (2), or, if you need the generality, then you refactor so you can choose between them at runtime (3).

Summary: lightweight branches allow you to defer the work of refactoring rather than having to pay for it up front. They greatly improve the hackability of code, by letting you try out many different alternatives reliably and without much hassle.

Zeya 0.3

I'm pleased to announce the 0.3 release of Zeya. Zeya is a music player that runs in your (HTML5 draft standard-compliant) web browser, giving you streaming access to your music collection from pretty much anywhere.

Romain Francoise has generously packaged Zeya for Debian. Debian "testing" (squeeze) users can now install Zeya as follows:

# apt-get install zeya

(Zeya 0.2 is in Debian "testing" at present; Zeya 0.3 will be in "unstable" shortly and in "testing" after the requisite testing period.)

Many significant changes have been made since Zeya 0.2:

• You can filter your music collection by title, artist, or album with Zeya's new search functionality. (Thanks to Romain Francoise)
• Zeya implements traffic shaping for Firefox clients, to keep from hosing low-bandwidth network links.
• Zeya supports password protecting your music collection with Basic HTTP authentication, configurable with --basic_auth_file. (Thanks to Samson Yeung)
• The default backend is now dir (read all music within a directory) instead of rhythmbox.
• Initial load time is significantly improved, as Zeya now compresses output data when appropriate. This yields a 3-7x decrease in transfer size. (Romain Francoise)
• The target output bitrate can be set with --bitrate. (Romain Francoise)
• Zeya does a better job of guessing reasonable metadata when the ID3 tags are missing. (Samson Yeung)
• Zeya listens on IPv6 interfaces by default. (Romain Francoise)
• Zeya is multithreaded for improved parallelism.
• zeyaclient.py supports skipping to the next song (with C-c) and jumping back to the query prompt (with C-c C-c).
• Zeya decodes MP3s using mpg123 instead of mpg321, for some performance improvements.
• An online guide to the keyboard shortcuts has been added (click "Help" at the bottom or press ?).

Many bug fixes and UI improvements have also been made.

Known issues:

• zeyaclient has not yet been updated to support basic HTTP authentication.

You can obtain Zeya via git:

git clone http://web.psung.name/git/zeya.git

As I mentioned above, Zeya is also packaged for Debian.

See http://web.psung.name/zeya/ for more information, including a quick start guide. We'd appreciate hearing any problem reports on our new bug tracker or via Debian's bug tracker.