template_cyclic_pointer_analysis.md

Template Cyclic Type Error Analysis: Pointer Shallow Semantic Analysis Proposal

Executive Summary

This report explores the validity of the insight that pointer types (classes, slices, pointers to structs) should not trigger cyclic type errors when contained in templated types, because pointers have a known fixed size regardless of the pointee type. The current semantic analysis performs "deep" analysis of field types, which causes false-positive cyclic errors for valid recursive data structures.

The Problem

Current Behavior

When a template type A contains a field of type B, which in turn contains a field of type A, DMD currently reports a circular reference error. This occurs even when the field in B is a pointer to A.

Example of the Issue

// fail_compilation/ice4094.d - Currently fails
struct Zug(int Z)
{
    const bahn = Bug4094!(0).hof.bahn;  // Requires full semantic of Bug4094
}

struct Bug4094(int Q)
{
    Zug!(0) hof;  // Direct containment - creates cycle
}

Error:

fail_compilation/ice4094.d(11): Error: circular reference to variable `ice4094.Zug!0.Zug.bahn`

Why This Should Work

If Bug4094 contained Zug!(0)* (pointer) instead of Zug!(0) (direct instance), the size is known (pointer size) without needing to analyze Zug's fields:

struct Bug4094(int Q)
{
    Zug!(0)* hof;  // Pointer - size is known (target.ptrsize)
}

How Semantic Analysis Currently Works

Field Determination Process

The key function is determineFields() in dsymbolsem.d:

bool determineFields(AggregateDeclaration ad)
{
    // For each field, call dsymbolSemantic to resolve its type
    if (v.semanticRun < PASS.semanticdone)
        v.dsymbolSemantic(null);

    // Check for direct struct containment cycle
    if (auto tvs = tv.isTypeStruct())
    {
        if (ad == tvs.sym)  // Direct containment check
        {
            // Error: cannot have field with same struct type
        }
    }
}

Size Calculation

In typesem.d, the size() function shows the key difference:

case Tpointer:
case Treference:
case Tclass:
case Taarray:       return target.ptrsize;  // Known immediately!

case Tstruct:
{
    import dmd.dsymbolsem: size;
    return t.isTypeStruct().sym.size(loc);  // Requires full field analysis
}

Key Insight: Pointers, references, classes, and associative arrays all have a size of target.ptrsize - this is known immediately without analyzing the pointed-to type.

The Proposal: Shallow Analysis for Pointer Types

Core Idea

When determining fields for a templated aggregate, skip deep semantic analysis for pointer-like field types. Instead:

1. Recognize that T*, T[], class T, and T[key] all have known sizes
2. Only perform shallow semantic analysis (resolve to the pointer type, not the pointee)
3. Defer full pointee analysis until actually needed (e.g., for code generation)

Mermaid Diagram: Current vs Proposed Flow

flowchart TD
    subgraph Current["Current: Deep Analysis"]
        C1[Template A instantiation] --> C2[Analyze field B]
        C2 --> C3[B needs full semantic]
        C3 --> C4[B contains A*]
        C4 --> C5[A* size known... but]
        C5 --> C6[Still analyze A fields]
        C6 --> C7[A contains B reference]
        C7 --> C8[CYCLE DETECTED!]
    end

    subgraph Proposed["Proposed: Shallow Analysis"]
        P1[Template A instantiation] --> P2[Analyze field B]
        P2 --> P3[B contains A*]
        P3 --> P4[A* is pointer type]
        P4 --> P5[Size known: ptrsize]
        P5 --> P6[Skip A field analysis]
        P6 --> P7[Success - no cycle]
    end

Loading

Analysis of Potential Problems

1. Template Constraint Checking

Concern: Template constraints (if conditions) may need full type information.

Analysis: Template constraints are evaluated at a later stage (semantic2/3). The shallow analysis for field determination happens in semantic1. The pointer type itself is sufficient for layout purposes.

2. hasPointers() Analysis

Concern: The GC needs to know if a struct contains pointers.

Analysis: In typesem.d, hasPointers() already handles this:

bool visitPointer(TypePointer t)
{
    return true;  // Pointers always have pointers!
}

For TypeStruct, it calls determineTypeProperties() which iterates fields. If we skip deep analysis for pointer fields, we still know they contain pointers.

3. Initializer Evaluation

Concern: Static initializers may need field information.

Analysis: Initializers are evaluated in semantic2, after field layout is complete. The shallow analysis would only affect semantic1 (field layout), not initializer evaluation.

4. Recursive Template Instantiation

Concern: Could this cause infinite template instantiation?

Analysis: No - template instantiation tracking is separate from field analysis. The TemplateInstance cache prevents duplicate instantiations.

5. Opaque Structs

Concern: Forward declarations and opaque structs.

Analysis: Opaque structs (struct S;) already defer field analysis. The proposed change is consistent with this - we just extend it to pointer fields.

Validity Assessment

Can We Skip Semantic Analysis of Pointer Types?

YES, with caveats:

1. For size calculation: Absolutely yes. Pointers have fixed size.

2. For field layout: Yes. A pointer field's alignment and size are known from the pointer type alone.

3. For type safety: Deferred. The type system only needs to know it's a pointer to T, not the internals of T.

Will This Remove Cyclic Errors Without Causing Other Problems?

MOSTLY YES:

Aspect	Impact	Mitigation
Size calculation	✓ No issue	Pointers have fixed size
Field layout	✓ No issue	Pointer size/align known
hasPointers()	✓ No issue	Pointers always true
Type checking	✓ Deferred	Done at use-site
CTFE	⚠ Needs care	Evaluate when needed
Template constraints	✓ No issue	Evaluated separately

Implementation Approach

Option 1: Modify determineFields()

In dsymbolsem.d, modify the field determination logic:

if (v.semanticRun < PASS.semanticdone)
{
    // For pointer types, only do shallow semantic
    if (isPointerLike(v.type))
    {
        v.type = v.type.shallowSemantic();  // Resolve to pointer, not pointee
    }
    else
    {
        v.dsymbolSemantic(null);  // Full semantic
    }
}

Option 2: Modify VarDeclaration.semantic()

Add a flag to request shallow semantic analysis:

void dsymbolSemantic(VarDeclaration v, Scope* sc, bool shallow = false)
{
    if (shallow && isPointerLike(v.type))
    {
        // Only resolve to pointer type
        return;
    }
    // ... full semantic
}

Option 3: Modify Type Semantic

In typesem.d, ensure pointer types short-circuit:

Type typeSemantic(Type t, Loc loc, Scope* sc)
{
    if (t.ty == Tpointer)
    {
        // For pointer types, only semantic the pointer itself
        // The pointee semantic is deferred
        return t;
    }
    // ...
}

Recommendations

Short Term

1. Implement Option 1 as it's the least invasive
2. Add test cases for valid recursive template structures with pointers
3. Verify existing test suite passes

Medium Term

1. Formalize shallow semantic as a concept in DMD
2. Document when deep vs shallow analysis is required
3. Consider extending to non-template types (consistent behavior)

Long Term

1. Lazy type analysis - Only analyze types when actually needed
2. Separate layout semantic from full semantic

Conclusion

The insight is valid. Pointer types (classes, slices, pointers, associative arrays) have known sizes regardless of what they point to. The current "deep" semantic analysis approach for templated types is overly conservative and produces false-positive cyclic errors.

Skipping deep semantic analysis for pointer fields in templated aggregates will:

• ✓ Remove invalid cyclic errors for valid recursive structures
• ✓ Not affect correctness (pointers have known sizes)
• ✓ Be consistent with how opaque structs are handled
• ⚠ Require careful testing around CTFE and initializers

The proposed change is architecturally sound and would bring D's type system in line with other languages that handle recursive types through indirection (pointers/references).

---

Report generated: 2026-03-05 Author: Richard (Rikki) Andrew Cattermole