use crate::{find_files::*, Client, Downloaded, Error};
use std::collections::{BTreeSet, HashMap, HashSet};
use std::ffi::CString;
use std::io::Write;
use std::path::{Path, PathBuf};
use std::sync::{Arc, Mutex};
use tokio::io::{AsyncBufReadExt, AsyncWriteExt};
use tracing::*;

use crate::deb;

/// The result of downloading/extracting a package.
#[derive(Debug, Clone)]
pub struct Packages {
    /// Paths of each of the extracted packages, in reverse order from
    /// the root (i.e. the root is the last element).
    pub result: Vec<Arc<PathBuf>>,
    /// Paths to directories (i.e. */usr/bin, */usr/lib etc), useful
    /// to create $PATH or $CFLAGS from the client.
    pub paths: Vec<Arc<String>>,
}

#[derive(Debug)]
struct Vertex<'a> {
    pkg: deb::Stanza<'a>,
    downloaded: Downloaded,
    index: Option<usize>,
    lowlink: usize,
    on_stack: bool,
    scc: usize,
    deps: Vec<usize>,
    context_path: Option<Arc<PathBuf>>,
    final_path: Option<Arc<PathBuf>>,
    deps_paths: Vec<Arc<PathBuf>>,
    last_transitive: (usize, usize),
    transitive_deps: Vec<Arc<(usize, PathBuf)>>,
    transitive_deps_h: BTreeSet<Arc<(usize, PathBuf)>>,
    ld_path: Vec<Arc<PathBuf>>,
    ld_path_h: BTreeSet<Arc<PathBuf>>,
    files: BTreeSet<Arc<String>>,
    v: usize,
}

/// Messages from the extractor.
#[derive(Debug)]
pub enum Msg {
    /// Downloading
    Downloading(String),
    /// Result
    Ok(Packages),
    /// Error
    Error(Error),
}

/// Download a Debian package and its dependency DAG from package
/// indices and the package's name.
pub async fn download_extract_deps<F: futures::Sink<Msg> + Clone + Send + Unpin + 'static>(
    index: &[deb::Index],
    client: &Client,
    package: &str,
    link_extra: &[(regex::Regex, regex::Regex)],
    tx: F,
) -> Result<Packages, Error>
where
    F::Error: std::fmt::Debug,
{
    let Some(pkg) = multi_lookup(index, &package).await else {
        return Err(Error::PackageNotFound {
            pkg: package.to_string(),
        });
    };

    let mut vertices = Vec::new();

    // We first run a DFS of the dependencies and store them in
    // `vertices` for later.
    let mut stack = vec![(pkg, None)];
    let mut seen: HashMap<_, (Vec<&str>, usize)> = HashMap::new();
    while let Some((pkg, rx)) = stack.pop() {
        info!("{:?}", pkg);
        if let Some(rx) = rx {
            let downloaded: Result<Result<Downloaded, Error>, _> = rx.await;
            let downloaded = downloaded.unwrap()?;
            seen.get_mut(pkg.package).unwrap().1 = vertices.len();
            debug!("initial deps: {:?}", seen.get(pkg.package).unwrap());
            let v_len = vertices.len();
            vertices.push(Vertex {
                downloaded,
                deps: Vec::new(),
                pkg,
                context_path: None,
                deps_paths: Vec::new(),
                files: BTreeSet::new(),
                final_path: None,
                ld_path: Vec::new(),
                ld_path_h: BTreeSet::new(),
                index: None,
                lowlink: 0,
                on_stack: false,
                scc: 0,
                last_transitive: (0, 0),
                transitive_deps: Vec::new(),
                transitive_deps_h: BTreeSet::new(),
                v: v_len,
            });
        } else if !seen.contains_key(pkg.package) {
            let rx = spawn_extract(client.clone(), &pkg, tx.clone()).await;
            let depends = pkg.depends.clone();
            let pkg_package = pkg.package;
            stack.push((pkg, Some(rx)));
            let deps = push_deps(&depends, index, &mut stack).await;
            seen.insert(pkg_package, (deps, 0));
        }
    }

    // Turn dependencies into their index in `vertices`.
    for v in vertices.iter_mut() {
        v.deps = seen
            .get(v.pkg.package)
            .unwrap()
            .0
            .iter()
            .map(|x| seen.get(x).unwrap().1)
            .collect()
    }

    let sccs = tarjan(&mut vertices);
    debug!("sccs: {:?}", sccs);

    let mut result = Vec::new();
    let files = Arc::new(Mutex::new(HashMap::new()));

    let mut ld_paths = HashSet::new();
    for scc in sccs.iter() {
        ld_paths.clear();

        // Two independent missions in one loop:
        // - Hash the context
        // - Collect the `ld_paths` of each package in the SCC.
        for v in scc.iter() {
            hash_context(&mut vertices, *v, &client.store_path, link_extra);

            // Find the extra ld paths to look for.
            vertices[*v].add_ld_paths().unwrap();
            ld_paths.extend(vertices[*v].ld_path.iter().cloned());
            for dep in vertices[*v].deps.iter() {
                for l in vertices[*dep].ld_path.iter() {
                    ld_paths.insert(l.clone());
                }
            }
        }

        // Once we have the ld paths of the entire SCC, add them to
        // each vertex of the SCC.
        for v in scc.iter() {
            for l in ld_paths.iter().cloned() {
                if vertices[*v].ld_path_h.insert(l.clone()) {
                    vertices[*v].ld_path.push(l.clone());
                }
            }
        }

        // Then, find the libraries in the `ld_paths` of each package
        // of the SCC.
        for v in scc.iter() {
            let a = vertices[*v].transitive_deps.len();
            vertices[*v].find_libs();
            vertices[*v].last_transitive = (a, vertices[*v].transitive_deps.len());
        }

        // And finalize each of the component (patch ELFs etc).
        for v in scc.iter() {
            span!(Level::DEBUG, "Finalize");
            let f = finalize(&mut vertices, &sccs, client, link_extra, &files, *v).await?;
            vertices[*v].final_path = Some(f.clone());
            result.push(f)
        }
    }
    let paths = vertices.last().unwrap().files.iter().cloned().collect();
    debug!("paths = {:?}", paths);
    debug!("result = {:?}", result);
    Ok(Packages { result, paths })
}

fn tarjan(vertices: &mut [Vertex]) -> Vec<Vec<usize>> {
    let mut sccs = Vec::new();
    let mut stack = Vec::new();
    let mut index = 0;

    #[derive(Debug)]
    struct C {
        vi: usize,
        d: usize,
    }
    let mut call_stack = vec![C {
        vi: vertices.len() - 1,
        d: 0,
    }];

    'outer: while let Some(mut c) = call_stack.pop() {
        debug!(
            "visiting {:?}: {:?} {:?} {:?}",
            c, vertices[c.vi].pkg.package, vertices[c.vi].index, vertices[c.vi].lowlink
        );
        if vertices[c.vi].index.is_none() {
            let ref mut v = vertices[c.vi];
            v.index = Some(index);
            v.lowlink = index;
            v.on_stack = true;
            index += 1;
            stack.push(c.vi);
        }
        if c.d > 0 {
            // Returning from the recursive call.
            let dep = vertices[c.vi].deps[c.d - 1];
            vertices[c.vi].lowlink = vertices[c.vi].lowlink.min(vertices[dep].lowlink);
        }
        while c.d < vertices[c.vi].deps.len() {
            let wi = vertices[c.vi].deps[c.d];
            debug!("dep of {:?}: {:?} ({:?})", c.vi, wi, vertices[c.vi].deps);
            if let Some(index) = vertices[wi].index {
                if vertices[wi].on_stack {
                    vertices[c.vi].lowlink = vertices[c.vi].lowlink.min(index)
                }
                c.d += 1;
            } else {
                c.d += 1;
                call_stack.push(c);
                call_stack.push(C { vi: wi, d: 0 });
                // Recursive call.
                continue 'outer;
            }
        }
        if Some(vertices[c.vi].lowlink) == vertices[c.vi].index {
            let mut scc = Vec::new();
            debug!("new scc");
            while let Some(p) = stack.pop() {
                debug!("-> {:?} {:?}", p, vertices[p].pkg.package);
                vertices[p].scc = sccs.len();
                vertices[p].on_stack = false;
                scc.push(p);
                if p == c.vi {
                    break;
                }
            }
            sccs.push(scc)
        }
    }
    sccs
}

async fn add_subst(downloaded: PathBuf, target: &Path, files: Files) -> Result<(), std::io::Error> {
    let mut files = files.lock().unwrap();
    for (f, m) in find_files(downloaded.clone())? {
        if !m.is_dir() {
            if let Ok(p) = f.strip_prefix(&downloaded) {
                use std::collections::hash_map::Entry;
                if let Entry::Vacant(e) = files.entry(p.to_path_buf()) {
                    debug!("add_subst {:?} -> {:?}", p, target);
                    e.insert(target.to_path_buf());
                }
            }
        }
    }
    Ok(())
}

async fn hash_reader(
    file: &Path,
    mut reader: impl tokio::io::AsyncReadExt + Unpin,
    hasher: &mut blake3::Hasher,
) -> std::io::Result<u64> {
    let mut buffer = [0; 65536];
    let mut total = 0;
    loop {
        match reader.read(&mut buffer).await {
            Ok(0) => return Ok(total),
            Ok(n) => {
                hasher.update(&buffer[..n]);
                total += n as u64;
            }
            Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue,
            Err(e) => {
                return Err(e);
            }
        }
    }
}

async fn extract_task(client: &Client, download: &mut Downloaded) -> Result<(), Error> {
    debug!("extracting {:?}", download);
    let path = download.path.with_extension("");
    let lock = client.lock_store_path(&path).await;
    let p = path.clone();
    let dp = download.path.clone();
    match tokio::task::spawn_blocking(move || {
        let mut f = std::io::BufReader::new(std::fs::File::open(&dp)?);
        let d = match deb::Deb::read(&mut f) {
            Ok(d) => d,
            Err(e) => {
                std::fs::remove_file(&dp).unwrap_or(());
                return Err(e.into());
            }
        };
        std::fs::create_dir_all(&p).unwrap_or(());

        d.decompress(&mut f, &p)
    })
    .await
    .unwrap()
    {
        Ok(()) => {
            drop(lock);
            download.path = path;
            Ok::<(), Error>(())
        }
        Err(e) => {
            std::fs::remove_dir_all(&path).unwrap_or(());
            std::fs::remove_file(&download.path).unwrap_or(());
            drop(lock);
            Err(e.into())
        }
    }
}

async fn spawn_extract<'a, S: futures::Sink<Msg> + Send + Unpin + 'static>(
    client: Client,
    stanza: &deb::Stanza<'a>,
    log_tx: S,
) -> tokio::sync::oneshot::Receiver<Result<Downloaded, Error>>
where
    S::Error: std::fmt::Debug,
{
    let url = client.url(stanza.file_name.as_deref());
    let sha256 = stanza.sha256.unwrap().to_string();
    let (tx, rx) = tokio::sync::oneshot::channel();
    tokio::spawn(async move {
        let permit = client.download_sem.clone().acquire_owned().await.unwrap();
        info!("downloading {:?}", url);
        let (mut task, _) = match client.download_url(&url, &sha256, log_tx).await {
            Ok(x) => x,
            Err(e) => {
                tx.send(Err(e)).unwrap_or(());
                return Ok(());
            }
        };
        let is_extracted = std::fs::metadata(&task.path.with_extension("")).is_ok();
        info!("finished downloading {:?}", url);
        if !is_extracted {
            // Sets extension
            if let Err(e) = extract_task(&client, &mut task).await {
                info!("finished extracting {:?} {:?}", url, e);
                tx.send(Err(e)).unwrap_or(());
            } else {
                info!("finished extracting {:?}, Ok", url);
                tx.send(Ok(task)).unwrap_or(());
            }
            info!("sent {:?}", url);
        } else {
            task.path.set_extension("");
            tx.send(Ok(task)).unwrap_or(());
        }
        drop(permit);
        Ok::<_, Error>(())
    });
    rx
}

async fn multi_lookup<'a>(index: &'a [deb::Index], package: &str) -> Option<deb::Stanza<'a>> {
    for ind in index {
        if let Some(i) = ind.lookup_async(package).await {
            return Some(i);
        }
    }
    for ind in index {
        if let Some(i) = ind.lookup_virtual_async(package).await.into_iter().next() {
            return Some(i);
        }
    }
    debug!("multi_lookup: package {:?} not found", package);
    None
}

type Files = Arc<Mutex<HashMap<PathBuf, PathBuf>>>;

fn hash_context(
    vertices: &mut [Vertex],
    v: usize,
    store_path: &Path,
    link_extra: &[(regex::Regex, regex::Regex)],
) {
    let mut context_hasher = blake3::Hasher::new();
    context_hasher.update(vertices[v].pkg.sha256.unwrap().as_bytes());
    for d in vertices[v].deps.iter() {
        let w = &vertices[*d];
        if w.scc == vertices[v].scc {
            // If in the same SCC, we can't know anything other than the SHA256.
            context_hasher.update(w.pkg.sha256.unwrap().as_bytes());
        } else {
            context_hasher.update(w.final_path.as_ref().unwrap().to_str().unwrap().as_bytes());
        }
    }
    for (a, b) in link_extra {
        context_hasher.update(b"\0");
        context_hasher.update(a.to_string().as_bytes());
        context_hasher.update(b"\0");
        context_hasher.update(b.to_string().as_bytes());
    }
    let s = data_encoding::HEXLOWER.encode(context_hasher.finalize().as_bytes());
    debug!("hash context {:?} {:?}", vertices[v].pkg.package, s);
    vertices[v].context_path = Some(Arc::new(store_path.join(s)));
}

impl<'a> Vertex<'a> {
    /// Some libexec files (e.g. gcc) are searched relative to their
    /// original package /bin path. Propagating the /usr/libexec
    /// folder avoids overrides and ad-hoc code in the client.
    async fn link_extra<S: AsRef<str> + std::fmt::Debug>(
        &mut self,
        final_path: &Path,
        extra: &[S],
    ) -> Result<(), Error> {
        debug!("linking extra path in {:?}: {:?}", final_path, extra);
        for path in extra {
            let path = path.as_ref();
            let final_extra = final_path.join(path);

            for d in self.deps_paths.iter() {
                let d_extra = d.join(path);
                let Ok(meta) = tokio::fs::metadata(&d_extra).await else {
                    continue;
                };
                let mut stack = vec![(d_extra.clone(), meta)];
                while let Some((elt, meta)) = stack.pop() {
                    if let Ok(mut dir) = tokio::fs::read_dir(&elt).await {
                        let p = elt.strip_prefix(&d_extra).unwrap();
                        tokio::fs::create_dir_all(&final_extra.join(&p)).await?;
                        while let Some(e) = dir.next_entry().await? {
                            stack.push((e.path(), e.metadata().await?));
                        }
                    } else if meta.is_file() {
                        let p = elt.strip_prefix(&d_extra).unwrap();
                        debug!("libexec hard link {:?} to {:?}", elt, final_extra.join(&p));
                        tokio::fs::hard_link(&elt, &final_extra.join(&p))
                            .await
                            .unwrap_or(());
                    }
                }
            }
        }
        Ok(())
    }

    fn add_ld_paths(&mut self) -> Result<(), std::io::Error> {
        let mut ld_so = self.downloaded.path.join("etc");
        ld_so.push("ld.so.conf.d");
        if let Ok(dir) = std::fs::read_dir(&ld_so) {
            for f in dir {
                let f = f?;
                if let Ok(f) = std::fs::read_to_string(&f.path()) {
                    for path in f.lines().rev().filter(|x| !x.starts_with("#")) {
                        let path = Path::new(path);
                        if self.ld_path_h.insert(Arc::new(path.to_path_buf())) {
                            self.ld_path.push(Arc::new(path.to_path_buf()))
                        }
                    }
                }
            }
        }
        if !self.ld_path.is_empty() {
            info!("ld_path: {:?}", self.ld_path)
        }
        Ok(())
    }

    /// Let `path` be the path to the raw extracted deb package, and
    /// `dest` be the final destination of this package in the store
    /// (when taking the package's context into account).
    ///
    /// Then, `find_libs` finds all paths in `path` that match the
    /// patterns in self.ld_path (`self.ld_path` paths are of the form
    /// `/usr/lib/x86_64-linux`), and add their equivalent in `dest` to
    /// `self.transitive_deps`.
    ///
    /// This makes sure that packages depending on `self` will be able
    /// to find the correct paths to these libs.
    fn find_libs(&mut self) {
        for ld in self.ld_path.iter() {
            let path = self.downloaded.path.join(ld.strip_prefix("/").unwrap());
            if std::fs::metadata(&path).is_ok() {
                let path = Arc::new((self.v, ld.strip_prefix("/").unwrap().to_path_buf()));
                if self.transitive_deps_h.insert(path.clone()) {
                    debug!("find_libs {:?}: adding {:?}", self.pkg.package, path);
                    self.transitive_deps.push(path);
                }
            }
        }
    }
}

async fn patch_elf<'a>(
    vertices: &mut [Vertex<'a>],
    v: usize,
    f: &Path,
    dest_path: &Path,
    files: &Files,
) -> Result<bool, Error> {
    use elfedit::*;
    info!("patch_elf {:?}", f);
    let file = std::fs::OpenOptions::new()
        .read(true)
        .write(true)
        .open(&f)?;

    let mut elf = match Elf::open(&file) {
        Ok(elf) => elf,
        Err(e) => {
            info!("error opening {:?}: {:?}", file, e);
            return Ok(false);
        }
    };
    info!("patching {:?}", f);
    let Some(parsed) = elf.parse().unwrap() else {
        info!("No dynamic section");
        return Ok(false);
    };
    let needed: Vec<_> = parsed
        .needed()
        .map(|x| x.unwrap().to_str().unwrap().to_string())
        .collect();
    let interp = parsed.interpreter();
    if let Some(interp) = interp.unwrap() {
        let interp = interp.to_str().unwrap();
        let files = files.lock().unwrap();

        let p = Path::new(interp).strip_prefix("/").unwrap();

        let subst = if let Some(subst) = files.get(p) {
            subst.join(p)
        } else if interp.starts_with("/usr")
            || interp.starts_with("/lib")
            || interp.starts_with("/bin")
        {
            // https://www.freedesktop.org/wiki/Software/systemd/TheCaseForTheUsrMerge/
            let p2 = "usr".to_string() + interp;
            let p2 = Path::new(&p2);
            debug!("{:?}", p2);
            if let Some(subst) = files.get(p2) {
                subst.join(p2)
            } else {
                error!("No subst for {:?}", p2);
                let mut p2 = p2.to_path_buf();
                while p2.pop() {
                    debug!("p2 = {:?} {:?}", p2, files.get(&p2));
                }
                return Ok(false);
            }
        } else {
            // TODO: not sure what else to do here, we
            // might want to set the interpreter to a
            // different value (equivalent to "recompiling
            // everything" on Nix).
            info!("Interpreter is {interp}. Already patched?");
            return Ok(false);
        };
        let subst = CString::new(subst.to_str().unwrap()).unwrap();
        info!("set interpreter {:?}", subst);
        elf.set_interpreter(subst.to_bytes_with_nul());
    } else if needed.is_empty() {
        // No need to patch
        return Ok(false);
    }

    let mut deps_h = BTreeSet::new();
    let mut path = String::new();
    debug!("needed: {:?} -> {:?}", f, needed);
    let mut satisfied = HashMap::new();
    // First, prefer local deps.
    for ld in vertices[v].ld_path.iter() {
        let mut p = vertices[v]
            .context_path
            .clone()
            .unwrap()
            .join(ld.strip_prefix("/").unwrap());
        let mut at_least_one = false;
        for n in needed.iter() {
            let e = satisfied.entry(n);
            use std::collections::hash_map::Entry;
            if let Entry::Occupied(_) = e {
                continue;
            }

            p.push(&n);
            debug!("trying local path {:?}", p);
            if tokio::fs::metadata(&p).await.is_ok() {
                if let Entry::Vacant(e) = e {
                    e.insert(());
                }
                at_least_one = true;
                p.pop();
                break;
            } else {
                p.pop();
            }
        }
        if at_least_one {
            if !path.is_empty() {
                path.push(':')
            }
            path.push_str(p.to_str().unwrap())
        }
    }

    for dep_ in vertices[v].transitive_deps.iter().rev() {
        let (dep, dep_path) = dep_.as_ref();
        if !deps_h.insert(dep) {
            continue;
        }
        let mut dep = if vertices[*dep].scc == vertices[v].scc {
            vertices[*dep].context_path.clone().unwrap().join(dep_path)
        } else {
            vertices[*dep].final_path.clone().unwrap().join(dep_path)
        };
        debug!("dep of {:?}: {:?}", f, dep);
        let mut is_needed = false;
        for n in needed.iter() {
            let e = satisfied.entry(n);
            use std::collections::hash_map::Entry;
            if let Entry::Occupied(_) = e {
                continue;
            }
            dep.push(&n);
            let exists = tokio::fs::metadata(&dep).await.is_ok();
            if exists {
                if let Entry::Vacant(e) = e {
                    e.insert(());
                }
                debug!("exists {:?}", dep);
                is_needed = true;
            }
            dep.pop();
        }
        if !is_needed {
            continue;
        }
        if !path.is_empty() {
            path.push(':')
        }
        path.push_str(dep.to_str().unwrap());
    }

    /*
    // Add potential local libs.
    let mut last_added = None;
    for (d, _) in find_files(vertices[v].downloaded.path.clone())? {
        if last_added.as_deref() == d.parent() {
            continue;
        }
        for n in needed.iter() {
            if d.file_name().unwrap().to_str().unwrap() == n {
                last_added = d.parent().map(|x| x.to_path_buf());
                if !path.is_empty() {
                    path.push(':')
                }
                let suffix = d
                    .parent()
                    .unwrap()
                    .strip_prefix(&vertices[v].downloaded.path)
                    .unwrap();
                path.push_str(
                    vertices[v]
                        .context_path
                        .as_ref()
                        .unwrap()
                        .join(suffix)
                        .to_str()
                        .unwrap(),
                );
            }
        }
    }
    */
    path.push('\0');
    info!("Setting path {:?}", path);
    if path.len() > 1 {
        elf.set_runpath(&path.as_bytes());
    }

    debug!("patching into {:?}", dest_path);
    Ok(elf.update(Some(dest_path)).unwrap()) // map_err(From::from)
}

async fn finalize<'a>(
    vertices: &mut [Vertex<'a>],
    sccs: &[Vec<usize>],
    client: &Client,
    link_extra: &[(regex::Regex, regex::Regex)],
    files: &Files,
    v: usize,
) -> Result<Arc<PathBuf>, Error> {
    debug!(
        "finalize {:?} {:#?}",
        vertices[v].pkg.package, vertices[v].transitive_deps
    );

    let mut ld_path = std::mem::replace(&mut vertices[v].ld_path, Vec::new());
    let mut ld_path_h = std::mem::replace(&mut vertices[v].ld_path_h, BTreeSet::new());
    let mut transitive_deps = std::mem::replace(&mut vertices[v].transitive_deps, Vec::new());
    let mut transitive_deps_h =
        std::mem::replace(&mut vertices[v].transitive_deps_h, BTreeSet::new());
    let mut deps_paths = Vec::new();

    for dep in vertices[v].deps.iter() {
        debug!(
            "dep: {:?} -> {:?} {:?}",
            vertices[v].pkg.package, dep, vertices[*dep].pkg.package
        );

        let direct = if vertices[*dep].scc == vertices[v].scc {
            vertices[*dep].context_path.clone().unwrap()
        } else {
            vertices[*dep].final_path.clone().unwrap()
        };

        for ld in vertices[*dep].ld_path.iter() {
            if ld_path_h.insert(ld.clone()) {
                ld_path.push(ld.clone());
            }
            let l = ld.strip_prefix("/").unwrap();
            if std::fs::metadata(&direct.join(l)).is_ok() {
                let path = Arc::new((*dep, l.to_path_buf()));
                if transitive_deps_h.insert(path.clone()) {
                    transitive_deps.push(path);
                }
            }
        }

        for d in vertices[*dep].transitive_deps.iter() {
            if transitive_deps_h.insert(d.clone()) {
                debug!(
                    "adding transitive dep: {:?} -> {:?}",
                    vertices[v].pkg.package, d
                );
                transitive_deps.push(d.clone());
            }
        }

        debug!(
            "adding direct dep: {:?} {:?} {:?}",
            vertices[*dep].scc, vertices[v].scc, direct
        );
        deps_paths.push(direct)
    }

    debug!("transitive {:#?}", transitive_deps);

    // Direct deps should come after transitive ones, in order to be
    // picked up earlier when patching the ELFs.
    for dep in vertices[v].deps.iter() {
        let direct = if vertices[*dep].scc == vertices[v].scc {
            vertices[*dep].context_path.clone().unwrap()
        } else {
            vertices[*dep].final_path.clone().unwrap()
        };

        for ld in vertices[*dep].ld_path.iter() {
            let l = ld.strip_prefix("/").unwrap();
            if std::fs::metadata(&direct.join(l)).is_ok() {
                let path = Arc::new((*dep, l.to_path_buf()));
                // Push even if it already exists since we need direct
                // deps to come after indirect ones.
                transitive_deps.push(path);
            }
        }
    }

    vertices[v].ld_path = ld_path;
    vertices[v].ld_path_h = ld_path_h;
    vertices[v].transitive_deps = transitive_deps;
    vertices[v].transitive_deps_h = transitive_deps_h;
    vertices[v].deps_paths = deps_paths;

    let dest = vertices[v].context_path.clone().unwrap();

    let lock = client.lock_store_path(&*dest).await;

    let base_package_name = vertices[v]
        .pkg
        .file_name
        .unwrap()
        .split('/')
        .last()
        .unwrap();
    let base_package_name = Path::new(&base_package_name).with_extension("");
    let base_package_name = base_package_name.to_str().unwrap();

    let final_path = if std::fs::metadata(&*dest).is_err() {
        info!(
            "create final path for {dest:?} ({:?})",
            vertices[v].pkg.package
        );
        match create_final_path(
            client,
            &files,
            vertices,
            sccs,
            v,
            &dest,
            &base_package_name,
            link_extra,
        )
        .await
        {
            Ok(x) => x,
            Err(e) => {
                tokio::fs::remove_dir_all(&*dest).await.unwrap_or(());
                return Err(e);
            }
        }
    } else {
        info!("found, no patching: {:?}", dest);
        let mut output_hasher = blake3::Hasher::new();
        let blakesums = dest.join("blake3sums");
        let file = match tokio::fs::File::open(&blakesums).await {
            Ok(file) => file,
            Err(e) => {
                error!(
                    "Error {:?} {:?}: {:?}",
                    blakesums, vertices[v].downloaded.path, e
                );
                return Err(e.into());
            }
        };
        hash_reader(&blakesums, file, &mut output_hasher).await?;

        let r =
            tokio::io::BufReader::new(tokio::fs::File::open(&dest.join("paths")).await.unwrap());
        let mut l = r.lines();
        while let Some(l) = l.next_line().await? {
            vertices[v].files.insert(Arc::new(l));
        }

        client.store_path.join(&format!(
            "{}-{}",
            data_encoding::HEXLOWER.encode(output_hasher.finalize().as_bytes()),
            base_package_name,
        ))
    };
    let final_path = Arc::new(final_path);

    add_subst(vertices[v].downloaded.path.clone(), &dest, files.clone()).await?;

    info!("symlink {:?} {:?}", vertices[v].downloaded.path, final_path);
    match std::os::unix::fs::symlink(&*dest, &*final_path) {
        Ok(()) => (),
        Err(e) if e.kind() == std::io::ErrorKind::AlreadyExists => {
            let got = std::fs::read_link(&*final_path)?;
            debug!("Path already exists, previous value {:?}", got);
            // This situation means that we've come to the same
            // result via different build recipes.
            /*
                if dest != got {
                return Err(Error::WrongResultSymlink {
                expected: dest,
                got,
            });
            }
                 */
        }
        Err(e) => return Err(e.into()),
    }
    drop(lock);
    info!("done with {:?}", vertices[v].pkg.package);
    Ok(final_path)
}

async fn copy(
    hashing: &mut Vec<tokio::task::JoinHandle<Result<Option<(PathBuf, String)>, Error>>>,
    from: &Path,
    to: &Path,
) -> Result<(), std::io::Error> {
    let mut stack = vec![from.to_path_buf()];
    while let Some(elt) = stack.pop() {
        let dir = tokio::fs::read_dir(&elt).await;
        debug!("copy {:?}", dir);
        if let Ok(mut dir) = dir {
            let p = elt.strip_prefix(&from).unwrap();
            tokio::fs::create_dir_all(&to.join(&p)).await.unwrap();
            while let Some(e) = dir.next_entry().await.unwrap() {
                stack.push(e.path());
            }
        } else {
            let p = elt.strip_prefix(&from).unwrap();
            if p == Path::new("blake3sums") {
                continue;
            }
            debug!("copy {:?} to {:?}", elt, to.join(&p));
            let to_p = to.join(&p);
            tokio::fs::hard_link(&elt, &to_p).await.unwrap_or(());
            let p = p.to_path_buf();
            hashing.push(tokio::spawn(async move {
                // hash + write
                info!("copy, hashing {:?}", to_p);
                if let Ok(file) = tokio::fs::File::open(&to_p).await {
                    let mut hasher = blake3::Hasher::new();
                    hash_reader(&to_p, file, &mut hasher).await.unwrap();
                    let hex = data_encoding::HEXLOWER.encode(hasher.finalize().as_bytes());
                    Ok::<_, Error>(Some((p, hex)))
                } else {
                    Ok(None)
                }
            }));
        }
    }
    Ok(())
}

async fn create_final_path<'a>(
    client: &Client,
    files: &Files,
    vertices: &mut [Vertex<'a>],
    sccs: &[Vec<usize>],
    v: usize,
    dest: &Path,
    base_package_name: &str,
    link_extra: &[(regex::Regex, regex::Regex)],
) -> Result<PathBuf, Error> {
    // Link the required libexec before hashing.
    let tmp = async_tempfile::TempDir::new_in(dest.parent().unwrap()).await?;
    vertices[v]
        .link_extra(&tmp.dir_path(), &["usr/libexec", "usr/lib/gcc"])
        .await
        .unwrap();

    let scc = vertices[v].scc;

    let mut hashing = Vec::new();
    for (pkg, dep) in link_extra {
        if pkg.is_match(vertices[v].pkg.package) {
            for s in &sccs[..scc] {
                for &d in s.iter() {
                    if dep.is_match(vertices[d].pkg.package) {
                        debug!(
                            "match, copying {:?} to {:?}",
                            vertices[d], vertices[v].context_path
                        );
                        copy(
                            &mut hashing,
                            &vertices[d].context_path.clone().unwrap(),
                            &tmp.dir_path(),
                        )
                        .await?;
                    }
                }
            }
        }
    }

    // Patch the ELFs, now that we have all the deps.
    let mut hashes = Vec::with_capacity(hashing.len());
    debug!("create_final_path {:?}", vertices[v].downloaded.path);
    for (f, meta) in find_files(vertices[v].downloaded.path.to_path_buf())? {
        debug!("f = {:?}", f);
        let rel = f.strip_prefix(&vertices[v].downloaded.path).unwrap();
        let dest_path = tmp.dir_path().join(&rel);

        if meta.is_dir() {
            tokio::fs::create_dir_all(dest_path).await.unwrap_or(());
            continue;
        }

        if meta.is_symlink() {
            // Relink the file to the subst.
            let target = tokio::fs::read_link(&f).await?;
            debug!("relink {:?} -> {:?} {:?}", f, target, target.is_relative());
            let subst = {
                let l = files.lock().unwrap();
                let target_rel = rel.parent().unwrap().join(&target);
                if let Some(subst) = l.get(&target_rel) {
                    Some(subst.join(&target_rel))
                } else {
                    None
                }
            };
            if let Some(subst) = subst {
                debug!("relink to {:?}", dest_path);
                tokio::fs::symlink(&subst, &dest_path).await?;
                hashes.push((f, subst.to_str().unwrap().to_string()))
            } else {
                // Leave the symlink untouched
                // tokio::fs::create_dir_all(dest_path.parent().unwrap()).await.unwrap_or(());
                debug!("symlink {:?} {:?} {:?}", target, dest_path, f);
                tokio::fs::symlink(&target, &dest_path).await?;
                hashes.push((f, target.to_str().unwrap().to_string()));
            }
            continue;
        }

        if !patch_elf(vertices, v, &f, &dest_path, &files)
            .await
            .unwrap_or(false)
        {
            // Hard link
            debug!("hard link {:?} {:?}", f, dest_path);
            tokio::fs::hard_link(&f, &dest_path).await.unwrap_or(());
        }

        let f = rel.to_path_buf();
        hashing.push(tokio::spawn(async move {
            // hash + write
            info!("create_final_path: hashing {:?}", f);
            if let Ok(file) = tokio::fs::File::open(&dest_path).await {
                let mut hasher = blake3::Hasher::new();
                hash_reader(&dest_path, file, &mut hasher).await.unwrap();
                let hex = data_encoding::HEXLOWER.encode(hasher.finalize().as_bytes());
                Ok::<_, Error>(Some((f, hex)))
            } else {
                Ok(None)
            }
        }));
    }
    info!("patched all");

    for h in hashing.into_iter() {
        if let Some(h) = h.await.unwrap().unwrap() {
            hashes.push(h)
        }
    }
    hashes.sort_by(|a, b| a.0.cmp(&b.0));
    info!("hashed all");

    let mut output_hasher = blake3::Hasher::new();
    {
        let blakesums = tmp.dir_path().join("blake3sums");
        let mut file = tokio::fs::File::create(&blakesums).await?;
        for (path, hash) in hashes {
            let path = path.to_str().unwrap();
            file.write_all(hash.as_bytes()).await?;
            file.write_all(b" ").await?;
            file.write_all(path.as_bytes()).await?;
            file.write_all(b"\n").await?;
            writeln!(output_hasher, "{} {}", hash, path)?;
        }
    }
    let final_path = client.store_path.join(&format!(
        "{}-{}",
        data_encoding::HEXLOWER.encode(output_hasher.finalize().as_bytes()),
        base_package_name,
    ));

    {
        let transitive = tmp.dir_path().join("paths");
        let mut file = tokio::fs::File::create(&transitive).await?;
        for path in vertices[v].files.iter() {
            file.write_all(path.as_bytes()).await?;
            file.write_all(b"\n").await?;
        }
    }

    for (f, _) in find_dirs(vertices[v].downloaded.path.to_path_buf())? {
        let rel = f.strip_prefix(&vertices[v].downloaded.path).unwrap();
        vertices[v]
            .files
            .insert(Arc::new(final_path.join(rel).to_str().unwrap().to_string()));
    }

    info!("rename {:?} to {:?}", tmp.dir_path(), dest);
    tokio::fs::rename(tmp.dir_path(), dest).await.unwrap();
    std::mem::forget(tmp);

    Ok(final_path)
}

async fn push_deps<'a>(
    depends: &[deb::Dep<'a>],
    index: &'a [deb::Index],
    stack: &mut Vec<(
        deb::Stanza<'a>,
        Option<tokio::sync::oneshot::Receiver<Result<Downloaded, Error>>>,
    )>,
) -> Vec<&'a str> {
    let mut d = Vec::new();
    for dep in depends.iter() {
        match dep {
            deb::Dep::Simple(s) => {
                debug!("dep {:?}", s);
                let Some(dep) = multi_lookup(index, &s.name).await else {
                    panic!("could not find {:?}", s.name)
                };
                d.push(dep.package);
                stack.push((dep, None))
            }
            deb::Dep::Alternatives { alt } => {
                debug!("alt {:?}", alt);
                let stack_len = stack.len();
                for dep in alt {
                    if let Some(dep_) = multi_lookup(index, &dep.name).await {
                        d.push(dep_.package);
                        stack.push((dep_, None));
                        break;
                    }
                }
                if stack.len() == stack_len {
                    panic!("Not found: {:?}", alt);
                }
            }
        }
    }
    d
}