4
\$\begingroup\$

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):

enter image description here

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?

\$\endgroup\$
1
  • \$\begingroup\$ Java .properties files use a backslash key: xxx/ new line __yyy/ new line __zz. Which seems a bit more safe. But that is a matter of taste. \$\endgroup\$ – Joop Eggen Nov 17 '20 at 11:59
2
\$\begingroup\$

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> = [];
\$\endgroup\$
3
  • 1
    \$\begingroup\$ "Their logic is much easier to understand at a glance than a long chunk of code." I definitely disagree with that. ^(\w+): Completely agree. I barely know regex and this makes sense to me. However, none of this (.+(?:\n .*|\n[^:\n]+$)*) makes any sense at a glance. I'm not saying regex is bad, it's performant and has its place, but it's definitely incorrect to say it is any degree of easy to understand at a glance. Maybe a very very long glance lol. \$\endgroup\$ – Shelby115 Nov 17 '20 at 1:03
  • \$\begingroup\$ Thanks! I always underestimate how fast regular expressions are - and you're right, this is a hell of a lot faster. Running it x1000 on each keystroke, i'm getting between two to ten times the performance that my initial function is. I'm curious what the difference would be on a lower-level language though. \$\endgroup\$ – user2950509 Nov 17 '20 at 10:58
  • \$\begingroup\$ also, I replaced for (const [fullMatch, key, value] of text.matchAll(pattern)) with while ((match = pattern.exec(text)) !== null) so that it isn't incompatible with any browsers which haven't implemented ECMAScript 2020 \$\endgroup\$ – user2950509 Nov 17 '20 at 11:01
1
\$\begingroup\$

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`));
\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ Thanks! It'll be run pretty often (on every keypress) so I'd rather keep it as performant as possible - but it's a good point about \r\n, I haven't actually tested it properly with anything other than LF line endings. About typescript, it's true I'm not really taking advantage of it much, but that's because it's all pretty straightforward code. As far as I can tell there's not really many occasions to utilize it, so yeah it's pretty much just javascript at this point. \$\endgroup\$ – user2950509 Nov 16 '20 at 14:35
  • 1
    \$\begingroup\$ @user2950509 IMO, TypeScript shines best when the code that is written looks almost identical to JavaScript. That way, it's as easy to understand as JS, except with the added bonus that it warns you when you attempt to use a certain value unsafely. Code with lots of TypeScript syntax (while sometimes necessary) can be harder to read and is sometimes an indication of over-engineering. \$\endgroup\$ – CertainPerformance Nov 17 '20 at 0:16
  • \$\begingroup\$ To whoever downvoted me, I would appreciate a comment on why I was downvoted. Is something I wrote incorrect? \$\endgroup\$ – Shelby115 Nov 25 '20 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.