RPM Packaging with the OBS – Part 2

A while back I wrote a post about how to get started packaging software using the openSUSE Build Service by setting up a home project and branching an existing package. This post will go into more detail on how to create a new package from scratch. Keep in mind that I’m just learning this too, so take everything I say with a grain of salt. =)

I assume that you already have osc installed, which is the build service’s command-line client. If you’re using openSUSE, you should be able to get it from the default repos; if you’re using another distribution, you may be able to find a package here, or if that fails, you can always get it from source. Most of the actions described here, such as creating a package, can also be done from the build service’s web interface. Whether you use the web interface or the command-line client is entirely up to you, but I’ll focus primarily on osc usage in this post. The web interface is great, but it’s also far easier to learn on your own, plus I always like encouraging people to use the command-line whenever they can.

Note: my intent here is to not only create a software package, but to do it using best practices. Why bother doing something if you’re not going to do it well?

Creating a Package

First, if you haven’t yet, you’ll need to initialize a local copy of your home project. Create a folder somewhere to store your OBS packages, then cd into it and run osc init home:<username>. If this is your first run, it will prompt you for your username and password.

From your local project, you can create a new package with osc mkpac <packagename>. This method of creating a package will only create a local copy in a new folder; you will need to add sources and commit the changes before it’s available on the server.

The Specfile

The specfile is where all the magic happens, and it is by far the most complicated part of RPM packaging. Fortunately, there is a handy tool for generating new specfiles in the rpmdevtools package. openSUSE users can install it from here, and Fedora users should be able to find it included in the main repos. The basic usage is

$ rpmdev-newspec -t <TYPE> <NAME>

The available types are dummy, lib, minimal, and some language-specific ones for OCaml, Perl, PHP, Python, R, and Ruby. Running it will create a new file called <NAME>.spec. For users who don’t have the tool installed, this is what the minimal template looks like, which I’ll be using in a later example.

At the top of the specfile are several different pieces of information that you will need to fill in about your package.

  • Name – the name of your package (should be filled in)
  • Version – the version number for your package’s source
  • Release – current release number (defaults to 1)
  • License – the license used by the packaged software
  • Summary – short description of the package
  • URL – where the user can find more information about this package’s software
  • Source0 – name of the tarball containing the software’s sources
  • BuildRequires / Requires – list of build / runtime dependencies respectively

Of the above fields, name, version, source, and dependencies (if any) must be filled in; everything else is not strictly required in order to get the package to build, but information like the license and summary will be required if you plan on submitting your package to a repository. In general it’s just good practice to make sure you don’t leave any fields blank.

You’ll notice that there’s one field commented out, and that’s BuildArch. When using the openSUSE build service, the available architectures for a package are specified in its metadata, not the specfile, so there’s no need to fill it in here.

Below these fields you’ll find several different sections, each with a different header.

%description – basically an extended summary. The description is specified in its own section in order to allow the use of newlines. Detailed information about what your package is should go here.

%prep – commands to prepare for the build. The default implementation uses a macro called %setup, which should be all you need in this section for the majority of use cases. The %setup macro expects the source to be specified as a tarball with one root directory called <name>-<version>. It will then take care of extracting the archive and cd’ing into the root folder.

%build – this is where the project source is compiled. The default implementation simply calls make with %{?_smp_mflags}, which will usually contain parameters like -j16 that add support for parallel building. Note: any line of code in the sections %prep, %build, %install, and %clean not starting with a percent sign (which denotes an RPM macro) is interpreted as simple bash. This gives a lot of control over exactly how the software is built. Macros exist to serve two purposes: variable substitution (like %{?_smp_mflags}) and automation of common tasks (like %setup); when neither one of those is needed, you can treat these sections as you would a shellscript.

%install – install the compiled software into the filesystem. The default implementation calls make again, this time with the install target. Since RPM building is done in an isolated environment, we have to make sure that the software is installed into that environment and not our computer’s filesystem, so we pass in a parameter DESTDIR that is set to that environment’s root. Note: any time the filesystem needs to be accessed with an absolute path, make sure you use macros to do it. For example, if you need to manually copy a file to /usr/bin, use cp file/to/copy %{buildroot}%{_bindir}. This has the added advantage of making cross-platform and cross-architecture builds easier since there are fewer hard-coded paths.

%clean – cleans up after the build. Defaults to deleting the entire build environment, which is also the default behavior if the %clean section isn’t specified at all. Unless you have very specific cleaning requirements, then this shouldn’t need to be changed.

%files – a list of files that your package is expected to install. The default implementation simply includes the %doc macro, which tells it to include the folder %{_docdir}/%{name} (the default value is /usr/share/doc/packages/<name>). Appending additional file names to the end of %doc will specify individual files contained in that folder. Note: it is considered an error to install a file that isn’t specified in this section and vice versa. This is mostly for security reasons, though admittedly it can be a pain in the ass, especially if you’re not intimately familiar with the software you’re packaging. Using wildcards can help, though; for example, if your package installs several files in /usr/bin, then you can take care of all of them with the line %{_bindir}/*. Second Note: the %{buildroot} macro isn’t necessary, since it’s just a list of files that are expected to be there on the target system. No actual system modification takes place here.

%changelog – a list of recent changes. This won’t become important until you have to start maintaining your package for a large userbase, and it can remain blank for the time being.

Let’s Write Some Code

To go through a full demonstration of packaging, we’ll first need something to package. We’ll start with the ever-popular hello world example. =)

First, if you haven’t yet, create a new package with osc mkpac and cd into its folder (I’m going to assume a package name of “hello” for this example). Before we create the specfile, though, we need to create our project’s sources. Here’s an example project structure:

hello-1.0
 | - Makefile
 | - src
      | - hello.c

The file hello.c is just your standard everyday hello world:

#include <stdio.h>

int main(void)
{
    printf("hello world\n");
    return 0;
}

And the Makefile is pretty standard too:

CC := clang
CFLAGS := -g -Wall
TARGET := hello
SOURCES := $(shell find src -type f -name *.c)
OBJECTS := $(patsubst src/%,build/%,$(SOURCES:.c=.o))
DEPS := $(OBJECTS:.o=.deps)

PREFIX = /usr/local
BINDIR = $(PREFIX)/bin

all: $(TARGET)

$(TARGET): $(OBJECTS)
    @echo "  Linking..."; $(CC) $^ -o $(TARGET)

build/%.o: src/%.c
    @mkdir -p build
    @echo "  CC $<"; $(CC) $(CFLAGS) -MD -MF $(@:.o=.deps) -c -o $@ $<

install: all
    @echo "  Installing..."; install -D $(TARGET) $(DESTDIR)$(BINDIR)/$(TARGET)

uninstall:
    @echo "  Uninstalling..."; $(RM) $(DESTDIR)$(BINDIR)/$(TARGET)

clean:
    @echo "  Cleaning..."; $(RM) -r build $(TARGET)

-include $(DEPS)

.PHONY: all install uninstall clean

Note that this Makefile includes an install target and uses the DESTDIR variable to determine where files should be installed. Both of these are there in order to make it easy to use in packaging, as these are both expected by the specfile.

Now that our source is written, we need to prepare it for packaging. Run the following commands from your package’s folder (which should be the parent of hello-1.0):

$ tar -cvzf hello-1.0.tar.gz hello-1.0/
$ rm -rf hello-1.0

Now we have our source packaged up into a tarball. We can now create the specfile:

$ rpmdev-newspec -t minimal hello

Open the specfile in an editor and make sure you have the following fields specified:

  • Name: hello
  • Version: 1.0
  • Source0: %{name}-%{version}.tar.gz
  • BuildRequires: clang

You should also put in values for summary, license, and URL, but those aren’t necessary for building. Note that I put clang as a build requirement, since it’s the compiler specified in the Makefile, but no runtime requirements.

The minimal default specfile is almost good enough to work without additional changes; however, there are a couple more things we need to add:

  1. In the %install section, at the end of the make install command, add PREFIX=%{_usr}. By convention, Makefile installations default to /usr/local, but packages should install files to /usr.
  2. In the %files section, add a line with %{_bindir}/*. The only file we want to install will be put in /usr/bin, and this wildcard will catch it for us.

One last thing to check is that your home project has the desired repositories enabled. You can run osc meta prj -e to edit your project’s metadata. Here’s an example if you want to build your packages against openSUSE 12.1:

<project name="home:kog13">
  <repository name="openSUSE_12.1">
    <path project="openSUSE:12.1" repository="standard"/>
    <arch>i586</arch>
    <arch>x86_64</arch>
  </repository>
</project>

After that, you can try a local build with osc build. It will first check the dependencies and cache any that haven’t been cached yet (the first run can take a little while), you’ll be prompted for the root password, and then the build starts. If all goes well, you should get no errors. Assuming you didn’t provide a custom build root, the resulting RPM file can be found somewhere in the vicinity of /var/tmp/build-root/home/abuild/rpmbuild/RPMS.

If you want to make the package available on the server, then run osc add * followed by osc commit. This will push your files to the server and schedule a remote build, whose status you can check either through the web interface or via osc results.

rpmlint

You may not have gotten any errors, but odds are that rpmlint spat back a whole bunch of warnings at you. rpmlint is a tool that analyzes your specfile and makes sure you didn’t do anything stupid. The warnings are very descriptive and usually pretty self-explanatory, and there are too many of them to cover in this post. You can find a list of common checks and what they mean here.

Sometimes you’ll want to tell rpmlint to interpret a check differently, or to skip one entirely. In cases like these, you can define custom rpmlint behaviors using an rc file. The file should be named <name>.rpmlintrc and included as a source, so if you have Source0 set to your tarball, then you can add another value called Source1 set to your rc file. The next time you run a build, rpmlint will take your rc file into account when deciding what errors and warnings to show you.

Hello, World!

And there you have it, your first RPM package created from scratch! In a future post I will cover the process of taking an existing software project and creating a package for it, which is where the real fun comes in.

Until then, happy packaging.

Playing with the Spotify API

The good folks over at Spotify were kind enough to release a development library for their service, called libspotify, which lets anyone under the sun write an application that can search for and play music. It’s really cool, but figuring out how exactly to use it can be difficult. The intent of this post is to help you develop, step-by-step, a small application utilizing the Spotify API in its native C.

The libspotify development libraries are cross-platform, but this post is written primarily with Linux in mind. However, many ideas presented here should be usable on other platforms; the primary differences will be how sound is played and how the project is built. In this tutorial, the application will use an ALSA backend and GNU Make for compilation.

Getting an Account

Unfortunately, since reality often sucks sometimes, you’ll need a Spotify Premium account in order to use libspotify or any application built with it. Fortunately, it’s only $10/month, which is pretty damn cheap considering what it provides.

Assuming you’ve successfully signed up for Spotify Premium, then head over to the libspotify download page and download the version corresponding to your system.

Installing libspotify

If you’re not using Linux, feel free to skip this section.

I highly recommend using this method for installing anything packaged in a tarball. Assuming the tarball was saved to your home directory’s Downloads folder, then log in to a shell as root, cd to /opt, and run these commands (this is for 32-bit Linux; update the version numbers and architectures as needed):

[/opt]# mv /home/<user>/Downloads/libspotify-12.1.51-Linux-i686-release.tar.gz .
[/opt]# tar -xf libspotify-12.1.51-Linux-i686-release.tar.gz
[/opt]# mv libspotify-12.1.51-Linux-i686-release libspotify && cd libspotify
[/opt/libspotify]# mkdir 12.1.51
[/opt/libspotify]# mv * 12.1.51
[/opt/libspotify]# ln -s 12.1.51/ current

These steps are optional, but setting up libraries like this makes it easier to upgrade when a new version comes out. This next step, however, is not optional (if you didn’t follow the steps above, just make sure to run this as root in the extracted directory):

[/opt/libspotify/current]# make install

To make sure that pkg-config can find libspotify, run pkg-config --print-provides libspotify, and if it was installed successfully, it should print back the version number (in this case, 12.1.51).

If pkg-config didn’t print anything, then you might need to update its search path. By default libspotify installs to /usr/local, so run export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig/ and try again. An alternative is to re-install libspotify with a different prefix, one that pkg-config will search by default (such as /usr). Run make in libspotify’s root with no options to see its usage.

In addition to libspotify, make sure that you have the development libraries for ALSA and glibc installed and a C compiler.

Setting Up

Create a new folder for your project (I call mine “spot”), then cd into it and create a sub-folder called “src”. The first thing we’re going to do is make sure we have access to spotify, so we’ll create a new source file like this:

// src/keys.c
#include <stdint.h>
#include <stdlib.h>

const uint8_t g_appkey[] = ... ;
const size_t g_appkey_size = sizeof(g_appkey);
const char *username = ... ;
const char *password = ... ;

The app key, username, and password will all be unique to your account. If you don’t have an app key yet, you can get one here.

Now let’s create a stub for our main source file:

// src/main.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libspotify/api.h>

extern const uint8_t g_appkey[];
extern const size_t g_appkey_size;
extern const char *username;
extern const char *password;

int main(void)
{
    printf("hello spotify!\n");
    return 0;
}

This doesn’t do anything yet other than allow us to access the information provided in key.c and pull in some headers that we’ll need later, including the ones provided by libspotify.

Now we just need to be able to build it. If you’re using make, here’s a generic Makefile that you can use. Otherwise, you can run a command like clang src/*.c -o spot `pkg-config --cflags --libs libspotify alsa` -lpthread.

Running the resulting executable should print “hello spotify!” to the screen.

Creating a Session and Logging In

The first step is to initialize a new Spotify session. libspotify uses structs to store the data necessary to create a new session, which can be initialized in the global scope like this:

// src/main.c

static sp_session_callbacks session_callbacks = {
    .logged_in = &on_login,
    .notify_main_thread = &on_main_thread_notified,
    .music_delivery = &on_music_delivered,
    .log_message = &on_log,
    .end_of_track = &on_end_of_track
};

static sp_session_config spconfig = {
    .api_version = SPOTIFY_API_VERSION,
    .cache_location = "tmp",
    .settings_location = "tmp",
    .application_key = g_appkey,
    .application_key_size = 0, // set in main()
    .user_agent = "spot",
    .callbacks = &session_callbacks,
    NULL
};

Two things to note here. One is that the app key size must be set in main because it uses sizeof(), and the other is the callback list. Spotify makes heavy use of callbacks, and all of the methods defined in session_callbacks will be given stubs shortly. First, though, we’ll set up a basic debugging mechanism. Put the following at the top of main.c:

// src/main.c
#define DEBUG 1

void debug(const char *format, ...)
{
    if (!DEBUG)
        return;

    va_list argptr;
    va_start(argptr, format);
    vprintf(format, argptr);
    printf("\n");
}

This method mimics printf, but will only print text when DEBUG is non-zero. So using this, we will now create our callback stubs:

// src/main.c

static void on_login(sp_session *session, sp_error error)
{
    debug("callback: on_login");
}

static void on_main_thread_notified(sp_session *session)
{
    debug("callback: on_main_thread_notified");
}

static int on_music_delivered(sp_session *session, const sp_audioformat *format, const void *frames, int num_frames)
{
    debug("callback: on_music_delivered");
    return 0;
}

static void on_log(sp_session *session, const char *data)
{
    // this method is *very* verbose, so this data should really be written out to a log file
}

static void on_end_of_track(sp_session *session)
{
    debug("callback: on_end_of_track");
}

Now let’s try to create a session and log in:

int g_logged_in;

int main(void)
{
    sp_error error;
    sp_session *session;

    // create the spotify session
    spconfig.application_key_size = g_appkey_size;
    error = sp_session_create(&spconfig, &session);
    if (error != SP_ERROR_OK) {
        fprintf(stderr, "Error: unable to create spotify session: %s\n", sp_error_message(error));
        return 1;
    }

    int next_timeout = 0;

    g_logged_in = 0;
    sp_session_login(session, username, password, 0, NULL);
    while (!g_logged_in) {
        sp_session_process_events(session, &next_timeout);
        usleep(next_timeout * 1000);
    }

    printf("success!\n");
    return 0;
}

And a quick update to our login callback:

static void on_login(sp_session *session, sp_error error)
{
    debug("callback: on_login");
    if (error != SP_ERROR_OK) {
        fprintf(stderr, "Error: unable to log in: %s\n", sp_error_message(error));
        exit(1);
    }

    g_logged_in = 1;
}

That’s a lot of code to keep track of at once, so for reference, this is what your program should look like now. Build it, run it, and if all went well, you should see “success!” printed to the screen after a short wait. If not, then an error message should be displayed saying what went wrong.

So, what exactly is going on? Well, creating the session is pretty straightforward. You make a call to sp_session_create, passing it references to our structs, and check if it worked. If not, print out the error and exit the program.

Then we try to log in. This one’s a little more complicated, since we have to wait for the callback before we know if it worked or not. We use a global variable g_logged_in to keep track of this; set it to 0, try to log in, and then loop until it gets set to 1 by the callback.

libspotify uses a very event-centric design, so the heart of any program built on it is a loop that repeatedly calls sp_session_process_events, which takes a session object and the location of an int variable, where it saves the number of milliseconds until it should be called again. Since our program is single-threaded, we can use a simple call to usleep to wait until libspotify is ready to process more events.

Alright, so far so good. Now let’s do some searching.

Querying for Tracks

libspotify offers many different ways to query the Spotify database, but to keep things simple, we’ll ask the user for both an artist and a track name and take just the first result.

First, we’ll modify the event loop:

while (1) {
    sp_session_process_events(session, &next_timeout);
}

NOTE: technically speaking, this is not the correct way to do this, but it works well enough for a basic single-threaded application. See the FAQ for more information on how it’s supposed to be done, but doing it correctly requires mutexes and conditionals and other complicated stuff that I won’t get in to here.

Now it will run forever until we call exit(). Then instead of waiting inside main, we’ll kick off a search directly from the login callback. Here’s how we’ll do it:

void run_search(sp_session *session)
{
    // ask the user for an artist and track
    char artist[1024];
    printf("Artist: ");
    fgets(artist, 1024, stdin);
    artist[strlen(artist)-1] = '\0';

    char track[1024];
    printf("Track: ");
    fgets(track, 1024, stdin);
    track[strlen(track)-1] = '\0';

    // format the query, e.g. "artist:<artist> track:<track>"
    char q[4096];
    sprintf(q, "artist:\"%s\" track:\"%s\"", artist, track);

    // start the search
    sp_search_create(session, q, 0, 1, 0, 0, 0, 0, 0, 0, SP_SEARCH_STANDARD,
        &on_search_complete, session);
}

static void on_login(sp_session *session, sp_error error)
{
    debug("callback: on_login");
    if (error != SP_ERROR_OK) {
        fprintf(stderr, "Error: unable to log in: %s\n", sp_error_message(error));
        exit(1);
    }

    g_logged_in = 1;
    run_search(session);
}

You’ll notice there’s one piece missing, which is the “search completed” callback. No problem:

static void on_search_complete(sp_search *search, void *userdata)
{
    debug("callback: on_search_complete");
    sp_error error = sp_search_error(search);
    if (error != SP_ERROR_OK) {
    	fprintf(stderr, "Error: %s\n", sp_error_message(error));
    	exit(1);
    }

    int num_tracks = sp_search_num_tracks(search);
    if (num_tracks == 0) {
    	printf("Sorry, couldn't find that track. =/\n");
    	exit(0);
    }

    sp_track *track = sp_search_track(search, 0);
    // TODO: play this track
    printf("Found track!\n");
}

NOTE: the callback for a completed search accepts an opaque pointer to any data you wish to pass in. In the example above we’re passing in a reference to the session object; alternatively, you can define the session in the global scope and pass in NULL or some other piece of data.

Alright, that’s a lot of code, but it’s fairly straightforward. The order of events goes like this:

  1. We send a login request and wait until on_login is invoked. If the attempt failed, print the error and exit.
  2. From there we call run_search, which asks the user for an artist and track name and kicks off the search.
  3. We wait some more until on_search_complete is invoked, signaling that the search has finished.
  4. We check that the search was successful, and if so, we look up the first (and only, since we only requested one) track from the results.

Now that we’ve located a Spotify track object, there’s one last step: playing it.

Playing Music with ALSA

Now we’ve got a decent grasp on how libspotify works, but turning the bytes of a music file into sound is an entirely different beast, and one that’s far too complex for the scope of this post. Fortunately, the libspotify examples come with a working ALSA implementation, so we’ll just borrow some of their magic.

The relevant example is located in share/doc/libspotify/examples/jukebox, relative to libspotify’s root. Copy these files into your project’s src directory:

  • audio.h
  • queue.h
  • audio.c
  • alsa-audio.c

We’ll also need to borrow one method from jukebox.c, and that’s the music_delivery method (renamed to remain consistent with our event callback naming scheme):

static int on_music_delivered(sp_session *session, const sp_audioformat *format, const void *frames, int num_frames)
{
    audio_fifo_t *af = &g_audiofifo;
    audio_fifo_data_t *afd;
    size_t s;

    if (num_frames == 0)
        return 0; // Audio discontinuity, do nothing

    pthread_mutex_lock(&af->mutex);

    /* Buffer one second of audio */
    if (af->qlen > format->sample_rate) {
        pthread_mutex_unlock(&af->mutex);

        return 0;
    }

    s = num_frames * sizeof(int16_t) * format->channels;

    afd = malloc(sizeof(*afd) + s);
    memcpy(afd->samples, frames, s);

    afd->nsamples = num_frames;

    afd->rate = format->sample_rate;
    afd->channels = format->channels;

    TAILQ_INSERT_TAIL(&af->q, afd, link);
    af->qlen += num_frames;

    pthread_cond_signal(&af->cond);
    pthread_mutex_unlock(&af->mutex);

    return num_frames;
}

Almost there! We’re missing a reference to the global audio fifo object referenced in this callback, which we should define in the global scope …

static audio_fifo_t g_audiofifo;

and initialize in main:

audio_init(&g_audiofifo)

Then we’ll create a method that takes a track object and starts playing it:

void play(sp_session *session, sp_track *track)
{
	sp_error error = sp_session_player_load(session, track);
	if (error != SP_ERROR_OK) {
		fprintf(stderr, "Error: %s\n", sp_error_message(error));
		exit(1);
	}

	printf("\n");
	printf("Playing...\n");

	sp_session_player_play(session, 1);
}

Call it at the end of on_search_complete

    ...
    sp_track *track = sp_search_track(search, 0);
    play((sp_session*)userdata, track);
}

…and ask the program to quit once it’s done.

static void on_end_of_track(sp_session *session)
{
    debug("callback: on_end_of_track");
    audio_fifo_flush(&g_audiofifo);
    printf("Done.\n");
    exit(0);
}

And that’s it!

Wrapping Up

If you’ve gotten everything working thus far, then you should now have a custom console application that asks the user for an artist and track name and plays the first matching Spotify result. How cool is that?

I have many more ideas for libspotify in the future. I’ve barely begun to scratch the surface of its feature set, which includes account caching, image downloading, browsing, and song popularity.

More examples can be found here, and be sure to check out the libspotify documentation.

Software vs. Music

So I’ve been thinking.

And this isn’t really something new, but I’ve never gotten around to putting these thoughts anywhere outside of my head. In part because they’re difficult to word correctly, in part because I have no idea if this is even a valid comparison, and in part because of simple laziness.

Here’s the thing. I love software. Anybody who finds this surprising has simply not been paying attention, but it bears repeating. I love logic, and computer software is the ultimate culmination of logical reasoning built to serve a purpose. There’s something about writing a well-written program that lets you step back and treat it as a black box, knowing not only that it works but that it works well, which can then be used as a building block for an even better program, and so on ad infinitum.

But, beyond the realm of fellow computer scientists, no one really cares.

The problem is that nobody really wants to know how their computer works, and hardware and software vendors don’t encourage them to learn. The less you know, the more money Microsoft can squeeze out of you (I don’t mean to pick on Microsoft, but you’re an easy target when you hold a monopoly on desktop computing). Computers are a tool; does anyone really care what type of wood a hammer has in its handle, or how that hammer was put together?

Let’s change the subject for a moment.

I don’t think anybody would dispute that music is a form of art based on time and sound. But what’s the appeal? What is it about pitch and rhythm that causes it to be so attractive? There are entire books written on the subject, so I won’t answer that question here, but suffice it to say that people do, for one reason or another, find arranged, structured sound enjoyable.

What if I were to ask you when the “peak” of modern music was? The 60′s? The early 90′s? How about the past couple years? Many internet denizens will go on at length about how shitty the music of today is, bemoaning the popularity of artists (since music is an art, its creator must be an artist) like Nickelback and Katy Perry.

But what is it about these artists that draws so much derision?

Any typical answer will likely consist of something along the lines of “it’s not original,” or “it’s mass-produced crap.” The key thing to note about these responses is that they place a lot of emphasis on how unique the piece is, on whether or not it creates something new. This is a common trend with how our culture views art; the quality of the end result is heavily influenced by what came before it, and may be perceived far differently than if its merits were considered in a cultural vacuum.

I believe the reason for this line of thinking is that creating something original is much harder than taking someone else’s idea and simply making changes to it, and the harder you work, the more you must love the craft in order to put forth so much effort. Good music is not written by people who listened to the radio once or twice and wanted to write a song too. It’s written by people who study music, who understand on some level the way our culture reacts to certain forms, and who deliberately try to exploit the cultural context of today’s world to create something original.

I would argue that the same is true for software.

Nobody who owns a Mac has probably ever used a media management program that wasn’t iTunes, and plenty of Windows users are running it as well. What the average computer user doesn’t really seem to know is that there is more than one way to organize, find, and play music. Here are some programs that were written to try and improve the act of listening to music:

  • Rhythmbox – the UI was inspired by iTunes, but it is much smaller, leaner, and cleaner
  • Banshee – the UI introduces some great new ideas, most notably the album grid
  • Amarok – nobody else on the market has a UI like this. Just look at those buttons!
  • Clementine – inspired by old-school Amarok, it’s packed with features yet remains relatively lean
  • Guayadeque – the playlist-centric design is a feature that every other media player should seriously consider stealing

And there is so much more, but what all of these applications have in common is that they attempted to introduce something new, from subtle optimizations to complete overhauls, and as a result improve the user experience as much as possible. Not only that, but they are all free and open-source, supported by a community of enthusiasts who care not only about having great software, but about sharing the means as well as the ends.

The main advantage that iTunes has over other programs is that it’s backed by a powerful marketing department and ships as the default player on every Apple computer. There’s no reason to try anything else because iTunes “just works.” Well, so do these other programs, but the effort of finding and installing them is too great if there’s no perceived gain. It would be naive of me to claim that iTunes doesn’t have a good UI and community support, so if someone’s computer already does what they want it to do (play music), then why would they bother trying to change how that task is performed?

What our society currently lacks is a general appreciation for good software, and by “good” I mean software written to serve more of a purpose than to provide its developer with a paycheck. Good software is attempting to improve the experience of its users. To be fair, Apple is nothing if not fanatically devoted to the user experience, but there’s no room for experimentation if you exclusively use Apple products, and they are masters of consumer lock-in.

Unfortunately, there still remains one stumbling block to increasing the adoption of programs that strive to present new ideas, and it’s that software is hard. Writing an application like those listed above is not easy, and often sponsored by a company that can afford full-time developers. On an even more fundamental level, many people have no idea how to find and install new applications, much less appreciate the ideas that they present. Hopefully both of these will improve with time as developer’s tools become more powerful and the average Joe becomes a more capable end user.

Music lovers are known for taking the time to actively search for new music, to find something original, and to help support up-and-coming artists who have the talent and drive to become successful. The difference between someone who enjoys music and someone who truly loves it is that the latter takes that time to explore, and to be open to whatever new ideas they may find along the way. So the next time someone asks me what program I use, be it for playing music, browsing the web, or writing papers, I’ll respond with:

“It’s a pretty obscure program written by this new developer. You probably haven’t heard of it.”

A Generic C/C++ Linux Project Makefile

The GNU Autotools are, arguably, one of the biggest hurdles to learning how to write programs on Linux. From M4 to automake syntax to libtool, there is a lot to keep track of even if you’re just trying to write hello world. The good news: unless you have a completed application that you wish to begin distributing, it’s okay to simply avoid them entirely. The Autotools became popular as a way to ensure maximum portability, but if you’re only worried about it working on your machine, then this is a non-issue.

The absolute simplest way to get your program to compile is to write a shell script:

#!/bin/bash
clang -Wall -g -o program src/*.c

If all you want to do is have your code compile, then the above should work fine, and it’s more than enough for hello world. But what if you want to be able to clean up object files before committing to a repository, or compile only those source files that were changed most recently? This is where Make comes in handy. Here are several generic Makefiles that should help you get started setting one up for your own project.

All of these have several configurable variables in common:

  1. CC – the compiler’s executable (usually gcc, but I prefer clang)
  2. TARGET – the name of the final, compiled result
  3. SRCDIR – the directory your source files are in
  4. SRCEXT – the extension shared by your source files (use cpp for C++ projects)
  5. BUILDDIR – where compiled objects are placed. This shouldn’t exist before compiling

Executable

# Generic Makefile for compiling a simple executable.

CC := clang
SRCDIR := src
BUILDDIR := build
CFLAGS := -g -Wall
TARGET := program

SRCEXT := c
SOURCES := $(shell find $(SRCDIR) -type f -name *.$(SRCEXT))
OBJECTS := $(patsubst $(SRCDIR)/%,$(BUILDDIR)/%,$(SOURCES:.$(SRCEXT)=.o))
DEPS := $(OBJECTS:.o=.deps)

$(TARGET): $(OBJECTS)
    @echo " Linking..."; $(CC) $^ -o $(TARGET)

$(BUILDDIR)/%.o: $(SRCDIR)/%.$(SRCEXT)
    @mkdir -p $(BUILDDIR)
    @echo " CC $<"; $(CC) $(CFLAGS) -MD -MF $(@:.o=.deps) -c -o $@ $<

clean:
    @echo " Cleaning..."; $(RM) -r $(BUILDDIR) $(TARGET)

-include $(DEPS)

.PHONY: clean

Executable (with pkg-config)

If your project has dependencies that can be satisfied with pkg-config (and they really should be), then here’s another option. PKGS should be a space-separated list of dependencies as recognized by pkg-config:

# Generic Makefile for compiling an executable, with pkg-config dependencies.

CC := clang
PKGS := ...
SRCDIR := src
BUILDDIR := build
CFLAGS := -g -Wall `pkg-config --cflags $(PKGS)`
LIBS := `pkg-config --libs $(PKGS)`
TARGET := program

SRCEXT = c
SOURCES := $(shell find $(SRCDIR) -type f -name *.$(SRCEXT))
OBJECTS := $(patsubst $(SRCDIR)/%,$(BUILDDIR)/%,$(SOURCES:.$(SRCEXT)=.o))
DEPS := $(OBJECTS:.o=.deps)

$(TARGET): $(OBJECTS)
    @echo " Linking..."; $(CC) $^ -o $(TARGET) $(LIBS)

$(BUILDDIR)/%.o: $(SRCDIR)/%.$(SRCEXT)
    @mkdir -p $(BUILDDIR)
    @echo " CC $<"; $(CC) $(CFLAGS) -MD -MF $(@:.o=.deps) -c -o $@ $<

clean:
    @echo " Cleaning..."; $(RM) -r $(BUILDDIR) $(TARGET)

-include $(DEPS)

.PHONY: clean

Shared Library (with pkg-config)

Finally, here’s one for projects that compile to a shared library instead of an executable (to change the name of the library, adjust LIBNAME rather than TARGET):

# Generic Makefile for compiling a shared library.

CC := clang
PKGS := ...
LIBNAME := mylib
SRCDIR := src
BUILDDIR := build
CFLAGS := -g -Wall `pkg-config --cflags $(PKGS)`
LIBS := `pkg-config --libs $(PKGS)`
TARGET := lib$(LIBNAME).so
LDFLAGS := -shared -Wl,-soname=$(TARGET)

SRCEXT = c
SOURCES := $(shell find $(SRCDIR) -type f -name *.$(SRCEXT))
OBJECTS := $(patsubst $(SRCDIR)/%,$(BUILDDIR)/%,$(SOURCES:.$(SRCEXT)=.o))
DEPS := $(OBJECTS:.o=.deps)

$(TARGET): $(OBJECTS)
    @echo " Linking..."; $(CC) $(LDFLAGS) $^ -o $(TARGET) $(LIBS)

$(BUILDDIR)/%.o: $(SRCDIR)/%.$(SRCEXT)
    @mkdir -p $(BUILDDIR)
    @echo " CC $<"; $(CC) $(CFLAGS) -MD -MF $(@:.o=.deps) -c -o $@ $<

clean:
    @echo " Cleaning..."; $(RM) -r $(BUILDDIR) $(TARGET)

-include $(DEPS)

.PHONY: clean

Remember, these are not intended to be the be-all, end-all solution to building a project. If you’re seriously considering distributing your project to the full free software community, then it would be a good idea to consider using the Autotools. However, if you just want to get up and running so you can start hashing out ideas and functionality, then these should provide you with a quick jump-start so that you can get straight to coding as fast as possible.

Happy programming.

The Price of Free

Prelude

I’ve had free software on my mind quite a bit lately. This is likely due in part to the recent RMS interview on the Linux Action Show, reading The Cathedral & The Bazaar, and my recent purchase of a ZaReason laptop, which is the first time I’ve made such a major hardware purchase with Linux support as the top priority.

Before any of my thoughts here make sense, it’s important to emphasize how I view and approach software. Computers are first and foremost a tool, but to the vast majority of the world, that’s all they are. There is by and large no appreciation for the complexity (and dare I say, art) of computer software beyond “I love how the little elves inside my Mac make it possible to watch cat videos.” On the contrary, people who actually know a little bit about how computers work are classified as nerds. You’re not supposed to care, since Apple and Microsoft will take care of all that hard stuff for you if you just hand them a little bit of money.

I firmly believe that capitalism is both the best and the worst thing to happen to software. I say best because without the funding provided to groups at Bell Labs and MIT, software as we know it would likely not exist. In the span of a generation, we’ve gone from simple number crunching with computers the size of a room to having, quite literally, the entire knowledge base of mankind in the palm of our hand.

But this comes at a cost in the form of demand. The usefulness of computers cannot be overstated, and neither can their demand. Because demand is so high and the number of people who know enough to fulfill that demand is so low, Apple and Microsoft (among others) can charge users much more than they would otherwise be able to. In dollars, how much is an operating system worth? $200? $1,000? $5?! Nobody knows. This excess demand is seen most sharply on the internet, where good programming and security practices are often eschewed in favor of getting it done now. Everyone and their mother wants a website or an app; entrepreneurs are coming up with grandiose ideas for the next great product, but just need someone to “code it up for them.” The appreciation for the process of software development is almost completely overshadowed by the rabid desire for what it produces.

This isn’t to say that everyone should drop what they’re doing and go learn to program; I do want some job security, and specialization is what made society what it is today; but given the prevalence of computers in our day-to-day lives, I do believe it’s important to have a more fundamental understanding of how they work. It should not be socially acceptable to proudly admit knowing nothing about computers while those who do know something about computers are, quite often, ridiculed for that knowledge.

On Users of Free Software

The existence of free and open-source software like Linux is a modern miracle that goes largely unnoticed. We live in a capitalist-driven society, yet for the past few decades, people have been contributing source code for free to improve the quality of many different software projects. Why? Because we love software. Somewhere out there in this capitalist, algorithm-illiterate world, there are enough people who are not only smart enough to write software, but are passionate enough about it to spend their free time doing it. Linux is a labor of love, as is almost every other free software project in existence. We want software to get better, but more important than that, we want it to be more than just a tool. We want it to be our tool.

I want more people to use Linux, because an increased user base would help prove its validity as a day-to-day operating system. More users = more testers = more bugs reported = more bugs fixed. But, due to the lack of large numbers of paid developers (Red Hat and GNOME are examples of paid free software developers, but their size pales in comparison to Apple and Microsoft), there is a price to be paid for using free software: to get the most out of free software, you must participate in it. Linux is not a tool to be consumed in the same way as Mac and Windows. If something goes wrong, you must put in some effort to fix it, either by searching Google for people who’ve had a similar problem, filing a formal bug report, or attempting to implement a fix yourself, but there is no company standing by to take your complaints.

There is nothing in the free software world that I hate more than non-constructive criticism, since the whole point of free software is to spread ideas and introduce new ones, not to tear down someone else’s. It is quite literally impossible to please everyone, so there’s no point in even trying to. This means that those of us who use free software will, ultimately, run into something that we don’t like. And that’s okay, because we have every right to change it, either through a patch or a new extension; in fact, given how short-handed the developers of that software likely are, we’re almost obligated to. This doesn’t mean that you have to be a programmer in order to use free software (it is free, after all), but it does mean that you should put in a little effort to become part of the community if you’re going to criticize the software for an outstanding bug or strange design decision. Quite often it’s enough to share your experience, either through a bug report or as a feature suggestion, where someone can see it and create a solution.

Joining a free software community is, however, easier said than done. The first step is to locate the project’s official communication channels. As an openSUSE user, this would be the forums, IRC, and mailing lists. Once you begin to run into specific issues that you want to solve, you’ll want to find out where to submit bugs and suggest features. Taking a glance through the project’s home page, we can find the wiki and even a social network. Other, smaller projects likely won’t have quite as many different places to communicate, but almost all of them will have a mailing list and a place to report bugs.

Bottom line: if you use Linux or other free software and you’ve run into an issue ranging anywhere from severe bug to minor annoyance, talk to someone about it. Someone who can help. That’s what free software is about, and we as a community want nothing more than to see the user base grow and the software improve. Post on the forums. Lurk in an IRC channel. Because without community support, you will eventually run into something you don’t like, get frustrated, and wonder why you didn’t just stick with Windows. And that’s the price of free software.

Haskell Code Jam

Google Code Jam is coming up soon, so it’s time to practice. This post will cover two practice problems, with full solutions provided at the end of each one. Clicking on the title will open up the corresponding page for that problem.

At the end, I provide a re-usable module incorporating many of the techniques that will be discussed.


Reverse Words

Let’s start off easy. The goal of this problem is simply to take a string and reverse the order of its words. Input looks like this:

3
this is a test
foobar
all your base

And output should look like this:

Case #1: test a is this
Case #2: foobar
Case #3: base your all

Alright, so first we need to figure out how to read the input. Since we’re reading from standard input, it’s fairly easy:

main :: IO ()
main = do
    input <- fmap lines getContents

Now we have the required input as a list of strings. The head of the list will be the number of cases (in this case, 3), followed by one line for each case. Since we know in advance that each case only needs one line and we have all the lines stored in a list, it’s not really necessary to read in the number of cases. The input we’re really interested in is everything else:

-- inside main
let input' = tail input

Here’s our first big stumbling block. We have the input in a list, but how do we loop through it in a way that lets us print out the case number with it? Haskell is stateless, so a standard for loop won’t work.

There are probably other ways to do this, but my solution is to create some new data types:

data Unsolved = Unsolved { unsolvedNumber :: Int, input :: String }
data Solved = Solved { solvedNumber :: Int, answer :: String }

Notice that there are two separate types, one for unsolved cases and one for solved cases. We’ll see why in a minute, but the important thing is that this gives us the ability to tie a case number to its input. We can use zipWith to turn a list of strings (the input) into a list of unsolved cases:

-- inside main
let cases = zipWith Unsolved [1..] input'

This makes solving the problem very straightforward: we want to take a list of Unsolved cases and turn it into a list of Solved cases, then print them out. In order to print, Solved needs to be a part of Show:

instance Show Solved where
    show (Solved n ans) = "Case #" ++ (show n) ++ ": " ++ ans

There’s one last thing to take care of before we can start implementing the solution. The method that will actually solve the problem for us should take an unsolved case and return a solved one, so we want to map that over our list of cases and print out each result:

-- inside main
mapM_ putStrLn $ map (show.solve) cases

This takes our list of unsolved cases and maps (show.solve) over it, a composite function which solves the case and returns its string representation. The result of that is our list of output lines, which we then print to the screen.

Okay, now let’s get down to the solution. The structure of solve will look like this:

solve :: Unsolved -> Solved
solve (Unsolved n input) = Solved n ans
    where ans = ...

But how do we get the answer? Well, what we want to do is take a string, break it into its separate words, reverse them, and put them back together. Fortunately, Haskell provides built-in methods that will do these, so getting the answer is as simple as composing them together and feeding it the input:

solve :: Unsolved -> Solved
solve (Unsolved n input) = Solved n ans
    where ans = (unwords.reverse.words) input

The full solution can be found here.


Store Credit

This problem is a little trickier. The goal is, given a store credit and list of available items, which two items can you buy to use up all of the credit? In other words, which two numbers in the list of item prices will add up to the value of the store credit?

Our sample input:

3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3

and the desired output:

Case #1: 2 3
Case #2: 1 4
Case #3: 4 5

These require a little explanation, which can be found on the problem’s page. To summarize, each case consists of three lines: the store credit, number of available items, and a space-separated list of item prices. The output consists of two numbers, which are the indices (starting at 1) of the two prices which will add up to the available credit, with the lower index appearing first.

We can see that each case now has multiple lines of input, so we need to make a slight change to Unsolved:

type Input = [String]

data Unsolved = Unsolved { unsolvedNumber :: Int, input :: Input }
data Solved = Solved { solvedNumber :: Int, answer :: String }

For convenience, we now define Input as being a list of strings. Solved remains unchanged since our final answer must still be a single string.

Just like in the previous problem, we can ignore the first line of input, since Haskell is high-level enough that knowing the number of cases is not only optional, it’s almost a handicap. It’s much easier to simply deal with a list of strings than it is to try and incorporate additional information with it.

main :: IO ()
main = do
    input <- fmap (tail.lines) getContents

Note that instead of simply mapping lines over the contents, we can use the composite function tail.lines, which will convert the contents into a list and drop the first element for us, saving us a line of code.

But we can’t simply create our list of cases using this result, because each case requires multiple lines of input. We need to convert this list of strings into a list of inputs, where each element is a list of three strings (since each case requires three lines of input). The following method will do that for us:

splitIntoCases :: [String] -> [Input]
splitIntoCases input
    | post == [] = [pre]
    | otherwise = pre:(splitIntoCases post)
    where (pre,post) = splitAt 3 input

This method will convert the input

["100", "3", "5 75 25", "200", "7", "150 24 79 50 88 345 3", "8", "8", "2 1 9 4 4 56 90 3"]

into this:

[["100", "3", "5 75 25"], ["200", "7", "150 24 79 50 88 345 3"], ["8", "8", "2 1 9 4 4 56 90 3"]]

Now we have a list of inputs that we can use to create our cases.

-- inside main
let cases = zipWith Unsolved [1..] (splitIntoCases input)

Using the same Show instance and mapM_ call from the previous problem, we then just have to work on solve.

solve :: Unsolved -> Solved
solve (Unsolved n input) = Solved n ans
    where ans = ...

The first step to solving this is to parse the input, which we can do with pattern matching and some calls to read:

solve (Unsolved n input) = Solved n ans
    where (l1:l2:l3:_) = input
          credit = read l1 :: Int
          prices = map read $ words l3 :: [Int]
          ans = ...

The first line contains our credit amount, which we read in as an Int. The second line tells us how many items there are, but since this is Haskell, we can skip that. Lastly, the third line is our space-separated list of prices; we can convert it into a list of Int‘s by first splitting it into words and then mapping read over it.

But now we’ve run into another “state” problem; the output requires us to print out the index of the items, but we have no for loops. Time to create another data type.

data Item = Item { index :: Int, price :: Int }

instance Show Item where
    show (Item index price) = show index

Fantastic, now we can zip it up:

-- inside solve
items = zipWith Item [1..] prices

Okay, we have a list of items, complete with index and price. Now we just need to find two whose prices add up to our credit. My preferred method in this scenario is to throw everything into a list comprehension:

-- inside solve
results = [(item1,item2) | item1 <- items, item2 <- items,
                           (index item1) < (index item2),
                           (price item1) + (price item2) == credit]

Using the list of items, this comprehension gives us a list of item pairs where 1) the index of the first item is smaller than that of the second, and 2) the sum of their prices equals the available credit.

Reading through the problem closely, we can see that each case has one and only one valid solution, so we can assume that this will return exactly one item. Knowing this, it’s easy enough to pattern match against it and extract the final answer:

-- inside solve
(res1,res2) = head [(item1,item2) | item1 <- items, item2 <- items,
                                    (index item1) < (index item2),
                                    (price item1) + (price item2) == credit]
answer = (show res1) ++ " " ++ (show res2)

The full solution can be found here.

Creating a CodeJam Module

After doing several problems, it’s clear that there are elements common to each one. Reading input, creating a list of Unsolved cases, and displaying the output are actions common to all code jam problems. So to make things easier (and faster), we can move the common code into a module.

As it so happens, I’ve already done that. But it may require a little explanation.

The goal of the module is to minimize the effort necessary to write a solution. Each solution needs just two things: the list of inputs and a method to convert an input into a result. Given both of these, the codeJam method will convert each input into a Case, solve it, and print the result.

But we can take it one step further. Remember, code jam problems have input that look like this:

N
...
...

The first line is the number of cases, followed by the lines for those cases. For most problems, each case requires the same number of lines. This means that we can programmatically determine how many lines each case needs by dividing the number of input lines past the first by the number of cases. Using this, we can automatically split up the input by case, which means we only need to provide a method that turns that input into an answer. The codeJam' method only requires one argument, which is the method that will solve each case.

This effectively turns the Reverse Words problem into a one-liner:

import CodeJam

main :: IO ()
main = codeJam' (\input -> unwords.reverse.words $ head input)

Store Credit also receives a facelift:

import CodeJam

data Item = Item { index :: Int, price :: Int }

instance Show Item where
    show (Item index price) = show index

main :: IO ()
main = codeJam' solve

solve :: Input -> String
solve input = (show res1) ++ " " ++ (show res2)
    where (l1:l2:l3:_) = input
          credit = read l1 :: Int
          prices = map read $ (words l3) :: [Int]
          itemlist = zipWith Item [1..] prices
          options = [(item1,item2) | item1 <- itemlist, item2 <- itemlist,
                                     (index item1) < (index item2),
                                     (price item1) + (price item2) == credit]
          (res1,res2) = head options

As you can see, being able to determine which parts of a solution are unique and which are re-usable drastically reduces the average number of lines of code necessary to solve each problem.

Good luck at the Code Jam!

Packaging with the Open Build Service

One of the reasons I like and use openSUSE is its (oddly) unique approach to repositories. The other major distros all trend towards having one single massive repository, occasionally adding more if absolutely necessary. openSUSE, on the other hand, proudly wears its modular repository system as a badge of honor, as evident by the existence of such projects as SUSE Studio and the Open Build Service (formerly the openSUSE Build Service). While this carries with it both pros and cons, one of its biggest pros is how easy it makes getting started with packaging; simply create a login at build.opensuse.org and you already have your own personal (public) repo.

As easy as it is to set up your own repo, actually putting software into it can be a little tricky, but that’s the nature of packaging. The easiest method is to find an existing package that you want to modify, tweak it with the desired changes, and either push it to your home repository or formally request that your changes be merged back into the original.

The rest of this post won’t focus much on the details of RPM packaging, but instead will go over the steps necessary to begin modifying existing packages.

Creating an Account

First things first, you’ll need to create an account at build.opensuse.org (click on “Register” in the top-right). Once you’re logged in to your new account, the main page should look like this:

Click on “Home Project” in the top-right to go to your own personal repo:

From here, you could go to “Packages -> Create package / Branch package from other project” and begin uploading/modifying files to it, but we’re going to do this the hard way. The command-line tool takes some getting used to, but will be quite a bit more efficient in the long run.

Getting OSC

The Build Service’s command line tool is called osc and resembles command-line subversion. You can think of osc as a glorified version control system that builds your package on the OBS servers with every commit (Note: osc is NOT a replacement for your version control system).

To install it, you’ll need to add the Tools repository (be sure to update the URL with your openSUSE version if you’re not using 12.1), then search for and install the package osc. You can make sure it’s installed by typing man osc.

Configure Your Project

Before you can start building packages, you have to make sure your project is linked against the correct repositories. For example, if you’re packaging programs for openSUSE 12.1, you’ll need to make sure the standard 12.1 repo is enabled. Other repositories can be added later on if your packages require external dependencies, but don’t worry about that for now. As an example, here’s the metadata for my home project:

<project name="home:kog13">
  <title>kog13's Home Project</title>
  <description></description>
  <person userid="kog13" role="maintainer"/>
  <person userid="kog13" role="bugowner"/>
  <repository name="openSUSE_12.1">
    <path project="openSUSE:12.1" repository="standard"/>
    <arch>i586</arch>
    <arch>x86_64</arch>
  </repository>
</project>

Project metadata can be modified with osc meta prj -e home:<username>.

Branching a Package

Begin by opening a terminal, creating a new folder for OBS packages in your workspace, and cd‘ing into it. I store my OBS projects in ~/workspace/home:kog13.

So, let’s say you installed someone’s hello world program, but you didn’t want it to print out “hello world.” You wanted it to print out something more interesting. The solution: branch their OBS “hello world” package, modify their code, and release your improved version.

A note on branching: when you branch someone’s project, it isn’t available to download through a URL like normal packages. The intent behind branching is to make modifications that you then request be applied to the original via osc submitrequest. If instead you want to fork it completely, you’ll need to create a new package and then copy its contents over. Don’t worry, I’ll cover both scenarios.

It just so happens that I already have “hello world” packaged up. But you’re not happy with it. So you want to branch it. You can do so fairly easily:

osc branch home:kog13/hello-world

This command specifies that you want to branch the hello-world package from the home:kog13 project (my personal repository). After running it, you’re told that you can then check out a working copy:

A working copy of the branched package can be checked out with:
osc co home:<username>:branches:home:kog13/hello-world

This means that the branch has been created server-side, and you can now create a local working copy by entering that command. Note: if you’re not a fan of long colon-riddled folder names, you can specify the name of the new folder using the -o option, e.g. osc co home:<username>:branches:home:kog13/hello-world -o hello-world.

Check out the folder and cd into it. You should see two files: hello-world.spec and hello-1.0.tar. The spec file is the RPM build recipe, which doesn’t need to be changed. What does need to be changed is inside the source tarball:

$ tar -xf hello-1.0.tar
$ cd hello-1.0/

The source consists of just one file, hello.c. To modify its message, open it in a text editor and replace “hello world” with your desired new message. After that’s done let’s package it back up again:

$ cd ../
$ rm hello-1.0.tar
$ tar -cf hello-1.0.tar hello-1.0/
$ rm -r hello-1.0/

This re-creates the source archive with your changes and cleans up the extracted copy. To build it locally, run osc build; to submit your changes and schedule it to be built server-side, run osc commit -m "Your commit message here.". You can check on the server-side build status by running osc results periodically.

Once it’s committed, you can request the owner of the original package (me) to accept your changes with osc submitrequest -m "Please accept my awesome changes."

But what if I refuse to accept your changes? In a bout of righteous fury, you decide to fork my package and distribute it separately through your own home repository.

Creating a Package

Use this command to create a new package server-side:

osc meta pkg -e home:<username>/hello-world

Just give it a title and description, then save and quit. After that, check out a local working copy (not inside any existing local copies of other packages; this is why I recommend keeping a separate folder in your workspace for OBS packages):

osc co home:<username>/hello-world -o my-hello-world

The easiest way to create a fork is to simply copy over everything from the branched project. Assuming that both are checked out into the same parent folder, the following commands should be enough to create the copy and commit it to your home repository:

$ cp hello-world/* my-hello-world/
$ cd my-hello-world/
$ osc add *
$ osc commit -m "Forking your package, can't stop me now!"

Once the package has finished building, you can direct other people to it by giving them your repository’s URL:


http://download.opensuse.org/repositories/home:/<username>/

From there, navigate to the appropriate openSUSE version and architecture, then click on your shiny new package to download and install it.

That pretty much covers the basics of using the build service to make changes and updates to existing packages. Feel free to go nuts hacking on other people’s packages, and always remember to have a lot of fun.

Solving the Queens Problem with Haskell

The eight queens puzzle is a classic problem in algorithm design because it showcases the power of backtracking and recursion. The premise is simple: find a way to place 8 queens on an 8×8 board such that none of them are attacking each other, which means that no two queens can share the same row, column, or diagonal.

Sounds simple enough, but how to implement it? The most basic solution would be to brute force it: try every possible configuration, stopping when a valid one is found. Not very efficient, but hey, at least it’s easy to understand.

As the title suggests, the solution I plan on implementing will be written in Haskell. So first, let’s get some boilerplate out of the way:

import System.Environment

type Queen = (Int,Int)

main :: IO ()
main = do
    args <- getArgs
    let n = case args of [] -> 8
                         (a:rgs) -> read a :: Int
    putStrLn $ show (solveQueens n)

Since we’re solving a problem that takes place on a chess board, we’ll define a custom datatype to represent a queen as a pair of integers, denoting her location as an (x,y) coordinate. Then, in order to make it possible to find a solution for any size board, we support providing a new value of n on the command line, defaulting to 8 if none is provided. After that we call solveQueens, which we haven’t written yet, and display its results.

Brute-Forcing It

So we need to write solveQueens, which should take some n and return a list of n queens. Because Haskell doesn’t support null values, we’ll wrap the result up in a Maybe monad, just in case we get some invalid n. In particular, we want to prevent any negative values (not possible), zero (non-existent), or one (which is vacuously satisfied).

Since Haskell is a functional language, we have to make sure that any data structure we plan to use is passed in as a parameter, but it’s bad design to require an extra parameter from the user just so we can have something to operate on. We also don’t want to check if n is valid more than once, and since we’re writing this in Haskell, it will almost certainly be recursive (spoiler: it will be). Hence, solveQueens will simply be the algorithm’s entry point and not the heavy lifter.

solveQueens :: Int -> Maybe [Queen]
solveQueens n
    | n < 2 = Nothing
    | otherwise = solveQueens' n []

Notice the very clever naming scheme.

Remember, the idea behind brute-forcing the solution is to try every possible combination, stopping once we’ve found one that works (we’re only interested in finding a solution, not necessarily all of them). We want our utility method solveQueens' to take an empty list and transform it into an answer, so assuming that our as-yet unwritten isValid method works as expected, we could write this:

solveQueens' :: Int -> [Queen] -> Maybe [Queen]
solveQueens' n stack
    | x < 1 = if isValid stack then Just stack else Nothing
    | otherwise = foldl loop Nothing [1..n]
    where x = n - length stack
          loop (Just s) y = Just s
          loop Nothing  y = solveQueens' n $ (x,y):stack

What we’re doing here is starting at the right-hand column, picking a value (row) for each one and then recursing on solveQueens' until the board is filled (remember, no two queens can share the same row, column, or diagonal). The decision to go by column instead of row is rather arbitrary, but the decision to go right-to-left is due to Haskell’s list append syntax. The prepend operator (“:”) is faster than the append operator (“++”), so we essentially iterate backwards, adding each new value to the front of the list.

Once we’ve gone off the left-hand side of the board (when x < 1), we know that one queen has been placed for each column. At that point, we return the current value if and only if it's a valid result; if not, then we return Nothing. Once a valid answer has been found, each iteration will simply pass it back up the stack, eventually handing it back to main.

There's just one piece missing: how do we tell if a configuration is valid? Well, we know that no two queens can a) share an x-value, b) share a y-value, or c) share a diagonal. Testing the x and y values is simply a direct comparison, but the diagonal requires a little trick. Two queens are sharing a diagonal if the distance between their y's is equal to the distance between their x's.

Here's the implementation:

isValid :: [Queen] -> Bool
isValid stack = foldl validate True pairs
    where pairs = [(s1,s2) | s1 <- stack, s2 <- stack, s1 /= s2]
          validate False _ = False
          validate True ((x1,y1), (x2,y2)) =
              x1 /= x2 && y1 /= y2 && (abs $ y2 - y1) /= (abs $ x2 - x1)

This code looks dense, but it's really quite simple. We first get a list of square-square pairs, taking care to make sure that we don't compare a square with itself. This list holds all of the comparisons we need to make. Since we're looking for failure conditions (sharing an x, y, or diagonal), we start out by assuming True, and if it turns out that a failure condition was met, we simply pass it back up the stack.

The last line is where the actual logic is. We can invert the failure conditions by using DeMorgan's Law, which means the result of this statement can be set directly; True to continue checking, False if an error was found. Hence, it should return True only if a) their x's are different, b) their y's are different, and c) they are not on a diagonal.

Let's see what result we get for 8, the default value of n:

Just [(1,4),(2,2),(3,7),(4,3),(5,6),(6,8),(7,5),(8,1)]

If we draw out an 8x8 board and mark each of these squares with a queen, we can see that this is indeed a correct solution. But how fast is it?

real    0m6.348s
user    0m6.324s
sys     0m0.020s

Yikes. But wait, we forgot to turn on full optimizations:

real    0m2.068s
user    0m2.043s
sys     0m0.023s

That's a huge improvement, but we can do better.

Backtracking

Believe it or not, the brute-force solution we just finished is already well on its way to being transformed into a backtracking one. Think of it as walking through a maze. When you hit a wall, you want to take a step back and then try a different direction. That's more or less what our brute-force algorithm does. When it finds an invalid configuration, it takes a step back (or several) and tries a different one, though it's still brute-force in the sense that it's designed to test every possible configuration until it finds a valid one.

In order to make our algorithm more efficient, we want to be able to recognize, as early as possible, when our current path is fruitless. We don't want to wait until we actually bump into the wall, since it's much more efficient to turn around the moment we see ourselves walking into a dead-end. What qualifies as a dead-end? Well, if we add a queen onto a square that causes it to be in conflict with one that's already in place, there's no need to wait until the board is filled before backing up.

Let's work backwards a little bit. In order to catch dead-ends as soon as possible, we need to check the validity of the current board as each queen is being placed, rather than waiting until the end. Knowing this, we can re-design our isValid method to take two parameters: the current board and the proposed placement for our new queen. By assuming that the existing board is conflict-free, we only need to make comparisons on the new addition, drastically reducing the number of operations needed.

-- Modified to take advantage of backtracking
isValid :: [Queen] -> Queen -> Bool
isValid stack (x2,y2) = foldl validate True stack
    where validate False _ = False
          validate True (x1,y1) =
              x1 /= x2 && y1 /= y2 && (abs $ y2 - y1) /= (abs $ x2 - x1)

This version is essentially the same, but a little bit shorter than our first one since we don't need to calculate which queens to compare.

solveQueens' also needs a slight modification:

-- Modified to take advantage of backtracking
solveQueens' :: Int -> [Queen] -> Maybe [Queen]
solveQueens' n stack
    | x < 1 = Just stack
    | otherwise = foldl loop Nothing [1..n]
    where x = n - length stack
          loop (Just s) y = Just s
          loop Nothing  y =
              if isValid stack (x,y)
                  then solveQueens' n $ (x,y):stack
                  else Nothing

The initial version of this method simply prepended each possible new value for (x,y) onto the list and recursed on it. Since we modified isValid, we want to prepend (x,y) to the list if and only if it won't cause any conflicts. Then, if we detect that the board is full, we can simply return our current configuration since we know that it's valid.

The results should end up being the same, so what we're really interested in now is the speed (don't forget to compile with optimizations):

real    0m0.006s
user    0m0.002s
sys     0m0.004s

That's more than 300x faster, a difference which grows exponentially as you start to increase the value of n. For example, with n = 9, the backtracking solution has virtually no change in running speed, but our original brute-force solution jumps up to 23 seconds.

Both solutions can be found here.

The algorithm could be further improved by finding all valid configurations and not just the first one. But I'll leave you to do that on your own.
:)

Thinking Functionally

Functional programming is, rightly or wrongly, often seen as a lot harder than imperative or object-oriented programming. There are several possible reasons for this. There’s the obvious issue of education; most college classes teach Java and C++, imprinting the object-oriented mindset deeply into impressionable minds (“Concepts of Programming Languages” was the only class I took that taught functional concepts), and functional languages often work on a higher level of abstraction, appearing to be a lot more “math-y.”

To demonstrate the algorithmic transition that takes place going from an object-oriented/imperative style to functional, here’s a very simple example: printing out the elements of a list (functional languages excel in data traversal and manipulation).

Here’s our algorithm, described imperatively:

  1. Print out an opening bracket
  2. Initialize an index counter, starting at zero
  3. Print out the current element
  4. If there is another element after this one, print out a comma and a space
  5. Increment the index counter
  6. Repeat steps 3-5 until the counter goes past the end of the list

And a simple version in Java:

// imperative algorithm in Java
public void printList(java.util.List list) {
    System.out.print("[");

    int length = list.size();
    for (int i = 0; i<length; i++) {
        System.out.print(list.get(i));
        if (i < length-1)
            System.out.print(", ");
    }       

    System.out.println("]");
}

Java itself doesn’t support a functional style, so let’s switch over to Scala. Scala as a language provides support for both object-oriented/imperative and functional styles, so it provides a good transition.

Here’s the same basic algorithm, re-written in Scala.

// imperative algorithm in Scala
def printList(list:List[Any]) = {
  System.out.print("[")

  for (i <- 0 until list.size) {
    System.out.print(list(i))
    if (i < list.size-1)
      System.out.print(", ")
  }

  System.out.println("]")
}

Okay, we’ve migrated the algorithm over to Scala. Now what? How do we go about making this functional?

Well, as it turns out, the imperative version by itself is almost completely useless. The idea to demonstrate here is that programming in a new paradigm is similar to learning how to speak in a new natural language. Planning out everything you want to say in English and then translating it word-for-word is going to get you a lot of weird stares. To become good at it, you have to learn to think in the new language. Same goes for functional programming.

So, we need a new algorithm. And in the functional way of things, we’re going to write it using immutability and pattern matching.

One of the biggest hurdles to thinking functionally is that immutability (the idea that variables, once created, shouldn’t change) removes one of programming’s most useful tools, the for loop, since it relies heavily on updating an existing value. Instead we have recursion. Looping through a list changes from incrementing an index counter to calling the same function with a smaller list, namely everything minus the first element. We then use pattern matching to quickly deconstruct the list to see what it is we’re working with.

So, a basic functional algorithm might look something like this.

  1. Print out the opening bracket
  2. Print out the list’s first element, if any
  3. If the list has more than one element, print out a comma and a space
  4. Repeat steps 2-3 with the list minus its first element as long as elements remain
  5. Print out the closing bracket

This kind of works, but isn’t quite there yet. Functional programming also has a strong emphasis on minimizing side effects, so to make things a little more meta, we’ll break this up into two algorithms: one which will calculate the contents of the list as a string, and one which will print the brackets and that resulting string.

What the hell am I talking about, you ask?

// functional algorithm in Scala
def printList(list:List[Any]) = {
  def listElements(xs:List[Any]):String = xs match {
    case x :: y :: z => x + ", " + listElements(y::z)
    case x :: y => x.toString
    case _ => ""
  }
  println("[" + listElements(list) + "]")
}

Notice the function within a function. printList() is a function that technically only has one line, which is the print statement on line 8. This does exactly what I described: prints the opening bracket plus the contents of the list plus the closing bracket. listElements() is an inner function that takes care of the task of turning a list of elements into a single string, and is the bulk of the algorithm’s complexity.

Knowing that we can define inner functions, we can narrow the problem down to translating a list into a string. This is the type of problem that functional programming is known for: turning one or more values into a single result. You’ll notice that the return keyword is nowhere to be found in this algorithm; that’s because functional methods must return a value, and so they automatically return the value of the last statement (in this case, whichever case statement was matched). Technically, printList() isn’t functional at all, but is instead a wrapper around the functional listElements() whose only purpose is to carry out the side-effect of printing to the screen.

Scala’s match keyword lets us do pattern matching on a variable. Think of it as a beefed-up switch statement, where we execute certain code based on some variable’s value. Since we’re working with lists, scala’s :: operator will tell the match statement to match against list elements. The last value may or may not be empty, so in general, x :: y matches x to the list’s first element and y to the rest of the list, if any. If the list is empty, this match will fail.

So to re-cap, there are two cases we’re interested in: when the list has at least two elements (so we know to print a comma), and when the list only has one (no comma needed).

The first case statement matches any list with at least two elements: the first element x, the second element y, and the rest of the list (if any) z. In this case, we want to print x, a comma, and then follow it up with the rest (the result of recursing listElements() on the rest of the list y::z).

The second case statement will match any list with at least one element. Note that order is important here: every list that has at least two elements will also have at least one element, so we only want to check this case if the first one fails. Since the first one failed, we know that there’s only one element (in other words, the rest of the list y will always be empty), so we return the string value of x and let the recursion bottom out.

The final case statement will only match if all of the other statements failed, which will only happen on an empty list. To avoid errors being thrown when printList() is called with an empty list, we let the program know to simply return an empty string.

This was only a basic primer, but hopefully it’ll give you a good starting point when beginning to work with functional languages like Scala.

Happy coding.

Adding Javadoc Search to GNOME 3

One of GNOME 3′s more interesting features is its built-in search provider. Press the Super key, start typing, and there are buttons at the bottom of the screen to open up that search term in the engine of your choice. My copy of GNOME 3 (installed via openSUSE) comes with Google and Wikipedia as the default options, which are both very useful. But as a programmer, this opens up the possibility for one of the most global, accessible, and usable documentation search engines ever. Lord knows I’ve wasted way too much of my programming time Ctrl+F’ing through Javadoc pages.

For those who haven’t yet used GNOME 3, here’s what I’m referring to:

Our goal is to add a Javadoc button to this list. On the GNOME Shell side of things, it’s really easy; the harder part is deciding where exactly to search.

I decided to go with using Kiwidoc, a useful website designed to make searching for Javadoc easier. This has several advantages: first, to my knowledge, the official Javadoc pages do not offer online search short of Ctrl+F; second, using Kiwidoc avoids the need to download the full Javadoc to your hard drive, which is required of most Javadoc search plugins. The only downside is, again only as far as I know, there is no way to add custom Javadoc pages to Kiwidoc, so anyone doing jEdit plugin development might be shit out of luck.

To add a new search provider, we’ll need to add a new search provider definition in /usr/share/gnome-shell/search_providers. Here’s what google.xml looks like:

<OpenSearchDescription xmlns="http://a9.com/-/spec/opensearch/1.1/">
<ShortName>Google</ShortName>
<Description>Google Search</Description>
<InputEncoding>UTF-8</InputEncoding>
<Image width="16" height="16">data:image/x-icon;base64,AAABAAEAEBAAAAEAGABoAwAAFgAAACgAAAAQAAAAIAAAAAEAGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADs9Pt8xetPtu9FsfFNtu%2BTzvb2%2B%2Fne4dFJeBw0egA%2FfAJAfAA8ewBBegAAAAD%2B%2FPtft98Mp%2BwWsfAVsvEbs%2FQeqvF8xO7%2F%2F%2F63yqkxdgM7gwE%2FggM%2BfQA%2BegBDeQDe7PIbotgQufcMufEPtfIPsvAbs%2FQvq%2Bfz%2Bf%2F%2B%2B%2FZKhR05hgBBhQI8hgBAgAI9ewD0%2B%2Fg3pswAtO8Cxf4Kw%2FsJvvYAqupKsNv%2B%2Fv7%2F%2FP5VkSU0iQA7jQA9hgBDgQU%2BfQH%2F%2Ff%2FQ6fM4sM4KsN8AteMCruIqqdbZ7PH8%2Fv%2Fg6Nc%2Fhg05kAA8jAM9iQI%2BhQA%2BgQDQu6b97uv%2F%2F%2F7V8Pqw3eiWz97q8%2Ff%2F%2F%2F%2F7%2FPptpkkqjQE4kwA7kAA5iwI8iAA8hQCOSSKdXjiyflbAkG7u2s%2F%2B%2F%2F39%2F%2F7r8utrqEYtjQE8lgA7kwA7kwA9jwA9igA9hACiWSekVRyeSgiYSBHx6N%2F%2B%2Fv7k7OFRmiYtlAA5lwI7lwI4lAA7kgI9jwE9iwI4iQCoVhWcTxCmb0K%2BooT8%2Fv%2F7%2F%2F%2FJ2r8fdwI1mwA3mQA3mgA8lAE8lAE4jwA9iwE%2BhwGfXifWvqz%2B%2Ff%2F58u%2Fev6Dt4tr%2B%2F%2F2ZuIUsggA7mgM6mAM3lgA5lgA6kQE%2FkwBChwHt4dv%2F%2F%2F728ei1bCi7VAC5XQ7kz7n%2F%2F%2F6bsZkgcB03lQA9lgM7kwA2iQktZToPK4r9%2F%2F%2F9%2F%2F%2FSqYK5UwDKZAS9WALIkFn%2B%2F%2F3%2F%2BP8oKccGGcIRJrERILYFEMwAAuEAAdX%2F%2Ff7%2F%2FP%2B%2BfDvGXQLIZgLEWgLOjlf7%2F%2F%2F%2F%2F%2F9QU90EAPQAAf8DAP0AAfMAAOUDAtr%2F%2F%2F%2F7%2B%2Fu2bCTIYwDPZgDBWQDSr4P%2F%2Fv%2F%2F%2FP5GRuABAPkAA%2FwBAfkDAPAAAesAAN%2F%2F%2B%2Fz%2F%2F%2F64g1C5VwDMYwK8Yg7y5tz8%2Fv%2FV1PYKDOcAAP0DAf4AAf0AAfYEAOwAAuAAAAD%2F%2FPvi28ymXyChTATRrIb8%2F%2F3v8fk6P8MAAdUCAvoAAP0CAP0AAfYAAO4AAACAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAQAA</Image>
<Url type="text/html" method="GET" template="http://www.google.com/search?q={searchTerms}"/>
</OpenSearchDescription>

The only parts we’ll need to change are the name, description, and search template string (not sure about the image, since it doesn’t show up with my theme; if I find out how the image works, then I’ll add how to give each provider a custom one). Here’s what my javadoc.xml looks like:

<OpenSearchDescription xmlns="http://a9.com/-/spec/opensearch/1.1/">
<ShortName>Javadoc</ShortName>
<Description>Javadoc Search</Description>
<InputEncoding>UTF-8</InputEncoding>
<Image width="16" height="16">data:image/x-icon;base64,AAABAAEAEBAAAAEAGABoAwAAFgAAACgAAAAQAAAAIAAAAAEAGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADs9Pt8xetPtu9FsfFNtu%2BTzvb2%2B%2Fne4dFJeBw0egA%2FfAJAfAA8ewBBegAAAAD%2B%2FPtft98Mp%2BwWsfAVsvEbs%2FQeqvF8xO7%2F%2F%2F63yqkxdgM7gwE%2FggM%2BfQA%2BegBDeQDe7PIbotgQufcMufEPtfIPsvAbs%2FQvq%2Bfz%2Bf%2F%2B%2B%2FZKhR05hgBBhQI8hgBAgAI9ewD0%2B%2Fg3pswAtO8Cxf4Kw%2FsJvvYAqupKsNv%2B%2Fv7%2F%2FP5VkSU0iQA7jQA9hgBDgQU%2BfQH%2F%2Ff%2FQ6fM4sM4KsN8AteMCruIqqdbZ7PH8%2Fv%2Fg6Nc%2Fhg05kAA8jAM9iQI%2BhQA%2BgQDQu6b97uv%2F%2F%2F7V8Pqw3eiWz97q8%2Ff%2F%2F%2F%2F7%2FPptpkkqjQE4kwA7kAA5iwI8iAA8hQCOSSKdXjiyflbAkG7u2s%2F%2B%2F%2F39%2F%2F7r8utrqEYtjQE8lgA7kwA7kwA9jwA9igA9hACiWSekVRyeSgiYSBHx6N%2F%2B%2Fv7k7OFRmiYtlAA5lwI7lwI4lAA7kgI9jwE9iwI4iQCoVhWcTxCmb0K%2BooT8%2Fv%2F7%2F%2F%2FJ2r8fdwI1mwA3mQA3mgA8lAE8lAE4jwA9iwE%2BhwGfXifWvqz%2B%2Ff%2F58u%2Fev6Dt4tr%2B%2F%2F2ZuIUsggA7mgM6mAM3lgA5lgA6kQE%2FkwBChwHt4dv%2F%2F%2F728ei1bCi7VAC5XQ7kz7n%2F%2F%2F6bsZkgcB03lQA9lgM7kwA2iQktZToPK4r9%2F%2F%2F9%2F%2F%2FSqYK5UwDKZAS9WALIkFn%2B%2F%2F3%2F%2BP8oKccGGcIRJrERILYFEMwAAuEAAdX%2F%2Ff7%2F%2FP%2B%2BfDvGXQLIZgLEWgLOjlf7%2F%2F%2F%2F%2F%2F9QU90EAPQAAf8DAP0AAfMAAOUDAtr%2F%2F%2F%2F7%2B%2Fu2bCTIYwDPZgDBWQDSr4P%2F%2Fv%2F%2F%2FP5GRuABAPkAA%2FwBAfkDAPAAAesAAN%2F%2F%2B%2Fz%2F%2F%2F64g1C5VwDMYwK8Yg7y5tz8%2Fv%2FV1PYKDOcAAP0DAf4AAf0AAfYEAOwAAuAAAAD%2F%2FPvi28ymXyChTATRrIb8%2F%2F3v8fk6P8MAAdUCAvoAAP0CAP0AAfYAAO4AAACAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAQAA</Image>
<Url type="text/html" method="GET" template="http://www.kiwidoc.com/java/s/p/findKeywords?k={searchTerms}"/>
</OpenSearchDescription>

Save it, then restart the shell with Alt+F2 and the command ‘r’, or log out and back in. Now we can use the Shell to search for Javadoc:

And here’s what it brings up:

This can obviously be extended to work with more than just Javadoc; the only potentially hard part is narrowing down what query string to use.

Have fun.