/*
 * Copyright (C) 2019 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"

#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
#include "AXIsolatedTree.h"

#include "AXIsolatedObject.h"
#include "AXLogger.h"
#include "FrameView.h"
#include "Page.h"
#include <wtf/NeverDestroyed.h>
#include <wtf/SetForScope.h>

namespace WebCore {

Lock AXIsolatedTree::s_cacheLock;

static unsigned newTreeID()
{
    static unsigned s_currentTreeID = 0;
    return ++s_currentTreeID;
}

HashMap<PageIdentifier, Ref<AXIsolatedTree>>& AXIsolatedTree::treePageCache()
{
    static NeverDestroyed<HashMap<PageIdentifier, Ref<AXIsolatedTree>>> map;
    return map;
}

HashMap<AXIsolatedTreeID, Ref<AXIsolatedTree>>& AXIsolatedTree::treeIDCache()
{
    static NeverDestroyed<HashMap<AXIsolatedTreeID, Ref<AXIsolatedTree>>> map;
    return map;
}

AXIsolatedTree::AXIsolatedTree(AXObjectCache* axObjectCache)
    : m_treeID(newTreeID())
    , m_axObjectCache(axObjectCache)
    , m_usedOnAXThread(axObjectCache->usedOnAXThread())
{
    AXTRACE("AXIsolatedTree::AXIsolatedTree");
    ASSERT(isMainThread());
}

AXIsolatedTree::~AXIsolatedTree()
{
    AXTRACE("AXIsolatedTree::~AXIsolatedTree");
}

void AXIsolatedTree::clear()
{
    AXTRACE("AXIsolatedTree::clear");
    ASSERT(isMainThread());
    m_axObjectCache = nullptr;
    m_nodeMap.clear();

    Locker locker { m_changeLogLock };
    m_pendingSubtreeRemovals.append(m_rootNode->objectID());
    m_rootNode = nullptr;
}

RefPtr<AXIsolatedTree> AXIsolatedTree::treeForID(AXIsolatedTreeID treeID)
{
    AXTRACE("AXIsolatedTree::treeForID");
    Locker locker { s_cacheLock };
    return treeIDCache().get(treeID);
}

Ref<AXIsolatedTree> AXIsolatedTree::create(AXObjectCache* axObjectCache)
{
    AXTRACE("AXIsolatedTree::create");
    ASSERT(isMainThread());
    ASSERT(axObjectCache && axObjectCache->pageID());

    auto tree = adoptRef(*new AXIsolatedTree(axObjectCache));

    auto& document = axObjectCache->document();
    if (!document.view()->layoutContext().isInRenderTreeLayout() && !document.inRenderTreeUpdate() && !document.inStyleRecalc())
        document.updateLayoutIgnorePendingStylesheets();

    // Generate the nodes of the tree and set its root and focused objects.
    // For this, we need the root and focused objects of the AXObject tree.
    auto* axRoot = axObjectCache->getOrCreate(axObjectCache->document().view());
    if (axRoot)
        tree->generateSubtree(*axRoot, nullptr, true);
    auto* axFocus = axObjectCache->focusedObjectForPage(axObjectCache->document().page());
    if (axFocus)
        tree->setFocusedNodeID(axFocus->objectID());

    // Now that the tree is ready to take client requests, add it to the tree
    // maps so that it can be found.
    auto pageID = axObjectCache->pageID();
    Locker locker { s_cacheLock };
    ASSERT(!treePageCache().contains(*pageID));
    treePageCache().set(*pageID, tree.copyRef());
    treeIDCache().set(tree->treeID(), tree.copyRef());

    return tree;
}

void AXIsolatedTree::removeTreeForPageID(PageIdentifier pageID)
{
    AXTRACE("AXIsolatedTree::removeTreeForPageID");
    ASSERT(isMainThread());
    Locker locker { s_cacheLock };

    if (auto tree = treePageCache().take(pageID)) {
        tree->clear();
        treeIDCache().remove(tree->treeID());
    }
}

RefPtr<AXIsolatedTree> AXIsolatedTree::treeForPageID(PageIdentifier pageID)
{
    Locker locker { s_cacheLock };

    if (auto tree = treePageCache().get(pageID))
        return RefPtr { tree };

    return nullptr;
}

RefPtr<AXIsolatedObject> AXIsolatedTree::nodeForID(AXID axID) const
{
    // In isolated tree mode 2, only access m_readerThreadNodeMap on the AX thread.
    ASSERT(m_usedOnAXThread ? !isMainThread() : isMainThread());
    if (m_usedOnAXThread && isMainThread())
        return nullptr;

    return axID.isValid() ? m_readerThreadNodeMap.get(axID) : nullptr;
}

Vector<RefPtr<AXCoreObject>> AXIsolatedTree::objectsForIDs(const Vector<AXID>& axIDs) const
{
    AXTRACE("AXIsolatedTree::objectsForIDs");
    Vector<RefPtr<AXCoreObject>> result;
    result.reserveCapacity(axIDs.size());

    for (const auto& axID : axIDs) {
        if (auto object = nodeForID(axID))
            result.uncheckedAppend(object);
    }

    return result;
}

Vector<AXID> AXIsolatedTree::idsForObjects(const Vector<RefPtr<AXCoreObject>>& objects) const
{
    return objects.map([] (const RefPtr<AXCoreObject>& object) -> AXID {
        return object ? object->objectID() : AXID();
    });
}

void AXIsolatedTree::updateChildrenIDs(AXID axID, Vector<AXID>&& childrenIDs)
{
    ASSERT(isMainThread());
    ASSERT(m_changeLogLock.isLocked());

    if (axID.isValid()) {
        m_nodeMap.set(axID, childrenIDs);
        m_pendingChildrenUpdates.append(std::make_pair(axID, WTFMove(childrenIDs)));
    }
}

void AXIsolatedTree::generateSubtree(AXCoreObject& axObject, AXCoreObject* axParent, bool attachWrapper)
{
    AXTRACE("AXIsolatedTree::generateSubtree");
    ASSERT(isMainThread());

    if (!axObject.objectID().isValid())
        return;

    auto object = createSubtree(axObject, axParent ? axParent->objectID() : AXID(), attachWrapper);
    Locker locker { m_changeLogLock };
    if (!axParent)
        setRootNode(object.ptr());
    else if (axParent->objectID().isValid()) // Need to check for the objectID of axParent again because it may have been detached while traversing the tree.
        updateChildrenIDs(axParent->objectID(), axParent->childrenIDs());
}

AXIsolatedTree::NodeChange AXIsolatedTree::nodeChangeForObject(AXCoreObject& axObject, AXID parentID, bool attachWrapper)
{
    ASSERT(isMainThread());

    auto object = AXIsolatedObject::create(axObject, this, parentID);
    NodeChange nodeChange { object, nullptr };

    if (!object->objectID().isValid()) {
        // Either the axObject has an invalid ID or something else went terribly wrong. Don't bother doing anything else.
        ASSERT_NOT_REACHED();
        return nodeChange;
    }

    ASSERT(axObject.wrapper());
    if (attachWrapper)
        object->attachPlatformWrapper(axObject.wrapper());
    else {
        // Set the wrapper in the NodeChange so that it is set on the AX thread.
        nodeChange.wrapper = axObject.wrapper();
    }

    return nodeChange;
}

void AXIsolatedTree::queueChanges(const NodeChange& nodeChange, Vector<AXID>&& childrenIDs)
{
    ASSERT(isMainThread());

    Locker locker { m_changeLogLock };
    m_pendingAppends.append(nodeChange);
    updateChildrenIDs(nodeChange.isolatedObject->objectID(), WTFMove(childrenIDs));
}

Ref<AXIsolatedObject> AXIsolatedTree::createSubtree(AXCoreObject& axObject, AXID parentID, bool attachWrapper)
{
    AXTRACE("AXIsolatedTree::createSubtree");
    ASSERT(isMainThread());

    if (!m_creatingSubtree)
        axObjectCache()->processDeferredChildrenChangedList();
    SetForScope<bool> creatingSubtree(m_creatingSubtree, true);

    auto nodeChange = nodeChangeForObject(axObject, parentID, attachWrapper);

    auto axChildren = axObject.children();
    Vector<AXID> childrenIDs;
    childrenIDs.reserveCapacity(axChildren.size());
    for (const auto& axChild : axChildren) {
        auto child = createSubtree(*axChild, axObject.objectID(), attachWrapper);
        childrenIDs.uncheckedAppend(child->objectID());
    }

    queueChanges(nodeChange, WTFMove(childrenIDs));

    return nodeChange.isolatedObject;
}

void AXIsolatedTree::updateNode(AXCoreObject& axObject)
{
    AXTRACE("AXIsolatedTree::updateNode");
    AXLOG(&axObject);
    ASSERT(isMainThread());

    AXID axID = axObject.objectID();
    auto* axParent = axObject.parentObject();
    AXID parentID = axParent ? axParent->objectID() : AXID();

    auto newObject = AXIsolatedObject::create(axObject, this, parentID);
    newObject->m_childrenIDs = axObject.childrenIDs();

    Locker locker { m_changeLogLock };
    // Remove the old object and set the new one to be updated on the AX thread.
    m_pendingNodeRemovals.append(axID);
    m_pendingAppends.append({ newObject, axObject.wrapper() });
}

void AXIsolatedTree::updateNodeProperty(const AXCoreObject& axObject, AXPropertyName property)
{
    AXTRACE("AXIsolatedTree::updateNodeProperty");
    ASSERT(isMainThread());

    AXPropertyMap propertyMap;
    switch (property) {
    case AXPropertyName::CanSetFocusAttribute:
        propertyMap.set(AXPropertyName::CanSetFocusAttribute, axObject.canSetFocusAttribute());
        break;
    case AXPropertyName::IsChecked:
        propertyMap.set(AXPropertyName::IsChecked, axObject.isChecked());
        break;
    case AXPropertyName::IsEnabled:
        propertyMap.set(AXPropertyName::IsEnabled, axObject.isEnabled());
        break;
    case AXPropertyName::SortDirection:
        propertyMap.set(AXPropertyName::SortDirection, static_cast<int>(axObject.sortDirection()));
        break;
    case AXPropertyName::IdentifierAttribute:
        propertyMap.set(AXPropertyName::IdentifierAttribute, axObject.identifierAttribute().isolatedCopy());
        break;
    default:
        return;
    }

    Locker locker { m_changeLogLock };
    m_pendingPropertyChanges.append({ axObject.objectID(), propertyMap });
}

void AXIsolatedTree::updateSubtree(AXCoreObject& axObject)
{
    AXTRACE("AXIsolatedTree::updateSubtree");
    AXLOG(&axObject);
    ASSERT(isMainThread());

    removeSubtree(axObject.objectID());
    generateSubtree(axObject, axObject.parentObject(), false);
}

void AXIsolatedTree::updateChildren(AXCoreObject& axObject)
{
    AXTRACE("AXIsolatedTree::updateChildren");
    AXLOG("For AXObject:");
    AXLOG(&axObject);
    ASSERT(isMainThread());

    if (m_nodeMap.isEmpty()) {
        ASSERT_NOT_REACHED();
        return;
    }

    if (!axObject.document() || !axObject.document()->hasLivingRenderTree())
        return;

    // updateChildren may be called as the result of a children changed
    // notification for an axObject that has no associated isolated object.
    // An example of this is when an empty element such as a <canvas> or <div>
    // is added a new child. So find the closest ancestor of axObject that has
    // an associated isolated object and update its children.
    auto iterator = m_nodeMap.end();
    auto* axAncestor = Accessibility::findAncestor(axObject, true, [&iterator, this] (auto& ancestor) {
        auto it = m_nodeMap.find(ancestor.objectID());
        if (it != m_nodeMap.end()) {
            iterator = it;
            return true;
        }

        // ancestor has no node in the isolated tree, thus add it.
        auto* axParent = ancestor.parentObject();
        AXID axParentID = axParent ? axParent->objectID() : AXID();
        auto nodeChange = nodeChangeForObject(ancestor, axParentID, true);
        queueChanges(nodeChange, ancestor.childrenIDs());

        return false;
    });
    if (!axAncestor || !axAncestor->objectID().isValid() || iterator == m_nodeMap.end()) {
        // This update triggered before the isolated tree has been repopulated.
        // Return here since there is nothing to update.
        return;
    }

    // iterator is pointing to the m_nodeMap entry corresponding to axAncestor->objectID().
    ASSERT(iterator->key == axAncestor->objectID());
    auto removals = iterator->value;

    const auto& axChildren = axAncestor->children();
    auto axChildrenIDs = axAncestor->childrenIDs(false);

    bool updatedChild = false; // Set to true if at least one child's subtree is updated.
    for (size_t i = 0; i < axChildren.size() && i < axChildrenIDs.size(); ++i) {
        ASSERT(axChildren[i]->objectID() == axChildrenIDs[i]);
        ASSERT(axChildrenIDs[i].isValid());
        size_t index = removals.find(axChildrenIDs[i]);
        if (index != notFound)
            removals.remove(index);
        else {
            // This is a new child, add it to the tree.
            AXLOG("Adding a new child for:");
            AXLOG(axChildren[i]);
            generateSubtree(*axChildren[i], axAncestor, true);
            updatedChild = true;
        }
    }

    // What is left in removals are the IDs that are no longer children of
    // axObject. Thus, remove them from the tree.
    for (const AXID& childID : removals)
        removeSubtree(childID);

    if (updatedChild || removals.size()) {
        // Make the children IDs of the isolated object to be the same as the AXObject's.
        Locker locker { m_changeLogLock };
        updateChildrenIDs(axAncestor->objectID(), WTFMove(axChildrenIDs));
    }
}

RefPtr<AXIsolatedObject> AXIsolatedTree::focusedNode()
{
    AXTRACE("AXIsolatedTree::focusedNode");
    // Apply pending changes in case focus has changed and hasn't been updated.
    applyPendingChanges();
    Locker locker { m_changeLogLock };
    AXLOG(makeString("focusedNodeID ", m_focusedNodeID.loggingString()));
    AXLOG("focused node:");
    AXLOG(nodeForID(m_focusedNodeID));
    return nodeForID(m_focusedNodeID);
}

RefPtr<AXIsolatedObject> AXIsolatedTree::rootNode()
{
    AXTRACE("AXIsolatedTree::rootNode");
    Locker locker { m_changeLogLock };
    return m_rootNode;
}

void AXIsolatedTree::setRootNode(AXIsolatedObject* root)
{
    AXTRACE("AXIsolatedTree::setRootNode");
    ASSERT(isMainThread());
    ASSERT(m_changeLogLock.isLocked());
    ASSERT(!m_rootNode);
    ASSERT(root);

    m_rootNode = root;
}

void AXIsolatedTree::setFocusedNodeID(AXID axID)
{
    AXTRACE("AXIsolatedTree::setFocusedNodeID");
    AXLOG(makeString("axID ", axID.loggingString()));
    ASSERT(isMainThread());

    AXPropertyMap propertyMap;
    propertyMap.set(AXPropertyName::IsFocused, true);

    Locker locker { m_changeLogLock };
    m_pendingFocusedNodeID = axID;
    m_pendingPropertyChanges.append({ axID, propertyMap });
}

void AXIsolatedTree::removeNode(AXID axID)
{
    AXTRACE("AXIsolatedTree::removeNode");
    AXLOG(makeString("AXID ", axID.loggingString()));
    ASSERT(isMainThread());

    m_nodeMap.remove(axID);
    Locker locker { m_changeLogLock };
    m_pendingNodeRemovals.append(axID);
}

void AXIsolatedTree::removeSubtree(AXID axID)
{
    AXTRACE("AXIsolatedTree::removeSubtree");
    AXLOG(makeString("Removing subtree for axID ", axID.loggingString()));
    ASSERT(isMainThread());

    Vector<AXID> removals = { axID };
    while (removals.size()) {
        AXID axID = removals.takeLast();
        if (!axID.isValid())
            continue;

        auto it = m_nodeMap.find(axID);
        if (it != m_nodeMap.end()) {
            removals.appendVector(it->value);
            m_nodeMap.remove(axID);
        }
    }

    Locker locker { m_changeLogLock };
    m_pendingSubtreeRemovals.append(axID);
}

void AXIsolatedTree::applyPendingChanges()
{
    AXTRACE("AXIsolatedTree::applyPendingChanges");

    // In isolated tree mode 2, only apply pending changes on the AX thread.
    ASSERT(m_usedOnAXThread ? !isMainThread() : isMainThread());
    if (m_usedOnAXThread && isMainThread())
        return;

    Locker locker { m_changeLogLock };

    if (m_pendingFocusedNodeID != m_focusedNodeID) {
        AXLOG(makeString("focusedNodeID ", m_focusedNodeID.loggingString(), " pendingFocusedNodeID ", m_pendingFocusedNodeID.loggingString()));

        if (m_focusedNodeID.isValid()) {
            // Set the old focused object's IsFocused property to false.
            AXPropertyMap propertyMap;
            propertyMap.set(AXPropertyName::IsFocused, false);
            m_pendingPropertyChanges.append({ m_focusedNodeID, propertyMap });
        }
        m_focusedNodeID = m_pendingFocusedNodeID;
    }

    while (m_pendingNodeRemovals.size()) {
        auto axID = m_pendingNodeRemovals.takeLast();
        AXLOG(makeString("removing axID ", axID.loggingString()));
        if (auto object = nodeForID(axID)) {
            object->detach(AccessibilityDetachmentType::ElementDestroyed);
            m_readerThreadNodeMap.remove(axID);
        }
    }

    while (m_pendingSubtreeRemovals.size()) {
        auto axID = m_pendingSubtreeRemovals.takeLast();
        AXLOG(makeString("removing subtree axID ", axID.loggingString()));
        if (auto object = nodeForID(axID)) {
            object->detach(AccessibilityDetachmentType::ElementDestroyed);
            m_pendingSubtreeRemovals.appendVector(object->m_childrenIDs);
            m_readerThreadNodeMap.remove(axID);
        }
    }

    for (const auto& item : m_pendingAppends) {
        AXID axID = item.isolatedObject->objectID();
        AXLOG(makeString("appending axID ", axID.loggingString()));
        if (!axID.isValid())
            continue;

        auto& wrapper = item.wrapper ? item.wrapper : item.isolatedObject->wrapper();
        if (!wrapper)
            continue;

        if (auto object = m_readerThreadNodeMap.get(axID)) {
            if (object != &item.isolatedObject.get()
                && object->wrapper() == wrapper.get()) {
                // The new IsolatedObject is a replacement for an existing object
                // as the result of an update. Thus detach the wrapper from the
                // existing object and attach it to the new one.
                object->detachWrapper(AccessibilityDetachmentType::ElementChanged);
                item.isolatedObject->attachPlatformWrapper(wrapper.get());
            }
            m_readerThreadNodeMap.remove(axID);
        }

        if (!item.isolatedObject->wrapper()) {
            // The new object hasn't been attached a wrapper yet, so attach it.
            item.isolatedObject->attachPlatformWrapper(wrapper.get());
        }

        auto addResult = m_readerThreadNodeMap.add(axID, item.isolatedObject.get());
        // The newly added object must have a wrapper.
        ASSERT_UNUSED(addResult, addResult.iterator->value->wrapper());
        // The reference count of the just added IsolatedObject must be 2
        // because it is referenced by m_readerThreadNodeMap and m_pendingAppends.
        // When m_pendingAppends is cleared, the object will be held only by m_readerThreadNodeMap. The exception is the root node whose reference count is 3.
        ASSERT_WITH_MESSAGE(
            addResult.iterator->value->refCount() == 2 || (addResult.iterator->value.ptr() == m_rootNode.get() && m_rootNode->refCount() == 3),
            "unexpected ref count after adding object to m_readerThreadNodeMap: %d", addResult.iterator->value->refCount()
        );
    }
    m_pendingAppends.clear();

    for (auto& update : m_pendingChildrenUpdates) {
        AXLOG(makeString("updating children for axID ", update.first.loggingString()));
        if (auto object = nodeForID(update.first))
            object->m_childrenIDs = WTFMove(update.second);
    }
    m_pendingChildrenUpdates.clear();

    for (auto& change : m_pendingPropertyChanges) {
        if (auto object = nodeForID(change.axID)) {
            for (auto& property : change.properties)
                object->setProperty(property.key, WTFMove(property.value));
        }
    }
    m_pendingPropertyChanges.clear();
}

} // namespace WebCore

#endif // ENABLE(ACCESSIBILITY_ISOLATED_TREE)