DEV Community: Daniel Marinho

Parsing a JSON String recursively in a BFS style.

Daniel Marinho — Sat, 03 Feb 2024 19:55:42 +0000

This week I had to face a rather peculiar challenge, not because of the context it was embedded in, but because the insight for solving the problem ended up arising from memories of college days in data structure classes (which made me rethink some fallacies). 😁

Context 📝

Here's the deal: In a bank where message events were stored in JSONB format (Postgres), there were several messages saved as text; basically, a JSON String. The problem is that in this format, you can't take advantage of Postgres to index these messages or perform operations on them as if they were objects, for example:

--- events.data:
--- "{\"user\": { "\name\": \"daniel\", \"age\": \"30ish\" }}"

SELECT data FROM "events" WHERE data->'user'->>'name' = 'daniel';

The scenario above simply won't work because the information that should be JSONB is stored as text. To make matters worse, to make this work, I would have to iterate over this text by applying a "regex" to it, which is a terrible idea:

--- events.data:
--- "{\"user\": { "\name\": \"daniel\", \"age\": \"30ish\" }}"

SELECT data FROM "events" WHERE data::TEXT LIKE '%daniel%';

There are millions of complications and flaws in this model that I don't even know where to begin. To make matters worse, there are event records where there were several layers of string escaping, for example:

--- events.data:
--- "{\"user\": { \"name\": \"daniel\", \"age\": \"30ish\", \"address\": \"{ \\\"street\\\": \\\"some avenue\\\", \\\"number\\\": \\\"007\\\", \\\"state\\\": \\\"my precious state\\\" }\" }}"

As you descended another level within the object, more string escapes would exist. 😱

The Pseudo Solution 🐛

At first, the solution I had in mind was simple. I knew I could set up a small JavaScript routine to use JSON decoding natively and get an object in the end:

const jsonString = "{\"user\": { \"name\": \"daniel\", \"age\": \"30ish\", \"address\": \"{ \\\"street\\\": \\\"some avenue\\\", \\\"number\\\": \\\"007\\\", \\\"state\\\": \\\"my precious state\\\" }\" }}";

const jsonObject = JSON.parse(jsonString);

console.log(jsonObject);
/**
*{
*  user: {
*    "name": "daniel",
*    "age": "30ish",
*    "address": "{
*      \"street\": \"some avenue\",
*      \"number\": \"007\",
*      \"state\": \"my precious state\"
*    }"
*  }
*}
**/

Using this approach, I could only solve the problem of the first layer. From the second layer onwards, the data would still not be in the object format I needed. I would have to do the process again, and again for each key, where the value persisted as a string.

Dividing the Problem 🧩

At first, I needed to break this problem into smaller things, starting with converting a string to an object, considering 2 possible scenarios:

The JSON could have undergone only one conversion to String, which would simplify our process to just reversing the method, applying JSON.parse().

The JSON could have undergone numerous conversion processes to String, making things a bit more complicated: I would need to convert the string N times until it became an object.

By solving these two problems, I could solve the larger problem (3rd problem) which was to rethink the process of converting a string to an object, iteratively over all the keys of the JSON.

Problem number 1 was already solved. I decided to use the method provided in JavaScript to transform a JSON String into an Object by applying JSON.parse(). For this, I just needed to make sure that I was converting a string and not trying to apply JSON.parse() on an object; which would throw an error at runtime.

export function isJsonParsable(json: unknown): boolean {
  try {
    if (typeof json === "string") {
      JSON.parse(json);
      return true;
    } else {
      return false;
    }
  } catch {
    return false;
  }
};

With the help of this utility, I could reuse it to check the value I was going to try to convert before applying the conversion:

export function cleanJsonString(
  result: string | Record<string, any>,
): Record<string, any> {
  if (isJsonParsable(result)) {
    return cleanJsonString(JSON.parse(result as string));
  } else {
    return result as Record<string, any>;
  }
}

These two functions would help me solve the main problem: converting the entire JSON String to a final object.

Applying BFS to a JSON ✨

Firstly; I understood that when we apply JSON.parse() on a JSON String, it flattens it layer by layer, so to speak. If I apply JSON.stringify() on an object 3 times, to undo it, I need to apply JSON.parse() also 3 times to get the original value.

Based on this, I need to iterate over this structure, recursively, where for each new property that exists within the object, I redo the conversion process until all JSON properties are flattened.

The structure of an object is similar to the structure of a tree. You have several nodes that in turn can have another node or a primitive value, where it would be the end of the line, a leaf.

Applying BFS in this sense, I convert each key of the JSON to an object until it can no longer be converted. At this point, I start converting the children, always recursively, until at some point there will be no descendants left to be converted.

export function treeParsing(jsonString: string): Record<string, any> {
  // We use a closure responsible for iterating
  const bfs = (node: Record<string, any>): void => {
    for (const key in node) {
      // We will only flatten the nodes;
      if (isJsonParsable(node[key])) {
        node[key] = cleanJsonString(node[key]);
        bfs(node[key]);
      // We won't try to flatten leaves;
      } else if (typeof node[key] === "object") {
        bfs(node[key]);
      }
    }
  };
  // Validate that we will work with valid JSON String;
  if (!isJsonParsable(jsonString)) return;
  // Flatten the first level to work on the nodes;
  const jsonData: Record<string, any> = cleanJsonString(jsonString);
  bfs(jsonData);
  return jsonData;
}

Applying BFS to each key of the object, I end up generating recursively the flattening of strings for each node. In the end, our example string where the deepest levels contain an excessive process of escapes, ends up returning to the original object:

const jsonString = "{\"user\": { \"name\": \"daniel\", \"age\": \"30ish\", \"address\": \"{ \\\"street\\\": \\\"some avenue\\\", \\\"number\\\": \\\"007\\\", \\\"state\\\": \\\"my precious state\\\" }\" }}";

const jsonObject = treeParsing(jsonString);

console.log(jsonObject);
/**
*{
*  user: {
*    name: "daniel",
*    age: "30ish",
*    address: {
*       street: "some avenue",
*       number: 007,
*       state: "my precious state",
*     }
*  }
*}
**/

Now, the fun part! What's the time complexity of this beast? Well, for the validation part in the isJsonParsable function, it mainly uses the JSON.parse() to iterate over every character in the string to validate if the whole string sequence is a valid JSON string. Linear operation, that's an O(p). Now, the cleanJsonString will depend on the number of times we'll need to convert the string back into an object. That differs from string to string, also linear, let's call O(s). Now for the recursive part, this will run every time for every new key-value the BFS generates; also linear time. We'll call it a classic O(n).

Time

O(n) * (O(p) + O(s))
O(n) * O(p + s)
// reducing constants
O(n)

In terms of time complexity, it's still linear, O(n), because even though the sizes of "p" and "s" might differ from "n", they are not independent of it. As "n" grows, both "p" and "s" are influenced by it. Therefore, the overall time complexity is still linear. So yes, we can say it's equivalent to O(n).

For space, we have a single variable - jsonData - that stores all the information about the string and its value in a single space. Since its size depends on the size of the JSON itself, we can call it an O(n) in space.

Space

O(n)

There it is! A moment of epiphany that brought back good memories from college and made me rethink the phrase "I'll never use this in my life". 😂

Made myself a repo of this, for future reference. :)

TypeScript: The Power of Never 🙅‍♂️

Daniel Marinho — Thu, 14 Sep 2023 21:28:53 +0000

When creating new types or interfaces in your projects, you may come up with crazy solutions to solve a problem to ensure property values that actually can be handled at the type level of your code.

Drafting

Just recently, I was creating my personal site and experimenting with new things and ideas, and one of them was to have a mutable type to use as the propType for a component that was responsible for handling gradient headers on a page.

The main idea is that you can use custom colors to set your left and right edges, but also, have the option to define a custom linear gradient if you like. The catch is, they can't co-exist at the same time.

In our drafted idea, our type would be something like this:

type GradientTitle = {
   name: string;
   leftColor?: string;
   rightColor?: string;
   customColor?: string;
}

This way, we can set our gradient with custom values, like so (using pug 🐶):

...
GradientTitle(
   name="My Awesome Name"
   leftColor="#a163f1"
   rightColor="#3498ea"
)
...

If we want to use a custom gradient, we could do it, like so:

GradientTitle(
   name="My Awesome Name"
   customColor="linear-gradient(45deg,#a163f1,#6363f1 22%,#3498ea 40%,#40dfa3 67%, rgba(64, 223, 163, 0));"
)

The problem here is that there is nothing that blocks us from having the two options at the same time. Moreover, what should happen if we have both options set?

// Gradient hell
GradientTitle(
   name="My Awesome Name"
   leftColor="#a163f1"
   rightColor="#3498ea"
   customColor="linear-gradient(45deg,#a163f1,#6363f1 22%,#3498ea 40%,#40dfa3 67%, rgba(64, 223, 163, 0));"
)

Ideias

First off, having everything optional does not seem reasonable. What if I say I have this for "leftColor" and nothing, for "rightColor"? That would have us creating business logic inside the component just to handle what properties have values or not and then deciding if we should use leftColor and rightColor, or customColor.

We would need to create a function just to validate our props to decide what to use, something like this:

const isCustomColor: boolean = (props: GradientTitle) =>
   typeof props.leftColor !== 'string' && typeof props.rightColor !== 'string' && typeof props.customColor === 'string';

...
if (isCustomColor(props)) {
 // Use props.customColor
} else {
 // Use props.leftColor and props.rightColor
}

That is one way of resolving this problem at runtime. However, wouldn't it be nicer to solve this issue at the type level? I mean, let's make TS do this job for us, shall we?

In our case, we have our GradientTitle type already defined:

// remember
type GradientTitle = {
   name: string;
   leftColor?: string;
   rightColor?: string;
   customColor?: string;
}

First off, let's decide what is mandatory for this type. The name seems to be the key value for this component to exist, so let's have it as our base type:

type GradientProp = {
   name: string;
}

Nice! Now, we should handle how we should address the colors, in a way we can have the option of using left and right or using a custom value, but never both. See what I did there? never? 😂

The NEVER type

Never in TypeScript deserves a whole new topic, but essentially, it's a way to define a type that should never be present. Simply put, JavaScript does not have a primitive value of type "never". We have string, number, bigint, boolean, symbol, null, and undefined. So, when it comes to the type level when a property of type never exists in the scope, the TS throws an error informing us that "this shouldn't be here".

Phew! That's a lot of information in a short paragraph. With that said, let's use this never to our advantage.

Back to the example

There are two options available in our scenario: one is having both left and right colors defined but never having customColor, and the other is to have the customColor defined but never have left and right colors set. That would leave us with this:

type GradientProps = {
   name: string;
}

type LeftAndRightColors = {
   leftColor: string;
   rightColor: string;
   customColor?: never;
}

type CustomColor = {
   customColor: string;
   rightColor?: never;
   leftColor?: never;
}

You might be asking, "Why are there optional values in these types?". I got you! Let's think about that.

In the type LeftAndRightColors, we should set the left and right colors. If customColor wasn't optional, the TS would yell at us saying that we should have a value of type 'never' to this property. However, if you assign anything to customColor in this object, you'll get a type error.

type LeftAndRightColors = {
   leftColor: string;
   rightColor: string;
   customColor: never;
}

const LRColors: LeftAndRightColors = {
      // ^error: Property 'customColor' is missing in type.
   leftColor: "#000000",
   rightColor: "#111111"
}

Now, if we have it as an optional property, the TS would not yell at us when missing. Moreover, as we have its type defined as never, if we set anything to it we also get an error.

type LeftAndRightColors = {
   leftColor: string;
   rightColor: string;
   customColor?: never;
}

const LRColors: LeftAndRightColors = {
   leftColor: "#000000",
   rightColor: "#111111",
   customColor: "anything"
   // ^erro: Types of property 'customColor' are incompatible.
}

Now, we have two types defining the two scenarios we may encounter. However, we can still improve this.

Separation of concerns

It does not seem reasonable to have these properties repeating themselves within these two types, LeftAndRightColor and CustomColor. We should have their values defined as normal and then have new types to negate the property value when necessary. Like so:

type LeftAndRightColors = {
   leftColor: string;
   rightColor: string;
}

type CustomColor = {
   customColor: string;
}

type CustomNotAllowed = {
   customColor?: never;
}

type LRNotAllowed = {
   leftColor?: never;
   rightColor?: never;
}

With that, we can use our intersection operator to define the negatives in our types, just by intersecting them, like so:

type LeftAndRightColors = {
   leftColor: string;
   rightColor: string;
} & CustomNotAllowed;

type CustomColor = {
   customColor: string;
} & LRNotAllowed;

Using Type Operations

In TypeScript we have what we call Union Types and Intersection Types. Union Types are types that are combined using the | symbol and Intersection Types are types that are combined with the & symbol. The idea is that you can create a new type by combining some existing types, making their type rules co-exist.

When we intersect two types, it creates a new type combining all its property rules as a result. In addition, we can easily understand whats going on by renaming our boundaries.

type GradientProps = {
   name: string;
}

type LRNotAllowed = {
   leftColor?: never;
   rightColor?: never;
}

type CustomNotAllowed = {
   customColor?: never;
}

type LeftAndRightColors = {
   leftColor: string;
   rightColor: string;
} & CustomNotAllowed;

type CustomColor = {
   customColor: string;
} & LRNotAllowed;

export type GradientTitle = GradientProps & (LeftAndRightColors | CustomColor);

Finally, we have TypeScript handling at the type level of what properties are allowed to exist based on the values. Also, we can easily understand what each type is responsible for and combine its effects using type operators.

Conclusion

The never type in TypeScript can be very helpful when defining boundaries on property values. Combined with operators, we can create very powerful types that better handle specific rules of complex components.