Skip to content

Commit 180d191

Browse files
committed
🔒 Read the alternates chain in Git's grammar, not as literal lines
`objects/info/alternates` is not a list of literal lines. Git's `parse_alt_odb_entry()` recognizes a C-style quoted entry and unquotes it before it resolves an object directory, and the containment proof added alongside Push read every non-comment line verbatim. The two readings can be made to disagree on purpose. `"/elsewhere/objects"` is an external database to Git and a *relative* path whose first segment is a quote character to anything comparing spellings — so a real directory of that literal name, planted inside the authenticated object database, satisfies a literal reading while Git unquotes the entry and traverses the external database. A document can write both halves, because both are files inside the Workspace. Entries are now scanned the way Git scans them: a `#` entry is a comment, an entry beginning with `"` is unquoted first, and everything else is ordinary text. Unquoting assembles bytes rather than characters, because an octal escape names a byte and three of them can name one character, so the path this produces is the path Git would open. Quoting Git's own reader rejects — unterminated, an unknown escape, a short octal — is ordinary text to Git and stays ordinary text here, which keeps a broken-looking entry safely classified instead of quietly resolved as something it is not. An entry whose exact path cannot be named — a closing quote with more text after it, bytes that name no path — is refused rather than approximated, because a path that cannot be named cannot be proven contained. Nothing is repaired. The graph is still rejected whole, still before `ls-remote` and after every local authority check, and still as a provider-boundary failure that publishes no outcome, repeats no authored path and fail-stops the run. Completed replay is untouched: it reaches no provider, so it validates no graph, builds no control repository and runs no Git for the push. The regression plants the quoted entry *and* the literal decoy that makes the previous reading accept, and proves the escape is real by resolving the foreign commit through that entry with an ordinary `git` in the same export. Restoring the literal-line parser fails that test alone, with the other twenty steps in the suite still passing. Refs #370.
1 parent 6953590 commit 180d191

4 files changed

Lines changed: 288 additions & 11 deletions

File tree

‎architecture.md‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -998,7 +998,11 @@ address it.
998998
What an attachment grants access to is authenticated separately from where it
999999
came from, because local state can name further local state: a Git object
10001000
database names further ones through its alternates chain, and a symbolic link
1001-
under it redirects a read before Git reports anything about it. The graph a
1001+
under it redirects a read before Git reports anything about it. Such a graph is
1002+
read in the consuming tool's own grammar rather than as text: Git unquotes a
1003+
C-style quoted alternates entry before resolving it, so a containment proof that
1004+
compared spellings could be satisfied by a decoy of that literal name while the
1005+
traversal went elsewhere. The graph a
10021006
provider could traverse is therefore proven contained on the live provider's
10031007
first use of the attachment — before any external observation, and on no other
10041008
path, so a completed replay reaches no provider and performs no such proof. A

‎packages/workflow/src/deno/composition/object-source.ts‎

Lines changed: 185 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -125,19 +125,195 @@ function* containedTree(directory: string, operation: string): Operation<void> {
125125
}
126126

127127
/**
128-
* The object directories one alternates file names, as Git would read them.
128+
* What one alternates entry turns out to be.
129129
*
130-
* One path per line. A blank line is nothing and a `#` line is a comment, which
131-
* is what Git's own reader does with them; every other line is a path, absolute
132-
* or relative to the object directory that named it.
130+
* `ignored` is a comment or an empty entry, which Git skips. `path` is an
131+
* object directory Git will traverse. `undecidable` is an entry this reading
132+
* cannot say the exact path of — and an entry whose path cannot be named
133+
* exactly cannot be held to containment, so it is refused rather than guessed.
133134
*/
134-
function alternatePaths(content: string, from: string): string[] {
135+
type AlternateEntry =
136+
| { readonly kind: "ignored" }
137+
| { readonly kind: "path"; readonly value: string }
138+
| { readonly kind: "undecidable" };
139+
140+
/** The one-character escapes Git's C-style unquoting understands. */
141+
const ESCAPES: ReadonlyMap<string, number> = new Map([
142+
["a", 0x07],
143+
["b", 0x08],
144+
["f", 0x0c],
145+
["n", 0x0a],
146+
["r", 0x0d],
147+
["t", 0x09],
148+
["v", 0x0b],
149+
["\\", 0x5c],
150+
['"', 0x22],
151+
]);
152+
153+
const OCTAL = /^[0-7]$/;
154+
155+
type Unquoted =
156+
/** The path the quoting names, and where the closing quote left off. */
157+
| { readonly kind: "path"; readonly value: string; readonly end: number }
158+
/** Quoting Git's own reader rejects, which it then reads as ordinary text. */
159+
| { readonly kind: "literal" }
160+
/** Bytes this host cannot name a path with, so the exact path is unknown. */
161+
| { readonly kind: "undecidable" };
162+
163+
/** The path these bytes name, or `undefined` when they name none. */
164+
function decodePath(bytes: readonly number[]): string | undefined {
165+
if (bytes.includes(0)) {
166+
return undefined;
167+
}
168+
try {
169+
return new TextDecoder("utf-8", { fatal: true }).decode(new Uint8Array(bytes));
170+
} catch {
171+
return undefined;
172+
}
173+
}
174+
175+
/**
176+
* Read a C-style quoted alternates entry the way Git's own unquoting reads one.
177+
*
178+
* Bytes rather than characters, because that is what Git unquotes into and what
179+
* it hands the operating system: an octal escape names one byte, and three of
180+
* them can name one character. Assembling bytes and decoding once is what keeps
181+
* the path this produces the path Git would open.
182+
*
183+
* Quoting Git rejects — an unterminated string, an escape it does not know, a
184+
* short octal escape — is not an error here either. Git falls back to reading
185+
* the line as ordinary text, so this says `literal` and the caller does the
186+
* same, which is what keeps a broken-looking line safely classified rather than
187+
* quietly resolved as something it is not.
188+
*/
189+
function unquoteCStyle(text: string): Unquoted {
190+
const encoder = new TextEncoder();
191+
const bytes: number[] = [];
192+
let index = 1;
193+
194+
for (;;) {
195+
let plain = index;
196+
while (plain < text.length && text[plain] !== '"' && text[plain] !== "\\") {
197+
plain += 1;
198+
}
199+
for (const byte of encoder.encode(text.slice(index, plain))) {
200+
bytes.push(byte);
201+
}
202+
index = plain;
203+
if (index >= text.length) {
204+
return { kind: "literal" };
205+
}
206+
207+
const delimiter = text[index];
208+
index += 1;
209+
if (delimiter === '"') {
210+
const value = decodePath(bytes);
211+
return value === undefined ? { kind: "undecidable" } : { kind: "path", value, end: index };
212+
}
213+
214+
const escape = text[index];
215+
index += 1;
216+
if (escape === undefined) {
217+
return { kind: "literal" };
218+
}
219+
const simple = ESCAPES.get(escape);
220+
if (simple !== undefined) {
221+
bytes.push(simple);
222+
continue;
223+
}
224+
const second = text[index];
225+
const third = text[index + 1];
226+
if (
227+
!OCTAL.test(escape) ||
228+
second === undefined ||
229+
third === undefined ||
230+
!OCTAL.test(second) ||
231+
!OCTAL.test(third)
232+
) {
233+
return { kind: "literal" };
234+
}
235+
index += 2;
236+
bytes.push((Number(escape) << 6) | (Number(second) << 3) | Number(third));
237+
}
238+
}
239+
240+
/**
241+
* The next entry an alternates file holds, and what is left after it.
242+
*
243+
* This is Git's `parse_alt_odb_entry`, and being Git's is the whole point. A
244+
* line is not the unit: a `#` line is a comment, a line beginning with `"` is a
245+
* **quoted** path that Git unquotes before it resolves anything — and a quoted
246+
* string may contain the separator, so where an entry ends is decided by the
247+
* quoting rather than by the next newline. Everything else is ordinary text.
248+
*
249+
* Reading a quoted entry literally is what a validator must not do. The two
250+
* spellings resolve to different places on purpose: `"/elsewhere/objects"` is
251+
* an external database to Git and a relative path with quote characters in its
252+
* name to anything comparing strings, so a directory of that literal name sits
253+
* inside the authenticated database and answers for a traversal that never goes
254+
* there.
255+
*
256+
* A closing quote with more text after it on its line is the one shape this
257+
* refuses. Git consumes it in a way no containment check can restate as a
258+
* single path, and an entry whose exact path cannot be named cannot be proven
259+
* contained.
260+
*/
261+
function nextAlternateEntry(text: string): { entry: AlternateEntry; rest: string } {
262+
const separator = text.indexOf("\n");
263+
const line = separator < 0 ? text.length : separator;
264+
const after = (end: number): string => (end < text.length ? text.slice(end + 1) : "");
265+
266+
if (text.startsWith("#")) {
267+
return { entry: { kind: "ignored" }, rest: after(line) };
268+
}
269+
270+
if (text.startsWith('"')) {
271+
const unquoted = unquoteCStyle(text);
272+
if (unquoted.kind === "undecidable") {
273+
return { entry: { kind: "undecidable" }, rest: "" };
274+
}
275+
if (unquoted.kind === "path") {
276+
const trailing = text[unquoted.end];
277+
if (trailing !== undefined && trailing !== "\n") {
278+
return { entry: { kind: "undecidable" }, rest: "" };
279+
}
280+
return { entry: { kind: "path", value: unquoted.value }, rest: after(unquoted.end) };
281+
}
282+
// Broken quoting. Git reads the line as ordinary text, and so does this.
283+
}
284+
285+
const literal = text.slice(0, line);
286+
return {
287+
entry: literal === "" ? { kind: "ignored" } : { kind: "path", value: literal },
288+
rest: after(line),
289+
};
290+
}
291+
292+
/**
293+
* Every object directory one alternates file names, resolved as Git resolves it.
294+
*
295+
* A relative entry is relative to the object directory that named it, which is
296+
* what Git's own `relative_base` makes it.
297+
*/
298+
function alternatePaths(content: string, from: string, operation: string): string[] {
135299
const paths: string[] = [];
136-
for (const line of content.split("\n")) {
137-
if (line === "" || line.startsWith("#")) {
300+
let rest = content;
301+
while (rest !== "") {
302+
const scanned = nextAlternateEntry(rest);
303+
rest = scanned.rest;
304+
const entry = scanned.entry;
305+
if (entry.kind === "undecidable") {
306+
uncontained(
307+
operation,
308+
"its object database holds an alternates entry whose object directory this run " +
309+
"cannot name exactly, so it cannot be proven to stay inside the database this run " +
310+
"authenticated",
311+
);
312+
}
313+
if (entry.kind === "ignored") {
138314
continue;
139315
}
140-
paths.push(line.startsWith("/") ? line : `${from}/${line}`);
316+
paths.push(entry.value.startsWith("/") ? entry.value : `${from}/${entry.value}`);
141317
}
142318
return paths;
143319
}
@@ -169,7 +345,7 @@ function* containedAlternates(
169345
if ((yield* entry(file))?.isFile() !== true) {
170346
return;
171347
}
172-
for (const named of alternatePaths(yield* readTextFile(file), directory)) {
348+
for (const named of alternatePaths(yield* readTextFile(file), directory, operation)) {
173349
let resolved: string;
174350
try {
175351
resolved = yield* until(realpath(named));

‎packages/workflow/tests/git-push.test.ts‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -991,6 +991,94 @@ describe("workflow Git.Push object-source containment", () => {
991991
});
992992
});
993993

994+
/**
995+
* The same escape, spelled the way Git reads it rather than the way a string
996+
* comparison does.
997+
*
998+
* `objects/info/alternates` is not a list of literal lines. An entry
999+
* beginning with `"` is a C-style quoted path, and Git unquotes it before it
1000+
* resolves anything — so `"/elsewhere/objects"` is an external database to
1001+
* Git and a *relative* path whose first segment is a quote character to
1002+
* anything that compares the spelling. A validator reading it literally is
1003+
* answered by a directory of that literal name planted inside the
1004+
* authenticated database, and the traversal it thinks it described goes
1005+
* somewhere else entirely.
1006+
*
1007+
* Both halves are planted here: the quoted entry Git will follow, and the
1008+
* literal decoy that makes a literal reading accept it.
1009+
*/
1010+
it("refuses a quoted alternates entry whose literal spelling has an inside decoy", function* () {
1011+
const root = yield* useStorageRoot();
1012+
const remote = yield* useBareRemote(REMOTE);
1013+
const path = runPath(root, "release-1.4");
1014+
const foreign = yield* useBareRemote({
1015+
commits: [{ message: "foreign", entries: [{ path: "foreign.txt", content: "foreign\n" }] }],
1016+
});
1017+
const foreignCommit = foreign.heads.get("main") ?? "";
1018+
const foreignObjects = `${foreign.locator}/objects`;
1019+
// Valid C-style quoting: the path holds no quote or backslash of its own.
1020+
const quoted = `"${foreignObjects}"`;
1021+
1022+
yield* withStorage(root, function* () {
1023+
const database = yield* createRun();
1024+
const counting = countingHost();
1025+
const failure = yield* raised(
1026+
runWorkflowDocument(
1027+
database,
1028+
document(
1029+
remote.locator,
1030+
`<Git.Switch branch="${BRANCH}" />`,
1031+
`<Plant />`,
1032+
`<Git.Push />`,
1033+
),
1034+
countingOptions(counting),
1035+
(run) =>
1036+
scoped(function* () {
1037+
yield* registerComponents([
1038+
plantObjectGraph(database, function* (workspace, checkout) {
1039+
const objects = `${checkout}/.git/objects`;
1040+
yield* workspace.filesystem.mkdir(`${objects}/info`, { recursive: true });
1041+
yield* workspace.filesystem.writeFile(
1042+
`${objects}/info/alternates`,
1043+
`${quoted}\n`,
1044+
);
1045+
// The decoy: a real directory inside the authenticated
1046+
// database whose name is the entry's literal spelling, so a
1047+
// literal reading resolves it and is satisfied.
1048+
yield* workspace.filesystem.mkdir(`${objects}/${quoted}`, { recursive: true });
1049+
}),
1050+
]);
1051+
return yield* run();
1052+
}),
1053+
),
1054+
);
1055+
1056+
// One fixed, cause-free boundary failure, repeating no path an author
1057+
// wrote and no spelling they chose.
1058+
expect(String(failure)).toContain("executed and published nothing");
1059+
expect(String(failure)).not.toContain(foreignObjects);
1060+
expect(String(failure)).not.toContain(quoted);
1061+
1062+
expect(subcommands(counting.counters)).not.toContain("ls-remote");
1063+
expect(subcommands(counting.counters)).not.toContain("push");
1064+
expect(yield* gitHostEvents(database)).toHaveLength(0);
1065+
expect(publishedRoots(path)).toBe(3);
1066+
expect(committedRoot(path)).toBe(latestRoot(path));
1067+
expect(remoteRefs(remote).has(DESTINATION)).toBe(false);
1068+
1069+
// The escape really was reachable, and reachable through the *quoted*
1070+
// entry: ordinary Git in the same export unquotes it, links the foreign
1071+
// database and resolves a commit this run never held. The decoy is a
1072+
// directory with no objects in it, so nothing but the unquoting explains
1073+
// this answer.
1074+
const reached = yield* inCheckout(database, yield* checkoutPath(database), function* (run) {
1075+
const top = (yield* run(["rev-parse", "--show-toplevel"])).trim();
1076+
return nativeGit(["cat-file", "-t", foreignCommit], top, top);
1077+
});
1078+
expect(reached).toBe("commit");
1079+
});
1080+
});
1081+
9941082
/**
9951083
* The link an author can write, which needs no chain at all.
9961084
*

‎specs/workflow-workspace-spec.md‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1052,7 +1052,16 @@ link anywhere under `objects/` redirects a read before Git reports anything abou
10521052
it — both are files inside the Workspace, so both are things a document can
10531053
write. Everything Git may traverse is therefore proven to resolve inside the
10541054
object database this run authenticated, before the first remote observation and
1055-
after every local authority check. A graph that leaves it is rejected rather than
1055+
after every local authority check.
1056+
1057+
That chain is read the way Git reads it, spelling included. An entry beginning
1058+
with `"` is a C-style quoted path Git unquotes before resolving anything, so the
1059+
same bytes name an external database to Git and a relative path with quote
1060+
characters in its name to anything comparing spellings — and a directory of that
1061+
literal name, planted inside the authenticated database, would answer for a
1062+
traversal that never goes there. Quoting Git itself rejects is ordinary text to
1063+
Git and to this proof alike. An entry whose exact path cannot be named is
1064+
refused rather than approximated. A graph that leaves it is rejected rather than
10561065
repaired: deleting an authored alternate would publish from a database the run
10571066
edited on the author's behalf, and ignoring one would publish from a database
10581067
that is not the one it verified. The refusal is a boundary failure — nothing is

0 commit comments

Comments
 (0)