Planet SoC

Yesterday, 10 July, was the due date for the second
milestone of my work on DebGraph. I am happy to report that
we are roughly two weeks ahead of schedule, so meeting this
milestone was not a cause for worry.

We now have support for the following graph operators:

• Difference

• Intersection
• Filter (by properties)
• Find Cycles (via Tarjan’s
  algorithm)

• Find Dependencies
• Find Reverse Dependencies
• Symmetric Difference (XOR)
• Union

The next milestone includes the development of a high-level
language (or integration with an existing extension
language) that streamlines the construction of complex
queries using the operators listed above. We can build
arbitrarily complex queries using the C++ operators, but
dealing with the static typing and compiler toolchain can be
very clunky. As such, I have spent the past week working on
Lua bindings for DebGraph, which will enable us to query the
graph of Debian packages from a clean, dynamically typed
language. Lua has a powerful C API that exposes the Lua
stack and lets us move DebGraph information to and from the
Lua interpreter. I’m writing documentation that outlines
how to use DebGraph from both C++ and Lua in order to make
this work accessible to more folks.

Sneak peak

As an example, we can utilize the FindCycles operator in Lua
as follows:

libdg = package.loadlib("./libdebgraph.so",
"luaopenlibdebgraph")
libdg()
LoadPackages('cache')
-- 'g' is the main graph of unstable binary-arm packages
cycles = FindCycles(g)
print("Found " .. #fc .. " cycles")
for compkey,comp in pairs(cycles) do
    compnodes = ""
    for nodekey,node in pairs(comp) do
        prop = GetProperty(node, "Package")
        compnodes = compnodes .. prop .. " "
    end
    print("* " .. comp_nodes)
end

The above Lua script produces the following result:

reading cache/unstable/main/binary-arm/Packages
Found 61 cycles
* debconf-english debconf-i18n debconf
* perl-modules perl 
* cdebconf fontconfig-config fontconfig gsfonts-x11
libcairo2 libfontconfig1 libgtk2.0-0 libpango1.0-0
libpango1.0-common libxft2 ucf x11-utils xutils
[...]

These are the package names in the strongly connected
components, shown in alphabetical order.

There is still a lot of work to do before the Lua binding
will achieve feature parity with the core library, but we
have now laid the foundation (and a brick or two).