Parsing "key: value" format in which values can span multiple lines

Question

So I've written a function which parses a fairly simple key-value pair syntax. Each pair can span across multiple lines, as long as the value does not have a colon in it. If it does, then any new line must be preceded by three spaces. For each pair, I create an object with the key, the value, and the offset at which they appear (from the beginning of the string).

You can get a better idea of this syntax from the following image (keys in blue, values in green):

I thought about using regex, but seeing as I also need to keep track of the offsets for each item, and performance is extremely important - I thought it may be easier/more efficient to just use plain typescript. Here's the function I came up with:

function parseTitlePageChunk(text: string):{key:string, value:string, keyoffset:number, valueoffset:number}[] {
    console.time("pairs");
    let pairs = [];
    let potentialValue = ""; //keep track of a string which may be a key
    let potentialKey = ""; //keep track of a string which may be a value
    let potentialKeyOffset = 0;
    let potentialValueOffset = 0;
    let colonInLine = false;
    let forceValue = false; //true if a line starts with three spaces
    let spaceCounter = -1; //if the spaceCounter==-1 there's no more spaces at the beginning of the line
    for (let i = 0; i < text.length; i++) {
        let c = text[i];
        if (c == ':' && !colonInLine && !forceValue) {
            //We ran into a colon, promote the potential key to an actual one
            pairs.push({key: potentialKey, value:"", keyoffset:potentialKeyOffset, valueoffset:potentialValueOffset});
            potentialValue = ""; //reset the potential value
            potentialValueOffset = i+1; //reset the potential value offset
            colonInLine = true;
        }
        else if (c == '\n' && pairs.length > 0) {
            //we hit a new line, and there exists a previous key
            pairs[pairs.length - 1].value = potentialValue; //set the value of the previous key
            pairs[pairs.length - 1].valueoffset = potentialValueOffset;
            potentialValue += '\n';
            potentialKey = "\n";
            potentialKeyOffset = i;
            colonInLine = false;
            forceValue = false;
            spaceCounter = 0;
        }
        else {
            if(spaceCounter!=-1 && c == ' '){
                spaceCounter++;
            }
            else{
                spaceCounter = -1;
            }
            potentialValue += c;
            potentialKey += c;
            if(spaceCounter>=3) forceValue=true;
        }
    }
    if (pairs.length > 0) {
        //add the last potential value as a key
        pairs[pairs.length - 1].value = potentialValue;
        pairs[pairs.length - 1].valueoffset = potentialValueOffset;
    }
    console.timeEnd("pairs");
    return pairs;
}

Here's a sample input:

Key: in-line value
Key2: in-line value: with a colon
Key3: multi-line value
which continues here
Key4: multi-line value which
   continues here: has a colon
   yet is still a value

which outputs the following (stringified to JSON):

[{
    "key": "Key",
    "value": " in-line value",
    "keyoffset": 0,
    "valueoffset": 4
}, {
    "key": "\nKey2",
    "value": " in-line value: with a colon",
    "keyoffset": 18,
    "valueoffset": 24
}, {
    "key": "\nKey3",
    "value": " multi-line value\nwhich continues here",
    "keyoffset": 52,
    "valueoffset": 58
}, {
    "key": "\nKey4",
    "value": " multi-line value which\n   continues here: has a colon\n   yet is still a value\n",
    "keyoffset": 96,
    "valueoffset": 102
}]

It works pretty flawlessly as far as I can tell, and seems quite efficient (it's only iterating through the string once), but I also find it's a little overcomplicated for what seems like a fairly simple task. However I can't figure out how to simplify it any further. Thoughts?

Answer 1

Regular expressions are a good solution here:

• They are often more performant than manually messing with indicies and checking values, especially when the logic to implement isn't trivial
• Their logic is much easier to understand at a glance than a long chunk of code
• The indicies of each match can be kept track of by checking the length of the full match

For this problem, you may use:

^(\w+):(.+(?:\n   .*|\n[^:\n]+$)*)

https://regex101.com/r/8NgGLZ/1

• ^(\w+): - Match the key at the beginning of a line, put it in a capture group, followed by :
• (.+(?:\n .*|\n[^:\n]+$)*) - Match the value in a capture group:
  • .+ - Match anything on the first line, followed by zero or more occurrences of:
    • \n .* - A newline, followed by 3 spaces, followed by anything else on the line, OR:
    • \n[^:\n]+$ - A newline, followed by anything but a colon or newline

Perform a global regular expression match using the above pattern, and then you can iterate through the capture groups:

function parseTitlePageChunk(text) {
    let currentOffset = 0;
    const pairs = [];
    const pattern = /^(\w+):(.+(?:\n   .*|\n[^:\n]+$)*)/gm;
    for (const [fullMatch, key, value] of text.matchAll(pattern)) {
        pairs.push({
            key,
            value,
            keyoffset: currentOffset,
            valueoffset: currentOffset + key.length + 1, // add 1 due to the ;
        });
        currentOffset += fullMatch.length + 1; // add 1 due to the \n that follows
    }
    return pairs;
}

const result = parseTitlePageChunk(`Key: in-line value
Key2: in-line value: with a colon
Key3: multi-line value
which continues here
Key4: multi-line value which
   continues here: has a colon
   yet is still a value`);
console.log(result);

I compared the runtime required of the above against your original code. Using .repeat(50000) on the example input, this looks to run 5 to 10 times faster: 800-1500ms vs 100-150ms.

Note that in my implementation, the keys do not include the newlines, which is why my indicies are one off of yours. (If you actually do want the keys to include possibly-existing prior newlines, it's a simple tweak)

In TypeScript syntax, change to the following:

type Pair = {
    key: string;
    value: string;
    keyoffset: number;
    valueoffset: number;
};
function parseTitlePageChunk(text: string) {
    let currentOffset = 0;
    const pairs: Array<Pair> = [];

Answer 2

My idea is to split text for the lines and then merge them by separating different key/value pairs. Next just parse all pairs from the list. This is similar to what Shelby suggested. Here is the code for complete solution:

const joinUntil = (lines, test) => {
    const index = lines.findIndex(test);
    const offset = index === -1 ? Infinity : index;
    return [lines.slice(0, offset).join('\n'), lines.slice(offset)];
}

const normalize = (lines) => {
    if (lines.length === 0) return [];
    const stop = (line, i) => i > 0 && line.includes(':') && !line.startsWith('   ');
    const [result, rest] = joinUntil(lines, stop);
    return [result].concat(normalize(rest));
}

const splitOnce = (str, sep) => {
    const [first, ...rest] = str.split(sep);
    return [first, rest.join(sep)];
}

const parsePair = (str) => {
    const [key, value] = splitOnce(str, ':');
    return { [key]: value }
}

const parse = (str) => normalize(str.split('\n')).map(parsePair);

console.log(parse(`Key: in-line value
Key2: in-line value: with a colon
Key3: multi-line value
which continues here
Key4: multi-line value which
   continues here: has a colon
   yet is still a value`));

Answer 3

Readability

Depending on how often this function is going to be called you could opt for a more readable version that may be slightly less performant. Using functions like split and map you could make this pretty simple. Here is an example below.

// Start with kvp strings and newline kvp strings.
var texts = [
    "key1: value1\r\nkey2: value2",
    "key3: value3",
    "key4: value4\r\nkey5: value5"
];

// Splits the newlines into their own kvp strings.
texts = texts.map(function (text) {
    return text.split("\r\n");
}).reduce(function (finalArray, arrayContainingArrays) { 
    // Pro-tip: Do not name these parameters a and b, it helps no one.
    return finalArray.concat(arrayContainingArrays);
});

// Now that we don't have to worry about newlines anymore.
var texts = [
    "key1: value1",
    "key2: value2",
    "key3: value3",
    "key4: value4",
    "key5: value5",
    // etc.
];

// Map each kvp string by splitting on colon.
var kvps = texts.map(function (text) { 
    var parts = text.split(":");
    // Split usually returns an array of at least one object, but something like "".split("") can return an empty array, so if there's an empty array set the value to [text].
    parts = parts.length > 0 ? parts : [text];
    // Shift(): Removes the first item in the array and returns it.
    var key = parts.shift(); 
    // Join on colon in case there were multiple colons (e.g. "key1: value1:hello" would result in { key: "key1", value: "value1:hello" }).
    // Additionally, if text doesn't contain a colon, add it as the key with an undefined value (e.g. "Hello World!" will become (e.g. { key: "Hello World!", value: undefined }).
    var value = parts.length > 0 ? parts.join(":").trim() : undefined;
    return { key: key, value: value };
});

Now, I want to state, I may have missed some of the functionality your function does and honestly, that's okay, I've written this for you to see an alternate path, not to necessarily walk you through that alternate path.

Other Notes

• I used \r\n instead of just \n, it's what I'm used to typing, working in a Windows environment.
• Not only is the way outlined above more readable, but it doesn't have any opportunities for those pesky "off by 1" errors.
• I've never written any TypeScript, but it doesn't seem like you're taking much advantage of TypeScript aside from the function declaration.
• Don't accept this as an answer, it is really just a note on readability. Someone that better knows TypeScript should write a code review.