pub struct SemaPlusPlus<T> {
    queue_and_cv: Arc<(Mutex<VecDeque<T>>, Condvar)>,
}

impl<T> SemaPlusPlus<T> {
    pub fn send(&self, message: T) {
        let (queue_lock, cv) = &*self.queue_and_cv;
        let mut queue = queue_lock.lock().unwrap();
        let queue_was_empty = queue.is_empty();
        queue.push_back(message);
        // if a queue is not empty, then another thread must have notified and main()
        // must be awake
        if queue_was_empty {
            cv.notify_all();
        }
    }

    pub fn recv(&self) -> T {
        let (queue_lock, cv) = &*self.queue_and_cv;
        // wait_while dereferences the guard and pass the protected data to the closure,
        // when the condition is true, it releases the lock and sleep until another thread
        // notify_all
        let mut queue = cv
            .wait_while(queue_lock.lock().unwrap(), |queue| queue.is_empty())
            .unwrap();
        queue.pop_front().unwrap()
    }
}

fn main() {
    let sem: SemaPlusPlus<String> = SemaPlusPlus::new();
    let mut handlers = Vec::new();
    for i in 0..NUM_THREADS {
        let sem_clone = sem.clone();
        let handle = thread::spawn(move || {
            rand_sleep();
            sem_clone.send(format!("thread {} just finished!", i))
        });
        handlers.push(handle);
    }
    // main is the only consumer of the queue,
    // it wakes up when some thread notify_all, locks the queue, consume the message
    // and release the lock until it is notified again
    for _ in 0..NUM_THREADS {
        println!("{}", sem.recv())
    }

    for handle in handlers {
        handle.join().unwrap();
    }
}

• Mutex-based channel is inefficient:
  • it does not allow the queue producer and consumer modify the queue simultaneously.
  • It involves system calls.
• Go channels are MCMC, but it essentially implement Mutex<VecDeque<>> with fuxtex.

• Minimal lock usage.
• Channels are not the best choice for global values -> lock still required.

/// Factor the number while receiving numbers from stdin
fn main() {
    let (sender, receiver) = crossbeam_channel::unbounded();
    let mut threads = Vec::new();
    for _ in 0..num_cpus::get() {
        // The channel maintains a reference counter for senders and for receivers
        // when receiver.clone(), the receiver counter increments.
        let receiver = receiver.clone();
        threads.push(thread::spawn(move || {
            while let Ok(next_num) = receiver.recv() {
                factor_number(next_num);
            }
        }));
    }

    let stdin = std::io::stdin();
    for line in stdin.lock().lines() {
        let num = line.unwrap().parse::<u32>().unwrap();
        sender.send(num).expect("Cannot send to channel when there is no receiver");
    }

    // decrement the sender counter, when no sender, the channel is closed
    drop(sender);

    for thread in threads {
        thread.join().expect("panic");
    }
}

One should use associated types instead of generic type parameters in a trait if there should only exist one trait implementation for any type. For instance, for any given type, the Item type should be unambiguous even if type contains generic parameters.

/* standard trait
trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}
*/

#[derive(Default)]
struct MyVec<T> {  // we cannot directly implement Iterator for MyVec<T> as it does not store internal states.
    vec: Vec<T>
}

struct MyVecIter<'a, T> {
    vec: &'a Vec<T>,
    position: usize,
}

impl<'a, T> Iterator for MyVecIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.position < self.vec.len() {
            let item = &self.vec[self.position];
            self.position += 1;
            Some(item)
        } else {
            None
        }
    }
}

impl<T> MyVec<T> {
    fn iter(&self) -> MyVecIter<'_, T> {  // this does not consume MyIter
        MyVecIter {
            vec: &self.vec,
            position: 0,
        }
    }
}

impl<'a, T> IntoIterator for &'a MyVec<T> {  // this consumes MyIter
    type Item = &'a T;
    type IntoIter = MyVecIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// usage
let my_vec = MyVec::<i32>::default();
let mut my_vec_iter = my_vec.into_iter();
my_vec_iter.next();

On the other hands, sometimes we want multiple trait implementations for the given type, e.g., convert a type to both String and i32, or when the type has different generic bounds:

impl From<i32> for MyType {}

impl From<String> for MyType {}

impl<T> MyTrait for Vec<T> where T: Display {}

impl<T> MyTrait for Vec<T> where T: Debug {}

There are two ways to pass into a function a type that implements a trait: static dispatch and dynamic dispatch:

fn static_dispatch(item: impl MyTrait) {}  // or static_dispatch<T: MyTrait>(item: T) {}

fn dynamic_dispatch(item: &dyn MyTrait) {}

Static dispatch tells the compiler to make a copy of the function for each T and replace each generic parameter with the concrete type provided, which is called monomorphization. In this way the compiler can optimize the generic code just at non-generic code. To avoid generating duplicated machine code, one can declare a non-generic inner function inside the generic function.

When calling dynamic_dispatch, the caller passes a trait object, which is the combination of a type that implements the trait and a pointer to its virtual method table (vtable) which holds all trait method implementations of this type. Since dyn is not resolved during the compile time, it is !Sized and hence it needs to be a wide pointer (&dyn) holder, e.g., &mut, Box or Arc.

Only object-safe traits can allow dynamic dispatch. An object-safe trait must satisfy:

1. All methods are object-safe:
   1. No generic parameters,
   2. No Self as return type, otherwise the memory layout cannot be determined during the compile time.
   3. No static methods, i.e., must take &self or &mut self, otherwise the vtable is not available.
2. Trait cannot be Sized bound, otherwise it’s against the nature of dynamic dispatch.

Broadly speaking, use static dispatch in a library, and dynamic dispatch in a binary (no other users):

pub struct DynamicLogger {
    writer: Box<dyn Write>
}

pub struct StaticLogger<W: Write> {
    writer: W
}

// usage
let file = File::create("dynamic_log.txt")?;
let dynamic_logger = DynamicLogger { writer: Box::new(file) };  // Users are forced to use dynamic dispatch

// Both works for static dispatch
let file = File::create("static_log.txt")?;
let logger = Logger { writer: file };

let file: Box<dyn Write> = Box::new(File::create("static_log.txt")?);
let logger = Logger { writer: file };

fn collect_to_map<T, S>(items: impl IntoIterator<Item = T>) -> HashMap<T, usize, S>
where
   HashMap<T, usize, S>: FromIterator<(T, usize)>
{
   items
       .into_iter()
       .enumerate()
       .map(|(i, item)| (item, i))
       .collect()
}

The trait above is better than explicitly writing T: Hash + Eq and S: BuildHasher + Default since they are implicitly required for HashMap to implement FromIterator.

impl Debug for AnyIterable
where
    // the reference to Self implements IntoIterator for any lifetime 'a
    for<'a> &'a Self: IntoIterator,
    // the item (associated type in Self) produced by iterating over the reference to Self implement Debug
    // We cannnot write <&'a Self>::Item because the associated type Item only exists in IntoIterator
    for<'a> <&'a Self as IntoIterator>::Item: Debug,
{
    // since fmt signature does not allow lifetime annotation,
    // we need to specify "the reference implements the trait for any lifetime"
    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        f.debug_list()  // formats items, e.g., [item1, item2]
            .entries(self) // iterates over self and debug-formatted each item
            .finish()
    }
}

The code above adds trait bounds for both outer type and the inner associated type. It implement Debug for any type that can be iterated over and whose elements are Debug.

#![feature(impl_trait_in_assoc_type)] // require nightly

#[derive(Default)]
struct MyVec<T> {
    vec: Vec<T>,
}

impl<T> IntoIterator for MyVec<T> {
    type Item = T;
    type IntoIter = impl Iterator<Item = Self::Item>; // existential type

    fn into_iter(self) -> Self::IntoIter {
        let mut vec = self.vec;
        let position = 0;
        std::iter::from_fn(move || {
            if position < vec.len() {
                let item = vec.remove(position); // consume vec
                Some(item)
            } else {
                None
            }
        })
    }
}

fn main() {
    let mut my_vec = MyVec::<i32>::default().into_iter();
    println!("{:?}", my_vec.next());
}

The code above uses existential types in the associated types to avoid creating new type MyVecIter, hence perform zero-cost type erasure.

Below is my personal solution for the problem, while it was accepted, there is space to improve it and I may come back when I have another idea.

use std::{cell::RefCell, collections::HashMap, rc::Rc};

type List = Option<Rc<RefCell<ListNode>>>;

struct ListNode {
    key: i32,
    value: i32,
    prev: List,
    next: List,
}

struct LRUCache {
    head: List,
    tail: List,
    data: HashMap<i32, Rc<RefCell<ListNode>>>,
    capacity: usize,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        Self {
            head: None,
            tail: None,
            data: HashMap::new(),
            capacity: capacity as usize,
        }
    }

    fn move_to_front(&mut self, node: Rc<RefCell<ListNode>>) {
        // early return if the node is already the head
        if let Some(head) = &self.head {
            if Rc::ptr_eq(head, &node) {
                return;
            }
        }

        let prev = node.borrow().prev.clone();
        let next = node.borrow().next.clone();

        match (prev.as_ref(), next.as_ref()) {
            (None, None) => {
                // insert a new node only modifies the head,
                // the rest of the list is untouched.
            }
            (Some(prev), None) => {
                // get the tail node
                prev.borrow_mut().next = None;
                self.tail = Some(Rc::clone(prev));
            }
            (None, Some(_)) => {
                // get the head node is already handled
                return;
            }
            (Some(prev), Some(next)) => {
                // get a node in the middle of a list,
                // connect its prev and next
                prev.borrow_mut().next = Some(Rc::clone(next));
                next.borrow_mut().prev = Some(Rc::clone(prev));
            }
        }

        // update node to be the new head
        if let Some(old_head) = &self.head {
            node.borrow_mut().next = Some(Rc::clone(old_head));
            old_head.borrow_mut().prev = Some(Rc::clone(&node));
        } else {
            // insert a node to the empty list
            self.tail = Some(Rc::clone(&node));
        }
        node.borrow_mut().prev = None;
        self.head = Some(node);
    }

    fn get(&mut self, key: i32) -> i32 {
        let mut result = -1;
        if let Some(node) = self.data.get(&key) {
            result = node.borrow().value;
            self.move_to_front(Rc::clone(node));
        }
        result
    }

    fn put(&mut self, key: i32, value: i32) {
        if let Some(node) = self.data.get(&key) {
            let node = Rc::clone(node);
            node.borrow_mut().value = value;
            self.move_to_front(node);
        } else {
            let new_node = Rc::new(RefCell::new(ListNode {
                key,
                value,
                prev: None,
                next: None,
            }));
            // evict the tail node
            if self.data.len() >= self.capacity {
                if let Some(tail) = self.tail.take() {
                    // cannot simply take the prev as it breaks the list?
                    let prev = tail.borrow().prev.clone();
                    self.data.remove(&tail.borrow().key);
                    if let Some(prev) = prev {
                        prev.borrow_mut().next = None;
                        self.tail = Some(prev);
                    } else {
                        self.head = None;
                        self.tail = None;
                    }
                }
            }
            self.data.insert(key, Rc::clone(&new_node));
            self.move_to_front(new_node);
        }
    }
}

• Complexity is anything related to the structure of a software system that makes it hard to understand and modify the system.
• \(C = \sum_p(c_pt_p)\): The overall complexity is determined by the complexity of each part \(p\) weighted by the fraction of time developers working on that part.
  • Isolating complexity in a place where it will never be seen is as good as eliminating the complexity.
• Complexity is more apparent to readers than writers: if you write a piece of code that seems simple to you, but others think it is complex, then it is complex.

• Change amplification: a seemingly simple change requires code modifications in many different places.
• Cognitive load: developers have to spend more time learning the required information to complete a task, which leads to greater risk of bugs.
  • E.g., a function allocates memory and returns a pointer to the memory, but assumes the caller should free the memory.
  • Sometimes an approach that requires more lines of code is actually simpler as it reduces cognitive load.
• Unknown unknowns (the worst!): it is not obvious which pieces of code must be modified or which information must have to complete the task.
• The goal of a good design is for a system to be obvious: a developer can make a quick guess about what to do and yet to be confident that the guess is correct.

• Complexity is caused by two things: dependencies and obscurity.
• A dependency exists when a code cannot be understood and modified in isolation.
  • E.g., in network protocols both senders and receivers must conform to the protocol, changing code for the sender almost always requires corresponding changes at the receiver.
  • Dependencies are fundamental and cannot be completely eliminated, the goal is to make the dependencies remain simple and obvious (e.g., variable renaming are detected by compilers).
• Obscurity occurs when important information is not obvious, e.g., a variable is too generic or the documentation is inadequate.
  • Obscurity is often associated with non-obvious dependencies.
  • Inconsistency is also a major contributor, e.g., the same variable name is used for two different purposes.
  • The need for extensive documentation is often a red flag that the design is complex.
• Dependencies lead to change amplification and cognitive load; obscurity creates unknown unknowns and cognitive load.

• Requires an investment mindset to improve the system design rather than taking the fastest path to finish the current task.
• Proactive investment: try a couple of alternative designs and pick the cleanest one; imagine a few ways in which the system might need to be changed in the future; write documentation.
• Reactive investments: continuously make small improvements to the system design when a design problem becomes obvious rather than patching around it.
• The ideal design tends to emerge in bits and pieces, thus the best approach is to make lots of small investments on a continual basis, e.g., 10-20% of total development time on investments.

• A module interface contains two information: formal and informal.
• The formal part for a method is its signature; The formal interface for a class consists of the signatures for all public methods and variables.
• The informal part includes its high-level behavior and usage constraints; they can only be described using comments and cannot be ensured by the programming languages.
  • Informal aspects are larger and more complex than the formal aspects for most interfaces.
• While providing choice is good, interfaces should be designed to make the common case as simple as possible (c.f. \(C = \sum_p(c_pt_p)\)).

• An abstraction is a simplified view of an entity, which omits unimportant details.
  • The more unimportant details that are omitted from an abstraction, the better, otherwise the abstraction increases the cognitive load.
  • A detail can only be omitted if it is unimportant, otherwise obscurity occurs.
• In modular programming, each module provides an abstraction in form of its interface.
• The key to designing abstractions is to understand what is important.
  • E.g., how to choose storage blocks for a file is unimportant to users, but the rules for flushing data to secondary storage is important for databases, hence it must be visible in the file system interface.
  • Garbage collectors in Go and Java do not have interface at all.

• The leakage occurs when a design decision is reflected in multiple modules. thus creating dependencies between the modules.
  • Interface information is by definition has been leaked.
• Information can be leaked even if it does not appear in the interface, i.e., back-door leakage.
  • E.g., two classes read and write the same file format, then if the format changes, both classes need to be modified; such leakage is more pernicious than interface leakage as it is not obvious.
• If affected classes are relatively small and closely tied to the leaked information, they may need to be merged into a single class.
  • The bigger class is deeper as the entire computation is easier to be abstracted in the interface compared to separate sub-computations.
• One may also pull the leaked information out of all affected classes and create a new class to encapsulate the information, i.e., replace back-door leakage with interface leakage.
• One should avoid exposing internal data structures (e.g., return by reference) as such approach makes more work for callers, and make the module shallow.
  • E.g., instead of writing getParams() which returns a map of all parameters, one should have getParameter(String name) and getIntParameter(String name) to return a specific parameter and throw an exception if the name does not exist or cannot be converted.

• Temporal decomposition is a common cause of information leakage.
• It decompose the system into operations corresponding to the execution order.
  • E.g., A file-reading application is broken into 3 classes: read, modify and write, then both reading and writing steps have knowledge about the file format.
  • The solution is to combine the core mechanisms for reading and writing into a single class.
• Orders should not be reflected in the module structure unless different stages use totally different information.
• One should focus on the knowledge needed to perform each task, not the order in which tasks occur.

• Specialized design: use individual method in the text class to support each high-level features, e.g., backspace(Cursor cursor) deletes the character before the cursor; delete(Cursor cursor) deletes the character after the cursor; deleteSelection(Selection selection) deletes the selected section.
• The specialized design creates a high cognitive load for the UI developers: the implementation ends up with a large number of shallow methods so a UI developer had to learn all of them.
  • E.g., backspace provides a false abstraction as it does not hide the information about which character to delete.
• The specialized design also creates information leakage: abstractions related to the UI such as backspace key and selection, are reflected in the text class, increasing the cognitive load for the text class developers.
• General-purpose design define API only in terms of basic text features without reflecting the higher-level operations.
  • Only three methods are needed to modify a text: insert(Position position, String newText), delete(Position start, Position end) and changePosition(Position position, int numChars).
    • The new API uses a more generic Position to replace a specific user interface Cursor.
    • The delete key can be implemented as text.delete(cursor, text.ChangePosition(cursor, 1)), the backspace key can be implemented as text.delete(cursor, text.ChangePosition(cursor, -1)).
• The new design is more obvious, e.g., the UI developer knows which character to delete from the interface, and also has less code overall.
• The general-purpose methods can also be used for new feature, e.g., search and replace text.

• A pass-through method is a method that does little except invoke another method, whose signature is similar or identical to the callee function.
• Pass-through methods usually indicates there is not a clean division of responsibility between classes.
• Pass-through methods also create dependencies between classes.
• The solution is to refactor the classes, e.g., expose the lower level class directly to the higher level (b), redistribute the functionality (c) or merge them (d):

• A pass-through variable is a variable that is passed down through a long chain of methods.
• Pass-through variables add complexity as all intermediate methods must be aware of the existence and need to be modified when a new variable is used.
• The author’s solution is to introduce a context object which stores all application’s global states, e.g., configuration options and timeout value, and there is one context object per system instance.
• To avoid passing through the context variable, a reference to the context can be saved in other objects.
  • When a new object is created, the context reference is passed to the constructor.
• Contexts should be immutable to avoid thread-safety issues and may create non-obvious dependencies.

• Dispatcher: a method that uses its arguments to select a specific method to invoke and passes most of its arguments.
  • E.g., when a web server receives an HTTP request, it invokes a dispatcher to examine the URL and selects a specific method to handle the request.
• Polymorphous methods, e.g., len(string) and len(array) reduces cognitive load; they are usally in the same layer and do not invoke each other.
• Decorator: a wrapper that takes an existing object and extends its functionality.
• Decorators are often shallow and contain pass-through methods, one should consider following alternatives before using them:
  • Add the new functionality directly to the class if it is relatively general-purpose; or merge it with the specific use case if it is specialized.
  • Merge the new functionality with an existing decorator to make the existing decorator deeper.
  • Implement it as a stand-alone class independent of the base class, e.g., Window and ScrollableWindow.

• Example 1: instead of throwing an exception when a key does not exist in remove, simply return to ensure the key no longer exists.
• Example 2: instead of throwing an exception when trying to delete a file that is still open in other processes, mark the file for deletion to deny any processes open the old file later, and delete the file after all processed have closed the file.
• Example 3: instead of throwing an IndexOutOfBoundsExeception when substring(s, begin, end) takes out-of-range arguments, return the overlap substring.

• An exceptional condition is detected and handled at a low level in the system so that higher levels need not be aware of the condition.
• E.g., when a TCP packet is lost, the packet is resent within the implementation and clients are unaware of the dropped packets (they notice the hanging and can abort manually).
• Exception masking results in deeper classes and pulls complexity downward.

• Exception aggregation handles many special-purpose exceptions with a single general-purpose handler.
• Example 1: instead of catching the exception for each individual missing parameter, let the single top-level exception handler aggregate the error message with a single top-level try-catch block.
  • The top-level handler encapsulates knowledge about how to generate error responses, but knows nothing about specific errors.
  • Each service knows how to generate errors, but does not know how to send the response.
• Example 2: promote rare exceptions (e.g., corrupted files) to more common exceptions (e.g., server crashes) so that the same handler can be used.

• The correct process of writing comments will improve the system design.
• A significant amount of design information that was in the mind of the designer cannot be represented in code, e.g., the high-level description of a method, the motivation for a particular design.
• Comments are fundamental to abstractions: if users must read the code to use it, then there is no abstraction.
  • If there is no comment, the only abstraction of a method is its declaration which misses too much essential information to provide a useful abstraction by itself; e.g., whether end is inclusive.
• Good comments reduce cognitive load and unknown unknowns.

• Follow the comment conventions, e.g., Doxygen for C++, godoc for Go.
• Comments categories:
  • Interface: a comment block that precedes the declaration; describes the interface, e.g., overall behavior or abstraction, arguments, return values, side effects or exceptions and any requirements the caller must satisfy.
  • Data structure member: a comment next to the declaration of a field in a data structure, e.g., a variable.
  • Implementation comment: a comment inside the code to describe how the code work internally.
  • Cross-module comment: a comment describing dependencies that cross module boundaries.
• The interface and the data structure member comments are the most important and should be always present.
• Don’t repeat the code: if someone who has never seen the code can also write the comment by just looking at the code next to the comment, then the comment has no value.
• Don’t use the same words in the comment that appear in the name of the entity being described, pick words that provide additional information.
• Comments should augment the code by providing information at a different level of detail.
  • Lower-level: add precision by clarifying the exact meaning of the code.
  • Higher-level: offer intuition behind the code.

• Vague name examples: “count”, “status”, “x”, “result” in a no return method.
• It’s fine to use generic “i/j” in a loop as long as the loop does not span large.
• A name may also become too specific, e.g., delete(Range Selection) suggests the argument must be a selection, but it can also be passed with unselected range.
• If you find it difficult to come up with a name that is precise, intuitive and not too long, then it is a red flag that the variable may not have a clear design.
  • Consider alternative factorings, e.g., separate the representation into multiple variables.

• Always use the common name for and only for the given purpose, e.g., ch for a channel.
• Make sure the purpose is narrow enough that all variables with the same name have the same behavior.
  • E.g., a block purpose is not narrow as it can have different behaviors for physical and logical blocks.
• When you need multiple variables that refer to the same general thing, use the common name for each variable and add a distinguishing prefix, e.g., srcBlock and dstBlock.
• Always use i in outmost loops and j for nested loops.