A means of generating all the possible combination of MQTT wildcards and token arrangements for a given topic while minimizing allocations as much as possible. The topic should not contain any wildcard to begin with plus as per the MQTT specification, it should have at least 1 character

mqtt_generate_topics.go

package main

import (
	"fmt"
	"strings"
)

type node struct {
	val            string
	isIntermediary bool
	exact          *node
	singleLevel    *node
}

func populate(parent *node, tokens []string) {
	parent.isIntermediary = true
	parent.exact = &node{val: tokens[0]}
	parent.singleLevel = &node{val: "+"}
	if len(tokens) == 1 {
		return
	}
	populate(parent.exact, tokens[1:])
	populate(parent.singleLevel, tokens[1:])
}

// tokens should be of length >= 1 otherwise panics
func generateTopicStrings(tokens []string) []string {
	// create tree of each possible combination of tokens & wildcards
	root := new(node)
	populate(root, tokens)

	// the expected no. of pure single level topics is the number of leaves.
	// hence, if we have 3 levels e.g. from the topic foo/bar/quz, we'll
	// expect 2^3 pure single level tokens. Courtesy of binary representation
	// and bitshifts, this operation is equivalent to 1 << 3. Hence, with L levels
	// we get the result via 1 << l
	noTopics := (1 << len(tokens))

	// the expected no. of topics terminated by # ie a multilevel match is a geometric series.
	// Drawing out the tree, each and every node from the root can be extended
	// to have a '#' as a child. Suppose we have foo/bar/quz as the select topic.
	// At the zeroth level (ie root), we have 1 '#' since it matches every topic.
	// At the first level, we have 'foo/#' and '+/#' ie 2^1. At the second level, we have
	// 'foo/bar/#', 'foo/+/#', '+/bar/#' and '+/+/#' ie 2^2.
	// Hence with L levels, the expected result is 1 + 2^1 + 2^2 + ... 2^L.
	// Using the formula for summing geometric series and simplifying, we end up with 2^(L+1) - 1
	// Once again, courtesy of binary representation and bitshifts, this operation is equivalent to
	// 1 << (L+1) - 1, which is equal to 2 << L - 1
	noTopics += (2 << len(tokens)) - 1
	generatedTopics := make([]string, 0, noTopics)

	// ensure temp has enough space to avoid
	// unecessary allocations
	temp := make([]string, 0, len(tokens)+1)

	// ensure string builder has enough space to avoid unecessary allocations
	// the possible max length for a given generated string is the sum of the length of
	// each token plus space for the '/' separators plus a multilevel '#' at the end
	strBLen := 0
	for _, t := range tokens {
		strBLen += len(t)
	}
	strBLen += (len(tokens) + 1)

	// traverse the tree. On each leaf-node, a slice 'ts' temporarily holding
	// the tokens for a given generated topic shall be 'emitted'. Furthermore,
	// on both leaf-nodes and intermediary nodes, 'ts' shall be emitted with
	// the contents of multi-level match token
	traverse(root, temp, func(ts []string) {
		var strB strings.Builder
		strB.Grow(strBLen)

		strB.WriteString(ts[0])
		for _, t := range ts[1:] {
			strB.WriteByte('/')
			strB.WriteString(t)
		}
		generatedTopics = append(generatedTopics, strB.String())
	})

	return generatedTopics
}

func traverse(n *node, temp []string, emitTokens func([]string)) {
	if n.isIntermediary == true {
		traverse(n.exact, append(temp, n.exact.val), emitTokens)
		traverse(n.singleLevel, append(temp, "+"), emitTokens)
	} else { // isLeaf
		emitTokens(temp)
	}
	emitTokens(append(temp, "#"))

}

func main() {
	// assume a given topic 'foo/bar/quz' is already split
	// into its constituent tokens
	tokens := []string{"foo", "bar", "quz"}
	ts := generateTopicStrings(tokens)
	for _, t := range ts {
		fmt.Println(t)
	}
}
/*
OUTPUT:

  foo/bar/quz
  foo/bar/quz/#
  foo/bar/+
  foo/bar/+/#
  foo/bar/#
  foo/+/quz
  foo/+/quz/#
  foo/+/+
  foo/+/+/#
  foo/+/#
  foo/#
  +/bar/quz
  +/bar/quz/#
  +/bar/+
  +/bar/+/#
  +/bar/#
  +/+/quz
  +/+/quz/#
  +/+/+
  +/+/+/#
  +/+/#
  +/#
  #
  
*/