Writing recursive descent parsers is easy, especially in Python (just like everything is easy in Python). But Python defines a low limit on the number of recursive calls that can be made, and recursive descent parsers are prone to exceed this limit. We should thus write our parser without real recursion. Fortunately, Python offers us a way out: Coroutines, introduced in Python 2.5 as per PEP 342. Using coroutines and a simple trampoline function, we can convert every mutually recursive set of functions into a set of coroutines that require constant stack space. Let s say our parser looks like this (tokens being an iterator over characters):

def parse(tokens):
    token = next(tokens)
    if token.isalnum():
        return token
    elif token == '(':
         result = parse(tokens)
         if next(tokens) != ')': raise ...
         return result
    else:
         raise ...

We now apply the following transformations:
return X => yield (X)
parse() => (yield parse()) That is, we yield the value we want to return, and we yield a generator whenever we want to call (using a yield expression). Our rewritten parser reads:

def parse(tokens):
    token = next(tokens)
    if token.isalnum():
        yield token
    elif token == '(':
         result = yield parse(tokens)
         if next(tokens) != ')': raise ...
         return result
    else:
         raise ...

We obviously cannot call that generator like the previous function. What we need to introduce is a trampoline. A trampoline is a function that manages that yielded generators, calls them, and passes their result upwards. It looks like this:

def trampoline(generator):
    """Execute the generator using trampolining. """
    queue = collections.deque()
    def schedule(coroutine, stack=(), value=None):
        def resume():
            if 0:
                global prev
                now = stack_len(stack)
                if now < prev:
                    print("Length", now)
                    prev = -1
                elif prev != -1:
                    prev = now
            result = coroutine.send(value)
            if isinstance(result, types.GeneratorType):     # Normal call
                schedule(result, (coroutine, stack))
            elif isinstance(result, Tail):                  # Tail call (if you want to)
                schedule(result.value, stack)
            elif stack:                                     # Return to parent
                schedule(stack[0], stack[1], result)
            else:                                           # Final Return
                return result
        queue.append(resume)
    schedule(generator)
    result = None
    while queue:
        func = queue.popleft()
        result = func()
    return result

This function is based on the code in PEP 342, the difference being that

• we do not correctly propagate exceptions through the stack, but directly unwind to the caller of the parser (we don t handle exceptions inside our parser generators anyway)
• the code actually compiles (code in PEP used value = coroutine.send(value) which does not work)
• the code returns a value (code in PEP was missing a return in schedule)
• we don t use a class, and allow only one function to be scheduled at once (yes, we could get rid of the queue)
• we allow tail calls [where Tail = namedtuple("Tail", ["result"])] to save some more memory.

For a more generic version of that, you might want to re-add exception passing, but the exceptions will then have long tracebacks, so I m not sure how well they will work if you have deep recursion. Now, the advantage of that is that our parser now requires constant stack space, because the actual real stack is stored in the heap using tuples which are used like singly-linked lists in scheme here. So, the only recursion limit is available memory. A disadvantage of that transformation is that the code will run slightly slower for small inputs that could be handled using a normally recursive parser.
Filed under: Python

You can use a PBO solver to clean up your system from unneeded automatically installed packages. First of all, you convert the system state to PB, and add an optimization function telling it to remove as many automatically installed packages as possible. Then you run this thing through a solver (such as clasp, which seems the fastest solver for PBO instances in the Debian archive) and convert its output to human-readable package names. Code is provided at http://anonscm.debian.org/gitweb/?p=users/jak/cleanup.git, under the MPL 2.0. You need to have python-apt and clasp installed to use it. There is potential minisat+ support, but it s currently a bit broken. To use, run python program_builder.py, and it will tell you which packages are no longer needed on your system. It ignores Suggests, if you want those in, you have to hack the code and replace Recommends by Recommends , Suggests . You can also turn of such dependencies by setting Program.hard_softdeps to False.
Filed under: APT2, Debian, Python

Debian packages commonly use or dependencies of the form a b to mean that a or b should be installed, while preferring option a over b. In general, for resolving an or dependency, we will try all options from the left to the right, preferring the left-most option. We also prefer real packages over virtual ones. If one of the alternatives is already installed we use that.

def solve_or(or):
  best_real = None
  best_virtual = None
  for dep in or:
     for target in dep:
        if target.name == dep.name and best_real is None:
           best_real = target
        if target.name != dep.name and best_virtual is None:
           best_virtual = target        
        if target.is_installed():
          return target
  return best_real if best_real is not None else best_virtual

Now, this way of solving dependencies is slightly problematic. Let us consider a package that depends on: a b, b. APT will likely choose to install a to satisfy the first dependency and b to satisfy the second. I currently have draft code around for a future version of APT that will cause it to later on revert unneeded changes, which means that APT will then only install b . This result closely matches the CUDF solvers and cupt s solver. On the topic of solving algorithms, we also have the problem that optimizing solvers like the ones used with apt-cudf do not respect the order of dependencies, rather choosing to minimise the number of packages installed. This causes such a solver to often do stuff like selecting an sqlite database as backend for some service rather then a larger SQL server, as that installs fewer packages. To make such solvers aware of the implicit preferences, we can introduce a new type of dependency category: Weak conflicts, also known as Recommends-Not. If a package P defines a Recommends-Not dependency against a package Q, then this means that Q should not be installed if P is installed. Now, if we have a dependency like: Depends: a b c we can encode this as: Recommends-Not: c, c, b Causing the solver to prefer a, then b, and then c. This should be representable as a pseudo-boolean optimization problem, as is common for the dependency problem, although I have not looked at that yet it should work by taking the standard representation of conflicts, adding a relaxation variable and then minimising [or maximising] the number of relaxation variables.
Filed under: APT2, Debian, General

In the past days, I looked at various memory allocators in a quest to improve performance in my multi-threaded test cases of a reference counting language runtime / object allocator (a fun project). It turns out the glibc s memory allocator is relatively slow, especially if you do loops that create one element and destroy one element at the same time (for example, map() on a list you no longer use after you passed it to map). To fix this problem, I considered various options. The first option was to add a thread-local cache around malloc(). So whenever we want to free() an object, we place it on a thread-local list instead, and if a malloc() request for an object of that size comes in, we reuse the old object. This fixes the problem with the lists, but experiments shown another problem with the glibc allocator: Allocating many objects without releasing others (let s say appending an element to a functional list). I started testing with tcmalloc instead, and noticed that it was several times faster (reducing run time from 6.75 seconds to 1.33 seconds (5 times faster)). As I do not want to depend on a C++ code base, I decided to write a simple allocator that allocates blocks of memory via mmap(), splits those into objects, and puts the objects on a local free list. That allocator performed faster than tcmalloc(), but was also just a simple test case, and not really useable, due to potential fragmentation problems (and because the code was statically linked in, causing thread-local storage to be considerably faster, as it does not need to call a function on every TLS access, but can rather go through a segment register). I then discovered jemalloc, and tried testing with this. It turned out that jemalloc was even faster than tcmalloc in all test cases, and also required about the same amount of memory as tcmalloc (and slightly more than the custom test code, as that combined reference counting with memory allocator metadata and thus had less meta data overhead). Using jemalloc, the list building test performs in 0.9X seconds now (instead of tcmalloc s 1.33 or glibc s 6.75 seconds), requires 0 major page faults (tcmalloc has 2), and uses 5361472 kb memory (tcmalloc uses 5290240, glibc requires 7866608). Given that jemalloc is written in C, I can only recommend it to everyone in need of a scalable memory allocator. Depending on your workload, it might require less memory than tcmalloc (at least that s the case at Facebook) and is most likely faster than tcmalloc. It also provides tcmalloc-compatible profiling facilities (as Facebook needed them). Furthermore, jemalloc is also the memory allocator used by FreeBSD, and is used by Mozilla projects, and on several Facebook projects, and should thus be relatively stable and useable. All tests were run with 4 threads, on a dual-core laptop with hyper-threading, using (e)glibc 2.13, tcmalloc 2.0, and jemalloc 3.0. The tests may not be representative of real world performance, and do not account for fragmentation. Should I try replacing Python s custom caching of malloc() calls with simply calling jemalloc, and run a few Python benchmarks? Anyone interested in that?
Filed under: General

One thing I thought about today is reference counting in combination with tail calls. Imagine a function like this:

function f(x)   return g(x+1);  

Now consider that x is a reference counted object and that x + 1 creates a new object. The call to g(x + 1) shall be in tail call position. In most reference counted languages, the reference to an argument is owned by the caller. That is, f() owns the reference to x + 1. In that case, the call to g() would no longer be in a tail call position, as we still have to decrease the reference count after g() exits. An alternative would be that the callee owns the reference. This however, will most likely create far more reference count changes than a caller-owns language (increase reference count in caller, decrease reference count in callee). For example, the following function requires an increment before the call to g().

function f1(x)   return g(x);  

Does anyone have any ideas on how to solve the problem of tail calls while avoiding the callee-owns scenario? Something that does not require a (non-reference-counting) garbage collector would be preferably.
Filed under: General

In the language introduced yesterday, mutable parameters play the important role of representing the side effects of actions in the type system and thus ensure referential transparency. One of the questions currently unaddressed is how to handle currying in the presence of mutable parameters. In order to visualise this problem, consider a function

    printLn(mutable IO, String line)

If we bind the the first parameter, what should be the type of the function, and especially important how do we get back the mutable parameter? Consider the partially applied form printLn1:

    printLn1(String line)

The mutability parameter would be lost and we could not do any further I/O (and the curried form would appear as a pure function, so a good compiler would not even emit a call to it) An answer might be to put the thing into the result when currying:

    printLn2(String line) -> mutable IO

But how can we explain this? In the end result, do we maybe have to use a signature like:

    printLn(String, mutable in IO io1, mutable out IO io2)

We could then introduce syntax to call that as

    printLn(string, mutable io)

Where as the mutable io argument basically expands to io and io1 for the first call, and for later calls to io1, io2 , and so on. It can also be easily curried by allowing currying to take place on variables not declared as output parameters. We can then curry the function as:

    printLn3(mutable in IO io1, mutable out IO io2)
    printLn4(mutable out IO io2)

If so, we can rename mutable back to unique and make that easier by introducing the unary operator & for two locations, just like Mercury uses ! for it. We could then write calls looking like this:

    printLn("Hello", &io);
    printLn("Hello", io, io1);

How out parameters are explained is a different topic; we could probably say that an out parameter defines a new variable. Another option is to forbid currying of mutable parameters entirely. This would have the advantage of maintaining the somewhat simple one parameter style. The programming language Clean does not provide any special syntactic sugar for having mutable variables. In Clean, the function gets a unique object and returns a unique object (noted by *). For example, the main entry point in a Clean program (with state) looks like this:

    Start:: *World -> *World

In short, the function Start gets a abstract world passed that is unique and at the end returns a new unique world. In Clean syntax, our example function would most likely have the signature:

    printLn :: String *IO -> *IO

You know have to either maintain one additional variable for the new unique object, which gets a bit complicated with time. On the other hand, you can do function composition on this (if you have a function composition operator that preserves uniqueness when available, as should be possible in Clean):

    printTwoLines :: *IO -> *IO
    printTwoLines = (printLn "World") o (printLn "Hello")

Function composition on mutable things however, does not seem like it is needed often enough in a functional programming language with a C syntax. People might also ask why monads are not used instead. Simon L Peyton Jones and Philip Wadler described monadic I/O in their paper Imperative Functional Programming (http://research.microsoft.com/en-us/um/people/simonpj/papers/imperative.ps.Z) in 1993, and it is used in Haskell (the paper was about the implementation in Haskell anyway), one of the world s most popular and successful functional programming languages. While monadic I/O works for the Haskell crowd, and surely some other people, the use of Monads also limits the expressiveness of code, at least as far as I can tell. At least as soon as you want to combine multiple monads, you will have to start lifting stuff from one monad to another (liftIO and friends), or perform all operations in the IO monad, which prevents obvious optimizations (such as parallelizing the creation of two arrays) in short dependencies between actions are more strict than they have to be. For a functional language targeting imperative programmers, the lifting part seems a bit too complicated. One of the big advantages of monads is that they are much easier to implement, as they do not require extensions to the type system and the Hindley-Milner type inference algorithm used by the cool functional programming languages. If you want uniqueness typing however, you need to modify the algorithm or infer the basic types first and then infer uniqueness in a second pass (as Clean seems to do it).
Filed under: General

Just for you, and this time in the Pythonesque rendering.

module main:
    import std (range)
    import std.io (printf, IO)
    # print the Fahrenheit-Celcius table for fahr = 0, 20, ..., 300
    function main(mutable IO io):
        Int lower = 0    # lower bound
        Int upper = 300  # upper bound
        Int step = 20    # step
        for Int fahr in range(lower, upper, step):
            Double celcius = 5 * (fahr - 32) / 9
            std.io.printf(io, "%3d\t%6.1f\n", fahr, celcius)

It does not really look like it, but this language is purely functional. It represents side effects using unique types. If you declare a mutable parameter, you basically declare a unique input parameter and a unique output parameter. I m also giving you a list implementation

module std.container.list:
    ## The standard singly-linked list type
    type List[E]:
        Nil                     ## empty list
        Node:
            E value             ## current value
            List[E] next        ## remaining list
 

And yes, both languages should be able to be represented using the same abstract syntax tree. The only change is the replacement of the opening curly brace by a colon, the removal of the closing curly bracket and semicolons, the replacement of C-style comments with Python-style comments and the requirement of indentation; oh and the for statement gets a bit lighter as well.
Filed under: General

Just for you:

module main  
    import std (range);
    import std.io (printf, IO);
    /* print the Fahrenheit-Celcius table
        for fahr = 0, 20, ..., 300 */
    function main(mutable IO io)  
        Int lower = 0;   // lower bound
        Int upper = 300; // upper bound
        Int step = 20;   // step
        for (Int fahr in range(lower, upper, step))  
            Double celcius = 5 * (fahr - 32) / 9;
            std.io.printf(io, "%3d\t%6.1f\n", fahr, celcius);
         
     
 

It does not really look like it, but this language is purely functional. It represents side effects using unique types. If you declare a mutable parameter, you basically declare a unique input parameter and a unique output parameter. I m also giving you a list implementation

module std.container.list  
    /** The standard singly-linked list type */
    type List[E]  
        Nil;                    /** empty list */
        Node  
            E value;            /** current value */
            List[E] next;       /** remaining list */
         
     
 

Thus are only excerpts from a document with tens of pages and the reference implementation of the standard library. The incomplete working draft for the language is attached: JAK Programming Language Early Working Draft (28 pages). Update: Fixed the link.
Filed under: General

I have just released version 0.2 RC1 of my hardlink program. Compared to the 0.1.X series, the program has been rewritten in C, as Python was to memory-hungry for people with millions of files. The new program uses almost the same algorithm and has almost completely the same bugs as the old version. The code should be portable to all UNIX-like platforms supporting nftw(). I have tested the code on Debian, FreeBSD 9, and Minix 3.2. For storing path names, it uses a flexible array member on C99 compilers, a zero-length-array on GNU compilers, and a array of length 1 on all other compilers (which should work everywhere as far as I heard). The new version may have slightly different behaviour compared to 0.1.2 when regular expressions are specified on the command-line, as a result of the switch from Python s regular expression engine to PCRE (if compiled with PCRE support, you can also use POSIX extended regular expressions if you like). The code is significantly faster than the old code (in situations where it s not I/O bound), and uses much less memory than the old one. Per file, we now store a <tt>struct stat</tt>, a pointer, an int, a char, and the filename; as well as three pointers for a binary search tree (which uses tsearch()). It should also be compatible to Red Hat s original hardlink tool now command-line-wise, there is at least a -c option now. The history and the name conflict are interesting, but probably nothing for this post. We re even less resistant against changing trees than Fedora s tool (and derived) currently, but should otherwise be better (and far more complicated and feature-packed). And we don t require mmap(), but use fread() instead. There was no real performance difference in testing. And we are not GPL-licensed, but use the MIT/Expat license. The package is currently entering Debian experimental for testing purposes. If you have used hardlink previously, or are just curious, give it try. And the makefile is now compatible with the various BSD makes out there, if that s interesting for you. Link to website: http://jak-linux.org/projects/hardlink/
Filed under: General

Over the last years, I have developed a variety of metapackages for managing the package selections of the systems I administrate. The meta packages are organized like this:

jak-standard

Standard packages for all systems

jak-desktop

Standard packages for all desktop systems (GNOME 3 if possible, otherwise GNOME 2)

jak-printing

Print support

jak-devel

Development packages

jak-machine-<X>

The meta package defining the computer X

Each computer has a jak-machine-X package installed. This package is marked as manually installed, all other packages are marked as automatically installed. The machine packages have the attribute XB-Important: yes set in debian/control. This creates an Important: yes field. This field is not official, but APT recognizes it and does not remove those packages (the same field is set for the APT package by APT when building the cache, as APT should not be removed either by APT). It seems to work a bit like Essential, with the exception that non-installed packages are not installed automatically on dist-upgrade. The meta packages are created using seed files similar to Ubuntu. In contrast to Ubuntu, I m not using germinate to create the packages from the seeds, but a custom dh_germinate_lite that simply takes a seed file and creates the correct substvars. It s faster than germinate and really simplistic. It also does not handle Recommends currently. The whole result can be seen on http://anonscm.debian.org/gitweb/?p=users/jak/jak-meta.git. Maybe that s useful for some people. And if you happen to find some packages in the seeds that are deprecated, please let me know. Oh, and yes, some packages (such as the letterman one) are internal software not publically available yet [letterman is a simple GUI for creating letters using LaTeX]. While I m at it, I also built Ubuntu s version of wine1.2 for i386 squeeze. It can be found in
deb http://people.debian.org/~jak/debian/ squeeze main (it still needs a few changes to be correct though, I ll upload a jak2 build soon). I also built updated sun-java6 packages for my parents (mostly needed due to the plugin, some websites do not work with the IcedTea one), but can t share the binaries due to licensing requirements. I may push out a source repository, though, so others can build those packages themselves. I ll let you know once that s done.
Filed under: Debian, General

Just because Julien did it, I moved my website to almost the same design now. Still using ikiwiki, of course. I m still missing a few things, such as marking the currently active page in the menu, but I hope to get that done as well soon. Go to http://jak-linux.org/ to see it.
Filed under: General

If someone in Germany (or want to send it to Germany [at low costs]) still has (new) Touchpads to sell, I d buy one or two of them at the reduced price (16GB: 99 , 32GB: 129 ), or take them for free. I promise that I will not sell them to others. I m interested in WebOS, in running Debian and/or Ubuntu on those devices (for the extra fun factor), and lend it to family members for surfing, etc. I also take other tablets and smart phones and various kinds of ARM and PowerPC hardware (I guess that s all that s interesting for me) for free, just send me an email if you have some and want to give them to me. This applies to Intel stuff as well, I d really like to get some kind of WeTab/ExoPC, but can t buy one currently (and they re probably to outdated hardware-wise for buying to make sense).
Filed under: Uncategorized

Common licenses for software include the term worldwide . Now, what does worldwide mean? The problem with the term worldwide is that it is ambigous and depending on it s interpretation, violates against DFSG 6 which states: No Discrimination Against Fields of Endeavor . The reason: Space travel. If we take the term worldwide to mean everywhere on earth , the license becomes non-free, as it prohibits the use outside of this planet. Affected by this problem are the patent section of GPL-3, the Apache 2.0 license, the CC licenses, the GFDL, and probably also others. Now what should be used instead? Universal? No, that wouldn t work in case there are multiple ones (while travelling between them (if they exist) could be impossible, it would still be a restriction). The correct team would probably be omniversal meaning everywhere in the omniverse . But really, avoiding locations is probably the best way. In any case, if you have received software from me under a license that uses the term worldwide , you can treat worldwide as everywhere, and are thus free to use it outside of earth (and other planets).
Filed under: General

Yesterday I released version 4 of dh-autoreconf, fixing two bugs, and introducing a new feature: Patching ltmain.sh to make -Wl, as-needed work. For this new feature, run dh_autoreconf with the as-needed option. dh_autoreconf will then patch all ltmain.sh equal to the system one (which should be all ltmain.sh files if libtoolize ran before or via dh_autoreconf). On clean, dh_autoreconf_clean reverses the patch again. So, if your package runs autoreconf, and patches ltmain.sh via a patch you can now do this automatically via dh-autoreconf and be future-proof. The only problem is that this might break once the patch no longer applies to libtool, at which point I need to update the package to include an updated patch. A solution for this problem would be to include the patch in libtool itself, as I proposed in Bug#347650. In case this works well, the option could also become the default which would make things even easier.
Filed under: Debian

Yesterday was my 21st birthday, and I received all Hitchhiker s Guide to the Galaxy novels, the five ones in one book, and the sixth one written by Eoin Colfer in another book. Needless to say, the first book weights more than an N900. I did not read them yet, so now is the perfect chance to do so. Yes, I did not know that 25th is towel day, sorry for that. I also bought a Toshiba AC100 before my birthday, a Tegra 2 based notebook/netbook/ web companion with 1 GHz dual core ARM Cortex A9 chip and 512 MB RAM. It runs Android by default, and had a price of 160 which is low compared to anything else with Cortex A9. It currently runs Ubuntu 11.04 with a specialised kernel 2.6.37 from time to time, without sound and accelerated video (and not functioning HDMI). Mostly waiting for Nvidia to release a new binary blob for the video part (And yes, if you just want to build packages, you can probably get happy without those things). Another thing happening last week is the upload of python-apt 0.8.0 to unstable, marking the beginning (or end) of the API transition I started more than a year ago. Almost all packages not supporting it have proper Breaks in python-apt [most of them already fixed, only 2 packages remaining, one of which is "maintained" (well, not really maintained right now) by me], but there may be some which do not work correctly despite being fixed (or at least thought to be fixed). If you know any other interesting thing I did last week, leave a comment, I wrote enough now. And yes, WordPress wants to write a multiplication sign instead of an x, so I had to use &#120 instead.
Filed under: Debian, General, Ubuntu

I did not write much code or merge much of my prototype code, but some things happened since the last blog post about APT2 specific things in August and I forgot to write about them. First of all, I dropped the GVariant-based cache. The format strings were simply getting ugly long and were not very understandable, performance was just much too slow (needing more than a few nanoseconds for a package lookup is obviously too slow for solving dependency problems); furthermore, building the cache was also slow and complicated because we needed all attributes of an object at once to pass them to GVariant, leading to ugly API. I replaced the GVariant cache with one that can be easily mmap()ed and is described completely in C. It s derived from APT s cache design (but more robust, as it includes the size of the cache and we can thus detect to small files, although that s scheduled for the next ABI break in APT as well), but has fewer duplicate data, and uses arrays where APT uses linked lists. The reason for arrays is simple: They take up less space and can be represented naturally in Python and other languages using array-based lists. The cache also contains a coalesced hash table which does use a linked list, but that one is a bit different, as it is for searching only and not exposed. Everything non-stringy is 64-bit aligned in order to keep things as simple as possible. All integers are fixed size, thus the format is architecture-independent if you fix byte orders. The format is described at http://people.debian.org/~jak/apt2-doc/apt-Cache-Format.html. I stole one more idea from cupt and changed the configuration system to verify types of variables. APT2 s configuration system knows more types than cupt s, though, including regular expressions, directory and filenames (i.e. it does not let you store a value /d/ in a file variable), strings (which store everything), unsigned and signed integers, and boolean options; all of which are checked when parsing files (producing warnings) or command-line options (producing errors). I have also simplified the type world by removing all iterator types except for one, replacing them with get_thing() and n_things() functions in the objects holding the arrays. Makes cool bindings slightly harder, but makes the C API much easier to use from C. Most things expected from a package manager are still missing, but what is there looks good in most cases (especially AptConfiguration has a nice API, and no complaints from valgrind anywhere). Currently I am working on Python bindings so I can interact with the functions easily and check things in an interactive fashion; and I am also writing a document explaining the concepts behind APT2, drafts at http://people.debian.org/~jak/midlevel.pdf. I also have some more code pending further thoughts (including complete index parsing), but it might still take some time before I have something usable in the wild. On other package managers: From time to time I also use Cupt, look at Cupt code, hack Cupt code, and report bugs against Cupt. I still do not really understand the (extreme) nesting of directory structures in the source code, why there are so (extremely) many source files split all over them, or the general concepts of Cupt, but I can hack together what I need for my personal testing. I also play with yum whenever I end up on a Fedora system (which happens from time to time).
Filed under: APT2

As everyone should know, underscores in C are not cool, as they cause undefined behavior per 7.1.3:

All identifiers that begin with an underscore and either an uppercase letter or another underscore are always reserved for any use.
[...]
If the program declares or defines an identifier in a context in which it is reserved (other than as allowed by 7.1.4), or defines a reserved identifier as a macro name, the behavior is undefined.

Yet, they are widely used everywhere. Here are some examples:

• inclusion guards in GLib: __G_VARIANT_H__
• internal Python functions: _PyUnicode_AsString
• various macros in APT: __deprecated, __hot

All of this triggers undefined behavior and is thus uncool. Of course in APT, it s most stupid, as we do not have any namespace and could thus
end up redefining things we should not much more likely then the other two. But why were those solutions chosen in the first place, and what is the alternative? I cannot answer the first question, but for the second one, the obvious alternative is to use trailing underscores:

• inclusion guards, defined behavior: G_VARIANT_H__
• internal functions, defined behavior: PyUnicode_AsString_
• various macros, defined behavior: deprecated__, hot__

Then there is another class of reserved identifiers with underscores:

All identifiers that begin with an underscore are always reserved for use as identifiers
with file scope in both the ordinary and tag name spaces.

Meaning that everything except for parameters, local variables and members of structs/unions that starts with an underscore is reserved. So, if you happen to create a variable _mylibrary_debug_flag, you trigger undefined behavior as well. And while we re at it, do not think you can create a type ending in _t: POSIX reserves all identifiers ending in _t for its own use. In summary, whenever you write C and want to be 100% safe of undefined-behavior-because-of-naming, do not start any identifier with an underscore and do not end any identifier with _t.
Filed under: General

One important aspect of the mancoosi project is to build a model of the installation process in order to simulate packages upgrades before committing the changes on the machine. This work described here and here (and in upcoming publications) relays on the availability installation plan of the meta-installer (the exact order in which packages will be installed, configured and removed ) to run a simulation of maintainers scripts and check for potential problems accordingly to the model. Thanks to the help of Julian Andres Klode upstream and maintainer of the python-apt bindings it is now possible to extract the installation plan from apt-get without resorting to debug printout or other hacks. A forthcoming integration with mpm (Mancoosi-Package-Manager, our testbed meta-installer) will give us the possibility to hook the model checker to the meta-installer and to run it before every upgrade. The two important changes in the python-apt bindings that will make this possible are the new bindings to the class OrderList and the sub-classing of the class package manager. PackageManager . Regarding the latter, this is a small example (thanks again Julien !) that you can use to get the installation plan as computed by apt-get. In theory, this will also allow to experiment with different back-ends (like rpm - blah ! :) ) easily without the need to hack the c++ code. And this is the result on my machine :

The last two weeks, two new python-apt releases were made. 0.8.0~exp3 did not add much, but 0.8.0~exp4 added some new bindings for our friends at the mancoosi project. I also committed several fixes to the APT repository, but did not upload them yet. In #debian-devel, some people (including me and others on the Debian side; and sladen, sabdfl for the Ubuntu side) discussed the Ubuntu font license which is considered non-free by Debian, due to extreme naming restrictions in section 2 (unmodified versions must keep the name, slightly modified versions must keep the name and add something). Some consider those restrictions equivalent to invariant sections. After we discusses the font license, we quickly got to discuss Doctor Who and time travel, as those two are obviously connected. Some other things happened as well, like closing more bugs, but all in all, the last two weeks where a bit less intensive than the two weeks before them.
Filed under: Debian

python-apt 0.8.0~exp2 bug fix release On Tuesday, I uploaded python-apt 0.8.0~exp2 to experimental, fixing about 10 bugs reported in Ubuntu and Debian bug trackers. It should know even convert integers correctly on all architectures, previously we could have passed long via varargs where int was expected. Bugs Until Thursday, I went through the bug list in Launchpad and closed/fixed/reassigned/merged about 100 bugs in APT and python-apt. APT & python-apt updates for squeeze Today, I uploaded updates of apt and python-apt to stable. They include support for xz and parsing multi-arch dependencies, as wanted by ftpmasters. APT 0.8.14 and wildcards/regular expression pinning Today, I uploaded apt 0.8.14 to Debian unstable, introducing support for pinning using glob() like Syntax and POSIX extended regular expressions. Let s say we want to pin all packages starting with gnome or kde to 990. The following example does this, using glob-like patterns for gnome, and a regular expression enclosed in / for kde:

Package: gnome* /^kde/
Pin: release a=experimental
Pin-Priority: 990
This closes 10-year-old Bug#121132 in Debian. Have fun with this feature, but please note that it may not be the fastest thing on earth, as it checks every package in the cache on initialization of such queries, which may take a few 10 ms. Since some time already, it s also possible to use such expressions for the Pin field. Thus users of Ubuntu releases could use the following piece of preferences to pin all packages in archives starting with lucid (e.g. lucid, lucid-updates) to 990:

Package: *
Pin: release a=lucid*
Pin-Priority: 990
Those types of pins do not have the negative performance impact of complex expressions in the Package header, as they are only checked against a smaller set of packages, or if Package: * , simply checked against the package files in the cache.
Filed under: Debian