Possible issue with TypeStructure (type subsumption cache keys)

[majocha]

On discord there is a report that VS insiders 1111.16
throws "FS0193 internal error: Array dimensions exceeded supported range" when editing a repo.

In previous insiders the same repo caused problems during build in VS:

clr!CopyValueClassUnchecked+0xdd
clr!MethodTable::FastBox+0x3e
clr!MethodTable::Box+0x81
clr!ReflectionInvocation::TypedReferenceToObject+0xfe
mscorlib+0x54ca7b
FSharp_Core!Unknown+0x66
FSharp_Core!Unknown+0xb4
FSharp_Compiler_Service!FSharp.Compiler.TypeRelations+TTypeCacheKey.Equals(TTypeCacheKey, System.Collections.IEqualityComparer)+0x26
FSharp_Compiler_Service!FSharp.Compiler.TypeRelations+options@38.System.Collections.Generic.IEqualityComparer<FSharp.Compiler.TypeRelations.TTypeCacheKey>.Equals(TTypeCacheKey, TTypeCacheKey)+0x31
System.Collections.Concurrent.ConcurrentDictionary`2[[FSharp.Compiler.TypeRelations+TTypeCacheKey, FSharp.Compiler.Service],[System.__Canon, mscorlib]].TryAddInternal(TTypeCacheKey, System.__Canon, Boolean, Boolean, System.__Canon ByRef)+0x1c0
System.Collections.Concurrent.ConcurrentDictionary`2[[FSharp.Compiler.TypeRelations+TTypeCacheKey, FSharp.Compiler.Service],[System.__Canon, mscorlib]].GetOrAdd(TTypeCacheKey, System.Func`2<TTypeCacheKey,System.__Canon>)+0xbf

Which makes me think the issue is related to type subsumption cache keys.

I suspect the "Array dimensions exceeded supported range" happens here:

fsharp/src/Compiler/Utilities/TypeHashing.fs

Lines 426 to 469 in 6a50577

	let rec private accumulateTType (ty: TType) =
	seq {
	match ty with
	| TType_ucase(u, tinst) ->
	TypeToken.Stamp u.TyconRef.Stamp
	TypeToken.UCase u.CaseName
	for arg in tinst do
	yield! accumulateTType arg
	| TType_app(tcref, tinst, n) ->
	TypeToken.Stamp tcref.Stamp
	toNullnessToken n
	for arg in tinst do
	yield! accumulateTType arg
	| TType_anon(info, tys) ->
	TypeToken.Stamp info.Stamp
	for arg in tys do
	yield! accumulateTType arg
	| TType_tuple(tupInfo, tys) ->
	TypeToken.TupInfo(evalTupInfoIsStruct tupInfo)
	for arg in tys do
	yield! accumulateTType arg
	| TType_forall(tps, tau) ->
	for tp in tps do
	TypeToken.Stamp tp.Stamp
	yield! accumulateTType tau
	| TType_fun(d, r, n) ->
	yield! accumulateTType d
	yield! accumulateTType r
	toNullnessToken n
	| TType_var(r, n) ->
	TypeToken.Stamp r.Stamp
	toNullnessToken n
	| TType_measure m -> yield! accumulateMeasure m
	}
	/// Get the full structure of a type as a sequence of tokens, suitable for equality
	let getTypeStructure =
	Extras.WeakMap.getOrCreate (fun ty -> accumulateTType ty |> ImmutableArray.ofSeq |> TypeStructure)

because of some circularity that makes this seq infinite (?)

But is this code released to 1111.16? Where can I check this?

[T-Gro]

The "About Visual Studio" dialog will show something like this:

Visual F# Tools 18.0.0-rc2.25455.2+1614065b2e732a13982b3cd7b629ca83593d1c67
Microsoft Visual F# Tools

The part after the plus symbol points to a commit.
E.g. the one from above points to https://github.com/search?q=repo%3Adotnet%2Ffsharp+1614065b2e732a13982b3cd7b629ca83593d1c67&type=commits

Since this is now RC2, code added to "main" and not back ported to "release/dev18.0" (and going trough additional internal justification process...) is not making it to the first official release of VS18 anymore.

[T-Gro]

That being said, an internal error for the caching mechanism would meet the bar here, even though the code might have drifted in the meantime.

[majocha]

It is possible to do a simple fail safe like this that should be harmless.

    // If the sequence got too long, just drop it.
    let private getTokens tokens =
        let result = tokens |> Seq.truncate 256 |> Array.ofSeq
        if result.Length = 256 then Array.singleton (TypeToken.NeverEqual NeverEqual.Singleton) else result

    /// Get the full structure of a type as a sequence of tokens, suitable for equality
    let getTypeStructure =
        Extras.WeakMap.getOrCreate (fun ty -> accumulateTType ty |> getTokens |> TypeStructure)

The thing is, I'm very not sure what the actual problem is without a repro.
I'm also unsure this is the actual problem, it doesn't seem possible for this to go into infinite loop.

[T-Gro]

This was fixed with #19010