The collision resolution mechanism in `ImportUsed` is insufficient when importing > 2 packages with the same base name

[theclapp]

The following test case triggers an unexpected result

func TestSimilarPackageNames(t *testing.T) {
	const c = 300

	// The error we're checking for is a heisenbug in interp.ImportUsed() that
	// depends on map iteration order, so basically we have to keep trying till
	// it happens. Once it's fixed then of course it'll never happen so we
	// can't just iterate forever. :) But 10 tries seems to do it.
	for j := 0; j < 10; j++ {
		var ignore int
		var output int

		i := interp.New(interp.Options{})
		require.NotNil(t, i)

		i.Use(interp.Exports{
			"pkg/pkg": {
				"Output": reflect.ValueOf(&output).Elem(),
			},
			// This package has various things but no "Bold"
			"github.com/user1/proj1/font/font": {
				"Ignore": reflect.ValueOf(&ignore).Elem(),
			},
			// This package also has various things but no "Bold"
			"github.com/user2/proj2/font/font": {
				"Ignore": reflect.ValueOf(&ignore).Elem(),
			},
			"github.com/user3/proj3/font/font": {
				"C": reflect.ValueOf(c),
			},
		})
		i.ImportUsed()

		_, err := i.Compile(`
package main
import (
	font "github.com/user3/proj3/font"
	. "pkg"
)
func main() {
	*&Output = font.C
}
`)
		// Expect a "compile-time" error.
		require.NoError(t, err)
	}
}

Expected result

No errors / all tests pass.

Got

% go test ./interp -run TestSimilarPackageNames

# this run is fine: "font" => proj3
interp.go:648: ImportUsed: Collision: k: github.com/user2/proj2/font, orig name: "font", name2: "github.com/user1/proj1_font/_.go", new name: "github.com/user2/proj2_font/_.go"
interp.go:663: sc.sym: font -> github.com/user3/proj3/font
interp.go:663: sc.sym: github.com/user1/proj1_font/_.go -> github.com/user1/proj1/font
interp.go:663: sc.sym: github.com/user2/proj2_font/_.go -> github.com/user2/proj2/font
interp.go:663: sc.sym: pkg -> pkg

# this run is fine, too: font => proj3
interp.go:648: ImportUsed: Collision: k: github.com/user2/proj2/font, orig name: "font", name2: "github.com/user1/proj1_font/_.go", new name: "github.com/user2/proj2_font/_.go"
interp.go:663: sc.sym: font -> github.com/user3/proj3/font
interp.go:663: sc.sym: github.com/user1/proj1_font/_.go -> github.com/user1/proj1/font
interp.go:663: sc.sym: github.com/user2/proj2_font/_.go -> github.com/user2/proj2/font
interp.go:663: sc.sym: pkg -> pkg

# this run fails: font => proj1, shadowing proj3
interp.go:648: ImportUsed: Collision: k: github.com/user3/proj3/font, orig name: "font", name2: "github.com/user2/proj2_font/_.go", new name: "github.com/user3/proj3_font/_.go"
interp.go:663: sc.sym: font -> github.com/user1/proj1/font
interp.go:663: sc.sym: github.com/user2/proj2_font/_.go -> github.com/user2/proj2/font
interp.go:663: sc.sym: github.com/user3/proj3_font/_.go -> github.com/user3/proj3/font
interp.go:663: sc.sym: pkg -> pkg
--- FAIL: TestSimilarPackageNames (0.00s)
    interp_eval_test.go:1978:
                Error Trace:    [...]/github.com/traefik/yaegi/interp/interp_eval_test.go:1978
                Error:          Received unexpected error:
                                8:13: package font "github.com/user1/proj1/font" has no symbol C
                Test:           TestSimilarPackageNames
FAIL
FAIL    github.com/traefik/yaegi/interp 0.363s
FAIL

Yaegi Version

381e045

Additional Notes

I instrumented ImportUsed as follows:

 func (interp *Interpreter) ImportUsed() {
 	sc := interp.universe
+	collision := false
 	for k := range interp.binPkg {
 		// By construction, the package name is the last path element of the key.
 		name := path.Base(k)
+		origName := name
 		if sym, ok := sc.sym[name]; ok {
 			// Handle collision by renaming old and new entries.
 			name2 := key2name(fixKey(sym.typ.path))
@@ -641,9 +645,24 @@ func (interp *Interpreter) ImportUsed() {
 				delete(sc.sym, name)
 			}
 			name = key2name(fixKey(k))
+			log.Printf("ImportUsed: Collision: k: %s, orig name: %q, name2: %q, new name: %q", k, origName, name2, name)
+			collision = true
 		}
 		sc.sym[name] = &symbol{kind: pkgSym, typ: &itype{cat: binPkgT, path: k, scope: sc}}
 	}
+	if collision {
+		var names []string
+		for name, sym := range sc.sym {
+			if sym != nil && sym.typ != nil && sym.typ.path != "" {
+				names = append(names, name)
+			}
+		}
+		sort.Strings(names)
+		for _, name := range names {
+			sym := sc.sym[name]
+			log.Printf("sc.sym: %v -> %v", name, sym.typ.path)
+		}
+	}
 }

As the comment in the test notes, this is a "heisenbug" that depends on the map traversal order of interp.binPkg.

If you have one "font" packages, there's no collision.

If you have two "font" packages, one is renamed to (for example) github.com/user1/proj1_font/_.go and the other to github.com/user2/proj2_font/_.go, and that's still fine.

But if you have three, then the first two are renamed, and the third keeps its real name, thus shadowing the other two and hiding their symbols. Whether the test fails depends on whether github.com/user3/proj3/font loses the renaming fight.

In the first two times through the loop in the sample output, it "wins", but "loses" on the third iteration.

[theclapp]

It turns out this isn't actually a "heisenbug" ("a software bug that seems to disappear or alter its behavior when one attempts to study it"), as such, it's just random. There doesn't seem to be a special name for that kind of bug. 😆

[theclapp]

As a concrete example, a project I'm using Yaegi with imports these three "font" packages:

gioui.org/font github.com/go-text/typesetting/font github.com/go-text/typesetting/opentype/api/font