$ show starkware-libs/cairo
This repository is the official compiler for the Cairo programming language, a Turing-complete language designed for provable computation (zero-knowledge proofs). It compiles Cairo source through a multi-stage pipeline: parsing (via LALRPOP), semantic analysis with type inference and trait resolution, lowering to a control-flow graph with extensive optimizations (CSE, constant folding, inlining, match optimization, gas redeposit), generation of the Sierra intermediate representation (a safe, bounded subset for ZK provability), and final compilation to CASM (Cairo Assembly) for execution on the Cairo VM. The compiler uses the Salsa incremental computation framework for query-based caching and is split into 40+ crates organized by compiler phase (parser, semantic, lowering, sierra-generator, sierra-to-casm, etc.). It also includes a full toolchain for Starknet smart contract development, with plugins for contracts, storage, events, and ABI generation. CLI tools (cairo-compile, cairo-run, sierra-compile, starknet-compile, cairo-test, cairo-format) provide end-to-end functionality. The standard library ('corelib'), written in Cairo, provides fundamental types, collections, hash functions, and Starknet-specific primitives. The codebase demonstrates high craftsmanship with clean abstractions, a generic dataflow analysis framework, deterministic hash map utilities, and a reusable graph algorithm library. It is actively maintained with extensive CI, benchmarks, and a golden-file test infrastructure.
The LLM identified 5 files worth highlighting for reuse:
Generic implementation of Tarjan's strongly connected components algorithm via the `GraphNode` trait. Self-contained and extractable to any project requiring SCC computation on directed graphs. Demonstrates clean separation of algorithm from graph representation.
An `OrderedHashMap` that maintains insertion order while providing O(1) lookups. Includes methods like `map`, `aggregate_by`, `iter_sorted`, and `merge`. Designed to eliminate nondeterminism in compiler output due to hash randomization. Easily extractable as a standalone crate.
Defines the `DataflowAnalyzer` trait for both forward and backward dataflow analysis over lowering IR. Supports block-level, statement-level, and edge-level overrides with automatic predecessor/successor tracking and state merging. A reusable pattern for any compiler or static analysis tool needing dataflow passes.
A self-contained test file parser that supports declarative test cases with expected output, diagnostics, and error annotations. Provides `compare_contents_or_fix_with_path` for golden file management. Could be extracted and reused in any Rust project that wants a structured test input format.
Implements the `#[derive(DebugWithDb)]` proc macro, which automatically generates a debug implementation that accepts a database reference. Handles field-level attributes like `hide_field_debug_with_db`. Demonstrates advanced proc macro techniques and is extractable for use in other salsa-based projects.