Algorithms
Tab-separated values
Cells as spreadsheets put them on the clipboard, read and written.
Behaviour
Any block of cells reads back as itself
// Every character that means something here, among ordinary ones and any others.
const cell = fc.oneof(
fc.string({
unit: fc.constantFrom("a", "b", " ", "\t", "\n", "\r", '"', "\uFEFF", "日", ","),
maxLength: 6,
}),
fc.string({ unit: "binary", maxLength: 6 }),
);
// At least one row, each of at least one cell; rows need not be of one length.
const block = fc.array(fc.array(cell, { minLength: 1, maxLength: 5 }), { minLength: 1, maxLength: 6 });
fc.assert(
fc.property(block, (cells) => JSON.stringify(parseTSV(formatTSV(cells))) === JSON.stringify(cells)),
{ numRuns: 2000 },
);Cells are separated by tabs, and rows by newlines
expect(
formatTSV([
["a", "b"],
["c", "d"],
]),
).toBe("a\tb\nc\td");
expect(parseTSV("a\tb\nc\td")).toEqual([
["a", "b"],
["c", "d"],
]);A cell containing a tab, a newline or a quote is quoted, with its quotes doubled
expect(formatTSV([['say "hi"', "two\nlines", "old\rmac"]])).toBe(
'"say ""hi"""\t"two\nlines"\t"old\rmac"',
);
expect(parseTSV('"say ""hi"""\t"two\nlines"\t"old\rmac"')).toEqual([
['say "hi"', "two\nlines", "old\rmac"],
]);Rows end with a newline, a carriage return, or both as one
expect(parseTSV("a\r\nb\rc\nd")).toEqual([["a"], ["b"], ["c"], ["d"]]);
expect(parseTSV("a\n\rb")).toEqual([["a"], [""], ["b"]]);The trailing newline a spreadsheet adds is not a row
expect(parseTSV("a\tb\n")).toEqual([["a", "b"]]);
expect(parseTSV("a\r\nb\r\n")).toEqual([["a"], ["b"]]);
expect(parseTSV("a\r")).toEqual([["a"]]);Only one trailing newline is set aside: an empty line before it is a row of one empty cell
expect(parseTSV("a\n\n")).toEqual([["a"], [""]]);
expect(parseTSV("a\r\n\r\n\r\n")).toEqual([["a"], [""], [""]]);
expect(parseTSV("\n")).toEqual([[""]]);A last row of one empty cell is written with a newline after it, so that it is not taken for the trailing one
expect(formatTSV([["a"], [""]])).toBe("a\n\n");
expect(parseTSV(formatTSV([["a"], [""]]))).toEqual([["a"], [""]]);
expect(formatTSV([["a"], [""], [""]])).toBe("a\n\n\n");
// Nothing else needs one: a single cell copies as its text alone.
expect(formatTSV([["a"]])).toBe("a");
expect(formatTSV([[""]])).toBe("");
expect(formatTSV([["a"], ["", ""]])).toBe("a\n\t");Empty cells are kept
expect(parseTSV("a\t\tc\n\t\t")).toEqual([
["a", "", "c"],
["", "", ""],
]);
expect(parseTSV("")).toEqual([[""]]);
expect(parseTSV('a\t""\t')).toEqual([["a", "", ""]]);A quote that is not at the start of a cell is an ordinary character
expect(parseTSV('5" nail\tok')).toEqual([['5" nail', "ok"]]);
expect(parseTSV('"a"b"\tok')).toEqual([['ab"', "ok"]]);A quote that is never closed is an ordinary character, and the cells after it are still cells
expect(parseTSV('"abc\tdef\nghi\tjkl')).toEqual([
['"abc', "def"],
["ghi", "jkl"],
]);
expect(parseTSV('a\t"b ""c\n1\t2\n')).toEqual([
["a", '"b ""c'],
["1", "2"],
]);
expect(parseTSV('"')).toEqual([['"']]);A byte-order mark at the start of the text is not part of the first cell
expect(parseTSV("\uFEFFa\tb\nc\td")).toEqual([
["a", "b"],
["c", "d"],
]);
expect(parseTSV('\uFEFF"a\tb"\tc')).toEqual([["a\tb", "c"]]);
expect(parseTSV("\uFEFF")).toEqual([[""]]);
// Only there: anywhere else it is a character like any other.
expect(parseTSV("a\t\uFEFFb")).toEqual([["a", "\uFEFFb"]]);A cell that starts with a byte-order mark is quoted, so that the mark is kept at the start of a text
expect(formatTSV([["\uFEFFa", "b\uFEFF"]])).toBe('"\uFEFFa"\tb\uFEFF');
expect(parseTSV(formatTSV([["\uFEFFa"]]))).toEqual([["\uFEFFa"]]);
expect(parseTSV(formatTSV([["\uFEFF"]]))).toEqual([["\uFEFF"]]);Reading examines each character a fixed number of times, even where quotes are never closed
/** A text that counts the characters looked at in it, however they are asked for. */
function counted(source: string) {
let examined = 0;
const text = new Proxy(new String(source), {
get(_, key) {
if (key === "length") return source.length;
if (key === "charCodeAt") {
return (at: number) => {
examined += 1;
return source.charCodeAt(at);
};
}
if (key === "indexOf") {
return (search: string, from: number) => {
const at = source.indexOf(search, from);
examined += (at === -1 ? source.length : at + 1) - from;
return at;
};
}
if (key === "slice") {
return (start: number, end: number) => {
examined += end - start;
return source.slice(start, end);
};
}
throw new Error(`a way of reading the text that is not counted: ${String(key)}`);
},
}) as unknown as string;
return { text, examined: () => examined };
}
const cells = 100_000;
for (const source of [
"plain\tcells\n".repeat(cells),
'"quoted ""cells"""\t"of two\nlines"\n'.repeat(cells),
// The first quote is never closed: every quote after it is one of a pair.
`"a\t${'""\t'.repeat(cells)}`,
]) {
const { text, examined } = counted(source);
const rows = parseTSV(text);
expect(rows.length).toBeGreaterThan(0);
// Once to look for a closing quote, once to find where the cell ends, once to copy it.
expect(examined()).toBeLessThanOrEqual(3 * source.length);
}React
Install
npx shadcn@latest add https://ui.publictheta.com/r/tsv.jsonSource
src/algorithms/tsv.ts
/**
* Tab-separated values, as spreadsheets put cells on the clipboard: rows
* separated by newlines, cells by tabs, and a cell that itself contains a tab,
* a newline or a quote wrapped in quotes with its quotes doubled.
*
* A block is at least one row, and a row at least one cell: the text has no way
* to say "no rows" or "a row of nothing". Every such block reads back as itself.
*
* One newline at the very end of a text ends the last row and starts no other —
* some spreadsheets write it and some do not. So a block whose last row is a
* single empty cell is written with a newline after that row, which is what
* tells it from a block without the row; nothing else is given one, and a
* single cell copies as its text alone.
*
* Reading is one pass over the text, with one string made per cell.
*/
const TAB = 9;
const LF = 10;
const CR = 13;
const QUOTE = 34;
const BOM = 0xfeff;
// A mark at the very start of a text is read as its encoding, not as the cell's.
const quoted = /[\t\n\r"]|^\uFEFF/;
/** The text for a block of cells. */
export function formatTSV(rows: ReadonlyArray<readonly string[]>): string {
const text = rows
.map((row) =>
row.map((cell) => (quoted.test(cell) ? `"${cell.replaceAll('"', '""')}"` : cell)).join("\t"),
)
.join("\n");
const last = rows.at(-1);
return rows.length > 1 && last?.length === 1 && last[0] === "" ? `${text}\n` : text;
}
/** The block of cells in a text. */
export function parseTSV(text: string): string[][] {
const rows: string[][] = [];
let row: string[] = [];
const length = text.length;
let index = text.charCodeAt(0) === BOM ? 1 : 0;
for (;;) {
// What a quoted start of the cell said, and where the rest of the cell begins.
let opening = "";
let from = index;
if (text.charCodeAt(index) === QUOTE) {
let content = "";
let scan = index + 1;
for (;;) {
const close = text.indexOf('"', scan);
// Never closed: the quote is a character, and the cell ends where any other would.
if (close === -1) break;
content += text.slice(scan, close);
if (text.charCodeAt(close + 1) === QUOTE) {
content += '"';
scan = close + 2;
} else {
opening = content;
from = index = close + 1;
break;
}
}
}
let code = -1;
while (index < length) {
code = text.charCodeAt(index);
if (code === TAB || code === LF || code === CR) break;
index += 1;
}
row.push(opening === "" ? text.slice(from, index) : opening + text.slice(from, index));
if (index === length) break;
index += 1;
if (code === TAB) continue;
if (code === CR && text.charCodeAt(index) === LF) index += 1;
rows.push(row);
row = [];
// A newline at the very end starts no row.
if (index === length) return rows;
}
rows.push(row);
return rows;
}