Skip to content
crustify-rsPublic

About

Dependency-ordered graph of C types and symbols based on CodeQL, suitable for neuro-symbolic workflows.

Resources

Stars

2 stars

Watchers

1 watching

Forks

Latest commit

 

History

79 Commits

Folders and files

Repository files navigation

Wavefront

Wavefront analyzes a C codebase and schedules its units in dependency order for translation to Rust. It extracts entities and dependencies with CodeQL, builds a cycle-free dependency graph of the codebase's types and symbols, and packs that graph into ordered waves of batches. Each batch can be translated once the waves before it are complete.

Wavefront keeps its analysis simple: it infers facts from the codebase without data-flow or points-to analysis. It is built for neuro-symbolic workflows, in which human or LLM reasoning complements its static facts:

  • You can state the polymorphic and type-erased edges that Wavefront cannot infer. Wavefront loads them into the dependency graph, and its schedules order units by them.
  • You can record pointer-level ownership and lifecycle properties for each type and symbol. Wavefront returns them with the records of that type or symbol.

Requirements

Install

git clone https://github.com/crustify-rs/wavefront.git
cd wavefront
python -m pip install -e .
codeql pack install src/

Usage

wavefront REPO_ROOT --config PATH COMMAND ...

REPO_ROOT is the root of the C repository. --config names its wavefront-config.json; a relative path is resolved from REPO_ROOT.

Configuration

{
  "state_dir": ".wavefront",
  "closure": {
    "impl_files": {"included": ["src/"], "excluded": ["src/tests/"]},
    "api_headers": {"included": ["include/widget.h"]}
  },
  "modules": [
    {"name": "src/mem.c", "files": ["src/mem.c", "src/mem.h"]},
    {"name": "src/widget.c", "files": ["src/widget.c", "include/widget.h"]}
  ],
  "schedule_seeds": ["include/widget.h"],
  "t3_dir": "t3"
}
Key Meaning
state_dir Directory for the CodeQL database and tables, ownership findings, and caches.
closure The program Wavefront analyzes. The graph, the queries and the usage counts cover it. It has two parts: impl_files, the sources and private headers that implement the program, and api_headers, the headers that publish its API. Each part lists its included files and directories, less what excluded matches. See Files.
modules Optional. A list of module records, {name, files}. A module is a named group of files and items, typically a translation unit with its headers. It is unrelated to C++20 modules. Each entry of files is a file entry, as in schedule_seeds. A schedule orders each module's units together, and orders the modules by their dependencies, with their cycles cut. A unit that no module claims is ordered alone. See Modules.
schedule_seeds Optional. The list of file entries that wavefront schedule starts from. Each entry seeds what its file defines or declares, and a schedule holds its seeds and what they depend on. A file entry is a path, a directory written with a trailing slash, or {path, items}. The included and excluded items of items, each {name, kind}, narrow what the entry seeds. Without schedule_seeds, a schedule starts from every unit of the closure. See Schedule seeds.
t3_dir Optional. Directory, relative to state_dir, holding the T3 tables (examples/t3/).

Paths are relative to REPO_ROOT. A trailing slash selects a directory recursively, in included and excluded alike. excluded is optional. For a complete configuration, see examples/wavefront-config.json.

1. Extract

Build the project under CodeQL, then extract the T1 (entity) and T2 (edge) tables into <state_dir>/codeql/:

codeql database create REPO_ROOT/.wavefront/codeql/db \
  --language=cpp --source-root=REPO_ROOT --command="make -j"
wavefront REPO_ROOT --config wavefront-config.json extract-ql

Run extract-ql again only when the database changes.

2. Query

wavefront REPO_ROOT --config PATH query [SUBJECT] [FLAGS]
Subject Output
none Every entity, one name, kind, defined_in, declared_in line each, grouped by kind. --closure-only, --external-only, --api-only and --file narrow it.
functions, globals, macros, function_pointers, typedefs Records of that kind: signatures, callers and callees, and findings. A function pointer is a typedef declaring one, its aliases folded in, or one written inline, named by its signature. A typedef is one that names no struct, union, enum or function pointer.
structs, unions, enums Records of that kind: fields, casts, users, and findings.
files The closure, external, and API file sets.
dag Dependency closures, graph layers, and cycle twins.

Common flags:

Flag Effect
--name NAME ... Select entities by name. Without it, a kind's subject lists its names.
--file FILE ... Narrow named entities to those defined in these files.
--closure-only, --external-only Keep entities defined in the closure's files, or the external ones it reaches.
--api-only Keep entities the api_headers publish.
--update FINDINGS Submit findings for one named entity (- reads stdin).
--in-tree, --out-of-tree Listing only: keep entities defined inside, or outside, the repository.

Struct, union and enum views (one --name):

Flag Effect
--fields Print the declared fields and their records.
--lifecycle-ops Print the routines that drop, dispose, clone, or construct the type.
--users Print every function that uses the type, and for an enum every global and macro that names one of its constants.
--field-touchers Print each field and the functions that access it.
--layout-users Print every function, global and aggregate that depends on the type's layout, with the sites of each use.
--raw-sites Print every function that allocates or frees the type with a raw routine (a lifecycle role on a void *, in the ownership store), with each site. With --unresolved and no --name: the raw sites on type-erased values no table types.

Function searches (--callees and --callers also take a global, macro or typedef):

Flag Effect
--taking SPEC Find functions with an argument of type SPEC (a type, void, or string).
--returning SPEC Find functions that return a pointer of type SPEC.
--lifetime-for SPEC Find the submitted lifecycle routines acting on SPEC.
--calling FN,... With --taking or --returning, keep functions that reach one of FN.
--callees, --callers Walk the call graph forward or backward from --name.
--depth N Hop limit for the walks above; default 1.
--array Keep matches classified as arrays.

Graph views (query dag):

Flag Effect
--name NAME ... Print the dependency closure of the named nodes.
--depth N Limit the closure to N hops.
--layer N Print every node in layer N.
--scc hi-deps|lo-deps With --name, print the cycle twins recorded in fallback or back_fill.
--loc Report estimated lines of code.
--kind KIND With --name, keep its nodes of this kind (function, struct, ...). A name that names several nodes resolves to all of them, listed under matches with their kinds and files.
--api-headers-only Use the public-signature graph.

Examples:

# List everything the headers publish, by kind.
wavefront /src/widget --config wavefront-config.json query --api-only

# Show one type's fields.
wavefront /src/widget --config wavefront-config.json \
  query structs --name widget_st --fields

# Find functions that take widget_st and reach widget_release within 3 calls.
wavefront /src/widget --config wavefront-config.json \
  query functions --taking widget_st --calling widget_release --depth 3

# Show the dependencies of widget_new.
wavefront /src/widget --config wavefront-config.json \
  query dag --name widget_new --depth 1

Each subject's --help lists its complete flags.

A type or symbol record has two parts: composed, which Wavefront derives from the code, and findings, which you fill. findings lists every slot the entity accepts, in the shape --update takes, so you can fill it in and submit it. See docs/artifacts/findings.md and examples/findings.json.

3. Schedule

wavefront REPO_ROOT --config PATH schedule --output PATH [FLAGS]

A schedule:

  • orders every unit of the config's closure, in the groups its modules make;
  • keeps its schedule_seeds and every unit they depend on; and
  • emits one wave per layer of each module.

A unit that no module claims goes in one of two places:

  • If the unit is a seed, if only such a seed needs it, or if the scheduled units reach it only through cut edges, it goes in a separate wave with no module.
  • Otherwise, it goes in a wave of the first module that needs it, ahead of the wave that does.

A narrow schedule keeps the order and cuts of the whole closure, so a consumer can schedule parts of a library in turn without changing the order.

Each unit carries its module, its defined_in and declared_in files, and the statistics a consumer weighs its work by. A unit also carries its release points:

Unit Field The point after which
struct, union, enum opaque_after none of its layout users is left to process
struct, union memory_unmanaged_after no C allocates or frees it with a raw routine
function, global, macro, function pointer, typedef unreferenced_after none of its referrers is left to process
Flag Default Effect
--output PATH Required. Output file; its directory must exist.
--api-headers-only Schedule the public API from the public-signature graph.
--max-types N none Types per type batch.
--min-fields N none Declared fields that close a type batch.
--max-syms N none Symbols per symbol batch.
--max-loc N none Body lines per symbol batch; 0 disables the limit.

Without a cap, a wave holds at most two batches for the consumer to split: its types and generator macros, then everything else. A wave with units of only one of the two groups holds one batch.

Example:

wavefront /src/widget --config wavefront-config.json schedule \
  --api-headers-only --output /src/widget/schedule.json

See examples/schedule.json for the output.

Documentation

Document Contents
docs/graph.md The dependency graph: nodes, edges, type erasure, cycles, polymorphism, and limitations.
docs/scoping.md The closure, modules, the schedule seeds, closure and external entities, the API view, and default and API modes.
docs/batching.md Units, their order, waves, batch caps, and release points.
docs/pointer-properties.md The pointer properties recorded in the ownership store.
docs/type-lifecycle.md Lifecycle roles, and how to find the routines that play them.
docs/artifacts/ Field reference for type and symbol records, findings, the ownership store, schedules, and T3 tables.

Tests

PYTHONPATH=src python -m unittest discover -s tests

The default suite does not run CodeQL. The tests that compose, query or schedule a fixture read the fixture's committed tables, in tests/fixtures/<name>/codeql/.

The CodeQL tests are opt-in. They build each fixture's database and run the queries, then check the queries' golden tables and that the committed tables are current. Before you land a change to a query or to a fixture's C, run them and make sure they pass:

WAVEFRONT_CODEQL_TESTS=1 PYTHONPATH=src python -m unittest discover -s tests

After such a change, re-extract the committed tables and review their diff:

PYTHONPATH=src python tests/regenerate_tables.py [FIXTURE ...]

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Maintainers

Acknowledgements

This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) Translating All C To Rust (TRACTOR) program under Agreement No. HR00112590134.

About

Dependency-ordered graph of C types and symbols based on CodeQL, suitable for neuro-symbolic workflows.

Resources

Stars

2 stars

Watchers

1 watching

Forks

Releases

Packages

Contributors

Languages