Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
98.44%
189 / 192
84.21%
16 / 19
 CRAP
0.00%
0 / 1
ChangeBuilder
98.44%
189 / 192
84.21%
16 / 19
 98
0.00%
0 / 1
 __construct
100.00%
1 / 1
100.00%
1 / 1
 1
 diff
94.74%
18 / 19
0.00%
0 / 1
 4.00
 correspond
100.00%
22 / 22
100.00%
1 / 1
 13
 pair
100.00%
2 / 2
100.00%
1 / 1
 1
 slots
100.00%
7 / 7
100.00%
1 / 1
 4
 predicates
100.00%
6 / 6
100.00%
1 / 1
 5
 emit
100.00%
32 / 32
100.00%
1 / 1
 12
 linkTo
100.00%
16 / 16
100.00%
1 / 1
 8
 nodeObject
100.00%
1 / 1
100.00%
1 / 1
 2
 deleteUnreachable
100.00%
21 / 21
100.00%
1 / 1
 11
 reachableEmbedded
100.00%
13 / 13
100.00%
1 / 1
 7
 partition
100.00%
7 / 7
100.00%
1 / 1
 5
 keyed
100.00%
6 / 6
100.00%
1 / 1
 3
 plainObject
80.00%
4 / 5
0.00%
0 / 1
 5.20
 datatypeForNode
88.89%
8 / 9
0.00%
0 / 1
 5.03
 signatureOf
100.00%
1 / 1
100.00%
1 / 1
 1
 signature
100.00%
13 / 13
100.00%
1 / 1
 4
 collect
100.00%
6 / 6
100.00%
1 / 1
 6
 sameTypes
100.00%
5 / 5
100.00%
1 / 1
 1
1<?php
2
3declare(strict_types=1);
4
5namespace LambdaTwelve\OneRecord\Change;
6
7use LambdaTwelve\OneRecord\JsonLd\Comparer;
8use LambdaTwelve\OneRecord\Model\LogisticsObject;
9use LambdaTwelve\OneRecord\Model\ModelException;
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\Vocabulary\Generated\Cargo;
17use LambdaTwelve\OneRecord\Vocabulary\PropertyKind;
18use LambdaTwelve\OneRecord\Vocabulary\Vocabulary;
19use LogicException;
20
21/**
22 * Computes the api:Change that turns one version of a logistics object into
23 * another: what a host sends when it republishes updated data, and what a
24 * partner sends to request a correction.
25 *
26 * Two phases, because an embedded node is one node however many links reach
27 * it (R2-011, R3-001, R4-001). First a correspondence between the old and the
28 * new embedded nodes is built over the whole graphs: unchanged content pairs
29 * up first, in every slot, so an unchanged branch is never sacrificed to an
30 * edit elsewhere; then a slot left with exactly one old and one new node of
31 * the same type pairs them for an in-place edit (spec example C3). Only then
32 * are operations emitted from that correspondence: plain values as
33 * DELETE/ADD pairs, a link deleted where its target no longer corresponds, a
34 * link added to the node that represents the target (an existing node edited
35 * to match it, or one blank node introduced once for it, C2), and an old
36 * node's own triples deleted once when no surviving link reaches it (C4).
37 * Logistics events are never part of a change; the spec forbids it.
38 */
39final class ChangeBuilder
40{
41    private int $blankCounter = 0;
42
43    private ?Iri $root = null;
44
45    /** @var array<string, Iri|BlankNode> old embedded node => the new node it corresponds to */
46    private array $forward = [];
47
48    /** @var array<string, Iri|BlankNode> new embedded node => the old node that represents it */
49    private array $backward = [];
50
51    /** @var array<string, BlankNode> new embedded node no old node represents => the blank node introducing it */
52    private array $introduced = [];
53
54    /** @var array<string, true> old nodes whose pair's operations were emitted */
55    private array $emitted = [];
56
57    /** @var array<string, string> content signatures of old nodes */
58    private array $fromSignatures = [];
59
60    /** @var array<string, string> content signatures of new nodes */
61    private array $toSignatures = [];
62
63    public function __construct(
64        private readonly ?Vocabulary $vocabulary = null,
65        private readonly ?Comparer $comparer = null,
66    ) {}
67
68    /**
69     * @param int $revision the current revision of $from, which the change applies to
70     * @return ?Change null when the two versions are the same
71     */
72    public function diff(LogisticsObject $from, LogisticsObject $to, int $revision, ?string $description = null): ?Change
73    {
74        if (!$from->iri->equals($to->iri)) {
75            throw new ModelException(\sprintf('Cannot diff "%s" against "%s": a change applies to one logistics object.', $from->iri->value, $to->iri->value));
76        }
77        // Servers may list inferred superclasses in @type (NE:ONE does; spec question 21), so only the
78        // most specific classes decide whether the type changed. Type triples are never diffed: the
79        // spec gives a Change no way to retype an object, and the applier refuses such operations.
80        $vocabulary = $this->vocabulary ?? Vocabulary::default();
81        if ($vocabulary->mostSpecific($from->types()) !== $vocabulary->mostSpecific($to->types())) {
82            throw ChangeException::because('Invalid resource', 'The type of a logistics object cannot be changed with a Change.');
83        }
84
85        $this->blankCounter = 0;
86        $this->forward = [];
87        $this->backward = [];
88        $this->introduced = [];
89        $this->emitted = [];
90        $this->fromSignatures = [];
91        $this->toSignatures = [];
92        $this->root = $from->iri;
93
94        $this->correspond($from->graph, $to->graph, $from->iri, $to->iri);
95        $operations = $this->emit($from->graph, $to->graph, $from->iri, $to->iri);
96        $operations = [...$operations, ...$this->deleteUnreachable($from->graph, $from->iri, $operations)];
97        if ($operations === []) {
98            return null;
99        }
100
101        return new Change($from->iri, $revision, $operations, $description);
102    }
103
104    // --- Phase 1: correspondence ------------------------------------------
105
106    private function correspond(Graph $fromGraph, Graph $toGraph, Iri $fromRoot, Iri $toRoot): void
107    {
108        $this->pair($fromRoot, $toRoot);
109        $queue = [[$fromRoot, $toRoot]];
110        while ($queue !== []) {
111            [$old, $new] = array_shift($queue);
112            $slots = $this->slots($fromGraph, $toGraph, $old, $new);
113            // Unchanged content first, in every slot of this node, so an edit in one slot can never
114            // take a node another slot still needs as it is (R4-001).
115            foreach ($slots as [$olds, $news]) {
116                foreach ($news as $candidate) {
117                    if (isset($this->backward[$candidate->toNTriples()])) {
118                        continue;
119                    }
120                    $signature = $this->signatureOf($toGraph, $candidate, $this->toSignatures);
121                    foreach ($olds as $existing) {
122                        if (!isset($this->forward[$existing->toNTriples()]) && $this->signatureOf($fromGraph, $existing, $this->fromSignatures) === $signature) {
123                            $this->pair($existing, $candidate);
124                            $queue[] = [$existing, $candidate];
125                            break;
126                        }
127                    }
128                }
129            }
130            // Then one unmatched old against one unmatched new of the same type: an in-place edit (C3).
131            foreach ($slots as [$olds, $news]) {
132                $unmatchedOld = array_values(array_filter($olds, fn(Iri|BlankNode $n): bool => !isset($this->forward[$n->toNTriples()])));
133                $unmatchedNew = array_values(array_filter($news, fn(Iri|BlankNode $n): bool => !isset($this->backward[$n->toNTriples()])));
134                if (\count($unmatchedOld) === 1 && \count($unmatchedNew) === 1 && $unmatchedOld[0] instanceof Iri
135                    && $this->sameTypes($fromGraph, $unmatchedOld[0], $toGraph, $unmatchedNew[0])) {
136                    $this->pair($unmatchedOld[0], $unmatchedNew[0]);
137                    $queue[] = [$unmatchedOld[0], $unmatchedNew[0]];
138                }
139            }
140        }
141    }
142
143    private function pair(Iri|BlankNode $old, Iri|BlankNode $new): void
144    {
145        $this->forward[$old->toNTriples()] = $new;
146        $this->backward[$new->toNTriples()] = $old;
147    }
148
149    /**
150     * The embedded objects of two corresponding nodes, per predicate.
151     *
152     * @return array<string, array{list<Iri|BlankNode>, list<Iri|BlankNode>}>
153     */
154    private function slots(Graph $fromGraph, Graph $toGraph, Iri|BlankNode $old, Iri|BlankNode $new): array
155    {
156        $slots = [];
157        foreach ($this->predicates($fromGraph, $toGraph, $old, $new) as $predicate) {
158            [, $oldEmbedded] = $this->partition($fromGraph, $fromGraph->objects($old, $predicate));
159            [, $newEmbedded] = $this->partition($toGraph, $toGraph->objects($new, $predicate));
160            if ($oldEmbedded !== [] || $newEmbedded !== []) {
161                $slots[$predicate->value] = [$oldEmbedded, $newEmbedded];
162            }
163        }
164
165        return $slots;
166    }
167
168    /**
169     * @return list<Iri>
170     */
171    private function predicates(Graph $fromGraph, Graph $toGraph, Iri|BlankNode $old, Iri|BlankNode $new): array
172    {
173        $predicates = [];
174        foreach ([...$fromGraph->about($old), ...$toGraph->about($new)] as $triple) {
175            $predicates[$triple->predicate->value] = $triple->predicate;
176        }
177        ksort($predicates, SORT_STRING);
178        $isRoot = $this->root !== null && $old->equals($this->root);
179
180        return array_values(array_filter($predicates, static fn(Iri $p): bool => $p->value !== Cargo::events && !($isRoot && $p->value === Graph::RDF_TYPE)));
181    }
182
183    // --- Phase 2: operations ------------------------------------------------
184
185    /**
186     * @return list<Operation>
187     */
188    private function emit(Graph $fromGraph, Graph $toGraph, Iri|BlankNode $old, Iri|BlankNode $new): array
189    {
190        $key = $old->toNTriples();
191        if (isset($this->emitted[$key])) {
192            return [];
193        }
194        $this->emitted[$key] = true;
195        $operations = [];
196        $pairs = [];
197        foreach ($this->predicates($fromGraph, $toGraph, $old, $new) as $predicate) {
198            [$oldPlain, $oldEmbedded] = $this->partition($fromGraph, $fromGraph->objects($old, $predicate));
199            [$newPlain, $newEmbedded] = $this->partition($toGraph, $toGraph->objects($new, $predicate));
200
201            // Plain values: set difference on their N-Triples form (numbers normalised).
202            $oldKeys = $this->keyed($oldPlain);
203            $newKeys = $this->keyed($newPlain);
204            foreach (array_diff_key($oldKeys, $newKeys) as $term) {
205                $operations[] = Operation::delete($old, $predicate, $this->plainObject($fromGraph, $predicate, $term));
206            }
207            foreach (array_diff_key($newKeys, $oldKeys) as $term) {
208                $operations[] = Operation::add($old, $predicate, $this->plainObject($toGraph, $predicate, $term));
209            }
210
211            // Links: one survives when its target corresponds to a node in the new slot.
212            $wanted = [];
213            foreach ($newEmbedded as $node) {
214                $wanted[$node->toNTriples()] = true;
215            }
216            $covered = [];
217            foreach ($oldEmbedded as $node) {
218                $target = $this->forward[$node->toNTriples()] ?? null;
219                if ($target === null || !isset($wanted[$target->toNTriples()])) {
220                    $operations[] = Operation::delete($old, $predicate, $this->nodeObject($fromGraph, $predicate, $node, $node));
221                    continue;
222                }
223                $covered[$target->toNTriples()] = true;
224                $pairs[] = [$node, $target];
225            }
226            foreach ($newEmbedded as $node) {
227                if (!isset($covered[$node->toNTriples()])) {
228                    $operations = [...$operations, ...$this->linkTo($toGraph, $old, $predicate, $node)];
229                }
230            }
231        }
232        foreach ($pairs as [$oldChild, $newChild]) {
233            $operations = [...$operations, ...$this->emit($fromGraph, $toGraph, $oldChild, $newChild)];
234        }
235
236        return $operations;
237    }
238
239    /**
240     * Link a subject to the node that represents a new embedded node: the old
241     * node edited to match it, the blank node already introduced for it, or a
242     * fresh blank node with its triples (spec example C2), introduced once.
243     *
244     * @return list<Operation>
245     */
246    private function linkTo(Graph $toGraph, Iri|BlankNode $subject, Iri $predicate, Iri|BlankNode $node): array
247    {
248        $key = $node->toNTriples();
249        $existing = $this->backward[$key] ?? null;
250        if ($existing instanceof Iri) {
251            return [Operation::add($subject, $predicate, $this->nodeObject($toGraph, $predicate, $node, $existing))];
252        }
253        if (isset($this->introduced[$key])) {
254            return [Operation::add($subject, $predicate, $this->nodeObject($toGraph, $predicate, $node, $this->introduced[$key]))];
255        }
256        $blank = $this->introduced[$key] = new BlankNode('b' . $this->blankCounter++);
257        $operations = [Operation::add($subject, $predicate, $this->nodeObject($toGraph, $predicate, $node, $blank))];
258        foreach ($toGraph->about($node) as $triple) {
259            if ($triple->predicate->value === Graph::RDF_TYPE) {
260                continue;
261            }
262            $object = $triple->object;
263            if (($object instanceof BlankNode || $object instanceof Iri) && LogisticsObject::isEmbeddedIn($toGraph, $object, $this->root)) {
264                $operations = [...$operations, ...$this->linkTo($toGraph, $blank, $triple->predicate, $object)];
265            } else {
266                $operations[] = Operation::add($blank, $triple->predicate, $this->plainObject($toGraph, $triple->predicate, $object));
267            }
268        }
269
270        return $operations;
271    }
272
273    /**
274     * An operation object for a link: the class of the node in its graph, the identity of its representation.
275     */
276    private function nodeObject(Graph $graph, Iri $predicate, Iri|BlankNode $node, Iri|BlankNode $representation): OperationObject
277    {
278        return new OperationObject($this->datatypeForNode($graph, $predicate, $node), $representation instanceof Iri ? $representation->value : $representation->toNTriples());
279    }
280
281    /**
282     * Spec example C4, decided on the whole graph: once the link deletions are
283     * known, every embedded node of the old graph that no surviving link
284     * reaches loses its own triples, once, however many links used to reach
285     * it. A node still reached from elsewhere keeps them (R3-001).
286     *
287     * @param list<Operation> $operations
288     * @return list<Operation>
289     */
290    private function deleteUnreachable(Graph $from, Iri $root, array $operations): array
291    {
292        $deletedLinks = [];
293        foreach ($operations as $operation) {
294            if ($operation->kind === OperationKind::Delete && !$operation->object->isLiteral()) {
295                $deletedLinks[$operation->subject->toNTriples() . ' ' . $operation->predicate->value . ' ' . $operation->object->value] = true;
296            }
297        }
298        $surviving = new Graph();
299        foreach ($from as $triple) {
300            $object = $triple->object;
301            if ($object instanceof Iri && isset($deletedLinks[$triple->subject->toNTriples() . ' ' . $triple->predicate->value . ' ' . $object->value])) {
302                continue;
303            }
304            $surviving->add($triple);
305        }
306        $before = $this->reachableEmbedded($from, $root);
307        $after = $this->reachableEmbedded($surviving, $root);
308        $deletes = [];
309        foreach ($before as $key => $node) {
310            if (isset($after[$key])) {
311                continue;
312            }
313            foreach ($surviving->about($node) as $triple) {
314                if ($triple->predicate->value === Graph::RDF_TYPE) {
315                    continue;
316                }
317                $deletes[] = Operation::delete($node, $triple->predicate, $this->plainObject($from, $triple->predicate, $triple->object));
318            }
319        }
320
321        return $deletes;
322    }
323
324    /**
325     * @return array<string, Iri|BlankNode> embedded nodes reachable from the root, by N-Triples key
326     */
327    private function reachableEmbedded(Graph $graph, Iri $root): array
328    {
329        $seen = [$root->toNTriples() => true];
330        $found = [];
331        $queue = [$root];
332        while ($queue !== []) {
333            $node = array_shift($queue);
334            foreach ($graph->about($node) as $triple) {
335                $object = $triple->object;
336                $key = $object->toNTriples();
337                if (($object instanceof BlankNode || $object instanceof Iri) && !isset($seen[$key]) && LogisticsObject::isEmbeddedIn($graph, $object, $root)) {
338                    $seen[$key] = true;
339                    $found[$key] = $object;
340                    $queue[] = $object;
341                }
342            }
343        }
344
345        return $found;
346    }
347
348    // --- Helpers --------------------------------------------------------------
349
350    /**
351     * @param list<Term> $terms
352     * @return array{list<Term>, list<Iri|BlankNode>}
353     */
354    private function partition(Graph $graph, array $terms): array
355    {
356        $plain = [];
357        $embedded = [];
358        foreach ($terms as $term) {
359            if (($term instanceof BlankNode || $term instanceof Iri) && LogisticsObject::isEmbeddedIn($graph, $term, $this->root)) {
360                $embedded[] = $term;
361            } else {
362                $plain[] = $term;
363            }
364        }
365
366        return [$plain, $embedded];
367    }
368
369    /**
370     * @param list<Term> $terms
371     * @return array<string, Term>
372     */
373    private function keyed(array $terms): array
374    {
375        $comparer = $this->comparer ?? new Comparer();
376        $keyed = [];
377        foreach ($terms as $term) {
378            $key = $term instanceof Literal ? $comparer->normaliseLiteral($term)->toNTriples() : $term->toNTriples();
379            $keyed[$key] = $term;
380        }
381
382        return $keyed;
383    }
384
385    private function plainObject(Graph $graph, Iri $predicate, Term $term): OperationObject
386    {
387        if ($term instanceof Literal) {
388            return OperationObject::literal($term);
389        }
390        if (!$term instanceof Iri && !$term instanceof BlankNode) {
391            throw new LogicException('Unexpected term ' . $term::class);
392        }
393
394        return new OperationObject($this->datatypeForNode($graph, $predicate, $term), $term instanceof Iri ? $term->value : $term->toNTriples());
395    }
396
397    /**
398     * The "datatype" of a node-valued operation object is the class of the
399     * node: its declared type when the graph has one, else the property's
400     * range from the ontology, else cargo:LogisticsObject.
401     */
402    private function datatypeForNode(Graph $graph, Iri $predicate, Iri|BlankNode $node): string
403    {
404        $types = array_map(static fn(Iri $t): string => $t->value, $graph->typesOf($node));
405        if ($types !== []) {
406            $specific = ($this->vocabulary ?? Vocabulary::default())->mostSpecific($types);
407            sort($specific, SORT_STRING);
408
409            return $specific[0];
410        }
411        $info = ($this->vocabulary ?? Vocabulary::default())->property($predicate->value);
412        if ($info !== null && $info->kind === PropertyKind::Object && $info->ranges !== []) {
413            return $info->ranges[0];
414        }
415
416        return Cargo::LogisticsObject;
417    }
418
419    /**
420     * @param array<string, string> $cache
421     */
422    private function signatureOf(Graph $graph, Iri|BlankNode $node, array &$cache): string
423    {
424        return $cache[$node->toNTriples()] ??= $this->signature($graph, $node);
425    }
426
427    private function signature(Graph $graph, Iri|BlankNode $node): string
428    {
429        $comparer = $this->comparer ?? new Comparer();
430        $sub = new Graph();
431        $seen = [];
432        $this->collect($graph, $node, $sub, $seen);
433        // Re-root at a fixed blank label so identical content under different ids hashes the same.
434        $rerooted = new Graph();
435        $marker = new BlankNode('root');
436        foreach ($sub as $triple) {
437            $rerooted->add(new Triple(
438                $triple->subject->equals($node) ? $marker : $triple->subject,
439                $triple->predicate,
440                $triple->object->equals($node) ? $marker : $triple->object,
441            ));
442        }
443
444        return implode("\n", array_map(static fn(Triple $t): string => $t->toNTriples(), $comparer->canonical($rerooted)->sorted()));
445    }
446
447    /**
448     * @param array<string, true> $seen
449     */
450    private function collect(Graph $graph, Iri|BlankNode $node, Graph $into, array &$seen): void
451    {
452        $seen[$node->toNTriples()] = true;
453        foreach ($graph->about($node) as $triple) {
454            $into->add($triple);
455            $object = $triple->object;
456            if (($object instanceof BlankNode || $object instanceof Iri) && !isset($seen[$object->toNTriples()]) && LogisticsObject::isEmbeddedIn($graph, $object, $this->root)) {
457                $this->collect($graph, $object, $into, $seen);
458            }
459        }
460    }
461
462    private function sameTypes(Graph $a, Iri|BlankNode $nodeA, Graph $b, Iri|BlankNode $nodeB): bool
463    {
464        $typesA = array_map(static fn(Iri $t): string => $t->value, $a->typesOf($nodeA));
465        $typesB = array_map(static fn(Iri $t): string => $t->value, $b->typesOf($nodeB));
466        sort($typesA, SORT_STRING);
467        sort($typesB, SORT_STRING);
468
469        return $typesA === $typesB;
470    }
471}