text: /*
   * This source file is part of RmlUi, the HTML/CSS Interface Middleware
   *
   * For the latest information, see http://github.com/mikke89/RmlUi
   *
   * Copyright (c) 2008-2010 CodePoint Ltd, Shift Technology Ltd
   * Copyright (c) 2019 The RmlUi Team, and contributors
   *
   * Permission is hereby granted, free of charge, to any person obtaining a copy
   * of this software and associated documentation files (the "Software"), to deal
   * in the Software without restriction, including without limitation the rights
   * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   * copies of the Software, and to permit persons to whom the Software is
   * furnished to do so, subject to the following conditions:
   *
   * The above copyright notice and this permission notice shall be included in
   * all copies or substantial portions of the Software.
   * 
   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
   * THE SOFTWARE.
   *
   */
  
  #include "LayoutEngine.h"
  #include "LayoutBlockBoxSpace.h"
  #include "LayoutDetails.h"
  #include "LayoutFlex.h"
  #include "LayoutInlineBoxText.h"
  #include "LayoutTable.h"
  #include "Pool.h"
  #include "../../Include/RmlUi/Core/Element.h"
  #include "../../Include/RmlUi/Core/Profiling.h"
  #include "../../Include/RmlUi/Core/Types.h"
  #include <cstddef>
  #include <float.h>
  
  namespace Rml {
  
  #define MAX(a, b) (a > b ? a : b)
  
  template <size_t Size>
  struct LayoutChunk {
  	alignas(std::max_align_t) byte buffer[Size];
  };
  
  static constexpr std::size_t ChunkSizeBig = sizeof(LayoutBlockBox);
  static constexpr std::size_t ChunkSizeMedium = MAX(sizeof(LayoutInlineBox), sizeof(LayoutInlineBoxText));
  static constexpr std::size_t ChunkSizeSmall = MAX(sizeof(LayoutLineBox), sizeof(LayoutBlockBoxSpace));
  
  static Pool< LayoutChunk<ChunkSizeBig> > layout_chunk_pool_big(50, true);
  static Pool< LayoutChunk<ChunkSizeMedium> > layout_chunk_pool_medium(50, true);
  static Pool< LayoutChunk<ChunkSizeSmall> > layout_chunk_pool_small(50, true);
  
  
  // Formats the contents for a root-level element (usually a document or floating element).
  void LayoutEngine::FormatElement(Element* element, Vector2f containing_block, const Box* override_initial_box, Vector2f* out_visible_overflow_size)
  {
  	RMLUI_ASSERT(element && containing_block.x >= 0 && containing_block.y >= 0);
  #ifdef RMLUI_ENABLE_PROFILING
  	RMLUI_ZoneScopedC(0xB22222);
  	auto name = CreateString(80, "%s %x", element->GetAddress(false, false).c_str(), element);
  	RMLUI_ZoneName(name.c_str(), name.size());
  #endif
  
  	auto containing_block_box = MakeUnique<LayoutBlockBox>(nullptr, nullptr, Box(containing_block), 0.0f, FLT_MAX);
  
  	Box box;
  	if (override_initial_box)
  		box = *override_initial_box;
  	else
  		LayoutDetails::BuildBox(box, containing_block, element);
  
  	float min_height, max_height;
  	LayoutDetails::GetDefiniteMinMaxHeight(min_height, max_height, element->GetComputedValues(), box, containing_block.y);
  
  	LayoutBlockBox* block_context_box = containing_block_box->AddBlockElement(element, box, min_height, max_height);
  
  	for (int layout_iteration = 0; layout_iteration < 2; layout_iteration++)
  	{
  		for (int i = 0; i < element->GetNumChildren(); i++)
  		{
  			if (!FormatElement(block_context_box, element->GetChild(i)))
  				i = -1;
  		}
  
  		if (block_context_box->Close() == LayoutBlockBox::OK)
  			break;
  	}
  
  	block_context_box->CloseAbsoluteElements();
  
  	if (out_visible_overflow_size)
  		*out_visible_overflow_size = block_context_box->GetVisibleOverflowSize();
  
  	element->OnLayout();
  }
  
  void* LayoutEngine::AllocateLayoutChunk(size_t size)
  {
  	static_assert(ChunkSizeBig > ChunkSizeMedium && ChunkSizeMedium > ChunkSizeSmall, "The following assumes a strict ordering of the chunk sizes.");
  
  	// Note: If any change is made here, make sure a corresponding change is applied to the deallocation procedure below.
  	if (size <= ChunkSizeSmall)
  		return layout_chunk_pool_small.AllocateAndConstruct();
  	else if (size <= ChunkSizeMedium)
  		return layout_chunk_pool_medium.AllocateAndConstruct();
  	else if (size <= ChunkSizeBig)
  		return layout_chunk_pool_big.AllocateAndConstruct();
  
  	RMLUI_ERROR;
  	return nullptr;
  }
  
  void LayoutEngine::DeallocateLayoutChunk(void* chunk, size_t size)
  {
  	// Note: If any change is made here, make sure a corresponding change is applied to the allocation procedure above.
  	if (size <= ChunkSizeSmall)
  		layout_chunk_pool_small.DestroyAndDeallocate((LayoutChunk<ChunkSizeSmall>*)chunk);
  	else if (size <= ChunkSizeMedium)
  		layout_chunk_pool_medium.DestroyAndDeallocate((LayoutChunk<ChunkSizeMedium>*)chunk);
  	else if (size <= ChunkSizeBig)
  		layout_chunk_pool_big.DestroyAndDeallocate((LayoutChunk<ChunkSizeBig>*)chunk);
  	else
  	{
  		RMLUI_ERROR;
  	}
  }
  
  // Positions a single element and its children within this layout.
  bool LayoutEngine::FormatElement(LayoutBlockBox* block_context_box, Element* element)
  {
  #ifdef RMLUI_ENABLE_PROFILING
  	RMLUI_ZoneScoped;
  	auto name = CreateString(80, ">%s %x", element->GetAddress(false, false).c_str(), element);
  	RMLUI_ZoneName(name.c_str(), name.size());
  #endif
  
  	auto& computed = element->GetComputedValues();
  
  	// Check if we have to do any special formatting for any elements that don't fit into the standard layout scheme.
  	if (FormatElementSpecial(block_context_box, element))
  		return true;
  
  	const Style::Display display = element->GetDisplay();
  
  	// Fetch the display property, and don't lay this element out if it is set to a display type of none.
  	if (display == Style::Display::None)
  		return true;
  
  	// Tables and flex boxes need to be specially handled when they are absolutely positioned or floated. Currently it is assumed for both
  	// FormatElement(element, containing_block) and GetShrinkToFitWidth(), and possibly others, that they are strictly called on block boxes.
  	// The mentioned functions need to be updated if we want to support all combinations of display, position, and float properties.
  	auto uses_unsupported_display_position_float_combination = [display, element](const char* abs_positioned_or_floated) -> bool {
  		if (display == Style::Display::Flex || display == Style::Display::Table)
  		{
  			const char* element_type = (display == Style::Display::Flex ? "Flex" : "Table");
  			Log::Message(Log::LT_WARNING,
  				"%s elements cannot be %s. Instead, wrap it within a parent block element which is %s. Element will not be formatted: %s",
  				element_type, abs_positioned_or_floated, abs_positioned_or_floated, element->GetAddress().c_str());
  			return true;
  		}
  		return false;
  	};
  
  	// Check for an absolute position; if this has been set, then we remove it from the flow and add it to the current
  	// block box to be laid out and positioned once the block has been closed and sized.
  	if (computed.position == Style::Position::Absolute || computed.position == Style::Position::Fixed)
  	{
  		if (uses_unsupported_display_position_float_combination("absolutely positioned"))
  			return true;
  
  		// Display the element as a block element.
  		block_context_box->AddAbsoluteElement(element);
  		return true;
  	}
  
  	// If the element is floating, we remove it from the flow.
  	if (computed.float_ != Style::Float::None)
  	{
  		if (uses_unsupported_display_position_float_combination("floated"))
  			return true;
  
  		LayoutEngine::FormatElement(element, LayoutDetails::GetContainingBlock(block_context_box));
  		return block_context_box->AddFloatElement(element);
  	}
  
  	// The element is nothing exceptional, so format it according to its display property.
  	switch (display)
  	{
  		case Style::Display::Block:       return FormatElementBlock(block_context_box, element);
  		case Style::Display::Inline:      return FormatElementInline(block_context_box, element);
  		case Style::Display::InlineBlock: return FormatElementInlineBlock(block_context_box, element);
  		case Style::Display::Flex:        return FormatElementFlex(block_context_box, element);
  		case Style::Display::Table:       return FormatElementTable(block_context_box, element);
  
  		case Style::Display::TableRow:
  		case Style::Display::TableRowGroup:
  		case Style::Display::TableColumn:
  		case Style::Display::TableColumnGroup:
  		case Style::Display::TableCell:
  		{
  			// These elements should have been handled within FormatElementTable, seems like we're encountering table parts in the wild.
  			const Property* display_property = element->GetProperty(PropertyId::Display);
  			Log::Message(Log::LT_WARNING, "Element has a display type '%s', but is not located in a table. Element will not be formatted: %s",
  				display_property ? display_property->ToString().c_str() : "*unknown*",
  				element->GetAddress().c_str()
  			);
  			return true;
  		}
  		case Style::Display::None:        RMLUI_ERROR; /* handled above */ break;
  	}
  
  	return true;
  }
  
  // Formats and positions an element as a block element.
  bool LayoutEngine::FormatElementBlock(LayoutBlockBox* block_context_box, Element* element)
  {
  	RMLUI_ZoneScopedC(0x2F4F4F);
  
  	Box box;
  	float min_height, max_height;
  	LayoutDetails::BuildBox(box, min_height, max_height, block_context_box, element);
  
  	LayoutBlockBox* new_block_context_box = block_context_box->AddBlockElement(element, box, min_height, max_height);
  	if (new_block_context_box == nullptr)
  		return false;
  
  	// Format the element's children.
  	for (int i = 0; i < element->GetNumChildren(); i++)
  	{
  		if (!FormatElement(new_block_context_box, element->GetChild(i)))
  			i = -1;
  	}
  
  	// Close the block box, and check the return code; we may have overflowed either this element or our parent.
  	switch (new_block_context_box->Close())
  	{
  		// We need to reformat ourself; format all of our children again and close the box. No need to check for error
  		// codes, as we already have our vertical slider bar.
  		case LayoutBlockBox::LAYOUT_SELF:
  		{
  			for (int i = 0; i < element->GetNumChildren(); i++)
  				FormatElement(new_block_context_box, element->GetChild(i));
  
  			if (new_block_context_box->Close() == LayoutBlockBox::OK)
  			{
  				element->OnLayout();
  				break;
  			}
  		}
  		//-fallthrough
  		// We caused our parent to add a vertical scrollbar; bail out!
  		case LayoutBlockBox::LAYOUT_PARENT:
  		{
  			return false;
  		}
  		break;
  
  		default:
  			element->OnLayout();
  	}
  
  	return true;
  }
  
  // Formats and positions an element as an inline element.
  bool LayoutEngine::FormatElementInline(LayoutBlockBox* block_context_box, Element* element)
  {
  	RMLUI_ZoneScopedC(0x3F6F6F);
  
  	const Vector2f containing_block = LayoutDetails::GetContainingBlock(block_context_box);
  
  	Box box;
  	LayoutDetails::BuildBox(box, containing_block, element, BoxContext::Inline);
  	LayoutInlineBox* inline_box = block_context_box->AddInlineElement(element, box);
  
  	// Format the element's children.
  	for (int i = 0; i < element->GetNumChildren(); i++)
  	{
  		if (!FormatElement(block_context_box, element->GetChild(i)))
  			return false;
  	}
  
  	inline_box->Close();
  
  	return true;
  }
  
  // Positions an element as a sized inline element, formatting its internal hierarchy as a block element.
  bool LayoutEngine::FormatElementInlineBlock(LayoutBlockBox* block_context_box, Element* element)
  {
  	RMLUI_ZoneScopedC(0x1F2F2F);
  
  	// Format the element separately as a block element, then position it inside our own layout as an inline element.
  	Vector2f containing_block_size = LayoutDetails::GetContainingBlock(block_context_box);
  
  	FormatElement(element, containing_block_size);
  
  	block_context_box->AddInlineElement(element, element->GetBox())->Close();
  
  	return true;
  }
  
  bool LayoutEngine::FormatElementFlex(LayoutBlockBox* block_context_box, Element* element)
  {
  	const ComputedValues& computed = element->GetComputedValues();
  	const Vector2f containing_block = LayoutDetails::GetContainingBlock(block_context_box);
  	RMLUI_ASSERT(containing_block.x >= 0.f);
  
  	// Build the initial box as specified by the flex's style, as if it was a normal block element.
  	Box box;
  	LayoutDetails::BuildBox(box, containing_block, element, BoxContext::Block);
  
  	Vector2f min_size, max_size;
  	LayoutDetails::GetMinMaxWidth(min_size.x, max_size.x, computed, box, containing_block.x);
  	LayoutDetails::GetMinMaxHeight(min_size.y, max_size.y, computed, box, containing_block.y);
  
  	// Add the flex container element as if it was a normal block element.
  	LayoutBlockBox* flex_block_context_box = block_context_box->AddBlockElement(element, box, min_size.y, max_size.y);
  	if (!flex_block_context_box)
  		return false;
  
  	// Format the flexbox and all its children.
  	ElementList absolutely_positioned_elements;
  	Vector2f formatted_content_size, content_overflow_size;
  	LayoutFlex::Format(
  		box, min_size, max_size, containing_block, element, formatted_content_size, content_overflow_size, absolutely_positioned_elements);
  
  	// Set the box content size to match the one determined by the formatting procedure.
  	flex_block_context_box->GetBox().SetContent(formatted_content_size);
  	// Set the inner content size so that any overflow can be caught.
  	flex_block_context_box->ExtendInnerContentSize(content_overflow_size);
  
  	// Finally, add any absolutely positioned flex children.
  	for (Element* abs_element : absolutely_positioned_elements)
  		flex_block_context_box->AddAbsoluteElement(abs_element);
  
  	// Close the block box, this may result in scrollbars being added to ourself or our parent.
  	const auto close_result = flex_block_context_box->Close();
  	if (close_result == LayoutBlockBox::LAYOUT_PARENT)
  	{
  		// Scollbars added to parent, bail out to reformat all its children.
  		return false;
  	}
  	else if (close_result == LayoutBlockBox::LAYOUT_SELF)
  	{
  		// Scrollbars added to flex container, it needs to be formatted again to account for changed width or height.
  		absolutely_positioned_elements.clear();
  
  		LayoutFlex::Format(
  			box, min_size, max_size, containing_block, element, formatted_content_size, content_overflow_size, absolutely_positioned_elements);
  
  		flex_block_context_box->GetBox().SetContent(formatted_content_size);
  		flex_block_context_box->ExtendInnerContentSize(content_overflow_size);
  
  		if (flex_block_context_box->Close() == LayoutBlockBox::LAYOUT_PARENT)
  			return false;
  	}
  
  	element->OnLayout();
  
  	return true;
  }
  
  
  bool LayoutEngine::FormatElementTable(LayoutBlockBox* block_context_box, Element* element_table)
  {
  	const ComputedValues& computed_table = element_table->GetComputedValues();
  
  	const Vector2f containing_block = LayoutDetails::GetContainingBlock(block_context_box);
  
  	// Build the initial box as specified by the table's style, as if it was a normal block element.
  	Box box;
  	LayoutDetails::BuildBox(box, containing_block, element_table, BoxContext::Block);
  
  	Vector2f min_size, max_size;
  	LayoutDetails::GetMinMaxWidth(min_size.x, max_size.x, computed_table, box, containing_block.x);
  	LayoutDetails::GetMinMaxHeight(min_size.y, max_size.y, computed_table, box, containing_block.y);
  	const Vector2f initial_content_size = box.GetSize();
  
  	// Format the table, this may adjust the box content size.
  	const Vector2f table_content_overflow_size = LayoutTable::FormatTable(box, min_size, max_size, element_table);
  
  	const Vector2f final_content_size = box.GetSize();
  	RMLUI_ASSERT(final_content_size.y >= 0);
  
  	if (final_content_size != initial_content_size)
  	{
  		// Perform this step to re-evaluate any auto margins.
  		LayoutDetails::BuildBoxSizeAndMargins(box, min_size, max_size, containing_block, element_table, BoxContext::Block, true);
  	}
  
  	// Now that the box is finalized, we can add table as a block element. If we did it earlier, eg. just before formatting the table,
  	// then the table element's offset would not be correct in cases where table size and auto-margins were adjusted.
  	LayoutBlockBox* table_block_context_box = block_context_box->AddBlockElement(element_table, box, final_content_size.y, final_content_size.y);
  	if (!table_block_context_box)
  		return false;
  
  	// Set the inner content size so that any overflow can be caught.
  	table_block_context_box->ExtendInnerContentSize(table_content_overflow_size);
  
  	// If the close failed, it probably means that its parent produced scrollbars.
  	if (table_block_context_box->Close() != LayoutBlockBox::OK)
  		return false;
  
  	return true;
  }
  
  // Executes any special formatting for special elements.
  bool LayoutEngine::FormatElementSpecial(LayoutBlockBox* block_context_box, Element* element)
  {
  	static const String br("br");
  	
  	// Check for a <br> tag.
  	if (element->GetTagName() == br)
  	{
  		block_context_box->AddBreak();
  		element->OnLayout();
  		return true;
  	}
  
  	return false;
  }
  
  } // namespace Rml
  