I just pushed a new release of haggle to Hackage today. The haggle library implements a number of different representations of graph data structures with different capability and efficiency tradeoffs. It is inspired by both fgl and boost::graph, with the goal of enabling users to choose the right graph representation for their needs, while avoiding the partial functions that are used in fgl.

This release largely adds some instances contributed by users (including some Unbox instances). The one small API change is to finally expose a function, vertexId, to extract an Int from a Vertex. One of haggle’s original goals was to keep the Vertex type opaque to ensure that users could not create invalid vertices in graphs. However, it became apparent that some part of the structure would need to be exposed, at least in a read-only capacity:

• Interfacing with external libraries (e.g., to render graphs using GraphViz)
• Implementing many graph algorithms efficiently usually requires an index of vertices that benefits from a raw Int representation

While I had haggle paged in, I also took the opportunity to clean up some technical debt, fix compilation with some older versions of GHC, and migrate to Github Actions for CI (from Travis CI). I used the excellent haskell-ci tool to auto-generate the CI configuration, which worked on the first try. It was a great experience, so I expect to use it going forward on all of my simpler packages.

TL;DR

The build-bom tool makes it easy to obtain LLVM IR for C/C++ programs without requiring any modifications to build systems by using the low-level debugger primitive ptrace. This is something you may want if you build tools to analyze C/C++ programs. A typical use of build-bom looks like:

./configure
build-bom generate-bitcode -- make
build-bom extract-bitcode /path/to/binary --output binary.bc

Background

What is LLVM IR?

LLVM IR is the intermediate representation of code used by LLVM. The IR is a form of three address code that can be thought of as an abstract load/store machine with unlimited virtual registers. It is both straightforward to generate from many imperative languages and amenable to the analyses and transformations necessary for an optimizing compiler.

Note that this is often referred to as LLVM Bitcode. To be precise, the bitcode is the format of a data stream that is used to represent LLVM IR. The distinction is slightly academic, as the LLVM bitcode format is not used for anything besides LLVM IR. I will refer to it as LLVM IR in this post.

Why LLVM IR?

There are, presumably, many things one can do with programs represented in LLVM IR. I will focus on the needs of program analysis (e.g., static analysis and verification) tools, which analyze programs to learn things about them. By virtue of maintaining Single Static Assignment (SSA) form, it is especially amenable to static analysis. Common program analysis tasks include finding bugs or proving that programs satisfy some specification (e.g., proving the absence of memory errors).

While analyzing C and C++ source directly would be idealIt would be worth devoting an entire post to some of the nuanced differences between source-level analysis and analysis of LLVM IR.

, it is very difficult in practice due to the complexity of parsing and semantically analyzing C (and particularly C++). By analyzing programs represented in LLVM IR insteadOne might ask: why LLVM IR over one of the nearly countless other compiler IRs out there? The LLVM project has a thriving community with many contributors, as well as one of the most mature C/C++ frontends available. It has also maintained a reasonably high degree of compatibility over the years (at least at the LLVM IR level). There are also libraries in many different programming languages for reading and creating LLVM IR.

, tools are able to reuse the parser and semantic analysis of the Clang compiler, which has the benefit of many thousands of person hours of engineering. Beyond simplifying parsing, the number of constructs in LLVM IR (i.e., the number of instructions) is significantly smaller than the number of syntactic constructs in C. This simpler representation, which still precisely captures the semantics of the program, in turn simplifies the implementation of program analysis tools.

Where does LLVM IR Come From?

To turn a C source file into LLVM IR, one usually uses clang with the -emit-llvm argument:

clang -emit-llvm -c foo.c -o foo.bc

That works well for a single source file, but creating LLVM IR for an entire program is more complicated. In fact, it is as complicated as the build system for the program, which can be arbitrarily complicated. In simple cases, one could modify the build system to generate LLVM IR instead of object files and then combine them into a single larger LLVM IR file using llvm-link. Ideally, there would be a tool to make the process easier.

Challenging Build Features

Before looking at possible implementations of a tool to generate LLVM IR for a C/C++ codebase, it is helpful to think about the constraints that such a tool should satisfy. These constraints are embodied by challenging features of build systems that appear in the wild.

1. There is no standard build tooling for C/C++. Since there is no standard build system, every C/C++ project invents its own build system. While there are a number of common build systems (e.g., autotools and cmake), every instance of these build systems has its own unique quirks. A general LLVM IR generator cannot assume anything about the build system.
2. Build systems can invoke build intermediate executable artifacts. This case is not common, but arises for projects that build an intermediate code generator that generates additional source files. These intermediate binaries are necessary and must work, or the build will fail. A general LLVM IR generator must generate executable artifacts faithfully.
3. Build systems can delete intermediate files and directories. Some build systems, particularly cmake, aggressively discard intermediate files and directories. A general LLVM IR generator must not leave LLVM IR in the build tree.
4. Build systems can be configured via environment variables (except when they cannot) Some build systems, like cmake, can be configured through environment variables (e.g., CC). However, others reset environment variables either to achieve hermetic builds (or incidentally). A general LLVM IR generator cannot rely on being able to pass environment variables to all stages of a build process.
5. Build systems can invoke other build systems at build time. While recursive make is a famous and often maligned example, the reality of build systems in the wild can be even worse. For example, there are a number of build systems based on autotools that invoke other autotools build systems (i.e., configure scripts) at build timeI remember encountering this when attempting to generate LLVM IR for gdb, which contains a few sub-libraries with their own configure scripts.
   
   . It is usually very difficult to control the build flags passed to those recursively-invoked build systems, as they are not designed for customization. A general LLVM IR generator cannot require passing arguments to the build system.
6. Configure scripts are very clever. Not all configure scripts (or variants for other build systems) are overly clever; however, some go to extraordinary lengths to fingerprint the system compiler. A general LLVM IR generator cannot fool a configure script into believing it is the system compiler without actually being the system compiler.
7. Build systems can hard-code absolute paths to tools. While it is not common, the configure stage of a build system may pick up absolute paths to build tools, which can become difficult to modify after configuration time. A general LLVM IR generator cannot rely on substituting build tools post-configuration.
8. Build systems may be externally-orchestrated. Some projects with complex dependencies or complex run-time setup requirementsThe build system for the NASA F’ (F prime) system is orchestrated by a number of python scripts that aggressively regenerate the build system after any changes. This is convenient for development, but is a pain when attempting to modify the build system temporarily.
   
   provide orchestration scripts. Those scripts can aggressively reconfigure the build system, making it difficult to make spot modifications to substitute non-standard build tools. A general LLVM IR generator cannot rely on being able to modify the build system.
9. Build system binaries can be statically linked. Build systems written in Golang or running on a fully statically linked distribution are more difficult to interpose upon. A general LLVM IR generator cannot rely on LD_PRELOAD hooks.

Related Tools

With some background on the requirements imposed on an LLVM IR generator by the challenges of real build systems, it is useful to look at the other tools in the ecosystem that try to solve this problem.

Clang Compilation Database

The clang compiler natively supports maintaining a compilation database, which records all of the commands used in a build. See the -MJ command line option and the Compilation Database documentation for details. Some build systems, like cmake, provide native support for generating a compilation database. For well-behaved builds, one can easily write a script to replay the compilation database and generate LLVM IR for all of the input files.

This approach is elegant, but only works for build systems that are already compatible with clang and that do not dynamically generate/delete source files. Dynamic source generation can be problematic because entries in the database may not exist after a build completes, so replaying the build accurately can be impossible.

Clang Link Time Optimization (LTO)

The clang compiler also now supports Link Time Optimization (LTO), which enables whole-program optimization by causing clang to populate object files with LLVM IR rather than native machine code. It then performs whole-program optimization at link time over a combined whole-program LLVM IR file. This is exactly what we want in principle, but in practice can be tricky to work with.

• Supporting LTO requires the build system to be modified to support LTO, which can be a non-trivial effort.
• Users would need to manually collect all of the LLVM IR they want to analyze, which can be difficult if a build system is set up to build multiple independent binaries or libraries that should not have their constituent object files combined for analysis.

wllvm

I started writing the wllvm tool in 2011 to solve the problem of generating LLVM IR for entire programs and librariesWhile I wrote wllvm, it has been graciously maintained for the last few years by Ian Mason, as most of my work has not involved LLVM until recently.

. wllvm is a set of Python scripts that mimic a compiler driver, which attempts to be a drop-in replacement for gcc. Typically, one uses wllvm by configuring the build system to use wllvm as an alternative compiler (e.g., via the CC environment variable for autotools builds or cmake builds).

When invoked, the wllvm script compiles its input twice: first by invoking the underlying compiler with all of the requested flags and then again by using clang to generate LLVM IRInterpreting compiler command line arguments is one of the major sources of complexity in wllvm. The GCC family of compilers support a large number of complex command line arguments. wllvm needs to be able to parse command lines to pick out the names of input files and output files so that it can recompile the inputs and attach metadata to the generated object files. To do this, wllvm attempts to implement a command line argument parser compatible with GCC.

. The script then writes the pathwllvm saves the path of the LLVM IR in object files. Originally, it saved the contents of the LLVM IR into the special ELF section directly. This is more convenient and ensures that LLVM IR never gets lost. However, it was occasionally problematic on 32 bit systems when building LLVM IR with debug information. The maximum size for an ELF section on a 32 bit platform is 4GB, which could be exceeded in debug builds for large programs.

to the generated LLVM IR file into a special ELF section of the object file (.llvm_bc). When the object files for a binary (shared library or executable) are linked together, the linker concatenates the contents of all of the sections with the same name, which collects all of the LLVM IR file paths into a single section. wllvm comes with a helper script, extract-bc, to extract the LLVM IR file paths, collect all of the corresponding files on disk, and link them into a single monolithic LLVM IR file using llvm-link.

In order to support build systems that delete intermediate files or directories, wllvm supports saving generated LLVM IR into a separate directory tree that the build system does not touch. wllvm supports generating LLVM IR using either clang or the Dragonegg plugin, which is a (since abandoned) GCC plugin that supports generating LLVM IR. The Dragonegg codepath was important in the early days of the LLVM project, when the clang frontend was less mature and was unable to compile some common codebases. These days, clang can handle nearly every somewhat modern codebase.

I had a great deal of success with wllvm. The cases where it fails tend to involve complex multi-stage build systems where when:

• The build system invokes autoconf scripts in ways that make it impossible to specify an alternative compiler
• The build system is too clever and detects that wllvm is an unrecognized compiler and refuses to build
• The build system makes it difficult to impossible to specify an alternative compiler
• The build system makes it difficult to impossible to replace the detected compiler after configure runs (e.g., because it refers to build tools with absolute paths)
• The build system pipes input files to the compilerPiped inputs are problematic because wllvm needs to compile them twice. The compilation to a normal object file drains the contents of the pipe, leaving an empty pipe for the second compilation with clang.
  
  

Note that none of these cases are particularly common (i.e., wllvm is very effective), but the rare difficult build systems are incredibly frustrating.

gllvm

The gllvm tool is substantially similar to wllvm. It was written by Ian Mason, who is also the primary maintainer of wllvm. gllvm operates in essentially the same manner as wllvm. In contrast, gllvm is:

• Written in Golang
• Easier to maintain
• More actively maintained
• Easier to distributegllvm is easier to distribute because it uses libraries to manipulate ELF and Mach-O files, rather than command line tools (which wllvm assumes are installed and available).
  
  
• Fastergllvm is faster than wllvm because it builds the object file and LLVM IR in parallel.
  
  

The only disadvantage to using gllvm is that it does not support the Dragonegg plugin, which is much less significant in 2021. My personal feeling is that wllvm should probably be deprecated in favor of gllvm at this point.

blight

The blight system is a set of scripts that provide a convenient interface for executing actions (hooks) before and after commands are invoked. It provides hooks by exporting environment variables that many build systems respect (e.g., CC, CXX, and LD). Each of the scripts that implement pre- and post-hooks can be configured by other environment variables.

blight aims to make adding custom pre- and post-hooks as simple as possible, making it a more general tool than wllvm and gllvm. It can be used to generate LLVM IR by hooking CC and CXX (i.e., the C and C++ compilers) and using a post-hook to invoke clang to generate LLVM IR.

As blight relies on manipulating the environment, both through build system configuration and PATH manipulation, it can fail in the same ways that wllvm and gllvm can.

Bear

The Bear tool does not generate LLVM IR directly; instead, it generates a Clang compilation database from nearly arbitrary builds for later processing (e.g., generating LLVM IR). It operates somewhat differently from the others. It uses an LD_PRELOADLD_PRELOAD is an environment variable that can be used to inject a shared library into the address space of a process on Linux and many other UNIX-like systems. If LD_PRELOAD contains the path to a shared library, the dynamic loader will arrange the address space such that symbols defined in the shared library override any dynamic symbol table entries with the same name. This means that LD_PRELOAD only works for dynamically-linked binaries and is only able to override functions with appropriate linkage (e.g., static functions cannot be hooked).

hook to observe build systems and catch invocations of compilers and records them in a compilation database. Specifically, it observes calls to the exec family of functions and records their arguments.

Several caveats apply:

• Relying on LD_PRELOAD means that statically linked build tools are not supported; in a nod to this limitation, Bear has a fallback mode based on compiler wrapper scripts
• Builds cannot always be replayed from an artifact like a compilation database

Designing build-bom

The build-bom tool is inspired by the tools described above, but attempts to learn from and improve upon them. The goal of build-bom is to generate LLVM IR for arbitrarily complex projects without requiring any modifications at all to their build systems. build-bom:

1. Observes build processes and,
2. For each source file f compiled with a recognized compiler, rebuilds f using clang to generate LLVM IR.

Much like wllvm, it parses command line arguments to recognize sources and targets so that it can attach LLVM IR to object files in a dedicated ELF section. It provides a sub-command to extract LLVM IR after builds complete.

Initial Design

In the original design of build-bom I aspired to a two stage process much like Bear, where the tool would record builds and replay them to generate LLVM IR and also enable post-build analysis of dependencies (e.g., constructing a Software Bill of Materials). In my mind, the distinguishing feature of build-bom was that it would use ptrace to observe uses of the execve system call (i.e., trace spawned processes) instead of using LD_PRELOAD hooks. By using the lower-level facilities provided by the kernel rather than the dynamic loader, it would be more robust and work for statically-linked build system and for build systems that alter the environment.

During the initial testing of this design, it became apparent that replaying arbitrary builds is not practical. A few of the observed failures included:

• Build systems that move files cannot be replayed. While it may seem like recording a file move (and all other file operations) should solve this problem, most file move operations do not correspond to a single system callWhile file move operations within a single filesystem can be performed with the rename system call, it does not work across filesystems. Most programs that need to move files use a mix of I/O calls and integrity checks provided by their programming language standard library.
  
  . This means that recording and replaying file move operations reliably is not really possible.
• The effects of shell scripts invoked by build systems are difficult to record. The executables invoked by a shell script can be observed and recorded using ptrace. However, shell actions (e.g., file redirections and pipes) cannot be easily replayed. This means that files created by shell scripts in the build process cannot be recreated while replaying the build; if the build system removed them, they are gone.

In principle, replaying every write system call—along with its arguments—should be sufficient to reconstruct any files. Tracking operations at this granularity seems problematically complex, and could ultimately require recording a huge range of system calls.

Actual Design

Rather than recording traces of build events, build-bom is now a hybrid of the wllvm and Bear approaches. It uses ptrace to attach to the build process (e.g., make or ninja) and generates LLVM IR with clang as it observes execve system calls that spawn recognized compilers. Like wllvm, it parses compiler command line arguments to determine source files and targets, enabling it to both generate LLVM IR for source files and attach it to the corresponding target (i.e., object file) created by the original compilation command.

By attaching to the build process (and all child processes) with ptrace, build-bom is able to invoke clangNote that build-bom does not support generating LLVM IR with the Dragonegg plugin.

to generate LLVM IR in the narrow window between the time the original compilation command finishes, but before it finishes terminating. This sequencing of events prevents race conditions by ensuring that the build system cannot move, rename, or remove files we need (e.g, renaming generated object files).

In contrast to wllvm, build-bom does not invent a custom format for storing LLVM IR in an ELF section. Instead, the contents of the distinguished ELF section is a tar file. When build-bom generates LLVM IR for a source file, it wraps the LLVM IR in a tar file that it injects into the distinguished ELF section using objcopy. When the system linker combines the LLVM IR ELF sections, it concatenates their contents. It turns out that concatenating tar files produces a valid tar file with the combined contents of the original tar files. This small change means that extracting LLVM IR after the build completes is somewhat simpler, requiring just:

1. Extracting the contents of the tar file into a temporary directory
2. Linking together all of the individual LLVM bitcode files using llvm-link

Interesting Implementation Details

Implementing build-bom was an interesting experience, as it shared some similarities with implementing a debugger.

The system call tracing in build-bom uses the ptrace system call on LinuxThe same approach should work on the BSDs (but likely not MacOS).

through the excellent pete library. In order to use ptrace, at least in the way that build-bom requires:

1. The process to be traced (i.e., the build process) needs to invoke ptrace(PTRACE_TRACEME, ...) to halt the tracee and allow the tracer to attach
2. The tracer (i.e., build-bom) needs to invoke ptrace(PTRACE_ATTACH, ...) to attach to the tracee
3. The tracer repeatedly invokes ptrace(PTRACE_SYSCALL, ...) to resume the tracee, but halt at the next system call
4. Each time the tracer stops the tracee at a system call, it can inspect the tracee state to determine what system call was invoked and what arguments were passed to it

While ptrace supports reading memory from the tracee using ptrace(PTRACE_PEEKDATA, ...), it only supports reading a pointer-sized value at a timeThe BSD implementations of ptrace support an additional command, PT_IO, which supports reading (or writing) arbitrary amounts of memory from the traced process.

. This is too inefficient to read large amounts of data. build-bom uses the typical workaround of performing bulk reads by reading from /proc/<pid>/mem with helper functions from the pete library.

Many build systems pass relative path names to build tools, rather than absolute paths. This is entirely reasonable from the point of view of the build system, but it does pose a slight challenge for build-bom. Throughout a build, a build tool will often change its working directory, which means that the working directory of the build tool and build-bom get out of sync. When the build system uses relative paths, build-bom must correct them in order to be able to generate LLVM IR through recompilation. While build-bom could change working directories with the build system, this would become complicated and inefficient with parallel builds. Instead, it normalizes relative paths into absolute paths when reading arguments passed to system calls.

Interpreting paths passed as arguments to system calls turned out to be a surprisingly tricky proposition. On Linux, paths are NUL terminated strings with / as a separator. There are no constraints on the encoding for paths beyond that, nor are there indicators as to what the encoding of any particular path is. The rust String type is explicitly a UTF-8 encoded string. This means that paths cannot be treated as rust strings; instead, build-bom represents them using the raw OsString type, which have no particular encoding for their contents. Semantically, this is entirely correct; however, it is a bit painful when trying to parse, manipulate, and print paths in build-bom.

Evaluation Against Requirements

Earlier in this post, I outlined a list of challenging build features that a general LLVM IR generation tool should be able to handle. Since build-bom attempts to be a general LLVM IR generation tool, let’s evaluate how many it addresses.

1. ✓ build-bom is build system agnostic
2. ✓ build-bom unobtrusively generates both the original executable build artifacts and LLVM IR, enabling intermediate build artifacts to be executed
3. ✓ build-bom generates LLVM IR for each source file at the same time the original object file is generated (recall, in the very narrow window between when the compiler completes but before it exists), ensuring that intermediate files are accessible
4. ✓ build-bom does not require any control over environment variables to work, nor does it require build systems to respect any environment variables
5. ✓ build-bom traces commands run in an entire process tree, which transparently includes child build processes
6. ✓ build-bom does not interpose in configuration processes or ever modify the arguments passed to the compiler
7. ✓ build-bom observes build commands, rather than interposing via scripts, so absolute paths in build systems (e.g., for compilers) are not problematic
8. ✓ build-bom does not need to directly trace or even be aware of the actual build process; running any orchestration scripts under build-bom will indirectly trace the build process
9. ✓ build-bom traces system calls with kernel support (i.e., through ptrace), and so does not rely on the dynamic loader

Design Consequences

Relying on ptrace to observe system calls issued by the build system serializes all of them through build-bom. This significantly reduces the parallelism available in the build system (though processes still execute in parallel when not waiting in system calls).

The reliance on ptrace also ties build-bom to UNIX-like systems. This is not a hard limitation, as MacOS and Windows both support other mechanisms that would enable the same functionality. A build-bom backend can be implemented for any system with kernel support for debugging.

• While MacOS has the ptrace system call, it is not fully-featured; MacOS debuggers require additional Mach system calls
• Windows has analogous system calls

Since build-bom is essentially a debugger, other debuggers cannot attach to any of the processes being traced.

The build-bom approach is less well-suited to builds where build commands are actually executed by a separate daemon process. Thus, using build-bom with systems like distcc and bazel is tricky. Avoiding distcc to generate LLVM IR is fairly easy. In the case of a build based on bazel (or similar systems), the server process would need to be traced.

Future Directions

There are a few major features that I plan to add to build-bom as they become needed:

• Support for response files Response files are a feature provided by both gcc and clang to make it possible to pass in large numbers of arguments, especially on WindowsOperating systems typically limit the number of command line arguments, as well as the total storage occupied by command line arguments. See the definition of ARG_MAX on POSIX-like systems, which is typically a few megabytes on Linux. The limit is considerably lower on Windows (about 32kB), which is usually the motivation for supporting response files.
  
  . A response file simply records each argument to a process on its own line; build-bom would need to parse response files to determine the inputs and outputs of compilation commands.
• Support piped inputs Currently build-bom does not work correctly with file inputs that are provided to the compiler via pipe. The original compilation command drains the pipe, leaving build-bom with no input file contents to pass to clang to generate bitcode. To fix this, build-bom will need to inspect input files and, if they are pipes, replace the pipe file with a temporary file on disk with the contents of the pipeNote that this requires modifying the command line arguments in the build process to point to the new temporary file. This is somewhat complicated, as it requires finding space in the build process to store the new path without clobbering any existing data. It remains to be seen how this can best be handled.
  
  .
• Support architectures besides x86_64 build-bom contains a hard-coded table mapping system call numbers to names to be matched on. Unfortunately, system call numbers differ across architectures on Linux. Adding support for new architectures is straightforward.
• Support ELF modification via library To attach LLVM IR to an object file, build-bom calls the objcopy binary, which it assumes is installed on the system. Using a library to read and write ELF files would reduce the run-time dependency footprint.
• Support for Windows and MacOS Extending support to Windows and MacOS requires understanding the necessary debugging system calls, but is not conceptually difficult.
• Support for arbitrary build command interposition Currently, build-bom runs extra commands to generate LLVM IR. It is a small delta to being able to arbitrarily modify build commands. I envision a sed~/~awk-like interface for matching and rewriting command line arguments. Potential uses include, but are not limited to:
  • Forcing the generation of debugging information
  • Forcing certain optimization levels
  • Enabling Address Sanitizer or Thread Sanitizer

Summary

The build-bom tool simplifies generating LLVM IR for C and C++ codebases. Compared to previous tools in this space, build-bom supports a wider range of build system features without requiring any modification to the build system in order to run. The major insight of build-bom is to use ptrace, the system call that provides debugging services on Linux, to observe build processes and generate LLVM IR just-in-time, avoiding many of the complexities inherent to other approaches.

The excellent avy package for emacs provides an efficient mechanism for positioning the cursor in the current window. The avy workflow is:

1. Active avy via one of several possible functions
2. Type a few characters corresponding to the location on screen you want to navigate to
3. Avy will highlight each occurrence of those characters with navigation hints
4. Type the one or two letters corresponding to the desired destination

Avy typically enables navigation to any position on screen in four or five keystrokes. There are variants to highlight candidates based on a single character (avy-goto-char), two characters (avy-goto-char-2), a character at the beginning of a word (avy-goto-word-1), or an arbitrary number of characters entered within a short time limit (avy-goto-char-timer).

I find that the one and two character variants produce too many matches for me to easily visually identify my target. As a result, I have been using avy-goto-char-timer, which allows you to enter any number of characters; after a timeout following the final character, avy activates and highlights matches for selection.

The avy-goto-char-timer function, unfortunately, does not provide a means for correcting typos. This minor annoyance has kept me from using avy as much as I would like for navigation within a buffer. I finally decided to fix it by introducing my own variant:

(defun tr/avy-prompt (s)
  "Prompt for an avy target and activate avy with it."
  (interactive "MAvy: ")
  (avy-process (avy--regex-candidates s)))

This function (which I bind to C-]) simply uses the minibuffer to prompt for a string and activates avy on that string. Since the string is entered in the minibuffer, all normal editing commands work on it. A future variant could potentially use completing-read to provide a filtered list of candidates (e.g., via selectrum).

This is part two of the presumably unending type errors series. The previous entry involved an amusing type error. This time the error is a bit less amusing:

ghc: panic! (the 'impossible' happened)
  (GHC version 8.8.3 for x86_64-unknown-linux):
        exprToType
  Call stack:
      CallStack (from HasCallStack):
        callStackDoc, called at compiler/utils/Outputable.hs:1159:37 in ghc:Outputable
        pprPanic, called at compiler/coreSyn/CoreSyn.hs:1997:28 in ghc:CoreSyn

Please report this as a GHC bug:  https://www.haskell.org/ghc/reportabug

Unfortunately, there was no additional context to help narrow down the problem. The file in question has a few hundred lines of code. My starting set of observations was:

• The code compiles and works on GHC 8.6.5 (so can’t be too bad)
• It used to compile and work under GHC 8.8.3 (so there were no compile errors)
• There were some warnings (but they didn’t seem particularly relevant)

I had vague memories of seeing this error before in another context and moving code around until the error went away. I don’t remember any details besides that approach to debugging being unsatisfying. Ultimately, I took a guess that:

1. GHC was attempting to print a warning related to inferred types
2. GHC has recently started warning about type family applications appearing as kinds

There was one function in the file in question that had an explicitly quantified kind variable meeting those conditions. Adding an explicit (dependent) kind annotation to that variable caused the crash to go away.

I find that I run into a large number of what I would consider Funny Type Errors while using GHC. This is the first post in what will presumably be a long series of posts on the topic.

Today I was working on trying to improve the performance of a codebase that uses a large number of the type system extensions provided by modern GHC including -XGADTs and -XTypeInType. Seeing strange type errors in this code is expected on a daily basis. However, the code I was working in today was not doing anything too unusual. A reduced example of the surprising code is:

{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeInType #-}
{-# OPTIONS_GHC -Wall -Wcompat #-}
import qualified Data.Functor.Const as C
import           Data.Kind ( Type )

data Pair (a :: k -> Type) (b :: k -> Type) where
  Pair :: a tp -> b tp -> Pair a b

data MonoStruct =
  MonoStruct { item :: Pair (C.Const Int) (C.Const Int)
             , otherData :: Int
             }

getFirst :: MonoStruct -> Int
getFirst ms =
  let Pair a _b = item ms
  in C.getConst a

update :: MonoStruct -> Int -> MonoStruct
update ms f = ms { item = Pair (C.Const f) (C.Const f) }

Naively, I expected this to compile. Instead, GHC (8.6.5 and 8.8.3) report the errors:

❯ ghci poly.hs
GHCi, version 8.8.3: https://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( poly.hs, interpreted )

poly.hs:18:19: error:
    • Cannot use record selector ‘item’ as a function due to escaped type variables
      Probable fix: use pattern-matching syntax instead
    • In the expression: item ms
      In a pattern binding: Pair a _b = item ms
      In the expression: let Pair a _b = item ms in C.getConst a
   |
18 |   let Pair a _b = item ms
   |                   ^^^^

poly.hs:22:15: error:
    • Record update for insufficiently polymorphic field:
        item :: Pair (C.Const Int) (C.Const Int)
    • In the expression: ms {item = Pair (C.Const f) (C.Const f)}
      In an equation for ‘update’:
          update ms f = ms {item = Pair (C.Const f) (C.Const f)}
   |
22 | update ms f = ms { item = Pair (C.Const f) (C.Const f) }
   |               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is very strange: the MonoStruct type does not contain any polymorphic fields. In fact, I called it MonoStruct in this example because it looks entirely monomorphic. To dig a little deeper, we can ask ghci for some additional information:

Prelude> :set -fprint-explicit-foralls
Prelude> :set -fprint-explicit-kinds
Prelude> :load poly.hs
[1 of 1] Compiling Main             ( poly.hs, interpreted )
Ok, one module loaded.
*Main> :info MonoStruct
data MonoStruct
  = forall {k}.
    MonoStruct {item :: Pair k (C.Const k Int) (C.Const k Int)}
   -- Defined at poly.hs:11:1

This shows us what is really happening. Note the definition of Pair: it takes two data items that are indexed by a poly-kinded type parameter (k). This has an unfortunate interaction with the use of Const as the data elements, as Const is also kind polymorphic. This means that while the type of the Pair in MonoStruct looks monomorphic, the kind of the pair could change on update, which causes the error we see from ghci. As a concrete example, we could populate our Pair with Const Int Int or Const Int '[Natural]. Specializing the type put into the Pair removes the unwanted polymorphism:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeInType #-}
{-# OPTIONS_GHC -Wall -Wcompat #-}
import           Data.Kind ( Type )

data Tag = A | B

data ConstInt (k :: Tag) = ConstInt { getConstInt :: Int }

data Pair (a :: k -> Type) (b :: k -> Type) where
  Pair :: a tp -> b tp -> Pair a b

data MonoStruct =
  MonoStruct { item :: Pair ConstInt ConstInt
             }

getFirst :: MonoStruct -> Int
getFirst ms =
  case item ms of
    Pair a _b -> getConstInt a

update :: MonoStruct -> Int -> MonoStruct
update ms f = ms { item = Pair (ConstInt f) (ConstInt f) }

Instead of writing about something productive, I am going to again write about writing. Or at least the infrastructure for writing. First, I decided to switch comments from Disqus to utteranc.es, which is a clever approach to hosting comments for statically-generated sites. For each post, the script creates a GitHub issue and adds each comment to the issue. There are no ads, and it is all around more civilized. Moreover, I appreciate the simplicity of the model. Not that I expect an excessive comment load.

Next, I updated the version of the Hakyll static site generator from something very old to the latest as of the time of writing. I am very pleased to report that it did not require any code changes. I can only aspire to that level of stability in my own code. Despite not requiring any code changes, I took the opportunity to change one line of code to enable support for writing in Emacs org-mode instead of markdown.

Recently, I had the urge to optimize the startup time of my emacs configuration. I managed to reduce my startup time from three seconds to under half a second. It was a fun exercise even though I don’t really start emacs that often. Even that minor reduction makes starting a new emacs instance (e.g., from mutt or in a terminal) much more pleasant. I could use the server functionality in emacs (along with emacsclient) to always connect to a single persistent instance, but I like the isolation of separate processes. I’ve had the server crash before bringing down all of my sessions, which is fairly annoying. Most of the startup time savings came from systematically employing lazy package loading through John Wiegley’s excellent use-package. Besides making it easy to properly load packages lazily, use-package also handles package installation and configuration.

use-package encourages a configuration style that isolates the configuration for each package in a use-package form. Moreover, the configuration of each package is split into initialization steps taken at emacs startup time (via the :init section) and configuration steps executed after the package is loaded (via the :config section). Packages can also be loaded lazily, which significantly improves startup time. By default, use-package forms that bind keys or are associated with a specific file type are loaded lazily.

After doing a bit of profiling with esup, which is an emacs startup profiler, I found a few surprising initialization steps that were taking up most of my startup time. The most expensive parts are difficult to optimize further: theme loading, font setting in GUI mode, and initialization of the package library. Aside from that, cc-mode was one of the most expensive things to load; moving more of the setup from :init to :config took care of that.

There was at least one interesting and unexpected consequence of my use-package configuration that I did not initially appreciate. I decided to set

(setq use-package-always-ensure t)

This option tells use-package to automatically download and install packages that are not already installed. This is convenient to bootstrap a new emacs installation or to bring an existing one up to date with the latest changes to your emacs configuration. It has side effect of breaking when the package being set up is not in one of the emacs package repositories (i.e., local packages). This came up while setting up a major mode for netlogo. It eventually occurred to me that I could tell use-package to not try to install this package by setting :ensure nil in the use-package form:

(use-package netlogo-mode
  :ensure nil
  :load-path "~/.config/local/emacs.d/lisp"
  :mode ("\\.nls$\\|\\.nlogo$" . netlogo-mode))

In the process, I cleaned out old configurations I didn’t need anymore and enabled a few new packages including:

• swiper (for sophisticated finding and replacing)
• avy (for quick navigation)
• switch-window (for faster movement between windows)

It was fun to refresh my entire configuration. I should probably do that more often.

Over the last few weeks, I’ve found myself having to copy and paste large chunks of text into emacs running in a terminal. This leads to some annoyance, as each character pasted triggers a keystroke. In particular, every newline triggers indentation via newline-and-indent. This is very annoying, as the indentation usually gets a bit messy and turns into an ugly staircase of text. Vim has a solution to this problem via a command :set paste, which turns off indentation while pasting. More generally, most terminals support what is known as bracketed paste to enter a large string of text as one virtual keystroke. I recently discovered the emacs equivalent: bracketed-paste mode on melpa. Now a long standing annoyance is fixed with a simple:

(require 'bracketed-paste)
(bracketed-paste-enable)

I recently found myself looking at Linux instant messaging clients again. Sometimes I feel like some kind of Luddite for still using a desktop instant messaging client, but I just cannot bring myself to use a web application. I have used pidgin for as long as I can remember, but I have been looking for an alternative with better support for primarily keyboard interaction. My biggest complaints about pidgin center around odd focus issues that sometimes seem to require a mouse to fix.

Unfortunately, none of the GUI clients seem to offer decent keybindings. That leaves console clients. I have tried finch, which isthe console frontend to libpurple (which is itself the library that provides all of the interesting functionality in pidgin). finch comes with an interesting console window manager built on top of ncurses called gnt. I found the default UI and keybindings to be maddening, even more than most normal GUI applications. That defeated the purpose of switching.

gnt has a surprising feature: it supports alternative window manager layouts through plugins. I tried to use the one that mimics an irssi-style client. This interface superficially looked like irssi, but the interaction model was still annoying and required awkward focus changing commands. Moreover, it interacted badly with terminal resize events. Whenever I would move the terminal to another monitor with xmonad, the subsequent resize event would jumble the window positions. This caused awkward overlaps, which ruined the irssi-like illusion that the window manager plugin was trying to present. It turns out that the plugin really just carefully arranges windows to mimic the irssi interface, but only on application startup. It would not reflow the layout in response to changes.

For now, I have settled on profanity. Profanity is a console client that also mimics the irssi interface. It is significantly more successful at doing so than finch. The only downside to profanity is that it only supports a single account. It is not a huge burden to use tmux to manage a few instances for different accounts, though I would not object to multi-account support. It is worth noting that profanity only supports XMPP, which is fine for my purposes. It seems to support all of the XMPP extensions that I need (and then some), including multi-user chats. I had to spend a bit of time configuring things properly, but I eventually managed to get it working well with tmux and my xmonad configuration. Most of this configuration was related to notifications. I use X window urgent hints to show activity notifications in my xmonad bar (taffybar). Profanity easily supports this mode of operation with the /flash configuration option. There was a bit of an issue with running it in a tmux session, though; tmux would set the urgent hint when there was any console activity at all. Annoyingly, this included clock updates in the profanity status bar. I had to disable that with the /time configuration option, which was unfortunately a new addition as of 0.4.7. Of course, the version shipped with Ubuntu 15.10 is 0.4.6.

Overall, I am pleased with profanity so far. We shall see if I can stand it in a week.

I recently ran into a strange problem with running emacs. A few days ago, my delete, page up, and page down keys stopped working, but only when emacs was run in the terminal. Whenever I hit one of those keys, emacs would complain that the region was empty. This was baffling for a while. Searching the internet turned up nothing, so I had to assume that it was something I had done. One further symptom manifest: when I used my M-[ keybinding, the bound function would execute and it inserted 3~ into the buffer. That was unusual.

It turns out that binding M-[ to anything is a bad idea because Meta and Escape are the same in emacs. It also turns out that Escape-[ is the prefix for a few keycodes, including delete, page up, and page down. My delete key was being intercepted and invoking my keybinding. When the associated function was successful, the rest of the delete keycode was inserted into the buffer.

Lesson learned: do not bind M-[.