Extract generic type parameters from a string

Question

I want to create a function that extracts 'generic type parameters' from a type definition (as plain string).

It should take an input string like this:

Foo<Bar, Baz<Qux>>

And return an object with the referenced types + generics, something like this (doesn't have to be in this exact format of course, as long as I can retrieve the required information):

{
   "name": "Foo",
   "generics": [
      {
         "name": "Bar",
         "generics": []
      },

      {
         "name": "Baz",
         "generics": [
            {
               "name": "Qux",
               "generics": []
            }
         ]
      }
   ]
}

My guess would be to use String.match with a regex like /<.*>/g, split the result with a comma as delimiter, and recursively parse the generics of each parameter. However, I feel like this is way too complicated and that there's a much easier way that I'm missing.

Answer 1

if you are Chrome user, this code working in console:

// let inputString = "Foo<Bar, Baz<Qux<Some, Thing<Else<But, Not>, So<Is>>, Other>>>"
let inputString = "Foo<Bar, Baz<Qux>>"
const replacements = {}
let replacementIndex = 0
while (true) {
  const replacement = (inputString.match(/[A-Z][a-z0-9]+<(([A-Z][a-z0-9]+)[,\s]*)+>/) || [])[0]
  if (replacement) {
    const key = `Key${replacementIndex}`
    replacementIndex++
    replacements[key] = replacement
    inputString = inputString.replace(replacement, key)
  } else {
    break
  }
}

const resultJson = {}

const parseSentence = (text) => {
  const [key, valuesStr] = text.replace(/>$/, '').split(/</)
  const values = valuesStr.split(',').map((x) => x.trim())
  return {
    [key]: values,
  }
}

Object.keys(replacements).forEach((key) => {
  resultJson[key] = parseSentence(replacements[key])
})

while (true) {
  let replacementsFound = false
  Object.keys(resultJson).forEach((key) => {
    Object.keys(resultJson[key]).forEach((name) => {
      resultJson[key][name] = resultJson[key][name].map((value) => {
        if (/^Key[\d+]$/.test(value)) {
          replacementsFound = true
          return resultJson[value]
        }
        return value
      })
    })
  })
  if (!replacementsFound) {
    break
  }
}

const resultKey = `Key${replacementIndex - 1}`
const unpreparedResult = resultJson[resultKey]

const prepareResultJson = (json) => {
  const name = Object.keys(json)[0]
  const generics = []
  json[name].forEach((generic) => {
    if (typeof generic === 'string') {
      generics.push({ name: generic, generics: [] })
    } else {
      generics.push(prepareResultJson(generic))
    }
  })
  const result = {
    name,
    generics,
  }
  return result
}

const finalResult = prepareResultJson(unpreparedResult)

console.log(finalResult)

Also you can follow this url: https://codepen.io/SergioBelevskij/pen/ZPdVyM

Answer 2

Heavily inspired by Mr. Polywhirl's answer I created the following implementation:

^{(With Typescript type annotations for clarity)}

type TypeInfo = { //the returned object format
    name: string;
    generics: TypeInfo[];
}

function parseGenerics(input: string): TypeInfo {
    input = input.trim();
    const startIndex = input.indexOf('<'),
          endIndex = input.lastIndexOf('>');

    if (startIndex !== -1 && endIndex === -1) {
        throw new Error("Missing closing bracket '>' for " + input);
    } else if (startIndex === -1 && endIndex !== -1) {
        throw new Error("Missing opening bracket '<' for " + input);
    } else if (startIndex === -1 && endIndex === -1) { //no generics
        return {
            name: input,
            generics: []
        };
    } else {
        const head = input.substring(0, startIndex),
              tail = input.substring(startIndex + 1, endIndex);

        return {
            name: head,
            generics: tail.split(/\s*,\s*/).map(parseGenerics)
        };
    }
}

Using Foo<Bar, Baz<Qux>> as input this results in:

{
    "name": "Foo",
    "generics": [
        {
            "name": "Bar",
            "generics": []
        },
        {
            "name": "Baz",
            "generics": [
                {
                    "name": "Qux",
                    "generics": []
                }
            ]
        }
    ]
}

I prefer this implementation over Mr. Polywhirl's because it immediately creates the correct data format instead of needing additional conversion steps. This makes it (in my opinion) a cleaner and more streamlined solution.

Answer 3

The easiest way to do this would to recursively build a key-map structure and then convert that to a tree.

The keyMapToTree function below uses an internal helper function called keyMapToTreeInner.

console.log(keyMapToTree(parseAsKeyMap('Foo<Bar, Baz<Qux>>')));

function parseAsKeyMap(input, tree = {}) {
  input = input.trim();
  let startIndex = input.indexOf('<'),
    endIndex   = input.lastIndexOf('>');
  if (startIndex !== -1 && endIndex === -1) {
    throw new Error("Missing closing bracket '>' for " + input);
  } else if (startIndex === -1 && endIndex !== -1) {
    throw new Error("Missing opening bracket '<' for " + input);
  } else if (startIndex !== -1 && endIndex !== -1) {
    let head = input.substring(0, startIndex),
      tail = input.substring(startIndex + 1, endIndex);
    tree[head] = {};
    tail.split(/\s*,\s*/).forEach(token => parseAsKeyMap(token, tree[head]));
  } else {
    tree[input] = {};
  }
  return tree;
}

function keyMapToTree(input) {
  let keys = Object.keys(input);
  if (keys.length !== 1) {
    throw new Error('Object must be non-null and have only one key!');
  }
  let key = keys[0], node = { name: key, generics: [] };
  keyMapToTreeInner(input[key], node.generics);
  return node;
}

function keyMapToTreeInner(input, nodeArray) {
  Object.keys(input).map(key => {
    let node = { name: key, generics: [] };
    keyMapToTreeInner(input[key], node.generics);
    nodeArray.push(node)
  });
}

.as-console-wrapper {
  top: 0;
  max-height: 100% !important;
}

<!--

The initial key-map will look like this, so convert this structure to a tree.

{
  "Foo": {
    "Bar": {},
    "Baz": {
      "Qux": {}
    }
  }
}

-->