Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
92.86%
143 / 154
75.00%
12 / 16
 CRAP
0.00%
0 / 1
Comparer
92.86%
143 / 154
75.00%
12 / 16
 87.63
0.00%
0 / 1
 __construct
100.00%
1 / 1
100.00%
1 / 1
 1
 compare
100.00%
18 / 18
100.00%
1 / 1
 2
 isomorphic
100.00%
1 / 1
100.00%
1 / 1
 1
 canonical
100.00%
14 / 14
100.00%
1 / 1
 6
 normaliseNode
100.00%
5 / 5
100.00%
1 / 1
 4
 normaliseTerm
80.00%
4 / 5
0.00%
0 / 1
 4.13
 normaliseLiteral
86.96%
20 / 23
0.00%
0 / 1
 16.57
 canonicalDateTime
0.00%
0 / 6
0.00%
0 / 1
 12
 canonicalDecimal
100.00%
7 / 7
100.00%
1 / 1
 9
 canonicalInteger
80.00%
4 / 5
0.00%
0 / 1
 3.07
 canonicalLabels
100.00%
14 / 14
100.00%
1 / 1
 6
 search
100.00%
13 / 13
100.00%
1 / 1
 6
 serialise
100.00%
7 / 7
100.00%
1 / 1
 4
 smallestTieClass
100.00%
14 / 14
100.00%
1 / 1
 9
 refine
100.00%
18 / 18
100.00%
1 / 1
 9
 termHash
100.00%
3 / 3
100.00%
1 / 1
 2
1<?php
2
3declare(strict_types=1);
4
5namespace LambdaTwelve\OneRecord\JsonLd;
6
7use DateTimeImmutable;
8use DateTimeZone;
9use Exception;
10use LambdaTwelve\OneRecord\Rdf\BlankNode;
11use LambdaTwelve\OneRecord\Rdf\Graph;
12use LambdaTwelve\OneRecord\Rdf\Iri;
13use LambdaTwelve\OneRecord\Rdf\Literal;
14use LambdaTwelve\OneRecord\Rdf\Term;
15use LambdaTwelve\OneRecord\Rdf\Triple;
16use LambdaTwelve\OneRecord\Rdf\Xsd;
17use LambdaTwelve\OneRecord\Spec\Namespaces;
18
19/**
20 * Compares two RDF graphs for isomorphism: equal up to a relabelling of blank
21 * nodes, with literal values normalised.
22 *
23 * This is how the NE:ONE interoperability suite judges "same graph", and how
24 * tests check that a document survives a round trip. Two servers give the
25 * same embedded object different identifiers, so IRIs under configurable
26 * prefixes (`internal:` here, `neone:` there) are compared as blank nodes.
27 *
28 * Blank nodes are labelled by iterated hashing of their neighbourhood; nodes
29 * the hashing cannot tell apart are, for ONE Record's tree-shaped documents,
30 * structurally identical, and get ordinal labels in a stable order.
31 */
32final class Comparer
33{
34    /**
35     * @param list<string> $blankNodePrefixes IRI prefixes whose nodes are compared as blank nodes
36     */
37    public function __construct(
38        private readonly array $blankNodePrefixes = [Namespaces::EMBEDDED],
39        private readonly bool $normaliseNumbers = true,
40        private readonly bool $ignoreLanguageTags = false,
41    ) {}
42
43    public function compare(Graph $left, Graph $right): Diff
44    {
45        $leftCanonical = $this->canonical($left);
46        $rightCanonical = $this->canonical($right);
47        $leftKeys = array_map(static fn(Triple $t): string => $t->toNTriples(), $leftCanonical->sorted());
48        $rightKeys = array_map(static fn(Triple $t): string => $t->toNTriples(), $rightCanonical->sorted());
49        $leftOnly = array_values(array_diff($leftKeys, $rightKeys));
50        $rightOnly = array_values(array_diff($rightKeys, $leftKeys));
51
52        $byKey = static function (Graph $graph): array {
53            $map = [];
54            foreach ($graph as $triple) {
55                $map[$triple->toNTriples()] = $triple;
56            }
57
58            return $map;
59        };
60        $leftMap = $byKey($leftCanonical);
61        $rightMap = $byKey($rightCanonical);
62
63        return new Diff(
64            array_map(static fn(string $k): Triple => $leftMap[$k], $leftOnly),
65            array_map(static fn(string $k): Triple => $rightMap[$k], $rightOnly),
66        );
67    }
68
69    public function isomorphic(Graph $left, Graph $right): bool
70    {
71        return $this->compare($left, $right)->isEqual();
72    }
73
74    /**
75     * The graph with normalised literals and canonical blank node labels.
76     */
77    public function canonical(Graph $graph): Graph
78    {
79        $normalised = new Graph();
80        foreach ($graph as $triple) {
81            $subject = $this->normaliseNode($triple->subject);
82            $object = $this->normaliseTerm($triple->object);
83            $normalised->add(new Triple($subject, $triple->predicate, $object));
84        }
85
86        $labels = $this->canonicalLabels($normalised);
87        if ($labels === []) {
88            return $normalised;
89        }
90        $relabelled = new Graph();
91        foreach ($normalised as $triple) {
92            $subject = $triple->subject instanceof BlankNode ? new BlankNode($labels[$triple->subject->label]) : $triple->subject;
93            $object = $triple->object instanceof BlankNode ? new BlankNode($labels[$triple->object->label]) : $triple->object;
94            $relabelled->add(new Triple($subject, $triple->predicate, $object));
95        }
96
97        return $relabelled;
98    }
99
100    private function normaliseNode(Iri|BlankNode $node): Iri|BlankNode
101    {
102        if ($node instanceof Iri) {
103            foreach ($this->blankNodePrefixes as $prefix) {
104                if (str_starts_with($node->value, $prefix)) {
105                    return new BlankNode('e' . hash('crc32b', $node->value) . '_' . bin2hex(substr($node->value, \strlen($prefix))));
106                }
107            }
108        }
109
110        return $node;
111    }
112
113    private function normaliseTerm(Term $term): Term
114    {
115        if ($term instanceof Iri || $term instanceof BlankNode) {
116            return $this->normaliseNode($term);
117        }
118        if (!$term instanceof Literal) {
119            return $term;
120        }
121
122        return $this->normaliseLiteral($term);
123    }
124
125    /**
126     * The literal in the form this comparer considers canonical: numbers in
127     * JSON-LD's canonical lexical forms, booleans as true/false.
128     */
129    public function normaliseLiteral(Literal $term): Literal
130    {
131        if ($this->ignoreLanguageTags && $term->language !== null) {
132            return Literal::string($term->lexical);
133        }
134        if (!$this->normaliseNumbers) {
135            return $term;
136        }
137
138        // Every integer type is the same number; servers pick one or the other (NE:ONE writes xsd:int).
139        // Which types those are is Xsd's knowledge, not a second list here (R10-003).
140        if (Xsd::isIntegerType($term->datatype)) {
141            return preg_match('/^[+-]?\d+$/', $term->lexical) === 1
142                ? new Literal(self::canonicalInteger($term->lexical), Literal::XSD_INTEGER)
143                : $term;
144        }
145
146        return match ($term->datatype) {
147            Literal::XSD_DOUBLE => is_numeric($term->lexical)
148                ? new Literal(Literal::formatDouble((float) $term->lexical), Literal::XSD_DOUBLE)
149                : $term,
150            // Exact: 9007199254740993 and 9007199254740992 differ, however a float would see them (AR-011).
151            Literal::XSD_DECIMAL => ($decimal = self::canonicalDecimal($term->lexical)) !== null
152                ? new Literal($decimal, Literal::XSD_DECIMAL)
153                : $term,
154            Literal::XSD_BOOLEAN => match ($term->lexical) {
155                '1' => Literal::boolean(true),
156                '0' => Literal::boolean(false),
157                default => $term,
158            },
159            Literal::XSD_DATETIME => self::canonicalDateTime($term),
160            default => $term,
161        };
162    }
163
164    /**
165     * One instant, one lexical form: UTC, no trailing zero fraction
166     * ("2026-10-02T11:00:00.000Z" and "2026-10-02T11:00:00Z" are the same value).
167     */
168    private static function canonicalDateTime(Literal $term): Literal
169    {
170        try {
171            $value = new DateTimeImmutable($term->lexical);
172        } catch (Exception) {
173            return $term;
174        }
175        $utc = $value->setTimezone(new DateTimeZone('UTC'));
176        $fraction = rtrim($utc->format('u'), '0');
177
178        return new Literal($utc->format('Y-m-d\TH:i:s') . ($fraction === '' ? '' : '.' . $fraction) . 'Z', Literal::XSD_DATETIME);
179    }
180
181    /**
182     * The canonical xsd:decimal lexical form: no sign on zero, no leading
183     * zeros, no trailing fraction zeros, no bare dot; null when not a decimal.
184     */
185    private static function canonicalDecimal(string $lexical): ?string
186    {
187        if (preg_match('/^([+-]?)(\d*)(?:\.(\d*))?$/', $lexical, $m) !== 1 || ($m[2] === '' && ($m[3] ?? '') === '')) {
188            return null;
189        }
190        $integer = ltrim($m[2], '0');
191        $fraction = rtrim($m[3] ?? '', '0');
192        if ($integer === '' && $fraction === '') {
193            return '0';
194        }
195
196        return ($m[1] === '-' ? '-' : '') . ($integer === '' ? '0' : $integer) . ($fraction === '' ? '' : '.' . $fraction);
197    }
198
199    private static function canonicalInteger(string $lexical): string
200    {
201        $negative = str_starts_with($lexical, '-');
202        $digits = ltrim(ltrim($lexical, '+-'), '0');
203        if ($digits === '') {
204            return '0';
205        }
206
207        return ($negative ? '-' : '') . $digits;
208    }
209
210    /**
211     * @return array<string, string> original label => canonical label
212     */
213    private function canonicalLabels(Graph $graph): array
214    {
215        /** @var array<string, BlankNode> $blanks */
216        $blanks = [];
217        foreach ($graph as $triple) {
218            foreach ([$triple->subject, $triple->object] as $term) {
219                if ($term instanceof BlankNode) {
220                    $blanks[$term->label] = $term;
221                }
222            }
223        }
224        if ($blanks === []) {
225            return [];
226        }
227
228        // Colour refinement first. Nodes left tied are not necessarily interchangeable (two
229        // cycles of different length can share a colour), so no single choice among them is
230        // canonical. Every choice is explored: individualise each member of the smallest tie
231        // class in turn, refine, recurse, and keep the branch whose relabelled graph sorts
232        // first. That is a canonical form, label-free by construction (AR-010, R2-001); the
233        // cost is exponential in symmetry, hence the budget.
234        $hashes = $this->refine($graph, $blanks, array_fill_keys(array_keys($blanks), ''));
235        $budget = self::SEARCH_BUDGET;
236        [, $hashes] = $this->search($graph, $blanks, $hashes, $budget);
237
238        $labels = [];
239        foreach ($hashes as $label => $hash) {
240            $labels[$label] = 'c' . substr($hash, 0, 24);
241        }
242
243        return $labels;
244    }
245
246    /** Leaves of the individualisation tree the comparer will visit before giving up. */
247    private const int SEARCH_BUDGET = 20000;
248
249    /**
250     * @param array<string, BlankNode> $blanks
251     * @param array<string, string> $hashes a stable colouring
252     * @return array{string, array<string, string>} the smallest serialisation reachable and the colouring that gives it
253     */
254    private function search(Graph $graph, array $blanks, array $hashes, int &$budget): array
255    {
256        $tie = $this->smallestTieClass($hashes);
257        if ($tie === []) {
258            if (--$budget < 0) {
259                throw new ComparisonBudgetExceeded(\sprintf('The graph is too symmetric to canonicalise within %d steps.', self::SEARCH_BUDGET));
260            }
261
262            return [$this->serialise($graph, $hashes), $hashes];
263        }
264        $best = null;
265        foreach ($tie as $member) {
266            $branch = $hashes;
267            // The same mark for every member: the branches must stay comparable with the other graph's.
268            $branch[$member] = hash('sha256', 'individual ' . $branch[$member]);
269            $candidate = $this->search($graph, $blanks, $this->refine($graph, $blanks, $branch), $budget);
270            if ($best === null || strcmp($candidate[0], $best[0]) < 0) {
271                $best = $candidate;
272            }
273        }
274
275        return $best;
276    }
277
278    /**
279     * @param array<string, string> $hashes
280     */
281    private function serialise(Graph $graph, array $hashes): string
282    {
283        $lines = [];
284        foreach ($graph as $triple) {
285            $s = $triple->subject instanceof BlankNode ? '_:' . $hashes[$triple->subject->label] : $triple->subject->toNTriples();
286            $o = $triple->object instanceof BlankNode ? '_:' . $hashes[$triple->object->label] : $triple->object->toNTriples();
287            $lines[] = $s . ' ' . $triple->predicate->toNTriples() . ' ' . $o;
288        }
289        sort($lines, SORT_STRING);
290
291        return implode("\n", $lines);
292    }
293
294    /**
295     * The members of the smallest class of tied nodes (ties broken by hash, so
296     * both graphs pick the same class), or [] when every node is distinct.
297     *
298     * @param array<string, string> $hashes
299     * @return list<string>
300     */
301    private function smallestTieClass(array $hashes): array
302    {
303        $groups = [];
304        foreach ($hashes as $label => $hash) {
305            $groups[$hash][] = $label;
306        }
307        $best = null;
308        foreach ($groups as $hash => $members) {
309            if (\count($members) < 2) {
310                continue;
311            }
312            if ($best === null || \count($members) < \count($groups[$best]) || (\count($members) === \count($groups[$best]) && strcmp((string) $hash, $best) < 0)) {
313                $best = (string) $hash;
314            }
315        }
316        if ($best === null) {
317            return [];
318        }
319        $members = $groups[$best];
320        sort($members, SORT_STRING);
321
322        return $members;
323    }
324
325    /**
326     * Weisfeiler-Lehman style refinement until the partition stops changing.
327     *
328     * @param array<string, BlankNode> $blanks
329     * @param array<string, string> $hashes
330     * @return array<string, string>
331     */
332    private function refine(Graph $graph, array $blanks, array $hashes): array
333    {
334        $distinct = \count(array_unique($hashes));
335        for ($round = 0; $round < \count($blanks) + 1; $round++) {
336            $next = [];
337            foreach ($blanks as $label => $node) {
338                $parts = [$hashes[$label]];
339                foreach ($graph as $triple) {
340                    if ($triple->subject instanceof BlankNode && $triple->subject->label === $label) {
341                        $parts[] = 'o ' . $triple->predicate->value . ' ' . $this->termHash($triple->object, $hashes);
342                    }
343                    if ($triple->object instanceof BlankNode && $triple->object->label === $label) {
344                        $parts[] = 'i ' . $triple->predicate->value . ' ' . $this->termHash($triple->subject, $hashes);
345                    }
346                }
347                sort($parts, SORT_STRING);
348                $next[$label] = hash('sha256', implode("\n", $parts));
349            }
350            $hashes = $next;
351            $nowDistinct = \count(array_unique($hashes));
352            if ($nowDistinct === $distinct) {
353                break;
354            }
355            $distinct = $nowDistinct;
356        }
357
358        return $hashes;
359    }
360
361
362    /**
363     * @param array<string, string> $hashes
364     */
365    private function termHash(Term $term, array $hashes): string
366    {
367        if ($term instanceof BlankNode) {
368            return 'b:' . $hashes[$term->label];
369        }
370
371        return $term->toNTriples();
372    }
373}