/**
 * @file llinventorymodel.cpp
 * @brief Implementation of the inventory model used to track agent inventory.
 *
 * $LicenseInfo:firstyear=2002&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2014, Linden Research, Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */

#include "llviewerprecompiledheaders.h"

#include <typeinfo>
#include <random>

#include "llinventorymodel.h"

#include "llaisapi.h"
#include "llagent.h"
#include "llagentwearables.h"
#include "llappearancemgr.h"
#include "llavatarnamecache.h"
#include "llclipboard.h"
#include "lldispatcher.h"
#include "llinventorypanel.h"
#include "llinventorybridge.h"
#include "llinventoryfunctions.h"
#include "llinventorymodelbackgroundfetch.h"
#include "llinventoryobserver.h"
#include "llinventorypanel.h"
#include "llfloaterpreviewtrash.h"
#include "llnotificationsutil.h"
#include "llmarketplacefunctions.h"
#include "llwindow.h"
#include "llviewercontrol.h"
#include "llviewernetwork.h"
#include "llpreview.h"
#include "llviewergenericmessage.h"
#include "llviewermessage.h"
#include "llviewerfoldertype.h"
#include "llviewerwindow.h"
#include "llappviewer.h"
#include "llviewerregion.h"
#include "llcallbacklist.h"
#include "llvoavatarself.h"
#include "llgesturemgr.h"
#include "llsdserialize.h"
#include "llsdutil.h"
#include "bufferarray.h"
#include "bufferstream.h"
#include "llcorehttputil.h"
#include "hbxxh.h"
#include "llstartup.h"

//#define DIFF_INVENTORY_FILES
#ifdef DIFF_INVENTORY_FILES
#include "process.h"
#endif

#include <algorithm>
#include <boost/algorithm/string/join.hpp>

// Increment this if the inventory contents change in a non-backwards-compatible way.
// For viewer 2, the addition of link items makes a pre-viewer-2 cache incorrect.
const S32 LLInventoryModel::sCurrentInvCacheVersion = 3;
BOOL LLInventoryModel::sFirstTimeInViewer2 = TRUE;

S32 LLInventoryModel::sPendingSystemFolders = 0;

///----------------------------------------------------------------------------
/// Local function declarations, constants, enums, and typedefs
///----------------------------------------------------------------------------

//BOOL decompress_file(const char* src_filename, const char* dst_filename);
static const char PRODUCTION_CACHE_FORMAT_STRING[] = "%s.inv.llsd";
static const char GRID_CACHE_FORMAT_STRING[] = "%s.%s.inv.llsd";
static const char * const LOG_INV("Inventory");

struct InventoryIDPtrLess
{
    bool operator()(const LLViewerInventoryCategory* i1, const LLViewerInventoryCategory* i2) const
    {
        return (i1->getUUID() < i2->getUUID());
    }
};

class LLCanCache : public LLInventoryCollectFunctor
{
public:
    LLCanCache(LLInventoryModel* model) : mModel(model) {}
    virtual ~LLCanCache() {}
    virtual bool operator()(LLInventoryCategory* cat, LLInventoryItem* item);
protected:
    LLInventoryModel* mModel;
    std::set<LLUUID> mCachedCatIDs;
};

bool LLCanCache::operator()(LLInventoryCategory* cat, LLInventoryItem* item)
{
    bool rv = false;
    if(item)
    {
        if(mCachedCatIDs.find(item->getParentUUID()) != mCachedCatIDs.end())
        {
            rv = true;
        }
    }
    else if(cat)
    {
        // HACK: downcast
        LLViewerInventoryCategory* c = (LLViewerInventoryCategory*)cat;
        if(c->getVersion() != LLViewerInventoryCategory::VERSION_UNKNOWN)
        {
            S32 descendents_server = c->getDescendentCount();
            S32 descendents_actual = c->getViewerDescendentCount();
            if(descendents_server == descendents_actual)
            {
                mCachedCatIDs.insert(c->getUUID());
                rv = true;
            }
        }
    }
    return rv;
}

struct InventoryCallbackInfo
{
    InventoryCallbackInfo(U32 callback, const LLUUID& inv_id) :
        mCallback(callback), mInvID(inv_id) {}
    U32 mCallback;
    LLUUID mInvID;
};

///----------------------------------------------------------------------------
/// Class LLDispatchClassifiedClickThrough
///----------------------------------------------------------------------------

class LLDispatchBulkUpdateInventory : public LLDispatchHandler
{
public:
    virtual bool operator()(
        const LLDispatcher* dispatcher,
        const std::string& key,
        const LLUUID& invoice,
        const sparam_t& strings)
    {
        LLSD message;

        // Expect single string parameter in the form of a notation serialized LLSD.
        sparam_t::const_iterator it = strings.begin();
        if (it != strings.end()) {
            const std::string& llsdRaw = *it++;
            std::istringstream llsdData(llsdRaw);
            if (!LLSDSerialize::deserialize(message, llsdData, llsdRaw.length()))
            {
                LL_WARNS() << "LLDispatchBulkUpdateInventory: Attempted to read parameter data into LLSD but failed:" << llsdRaw << LL_ENDL;
            }
        }

        LLInventoryModel::update_map_t update;
        LLInventoryModel::cat_array_t folders;
        LLInventoryModel::item_array_t items;
        std::list<InventoryCallbackInfo> cblist;
        uuid_vec_t wearable_ids;

        LLSD item_data = message["item_data"];
        if (item_data.isArray())
        {
            for (LLSD::array_iterator itd = item_data.beginArray(); itd != item_data.endArray(); ++itd)
            {
                const LLSD &item(*itd);

                // Agent id probably should be in the root of the message
                LLUUID agent_id = item["agent_id"].asUUID();
                if (agent_id != gAgent.getID())
                {
                    LL_WARNS() << "Got a BulkUpdateInventory for the wrong agent." << LL_ENDL;
                    return false;
                }

                LLPointer<LLViewerInventoryItem> titem = new LLViewerInventoryItem;
                titem->unpackMessage(item);
                LL_DEBUGS("Inventory") << "unpacked item '" << titem->getName() << "' in "
                    << titem->getParentUUID() << LL_ENDL;
                // callback id might be no longer supported
                U32 callback_id = item["callback_id"].asInteger();

                if (titem->getUUID().notNull())
                {
                    items.push_back(titem);
                    cblist.push_back(InventoryCallbackInfo(callback_id, titem->getUUID()));
                    if (titem->getInventoryType() == LLInventoryType::IT_WEARABLE)
                    {
                        wearable_ids.push_back(titem->getUUID());
                    }

                    // examine update for changes.
                    LLViewerInventoryItem* itemp = gInventory.getItem(titem->getUUID());
                    if (itemp)
                    {
                        if (titem->getParentUUID() == itemp->getParentUUID())
                        {
                            update[titem->getParentUUID()];
                        }
                        else
                        {
                            ++update[titem->getParentUUID()];
                            --update[itemp->getParentUUID()];
                        }
                    }
                    else
                    {
                        LLViewerInventoryCategory* folderp = gInventory.getCategory(titem->getParentUUID());
                        if (folderp)
                        {
                            ++update[titem->getParentUUID()];
                        }
                    }
                }
                else
                {
                    cblist.push_back(InventoryCallbackInfo(callback_id, LLUUID::null));
                }
            }
        }

        LLSD folder_data = message["folder_data"];
        if (folder_data.isArray())
        {
            for (LLSD::array_iterator itd = folder_data.beginArray(); itd != folder_data.endArray(); ++itd)
            {
                const LLSD &folder(*itd);

                LLPointer<LLViewerInventoryCategory> tfolder = new LLViewerInventoryCategory(gAgent.getID());
                tfolder->unpackMessage(folder);

                LL_DEBUGS("Inventory") << "unpacked folder '" << tfolder->getName() << "' ("
                        << tfolder->getUUID() << ") in " << tfolder->getParentUUID()
                        << LL_ENDL;

                // If the folder is a listing or a version folder, all we need to do is update the SLM data
                int depth_folder = depth_nesting_in_marketplace(tfolder->getUUID());
                if ((depth_folder == 1) || (depth_folder == 2))
                {
                    // Trigger an SLM listing update
                    LLUUID listing_uuid = (depth_folder == 1 ? tfolder->getUUID() : tfolder->getParentUUID());
                    S32 listing_id = LLMarketplaceData::instance().getListingID(listing_uuid);
                    LLMarketplaceData::instance().getListing(listing_id);
                    // In that case, there is no item to update so no callback -> we skip the rest of the update
                }
                else if (tfolder->getUUID().notNull())
                {
                    folders.push_back(tfolder);
                    LLViewerInventoryCategory* folderp = gInventory.getCategory(tfolder->getUUID());
                    if (folderp)
                    {
                        if (tfolder->getParentUUID() == folderp->getParentUUID())
                        {
                            update[tfolder->getParentUUID()];
                        }
                        else
                        {
                            ++update[tfolder->getParentUUID()];
                            --update[folderp->getParentUUID()];
                        }
                    }
                    else
                    {
                        // we could not find the folder, so it is probably
                        // new. However, we only want to attempt accounting
                        // for the parent if we can find the parent.
                        folderp = gInventory.getCategory(tfolder->getParentUUID());
                        if (folderp)
                        {
                            ++update[tfolder->getParentUUID()];
                        }
                    }
                }
            }
        }

        gInventory.accountForUpdate(update);

        for (LLInventoryModel::cat_array_t::iterator cit = folders.begin(); cit != folders.end(); ++cit)
        {
            gInventory.updateCategory(*cit);
        }
        for (LLInventoryModel::item_array_t::iterator iit = items.begin(); iit != items.end(); ++iit)
        {
            gInventory.updateItem(*iit);
        }
        gInventory.notifyObservers();

        /*
        Transaction id not included?

        // The incoming inventory could span more than one BulkInventoryUpdate packet,
        // so record the transaction ID for this purchase, then wear all clothing
        // that comes in as part of that transaction ID.  JC
        if (LLInventoryState::sWearNewClothing)
        {
            LLInventoryState::sWearNewClothingTransactionID = tid;
            LLInventoryState::sWearNewClothing = FALSE;
        }

        if (tid.notNull() && tid == LLInventoryState::sWearNewClothingTransactionID)
        {
            count = wearable_ids.size();
            for (i = 0; i < count; ++i)
            {
                LLViewerInventoryItem* wearable_item;
                wearable_item = gInventory.getItem(wearable_ids[i]);
                LLAppearanceMgr::instance().wearItemOnAvatar(wearable_item->getUUID(), true, true);
            }
        }
        */

        if (LLInventoryState::sWearNewClothing && wearable_ids.size() > 0)
        {
            LLInventoryState::sWearNewClothing = FALSE;

            size_t count = wearable_ids.size();
            for (S32 i = 0; i < count; ++i)
            {
                LLViewerInventoryItem* wearable_item;
                wearable_item = gInventory.getItem(wearable_ids[i]);
                LLAppearanceMgr::instance().wearItemOnAvatar(wearable_item->getUUID(), true, true);
            }
        }

        std::list<InventoryCallbackInfo>::iterator inv_it;
        for (inv_it = cblist.begin(); inv_it != cblist.end(); ++inv_it)
        {
            InventoryCallbackInfo cbinfo = (*inv_it);
            gInventoryCallbacks.fire(cbinfo.mCallback, cbinfo.mInvID);
        }
        return true;
    }
};
static LLDispatchBulkUpdateInventory sBulkUpdateInventory;

///----------------------------------------------------------------------------
/// Class LLInventoryValidationInfo
///----------------------------------------------------------------------------
LLInventoryValidationInfo::LLInventoryValidationInfo()
{
}

void LLInventoryValidationInfo::toOstream(std::ostream& os) const
{
    os << "mFatalErrorCount " << mFatalErrorCount
       << " mWarningCount " << mWarningCount
       << " mLoopCount " << mLoopCount
       << " mOrphanedCount " << mOrphanedCount;
}


std::ostream& operator<<(std::ostream& os, const LLInventoryValidationInfo& v)
{
    v.toOstream(os);
    return os;
}

void LLInventoryValidationInfo::asLLSD(LLSD& sd) const
{
    sd["fatal_error_count"] = mFatalErrorCount;
    sd["loop_count"] = mLoopCount;
    sd["orphaned_count"] = mOrphanedCount;
    sd["initialized"] = mInitialized;
    sd["missing_system_folders_count"] = LLSD::Integer(mMissingRequiredSystemFolders.size());
    sd["fatal_no_root_folder"] = mFatalNoRootFolder;
    sd["fatal_no_library_root_folder"] = mFatalNoLibraryRootFolder;
    sd["fatal_qa_debug_mode"] = mFatalQADebugMode;

    sd["warning_count"] = mWarningCount;
    if (mWarningCount>0)
    {
        sd["warnings"] = LLSD::emptyArray();
        for (auto const& it : mWarnings)
        {
            S32 val =LLSD::Integer(it.second);
            if (val>0)
            {
                sd["warnings"][it.first] = val;
            }
        }
    }
    if (mMissingRequiredSystemFolders.size()>0)
    {
        sd["missing_system_folders"] = LLSD::emptyArray();
        for(auto ft: mMissingRequiredSystemFolders)
        {
            sd["missing_system_folders"].append(LLFolderType::lookup(ft));
        }
    }
    sd["duplicate_system_folders_count"] = LLSD::Integer(mDuplicateRequiredSystemFolders.size());
    if (mDuplicateRequiredSystemFolders.size()>0)
    {
        sd["duplicate_system_folders"] = LLSD::emptyArray();
        for(auto ft: mDuplicateRequiredSystemFolders)
        {
            sd["duplicate_system_folders"].append(LLFolderType::lookup(ft));
        }
    }

}

///----------------------------------------------------------------------------
/// Class LLInventoryModel
///----------------------------------------------------------------------------

// global for the agent inventory.
LLInventoryModel gInventory;

// Default constructor
LLInventoryModel::LLInventoryModel()
:   // These are now ordered, keep them that way.
    mBacklinkMMap(),
    mIsAgentInvUsable(false),
    mRootFolderID(),
    mLibraryRootFolderID(),
    mLibraryOwnerID(),
    mCategoryMap(),
    mItemMap(),
    mParentChildCategoryTree(),
    mParentChildItemTree(),
    mLastItem(NULL),
    mIsNotifyObservers(FALSE),
    mModifyMask(LLInventoryObserver::ALL),
    mChangedItemIDs(),
    mBulkFecthCallbackSlot(),
    mObservers(),
    mHttpRequestFG(NULL),
    mHttpRequestBG(NULL),
    mHttpOptions(),
    mHttpHeaders(),
    mHttpPolicyClass(LLCore::HttpRequest::DEFAULT_POLICY_ID),
    mCategoryLock(),
    mItemLock(),
    mValidationInfo(new LLInventoryValidationInfo)
{}


// Destroys the object
LLInventoryModel::~LLInventoryModel()
{
    cleanupInventory();
}

void LLInventoryModel::cleanupInventory()
{
    empty();
    // Deleting one observer might erase others from the list, so always pop off the front
    while (!mObservers.empty())
    {
        observer_list_t::iterator iter = mObservers.begin();
        LLInventoryObserver* observer = *iter;
        mObservers.erase(iter);
        delete observer;
    }

    if (mBulkFecthCallbackSlot.connected())
    {
        mBulkFecthCallbackSlot.disconnect();
    }
    mObservers.clear();

    // Run down HTTP transport
    mHttpHeaders.reset();
    mHttpOptions.reset();

    delete mHttpRequestFG;
    mHttpRequestFG = NULL;
    delete mHttpRequestBG;
    mHttpRequestBG = NULL;
}

// This is a convenience function to check if one object has a parent
// chain up to the category specified by UUID.
BOOL LLInventoryModel::isObjectDescendentOf(const LLUUID& obj_id,
                                            const LLUUID& cat_id) const
{
    if (obj_id == cat_id) return TRUE;

    const LLInventoryObject* obj = getObject(obj_id);
    while(obj)
    {
        const LLUUID& parent_id = obj->getParentUUID();
        if( parent_id.isNull() )
        {
            return FALSE;
        }
        if(parent_id == cat_id)
        {
            return TRUE;
        }
        // Since we're scanning up the parents, we only need to check
        // in the category list.
        obj = getCategory(parent_id);
    }
    return FALSE;
}

const LLViewerInventoryCategory *LLInventoryModel::getFirstNondefaultParent(const LLUUID& obj_id) const
{
    const LLInventoryObject* obj = getObject(obj_id);
    if(!obj)
    {
        LL_WARNS(LOG_INV) << "Non-existent object [ id: " << obj_id << " ] " << LL_ENDL;
        return NULL;
    }
    // Search up the parent chain until we get to root or an acceptable folder.
    // This assumes there are no cycles in the tree else we'll get a hang.
    LLUUID parent_id = obj->getParentUUID();
    while (!parent_id.isNull())
    {
        const LLViewerInventoryCategory *cat = getCategory(parent_id);
        if (!cat) break;
        const LLFolderType::EType folder_type = cat->getPreferredType();
        if (folder_type != LLFolderType::FT_NONE &&
            folder_type != LLFolderType::FT_ROOT_INVENTORY &&
            !LLFolderType::lookupIsEnsembleType(folder_type))
        {
            return cat;
        }
        parent_id = cat->getParentUUID();
    }
    return NULL;
}

//
// Search up the parent chain until we get to the specified parent, then return the first child category under it
//
const LLViewerInventoryCategory* LLInventoryModel::getFirstDescendantOf(const LLUUID& master_parent_id, const LLUUID& obj_id) const
{
    if (master_parent_id == obj_id)
    {
        return NULL;
    }

    const LLViewerInventoryCategory* current_cat = getCategory(obj_id);

    if (current_cat == NULL)
    {
        current_cat = getCategory(getObject(obj_id)->getParentUUID());
    }

    while (current_cat != NULL)
    {
        const LLUUID& current_parent_id = current_cat->getParentUUID();

        if (current_parent_id == master_parent_id)
        {
            return current_cat;
        }

        current_cat = getCategory(current_parent_id);
    }

    return NULL;
}

LLInventoryModel::EAncestorResult LLInventoryModel::getObjectTopmostAncestor(const LLUUID& object_id, LLUUID& result) const
{
    LLInventoryObject *object = getObject(object_id);
    if (!object)
    {
        LL_WARNS(LOG_INV) << "Unable to trace topmost ancestor, initial object " << object_id << " does not exist" << LL_ENDL;
        return ANCESTOR_MISSING;
    }

    std::set<LLUUID> object_ids{ object_id }; // loop protection
    while (object->getParentUUID().notNull())
    {
        LLUUID parent_id = object->getParentUUID();
        if (object_ids.find(parent_id) != object_ids.end())
        {
            LL_WARNS(LOG_INV) << "Detected a loop on an object " << parent_id << " when searching for ancestor of " << object_id << LL_ENDL;
            return ANCESTOR_LOOP;
        }
        object_ids.insert(parent_id);
        LLInventoryObject *parent_object = getObject(parent_id);
        if (!parent_object)
        {
            LL_WARNS(LOG_INV) << "unable to trace topmost ancestor of " << object_id << ", missing item for uuid " << parent_id << LL_ENDL;
            return ANCESTOR_MISSING;
        }
        object = parent_object;
    }
    result = object->getUUID();
    return ANCESTOR_OK;
}

// Get the object by id. Returns NULL if not found.
LLInventoryObject* LLInventoryModel::getObject(const LLUUID& id) const
{
    LLViewerInventoryCategory* cat = getCategory(id);
    if (cat)
    {
        return cat;
    }
    LLViewerInventoryItem* item = getItem(id);
    if (item)
    {
        return item;
    }
    return NULL;
}

// Get the item by id. Returns NULL if not found.
LLViewerInventoryItem* LLInventoryModel::getItem(const LLUUID& id) const
{
    LLViewerInventoryItem* item = NULL;
    if(mLastItem.notNull() && mLastItem->getUUID() == id)
    {
        item = mLastItem;
    }
    else
    {
        item_map_t::const_iterator iter = mItemMap.find(id);
        if (iter != mItemMap.end())
        {
            item = iter->second;
            mLastItem = item;
        }
    }
    return item;
}

// Get the category by id. Returns NULL if not found
LLViewerInventoryCategory* LLInventoryModel::getCategory(const LLUUID& id) const
{
    LLViewerInventoryCategory* category = NULL;
    cat_map_t::const_iterator iter = mCategoryMap.find(id);
    if (iter != mCategoryMap.end())
    {
        category = iter->second;
    }
    return category;
}

S32 LLInventoryModel::getItemCount() const
{
    return mItemMap.size();
}

S32 LLInventoryModel::getCategoryCount() const
{
    return mCategoryMap.size();
}

// Return the direct descendents of the id provided. The array
// provided points straight into the guts of this object, and
// should only be used for read operations, since modifications
// may invalidate the internal state of the inventory. Set passed
// in values to NULL if the call fails.
void LLInventoryModel::getDirectDescendentsOf(const LLUUID& cat_id,
                                              cat_array_t*& categories,
                                              item_array_t*& items) const
{
    categories = get_ptr_in_map(mParentChildCategoryTree, cat_id);
    items = get_ptr_in_map(mParentChildItemTree, cat_id);
}

void LLInventoryModel::getDirectDescendentsOf(const LLUUID& cat_id, cat_array_t& categories, item_array_t& items, LLInventoryCollectFunctor& f) const
{
    if (cat_array_t* categoriesp = get_ptr_in_map(mParentChildCategoryTree, cat_id))
    {
        for (LLViewerInventoryCategory* pFolder : *categoriesp)
        {
            if (f(pFolder, nullptr))
            {
                categories.push_back(pFolder);
            }
        }
    }

    if (item_array_t* itemsp = get_ptr_in_map(mParentChildItemTree, cat_id))
    {
        for (LLViewerInventoryItem* pItem : *itemsp)
        {
            if (f(nullptr, pItem))
            {
                items.push_back(pItem);
            }
        }
    }
}

LLInventoryModel::digest_t LLInventoryModel::hashDirectDescendentNames(const LLUUID& cat_id) const
{
    LLInventoryModel::cat_array_t* cat_array;
    LLInventoryModel::item_array_t* item_array;
    getDirectDescendentsOf(cat_id,cat_array,item_array);
    if (!item_array)
    {
        return LLUUID::null;
    }
    HBXXH128 item_name_hash;
    for (LLInventoryModel::item_array_t::const_iterator iter = item_array->begin();
         iter != item_array->end();
         iter++)
    {
        const LLViewerInventoryItem *item = (*iter);
        if (!item)
            continue;
        item_name_hash.update(item->getName());
    }
    return item_name_hash.digest();
}

// SJB: Added version to lock the arrays to catch potential logic bugs
void LLInventoryModel::lockDirectDescendentArrays(const LLUUID& cat_id,
                                                  cat_array_t*& categories,
                                                  item_array_t*& items)
{
    getDirectDescendentsOf(cat_id, categories, items);
    if (categories)
    {
        mCategoryLock[cat_id] = true;
    }
    if (items)
    {
        mItemLock[cat_id] = true;
    }
}

void LLInventoryModel::unlockDirectDescendentArrays(const LLUUID& cat_id)
{
    mCategoryLock[cat_id] = false;
    mItemLock[cat_id] = false;
}

void LLInventoryModel::consolidateForType(const LLUUID& main_id, LLFolderType::EType type)
{
    // Make a list of folders that are not "main_id" and are of "type"
    std::vector<LLUUID> folder_ids;
    for (cat_map_t::iterator cit = mCategoryMap.begin(); cit != mCategoryMap.end(); ++cit)
    {
        LLViewerInventoryCategory* cat = cit->second;
        if ((cat->getPreferredType() == type) && (cat->getUUID() != main_id))
        {
            folder_ids.push_back(cat->getUUID());
        }
    }

    // Iterate through those folders
    for (std::vector<LLUUID>::iterator folder_ids_it = folder_ids.begin(); folder_ids_it != folder_ids.end(); ++folder_ids_it)
    {
        LLUUID folder_id = (*folder_ids_it);

        // Get the content of this folder
        cat_array_t* cats;
        item_array_t* items;
        getDirectDescendentsOf(folder_id, cats, items);

        // Move all items to the main folder
        // Note : we get the list of UUIDs and iterate on them instead of iterating directly on item_array_t
        // elements. This is because moving elements modify the maps and, consequently, invalidate iterators on them.
        // This "gather and iterate" method is verbose but resilient.
        std::vector<LLUUID> list_uuids;
        for (item_array_t::const_iterator it = items->begin(); it != items->end(); ++it)
        {
            list_uuids.push_back((*it)->getUUID());
        }
        for (std::vector<LLUUID>::const_iterator it = list_uuids.begin(); it != list_uuids.end(); ++it)
        {
            LLViewerInventoryItem* item = getItem(*it);
            changeItemParent(item, main_id, TRUE);
        }

        // Move all folders to the main folder
        list_uuids.clear();
        for (cat_array_t::const_iterator it = cats->begin(); it != cats->end(); ++it)
        {
            list_uuids.push_back((*it)->getUUID());
        }
        for (std::vector<LLUUID>::const_iterator it = list_uuids.begin(); it != list_uuids.end(); ++it)
        {
            LLViewerInventoryCategory* cat = getCategory(*it);
            changeCategoryParent(cat, main_id, TRUE);
        }

        // Purge the emptied folder
        // Note that this might be a system folder, don't validate removability
        LLViewerInventoryCategory* cat = getCategory(folder_id);
        if (cat)
        {
            const LLUUID trash_id = findCategoryUUIDForType(LLFolderType::FT_TRASH);
            if (trash_id.notNull())
            {
                changeCategoryParent(cat, trash_id, TRUE);
            }
        }
        remove_inventory_category(folder_id, NULL);
    }
}

void LLInventoryModel::ensureCategoryForTypeExists(LLFolderType::EType preferred_type)
{
    LLUUID rv = LLUUID::null;
    LLUUID root_id = gInventory.getRootFolderID();
    if (LLFolderType::FT_ROOT_INVENTORY == preferred_type)
    {
        rv = root_id;
    }
    else if (root_id.notNull())
    {
        cat_array_t* cats = NULL;
        cats = get_ptr_in_map(mParentChildCategoryTree, root_id);
        if (cats)
        {
            S32 count = cats->size();
            for (S32 i = 0; i < count; ++i)
            {
                LLViewerInventoryCategory* p_cat = cats->at(i);
                if (p_cat && p_cat->getPreferredType() == preferred_type)
                {
                    const LLUUID& folder_id = cats->at(i)->getUUID();
                    if (rv.isNull() || folder_id < rv)
                    {
                        rv = folder_id;
                    }
                }
            }
        }
    }

    if (rv.isNull() && root_id.notNull())
    {

        if (isInventoryUsable())
        {
            createNewCategory(
                root_id,
                preferred_type,
                LLStringUtil::null,
                [preferred_type](const LLUUID &new_cat_id)
            {
                    if (new_cat_id.isNull())
                    {
                        LL_WARNS("Inventory")
                            << "Failed to create folder of type " << preferred_type
                            << LL_ENDL;
                    }
                    else
                    {
                        LL_WARNS("Inventory") << "Created category: " << new_cat_id
                            << " for type: " << preferred_type << LL_ENDL;
                        sPendingSystemFolders--;
                    }
            }
            );
        }
        else
        {
            LL_WARNS("Inventory") << "Can't create requested folder, type " << preferred_type
                << " because inventory is not usable" << LL_ENDL;
        }
    }
    else
    {
        sPendingSystemFolders--;
    }
}

const LLUUID LLInventoryModel::findCategoryUUIDForTypeInRoot(
    LLFolderType::EType preferred_type,
    const LLUUID& root_id) const
{
    LLUUID rv = LLUUID::null;
    if(LLFolderType::FT_ROOT_INVENTORY == preferred_type)
    {
        rv = root_id;
    }
    else if (root_id.notNull())
    {
        cat_array_t* cats = NULL;
        cats = get_ptr_in_map(mParentChildCategoryTree, root_id);
        if(cats)
        {
            S32 count = cats->size();
            for(S32 i = 0; i < count; ++i)
            {
                LLViewerInventoryCategory* p_cat = cats->at(i);
                if(p_cat && p_cat->getPreferredType() == preferred_type)
                {
                    const LLUUID& folder_id = cats->at(i)->getUUID();
                    if (rv.isNull() || folder_id < rv)
                    {
                        rv = folder_id;
                    }
                }
            }
        }
    }

    if(rv.isNull()
       && root_id.notNull()
       && preferred_type != LLFolderType::FT_MARKETPLACE_LISTINGS
       && preferred_type != LLFolderType::FT_OUTBOX)
    {
        // if it does not exists, it should either be added
        // to createCommonSystemCategories or server should
        // have set it
        llassert(!isInventoryUsable());
        LL_WARNS("Inventory") << "Tried to find folder, type " << preferred_type
                                  << " but category does not exist" << LL_ENDL;
    }
    return rv;
}

// findCategoryUUIDForType() returns the uuid of the category that
// specifies 'type' as what it defaults to containing. The category is
// not necessarily only for that type. *NOTE: This will create a new
// inventory category on the fly if one does not exist.
const LLUUID LLInventoryModel::findCategoryUUIDForType(LLFolderType::EType preferred_type) const
{
    return findCategoryUUIDForTypeInRoot(preferred_type, gInventory.getRootFolderID());
}

const LLUUID LLInventoryModel::findUserDefinedCategoryUUIDForType(LLFolderType::EType preferred_type) const
{
    LLUUID cat_id;
    switch (preferred_type)
    {
    case LLFolderType::FT_OBJECT:
    {
        cat_id = LLUUID(gSavedPerAccountSettings.getString("ModelUploadFolder"));
        break;
    }
    case LLFolderType::FT_TEXTURE:
    {
        cat_id = LLUUID(gSavedPerAccountSettings.getString("TextureUploadFolder"));
        break;
    }
    case LLFolderType::FT_SOUND:
    {
        cat_id = LLUUID(gSavedPerAccountSettings.getString("SoundUploadFolder"));
        break;
    }
    case LLFolderType::FT_ANIMATION:
    {
        cat_id = LLUUID(gSavedPerAccountSettings.getString("AnimationUploadFolder"));
        break;
    }
    case LLFolderType::FT_MATERIAL:
    {
        cat_id = LLUUID(gSavedPerAccountSettings.getString("PBRUploadFolder"));
        break;
    }
    default:
        break;
    }

    if (cat_id.isNull() || !getCategory(cat_id))
    {
        cat_id = findCategoryUUIDForTypeInRoot(preferred_type, getRootFolderID());
    }
    return cat_id;
}

const LLUUID LLInventoryModel::findLibraryCategoryUUIDForType(LLFolderType::EType preferred_type) const
{
    return findCategoryUUIDForTypeInRoot(preferred_type, gInventory.getLibraryRootFolderID());
}

// Convenience function to create a new category. You could call
// updateCategory() with a newly generated UUID category, but this
// version will take care of details like what the name should be
// based on preferred type.
void LLInventoryModel::createNewCategory(const LLUUID& parent_id,
                                           LLFolderType::EType preferred_type,
                                           const std::string& pname,
                                           inventory_func_type callback,
                                           const LLUUID& thumbnail_id)
{
    LL_DEBUGS(LOG_INV) << "Create '" << pname << "' in '" << make_inventory_path(parent_id) << "'" << LL_ENDL;
    if (!isInventoryUsable())
    {
        LL_WARNS(LOG_INV) << "Inventory is not usable; can't create requested category of type "
                          << preferred_type << LL_ENDL;
        if (callback)
        {
            callback(LLUUID::null);
        }
        return;
    }

    if(LLFolderType::lookup(preferred_type) == LLFolderType::badLookup())
    {
        LL_DEBUGS(LOG_INV) << "Attempt to create undefined category." << LL_ENDL;
        if (callback)
        {
            callback(LLUUID::null);
        }
        return;
    }

    if (preferred_type != LLFolderType::FT_NONE)
    {
        // Ultimately this should only be done for non-singleton
        // types. Requires back-end changes to guarantee that others
        // already exist.
        LL_WARNS(LOG_INV) << "Creating new system folder, type " << preferred_type << LL_ENDL;
    }

    std::string name = pname;
    if (pname.empty())
    {
        name.assign(LLViewerFolderType::lookupNewCategoryName(preferred_type));
    }

    if (AISAPI::isAvailable())
    {
        LLSD new_inventory = LLSD::emptyMap();
        new_inventory["categories"] = LLSD::emptyArray();
        LLViewerInventoryCategory cat(LLUUID::null, parent_id, preferred_type, name, gAgent.getID());
        cat.setThumbnailUUID(thumbnail_id);
        LLSD cat_sd = cat.asAISCreateCatLLSD();
        new_inventory["categories"].append(cat_sd);
        AISAPI::CreateInventory(
            parent_id,
            new_inventory,
            [this, callback, parent_id, preferred_type, name] (const LLUUID& new_category)
        {
            if (new_category.isNull())
            {
                if (callback && !callback.empty())
                {
                    callback(new_category);
                }
                return;
            }

            // todo: not needed since AIS does the accounting?
            LLViewerInventoryCategory* folderp = gInventory.getCategory(new_category);
            if (!folderp)
            {
                // Add the category to the internal representation
                LLPointer<LLViewerInventoryCategory> cat = new LLViewerInventoryCategory(
                    new_category,
                    parent_id,
                    preferred_type,
                    name,
                    gAgent.getID());

                LLInventoryModel::LLCategoryUpdate update(cat->getParentUUID(), 1);
                accountForUpdate(update);

                cat->setVersion(LLViewerInventoryCategory::VERSION_INITIAL - 1); // accountForUpdate() will icrease version by 1
                cat->setDescendentCount(0);
                updateCategory(cat);
            }

            if (callback && !callback.empty())
            {
                callback(new_category);
            }
        });
        return;
    }

    LLViewerRegion* viewer_region = gAgent.getRegion();
    std::string url;
    if ( viewer_region )
        url = viewer_region->getCapability("CreateInventoryCategory");

    if (!url.empty())
    {
        //Let's use the new capability.
        LLUUID id;
        id.generate();
        LLSD request, body;
        body["folder_id"] = id;
        body["parent_id"] = parent_id;
        body["type"] = (LLSD::Integer) preferred_type;
        body["name"] = name;

        request["message"] = "CreateInventoryCategory";
        request["payload"] = body;

        LL_DEBUGS(LOG_INV) << "Creating category via request: " << ll_pretty_print_sd(request) << LL_ENDL;
        LLCoros::instance().launch("LLInventoryModel::createNewCategoryCoro",
            boost::bind(&LLInventoryModel::createNewCategoryCoro, this, url, body, callback));
        return;
    }

    if (callback)
    {
        callback(LLUUID::null); // Notify about failure
    }
}

void LLInventoryModel::createNewCategoryCoro(std::string url, LLSD postData, inventory_func_type callback)
{
    LLCore::HttpRequest::policy_t httpPolicy(LLCore::HttpRequest::DEFAULT_POLICY_ID);
    LLCoreHttpUtil::HttpCoroutineAdapter::ptr_t
        httpAdapter(new LLCoreHttpUtil::HttpCoroutineAdapter("createNewCategoryCoro", httpPolicy));
    LLCore::HttpRequest::ptr_t httpRequest(new LLCore::HttpRequest);
    LLCore::HttpOptions::ptr_t httpOpts(new LLCore::HttpOptions);


    httpOpts->setWantHeaders(true);

    LL_INFOS("HttpCoroutineAdapter", "genericPostCoro") << "Generic POST for " << url << LL_ENDL;

    LLSD result = httpAdapter->postAndSuspend(httpRequest, url, postData, httpOpts);

    LLSD httpResults = result[LLCoreHttpUtil::HttpCoroutineAdapter::HTTP_RESULTS];
    LLCore::HttpStatus status = LLCoreHttpUtil::HttpCoroutineAdapter::getStatusFromLLSD(httpResults);

    if (!status)
    {
        LL_WARNS() << "HTTP failure attempting to create category." << LL_ENDL;
        if (callback)
        {
            callback(LLUUID::null);
        }
        return;
    }

    if (!result.has("folder_id"))
    {
        LL_WARNS() << "Malformed response contents" << ll_pretty_print_sd(result) << LL_ENDL;
        if (callback)
        {
            callback(LLUUID::null);
        }
        return;
    }

    LLUUID categoryId = result["folder_id"].asUUID();

    LLViewerInventoryCategory* folderp = gInventory.getCategory(categoryId);
    if (!folderp)
    {
        // Add the category to the internal representation
        LLPointer<LLViewerInventoryCategory> cat = new LLViewerInventoryCategory(categoryId,
            result["parent_id"].asUUID(), (LLFolderType::EType)result["type"].asInteger(),
            result["name"].asString(), gAgent.getID());

        LLInventoryModel::LLCategoryUpdate update(cat->getParentUUID(), 1);
        accountForUpdate(update);

        cat->setVersion(LLViewerInventoryCategory::VERSION_INITIAL - 1); // accountForUpdate() will icrease version by 1
        cat->setDescendentCount(0);
        updateCategory(cat);
    }
    else
    {
        // bulk processing was faster than coroutine (coro request->processBulkUpdateInventory->coro response)
        // category already exists, but needs an update
        if (folderp->getVersion() != LLViewerInventoryCategory::VERSION_INITIAL
            || folderp->getDescendentCount() != LLViewerInventoryCategory::DESCENDENT_COUNT_UNKNOWN)
        {
            LL_WARNS() << "Inventory desync on folder creation. Newly created folder already has descendants or got a version.\n"
                << "Name: " << folderp->getName()
                << " Id: " << folderp->getUUID()
                << " Version: " << folderp->getVersion()
                << " Descendants: " << folderp->getDescendentCount()
                << LL_ENDL;
        }
        // Recreate category with correct values
        // Creating it anew just simplifies figuring out needed change-masks
        // and making all needed updates, see updateCategory
        LLPointer<LLViewerInventoryCategory> cat = new LLViewerInventoryCategory(categoryId,
            result["parent_id"].asUUID(), (LLFolderType::EType)result["type"].asInteger(),
            result["name"].asString(), gAgent.getID());

        if (folderp->getParentUUID() != cat->getParentUUID())
        {
            LL_WARNS() << "Inventory desync on folder creation. Newly created folder has wrong parent.\n"
                << "Name: " << folderp->getName()
                << " Id: " << folderp->getUUID()
                << " Expected parent: " << cat->getParentUUID()
                << " Actual parent: " << folderp->getParentUUID()
                << LL_ENDL;
            LLInventoryModel::LLCategoryUpdate update(cat->getParentUUID(), 1);
            accountForUpdate(update);
        }
        // else: Do not update parent, parent is already aware of the change. See processBulkUpdateInventory

        cat->setVersion(LLViewerInventoryCategory::VERSION_INITIAL - 1); // accountForUpdate() will icrease version by 1
        cat->setDescendentCount(0);
        updateCategory(cat);
    }

    if (callback)
    {
        callback(categoryId);
    }

}

// This is optimized for the case that we just want to know whether a
// category has any immediate children meeting a condition, without
// needing to recurse or build up any lists.
bool LLInventoryModel::hasMatchingDirectDescendent(const LLUUID& cat_id,
                                                   LLInventoryCollectFunctor& filter)
{
    LLInventoryModel::cat_array_t *cats;
    LLInventoryModel::item_array_t *items;
    getDirectDescendentsOf(cat_id, cats, items);
    if (cats)
    {
        for (LLInventoryModel::cat_array_t::const_iterator it = cats->begin();
             it != cats->end(); ++it)
        {
            if (filter(*it,NULL))
            {
                return true;
            }
        }
    }
    if (items)
    {
        for (LLInventoryModel::item_array_t::const_iterator it = items->begin();
             it != items->end(); ++it)
        {
            if (filter(NULL,*it))
            {
                return true;
            }
        }
    }
    return false;
}

// Starting with the object specified, add its descendents to the
// array provided, but do not add the inventory object specified by
// id. There is no guaranteed order. Neither array will be erased
// before adding objects to it. Do not store a copy of the pointers
// collected - use them, and collect them again later if you need to
// reference the same objects.

class LLAlwaysCollect : public LLInventoryCollectFunctor
{
public:
    virtual ~LLAlwaysCollect() {}
    virtual bool operator()(LLInventoryCategory* cat,
                            LLInventoryItem* item)
    {
        return TRUE;
    }
};

void LLInventoryModel::collectDescendents(const LLUUID& id,
                                          cat_array_t& cats,
                                          item_array_t& items,
                                          BOOL include_trash)
{
    LLAlwaysCollect always;
    collectDescendentsIf(id, cats, items, include_trash, always);
}

void LLInventoryModel::collectDescendentsIf(const LLUUID& id,
                                            cat_array_t& cats,
                                            item_array_t& items,
                                            BOOL include_trash,
                                            LLInventoryCollectFunctor& add)
{
    // Start with categories
    if(!include_trash)
    {
        const LLUUID trash_id = findCategoryUUIDForType(LLFolderType::FT_TRASH);
        if(trash_id.notNull() && (trash_id == id))
            return;
    }
    cat_array_t* cat_array = get_ptr_in_map(mParentChildCategoryTree, id);
    if(cat_array)
    {
        S32 count = cat_array->size();
        for(S32 i = 0; i < count; ++i)
        {
            LLViewerInventoryCategory* cat = cat_array->at(i);
            if(add(cat,NULL))
            {
                cats.push_back(cat);
            }
            collectDescendentsIf(cat->getUUID(), cats, items, include_trash, add);
        }
    }

    LLViewerInventoryItem* item = NULL;
    item_array_t* item_array = get_ptr_in_map(mParentChildItemTree, id);

    // Move onto items
    if(item_array)
    {
        S32 count = item_array->size();
        for(S32 i = 0; i < count; ++i)
        {
            item = item_array->at(i);
            if(add(NULL, item))
            {
                items.push_back(item);
            }
        }
    }
}

void LLInventoryModel::addChangedMaskForLinks(const LLUUID& object_id, U32 mask)
{
    const LLInventoryObject *obj = getObject(object_id);
    if (!obj || obj->getIsLinkType())
        return;

    LLInventoryModel::item_array_t item_array = collectLinksTo(object_id);
    for (LLInventoryModel::item_array_t::iterator iter = item_array.begin();
         iter != item_array.end();
         iter++)
    {
        LLViewerInventoryItem *linked_item = (*iter);
        addChangedMask(mask, linked_item->getUUID());
    };
}

const LLUUID& LLInventoryModel::getLinkedItemID(const LLUUID& object_id) const
{
    const LLInventoryItem *item = gInventory.getItem(object_id);
    if (!item)
    {
        return object_id;
    }

    // Find the base item in case this a link (if it's not a link,
    // this will just be inv_item_id)
    return item->getLinkedUUID();
}

LLViewerInventoryItem* LLInventoryModel::getLinkedItem(const LLUUID& object_id) const
{
    return object_id.notNull() ? getItem(getLinkedItemID(object_id)) : NULL;
}

LLInventoryModel::item_array_t LLInventoryModel::collectLinksTo(const LLUUID& id)
{
    // Get item list via collectDescendents (slow!)
    item_array_t items;
    const LLInventoryObject *obj = getObject(id);
    // FIXME - should be as in next line, but this is causing a
    // stack-smashing crash of cause TBD... check in the REBUILD code.
    //if (obj && obj->getIsLinkType())
    if (!obj || obj->getIsLinkType())
        return items;

    std::pair<backlink_mmap_t::iterator, backlink_mmap_t::iterator> range = mBacklinkMMap.equal_range(id);
    for (backlink_mmap_t::iterator it = range.first; it != range.second; ++it)
    {
        LLViewerInventoryItem *item = getItem(it->second);
        if (item)
        {
            items.push_back(item);
        }
    }

    return items;
}

bool LLInventoryModel::isInventoryUsable() const
{
    bool result = false;
    if(gInventory.getRootFolderID().notNull() && mIsAgentInvUsable)
    {
        result = true;
    }
    return result;
}

// Calling this method with an inventory item will either change an
// existing item with a matching item_id, or will add the item to the
// current inventory.
U32 LLInventoryModel::updateItem(const LLViewerInventoryItem* item, U32 mask)
{
    if(item->getUUID().isNull())
    {
        return mask;
    }

    if(!isInventoryUsable())
    {
        LL_WARNS(LOG_INV) << "Inventory is broken." << LL_ENDL;
        return mask;
    }

    if (item->getType() == LLAssetType::AT_MESH)
    {
        return mask;
    }

    LLPointer<LLViewerInventoryItem> old_item = getItem(item->getUUID());
    LLPointer<LLViewerInventoryItem> new_item;
    if(old_item)
    {
        // We already have an old item, modify its values
        new_item = old_item;
        LLUUID old_parent_id = old_item->getParentUUID();
        LLUUID new_parent_id = item->getParentUUID();
        bool update_parent_on_server = false;

        if (new_parent_id.isNull() && !LLApp::isExiting())
        {
            if (old_parent_id.isNull())
            {
                // Item with null parent will end in random location and then in Lost&Found,
                // either move to default folder as if it is new item or don't move at all
                LL_WARNS(LOG_INV) << "Update attempts to reparent item " << item->getUUID()
                                  << " to null folder. Moving to Lost&Found. Old item name: " << old_item->getName()
                                  << ". New name: " << item->getName()
                                  << "." << LL_ENDL;
                new_parent_id = findCategoryUUIDForType(LLFolderType::FT_LOST_AND_FOUND);
                update_parent_on_server = true;
            }
            else
            {
                // Probably not the best way to handle this, we might encounter real case of 'lost&found' at some point
                LL_WARNS(LOG_INV) << "Update attempts to reparent item " << item->getUUID()
                                  << " to null folder. Old parent not null. Moving to old parent. Old item name: " << old_item->getName()
                                  << ". New name: " << item->getName()
                                  << "." << LL_ENDL;
                new_parent_id = old_parent_id;
                update_parent_on_server = true;
            }
        }

        if(old_parent_id != new_parent_id)
        {
            // need to update the parent-child tree
            item_array_t* item_array;
            item_array = get_ptr_in_map(mParentChildItemTree, old_parent_id);
            if(item_array)
            {
                vector_replace_with_last(*item_array, old_item);
            }
            item_array = get_ptr_in_map(mParentChildItemTree, new_parent_id);
            if(item_array)
            {
                if (update_parent_on_server)
                {
                    LLInventoryModel::LLCategoryUpdate update(new_parent_id, 1);
                    gInventory.accountForUpdate(update);
                }
                item_array->push_back(old_item);
            }
            mask |= LLInventoryObserver::STRUCTURE;
        }
        if(old_item->getName() != item->getName())
        {
            mask |= LLInventoryObserver::LABEL;
        }
        if (old_item->getPermissions() != item->getPermissions())
        {
            mask |= LLInventoryObserver::INTERNAL;
        }
        old_item->copyViewerItem(item);
        if (update_parent_on_server)
        {
            // Parent id at server is null, so update server even if item already is in the same folder
            old_item->setParent(new_parent_id);
            new_item->updateParentOnServer(FALSE);
        }
        mask |= LLInventoryObserver::INTERNAL;
    }
    else
    {
        // Simply add this item
        new_item = new LLViewerInventoryItem(item);
        addItem(new_item);

        if(item->getParentUUID().isNull())
        {
            const LLUUID category_id = findCategoryUUIDForType(LLFolderType::assetTypeToFolderType(new_item->getType()));
            new_item->setParent(category_id);
            item_array_t* item_array = get_ptr_in_map(mParentChildItemTree, category_id);
            if( item_array )
            {
                LLInventoryModel::LLCategoryUpdate update(category_id, 1);
                gInventory.accountForUpdate(update);

                // *FIX: bit of a hack to call update server from here...
                new_item->updateParentOnServer(FALSE);
                item_array->push_back(new_item);
            }
            else
            {
                LL_WARNS(LOG_INV) << "Couldn't find parent-child item tree for " << new_item->getName() << LL_ENDL;
            }
        }
        else
        {
            // *NOTE: The general scheme is that if every byte of the
            // uuid is 0, except for the last one or two,the use the
            // last two bytes of the parent id, and match that up
            // against the type. For now, we're only worried about
            // lost & found.
            LLUUID parent_id = item->getParentUUID();
            if(parent_id == CATEGORIZE_LOST_AND_FOUND_ID)
            {
                parent_id = findCategoryUUIDForType(LLFolderType::FT_LOST_AND_FOUND);
                new_item->setParent(parent_id);
                LLInventoryModel::update_list_t update;
                LLInventoryModel::LLCategoryUpdate new_folder(parent_id, 1);
                update.push_back(new_folder);
                accountForUpdate(update);

            }
            item_array_t* item_array = get_ptr_in_map(mParentChildItemTree, parent_id);
            if(item_array)
            {
                item_array->push_back(new_item);
            }
            else
            {
                // Whoops! No such parent, make one.
                LL_INFOS(LOG_INV) << "Lost item: " << new_item->getUUID() << " - "
                                  << new_item->getName() << LL_ENDL;
                parent_id = findCategoryUUIDForType(LLFolderType::FT_LOST_AND_FOUND);
                new_item->setParent(parent_id);
                item_array = get_ptr_in_map(mParentChildItemTree, parent_id);
                if(item_array)
                {
                    LLInventoryModel::LLCategoryUpdate update(parent_id, 1);
                    gInventory.accountForUpdate(update);
                    // *FIX: bit of a hack to call update server from
                    // here...
                    new_item->updateParentOnServer(FALSE);
                    item_array->push_back(new_item);
                }
                else
                {
                    LL_WARNS(LOG_INV) << "Lost and found Not there!!" << LL_ENDL;
                }
            }
        }
        mask |= LLInventoryObserver::ADD;
    }
    if(new_item->getType() == LLAssetType::AT_CALLINGCARD)
    {
        mask |= LLInventoryObserver::CALLING_CARD;
        // Handle user created calling cards.
        // Target ID is stored in the description field of the card.
        LLUUID id;
        std::string desc = new_item->getDescription();
        BOOL isId = desc.empty() ? FALSE : id.set(desc, FALSE);
        if (isId)
        {
            // Valid UUID; set the item UUID and rename it
            new_item->setCreator(id);
            LLAvatarName av_name;

            if (LLAvatarNameCache::get(id, &av_name))
            {
                new_item->rename(av_name.getUserName());
                mask |= LLInventoryObserver::LABEL;
            }
            else
            {
                // Fetch the current name
                LLAvatarNameCache::get(id,
                    boost::bind(&LLViewerInventoryItem::onCallingCardNameLookup, new_item.get(),
                    _1, _2));
            }

        }
    }
    else if (new_item->getType() == LLAssetType::AT_GESTURE)
    {
        mask |= LLInventoryObserver::GESTURE;
    }
    addChangedMask(mask, new_item->getUUID());
    return mask;
}

LLInventoryModel::cat_array_t* LLInventoryModel::getUnlockedCatArray(const LLUUID& id)
{
    cat_array_t* cat_array = get_ptr_in_map(mParentChildCategoryTree, id);
    if (cat_array)
    {
        llassert_always(mCategoryLock[id] == false);
    }
    return cat_array;
}

LLInventoryModel::item_array_t* LLInventoryModel::getUnlockedItemArray(const LLUUID& id)
{
    item_array_t* item_array = get_ptr_in_map(mParentChildItemTree, id);
    if (item_array)
    {
        llassert_always(mItemLock[id] == false);
    }
    return item_array;
}

// Calling this method with an inventory category will either change
// an existing item with the matching id, or it will add the category.
void LLInventoryModel::updateCategory(const LLViewerInventoryCategory* cat, U32 mask)
{
    if(!cat || cat->getUUID().isNull())
    {
        return;
    }

    if(!isInventoryUsable())
    {
        LL_WARNS(LOG_INV) << "Inventory is broken." << LL_ENDL;
        return;
    }

    LLPointer<LLViewerInventoryCategory> old_cat = getCategory(cat->getUUID());
    if(old_cat)
    {
        // We already have an old category, modify its values
        LLUUID old_parent_id = old_cat->getParentUUID();
        LLUUID new_parent_id = cat->getParentUUID();
        if(old_parent_id != new_parent_id)
        {
            // need to update the parent-child tree
            cat_array_t* cat_array;
            cat_array = getUnlockedCatArray(old_parent_id);
            if(cat_array)
            {
                vector_replace_with_last(*cat_array, old_cat);
            }
            cat_array = getUnlockedCatArray(new_parent_id);
            if(cat_array)
            {
                cat_array->push_back(old_cat);
            }
            mask |= LLInventoryObserver::STRUCTURE;
            mask |= LLInventoryObserver::INTERNAL;
        }
        if(old_cat->getName() != cat->getName())
        {
            mask |= LLInventoryObserver::LABEL;
        }
        // Under marketplace, category labels are quite complex and need extra upate
        const LLUUID marketplace_id = findCategoryUUIDForType(LLFolderType::FT_MARKETPLACE_LISTINGS);
        if (marketplace_id.notNull() && isObjectDescendentOf(cat->getUUID(), marketplace_id))
        {
            mask |= LLInventoryObserver::LABEL;
        }
        old_cat->copyViewerCategory(cat);
        addChangedMask(mask, cat->getUUID());
    }
    else
    {
        // add this category
        LLPointer<LLViewerInventoryCategory> new_cat = new LLViewerInventoryCategory(cat->getOwnerID());
        new_cat->copyViewerCategory(cat);
        addCategory(new_cat);

        // make sure this category is correctly referenced by its parent.
        cat_array_t* cat_array;
        cat_array = getUnlockedCatArray(cat->getParentUUID());
        if(cat_array)
        {
            cat_array->push_back(new_cat);
        }

        // make space in the tree for this category's children.
        llassert_always(mCategoryLock[new_cat->getUUID()] == false);
        llassert_always(mItemLock[new_cat->getUUID()] == false);
        cat_array_t* catsp = new cat_array_t;
        item_array_t* itemsp = new item_array_t;
        mParentChildCategoryTree[new_cat->getUUID()] = catsp;
        mParentChildItemTree[new_cat->getUUID()] = itemsp;
        mask |= LLInventoryObserver::ADD;
        addChangedMask(mask, cat->getUUID());
    }
}

void LLInventoryModel::moveObject(const LLUUID& object_id, const LLUUID& cat_id)
{
    LL_DEBUGS(LOG_INV) << "LLInventoryModel::moveObject()" << LL_ENDL;
    if(!isInventoryUsable())
    {
        LL_WARNS(LOG_INV) << "Inventory is broken." << LL_ENDL;
        return;
    }

    if((object_id == cat_id) || !is_in_map(mCategoryMap, cat_id))
    {
        LL_WARNS(LOG_INV) << "Could not move inventory object " << object_id << " to "
                          << cat_id << LL_ENDL;
        return;
    }
    LLPointer<LLViewerInventoryCategory> cat = getCategory(object_id);
    if(cat && (cat->getParentUUID() != cat_id))
    {
        LL_DEBUGS(LOG_INV) << "Move category '" << make_path(cat) << "' to '" << make_inventory_path(cat_id) << "'" << LL_ENDL;
        cat_array_t* cat_array;
        cat_array = getUnlockedCatArray(cat->getParentUUID());
        if(cat_array) vector_replace_with_last(*cat_array, cat);
        cat_array = getUnlockedCatArray(cat_id);
        cat->setParent(cat_id);
        if(cat_array) cat_array->push_back(cat);
        addChangedMask(LLInventoryObserver::STRUCTURE, object_id);
        return;
    }
    LLPointer<LLViewerInventoryItem> item = getItem(object_id);
    if(item && (item->getParentUUID() != cat_id))
    {
        LL_DEBUGS(LOG_INV) << "Move item '" << make_path(item) << "' to '" << make_inventory_path(cat_id) << "'" << LL_ENDL;
        item_array_t* item_array;
        item_array = getUnlockedItemArray(item->getParentUUID());
        if(item_array) vector_replace_with_last(*item_array, item);
        item_array = getUnlockedItemArray(cat_id);
        item->setParent(cat_id);
        if(item_array) item_array->push_back(item);
        addChangedMask(LLInventoryObserver::STRUCTURE, object_id);
        return;
    }
}

// Migrated from llinventoryfunctions
void LLInventoryModel::changeItemParent(LLViewerInventoryItem* item,
                                        const LLUUID& new_parent_id,
                                        BOOL restamp)
{
    if (item->getParentUUID() == new_parent_id)
    {
        LL_DEBUGS(LOG_INV) << make_info(item) << " is already in folder " << make_inventory_info(new_parent_id) << LL_ENDL;
    }
    else
    {
        LL_INFOS(LOG_INV) << "Move item " << make_info(item)
            << " from " << make_inventory_info(item->getParentUUID())
            << " to " << make_inventory_info(new_parent_id) << LL_ENDL;

        LLInventoryModel::LLCategoryUpdate old_folder(item->getParentUUID(),-1);
        accountForUpdate(old_folder);
        LLInventoryModel::LLCategoryUpdate new_folder(new_parent_id, 1, false);
        accountForUpdate(new_folder);

        LLPointer<LLViewerInventoryItem> new_item = new LLViewerInventoryItem(item);
        new_item->setParent(new_parent_id);
        new_item->updateParentOnServer(restamp);
        updateItem(new_item);
        notifyObservers();
    }
}

// Migrated from llinventoryfunctions
void LLInventoryModel::changeCategoryParent(LLViewerInventoryCategory* cat,
                                            const LLUUID& new_parent_id,
                                            BOOL restamp)
{
    if (!cat)
    {
        return;
    }

    // Can't move a folder into a child of itself.
    if (isObjectDescendentOf(new_parent_id, cat->getUUID()))
    {
        return;
    }

    LL_INFOS(LOG_INV) << "Move category " << make_info(cat)
        << " from " << make_inventory_info(cat->getParentUUID())
        << " to " << make_inventory_info(new_parent_id) << LL_ENDL;

    LLInventoryModel::LLCategoryUpdate old_folder(cat->getParentUUID(), -1);
    accountForUpdate(old_folder);
    LLInventoryModel::LLCategoryUpdate new_folder(new_parent_id, 1, false);
    accountForUpdate(new_folder);

    LLPointer<LLViewerInventoryCategory> new_cat = new LLViewerInventoryCategory(cat);
    new_cat->setParent(new_parent_id);
    new_cat->updateParentOnServer(restamp);
    updateCategory(new_cat);
    notifyObservers();
}

void LLInventoryModel::rebuildBrockenLinks()
{
    // make sure we aren't adding expensive Rebuild to anything else.
    notifyObservers();

    for (const broken_links_t::value_type &link_list : mPossiblyBrockenLinks)
    {
        for (const LLUUID& link_id : link_list.second)
        {
            addChangedMask(LLInventoryObserver::REBUILD , link_id);
        }
    }
    for (const LLUUID& link_id : mLinksRebuildList)
    {
        addChangedMask(LLInventoryObserver::REBUILD , link_id);
    }
    mPossiblyBrockenLinks.clear();
    mLinksRebuildList.clear();
    notifyObservers();
}

// Does not appear to be used currently.
void LLInventoryModel::onItemUpdated(const LLUUID& item_id, const LLSD& updates, bool update_parent_version)
{
    U32 mask = LLInventoryObserver::NONE;

    LLPointer<LLViewerInventoryItem> item = gInventory.getItem(item_id);
    LL_DEBUGS(LOG_INV) << "item_id: [" << item_id << "] name " << (item ? item->getName() : "(NOT FOUND)") << LL_ENDL;
    if(item)
    {
        for (LLSD::map_const_iterator it = updates.beginMap();
             it != updates.endMap(); ++it)
        {
            if (it->first == "name")
            {
                LL_INFOS(LOG_INV) << "Updating name from " << item->getName() << " to " << it->second.asString() << LL_ENDL;
                item->rename(it->second.asString());
                mask |= LLInventoryObserver::LABEL;
            }
            else if (it->first == "desc")
            {
                LL_INFOS(LOG_INV) << "Updating description from " << item->getActualDescription()
                                  << " to " << it->second.asString() << LL_ENDL;
                item->setDescription(it->second.asString());
            }
            else
            {
                LL_ERRS(LOG_INV) << "unhandled updates for field: " << it->first << LL_ENDL;
            }
        }
        mask |= LLInventoryObserver::INTERNAL;
        addChangedMask(mask, item->getUUID());
        if (update_parent_version)
        {
            // Descendent count is unchanged, but folder version incremented.
            LLInventoryModel::LLCategoryUpdate up(item->getParentUUID(), 0);
            accountForUpdate(up);
        }
        notifyObservers(); // do we want to be able to make this optional?
    }
}

// Not used?
void LLInventoryModel::onCategoryUpdated(const LLUUID& cat_id, const LLSD& updates)
{
    U32 mask = LLInventoryObserver::NONE;

    LLPointer<LLViewerInventoryCategory> cat = gInventory.getCategory(cat_id);
    LL_DEBUGS(LOG_INV) << "cat_id: [" << cat_id << "] name " << (cat ? cat->getName() : "(NOT FOUND)") << LL_ENDL;
    if(cat)
    {
        for (LLSD::map_const_iterator it = updates.beginMap();
             it != updates.endMap(); ++it)
        {
            if (it->first == "name")
            {
                LL_INFOS(LOG_INV) << "Updating name from " << cat->getName() << " to " << it->second.asString() << LL_ENDL;
                cat->rename(it->second.asString());
                mask |= LLInventoryObserver::LABEL;
            }
            else
            {
                LL_ERRS(LOG_INV) << "unhandled updates for field: " << it->first << LL_ENDL;
            }
        }
        mask |= LLInventoryObserver::INTERNAL;
        addChangedMask(mask, cat->getUUID());
        notifyObservers(); // do we want to be able to make this optional?
    }
}

// Update model after descendents have been purged.
void LLInventoryModel::onDescendentsPurgedFromServer(const LLUUID& object_id, bool fix_broken_links)
{
    LLPointer<LLViewerInventoryCategory> cat = getCategory(object_id);
    if (cat.notNull())
    {
        // do the cache accounting
        S32 descendents = cat->getDescendentCount();
        if(descendents > 0)
        {
            LLInventoryModel::LLCategoryUpdate up(object_id, -descendents);
            accountForUpdate(up);
        }

        // we know that descendent count is 0, however since the
        // accounting may actually not do an update, we should force
        // it here.
        cat->setDescendentCount(0);

        // unceremoniously remove anything we have locally stored.
        LLInventoryModel::cat_array_t categories;
        LLInventoryModel::item_array_t items;
        collectDescendents(object_id,
                           categories,
                           items,
                           LLInventoryModel::INCLUDE_TRASH);
        S32 count = items.size();

        LLUUID uu_id;
        for(S32 i = 0; i < count; ++i)
        {
            uu_id = items.at(i)->getUUID();

            // This check prevents the deletion of a previously deleted item.
            // This is necessary because deletion is not done in a hierarchical
            // order. The current item may have been already deleted as a child
            // of its deleted parent.
            if (getItem(uu_id))
            {
                deleteObject(uu_id, fix_broken_links);
            }
        }

        count = categories.size();
        // Slightly kludgy way to make sure categories are removed
        // only after their child categories have gone away.

        // FIXME: Would probably make more sense to have this whole
        // descendent-clearing thing be a post-order recursive
        // function to get the leaf-up behavior automatically.
        S32 deleted_count;
        S32 total_deleted_count = 0;
        do
        {
            deleted_count = 0;
            for(S32 i = 0; i < count; ++i)
            {
                uu_id = categories.at(i)->getUUID();
                if (getCategory(uu_id))
                {
                    cat_array_t* cat_list = getUnlockedCatArray(uu_id);
                    if (!cat_list || (cat_list->size() == 0))
                    {
                        deleteObject(uu_id, fix_broken_links);
                        deleted_count++;
                    }
                }
            }
            total_deleted_count += deleted_count;
        }
        while (deleted_count > 0);
        if (total_deleted_count != count)
        {
            LL_WARNS(LOG_INV) << "Unexpected count of categories deleted, got "
                              << total_deleted_count << " expected " << count << LL_ENDL;
        }
        //gInventory.validate();
    }
}

// Update model after an item is confirmed as removed from
// server. Works for categories or items.
void LLInventoryModel::onObjectDeletedFromServer(const LLUUID& object_id, bool fix_broken_links, bool update_parent_version, bool do_notify_observers)
{
    LLPointer<LLInventoryObject> obj = getObject(object_id);
    if(obj)
    {
        if (getCategory(object_id))
        {
            // For category, need to delete/update all children first.
            onDescendentsPurgedFromServer(object_id, fix_broken_links);
        }


        // From item/cat removeFromServer()
        if (update_parent_version)
        {
            LLInventoryModel::LLCategoryUpdate up(obj->getParentUUID(), -1);
            accountForUpdate(up);
        }

        // From purgeObject()
        LLViewerInventoryItem *item = getItem(object_id);
        if (item && (item->getType() != LLAssetType::AT_LSL_TEXT))
        {
            LLPreview::hide(object_id, TRUE);
        }
        deleteObject(object_id, fix_broken_links, do_notify_observers);
    }
}


// Delete a particular inventory object by ID.
void LLInventoryModel::deleteObject(const LLUUID& id, bool fix_broken_links, bool do_notify_observers)
{
    LL_DEBUGS(LOG_INV) << "LLInventoryModel::deleteObject()" << LL_ENDL;
    LLPointer<LLInventoryObject> obj = getObject(id);
    if (!obj)
    {
        LL_WARNS(LOG_INV) << "Deleting non-existent object [ id: " << id << " ] " << LL_ENDL;
        return;
    }

    //collect the links before removing the item from mItemMap
    LLInventoryModel::item_array_t links = collectLinksTo(id);

    LL_DEBUGS(LOG_INV) << "Deleting inventory object " << id << LL_ENDL;
    mLastItem = NULL;
    LLUUID parent_id = obj->getParentUUID();
    mCategoryMap.erase(id);
    mItemMap.erase(id);
    //mInventory.erase(id);
    item_array_t* item_list = getUnlockedItemArray(parent_id);
    if(item_list)
    {
        LLPointer<LLViewerInventoryItem> item = (LLViewerInventoryItem*)((LLInventoryObject*)obj);
        vector_replace_with_last(*item_list, item);
    }
    cat_array_t* cat_list = getUnlockedCatArray(parent_id);
    if(cat_list)
    {
        LLPointer<LLViewerInventoryCategory> cat = (LLViewerInventoryCategory*)((LLInventoryObject*)obj);
        vector_replace_with_last(*cat_list, cat);
    }

    // Note : We need to tell the inventory observers that those things are going to be deleted *before* the tree is cleared or they won't know what to delete (in views and view models)
    addChangedMask(LLInventoryObserver::REMOVE, id);
    gInventory.notifyObservers();

    item_list = getUnlockedItemArray(id);
    if(item_list)
    {
        if (item_list->size())
        {
            LL_WARNS(LOG_INV) << "Deleting cat " << id << " while it still has child items" << LL_ENDL;
        }
        delete item_list;
        mParentChildItemTree.erase(id);
    }
    cat_list = getUnlockedCatArray(id);
    if(cat_list)
    {
        if (cat_list->size())
        {
            LL_WARNS(LOG_INV) << "Deleting cat " << id << " while it still has child cats" << LL_ENDL;
        }
        mParentChildCategoryTree.erase(id);
        delete cat_list;
    }
    addChangedMask(LLInventoryObserver::REMOVE, id);

    bool is_link_type = obj->getIsLinkType();
    if (is_link_type)
    {
        removeBacklinkInfo(obj->getUUID(), obj->getLinkedUUID());
    }

    // Can't have links to links, so there's no need for this update
    // if the item removed is a link. Can also skip if source of the
    // update is getting broken link info separately.
    if (fix_broken_links && !is_link_type)
    {
        rebuildLinkItems(links);
    }
    obj = nullptr; // delete obj
    if (do_notify_observers)
    {
        notifyObservers();
    }
}

void LLInventoryModel::rebuildLinkItems(LLInventoryModel::item_array_t& items)
{
    // REBUILD is expensive, so clear the current change list first else
    // everything else on the changelist will also get rebuilt.
    if (items.size() > 0)
    {
        notifyObservers();
        for (LLInventoryModel::item_array_t::const_iterator iter = items.begin();
            iter != items.end();
            iter++)
        {
            const LLViewerInventoryItem *linked_item = (*iter);
            if (linked_item)
            {
                addChangedMask(LLInventoryObserver::REBUILD, linked_item->getUUID());
            }
        }
        notifyObservers();
    }
}

// Add/remove an observer. If the observer is destroyed, be sure to
// remove it.
void LLInventoryModel::addObserver(LLInventoryObserver* observer)
{
    mObservers.insert(observer);
}

void LLInventoryModel::removeObserver(LLInventoryObserver* observer)
{
    mObservers.erase(observer);
}

BOOL LLInventoryModel::containsObserver(LLInventoryObserver* observer) const
{
    return mObservers.find(observer) != mObservers.end();
}

void LLInventoryModel::idleNotifyObservers()
{
    // *FIX:  Think I want this conditional or moved elsewhere...
    handleResponses(true);

    if (mLinksRebuildList.size() > 0)
    {
        if (mModifyMask != LLInventoryObserver::NONE || (mChangedItemIDs.size() != 0))
        {
            notifyObservers();
        }
        for (const LLUUID& link_id : mLinksRebuildList)
        {
            addChangedMask(LLInventoryObserver::REBUILD , link_id);
        }
        mLinksRebuildList.clear();
        notifyObservers();
    }

    if (mModifyMask == LLInventoryObserver::NONE && (mChangedItemIDs.size() == 0))
    {
        return;
    }
    notifyObservers();
}

// Call this method when it's time to update everyone on a new state.
void LLInventoryModel::notifyObservers()
{
    if (mIsNotifyObservers)
    {
        // Within notifyObservers, something called notifyObservers
        // again.  This type of recursion is unsafe because it causes items to be
        // processed twice, and this can easily lead to infinite loops.
        LL_WARNS(LOG_INV) << "Call was made to notifyObservers within notifyObservers!" << LL_ENDL;
        return;
    }

    mIsNotifyObservers = TRUE;
    for (observer_list_t::iterator iter = mObservers.begin();
         iter != mObservers.end(); )
    {
        LLInventoryObserver* observer = *iter;
        observer->changed(mModifyMask);

        // safe way to increment since changed may delete entries! (@!##%@!@&*!)
        iter = mObservers.upper_bound(observer);
    }

    // If there were any changes that arrived during notifyObservers,
    // shedule them for next loop
    mModifyMask = mModifyMaskBacklog;
    mChangedItemIDs.clear();
    mChangedItemIDs.insert(mChangedItemIDsBacklog.begin(), mChangedItemIDsBacklog.end());
    mAddedItemIDs.clear();
    mAddedItemIDs.insert(mAddedItemIDsBacklog.begin(), mAddedItemIDsBacklog.end());

    mModifyMaskBacklog = LLInventoryObserver::NONE;
    mChangedItemIDsBacklog.clear();
    mAddedItemIDsBacklog.clear();

    mIsNotifyObservers = FALSE;
}

// store flag for change
// and id of object change applies to
void LLInventoryModel::addChangedMask(U32 mask, const LLUUID& referent)
{
    if (mIsNotifyObservers)
    {
        // Something marked an item for change within a call to notifyObservers
        // (which is in the process of processing the list of items marked for change).
        // This means the change will have to be processed later.
        // It's preferable for this not to happen, but it's not an issue unless code
        // specifically wants to notifyObservers immediately (changes won't happen untill later)
        LL_WARNS(LOG_INV) << "Adding changed mask within notify observers! Change's processing will be performed on idle." << LL_ENDL;
        LLViewerInventoryItem *item = getItem(referent);
        if (item)
        {
            LL_WARNS(LOG_INV) << "Item " << item->getName() << LL_ENDL;
        }
        else
        {
            LLViewerInventoryCategory *cat = getCategory(referent);
            if (cat)
            {
                LL_WARNS(LOG_INV) << "Category " << cat->getName() << LL_ENDL;
            }
        }
    }

    if (mIsNotifyObservers)
    {
        mModifyMaskBacklog |= mask;
    }
    else
    {
        mModifyMask |= mask;
    }

    bool needs_update = false;
    if (referent.notNull())
    {
        if (mIsNotifyObservers)
        {
            needs_update = mChangedItemIDsBacklog.find(referent) == mChangedItemIDsBacklog.end();
        }
        else
        {
            needs_update = mChangedItemIDs.find(referent) == mChangedItemIDs.end();
        }
    }

    if (needs_update)
    {
        if (mIsNotifyObservers)
        {
            mChangedItemIDsBacklog.insert(referent);
        }
        else
        {
            mChangedItemIDs.insert(referent);
        }

        if (mask != LLInventoryObserver::LABEL)
        {
            // Fix me: From DD-81, probably shouldn't be here, instead
            // should be somewhere in an observer or in
            // LLMarketplaceInventoryObserver::onIdleProcessQueue
            update_marketplace_category(referent, false);
        }

        if (mask & LLInventoryObserver::ADD)
        {
            if (mIsNotifyObservers)
            {
                mAddedItemIDsBacklog.insert(referent);
            }
            else
            {
                mAddedItemIDs.insert(referent);
            }
        }

        // Update all linked items.  Starting with just LABEL because I'm
        // not sure what else might need to be accounted for this.
        if (mask & LLInventoryObserver::LABEL)
        {
            addChangedMaskForLinks(referent, LLInventoryObserver::LABEL);
        }
    }
}

bool LLInventoryModel::fetchDescendentsOf(const LLUUID& folder_id) const
{
    if(folder_id.isNull())
    {
        LL_WARNS(LOG_INV) << "Calling fetch descendents on NULL folder id!" << LL_ENDL;
        return false;
    }
    LLViewerInventoryCategory* cat = getCategory(folder_id);
    if(!cat)
    {
        LL_WARNS(LOG_INV) << "Asked to fetch descendents of non-existent folder: "
                          << folder_id << LL_ENDL;
        return false;
    }
    //S32 known_descendents = 0;
    ///cat_array_t* categories = get_ptr_in_map(mParentChildCategoryTree, folder_id);
    //item_array_t* items = get_ptr_in_map(mParentChildItemTree, folder_id);
    //if(categories)
    //{
    //  known_descendents += categories->size();
    //}
    //if(items)
    //{
    //  known_descendents += items->size();
    //}
    return cat->fetch();
}

//static
std::string LLInventoryModel::getInvCacheAddres(const LLUUID& owner_id)
{
    std::string inventory_addr;
    std::string owner_id_str;
    owner_id.toString(owner_id_str);
    std::string path(gDirUtilp->getExpandedFilename(LL_PATH_CACHE, owner_id_str));
    if (LLGridManager::getInstance()->isInProductionGrid())
    {
        inventory_addr = llformat(PRODUCTION_CACHE_FORMAT_STRING, path.c_str());
    }
    else
    {
        // NOTE: The inventory cache filenames now include the grid name.
        // Add controls against directory traversal or problematic pathname lengths
        // if your viewer uses grid names from an untrusted source.
        const std::string& grid_id_str = LLGridManager::getInstance()->getGridId();
        const std::string& grid_id_lower = utf8str_tolower(grid_id_str);
        inventory_addr = llformat(GRID_CACHE_FORMAT_STRING, path.c_str(), grid_id_lower.c_str());
    }
    return inventory_addr;
}

void LLInventoryModel::cache(
    const LLUUID& parent_folder_id,
    const LLUUID& agent_id)
{
    LL_DEBUGS(LOG_INV) << "Caching " << parent_folder_id << " for " << agent_id
                       << LL_ENDL;
    LLViewerInventoryCategory* root_cat = getCategory(parent_folder_id);
    if(!root_cat) return;
    cat_array_t categories;
    categories.push_back(root_cat);
    item_array_t items;

    LLCanCache can_cache(this);
    can_cache(root_cat, NULL);
    collectDescendentsIf(
        parent_folder_id,
        categories,
        items,
        INCLUDE_TRASH,
        can_cache);
    // Use temporary file to avoid potential conflicts with other
    // instances (even a 'read only' instance unzips into a file)
    std::string temp_file = gDirUtilp->getTempFilename();
    saveToFile(temp_file, categories, items);
    std::string gzip_filename = getInvCacheAddres(agent_id);
    gzip_filename.append(".gz");
    if(gzip_file(temp_file, gzip_filename))
    {
        LL_DEBUGS(LOG_INV) << "Successfully compressed " << temp_file << " to " << gzip_filename << LL_ENDL;
        LLFile::remove(temp_file);
    }
    else
    {
        LL_WARNS(LOG_INV) << "Unable to compress " << temp_file << " into " << gzip_filename << LL_ENDL;
    }
}


void LLInventoryModel::addCategory(LLViewerInventoryCategory* category)
{
    //LL_INFOS(LOG_INV) << "LLInventoryModel::addCategory()" << LL_ENDL;
    if(category)
    {
        // We aren't displaying the Meshes folder
        if (category->mPreferredType == LLFolderType::FT_MESH)
        {
            return;
        }

        // try to localize default names first. See EXT-8319, EXT-7051.
        category->localizeName();

        // Insert category uniquely into the map
        mCategoryMap[category->getUUID()] = category; // LLPointer will deref and delete the old one
        //mInventory[category->getUUID()] = category;
    }
}

bool LLInventoryModel::hasBacklinkInfo(const LLUUID& link_id, const LLUUID& target_id) const
{
    std::pair <backlink_mmap_t::const_iterator, backlink_mmap_t::const_iterator> range;
    range = mBacklinkMMap.equal_range(target_id);
    for (backlink_mmap_t::const_iterator it = range.first; it != range.second; ++it)
    {
        if (it->second == link_id)
        {
            return true;
        }
    }
    return false;
}

void LLInventoryModel::addBacklinkInfo(const LLUUID& link_id, const LLUUID& target_id)
{
    if (!hasBacklinkInfo(link_id, target_id))
    {
        mBacklinkMMap.insert(std::make_pair(target_id, link_id));
    }
}

void LLInventoryModel::removeBacklinkInfo(const LLUUID& link_id, const LLUUID& target_id)
{
    std::pair <backlink_mmap_t::iterator, backlink_mmap_t::iterator> range;
    range = mBacklinkMMap.equal_range(target_id);
    for (backlink_mmap_t::iterator it = range.first; it != range.second; )
    {
        if (it->second == link_id)
        {
            backlink_mmap_t::iterator delete_it = it; // iterator will be invalidated by erase.
            ++it;
            mBacklinkMMap.erase(delete_it);
        }
        else
        {
            ++it;
        }
    }
}

void LLInventoryModel::addItem(LLViewerInventoryItem* item)
{
    llassert(item);
    if(item)
    {
        if (item->getType() <= LLAssetType::AT_NONE)
        {
            LL_WARNS(LOG_INV) << "Got bad asset type for item [ name: " << item->getName()
                              << " type: " << item->getType()
                              << " inv-type: " << item->getInventoryType() << " ], ignoring." << LL_ENDL;
            return;
        }

        if (LLAssetType::lookup(item->getType()) == LLAssetType::BADLOOKUP)
        {
            if (item->getType() >= LLAssetType::AT_COUNT)
            {
                // Not yet supported.
                LL_DEBUGS(LOG_INV) << "Got unknown asset type for item [ name: " << item->getName()
                    << " type: " << item->getType()
                    << " inv-type: " << item->getInventoryType() << " ]." << LL_ENDL;
            }
            else
            {
                LL_WARNS(LOG_INV) << "Got unknown asset type for item [ name: " << item->getName()
                    << " type: " << item->getType()
                    << " inv-type: " << item->getInventoryType() << " ]." << LL_ENDL;
            }
        }

        // This condition means that we tried to add a link without the baseobj being in memory.
        // The item will show up as a broken link.
        if (item->getIsBrokenLink())
        {
            if (item->getAssetUUID().notNull()
                && LLInventoryModelBackgroundFetch::getInstance()->folderFetchActive())
            {
                // Schedule this link for a recheck as inventory gets loaded
                // Todo: expand to cover not just an initial fetch
                mPossiblyBrockenLinks[item->getAssetUUID()].insert(item->getUUID());

                // Do a blank rebuild of links once fetch is done
                if (!mBulkFecthCallbackSlot.connected())
                {
                    // Links might take a while to update this way, and there
                    // might be a lot of them. A better option might be to check
                    // links periodically with final check on fetch completion.
                    mBulkFecthCallbackSlot =
                        LLInventoryModelBackgroundFetch::getInstance()->setFetchCompletionCallback(
                            [this]()
                    {
                        // rebuild is just in case, primary purpose is to wipe
                        // the list since we won't be getting anything 'new'
                        // see mLinksRebuildList
                        rebuildBrockenLinks();
                        mBulkFecthCallbackSlot.disconnect();
                    });
                }
                LL_DEBUGS(LOG_INV) << "Scheduling a link to be rebuilt later [ name: " << item->getName()
                    << " itemID: " << item->getUUID()
                    << " assetID: " << item->getAssetUUID() << " )  parent: " << item->getParentUUID() << LL_ENDL;

            }
            else
            {
                LL_INFOS(LOG_INV) << "Adding broken link [ name: " << item->getName()
                    << " itemID: " << item->getUUID()
                    << " assetID: " << item->getAssetUUID() << " )  parent: " << item->getParentUUID() << LL_ENDL;
            }
        }
        if (!mPossiblyBrockenLinks.empty())
        {
            // check if we are waiting for this item
            broken_links_t::iterator iter = mPossiblyBrockenLinks.find(item->getUUID());
            if (iter != mPossiblyBrockenLinks.end())
            {
                mLinksRebuildList.insert(iter->second.begin() , iter->second.end());
                mPossiblyBrockenLinks.erase(iter);
            }
        }
        if (item->getIsLinkType())
        {
            // Add back-link from linked-to UUID.
            const LLUUID& link_id = item->getUUID();
            const LLUUID& target_id = item->getLinkedUUID();
            addBacklinkInfo(link_id, target_id);
        }
        mItemMap[item->getUUID()] = item;
    }
}

// Empty the entire contents
void LLInventoryModel::empty()
{
//  LL_INFOS(LOG_INV) << "LLInventoryModel::empty()" << LL_ENDL;
    std::for_each(
        mParentChildCategoryTree.begin(),
        mParentChildCategoryTree.end(),
        DeletePairedPointer());
    mParentChildCategoryTree.clear();
    std::for_each(
        mParentChildItemTree.begin(),
        mParentChildItemTree.end(),
        DeletePairedPointer());
    mParentChildItemTree.clear();
    mBacklinkMMap.clear(); // forget all backlink information.
    mCategoryMap.clear(); // remove all references (should delete entries)
    mItemMap.clear(); // remove all references (should delete entries)
    mLastItem = NULL;
    //mInventory.clear();
}

void LLInventoryModel::accountForUpdate(const LLCategoryUpdate& update) const
{
    LLViewerInventoryCategory* cat = getCategory(update.mCategoryID);
    if(cat)
    {
        S32 version = cat->getVersion();
        if(version != LLViewerInventoryCategory::VERSION_UNKNOWN)
        {
            S32 descendents_server = cat->getDescendentCount();
            S32 descendents_actual = cat->getViewerDescendentCount();
            if(descendents_server == descendents_actual)
            {
                descendents_actual += update.mDescendentDelta;
                cat->setDescendentCount(descendents_actual);
                if (update.mChangeVersion)
                {
                cat->setVersion(++version);
                }
                LL_DEBUGS(LOG_INV) << "accounted: '" << cat->getName() << "' "
                                   << version << " with " << descendents_actual
                                   << " descendents." << LL_ENDL;
            }
            else
            {
                // Error condition, this means that the category did not register that
                // it got new descendents (perhaps because it is still being loaded)
                // which means its descendent count will be wrong.
                LL_WARNS(LOG_INV) << "Accounting failed for '" << cat->getName() << "' version:"
                                  << version << " due to mismatched descendent count:  server == "
                                  << descendents_server << ", viewer == " << descendents_actual << LL_ENDL;
            }
        }
        else
        {
            LL_WARNS(LOG_INV) << "Accounting failed for '" << cat->getName() << "' version: unknown ("
                              << version << ")" << LL_ENDL;
        }
    }
    else
    {
        LL_WARNS(LOG_INV) << "No category found for update " << update.mCategoryID << LL_ENDL;
    }
}

void LLInventoryModel::accountForUpdate(
    const LLInventoryModel::update_list_t& update) const
{
    update_list_t::const_iterator it = update.begin();
    update_list_t::const_iterator end = update.end();
    for(; it != end; ++it)
    {
        accountForUpdate(*it);
    }
}

void LLInventoryModel::accountForUpdate(
    const LLInventoryModel::update_map_t& update) const
{
    LLCategoryUpdate up;
    update_map_t::const_iterator it = update.begin();
    update_map_t::const_iterator end = update.end();
    for(; it != end; ++it)
    {
        up.mCategoryID = (*it).first;
        up.mDescendentDelta = (*it).second.mValue;
        accountForUpdate(up);
    }
}

LLInventoryModel::EHasChildren LLInventoryModel::categoryHasChildren(
    const LLUUID& cat_id) const
{
    LLViewerInventoryCategory* cat = getCategory(cat_id);
    if(!cat) return CHILDREN_NO;
    if(cat->getDescendentCount() > 0)
    {
        return CHILDREN_YES;
    }
    if(cat->getDescendentCount() == 0)
    {
        return CHILDREN_NO;
    }
    if((cat->getDescendentCount() == LLViewerInventoryCategory::DESCENDENT_COUNT_UNKNOWN)
       || (cat->getVersion() == LLViewerInventoryCategory::VERSION_UNKNOWN))
    {
        return CHILDREN_MAYBE;
    }

    // Shouldn't have to run this, but who knows.
    parent_cat_map_t::const_iterator cat_it = mParentChildCategoryTree.find(cat->getUUID());
    if (cat_it != mParentChildCategoryTree.end() && cat_it->second->size() > 0)
    {
        return CHILDREN_YES;
    }
    parent_item_map_t::const_iterator item_it = mParentChildItemTree.find(cat->getUUID());
    if (item_it != mParentChildItemTree.end() && item_it->second->size() > 0)
    {
        return CHILDREN_YES;
    }

    return CHILDREN_NO;
}

bool LLInventoryModel::isCategoryComplete(const LLUUID& cat_id) const
{
    LLViewerInventoryCategory* cat = getCategory(cat_id);
    if(cat && (cat->getVersion()!=LLViewerInventoryCategory::VERSION_UNKNOWN))
    {
        S32 descendents_server = cat->getDescendentCount();
        S32 descendents_actual = cat->getViewerDescendentCount();
        if(descendents_server == descendents_actual)
        {
            return true;
        }
    }
    return false;
}

bool LLInventoryModel::loadSkeleton(
    const LLSD& options,
    const LLUUID& owner_id)
{
    LL_PROFILE_ZONE_SCOPED;
    LL_DEBUGS(LOG_INV) << "importing inventory skeleton for " << owner_id << LL_ENDL;

    typedef std::set<LLPointer<LLViewerInventoryCategory>, InventoryIDPtrLess> cat_set_t;
    cat_set_t temp_cats;
    bool rv = true;

    for(LLSD::array_const_iterator it = options.beginArray(),
        end = options.endArray(); it != end; ++it)
    {
        LLSD name = (*it)["name"];
        LLSD folder_id = (*it)["folder_id"];
        LLSD parent_id = (*it)["parent_id"];
        LLSD version = (*it)["version"];
        if(name.isDefined()
            && folder_id.isDefined()
            && parent_id.isDefined()
            && version.isDefined()
            && folder_id.asUUID().notNull() // if an id is null, it locks the viewer.
            )
        {
            LLPointer<LLViewerInventoryCategory> cat = new LLViewerInventoryCategory(owner_id);
            cat->rename(name.asString());
            cat->setUUID(folder_id.asUUID());
            cat->setParent(parent_id.asUUID());

            LLFolderType::EType preferred_type = LLFolderType::FT_NONE;
            LLSD type_default = (*it)["type_default"];
            if(type_default.isDefined())
            {
                preferred_type = (LLFolderType::EType)type_default.asInteger();
            }
            cat->setPreferredType(preferred_type);
            cat->setVersion(version.asInteger());
            temp_cats.insert(cat);
        }
        else
        {
            LL_WARNS(LOG_INV) << "Unable to import near " << name.asString() << LL_ENDL;
            rv = false;
        }
    }

    S32 cached_category_count = 0;
    S32 cached_item_count = 0;
    if(!temp_cats.empty())
    {
        update_map_t child_counts;
        cat_array_t categories;
        item_array_t items;
        changed_items_t categories_to_update;
        item_array_t possible_broken_links;
        cat_set_t invalid_categories; // Used to mark categories that weren't successfully loaded.
        std::string inventory_filename = getInvCacheAddres(owner_id);
        const S32 NO_VERSION = LLViewerInventoryCategory::VERSION_UNKNOWN;
        std::string gzip_filename(inventory_filename);
        gzip_filename.append(".gz");
        LLFILE* fp = LLFile::fopen(gzip_filename, "rb");
        bool remove_inventory_file = false;
        if (LLAppViewer::instance()->isSecondInstance())
        {
            // Safeguard viewer against trying to unpack file twice
            // ex: user logs into two accounts simultaneously, so two
            // viewers are trying to unpack library into same file
            //
            // Would be better to do it in gunzip_file, but it doesn't
            // have access to llfilesystem
            inventory_filename = gDirUtilp->getTempFilename();
            remove_inventory_file = true;
        }
        if(fp)
        {
            fclose(fp);
            fp = NULL;
            if(gunzip_file(gzip_filename, inventory_filename))
            {
                // we only want to remove the inventory file if it was
                // gzipped before we loaded, and we successfully
                // gunziped it.
                remove_inventory_file = true;
            }
            else
            {
                LL_INFOS(LOG_INV) << "Unable to gunzip " << gzip_filename << LL_ENDL;
            }
        }
        bool is_cache_obsolete = false;
        if (loadFromFile(inventory_filename, categories, items, categories_to_update, is_cache_obsolete))
        {
            // We were able to find a cache of files. So, use what we
            // found to generate a set of categories we should add. We
            // will go through each category loaded and if the version
            // does not match, invalidate the version.
            S32 count = categories.size();
            cat_set_t::iterator not_cached = temp_cats.end();
            std::set<LLUUID> cached_ids;
            for(S32 i = 0; i < count; ++i)
            {
                LLViewerInventoryCategory* cat = categories[i];
                cat_set_t::iterator cit = temp_cats.find(cat);
                if (cit == temp_cats.end())
                {
                    continue; // cache corruption?? not sure why this happens -SJB
                }
                LLViewerInventoryCategory* tcat = *cit;

                if (categories_to_update.find(tcat->getUUID()) != categories_to_update.end())
                {
                    tcat->setVersion(NO_VERSION);
                    LL_WARNS() << "folder to update: " << tcat->getName() << LL_ENDL;
                }

                // we can safely ignore anything loaded from file, but
                // not sent down in the skeleton. Must have been removed from inventory.
                if (cit == not_cached)
                {
                    continue;
                }
                else if (cat->getVersion() != tcat->getVersion())
                {
                    // if the cached version does not match the server version,
                    // throw away the version we have so we can fetch the
                    // correct contents the next time the viewer opens the folder.
                    tcat->setVersion(NO_VERSION);
                }
                else
                {
                    cached_ids.insert(tcat->getUUID());

                    // At the moment download does not provide a thumbnail
                    // uuid, use the one from cache
                    tcat->setThumbnailUUID(cat->getThumbnailUUID());
                }
            }

            // go ahead and add the cats returned during the download
            std::set<LLUUID>::const_iterator not_cached_id = cached_ids.end();
            cached_category_count = cached_ids.size();
            for(cat_set_t::iterator it = temp_cats.begin(); it != temp_cats.end(); ++it)
            {
                if(cached_ids.find((*it)->getUUID()) == not_cached_id)
                {
                    // this check is performed so that we do not
                    // mark new folders in the skeleton (and not in cache)
                    // as being cached.
                    LLViewerInventoryCategory *llvic = (*it);
                    llvic->setVersion(NO_VERSION);
                }
                addCategory(*it);
                ++child_counts[(*it)->getParentUUID()];
            }

            // Add all the items loaded which are parented to a
            // category with a correctly cached parent
            S32 bad_link_count = 0;
            S32 good_link_count = 0;
            S32 recovered_link_count = 0;
            cat_map_t::iterator unparented = mCategoryMap.end();
            for(item_array_t::const_iterator item_iter = items.begin();
                item_iter != items.end();
                ++item_iter)
            {
                LLViewerInventoryItem *item = (*item_iter).get();
                const cat_map_t::iterator cit = mCategoryMap.find(item->getParentUUID());

                if(cit != unparented)
                {
                    const LLViewerInventoryCategory* cat = cit->second.get();
                    if(cat->getVersion() != NO_VERSION)
                    {
                        // This can happen if the linked object's baseobj is removed from the cache but the linked object is still in the cache.
                        if (item->getIsBrokenLink())
                        {
                            //bad_link_count++;
                            LL_DEBUGS(LOG_INV) << "Attempted to add cached link item without baseobj present ( name: "
                                               << item->getName() << " itemID: " << item->getUUID()
                                               << " assetID: " << item->getAssetUUID()
                                               << " ).  Ignoring and invalidating " << cat->getName() << " . " << LL_ENDL;
                            possible_broken_links.push_back(item);
                            continue;
                        }
                        else if (item->getIsLinkType())
                        {
                            good_link_count++;
                        }
                        addItem(item);
                        cached_item_count += 1;
                        ++child_counts[cat->getUUID()];
                    }
                }
            }
            if (possible_broken_links.size() > 0)
            {
                for(item_array_t::const_iterator item_iter = possible_broken_links.begin();
                    item_iter != possible_broken_links.end();
                    ++item_iter)
                {
                    LLViewerInventoryItem *item = (*item_iter).get();
                    const cat_map_t::iterator cit = mCategoryMap.find(item->getParentUUID());
                    const LLViewerInventoryCategory* cat = cit->second.get();
                    if (item->getIsBrokenLink())
                    {
                        bad_link_count++;
                        invalid_categories.insert(cit->second);
                        //LL_INFOS(LOG_INV) << "link still broken: " << item->getName() << " in folder " << cat->getName() << LL_ENDL;
                    }
                    else
                    {
                        // was marked as broken because of loading order, its actually fine to load
                        addItem(item);
                        cached_item_count += 1;
                        ++child_counts[cat->getUUID()];
                        recovered_link_count++;
                    }
                }

                LL_DEBUGS(LOG_INV) << "Attempted to add " << bad_link_count
                                   << " cached link items without baseobj present. "
                                   << good_link_count << " link items were successfully added. "
                                   << recovered_link_count << " links added in recovery. "
                                   << "The corresponding categories were invalidated." << LL_ENDL;
            }

        }
        else
        {
            // go ahead and add everything after stripping the version
            // information.
            for(cat_set_t::iterator it = temp_cats.begin(); it != temp_cats.end(); ++it)
            {
                LLViewerInventoryCategory *llvic = (*it);
                llvic->setVersion(NO_VERSION);
                addCategory(*it);
            }
        }

        // Invalidate all categories that failed fetching descendents for whatever
        // reason (e.g. one of the descendents was a broken link).
        for (cat_set_t::iterator invalid_cat_it = invalid_categories.begin();
             invalid_cat_it != invalid_categories.end();
             invalid_cat_it++)
        {
            LLViewerInventoryCategory* cat = (*invalid_cat_it).get();
            cat->setVersion(NO_VERSION);
            LL_DEBUGS(LOG_INV) << "Invalidating category name: " << cat->getName() << " UUID: " << cat->getUUID() << " due to invalid descendents cache" << LL_ENDL;
        }
        if (invalid_categories.size() > 0)
        {
            LL_DEBUGS(LOG_INV) << "Invalidated " << invalid_categories.size() << " categories due to invalid descendents cache" << LL_ENDL;
        }

        // At this point, we need to set the known descendents for each
        // category which successfully cached so that we do not
        // needlessly fetch descendents for categories which we have.
        update_map_t::const_iterator no_child_counts = child_counts.end();
        for(cat_set_t::iterator it = temp_cats.begin(); it != temp_cats.end(); ++it)
        {
            LLViewerInventoryCategory* cat = (*it).get();
            if(cat->getVersion() != NO_VERSION)
            {
                update_map_t::const_iterator the_count = child_counts.find(cat->getUUID());
                if(the_count != no_child_counts)
                {
                    const S32 num_descendents = (*the_count).second.mValue;
                    cat->setDescendentCount(num_descendents);
                }
                else
                {
                    cat->setDescendentCount(0);
                }
            }
        }

        if(remove_inventory_file)
        {
            // clean up the gunzipped file.
            LLFile::remove(inventory_filename);
        }
        if(is_cache_obsolete && !LLAppViewer::instance()->isSecondInstance())
        {
            // If out of date, remove the gzipped file too.
            LL_WARNS(LOG_INV) << "Inv cache out of date, removing" << LL_ENDL;
            LLFile::remove(gzip_filename);
        }
        categories.clear(); // will unref and delete entries
    }

    LL_INFOS(LOG_INV) << "Successfully loaded " << cached_category_count
                      << " categories and " << cached_item_count << " items from cache."
                      << LL_ENDL;

    return rv;
}

// This is a brute force method to rebuild the entire parent-child
// relations. The overall operation has O(NlogN) performance, which
// should be sufficient for our needs.
void LLInventoryModel::buildParentChildMap()
{
    LL_INFOS(LOG_INV) << "LLInventoryModel::buildParentChildMap()" << LL_ENDL;

    // *NOTE: I am skipping the logic around folder version
    // synchronization here because it seems if a folder is lost, we
    // might actually want to invalidate it at that point - not
    // attempt to cache. More time & thought is necessary.

    // First the categories. We'll copy all of the categories into a
    // temporary container to iterate over (oh for real iterators.)
    // While we're at it, we'll allocate the arrays in the trees.
    cat_array_t cats;
    cat_array_t* catsp;
    item_array_t* itemsp;

    for(cat_map_t::iterator cit = mCategoryMap.begin(); cit != mCategoryMap.end(); ++cit)
    {
        LLViewerInventoryCategory* cat = cit->second;
        cats.push_back(cat);
        if (mParentChildCategoryTree.count(cat->getUUID()) == 0)
        {
            llassert_always(mCategoryLock[cat->getUUID()] == false);
            catsp = new cat_array_t;
            mParentChildCategoryTree[cat->getUUID()] = catsp;
        }
        if (mParentChildItemTree.count(cat->getUUID()) == 0)
        {
            llassert_always(mItemLock[cat->getUUID()] == false);
            itemsp = new item_array_t;
            mParentChildItemTree[cat->getUUID()] = itemsp;
        }
    }

    // Insert a special parent for the root - so that lookups on
    // LLUUID::null as the parent work correctly. This is kind of a
    // blatent wastes of space since we allocate a block of memory for
    // the array, but whatever - it's not that much space.
    if (mParentChildCategoryTree.count(LLUUID::null) == 0)
    {
        catsp = new cat_array_t;
        mParentChildCategoryTree[LLUUID::null] = catsp;
    }

    // Now we have a structure with all of the categories that we can
    // iterate over and insert into the correct place in the child
    // category tree.
    S32 count = cats.size();
    S32 i;
    S32 lost = 0;
    cat_array_t lost_cats;
    for(i = 0; i < count; ++i)
    {
        LLViewerInventoryCategory* cat = cats.at(i);
        catsp = getUnlockedCatArray(cat->getParentUUID());
        if(catsp &&
           // Only the two root folders should be children of null.
           // Others should go to lost & found.
           (cat->getParentUUID().notNull() ||
            cat->getPreferredType() == LLFolderType::FT_ROOT_INVENTORY ))
        {
            catsp->push_back(cat);
        }
        else
        {
            // *NOTE: This process could be a lot more efficient if we
            // used the new MoveInventoryFolder message, but we would
            // have to continue to do the update & build here. So, to
            // implement it, we would need a set or map of uuid pairs
            // which would be (folder_id, new_parent_id) to be sent up
            // to the server.
            LL_INFOS(LOG_INV) << "Lost category: " << cat->getUUID() << " - "
                              << cat->getName() << LL_ENDL;
            ++lost;
            lost_cats.push_back(cat);
        }
    }
    if(lost)
    {
        LL_WARNS(LOG_INV) << "Found  " << lost << " lost categories." << LL_ENDL;
    }

    // Do moves in a separate pass to make sure we've properly filed
    // the FT_LOST_AND_FOUND category before we try to find its UUID.
    for(i = 0; i<lost_cats.size(); ++i)
    {
        LLViewerInventoryCategory *cat = lost_cats.at(i);

        // plop it into the lost & found.
        LLFolderType::EType pref = cat->getPreferredType();
        if(LLFolderType::FT_NONE == pref)
        {
            cat->setParent(findCategoryUUIDForType(LLFolderType::FT_LOST_AND_FOUND));
        }
        else if(LLFolderType::FT_ROOT_INVENTORY == pref)
        {
            // it's the root
            cat->setParent(LLUUID::null);
        }
        else
        {
            // it's a protected folder.
            cat->setParent(gInventory.getRootFolderID());
        }
        // FIXME note that updateServer() fails with protected
        // types, so this will not work as intended in that case.
        // UpdateServer uses AIS, AIS cat move is not implemented yet
        // cat->updateServer(TRUE);

        // MoveInventoryFolder message, intentionally per item
        cat->updateParentOnServer(FALSE);
        catsp = getUnlockedCatArray(cat->getParentUUID());
        if(catsp)
        {
            catsp->push_back(cat);
        }
        else
        {
            LL_WARNS(LOG_INV) << "Lost and found Not there!!" << LL_ENDL;
        }
    }

    const BOOL COF_exists = (findCategoryUUIDForType(LLFolderType::FT_CURRENT_OUTFIT) != LLUUID::null);
    sFirstTimeInViewer2 = !COF_exists || gAgent.isFirstLogin();


    // Now the items. We allocated in the last step, so now all we
    // have to do is iterate over the items and put them in the right
    // place.
    item_array_t items;
    if(!mItemMap.empty())
    {
        LLPointer<LLViewerInventoryItem> item;
        for(item_map_t::iterator iit = mItemMap.begin(); iit != mItemMap.end(); ++iit)
        {
            item = (*iit).second;
            items.push_back(item);
        }
    }
    count = items.size();
    lost = 0;
    uuid_vec_t lost_item_ids;
    for(i = 0; i < count; ++i)
    {
        LLPointer<LLViewerInventoryItem> item;
        item = items.at(i);
        itemsp = getUnlockedItemArray(item->getParentUUID());
        if(itemsp)
        {
            itemsp->push_back(item);
        }
        else
        {
            LL_INFOS(LOG_INV) << "Lost item: " << item->getUUID() << " - "
                              << item->getName() << LL_ENDL;
            ++lost;
            // plop it into the lost & found.
            //
            item->setParent(findCategoryUUIDForType(LLFolderType::FT_LOST_AND_FOUND));
            // move it later using a special message to move items. If
            // we update server here, the client might crash.
            //item->updateServer();
            lost_item_ids.push_back(item->getUUID());
            itemsp = getUnlockedItemArray(item->getParentUUID());
            if(itemsp)
            {
                itemsp->push_back(item);
            }
            else
            {
                LL_WARNS(LOG_INV) << "Lost and found Not there!!" << LL_ENDL;
            }
        }
    }
    if(lost)
    {
        LL_WARNS(LOG_INV) << "Found " << lost << " lost items." << LL_ENDL;
        LLMessageSystem* msg = gMessageSystem;
        BOOL start_new_message = TRUE;
        const LLUUID lnf = findCategoryUUIDForType(LLFolderType::FT_LOST_AND_FOUND);
        for(uuid_vec_t::iterator it = lost_item_ids.begin() ; it < lost_item_ids.end(); ++it)
        {
            if(start_new_message)
            {
                start_new_message = FALSE;
                msg->newMessageFast(_PREHASH_MoveInventoryItem);
                msg->nextBlockFast(_PREHASH_AgentData);
                msg->addUUIDFast(_PREHASH_AgentID, gAgent.getID());
                msg->addUUIDFast(_PREHASH_SessionID, gAgent.getSessionID());
                msg->addBOOLFast(_PREHASH_Stamp, FALSE);
            }
            msg->nextBlockFast(_PREHASH_InventoryData);
            msg->addUUIDFast(_PREHASH_ItemID, (*it));
            msg->addUUIDFast(_PREHASH_FolderID, lnf);
            msg->addString("NewName", NULL);
            if(msg->isSendFull(NULL))
            {
                start_new_message = TRUE;
                gAgent.sendReliableMessage();
            }
        }
        if(!start_new_message)
        {
            gAgent.sendReliableMessage();
        }
    }

    const LLUUID &agent_inv_root_id = gInventory.getRootFolderID();
    if (agent_inv_root_id.notNull())
    {
        cat_array_t* catsp = get_ptr_in_map(mParentChildCategoryTree, agent_inv_root_id);
        if(catsp)
        {
            // *HACK - fix root inventory folder
            // some accounts has pbroken inventory root folders

            std::string name = "My Inventory";
            for (parent_cat_map_t::const_iterator it = mParentChildCategoryTree.begin(),
                     it_end = mParentChildCategoryTree.end(); it != it_end; ++it)
            {
                cat_array_t* cat_array = it->second;
                for (cat_array_t::const_iterator cat_it = cat_array->begin(),
                         cat_it_end = cat_array->end(); cat_it != cat_it_end; ++cat_it)
                    {
                    LLPointer<LLViewerInventoryCategory> category = *cat_it;

                    if(category && category->getPreferredType() != LLFolderType::FT_ROOT_INVENTORY)
                        continue;
                    if ( category && 0 == LLStringUtil::compareInsensitive(name, category->getName()) )
                    {
                        if(category->getUUID()!=mRootFolderID)
                        {
                            LLUUID& new_inv_root_folder_id = const_cast<LLUUID&>(mRootFolderID);
                            new_inv_root_folder_id = category->getUUID();
                        }
                    }
                }
            }

            LLPointer<LLInventoryValidationInfo> validation_info = validate();
            if (validation_info->mFatalErrorCount > 0)
            {
                // Fatal inventory error. Will not be able to engage in many inventory operations.
                // This should be followed by an error dialog leading to logout.
                LL_WARNS("Inventory") << "Fatal errors were found in validate(): unable to initialize inventory! "
                                      << "Will not be able to do normal inventory operations in this session."
                                      << LL_ENDL;
                mIsAgentInvUsable = false;
            }
            else
            {
                mIsAgentInvUsable = true;
            }
            validation_info->mInitialized = true;
            mValidationInfo = validation_info;

            // notifyObservers() has been moved to
            // llstartup/idle_startup() after this func completes.
            // Allows some system categories to be created before
            // observers start firing.
        }
    }
}

// Would normally do this at construction but that's too early
// in the process for gInventory.  Have the first requestPost()
// call set things up.
void LLInventoryModel::initHttpRequest()
{
    if (! mHttpRequestFG)
    {
        // Haven't initialized, get to it
        LLAppCoreHttp & app_core_http(LLAppViewer::instance()->getAppCoreHttp());

        mHttpRequestFG = new LLCore::HttpRequest;
        mHttpRequestBG = new LLCore::HttpRequest;
        mHttpOptions = LLCore::HttpOptions::ptr_t(new LLCore::HttpOptions);
        mHttpOptions->setTransferTimeout(300);
        mHttpOptions->setUseRetryAfter(true);
        // mHttpOptions->setTrace(2);       // Do tracing of requests
        mHttpHeaders = LLCore::HttpHeaders::ptr_t(new LLCore::HttpHeaders);
        mHttpHeaders->append(HTTP_OUT_HEADER_CONTENT_TYPE, HTTP_CONTENT_LLSD_XML);
        mHttpHeaders->append(HTTP_OUT_HEADER_ACCEPT, HTTP_CONTENT_LLSD_XML);
        mHttpPolicyClass = app_core_http.getPolicy(LLAppCoreHttp::AP_INVENTORY);
    }

    if (!gGenericDispatcher.isHandlerPresent("BulkUpdateInventory"))
    {
        gGenericDispatcher.addHandler("BulkUpdateInventory", &sBulkUpdateInventory);
    }
}

void LLInventoryModel::handleResponses(bool foreground)
{
    if (foreground && mHttpRequestFG)
    {
        mHttpRequestFG->update(0);
    }
    else if (! foreground && mHttpRequestBG)
    {
        mHttpRequestBG->update(50000L);
    }
}

LLCore::HttpHandle LLInventoryModel::requestPost(bool foreground,
                                                 const std::string & url,
                                                 const LLSD & body,
                                                 const LLCore::HttpHandler::ptr_t &handler,
                                                 const char * const message)
{
    if (! mHttpRequestFG)
    {
        // We do the initialization late and lazily as this class is
        // statically-constructed and not all the bits are ready at
        // that time.
        initHttpRequest();
    }

    LLCore::HttpRequest * request(foreground ? mHttpRequestFG : mHttpRequestBG);
    LLCore::HttpHandle handle(LLCORE_HTTP_HANDLE_INVALID);

    handle = LLCoreHttpUtil::requestPostWithLLSD(request,
                                                 mHttpPolicyClass,
                                                 url,
                                                 body,
                                                 mHttpOptions,
                                                 mHttpHeaders,
                                                 handler);
    if (LLCORE_HTTP_HANDLE_INVALID == handle)
    {
        LLCore::HttpStatus status(request->getStatus());
        LL_WARNS(LOG_INV) << "HTTP POST request failed for " << message
                          << ", Status: " << status.toTerseString()
                          << " Reason: '" << status.toString() << "'"
                          << LL_ENDL;
    }
    return handle;
}

void LLInventoryModel::createCommonSystemCategories()
{
    //amount of System Folder we should wait for
    sPendingSystemFolders = 9;

    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_TRASH);
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_FAVORITE);
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_CALLINGCARD);
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_MY_OUTFITS);
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_CURRENT_OUTFIT);
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_LANDMARK); // folder should exist before user tries to 'landmark this'
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_SETTINGS);
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_MATERIAL); // probably should be server created
    gInventory.ensureCategoryForTypeExists(LLFolderType::FT_INBOX);
}

struct LLUUIDAndName
{
    LLUUIDAndName() {}
    LLUUIDAndName(const LLUUID& id, const std::string& name);
    bool operator==(const LLUUIDAndName& rhs) const;
    bool operator<(const LLUUIDAndName& rhs) const;
    bool operator>(const LLUUIDAndName& rhs) const;

    LLUUID mID;
    std::string mName;
};

LLUUIDAndName::LLUUIDAndName(const LLUUID& id, const std::string& name) :
    mID(id), mName(name)
{
}

bool LLUUIDAndName::operator==(const LLUUIDAndName& rhs) const
{
    return ((mID == rhs.mID) && (mName == rhs.mName));
}

bool LLUUIDAndName::operator<(const LLUUIDAndName& rhs) const
{
    return (mID < rhs.mID);
}

bool LLUUIDAndName::operator>(const LLUUIDAndName& rhs) const
{
    return (mID > rhs.mID);
}

// static
bool LLInventoryModel::loadFromFile(const std::string& filename,
                                    LLInventoryModel::cat_array_t& categories,
                                    LLInventoryModel::item_array_t& items,
                                    LLInventoryModel::changed_items_t& cats_to_update,
                                    bool &is_cache_obsolete)
{
    LL_PROFILE_ZONE_NAMED("inventory load from file");

    if(filename.empty())
    {
        LL_ERRS(LOG_INV) << "filename is Null!" << LL_ENDL;
        return false;
    }
    LL_INFOS(LOG_INV) << "loading inventory from: (" << filename << ")" << LL_ENDL;

    llifstream file(filename.c_str());

    if (!file.is_open())
    {
        LL_INFOS(LOG_INV) << "unable to load inventory from: " << filename << LL_ENDL;
        return false;
    }

    is_cache_obsolete = true; // Obsolete until proven current

    //U64 lines_count = 0U;
    std::string line;
    LLPointer<LLSDParser> parser = new LLSDNotationParser();
    while (std::getline(file, line))
    {
        LLSD s_item;
        std::istringstream iss(line);
        if (parser->parse(iss, s_item, line.length()) == LLSDParser::PARSE_FAILURE)
        {
            LL_WARNS(LOG_INV)<< "Parsing inventory cache failed" << LL_ENDL;
            break;
        }

        if (s_item.has("inv_cache_version"))
        {
            S32 version = s_item["inv_cache_version"].asInteger();
            if (version == sCurrentInvCacheVersion)
            {
                // Cache is up to date
                is_cache_obsolete = false;
                continue;
            }
            else
            {
                LL_WARNS(LOG_INV)<< "Inventory cache is out of date" << LL_ENDL;
                break;
            }
        }
        else if (s_item.has("cat_id"))
        {
            if (is_cache_obsolete)
                break;

            LLPointer<LLViewerInventoryCategory> inv_cat = new LLViewerInventoryCategory(LLUUID::null);
            if(inv_cat->importLLSD(s_item))
            {
                categories.push_back(inv_cat);
            }
        }
        else if (s_item.has("item_id"))
        {
            if (is_cache_obsolete)
                break;

            LLPointer<LLViewerInventoryItem> inv_item = new LLViewerInventoryItem;
            if( inv_item->fromLLSD(s_item) )
            {
                if(inv_item->getUUID().isNull())
                {
                    LL_DEBUGS(LOG_INV) << "Ignoring inventory with null item id: "
                        << inv_item->getName() << LL_ENDL;
                }
                else
                {
                    if (inv_item->getType() == LLAssetType::AT_UNKNOWN)
                    {
                        cats_to_update.insert(inv_item->getParentUUID());
                    }
                    else
                    {
                        items.push_back(inv_item);
                    }
                }
            }
        }

//      TODO(brad) - figure out how to reenable this without breaking everything else
//      static constexpr U64 BATCH_SIZE = 512U;
//      if ((++lines_count % BATCH_SIZE) == 0)
//      {
//          // SL-19968 - make sure message system code gets a chance to run every so often
//          pump_idle_startup_network();
//      }
    }

    file.close();

    return !is_cache_obsolete;
}

// static
bool LLInventoryModel::saveToFile(const std::string& filename,
    const cat_array_t& categories,
    const item_array_t& items)
{
    if (filename.empty())
    {
        LL_ERRS(LOG_INV) << "Filename is Null!" << LL_ENDL;
        return false;
    }

    LL_INFOS(LOG_INV) << "saving inventory to: (" << filename << ")" << LL_ENDL;

    try
    {
        llofstream fileXML(filename.c_str());
        if (!fileXML.is_open())
        {
            LL_WARNS(LOG_INV) << "Failed to open file. Unable to save inventory to: " << filename << LL_ENDL;
            return false;
        }

        LLSD cache_ver;
        cache_ver["inv_cache_version"] = sCurrentInvCacheVersion;

        if (fileXML.fail())
        {
            LL_WARNS(LOG_INV) << "Failed to write cache version to file. Unable to save inventory to: " << filename << LL_ENDL;
            return false;
        }

        fileXML << LLSDOStreamer<LLSDNotationFormatter>(cache_ver) << std::endl;

        S32 count = categories.size();
        S32 cat_count = 0;
        S32 i;
        for (i = 0; i < count; ++i)
        {
            LLViewerInventoryCategory* cat = categories[i];
            if (cat->getVersion() != LLViewerInventoryCategory::VERSION_UNKNOWN)
            {
                fileXML << LLSDOStreamer<LLSDNotationFormatter>(cat->exportLLSD()) << std::endl;
                cat_count++;
            }

            if (fileXML.fail())
            {
                LL_WARNS(LOG_INV) << "Failed to write a folder to file. Unable to save inventory to: " << filename << LL_ENDL;
                return false;
            }
        }

        S32 it_count = items.size();
        for (i = 0; i < it_count; ++i)
        {
            fileXML << LLSDOStreamer<LLSDNotationFormatter>(items[i]->asLLSD()) << std::endl;

            if (fileXML.fail())
            {
                LL_WARNS(LOG_INV) << "Failed to write an item to file. Unable to save inventory to: " << filename << LL_ENDL;
                return false;
            }
        }
        fileXML.flush();

        fileXML.close();

        LL_INFOS(LOG_INV) << "Inventory saved: " << cat_count << " categories, " << it_count << " items." << LL_ENDL;
    }
    catch (...)
    {
        LOG_UNHANDLED_EXCEPTION("");
        LL_INFOS(LOG_INV) << "Failed to save inventory to: (" << filename << ")" << LL_ENDL;
        return false;
    }

    return true;
}

// message handling functionality
// static
void LLInventoryModel::registerCallbacks(LLMessageSystem* msg)
{
    //msg->setHandlerFuncFast(_PREHASH_InventoryUpdate,
    //                  processInventoryUpdate,
    //                  NULL);
    //msg->setHandlerFuncFast(_PREHASH_UseCachedInventory,
    //                  processUseCachedInventory,
    //                  NULL);
    msg->setHandlerFuncFast(_PREHASH_UpdateCreateInventoryItem,
                        processUpdateCreateInventoryItem,
                        NULL);
    msg->setHandlerFuncFast(_PREHASH_RemoveInventoryItem,
                        processRemoveInventoryItem,
                        NULL);
    msg->setHandlerFuncFast(_PREHASH_RemoveInventoryFolder,
                        processRemoveInventoryFolder,
                        NULL);
    msg->setHandlerFuncFast(_PREHASH_RemoveInventoryObjects,
                            processRemoveInventoryObjects,
                            NULL);
    msg->setHandlerFuncFast(_PREHASH_SaveAssetIntoInventory,
                        processSaveAssetIntoInventory,
                        NULL);
    msg->setHandlerFuncFast(_PREHASH_BulkUpdateInventory,
                            processBulkUpdateInventory,
                            NULL);
    msg->setHandlerFunc("MoveInventoryItem", processMoveInventoryItem);
}


//  static
void LLInventoryModel::processUpdateCreateInventoryItem(LLMessageSystem* msg, void**)
{
    // do accounting and highlight new items if they arrive
    if (gInventory.messageUpdateCore(msg, true, LLInventoryObserver::UPDATE_CREATE))
    {
        U32 callback_id;
        LLUUID item_id;
        msg->getUUIDFast(_PREHASH_InventoryData, _PREHASH_ItemID, item_id);
        msg->getU32Fast(_PREHASH_InventoryData, _PREHASH_CallbackID, callback_id);

        gInventoryCallbacks.fire(callback_id, item_id);

        // Message system at the moment doesn't support Thumbnails and potential
        // newer features so just rerequest whole item
        //
        // todo: instead of unpacking message fully,
        // grab only an item_id, then fetch
        LLInventoryModelBackgroundFetch::instance().scheduleItemFetch(item_id, true);
    }

}

bool LLInventoryModel::messageUpdateCore(LLMessageSystem* msg, bool account, U32 mask)
{
    //make sure our added inventory observer is active
    start_new_inventory_observer();

    LLUUID agent_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS(LOG_INV) << "Got a inventory update for the wrong agent: " << agent_id
                          << LL_ENDL;
        return false;
    }
    item_array_t items;
    update_map_t update;
    S32 count = msg->getNumberOfBlocksFast(_PREHASH_InventoryData);
    // Does this loop ever execute more than once?
    for(S32 i = 0; i < count; ++i)
    {
        LLPointer<LLViewerInventoryItem> titem = new LLViewerInventoryItem;
        titem->unpackMessage(msg, _PREHASH_InventoryData, i);
        LL_DEBUGS(LOG_INV) << "LLInventoryModel::messageUpdateCore() item id: "
                           << titem->getUUID() << LL_ENDL;
        items.push_back(titem);
        // examine update for changes.
        LLViewerInventoryItem* itemp = gInventory.getItem(titem->getUUID());
        if(itemp)
        {
            if(titem->getParentUUID() == itemp->getParentUUID())
            {
                update[titem->getParentUUID()];
            }
            else
            {
                ++update[titem->getParentUUID()];
                --update[itemp->getParentUUID()];
            }
        }
        else
        {
            ++update[titem->getParentUUID()];
        }
    }
    if(account)
    {
        gInventory.accountForUpdate(update);
    }

    if (account)
    {
        mask |= LLInventoryObserver::CREATE;
    }
    //as above, this loop never seems to loop more than once per call
    for (item_array_t::iterator it = items.begin(); it != items.end(); ++it)
    {
        gInventory.updateItem(*it, mask);
    }
    gInventory.notifyObservers();
    gViewerWindow->getWindow()->decBusyCount();

    return true;
}

//  static
void LLInventoryModel::removeInventoryItem(LLUUID agent_id, LLMessageSystem* msg, const char* msg_label)
{
    LLUUID item_id;
    S32 count = msg->getNumberOfBlocksFast(msg_label);
    LL_DEBUGS(LOG_INV) << "Message has " << count << " item blocks" << LL_ENDL;
    uuid_vec_t item_ids;
    update_map_t update;
    for(S32 i = 0; i < count; ++i)
    {
        msg->getUUIDFast(msg_label, _PREHASH_ItemID, item_id, i);
        LL_DEBUGS(LOG_INV) << "Checking for item-to-be-removed " << item_id << LL_ENDL;
        LLViewerInventoryItem* itemp = gInventory.getItem(item_id);
        if(itemp)
        {
            LL_DEBUGS(LOG_INV) << "Item will be removed " << item_id << LL_ENDL;
            // we only bother with the delete and account if we found
            // the item - this is usually a back-up for permissions,
            // so frequently the item will already be gone.
            --update[itemp->getParentUUID()];
            item_ids.push_back(item_id);
        }
    }
    gInventory.accountForUpdate(update);
    for(uuid_vec_t::iterator it = item_ids.begin(); it != item_ids.end(); ++it)
    {
        LL_DEBUGS(LOG_INV) << "Calling deleteObject " << *it << LL_ENDL;
        gInventory.deleteObject(*it);
    }
}

//  static
void LLInventoryModel::processRemoveInventoryItem(LLMessageSystem* msg, void**)
{
    LL_DEBUGS(LOG_INV) << "LLInventoryModel::processRemoveInventoryItem()" << LL_ENDL;
    LLUUID agent_id, item_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS(LOG_INV) << "Got a RemoveInventoryItem for the wrong agent."
                          << LL_ENDL;
        return;
    }
    LLInventoryModel::removeInventoryItem(agent_id, msg, _PREHASH_InventoryData);
    gInventory.notifyObservers();
}

//  static
void LLInventoryModel::removeInventoryFolder(LLUUID agent_id,
                                             LLMessageSystem* msg)
{
    LLUUID folder_id;
    uuid_vec_t folder_ids;
    update_map_t update;
    S32 count = msg->getNumberOfBlocksFast(_PREHASH_FolderData);
    for(S32 i = 0; i < count; ++i)
    {
        msg->getUUIDFast(_PREHASH_FolderData, _PREHASH_FolderID, folder_id, i);
        LLViewerInventoryCategory* folderp = gInventory.getCategory(folder_id);
        if(folderp)
        {
            --update[folderp->getParentUUID()];
            folder_ids.push_back(folder_id);
        }
    }
    gInventory.accountForUpdate(update);
    for(uuid_vec_t::iterator it = folder_ids.begin(); it != folder_ids.end(); ++it)
    {
        gInventory.deleteObject(*it);
    }
}

//  static
void LLInventoryModel::processRemoveInventoryFolder(LLMessageSystem* msg,
                                                    void**)
{
    LL_DEBUGS() << "LLInventoryModel::processRemoveInventoryFolder()" << LL_ENDL;
    LLUUID agent_id, session_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_SessionID, session_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS() << "Got a RemoveInventoryFolder for the wrong agent."
        << LL_ENDL;
        return;
    }
    LLInventoryModel::removeInventoryFolder( agent_id, msg );
    gInventory.notifyObservers();
}

//  static
void LLInventoryModel::processRemoveInventoryObjects(LLMessageSystem* msg,
                                                    void**)
{
    LL_DEBUGS() << "LLInventoryModel::processRemoveInventoryObjects()" << LL_ENDL;
    LLUUID agent_id, session_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_SessionID, session_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS() << "Got a RemoveInventoryObjects for the wrong agent."
        << LL_ENDL;
        return;
    }
    LLInventoryModel::removeInventoryFolder( agent_id, msg );
    LLInventoryModel::removeInventoryItem( agent_id, msg, _PREHASH_ItemData );
    gInventory.notifyObservers();
}

//  static
void LLInventoryModel::processSaveAssetIntoInventory(LLMessageSystem* msg,
                                                     void**)
{
    LLUUID agent_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS() << "Got a SaveAssetIntoInventory message for the wrong agent."
                << LL_ENDL;
        return;
    }

    LLUUID item_id;
    msg->getUUIDFast(_PREHASH_InventoryData, _PREHASH_ItemID, item_id);

    // The viewer ignores the asset id because this message is only
    // used for attachments/objects, so the asset id is not used in
    // the viewer anyway.
    LL_DEBUGS() << "LLInventoryModel::processSaveAssetIntoInventory itemID="
        << item_id << LL_ENDL;
    LLViewerInventoryItem* item = gInventory.getItem( item_id );
    if( item )
    {
        LLCategoryUpdate up(item->getParentUUID(), 0);
        gInventory.accountForUpdate(up);
        gInventory.addChangedMask( LLInventoryObserver::INTERNAL, item_id);
        gInventory.notifyObservers();
    }
    else
    {
        LL_INFOS() << "LLInventoryModel::processSaveAssetIntoInventory item"
            " not found: " << item_id << LL_ENDL;
    }
    if(gViewerWindow)
    {
        gViewerWindow->getWindow()->decBusyCount();
    }
}

// static
void LLInventoryModel::processBulkUpdateInventory(LLMessageSystem* msg, void**)
{
    LLUUID agent_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS() << "Got a BulkUpdateInventory for the wrong agent." << LL_ENDL;
        return;
    }
    LLUUID tid;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_TransactionID, tid);
#ifndef LL_RELEASE_FOR_DOWNLOAD
    LL_DEBUGS("Inventory") << "Bulk inventory: " << tid << LL_ENDL;
#endif

    update_map_t update;
    cat_array_t folders;
    S32 count;
    S32 i;
    count = msg->getNumberOfBlocksFast(_PREHASH_FolderData);
    for(i = 0; i < count; ++i)
    {
        LLPointer<LLViewerInventoryCategory> tfolder = new LLViewerInventoryCategory(gAgent.getID());
        tfolder->unpackMessage(msg, _PREHASH_FolderData, i);
        LL_DEBUGS("Inventory") << "unpacked folder '" << tfolder->getName() << "' ("
                               << tfolder->getUUID() << ") in " << tfolder->getParentUUID()
                               << LL_ENDL;

        // If the folder is a listing or a version folder, all we need to do is update the SLM data
        int depth_folder = depth_nesting_in_marketplace(tfolder->getUUID());
        if ((depth_folder == 1) || (depth_folder == 2))
        {
            // Trigger an SLM listing update
            LLUUID listing_uuid = (depth_folder == 1 ? tfolder->getUUID() : tfolder->getParentUUID());
            S32 listing_id = LLMarketplaceData::instance().getListingID(listing_uuid);
            LLMarketplaceData::instance().getListing(listing_id);
            // In that case, there is no item to update so no callback -> we skip the rest of the update
        }
        else if(tfolder->getUUID().notNull())
        {
            folders.push_back(tfolder);
            LLViewerInventoryCategory* folderp = gInventory.getCategory(tfolder->getUUID());
            if(folderp)
            {
                if (folderp->getVersion() != LLViewerInventoryCategory::VERSION_UNKNOWN)
                {
                    if (tfolder->getParentUUID() == folderp->getParentUUID())
                    {
                        update[tfolder->getParentUUID()];
                    }
                    else
                    {
                        ++update[tfolder->getParentUUID()];
                        --update[folderp->getParentUUID()];
                    }
                }
                else
                {
                    folderp->fetch();
                }
            }
            else
            {
                // we could not find the folder, so it is probably
                // new. However, we only want to attempt accounting
                // for the parent if we can find the parent.
                folderp = gInventory.getCategory(tfolder->getParentUUID());
                if(folderp)
                {
                    if (folderp->getVersion() != LLViewerInventoryCategory::VERSION_UNKNOWN)
                    {
                        ++update[tfolder->getParentUUID()];
                    }
                    else
                    {
                        folderp->fetch();
                    }
                }
            }
        }
    }


    count = msg->getNumberOfBlocksFast(_PREHASH_ItemData);
    uuid_vec_t wearable_ids;
    item_array_t items;
    std::list<InventoryCallbackInfo> cblist;
    for(i = 0; i < count; ++i)
    {
        LLPointer<LLViewerInventoryItem> titem = new LLViewerInventoryItem;
        titem->unpackMessage(msg, _PREHASH_ItemData, i);
        LL_DEBUGS("Inventory") << "unpacked item '" << titem->getName() << "' in "
                               << titem->getParentUUID() << LL_ENDL;
        U32 callback_id;
        msg->getU32Fast(_PREHASH_ItemData, _PREHASH_CallbackID, callback_id);
        if(titem->getUUID().notNull() ) // && callback_id.notNull() )
        {
            items.push_back(titem);
            cblist.push_back(InventoryCallbackInfo(callback_id, titem->getUUID()));
            if (titem->getInventoryType() == LLInventoryType::IT_WEARABLE)
            {
                wearable_ids.push_back(titem->getUUID());
            }
            // examine update for changes.
            LLViewerInventoryItem* itemp = gInventory.getItem(titem->getUUID());
            if(itemp)
            {
                if(titem->getParentUUID() == itemp->getParentUUID())
                {
                    update[titem->getParentUUID()];
                }
                else
                {
                    ++update[titem->getParentUUID()];
                    --update[itemp->getParentUUID()];
                }
            }
            else
            {
                LLViewerInventoryCategory* folderp = gInventory.getCategory(titem->getParentUUID());
                if(folderp)
                {
                    if (folderp->getVersion() != LLViewerInventoryCategory::VERSION_UNKNOWN)
                    {
                        ++update[titem->getParentUUID()];
                    }
                    else
                    {
                        folderp->fetch();
                    }
                }
            }
        }
        else
        {
            cblist.push_back(InventoryCallbackInfo(callback_id, LLUUID::null));
        }
    }
    gInventory.accountForUpdate(update);

    for (cat_array_t::iterator cit = folders.begin(); cit != folders.end(); ++cit)
    {
        gInventory.updateCategory(*cit);
        if ((*cit)->getVersion() != LLViewerInventoryCategory::VERSION_UNKNOWN)
        {
            // Temporary workaround: just fetch the item using AIS to get missing fields.
            // If this works fine we might want to extract 'ids only' from the message
            // then use AIS as a primary fetcher
            LLInventoryModelBackgroundFetch::instance().scheduleFolderFetch((*cit)->getUUID(), true /*force, since it has changes*/);
        }
        // else already called fetch() above
    }
    for (item_array_t::iterator iit = items.begin(); iit != items.end(); ++iit)
    {
        gInventory.updateItem(*iit);

        // Temporary workaround: just fetch the item using AIS to get missing fields.
        // If this works fine we might want to extract 'ids only' from the message
        // then use AIS as a primary fetcher
        LLInventoryModelBackgroundFetch::instance().scheduleItemFetch((*iit)->getUUID(), true);
    }
    gInventory.notifyObservers();

    // The incoming inventory could span more than one BulkInventoryUpdate packet,
    // so record the transaction ID for this purchase, then wear all clothing
    // that comes in as part of that transaction ID.  JC
    if (LLInventoryState::sWearNewClothing)
    {
        LLInventoryState::sWearNewClothingTransactionID = tid;
        LLInventoryState::sWearNewClothing = FALSE;
    }

    if (tid.notNull() && tid == LLInventoryState::sWearNewClothingTransactionID)
    {
        count = wearable_ids.size();
        for (i = 0; i < count; ++i)
        {
            LLViewerInventoryItem* wearable_item;
            wearable_item = gInventory.getItem(wearable_ids[i]);
            LLAppearanceMgr::instance().wearItemOnAvatar(wearable_item->getUUID(), true, true);
        }
    }

    std::list<InventoryCallbackInfo>::iterator inv_it;
    for (inv_it = cblist.begin(); inv_it != cblist.end(); ++inv_it)
    {
        InventoryCallbackInfo cbinfo = (*inv_it);
        gInventoryCallbacks.fire(cbinfo.mCallback, cbinfo.mInvID);
    }
}

// static
void LLInventoryModel::processMoveInventoryItem(LLMessageSystem* msg, void**)
{
    LL_DEBUGS() << "LLInventoryModel::processMoveInventoryItem()" << LL_ENDL;
    LLUUID agent_id;
    msg->getUUIDFast(_PREHASH_AgentData, _PREHASH_AgentID, agent_id);
    if(agent_id != gAgent.getID())
    {
        LL_WARNS() << "Got a MoveInventoryItem message for the wrong agent."
                << LL_ENDL;
        return;
    }

    LLUUID item_id;
    LLUUID folder_id;
    std::string new_name;
    bool anything_changed = false;
    S32 count = msg->getNumberOfBlocksFast(_PREHASH_InventoryData);
    for(S32 i = 0; i < count; ++i)
    {
        msg->getUUIDFast(_PREHASH_InventoryData, _PREHASH_ItemID, item_id, i);
        LLViewerInventoryItem* item = gInventory.getItem(item_id);
        if(item)
        {
            LLPointer<LLViewerInventoryItem> new_item = new LLViewerInventoryItem(item);
            msg->getUUIDFast(_PREHASH_InventoryData, _PREHASH_FolderID, folder_id, i);
            msg->getString("InventoryData", "NewName", new_name, i);

            LL_DEBUGS() << "moving item " << item_id << " to folder "
                     << folder_id << LL_ENDL;
            update_list_t update;
            LLCategoryUpdate old_folder(item->getParentUUID(), -1);
            update.push_back(old_folder);
            LLCategoryUpdate new_folder(folder_id, 1);
            update.push_back(new_folder);
            gInventory.accountForUpdate(update);

            new_item->setParent(folder_id);
            if (new_name.length() > 0)
            {
                new_item->rename(new_name);
            }
            gInventory.updateItem(new_item);
            anything_changed = true;
        }
        else
        {
            LL_INFOS() << "LLInventoryModel::processMoveInventoryItem item not found: " << item_id << LL_ENDL;
        }
    }
    if(anything_changed)
    {
        gInventory.notifyObservers();
    }
}

//----------------------------------------------------------------------------
// Trash: LLFolderType::FT_TRASH, "ConfirmEmptyTrash"
// Lost&Found: LLFolderType::FT_LOST_AND_FOUND, "ConfirmEmptyLostAndFound"

bool LLInventoryModel::callbackEmptyFolderType(const LLSD& notification, const LLSD& response, LLFolderType::EType preferred_type)
{
    S32 option = LLNotificationsUtil::getSelectedOption(notification, response);
    if (option == 0) // YES
    {
        const LLUUID folder_id = findCategoryUUIDForType(preferred_type);
        purge_descendents_of(folder_id, NULL);
    }
    return false;
}

void LLInventoryModel::emptyFolderType(const std::string notification, LLFolderType::EType preferred_type)
{
    if (!notification.empty())
    {
        LLSD args;
        if(LLFolderType::FT_TRASH == preferred_type)
        {
            LLInventoryModel::cat_array_t cats;
            LLInventoryModel::item_array_t items;
            const LLUUID trash_id = findCategoryUUIDForType(preferred_type);
            gInventory.collectDescendents(trash_id, cats, items, LLInventoryModel::INCLUDE_TRASH); //All descendants
            S32 item_count = items.size() + cats.size();
            args["COUNT"] = item_count;
        }
        LLNotificationsUtil::add(notification, args, LLSD(),
                                        boost::bind(&LLInventoryModel::callbackEmptyFolderType, this, _1, _2, preferred_type));
    }
    else
    {
        const LLUUID folder_id = findCategoryUUIDForType(preferred_type);
        purge_descendents_of(folder_id, NULL);
    }
}

//----------------------------------------------------------------------------

void LLInventoryModel::removeItem(const LLUUID& item_id)
{
    LLViewerInventoryItem* item = getItem(item_id);
    if (! item)
    {
        LL_WARNS("Inventory") << "couldn't find inventory item " << item_id << LL_ENDL;
    }
    else
    {
        const LLUUID new_parent = findCategoryUUIDForType(LLFolderType::FT_TRASH);
        if (new_parent.notNull())
        {
            LL_INFOS("Inventory") << "Moving to Trash (" << new_parent << "):" << LL_ENDL;
            changeItemParent(item, new_parent, TRUE);
        }
    }
}

void LLInventoryModel::removeCategory(const LLUUID& category_id)
{
    if (! get_is_category_removable(this, category_id))
    {
        return;
    }

    // Look for any gestures and deactivate them
    LLInventoryModel::cat_array_t   descendent_categories;
    LLInventoryModel::item_array_t  descendent_items;
    collectDescendents(category_id, descendent_categories, descendent_items, FALSE);

    for (LLInventoryModel::item_array_t::const_iterator iter = descendent_items.begin();
         iter != descendent_items.end();
         ++iter)
    {
        const LLViewerInventoryItem* item = (*iter);
        const LLUUID& item_id = item->getUUID();
        if (item->getType() == LLAssetType::AT_GESTURE
            && LLGestureMgr::instance().isGestureActive(item_id))
        {
            LLGestureMgr::instance().deactivateGesture(item_id);
        }
    }

    LLViewerInventoryCategory* cat = getCategory(category_id);
    if (cat)
    {
        const LLUUID trash_id = findCategoryUUIDForType(LLFolderType::FT_TRASH);
        if (trash_id.notNull())
        {
            changeCategoryParent(cat, trash_id, TRUE);
        }
    }

    checkTrashOverflow();
}

void LLInventoryModel::removeObject(const LLUUID& object_id)
{
    if(object_id.isNull())
    {
        return;
    }

    LLInventoryObject* obj = getObject(object_id);
    if (dynamic_cast<LLViewerInventoryItem*>(obj))
    {
        removeItem(object_id);
    }
    else if (dynamic_cast<LLViewerInventoryCategory*>(obj))
    {
        removeCategory(object_id);
    }
    else if (obj)
    {
        LL_WARNS("Inventory") << "object ID " << object_id
                              << " is an object of unrecognized class "
                              << typeid(*obj).name() << LL_ENDL;
    }
    else
    {
        LL_WARNS("Inventory") << "object ID " << object_id << " not found" << LL_ENDL;
    }
}

bool callback_preview_trash_folder(const LLSD& notification, const LLSD& response)
{
    S32 option = LLNotificationsUtil::getSelectedOption(notification, response);
    if (option == 0) // YES
    {
        LLFloaterPreviewTrash::show();
    }
    return false;
}

void  LLInventoryModel::checkTrashOverflow()
{
    static LLCachedControl<U32> trash_max_capacity(gSavedSettings, "InventoryTrashMaxCapacity");

    // Collect all descendants including those in subfolders.
    //
    // Note: Do we really need content of subfolders?
    // This was made to prevent download of trash folder timeouting
    // viewer and sub-folders are supposed to download independently.
    LLInventoryModel::cat_array_t cats;
    LLInventoryModel::item_array_t items;
    const LLUUID trash_id = findCategoryUUIDForType(LLFolderType::FT_TRASH);
    gInventory.collectDescendents(trash_id, cats, items, LLInventoryModel::INCLUDE_TRASH);
    S32 item_count = items.size() + cats.size();

    if (item_count >= trash_max_capacity)
    {
        if (LLFloaterPreviewTrash::isVisible())
        {
            // bring to front
            LLFloaterPreviewTrash::show();
        }
        else
        {
            LLNotificationsUtil::add("TrashIsFull", LLSD(), LLSD(),
                boost::bind(callback_preview_trash_folder, _1, _2));
        }
    }
}

const LLUUID &LLInventoryModel::getRootFolderID() const
{
    return mRootFolderID;
}

void LLInventoryModel::setRootFolderID(const LLUUID& val)
{
    mRootFolderID = val;
}

const LLUUID &LLInventoryModel::getLibraryRootFolderID() const
{
    return mLibraryRootFolderID;
}

void LLInventoryModel::setLibraryRootFolderID(const LLUUID& val)
{
    mLibraryRootFolderID = val;
}

const LLUUID &LLInventoryModel::getLibraryOwnerID() const
{
    return mLibraryOwnerID;
}

void LLInventoryModel::setLibraryOwnerID(const LLUUID& val)
{
    mLibraryOwnerID = val;
}

// static
BOOL LLInventoryModel::getIsFirstTimeInViewer2()
{
    // Do not call this before parentchild map is built.
    if (!gInventory.mIsAgentInvUsable)
    {
        LL_WARNS() << "Parent Child Map not yet built; guessing as first time in viewer2." << LL_ENDL;
        return TRUE;
    }

    return sFirstTimeInViewer2;
}

LLInventoryModel::item_array_t::iterator LLInventoryModel::findItemIterByUUID(LLInventoryModel::item_array_t& items, const LLUUID& id)
{
    LLInventoryModel::item_array_t::iterator curr_item = items.begin();

    while (curr_item != items.end())
    {
        if ((*curr_item)->getUUID() == id)
        {
            break;
        }
        ++curr_item;
    }

    return curr_item;
}

// static
// * @param[in, out] items - vector with items to be updated. It should be sorted in a right way
// * before calling this method.
// * @param src_item_id - LLUUID of inventory item to be moved in new position
// * @param dest_item_id - LLUUID of inventory item before (or after) which source item should
// * be placed.
// * @param insert_before - bool indicating if src_item_id should be placed before or after
// * dest_item_id. Default is true.
void LLInventoryModel::updateItemsOrder(LLInventoryModel::item_array_t& items, const LLUUID& src_item_id, const LLUUID& dest_item_id, bool insert_before)
{
    LLInventoryModel::item_array_t::iterator it_src = findItemIterByUUID(items, src_item_id);
    LLInventoryModel::item_array_t::iterator it_dest = findItemIterByUUID(items, dest_item_id);

    // If one of the passed UUID is not in the item list, bail out
    if ((it_src == items.end()) || (it_dest == items.end()))
        return;

    // Erase the source element from the list, keep a copy before erasing.
    LLViewerInventoryItem* src_item = *it_src;
    items.erase(it_src);

    // Note: Target iterator is not valid anymore because the container was changed, so update it.
    it_dest = findItemIterByUUID(items, dest_item_id);

    // Go to the next element if one wishes to insert after the dest element
    if (!insert_before)
    {
        ++it_dest;
    }

    // Reinsert the source item in the right place
    if (it_dest != items.end())
    {
        items.insert(it_dest, src_item);
    }
    else
    {
        // Append to the list if it_dest reached the end
        items.push_back(src_item);
    }
}

// See also LLInventorySort where landmarks in the Favorites folder are sorted.
class LLViewerInventoryItemSort
{
public:
    bool operator()(const LLPointer<LLViewerInventoryItem>& a, const LLPointer<LLViewerInventoryItem>& b)
    {
        return a->getSortField() < b->getSortField();
    }
};

//----------------------------------------------------------------------------

// *NOTE: DEBUG functionality
void LLInventoryModel::dumpInventory() const
{
    LL_INFOS() << "\nBegin Inventory Dump\n**********************:" << LL_ENDL;
    LL_INFOS() << "mCategory[] contains " << mCategoryMap.size() << " items." << LL_ENDL;
    for(cat_map_t::const_iterator cit = mCategoryMap.begin(); cit != mCategoryMap.end(); ++cit)
    {
        const LLViewerInventoryCategory* cat = cit->second;
        if(cat)
        {
            LL_INFOS() << "  " <<  cat->getUUID() << " '" << cat->getName() << "' "
                    << cat->getVersion() << " " << cat->getDescendentCount()
                    << LL_ENDL;
        }
        else
        {
            LL_INFOS() << "  NULL!" << LL_ENDL;
        }
    }
    LL_INFOS() << "mItemMap[] contains " << mItemMap.size() << " items." << LL_ENDL;
    for(item_map_t::const_iterator iit = mItemMap.begin(); iit != mItemMap.end(); ++iit)
    {
        const LLViewerInventoryItem* item = iit->second;
        if(item)
        {
            LL_INFOS() << "  " << item->getUUID() << " "
                    << item->getName() << LL_ENDL;
        }
        else
        {
            LL_INFOS() << "  NULL!" << LL_ENDL;
        }
    }
    LL_INFOS() << "\n**********************\nEnd Inventory Dump" << LL_ENDL;
}

// Do various integrity checks on model, logging issues found and
// returning an overall good/bad flag.
LLPointer<LLInventoryValidationInfo> LLInventoryModel::validate() const
{
    LLPointer<LLInventoryValidationInfo> validation_info = new LLInventoryValidationInfo;
    S32 fatal_errs = 0;
    S32 warning_count= 0;
    S32 loop_count = 0;
    S32 orphaned_count = 0;

    if (getRootFolderID().isNull())
    {
        LL_WARNS("Inventory") << "Fatal inventory corruption: no root folder id" << LL_ENDL;
        validation_info->mFatalNoRootFolder = true;
        fatal_errs++;
    }
    if (getLibraryRootFolderID().isNull())
    {
        // Probably shouldn't be a fatality, inventory can function without a library
        LL_WARNS("Inventory") << "Fatal inventory corruption: no library root folder id" << LL_ENDL;
        validation_info->mFatalNoLibraryRootFolder = true;
        fatal_errs++;
    }

    if (mCategoryMap.size() + 1 != mParentChildCategoryTree.size())
    {
        // ParentChild should be one larger because of the special entry for null uuid.
        LL_INFOS("Inventory") << "unexpected sizes: cat map size " << mCategoryMap.size()
                              << " parent/child " << mParentChildCategoryTree.size() << LL_ENDL;

        validation_info->mWarnings["category_map_size"]++;
        warning_count++;
    }
    S32 cat_lock = 0;
    S32 item_lock = 0;
    S32 desc_unknown_count = 0;
    S32 version_unknown_count = 0;

    typedef std::map<LLFolderType::EType, S32> ft_count_map;
    ft_count_map ft_counts_under_root;
    ft_count_map ft_counts_elsewhere;

    // Loop over all categories and check.
    for(cat_map_t::const_iterator cit = mCategoryMap.begin(); cit != mCategoryMap.end(); ++cit)
    {
        const LLUUID& cat_id = cit->first;
        const LLViewerInventoryCategory *cat = cit->second;
        if (!cat)
        {
            LL_WARNS("Inventory") << "null cat" << LL_ENDL;
            validation_info->mWarnings["null_cat"]++;
            warning_count++;
            continue;
        }
        LLUUID topmost_ancestor_id;
        // Will leave as null uuid on failure
        EAncestorResult res = getObjectTopmostAncestor(cat_id, topmost_ancestor_id);
        switch (res)
        {
        case ANCESTOR_MISSING:
            orphaned_count++;
            break;
        case ANCESTOR_LOOP:
            loop_count++;
            break;
        case ANCESTOR_OK:
            break;
        default:
            LL_WARNS("Inventory") << "Unknown ancestor error for " << cat_id << LL_ENDL;
            validation_info->mWarnings["unknown_ancestor_status"]++;
            warning_count++;
            break;
        }

        if (cat_id != cat->getUUID())
        {
            LL_WARNS("Inventory") << "cat id/index mismatch " << cat_id << " " << cat->getUUID() << LL_ENDL;
            validation_info->mWarnings["cat_id_index_mismatch"]++;
            warning_count++;
        }

        if (cat->getParentUUID().isNull())
        {
            if (cat_id != getRootFolderID() && cat_id != getLibraryRootFolderID())
            {
                LL_WARNS("Inventory") << "cat " << cat_id << " has no parent, but is not root ("
                                      << getRootFolderID() << ") or library root ("
                                      << getLibraryRootFolderID() << ")" << LL_ENDL;
                validation_info->mWarnings["null_parent"]++;
                warning_count++;
            }
        }
        cat_array_t* cats;
        item_array_t* items;
        getDirectDescendentsOf(cat_id,cats,items);
        if (!cats || !items)
        {
            LL_WARNS("Inventory") << "invalid direct descendents for " << cat_id << LL_ENDL;
            validation_info->mWarnings["direct_descendents"]++;
            warning_count++;
            continue;
        }
        if (cat->getDescendentCount() == LLViewerInventoryCategory::DESCENDENT_COUNT_UNKNOWN)
        {
            desc_unknown_count++;
        }
        else if (cats->size() + items->size() != cat->getDescendentCount())
        {
            // In the case of library this is not unexpected, since
            // different user accounts may be getting the library
            // contents from different inventory hosts.
            if (topmost_ancestor_id.isNull() || topmost_ancestor_id != getLibraryRootFolderID())
            {
                LL_WARNS("Inventory") << "invalid desc count for " << cat_id << " [" << getFullPath(cat) << "]"
                                      << " cached " << cat->getDescendentCount()
                                      << " expected " << cats->size() << "+" << items->size()
                                      << "=" << cats->size() +items->size() << LL_ENDL;
                validation_info->mWarnings["invalid_descendent_count"]++;
                warning_count++;
            }
        }
        if (cat->getVersion() == LLViewerInventoryCategory::VERSION_UNKNOWN)
        {
            version_unknown_count++;
        }
        auto cat_lock_it = mCategoryLock.find(cat_id);
        if (cat_lock_it != mCategoryLock.end() && cat_lock_it->second)
        {
            cat_lock++;
        }
        auto item_lock_it = mItemLock.find(cat_id);
        if (item_lock_it != mItemLock.end() && item_lock_it->second)
        {
            item_lock++;
        }
        for (S32 i = 0; i<items->size(); i++)
        {
            LLViewerInventoryItem *item = items->at(i);

            if (!item)
            {
                LL_WARNS("Inventory") << "null item at index " << i << " for cat " << cat_id << LL_ENDL;
                validation_info->mWarnings["null_item_at_index"]++;
                warning_count++;
                continue;
            }

            const LLUUID& item_id = item->getUUID();

            if (item->getParentUUID() != cat_id)
            {
                LL_WARNS("Inventory") << "wrong parent for " << item_id << " found "
                                      << item->getParentUUID() << " expected " << cat_id
                                      << LL_ENDL;
                validation_info->mWarnings["wrong_parent_for_item"]++;
                warning_count++;
            }


            // Entries in items and mItemMap should correspond.
            item_map_t::const_iterator it = mItemMap.find(item_id);
            if (it == mItemMap.end())
            {
                LL_WARNS("Inventory") << "item " << item_id << " found as child of "
                                      << cat_id << " but not in top level mItemMap" << LL_ENDL;
                validation_info->mWarnings["item_not_in_top_map"]++;
                warning_count++;
            }
            else
            {
                LLViewerInventoryItem *top_item = it->second;
                if (top_item != item)
                {
                    LL_WARNS("Inventory") << "item mismatch, item_id " << item_id
                                          << " top level entry is different, uuid " << top_item->getUUID() << LL_ENDL;
                }
            }

            // Topmost ancestor should be root or library.
            LLUUID topmost_ancestor_id;
            EAncestorResult found = getObjectTopmostAncestor(item_id, topmost_ancestor_id);
            if (found != ANCESTOR_OK)
            {
                LL_WARNS("Inventory") << "unable to find topmost ancestor for " << item_id << LL_ENDL;
                validation_info->mWarnings["topmost_ancestor_not_found"]++;
                warning_count++;
            }
            else
            {
                if (topmost_ancestor_id != getRootFolderID() &&
                    topmost_ancestor_id != getLibraryRootFolderID())
                {
                    LL_WARNS("Inventory") << "unrecognized top level ancestor for " << item_id
                                          << " got " << topmost_ancestor_id
                                          << " expected " << getRootFolderID()
                                          << " or " << getLibraryRootFolderID() << LL_ENDL;
                    validation_info->mWarnings["topmost_ancestor_not_recognized"]++;
                    warning_count++;
                }
            }
        }

        // Does this category appear as a child of its supposed parent?
        const LLUUID& parent_id = cat->getParentUUID();
        if (!parent_id.isNull())
        {
            cat_array_t* cats;
            item_array_t* items;
            getDirectDescendentsOf(parent_id,cats,items);
            if (!cats)
            {
                LL_WARNS("Inventory") << "cat " << cat_id << " name [" << cat->getName()
                                      << "] orphaned - no child cat array for alleged parent " << parent_id << LL_ENDL;
                orphaned_count++;
            }
            else
            {
                bool found = false;
                for (S32 i = 0; i<cats->size(); i++)
                {
                    LLViewerInventoryCategory *kid_cat = cats->at(i);
                    if (kid_cat == cat)
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    LL_WARNS("Inventory") << "cat " << cat_id << " name [" << cat->getName()
                                          << "] orphaned - not found in child cat array of alleged parent " << parent_id << LL_ENDL;
                    orphaned_count++;
                }
            }
        }

        // Update count of preferred types
        LLFolderType::EType folder_type = cat->getPreferredType();
        bool cat_is_in_library = false;
        LLUUID topmost_id;
        if (getObjectTopmostAncestor(cat->getUUID(),topmost_id) == ANCESTOR_OK && topmost_id == getLibraryRootFolderID())
        {
            cat_is_in_library = true;
        }
        if (!cat_is_in_library)
        {
            if (getRootFolderID().notNull() && (cat->getUUID()==getRootFolderID() || cat->getParentUUID()==getRootFolderID()))
            {
                ft_counts_under_root[folder_type]++;
                if (folder_type != LLFolderType::FT_NONE)
                {
                    LL_DEBUGS("Inventory") << "Under root cat: " << getFullPath(cat) << " folder_type " << folder_type << LL_ENDL;
                }
            }
            else
            {
                ft_counts_elsewhere[folder_type]++;
                if (folder_type != LLFolderType::FT_NONE)
                {
                    LL_DEBUGS("Inventory") << "Elsewhere cat: " << getFullPath(cat) << " folder_type " << folder_type << LL_ENDL;
                }
            }
        }
    }

    // Loop over all items and check
    for(item_map_t::const_iterator iit = mItemMap.begin(); iit != mItemMap.end(); ++iit)
    {
        const LLUUID& item_id = iit->first;
        LLViewerInventoryItem *item = iit->second;
        if (item->getUUID() != item_id)
        {
            LL_WARNS("Inventory") << "item_id " << item_id << " does not match " << item->getUUID() << LL_ENDL;
            validation_info->mWarnings["item_id_mismatch"]++;
            warning_count++;
        }

        const LLUUID& parent_id = item->getParentUUID();
        if (parent_id.isNull())
        {
            LL_WARNS("Inventory") << "item " << item_id << " name [" << item->getName() << "] has null parent id!" << LL_ENDL;
            orphaned_count++;
        }
        else
        {
            cat_array_t* cats;
            item_array_t* items;
            getDirectDescendentsOf(parent_id,cats,items);
            if (!items)
            {
                LL_WARNS("Inventory") << "item " << item_id << " name [" << item->getName()
                                      << "] orphaned - alleged parent has no child items list " << parent_id << LL_ENDL;
                orphaned_count++;
            }
            else
            {
                bool found = false;
                for (S32 i=0; i<items->size(); ++i)
                {
                    if (items->at(i) == item)
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    LL_WARNS("Inventory") << "item " << item_id << " name [" << item->getName()
                                          << "] orphaned - not found as child of alleged parent " << parent_id << LL_ENDL;
                    orphaned_count++;
                }
            }

        }
        // Link checking
        if (item->getIsLinkType())
        {
            const LLUUID& link_id = item->getUUID();
            const LLUUID& target_id = item->getLinkedUUID();
            LLViewerInventoryItem *target_item = getItem(target_id);
            LLViewerInventoryCategory *target_cat = getCategory(target_id);
            // Linked-to UUID should have back reference to this link.
            if (!hasBacklinkInfo(link_id, target_id))
            {
                LL_WARNS("Inventory") << "link " << item->getUUID() << " type " << item->getActualType()
                                      << " missing backlink info at target_id " << target_id
                                      << LL_ENDL;
                orphaned_count++;
            }
            // Links should have referents.
            if (item->getActualType() == LLAssetType::AT_LINK && !target_item)
            {
                LL_WARNS("Inventory") << "broken item link " << item->getName() << " id " << item->getUUID() << LL_ENDL;
                orphaned_count++;
            }
            else if (item->getActualType() == LLAssetType::AT_LINK_FOLDER && !target_cat)
            {
                LL_WARNS("Inventory") << "broken folder link " << item->getName() << " id " << item->getUUID() << LL_ENDL;
                orphaned_count++;
            }
            if (target_item && target_item->getIsLinkType())
            {
                LL_WARNS("Inventory") << "link " << item->getName() << " references a link item "
                                      << target_item->getName() << " " << target_item->getUUID() << LL_ENDL;
            }

            // Links should not have backlinks.
            std::pair<backlink_mmap_t::const_iterator, backlink_mmap_t::const_iterator> range = mBacklinkMMap.equal_range(link_id);
            if (range.first != range.second)
            {
                LL_WARNS("Inventory") << "Link item " << item->getName() << " has backlinks!" << LL_ENDL;
            }
        }
        else
        {
            // Check the backlinks of a non-link item.
            const LLUUID& target_id = item->getUUID();
            std::pair<backlink_mmap_t::const_iterator, backlink_mmap_t::const_iterator> range = mBacklinkMMap.equal_range(target_id);
            for (backlink_mmap_t::const_iterator it = range.first; it != range.second; ++it)
            {
                const LLUUID& link_id = it->second;
                LLViewerInventoryItem *link_item = getItem(link_id);
                if (!link_item || !link_item->getIsLinkType())
                {
                    LL_WARNS("Inventory") << "invalid backlink from target " << item->getName() << " to " << link_id << LL_ENDL;
                }
            }
        }
    }

    // Check system folders
    for (auto fit=ft_counts_under_root.begin(); fit != ft_counts_under_root.end(); ++fit)
    {
        LL_DEBUGS("Inventory") << "Folder type " << fit->first << " count " << fit->second << " under root" << LL_ENDL;
    }
    for (auto fit=ft_counts_elsewhere.begin(); fit != ft_counts_elsewhere.end(); ++fit)
    {
        LL_DEBUGS("Inventory") << "Folder type " << fit->first << " count " << fit->second << " elsewhere" << LL_ENDL;
    }

    static LLCachedControl<bool> fake_system_folder_issues(gSavedSettings, "QAModeFakeSystemFolderIssues", false);
    static std::default_random_engine e{};
    static std::uniform_int_distribution<> distrib(0, 1);
    for (S32 ft=LLFolderType::FT_TEXTURE; ft<LLFolderType::FT_COUNT; ft++)
    {
        LLFolderType::EType folder_type = static_cast<LLFolderType::EType>(ft);
        if (LLFolderType::lookup(folder_type)==LLFolderType::badLookup())
        {
            continue;
        }
        bool is_automatic = LLFolderType::lookupIsAutomaticType(folder_type);
        bool is_singleton = LLFolderType::lookupIsSingletonType(folder_type);
        S32 count_under_root = ft_counts_under_root[folder_type];
        S32 count_elsewhere = ft_counts_elsewhere[folder_type];
        if (fake_system_folder_issues)
        {
            // Force all counts to be either 0 or 2, thus flagged as an error.
            count_under_root = 2*distrib(e);
            count_elsewhere = 2*distrib(e);
            validation_info->mFatalQADebugMode = true;
        }
        if (is_singleton)
        {
            if (count_under_root==0)
            {
                LL_WARNS("Inventory") << "Expected system folder type " << ft << " was not found under root" << LL_ENDL;
                // Need to create, if allowed.
                if (is_automatic)
                {
                    LL_WARNS("Inventory") << "Fatal inventory corruption: cannot create system folder of type " << ft << LL_ENDL;
                    validation_info->mMissingRequiredSystemFolders.insert(folder_type);
                    fatal_errs++;
                }
                else
                {
                    // Can create, and will when needed.
                    // (Not sure this is really a warning, but worth logging)
                    validation_info->mWarnings["missing_system_folder_can_create"]++;
                    warning_count++;
                }
            }
            else if (count_under_root > 1)
            {
                validation_info->mDuplicateRequiredSystemFolders.insert(folder_type);
                if (!is_automatic
                    && folder_type != LLFolderType::FT_SETTINGS
                    // FT_MATERIAL might need to be automatic like the rest of upload folders
                    && folder_type != LLFolderType::FT_MATERIAL
                    )
                {
                    // It is a fatal problem or can lead to fatal problems for COF,
                    // outfits, trash and other non-automatic folders.
                    validation_info->mFatalSystemDuplicate++;
                    fatal_errs++;
                    LL_WARNS("Inventory") << "Fatal inventory corruption: system folder type has excess copies under root, type " << ft << " count " << count_under_root << LL_ENDL;
                }
                else
                {
                    // For automatic folders it's not a fatal issue and shouldn't
                    // break inventory or other functionality further
                    // Exception: FT_SETTINGS is not automatic, but only deserves a warning.
                    validation_info->mWarnings["non_fatal_system_duplicate_under_root"]++;
                    warning_count++;
                    LL_WARNS("Inventory") << "System folder type has excess copies under root, type " << ft << " count " << count_under_root << LL_ENDL;
                }
            }
            if (count_elsewhere > 0)
            {
                LL_WARNS("Inventory") << "Found " << count_elsewhere << " extra folders of type " << ft << " outside of root" << LL_ENDL;
                validation_info->mWarnings["non_fatal_system_duplicate_elsewhere"]++;
                warning_count++;
            }
        }
    }


    if (cat_lock > 0 || item_lock > 0)
    {
        LL_INFOS("Inventory") << "Found locks on some categories: sub-cat arrays "
                << cat_lock << ", item arrays " << item_lock << LL_ENDL;
    }
    if (desc_unknown_count != 0)
    {
        LL_DEBUGS() << "Found " << desc_unknown_count << " cats with unknown descendent count" << LL_ENDL;
    }
    if (version_unknown_count != 0)
    {
        LL_DEBUGS("Inventory") << "Found " << version_unknown_count << " cats with unknown version" << LL_ENDL;
    }

    // FIXME need to fail login and tell user to retry, contact support if problem persists.
    bool valid = (fatal_errs == 0);
    LL_INFOS("Inventory") << "Validate done, fatal errors: " << fatal_errs << ", warnings: " << warning_count << ", valid: " << valid << LL_ENDL;

    validation_info->mFatalErrorCount = fatal_errs;
    validation_info->mWarningCount = warning_count;
    validation_info->mLoopCount = loop_count;
    validation_info->mOrphanedCount = orphaned_count;

    return validation_info;
}

// Provides a unix-style path from root, like "/My Inventory/Clothing/.../myshirt"
std::string LLInventoryModel::getFullPath(const LLInventoryObject *obj) const
{
    std::vector<std::string> path_elts;
    std::map<LLUUID,bool> visited;
    while (obj != NULL && !visited[obj->getUUID()])
    {
        path_elts.push_back(obj->getName());
        // avoid infinite loop in the unlikely event of a cycle
        visited[obj->getUUID()] = true;
        obj = getObject(obj->getParentUUID());
    }
    std::stringstream s;
    std::string delim("/");
    std::reverse(path_elts.begin(), path_elts.end());
    std::string result = "/" + boost::algorithm::join(path_elts, delim);
    return result;
}

///----------------------------------------------------------------------------
/// Local function definitions
///----------------------------------------------------------------------------


#if 0
BOOL decompress_file(const char* src_filename, const char* dst_filename)
{
    BOOL rv = FALSE;
    gzFile src = NULL;
    U8* buffer = NULL;
    LLFILE* dst = NULL;
    S32 bytes = 0;
    const S32 DECOMPRESS_BUFFER_SIZE = 32000;

    // open the files
    src = gzopen(src_filename, "rb");
    if(!src) goto err_decompress;
    dst = LLFile::fopen(dst_filename, "wb");
    if(!dst) goto err_decompress;

    // decompress.
    buffer = new U8[DECOMPRESS_BUFFER_SIZE + 1];

    do
    {
        bytes = gzread(src, buffer, DECOMPRESS_BUFFER_SIZE);
        if (bytes < 0)
        {
            goto err_decompress;
        }

        fwrite(buffer, bytes, 1, dst);
    } while(gzeof(src) == 0);

    // success
    rv = TRUE;

 err_decompress:
    if(src != NULL) gzclose(src);
    if(buffer != NULL) delete[] buffer;
    if(dst != NULL) fclose(dst);
    return rv;
}
#endif


///----------------------------------------------------------------------------
/// Class LLInventoryModel::FetchItemHttpHandler
///----------------------------------------------------------------------------

LLInventoryModel::FetchItemHttpHandler::FetchItemHttpHandler(const LLSD & request_sd)
    : LLCore::HttpHandler(),
      mRequestSD(request_sd)
{}

LLInventoryModel::FetchItemHttpHandler::~FetchItemHttpHandler()
{}

void LLInventoryModel::FetchItemHttpHandler::onCompleted(LLCore::HttpHandle handle,
                                                         LLCore::HttpResponse * response)
{
    do      // Single-pass do-while used for common exit handling
    {
        LLCore::HttpStatus status(response->getStatus());
        // status = LLCore::HttpStatus(404);                // Dev tool to force error handling
        if (! status)
        {
            processFailure(status, response);
            break;          // Goto common exit
        }

        LLCore::BufferArray * body(response->getBody());
        // body = NULL;                                 // Dev tool to force error handling
        if (! body || ! body->size())
        {
            LL_WARNS(LOG_INV) << "Missing data in inventory item query." << LL_ENDL;
            processFailure("HTTP response for inventory item query missing body", response);
            break;          // Goto common exit
        }

        // body->write(0, "Garbage Response", 16);      // Dev tool to force error handling
        LLSD body_llsd;
        if (! LLCoreHttpUtil::responseToLLSD(response, true, body_llsd))
        {
            // INFOS-level logging will occur on the parsed failure
            processFailure("HTTP response for inventory item query has malformed LLSD", response);
            break;          // Goto common exit
        }

        // Expect top-level structure to be a map
        // body_llsd = LLSD::emptyArray();              // Dev tool to force error handling
        if (! body_llsd.isMap())
        {
            processFailure("LLSD response for inventory item not a map", response);
            break;          // Goto common exit
        }

        // Check for 200-with-error failures
        //
        // Original Responder-based serivce model didn't check for these errors.
        // It may be more robust to ignore this condition.  With aggregated requests,
        // an error in one inventory item might take down the entire request.
        // So if this instead broke up the aggregated items into single requests,
        // maybe that would make progress.  Or perhaps there's structured information
        // that can tell us what went wrong.  Need to dig into this and firm up
        // the API.
        //
        // body_llsd["error"] = LLSD::emptyMap();       // Dev tool to force error handling
        // body_llsd["error"]["identifier"] = "Development";
        // body_llsd["error"]["message"] = "You left development code in the viewer";
        if (body_llsd.has("error"))
        {
            processFailure("Inventory application error (200-with-error)", response);
            break;          // Goto common exit
        }

        // Okay, process data if possible
        processData(body_llsd, response);
    }
    while (false);
}

void LLInventoryModel::FetchItemHttpHandler::processData(LLSD & content, LLCore::HttpResponse * response)
{
    start_new_inventory_observer();

#if 0
    LLUUID agent_id;
    agent_id = content["agent_id"].asUUID();
    if (agent_id != gAgent.getID())
    {
        LL_WARNS(LOG_INV) << "Got a inventory update for the wrong agent: " << agent_id
                          << LL_ENDL;
        return;
    }
#endif

    LLInventoryModel::item_array_t items;
    LLInventoryModel::update_map_t update;
    LLUUID folder_id;
    LLSD content_items(content["items"]);
    const S32 count(content_items.size());

    // Does this loop ever execute more than once?
    for (S32 i(0); i < count; ++i)
    {
        LLPointer<LLViewerInventoryItem> titem = new LLViewerInventoryItem;
        titem->unpackMessage(content_items[i]);

        LL_DEBUGS(LOG_INV) << "ItemHttpHandler::httpSuccess item id: "
                           << titem->getUUID() << LL_ENDL;
        items.push_back(titem);

        // examine update for changes.
        LLViewerInventoryItem * itemp(gInventory.getItem(titem->getUUID()));

        if (itemp)
        {
            if (titem->getParentUUID() == itemp->getParentUUID())
            {
                update[titem->getParentUUID()];
            }
            else
            {
                ++update[titem->getParentUUID()];
                --update[itemp->getParentUUID()];
            }
        }
        else
        {
            ++update[titem->getParentUUID()];
        }

        if (folder_id.isNull())
        {
            folder_id = titem->getParentUUID();
        }
    }

    // as above, this loop never seems to loop more than once per call
    for (LLInventoryModel::item_array_t::iterator it = items.begin(); it != items.end(); ++it)
    {
        gInventory.updateItem(*it);
    }
    gInventory.notifyObservers();
    gViewerWindow->getWindow()->decBusyCount();
}


void LLInventoryModel::FetchItemHttpHandler::processFailure(LLCore::HttpStatus status, LLCore::HttpResponse * response)
{
    const std::string & ct(response->getContentType());
    LL_WARNS(LOG_INV) << "Inventory item fetch failure\n"
                      << "[Status: " << status.toTerseString() << "]\n"
                      << "[Reason: " << status.toString() << "]\n"
                      << "[Content-type: " << ct << "]\n"
                      << "[Content (abridged): "
                      << LLCoreHttpUtil::responseToString(response) << "]" << LL_ENDL;
    gInventory.notifyObservers();
}

void LLInventoryModel::FetchItemHttpHandler::processFailure(const char * const reason, LLCore::HttpResponse * response)
{
    LL_WARNS(LOG_INV) << "Inventory item fetch failure\n"
                      << "[Status: internal error]\n"
                      << "[Reason: " << reason << "]\n"
                      << "[Content (abridged): "
                      << LLCoreHttpUtil::responseToString(response) << "]" << LL_ENDL;
    gInventory.notifyObservers();
}