deterministic_turtle is not idempotent on graphs containing shared RDF collections

[jdsika]

deterministic_turtle is not idempotent on at least one real graph: canonicalizing its own
output produces a different file, and the process does not converge.

Symptom

pass 0 (as written)  sha=8a4bcbd8c0de4252  229326 bytes  5115 triples
pass 1               sha=f1eddc962da07919  230308 bytes  5267 triples
pass 2               sha=97f31502b3284172  231294 bytes  5419 triples
pass 3               sha=cecca06d8634020e  232274 bytes  5571 triples
pass 4               sha=4ba887b9604efdd2  233254 bytes  5723 triples

+152 triples per pass, indefinitely. Comparing predicate histograms between passes, only
collection plumbing changes:

predicate	pass 1	pass 2
rdf:first	352	428
rdf:rest	352	428

Every other predicate is unchanged, so no statement is gained or lost — the collections are
being duplicated on each round trip.

Why it matters

This breaks the property the library exists to provide. A consumer that canonicalizes generated
RDF and commits it cannot verify the result: a CI check of the form "re-canonicalize and compare
bytes" fails on a file that was just canonicalized. That is exactly how we use it — see
ASCS-eV/asam-openx-standards, scripts/check_canonical.py.

Reproduction

The graph is a SHACL shapes file produced by shacl-play owl2shacl, attached below. It contains
81 sh:in constraints referencing 51 distinct collection nodes — 16 of those are referenced by
more than one property shape, with up to 5 references each.

from rdflib import Graph
from diffable_rdf import deterministic_turtle

cur = open("repro-shacl.ttl", "rb").read()
for i in range(5):
    g = Graph().parse(data=cur, format="turtle")
    print(i, len(g))
    nxt = deterministic_turtle(g).encode()
    if nxt == cur:
        print("fixed point")
        break
    cur = nxt

What I could not narrow down

Shared collections alone are not sufficient to trigger it. One collection node shared by
two, three, four or five subjects converges after a single pass:

N=2: converges  triples per pass: [6, 6]
N=3: converges  triples per pass: [7, 7]
N=4: converges  triples per pass: [8, 8]
N=5: converges  triples per pass: [9, 9]

So does the case of several subjects each owning an identical-content collection. The trigger is
therefore narrower than plain sharing — plausibly an interaction between the
Weisfeiler-Lehman blank-node hashing and collections whose cells are structurally
indistinguishable, but I did not isolate it. The attached file reproduces it reliably.

Environment

diffable-rdf 0.0.1, rdflib 7.6.0, pyoxigraph 0.5.9, Python 3.12.

Suggestion

Whatever the cause, a regression test asserting deterministic_turtle reaches a fixed point in
one pass would be worth having for any graph containing rdf:Lists — that is the invariant the
library promises and the one that broke.

[jdsika]

Root cause found, and it is not the WL hashing this issue suspected.

On the attached graph both earlier phases are faithful: RDFC-1.0 preserves all 4963 triples, and
the Weisfeiler-Lehman relabelling maps 276 blank nodes to 276 distinct labels, collapsing nothing.
The defect is entirely in the final rdflib serialization.

rdflib's isValidList checks that every cell of an rdf:List carries exactly two predicates, but
not how many statements point into the chain. So:

• a shared interior cell is consumed by an inline ( … ) and the other reference is left
  undefined — the list is silently lost, which is worse than the orphans this issue reported
• a shared head is written inline at every reference, so re-parsing yields one private copy
  per reference and the triple count grows, which is the +152 per pass observed here

Both are fixed in #2 by verifying the round trip and falling back to explicit
rdf:first/rdf:rest statements where the inline form cannot represent the collections.

On this graph: 4963 triples in, 4963 out, no orphaned cells, fixed point on the first pass,
isomorphic to the input, and all 81 sh:in constraints still resolving to their 452 literals.

The suggestion in this issue — a regression test asserting a fixed point for graphs containing
rdf:Lists — is included, alongside property tests for losslessness, idempotence,
label-independence and order-independence over 40 seeded graphs. Against the unfixed library that
suite fails 20 of 188.

[jdsika]

Fixed in #2 and released as v0.0.2 (now on PyPI).

deterministic_turtle now verifies that its output round-trips before returning it, and falls back to a serializer that states list structures explicitly when the compact ( ... ) syntax cannot express the graph. If neither form round-trips it raises rather than returning a lossy result.

The invariants are now enforced by a property-based harness over seeded random graphs and six hand-built collection-sharing arrangements — lossless, idempotent, blank-node-label-independent, and triple-order-independent — plus dangling-reference, list-cell-count and ten-pass byte-drift checks. Suite is 188 tests, green on Python 3.10–3.13.