use std::collections::{BTreeMap, BTreeSet, LinkedList};
use std::iter;
use std::ops::Bound;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::{Arc, Once, RwLock};
use std::thread::{self, Builder};

use big_s::S;
use document_changes::{DocumentChanges, IndexingContext};
pub use document_deletion::DocumentDeletion;
pub use document_operation::{IndexOperations, PayloadStats};
use fst::{IntoStreamer, Streamer as _};
use hashbrown::HashMap;
use heed::types::{Bytes, DecodeIgnore, Str, Unit};
use heed::{BytesDecode, Database, RoTxn, RwTxn};
pub use mini_string::MiniString;
pub use partial_dump::PartialDump;
pub use post_processing::recompute_word_fst_from_word_docids_database;
use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator};
pub use settings_changes::settings_change_extract;
pub use update_by_function::UpdateByFunction;
pub use word_delta::WordDelta;
pub use write::ChannelCongestion;
use write::{build_vectors, update_index, write_to_db};

use super::channel::*;
use super::steps::IndexingStep;
use super::thread_local::ThreadLocal;
use crate::constants::{RESERVED_GEOJSON_FIELD_NAME, RESERVED_GEO_FIELD_NAME};
use crate::disabled_typos_terms::DisabledTyposTerms;
use crate::documents::PrimaryKey;
use crate::fields_ids_map::metadata::{FieldIdMapWithMetadata, MetadataBuilder};
use crate::heed_codec::StrBEU16Codec;
use crate::index::PrefixSearch;
use crate::progress::{AtomicDatabaseStep, EmbedderStats, Progress};
use crate::proximity::ProximityPrecision;
use crate::update::new::steps::{PostProcessingWords, SettingsIndexerStep};
use crate::update::settings::SettingsDelta;
use crate::update::{GrenadParameters, WordsPrefixesFst};
use crate::vector::settings::{EmbedderAction, RemoveFragments, WriteBackToDocuments};
use crate::vector::{Embedder, RuntimeEmbedders, VectorStore};
use crate::{
    CboRoaringBitmapCodec, Error, FieldsIdsMap, FilterFeatures, FilterableAttributesFeatures,
    GlobalFieldsIdsMap, Index, InternalError, MustStopProcessing, PatternMatch, Result,
    ThreadPoolNoAbort,
};

pub(crate) mod de;
pub mod document_changes;
mod document_deletion;
mod document_operation;
mod extract;
mod guess_primary_key;
mod mini_string;
mod partial_dump;
mod post_processing;
pub mod settings_changes;
mod update_by_function;
mod word_delta;
mod write;

static LOG_MEMORY_METRICS_ONCE: Once = Once::new();

/// This is the main function of this crate.
///
/// Give it the output of the [`Indexer::document_changes`] method and it will execute it in the [`rayon::ThreadPool`].
#[allow(clippy::too_many_arguments)] // clippy: 😝
pub fn index<'pl, 'indexer, 'index, DC>(
    wtxn: &mut RwTxn,
    index: &'index Index,
    pool: &ThreadPoolNoAbort,
    grenad_parameters: GrenadParameters,
    db_fields_ids_map: &'indexer FieldsIdsMap,
    new_fields_ids_map: FieldsIdsMap,
    new_primary_key: Option<PrimaryKey<'pl>>,
    document_changes: &DC,
    embedders: RuntimeEmbedders,
    must_stop_processing: &'indexer MustStopProcessing,
    progress: &'indexer Progress,
    embedder_ip_policy: &'indexer http_client::policy::IpPolicy,
    embedder_stats: &'indexer EmbedderStats,
) -> Result<ChannelCongestion>
where
    DC: DocumentChanges<'pl>,
{
    let mut bbbuffers = Vec::new();
    let finished_extraction = AtomicBool::new(false);

    let vector_memory = grenad_parameters.max_memory;

    let (grenad_parameters, total_bbbuffer_capacity) =
        indexer_memory_settings(pool.current_num_threads(), grenad_parameters);

    let (extractor_sender, writer_receiver) = pool
        .install(|| extractor_writer_bbqueue(&mut bbbuffers, total_bbbuffer_capacity, 1000))
        .unwrap();

    let metadata_builder = MetadataBuilder::from_index(index, wtxn)?;
    let new_fields_ids_map = FieldIdMapWithMetadata::new(new_fields_ids_map, metadata_builder);
    let new_fields_ids_map = RwLock::new(new_fields_ids_map);
    let fields_ids_map_store = ThreadLocal::with_capacity(rayon::current_num_threads());
    let mut extractor_allocs = ThreadLocal::with_capacity(rayon::current_num_threads());
    let doc_allocs = ThreadLocal::with_capacity(rayon::current_num_threads());

    let indexing_context = IndexingContext {
        index,
        db_fields_ids_map,
        new_fields_ids_map: &new_fields_ids_map,
        doc_allocs: &doc_allocs,
        fields_ids_map_store: &fields_ids_map_store,
        must_stop_processing,
        progress,
        grenad_parameters: &grenad_parameters,
    };

    let index_embeddings = index.embedding_configs().embedding_configs(wtxn)?;
    let mut field_distribution = index.field_distribution(wtxn)?;
    let mut document_ids = index.documents_ids(wtxn)?;
    let mut modified_docids = roaring::RoaringBitmap::new();

    let congestion = thread::scope(|s| -> Result<ChannelCongestion> {
        let indexer_span = tracing::Span::current();
        let embedders = &embedders;
        let finished_extraction = &finished_extraction;
        // prevent moving the field_distribution and document_ids in the inner closure...
        let field_distribution = &mut field_distribution;
        let document_ids = &mut document_ids;
        let modified_docids = &mut modified_docids;
        let extractor_handle =
            Builder::new().name(S("indexer-extractors")).spawn_scoped(s, move || {
                pool.install(move || {
                    extract::extract_all(
                        document_changes,
                        indexing_context,
                        indexer_span,
                        extractor_sender,
                        embedders,
                        &mut extractor_allocs,
                        finished_extraction,
                        field_distribution,
                        index_embeddings,
                        document_ids,
                        modified_docids,
                        embedder_stats,
                    )
                })
                .unwrap()
            })?;

        let global_fields_ids_map = GlobalFieldsIdsMap::new(&new_fields_ids_map);

        let vector_arroy = index.vector_store;
        let backend = index.get_vector_store(wtxn)?.unwrap_or_default();
        let vector_stores: Result<HashMap<_, _>> = embedders
            .inner_as_ref()
            .iter()
            .map(|(embedder_name, runtime)| {
                let embedder_index = index
                    .embedding_configs()
                    .embedder_id(wtxn, embedder_name)?
                    .ok_or(InternalError::DatabaseMissingEntry {
                        db_name: "embedder_category_id",
                        key: None,
                    })?;

                let dimensions = runtime.embedder.dimensions();
                let writer =
                    VectorStore::new(backend, vector_arroy, embedder_index, runtime.is_quantized);

                Ok((
                    embedder_index,
                    (embedder_name.as_str(), &*runtime.embedder, writer, dimensions),
                ))
            })
            .collect();

        let mut vector_stores = vector_stores?;

        let congestion =
            write_to_db(writer_receiver, finished_extraction, index, wtxn, &vector_stores)?;

        indexing_context.progress.update_progress(IndexingStep::WaitingForExtractors);

        let (facet_field_ids_delta, word_delta, index_embeddings) =
            extractor_handle.join().unwrap()?;

        indexing_context.progress.update_progress(IndexingStep::WritingEmbeddingsToDatabase);

        pool.install(|| {
            build_vectors(
                index,
                wtxn,
                indexing_context.progress,
                index_embeddings,
                vector_memory,
                &mut vector_stores,
                None,
                indexing_context.must_stop_processing,
            )
        })
        .unwrap()?;

        pool.install(|| {
            post_processing::post_process(
                indexing_context,
                wtxn,
                global_fields_ids_map,
                &word_delta,
                facet_field_ids_delta,
            )
        })
        .unwrap()?;

        indexing_context.progress.update_progress(IndexingStep::BuildingGeoJson);
        index.cellulite.build(
            wtxn,
            &|| indexing_context.must_stop_processing.get(),
            indexing_context.progress,
        )?;

        indexing_context.progress.update_progress(IndexingStep::Finalizing);

        Ok(congestion) as Result<_>
    })?;

    // required to into_inner the new_fields_ids_map
    drop(fields_ids_map_store);

    let shard_docids = index.shard_docids();
    shard_docids
        .update_shards(wtxn, |shard, docids| document_changes.shard_docids(shard, docids))?;

    let new_fields_ids_map = new_fields_ids_map.into_inner().unwrap();
    update_index(
        index,
        wtxn,
        new_fields_ids_map,
        new_primary_key,
        embedders,
        embedder_ip_policy,
        field_distribution,
        document_ids,
    )?;

    Ok(congestion)
}

#[allow(clippy::too_many_arguments)]
pub fn reindex<'indexer, 'index, SD>(
    wtxn: &mut RwTxn<'index>,
    index: &'index Index,
    pool: &ThreadPoolNoAbort,
    grenad_parameters: GrenadParameters,
    settings_delta: &'indexer SD,
    must_stop_processing: &'indexer MustStopProcessing,
    progress: &'indexer Progress,
    embedder_ip_policy: &'indexer http_client::policy::IpPolicy,
    embedder_stats: Arc<EmbedderStats>,
) -> Result<ChannelCongestion>
where
    SD: SettingsDelta + Sync,
{
    delete_old_embedders_and_fragments(wtxn, index, settings_delta)?;
    delete_old_fid_based_databases(wtxn, index, settings_delta, must_stop_processing, progress)?;
    delete_old_fid_from_facet_databases(
        wtxn,
        index,
        settings_delta,
        must_stop_processing,
        progress,
    )?;
    delete_old_geo_databases(wtxn, index, settings_delta, must_stop_processing, progress)?;

    // Fetch the numbers from the words FST
    let (numbers_to_delete_from_words_fst, numbers_to_add_to_words_fst) =
        migrate_numbers(wtxn, index, settings_delta)?;

    // Clear word_pair_proximity if byWord to byAttribute
    let old_proximity_precision = settings_delta.old_proximity_precision();
    let new_proximity_precision = settings_delta.new_proximity_precision();
    if *old_proximity_precision == ProximityPrecision::ByWord
        && *new_proximity_precision == ProximityPrecision::ByAttribute
    {
        index.word_pair_proximity_docids.clear(wtxn)?;
    }

    if *settings_delta.new_prefix_search() == PrefixSearch::Disabled {
        index.delete_words_prefixes_fst(wtxn)?;
        index.word_prefix_docids.clear(wtxn)?;
        index.word_prefix_fid_docids.clear(wtxn)?;
        index.word_prefix_position_docids.clear(wtxn)?;
        index.exact_word_prefix_docids.clear(wtxn)?;
    }

    let mut bbbuffers = Vec::new();
    let finished_extraction = AtomicBool::new(false);

    let vector_memory = grenad_parameters.max_memory;

    let (grenad_parameters, total_bbbuffer_capacity) =
        indexer_memory_settings(pool.current_num_threads(), grenad_parameters);

    let (extractor_sender, writer_receiver) = pool
        .install(|| extractor_writer_bbqueue(&mut bbbuffers, total_bbbuffer_capacity, 1000))
        .unwrap();

    let mut extractor_allocs = ThreadLocal::with_capacity(rayon::current_num_threads());

    let db_fields_ids_map = index.fields_ids_map(wtxn)?;
    let new_fields_ids_map = settings_delta.new_fields_ids_map().clone();
    let new_fields_ids_map = RwLock::new(new_fields_ids_map);
    let fields_ids_map_store = ThreadLocal::with_capacity(rayon::current_num_threads());
    let doc_allocs = ThreadLocal::with_capacity(rayon::current_num_threads());

    let indexing_context = IndexingContext {
        index,
        db_fields_ids_map: &db_fields_ids_map,
        new_fields_ids_map: &new_fields_ids_map,
        doc_allocs: &doc_allocs,
        fields_ids_map_store: &fields_ids_map_store,
        must_stop_processing,
        progress,
        grenad_parameters: &grenad_parameters,
    };

    let index_embeddings = index.embedding_configs().embedding_configs(wtxn)?;
    let mut field_distribution = index.field_distribution(wtxn)?;

    let congestion = thread::scope(|s| -> Result<ChannelCongestion> {
        let indexer_span = tracing::Span::current();
        let finished_extraction = &finished_extraction;
        // prevent moving the field_distribution and document_ids in the inner closure...
        let field_distribution = &mut field_distribution;
        let extractor_handle =
            Builder::new().name(S("indexer-extractors")).spawn_scoped(s, move || {
                pool.install(move || {
                    extract::extract_all_settings_changes(
                        indexing_context,
                        indexer_span,
                        extractor_sender,
                        settings_delta,
                        &mut extractor_allocs,
                        finished_extraction,
                        field_distribution,
                        index_embeddings,
                        &embedder_stats,
                    )
                })
                .unwrap()
            })?;

        let global_fields_ids_map = GlobalFieldsIdsMap::new(&new_fields_ids_map);

        let new_embedders = settings_delta.new_embedders();
        let embedder_actions = settings_delta.embedder_actions();
        let index_embedder_category_ids = settings_delta.new_embedder_category_id();
        let mut vector_stores = vector_stores_from_embedder_actions(
            index,
            wtxn,
            embedder_actions,
            new_embedders,
            index_embedder_category_ids,
        )?;

        let congestion =
            write_to_db(writer_receiver, finished_extraction, index, wtxn, &vector_stores)?;

        indexing_context.progress.update_progress(IndexingStep::WaitingForExtractors);

        let (index_embeddings, mut word_delta, facet_field_ids_delta) =
            extractor_handle.join().unwrap()?;

        // Insert the recently added numbers into the added words
        word_delta.added.extend(numbers_to_add_to_words_fst);
        // Insert the recently removed numbers into deleted words
        word_delta.deleted.extend(numbers_to_delete_from_words_fst);

        indexing_context.progress.update_progress(IndexingStep::WritingEmbeddingsToDatabase);

        pool.install(|| {
            build_vectors(
                index,
                wtxn,
                indexing_context.progress,
                index_embeddings,
                vector_memory,
                &mut vector_stores,
                Some(embedder_actions),
                indexing_context.must_stop_processing,
            )
        })
        .unwrap()?;

        pool.install(|| {
            // This method writes an empty prefix FST when the prefix search is
            // disabled because it is based on the modified words during the process
            // and we have not necessarily modified any word during a settings change.
            post_processing::post_process(
                indexing_context,
                wtxn,
                global_fields_ids_map,
                &word_delta,
                facet_field_ids_delta,
            )?;

            // When the prefix search was disabled and is enabled we need to call the
            // WordsPrefixesFst::execute to generate and write the words FST from scratch
            // and call the compute_prefix_database_from_sources a second time to correctly
            // generate the prefixes databases.
            if *settings_delta.old_prefix_search() == PrefixSearch::Disabled
                && *settings_delta.new_prefix_search() == PrefixSearch::IndexingTime
            {
                indexing_context.progress.update_progress(PostProcessingWords::ComputePrefixFst);
                WordsPrefixesFst::new(wtxn, index).execute()?;
                let prefixes_fst = index.words_prefixes_fst(wtxn)?;

                let mut modified = BTreeSet::new();
                let deleted = BTreeSet::new();
                let mut prefix_stream = prefixes_fst.into_stream();
                while let Some(prefix) = prefix_stream.next() {
                    let Ok(prefix) = std::str::from_utf8(prefix) else { continue };
                    let Some(prefix) = MiniString::new(prefix) else { continue };
                    modified.insert(prefix);
                }
                post_processing::compute_prefix_database_from_sources(
                    index, wtxn, &modified, &deleted, progress,
                )?;
            }

            Ok(()) as Result<_>
        })
        .unwrap()?;

        indexing_context.progress.update_progress(IndexingStep::BuildingGeoJson);
        index.cellulite.build(
            wtxn,
            &|| indexing_context.must_stop_processing.get(),
            indexing_context.progress,
        )?;

        indexing_context.progress.update_progress(IndexingStep::Finalizing);

        Ok(congestion) as Result<_>
    })?;

    // required to into_inner the new_fields_ids_map
    drop(fields_ids_map_store);

    let new_fields_ids_map = new_fields_ids_map.into_inner().unwrap();
    let document_ids = index.documents_ids(wtxn)?;
    update_index(
        index,
        wtxn,
        new_fields_ids_map,
        None,
        settings_delta.new_embedders().clone(),
        embedder_ip_policy,
        field_distribution,
        document_ids,
    )?;

    Ok(congestion)
}

fn vector_stores_from_embedder_actions<'indexer>(
    index: &Index,
    rtxn: &RoTxn,
    embedder_actions: &'indexer BTreeMap<String, EmbedderAction>,
    embedders: &'indexer RuntimeEmbedders,
    index_embedder_category_ids: &'indexer std::collections::HashMap<String, u8>,
) -> Result<HashMap<u8, (&'indexer str, &'indexer Embedder, VectorStore, usize)>> {
    let vector_arroy = index.vector_store;
    let backend = index.get_vector_store(rtxn)?.unwrap_or_default();

    embedders
        .inner_as_ref()
        .iter()
        .filter_map(|(embedder_name, runtime)| match embedder_actions.get(embedder_name) {
            None => None,
            Some(action) if action.write_back().is_some() => None,
            Some(action) => {
                let Some(&embedder_category_id) = index_embedder_category_ids.get(embedder_name)
                else {
                    return Some(Err(crate::error::Error::InternalError(
                        crate::InternalError::DatabaseMissingEntry {
                            db_name: crate::index::db_name::VECTOR_EMBEDDER_CATEGORY_ID,
                            key: None,
                        },
                    )));
                };
                let writer = VectorStore::new(
                    backend,
                    vector_arroy,
                    embedder_category_id,
                    action.was_quantized,
                );
                let dimensions = runtime.embedder.dimensions();
                Some(Ok((
                    embedder_category_id,
                    (embedder_name.as_str(), runtime.embedder.as_ref(), writer, dimensions),
                )))
            }
        })
        .collect()
}

fn delete_old_embedders_and_fragments<SD>(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    settings_delta: &SD,
) -> Result<()>
where
    SD: SettingsDelta,
{
    let backend = index.get_vector_store(wtxn)?.unwrap_or_default();
    for action in settings_delta.embedder_actions().values() {
        let Some(WriteBackToDocuments { embedder_id, .. }) = action.write_back() else {
            continue;
        };
        let reader =
            VectorStore::new(backend, index.vector_store, *embedder_id, action.was_quantized);
        let Some(dimensions) = reader.dimensions(wtxn)? else {
            continue;
        };
        reader.clear(wtxn, dimensions)?;
    }

    // remove all vectors for the specified fragments
    for (embedder_name, RemoveFragments { fragment_ids }, was_quantized) in
        settings_delta.embedder_actions().iter().filter_map(|(name, action)| {
            action.remove_fragments().map(|fragments| (name, fragments, action.was_quantized))
        })
    {
        let Some(infos) = index.embedding_configs().embedder_info(wtxn, embedder_name)? else {
            continue;
        };
        let arroy = VectorStore::new(backend, index.vector_store, infos.embedder_id, was_quantized);
        let Some(dimensions) = arroy.dimensions(wtxn)? else {
            continue;
        };
        for fragment_id in fragment_ids {
            // we must keep the user provided embeddings that ended up in this store

            if infos.embedding_status.user_provided_docids().is_empty() {
                // no user provided: clear store
                arroy.clear_store(wtxn, *fragment_id, dimensions)?;
                continue;
            }

            // some user provided, remove only the ids that are not user provided
            let to_delete = arroy.items_in_store(wtxn, *fragment_id, |items| {
                items - infos.embedding_status.user_provided_docids()
            })?;

            for to_delete in to_delete {
                arroy.del_item_in_store(wtxn, to_delete, *fragment_id, dimensions)?;
            }
        }
    }

    Ok(())
}

fn delete_old_geo_databases<SD>(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    settings_delta: &SD,
    must_stop_processing: &MustStopProcessing,
    progress: &Progress,
) -> Result<()>
where
    SD: SettingsDelta + Sync,
{
    let _step = progress.update_progress_scoped(IndexingStep::DeletingFromGeoDatabases);

    let new_enabled_geojson = settings_delta
        .new_fields_ids_map()
        .id_with_metadata(RESERVED_GEOJSON_FIELD_NAME)
        .is_some_and(|(_id, meta)| meta.is_geojson_enabled());

    // Clear the cellulite database when the geojson support is removed
    if !new_enabled_geojson {
        index.cellulite.clear(wtxn)?;
    }

    if must_stop_processing.get() {
        return Err(Error::InternalError(InternalError::AbortedIndexation));
    }

    let new_enabled_geo = settings_delta
        .new_fields_ids_map()
        .id_with_metadata(RESERVED_GEO_FIELD_NAME)
        .is_some_and(|(_id, meta)| meta.is_geo_enabled());

    // Clear the geo rtree entry when the geo support is removed
    if !new_enabled_geo {
        index.delete_geo_rtree(wtxn)?;
    }

    Ok(())
}

pub fn migrate_numbers<SD>(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    settings_delta: &SD,
) -> Result<(BTreeSet<String>, BTreeSet<String>)>
where
    SD: SettingsDelta + Sync,
{
    let mut numbers_to_delete_from_words_fst = BTreeSet::new();
    let mut numbers_to_add_to_words_fst = BTreeSet::new();

    let old_disabled_typos_terms = settings_delta.old_disabled_typos_terms();
    let new_disabled_typos_terms = settings_delta.new_disabled_typos_terms();
    match (old_disabled_typos_terms, new_disabled_typos_terms) {
        (
            DisabledTyposTerms { disable_on_numbers: false },
            DisabledTyposTerms { disable_on_numbers: true },
        ) => {
            // We enable disableOnNumbers so we need to remove those from the words FST
            numbers_to_delete_from_words_fst =
                extract_numbers_from_words_fst(wtxn, index, new_disabled_typos_terms)?;
            let rtxn = index.read_txn()?;
            migrate_word_docids(
                &rtxn,
                index.word_docids,
                wtxn,
                index.exact_word_docids,
                &numbers_to_delete_from_words_fst,
            )?;
            migrate_word_docids(
                &rtxn,
                index.word_prefix_docids,
                wtxn,
                index.exact_word_prefix_docids,
                &numbers_to_delete_from_words_fst,
            )?;
        }
        (
            DisabledTyposTerms { disable_on_numbers: true },
            DisabledTyposTerms { disable_on_numbers: false },
        ) => {
            // We disable disableOnNumbers so we need to add those words to the words FST
            numbers_to_add_to_words_fst = extract_numbers_from_non_exact_searchable_attributes(
                wtxn,
                index,
                settings_delta.old_fields_ids_map(),
                old_disabled_typos_terms,
            )?;
            let rtxn = index.read_txn()?;
            migrate_word_docids(
                &rtxn,
                index.exact_word_docids,
                wtxn,
                index.word_docids,
                &numbers_to_add_to_words_fst,
            )?;
            migrate_word_docids(
                &rtxn,
                index.exact_word_prefix_docids,
                wtxn,
                index.word_prefix_docids,
                &numbers_to_add_to_words_fst,
            )?;
        }
        _ => (),
    }

    Ok((numbers_to_delete_from_words_fst, numbers_to_add_to_words_fst))
}

pub fn extract_numbers_from_words_fst(
    rtxn: &RoTxn<'_>,
    index: &Index,
    disabled_typos_terms: &DisabledTyposTerms,
) -> Result<BTreeSet<String>> {
    let mut removed_numbers = BTreeSet::new();
    let fst = index.words_fst(rtxn)?;
    let mut stream = fst.stream();
    // TODO use an automaton to only iterate over strings that are numbers
    //      (and thus starts with a digit)
    while let Some(bytes) = stream.next() {
        let word = std::str::from_utf8(bytes)?;
        if disabled_typos_terms.is_exact(word) {
            removed_numbers.insert(word.to_string());
        }
    }

    Ok(removed_numbers)
}

pub fn extract_numbers_from_non_exact_searchable_attributes(
    rtxn: &RoTxn<'_>,
    index: &Index,
    exact_attributes: &FieldIdMapWithMetadata,
    disabled_typos_terms: &DisabledTyposTerms,
) -> Result<BTreeSet<String>> {
    let mut numbers = BTreeSet::new();
    for result in index.word_fid_docids.remap_data_type::<DecodeIgnore>().iter(rtxn)? {
        let ((word, fid), _) = result?;
        let Some(metadata) = exact_attributes.metadata(fid) else { continue };
        if metadata.exact != PatternMatch::Match && disabled_typos_terms.is_exact(word) {
            numbers.insert(word.to_string());
        }
    }
    Ok(numbers)
}

pub fn migrate_word_docids(
    rtxn: &RoTxn<'_>,
    src: Database<Str, CboRoaringBitmapCodec>,
    wtxn: &mut RwTxn<'_>,
    dst: Database<Str, CboRoaringBitmapCodec>,
    words: &BTreeSet<String>,
) -> Result<()> {
    let src = src.remap_data_type::<Bytes>();
    let dst = dst.remap_data_type::<Bytes>();

    for word in words {
        let Some(docids_bytes) = src.get(rtxn, word)? else { continue };
        dst.put(wtxn, word, docids_bytes)?;
        src.delete(wtxn, word)?;
    }

    Ok(())
}

pub fn delete_old_fid_from_facet_databases<SD>(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    settings_delta: &SD,
    must_stop_processing: &MustStopProcessing,
    progress: &Progress,
) -> Result<()>
where
    SD: SettingsDelta + Sync,
{
    let mut remove_from_everywhere = BTreeSet::new();
    let mut remove_from_facet_search = BTreeSet::new();
    let mut remove_comparison_levels_only = BTreeSet::new();

    let old_fields_ids_map = settings_delta.old_fields_ids_map();
    let old_filterable_rules = settings_delta.old_filterable_rules();

    let new_fields_ids_map = settings_delta.new_fields_ids_map();
    let new_filterable_rules = settings_delta.new_filterable_rules();

    for (id, old_metadata) in old_fields_ids_map.iter_id_metadata() {
        if old_metadata.is_faceted(old_filterable_rules) != PatternMatch::Match {
            // This was not faceted, no need to delete it from the facet databases
            continue;
        }

        let Some(new_metadata) = new_fields_ids_map.metadata(id) else {
            // This field is no longer in the new fields ids map, delete it from everywhere
            remove_from_everywhere.insert(id);
            continue;
        };

        if new_metadata.is_faceted(new_filterable_rules) != PatternMatch::Match {
            // This field is no longer faceted, delete it from everywhere
            remove_from_everywhere.insert(id);
            continue;
        }

        // Check if the field still needs facet search databases
        let FilterableAttributesFeatures { facet_search: old_facet_search, filter: old_filter } =
            old_metadata.filterable_attributes_features(old_filterable_rules);
        let FilterableAttributesFeatures { facet_search: new_facet_search, filter: new_filter } =
            new_metadata.filterable_attributes_features(new_filterable_rules);

        if old_facet_search && !new_facet_search {
            // The field is no longer facet searchable, delete it from the facet search databases
            remove_from_facet_search.insert(id);
        }

        // Check if the field still needs facet level databases
        let FilterFeatures { equality: _, comparison: old_comparison } = old_filter;
        let old_asc_desc = old_metadata.is_asc_desc() == PatternMatch::Match;
        let old_sortable = old_metadata.is_sortable() == PatternMatch::Match;
        let is_old_comparison = old_sortable || old_asc_desc || old_comparison;

        let FilterFeatures { equality: _, comparison: new_comparison } = new_filter;
        let new_asc_desc = new_metadata.is_asc_desc() == PatternMatch::Match;
        let new_sortable = new_metadata.is_sortable() == PatternMatch::Match;
        let is_new_comparison = new_sortable || new_asc_desc || new_comparison;

        if is_old_comparison && !is_new_comparison {
            // Remove the comparison levels from the facets.
            remove_comparison_levels_only.insert(id);
        }
    }

    let Index {
        // filterable, sortable, distinct, :asc/:desc
        facet_id_exists_docids,
        facet_id_is_null_docids,
        facet_id_is_empty_docids,
        field_id_docid_facet_f64s,
        field_id_docid_facet_strings,

        // facet search
        facet_id_normalized_string_strings,
        facet_id_string_fst,

        // comparison, sortable, or :asc/:desc
        facet_id_f64_docids,
        facet_id_string_docids,
        ..
    } = index;

    // Deletes these fields IDs from all the filterable, facet and other datastructures.
    if !remove_from_everywhere.is_empty() {
        let databases: [Database<Bytes, DecodeIgnore>; _] = [
            facet_id_exists_docids.remap_types(),
            facet_id_is_null_docids.remap_types(),
            facet_id_is_empty_docids.remap_types(),
            field_id_docid_facet_f64s.remap_types(),
            field_id_docid_facet_strings.remap_types(),
            facet_id_normalized_string_strings.remap_types(),
            facet_id_string_fst.remap_types(),
            facet_id_f64_docids.remap_types(),
            facet_id_string_docids.remap_types(),
        ];

        progress.update_progress(IndexingStep::DeletingFromAllFilters);
        let (db_progress, db_progress_obj) = AtomicDatabaseStep::new(databases.len() as u32);
        progress.update_progress(db_progress_obj);

        for database in databases {
            if must_stop_processing.get() {
                return Err(Error::InternalError(InternalError::AbortedIndexation));
            }

            for id in remove_from_everywhere.iter().copied() {
                let mut iter = database.prefix_iter_mut(wtxn, &id.to_be_bytes())?;
                while iter.next().transpose()?.is_some() {
                    // safety: We don't keep any reference to the database.
                    unsafe { iter.del_current()? };
                }
            }

            db_progress.fetch_add(1, Ordering::Relaxed);
        }
    }

    // Delete the entries for these field IDs from the facet search datastructures.
    if !remove_from_facet_search.is_empty() {
        let databases: [Database<Bytes, DecodeIgnore>; _] =
            [facet_id_normalized_string_strings.remap_types(), facet_id_string_fst.remap_types()];

        progress.update_progress(IndexingStep::DeletingFromFacetsOnly);
        let (db_progress, db_progress_obj) = AtomicDatabaseStep::new(databases.len() as u32);
        progress.update_progress(db_progress_obj);

        // TODO merge with the above code
        for database in databases {
            if must_stop_processing.get() {
                return Err(Error::InternalError(InternalError::AbortedIndexation));
            }

            for id in remove_from_facet_search.iter().copied() {
                let mut iter = database.prefix_iter_mut(wtxn, &id.to_be_bytes())?;
                while iter.next().transpose()?.is_some() {
                    // safety: We don't keep any reference to the database.
                    unsafe { iter.del_current()? };
                }
            }

            db_progress.fetch_add(1, Ordering::Relaxed);
        }
    }

    // Deletes the levels > 0 for the entries corresponding to these
    // field IDs in the layered filter + comparison datastructures.
    if !remove_comparison_levels_only.is_empty() {
        let databases: [Database<Bytes, DecodeIgnore>; _] =
            [facet_id_f64_docids.remap_types(), facet_id_string_docids.remap_types()];

        progress.update_progress(IndexingStep::DeletingFromComparisonsOnly);
        let (db_progress, db_progress_obj) = AtomicDatabaseStep::new(databases.len() as u32);
        progress.update_progress(db_progress_obj);

        // TODO merge with the above code (or not?)
        for database in databases {
            if must_stop_processing.get() {
                return Err(Error::InternalError(InternalError::AbortedIndexation));
            }

            for id in remove_comparison_levels_only.iter().copied() {
                let mut iter = database.prefix_iter_mut(wtxn, &id.to_be_bytes())?;
                while let Some((key, _ignored)) = iter.next().transpose()? {
                    // We want to delete everything that is not from
                    // the level 0 as it provides equality comparisons.
                    //
                    // The first two bytes corresponds to the field ID
                    // while the third byte corresponds to the level.
                    if key.get(2).copied() != Some(0) {
                        // safety: We don't keep any reference to the database.
                        unsafe { iter.del_current()? };
                    }
                }
            }

            db_progress.fetch_add(1, Ordering::Relaxed);
        }
    }

    Ok(())
}

/// Deletes entries refering the provided
/// fids from the fid-based databases.
pub fn delete_old_fid_based_databases<SD>(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    settings_delta: &SD,
    must_stop_processing: &MustStopProcessing,
    progress: &Progress,
) -> Result<()>
where
    SD: SettingsDelta + Sync,
{
    // Get the fids to delete from the settings delta.
    // Compare the old and new fields ids map to find the fids that are no longer searchable.
    let fids_to_delete: BTreeSet<_> = {
        let old_fields_ids_map = settings_delta.old_fields_ids_map();
        let new_fields_ids_map = settings_delta.new_fields_ids_map();
        old_fields_ids_map
            .iter_id_metadata()
            .filter_map(|(id, metadata)| {
                if metadata.is_searchable() == PatternMatch::Match
                    && new_fields_ids_map
                        .metadata(id)
                        .is_none_or(|metadata| metadata.is_searchable() != PatternMatch::Match)
                {
                    Some(id)
                } else {
                    None
                }
            })
            .collect()
    };

    if fids_to_delete.is_empty() {
        return Ok(());
    };

    delete_old_fid_based_databases_from_fids(
        wtxn,
        index,
        must_stop_processing,
        &fids_to_delete,
        progress,
    )
}

/// Deletes entries related to field IDs that must no longer exist in the database.
/// Uses parallel fetching to speed up the deletion process.
pub fn delete_old_fid_based_databases_from_fids(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    must_stop_processing: &MustStopProcessing,
    fids_to_delete: &BTreeSet<u16>,
    progress: &Progress,
) -> Result<()> {
    let bounds = compute_fst_bounds(wtxn, index)?;

    progress.update_progress(SettingsIndexerStep::DeletingOldWordFidDocids);
    delete_old_word_fid_docids_parallel(
        wtxn,
        index,
        index.word_fid_docids.remap_data_type(),
        must_stop_processing,
        fids_to_delete,
        &bounds,
    )?;

    progress.update_progress(SettingsIndexerStep::DeletingOldFidWordCountDocids);
    delete_old_fid_word_count_docids(wtxn, index, must_stop_processing, fids_to_delete)?;

    progress.update_progress(SettingsIndexerStep::DeletingOldWordPrefixFidDocids);
    delete_old_word_fid_docids_parallel(
        wtxn,
        index,
        index.word_prefix_fid_docids.remap_data_type(),
        must_stop_processing,
        fids_to_delete,
        &bounds,
    )?;

    Ok(())
}

/// Use the FST to balance the work between threads
/// by generating appropriate word bounds.
fn compute_fst_bounds(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
) -> crate::Result<Vec<Option<Box<[u8]>>>> {
    let fst = index.words_fst(wtxn)?;

    let threads_count = rayon::current_num_threads() * 4;
    let keys_by_thread = fst.len().div_ceil(threads_count);

    // We iterate over the FST keys that represents the word dictionary and
    // roughly represents what can be found in the database we are cleaning.
    //
    // The database we are cleaning contains different words from the word
    // dictionary as it contains words from fields that are not indexed too
    // but it is mixed with indexed ones.
    //
    // We then divide equally the entries of the database to clean by
    // selecting ranges of keys that will be processed by each thread. We
    // also make sure not to specify the first and last keys to make sure
    // that if the fields to clean have keys that are higher or lower than
    // the first or last keys in the word dictionary we still find them.

    // Here we make sure to start with an unbounded
    // left bound for the first range
    let mut bounds = vec![None];
    let mut stream = fst.stream();
    let mut count = 0;
    while let Some(key) = stream.next() {
        let is_first = count == 0;
        let is_last = count == fst.len() - 1;

        // In this loop we make sure to account for every bounds
        // to divide the work between threads but not send the bounds
        // for the beginning or the end of the word dictionary
        if count % keys_by_thread == 0 && !(is_first || is_last) {
            bounds.push(Some(key.to_vec().into_boxed_slice()));
        }

        count += 1;
    }

    // We now push the last bound that
    // defines the end of the last range
    bounds.push(None);

    Ok(bounds)
}

/// Fetches keys to delete in parallel by using the FST bounds
/// to balance the work between threads.
fn fetch_keys_to_delete_in_parallel(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    database: Database<StrBEU16Codec, Unit>,
    fids_to_delete: &BTreeSet<u16>,
    bounds: &[Option<Box<[u8]>>],
) -> Result<LinkedList<Vec<Result<Vec<Box<[u8]>>>>>> {
    // We generate enough read transactions for each thread.
    let rtxns = iter::repeat_with(|| index.env.nested_read_txn(wtxn))
        .take(bounds.len().saturating_sub(1))
        .collect::<heed::Result<Vec<_>>>()?;

    // Run parallel fetching directly in the current rayon threadpool
    let results = rtxns
        .into_par_iter()
        .zip_eq(bounds.windows(2).collect::<Vec<_>>())
        .map(|(rtxn, win)| {
            let bound = match [win[0].as_deref(), win[1].as_deref()] {
                [None, None] => (Bound::Unbounded, Bound::Unbounded),
                [None, Some(end)] => (Bound::Unbounded, Bound::Excluded(end)),
                [Some(start), None] => (Bound::Included(start), Bound::Unbounded),
                [Some(start), Some(end)] => (Bound::Included(start), Bound::Excluded(end)),
            };

            let mut keys_to_delete = Vec::new();
            let iter = database.remap_types::<Bytes, DecodeIgnore>().range(&rtxn, &bound);
            for result in iter? {
                let (key_bytes, ()) = result?;
                let (_word, fid) =
                    StrBEU16Codec::bytes_decode(key_bytes).map_err(heed::Error::Decoding)?;

                if fids_to_delete.contains(&fid) {
                    keys_to_delete.push(key_bytes.to_vec().into_boxed_slice());
                }
            }

            Ok(keys_to_delete) as crate::Result<_>
        })
        .collect_vec_list();

    Ok(results)
}

/// Parallel version of delete_old_word_fid_docids that fetches keys in parallel
/// and then deletes them sequentially.
fn delete_old_word_fid_docids_parallel(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    database: Database<StrBEU16Codec, Unit>,
    must_stop_processing: &MustStopProcessing,
    fids_to_delete: &BTreeSet<u16>,
    bounds: &[Option<Box<[u8]>>],
) -> crate::Result<usize> {
    let results = fetch_keys_to_delete_in_parallel(wtxn, index, database, fids_to_delete, bounds)?;

    let database = database.remap_key_type::<Bytes>();
    let mut count = 0;
    for result in results.into_iter().flatten() {
        let keys = result?;
        if must_stop_processing.get() {
            return Err(Error::InternalError(InternalError::AbortedIndexation));
        }
        keys.into_iter().try_for_each(|key| {
            database.delete(wtxn, &key)?;
            count += 1;
            Ok(()) as Result<()>
        })?;
    }

    Ok(count)
}

fn delete_old_fid_word_count_docids(
    wtxn: &mut RwTxn<'_>,
    index: &Index,
    must_stop_processing: &MustStopProcessing,
    fids_to_delete: &BTreeSet<u16>,
) -> Result<(), Error> {
    let db = index.field_id_word_count_docids.remap_data_type::<DecodeIgnore>();
    for &fid_to_delete in fids_to_delete {
        if must_stop_processing.get() {
            return Err(Error::InternalError(InternalError::AbortedIndexation));
        }

        let mut iter = db.prefix_iter_mut(wtxn, &(fid_to_delete, 0))?;
        while let Some(((fid, _word_count), ())) = iter.next().transpose()? {
            debug_assert_eq!(fid, fid_to_delete);
            // safety: We don't keep any references to the data.
            unsafe { iter.del_current()? };
        }
    }

    Ok(())
}

fn indexer_memory_settings(
    current_num_threads: usize,
    grenad_parameters: GrenadParameters,
) -> (GrenadParameters, usize) {
    // We reduce the actual memory used to 5%. The reason we do this here and not in Meilisearch
    // is because we still use the old indexer for the settings and it is highly impacted by the
    // max memory. So we keep the changes here and will remove these changes once we use the new
    // indexer to also index settings. Related to #5125 and #5141.
    let grenad_parameters = GrenadParameters {
        max_memory: grenad_parameters.max_memory.map(|mm| mm * 5 / 100),
        ..grenad_parameters
    };

    // 5% percent of the allocated memory for the extractors, or min 100MiB
    // 5% percent of the allocated memory for the bbqueues, or min 50MiB
    //
    // Minimum capacity for bbqueues
    let minimum_total_bbbuffer_capacity = 50 * 1024 * 1024 * current_num_threads;
    // 50 MiB
    let minimum_total_extractors_capacity = minimum_total_bbbuffer_capacity * 2;

    let (grenad_parameters, total_bbbuffer_capacity) = grenad_parameters.max_memory.map_or(
        (
            GrenadParameters {
                max_memory: Some(minimum_total_extractors_capacity),
                ..grenad_parameters
            },
            minimum_total_bbbuffer_capacity,
        ), // 100 MiB by thread by default
        |max_memory| {
            let total_bbbuffer_capacity = max_memory.max(minimum_total_bbbuffer_capacity);
            let new_grenad_parameters = GrenadParameters {
                max_memory: Some(max_memory.max(minimum_total_extractors_capacity)),
                ..grenad_parameters
            };
            (new_grenad_parameters, total_bbbuffer_capacity)
        },
    );

    LOG_MEMORY_METRICS_ONCE.call_once(|| {
        tracing::debug!(
            "Indexation allocated memory metrics - \
            Total BBQueue size: {total_bbbuffer_capacity}, \
            Total extractor memory: {:?}",
            grenad_parameters.max_memory,
        );
    });

    (grenad_parameters, total_bbbuffer_capacity)
}
