Skip to content

Commit 8e7e660

Browse files
committed
🔑 Make a Git operation's durable identity injective
Architecture review of 6451b53: two Repository records differing only between `requestedBase` absent and `requestedBase` holding the character the encoding used for absence produced the same `describeSwitch()` effect name. Replay compares type and name, and neither the result protocol nor placement carries the record, so a replaced context could have been handed a transition recorded for a different record — on the one path where nothing is authenticated, because nothing is executed. `gitOperationFingerprint()` replaces the sentinel-and-separator encoding for Git operations: each value is length-prefixed and absence is a marker no encoded value can produce, so no arrangement of values can be read as another. Any character may appear in a branch, a base, a name or a path, which is exactly why a reserved one cannot carry the structure. It is a new function rather than a change to `fingerprintOf()`, whose digests are already part of retained Repository and Worktree identity. `Git.Switch` is new here, so its own encoding costs no compatibility. Two regressions. One records a legitimate switch under a record with no requested base, then replays the same expansion under a context differing only by that member holding the old absence sentinel: the journal diverges at the position it reaches, no Git runs, no result is appended and the frontier does not move. The other holds the encoding itself to injectivity across absence, the old separator and sentinel characters, length-prefix-shaped content and the empty string — so the property is the claim rather than the one example.
1 parent 1ec58fc commit 8e7e660

3 files changed

Lines changed: 195 additions & 10 deletions

File tree

‎packages/workflow/src/deno/composition/operations.ts‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,7 @@
5353

5454
import { scoped, type Operation, until } from "effection";
5555
import { lstat } from "@effectionx/fs";
56+
import { createHash } from "node:crypto";
5657
import type { Stats } from "node:fs";
5758
import { realpath } from "node:fs/promises";
5859
import type { Json } from "@executablemd/durable-streams";
@@ -95,6 +96,33 @@ import { attempted, type CompositionOutcome, type MutationContext } from "./effe
9596
import { repositoryDisagreement } from "./repository.ts";
9697
import { worktreeDisagreement } from "./worktree.ts";
9798

99+
/**
100+
* The digest one Git operation's durable identity is built from.
101+
*
102+
* Injective, because the values it covers include a whole retained record and a
103+
* document's own strings, and durable identity is what decides whether a
104+
* recorded result may be handed back for an invocation. Two different
105+
* observations that digested alike would let a replay return a transition
106+
* authorized for one of them to the other — without the live path, where the
107+
* observation is authenticated, ever running.
108+
*
109+
* So each value is length-prefixed rather than joined by a separator, and
110+
* absence is a marker no encoded value can produce. Any character may appear in
111+
* a branch, a base, a name or a path — including the ones a separator scheme
112+
* would reserve — and a length prefix says exactly how much of what follows
113+
* belongs to this value, so no arrangement of values can be read as another.
114+
*
115+
* This is deliberately its own encoding rather than a change to
116+
* `fingerprintOf()`, whose digests are already part of retained Repository and
117+
* Worktree identity in this run's history.
118+
*/
119+
export function gitOperationFingerprint(values: readonly (string | null)[]): string {
120+
const canonical = values
121+
.map((value) => (value === null ? "-" : `${value.length}:${value}`))
122+
.join("");
123+
return createHash("sha256").update(canonical, "utf8").digest("hex").slice(0, 16);
124+
}
125+
98126
/** What a component supplies about where its operation belongs. */
99127
export interface GitOperationRequest {
100128
/** The whole Repository record the component observed, to be compared. */

‎packages/workflow/src/deno/composition/switch.ts‎

Lines changed: 5 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -28,14 +28,9 @@ import { SWITCH } from "../../composition/components/GitSwitch.ts";
2828
import type { WorkflowRunDatabase } from "../../storage/api.ts";
2929
import { branchExists, resolveBaseCommit, resolveCommit, switchBranch } from "./git.ts";
3030
import type { RepositoryHost } from "./host.ts";
31-
import {
32-
fingerprintOf,
33-
settled,
34-
type CompositionOutcome,
35-
type MutationContext,
36-
} from "./effects.ts";
31+
import { settled, type CompositionOutcome, type MutationContext } from "./effects.ts";
3732
import { gitRefused } from "./refusals.ts";
38-
import { performGitOperation, type GitCheckout } from "./operations.ts";
33+
import { gitOperationFingerprint, performGitOperation, type GitCheckout } from "./operations.ts";
3934
import { placedCheckout } from "./identity.ts";
4035

4136
/** The effect type one branch change is recorded under. */
@@ -55,8 +50,9 @@ export function* describeSwitch(request: GitSwitchRequest): Operation<EffectDesc
5550
// The whole observation, not only what it asked for. The record a document was
5651
// written against is part of what this effect is: replaying a result recorded
5752
// for one Repository under an observation naming another would hand back a
58-
// transition that never described this invocation.
59-
const configuration = fingerprintOf([
53+
// transition that never described this invocation — and the encoding is
54+
// injective, so no two observations can arrive at one name.
55+
const configuration = gitOperationFingerprint([
6056
request.repository.name,
6157
request.repository.locatorFingerprint,
6258
request.repository.requestedBase,

‎packages/workflow/tests/git-switch-durability.test.ts‎

Lines changed: 162 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,16 @@ import { open } from "node:fs/promises";
2121
import { tmpdir } from "node:os";
2222
import { scoped, spawn, suspend, until, withResolvers } from "effection";
2323
import type { Operation } from "effection";
24-
import { GitOperationProtocolError } from "../src/composition/errors.ts";
24+
import { GitOperationError, GitOperationProtocolError } from "../src/composition/errors.ts";
25+
import { DivergenceError } from "@executablemd/durable-streams";
26+
import { RepositoryContext } from "../src/composition/context.ts";
27+
import type { RepositoryRecord } from "../src/composition/records.ts";
28+
import { gitOperationFingerprint } from "../src/deno/composition/operations.ts";
29+
import { withWorkflowWorkspace } from "../src/deno/workspace/host.ts";
30+
import type { WorkflowWorkspaceOptions } from "../src/deno/workspace/host.ts";
31+
import type { WorkflowRunDatabase } from "../src/storage/api.ts";
32+
import { collect, execute, inlineSource } from "@executablemd/core";
33+
import type { Json } from "@executablemd/durable-streams";
2534
import { WORKSPACE_GIT_SWITCH } from "../src/deno/composition/provider.ts";
2635
import { denoRepositoryHost } from "../src/deno/composition/host.ts";
2736
import type { GitInvocation, GitOutcome } from "../src/deno/composition/host.ts";
@@ -96,6 +105,14 @@ function isProtocolFailure(value: unknown): value is GitOperationProtocolError {
96105
return value instanceof GitOperationProtocolError;
97106
}
98107

108+
function isDivergence(value: unknown): value is DivergenceError {
109+
return value instanceof DivergenceError;
110+
}
111+
112+
function isGitFailure(value: unknown): value is GitOperationError {
113+
return value instanceof GitOperationError;
114+
}
115+
99116
/** Every table this run's database holds, as another connection sees them. */
100117
function tableNames(path: string): string[] {
101118
const database = new DatabaseSync(path);
@@ -138,6 +155,43 @@ function damageSwitchResult(path: string, damage: (record: Record<string, unknow
138155
}
139156
}
140157

158+
/**
159+
* One `<Git.Switch>` inside the checkout, under a supplied Repository context.
160+
*
161+
* A self-closing `<Repository>` retains a checkout and installs no context, so
162+
* the record the component observes is exactly the one a caller supplies here —
163+
* which is what a replaced context is, and what makes the two runs below differ
164+
* by nothing but that record.
165+
*/
166+
function observedSource(locator: string): string {
167+
return [
168+
`<Repository name="project" url="${locator}" as="repository" />`,
169+
"<Dir path={repository}>",
170+
`<Git.Switch branch="release" />`,
171+
"</Dir>",
172+
].join("\n");
173+
}
174+
175+
function runObserved(
176+
database: WorkflowRunDatabase,
177+
record: RepositoryRecord,
178+
locator: string,
179+
options: WorkflowWorkspaceOptions,
180+
): Operation<Json> {
181+
return scoped(function* () {
182+
return yield* withWorkflowWorkspace(
183+
database,
184+
scoped(function* () {
185+
yield* RepositoryContext.around({ current: () => record }, { at: "min" });
186+
return yield* collect(
187+
yield* execute({ ...inlineSource(observedSource(locator)), stream: database.journal }),
188+
);
189+
}),
190+
options,
191+
);
192+
});
193+
}
194+
141195
describe("workflow Git.Switch durability", () => {
142196
it("replays without moving a branch or appending a second transition", function* () {
143197
const root = yield* useStorageRoot();
@@ -349,6 +403,69 @@ describe("workflow Git.Switch durability", () => {
349403
});
350404
});
351405

406+
/**
407+
* A recorded transition belongs to the observation it was authorized for.
408+
*
409+
* Durable identity is type and name, and the name is where the observation
410+
* lives, so the encoding behind it has to be injective: two records that
411+
* digested alike would let a replay hand back a transition authorized for one
412+
* of them to the other, on the path where nothing is authenticated because
413+
* nothing is executed.
414+
*
415+
* `requestedBase` is the demonstration. A record that never supplied a base
416+
* retains `null`; a replaced context can supply the string a sentinel-based
417+
* encoding used for absence, and the two must still be different effects.
418+
*/
419+
it("refuses to replay a transition recorded for a different Repository record", function* () {
420+
const root = yield* useStorageRoot();
421+
const remote = yield* useBareRemote(REMOTE);
422+
const path = runPath(root, "release-1.4");
423+
424+
yield* withStorage(root, function* () {
425+
// What this fixture retains, learned from a run of its own: creation
426+
// identity is a function of the name, the url and the base.
427+
const learning = yield* createRun({ runId: "learning" });
428+
yield* runDocument(learning, `<Repository name="project" url="${remote.locator}" as="r" />`);
429+
const [learned] = yield* retainedRepositories(learning);
430+
const record = learned?.record;
431+
if (record === undefined || record.requestedBase !== null) {
432+
throw new Error("the fixture did not retain a Repository with no requested base");
433+
}
434+
435+
const database = yield* createRun();
436+
const first = countingHost();
437+
yield* runObserved(database, record, remote.locator, countingOptions(first));
438+
expect(subcommands(first.counters)).toContain("switch");
439+
const recorded = yield* gitEvents(database);
440+
expect(recorded).toHaveLength(1);
441+
const published = publishedRoots(path);
442+
443+
dropRootClose(path);
444+
445+
// The same expansion, under a context differing in one member only.
446+
const second = countingHost();
447+
const failure = yield* raised(
448+
runObserved(
449+
database,
450+
{ ...record, requestedBase: "\u0000" },
451+
remote.locator,
452+
countingOptions(second),
453+
),
454+
);
455+
456+
// Two different effects, so the recorded one is not this one's to take:
457+
// the journal says so at the position it reaches, before anything runs.
458+
// A collision would instead have handed this observation a transition
459+
// recorded for another, on the path where nothing is authenticated
460+
// because nothing is executed.
461+
expect(causedBy(failure, isDivergence)).toBeInstanceOf(DivergenceError);
462+
expect(causedBy(failure, isGitFailure)).toBe(undefined);
463+
expect(subcommands(second.counters)).not.toContain("switch");
464+
expect(yield* gitEvents(database)).toHaveLength(recorded.length);
465+
expect(publishedRoots(path)).toBe(published);
466+
});
467+
});
468+
352469
it("leaves the frontier untouched when a blocked switch is halted", function* () {
353470
const root = yield* useStorageRoot();
354471
const remote = yield* useBareRemote(REMOTE);
@@ -449,6 +566,50 @@ describe("workflow Git.Switch durability", () => {
449566
* it returns only once a reader has the pipe open, so the child is provably
450567
* running at the moment the scope is torn down.
451568
*/
569+
/**
570+
* The encoding behind a Git operation's durable identity, on its own.
571+
*
572+
* The replay above proves one collision cannot happen; this proves the shape of
573+
* the encoding, which is what makes every other arrangement of values safe too.
574+
* Absence, a separator, a length prefix and the empty string are all ordinary
575+
* content somewhere — a branch may be named `1:a`, a base may contain any
576+
* character — so none of them may be readable as structure.
577+
*/
578+
describe("workflow Git operation identity", () => {
579+
it("gives distinct values distinct fingerprints", function* () {
580+
const arrangements: (string | null)[][] = [
581+
[],
582+
[null],
583+
[""],
584+
["\u0000"],
585+
["\u0001"],
586+
["-"],
587+
[null, null],
588+
[null, ""],
589+
["", null],
590+
["a", "b"],
591+
["a\u0001b"],
592+
["ab", ""],
593+
["", "ab"],
594+
["1:a"],
595+
["1", "a"],
596+
["2:ab", "c"],
597+
["2:ab c"],
598+
["main", null],
599+
[null, "main"],
600+
];
601+
602+
const fingerprints = arrangements.map((values) => gitOperationFingerprint(values));
603+
expect(new Set(fingerprints).size).toBe(arrangements.length);
604+
});
605+
606+
it("gives one value one fingerprint", function* () {
607+
expect(gitOperationFingerprint(["main", null, "a\u0001b"])).toBe(
608+
gitOperationFingerprint(["main", null, "a\u0001b"]),
609+
);
610+
});
611+
});
612+
452613
describe("workflow Git operation teardown", () => {
453614
it("kills the Git child it spawned when the scope is halted", function* () {
454615
const directory = yield* useTempDirectory("xmd-git-teardown-");

0 commit comments

Comments
 (0)