programming

X.509 certificates and Mercurial

Friday, April 9th, 2010 | Development | 2 Comments

As one of the primary developers touching certificates in the Mercurial world, I am often asked how they work, what people need to do to use them and how they can work well with Mercurial.

A principal thing to remember here is that Mercurial will not work as a complete server out of the box, requesting authentication information, in the form of basic, digest, or certificates, at all. This means that in order to use X.509 certificates with Mercurial, one needs to place a web server that knows of these authentication mechanisms in front of it.

This guide is written at the existence of Mercurial version 1.5.1 and touches on many newer features, so if your distribution is old or lacks these features, perhaps it’s time to upgrade to the latest and greatest.

X.509 certificates and SSL/TLS

The most commonly known aspect of X.509 are the certificates. At some level, one can think of a X.509 certificate as having a public and a private key. The public key is the one that secure websites present to you when you, for instance, visit Gmail. You can encrypt data to the intended recipient using this key and only with the corresponding private key can this information be decrypted. In reality, the actual public/private key pair is only used to compute a shared secret, and this is the secret used to communicate securely for the remainder of the conversation.

A X.509 certificate is issued by a certificate authority—some of the commonly known certificate authorities, i.e. that are trusted by a lot of people, can be seen in your browser’s certificate settings—however, a certificate authority can be anybody you trust, e.g. yourself. This certificate authority can then issue server certificates (that represent a server’s identity), and client certificates (that represent a client’s identity). As long as you control the ecosystem of your environment, e.g. you know who your clients are, they know who you are, there is no reason to give out money to some third-party certificate authority, you can accomplish everything you need to on your own.

In order to become your own certificate authority and certificate issuer, you need one of two tools: OpenSSL or makecert.exe, the latter only being available on Windows (there are probably countless other tools as well, to be fair, but I do not cover them here). Below I will cover how to use each of these to set up everything, but before we delve into the details, we will look very briefly at what a certificate authority certificate is, and what ‘normal’ certificates are.

Certificate authority: A certificate authority is basically just a certificate that has signed itself. If you trust this certificate’s public key, you will also trust any certificate that has been issued by this certificate authority.

Normal certificates: A normal certificate is just a certificate that has been signed by a certificate authority (or in reality a certificate authority or an intermediate certificate—you can have a full chain of certificates signing each other if needed).

Now, there are a lot of weird details in these certificates. You may hear terms thrown around such as OU (Organisational Units) and whatnot. The only important part for our purposes is the CN (Common Name). This is the name of the certificate holder, e.g. the server’s name, or the user’s name. So if you access your server as ‘hg.my.cool.server’, your server certificate’s CN must be ‘hg.my.cool.server’.

OpenSSL

Like everything else in the X.509 certificate landscape, OpenSSL has a lot of options, switches and strange voodoo attached to it. Lest this post be turned into a really boring tutorial on certificates, I will just give a few very cursory examples of how you can generate the different certificates. There are plenty of different tutorials on this topic already. Note that Microsoft’s IIS is a tad weird in how exactly it requires the certificate to be constructed, so we will not cover this for OpenSSL, but only for makecert.exe (inquiring minds can figure out all the details of generating certificate requests and processing these in OpenSSL if they prefer).

  • Certificate authority: openssl req -x509 -nodes -days 365 -subj '/CN=MyCA' -newkey rsa:1024 -keyout ca.key -out ca.pem

    The ‘MyCA’ part specifies the name of your certificate authority, so you will probably want to name it something a bit more descriptive.

    This gives us a certificate authority certificate with a private key stored in ca.key and the public certificate in ca.pem. You will need both of these to issue other certificates. Also, if you do not want to get scary pop-ups with invalid certificate trust models in your browser when you browse the hg repositories through hgweb, you will need to install ca.pem into the trusted root certificate authorities in your browsers.

  • Normal certificates:

    • Generate request for signing: openssl req -new -nodes -out name-req.pem -keyout name.key -subj '/CN=name'

      You should, of course, replace name with something more sensible, e.g. your server’s fully qualified domain name (the one people will be entering in their browser to visit it).

    • Signing the request: openssl x509 -req -in name-req.pem -CA ca.pem -CAkey ca.key -out name.pem -CAcreateserial

    Do note that this is the quick-and-dirty way of generating certificates for use in testing/simpler controlled production scenarios. There are a lot more advanced features (like openssl ca) that will allow you to act more like a real certificate authority. If you need these things, go look up some OpenSSL tutorials, then come back here to see how things work with Mercurial.

    The final issue is getting these certificates into a form that your browser will like. They require the certificate to be in a special format, e.g. PKCS#12. To get that we use the openssl tool again like this: openssl pkcs12 -export -in name.pem -inkey name.key -out name.pfx. This file can be imported into your browser in a fitting place.

makecert.exe

makecert.exe is a bit of a different beast from openssl as it interfaces directly with the machine’s or user’s certificate store (the special place where certificates live a happy life in Windows).

  • Certificate authority: makecert.exe -pe -r -ss My -m 12 -n "CN=MyCA"

    This will install the root certificate into the current user’s personal certificate store and mark the private key exportable. To see the current user’s certificate store, run certmgr.msc.

    The certificate’s public key will need to be exported and subsequently imported into the ‘Trusted Root Certification Authorities’ on each machine that trusts this certificate to issue other certificates.

  • Server certificate: makecert.exe -pe -is My -in "MyCA" -n "CN=name" -sky exchange -ss My -sr LocalMachine -m 12 -eku 1.3.6.1.5.5.7.3.1 -sp "Microsoft RSA SChannel Cryptographic Provider" -sy 12

    Do note that this certificate is imported into the local machine’s personal certificate store—this is where IIS expects to find server certificates. To see these certificates, start mmc manually and add the certificate snap-in.

  • Client certificate: makecert.exe -pe -is My -in "MyCA" -n "CN=name" -sky exchange -ss My -m 12 -sp "Microsoft RSA SChannel Cryptographic Provider" -sy 12

If the client and server certificates aren’t generated on the machines you need them on, you need to select the certificate in the management snap-in and export it, including the private key. Exporting as PKCS#12 is usually the safest bet.

This should basically cover how we get the actual certificates. Now, to use them.

Configuring a web server to use certificates

There are countless web servers and operating systems to run them on. I will give a very brief guide to running it on two of the most archetypical web server/operating system combinations: Apache 2.2 on Linux (Ubuntu), and IIS7 on Windows Server 2008. In particular, I will assume that you have already got Mercurial running and working just fine on both web servers.

Apache 2.2 on Linux (Ubuntu)

Setting up apache with mod_ssl can be done in a multitude of ways, I’ll just presume you have enabled mod_ssl already and show how to create a really, really skeleton version of a SSL site that serves Mercurial repositories. We will set up a server that serves a few Mercurial repositories using hgwebdir, from the root of the website, and we’ll only define a virtual host for listening on port 443.

Server certificates

The main configuration is as follows:

<VirtualHost *:443>
  SSLEngine on
  SSLCertificateFile /path/to/myserver.pem
  SSLCertificateKeyFile /path/to/myserver.key
  SSLCACertificateFile /path/to/ca.pem
  SSLCACertificatePath /path/to

  ScriptAliasMatch ^(.*) /path/to/hgwebdir.cgi$1
</VirtualHost>

Do note that if you have cloned the Mercurial repository, you should copy hgwebdir.cgi to a different location and make it executable. Furthermore, see HgWebDirStepByStep for further instructions.

This simple solution serves our self-issued server certificate when we access our website using TLS/SSL.

Client certificates

Client certificates do not require much more than that:

<VirtualHost *:443>
  SSLEngine on
  SSLCertificateFile /path/to/myserver.pem
  SSLCertificateKeyFile /path/to/myserver.key
  SSLCACertificateFile /path/to/ca.pem
  SSLCACertificatePath /path/to
  SSLVerifyClient require

  ScriptAliasMatch ^(.*) /path/to/hgwebdir.cgi$1
</VirtualHost>

This allows anyone with a validating certificate to connect, but no other checks are made. In order to restrict which certificates can be used to connect to the server, we can use the built-in fake authentication mechanism of mod_ssl’s.

<VirtualHost *:443>
  SSLEngine on
  SSLCertificateFile /path/to/myserver.pem
  SSLCertificateKeyFile /path/to/myserver.key
  SSLCACertificateFile /path/to/ca.pem
  SSLCACertificatePath /path/to
  SSLVerifyClient require

  <Location />
    SSLRequireSSL
    SSLOptions +FakeBasicAuth
    AuthName "FakeBasicAuth"
    AuthType Basic
    AuthUserFile /path/to/httpd.passwd
    require valid-user
  </Location>

  ScriptAliasMatch ^(.*) /path/to/hgwebdir.cgi$1
</VirtualHost>

The fake basic auth basically means that we will create a file, httpd.passwd that contains the certificate subjects as usernames and password in its hashed form as password. Then mod_ssl takes care of verifying that the certificate is in this file before allowing it to access the remote location. To get the certificate subject to use as username, you can use openssl to get it: openssl x509 -subject -in name.pem. So for our simple client certificate example above, we would have a httpd.passwd file with the following contents:

/CN=name:xxj31ZMTZzkVA

The xxj31ZMTZzkVA part is password that has been hashed. Usually, if you’ve bought your certificate from a real certificate authority, your certificate will also contain country, organisation, and a host of other fancy things. You can also get these by embellishing the subject when you generate the certificate request, thus a real ‘username’ for a certificate might be /C=US/O=My fancy company/OU=West coast offices/CN=John Doe, but for our simple explanation purposes they merely detract from the message.

This is all it takes to set up client certificate authentication and authorization on Apache.

Internet Information Server 7 (Windows Server 2008)

Server certificates

The server certificate part is easy. Make sure the certificate is installed in the local machine’s personal certificate store, then add a HTTPS-binding to the site you want to host and select the relevant certificate in the drop-down list. That’s it.

Client certificates

Under SSL settings, set that the site requires SSL and that client certificates are required (few systems really work well with the optional part). This is the easy part. The hard part is that after IIS6, Microsoft has decided to drop the interface management UI for mapping certificates to Windows accounts completely, so we will have to do all this in an XML configuration file, and change some system XML-files and whatnot to get everything working.

The first file we need to edit is %SystemRoot%\system32\inetsrv\config\applicationHost.config where we need to find a line like this: <section name="iisClientCertificateMappingAuthentication" overrideModeDefault="Deny"> and change the Deny to Allow. This will allow us to configure this setting in the root of each website that your server is hosting. (If you have users who have write access to the file system, then they will also be able to override the setting for their virtual directories; it is up to you to figure out whether this poses a security risk for you).

In the root directory of your website, edit (or create) the file web.config that we can use to configure IIS7 (and ASP.NET for that matter, but that’s probably not terribly relevant here). For each user we want to grant access we want the certificate’s public key in PEM-encoded format (that is Base-64 in Microsoft parlance), formatted as a single string (i.e., you remove the newlines from the text-file and copy-paste the contents of the certificate, excluding the first and last line with the dashes). Below is a brief snippet that illustrates this:

<?xml version="1.0"?>
<configuration>
  <system.webServer>
    <security>
      <authentication>
        <iisClientCertificateMappingAuthentication enabled="true"
            oneToOneCertificateMappingEnabled="true">
          <oneToOneMappings>
            <add userName="testuser1" password="test" certificate="CERTIFICATE_STRING" />
          </oneToOneMappings>
        </iisClientCertificateMappingAuthentication>
      </authentication>
    </security>
  </system.webServer>
</configuration>

Now we have told IIS that the user with the certificate CERTIFICATE_STRING logs in as the user testuser1 using the password test. However, even though we’ve set the website to require the use of client certificates, anyone presenting an arbitrary certificate can log in, since anonymous access is enabled. To turn this off, and only allow access for the specified users in the authentication section, we will need to modify the authorization rules as well as the authentication rules to disallow anonymous users. Below the /authentication line in the above configuration we add the following:

<authorization>
  <remove users="*" roles="" verbs="" />
  <add accessType="Allow" users="testuser1" />
</authorization>

Unlike the certificate mapping, this can also be handled from inside the IIS configuration manager under authorization. Now, only testuser1 can log on to the site, using his client certificate. In general, you probably want some more users to be able to access your site, so you can go right ahead and add those as well.

Mercurial and X.509 certificates

All this, finally, brings us to how Mercurial interacts with certificates. There are, indeed, several things we need to cover here: how to use server certificates with ‘hg serve’ (the built-in web server), accessing a web server that requires client certificates from the Mercurial client, and how we can use the usual access control methods in Mercurial together with client certificates.

The built-in server, hg serve

Note: For hg serve to use SSL, you must have installed pyopenssl.

hg serve supports a --certificate option where you can specify a certificate file for a certificate that verifies. This detail is important, as right now, with the commands we issued above, we have a certificate file, we have a certificate authority file, and we have a private key file. We need to combine all these into a single file with this command: cat name.key name.pem ca.pem > hgserver.pem. If you have a certificate from a known certificate authority, you do not need to combine the certificate authority certificate into your certificate file.

To use this, you now simply just write hg serve --certificate hgserver.pem and you can access your stand-alone server using HTTPS.

Accessing a web server that requires client certificates

This is, of course, the really interesting part where everything comes together. In order to use client certificates you need them split up into two different files: name.pem and name.key (if you have followed the guide above for OpenSSL, you already have these two files, otherwise you need to generate them). Now we need to set up an auth section in our local hgrc file:

[auth]
something.prefix = my.server.tld
something.cert = name.pem
something.key = name.key

When you try to clone, push, pull, incoming, outgoing to my.server.tld (or any path below that), we will automatically send along the specified certificate file and decrypt stuff using the key file. Also note that the something can really be anything, as long as they are connected. That is, if you have two different client certificates for two different servers you could do something like this:

[auth]
something.prefix = my.server.tld
something.cert = name.pem
something.key = name.key

somethingelse.prefix = my.other.server.tld
somethingelse.cert = othername.pem
somethingelse.key = othername.key

Be aware that the paths to the certificate and keyfile should be absolute (otherwise they’re read relative to your current working directory).

There is currently no way to discern that certificates are included in the request or not (other than the request possibly failing). Also, the error messages that are given back if there are problems with certificates are less than stellar, but that is, unfortunately, the par for OpenSSL (which Mercurial uses by way of Python).

Access control using certificate users

Mercurial contains a number of mechanisms for controlling who can read/push from/to a specific repository. Furthermore, there are extensions such as the acl extension that allows you more fine-grained access control on who may push what files. The usernames that you can specify are delimited with either a space or a comma. See the problem?

A very common certificate username for Apache might be ‘/C=US/S=CA/O=ACME, Inc./OU=Coyote Solutions/CN=John Doe’. This will be parsed as allowing/denying access to the users ‘/C=US/S=CA/O=ACME’, ‘Inc./OU=Coyote’, ‘Solutions/CN=John’, and ‘Doe’. In short, you cannot use these mechanisms with Apache and client certificates right now (this should, of course, be rectified in the Mercurial source code somehow).

With IIS we have no such problem as we have mapped the client certificates to actual Windows account names, and we must just limit based on the Windows account names.

Verifying the server identity

The default for Mercurial (or any Python application for that matter), is to connect to a SSL/TLS server and not check that we actually trust the certificate being served. In fact, it is only possible to make Python do this from Python 2.6 and onward, and only if you specify special flags and special files to some of the SSL/TLS calls. Some kind developer who shall remain unnamed has added the necessary support to Mercurial so that we from Python 2.6 can actually verify the remote party. This is done by specifying a certificate trust file in your hgrc file in the web section:

[web]
cacerts = /path/to/cacerts.pem

This file should contain a list of the certificate authority certificates (PEM encoded), one after the other. If you’re already on a system that has OpenSSL installed, e.g. most GNU/Linux systems, this can be found in the file /etc/ssl/certs/ca-certificates.crt (or wherever your distribution places it). If not, then you will have to construct this file manually.

If verification fails, you will, again, get some cryptic OpenSSL error message.

Conclusion/Summary

These are all the many fancy ways that Mercurial can work together with certificates currently. Some of the ways are cumbersome, but they are hopefully not cumbersome due to Mercurial. We have tried to make them as easy to use as possible (if it can be said that certificates are easy to work with). It is also worth noting that prior to Python 2.6.4 (I believe), it is not possible to use client certificates with Mercurial, if you are also using a HTTP proxy server.

I will try to update this post if/when changes occur to the client and server certificate support in Mercurial. If you have suggestions or issues with using these, please file them on the Mercurial issue tracker, thanks!

Tags: , ,

Covariance and design principles

Thursday, October 18th, 2007 | Development | No Comments

As promised in the last blog post, it is time to get down and dirty with technical facts. Or said in another way, it is time to look at: ‘Why C# let me down’ (you may imagine the blood dripping from the italicised letters). As the title may lead you to believe, the let-down has a lot to do with covariant types, but what are covariant types anyway? Why do they matter? And then how come C# does not have them?

The basic principles of object-oriented languages builds on what in type theory is known as subtyping relationships that are typically expressed σ <: τ, meaning that σ is a subtype of τ. Or expressed in a typical C# manner:

public class τ {}

public class σ : τ {}

So in other words, we have the property that σ inherits from τ, or that σ is a subtype of τ. It is typical of most object-oriented programs (sorry, most well-written object-oriented programs) to allow you to use the type σ in place of the type τ anywhere in the program and still have a correct program. This is what is typically called Liskov’s substitution principle, which can be formulated like this: x : τ ⊢ q(x) ∧ σ <: τ ⇒ y : σ ⊢ q(y). So that is fairly densely looking and what does it really mean? Basically it says: if q(x) is some property that holds on an object x of type τ and if σ is a subtype of τ then if y is an object of type σ then q(y) must also hold. Or in layman’s terms: it must be possible to use a child class instance everywhere a child’s class ancestor is expected, without changes to the program, maintaining correctness of the program. So that is probably a pretty good property to go looking for.

Now, before everything gets lost in theory, let us take a look at the actual problem in C#, using an illustrating example:

public abstract class RandomNumberGenerator {
  public abstract double NextValue();
}

public class DiceResultGenerator : RandomNumberGenerator {
  public DiceResultGenerator(int rolls, int sides) {
    rolls_ = rolls;
    sides_ = sides;
  }

  override public double NextValue() {
    ...
  }

  private int rolls_, sides_;
}

Okay, so this code is a sensible implementation of some random number generator and a dice roller… or is it? When was the last time you got floating point results from rolling a die? Let us fix that up right here and now by changing the double in the DiceResultGenerator to an int. This is a safe operation since int <: double (and because Liskov’s substitution principle otherwise applies here—every time you expect a double you can safely use an int in its place). Ignoring floating point representations and byte sizes this typically holds in most object-oriented languages since the integers are contained in the real numbers. So what happens if we compile the modified source code with the Mono C# compiler (the Microsoft one will give a comparable result)?

`DiceResultGenerator.NextValue()': return type must be `double' to match overridden member `RandomNumberGenerator.NextValue()'

Bummer, we have not got covariance in method return types. This means that whenever we use a DiceResultGenerator, we must get a double out of it, rather than a int, and we will subsequently have to cast it to an int. All this just because the DiceResultGenerator is part of a sensible inheritance hierarchy for different means to obtain random numbers and that most random numbers are floating point values. That is just plain depressing.

So this is exactly what a covariant return type is: when a child class wants to return a subtype of what the overridden function of the ancestor class returns. And it does not work in C#. Of course, it works in C++, but there are so many other things that annoy me with that language.

C# why did you let me down so?! Oh well, it must be time to find the next language I might actually like.

Edit: Astute readers found out that I had switched the subtype relation around in the definition of Liskov’s substitution principle. Sorry.

Tags: , , , ,

Programming packages

Saturday, August 11th, 2007 | LaTeX | 1 Comment

Now that we have seen how to both write commands and environments, it is time to look at how we can reuse this code in several different documents. The basis of reusability in LaTeX is handled through packages, otherwise known as .sty-files. A copious amount of packages exist for LaTeX at CTAN, and we have seen several of them already: tikz, graphicx, fontenc, mathdesign, and many others. Common to each package is that it provides a number of commands and environments that gives you some form of functionality. Tikz allows us to create vector-based drawings directly from inside LaTeX, graphicx allows us to interface with a number of existing graphics formats, mathdesign provides new math fonts that correspond to a number of free and non-free serif fonts.

So, if you have some form of functionality that you use repeatedly in different projects and would like to abstract it away in a separate package that you can easily use in your other projects, a package is what you are looking for. The basis of creating a package is to pick a filename, say, mypackage.sty (on some systems you may have to keep to the 8.3 filename standard, so it may be prudent to name your packages to fit inside that, but it is not a requirement).

Every package starts with either the first or both of the following lines:

\ProvidesPackage{mypackage}[2006/05/01 version 1.0 by Someone]
\NeedsTeXFormat{LaTeX2e}

\ProvidesPackage‘s name is required to be the same as the file of the package, and \NeedsTeXFormat specifies what document format is required in order to use the package (if it is using functionality specific to a certain format). Here, LaTeX2e is what most of us use when we write documents, but plenty of others exist as well.

Packages can, of course, also depend on other packages, but unlike in the main document, we do not use \usepackage to include these, rather, a separate command, \RequirePackage exist instead that otherwise does the same thing (more or less). So if we were to require some higher level constructs for directing command flow using the ifthen package, we could use the following line of code inside our package:

\RequirePackage{ifthen}

With some packages it is also possible to pass them options, for instance for the babel package that takes care of renaming various commands to a specific language:

\usepackage[british,french]{babel}

These options dictate that we should load both the british and french modules and that we want to pre-select french (as that is the last option) for the language to write in. Likewise it might be relevant for your package to provide a number of options that can be used to control overall functionality of the package or pre-define certain environments or commands. Declaring a package option is done using the \DeclareOption command. So if we were to declare a theorem option, it might look like this:

\DeclareOption{theorem}{%
  % code goes here
}

And when we subsequently use the package in a document we can write:

\usepackage[theorem]{mypackage}

All the options aren’t executed at the point of declaration though, it requires a separate command, \ProcessOptions that can occur anywhere in the package code (though naturally after the \DeclareOption and before the end of the package). A reason to place it later in the document than immediately after your declared options could be that some options redefine commands that are introduced later on in the package, for instance.

Most of the remaining code in a package is just a collection of introducing new commands and environments. There is one thing that is worthy of notice, though, namely that command names that are internal to packages are typically given a @-sign inside them, as these are not directly available in normal documents, as we have seen before. Inside a package the @-sign behaves as a letter and you do not need to surround all such uses with \makeatletter and \makeatother. Also, remember that commands must be unique, there are no overloading, so try to pick names that don’t conflict with other packages. Of course, given the sheer number of packages in existence, this may prove rather difficult.

This is basically all there is to creating packages. The rest is pretty much up to what you need to abstract for kinds of behaviour. Looking back at the code we have seen in this blog, we might, for instance, pick out the layout of a book to package. That way we can reuse this layout at a later time, merely by including a package. And that is, in short, the basic idea of packages.

Tags: , , ,

Programming LaTeX — writing environments

Saturday, August 4th, 2007 | LaTeX | No Comments

We have previously seen how to create commands in LaTeX. Today, we will be looking at how we can create environments, that is the things that are typically started with a \begin and ended with an \end command. In the course of writing a document with a barebones LaTeX setup, we may see several of these environments: document, figure, table, itemize and enumerate. Each of these environments dictates some form of structure that helps abstract the actual layout of your document from the contents and structure of your document, an important tenant in the LaTeX world.

We can, for instance, imagine that we are writing a document where all figures are centered before they are drawn. In many cases this is accomplished by people using roughly the following code:

\begin{figure}
  \begin{center}
    % figure code goes here
  \end{center}
  \caption{...}
  \label{...}

\end{figure}

But with this, we have mixed together structure and layout, so let us drag the author out back and shoot him before it is too late. Rather, what we would want to do is somehow create a new environment, say myfigure, that takes care of centering the contents. In order to introduce a new environment, we may use the \newenvironment command, which functions very much like \newcommand except that it takes two arguments: what happens before the content, and what happens after the content. So using this knowledge, we can wrap up the centering code:

\newenvironment{myfigure}{
  \begin{figure}\begin{center}
}{
  \end{center}\end{figure}
}

Do note that the order of appearance of the figure and center environments matter. If you try to end a figure environment with a center environment, LaTeX will throw errors your way. With our brand new environment, we can now write our figure using our own environment:

\begin{myfigure}
  % figure code goes here
  \caption{...}
  \label{...}
\end{myfigure}

Thus, we nicely separate our layout and our structure. Normally it would seem prudent to find a better name than myfigure, one that better describes the purpose of the structural component, but sometimes no nifty names come to mind.

Like with commands, environments can also be given a number of parameters. These parameters are, however, only available in the ‘before content’ code. If we often customise our itemize environments to use different kinds or itemisation symbols, we could create an environment that lets us specify these easily:

\makeatletter
\newenvironment{myitemize}[1]{
  \begin{itemize}
    \expandafter\renewcommand\expandafter{
      \csname labelitem\romannumeral\the\@itemdepth\endcsname}{#1}
}{
  \end{itemize}
}

\makeatother

Now we can use this to change the item symbol like this:

\begin{myitemize}{$\star$}
  \item Test
\end{myitemize}

And there would be a nice little star to the left of ‘Test’.

This is basically what there is to environments at the surface. This leaves the technical details of how they are actually implemented (as they are not a part of plain TeX). In fact, \newenvironment is just a cover around creating two different commands: \environmentname and \endenvironmentname. Here the parameters are passed to the \environmentname exclusively, as that is typically where they are needed. Now, invoking \begin{environmentname} is not entirely the same as invoking \environmentname as \begin also sets up some other variables and starts a new group (scope in regular programming).

The primary goal of using environments, though, is to separate the content from the layout. If you keep this in mind when creating documents it will be extremely easy to tweak the layout without having to go through the entire document every time you wish to change all your figures to be centered, for instance.

Tags: ,

Programming LaTeX — writing commands

Friday, August 3rd, 2007 | LaTeX | No Comments

Most typesetting software lets the user operate within its functionality and thorough programming knowledge is required to write any form of extension to the system, typically in the form of a module written in C. With LaTeX this form of extensibility is built into the language, allowing you to program your own solutions, and to easily use other peoples’ solutions to problems. One of the key places to find these other solutions is at places like CTAN (the Comprehensive TeX Archive Network).

While many premade solutions exist, there will invariably be times where you need something custom made. Today we will look at the basics of creating new commands in LaTeX. Previous familiarity with programming will be a benefit, but, I hope, not an absolute requirement.

A command in LaTeX can accomplish pretty much anything (for the really interested, LaTeX is Turing complete), but for our purposes it is mostly used to abstract away formatting or change the values of counters or lengths. As such, familiar things in LaTeX such as \section, \usepackage and the like are all commands that abstract some behaviour. To familiarise ourselves with how to introduce commands, we will look at a fictional problem: We are writing a larger document containing a lot of acronyms, and we’d like to be able to standardise on the typography for printing acronyms, and ensure that the first time an acronym is used its full definition is written out.

Introducting a command in LaTeX is done using the \newcommand command. Its full definition is on the following form:

\newcommand{command-name}[number-of-arguments]{body}

Inside the body, the arguments can be referenced by typing #n where n is the n’th argument to the command. With this in mind, let us create an \ac command for typesetting acronyms.

\newcommand{\ac}[1]{\textbf{#1}}

What this does it create a command, \ac that takes one argument, and it expands to boldfacing the argument in the text. If you find using bold type for typesetting acronyms bad style, there is, fortunately, a single place to correct the formatting with this command, rather than having to go through the entire document and correct every single acronym.

While this lays the foundation for the command, what we would really like is to be able to define a number of acronyms, i.e. both their short forms and their expanded forms, and have LaTeX make sure that we have always presented the long form of an acronym the first time we use it. This is a good deal tricker, as we will have to introduce commands that are constructed dynamically. Basically we would like to be able to define an acronym like: \acronym{ETA}{Expected Time of Arrival}, and when we use it the first time have it print something like: ETA (Expected Time of Arrival) and just ETA at subsequent occurrances in the text.

So at the core we have something like:

\newcommand{\acronym}[2]{
}

And we need to fill something into the body. If we just do something like this:

\newcommand{\acronym}[2]{
  \newcommand{\acronym#1}{#2}
}

Then we’re told that the command \acronym already exists. So we need some way of splicing acronym and our command together to form a whole command. This can be done with the \csname and \endcsname constructs, like this:

\newcommand{\acronym}[2]{
  \newcommand{\csname acronym#1\endcsname}{#2}
}

However, now this tells us that the \csname command is already defined. So we need some way to indicate to LaTeX that it should resolve and concatenate acronym#1 first, then invoke \csname and finally call \newcommand. We can accomplish this using the fairly low-level command \expandafter. This command does, when placed in front of a command indicate that what comes after it should be expanded before we call the command. So we have to jump over \newcommand and \csname, so we will need two uses of \expandafter, like this:

\newcommand{\acronym}[2]{
  \expandafter\newcommand\expandafter{\csname acronym#1\endcsname}{#2}
}

Using this with our call to \acronym{ETA}{Expected Time of Arrival} creates a new command, \acronymETA, which we can call normally, and this command will print ‘Expected Time of Arrival’.

The next thing we need to accomplish is to only print this expanded text the first time we use the acronym. To aid us slightly, we use the ifthen package’s commands \newboolean and \setboolean as follows:

\newcommand{\acronym}[2]{
  \newboolean{acronym#1}
  \setboolean{acronym#1}{true}
  \expandafter\newcommand\expandafter{\csname acronym#1\endcsname}{#2}
}

Here the \newboolean figures out that the name of the boolean should be expanded before the creation of a new boolean on its own, so we don’t have to place manual \expandafter commands throughout the code.

This means that we have everything in place to create a new command that prints the actual acronym:

\newcommand{\ac}[1]{
  \ifthenelse{\boolean{acronym#1}}
  {#1 (\csname acronym#1\endcsname)
    \setboolean{acronym#1}{false}}
  {#1}
}

Using this as follows:

The \ac{ETA} is now 5 minutes. The \ac{ETA} is now 4 minutes.

Would result in the following: ‘The ETA (Expected Time of Arrival) is now 5 minutes. The ETA is now 4 minutes.’ This is, of course, all great and well, but recreating all of \ac can be a bit taxing, if we want to change the formatting of parts of the word. So let us create two more commands to typeset the acronym with and without the expanded text:

\newcommand{\printlongacronym}[2]{#1 (#2)}
\newcommand{\printshortacronym}[1]{#1}

And we change the definition of \ac to use these as follows:

\newcommand{\ac}[1]{
  \ifthenelse{\boolean{acronym#1}}
  {\printlongacronym{#1}{\csname acronym#1\endcsname}
    \setboolean{acronym#1}{false}}
  {\printshortacronym{#1}}
}

This now lets us change the formatting of acronyms merely by changing the definition of \printlongacronym and \printshortacronym, thus abstracting away all the technical issues of changing boolean values and whatnot from the end user. The user just needs to focus on how to adapt these two commands for his formatting needs. And, if these things are wrapped away in a package, the user can use \renewcommand to change the meaning of the commands.

This is basically all there is to commands: give it a name, some arguments and do something in the body. Even a simple command such as typesetting some code inline in the text might be a boon if you have to go over the document at a later time to fix up the layout.

Advanced commands and TeXing

Now that we have our fancy \ac function, it is time to consider what happens if we write something like: ‘Some of the \ac{CIA}'s archives have recently been opened up.’ The outcome could be one of two things, depending on whether this is the first use of the CIA acronym or not, namely:

Some of the CIA’s archives have recently been opened up.

or

Some of the CIA (Central Intelligence Agency)’s archives have recently been opened up.

In the latter case, the possessive should still have been attached to CIA rather than the parenthesis. One way to cope with this is to use TeX’s mechanism for defining functions and in particular functions with optional parameters. This is done using the TeX function \def. If we were to code a command with optional parameters (keeping in mind that optional parameters are typically given in []‘s as the first part of a command, in TeX), it would look something like this:

\def\acopt[#1]#2{
 \ifthenelse{\boolean{acronym#1}}
  {\printlongacronym{#2#1}{\csname acronym#2\endcsname}
    \setboolean{acronym#2}{false}}
  {\printshortacronym{#2#1}}
}

This basically means we can call it like this: \acopt['s]{CIA} and we’d get:

CIA’s (Central Intelligence Agency)

if this was the first use of the acronym. Now, we could just call \acopt whenever we need to add some fancy possessive or what have you to an acronym. However, we’d like to be able to extend \ac so that we only have to type one command, and that’ll figure out whether to call \acopt sensibly. In order to do this, we must use a built-in command \@ifnextchar. This command is primarily meant to be used from inside a package, but we can use it in normal document code by surrounding it by the two commands \makeatletter and \makeatother. These two commands are necessary, as @ isn’t treated as a normal letter in LaTeX commands and thus we’re required to change @’s code group (if you’re getting confused now, don’t worry, you can just use the two commands around the location where you need to use a command with an @ in it and worry about the details at some later time). With this we can define \ac like this:

\makeatletter
\def\ac{\@ifnextchar[\acopt\acnoopt}
\makeatother

What this does it it queries the token stream (the next bunch of characters in the document, for a very loosely hand-waved definition) and if the next character is a left-bracket we call \acopt, or otherwise we call \acnoopt, the latter of which we can define very easily:

\def\acnoopt#1{\acopt[]{#1}}

With this we can now both write \ac['s]{CIA} and \ac{CIA} and everything will sort itself out nicely.

On the horison

Apart from these few commands we’ve seen, it is also possible to define commands globally using \gdef (commands are otherwise local to the environment they’re declared in), redefine LaTeX commands using \renewcommand, create commands that cannot include paragraph changes using \newcommand* and many, many others. However, the command construction you’ve seen above goes for pretty much all the other commands as well, so presuming you’ve gleaned some meaning from my ramblings, you should be able to get somewhere fast no matter the situation.

Tags: ,

Drawing trees in LaTeX

Wednesday, February 21st, 2007 | LaTeX | 2 Comments

Last time we looked at how we could import graphics in the document using the graphics package. Today, we will look at how we can create vector graphics of trees from inside our LaTeX documents. As there are many aspects of the natural sciences that requires high quality drawings of trees, graphs, etc., it should come as no surprise that there are several packages for LaTeX trying to solve this issue. Some of these are:

There are advantages and disadvantages to all the packages, naturally, mfpic depends on metapost, which takes a certain mindset to use, pstricks works only with latex and not with pdflatex, xypic is primarily for diagrams and graphs, but can also be used for other things, but my definite favourite is pgf, as it works with both latex and pdflatex and generates good-looking output, at least in my opinion.

The pgf package is split in two: an easy-to-use frontend called TikZ and the backend called pgf. Today we’ll be looking exclusively at the frontend and try to draw simple trees with it.

First, let us look at an example of a tree:

\begin{tikzpicture}
    \tikzstyle{every node}=[circle,draw]
    \node {1}
        child { node {2} }
        child {
            node {3}
            child { node {4} }
            child { node {5} }
        }
        child { node {6} }
    ;
\end{tikzpicture}

What is happening here should be fairly self-evident, but let us run over it quickly. The call to \tikzstyle indicates that every node should be drawn, shaped as a circle. As for the tree, we have the root node with a 1 written in it. This root note has three children, of which the middle children has two further children. This gives us the following result (click on the image for the original PDF):

Figure 1

Another useful feature of TikZ is that you can name nodes so you can refer to them later on:

\begin{tikzpicture}
    \tikzstyle{every node}=[draw,circle]

    \node (root) {1}
        child { node {2} }
        child { node {3} }
        child { node (rightmost) {4} }
    ;

    \tikzstyle{every node}=[]

    \draw[-latex,color=red]
        (rightmost) .. controls +(southeast:1cm) and
                                +(right:3cm) ..
            node[near end,above right,color=black] {back}
        (root);

\end{tikzpicture}

In addition to figure 1, we can see that to name nodes we add a (name) after the node command. Once we’ve specified the actual tree, we reset the global style settings for nodes as we don’t want our edge labels having a visible circle around them. The last draw command uses TikZ’ syntax (which is alike to METAPOST’s syntax) for drawing Bézier curves and the embedded node statement is for placing an edge label. The controls statement says that the first Bézier control point is placed 1cm to the south east of the (rightmost) node, and the second Bézier control point is placed 3cm to the right of the (root) node. Thus we can draw lines between nodes easily without explicitly having to state their absolute placement.

The southeast and right in the control nodes are called anchor points in TikZ, and there are plenty other of these. There are, in fact, so many means of customising nodes that it’s impossible to cover it all here. Instead, use the PGF manual. It is very thorough and example-based, so you should be able to find solutions for pretty much everything.

Using the above code snippet we get the following result:

Figure 2

Before we leave the topic of drawing trees with TikZ, let’s look at the different forms of trees one can draw: trees growing downward (we’ve already seen these), trees growing upward, sideways, and trees where the edges fork down rather than go straight down, or where the edges curl down. There are plenty of possibilities. As the last example, let us look at the traditional fork down:

\begin{tikzpicture}
    \tikzstyle{every node}=[draw,rectangle]

    \node {1}
        [style=edge from parent fork down]
        child { node {2} }
        child {
            node {3}
            child { node {4} }
            child { node {5} }
        }
        child { node {6} }
    ;

\end{tikzpicture}

This requires that you add \usepackage{pgflibrarytikztrees} to your preamble, otherwise the fork down isn’t available. Once you’ve done that, this is the result of compiling the drawing:

Figure 3

There is plenty more to the node aspect of TikZ. Indeed, it can also be used to create graphs quite elegantly, and, naturally, TikZ doesn’t limit itself to just trees and graphs, it’s a quite versatile vector drawing language inside LaTeX. In future posts we’ll look at some more of these features.

Tags: ,

Customising class styles

Tuesday, October 31st, 2006 | LaTeX | No Comments

The basic premise of TeX is that nearly everything can be changed. So, we could change, for instance, the \maketitle command to output a page of fluffy bunnies with your title, name and other info (like \thanks) in a pink box. This will almost guarantee that your paper looks rather unique in your teacher’s pile of papers to grade—we will leave that up to you to decide whether that is a good thing, though.

Since the character @ lies in a special category (I’ll return to categories some other time—they aren’t strictly relevant to understand for the purpose of this post), it is a good choice to use as internal variables, since a user doesn’t accidentally use one. Thus, most internal commands are on the form \@myname.

So, when we write something like

\documentclass{article}

\author{Henrik Stuart}
\title{Brian, the Bunny Slayer}

\begin{document}
\maketitle
\end{document}

We get a fancy first page as seen in this figure:

Plain title page

Not really the thing that’ll catch a child’s fancy (nor most grown-ups for that matter).

Now, what happens when we write \title is that the following command is triggered (the exact details may differ by distribution and version):

\def\title#1{\gdef\@title{#1}}

What this basically does is to globally define the command \@title to contain your argument. In our case, using \@title inside the document would print out Brian, the Bunny Slayer (sans the quotes, if your browser supports them). Likkewise \author globally defines \@author. The difference between \def and \gdef will also be covered at a later time.

So, using our knowledge, we can generate our title in a… ehm… lovely pink box, like this:

\documentclass{article}

\usepackage{tikz,xcolor,pgflibrarysnakes,calc}

\author{Henrik Stuart}
\title{Brian, the Bunny slayer}

\makeatletter
\renewcommand{\maketitle}{
    \newpage

    \noindent
    \begin{tikzpicture}
        \draw[snake=bumps,fill=pink,color=pink]
            (0,0) rectangle (\textwidth,6cm);
        \draw[snake=bumps]
            (0,0) rectangle (\textwidth,6cm);
        \draw (.5\textwidth,4cm) node[baseline]
            {\color{white}\bfseries\Huge\@title};
        \draw (.5\textwidth,2cm) node[baseline]
            {\color{white}\bfseries\itshape\Large\@author};
    \end{tikzpicture}
}

\makeatother

\begin{document}
    \maketitle
\end{document}

which results in the following page:

Plain title page

This is probably very appetising for a 5-year old, but I’m not sure who else would want such a title page.

This, however, is not the primary point of this post—albeit it has taken up considerable space. Imagine that you’re working on your LaTeX document in a somewhat diverse group whose members use different distributions on different operating systems. Then \@author could’ve been \@author, or something entirely different, leading to an error when the other group members try to compute the document.

The \maketitle redefinition is a fairly benign command to modify, but imagine if you had to look up the internal commands for altering the layout of the table of contents, list of figure, chapters, sections, etc. Also imagine that the internals can be changed by a new version, rendering all your old documents obsolete. Thus, it is probably for the best to use a popular document class, as it is likely it will quickly be updated to accomodate a new version (or not need to be modified at all), and you can settle with just updating in one place.

The document class of choice isn’t article, report or book that most tutorials use, but rather memoir, which has been written to limit the amount of packages you need, and to provide a great deal of control over the layout and typography of your document. To use memoir, it has a dense and very useful documentation that I would suggest you pursue. It even contains a very good part on typography that is valuable reading. Most of my future posts will be using memoir, so to get ahead of the game, read and enjoy its manuals (also contained at the above link).

Tags: , ,

Extensible languages

Tuesday, March 28th, 2006 | Academe | No Comments

Yesterday I attended a colloquium where Erik van Wyk from University of Minnesota spoke on techniques and tools for making extensible languages. Now extensible language may sound like a strange concept, but it is a fairly simple idea that lies at heart of this: I want to add this new construct to my language because it may simplify my work. Now that’s a pretty basic motivation for us to do some work, so we don’t have to do so much work.

van Wyk et al. have developed something called Silver that allows them to specify these extensions using attribute grammars, which is a context-free grammar that has been extended with attributes, semantic rules and conditions. He described how they use forwarding in the attribute grammars to get modularity through refinement of the functionality of the extension.

What this means is that at the core level you could write an extension, say to introduce SQL statements directly in your language, you could introduce using connection select name, address from customers where balance > `balance and have it automatically converted to connection.Execute("select name, address from customers where balance > " + balance). This means at the core level your extension is nothing but a macro in the pre-processing sense.

Given your extension at the core level any error reporting, for instance is forwarded, is forwarded to your generated code. This is where the extension refinement comes in, because if you define the appropriate error reporting extensions to your module you could return better errors. And their framework builds further onto this, also making syntax- and control-flow analysis available using two temporal logics, CTL and LTL-FV. You can read more about temporal logics in Logic in Computer Science by Huth and Ryan.

Everything cannot be bliss, however, as this thing requires that the host language is written with these extensions in mind – that is, it has been written in Silver. van Wyk’s team is working on both a C and Java implementation, but given the sizes of in particular Java, it probably isn’t realistic that they’ll get a full model of Java for this. Another problem is, of course, that writing a full-fledged extension requires the programmer to know about attribute grammars, forwarding, temporal logic and a lot of other nitty gritty things. So, get ready to hire me or someone like me.

On a more realistic note I think the ramifications of having support for this in a language are huge as you can customise your language on the basis of your needs very easily. But I don’t think it will be feasible until the day that these extensions become easier to write. Until then I’m afraid it will remain an academic exercise, but here’s to hoping.

Tags: ,

X-Chat 2 Plugins

Tuesday, November 29th, 2005 | Development | No Comments

X-Chat 2 for Windows had its binary download changed from a free download to a shareware download with a 30 day limit a while ago. This was considered by many as a really bad idea. People thought the idea so mind-bogglingly stupid that they created their own free alternate builds without a trial period. This post is not about the thing that makes a lot of people feel like feeding the X-Chat 2 for Windows maintainer to the Ravenous Bugblatter Beast of Traal. No, not at all. What this post is about, however, is writing plugins for this IRC client. No, that’s not what it’s about either, let me try again. What this post is about, is my mind-bogglingly useless plugin for this IRC client. Yes, that’s better.

The plugin I have created is for controlling Winamp from X-Chat 2. Normal plugins for X-Chat 2 are made in C, but I have made a plugin in C++. The source code will illustrate both how to integrate with X-Chat 2 and Winamp using C++.

The plugin will not auto-display what you’re listening to whenever a song in winamp changes, since I find that annoying. In fact this plugin will do nothing at all unless you ask it to. The plugin’s functionality is bound to the WIA command, so to see the help for this thing, just go /help wia. The rest should be fairly self-evident.

I have only tested it on the alternate build I’ve listed above. If it does not work on other builds then try to compile the source on your own. I will not help you with problems with the source, compiling it, your social problems or anything else even remotely related to my X-Chat 2 plugin for controlling Winamp. (You get to figure out how your social problems may or may not be related to that on your own). The plugin is released under the GPL and standard disclaimers are in effect and all that stuff that keeps kind people from sucking (sorry, suing) every last penny out of me. (Not that we have pennies here, but figuratively speaking).

I hope someone, somewhere, sometime, might have some use for this. I haven’t added it to the official plugin repository for a reason. Please, don’t post my plugin there.

Binary files (.zip) – 31.4 kB
Source files (.zip) – 26.8 kB

Tags: ,

WSE, DIME, certificates and large attachments

Sunday, October 16th, 2005 | Development | No Comments

Sometimes technology isn’t really transparent enough, even for us developers. When you do web development with IIS, WSE and ASP.NET you might consider it fairly straightforward to create a webservice that accepts file uploads. I thought so, so off I went coding. Everything went well, the files were being uploaded. Time to test this on production data: 400 Bad Request. Hmm.

Of course, prior to this I have already modified web.config to up the max request length like this:

<httpRuntime maxRequestLength="40000" />

So why is it refusing files with an error 400 as soon as they go beyond about 4096KB? Well, it’s obvious, WSE has a built in limit that you must change as well! (In case my sarcasm isn’t showing, it was there. Trust me.)

<microsoft.web.services2>
  <messaging>
    <maxRequestLength>1024</maxRequestLength>

  </messaging>
</microsoft.web.services2>

This example is taken directly from the WSE documentation for the maxRequestLength. Also, you must remember to add the configuration section extension definition for WSE as well – see the documentation link for how to do this.

Of course, the story doesn’t end here. That would be too easy, because the file upload still has a tendency to fail. Hmm. What if we try to sync the value between httpRuntime’s maxRequestLength and WSE2′s maxRequestLength? Bonus! So, knowing that these two have to be identical for everything to go well it seems a bit… ridiculous to have to require the WSE2 field instead of WSE2 just using the httpRuntime value for the maximum request length. I’m sure there’s a brilliant reason for not doing this, however, that someone at Microsoft may know, but one could at least have it be equal to httpRuntime’s maxRequestLength, no? pretty please? Ah well. I’m sure I’m not the last to run into this problem.

So, now we have taken care of large attachments. Let’s add a bit of security so we can safely validate the sender of these large attachments. Stage left enter X.509 and SSL certificates. Stage right enter more troubles, a lot more troubles. So let’s look at a fresh start of IIS and the client, let’s upload a big file, let’s say 20 MB: 413: Request Entity too Large. I will have to be frank, this surprised me. How can the request be too large on HTTPS with client certificates when it isn’t too large on HTTPS without client certificates or on HTTP?

My science background teaches me to experiment in this case, so let’s try it first with a small attachment, say 4 KB, and then let’s try it with a big attachment, say 20 MB: 200 OK. Hmm. Not only does this seem to indicate a bug in IIS6 (which was the IIS I was working against), but it seems to indicate that there is some non-trivial state sharing going on between disparate connects from the same client. Unfortunately I haven’t had time to work more on this problem, but if I ever get around to fixing it I’ll make an update about it. For now I have just created a system that takes a temporary “session” variable that is fetched using a certificate call and then the file is uploading using this without certificate. Seems to work.

Gotta love obvious, transparent technology.

Tags:

« Previous Entries