Defence-in-depth for data-base backed websites: Roles

Role-based access control has been hugely influential in how we do authorization. So much that it's almost difficult to find an application that makes authorization decisions for users but does not have a concept of roles. Thus, a complete solution for doing application-level authorization decisions in the database must support application-level roles.

There are two major takes on how roles should be used. On one hand, we have what I'll call big roles, like User, Administrator, Support, and so on. Users usually have a single role. On the other hand, we have small roles, like the ones in Solaris' RBAC: Printer Management or File System Security, and so on, each letting users run a handful of privileged commands. Users usually have a whole bunch of roles, and get the permissions of the union of the permissions of the roles.

In Postgresql, there is support for role-based access control. Users have roles, and roles have permissions. We've used it when creating users in the procedure, which among other things does something like CREATE USER db_username WITH PASSWORD password IN ROLE kroll_role_user. Permissions are then given to the role kroll_role_user, and not to individual users. We also use the search path functionality to ensure that when users ask for a named table, they get a similarly named view in the schema we set up for them.

These two things, database roles and search paths, can be used to implement application-level big roles. By giving different classes of users different database roles, and creating view schemas that match what that role is supposed to be permitted, we can do things like allowing a moderator to set the sticky field of a row in the threads table, while still restricting the view used by regular users to reading threads and inserting new threads with sticky set to false.

If we modify the application to play along, we can give users access to several roles, and by prefixing table names with the schema for a role, the application can specify what authority it is asserting for each operation. That way, the user can operate under the rules of one role by default, but escalating when doing specific operations. A bit like sudo.

So what about small roles? I haven't studied it closely yet, but I believe that they could for the most part be implemented reasonably cleanly using WHERE clauses on the views. Any authorization rule that depends on information that is stored in the database should be possible to formulate as a WHERE clause (e.g. if we have some authorization matrix that the application already uses, then we can select the row for the current user, the column for the current operation, and check that the operation is permitted).

What we get from the database can be seen as data-level permissions, and schema-level permissions. By data-level, I mean that it operates on a row-by-row basis, where we can say that even if a user can sometimes be permitted to update a row in a table, a particular row may not be permitted (e.g. users can edit rows in the posts table if and only if they are specified in the author column). The schema-level permissions are things like allowing users to read from users, but not write. I believe that schema-level permissions match big roles in the application, and data-level matches small roles, but saying anything definitely on this will require studies of real-world role usage in web applications.

There may be situations where you want to combine multiple schema-level roles (i.e. when they do not match the big role idea directly), and you cannot have users select one at login, nor have the application escalate. One example could be if you have one role for letting customer service representatives see details about the specific issues that they handle and one role for giving access to summaries of entire categories of issues for statistics generation, and then have a page for displaying summary information about a specific issue. In that case you probably can't decide which schema to use beforehand. In these cases, combination roles can be created, which give the permissions of both roles. In the general case, this is not feasible since the number of roles combining two roles would be the square of the number of roles, and there could in principle be a need for any combination of roles, leading to O(nⁿ) combination roles. In practice, it's more likely that it's one or two roles (remember, this is schema-level roles we're talking about here) that need to be combined with ordinary roles. In that case, combination roles should be possible to use.

Combination roles can easily be implemented by having the search path for users with combination roles specify first the combination role, and then one of the ordinary ones. That way, if the ordinary role has sufficient rules for a view, then the combination role schema can just omit the view. For views like the one in the example above, a simple union between the views of the ordinary roles and a rule for inserting/updating etc via the corresponding view in the schema of one of the ordinary roles should suffice. It's only when both roles can modify the view and it's not clear from the context of the application which authority the user is asserting when doing the update that the combination role gets complicated. I don't see this as a real-world problem, but more experimentation will tell.

This concludes the implementation part of the series. Next up will be a post on unsolved problems, and performance test results.

Release of zoom-desktop

I've just made a new release of zoom-desktop and the applications there. Notably the tailing-application 'Svansprogram' have been updated.
Check it out, comments are more than welcome. Please write bug reports or feature requests on the issue tracker.
code.google.com/p/zoom-desktop

JavaOne 2010

How to make JavaOne suck?
Let Oracle host it.

Defence-in-depth for data-base backed websites: Writing

Writing though views seems to be quite different in different database servers. In Postgresql, it's done using something they call rules. Rules rewrite the queries early on, before they are sent off to the planner. Views are implemented as rules, so we actually already used them in the previous post, even though it didn't show.

If we have a table for forum threads like this:

CREATE TABLE impl.threads
(
  id serial not null,
  forum integer not null,
  locked integer not null default 0,
  sticky integer not null default 0,
  CONSTRAINT pk_threads PRIMARY KEY (id),
  CONSTRAINT fk_threads_forum FOREIGN KEY ("forum")
      REFERENCES impl.fora (id) ON DELETE CASCADE
);

and we want users to be able to start new threads, but not to be able to specify the locked or sticky values, we can create a rule on the view like this:

CREATE OR REPLACE RULE posts_insert AS
ON INSERT TO kroll_user.threads
DO INSTEAD
INSERT INTO impl.threads (forum, locked, sticky) VALUES (NEW.forum, 0, 0);

For the private messages view, we can set the sender to the current user, regardless of what the user tried:

create or replace rule messages_insert as
on insert to kroll_user.messages do instead
insert into impl.messages ("to", "from", posted, subject, text)
values (
  NEW."to", kroll_user.get_current_app_user(), NEW.posted,
  NEW.subject, NEW.text
);

Conditionals get a bit trickier. Posts should only be permitted to threads that are not locked. An insert to a locked thread should be ignored. Due to a limitation in Postgresql, it's impossible for it to figure out that if it shouldn't do anything then it should do nothing, so we have to explicitly tell it:

CREATE VIEW kroll_user.posts as select * from impl.posts;

grant select, insert, update on kroll_user.posts to kroll_role_user;

create or replace rule posts_insert as
on insert to kroll_user.posts
WHERE (select locked from impl.threads where threads.id=NEW.thread)<>1
DO ALSO
insert into impl.posts (thread, author, subject, body, created)
values (
  NEW.thread, kroll_user.get_current_app_user(), NEW.subject,
  NEW.body, now()
);

create or replace rule posts_insert_default as
on insert to kroll_user.posts
DO INSTEAD NOTHING;

Postgresql runs all rules that have matching WHERE clauses (and if there is no WHERE, then the rule always matches), so for a post to a locked thread, it (like the goggles) does NOTHING, while for a post to an unlocked thread, it both inserts the row and does NOTHING.

Updates are handled almost identically:

create or replace rule posts_update as
ON UPDATE TO kroll_user.posts
WHERE (
  select locked from impl.threads
  where threads.id=(select thread from impl.posts where id = OLD.id)
)<>1
DO ALSO
UPDATE impl.posts
SET subject=NEW.subject, body=NEW.body, edited=now()
WHERE id=NEW.id and author=kroll_user.get_current_app_user();

Writing to sequences can be done in a manner similar to how we did reading: by virtualizing the accessor functions:

create function kroll_user.nextval_threads_id_seq() returns bigint as
'select pg_catalog.nextval(''impl.threads_id_seq'');'
language sql security definer;
  
/* ... */
  
create function kroll_user.nextval(unknown) returns bigint as
'select case
    when CAST($1 as text)=''messages_id_seq''
    then kroll_user.nextval_messages_id_seq()
    when CAST($1 as text)=''posts_id_seq''
    then kroll_user.nextval_posts_id_seq()
    when CAST($1 as text)=''threads_id_seq''
    then kroll_user.nextval_threads_id_seq() 
    else pg_catalog.nextval(CAST($1 as text))
  end;'
language sql;

As stated in the beginning, this is how things work in Postgresql, and other database servers will require things to be done in different ways. For Oracle, MS-SQL, and DB2, the views are updatable automatically, without any extra rules. In some cases (like with the locked and sticky columns), you may have to use triggers to make certain parts non-writeable.

Next post will move back into vendor-neutral theory again. I'll discuss role-based access control and how the database can get involved in enforcing application roles.

Defence-in-depth for data-base backed websites: Reading

Now that we can create users and log them in, let's try to let them read some data. The actual tables are locked away in the impl schema to which regular users have no access. Selected parts of the tables can be made available though views. As we saw in the introduction, a table containing private messages between users can be exposed as a view that selects only the messages to or from the current user like so:

CREATE VIEW kroll_user.messages AS
SELECT id, "from", "to", posted, subject, text
FROM impl.messages
WHERE "to"=(SELECT id FROM kroll_user.current_app_user)
  OR "from"=(SELECT id FROM kroll_user.current_app_user);

So what's this SELECT id FROM kroll_user.current_app_user? current_app_user simply a view containing the appuser/dbuser mapping for the current user:

CREATE VIEW kroll_user.current_app_user AS
(SELECT appuser as id FROM mapping.users WHERE dbuser=current_user);

current_user is a special SQL-standardized function that is called without the usual parentheses and returns the login name of the current data base user as a string. Or, that's what Postgresql returns. There seems to be some disagreement on whether it should be the login name or the current security context, with Postgresql, DB2, and Firebird in the first camp and MS-SQL, MySQL and Oracle in the second. As long as we don't call it from a privileged stored procedure, that should not matter, however.

If we would like to filter out columns instead of rows, then this can be done by selecting null instead of the data for the column. Row-based and column-based filtering can also be combined. For the users table, I want to hide the email address of all users, except the logged-in user's own address. UNION to the rescue:

CREATE VIEW kroll_user.users AS (
  select id, "name", null as email, moderator from impl.users
  where id <> kroll_user.get_current_app_user()
) UNION (
  select id, "name", email, moderator from impl.users
  where id = kroll_user.get_current_app_user()
);
grant select on kroll_user.users to kroll_role_user;

Setting up read-only views of tables is pretty much straight-forward: decide what cells users should be allowed to see in each table, come up with SELECT statements that pick those, and make them into views.

Sequences are a bit trickier. Postgresql defines a sequnce to be "special single-row table" that can be used only via the functions nextval, currval, and setval. Unfortunately, Postgresql only allows currval to be run on actual sequences, and not on views of sequences. Since the sequences are data and thus stored in the impl schema to which users don't have access, we have to make a little workaround. Instead of virtualizing the sequence, we can virtualize the accessor functions:

create function kroll_user.currval_threads_id_seq() returns bigint as
'select pg_catalog.currval(''impl.threads_id_seq'');'
language sql security definer;

create function kroll_user.currval(unknown) returns bigint as
'select case
  when CAST($1 as text)=''threads_id_seq''
    then kroll_user.currval_threads_id_seq()
  else pg_catalog.currval(CAST($1 as text))
end;'
language sql;

This creates a new function called currval in the user schema (which is the first schema in the users' search path) that checks if the requested sequence is the one we want to virtualize (threads_id_seq). If it is, then we use a privileged access function for that specific sequence (which is a database object that we can explicitly grant access to). If it isn't, then we delegate to the built-in currval (which in Postgesql is stored in the pg_catalog schema). The delegation isn't strictly necessary if users don't have access to non-virtualized sequences, but it ensures we got correct error reporting at least.

That's about all there is to reading and filtering data, which is the majority of what most web apps do, and most of the code is plain old standard SQL. Next up will be writing data, which will lead us in to heavy vendor-specific terrain.

Defence-in-depth for data-base backed websites: Users

When you log your users in all the way to the database, user management of course becomes a bit more involved than when a user is just a row in a table. Users need database accounts, which require passwords. Passwords need to be changeable, and old user accounts should be disabled. We'll look at these things one by one. The SQL here is a bit outside what I'd normally write (it uses stored procedures, for instance), but bear with me - after this post it will mostly be downhill.

When users log in, the web app does not check the password, but instead creates a connection to the database using the user's database username and the password that the user gave to the web app. If the database accepts it, then apparently the user is authentic, and the web app can allow it to attempt any authorized action. But what user name should the web app use when logging the user in? We probably don't want to use the application user name, since users may want to change user names, the web app may want to allow users to have user names that contain characters that the database does not permit in its user names etc. One solution is to use a mapping table that maps application user identities to the corresponding database user names, and do a translation when logging in. I put my mapping in a separate schema from the normal tables (which I keep in impl), since it's not strictly part of the application data, but only relates to the authentication mechanism.

CREATE SCHEMA mapping; 

CREATE TABLE mapping.users
(
  dbuser text primary key,
  appuser int unique
);

But how can we look things up in the database before we log the user in? We don't have the One Big Application User any more, but we can have specialized user accounts with fixed passwords known by the application as long as they are locked down to specific operations.

CREATE USER kroll_user_login WITH PASSWORD 'asdf';
CREATE SCHEMA kroll_login;
GRANT USAGE ON SCHEMA kroll_login to kroll_user_login;
ALTER USER kroll_user_login SET SEARCH_PATH TO kroll_login;

CREATE or replace FUNCTION
kroll_login.get_dbuser_by_appuser (app_username text)
RETURNS text AS $$
DECLARE
  db_username text;
BEGIN
  db_username := (
    select dbuser from mapping.users
    where appuser=(select id from impl.users where "name"=$1)
  );
  return db_username;
END;
$$ language plpgsql SECURITY DEFINER;

GRANT EXECUTE ON FUNCTION kroll_login.get_dbuser_by_appuser(text)
TO kroll_user_login;

If an attacker would be able to seize control of a connection logged in as kroll_user_login, then the attacker can look up database user names all day long, but damage is limited to that.

The application code for logging the user in thus becomes:

1. Log in as kroll_user_login.
   
2. Run SELECT * FROM get_dbuser_by_appuser(?) with the username provided by the user.
   
3. Log in with the returned user name and the password that the user gave.
   
4. Create a session for the user, and store the connection as a session attribute.
   

So what about enrollment? We'd need to come up with a name for the database user, create it, create an application user, and set up the mapping between them. This can be done similarly to logging users in: a stored procedure and a special database user to run it:

CREATE USER kroll_user_signup WITH PASSWORD 'asdf';
CREATE SCHEMA kroll_signup;
GRANT USAGE ON SCHEMA kroll_signup
TO kroll_user_signup;
ALTER USER kroll_user_signup SET SEARCH_PATH TO kroll_signup;

CREATE SEQUENCE kroll_signup.create_user_seq;
GRANT SELECT, UPDATE on kroll_signup.create_user_seq TO kroll_user_signup;

CREATE or replace FUNCTION
kroll_signup.create_user (app_username text, password text, email text)
RETURNS void AS $$
DECLARE
  db_username text;
BEGIN
  db_username := 'kroll_user_' || nextval('create_user_seq');
  execute 'CREATE USER ' || db_username ||
         ' WITH PASSWORD ' || quote_literal(password) ||
         ' IN ROLE kroll_role_user';
  execute 'GRANT USAGE ON SCHEMA kroll_user TO ' || db_username;
  execute 'ALTER USER ' || db_username ||
    ' SET SEARCH_PATH TO kroll_user';
  INSERT INTO impl.users ("name", email)
    VALUES (app_username, quote_literal(email));
  INSERT INTO mapping.users (dbuser, appuser)
    VALUES (db_username, (select id from impl.users where "name"=app_username));
END;
$$ language plpgsql SECURITY DEFINER;

GRANT EXECUTE ON FUNCTION kroll_signup.create_user(text,text,text)
TO kroll_user_signup;

Calling kroll_signup.create_user creates a database user named kroll_user_n that has access only to the kroll_user schema. A row is inserted into the application's users table, and a row mapping between the two identities is added to the mapping.users table.

The kroll_user_signup user is created without the CREATEROLE option, since it is not this user that creates the new user accounts, but the stored procedure, which is running with SECURITY DEFINER. That is: when running the procedure, the permissions are those of the administrator who ran the setup scripts.

As you can see from the code above, all users share a single schema. We are thus not doing much in the database per user in addition to what the application needs when implemented using a single shared login. Database users are on a per-database level though, so prefixing them with the application name is probably a good idea if you want to share a single database instance between many applications.

Changing passwords is a bit different. The usual protocol is that the user specifies the current password, and the new password twice. If the provided current password matches the login password and the two new passwords are the same, then the login password is changed to the new password. The application can compare the two new passwords, but it cannot directly compare the current password with the login password, since login passwords are now only handled by the database. This can be solved by having the application create a new connection to the database using the user's database user name and the provided password. If that succeeds, then the password must have been correct, and we can update the login password to the new password. In Java, this would look something like the following (error handling omitted):

Connection normal_connection=Util.getConnection(request);
PreparedStatement ps=normal_connection.prepareStatement(
  "select current_user"
);
ResultSet rs=ps.executeQuery();
String db_username=rs.getString(1);
Connection special_connection=createConnection(username, old_password);
PreparedStatement ps=special_connection.prepareStatement(
    "ALTER ROLE " + db_username + " WITH PASSWORD '" + new_password + "'"
);
ps.executeUpdate();

Decommissioning, finally, is a complex topic on the application side. What information about the user should be removed? Should anything be removed? For the forum I wrote, I decided to just keep all the application data. The only thing that is removed is the ability log in, that is: the database user and the mapping. Again, a stored procedure and a dedicated database user are used:

CREATE USER kroll_user_remove WITH PASSWORD 'asdf' CREATEROLE;
CREATE SCHEMA kroll_remove;
GRANT USAGE ON SCHEMA kroll_remove TO kroll_user_remove;
ALTER USER kroll_user_remove SET SEARCH_PATH TO kroll_remove;

CREATE or replace FUNCTION
kroll_remove.remove_db_user (app_username integer)
RETURNS void AS $$
DECLARE
  db_username text;
BEGIN
  select dbuser into db_username from mapping.users where appuser=$1;
  delete from mapping.users where appuser=$1;
  execute 'REVOKE USAGE ON SCHEMA kroll_user FROM ' || db_username;
  execute 'DROP USER ' || db_username;
END;
$$ language plpgsql SECURITY DEFINER;

GRANT EXECUTE ON FUNCTION kroll_remove.remove_db_user(integer)
TO kroll_user_remove;

This was how user administration can be done when the application users are also database users. Next up will be reading and filtering application data.

layout animation in android XML

I am currently working on an app that lists issues for projects hosted at code.google.com. I really should get to grips with the google-api-java-client since the 'old' gdata client does not support Android but that is for another blog entry.

Instead of actually communicating with the server I have been spending time on 9-patch images, styles and animations. See the thing is I installed this cool app from Android Market that lists gigs at local club Debaser. It had a really fine ListView where the entries flies in from the right. Really nifty and I already knew there is a tween animation package in Android (I mean they have Romain Guy working there).

So I wrote a small translation animation like this

<translate
 android="http://schemas.android.com/apk/res/android"
 interpolator="@android:anim/bounce_interpolator"
 duration="300"
 fromxdelta="100%p"
 toxdelta="0%">
</translate>

This file goes into res/anim/rowanimation.xml

So then I added the following to my ListView in the layout XML file android:layoutAnimation="@anim/rowanimation" which of course didn't work. Now the sad thing is that the android documentation has a lot of information on how to define animations in XML and lots of code samples for how to use it from java but I couldn't find how to use animations from XML-declarations.

The error I found in log cat said Unknown layout animation name: translate so I dug into the android source for AnimationUtils and sure enough I could find that it is actually looking for something called layoutAnimation.

I'll spare you the suspense of searching the internets for a solution and just tell you that what you need to do. You need to define two animation files. You should do something like this:

<?xml version="1.0" encoding="utf-8"?>
<layoutAnimation  xmlns:android="http://schemas.android.com/apk/res/android"
 android:delay="10%"
 android:animation="@anim/rowanimation"
>
</layoutAnimation>

This file goes into res/anim/listanimation.xml and as you can see it references the previous animation file. The ListView should point to the android:layoutAnimation="@anim/listanimation"

Then things look cool when the list shows. The ListView will apply the rowanimation for each row, it will wait 10% of the total animation time before applying it to the next row so the effect is staggered down the rows. It looks really neat.

the proper use of 'final' in java

The proper use of the final keyword in java is always.

I set out to write a detailed explanation of why you always should use final but then I found this summary, enough said...

The difference between web and handsets

Having recently started to revive my interest in OpenGL-hacking (has it been 10 years already!) I've been reading up on what has been going on.
A lot it seems, several major versions of OpenGL, shader language, programmable pipelines. My head is still rotating around the Y-axis.
Now the really fun thing is that Android supports OpenGL ES, which handily combines my two interests at the present. Android and Open GL is fun, and it works, you might even say it zooms. But still, there is an uneasy feeling, it has to do with quality control.
The title of this blog posting is in regards to the difference in roll-out speed for a web application and the software in a consumer device.
Thing is, google has made several slip-ups with both the Nexus One and Android.
My N1 has a digitizer that goes haywire sometimes, I loose WiFi connectivity all the time. Oh and then there is another touch screen issue that I really love, the synaptics multi-touch. On occasion (not hard to reproduce) the Nexus One digitizer confuses X1 and X2.
Android 2.2 introduced the Open GL ES 2.0 (and there was much rejoicing) but they messed up royally and forgot to handle VBOs. At least they admitted to it which I think is really, really nice.
But you see where I'm going with this. My HTC Hero recently got updated to Android 2.1 and will probably never be upgraded to 2.2. Phone manufacturers never want to upgrade a phone unless the bad-will is seriously affecting their brand name. There is no money in upgrading a sold phone, simple as that.
Google on the other hand has built their fame and fortune on web-applications. Those can be upgraded several times a day. Release early, release often actually works there.
But that mind-set will not work so good when releasing consumer devices. At least not in the price range of a Nexus One, EVO or HTC Desire.
Anyway, I still think that Android is a success story, if you asked me a year ago I would have said that there is no way google can take a share on the phone market. So I hope that they come up with a good way to release patches to android that the handset manufacturers will bless and prove me wrong again.

Post Scriptum: If the VBO fix for GLES 2.0 only appears in Android 3.0 (Gingerbread) we are all royally hosed, the specs for that version does not match even the fanciest phones right now so it will never come to the android phone you hold in your hand right now.

Defence-in-depth for data-base backed websites: Introduction

Many years ago a college of mine (we cal call him Dr. Kroll, because that's what we used to call him) asked over beer a question that stuck with me for a long while.

When we build web applications that talk to databases, we generally let them do any action that they might ever need, at all times. Isn't that a bit reckless? Is there really a need to let the database permit the webserver to access Alice's data when it's processing a request from Bob?

Oracle has been talking about eliminating the One Big Application User (see e.g. Introducing Database Security for Application Developers), and OWASP talks about having the webapp use more than one account to limit what the application can do in their Guide to Authorization, but this is all about limiting what different parts of the code are allowed to do, in essence to the set of all operations that one piece of code could ever need. A more dynamic approach is suggested by Microsoft for application service providers that want to keep data from different customers separate by what they call Multi-Tenant Data Architecture.

In the approach Microsoft describes, the application connects to the database as the principal on whose behalf it's acting, so that the database can take that into account when deciding whether an operation should be authorized. In their example, the principal is the customer, and the filter is there so that users that belong to one customer cannot read data from other customers. I suggest that we extend that model to ordinary users for ordinary web sites.

I've been trying out a way of doing this for a little toy web application, and it seems to work quite well. The way it works is that we create one schema for holding the tables for the application, and another that holds views that are set up so that they structurally look exactly like the tables, but only show data that the application user is allowed to see. This requires one database user per application user, and that the webapp stops using a pool of generic connections, and instead uses one connection per logged-in application user. This is not as bad as it may first sound. It can even be added to an existing application with minimal changes - some changes to signup, login, and connection management, but nothing at all on a per-page basis. I'll start of with an easy example, and then go though different parts of the solution in a few upcoming posts.

The web app I built to test these ideas is a forum. One of the functions that commonly exists in fora is private messages. In my app, the messages are stored in a table that looks like this:

CREATE TABLE impl.messages
(
  id serial not null,
  "from" integer NOT NULL,
  "to" integer NOT NULL,
  posted timestamp without time zone NOT NULL,
  subject character(80),
  "text" text,
  CONSTRAINT pk_pm PRIMARY KEY (id),
  CONSTRAINT fk_from FOREIGN KEY ("from")
      REFERENCES impl.users (id),
  CONSTRAINT fk_to FOREIGN KEY ("to")
      REFERENCES impl.users (id)
);

(I'm using PostgreSQL, by the way. The ideas should be possible to implement in any competent database, but I haven't tested on any other yet).

This table would hold every private message sent by any user to any other user. When the application tries to read a message, however, we should limit it to only reading messages sent to or from the currently logged in user. Thus, in the schema that the application users use, we have a view that enforces that rule:

CREATE VIEW kroll_user.messages AS
SELECT id, "from", "to", posted, subject, text
FROM impl.messages
WHERE "to"=(SELECT id FROM kroll_user.current_app_user) OR "from"=(SELECT id FROM kroll_user.current_app_user);

This gives us a view of the messages table that looks like that the current user is the center of the universe. Every message in the table is either to or from that user. The (SELECT id FROM kroll_user.current_app_user) will be explained in a later post, but for now, let's just assume that it will return the ID of the application user in the application's users table.

So what does this give us? In a perfect webapp, then not much. If every part of the application properly filters the data it reads so that no user can ever get away with something like replacing the ID parameter in the URL to the message display page to that of a message meant for another user, and no parameter is ever pasted into an SQL statement without proper escaping, etc. then wouldn't need this. We also would never have any successful SQL injection attacks or news about stolen database records.

If we apply the principle of least privilege to how the application accesses the database, then we only permit the application to do things that the user on whose behalf it's operating is authorized for. That means that no matter how bad the application is at filtering out requests for other user's data, the database will still not leak anything that the user was not meant to see. As a matter of principles, this is how we should do things. I'm not even sure why we aren't doing it already. As I'll show in the next few posts, it isn't even hard to do.

Convenient improvised classes in Python

When writing a test suite for a little project I'm working on (multi-part blog post forthcoming), I wanted to return an array of objects from a function. Since they were only going to hold some values that would be passed to another function and then forgotten, I didn't feel like writing a proper class for them. The standard way would be to return a tuple or a dictionary, but I prefer the attribute access notation (foo.bar) to indexing (foo["bar"]), especially when sending the object to some other function that doesn't really care to keep track of what's a normal object and what just happens to be a dictionary because I was lazy.

So, what can be done? Turns you you can both have your cake and eat it too.

class improvise(object):
        def __init__(self, **kws):
                for (name, value) in kws.items():
                        setattr(self, name, value)

This little class takes keyword arguments to its constructor, and assigns each key/value pair as attributes on the instance. Use it like this: improvise(from_user=from_user, subject=subject, query=query), and the caller then gets an object that can be used like this: message.subject. Since the class doesn't care about which keyword arguments are used, it can be re-used by every function that wants to return objects without having to declare classes for them.

Chalk up one more for the flexibility of Python. Which, by the way, zooms.

AIDL callbacks in Android

There are several blog posts on the internet about doing this stuff so you probably can find better descriptions elsewhere. Probably by people that actually knows Android coding better than I do but anyway, this is my first attempt at hacking Android. You can find the source here: http://code.google.com/p/tretris/

So for our first Android app we (that is me and my pals) wanted to make a multiplayer Tetris-clone (I'll probably incur the wrath of the Tetris Company by even writing this blog). After a while we finally figured out that we wanted the game logic implemented in a Service that could run in the background on one device and push updates to game clients on the network and of course display something nice on the device hosting the service.

So, the use of XMPP and and the Smack library for network communication is food for another blog post but to put it simply, smack zooms.

Anyway, implementing a Service in Android isn't all that hard. You extend the android.app.Service class and do interesting stuff in onCreate like constructing a Timer.

You start the service from your activity by calling (you guessed it) startService.

Now we have a running service and there are a few ways to talk to a running service, using intents and messages, using the producer/consumer but I wanted to try my hand on method invocation. The nice thing about a service is that it is running in it's own Linux process but this makes it impossible to simply call methods on it. There is an RPC-mechanism in Android invented to handle this and it isn't as hard as writing WSDL/SOAP-stuff but there are some hoops to jump through.

First off: The interface description. You have to create a description of your RPC methods in Android Interface Description Language (AIDL). A poorly documented and strange language that looks a lot like java interfaces. To be fair, the documentation is brief but as far as I can tell correct and it gets you started.

Since I was using the android plug-in for eclipse it happily let me place the aidl-file amongst the java source and generated the stub classes automatically. So if you create a MyService.aidl with all the right package and import and wierd 'in' modifiers here and there you end up with a MyService java interface generated.

Second: we have a description and the tools works. Now, how do you get a GUI-activity to find the service? Well, you bind to it using intents (like so much else in Android). This is where the lack of closures in java (eerr, dalvik... whatever) becomes painful. Binding to a service is an asynchronous thing, so android makes a callback when the service is bound and running. This is a good thing but makes for messy code.

This is basically what we do:

bindService(serviceIntent, serviceConnection, BIND_AUTO_CREATE);

The serviceIntent is the usual kind of Intent object (in our case naming the implementation class directly). The serviceConnection is an instance of a class implementing the ServiceConnection interface (see it is involved just saying it). The BIND_AUTO_CREATE constant tells Android to create and run the service if it isn't already running.

So we end up with something like:

ServiceConnection serviceConnection = new ServiceConnection() {
 public void onServiceDisconnected(ComponentName name) {
  ...
 }

 public void onServiceConnected(ComponentName name, IBinder service) {
  MyService serviceInstance = MyService.Stub.asInterface(service);
  ...
 }
};
Intent serviceIntent = new Intent(this, XXXService.class);
bindService(serviceIntent, serviceConnection, BIND_AUTO_CREATE);

Wait a minute, what is that Stub doing there? Well, this is just one of those conventions the Android developers put there, it reminds me of the javax.rmi.PortableRemoteObject.narrow and you can think of it in those terms, as a strange kind of cast from generated stub code to what you are really after.
This is pretty sweet, some client cruft and we finally get the methods we expose on the service. Or at least a stub object that can call methods on the service.

Third: How to expose methods on the service. The service must implement the public IBinder onBind(Intent intent) and return an IBinder instance but not only that, an IBinder that can be "narrowed" to the generated interface. The place to find such a class is again the Stub-class on the generated MyService interface. What you do is that you create a sub-class of the Stub-class and return an instance of the sub-class (get the 't' right here). Like this in your service:

private MyService.Stub idlStub = new MyService.Stub() {
 public boolean myMethod() throws RemoteException {
  ...
 }
}

So the service has an anonymous subclass of the Stub as a member instance. This anonymous class implements all the methods in your RPC-interface. The anonymous instance also happens to be an IBinder. So what you return from onBind is simpy the idlStub instance.

To recap. The client binds to the service and gets an IBinder back, which it can "narrow" to the interface described in the aidl-file. The service implements a subclass to the generated Stub-class in the interface and returns that subclas for onBind. Easy as 1,2,3, well, actually my head is spinning already :-)

Callbacks: So now we have a GUI-client that can call methods on the service. So let us make the service call back into the GUI-client.

To do that we first define a call back interface, so create a MyCallback.aidl and define the methods that the service should be able to call on the clients. Then add a method on the service for registering clients, the nice thing the Android team did was to make the RPC symmetric, which means that you can use aidl-created interfaces as types for method parameters.

Great, now we have an interface called MyCallbak and a service method called something like registerClient(MyCallback client).

The service side is really easy to implement, there is no Stub voodoo at all, you get an invocation for register client, the method argument is already marshalled and ready to use.

The client side, the one that is to receive the callbacks has some more work to do. It must do the same thing with the Stub-class we did on the service side:

private MyCallback.Stub callback = new MyCallback.Stub() {
 ...
}

That callback member can then be used as argument to the registerClient(callback);

Conclusion: So does the RPC mechanism in android zoom. Well, it works and is reasonably easy to use but until I see some annotations on interfaces and more automagic I wouldn't say it zooms.

Parser Combinators in Python, Part 3

This is the third and final post in the Parser Combinators in Python series.
Part 1
Part 2

The only remaining part is now to get the parsers to look a bit nicer. This will of necessity be a much less objective post, since this is about aesthetically pleasing syntax, which is a never-ending source for fist fights.

Currently, the parser for multiplication expressions looks like this:
mul = Choice(Sequence(Sequence(simple, Exact("*")).apply(left), expr_rec).apply(Mul), simple)

First, let's clean up the Choice and Sequence parts by using operator overloading on the Parser base class, like this:

class Parser(object):
        def __or__(self, other):
                return Choice(self, other)

        def __and__(self, other):
                return Sequence(self, other)

The multiplication parser can now be written as:
mul = ((simple & Exact("*")).apply(left) & expr_rec).apply(Mul) | simple

The same goes for the addition parser. The parenthesis parser can also be simplified, from Sequence(Sequence(Exact("("), expr_rec).apply(right), Exact(")")).apply(left) to ((Exact("(") & expr_rec).apply(right) & Exact(")")).apply(left). One thing that can be noted here is that there are a lot of Sequence combinators with left or right applied. That is, there are a lot of little things in the grammar (like the "(" and ")" in the parenthesis parser) that is necessary for the parsing but that we don't really care about in the AST. Let's add some syntax to get rid of them. I'll abuse the shift operators for sequences where on ly one result is used, and I'll make them be arrows pointing to the interesting part. That is, A >> B means "parse A, then parse B. Throw away the result from A, and return only the result from B". The additions to the Parser class are:

        def __lshift__(self, other):
                return Sequence(self, other, False, left)

        def __rshift__(self, other):
                return Sequence(self, other, False, right)

The parsers can now be written as:

expr_rec=Recurse()
number = RegEx("0|([1-9][0-9]*)").apply(Number)
paren = Exact("(") >> expr_rec << Exact(")")
simple = number | paren
mul = (simple << Exact("*") & expr_rec).apply(Mul) | simple
add = (mul << Exact("+") & expr_rec).apply(Add) | mul
expr = add
expr_rec.set(expr)

The two words that stick out here are apply and Exact. Let's get rid of Exact by special-casing strings in the operators, wrapping the other argument in an Exact parser as necessary:

        def __or__(self, other):
                if other.__class__==types.StringType:
                        return Choice(self, Exact(other))
                else:
                        return Choice(self, other)
        def __and__(self, other):
                if other.__class__==types.StringType:
                        return Sequence(self, Exact(other))
                else:
                        return Sequence(self, other)
        def __lshift__(self, other):
                if other.__class__==types.StringType:
                        return Sequence(self, Exact(other), False, left)
                else:
                        return Sequence(self, other, False, left)
        def __rshift__(self, other):
                if other.__class__==types.StringType:
                        return Sequence(self, Exact(other), False, right)
                else:
                        return Sequence(self, other, False, right)

Since the strings can sometimes be to the left of the operator, we need right-hand versions of the operators as well. I'll just show one, since they are all on the same form.

        def __rlshift__(self, other):
                if other.__class__==types.StringType:
                        return Sequence(Exact(other), self, False, left)
                else:
                        return Sequence(other, self, False, left)

The parsers are now down to

expr_rec=Recurse()
number = RegEx("0|([1-9][0-9]*)").apply(Number)
paren = "(" >> expr_rec << ")"
simple = number | paren
mul = (simple << "*" & expr_rec).apply(Mul) | simple
add = (mul << "+" & expr_rec).apply(Add) | mul
expr = add
expr_rec.set(expr)

Which is pretty sweet if you'd ask me. In languages that let you invent new operators, you could avoid overloading "and" etc. with new meaning, and also have something nice for apply. If we'd abuse the == operator for this, we'd get

expr_rec=Recurse()
number = RegEx("0|([1-9][0-9]*)")   == Number
paren = "(" >> expr_rec << ")"
simple = number | paren
mul_op = simple << "*" & expr_rec   == Mul
mul = mul_op | simple
add_op = mul << "+" & expr_rec      == Add
add = add_op | mul
expr = add
expr_rec.set(expr)

This might arguably look better (the AST node creation really stands out), but is just too wrong for my taste.

So, we've come to road's end here. There are limits to how close you get get Python to BNF. Still, you can come close enough to have parsers that look a fair bit like their grammars, and that also are reasonably efficient. We also get the side benefit of being able to handle ambiguous grammars. In conclusion: the next time you write a parser, take a look at your friendly neighborhood parser combinator library. For Java, check out JParsec. For Python, there's PyParsing. There's implementations for most other languages as well. Enjoy!

SCons, half a year later

It's hard to believe, but it's already been half a year since I started using SCons for real. Seems like a good time to follow it up.

SCons is still very impressive. There are so many things you can do with a real language in the build script that there's no way I'll go back given a choice. Just today, I was writing a little test case for a Cygwin bug where large executables would crash. To test where the limit way, I created a little C file like this

char BLOAT_NAME[]={
#include "bloat.h"
};

with an entirely uninteresting bloat.h containing one million numbers with commas between them. Then, a SConstruct like this to build and link:

objects=[]
for i in range(100):
  objects.append(StaticObject(
    source="bloat.c",
    target="bloat_%d.o" % i,
    CFLAGS="-DBLOAT_NAME=g_bloat_%d" % i
  ))
Program(target="bloat.exe", source=objects + ["main.c"])

Et voila, a hundred object files were built from that one source file. With Make (even GNU Make), I don't know how to do it without depending on things like calling seq from a $(shell) and other icky platform-dependent stuff. Silly little example, but still.

A more serious use is in my big project (a half-secret reimplementation of the important parts of the system we're working on, which gives me 10 seconds edit-compile-debug cycles instead of 15 minutes), I wrote a little parser in Python for the build configuration files we have, and call that from my SConstruct. I loop over the list of source files and options that the parser produces, and add the corresponding nodes to the construction environment (i.e. I put StaticObjects in a list and then pass the list to Program like in the trivial example above). Works perfectly!

In a different side project, I also do multi-stage building, where I first build a tool that generates C code, and then build the generated code. The tool is wrapped in a Builder, and the source files that are generated get dependencies on the tool binary, so everything runs in the correct order.

That said, SCons does have some shortcomings. The biggest one is lack of detailed user documentation. There is a user guide that gets you started on simple projects, but when it comes to the details of the provided builders, or exactly how SCons interacts with user-defined builders, the manual is silent. The only other documentation there is is the API reference, but it's very shallow, and you're better of reading the source. But that's of course not a proper solution, since the code only tells you what happens to work at the moment, and not what you can rely on for the future.

Another problem is release engineering. Until recently, there were snapshots from the source control, and there were releases that happened out of the blue once every year or so, with barely any maintenance done. Now, they seem to have changed a little, as there is an alpha version of 2.0 out. Hopefully, they will sort things out.

So, in conclusion: SCons still zooms. It zooms enough to get this die-hard Make fan convert. Trust me, I'm picky about build systems. Really picky. SCons is the first system I've used that is actually better than Make. It is a proper build system that tracks dependencies and all that. Yet it's dead easy to start using. You should definitely use it.

Parser Combinators in Python, Part 2

This is part two of a three-part series on Parser Combinators in Python

• Part 1
• Part 3

My earlier blog post about parser combinators in Python ended with a real cliffhanger. How can the results be made into an AST instead of a list of tokens? What about the promised BNF-like syntax when building parsers? The arithmetic expression parser used as an example was quite far from that goal. Fear not, I'm back to solve at least the first of those two mysteries in this post.
How can we get a more useful result? Currently, all the parsers return lists of tokens (plain strings, actually), and Sequence and Choice concatenate lists. Ideally, we'd like something like a tree of AST elements, some representing operators, and some representing numbers.
So some parsers will return tokens or other objects representing some kind of terminal symbol, and some will return some kind of structures. The user will likely want to decide what kind of objects are used for the different terminals and which structures are used to combine them, and what parts should be used and what should be ignored. Let's add support for having the parsers apply a user-defined function to the parse result to the Parser base class:

class Parser(object):
        def apply(self, f):
                self.f=f
                return self

...and then add calls to self.f to all parse methods. For Exact it becomes:

def id(x):
        return x

class Exact(Parser):
        def __init__(self, text, f=id):
                Parser.__init__(self)
                self.text=text
                self.f=f

        def parse(self, s, pos):
                if s.startswith(self.text, pos):
                        yield (self.f(self.text), pos+len(self.text))

The user can now write Exact("Hej").apply(SwedishToEnglish), which will return "Hi" given a suitable SwedishToEnglish implementation. RegEx is similarly simple:

class RegEx(Parser):
        def __init__(self, to_match, f=id):
                Parser.__init__(self)
                self.re=re.compile(to_match)
                self.f=f
        def parse(self, s, pos):
                m=self.re.match(s, pos)
                if m:
                        yield (self.f(m.group(0)), m.end())

This allows things like RegEx("\\d+").apply(string.atoi), which is highly useful.
For Choice, it's also simple: just yield what parser A returned with self.f applied, then do the same for parser B:

class Choice(Parser):
        def __init__(self, a, b, f=id):
                Parser.__init__(self)
                self.a=a
                self.b=b
                self.f=f

        def parse(self, s, pos):
                for (a_result, a_pos) in self.a.parse(s, pos):
                        yield (self.f(a_result), a_pos)
                for (b_result, b_pos) in self.b.parse(s, pos):
                        yield (self.f(b_result), b_pos)

So what about Sequence? Since parser functions now return something user-defined as the result instead of a list of tokens, we cannot concatenate the results of parser A and parser B. The Sequence parser combinator is the one that will be used to build structures (e.g. number A followed by operator O, followed by number B becomes a structure saying that operator O should be applied to number A and number B). We're just adding a default here, since the user will override this for all interesting structures. So let's use the simplest possible structure as a default: the tuple.

def pair(a, b):
        return (a,b)

class Sequence(Parser):
        whitespace=re.compile("[ \\t\\n]+")
        def __init__(self, a, b, keep_whitespace=False, f=pair):
                Parser.__init__(self)
                self.a=a
                self.b=b
                self.keep_whitespace=keep_whitespace
                self.f=f

        def parse(self, s, pos):
                for (a_result, a_pos) in self.a.parse(s, pos):
                        if not self.keep_whitespace:
                                m=Sequence.whitespace.match(s, a_pos)
                                if m:
                                        a_pos=m.end()
                        for (b_result, b_pos) in self.b.parse(s, a_pos):
                                yield (self.f(a_result, b_result), b_pos)

I leave the function application changes to the other parsers as an exercise for the reader.
Now, let's use this in the example parser. As I'm sure you all noticed, there was a fault in the operator precedence in the previous post: addition bound harder than multiplication. This is fixed now. I've also added some classes for holding the AST, and they also have an eval method to evaluate the subexpression they represent. The example parser thus becomes:

def left(a, b):
        return a

def right(a, b):
        return b

class Add(object):
        def __init__(self, a, b):
                self.a=a
                self.b=b
        def eval(self):
                return self.a.eval() + self.b.eval()
        def __repr__(self):
                return "Add<%s,%s>" % (self.a, self.b)

class Mul(object):
        def __init__(self, a, b):
                self.a=a
                self.b=b
        def eval(self):
                return self.a.eval() * self.b.eval()
        def __repr__(self):
                return "Mul<%s,%s>" % (self.a, self.b)

class Number(object):
        def __init__(self, s):
                self.n=int(s)
        def eval(self):
                return self.n
        def __repr__(self):
                return str(self.n)

expr_rec=Recurse()
number = RegEx("0|([1-9][0-9]*)").apply(Number)
paren = Sequence(Sequence(Exact("("), expr_rec).apply(right), Exact(")")).apply(left)
simple = Choice(number, paren)
mul = Choice(Sequence(Sequence(simple, Exact("*")).apply(left), expr_rec).apply(Mul), simple)
add = Choice(Sequence(Sequence(mul, Exact("+")).apply(left), expr_rec).apply(Add), mul)
expr = add
expr_rec.set(expr)

s="1  +2\t*(4+3*2 )"
for (result,pos) in expr.parse(s, 0):
        print "Using the first %d characters" % pos
        print s[:pos]
        print result
        print result.eval()

Which, as expected, produces the following results:

Using the first 15 characters
1  +2 *(4+3*2 )
Add<1,Mul<2,Add<4,Mul<3,2>>>>
21
Using the first 5 characters
1  +2
Add<1,2>
3
Using the first 1 characters
1
1
1

That's all for this time. In the next, and final, episode, we'll take a look at how to make the parser look pretty by abusing operator overloading.

Random changes

Note to self: if random changes make a problem appear or disappear, maybe the operative word is "random", and not "changes".

Parser Combinators in Python

This is part one of a three-part series on Parser Combinators in Python

• Part 2
• Part 3

In an earlier post, I mentioned Parser Combinators and that you should use them. In this post, I will explain a bit what they are and how they work. In actual code, I suggest you use a ready-made library like PyParsing or JParsec, but it's nevertheless useful to know how they work.
For some reason, almost every single parsing tool ever written takes as input a file in some strange mixture of a domain-specific language and code snippets in the language you actually want to use, and generates a new file that holds a parsing function. Since I usually do not write parsers, and the domain-specific languages are invariably cryptic, I tend not to write parsers using those tools. I'm sure they work very well if you take the time to learn them, but for those of us only writing a non-trivial parser every other year or so, it doesn't make much sense.
There are alternatives, though. Recursive descent parsers, where you have a bunch of functions representing each rule, and have the functions calling each other like in the below example, works but are a bit tedious to write:

class Term(Parser):
        term_re=re.compile("0|([1-9][0-9]*)")
        def __init__(self, input):
                input.save_mark()
                m=Term.term_re.match(input.buffer())
                if m:
                        input.discard_mark()
                        self.term=m.group(0)
                        input.consume(m.end())
                else:
                        input.restore_mark()
                        raise ParseError()
class Add(Parser):
        def __init__(self, input):
                input.save_mark()
                try:
                        self.term_a=Term(input)
                        self.op=AddOperator(input)
                        self.term_b=Term(input)
                        input.discard_mark()
                except ParseError as e:
                        input.restore_mark()
                        raise e

Back-tracking is here implemented using exceptions and a class that can handle a number of restore points in a string.
A much better way of writing these is to use parser combinators. Parser combinators wrap up the code that combine different simple parsers, so that the previous example can be written to say that an Add is a Term followed by an AddOperator followed by another Term.
There are three things that come together in most parser combinator implementations: letting the parsers return a list of possible parses instead of just a single parse, lazy evaluation, and the use of operator overloading to make the definition of parsers look like BNF. The first feature gives us the ability to handle ambiguous grammars, which can be nice at times, but the main benefit is that when combined with the second, it gives us backtracking more or less for free. The operator overloading is entirely optional, but can make the parsers that are written using the library much easier to read.
So let's get started. Parsers are supposed to return a list of parse results, so a parser for exact matched would look like this:

class Exact(Parser):
        def __init__(self, text):
                self.text=text

        def parse(self, s, pos):
                if s.startswith(self.text, pos):
                        yield ([self.text], pos+len(self.text))

If the input text (s, at position pos) is exactly what we're looking for (self.text), then we yield that result and the position of the next character in the input. We use yield instead of appending to a list and retuning it to get lazy evaluation (which does not give us anything yet, but is essential when we come to alternatives and sequences)
Stepping up in abstraction a small step, we can try optional parsing. Given a parser that parses something, Optional gives us a new parser that parses that something, or nothing at all if that fails. Or actually, since we're generating a list of all possible parses, we yield both the empty parse and the something.

class Optional(Parser):
        def __init__(self, p):
                self.p=p

        def parse(self, s, pos):
                yield ([], pos)
                for t in self.p.parse(s, pos):
                        yield t

Now we can do things like list(Optional(Exact("1")).parse("123")) and get [([], 0), (["1"], 1)]: the two ways of parsing an optional "1" from "123" is nothing with 0 as the next position, or "1" with 1 as the next position.
These higher-order parsers, that is, parser classes that take parser instances as arguments and use them for the actual parsing, are called parser combinators.
Let's try choice next. Either parsing a "1" or parsing a "2" from "123" should be every possible way of parsing "1" from it, followed by every possible way of parsing "2" from it.

class Choice(Parser):
        def __init__(self, a, b):
                self.a=a
                self.b=b

        def parse(self, s, pos):
                for (a_results, a_pos) in self.a.parse(s, pos):
                        yield (a_results, a_pos)
                for (b_results, b_pos) in self.b.parse(s, pos):
                        yield (b_results, b_pos)

It doesn't matter if self.a succeeds or fails its parsing, we yield every possible parse of self.b from the same position anyway. This would normally be very inefficient: if a succeeds, there's no reason to try b. This is where lazy evaluation comes in. Unless someone actually asks for more results after we yielded what self.a yielded, self.b will never be used. Choice(Extact("1"), Exact("2)).parse("123").next() will never call the parse method of Exact("2"). If we use list() to get every single result from the parse, it will be called though. If you ask for only the first parse, the parsing will run until it gets one result. If you ask for every single possible way to parse the input, then the parser will try every single possible way of parsing it.
Next, let's do sequence. For every possible way of using parser A, use parser B where A left off. The result is whatever A produced, followed by whatever B produced, and the ending position is where B left off:

class Sequence(Parser):
        def __init__(self, a, b):
                self.a=a
                self.b=b

        def parse(self, s, pos):
                for (a_results, a_pos) in self.a.parse(s, pos):
                        for (b_results, ab_pos) in self.b.parse(s, a_pos):
                                yield (a_results + b_results, ab_pos)

In many cases, we want to ignore whitespace between any parts of the grammar. This can be done in the Sequence combinator by skipping whitespace after parsing with A, but before parsing with B, like this:

class Sequence(Parser):
        whitespace=re.compile("[ \\t\\n]+")
        def __init__(self, a, b, keep_whitespace=False):
                self.a=a
                self.b=b
                self.keep_whitespace=keep_whitespace

        def parse(self, s, pos):
                for (a_results, a_pos) in self.a.parse(s, pos):
                        if not self.keep_whitespace:
                                m=Sequence.whitespace.match(s, a_pos)
                                if m:
                                        a_pos=m.end()
                        for (b_results, ab_pos) in self.b.parse(s, a_pos):
                                yield (a_results + b_results, ab_pos)

The final part to having support for the BNF operators is something that allows us to match a parser multiple times. This is almost exactly like the Sequence parser, except that parser B is replaced with the combinator itself:

class Many(Parser):
        def __init__(self, p):
                self.p=p

        def parse(self, s, pos):
                yield ([], pos)
                for (p_results, p_pos) in self.p.parse(s, pos):
                        for (self_results, self_pos) in self.parse(s, p_pos):
                                yield (p_results + self_results, self_pos)

For most non-trivial grammars, there will be some rules that refer themselves, either directly or via some other rule. Since Python does not have forward declarators, we can use a little proxy class to solve it:

class Recurse(Parser):
        def set(self, p):
                self.p=p
        def parse(self, s, pos):
                for result in self.p.parse(s, pos):
                        yield result

This way, we can get the parser object in advance, refer to it in a bunch of rules, and then define the real recursively used parser and call the set method on the proxy, and everything will work.
In order to skip writing the boring parts of matching numbers or identifiers using sequences of choices of exact parsers, I usually use a regex parser, like so:

class RegEx(Parser):
        def __init__(self, to_match):
                self.re=re.compile(to_match)
        def parse(self, s, pos):
                m=self.re.match(s, pos)
                if m:
                        yield ([m.group(0)], m.end())

Putting all this together, we can write a parser for simple arithmetic expressions:

expr_rec = Recurse()
number = RegEx("0|([1-9][0-9]*)")
paren = Sequence(Exact("("), Sequence(expr_rec, Exact(")")))
simple = Choice(number, paren)
add = Choice(Sequence(simple, Sequence(Exact("+"), expr_rec)), simple)
mul = Choice(Sequence(add, Sequence(Exact("*"), expr_rec)), add)
expr = mul
expr_rec.set(expr)

There are two problems with this code: the first is that it's pretty hard to read with all the Sequence and Choice calls, and the second is that no AST is built: it's all just returned as a flat list of tokens. Since this post is long enough already, these problems will be solved in the next post.

The most natural of all keys

I sometimes hear, as an argument for using surrogate keys, that there is
no natural key for a table of persons. There is. It's a compound key
consisting of your mother's primary key and a sequence number telling
which of her chldren you are. In SQL:

create table person
(
      parent integer[],
      sequence int,
      name varchar(100),
      primary key (parent, sequence)
);

insert into person (parent, sequence, name) values ({}, 0, 'Lucy');
insert into person (parent, sequence, name) values ({0}, 0, 'Albert');
insert into person (parent, sequence, name) values ({0}, 1, 'Betty');
insert into person (parent, sequence, name) values ({1,0}, 0, 'Zim');

Here, Lucy is the first human ever (she has no human ancestor). Albert
and Betty are her children, and Betty has a son, Zim.

The only problem with this is that the foreign key cannot be
described in SQL. It actually has nothing to do with it being a
self-referencing key, but that the parent and
sequence columns of the referenced row should be
parts of the parent column of the referencing row. Something
like the following: foreign key (parent[1], parent[2:]) references person
(sequence, parent). Unfortunatly, only column names are permitted
in foreign key constranits, not arbitrary expressions. Implementing
the constraint as a CHECK instead is left as an excercise to
the reader.

Const correctnes and callback interfaces in C

From time to time, I use and/or design callback interfaces in C. Usually, the signature of the callback will be similar to

typedef int (*callback)(int some_argument, void* user_data);

and the function that calls the callback is

int do_something_with_callback(int another_argument, callback f, void* user_data);

This is all well and good (as long as the documentation for do_something_with_callback specifies exactly how if will call f). But consider the following example

#include <stdio.h>
int add(int a, void* user_data)
{
  int* b=(int*)user_data;
  return a + (*b);
}

typedef int (*callback)(int some_argument, void* user_data);

int apply_arithmetic_function(int initial_value, callback f, void* user_data)
{
  return f(initial_value, user_data);
}

int main()
{
  int v=1000;
  printf("%d\n", apply_arithmetic_function(123, add, &v));
  return 0;
}

This works, but as you can see, the add function does not write though its user_data pointer. Therefore, in isolation, it could be marked const, which is ususally a good thing. But is int add(int a, const void* user_data) compatible with the callback interface?

At first glance, it would seem like it, since something that takes a const pointer can be passed a non-const pointer (and gcc 4.3.4 with -Wall -Wextra -Werror -std=c99 -pedantic permitts it). But then again: what if the calling convention is different for const and non-const pointers? In a plain function call, it will work, since the compiler sees the signature of the actual function that is being called, but though the function pointer, it does not.

Looking at the (draft) spec, it is not permitted.
6.7.5.3§15 says:

For two function types to be compatible, both shall specify compatible return types. [127]

Moreover, the parameter type lists, if both are present, shall agree in the number of parameters and in use of the ellipsis terminator; corresponding parameters shall have compatible types.

127) If both function types are ‘‘old style’’, parameter types are not compared.

So, all the parameters in the signatures have to be "compatible". What does that mean? 6.7.3§9 says:

For two qualified types to be compatible, both shall have the identically qualified version of a compatible type ...

Ergo, the function signatures are not compatible, and 6.5.2.2§9 says:

If the function [that is to be called] is defined with a type that is not compatible with the type (of the expression) pointed to by the expression that denotes the called function, the behavior is undefined.

Conclusion: be careful with the types of callback functions. Copy-paste verbatim from the declaration, and write a comment at the site of the callback implementations saying that they are supposed to conform to a specific interface and that the parameter declarations may not be modified unless the interface is also changed.