How to consistently stringify maps when key iteration is not ordered?

Question

I am building a heterogeneous map for an interpreted programming language in Go. As part of the language, I want to be able to stringify any value for printing.

I have the following code:

// ObjKind helps determine what kind of object it is
type ObjKind uint

// Obj is an interface for all values in golflang.
// Any values must implement this interface.
type Obj interface {
    Bool() bool
    Equal(o Obj) bool
    Kind() ObjKind  // the kind of this object
    Repr() string   // debug representation of this object
    String() string // stringified representation of this object, for printing
}

type Map map[Obj]Obj

func (m Map) String() string {
    vs := []string{}
    for k, v := range m {
        vs = append(vs, fmt.Sprintf("%s:%s", k.String(), v.String()))
    }
    return fmt.Sprintf("{%s}", strings.Join(vs, ","))
}

However, this implementation has the flaw that iterating over keys in a map do not have consistent order, leading to my unit tests failing by having the elements in different orders each run. I cannot take the maps.Keys() and sort it, because this is a heterogenous map and the elements aren't necessarily the same type nor comparable (in the language's semantics).

Is there a way to guarantee an ordered iteration through such a map's keys, so that String() here consistently outputs the same string?

Map keys must be comparable, that’s literally the only requirement for a map key. If you want a certain ordering, what problem do you have defining the order you want? — Mr_Pink
– Mr_Pink, Commented Apr 24 at 18:15
go.dev/ref/spec#For_statements says "The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next." Perhaps use a slice to store the order of objects added to the map? — aMike
– aMike, Commented Apr 24 at 18:51
The suggestion to read keys-value pairs into a slice and then sort this slice will work. But since it seems that your question is related to unit testing - another possibility is to change your test assertions. Instead of asserting assert.Equals(obj.String(), "{a:A,b:B}") you could instead assert assert.Equal(2, strings.Count(obj.String(), ":")) (assert that there are 2 pairs) && assert.Contains(obj.String(), "a:A") && assert.Contains(obj.String(), "b:B"). — phonaputer
– phonaputer, Commented Apr 24 at 21:49

eik · Accepted Answer · 2025-04-25 12:38:27Z

1

How about using slices.Sort?

func (m Map) String() string {
    vs := make([]string, 0, len(m))
    for k, v := range m {
        vs = append(vs, fmt.Sprintf("%s:%s", k.String(), v.String()))
    }
    slices.Sort(vs)

    return fmt.Sprintf("{%s}", strings.Join(vs, ","))
}

Note for your Map that “If the key type is an interface type, [the comparison operators == and !=] must be defined for the dynamic key values; failure will cause a run-time panic.”

edited Apr 25 at 12:38

answered Apr 25 at 12:15

eik

4,7811 gold badge16 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user615344 · Accepted Answer · 2025-04-25 04:28:47Z

0

this is just a classic design decision. you have two choices, each with a drawback:

map

use this:

type Map map[Obj]Obj

but then you lose the ability to maintain any order of elements

slice

use one of these:

type SliceArray [][2]Obj

type SliceStruct []struct { Key, Value Obj }

but then you lose the ability to quickly index into a value

edited Apr 25 at 4:28

answered Apr 25 at 4:28

user615344

12 bronze badges

Collectives™ on Stack Overflow

How to consistently stringify maps when key iteration is not ordered?

2 Answers 2

Comments

map

slice

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

map

slice

Comments

Your Answer

Sign up or log in

Post as a guest

Related