void RenderView::mapLocalToContainer(const RenderLayerModelObject* paintInvalidationContainer, TransformState& transformState, MapCoordinatesFlags mode, bool* wasFixed, const PaintInvalidationState* paintInvalidationState) const
{
    ASSERT_UNUSED(wasFixed, !wasFixed || *wasFixed == static_cast<bool>(mode & IsFixed));

    if (!paintInvalidationContainer && mode & UseTransforms && shouldUseTransformFromContainer(0)) {
        TransformationMatrix t;
        getTransformFromContainer(0, LayoutSize(), t);
        transformState.applyTransform(t);
    }

    if ((mode & IsFixed) && m_frameView) {
        transformState.move(m_frameView->scrollOffsetForFixedPosition());
        // IsFixed flag is only applicable within this RenderView.
        mode &= ~IsFixed;
    }

    if (paintInvalidationContainer == this)
        return;

    if (mode & TraverseDocumentBoundaries) {
        if (RenderObject* parentDocRenderer = frame()->ownerRenderer()) {
            transformState.move(-frame()->view()->scrollOffset());
            if (parentDocRenderer->isBox())
                transformState.move(toLayoutSize(toRenderBox(parentDocRenderer)->contentBoxRect().location()));
            parentDocRenderer->mapLocalToContainer(paintInvalidationContainer, transformState, mode, wasFixed, paintInvalidationState);
            return;
        }
    }
}

void PointArray::estimateCost(const TransformState& transState,
                              bool incrementalDraw, const double* qualities,
                              DrawCount* drawCounts, int numEstimates) const
{
    TransformState relativeTrans = transState.translate(offset());
    V3f relCamera = relativeTrans.cameraPos();
    ClipBox clipBox(relativeTrans);

    std::vector<const OctreeNode*> nodeStack;
    nodeStack.push_back(m_rootNode.get());
    while (!nodeStack.empty())
    {
        const OctreeNode* node = nodeStack.back();
        nodeStack.pop_back();
        if (clipBox.canCull(node->bbox))
            continue;
        if (!node->isLeaf())
        {
            for (int i = 0; i < 8; ++i)
            {
                OctreeNode* n = node->children[i];
                if (n)
                    nodeStack.push_back(n);
            }
            continue;
        }
        for (int i = 0; i < numEstimates; ++i)
        {
            drawCounts[i] += node->drawCount(relCamera, qualities[i],
                                             incrementalDraw);
        }
    }
}

mat4 RenderTile::translatedMatrix(const std::array<float, 2>& translation,
                                  TranslateAnchorType anchor,
                                  const TransformState& state) const {
    if (translation[0] == 0 && translation[1] == 0) {
        return matrix;
    }

    mat4 vtxMatrix;

    if (anchor == TranslateAnchorType::Viewport) {
        const double sin_a = std::sin(-state.getAngle());
        const double cos_a = std::cos(-state.getAngle());
        matrix::translate(vtxMatrix, matrix,
                id.pixelsToTileUnits(translation[0] * cos_a - translation[1] * sin_a, state.getZoom()),
                id.pixelsToTileUnits(translation[0] * sin_a + translation[1] * cos_a, state.getZoom()),
                0);
    } else {
        matrix::translate(vtxMatrix, matrix,
                id.pixelsToTileUnits(translation[0], state.getZoom()),
                id.pixelsToTileUnits(translation[1], state.getZoom()),
                0);
    }

    return vtxMatrix;
}

    void reprojectLineLabels(gfx::VertexVector<gfx::Vertex<SymbolDynamicLayoutAttributes>>& dynamicVertexArray, const std::vector<PlacedSymbol>& placedSymbols,
			const mat4& posMatrix, bool pitchWithMap, bool rotateWithMap, bool keepUpright,
            const RenderTile& tile, const SymbolSizeBinder& sizeBinder, const TransformState& state) {

        const ZoomEvaluatedSize partiallyEvaluatedSize = sizeBinder.evaluateForZoom(state.getZoom());

        const std::array<double, 2> clippingBuffer = {{ 256.0 / state.getSize().width * 2.0 + 1.0, 256.0 / state.getSize().height * 2.0 + 1.0 }};

        const float pixelsToTileUnits = tile.id.pixelsToTileUnits(1, state.getZoom());

        const mat4 labelPlaneMatrix = getLabelPlaneMatrix(posMatrix, pitchWithMap,
                rotateWithMap, state, pixelsToTileUnits);
        
        const mat4 glCoordMatrix = getGlCoordMatrix(posMatrix, pitchWithMap, rotateWithMap, state, pixelsToTileUnits);
        
        dynamicVertexArray.clear();
        
        bool useVertical = false;

        for (auto& placedSymbol : placedSymbols) {
            // Don't do calculations for vertical glyphs unless the previous symbol was horizontal
            // and we determined that vertical glyphs were necessary.
            // Also don't do calculations for symbols that are collided and fully faded out
            if (placedSymbol.hidden || (placedSymbol.writingModes == WritingModeType::Vertical && !useVertical)) {
                hideGlyphs(placedSymbol.glyphOffsets.size(), dynamicVertexArray);
                continue;
            }
            // Awkward... but we're counting on the paired "vertical" symbol coming immediately after its horizontal counterpart
            useVertical = false;
            
			vec4 anchorPos = {{ placedSymbol.anchorPoint.x, placedSymbol.anchorPoint.y, 0, 1 }};
            matrix::transformMat4(anchorPos, anchorPos, posMatrix);

            // Don't bother calculating the correct point for invisible labels.
            if (!isVisible(anchorPos, clippingBuffer)) {
                hideGlyphs(placedSymbol.glyphOffsets.size(), dynamicVertexArray);
                continue;
            }

            const float cameraToAnchorDistance = anchorPos[3];
            const float perspectiveRatio = 0.5 + 0.5 * (cameraToAnchorDistance / state.getCameraToCenterDistance());

            const float fontSize = evaluateSizeForFeature(partiallyEvaluatedSize, placedSymbol);
            const float pitchScaledFontSize = pitchWithMap ?
                fontSize * perspectiveRatio :
                fontSize / perspectiveRatio;
            
            const Point<float> anchorPoint = project(placedSymbol.anchorPoint, labelPlaneMatrix).first;

            PlacementResult placeUnflipped = placeGlyphsAlongLine(placedSymbol, pitchScaledFontSize, false /*unflipped*/, keepUpright, posMatrix, labelPlaneMatrix, glCoordMatrix, dynamicVertexArray, anchorPoint, state.getSize().aspectRatio());
            
            useVertical = placeUnflipped == PlacementResult::UseVertical;

            if (placeUnflipped == PlacementResult::NotEnoughRoom || useVertical ||
                (placeUnflipped == PlacementResult::NeedsFlipping &&
                 placeGlyphsAlongLine(placedSymbol, pitchScaledFontSize, true /*flipped*/, keepUpright, posMatrix, labelPlaneMatrix, glCoordMatrix, dynamicVertexArray, anchorPoint, state.getSize().aspectRatio()) == PlacementResult::NotEnoughRoom)) {
                hideGlyphs(placedSymbol.glyphOffsets.size(), dynamicVertexArray);
            }
        }
    }

void RenderView::mapLocalToContainer(const RenderLayerModelObject* repaintContainer, TransformState& transformState, MapCoordinatesFlags mode, bool* wasFixed) const
{
    ASSERT_UNUSED(wasFixed, !wasFixed || *wasFixed == static_cast<bool>(mode & IsFixed));

    if (!repaintContainer && mode & UseTransforms && shouldUseTransformFromContainer(0)) {
        TransformationMatrix t;
        getTransformFromContainer(0, LayoutSize(), t);
        transformState.applyTransform(t);
    }

    if (mode & IsFixed && m_frameView)
        transformState.move(m_frameView->scrollOffsetForFixedPosition());

    if (repaintContainer == this)
        return;

    if (mode & TraverseDocumentBoundaries) {
        if (RenderObject* parentDocRenderer = frame()->ownerRenderer()) {
            transformState.move(-frame()->view()->scrollOffset());
            if (parentDocRenderer->isBox())
                transformState.move(toLayoutSize(toRenderBox(parentDocRenderer)->contentBoxRect().location()));
            parentDocRenderer->mapLocalToContainer(repaintContainer, transformState, mode, wasFixed);
            return;
        }
    }

    // If a container was specified, and was not 0 or the RenderView,
    // then we should have found it by now.
    ASSERT_ARG(repaintContainer, !repaintContainer);
}

void GeometryTile::queryRenderedFeatures(
    std::unordered_map<std::string, std::vector<Feature>>& result,
    const GeometryCoordinates& queryGeometry,
    const TransformState& transformState,
    const std::vector<const RenderLayer*>& layers,
    const RenderedQueryOptions& options,
    const mat4& projMatrix) {

    if (!getData()) return;

    const float queryPadding = getQueryPadding(layers);

    mat4 posMatrix;
    transformState.matrixFor(posMatrix, id.toUnwrapped());
    matrix::multiply(posMatrix, projMatrix, posMatrix);

    latestFeatureIndex->query(result,
                              queryGeometry,
                              transformState,
                              posMatrix,
                              util::tileSize * id.overscaleFactor(),
                              std::pow(2, transformState.getZoom() - id.overscaledZ),
                              options,
                              id.toUnwrapped(),
                              layers,
                              queryPadding * transformState.maxPitchScaleFactor());
}

void RenderMultiColumnFlowThread::mapAbsoluteToLocalPoint(MapCoordinatesFlags mode, TransformState& transformState) const
{
    // First get the transform state's point into the block flow thread's physical coordinate space.
    parent()->mapAbsoluteToLocalPoint(mode, transformState);
    LayoutPoint transformPoint = roundedLayoutPoint(transformState.mappedPoint());

    // Now walk through each region.
    const RenderMultiColumnSet* candidateColumnSet = nullptr;
    LayoutPoint candidatePoint;
    LayoutSize candidateContainerOffset;

    for (const auto& columnSet : childrenOfType<RenderMultiColumnSet>(*parent())) {
        candidateContainerOffset = columnSet.offsetFromContainer(parent(), LayoutPoint());

        candidatePoint = transformPoint - candidateContainerOffset;
        candidateColumnSet = &columnSet;

        // We really have no clue what to do with overflow. We'll just use the closest region to the point in that case.
        LayoutUnit pointOffset = isHorizontalWritingMode() ? candidatePoint.y() : candidatePoint.x();
        LayoutUnit regionOffset = isHorizontalWritingMode() ? columnSet.topLeftLocation().y() : columnSet.topLeftLocation().x();
        if (pointOffset < regionOffset + columnSet.logicalHeight())
            break;
    }

    // Once we have a good guess as to which region we hit tested through (and yes, this was just a heuristic, but it's
    // the best we could do), then we can map from the region into the flow thread.
    LayoutSize translationOffset = physicalTranslationFromRegionToFlow(candidateColumnSet, candidatePoint) + candidateContainerOffset;
    bool preserve3D = mode & UseTransforms && (parent()->style().preserves3D() || style().preserves3D());
    if (mode & UseTransforms && shouldUseTransformFromContainer(parent())) {
        TransformationMatrix t;
        getTransformFromContainer(parent(), translationOffset, t);
        transformState.applyTransform(t, preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
    } else
        transformState.move(translationOffset.width(), translationOffset.height(), preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
}

void RenderBoxModelObject::mapAbsoluteToLocalPoint(MapCoordinatesFlags mode, TransformState& transformState) const
{
    RenderObject* o = container();
    if (!o)
        return;

    if (o->isRenderFlowThread())
        transformState.move(o->columnOffset(LayoutPoint(transformState.mappedPoint())));

    o->mapAbsoluteToLocalPoint(mode, transformState);

    LayoutSize containerOffset = offsetFromContainer(o, LayoutPoint());

    if (!style()->hasOutOfFlowPosition() && o->hasColumns()) {
        RenderBlock* block = toRenderBlock(o);
        LayoutPoint point(roundedLayoutPoint(transformState.mappedPoint()));
        point -= containerOffset;
        block->adjustForColumnRect(containerOffset, point);
    }

    bool preserve3D = mode & UseTransforms && (o->style()->preserves3D() || style()->preserves3D());
    if (mode & UseTransforms && shouldUseTransformFromContainer(o)) {
        TransformationMatrix t;
        getTransformFromContainer(o, containerOffset, t);
        transformState.applyTransform(t, preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
    } else
        transformState.move(containerOffset.width(), containerOffset.height(), preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
}

mat4 RenderTile::translateVtxMatrix(const mat4& tileMatrix,
                                    const std::array<float, 2>& translation,
                                    TranslateAnchorType anchor,
                                    const TransformState& state,
                                    const bool inViewportPixelUnits) const {
    if (translation[0] == 0 && translation[1] == 0) {
        return tileMatrix;
    }

    mat4 vtxMatrix;

    const float angle = inViewportPixelUnits ?
        (anchor == TranslateAnchorType::Map ? state.getAngle() : 0) :
        (anchor == TranslateAnchorType::Viewport ? -state.getAngle() : 0);

    Point<float> translate = util::rotate(Point<float>{ translation[0], translation[1] }, angle);

    if (inViewportPixelUnits) {
        matrix::translate(vtxMatrix, tileMatrix, translate.x, translate.y, 0);
    } else {
        matrix::translate(vtxMatrix, tileMatrix,
                          id.pixelsToTileUnits(translate.x, state.getZoom()),
                          id.pixelsToTileUnits(translate.y, state.getZoom()),
                          0);
    }

    return vtxMatrix;
}

std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
    const double w = state.getWidth();
    const double h = state.getHeight();
    return tileCover(
        TileCoordinate::fromScreenCoordinate(state, z, { 0,   0   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { w,   0   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { w,   h   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { 0,   h   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { w/2, h/2 }).p,
        z);
}

void RenderGeometryMap::mapToContainer(TransformState& transformState,
                                       const RenderBox* container) const {
  // If the mapping includes something like columns, we have to go via
  // renderers.
  if (hasNonUniformStep()) {
    m_mapping.last().m_renderer->mapLocalToContainer(
        container, transformState, ApplyContainerFlip | m_mapCoordinatesFlags);
    transformState.flatten();
    return;
  }

#if ENABLE(ASSERT)
  bool foundContainer =
      !container || (m_mapping.size() && m_mapping[0].m_renderer == container);
#endif

  for (int i = m_mapping.size() - 1; i >= 0; --i) {
    const RenderGeometryMapStep& currentStep = m_mapping[i];

    // If container is the root RenderView (step 0) we want to apply its fixed
    // position offset.
    if (i > 0 && currentStep.m_renderer == container) {
#if ENABLE(ASSERT)
      foundContainer = true;
#endif
      break;
    }

    ASSERT(!i == isTopmostRenderView(currentStep.m_renderer));

    if (!i) {
      // A null container indicates mapping through the root RenderView, so
      // including its transform (the page scale).
      if (!container && currentStep.m_transform)
        transformState.applyTransform(*currentStep.m_transform.get());
    } else {
      TransformState::TransformAccumulation accumulate =
          currentStep.m_accumulatingTransform
              ? TransformState::AccumulateTransform
              : TransformState::FlattenTransform;
      if (currentStep.m_transform)
        transformState.applyTransform(*currentStep.m_transform.get(),
                                      accumulate);
      else
        transformState.move(currentStep.m_offset.width(),
                            currentStep.m_offset.height(), accumulate);
    }
  }

  ASSERT(foundContainer);
  transformState.flatten();
}

void RenderGeometryMap::mapToContainer(TransformState& transformState, const RenderLayerModelObject* container) const
{
    // If the mapping includes something like columns, we have to go via renderers.
    if (hasNonUniformStep()) {
        m_mapping.last().m_renderer->mapLocalToContainer(container, transformState, ApplyContainerFlip | m_mapCoordinatesFlags);
        return;
    }
    
    bool inFixed = false;
#if !ASSERT_DISABLED
    bool foundContainer = !container || (m_mapping.size() && m_mapping[0].m_renderer == container);
#endif

    for (int i = m_mapping.size() - 1; i >= 0; --i) {
        const RenderGeometryMapStep& currentStep = m_mapping[i];

        // If container is the RenderView (step 0) we want to apply its scroll offset.
        if (i > 0 && currentStep.m_renderer == container) {
#if !ASSERT_DISABLED
            foundContainer = true;
#endif
            break;
        }

        // If this box has a transform, it acts as a fixed position container
        // for fixed descendants, which prevents the propagation of 'fixed'
        // unless the layer itself is also fixed position.
        if (i && currentStep.m_hasTransform && !currentStep.m_isFixedPosition)
            inFixed = false;
        else if (currentStep.m_isFixedPosition)
            inFixed = true;

        if (!i) {
            // A null container indicates mapping through the RenderView, so including its transform (the page scale).
            if (!container && currentStep.m_transform)
                transformState.applyTransform(*currentStep.m_transform.get());

            // The root gets special treatment for fixed position
            if (inFixed)
                transformState.move(currentStep.m_offset.width(), currentStep.m_offset.height());
        } else {
            TransformState::TransformAccumulation accumulate = currentStep.m_accumulatingTransform ? TransformState::AccumulateTransform : TransformState::FlattenTransform;
            if (currentStep.m_transform)
                transformState.applyTransform(*currentStep.m_transform.get(), accumulate);
            else
                transformState.move(currentStep.m_offset.width(), currentStep.m_offset.height(), accumulate);
        }
    }

    ASSERT(foundContainer);
    transformState.flatten();    
}

std::vector<UnwrappedTileID> tileCover(const TransformState& state, int32_t z) {
    assert(state.valid());

    const double w = state.getSize().width;
    const double h = state.getSize().height;
    return tileCover(
        TileCoordinate::fromScreenCoordinate(state, z, { 0,   0   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { w,   0   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { w,   h   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { 0,   h   }).p,
        TileCoordinate::fromScreenCoordinate(state, z, { w/2, h/2 }).p,
        z);
}

void SVGRenderSupport::mapLocalToContainer(const RenderObject* object, const RenderLayerModelObject* repaintContainer, TransformState& transformState, bool* wasFixed)
{
    transformState.applyTransform(object->localToParentTransform());

    RenderObject* parent = object->parent();

    // At the SVG/HTML boundary (aka RenderSVGRoot), we apply the localToBorderBoxTransform
    // to map an element from SVG viewport coordinates to CSS box coordinates.
    // RenderSVGRoot's mapLocalToContainer method expects CSS box coordinates.
    if (parent->isSVGRoot())
        transformState.applyTransform(toRenderSVGRoot(parent)->localToBorderBoxTransform());

    MapCoordinatesFlags mode = UseTransforms;
    parent->mapLocalToContainer(repaintContainer, transformState, mode, wasFixed);
}

	/*
	 * Returns a matrix for converting from tile units to the correct label coordinate space.
	 */
    mat4 getLabelPlaneMatrix(const mat4& posMatrix, const bool pitchWithMap, const bool rotateWithMap, const TransformState& state, const float pixelsToTileUnits) {
        mat4 m;
        matrix::identity(m);
        if (pitchWithMap) {
            matrix::scale(m, m, 1 / pixelsToTileUnits, 1 / pixelsToTileUnits, 1);
            if (!rotateWithMap) {
                matrix::rotate_z(m, m, state.getBearing());
            }
        } else {
            matrix::scale(m, m, state.getSize().width / 2.0, -(state.getSize().height / 2.0), 1.0);
            matrix::translate(m, m, 1, -1, 0);
            matrix::multiply(m, m, posMatrix);
        }
        return m;
    }

void Style::update(MapData& data,
                   const TransformState& transform,
                   TexturePool& texturePool) {
    const float pixelRatio = transform.getPixelRatio();
    if (!sprite || !sprite->hasPixelRatio(pixelRatio)) {
        sprite = std::make_unique<Sprite>(spriteURL, pixelRatio);
        sprite->setObserver(this);

        spriteAtlas->resize(pixelRatio);
        spriteAtlas->setSprite(sprite);
    }

    bool allTilesUpdated = true;
    for (const auto& source : sources) {
        if (!source->update(data, transform, *this, *glyphAtlas, *glyphStore,
                       *spriteAtlas, sprite, texturePool, shouldReparsePartialTiles)) {
            allTilesUpdated = false;
        }
    }

    // We can only stop updating "partial" tiles when all of them
    // were notified of the arrival of the new resources.
    if (allTilesUpdated) {
        shouldReparsePartialTiles = false;
    }
}

void SVGRenderBase::mapLocalToContainer(const RenderObject* object, RenderBoxModelObject* repaintContainer, bool fixed , bool useTransforms, TransformState& transformState)
{
    ASSERT(!fixed); // We should have no fixed content in the SVG rendering tree.
    ASSERT(useTransforms); // Mapping a point through SVG w/o respecting transforms is useless.
    transformState.applyTransform(object->localToParentTransform());
    object->parent()->mapLocalToContainer(repaintContainer, fixed, useTransforms, transformState);
}

void Source::updateMatrices(const mat4 &projMatrix, const TransformState &transform) {
    for (std::pair<const Tile::ID, std::unique_ptr<Tile>> &pair : tiles) {
        Tile &tile = *pair.second;
        transform.matrixFor(tile.matrix, tile.id);
        matrix::multiply(tile.matrix, projMatrix, tile.matrix);
    }
}

void RenderView::mapAbsoluteToLocalPoint(MapCoordinatesFlags mode, TransformState& transformState) const
{
    if (mode & UseTransforms && shouldUseTransformFromContainer(0)) {
        TransformationMatrix t;
        getTransformFromContainer(0, LayoutSize(), t);
        transformState.applyTransform(t);
    }
}

void RenderView::mapAbsoluteToLocalPoint(bool fixed, bool /*useTransforms*/, TransformState& transformState) const
{
#if ENABLE(WKC_ANDROID_FIXED_ELEMENTS)
    if (false)
#endif
    if (fixed && m_frameView)
        transformState.move(-m_frameView->scrollOffset());
}