Apple Swift mangling rules for recurring context

On MacOS with Swift 5.6 and given the mangling rules from here with the following Swift code:

class Car //AB
{
    class Foo //AD
    {
        func Foo() -> Void //AD
        {
               
        }
    }
}

The resulting mangled name for Foo is _$s4TEST3CarC3FooCADyyF (Target name TEST), I cannot understand why Foo is given the index code AD, I would expect AC to be assigned:

AA   AB  AC 
TEST.Car.Foo.Foo

In this other example:

class TEST //AA
{
    class Car //AC
    {
        class Foo //AE
        {
            class Car //AC
            {
                func Foo() -> Void //AE
                {
                    
                }
            }
        }
    }
}

The mangled name is _$s4TESTAAC3CarC3FooCACCAEyyF, again those are the values I would assign:

AA        AB  AC
TEST.TEST.Car.Foo.Car.Foo

Why Foo is assigned to AE after the first long form encoding 3Foo? Why AB and AD are skipped and not used? Note that this is only in regards to recurrent items in the string, if the are no recurrent items i can encode all happily.

Solution

In the first case, the substitution indices are assigned as follows:

AA TEST
AB Car
AC TEST.Car
AD Foo
AE TEST.Car.Foo

You can get these results by using the demangling code from this question. Demangle the mangled name of the method, just without the F suffix - this is to allow us to add any A substitution of our choice to the end. (I've also removed the yy to reduce noise in the output)

print(swift_demangle("$s4TEST3CarC3FooCAdA")!)
print(swift_demangle("$s4TEST3CarC3FooCAdB")!)
print(swift_demangle("$s4TEST3CarC3FooCAdC")!)
print(swift_demangle("$s4TEST3CarC3FooCAdD")!)
print(swift_demangle("$s4TEST3CarC3FooCAdE")!)
/*
TEST.Car.FooFooTEST
TEST.Car.FooFooCar
TEST.Car.FooFooTEST.Car
TEST.Car.FooFooFoo
TEST.Car.FooFooTEST.Car.Foo
*/

So it turns out that, when the mangling algorithm mangles Car, it also "remembers" a substitution for TEST.Car (because it is a nominal type, perhaps), not just Car on its own. This happens regardless of whether the substitution is used later on or not, probably to make demangling easier (?)

You can also see this in effect when you change the code to:

class Car
{
    class Foo
    {
        func Foo() -> Car
        {
            fatalError("")
        }
    }
}

Now the method Foo's mangled name is $s6output3CarC3FooCAdCyF, making use of AC.

As a mental model, you can think of it as the substitution indices being associated with the letter C in the mangled name as well as the <number><identifier> parts, like this:

$s4TEST3CarC3FooCADyyF
   ^     ^ ^  ^ ^
   |     | |  | |
  AA     ABAC ADAE

A similar thing happens in the second case. AB is TEST.TEST and AD is TEST.TEST.Car.