[alrotighm] trampoline pattern

using trampoline to deal with recursive stack overflow situation(while tail-call is not applicable):

#include <iostream>
#include <vector>
#include <numeric>
#include <variant>
#include <functional>
#include <utility>

// --- (Paste the Bounce, Step, and trampoline definitions from above here) ---

template<typename T>
struct Bounce;

template<typename T>
using Step = std::variant<T, Bounce<T>>;

template<typename T>
struct Bounce {
    std::function<Step<T>()> thunk;
};

template<typename T>
T trampoline(Step<T> first_step) {
    Step<T> current_step = std::move(first_step);
    while (std::holds_alternative<Bounce<T>>(current_step)) {
        current_step = std::get<Bounce<T>>(current_step).thunk();
    }
    return std::get<T>(current_step);
}

// --- (Paste the sum_trampolined function from above here) ---

Step<long> sum_trampolined(const std::vector<long>& data, size_t index, long current_sum) {
    if (index == data.size()) {
        return current_sum;
    }
    return Bounce<long>{
        [=]() {
            return sum_trampolined(data, index + 1, current_sum + data[index]);
        }
    };
}


int main() {
    // This will now work without crashing!
    std::vector<long> large_vec(200000, 1);

    // To start the process, we create the very first step.
    Step<long> first_step = sum_trampolined(large_vec, 0, 0);

    // The trampoline function runs the computation to completion.
    long total = trampoline(first_step);

    std::cout << "Trampolined sum of large vector: " << total << std::endl;
    std::cout << "The program finished successfully." << std::endl;

    return 0;
}

[Algorithm] branchless binary search

template <class ForwardIt, class T, class Compare>
ForwardIt branchless_lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    auto length = last - first;

    while (length > 0)
    {
        auto half = length / 2;
        // multiplication (by 1) is needed for GCC to generate CMOV
        // comp returns 1 if value > first[half], returns 0 otherwise
        first += comp(first[half], value) * (length - half); 
        length = half;
    }

    return first;
}

[C++] coroutine cheat sheet - 2

Reference:
[C++] coroutine cheat sheet - 1
https://reductor.dev/cpp/2023/08/10/the-downsides-of-coroutines.html#how-normal-functions-and-the-stack-work

Rule

1. Do not resume caller's handler inside a mem_fn that returns value/handler.
   otherwise the return will be suspended in the callee.
   reference:
   https://lewissbaker.github.io/2020/05/11/understanding_symmetric_transfer
   A pattern, however, the caller's awaitable::await_suspend() could call callee's handler to resume,
   while callee's promise::final_suspend() could call caller handler to resume() and back to
   caller's awaitable::await_suspend().
2. Control the suspend from mem_fn that it's signature returns awaitable type.
3. Store {yeild values/caller's handler} inside the promise instance.
4. Make sure promise::final_suspend() is run before caller resume.
   This indicates, the caller::handler::resume() can only be called
   inside the promise::final_suspend() returned awaitable::await_suspend() and awaitable::await_ready() should return false to trigger the run of awaitable::await_suspend()
5. If promise::final_suspend() returns std::suspend_never{}, the coroutine heap is destroyed automatically/immidiately.
   If promise::final_suspend() returns other then std::suspend_never{} and
   has the awaitable::await_ready() returns false, the user defined coroutine
   handler's destructor should call detroy() manually to release the heap.
6. Thread local variables should not be used in coroutines to prevent buggy logic.
   https://rules.sonarsource.com/cpp/RSPEC-6367

Coroutine defined as:

task<void> func()
{
  int mylocal = 10;
  co_return;
}

Compiler generated coroutine code would be like:

// Struct representing the coroutine state
struct func_frame
{
  task<void>::promise_type __promise;
  int __step = 0;

  decltype(__promise.initial_suspend()) __initial_suspend_awaiter;
  decltype(__promise.final_suspend()) __final_suspend_awaiter;

  // Structure to hold local and temporary variables
  struct 
  {
    // Local and temporary variables reside here
    int mylocal;
  } local_and_temps;

  // Function to resume coroutine execution
  void resume()
  {
    switch(__step)
    {
      case 0:
        // co_await __promise.initial_suspend();
        __initial_suspend_awaiter = __promise.initial_suspend();
        if (!__initial_suspend_awaiter.await_ready())
        {
          __step = 1;
          __initial_suspend_awaiter.await_suspend();
          return;
        }
      case 1:
        __initial_suspend_awaiter.await_resume();
        // .. func body
        mylocal = 10;
        // co_return
        __promise.return_void();
        // co_await __promise.final_suspend();
        __final_suspend_awaiter = __promise.final_suspend();
        if (!__final_suspend_awaiter.await_ready())
        {
          __final_suspend_awaiter.await_suspend();
          return;
        }
        delete this;
    }
  }
};

// Coroutine function transformed into a coroutine frame
task<void> func()
{
  func_frame * frame = task<void>::promise_type::operator new(func_frame);
  task<void> ret = frame->__promise.get_return_object()
  frame->resume();
  return ret;
}

Which involves multiple function calls:

• func()
• promise_type::operator new()
• promise_type::promise_type()
• promise_type::get_return_value()
• promise_type::initial_suspend()
• initial_suspend::initial_suspend()
• initial_suspend::await_ready()
• initial_suspend::await_suspend() [opt]
• initial_suspend::await_resume()
• promise_type::return_void()
• final_suspend::final_suspend()
• final_suspend::await_ready()
• final_suspend::await_suspend() [opt]
• promise_type::operator delete()

Code explains:

#include <coroutine>
#include <iostream>

/**
Rule:
1. Do not resume caller's handler inside a mem_fn that returns value/handler.
  otherwise the return will be suspended in the callee.
2. Control the suspend from mem_fn that it's signature returns awaitable type.
3. store {yeild values/caller's handler} inside the promise instance.
4. make sure promise::final_suspend() is run before caller resume.
  this indicates, the caller::handler::resume() can only be called
  inside the promise::final_suspend() returned awaitable::await_suspend() and
  awaitable::await_ready() should return false to trigger the run of
  awaitable::await_suspend()
5. If promise::final_suspend() returns std::suspend_never{}, the coroutine heap
  is destroyed automatically.
  If promise::final_suspend() returns other then std::suspend_never{} and
  has the awaitable::await_ready() returns false, the user defined coroutine
handler's destructor should call detroy() manually to release the heap.
*/
using namespace std;

enum class TaskType : char {
  foo,
  bar,
};

template <TaskType ttype> struct Task;

// promise_type
template <TaskType ttype> struct promise_type {
  Task<ttype> get_return_object();
  std::suspend_always initial_suspend();

  auto final_suspend() noexcept;

  void return_value(int);
  void unhandled_exception();
  TaskType get_ttype() { return ttype; }
  int ret_val;
  std::coroutine_handle<promise_type<TaskType::bar>> promise_type_handle_;
};
// End promise_type

template <TaskType ttype>
struct Task : std::coroutine_handle<promise_type<ttype>> {
  using promise_type = promise_type<ttype>;
  // Awaitable interface definition
  bool await_ready() {
    std::cout << "await_ready: false\n";
    return false;
  }

  std::coroutine_handle<promise_type>
  await_suspend(std::coroutine_handle<::promise_type<TaskType::bar>> handler) {
    std::cout << "await_suspend receive handler pnted to type: "
              << (int)handler.promise().get_ttype()
              << " and this task's type: " << (int)this->promise().get_ttype()
              << "\n";

    // using this due to 13.4.2 Dependent Base Classes
    this->promise().promise_type_handle_ = handler;
    return *this;
  }

  int await_resume() {
    std::cout << "await_resume; type: " << (int)ttype << "\n";
    return this->promise().ret_val;
  }
  // End Awaitable interface definition

  ~Task() {
    std::cout << "Task destructor called, type: " << (int)ttype << "\n";
    this->destroy();
  }

  TaskType get_ttype() { return ttype; }

  // If has default Task constructor, this `return
  // {Task<ttype>::from_promise(*this)};` won't compile.
  // Task() { std::cout << "task construct type: " << (int)ttype << "\n"; }

}; // Task

// promise_type mem_fn definition
template <TaskType ttype> Task<ttype> promise_type<ttype>::get_return_object() {
  std::cout << "get_return_object type: " << (int)ttype << "\n";
  return {Task<ttype>::from_promise(*this)};
};

template <TaskType ttype>
std::suspend_always promise_type<ttype>::initial_suspend() {
  std::cout << "initial_suspend always\n";
  return {};
}

template <TaskType ttype> auto promise_type<ttype>::final_suspend() noexcept {
  std::cout << "final_suspend, this promise type: " << (int)ttype << "\n";
  // Bar's handler
  // if (promise_type_handle_) {
  //   std::cout << "resume bar's handler\n";
  //   promise_type_handle_.resume();
  // }
  struct tmp_awaitable {
    bool await_ready() noexcept {
      std::cout << "tmp_awaitable await_ready false\n";
      return false;
    }

    std::coroutine_handle<> await_suspend(
        std::coroutine_handle<::promise_type<TaskType::foo>> handler) noexcept {
      std::cout << "tmp_awaitable await_suspend\n";
      if (handler.promise().promise_type_handle_) {
        return handler.promise().promise_type_handle_;
      }
      std::cout << "tmp_awaitable await_suspend after resume\n";
      return std::noop_coroutine();
    }

    void await_resume() noexcept {
      std::cout << "tmp_awaitable await_resume\n";
    }
  };

  if constexpr (ttype == TaskType::foo) {
    std::cout << "final_suspend type: " << (int)ttype << " suspend never\n";
    // return std::suspend_never{};
    return tmp_awaitable{};
  } else {
    std::cout << "final_suspend type: " << (int)ttype << " suspend always\n";
    return std::suspend_always{};
  }
}

template <TaskType ttype> void promise_type<ttype>::return_value(int val) {
  std::cout << "return_val: " << val << "\n";
  ret_val = val;
  // promise_type_handle_.resume();
}

template <TaskType ttype> void promise_type<ttype>::unhandled_exception() {
  std::cout << "unhandled_exception\n";
}
// End promise_type mem_fn definition

Task<TaskType::foo> foo() {
  std::cout << "foo func start\n";
  co_return 42;
}

Task<TaskType::bar> bar() {
  std::cout << "bar func start\n";
  // co_return;
  // co_await foo();
  int val = co_await foo(); // Foo's task destructs here after co_await returns;
  std::cout << "bar func end val: " << val << "\n";
}

int main() {
  std::cout << "call bar\n";
  auto btask = bar();
  std::cout << "get btask and resume bar handle: " << (int)btask.get_ttype()
            << "\n";
  btask.resume();
  std::cout << "main-end\n";
  /*
        start call bar
        initial_suspend
        main-end
   */
}

[C++] Aggregate initialization takes base type's constructor regardless of `using base::base`

Bite by this constructor resolution rule:

1) D is an aggregate From 

[dcl.init.aggr] 

§11.6.2/1 (C++23 draft N4950): 

An aggregate is an array or a class with no user-declared or inherited constructors… (…) A class is an aggregate even if it has base classes. 

So `class D : public Base {}` is an aggregate.

2) Aggregate initialization rule From 

[dcl.init.aggr] 

§11.6.2/4: 

If the aggregate has a base class, each base class is initialized in the order of declaration using the corresponding elements of the initializer list. 

So the single element {42.3} is forwarded to the base class Base.

3) [class.base.init] §12.6.2/2:

In a non-delegating constructor, if a given potentially constructed subobject is not designated by a mem-initializer, then it is initialized as follows:

— if the entity is a base class, the base class’s default constructor is called,

unless otherwise specified by the rules of aggregate initialization.

And aggregate initialization rules (step 2) say the base is initialized from the element. That means the base is constructed as if by direct-initialization with that element.

4) Constructor overload resolution

Now, how does Base itself get constructed from 42.3?

That’s governed by [dcl.init] §11.6.1/17:

If the initializer is a parenthesized expression-list or a braced-init-list,

constructors are considered. 

The applicable constructors are selected by overload resolution ([over.match.ctor]).

So the compiler now does overload resolution among Base(int) and Base(double). The best match for 42.3 is Base(double).

#include <iostream>


class Base {
  public:
  // mark as `explicit` prevents derived type picking up this constructor
  Base(int) {
    std::cout << "base int\n";
  }

  // mark as `explicit` prevents derived type picking up this constructor
  Base(double) {
    std::cout << "base float\n";
  }
};


class D : public Base {

};


int main() {

  D d = {42.3}; // works
  // D d = 42.3; // failed, unless `using Base::Base;`
}

#include <iostream>


class Base {
  public:

   Base(double, int) {
    std::cout << "base double, float\n";
  }
};

class Base2 {
  public:

   Base2(double, int) {
    std::cout << "base2 double, float\n";
  }
};


class D : public Base, public Base2 {

};


int main() {

  D d = {{42.3, 42}, {42.4, 42}};
}

[C++][Cppcon 2025] Concept-based Generic Programming - Bjarne Stroustrup

Reference:

Concept-based Generic Programming - Bjarne Stroustrup - CppCon 2025

Concepts are functions

OOP

• Focused on defining type of objects, often in class hierarchies
• Applies to one object at a time
• Relies on name equivalence
• Run-time selection among an open set of types
• Inlining is difficult (typically impossible)
• Defining an interface requires precisely specifying types
  requires significant foresight, conceptually and in technical details.

GP

•  Focused on a functions' requirements on its arguments
•  Often involving relationships among multiple arguments
•  Relies on use patterns (a generalization of structural equivalence)
•  Compile-time selection among types in scope
•  Inlining is easy
•  Doesn't offer interfaces in the ABI sense
      Use OOP for that

Concepts can be partial constraints

We can't always get first shot perfect. Needs several iterations.

Concept can take value arguments

not just type arguments(same as template, i.e. non-type arguments)

Concepts are not just for template arguments

Concept type matching

Definition checking

e.g.

consteval bool is_power_of_two(int n) {
  if (n == 0) return false;
  while ((n&1) == 0) {
    n >>= 1;
  }
  return (n==1);
}


template<int S> concept buffer_space = (1024 <= S) && is_power_of_two(S);

template<typename T, int S>
  requires buffer_space<S>
struct Buffer {
  T buf[S];
};


void test0() {
  Buffer<char, 100> b1; // error, too small.
  Buffer<char, 10000> b2; // error, not binary
  Buffer<int, 2048> b3; // ok
}

[C++] brace init. disallows narrow conversion, use it for building up can_narrow concept.

1) brace init. disallows narrow conversion 

2) `requires` can only have expression, declaration is not allowed.
(i.e. T t; is not allowed, but T{} ok)

template<typename S, typename T>
concept can_narrow = requires() {
  T {std::declval<S>()};
};

int main() {
  if constexpr (can_narrow<float, int>) {
    cout << "double to int ok";
  } else{
    cout << "double to int not ok"; // hit here.
  }
}

[C++][P2738R1] constexpr cast from void*: towards constexpr type-erasure

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2738r1.pdf

Purpose:

Storing void* instead of a concrete type is a commonly used compilation firewall technique to reduce template instantiations and the number of symbols in compiled binaries. For example, with a template class that stores a T* pointer to some data, member functions are instantiated for each template combination; if instead some member functions along with a void* were part of a non-template base class, those member functions are instantiated only once.

On memory constrained embedded platforms, a common approach to achieve run-time memory savings is to ensure common code paths. Type erasure is helpful to achieve common code paths. To save memory, it is desirable to evaluate code at compile time to the maximal extent. To keep code common between compile time and run-time, limited type erasure is required at compile time.

struct A {
    virtual void f() {};
    int a;
};

struct B {
    int b;
};

struct C : B, A {};  // C inherits B first, then A

int main() {
    C c;
    void* v = &c;

	// static_cast<B*>(v) is UB; should static_cast to most derived type then
    // static_cast to base type.
    assert(static_cast<B*>(v) == static_cast<B*>(static_cast<C*>(v)));
}

Example: (https://godbolt.org/z/aYTTWqdEd)

#include <string_view>

struct Sheep {
    constexpr std::string_view speak() const noexcept {
        return "Baaaaaa";
    }
};

struct Cow {
    constexpr std::string_view speak() const noexcept {
        return "Mooo";
    }
};

class Animal_View {
private:
    const void* animal;
    std::string_view (*speak_function)(const void*);

public:
    template <typename Animal>
    constexpr Animal_View(const Animal& a)
        : animal{&a}, speak_function{[](const void* object) {
              return static_cast<const Animal*>(object)->speak();
          }} {}

    constexpr std::string_view speak() const noexcept {
        return speak_function(animal);
    }
};

// This is the key bit here. This is a single concrete function
// that can take anything that happens to have the "Animal_View" interface
std::string_view do_speak(Animal_View av) {
    return av.speak();
}

int main() {
    // A Cow is a cow. The only thing that makes it special
    // is that it has a "std::string_view speak() const" member
    constexpr Cow cow;

    // cannot be constexpr because of static_cast
    [[maybe_unused]] auto result = do_speak(cow);

    return static_cast<int>(result.size());
}