travitch / haggle

An efficient graph library for Haskell

I enjoy building secure and correct systems. I have built a number of static analysis and automated verification tools, with a recent focus on analysis of binaries.

Repositories

Data Structures

Data structures that may be generally useful

• haggle [39 ⭐ 📖]: An efficient graph library for Haskell
• persistent-vector [27 ⭐ 📖]: Persistent vectors for Haskell based on array mapped tries
• robbed [4 ⭐]: A pure Haskell implementation of Reduced Ordered Binary Decision Diagrams (BDDs)

Program Analysis

• ql-grep [3 ⭐]: A code search tool that implements CodeQL on the tree-sitter infrastructure
• build-bom [45 ⭐]: Dynamically discover the commands used to create a piece of software
• whole-program-llvm [682 ⭐]: A wrapper script to build whole-program LLVM bitcode files; note that I consider this to be obsoleted by build-bom, which takes a more robust approach to the same problem
• itanium-abi [12 ⭐ 📖]: An implementation of C++ name mangling for the Itanium ABI
• what4-serialize [0 ⭐]: Serialization/deserialization for What4 expressions

Binary Analysis

• crepitans [2 ⭐]: A tool for scriptable exploration of binaries
• dismantle [25 ⭐]: A library of assemblers and disassemblers derived from LLVM TableGen data
• portable-executable [2 ⭐]: Tools for working with the Windows Portable Executable (PE) file format
• semmc [35 ⭐]: Stratified synthesis for learning machine code instruction semantics
• macaw [201 ⭐]: Open source binary analysis tools.
• macaw-loader [5 ⭐]: Uniform interface to load a binary executable and get Macaw Memory and a list of entry points.
• renovate [47 ⭐]: A library for binary analysis and rewriting
• language-sleigh [5 ⭐]: A parser for the Sleigh language, which is used to represent ISA semantics in Ghidra
• mctrace [5 ⭐]: An implementation of DTrace for machine code

Debugging Tools

• ddmin [3 ⭐]: An implementation of delta debugging (ddmin) in Haskell
• surveyor [18 ⭐]: A symbolic debugger for C/C++ (via LLVM), machine code, and JVM programs
• binary-walkr [2 ⭐]: A tool for examining ELF binaries

Solvers

Note that these are interesting and informative, but definitely not efficient enough to use in production

• satisfaction [2 ⭐]: A DPLL SAT solver written in Haskell
• datalog [102 ⭐]: A pure Haskell implementation of Datalog
• ifscs [4 ⭐ 📖]: An inductive form set constraint solver in Haskell
• satir [1 ⭐]: An implementation of a SAT solver in Rust

Emacs Packages

• haskell-pragma.el [3 ⭐]: An emacs hydra to enable Haskell language extensions efficiently
• haskell-interactive-import.el [0 ⭐]: A Haskell function and minor mode for interactively adding imports to modules

Others

• taffybar [691 ⭐ 📖]: A gtk based status bar for tiling window managers such as XMonad; now maintained by Ivan Malison
• travitch [1 ⭐]: The code for my Github profile page, which generates this page
• blog [3 ⭐]: The code for my blog (ravit.ch)
• dotfiles [0 ⭐]: A collection of dotfiles managed by Chezmoi

haggle's Issues

Consider using backpack

I feel like many of the interfaces in this package would benefit from being specified as backpack signatures. Backpack signatures are easily extendable, so you could define the labeled graphs as extensions of normal graphs. I think it would simplify the types and functions.

Under what conditions can addLabeledEdge fail?

According to the docs, addLabeledEdge has the following type:

addLabeledEdge :: (MLabeledEdge g, PrimMonad m, MonadRef m) => 
    g m -> Vertex -> Vertex -> MEdgeLabel g -> m (Maybe Edge) 

Under what conditions will the resulting Maybe Edge be Nothing? Specifically, I assume that, unless both Vertexes are in g m, this will not create an Edge. Am I correct in this assumption?

Too strict bounds on ref-tf

Haggle builds with ref-tf 0.5, but forbids it.

Bifunctor instances

Given PR #7, it might be useful to have bifunctor instances for the other graph backends

Expose `vertexId`

From the haddocks:

Furthermore, the types of vertices (nodes in FGL) and edges are held as abstract in haggle, allowing for changes later if necessary. That said, changes are unlikely and the representations are exposed (with no guarantees) through an Internal module.

However, I see no such internal module. I really just want the vertexId function so I can convert haggle graphs to fgl (thence to graphviz). But right now I don't see any way to do this. Am I missing something?