fqqdk/planarity (0.1.0)
Installation
{
"repositories": [{
"type": "composer",
"url": "composer require fqqdk/planarity:0.1.0About this package
planarity
A minimal PHP extension exposing one function, planarity(), backed by the vendored
Boyer–Myrvold reference (eapsuite/, BSD — see eapsuite/VENDOR.md). It answers: is a graph
planar, and — when it is not — what is the Kuratowski witness that obstructs it.
planarity(int $n, array $edges): array
// $n — vertex count; vertices are 0 .. n-1
// $edges — list of [u, v] integer pairs (0-based, undirected). PREREQUISITE: a SIMPLE graph —
// unique undirected pairs, no parallel/duplicate edges. Self-loops are the one
// exception: they are dropped for you. Duplicate edges are the caller's responsibility;
// passing them is out of contract and may raise (Boyer's embedder rejects multigraphs).
// → ['planar' => bool, 'witness' => list<[u,v]>]
// witness = the isolated Kuratowski subgraph (K5 / K3,3 subdivision) when non-planar — the
// exact obstructing vertices, deduped & 0-based; [] when planar.
// throws ValueError on malformed input (endpoint out of range, n out of range)
Why a vendored C extension, and how it's kept safe
We reuse Boyer's proven algorithm rather than hand-roll planarity (which is error-prone, especially the Kuratowski extraction). The safety bargain for C we did not author:
- Our surface is tiny. One function, bounded input (
PLANARITY_MAX_N), a single cleanup path (goto cleanup→ onegp_Free) so no allocation can leak.planarity.cis the only authored C; the vendored library is compiled unmodified. - Proven with sanitizers, not by eye. ASan (overflow / use-after-free / invalid-free), UBSan (undefined behaviour), and LSan (leaks) run over the exercised paths and must be clean.
Build (host)
phpize && ./configure --enable-planarity && make
Two PHP installs may coexist on a dev host. The extension loads in the distro php
(/usr/bin/php8.5); a static /usr/local/bin/php build can have dynamic loading disabled. Use
the binary that loads it:
/usr/bin/php8.5 -d extension="$(pwd)/modules/planarity.so" --ri planarity
Tests
The behavioural suite is .phpt (PHP's native extension test format) under tests/, run by the
run-tests.php harness that phpize drops in — no phpunit/composer needed. It covers the planar
and non-planar verdicts (K5, K3,3, K6, Petersen, subdivisions — witnesses checked structurally as
Kuratowski subdivisions, not by brittle edge-for-edge comparison), the trivial/boundary cases,
input coercion, and every ValueError/TypeError path.
make test # after phpize && ./configure --enable-planarity && make
On a host without a build toolchain, the bundled image builds the extension and runs the suite:
docker build -t php-planarity .
docker run --rm php-planarity # runs `make test`
Note the contract: edges must form a simple graph (unique undirected pairs). Self-loops are dropped for you; passing parallel/duplicate edges is out of contract and may raise.
Safety proofs
Leaks / UB — the pure-C harness (tests/leakcheck.c), isolating the call sequence from
PHP's allocator so LSan runs with no host noise:
SRCS=$(find eapsuite/graphLib -name '*.c' | tr '\n' ' ')
INCS="-Ieapsuite/graphLib -Ieapsuite/graphLib/extensionSystem -Ieapsuite/graphLib/homeomorphSearch \
-Ieapsuite/graphLib/io -Ieapsuite/graphLib/lowLevelUtils -Ieapsuite/graphLib/planarityRelated"
gcc -fsanitize=address,undefined -g -O1 $INCS tests/leakcheck.c $SRCS -o /tmp/leakcheck
ASAN_OPTIONS=detect_leaks=1:halt_on_error=1 UBSAN_OPTIONS=halt_on_error=1 /tmp/leakcheck
ASan over the real extension (catches UB/overflow in the PHP-facing path; leaks off because a non-ASan php is noisy):
make clean
make CFLAGS="-fsanitize=address -fno-omit-frame-pointer -g -O1" EXTRA_LDFLAGS="-fsanitize=address"
LD_PRELOAD="$(gcc -print-file-name=libasan.so)" ASAN_OPTIONS=detect_leaks=0:halt_on_error=1 \
/usr/bin/php8.5 -d extension="$(pwd)/modules/planarity.so" <smoke script>
Valgrind over the extension. Disable Zend's pooled allocator — it frees everything at
request-end and would mask a real leak. Run it over the isolated exercise
(tests/valgrind-check.php), NOT phpunit: phpunit leaves its own framework objects unfreed at
shutdown, which Valgrind reports as "definitely lost" (an all-PHP-VM stack with no extension
frames — noise).
USE_ZEND_ALLOC=0 valgrind --leak-check=full --show-leak-kinds=definite,indirect \
--error-exitcode=99 php tests/valgrind-check.php
Proven: 0 errors / 0 bytes lost across planar, witness, and both error paths.
Dependencies
Dependencies
| ID | Version |
|---|---|
| php | >=8.1 |