Parsing shortcodes out of a string

Question

I wrote this shortcode parsing and it runs in \$O(N^2)\$. Is there a way to better optimize this?

  package shortcodes

  import (
          "regexp"
          "strings"
  )

  var (
          shortcodesRegex = regexp.MustCompile(`\[\S+(?:\s+[^="]+(|="[^"\]\s]+"))+\]`)
  )

  func Parse(content string) []map[string]string {
          results := make([]map[string]string, 0)
          indexes := shortcodesRegex.FindAllIndex([]byte(content), -1)

          for _, matches := range indexes {
                  result := make(map[string]string)
                  shortcode := string(content[matches[0]+1 : matches[1]-1])
                  parts := strings.Fields(shortcode)

                  for i, part := range parts {
                          if i == 0 {
                                  result["id"] = part
                                  continue
                          }

                          pair := strings.Split(part, "=")
                          if len(pair) > 1 {
                                  result[pair[0]] = pair[1][1 : len(pair[1])-1]
                          } else {
                                  result[pair[0]] = ""
                          }
                  }

                  results = append(results, result)
          }

          return results
  }

Here is one of the test cases I have written.

                  {
                          name: "basic",
                          args: args{`First shortcode is [fraction num="1" denom="2"] and the second is [square-root content="456"] which we will pass into a function which will return these IDs and all their values in a map`},
                          want: []map[string]string{
                                  {
                                          "id":    "fraction",
                                          "num":   "1",
                                          "denom": "2",
                                  },
                                  {
                                          "id":      "square-root",
                                          "content": "456",
                                  },
                          },
                  },

Answer 1

Thank you for the unit tests! They were invaluable; they really helped me to understand the problem you're tackling.

---

I am reading this

\[\S+(?:\s+[^="]+(|="[^"\]\s]+"))+\]

and I am not pleased with it, for several reasons.

There should be a comment illustrating the kind of text we seek to match. (The SMS reference was not helpful.)

The matching task seems fairly simple, yet this expression is relatively opaque. I do not find that it is a good means of communicating a technical idea to collaborators.

The ?: non-capturing group seems odd, and risks triggering excessive backtracking in the regex engine, which may be where your quadratic running time comes from.

Further down in the code we find that the string is parsed

• using regex
• using blank-delimited Fields
• using =-delimited Split

Surely a single regex with capturing groups could have picked out what we needed in one fell swoop?

If there is a specification for a valid Shortcode, please cite its URL. As written, this code is willing to accept e.g. a great deal of $%^&* punctuation, which I suspect is not part of the intended business use case.

Consider using a regex that looks more like this:

^\[([\w-]+)(\s+\w+="\d+")+\]$

Or perhaps with fine-grained capturing groups:

\[([\w-]+)(\s+(\w+)="(\d+)")+\]

If e.g. [a b-c="7"] is valid input, then turn \w+ into [\w-]+.

---

The Fields and Split logic is vanilla enough, with +/- 1 index offsets to strip punctuation. The logic is tightly bound to the regex, which validates that proper punctuation was found. I would be happier to see some of that logic pushed down into the regex, to keep it all in one place and make it more likely that maintainers will properly coordinate changes. Using fine-grained capturing groups seems a natural way to accomplish that.

---

Since "excessive running time" has been a challenge that this code has faced in the past, please add a unit test to address that and verify no regressions. Please add code that offers "very long" input strings to be parsed, and that notes elapsed wallclock time.