CSV: The Field That References Itself

This one looks like two problems bolted together and it is not. It is a parsing problem that turns into a graph problem, and the reason that shape is worth practicing is that the parsing half lulls you. You spend ten minutes on quoting rules, you get it right, you feel good, and then the last requirement lands and you have to produce a correct cycle detector under time pressure with a warm, comfortable brain. The parsing is the setup. The graph is the question.

The recipe

Say before you type: "A record is not a line, so I scan characters and carry one bit of state. Then each row is its own little dependency graph, and I need three states per field, not two: untouched, on the current path, finished."

Why split cannot do this

id,note
1,"hello, world"

line.split(",") gives you three fields out of two, and nothing downstream can recover, because the split has already thrown away the position where the answer lived. The information you needed was "was this comma inside quotes", and that is not a property of the comma. It is a property of everything to the left of it.

So you scan, and you carry exactly one bit:

while (i < text.length) {
  const ch = text[i];

  if (quoted) {
    if (ch === '"') {
      if (text[i + 1] === '"') { field += '"'; i += 2; continue; }  // "" is one "
      quoted = false; i += 1; continue;
    }
    field += ch; i += 1; continue;      // delimiters and newlines are literal in here
  }

  if (ch === '"' && field === "") { quoted = true; i += 1; continue; }
  if (ch === this.delimiter) { row.push(field); field = ""; i += 1; continue; }
  ...
}

Two details in there are worth saying out loud while you type them.

ch === '"' && field === "" is the rule that a quote only opens a field at the start of that field. Everywhere else it is an ordinary character, which is why 5" pipe is a value and not a parse error. Drop the field === "" guard and you have written a parser that cannot read a hardware catalogue.

The doubled quote is checked before the quote is allowed to close the field. Write the quote handling as a toggle, if (ch === quoteChar) quoted = !quoted, and "a""b" comes back as ab: the two quotes turn each other off and back on, and neither one ever lands in the field. The literal quote comes from the lookahead, not from the toggle.

A record is not a line

This is the one that separates people who have parsed a real export from people who have parsed an example.

note,who
"line one
line two",Ada

That is two physical lines and one record. If you wrote text.split("\n") and then scanned each line for quotes, you get the quoting right and the row count wrong, which is worse than getting both wrong because the failure is quiet. Your loop over lines never sees a record, it sees a fragment.

The fix is that the newline handling lives inside the same scanner, in the not-quoted branch, next to the delimiter handling. One loop, one state machine, and a newline becomes a row boundary only when the bit says you are outside quotes. Carriage return belongs in the same place: \r immediately before \n is part of the line ending, and if you forget it, your last column on every row is named something\r and nothing matches anything ever again.

A ragged row is a data error

When a row has four fields and the header has three, you have two choices and only one of them is defensible.

if (row.length !== header.length) {
  throw new Error("row " + r + " has " + row.length + " fields, header has " + header.length);
}

Padding the short row with empty strings invents values that nobody wrote, and dropping the extra field on a long row throws away a value somebody did write. Both produce a file that loads cleanly and is wrong, which is the expensive kind of wrong. Refusing costs someone five minutes. Say that trade out loud, because "I would rather fail loudly here" is the sentence being listened for.

Now the graph

A cell can hold a formula instead of a value:

first,last,full
Ada,Lovelace,=first+last

=first+last means "the resolved value of first, then the resolved value of last". Three things make this a graph rather than a lookup.

It points inside its own record. Row 2 knows nothing about row 1. Every row is a separate, tiny graph over the same set of column names, which is very convenient: one document can hold a clean row, a self reference, and a three field loop, and they do not interact.

It is transitive. a is =b, b is =c, c is 42. Resolving a means resolving b first, which means resolving c first. That is a depth first traversal whether or not you call it one.

Quoting is already over. "=total" in the file parses to =total, and a record has no memory of how its values were quoted. So it is a reference. It is tempting to thread a "this one was quoted" flag out of the parser so you can treat it as a literal, and that instinct is the wrong one: the parser's job ends when the quotes come off.

The three states

Here is the whole problem, in two lines of a file:

top,left,right,base
=left+right,=base,=base,x

top needs left, which needs base. Then top needs right, which needs base again. You have now arrived at base twice. That is not a cycle. That is a shared dependency, and shared dependencies are the normal case in every spreadsheet ever built.

Compare it with:

a,b
=b,=a

Here you arrive at a while you are still in the middle of computing a. That is a cycle.

In both cases you reached a field you had reached before. The difference is not "have I seen this field", it is "am I still inside it". So one visited set cannot express the answer. You need three states:

state	meaning	what it means when you arrive
untouched	never walked	go walk it
on the current path	started, not finished	cycle
finished	fully resolved down to literals	reuse the answer, keep going

const walk = (name: string): string => {
  const cached = done.get(name);
  if (cached !== undefined) return cached;          // finished: reuse
  if (onPath.has(name)) throw cycle(path, name);    // still open: cycle

  onPath.add(name);
  path.push(name);
  ... resolve every column this formula names ...
  path.pop();
  onPath.delete(name);
  done.set(name, out);
  return out;
};

The delete on the way out is the part that gets dropped under pressure, and the only thing standing between that and a broken tool is the line above it: done is read first, so a finished field hands back its cached answer before anything asks whether it is still open. Swap those two checks, or write the walk without a done to hide behind, and a missing delete is exactly visited with extra steps: the diamond above reports base as a cycle, every real file you run it against lights up red, and the report gets ignored inside a week. The detector in the next section is where this bites hardest, because it has no cached answer to fall back on. Leave a field marked as on the path instead of marking it finished and every shared dependency in the file comes back as a loop.

The done map is not an optimization you can skip either. Without it, a chain where each level references the level below it twice costs you two to the power of the depth. Twenty levels is a million resolutions of a graph with twenty one nodes in it.

Report the loop, not the path you took to it

"There is a cycle" is not an answer a human can act on. "total points at net points at total" is. And the difference between those two shows up in a case that a lazy implementation gets wrong:

a,b,c,d
=b,=c,=d,=b

a is not in the cycle. a is how you got there. The loop is b -> c -> d -> b, and if you report the whole call stack you will tell somebody to go look at a column that is completely innocent.

The fix is one line, and it is the reason you kept an ordered path array alongside the onPath set:

const fields = path.slice(path.indexOf(name));

Slice from where you re-entered, not from the bottom. The set answers "am I inside this", the array answers "in what order", and you need both. Say that while you type it, because reaching for both structures at once is the thing that reads as having done this before.

The detector and the resolver are the same walk

Once the resolver is right, a findCycles that reports every loop in the file is the same traversal with the reporting swapped: instead of throwing at a back edge, record it and keep going.

if (mark === ON_PATH) {
  found.push({ row, fields: path.slice(path.indexOf(ref)) });   // record, do not throw
} else if (mark === undefined) {
  walk(ref);
}
// FINISHED: shared dependency, nothing to do

Two properties are worth stating as design decisions rather than leaving implied.

It does not throw. This is the function somebody runs to explain a failure, so it has to survive the file that caused the failure. A reference to a column that does not exist is a different finding and it is not an edge, so the detector skips it and lets the resolver be the one that complains.

It keeps going after the first loop. A document can have a loop in row 2 and a different loop in row 9, and a tool that stops at the first one turns one bad file into nine round trips. The coloring gives you this for free: mark the field finished on the way out even when a cycle was found below it, and the outer loop over the header picks up the next untouched field.

Depth is real

A three hundred field chain is not a stress test, it is a wide export. Plain recursion handles it, but a cycle detector that recurses without ever checking onPath does not return at all, and the error a human sees is Maximum call stack size exceeded, which names nothing and blames nothing. That message is the exact failure this whole problem exists to replace.

What the interviewer is listening for

• Do you know a record is not a line? Everything about the parsing half is downstream of that.
• Can you name the two kinds of revisit? Finished and in progress are different, one set cannot hold both, and the diamond is the case that proves it.
• Does your error name the columns? Detecting a cycle is the easy half. Handing back b -> c -> d -> b, without the field that merely led you there, is the half that makes the tool usable.