<commit_before>/*
 * Copyright 2010, 2011 Esrille Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "Box.h"

#include <algorithm>
#include <new>
#include <iostream>

#include <Object.h>
#include <org/w3c/dom/Document.h>
#include <org/w3c/dom/Element.h>
#include <org/w3c/dom/Text.h>
#include <org/w3c/dom/html/HTMLIFrameElement.h>
#include <org/w3c/dom/html/HTMLImageElement.h>

#include "CSSSerialize.h"
#include "CSSStyleDeclarationImp.h"
#include "CSSTokenizer.h"
#include "ViewCSSImp.h"
#include "WindowImp.h"

#include "Table.h"

namespace org { namespace w3c { namespace dom { namespace bootstrap {

namespace {

Element getContainingElement(Node node)
{
    for (; node; node = node.getParentNode()) {
        if (node.getNodeType() == Node::ELEMENT_NODE)
            return interface_cast<Element>(node);
    }
    return 0;
}

}

Box::Box(Node node) :
    node(node),
    parentBox(0),
    firstChild(0),
    lastChild(0),
    previousSibling(0),
    nextSibling(0),
    childCount(0),
    marginTop(0.0f),
    marginBottom(0.0f),
    marginLeft(0.0f),
    marginRight(0.0f),
    paddingTop(0.0f),
    paddingBottom(0.0f),
    paddingLeft(0.0f),
    paddingRight(0.0f),
    borderTop(0.0f),
    borderBottom(0.0f),
    borderLeft(0.0f),
    borderRight(0.0f),
    offsetH(0.0f),
    offsetV(0.0f),
    positioned(false),
    stackingContext(0),
    x(0.0f),
    y(0.0f),
    backgroundColor(0x00000000),
    backgroundImage(0),
    backgroundLeft(0.0f),
    backgroundTop(0.0f),
    style(0),
    formattingContext(0),
    flags(0),
    shadow(0)
{
}

Box::~Box()
{
    while (0 < childCount) {
        Box* child = removeChild(firstChild);
        child->release_();
    }
    delete backgroundImage;
}

Box* Box::removeChild(Box* item)
{
    Box* next = item->nextSibling;
    Box* prev = item->previousSibling;
    if (!next)
        lastChild = prev;
    else
        next->previousSibling = prev;
    if (!prev)
        firstChild = next;
    else
        prev->nextSibling = next;
    item->parentBox = 0;
    --childCount;
    return item;
}

Box* Box::insertBefore(Box* item, Box* after)
{
    if (!after)
        return appendChild(item);
    item->previousSibling = after->previousSibling;
    item->nextSibling = after;
    after->previousSibling = item;
    if (!item->previousSibling)
        firstChild = item;
    else
        item->previousSibling->nextSibling = item;
    item->parentBox = this;
    item->retain_();
    ++childCount;
    return item;
}

Box* Box::appendChild(Box* item)
{
    Box* prev = lastChild;
    if (!prev)
        firstChild = item;
    else
        prev->nextSibling = item;
    item->previousSibling = prev;
    item->nextSibling = 0;
    lastChild = item;
    item->parentBox = this;
    item->retain_();
    ++childCount;
    return item;
}

Box* Box::getParentBox() const
{
    return parentBox;
}

bool Box::hasChildBoxes() const
{
    return firstChild;
}

Box* Box::getFirstChild() const
{
    return firstChild;
}

Box* Box::getLastChild() const
{
    return lastChild;
}

Box* Box::getPreviousSibling() const
{
    return previousSibling;
}

Box* Box::getNextSibling() const
{
    return nextSibling;
}

void Box::updatePadding()
{
    paddingTop = style->paddingTop.getPx();
    paddingRight = style->paddingRight.getPx();
    paddingBottom = style->paddingBottom.getPx();
    paddingLeft = style->paddingLeft.getPx();
}

void Box::updateBorderWidth()
{
    borderTop = style->borderTopWidth.getPx();
    borderRight = style->borderRightWidth.getPx();
    borderBottom = style->borderBottomWidth.getPx();
    borderLeft = style->borderLeftWidth.getPx();
}

const ContainingBlock* Box::getContainingBlock(ViewCSSImp* view) const
{
    const Box* box = this;
    do {
        const Box* parent = box->getParentBox();
        if (!parent)
            return view->getInitialContainingBlock();
        box = parent;
    } while (box->getBoxType() != BLOCK_LEVEL_BOX);
    return box;
}

// We also calculate offsetH and offsetV here.
void BlockLevelBox::setContainingBlock(ViewCSSImp* view)
{
    assert(isAbsolutelyPositioned());
    float x = 0.0f;
    float y = 0.0f;
    const Box* staticPosition = Box::towardViewPort(x, y);
    assert(staticPosition);
    if (!isFixed()) {
        assert(node);
        for (auto ancestor = node.getParentElement(); ancestor; ancestor = ancestor.getParentElement()) {
            CSSStyleDeclarationImp* style = view->getStyle(ancestor);
            if (!style)
                break;
            switch (style->position.getValue()) {
            case CSSPositionValueImp::Absolute:
            case CSSPositionValueImp::Relative:
            case CSSPositionValueImp::Fixed: {
                // Now we need to find the corresponding box for this ancestor.
                const Box* box = style->box;
                assert(box);
                while (box != staticPosition)
                    staticPosition = staticPosition->towardViewPort(x, y);
                offsetH = -x - box->paddingLeft;
                offsetV = -y - box->paddingTop;
                if (box->getBoxType() == BLOCK_LEVEL_BOX) {
                    absoluteBlock.width = box->getPaddingWidth();
                    absoluteBlock.height = box->getPaddingHeight();
                } else {
                    assert(box->getBoxType() == INLINE_LEVEL_BOX);
                    if (Box* inlineBlock = box->getFirstChild()) {
                        absoluteBlock.width = inlineBlock->getPaddingWidth();
                        absoluteBlock.height = inlineBlock->getPaddingHeight();
                    } else {
                        const Box* p = box->getParentBox();
                        float t = -box->paddingTop;
                        float l = -box->paddingLeft;
                        while (box != p)
                            box = box->towardViewPort(t, l);
                        box = style->lastBox;
                        float b = box->height + box->paddingBottom;
                        float r = box->width + box->paddingRight;
                        while (box != p)
                            box = box->towardViewPort(b, r);
                        absoluteBlock.width = r - l;
                        absoluteBlock.height = t - b;
                    }
                }

                // TODO: overflow
                while (staticPosition)
                    staticPosition = staticPosition->towardViewPort(x, y);
                absoluteBlock.width = view->getInitialContainingBlock()->width - x;
                absoluteBlock.height = view->getInitialContainingBlock()->height - y;
                return;
            }
            default:
                break;
            }
        }
    }
    while (staticPosition)
        staticPosition = staticPosition->towardViewPort(x, y);
    offsetH = -x;
    offsetV = -y;
    absoluteBlock.width = view->getInitialContainingBlock()->width - x;
    absoluteBlock.height = view->getInitialContainingBlock()->height - y;
}

FormattingContext* Box::updateFormattingContext(FormattingContext* context)
{
    if (isFlowRoot())
        return formattingContext;
    // TODO: adjust left and right blanks.
    return context;
}

bool Box::isFlowOf(const Box* flowRoot) const
{
    assert(flowRoot->isFlowRoot());
    for (const Box* box = this; box; box = box->getParentBox()) {
        if (box == flowRoot)
            return true;
    }
    return false;
}

// Calculate left, right, top, bottom for 'static' or 'relative' element.
// TODO: rtl
void Box::resolveOffset(CSSStyleDeclarationImp* style)
{
    assert(style->position.getValue() == CSSPositionValueImp::Relative ||
           style->position.getValue() == CSSPositionValueImp::Static);

    float h = 0.0f;
    if (!style->left.isAuto())
        h = style->left.getPx();
    else if (!style->right.isAuto())
        h = -style->right.getPx();
    offsetH += h;

    float v = 0.0f;
    if (!style->top.isAuto())
        v = style->top.getPx();
    else if (!style->bottom.isAuto())
        v = -style->bottom.getPx();
    offsetV += v;
}

void Box::resolveOffset(ViewCSSImp* view)
{
    if (isAnonymous())
        return;
    resolveOffset(getStyle());
}

bool BlockLevelBox::isFloat() const
{
    return style && style->isFloat();
}

bool BlockLevelBox::isFixed() const
{
    return style && style->position.getValue() == CSSPositionValueImp::Fixed;
}

bool BlockLevelBox::isAbsolutelyPositioned() const
{
    return style && style->isAbsolutelyPositioned();
}

void BlockLevelBox::dump(ViewCSSImp* view, std::string indent)
{
    std::cout << indent << "* block-level box (" << static_cast<void*>(this);
    if (!node)
        std::cout << ") [anonymous]";
    else {
        std::cout << ':' << node.self() << ')';
        std::cout << " [" << node.getNodeName() << ']';
    }
    std::cout << " (" << x << ", " << y << "), (" << getTotalWidth() << ", " << getTotalHeight() << ") " <<
    "m:" << marginTop << '-' << marginRight << '-' << marginBottom << '-' << marginLeft << ' ' <<
    "p:" << paddingTop << '-' <<  paddingRight << '-'<< paddingBottom<< '-' << paddingLeft << ' ' <<
    "b:" << borderTop << '-' <<  borderRight << '-' << borderBottom<< '-' << borderLeft << '\n';
    indent += "    ";
    if (!getFirstChild() && hasInline()) {
        for (auto i = inlines.begin(); i != inlines.end(); ++i) {
            if ((*i).getNodeType() == Node::TEXT_NODE) {
                Text text = interface_cast<Text>(*i);
                std::cout << indent << "* inline-level box: \"" << text.getData() << "\"\n";
            } else if (Box* box = view->getFloatBox(*i))
                box->dump(view, indent);
        }
        return;
    }
    for (Box* child = getFirstChild(); child; child = child->getNextSibling())
        child->dump(view, indent);
}

BlockLevelBox* BlockLevelBox::getAnonymousBox()
{
    BlockLevelBox* anonymousBox;
    if (hasAnonymousBox()) {
        anonymousBox = dynamic_cast<BlockLevelBox*>(firstChild);
        if (anonymousBox)
            return anonymousBox;
    }
    anonymousBox = new(std::nothrow) BlockLevelBox;
    if (anonymousBox) {
        anonymousBox->spliceInline(this);
        if (firstChild)
            insertBefore(anonymousBox, firstChild);
        else
            appendChild(anonymousBox);
    }
    return anonymousBox;
}

void BlockLevelBox::resolveWidth(ViewCSSImp* view, const ContainingBlock* containingBlock, float available)
{
    assert(style);
    resolveBackground(view);
    updatePadding();
    updateBorderWidth();
    resolveMargin(view, containingBlock, available);
}

void BlockLevelBox::resolveBackground(ViewCSSImp* view)
{
    assert(style);
    backgroundColor = style->backgroundColor.getARGB();
    if (!style->backgroundImage.isNone()) {
        view->preload(view->getDocument().getDocumentURI(), style->backgroundImage.getValue());
        backgroundImage = new(std::nothrow) BoxImage(this, view->getDocument().getDocumentURI(), style->backgroundImage.getValue(), style->backgroundRepeat.getValue());
    }
}

void BlockLevelBox::resolveWidth(float w)
{
    resolveNormalWidth(w);
    if (!style->maxWidth.isNone()) {
        float maxWidth = style->maxWidth.getPx();
        if (maxWidth < width)
            resolveNormalWidth(w, maxWidth);
    }
    float minWidth = style->minWidth.getPx();
    if (width < minWidth)
        resolveNormalWidth(w, minWidth);
}

// Calculate width
//
// marginLeft + borderLeftWidth + paddingLeft + width + paddingRight + borderRightWidth + marginRight
// == containingBlock->width (- scrollbar width, if any)
void BlockLevelBox::resolveNormalWidth(float w, float r)
{
    int autoCount = 3;
    unsigned autoMask = Left | Width | Right;
    if (style) {
        if (style->isFloat() || style->isInlineBlock())
            return resolveFloatWidth(w);
        if (!isnan(r)) {
            width = r;
            --autoCount;
            autoMask &= ~Width;
            w -= width;
        } else if (!style->width.isAuto()) {
            width = style->width.getPx();
            --autoCount;
            autoMask &= ~Width;
            w -= width;
        }
        if (!style->marginLeft.isAuto()) {
            marginLeft = style->marginLeft.getPx();
            --autoCount;
            autoMask &= ~Left;
            w -= marginLeft;
        }
        if (!style->marginRight.isAuto()) {  // TODO: assuming LTR
            if (1 < autoCount) {
                marginRight = style->marginRight.getPx();
                --autoCount;
                autoMask &= ~Right;
                w -= marginRight;
            }
        }
    }
    w -= borderLeft + paddingLeft + paddingRight + borderRight;
    switch (autoMask) {
    case Left | Width | Right:
        width = w;
        marginLeft = marginRight = 0.0f;
        break;
    case Left | Width:
        width = w;
        marginLeft = 0.0f;
        break;
    case Width | Right:
        width = w;
        marginRight = 0.0f;
        break;
    case Left | Right:
        marginLeft = marginRight = w / 2.0f;
        break;
    case Left:
        marginLeft = w;
        break;
    case Width:
        width = w;
        break;
    case Right:
        marginRight = w;
        break;
    default:
        break;
    }
}

void BlockLevelBox::resolveFloatWidth(float w, float r)
{
    assert(style);
    marginLeft = style->marginLeft.isAuto() ? 0.0f : style->marginLeft.getPx();
    marginRight = style->marginRight.isAuto() ? 0.0f : style->marginRight.getPx();
    if (!isnan(r))
        width = r;
    else if (!style->width.isAuto())
        width = style->width.getPx();
    else
        width = w - getBlankLeft() - getBlankRight();
}

void BlockLevelBox::resolveMargin(ViewCSSImp* view, const ContainingBlock* containingBlock, float available)
{
    resolveWidth((available != 0.0f) ? available : containingBlock->width);
    if (!style->marginTop.isAuto())
        marginTop = style->marginTop.getPx();
    else
        marginTop = 0;
    if (!style->marginBottom.isAuto())
        marginBottom = style->marginBottom.getPx();
    else
        marginBottom = 0;
    if (!style->height.isAuto())
        height = style->height.getPx();
}

void BlockLevelBox::layOutText(ViewCSSImp* view, Text text, FormattingContext* context)
{
    CSSStyleDeclarationImp* style = 0;
    Element element = getContainingElement(text);
    if (!element)
        return;  // TODO error

    style = view->getStyle(element);
    if (!style)
        return;  // TODO error
    style->resolve(view, this, element);
    std::u16string data = text.getData();
    if (style->processWhiteSpace(data, context->prevChar) == 0)
        return;

    bool psuedoChecked = false;
    CSSStyleDeclarationImp* firstLineStyle = 0;
    CSSStyleDeclarationImp* firstLetterStyle = 0;
    CSSStyleDeclarationImp* activeStyle = style;

    FontTexture* font = view->selectFont(activeStyle);
    float point = view->getPointFromPx(activeStyle->fontSize.getPx());
    size_t position = 0;
    for (;;) {
        if (!context->lineBox) {
            if (style->processLineHeadWhiteSpace(data) == 0)
                return;
            if (!context->addLineBox(view, this))
                return;  // TODO error
            if (!psuedoChecked && getFirstChild() == context->lineBox) {
                psuedoChecked  = true;
                // The current line box is the 1st line of this block box.
                // style to use can be a pseudo element styles from any ancestor elements.
                // Note the :first-line, first-letter pseudo-elements can only be attached to a block container element.
                std::list<CSSStyleDeclarationImp*> firstLineStyles;
                std::list<CSSStyleDeclarationImp*> firstLetterStyles;
                Box* box = this;
                for (;;) {
                    if (CSSStyleDeclarationImp* s = box->getStyle()) {
                        if (CSSStyleDeclarationImp* p = s->getPseudoElementStyle(CSSPseudoElementSelector::FirstLine))
                            firstLineStyles.push_front(p);
                        if (CSSStyleDeclarationImp* p = s->getPseudoElementStyle(CSSPseudoElementSelector::FirstLetter))
                            firstLetterStyles.push_front(p);
                    }
                    Box* parent = box->getParentBox();
                    if (!parent || parent->getFirstChild() != box)
                        break;
                    box = parent;
                }
                if (!firstLineStyles.empty()) {
                    CSSStyleDeclarationImp* parentStyle = style;
                    for (auto i = firstLineStyles.begin(); i != firstLineStyles.end(); ++i) {
                        (*i)->compute(view, parentStyle, 0);
                        parentStyle = *i;
                    }
                    firstLineStyle = firstLineStyles.back();
                    CSSStyleDeclarationImp* p = style->createPseudoElementStyle(CSSPseudoElementSelector::FirstLine);
                    assert(p);  // TODO
                    p->specify(firstLineStyle);
                    firstLineStyle = p;
                }
                if (!firstLetterStyles.empty()) {
                    CSSStyleDeclarationImp* parentStyle = style;
                    for (auto i = firstLetterStyles.begin(); i != firstLetterStyles.end(); ++i) {
                        (*i)->compute(view, parentStyle, 0);
                        parentStyle = *i;
                    }
                    firstLetterStyle = firstLetterStyles.back();
                    CSSStyleDeclarationImp* p = style->createPseudoElementStyle(CSSPseudoElementSelector::FirstLetter);
                    assert(p);  // TODO
                    p->specify(firstLetterStyle);
                    firstLetterStyle = p;
                }
                if (firstLetterStyle) {
                    activeStyle = firstLetterStyle;
                    font = view->selectFont(activeStyle);
                    point = view->getPointFromPx(activeStyle->fontSize.getPx());
                } else if (firstLineStyle) {
                    activeStyle = firstLineStyle;
                    font = view->selectFont(activeStyle);
                    point = view->getPointFromPx(activeStyle->fontSize.getPx());
                }
            }
        }

        InlineLevelBox* inlineLevelBox = new(std::nothrow) InlineLevelBox(text, activeStyle);
        if (!inlineLevelBox)
            return;  // TODO error
        style->addBox(inlineLevelBox);  // activeStyle? maybe not...
        inlineLevelBox->resolveWidth();
        float blankLeft = inlineLevelBox->getBlankLeft();
        if (0 < position)  // TODO: this is a bit awkward...
            inlineLevelBox->marginLeft = inlineLevelBox->paddingLeft = inlineLevelBox->borderLeft = blankLeft = 0;
        float blankRight = inlineLevelBox->getBlankRight();
        context->x += blankLeft;
        context->leftover -= blankLeft + blankRight;

        size_t fitLength = firstLetterStyle ? 1 : data.length();  // TODO: 1 is absolutely wrong...

        // We are still not sure if there's a room for text in context->lineBox.
        // If there's no room due to float box(es), move the linebox down to
        // the closest bottom of float box.
        // And repeat this process until there's no more float box in the context.
        float advanced;
        size_t length;
        bool linefeed;
        linefeed = false;
        size_t next = 1;
        float required = 0.0f;
        do {
            advanced = context->leftover;
            if (data[0] == '\n') {
                linefeed = true;
                length = 1;
                advanced = 0.0f;
                break;
            }
            length = font->fitText(data.c_str(), fitLength, point, context->leftover, &next, &required);
            if (0 < length) {
                advanced -= context->leftover;
                break;
            }
        } while (context->shiftDownLineBox());
        if (length == 0) {
            context->leftover -= required;
            advanced -= context->leftover;
            length = next;
        }

        if (!linefeed) {
            inlineLevelBox->setData(font, point, data.substr(0, length));
            inlineLevelBox->width = advanced;
            if (!firstLetterStyle && length < data.length()) {  // TODO: firstLetterStyle : actually we are not sure if the following characters would fit in the same line box...
                inlineLevelBox->marginRight = inlineLevelBox->paddingRight = inlineLevelBox->borderRight = blankRight = 0;
            }
        }
        inlineLevelBox->height = font->getHeight(point);
        inlineLevelBox->baseline += (activeStyle->lineHeight.getPx() - inlineLevelBox->height) / 2.0f;
        context->x += advanced + blankRight;
        LineBox* lineBox = context->lineBox;
        lineBox->appendChild(inlineLevelBox);
        lineBox->height = std::max(lineBox->height, std::max(activeStyle->lineHeight.getPx(), inlineLevelBox->height));
        lineBox->baseline = std::max(lineBox->baseline, inlineLevelBox->baseline);
        lineBox->width += blankLeft + advanced + blankRight;
        lineBox->underlinePosition = std::max(lineBox->underlinePosition, font->getUnderlinePosition(point));
        lineBox->underlineThickness = std::max(lineBox->underlineThickness, font->getUnderlineThickness(point));
        position += length;
        data.erase(0, length);
        if (data.length() == 0) {  // layout done?
            if (linefeed)
                context->nextLine(this);
            break;
        }

        if (firstLetterStyle) {
            firstLetterStyle = 0;
            if (firstLineStyle) {
                activeStyle = firstLineStyle;
                font = view->selectFont(activeStyle);
                point = view->getPointFromPx(activeStyle->fontSize.getPx());
            } else {
                activeStyle = style;
                font = view->selectFont(activeStyle);
                point = view->getPointFromPx(activeStyle->fontSize.getPx());
            }
        } else {
            context->nextLine(this);
            if (firstLineStyle) {
                firstLineStyle = 0;
                activeStyle = style;
                font = view->selectFont(activeStyle);
                point = view->getPointFromPx(activeStyle->fontSize.getPx());
            }
        }
    }
}

void BlockLevelBox::layOutInlineReplaced(ViewCSSImp* view, Node node, FormattingContext* context)
{
    CSSStyleDeclarationImp* style = 0;
    Element element = 0;
    if (element = getContainingElement(node)) {
        style = view->getStyle(element);
        if (!style)
            return;  // TODO error
        style->resolve(view, this, element);
    } else
        return;  // TODO error

    if (!context->lineBox) {
        if (!context->addLineBox(view, this))
            return;  // TODO error
    }
    InlineLevelBox* inlineLevelBox = new(std::nothrow) InlineLevelBox(node, style);
    if (!inlineLevelBox)
        return;  // TODO error
    style->addBox(inlineLevelBox);

    inlineLevelBox->resolveWidth();
    if (!style->width.isAuto())
        inlineLevelBox->width = style->width.getPx();
    else
        inlineLevelBox->width = 300;  // TODO
    if (!style->height.isAuto())
        inlineLevelBox->height = style->height.getPx();
    else
        inlineLevelBox->height = 24;  // TODO

    context->prevChar = 0;

    std::u16string tag = element.getLocalName();
    if (tag == u"img") {
        html::HTMLImageElement img = interface_cast<html::HTMLImageElement>(element);
        if (BoxImage* backgroundImage = new(std::nothrow) BoxImage(inlineLevelBox, view->getDocument().getDocumentURI(), img)) {
            inlineLevelBox->backgroundImage = backgroundImage;
            if (style->width.isAuto())
                inlineLevelBox->width = backgroundImage->getWidth();
            if (style->height.isAuto())
                inlineLevelBox->height = backgroundImage->getHeight();
        }
    } else if (tag == u"iframe") {
        html::HTMLIFrameElement iframe = interface_cast<html::HTMLIFrameElement>(element);
        inlineLevelBox->width = CSSTokenizer::parseInt(iframe.getWidth().c_str(), iframe.getWidth().size());
        inlineLevelBox->height = CSSTokenizer::parseInt(iframe.getHeight().c_str(), iframe.getHeight().size());
        html::Window contentWindow = iframe.getContentWindow();
        if (WindowImp* imp = dynamic_cast<WindowImp*>(contentWindow.self())) {
            imp->setSize(inlineLevelBox->width, inlineLevelBox->height);
            inlineLevelBox->shadow = imp->getView();
            std::u16string src = iframe.getSrc();
            if (!src.empty() && !imp->getDocument())
                iframe.setSrc(src);
        }
    } else if (!style->isInlineBlock()) {
        // TODO: This line should not be reached but currently it is as absolute boxes are created lazily.
        return;
    } else if (BlockLevelBox* inlineBlock = view->layOutBlockBoxes(element, 0, 0, 0, true)) {
        inlineLevelBox->appendChild(inlineBlock);
        inlineBlock->layOut(view, context);
        inlineLevelBox->width = inlineBlock->getTotalWidth();
        inlineLevelBox->marginLeft = inlineLevelBox->marginRight =
        inlineLevelBox->borderLeft = inlineLevelBox->borderRight =
        inlineLevelBox->paddingLeft = inlineLevelBox->paddingRight = 0.0f;

        inlineLevelBox->height = inlineBlock->getTotalHeight();
        inlineLevelBox->marginTop = inlineLevelBox->marginBottom =
        inlineLevelBox->borderTop = inlineLevelBox->borderBottom =
        inlineLevelBox->paddingTop = inlineLevelBox->paddingBottom = 0.0f;

        inlineLevelBox->baseline = inlineBlock->getBlankTop() + inlineBlock->height;
    } else
        return;  // TODO

    // TODO: calc inlineLevelBox->width and height with intrinsic values.
    if (inlineLevelBox->baseline == 0.0f)
        inlineLevelBox->baseline = inlineLevelBox->getBlankTop() + inlineLevelBox->height;  // TODO

    float blankLeft = inlineLevelBox->getBlankLeft();
    float blankRight = inlineLevelBox->getBlankRight();
    context->x += blankLeft;
    context->leftover -= blankLeft + blankRight;

    // We are still not sure if there's a room for text in context->lineBox.
    // If there's no room due to float box(es), move the linebox down to
    // the closest bottom of float box.
    // And repeat this process until there's no more float box in the context.
    do {
        if (inlineLevelBox->width <= context->leftover) {
            context->leftover -= inlineLevelBox->width;
            break;
        }
    } while (context->shiftDownLineBox());
    // TODO: deal with overflow

    context->x += inlineLevelBox->width + blankRight;
    LineBox* lineBox = context->lineBox;
    lineBox->appendChild(inlineLevelBox);
    lineBox->height = std::max(lineBox->height, inlineLevelBox->height);  // TODO: marginTop, etc.???
    lineBox->baseline = std::max(lineBox->baseline, inlineLevelBox->baseline);
    lineBox->width += blankLeft + inlineLevelBox->width + blankRight;
}

void BlockLevelBox::layOutFloat(ViewCSSImp* view, Node node, BlockLevelBox* floatBox, FormattingContext* context)
{
    assert(floatBox->style);
    if (!context->lineBox) {
        if (!context->addLineBox(view, this))
            return;   // TODO error
    }
    floatBox->layOut(view, context);
    floatBox->remainingHeight = floatBox->getTotalHeight();
    float w = floatBox->getTotalWidth();
    if (context->leftover < w && 0.0f < context->getLeftEdge()) {
        // Process this float box later in the other line box.
        context->floatNodes.push_back(node);
        return;
    }
    context->addFloat(floatBox, w);
}

void BlockLevelBox::layOutAbsolute(ViewCSSImp* view, Node node, BlockLevelBox* absBox, FormattingContext* context)
{
    // Just insert this absolute box into a line box now.
    // Absolute boxes will be processed later in ViewCSSImp::layOut().
    if (!context->lineBox) {
        if (!context->addLineBox(view, this))
            return;  // TODO error
    }
    context->lineBox->appendChild(absBox);
}

// Generate line boxes
void BlockLevelBox::layOutInline(ViewCSSImp* view, FormattingContext* context)
{
    assert(!hasChildBoxes());
    for (auto i = inlines.begin(); i != inlines.end(); ++i) {
        if (BlockLevelBox* box = view->getFloatBox(*i)) {
            if (box->isFloat())
                layOutFloat(view, *i, box, context);
            else if (box->isAbsolutelyPositioned())
                layOutAbsolute(view, *i, box, context);
        } else if ((*i).getNodeType() == Node::TEXT_NODE) {
            Text text = interface_cast<Text>(*i);
            layOutText(view, text, context);
        } else {
            // At this point, *i should be a replaced element or an inline block element.
            // TODO: it could be of other types as we develop...
            layOutInlineReplaced(view, *i, context);
        }
    }
    if (context->lineBox)
        context->nextLine(this);
}

// TODO for a more complete implementation, see,
//      http://groups.google.com/group/netscape.public.mozilla.layout/msg/0455a21b048ffac3?pli=1

void BlockLevelBox::shrinkToFit()
{
    fit(shrinkTo());
}

// returns the minimum total width
float Box::shrinkTo()
{
    return getTotalWidth();
}

float BlockLevelBox::shrinkTo()
{
    int autoCount = 3;
    float min = 0.0f;
    if (style && !style->width.isAuto()) {
        --autoCount;
        min = style->width.getPx();
    } else {
        for (Box* child = getFirstChild(); child; child = child->getNextSibling())
            min = std::max(min, child->shrinkTo());
    }
    min += borderLeft + paddingLeft + paddingRight + borderRight;
    if (style) {
        if (!style->marginLeft.isAuto()) {
            --autoCount;
            min += style->marginLeft.getPx();
        }
        if (!style->marginRight.isAuto()) {
            --autoCount;
            if (0 < autoCount)
                min += style->marginRight.getPx();
        }
    }
    return min;
}

void BlockLevelBox::fit(float w)
{
    if (getTotalWidth() == w)
        return;
    resolveWidth(w);
    if (style && !style->width.isAuto())
        return;
    for (Box* child = getFirstChild(); child; child = child->getNextSibling())
        child->fit(width);
}

FormattingContext* BlockLevelBox::collapseMargins(FormattingContext* context)
{
    if (Box* parent = getParentBox()) {  // TODO: root exception
        if (parent->getFirstChild() == this &&
            parent->borderTop == 0 && parent->paddingTop == 0 /* && TODO: check clearance */) {
            marginTop = std::max(marginTop, parent->marginTop);  // TODO: negative case
            parent->marginTop = 0.0f;
        } else if (Box* prev = getPreviousSibling()) {
            marginTop = std::max(prev->marginBottom, marginTop);  // TODO: negative case
            prev->marginBottom = 0.0f;
        }
    }
    context = updateFormattingContext(context);
    assert(context);
    context->updateRemainingHeight(getBlankTop());
    marginTop += context->clear(style->clear.getValue());
    return context;
}

void BlockLevelBox::collapseMarginBottom()
{
    // TODO: root exception
    if (height == 0 && borderBottom == 0 && paddingBottom == 0 /* && TODO: check clearance */) {
        if (Box* child = getLastChild()) {
            marginBottom = std::max(marginBottom, child->marginBottom);  // TODO: negative case
            child->marginBottom = 0;
        }
    }
}

void BlockLevelBox::layOut(ViewCSSImp* view, FormattingContext* context)
{
    const ContainingBlock* containingBlock = getContainingBlock(view);

    Element element = 0;
    if (!isAnonymous())
        element = getContainingElement(node);
    else if (const Box* box = dynamic_cast<const Box*>(containingBlock))
        element = getContainingElement(box->node);
    if (!element)
        return;  // TODO error

    style = view->getStyle(element);
    if (!style)
        return;  // TODO error

    if (!isAnonymous()) {
        style->resolve(view, containingBlock, element);
        resolveWidth(view, containingBlock,
                     (style->isInlineBlock() || style->isFloat()) ? context->leftover : 0.0f);
    } else {
        // The properties of anonymous boxes are inherited from the enclosing non-anonymous box.
        // Theoretically, we are supposed to create a new style for this anonymous box, but
        // of course we don't want to do so.
        backgroundColor = 0x00000000;
        paddingTop = paddingRight = paddingBottom = paddingLeft = 0.0f;
        borderTop = borderRight = borderBottom = borderLeft = 0.0f;
        marginTop = marginRight = marginLeft = marginBottom = 0.0f;
        width = containingBlock->width;
        height = 0.0f;
        stackingContext = style->getStackingContext();
    }

    textAlign = style->textAlign.getValue();
    context = collapseMargins(context);

    if (hasInline())
        layOutInline(view, context);
    for (Box* child = getFirstChild(); child; child = child->getNextSibling()) {
        child->layOut(view, context);
        // TODO: overflow
        width = std::max(width, child->getTotalWidth());
    }

    if ((style->width.isAuto() || style->marginLeft.isAuto() || style->marginRight.isAuto()) &&
        (style->isInlineBlock() || style->isFloat() || style->display == CSSDisplayValueImp::TableCell))
        shrinkToFit();

    collapseMarginBottom();

    if (isFlowRoot()) {
        float h = context->clear(3);
        if (Box* last = getLastChild())
            last->marginBottom += h;
        // Layout remaining float boxes in context
        while (!context->floatNodes.empty()) {
            context->addLineBox(view, this);
            context->nextLine(this, !context->floatNodes.empty());
        }
    }

    if (style->height.isAuto() || isAnonymous()) {
        height = 0.0f;<commit_msg>(BlockLevelBox::layOut) : Update the remaining float height by the heights of flow root children.<commit_after>/*
 * Copyright 2010, 2011 Esrille Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "Box.h"

#include <algorithm>
#include <new>
#include <iostream>

#include <Object.h>
#include <org/w3c/dom/Document.h>
#include <org/w3c/dom/Element.h>
#include <org/w3c/dom/Text.h>
#include <org/w3c/dom/html/HTMLIFrameElement.h>
#include <org/w3c/dom/html/HTMLImageElement.h>

#include "CSSSerialize.h"
#include "CSSStyleDeclarationImp.h"
#include "CSSTokenizer.h"
#include "ViewCSSImp.h"
#include "WindowImp.h"

#include "Table.h"

namespace org { namespace w3c { namespace dom { namespace bootstrap {

namespace {

Element getContainingElement(Node node)
{
    for (; node; node = node.getParentNode()) {
        if (node.getNodeType() == Node::ELEMENT_NODE)
            return interface_cast<Element>(node);
    }
    return 0;
}

}

Box::Box(Node node) :
    node(node),
    parentBox(0),
    firstChild(0),
    lastChild(0),
    previousSibling(0),
    nextSibling(0),
    childCount(0),
    marginTop(0.0f),
    marginBottom(0.0f),
    marginLeft(0.0f),
    marginRight(0.0f),
    paddingTop(0.0f),
    paddingBottom(0.0f),
    paddingLeft(0.0f),
    paddingRight(0.0f),
    borderTop(0.0f),
    borderBottom(0.0f),
    borderLeft(0.0f),
    borderRight(0.0f),
    offsetH(0.0f),
    offsetV(0.0f),
    positioned(false),
    stackingContext(0),
    x(0.0f),
    y(0.0f),
    backgroundColor(0x00000000),
    backgroundImage(0),
    backgroundLeft(0.0f),
    backgroundTop(0.0f),
    style(0),
    formattingContext(0),
    flags(0),
    shadow(0)
{
}

Box::~Box()
{
    while (0 < childCount) {
        Box* child = removeChild(firstChild);
        child->release_();
    }
    delete backgroundImage;
}

Box* Box::removeChild(Box* item)
{
    Box* next = item->nextSibling;
    Box* prev = item->previousSibling;
    if (!next)
        lastChild = prev;
    else
        next->previousSibling = prev;
    if (!prev)
        firstChild = next;
    else
        prev->nextSibling = next;
    item->parentBox = 0;
    --childCount;
    return item;
}

Box* Box::insertBefore(Box* item, Box* after)
{
    if (!after)
        return appendChild(item);
    item->previousSibling = after->previousSibling;
    item->nextSibling = after;
    after->previousSibling = item;
    if (!item->previousSibling)
        firstChild = item;
    else
        item->previousSibling->nextSibling = item;
    item->parentBox = this;
    item->retain_();
    ++childCount;
    return item;
}

Box* Box::appendChild(Box* item)
{
    Box* prev = lastChild;
    if (!prev)
        firstChild = item;
    else
        prev->nextSibling = item;
    item->previousSibling = prev;
    item->nextSibling = 0;
    lastChild = item;
    item->parentBox = this;
    item->retain_();
    ++childCount;
    return item;
}

Box* Box::getParentBox() const
{
    return parentBox;
}

bool Box::hasChildBoxes() const
{
    return firstChild;
}

Box* Box::getFirstChild() const
{
    return firstChild;
}

Box* Box::getLastChild() const
{
    return lastChild;
}

Box* Box::getPreviousSibling() const
{
    return previousSibling;
}

Box* Box::getNextSibling() const
{
    return nextSibling;
}

void Box::updatePadding()
{
    paddingTop = style->paddingTop.getPx();
    paddingRight = style->paddingRight.getPx();
    paddingBottom = style->paddingBottom.getPx();
    paddingLeft = style->paddingLeft.getPx();
}

void Box::updateBorderWidth()
{
    borderTop = style->borderTopWidth.getPx();
    borderRight = style->borderRightWidth.getPx();
    borderBottom = style->borderBottomWidth.getPx();
    borderLeft = style->borderLeftWidth.getPx();
}

const ContainingBlock* Box::getContainingBlock(ViewCSSImp* view) const
{
    const Box* box = this;
    do {
        const Box* parent = box->getParentBox();
        if (!parent)
            return view->getInitialContainingBlock();
        box = parent;
    } while (box->getBoxType() != BLOCK_LEVEL_BOX);
    return box;
}

// We also calculate offsetH and offsetV here.
void BlockLevelBox::setContainingBlock(ViewCSSImp* view)
{
    assert(isAbsolutelyPositioned());
    float x = 0.0f;
    float y = 0.0f;
    const Box* staticPosition = Box::towardViewPort(x, y);
    assert(staticPosition);
    if (!isFixed()) {
        assert(node);
        for (auto ancestor = node.getParentElement(); ancestor; ancestor = ancestor.getParentElement()) {
            CSSStyleDeclarationImp* style = view->getStyle(ancestor);
            if (!style)
                break;
            switch (style->position.getValue()) {
            case CSSPositionValueImp::Absolute:
            case CSSPositionValueImp::Relative:
            case CSSPositionValueImp::Fixed: {
                // Now we need to find the corresponding box for this ancestor.
                const Box* box = style->box;
                assert(box);
                while (box != staticPosition)
                    staticPosition = staticPosition->towardViewPort(x, y);
                offsetH = -x - box->paddingLeft;
                offsetV = -y - box->paddingTop;
                if (box->getBoxType() == BLOCK_LEVEL_BOX) {
                    absoluteBlock.width = box->getPaddingWidth();
                    absoluteBlock.height = box->getPaddingHeight();
                } else {
                    assert(box->getBoxType() == INLINE_LEVEL_BOX);
                    if (Box* inlineBlock = box->getFirstChild()) {
                        absoluteBlock.width = inlineBlock->getPaddingWidth();
                        absoluteBlock.height = inlineBlock->getPaddingHeight();
                    } else {
                        const Box* p = box->getParentBox();
                        float t = -box->paddingTop;
                        float l = -box->paddingLeft;
                        while (box != p)
                            box = box->towardViewPort(t, l);
                        box = style->lastBox;
                        float b = box->height + box->paddingBottom;
                        float r = box->width + box->paddingRight;
                        while (box != p)
                            box = box->towardViewPort(b, r);
                        absoluteBlock.width = r - l;
                        absoluteBlock.height = t - b;
                    }
                }

                // TODO: overflow
                while (staticPosition)
                    staticPosition = staticPosition->towardViewPort(x, y);
                absoluteBlock.width = view->getInitialContainingBlock()->width - x;
                absoluteBlock.height = view->getInitialContainingBlock()->height - y;
                return;
            }
            default:
                break;
            }
        }
    }
    while (staticPosition)
        staticPosition = staticPosition->towardViewPort(x, y);
    offsetH = -x;
    offsetV = -y;
    absoluteBlock.width = view->getInitialContainingBlock()->width - x;
    absoluteBlock.height = view->getInitialContainingBlock()->height - y;
}

FormattingContext* Box::updateFormattingContext(FormattingContext* context)
{
    if (isFlowRoot())
        return formattingContext;
    // TODO: adjust left and right blanks.
    return context;
}

bool Box::isFlowOf(const Box* flowRoot) const
{
    assert(flowRoot->isFlowRoot());
    for (const Box* box = this; box; box = box->getParentBox()) {
        if (box == flowRoot)
            return true;
    }
    return false;
}

// Calculate left, right, top, bottom for 'static' or 'relative' element.
// TODO: rtl
void Box::resolveOffset(CSSStyleDeclarationImp* style)
{
    assert(style->position.getValue() == CSSPositionValueImp::Relative ||
           style->position.getValue() == CSSPositionValueImp::Static);

    float h = 0.0f;
    if (!style->left.isAuto())
        h = style->left.getPx();
    else if (!style->right.isAuto())
        h = -style->right.getPx();
    offsetH += h;

    float v = 0.0f;
    if (!style->top.isAuto())
        v = style->top.getPx();
    else if (!style->bottom.isAuto())
        v = -style->bottom.getPx();
    offsetV += v;
}

void Box::resolveOffset(ViewCSSImp* view)
{
    if (isAnonymous())
        return;
    resolveOffset(getStyle());
}

bool BlockLevelBox::isFloat() const
{
    return style && style->isFloat();
}

bool BlockLevelBox::isFixed() const
{
    return style && style->position.getValue() == CSSPositionValueImp::Fixed;
}

bool BlockLevelBox::isAbsolutelyPositioned() const
{
    return style && style->isAbsolutelyPositioned();
}

void BlockLevelBox::dump(ViewCSSImp* view, std::string indent)
{
    std::cout << indent << "* block-level box (" << static_cast<void*>(this);
    if (!node)
        std::cout << ") [anonymous]";
    else {
        std::cout << ':' << node.self() << ')';
        std::cout << " [" << node.getNodeName() << ']';
    }
    std::cout << " (" << x << ", " << y << "), (" << getTotalWidth() << ", " << getTotalHeight() << ") " <<
    "m:" << marginTop << '-' << marginRight << '-' << marginBottom << '-' << marginLeft << ' ' <<
    "p:" << paddingTop << '-' <<  paddingRight << '-'<< paddingBottom<< '-' << paddingLeft << ' ' <<
    "b:" << borderTop << '-' <<  borderRight << '-' << borderBottom<< '-' << borderLeft << '\n';
    indent += "    ";
    if (!getFirstChild() && hasInline()) {
        for (auto i = inlines.begin(); i != inlines.end(); ++i) {
            if ((*i).getNodeType() == Node::TEXT_NODE) {
                Text text = interface_cast<Text>(*i);
                std::cout << indent << "* inline-level box: \"" << text.getData() << "\"\n";
            } else if (Box* box = view->getFloatBox(*i))
                box->dump(view, indent);
        }
        return;
    }
    for (Box* child = getFirstChild(); child; child = child->getNextSibling())
        child->dump(view, indent);
}

BlockLevelBox* BlockLevelBox::getAnonymousBox()
{
    BlockLevelBox* anonymousBox;
    if (hasAnonymousBox()) {
        anonymousBox = dynamic_cast<BlockLevelBox*>(firstChild);
        if (anonymousBox)
            return anonymousBox;
    }
    anonymousBox = new(std::nothrow) BlockLevelBox;
    if (anonymousBox) {
        anonymousBox->spliceInline(this);
        if (firstChild)
            insertBefore(anonymousBox, firstChild);
        else
            appendChild(anonymousBox);
    }
    return anonymousBox;
}

void BlockLevelBox::resolveWidth(ViewCSSImp* view, const ContainingBlock* containingBlock, float available)
{
    assert(style);
    resolveBackground(view);
    updatePadding();
    updateBorderWidth();
    resolveMargin(view, containingBlock, available);
}

void BlockLevelBox::resolveBackground(ViewCSSImp* view)
{
    assert(style);
    backgroundColor = style->backgroundColor.getARGB();
    if (!style->backgroundImage.isNone()) {
        view->preload(view->getDocument().getDocumentURI(), style->backgroundImage.getValue());
        backgroundImage = new(std::nothrow) BoxImage(this, view->getDocument().getDocumentURI(), style->backgroundImage.getValue(), style->backgroundRepeat.getValue());
    }
}

void BlockLevelBox::resolveWidth(float w)
{
    resolveNormalWidth(w);
    if (!style->maxWidth.isNone()) {
        float maxWidth = style->maxWidth.getPx();
        if (maxWidth < width)
            resolveNormalWidth(w, maxWidth);
    }
    float minWidth = style->minWidth.getPx();
    if (width < minWidth)
        resolveNormalWidth(w, minWidth);
}

// Calculate width
//
// marginLeft + borderLeftWidth + paddingLeft + width + paddingRight + borderRightWidth + marginRight
// == containingBlock->width (- scrollbar width, if any)
void BlockLevelBox::resolveNormalWidth(float w, float r)
{
    int autoCount = 3;
    unsigned autoMask = Left | Width | Right;
    if (style) {
        if (style->isFloat() || style->isInlineBlock())
            return resolveFloatWidth(w);
        if (!isnan(r)) {
            width = r;
            --autoCount;
            autoMask &= ~Width;
            w -= width;
        } else if (!style->width.isAuto()) {
            width = style->width.getPx();
            --autoCount;
            autoMask &= ~Width;
            w -= width;
        }
        if (!style->marginLeft.isAuto()) {
            marginLeft = style->marginLeft.getPx();
            --autoCount;
            autoMask &= ~Left;
            w -= marginLeft;
        }
        if (!style->marginRight.isAuto()) {  // TODO: assuming LTR
            if (1 < autoCount) {
                marginRight = style->marginRight.getPx();
                --autoCount;
                autoMask &= ~Right;
                w -= marginRight;
            }
        }
    }
    w -= borderLeft + paddingLeft + paddingRight + borderRight;
    switch (autoMask) {
    case Left | Width | Right:
        width = w;
        marginLeft = marginRight = 0.0f;
        break;
    case Left | Width:
        width = w;
        marginLeft = 0.0f;
        break;
    case Width | Right:
        width = w;
        marginRight = 0.0f;
        break;
    case Left | Right:
        marginLeft = marginRight = w / 2.0f;
        break;
    case Left:
        marginLeft = w;
        break;
    case Width:
        width = w;
        break;
    case Right:
        marginRight = w;
        break;
    default:
        break;
    }
}

void BlockLevelBox::resolveFloatWidth(float w, float r)
{
    assert(style);
    marginLeft = style->marginLeft.isAuto() ? 0.0f : style->marginLeft.getPx();
    marginRight = style->marginRight.isAuto() ? 0.0f : style->marginRight.getPx();
    if (!isnan(r))
        width = r;
    else if (!style->width.isAuto())
        width = style->width.getPx();
    else
        width = w - getBlankLeft() - getBlankRight();
}

void BlockLevelBox::resolveMargin(ViewCSSImp* view, const ContainingBlock* containingBlock, float available)
{
    resolveWidth((available != 0.0f) ? available : containingBlock->width);
    if (!style->marginTop.isAuto())
        marginTop = style->marginTop.getPx();
    else
        marginTop = 0;
    if (!style->marginBottom.isAuto())
        marginBottom = style->marginBottom.getPx();
    else
        marginBottom = 0;
    if (!style->height.isAuto())
        height = style->height.getPx();
}

void BlockLevelBox::layOutText(ViewCSSImp* view, Text text, FormattingContext* context)
{
    CSSStyleDeclarationImp* style = 0;
    Element element = getContainingElement(text);
    if (!element)
        return;  // TODO error

    style = view->getStyle(element);
    if (!style)
        return;  // TODO error
    style->resolve(view, this, element);
    std::u16string data = text.getData();
    if (style->processWhiteSpace(data, context->prevChar) == 0)
        return;

    bool psuedoChecked = false;
    CSSStyleDeclarationImp* firstLineStyle = 0;
    CSSStyleDeclarationImp* firstLetterStyle = 0;
    CSSStyleDeclarationImp* activeStyle = style;

    FontTexture* font = view->selectFont(activeStyle);
    float point = view->getPointFromPx(activeStyle->fontSize.getPx());
    size_t position = 0;
    for (;;) {
        if (!context->lineBox) {
            if (style->processLineHeadWhiteSpace(data) == 0)
                return;
            if (!context->addLineBox(view, this))
                return;  // TODO error
            if (!psuedoChecked && getFirstChild() == context->lineBox) {
                psuedoChecked  = true;
                // The current line box is the 1st line of this block box.
                // style to use can be a pseudo element styles from any ancestor elements.
                // Note the :first-line, first-letter pseudo-elements can only be attached to a block container element.
                std::list<CSSStyleDeclarationImp*> firstLineStyles;
                std::list<CSSStyleDeclarationImp*> firstLetterStyles;
                Box* box = this;
                for (;;) {
                    if (CSSStyleDeclarationImp* s = box->getStyle()) {
                        if (CSSStyleDeclarationImp* p = s->getPseudoElementStyle(CSSPseudoElementSelector::FirstLine))
                            firstLineStyles.push_front(p);
                        if (CSSStyleDeclarationImp* p = s->getPseudoElementStyle(CSSPseudoElementSelector::FirstLetter))
                            firstLetterStyles.push_front(p);
                    }
                    Box* parent = box->getParentBox();
                    if (!parent || parent->getFirstChild() != box)
                        break;
                    box = parent;
                }
                if (!firstLineStyles.empty()) {
                    CSSStyleDeclarationImp* parentStyle = style;
                    for (auto i = firstLineStyles.begin(); i != firstLineStyles.end(); ++i) {
                        (*i)->compute(view, parentStyle, 0);
                        parentStyle = *i;
                    }
                    firstLineStyle = firstLineStyles.back();
                    CSSStyleDeclarationImp* p = style->createPseudoElementStyle(CSSPseudoElementSelector::FirstLine);
                    assert(p);  // TODO
                    p->specify(firstLineStyle);
                    firstLineStyle = p;
                }
                if (!firstLetterStyles.empty()) {
                    CSSStyleDeclarationImp* parentStyle = style;
                    for (auto i = firstLetterStyles.begin(); i != firstLetterStyles.end(); ++i) {
                        (*i)->compute(view, parentStyle, 0);
                        parentStyle = *i;
                    }
                    firstLetterStyle = firstLetterStyles.back();
                    CSSStyleDeclarationImp* p = style->createPseudoElementStyle(CSSPseudoElementSelector::FirstLetter);
                    assert(p);  // TODO
                    p->specify(firstLetterStyle);
                    firstLetterStyle = p;
                }
                if (firstLetterStyle) {
                    activeStyle = firstLetterStyle;
                    font = view->selectFont(activeStyle);
                    point = view->getPointFromPx(activeStyle->fontSize.getPx());
                } else if (firstLineStyle) {
                    activeStyle = firstLineStyle;
                    font = view->selectFont(activeStyle);
                    point = view->getPointFromPx(activeStyle->fontSize.getPx());
                }
            }
        }

        InlineLevelBox* inlineLevelBox = new(std::nothrow) InlineLevelBox(text, activeStyle);
        if (!inlineLevelBox)
            return;  // TODO error
        style->addBox(inlineLevelBox);  // activeStyle? maybe not...
        inlineLevelBox->resolveWidth();
        float blankLeft = inlineLevelBox->getBlankLeft();
        if (0 < position)  // TODO: this is a bit awkward...
            inlineLevelBox->marginLeft = inlineLevelBox->paddingLeft = inlineLevelBox->borderLeft = blankLeft = 0;
        float blankRight = inlineLevelBox->getBlankRight();
        context->x += blankLeft;
        context->leftover -= blankLeft + blankRight;

        size_t fitLength = firstLetterStyle ? 1 : data.length();  // TODO: 1 is absolutely wrong...

        // We are still not sure if there's a room for text in context->lineBox.
        // If there's no room due to float box(es), move the linebox down to
        // the closest bottom of float box.
        // And repeat this process until there's no more float box in the context.
        float advanced;
        size_t length;
        bool linefeed;
        linefeed = false;
        size_t next = 1;
        float required = 0.0f;
        do {
            advanced = context->leftover;
            if (data[0] == '\n') {
                linefeed = true;
                length = 1;
                advanced = 0.0f;
                break;
            }
            length = font->fitText(data.c_str(), fitLength, point, context->leftover, &next, &required);
            if (0 < length) {
                advanced -= context->leftover;
                break;
            }
        } while (context->shiftDownLineBox());
        if (length == 0) {
            context->leftover -= required;
            advanced -= context->leftover;
            length = next;
        }

        if (!linefeed) {
            inlineLevelBox->setData(font, point, data.substr(0, length));
            inlineLevelBox->width = advanced;
            if (!firstLetterStyle && length < data.length()) {  // TODO: firstLetterStyle : actually we are not sure if the following characters would fit in the same line box...
                inlineLevelBox->marginRight = inlineLevelBox->paddingRight = inlineLevelBox->borderRight = blankRight = 0;
            }
        }
        inlineLevelBox->height = font->getHeight(point);
        inlineLevelBox->baseline += (activeStyle->lineHeight.getPx() - inlineLevelBox->height) / 2.0f;
        context->x += advanced + blankRight;
        LineBox* lineBox = context->lineBox;
        lineBox->appendChild(inlineLevelBox);
        lineBox->height = std::max(lineBox->height, std::max(activeStyle->lineHeight.getPx(), inlineLevelBox->height));
        lineBox->baseline = std::max(lineBox->baseline, inlineLevelBox->baseline);
        lineBox->width += blankLeft + advanced + blankRight;
        lineBox->underlinePosition = std::max(lineBox->underlinePosition, font->getUnderlinePosition(point));
        lineBox->underlineThickness = std::max(lineBox->underlineThickness, font->getUnderlineThickness(point));
        position += length;
        data.erase(0, length);
        if (data.length() == 0) {  // layout done?
            if (linefeed)
                context->nextLine(this);
            break;
        }

        if (firstLetterStyle) {
            firstLetterStyle = 0;
            if (firstLineStyle) {
                activeStyle = firstLineStyle;
                font = view->selectFont(activeStyle);
                point = view->getPointFromPx(activeStyle->fontSize.getPx());
            } else {
                activeStyle = style;
                font = view->selectFont(activeStyle);
                point = view->getPointFromPx(activeStyle->fontSize.getPx());
            }
        } else {
            context->nextLine(this);
            if (firstLineStyle) {
                firstLineStyle = 0;
                activeStyle = style;
                font = view->selectFont(activeStyle);
                point = view->getPointFromPx(activeStyle->fontSize.getPx());
            }
        }
    }
}

void BlockLevelBox::layOutInlineReplaced(ViewCSSImp* view, Node node, FormattingContext* context)
{
    CSSStyleDeclarationImp* style = 0;
    Element element = 0;
    if (element = getContainingElement(node)) {
        style = view->getStyle(element);
        if (!style)
            return;  // TODO error
        style->resolve(view, this, element);
    } else
        return;  // TODO error

    if (!context->lineBox) {
        if (!context->addLineBox(view, this))
            return;  // TODO error
    }
    InlineLevelBox* inlineLevelBox = new(std::nothrow) InlineLevelBox(node, style);
    if (!inlineLevelBox)
        return;  // TODO error
    style->addBox(inlineLevelBox);

    inlineLevelBox->resolveWidth();
    if (!style->width.isAuto())
        inlineLevelBox->width = style->width.getPx();
    else
        inlineLevelBox->width = 300;  // TODO
    if (!style->height.isAuto())
        inlineLevelBox->height = style->height.getPx();
    else
        inlineLevelBox->height = 24;  // TODO

    context->prevChar = 0;

    std::u16string tag = element.getLocalName();
    if (tag == u"img") {
        html::HTMLImageElement img = interface_cast<html::HTMLImageElement>(element);
        if (BoxImage* backgroundImage = new(std::nothrow) BoxImage(inlineLevelBox, view->getDocument().getDocumentURI(), img)) {
            inlineLevelBox->backgroundImage = backgroundImage;
            if (style->width.isAuto())
                inlineLevelBox->width = backgroundImage->getWidth();
            if (style->height.isAuto())
                inlineLevelBox->height = backgroundImage->getHeight();
        }
    } else if (tag == u"iframe") {
        html::HTMLIFrameElement iframe = interface_cast<html::HTMLIFrameElement>(element);
        inlineLevelBox->width = CSSTokenizer::parseInt(iframe.getWidth().c_str(), iframe.getWidth().size());
        inlineLevelBox->height = CSSTokenizer::parseInt(iframe.getHeight().c_str(), iframe.getHeight().size());
        html::Window contentWindow = iframe.getContentWindow();
        if (WindowImp* imp = dynamic_cast<WindowImp*>(contentWindow.self())) {
            imp->setSize(inlineLevelBox->width, inlineLevelBox->height);
            inlineLevelBox->shadow = imp->getView();
            std::u16string src = iframe.getSrc();
            if (!src.empty() && !imp->getDocument())
                iframe.setSrc(src);
        }
    } else if (!style->isInlineBlock()) {
        // TODO: This line should not be reached but currently it is as absolute boxes are created lazily.
        return;
    } else if (BlockLevelBox* inlineBlock = view->layOutBlockBoxes(element, 0, 0, 0, true)) {
        inlineLevelBox->appendChild(inlineBlock);
        inlineBlock->layOut(view, context);
        inlineLevelBox->width = inlineBlock->getTotalWidth();
        inlineLevelBox->marginLeft = inlineLevelBox->marginRight =
        inlineLevelBox->borderLeft = inlineLevelBox->borderRight =
        inlineLevelBox->paddingLeft = inlineLevelBox->paddingRight = 0.0f;

        inlineLevelBox->height = inlineBlock->getTotalHeight();
        inlineLevelBox->marginTop = inlineLevelBox->marginBottom =
        inlineLevelBox->borderTop = inlineLevelBox->borderBottom =
        inlineLevelBox->paddingTop = inlineLevelBox->paddingBottom = 0.0f;

        inlineLevelBox->baseline = inlineBlock->getBlankTop() + inlineBlock->height;
    } else
        return;  // TODO

    // TODO: calc inlineLevelBox->width and height with intrinsic values.
    if (inlineLevelBox->baseline == 0.0f)
        inlineLevelBox->baseline = inlineLevelBox->getBlankTop() + inlineLevelBox->height;  // TODO

    float blankLeft = inlineLevelBox->getBlankLeft();
    float blankRight = inlineLevelBox->getBlankRight();
    context->x += blankLeft;
    context->leftover -= blankLeft + blankRight;

    // We are still not sure if there's a room for text in context->lineBox.
    // If there's no room due to float box(es), move the linebox down to
    // the closest bottom of float box.
    // And repeat this process until there's no more float box in the context.
    do {
        if (inlineLevelBox->width <= context->leftover) {
            context->leftover -= inlineLevelBox->width;
            break;
        }
    } while (context->shiftDownLineBox());
    // TODO: deal with overflow

    context->x += inlineLevelBox->width + blankRight;
    LineBox* lineBox = context->lineBox;
    lineBox->appendChild(inlineLevelBox);
    lineBox->height = std::max(lineBox->height, inlineLevelBox->height);  // TODO: marginTop, etc.???
    lineBox->baseline = std::max(lineBox->baseline, inlineLevelBox->baseline);
    lineBox->width += blankLeft + inlineLevelBox->width + blankRight;
}

void BlockLevelBox::layOutFloat(ViewCSSImp* view, Node node, BlockLevelBox* floatBox, FormattingContext* context)
{
    assert(floatBox->style);
    if (!context->lineBox) {
        if (!context->addLineBox(view, this))
            return;   // TODO error
    }
    floatBox->layOut(view, context);
    floatBox->remainingHeight = floatBox->getTotalHeight();
    float w = floatBox->getTotalWidth();
    if (context->leftover < w && 0.0f < context->getLeftEdge()) {
        // Process this float box later in the other line box.
        context->floatNodes.push_back(node);
        return;
    }
    context->addFloat(floatBox, w);
}

void BlockLevelBox::layOutAbsolute(ViewCSSImp* view, Node node, BlockLevelBox* absBox, FormattingContext* context)
{
    // Just insert this absolute box into a line box now.
    // Absolute boxes will be processed later in ViewCSSImp::layOut().
    if (!context->lineBox) {
        if (!context->addLineBox(view, this))
            return;  // TODO error
    }
    context->lineBox->appendChild(absBox);
}

// Generate line boxes
void BlockLevelBox::layOutInline(ViewCSSImp* view, FormattingContext* context)
{
    assert(!hasChildBoxes());
    for (auto i = inlines.begin(); i != inlines.end(); ++i) {
        if (BlockLevelBox* box = view->getFloatBox(*i)) {
            if (box->isFloat())
                layOutFloat(view, *i, box, context);
            else if (box->isAbsolutelyPositioned())
                layOutAbsolute(view, *i, box, context);
        } else if ((*i).getNodeType() == Node::TEXT_NODE) {
            Text text = interface_cast<Text>(*i);
            layOutText(view, text, context);
        } else {
            // At this point, *i should be a replaced element or an inline block element.
            // TODO: it could be of other types as we develop...
            layOutInlineReplaced(view, *i, context);
        }
    }
    if (context->lineBox)
        context->nextLine(this);
}

// TODO for a more complete implementation, see,
//      http://groups.google.com/group/netscape.public.mozilla.layout/msg/0455a21b048ffac3?pli=1

void BlockLevelBox::shrinkToFit()
{
    fit(shrinkTo());
}

// returns the minimum total width
float Box::shrinkTo()
{
    return getTotalWidth();
}

float BlockLevelBox::shrinkTo()
{
    int autoCount = 3;
    float min = 0.0f;
    if (style && !style->width.isAuto()) {
        --autoCount;
        min = style->width.getPx();
    } else {
        for (Box* child = getFirstChild(); child; child = child->getNextSibling())
            min = std::max(min, child->shrinkTo());
    }
    min += borderLeft + paddingLeft + paddingRight + borderRight;
    if (style) {
        if (!style->marginLeft.isAuto()) {
            --autoCount;
            min += style->marginLeft.getPx();
        }
        if (!style->marginRight.isAuto()) {
            --autoCount;
            if (0 < autoCount)
                min += style->marginRight.getPx();
        }
    }
    return min;
}

void BlockLevelBox::fit(float w)
{
    if (getTotalWidth() == w)
        return;
    resolveWidth(w);
    if (style && !style->width.isAuto())
        return;
    for (Box* child = getFirstChild(); child; child = child->getNextSibling())
        child->fit(width);
}

FormattingContext* BlockLevelBox::collapseMargins(FormattingContext* context)
{
    if (Box* parent = getParentBox()) {  // TODO: root exception
        if (parent->getFirstChild() == this &&
            parent->borderTop == 0 && parent->paddingTop == 0 /* && TODO: check clearance */) {
            marginTop = std::max(marginTop, parent->marginTop);  // TODO: negative case
            parent->marginTop = 0.0f;
        } else if (Box* prev = getPreviousSibling()) {
            marginTop = std::max(prev->marginBottom, marginTop);  // TODO: negative case
            prev->marginBottom = 0.0f;
        }
    }
    context = updateFormattingContext(context);
    assert(context);
    context->updateRemainingHeight(getBlankTop());
    marginTop += context->clear(style->clear.getValue());
    return context;
}

void BlockLevelBox::collapseMarginBottom()
{
    // TODO: root exception
    if (height == 0 && borderBottom == 0 && paddingBottom == 0 /* && TODO: check clearance */) {
        if (Box* child = getLastChild()) {
            marginBottom = std::max(marginBottom, child->marginBottom);  // TODO: negative case
            child->marginBottom = 0;
        }
    }
}

void BlockLevelBox::layOut(ViewCSSImp* view, FormattingContext* context)
{
    const ContainingBlock* containingBlock = getContainingBlock(view);

    Element element = 0;
    if (!isAnonymous())
        element = getContainingElement(node);
    else if (const Box* box = dynamic_cast<const Box*>(containingBlock))
        element = getContainingElement(box->node);
    if (!element)
        return;  // TODO error

    style = view->getStyle(element);
    if (!style)
        return;  // TODO error

    if (!isAnonymous()) {
        style->resolve(view, containingBlock, element);
        resolveWidth(view, containingBlock,
                     (style->isInlineBlock() || style->isFloat()) ? context->leftover : 0.0f);
    } else {
        // The properties of anonymous boxes are inherited from the enclosing non-anonymous box.
        // Theoretically, we are supposed to create a new style for this anonymous box, but
        // of course we don't want to do so.
        backgroundColor = 0x00000000;
        paddingTop = paddingRight = paddingBottom = paddingLeft = 0.0f;
        borderTop = borderRight = borderBottom = borderLeft = 0.0f;
        marginTop = marginRight = marginLeft = marginBottom = 0.0f;
        width = containingBlock->width;
        height = 0.0f;
        stackingContext = style->getStackingContext();
    }

    textAlign = style->textAlign.getValue();
    context = collapseMargins(context);

    if (hasInline())
        layOutInline(view, context);
    for (Box* child = getFirstChild(); child; child = child->getNextSibling()) {
        child->layOut(view, context);
        if (child->isFlowRoot())
            context->updateRemainingHeight(child->getTotalHeight());
        // TODO: overflow
        width = std::max(width, child->getTotalWidth());
    }

    if ((style->width.isAuto() || style->marginLeft.isAuto() || style->marginRight.isAuto()) &&
        (style->isInlineBlock() || style->isFloat() || style->display == CSSDisplayValueImp::TableCell))
        shrinkToFit();

    collapseMarginBottom();

    if (isFlowRoot()) {
        float h = context->clear(3);
        if (Box* last = getLastChild())
            last->marginBottom += h;
        // Layout remaining float boxes in context
        while (!context->floatNodes.empty()) {
            context->addLineBox(view, this);
            context->nextLine(this, !context->floatNodes.empty());
        }
    }

    if (style->height.isAuto() || isAnonymous()) {
        height = 0.0f;
{'fraction_non_alphanumeric': 0.13007623409374186, 'fraction_numerical': 0.006029160265514942, 'mean_word_length': 2.2949238336278115, 'pattern_counts': {'":': 0, '<': 265, '<?xml version=': 0, '>': 744, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6462447', 'n_tokens_mistral': 19968, 'n_tokens_neox': 19341, 'n_words': 4426}