import {now} from '../util/time_control.ts';
import {mat4} from 'gl-matrix';
import {TileManager} from '../tile/tile_manager.ts';
import {EXTENT} from '../data/extent.ts';
import {SegmentVector} from '../data/segment.ts';
import {RasterBoundsArray, PosArray, TriangleIndexArray, LineStripIndexArray} from '../data/array_types.g.ts';
import rasterBoundsAttributes from '../data/raster_bounds_attributes.ts';
import posAttributes from '../data/pos_attributes.ts';
import {type ProgramConfiguration} from '../data/program_configuration.ts';
import {CrossTileSymbolIndex} from '../symbol/cross_tile_symbol_index.ts';
import {shaders} from '../shaders/shaders.ts';
import {Program} from '../webgl/program.ts';
import {programUniforms} from '../webgl/program/program_uniforms.ts';
import {Context} from '../webgl/context.ts';
import {DepthMode} from '../webgl/depth_mode.ts';
import {StencilMode} from '../webgl/stencil_mode.ts';
import {ColorMode} from '../webgl/color_mode.ts';
import {CullFaceMode} from '../webgl/cull_face_mode.ts';
import {Texture} from '../webgl/texture.ts';
import {Color} from '@maplibre/maplibre-gl-style-spec';
import {selectDebugSource, webglDrawFunctions, type DrawFunctions} from '../webgl/draw/index.ts';
import {type OverscaledTileID} from '../tile/tile_id.ts';
import {Mesh} from './mesh.ts';
import {MercatorShaderDefine, MercatorShaderVariantKey} from '../geo/projection/mercator_projection.ts';

import type {IReadonlyTransform} from '../geo/transform_interface.ts';
import type {Style} from '../style/style.ts';
import type {StyleLayer} from '../style/style_layer.ts';
import type {CrossFaded} from '../style/properties.ts';
import type {LineAtlas} from './line_atlas.ts';
import type {ImageManager} from './image_manager.ts';
import type {PatternAtlas} from './pattern_atlas.ts';
import type {GlyphManager} from './glyph_manager.ts';
import type {VertexBuffer} from '../webgl/vertex_buffer.ts';
import type {IndexBuffer} from '../webgl/index_buffer.ts';
import type {DepthRangeType, DepthMaskType, DepthFuncType} from '../webgl/types.ts';
import type {ResolvedImage} from '@maplibre/maplibre-gl-style-spec';
import type {IRenderToTexture} from './render_to_texture_interface.ts';
import type {TerrainData} from './terrain.ts';
import type {ProjectionData} from '../geo/projection/projection_data.ts';
import type {Framebuffer} from '../webgl/framebuffer.ts';
import {coveringTiles} from '../geo/projection/covering_tiles.ts';
import {isSymbolStyleLayer} from '../style/style_layer/symbol_style_layer.ts';
import {isCircleStyleLayer} from '../style/style_layer/circle_style_layer.ts';
import {isHeatmapStyleLayer} from '../style/style_layer/heatmap_style_layer.ts';
import {isLineStyleLayer} from '../style/style_layer/line_style_layer.ts';
import {isFillStyleLayer} from '../style/style_layer/fill_style_layer.ts';
import {isFillExtrusionStyleLayer} from '../style/style_layer/fill_extrusion_style_layer.ts';
import {isHillshadeStyleLayer} from '../style/style_layer/hillshade_style_layer.ts';
import {isColorReliefStyleLayer} from '../style/style_layer/color_relief_style_layer.ts';
import {isRasterStyleLayer} from '../style/style_layer/raster_style_layer.ts';
import {isBackgroundStyleLayer} from '../style/style_layer/background_style_layer.ts';
import {isCustomStyleLayer} from '../style/style_layer/custom_style_layer.ts';

export type RenderPass = 'offscreen' | 'opaque' | 'translucent';

type PainterOptions = {
    showOverdrawInspector: boolean;
    showTileBoundaries: boolean;
    showPadding: boolean;
    rotating: boolean;
    zooming: boolean;
    moving: boolean;
    fadeDuration: number;
    anisotropicFilterPitch: number;
};

export type RenderOptions = {
    isRenderingToTexture: boolean;
    isRenderingGlobe: boolean;
};

/**
 * Holds the texture used to render a 2D tile so it can be draped over 3D
 * terrain. All RTTObjects share a single FBO owned by the Painter; the
 * texture is swapped in via `Painter.bindRTT` before each render pass.
 * Owned by a `Tile` while in use, recycled via `Painter.releaseRTT` when
 * the tile no longer needs it.
 */
export type RTTObject = {
    texture: Texture;
    size: number;
};

/**
 * @internal
 * Initialize a new painter object.
 */
export class Painter {
    drawFunctions: DrawFunctions;
    context: Context;
    transform: IReadonlyTransform;
    renderToTexture: IRenderToTexture;
    _tileTextures: {
        [_: number]: Texture[];
    };
    /**
     * A pool of recyclable {@link RTTObject}s (textures only; the FBO is shared).
     */
    _rttObjectRecyclePool: RTTObject[];
    /**
     * Shared FBO used by all RTT render passes. The color attachment is
     * swapped to the target RTTObject's texture via {@link bindRTT}.
     * Created lazily on first use.
     */
    _rttSharedFbo: {
        fbo: Framebuffer;
        depthRenderbuffer: WebGLRenderbuffer;
        size: number;
    } | null;
    /**
     * Shared scratch FBO (color + depth-stencil) used by `{line,fill}-layer-opacity`.
     * The layer is rendered into this FBO, then composited into whatever framebuffer was previously bound
     * The canvas in the flat case, the per-terrain-tile RTT texture in the terrain case.
     * Resized in place to match the target dimensions.
     */
    layerOpacityFbo: Framebuffer | null;
    numSublayers: number;
    depthEpsilon: number;
    emptyProgramConfiguration: ProgramConfiguration;
    width: number;
    height: number;
    pixelRatio: number;
    tileExtentBuffer: VertexBuffer;
    tileExtentSegments: SegmentVector;
    tileExtentMesh: Mesh;

    debugBuffer: VertexBuffer;
    debugSegments: SegmentVector;
    rasterBoundsBuffer: VertexBuffer;
    rasterBoundsSegments: SegmentVector;
    rasterBoundsBufferPosOnly: VertexBuffer;
    rasterBoundsSegmentsPosOnly: SegmentVector;
    viewportBuffer: VertexBuffer;
    viewportSegments: SegmentVector;
    quadTriangleIndexBuffer: IndexBuffer;
    tileBorderIndexBuffer: IndexBuffer;
    _tileClippingMaskIDs: {[_: string]: number};
    stencilClearMode: StencilMode;
    style: Style;
    options: PainterOptions;
    lineAtlas: LineAtlas;
    imageManager: ImageManager;
    patternAtlas: PatternAtlas;
    glyphManager: GlyphManager;
    depthRangeFor3D: DepthRangeType;
    opaquePassCutoff: number;
    renderPass: RenderPass;
    currentLayer: number;
    currentStencilSource: string;
    nextStencilID: number;
    id: string;
    _showOverdrawInspector: boolean;
    cache: {[_: string]: Program<any>};
    crossTileSymbolIndex: CrossTileSymbolIndex;
    symbolFadeChange: number;
    debugOverlayTexture: Texture;
    debugOverlayCanvas: HTMLCanvasElement;
    // this object stores the current camera-matrix and the last render time
    // of the terrain-facilitators. e.g. depth & coords framebuffers
    // every time the camera-matrix changes the terrain-facilitators will be redrawn.
    terrainFacilitator: {depthDirty: boolean; coordsDirty: boolean; matrix: mat4; renderTime: number};

    constructor(gl: WebGL2RenderingContext, transform: IReadonlyTransform) {
        this.drawFunctions = webglDrawFunctions;
        this.context = new Context(gl);
        this.transform = transform;
        this.layerOpacityFbo = null;
        this._tileTextures = {};
        this._rttObjectRecyclePool = [];
        this._rttSharedFbo = null;
        this.terrainFacilitator = {depthDirty: true, coordsDirty: false, matrix: mat4.identity(new Float64Array(16)), renderTime: 0};

        this.setup();

        // Within each layer there are multiple distinct z-planes that can be drawn to.
        // This is implemented using the WebGL depth buffer.
        this.numSublayers = TileManager.maxOverzooming + TileManager.maxUnderzooming + 1;
        this.depthEpsilon = 1 / Math.pow(2, 16);

        this.crossTileSymbolIndex = new CrossTileSymbolIndex();
    }

    /*
     * Update the GL viewport, projection matrix, and transforms to compensate
     * for a new width and height value.
     */
    resize(width: number, height: number, pixelRatio: number): void {
        this.width = Math.floor(width * pixelRatio);
        this.height = Math.floor(height * pixelRatio);
        this.pixelRatio = pixelRatio;
        this.context.viewport.set([0, 0, this.width, this.height]);

        if (this.style) {
            for (const layerId of this.style._order) {
                this.style._layers[layerId].resize();
            }
        }
    }

    setup(): void {
        const context = this.context;

        const tileExtentArray = new PosArray();
        tileExtentArray.emplaceBack(0, 0);
        tileExtentArray.emplaceBack(EXTENT, 0);
        tileExtentArray.emplaceBack(0, EXTENT);
        tileExtentArray.emplaceBack(EXTENT, EXTENT);
        this.tileExtentBuffer = context.createVertexBuffer(tileExtentArray, posAttributes.members);
        this.tileExtentSegments = SegmentVector.simpleSegment(0, 0, 4, 2);

        const debugArray = new PosArray();
        debugArray.emplaceBack(0, 0);
        debugArray.emplaceBack(EXTENT, 0);
        debugArray.emplaceBack(0, EXTENT);
        debugArray.emplaceBack(EXTENT, EXTENT);
        this.debugBuffer = context.createVertexBuffer(debugArray, posAttributes.members);
        this.debugSegments = SegmentVector.simpleSegment(0, 0, 4, 5);

        const rasterBoundsArray = new RasterBoundsArray();
        rasterBoundsArray.emplaceBack(0, 0, 0, 0);
        rasterBoundsArray.emplaceBack(EXTENT, 0, EXTENT, 0);
        rasterBoundsArray.emplaceBack(0, EXTENT, 0, EXTENT);
        rasterBoundsArray.emplaceBack(EXTENT, EXTENT, EXTENT, EXTENT);
        this.rasterBoundsBuffer = context.createVertexBuffer(rasterBoundsArray, rasterBoundsAttributes.members);
        this.rasterBoundsSegments = SegmentVector.simpleSegment(0, 0, 4, 2);

        const rasterBoundsArrayPosOnly = new PosArray();
        rasterBoundsArrayPosOnly.emplaceBack(0, 0);
        rasterBoundsArrayPosOnly.emplaceBack(EXTENT, 0);
        rasterBoundsArrayPosOnly.emplaceBack(0, EXTENT);
        rasterBoundsArrayPosOnly.emplaceBack(EXTENT, EXTENT);
        this.rasterBoundsBufferPosOnly = context.createVertexBuffer(rasterBoundsArrayPosOnly, posAttributes.members);
        this.rasterBoundsSegmentsPosOnly = SegmentVector.simpleSegment(0, 0, 4, 5);

        const viewportArray = new PosArray();
        viewportArray.emplaceBack(0, 0);
        viewportArray.emplaceBack(1, 0);
        viewportArray.emplaceBack(0, 1);
        viewportArray.emplaceBack(1, 1);
        this.viewportBuffer = context.createVertexBuffer(viewportArray, posAttributes.members);
        this.viewportSegments = SegmentVector.simpleSegment(0, 0, 4, 2);

        const tileLineStripIndices = new LineStripIndexArray();
        tileLineStripIndices.emplaceBack(0);
        tileLineStripIndices.emplaceBack(1);
        tileLineStripIndices.emplaceBack(3);
        tileLineStripIndices.emplaceBack(2);
        tileLineStripIndices.emplaceBack(0);
        this.tileBorderIndexBuffer = context.createIndexBuffer(tileLineStripIndices);

        const quadTriangleIndices = new TriangleIndexArray();
        quadTriangleIndices.emplaceBack(1, 0, 2);
        quadTriangleIndices.emplaceBack(1, 2, 3);
        this.quadTriangleIndexBuffer = context.createIndexBuffer(quadTriangleIndices);

        const gl = this.context.gl;
        this.stencilClearMode = new StencilMode({func: gl.ALWAYS, mask: 0}, 0x0, 0xFF, gl.ZERO, gl.ZERO, gl.ZERO);

        this.tileExtentMesh = new Mesh(this.tileExtentBuffer, this.quadTriangleIndexBuffer, this.tileExtentSegments);
    }

    /*
     * Reset the drawing canvas by clearing the stencil buffer so that we can draw
     * new tiles at the same location, while retaining previously drawn pixels.
     */
    clearStencil(): void {
        const context = this.context;
        const gl = context.gl;

        this.nextStencilID = 1;
        this.currentStencilSource = undefined;

        // As a temporary workaround for https://github.com/mapbox/mapbox-gl-js/issues/5490,
        // pending an upstream fix, we draw a fullscreen stencil=0 clipping mask here,
        // effectively clearing the stencil buffer: once an upstream patch lands, remove
        // this function in favor of context.clear({ stencil: 0x0 })

        const matrix = mat4.create();
        mat4.ortho(matrix, 0, this.width, this.height, 0, 0, 1);
        mat4.scale(matrix, matrix, [gl.drawingBufferWidth, gl.drawingBufferHeight, 0]);

        const projectionData: ProjectionData = {
            mainMatrix: matrix,
            tileMercatorCoords: [0, 0, 1, 1],
            clippingPlane: [0, 0, 0, 0],
            projectionTransition: 0.0,
            fallbackMatrix: matrix,
            clipAntimeridian: false,
        };

        // Note: we force a simple mercator projection for the shader, since we want to draw a fullscreen quad.
        this.useProgram('clippingMask', null, true).draw(context, gl.TRIANGLES,
            DepthMode.disabled, this.stencilClearMode, ColorMode.disabled, CullFaceMode.disabled,
            null, null, projectionData,
            '$clipping', this.viewportBuffer,
            this.quadTriangleIndexBuffer, this.viewportSegments);
    }

    renderTileClippingMasks(layer: StyleLayer, tileIDs: OverscaledTileID[], renderToTexture: boolean): void {
        if (this.currentStencilSource === layer.source || !layer.isTileClipped() || !tileIDs?.length) {
            return;
        }

        this.currentStencilSource = layer.source;

        if (this.nextStencilID + tileIDs.length > 256) {
            // we'll run out of fresh IDs so we need to clear and start from scratch
            this.clearStencil();
        }

        const context = this.context;
        context.setColorMode(ColorMode.disabled);
        context.setDepthMode(DepthMode.disabled);

        const stencilRefs = {};

        // Set stencil ref values for all tiles
        for (const tileID of tileIDs) {
            stencilRefs[tileID.key] = this.nextStencilID++;
        }

        // A two-pass approach is needed for subdivided projections. See comment in draw_raster.ts
        // for more details. In non-subdivided projections the border flag does not change the mesh,
        // so one pass produces the same stencil mask.
        if (this.style.projection.useSubdivision) {
            this._renderTileMasks(stencilRefs, tileIDs, renderToTexture, true);
        }

        // Final pass - draw borderless tiles with GL_ALWAYS
        this._renderTileMasks(stencilRefs, tileIDs, renderToTexture, false);

        this._tileClippingMaskIDs = stencilRefs;
    }

    _renderTileMasks(tileStencilRefs: {[_: string]: number}, tileIDs: OverscaledTileID[], renderToTexture: boolean, useBorders: boolean): void {
        const context = this.context;
        const gl = context.gl;
        const projection = this.style.projection;
        const transform = this.transform;

        const program = this.useProgram('clippingMask');

        // tiles are usually supplied in ascending order of z, then y, then x
        for (const tileID of tileIDs) {
            const stencilRef = tileStencilRefs[tileID.key];
            const terrainData = this.getTerrainDataForTile(tileID, renderToTexture);

            const mesh = projection.getMeshFromTileID(this.context, tileID.canonical, useBorders, true, 'stencil');

            const projectionData = transform.getProjectionData({overscaledTileID: tileID, applyGlobeMatrix: !renderToTexture, applyTerrainMatrix: true});

            program.draw(context, gl.TRIANGLES, DepthMode.disabled,
                // Tests will always pass, and ref value will be written to stencil buffer.
                new StencilMode({func: gl.ALWAYS, mask: 0}, stencilRef, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE),
                ColorMode.disabled, renderToTexture ? CullFaceMode.disabled : CullFaceMode.backCCW, null,
                terrainData, projectionData, '$clipping', mesh.vertexBuffer,
                mesh.indexBuffer, mesh.segments);
        }
    }

    getTerrainDataForTile(tileID: OverscaledTileID, isRenderingToTexture: boolean): TerrainData | null {
        if (isRenderingToTexture && this.style.projection?.name === 'mercator') return null;
        return this.style.map.terrain?.getTerrainData(tileID) || null;
    }

    /**
     * Fills the depth buffer with the geometry of all supplied tiles.
     * Does not change the color buffer or the stencil buffer.
     */
    _renderTilesDepthBuffer(): void {
        const context = this.context;
        const gl = context.gl;
        const projection = this.style.projection;
        const transform = this.transform;

        const program = this.useProgram('depth');
        const depthMode = this.getDepthModeFor3D();
        const tileIDs = coveringTiles(transform, {tileSize: transform.tileSize});

        // tiles are usually supplied in ascending order of z, then y, then x
        for (const tileID of tileIDs) {
            const terrainData = this.style.map.terrain?.getTerrainData(tileID);
            const mesh = projection.getMeshFromTileID(this.context, tileID.canonical, true, true, 'raster');

            const projectionData = transform.getProjectionData({overscaledTileID: tileID, applyGlobeMatrix: true, applyTerrainMatrix: true});

            program.draw(context, gl.TRIANGLES, depthMode, StencilMode.disabled,
                ColorMode.disabled, CullFaceMode.backCCW, null,
                terrainData, projectionData, '$clipping', mesh.vertexBuffer,
                mesh.indexBuffer, mesh.segments);
        }
    }

    stencilModeFor3D(): StencilMode {
        this.currentStencilSource = undefined;

        if (this.nextStencilID + 1 > 256) {
            this.clearStencil();
        }

        const id = this.nextStencilID++;
        const gl = this.context.gl;
        return new StencilMode({func: gl.NOTEQUAL, mask: 0xFF}, id, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE);
    }

    stencilModeForClipping(tileID: OverscaledTileID): StencilMode {
        const gl = this.context.gl;
        return new StencilMode({func: gl.EQUAL, mask: 0xFF}, this._tileClippingMaskIDs[tileID.key], 0x00, gl.KEEP, gl.KEEP, gl.REPLACE);
    }

    /*
     * Sort coordinates by Z as drawing tiles is done in Z-descending order.
     * All children with the same Z write the same stencil value.  Children
     * stencil values are greater than parent's.  This is used only for raster
     * and raster-dem tiles, which are already clipped to tile boundaries, to
     * mask area of tile overlapped by children tiles.
     * Stencil ref values continue range used in _tileClippingMaskIDs.
     *
     * Attention: This function changes this.nextStencilID even if the result of it
     * is not used, which might cause problems when rendering due to invalid stencil
     * values.
     * Returns [StencilMode for tile overscaleZ map, sortedCoords].
     */
    getStencilConfigForOverlapAndUpdateStencilID(tileIDs: OverscaledTileID[]): [{
        [_: number]: Readonly<StencilMode>;
    }, OverscaledTileID[]] {
        const gl = this.context.gl;
        const coords = tileIDs.sort((a, b) => b.overscaledZ - a.overscaledZ);
        const minTileZ = coords[coords.length - 1].overscaledZ;
        const stencilValues = coords[0].overscaledZ - minTileZ + 1;
        if (stencilValues > 1) {
            this.currentStencilSource = undefined;
            if (this.nextStencilID + stencilValues > 256) {
                this.clearStencil();
            }
            const zToStencilMode = {};
            for (let i = 0; i < stencilValues; i++) {
                zToStencilMode[i + minTileZ] = new StencilMode({func: gl.GEQUAL, mask: 0xFF}, i + this.nextStencilID, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE);
            }
            this.nextStencilID += stencilValues;
            return [zToStencilMode, coords];
        }
        return [{[minTileZ]: StencilMode.disabled}, coords];
    }

    stencilConfigForOverlapTwoPass(tileIDs: OverscaledTileID[]): [
        { [_: number]: Readonly<StencilMode> }, // borderless tiles - high priority & high stencil values
        { [_: number]: Readonly<StencilMode> }, // tiles with border - low priority
        OverscaledTileID[]
    ] {
        const gl = this.context.gl;
        const coords = tileIDs.sort((a, b) => b.overscaledZ - a.overscaledZ);
        const minTileZ = coords[coords.length - 1].overscaledZ;
        const stencilValues = coords[0].overscaledZ - minTileZ + 1;

        this.clearStencil();

        if (stencilValues > 1) {
            const zToStencilModeHigh = {};
            const zToStencilModeLow = {};
            for (let i = 0; i < stencilValues; i++) {
                zToStencilModeHigh[i + minTileZ] = new StencilMode({func: gl.GREATER, mask: 0xFF}, stencilValues + 1 + i, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE);
                zToStencilModeLow[i + minTileZ] = new StencilMode({func: gl.GREATER, mask: 0xFF}, 1 + i, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE);
            }
            this.nextStencilID = stencilValues * 2 + 1;
            return [
                zToStencilModeHigh,
                zToStencilModeLow,
                coords
            ];
        } else {
            this.nextStencilID = 3;
            return [
                {[minTileZ]: new StencilMode({func: gl.GREATER, mask: 0xFF}, 2, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE)},
                {[minTileZ]: new StencilMode({func: gl.GREATER, mask: 0xFF}, 1, 0xFF, gl.KEEP, gl.KEEP, gl.REPLACE)},
                coords
            ];
        }
    }

    colorModeForRenderPass(): Readonly<ColorMode> {
        const gl = this.context.gl;
        if (this._showOverdrawInspector) {
            const numOverdrawSteps = 8;
            const a = 1 / numOverdrawSteps;

            return new ColorMode([gl.CONSTANT_COLOR, gl.ONE], new Color(a, a, a, 0), [true, true, true, true]);
        } else if (this.renderPass === 'opaque') {
            return ColorMode.unblended;
        } else {
            return ColorMode.alphaBlended;
        }
    }

    getDepthModeForSublayer(n: number, mask: DepthMaskType, func?: DepthFuncType | null): Readonly<DepthMode> {
        if (!this.opaquePassEnabledForLayer()) return DepthMode.disabled;
        const depth = 1 - ((1 + this.currentLayer) * this.numSublayers + n) * this.depthEpsilon;
        return new DepthMode(func || this.context.gl.LEQUAL, mask, [depth, depth]);
    }

    getDepthModeFor3D(): Readonly<DepthMode> {
        return new DepthMode(this.context.gl.LEQUAL, DepthMode.ReadWrite, this.depthRangeFor3D);
    }

    /*
     * The opaque pass and 3D layers both use the depth buffer.
     * Layers drawn above 3D layers need to be drawn using the
     * painter's algorithm so that they appear above 3D features.
     * This returns true for layers that can be drawn using the
     * opaque pass.
     */
    opaquePassEnabledForLayer(): boolean {
        return this.currentLayer < this.opaquePassCutoff;
    }

    render(style: Style, options: PainterOptions): void {
        this.style = style;
        this.options = options;

        this.lineAtlas = style.lineAtlas;
        this.imageManager = style.imageManager;
        this.patternAtlas = style.patternAtlas;
        this.glyphManager = style.glyphManager;

        this.symbolFadeChange = style.placement.symbolFadeChange(now());

        this.imageManager.beginFrame();

        const layerIds = this.style._order;
        const tileManagers = this.style.tileManagers;

        const coordsAscending: {[_: string]: OverscaledTileID[]} = {};
        const coordsDescending: {[_: string]: OverscaledTileID[]} = {};
        const coordsDescendingSymbol: {[_: string]: OverscaledTileID[]} = {};
        const renderOptions: RenderOptions = {isRenderingToTexture: false, isRenderingGlobe: style.projection?.transitionState > 0};

        for (const id in tileManagers) {
            const tileManager = tileManagers[id];
            if (tileManager.used) {
                tileManager.prepare(this.context);
            }

            coordsAscending[id] = tileManager.getVisibleCoordinates(false);
            coordsDescending[id] = coordsAscending[id].slice().reverse();
            coordsDescendingSymbol[id] = tileManager.getVisibleCoordinates(true).reverse();
        }

        this.opaquePassCutoff = Infinity;
        for (let i = 0; i < layerIds.length; i++) {
            const layerId = layerIds[i];
            if (this.style._layers[layerId].is3D()) {
                this.opaquePassCutoff = i;
                break;
            }
        }

        this.maybeDrawDepth(false);

        if (this.renderToTexture) {
            this.renderToTexture.prepareForRender(this.style, this.transform.zoom);
            // this is disabled, because render-to-texture is rendering all layers from bottom to top.
            this.opaquePassCutoff = 0;
        }

        // Offscreen pass ===============================================
        // We first do all rendering that requires rendering to a separate
        // framebuffer, and then save those for rendering back to the map
        // later: in doing this we avoid doing expensive framebuffer restores.
        this.renderPass = 'offscreen';

        for (const layerId of layerIds) {
            const layer = this.style._layers[layerId];
            if (!layer.hasOffscreenPass() || layer.isHidden(this.transform.zoom)) continue;

            const coords = coordsDescending[layer.source];
            if (layer.type !== 'custom' && !coords.length) continue;

            this.renderLayer(this, tileManagers[layer.source], layer, coords, renderOptions);
        }

        // Rebind the main framebuffer now that all offscreen layers have been rendered:
        this.context.viewport.set([0, 0, this.width, this.height]);
        this.context.bindFramebuffer.set(null);

        // Clear buffers in preparation for drawing to the main framebuffer
        this.context.clear({color: options.showOverdrawInspector ? Color.black : Color.transparent, depth: 1});
        this.clearStencil();

        // draw sky first to not overwrite symbols
        if (this.style.sky) this.drawFunctions.sky(this, this.style.sky);

        this._showOverdrawInspector = options.showOverdrawInspector;
        this.depthRangeFor3D = [0, 1 - ((style._order.length + 2) * this.numSublayers * this.depthEpsilon)];

        // Opaque pass ===============================================
        // Draw opaque layers top-to-bottom first.
        if (!this.renderToTexture) {
            this.renderPass = 'opaque';

            for (this.currentLayer = layerIds.length - 1; this.currentLayer >= 0; this.currentLayer--) {
                const layer = this.style._layers[layerIds[this.currentLayer]];
                const tileManager = tileManagers[layer.source];
                const coords = coordsAscending[layer.source];

                this.renderTileClippingMasks(layer, coords, false);
                this.renderLayer(this, tileManager, layer, coords, renderOptions);
            }
        }

        // Translucent pass ===============================================
        // Draw all other layers bottom-to-top.
        this.renderPass = 'translucent';

        let globeDepthRendered = false;

        for (this.currentLayer = 0; this.currentLayer < layerIds.length; this.currentLayer++) {
            const layer = this.style._layers[layerIds[this.currentLayer]];
            const tileManager = tileManagers[layer.source];

            if (this.renderToTexture?.renderLayer(layer, renderOptions)) continue;

            if (!this.opaquePassEnabledForLayer() && !globeDepthRendered) {
                globeDepthRendered = true;
                // Render the globe sphere into the depth buffer - but only if globe is enabled and terrain is disabled.
                // There should be no need for explicitly writing tile depths when terrain is enabled.
                if (renderOptions.isRenderingGlobe && !this.style.map.terrain) {
                    this._renderTilesDepthBuffer();
                }
            }

            // For symbol layers in the translucent pass, we add extra tiles to the renderable set
            // for cross-tile symbol fading. Symbol layers don't use tile clipping, so no need to render
            // separate clipping masks
            const coords = (layer.type === 'symbol' ? coordsDescendingSymbol : coordsDescending)[layer.source];

            this.renderTileClippingMasks(layer, coordsAscending[layer.source], !!this.renderToTexture);
            this.renderLayer(this, tileManager, layer, coords, renderOptions);
        }

        // Render atmosphere, only for Globe projection
        if (renderOptions.isRenderingGlobe) {
            this.drawFunctions.atmosphere(this, this.style.sky, this.style.light);
        }

        if (this.options.showTileBoundaries) {
            const selectedSource = selectDebugSource(this.style, this.transform.zoom);
            if (selectedSource) {
                this.drawFunctions.debug(this, selectedSource, selectedSource.getVisibleCoordinates());
            }
        }

        if (this.options.showPadding) {
            this.drawFunctions.debugPadding(this);
        }

        // Set defaults for most GL values so that anyone using the state after the render
        // encounters more expected values.
        this.context.setDefault();
    }

    /**
     * Update the depth framebuffer if the camera has moved or tiles have reloaded.
     * Marks coords as depthDirty so they are re-rendered on next demand.
     */
    maybeDrawDepth(requireExact: boolean): void {
        if (!this.style?.map?.terrain) {
            return;
        }
        const prevMatrix = this.terrainFacilitator.matrix;
        const currMatrix = this.transform.modelViewProjectionMatrix;

        // Update depth-framebuffer on camera movement, or tile reloading
        let doUpdate = this.terrainFacilitator.depthDirty;
        doUpdate ||= requireExact ? !mat4.exactEquals(prevMatrix, currMatrix) : !mat4.equals(prevMatrix, currMatrix);
        doUpdate ||= this.style.map.terrain.tileManager.anyTilesAfterTime(this.terrainFacilitator.renderTime);

        if (!doUpdate) {
            return;
        }

        mat4.copy(prevMatrix, currMatrix);
        this.terrainFacilitator.renderTime = now();
        this.terrainFacilitator.depthDirty = false;
        this.terrainFacilitator.coordsDirty = true;
        this.drawFunctions.terrainDepth(this, this.style.map.terrain);
    }

    /**
     * Render the coords framebuffer if it is coordsDirty
     */
    maybeDrawCoords(): void {
        if (!this.style?.map?.terrain || !this.terrainFacilitator.coordsDirty) {
            return;
        }
        this.terrainFacilitator.coordsDirty = false;
        this.drawFunctions.terrainCoords(this, this.style.map.terrain);
    }

    renderLayer(painter: Painter, tileManager: TileManager, layer: StyleLayer, coords: OverscaledTileID[], renderOptions: RenderOptions): void {
        if (layer.isHidden(this.transform.zoom)) return;
        if (layer.type !== 'background' && layer.type !== 'custom' && !(coords || []).length) return;
        this.id = layer.id;

        const draw = this.drawFunctions;
        if (isSymbolStyleLayer(layer)) {
            draw.symbol(painter, tileManager, layer, coords, this.style.placement.variableOffsets, renderOptions);
        } else if (isCircleStyleLayer(layer)) {
            draw.circle(painter, tileManager, layer, coords, renderOptions);
        } else if (isHeatmapStyleLayer(layer)) {
            draw.heatmap(painter, tileManager, layer, coords, renderOptions);
        } else if (isLineStyleLayer(layer)) {
            draw.line(painter, tileManager, layer, coords, renderOptions);
        } else if (isFillStyleLayer(layer)) {
            draw.fill(painter, tileManager, layer, coords, renderOptions);
        } else if (isFillExtrusionStyleLayer(layer)) {
            draw.fillExtrusion(painter, tileManager, layer, coords, renderOptions);
        } else if (isHillshadeStyleLayer(layer)) {
            draw.hillshade(painter, tileManager, layer, coords, renderOptions);
        } else if (isColorReliefStyleLayer(layer)) {
            draw.colorRelief(painter, tileManager, layer, coords, renderOptions);
        } else if (isRasterStyleLayer(layer)) {
            draw.raster(painter, tileManager, layer, coords, renderOptions);
        } else if (isBackgroundStyleLayer(layer)) {
            draw.background(painter, tileManager, layer, coords, renderOptions);
        } else if (isCustomStyleLayer(layer)) {
            draw.custom(painter, tileManager, layer, renderOptions);
        }
    }

    static readonly MAX_TEXTURE_POOL_SIZE_PER_BUCKET = 50;

    saveTileTexture(texture: Texture): void {
        const textures = this._tileTextures[texture.size[0]];
        if (!textures) {
            this._tileTextures[texture.size[0]] = [texture];
        } else if (textures.length < Painter.MAX_TEXTURE_POOL_SIZE_PER_BUCKET) {
            textures.push(texture);
        } else {
            texture.destroy();
        }
    }

    getTileTexture(size: number): Texture {
        const textures = this._tileTextures[size];
        return textures && textures.length > 0 ? textures.pop() : null;
    }

    acquireRTT(size: number): RTTObject {
        const gl = this.context.gl;
        const obj = this._rttObjectRecyclePool.pop();
        if (obj) {
            if (obj.size !== size) {
                gl.bindTexture(gl.TEXTURE_2D, obj.texture.texture);
                gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, size, size, 0, gl.RGBA, gl.UNSIGNED_BYTE, null);
                obj.texture.size = [size, size];
                obj.size = size;
            }
            return obj;
        }
        const texture = new Texture(this.context, {width: size, height: size, data: null}, gl.RGBA);
        texture.bind(gl.LINEAR, gl.CLAMP_TO_EDGE);
        if (this.context.extTextureFilterAnisotropic) {
            gl.texParameterf(gl.TEXTURE_2D, this.context.extTextureFilterAnisotropic.TEXTURE_MAX_ANISOTROPY_EXT, this.context.extTextureFilterAnisotropicMax);
        }
        return {texture, size};
    }

    /**
     * Binds the shared RTT FBO with the given RTTObject's texture attached
     * as color target. Creates / resizes the shared FBO and depth-stencil
     * renderbuffer lazily.
     */
    bindRTT(obj: RTTObject): void {
        const gl = this.context.gl;
        const size = obj.size;

        // Lazy-create the shared FBO + depth-stencil renderbuffer
        if (!this._rttSharedFbo) {
            const fbo = this.context.createFramebuffer(size, size, true, true);
            const depthRenderbuffer = this.context.createRenderbuffer(gl.DEPTH_STENCIL, size, size);
            fbo.depthAttachment.set(depthRenderbuffer);
            this._rttSharedFbo = {fbo, depthRenderbuffer, size};
        }

        // Resize the shared depth-stencil renderbuffer if needed
        if (this._rttSharedFbo.size !== size) {
            this.context.bindRenderbuffer.set(this._rttSharedFbo.depthRenderbuffer);
            gl.renderbufferStorage(gl.RENDERBUFFER, gl.DEPTH_STENCIL, size, size);
            this.context.bindRenderbuffer.set(null);
            this._rttSharedFbo.fbo.width = size;
            this._rttSharedFbo.fbo.height = size;
            this._rttSharedFbo.size = size;
        }

        // Swap in the target texture and bind
        this._rttSharedFbo.fbo.colorAttachment.set(obj.texture.texture);
        this.context.bindFramebuffer.set(this._rttSharedFbo.fbo.framebuffer);
    }

    releaseRTT(obj: RTTObject): void {
        this._rttObjectRecyclePool.push(obj);
    }

    /**
     * Checks whether a pattern image is needed, and if it is, whether it is not loaded.
     *
     * @returns true if a needed image is missing and rendering needs to be skipped.
     */
    isPatternMissing(image?: CrossFaded<ResolvedImage> | null): boolean {
        if (!image) return false;
        if (!image.from || !image.to) return true;
        const imagePosA = this.patternAtlas.getPattern(image.from.toString());
        const imagePosB = this.patternAtlas.getPattern(image.to.toString());
        return !imagePosA || !imagePosB;
    }

    /**
     * Finds the required shader and its variant (base/terrain/globe, etc.) and binds it, compiling a new shader if required.
     * @param name - Name of the desired shader.
     * @param programConfiguration - Configuration of shader's inputs.
     * @param forceSimpleProjection - Whether to force the use of a shader variant with simple mercator projection vertex shader.
     * @param defines - Additional macros to be injected at the beginning of the shader. Expected format is `['#define XYZ']`, etc.
     * False by default. Use true when drawing with a simple projection matrix is desired, eg. when drawing a fullscreen quad.
     * @returns
     */
    useProgram(name: string, programConfiguration?: ProgramConfiguration | null, forceSimpleProjection: boolean = false, defines: string[] = []): Program<any> {
        this.cache ||= {};
        const useTerrain = !!this.style.map.terrain;

        const projection = this.style.projection;

        const projectionPrelude = forceSimpleProjection ? shaders.projectionMercator : projection.shaderPreludeCode;
        const projectionDefine = forceSimpleProjection ? MercatorShaderDefine : projection.shaderDefine;
        const projectionKey = `/${forceSimpleProjection ? MercatorShaderVariantKey : projection.shaderVariantName}`;

        const configurationKey = (programConfiguration ? programConfiguration.cacheKey : '');
        const overdrawKey = (this._showOverdrawInspector ? '/overdraw' : '');
        const terrainKey = (useTerrain ? '/terrain' : '');
        const definesKey = (defines ? `/${defines.join('/')}` : '');

        const key = name + configurationKey + projectionKey + overdrawKey + terrainKey + definesKey;

        this.cache[key] ||= new Program(
            this.context,
            shaders[name],
            programConfiguration,
            programUniforms[name],
            this._showOverdrawInspector,
            useTerrain,
            projectionPrelude,
            projectionDefine,
            defines
        );
        return this.cache[key];
    }

    /*
     * Reset some GL state to default values to avoid hard-to-debug bugs
     * in custom layers.
     */
    setCustomLayerDefaults(): void {
        this.context.setCustomLayerDefaults();
    }

    /*
     * Set GL state shared by all layers.
     */
    setBaseState(): void {
        const gl = this.context.gl;
        this.context.cullFace.set(false);
        this.context.viewport.set([0, 0, this.width, this.height]);
        this.context.blendEquation.set(gl.FUNC_ADD);
    }

    initDebugOverlayCanvas(): void {
        if (this.debugOverlayCanvas == null) {
            this.debugOverlayCanvas = document.createElement('canvas');
            this.debugOverlayCanvas.width = 512;
            this.debugOverlayCanvas.height = 512;
            const gl = this.context.gl;
            this.debugOverlayTexture = new Texture(this.context, this.debugOverlayCanvas, gl.RGBA);
        }
    }

    destroy(): void {
        if (this._tileTextures) {
            for (const size in this._tileTextures) {
                const textures = this._tileTextures[size];
                if (textures) {
                    for (const texture of textures) {
                        texture.destroy();
                    }
                }
            }
            this._tileTextures = {};
        }

        for (const obj of this._rttObjectRecyclePool) {
            obj.texture.destroy();
        }
        this._rttObjectRecyclePool = [];

        if (this._rttSharedFbo) {
            // Detach so Framebuffer.destroy() doesn't delete the texture/renderbuffer
            // that we already manage separately.
            this._rttSharedFbo.fbo.colorAttachment.set(null);
            this._rttSharedFbo.fbo.depthAttachment.set(null);
            const gl = this.context.gl;
            gl.deleteRenderbuffer(this._rttSharedFbo.depthRenderbuffer);
            gl.deleteFramebuffer(this._rttSharedFbo.fbo.framebuffer);
            this._rttSharedFbo = null;
        }

        this.layerOpacityFbo?.destroy();
        this.layerOpacityFbo = null;

        if (this.tileExtentBuffer) this.tileExtentBuffer.destroy();
        if (this.debugBuffer) this.debugBuffer.destroy();
        if (this.rasterBoundsBuffer) this.rasterBoundsBuffer.destroy();
        if (this.rasterBoundsBufferPosOnly) this.rasterBoundsBufferPosOnly.destroy();
        if (this.viewportBuffer) this.viewportBuffer.destroy();
        if (this.tileBorderIndexBuffer) this.tileBorderIndexBuffer.destroy();
        if (this.quadTriangleIndexBuffer) this.quadTriangleIndexBuffer.destroy();
        if (this.tileExtentMesh) this.tileExtentMesh.vertexBuffer?.destroy();
        if (this.tileExtentMesh) this.tileExtentMesh.indexBuffer?.destroy();

        if (this.debugOverlayTexture) {
            this.debugOverlayTexture.destroy();
        }

        if (this.cache) {
            for (const key in this.cache) {
                const program = this.cache[key];
                if (program?.program) {
                    this.context.gl.deleteProgram(program.program);
                }
            }
            this.cache = {};
        }

        if (this.context) {
            this.context.setDefault();
        }
    }

    /*
     * Return true if drawing buffer size is != from requested size.
     * That means that we've reached GL limits somehow.
     * Note: drawing buffer size changes only when canvas size changes
     */
    overLimit(): boolean {
        const {drawingBufferWidth, drawingBufferHeight} = this.context.gl;
        return this.width !== drawingBufferWidth || this.height !== drawingBufferHeight;
    }
}
