From ed51d48f7353a5ceefa798ded52d3af465d4d0ec Mon Sep 17 00:00:00 2001
From: Vika <vika@fireburn.ru>
Date: Mon, 13 Nov 2023 22:19:42 +0300
Subject: Switch reply contexts from a Vec to HashMap

This reduces the worst-case complexity to O(n) from O(n^2).
---
 src/micropub/mod.rs | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)

(limited to 'src')

diff --git a/src/micropub/mod.rs b/src/micropub/mod.rs
index c3e78fe..4a501bb 100644
--- a/src/micropub/mod.rs
+++ b/src/micropub/mod.rs
@@ -1,4 +1,5 @@
 use std::collections::HashMap;
+use url::Url;
 use std::sync::Arc;
 
 use crate::database::{MicropubChannel, Storage, StorageError};
@@ -58,18 +59,15 @@ struct FetchedPostContext {
 fn populate_reply_context(
     mf2: &serde_json::Value,
     prop: &str,
-    ctxs: &[FetchedPostContext],
+    ctxs: &HashMap<Url, FetchedPostContext>,
 ) -> Option<Vec<serde_json::Value>> {
     mf2["properties"][prop].as_array().map(|array| {
         array
             .iter()
-            // TODO: This seems to be O(n^2) and I don't like it.
-            // Switching `ctxs` to a hashmap might speed it up to O(n)
-            // The key would be the URL/UID
             .map(|i| {
-                let mut item = ctxs
-                    .iter()
-                    .find(|ctx| Some(ctx.url.as_str()) == i.as_str())
+                let mut item = i.as_str()
+                    .and_then(|i| i.parse::<Url>().ok())
+                    .and_then(|url| ctxs.get(&url))
                     .and_then(|ctx| ctx.mf2["items"].get(0))
                     .unwrap_or(i)
                     .clone();
@@ -153,13 +151,13 @@ async fn background_processing<D: 'static + Storage>(
                     .get("webmention")
                     .and_then(|i| i.first().cloned());
 
-                dbg!(Some(FetchedPostContext {
+                dbg!(Some((url.clone(), FetchedPostContext {
                     url,
                     mf2: serde_json::to_value(mf2).unwrap(),
                     webmention
-                }))
+                })))
             })
-            .collect::<Vec<FetchedPostContext>>()
+            .collect::<HashMap<Url, FetchedPostContext>>()
             .await
     };
 
@@ -201,9 +199,9 @@ async fn background_processing<D: 'static + Storage>(
         tokio_stream::iter(
             post_contexts
                 .into_iter()
-                .filter(|ctx| ctx.webmention.is_some()),
+                .filter(|(url, ctx)| ctx.webmention.is_some()),
         )
-        .for_each_concurrent(2, |ctx| async move {
+        .for_each_concurrent(2, |(url, ctx)| async move {
             let mut map = std::collections::HashMap::new();
             map.insert("source", uid);
             map.insert("target", ctx.url.as_str());
@@ -729,16 +727,17 @@ mod tests {
                 "content": ["This is a post which was reacted to."]
             }
         });
-        let reply_contexts = vec![FetchedPostContext {
-            url: "https://fireburn.ru/posts/example".parse().unwrap(),
+        let fetched_ctx_url: url::Url = "https://fireburn.ru/posts/example".parse().unwrap();
+        let reply_contexts = vec![(fetched_ctx_url.clone(), FetchedPostContext {
+            url: fetched_ctx_url.clone(),
             mf2: json!({ "items": [test_ctx] }),
             webmention: None,
-        }];
+        })].into_iter().collect();
 
         let like_of = super::populate_reply_context(&mf2, "like-of", &reply_contexts).unwrap();
 
         assert_eq!(like_of[0]["properties"]["content"], test_ctx["properties"]["content"]);
-        assert_eq!(like_of[0]["properties"]["url"][0].as_str().unwrap(), reply_contexts[0].url.as_str());
+        assert_eq!(like_of[0]["properties"]["url"][0].as_str().unwrap(), reply_contexts[&fetched_ctx_url].url.as_str());
 
         assert_eq!(like_of[1], already_expanded_reply_ctx);
         assert_eq!(like_of[2], "https://fireburn.ru/posts/non-existent");
-- 
cgit 1.4.1