Runtime error during GC

[vladimir-tikhonov]

First of all, I'm sorry for such complex code example (even after a ~10x reduction from the original class) - it's extremely tricky to catch. But I believe that it's not about the algorithm itself, but about a specific memory layout. Originally I caught it after a few seconds of running my app (when new allocation triggered garbage collection), but it can be reproduced reliably by calling gc.collect() manually - like in Test's constructor.

Link to webassembly studio: https://webassembly.studio/?f=wl2iowedpud

Code

export class Test {
    public constructor() {
        const a = new Vertex();
        const b = new Vertex();
        const c = new Vertex();
        const d = new Vertex();

        const faces: Face[] = [];
        faces.push( this.createTriangle( a, c, b ) );
        faces.push( this.createTriangle( d, a, b ) );
        faces.push( this.createTriangle( d, b, c ) );
        faces.push( this.createTriangle( d, c, a ) );

        for ( let i = 0; i < 3; i++ ) {
            const k = ( i + 1 ) % 3;
            faces[ i + 1 ].getEdge( 0 ).setTwin( faces[ k + 1 ].getEdge( 1 ) );
            faces[ i + 1 ].getEdge( 2 ).setTwin( faces[ 0 ].getEdge( ( 3 - i ) % 3 ) );
        }

        const nextFace = faces[ 3 ];
        const nextVertex = new Vertex();
        const newFaces = this.buildFaces( nextVertex, [ nextFace.edge!, nextFace.edge!.next! ] );

        gc.collect();
        this.merge( newFaces[ 0 ], newFaces[ 0 ].edge! );
        gc.collect();
    }

    private merge( face: Face, edge: Edge ): void {
        const oppositeEdge = edge.twin!;
        const previousOppositeEdge = oppositeEdge.previous!;
        const nextOppositeEdge = oppositeEdge.next!;

        for ( let currentEdge = nextOppositeEdge; currentEdge !== previousOppositeEdge.next; currentEdge = currentEdge.next! ) {
            currentEdge.face = face;
        }
    }

    private buildFaces( eyeVertex: Vertex, horizon: Edge[] ): Face[] {
        const newFaces: Face[] = [];
        let hedgeSidePrevious: Edge|null = null;
        let hedgeSideBegin: Edge|null = null;

        for ( let i = 0; i < horizon.length; i++ ) {
            const edge = horizon[ i ];
            const newFace = this.createTriangle(
                eyeVertex,
                edge.getHead(),
                edge.getTail()
            );
            newFaces.push( newFace );
            newFace.getEdge( 2 ).setTwin( edge.twin! );

            const hedgeSide = newFace.edge!;
            if ( hedgeSidePrevious !== null ) {
                hedgeSide.next!.setTwin( hedgeSidePrevious );
            } else {
                hedgeSideBegin = hedgeSide;
            }

            hedgeSidePrevious = hedgeSide;
        }

        hedgeSideBegin!.next!.setTwin( hedgeSidePrevious! );

        return newFaces;
    }

    private createTriangle( a: Vertex, b: Vertex, c: Vertex ): Face {
        const face = new Face();
        const edgeAb = new Edge();
        edgeAb.tail = a;
        edgeAb.face = face;
        const edgeBc = new Edge();
        edgeBc.tail = b;
        edgeBc.face = face;
        const edgeCa = new Edge();
        edgeCa.tail = c;
        edgeCa.face = face;

        edgeAb.previous = edgeCa;
        edgeAb.next = edgeBc;
        edgeBc.previous = edgeAb;
        edgeBc.next = edgeCa;
        edgeCa.previous = edgeBc;
        edgeCa.next = edgeAb;

        face.edge = edgeAb;

        return face;
    }
}

export class Vertex {
}

export class Edge {
    public next: Edge|null = null;

    public previous: Edge|null = null;

    public twin: Edge|null = null;

    public tail: Vertex|null = null;

    public face: Face|null = null;

    public getHead(): Vertex {
        return this.twin!.tail!;
    }

    public getTail(): Vertex {
        return this.tail!;
    }

    public setTwin( twin: Edge ): void {
        this.twin = twin;
        twin.twin = this;
    }
}

export class Face {
    public edge: Edge|null = null;

    public getEdge( idx: i32 ): Edge {
        let result = this.edge!;
        while ( idx > 0 ) {
            result = result.next!;
            idx--;
        }

        return result;
    }
}

new Test();

Stack trace

abort
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	
    ~lib/rt/pure/markGray
    ~lib/rt/pure/__visit	
    ~lib/rt/__visit_members	

[dcodeIO]

On a first glimpse it appears that there's something wrong when compiling

        for ( let currentEdge = nextOppositeEdge; currentEdge !== previousOppositeEdge.next; currentEdge = currentEdge.next! ) {
            currentEdge.face = face;
        }

Changing that loop to

      var currentEdge = nextOppositeEdge;
      while (currentEdge !== previousOppositeEdge.next) {
        currentEdge.face = face;
        currentEdge = currentEdge.next!;
      }

gets rid of the error.

There have been quite a few problems with how we compile for loops in the past already, which originates from the complexity introduced by managing various shortcuts while still keeping track of ARC. Makes me wonder whether it'd be more maintainable if all those shortcuts were removed and kept to Binaryen to optimize later.

[vladimir-tikhonov]

@dcodeIO thanks for the workaround, it worked just fine in the original code!

[dcodeIO]

Gave this a shot in the PR linked above. Can you give that a try with your full code base?

[vladimir-tikhonov]

@dcodeIO sure 👍

1. By inspecting a .wat file I can see that the only "real" change is in the loop you pointed out, where _release was moved outside the body of the loop.
2. All other loops (which are fairly mundane compared with the above) underwent the same series of transformations, with some renaming / wrapping in additional block - nothing really fishy there.
3. I can now run a program without any issues up until it hits A specific pattern of pushes to array causes a runtime error in ~lib/rt/tlsf/insertBlock #1042 with or without workaround. Forced GC runs just fine as well.

Overall this seems to be working fine without any regressions. Thanks!

[vladimir-tikhonov]

Re-tested on the latest nightly:

1. A lot changes in loop code but all seems benign.
2. A lot of extra "retain+release" pairs were removed, especially when dealing with arrays in constructors. I didn't carefully inspect them all, but the ones I've inspected look fine.
3. Found a new issue False positive "Object is possibly 'null'" error #1056 (annoying but can be easily workarounded) and re-checked A specific pattern of pushes to array causes a runtime error in ~lib/rt/tlsf/insertBlock #1042 which is still failing on the same place.

Thanks for your help, @dcodeIO!