From 74f8201586435a7a2e7f8fd49c7eb0750a089180 Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
Date: Wed, 20 Jan 2021 14:47:42 +0300
Subject: Avoid intermediate collections

---
 crates/ide/src/runnables.rs | 46 ++++++++++++++++++++-------------------------
 docs/dev/style.md           | 34 ++++++++++++++++++++++++++++++++-
 2 files changed, 53 insertions(+), 27 deletions(-)

diff --git a/crates/ide/src/runnables.rs b/crates/ide/src/runnables.rs
index 13582e61f..47a85dc45 100644
--- a/crates/ide/src/runnables.rs
+++ b/crates/ide/src/runnables.rs
@@ -101,24 +101,22 @@ pub(crate) fn runnables(db: &RootDatabase, file_id: FileId) -> Vec<Runnable> {
         Some(it) => it,
     };
 
-    runnables_mod(&sema, module)
+    let mut res = Vec::new();
+    runnables_mod(&sema, &mut res, module);
+    res
 }
 
-fn runnables_mod(sema: &Semantics<RootDatabase>, module: hir::Module) -> Vec<Runnable> {
-    let mut res: Vec<Runnable> = module
-        .declarations(sema.db)
-        .into_iter()
-        .filter_map(|def| {
-            let runnable = match def {
-                hir::ModuleDef::Module(it) => runnable_mod(&sema, it),
-                hir::ModuleDef::Function(it) => runnable_fn(&sema, it),
-                _ => None,
-            };
-            runnable.or_else(|| module_def_doctest(&sema, def))
-        })
-        .collect();
+fn runnables_mod(sema: &Semantics<RootDatabase>, acc: &mut Vec<Runnable>, module: hir::Module) {
+    acc.extend(module.declarations(sema.db).into_iter().filter_map(|def| {
+        let runnable = match def {
+            hir::ModuleDef::Module(it) => runnable_mod(&sema, it),
+            hir::ModuleDef::Function(it) => runnable_fn(&sema, it),
+            _ => None,
+        };
+        runnable.or_else(|| module_def_doctest(&sema, def))
+    }));
 
-    res.extend(module.impl_defs(sema.db).into_iter().flat_map(|it| it.items(sema.db)).filter_map(
+    acc.extend(module.impl_defs(sema.db).into_iter().flat_map(|it| it.items(sema.db)).filter_map(
         |def| match def {
             hir::AssocItem::Function(it) => {
                 runnable_fn(&sema, it).or_else(|| module_def_doctest(&sema, it.into()))
@@ -128,18 +126,14 @@ fn runnables_mod(sema: &Semantics<RootDatabase>, module: hir::Module) -> Vec<Run
         },
     ));
 
-    res.extend(module.declarations(sema.db).into_iter().flat_map(|def| match def {
-        hir::ModuleDef::Module(submodule) => match submodule.definition_source(sema.db).value {
-            hir::ModuleSource::SourceFile(_) => {
-                mark::hit!(dont_recurse_in_outline_submodules);
-                Vec::new()
+    for def in module.declarations(sema.db) {
+        if let hir::ModuleDef::Module(submodule) = def {
+            match submodule.definition_source(sema.db).value {
+                hir::ModuleSource::Module(_) => runnables_mod(sema, acc, submodule),
+                hir::ModuleSource::SourceFile(_) => mark::hit!(dont_recurse_in_outline_submodules),
             }
-            hir::ModuleSource::Module(_) => runnables_mod(sema, submodule),
-        },
-        _ => Vec::new(),
-    }));
-
-    res
+        }
+    }
 }
 
 pub(crate) fn runnable_fn(sema: &Semantics<RootDatabase>, def: hir::Function) -> Option<Runnable> {
diff --git a/docs/dev/style.md b/docs/dev/style.md
index aed15cee9..389649398 100644
--- a/docs/dev/style.md
+++ b/docs/dev/style.md
@@ -421,12 +421,44 @@ fn frobnicate(s: &str) {
 **Rationale:** reveals the costs.
 It is also more efficient when the caller already owns the allocation.
 
-## Collection types
+## Collection Types
 
 Prefer `rustc_hash::FxHashMap` and `rustc_hash::FxHashSet` instead of the ones in `std::collections`.
 
 **Rationale:** they use a hasher that's significantly faster and using them consistently will reduce code size by some small amount.
 
+## Avoid Intermediate Collections
+
+When writing a recursive function to compute a sets of things, use an accumulator parameter instead of returning a fresh collection.
+Accumulator goes first in the list of arguments.
+
+```rust
+// GOOD
+pub fn reachable_nodes(node: Node) -> FxHashSet<Node> {
+    let mut res = FxHashSet::default();
+    go(&mut res, node);
+    res
+}
+fn go(acc: &mut FxHashSet<Node>, node: Node) {
+    acc.insert(node);
+    for n in node.neighbors() {
+        go(acc, n);
+    }
+}
+
+// BAD
+pub fn reachable_nodes(node: Node) -> FxHashSet<Node> {
+    let mut res = FxHashSet::default();
+    res.insert(node);
+    for n in node.neighbors() {
+        res.extend(reachable_nodes(n));
+    }
+    res
+}
+```
+
+**Rational:** re-use allocations, accumulator style is more concise for complex cases.
+
 # Style
 
 ## Order of Imports
-- 
cgit v1.2.3