folly Documentation

File: README.md Copy Chapter

Folly: Facebook Open-source Library

What is `folly`?

Folly (an acronym loosely after Facebook Open Source Library) is a
library of C++20 components designed with practicality and efficiency
in mind. Folly contains a variety of core library components used extensively
at Facebook. In particular, it's often a dependency of Facebook's other
open source C++ efforts and place where those projects can share code.

It complements (as opposed to competing against) offerings
such as Boost and of course std. In fact, we embark on defining our
own component only when something we need is either not available, or
does not meet the needed performance profile. We endeavor to remove
things from folly if or when std or Boost obsoletes them.

Performance concerns permeate much of Folly, sometimes leading to
designs that are more idiosyncratic than they would otherwise be (see
e.g. PackedSyncPtr.h, SmallLocks.h). Good performance at large
scale is a unifying theme in all of Folly.

Check it out in the intro video Copy Chapter

Logical Design

Folly is a collection of relatively independent components, some as
simple as a few symbols. There is no restriction on internal
dependencies, meaning that a given folly module may use any other
folly components.

All symbols are defined in the top-level namespace folly, except of
course macros. Macro names are ALL_UPPERCASE and should be prefixed
with FOLLY_. Namespace folly defines other internal namespaces
such as internal or detail. User code should not depend on symbols
in those namespaces.

Physical Design

At the top level Folly uses the classic "stuttering" scheme
folly/folly used by Boost and others. The first directory serves as
an installation root of the library (with possible versioning a la
folly-1.0/), and the second is to distinguish the library when
including files, e.g. #include <folly/FBString.h>.

The directory structure is flat (mimicking the namespace structure),
i.e. we don't have an elaborate directory hierarchy (it is possible
this will change in future versions). The subdirectory experimental
contains files that are used inside folly and possibly at Facebook but
not considered stable enough for client use. Your code should not use
files in folly/experimental lest it may break when you update Folly.

The folly/folly/test subdirectory includes the unittests for all
components, usually named ComponentXyzTest.cpp for each
ComponentXyz.*. The folly/folly/docs directory contains
documentation.

What's in it?

Because of folly's fairly flat structure, the best way to see what's in it
is to look at the headers in top level folly/ directory. You can also
check the docs folder for documentation, starting with the
overview.

Folly is published on GitHub at https://github.com/facebook/folly.

Build Notes

Because folly does not provide any ABI compatibility guarantees from commit to
commit, we generally recommend building folly as a static library.

folly supports gcc (5.1+), clang, or MSVC. It should run on Linux (x86-32,
x86-64, and ARM), iOS, macOS, and Windows (x86-64). The CMake build is only
tested on some of these platforms; at a minimum, we aim to support macOS and
Linux (on the latest Ubuntu LTS release or newer.)

`getdeps.py` Copy Chapter

This script is used by many of Meta's OSS tools. It will download and build all of the necessary dependencies first, and will then invoke cmake etc to build folly. This will help ensure that you build with relevant versions of all of the dependent libraries, taking into account what versions are installed locally on your system.

It's written in python so you'll need python3.6 or later on your PATH. It works on Linux, macOS and Windows.

The settings for folly's cmake build are held in its getdeps manifest build/fbcode_builder/manifests/folly, which you can edit locally if desired.

Dependencies Copy Section

If on Linux or MacOS (with homebrew installed) you can install system dependencies to save building them:

# Clone the repo
git clone https://github.com/facebook/folly
# Install dependencies
cd folly
sudo ./build/fbcode_builder/getdeps.py install-system-deps --recursive

If you'd like to see the packages before installing them:

./build/fbcode_builder/getdeps.py install-system-deps --dry-run --recursive

On other platforms or if on Linux and without system dependencies getdeps.py will mostly download and build them for you during the build step.

Some of the dependencies getdeps.py uses and installs are:

• a version of boost compiled with C++14 support.
• googletest is required to build and run folly's tests.

Build Copy Section

This script will download and build all of the necessary dependencies first,
and will then invoke cmake etc to build folly. This will help ensure that you build with relevant versions of all of the dependent libraries, taking into account what versions are installed locally on your system.

getdeps.py currently requires python 3.6+ to be on your path.

getdeps.py will invoke cmake etc.

# Clone the repo
git clone https://github.com/facebook/folly
cd folly
# Build, using system dependencies if available
python3 ./build/fbcode_builder/getdeps.py --allow-system-packages build

It puts output in its scratch area:

• installed/folly/lib/libfolly.a: Library

You can also specify a --scratch-path argument to control
the location of the scratch directory used for the build. You can find the default scratch install location from logs or with python3 ./build/fbcode_builder/getdeps.py show-inst-dir.

There are also
--install-dir and --install-prefix arguments to provide some more
fine-grained control of the installation directories. However, given that
folly provides no compatibility guarantees between commits we generally
recommend building and installing the libraries to a temporary location, and
then pointing your project's build at this temporary location, rather than
installing folly in the traditional system installation directories. e.g., if you are building with CMake you can use the CMAKE_PREFIX_PATH variable to allow CMake to find folly in this temporary installation directory when
building your project.

If you want to invoke cmake again to iterate, there is a helpful run_cmake.py script output in the scratch build directory. You can find the scratch build directory from logs or with python3 ./build/fbcode_builder/getdeps.py show-build-dir.

Run tests Copy Section

By default getdeps.py will build the tests for folly. To run them:

cd folly
python3 ./build/fbcode_builder/getdeps.py --allow-system-packages test

`build.sh`/`build.bat` wrapper Copy Section

build.sh can be used on Linux and MacOS, on Windows use
the build.bat script instead. Its a wrapper around getdeps.py.

Build with cmake directly Copy Chapter

If you don't want to let getdeps invoke cmake for you then by default, building the tests is disabled as part of the CMake all target.
To build the tests, specify -DBUILD_TESTS=ON to CMake at configure time.

NB if you want to invoke cmake again to iterate on a getdeps.py build, there is a helpful run_cmake.py script output in the scratch-path build directory. You can find the scratch build directory from logs or with python3 ./build/fbcode_builder/getdeps.py show-build-dir.

Running tests with ctests also works if you cd to the build dir, e.g.
(cd $(python3 ./build/fbcode_builder/getdeps.py show-build-dir) && ctest)

Finding dependencies in non-default locations Copy Section

If you have boost, gtest, or other dependencies installed in a non-default
location, you can use the CMAKE_INCLUDE_PATH and CMAKE_LIBRARY_PATH
variables to make CMAKE look also look for header files and libraries in
non-standard locations. For example, to also search the directories
/alt/include/path1 and /alt/include/path2 for header files and the
directories /alt/lib/path1 and /alt/lib/path2 for libraries, you can invoke
cmake as follows:

cmake \
  -DCMAKE_INCLUDE_PATH=/alt/include/path1:/alt/include/path2 \
  -DCMAKE_LIBRARY_PATH=/alt/lib/path1:/alt/lib/path2 ...

Ubuntu LTS, CentOS Stream, Fedora Copy Chapter

Use the getdeps.py approach above. We test in CI on Ubuntu LTS, and occasionally on other distros.

If you find the set of system packages is not quite right for your chosen distro, you can specify distro version specific overrides in the dependency manifests (e.g. https://github.com/facebook/folly/blob/main/build/fbcode_builder/manifests/boost ). You could probably make it work on most recent Ubuntu/Debian or Fedora/Redhat derived distributions.

At time of writing (Dec 2021) there is a build break on GCC 11.x based systems in lang_badge_test. If you don't need badge functionality you can work around by commenting it out from CMakeLists.txt (unfortunately fbthrift does need it)

Windows (Vcpkg) Copy Chapter

Note that many tests are disabled for folly Windows builds, you can see them in the log from the cmake configure step, or by looking for WINDOWS_DISABLED in CMakeLists.txt

That said, getdeps.py builds work on Windows and are tested in CI.

If you prefer, you can try Vcpkg. folly is available in Vcpkg and releases may be built via vcpkg install folly:x64-windows.

You may also use vcpkg install folly:x64-windows --head to build against main.

macOS Copy Chapter

getdeps.py builds work on macOS and are tested in CI, however if you prefer, you can try one of the macOS package managers

Homebrew Copy Section

folly is available as a Formula and releases may be built via brew install folly.

You may also use folly/build/bootstrap-osx-homebrew.sh to build against main:

./folly/build/bootstrap-osx-homebrew.sh

This will create a build directory _build in the top-level.

MacPorts Copy Section

Install the required packages from MacPorts:

sudo port install \
    boost \
    cmake \
    gflags \
    git \
    google-glog \
    libevent \
    libtool \
    lz4 \
    lzma \
    openssl \
    snappy \
    xz \
    zlib

Download and install folly with the parameters listed below:

git clone https://github.com/facebook/folly.git
  cd folly
  mkdir _build
  cd _build
  cmake ..
  make
  sudo make install

File: folly/coro/safe/docs/Captures.md Copy Chapter

Simple guide to `bind::capture()`, `capture` and friends Copy Chapter

If you are just reading some code with bind::capture() arguments -- think of
these as zero-cost (compile-time) smart pointers, each owned by the
async_closure taking the arg.

For example, n below is a capture. It is an owned capture, a
wrapper around int whose lifetime is tightly bound to the closure.

namespace bind = folly::bind; // Can add to `.cpp` files and project namespaces

assert(15 == co_await async_closure(
    // NB: Can omit the outer `args` -- its sole arg is `bind::ext::like_args`
    bind::args{bind::capture(5)},
    [](auto n) -> closure_task {
      co_await async_closure(
        bind::args{n},
        [](auto nRef) -> closure_task<void> {
          *nRef += 10;
          co_return;
        });
      co_return *n;
    }));

On the other hand, nRef is capture. It is a capture reference
that was implicitly made from n. Per LifetimeSafetyDesign.md, there are
various compile-time checks that make it harder to construct invalid capture
references.

When & how to use `bind::capture()` Copy Section

1. If type T requires async RAII (co_cleanup), you will need
   bind::capture_in_place<T>(). For a working example, see BackgroundTask.h or
   SafeAsyncScope.h.

2. Suppose you passed a co_cleanup type T into an async closure (example:
   safeAsyncScope<>()). Then, the closure will internally own
   co_cleanup_capture<T>, and the closure's coroutine will get a capture
   reference c.

   Now imagine your closure wants to pass a reference to a variable v
   into the cleanup object, something like c.someMethod(v). Any correctly
   implemented co_cleanup type should require that its inputs are valid
   beyond the point where its cleanup is awaited. For example, cleanup runs
   after your closure's coroutine exits, so any references to your coro's
   stack are unsafe. The capture type system causes such safety bugs not to
   compile. See LifetimeSafetyBenefits.md for more.

   captures are our mechanism for making lifetime-safe references. In order
   to make c.someMethod(v) work, you will need to make v itself a capture,
   by having your closure take auto v, and make it either:

   • bind::capture() for an owned capture, OR
   • parentA to make a capture reference from a parent's capture.

Accessing `capture`s Copy Section

If your function takes a capture, here is all you need to know:

• All capture<T> class templates act like pointers. Use -> and * to
  access your T.
• Don't worry about the difference between the capture templates -- either
  pass by auto, or use the type from the compiler error.
• Never move the capture wrapper, always move the T inside it.
  In other words -- good: *std::move(cap), bad: std::move(*cap).
• Captures should be transparent to value-category modifiers. That is:
  • const capture<T> acts like & converts to capture<const T>.
  • capture<T>& converts to capture<T&>.
  • capture<T>&& converts to capture<T&&>.
• If you pass capture<Value> c into an async_closure, it is always passed
  by-reference. That is, the child closure automatically gets
  capture<Value&>, or capture<Value&&> from std::move(c).
• capture<T> behaves much like T, besides the above caveats (must
  dereference; pass-by-reference in async closures):

  • For value type V, capture<V> represents ownership. The capture
    wrapper belongs to whatever constructed it, and should not be moved
    -- but, if V is movable, you can of course move the inner type:

    cpp Copy

    V dst = *std::move(srcCap);

  • capture<V&> is copyable & movable.

  • capture<V&&> is move-only, can explicitly convert to capture<V&>

    Caveat: To reduce use-after-move errors, dereferencing requires rvalues.
    That is, *rcap won't work -- you must *std::move(rcap).

• Power users: It is a limitation of C++ that operator-> loses value
  category by returning a pointer. In special cases where this is critical
  for a good UX, it is technically possible to address that returning a
  pointer to a specially crafted rvalue proxy for rval_ptr queries. In
  regular metaprogramming, you should use (*cap).member for deref.

`safe_alias` warning: the "composition hole" & lambda captures Copy Section

It bears repeating the "composition hole" warning from SafeAlias.h.

• If a type stores any kind of reference (like capture<Ref>) or pointer, or
  anything else that's not a straight-up value type, then it must
  correctly specialize safe_alias_of.
• When your child closure gets a lambda (or another object) from a parent,
  it is particularly risky to pass capture<Ref>s into its operator()
  (or other member function). If the parent stored any reference in that
  object, (as easy as [&](...) { ... }, then the child can incorrectly
  plumb through its own short-lived references into the parent's scope.

Syntax sugar: `capture_indirect>` Copy Section

To access capture<shared_ptr> capSharedN, you need to dereference twice:

**capSharedN += 10;

Writing bind::capture_indirect() gives you capture_indirect<shared_ptr>,
which needs just one dereference, and can still access the shared_ptr via
get_underlying_unsafe() -- but see its docblock for RISKS.

Watch out: Be sure to null-check capture_indirect via its operator bool.
This is important, since, the underlying type is typically nullable!

Escape hatch: Capture-by-reference Copy Section

Use via bind::capture_const_ref{}, bind::capture{bind::const_ref{}},
bind::capture_mut_ref{}, etc in your closure's bind::args{} list.

This mechanism solves problems similar to AfterCleanup.h, but after-cleanup
is strictly safer, so you should prefer it when applicable.

Capture-by-ref is a way of turning a reference from a parent scope into a
capture<T&> or <T&&> inside a child async_now_closure. While the
now_task restriction aids lifetime safety, the user must still be careful to
avoid giving the child the ability to store short-lived child refs in the
parent's scope. To fix a concrete instance of this problem, the
BindAsyncClosure.h implementation blocks the capture-by-ref mechanism
from passing co_cleanup refs & captures.

Design notes for capture-by-reference

This section discusses potential relaxations of the capture-by-ref safety
rules, which would make it more broadly applicable. However, the relaxations
would come with both new footguns, and new complexity, so I'm currently
thinking of them as "rejected designs" rather than future work.

Note 1: It would be within the spirit of regular RAII to defer awaiting the
closure to a later point in the current scope. That is, the safe_task taking
these capture_ref() args would be marked down to <= lexical_scope_ref
safety. This could be a new safety level with:

after_cleanup_ref >= lexical_scope_ref >= shared_cleanup

The valid lifetime for this body-only safe_task is clearly shorter than
after_cleanup_ref -- it's invalid whenever the captured refs are destroyed,
which (under typical RAII) is a bit longer than the lexical lifetime of the
task. In the lexical_scope_ref scenario, the user can, of course, invalidate
the reference before awaiting the task, but it takes a bit of effort, and might
be covered if the P1179R1 lifetime safety profile
is standardized. For example:

std::optional<safe_task<safe_alias::lexical_scope_ref, void>> t;
{
  int i = 5;
  t = async_closure([](auto i) -> closure_task<void> {
    std::cout << *i << std::endl;
    co_return;
  }, capture_ref(i));
  ++i;
}
// BAD: The reference to `i` is now invalid!
co_await std::move(*t);

Note 2: The way that async_closure(... bind::capture_const_ref(...) ...)
behaves, it seems like we could just universally allow creating
lexical_scope_capture<T&> from T& -- even outside async_closure
invocations. Captures.h would need to support auto-upgrade of
lexical_scope_capture to capture or after_cleanup_capture, depending on
shared_cleanup status. This "universal" implementation would be more
complex, but without async_closure()'s capture-upgrade semantics, there's not
a lot of value in obtaining a lexical_scope_capture<Ref> -- for example, you
can't use it to schedule work on a nested safe_async_scope.

Debugging lifetime safety compile errors Copy Section

If you're working with captures, and get a compile error about safe_task,
safe_alias_of, or similar, there is a good chance that you triggered a
lifetime safety check. Read LifetimeSafetyDebugging.md for what to do next --
it also covers the lifetime safety design of Captures.h.

Implementation gaps Copy Section

• While Captures.h mentions restricted_co_cleanup_capture, the
  implementation is not finished. See FutureWork.md for more details.
• FutureLinters.md describes several linters that help achieve maximum
  lifetime safety when using captures.

Notes for advanced users Copy Chapter

Why does `capture` even exist? Copy Section

async_closure is a lexical scope with guaranteed async RAII. When implementing
such a thing, you end up needing to store two kinds of values that live strictly
longer than the coroutine function scope itself. Specifically:

• Values with co_cleanup (details in CoCleanupAsyncRAII.md). The
  archetypal type is safe_async_scope, which is immovable to allow an
  efficient implementation -- so the storage mechanism also needs to support
  in-place construction.
• Values that outlive the cleanup, so they can be safely referenced by the
  co_cleanup types.
• Both kinds of values are passed by-reference into the inner coro. And,
  since async_closure tasks often need to be movable (e.g. to run on
  scopes), the value storage must provide stable pointers.
• In addition to the above two special types of data, we want to be able to
  pass regular arguments into async closures, without ambiguity.

At its core, capture<T> addresses those "must have" needs.

However, it also provides some important "bonus" features:

• As discussed in "your own co_cleanup type" below, types supporting
  co_cleanup should not be usable outside of a "managed" context that always
  awaits cleanup.

  Without captures, passing a "passkey" type into the in-place constructor for
  co_cleanup type could address this need (with some static assertions).
  However, with captures, capture_proxy gives us a cleaner solution.

• captures also help us enforce safe_alias lifetime safety heuristics
  using the type system. Doing something equivalent with static analysis on
  "plain" arguments would be prohibitive, e.g. because it would require
  chasing references across compilation units. In contrast, capture types
  automatically embed a lifetime safety contract.

`shared_cleanup` closures downgrade `capture` safety to `after_cleanup_` Copy Section

tl;dr If you see after_cleanup_SOME_capture, know that it quacks just like
SOME_capture, but with a lower safe_alias level. If this behavior is
blocking you, you may benefit from finishing restricted_co_cleanup_capture.

Problem solved

When a child closure takes a reference to a parent's async scope, it can easily
give a short-lived reference to a longer-lived task on that scope:

co_await async_closure(
    safeAsyncScope<CancelViaParent>(),
    [](auto scope) -> closure_task<void> {
      co_await async_closure(
          bind::args{scope, bind::capture(5)},
          [](auto outerScope, auto n1) -> closure_task<void> {
              outerScope->with(co_await co_current_executor).schedule(
                  [](capture n2) -> co_cleanup_safe_task<void> {
                    assert(*n2 == 5); // Invalid memory access!
                    co_return;
                  }(n1));
          });
    });

Note that the lifetime of n1 aka n2 is shorter than that of scope. That
is, by the time *n2 happens, the closure owning n1 may have been destroyed.

Fortunately, this code doesn't compile thanks to the after_cleanup_ downgrade
described below:

no known conversion from 'after_cleanup_capture' to 'capture'

Changing the inner lambda to after_cleanup_capture still won't compile:

Bad safe_task: check for unsafe aliasing in arguments or return type

Relaxing the inner task to safe_task<safe_alias::after_cleanup_ref, void> also
won't let the bug through, since schedule() won't take a less-safe task.

constraints not satisfied ... schedule( ...
is_void_safe_task<
    safe_task<safe_alias::after_cleanup_ref, void>,
    safe_alias::co_cleanup_safe_ref>' evaluated to false

To understand the solution, let's reformulate this bug more abstractly:

• Any closure taking co_cleanup_capture<T&> is vulnerable to the problem,
  unless the API of T specifically ensures that it only takes inputs of
  safety maybe_value. In this section, we focus on co_cleanup types that
  must be able to take references, like safe_async_scope.

  NB: Types with value-only APIs should expose capture_restricted_proxy().

• Actually, closures sometimes reference co_cleanup types in ways besides
  co_cleanup_capture<T&> -- for example, capture<AsyncObjectPtr<T>>. For
  this reason, we define a brand-new level safe_alias::shared_cleanup,
  which must be used for any type that may give a child closure access to the
  parent's longer-lived lexical scope.

  Note: The name shared_cleanup aims to evoke that a child taking such
  an argument must take the parent's perspective on safety measurements.

• By definition, APIs of co_cleanup types must guard against inputs less
  safe than co_cleanup_safe_ref, so the problem can only occur if a child
  is able to obtain a plain capture<> (or equivalently capture_heap<> /
  `capture_indirect<>).

• Plain capture<>s come about in two ways:

  • Getting a capture<> reference from a parent. This scenario is fine --
    if the parent could safely hold the capture<> together with the
    co_cleanup_capture<T&> that creates the risk, then it's no less safe
    for the child to handle that capture ref.

  • Making an owned capture. By default, owned captures are plain, but
    in the above example, after_cleanup_capture<> makes an appearance.
    That is, in fact, the fix!

    Anytime a closure takes a shared_cleanup input, it loses the
    ability to instantiate plain captures. Its owned captures get the
    after_cleanup_ prefix (the "downgrade"), and it can no longer
    "upgrade" after_cleanup_capture references that it gets from a parent
    -- more on both below.

Now that you saw the problem, and the solution, let's review the formalism.

Upgrade/downgrade rules

The reference downgrade rules rely on the fact that co_cleanup_capture APIs
(per "your own co_cleanup type" below) are required to check that the lifetime
safety of each input is >= co_cleanup_safe_ref.

An async_closure is considered shared_cleanup if any of its external
(non-owned) arguments have shared_cleanup safety. Such closures deviate from
normal capture-passing rules in two ways:

• Own captures are downgraded: In the example, you will note that n1 is
  of type after_cleanup_capture. Whereas, in the absence of outerScope,
  the type would be capture.

• Parent captures are not upgraded: Suppose the example scheduled a
  closure: .schedule(async_closure(bind::args{n1}, ...)). Then, inside
  that closure n1 would be visible as capture because it can't be
  exfiltrated to outerScope. That's the upgrade behavior[†]. But, when
  passing bind::args{outerScope, n1}, the shared_cleanup argument blocks
  the upgrade, and the closure would still see after_cleanup_capture.

  [†] Note that when a closure upgrades its refs, e.g. from
  after_cleanup_capture to capture, the safety of the closure's task is
  not affected. That is, reference upgrades are an internal matter.

**Why is the downgraded name `after_cleanup_`?**

In short, because such captures can safely be used in co_return move_after_cleanup() and similar constructs.

We need a new after_cleanup_ref level because:

• after_cleanup_capture is safer than a shared_cleanup ref, which is
  not allowed in move_after_cleanup et al.
• after_cleanup_ref is less safe than co_cleanup_safe_ref, since we don't
  want the downgraded references to be scheduled on scopes.

Avoid safety downgrades via `restricted_co_cleanup_capture` Copy Section

NB: This feature isn't fully implemented yet (see "Implementation gaps"
in this doc, and FutureWork.md), but what remains is quite simple, just
search the code for "restricted".

In some scenarios -- e.g. passing around a fire-and-forget logger -- it is
important to avoid the safety downgrade. For example, a closure taking a
co_cleanup_capture<Logger&> would be unable to pass any of its own captures to
a co_cleanup_capture<safe_async_scope&> that it owns.

To avoid downgrades, pass restricted_co_cleanup_capture<Logger&> to the child
closure. This capture uses ADL customization point
capture_restricted_proxy() to dereference, returning a proxy object that
only accepts inputs with maybe_value safety. Obviously, such a proxy
cannot accidentally pass short-lived refs from a child closure to a parent
co_cleanup_capture, and thus it needs no downgrades.

IMPORTANT: The implementation must pick between one of:

• "once restricted, always restricted"
• "restricted->unrestricted also downgrades captures from parents"

What we cannot do is "let a closure take a formerly restricted ref as
unrestricted and take non-downgraded refs from parents." If both were
possible at once, then the following lifetime safety violation could occur:

• depth 0: creates a co_cleanup_capture<S&> x0
• depth 1: takes restricted x1 and owns capture y1
• depth 2: unrestricts x1 as x2, takes ref to y1 as y2
  The problem is that short-lived y2 can now be passed to x0. Either
  solution above eliminates the safety gap.

The no-cleanup closure optimization & `_heap` captures Copy Section

Although async_closure was built to support async RAII, it should also see
usage just because of LifetimeSafetyBenefits.md.

Closures are implemented in such a way that users don't have to choose between
safety and performance. Specifically, an async closure that takes no
co_cleanup captures should perform exactly the same as the bare inner
coroutine.

This zero-cost behavior is called the "no-cleanup closure optimization". When
implementing async RAII, it is hard (or perhaps impossible) to avoid allocating
a second coro frame, the one that awaits cleanup. But, when async_closure sees
that it owns no co_cleanup_captures, it will:

• Omit the outer coro frame (which would now be no-op)
• Move in its own captures into the inner coro.
• For owned captures that are bind::in_place, automatically use the
  capture_heap variation.

From most perspectives, a no-cleanup closure quacks just like its
outer-coro-awaits-inner-coro cousin. However, its own capture args' signatures
will differ:

• capture<Value> is passed instead of capture<Value&>.
• bind::in_place captures use the capture_heap template.

By design, reference and value, plain and _heap captures have identical
interfaces, letting async_closure freely pick the storage for those typical
inner coros that take all captures by auto.

In the unlikely event of a no-cleanup closure taking lots of bind::in_place
captures, you can try async_closure::force_outer_coro to coalesce allocations.

Integrating your own `co_cleanup` type Copy Section

This section assumes you're familiar with CoCleanupAsyncRAII.md.

A properly implemented co_cleanup type T should:

• Construct T in a state that does not yet require cleanup.

• Be immovable, e.g. derive from private folly::NonCopyableNonMovable.

  This prevents lifetime issues, since all our safety checks assume that
  the T is cleaned up by its original owner.

• Restrict public APIs that affect T's need for cleanup to only be
  accessible by dereferencing co_cleanup_capture<T&>. This guarantees that
  if cleanup is needed, it will be called.

  When capture types evaluate operator* and operator->, they look
  for an ADL customization point. Declare it like so:

  cpp Copy

  template <capture_proxy_kind Kind, const_or_not<YourType> T>
  friend auto capture_proxy(capture_proxy_tag<Kind>, T&);

  This should return a proxy type implementing your public API appropriate
  for both Kind, and the const-qualification of T -- forward_like
  may be useful when accessing members of T. The proxy type should be
  NonCopyableNonMovable with a constructor restricted to your class.

• For public APIs, require lenient_safe_alias_of_v of at least
  co_cleanup_safe_ref for any input that may be stored until cleanup time.

• If restricted_co_cleanup_capture<T&> support is desired, ADL-customize
  capture_restricted_proxy() as above, and enforce that all API inputs have
  lenient_safe_alias_of_v of maybe_value.

How many templates are in this type zoo? Can't you type-erase? Copy Section

Look at is_any_capture. There are 8 as of this writing. Only the 3
after_cleanup_ ones are specific to lifetime-safety tracking.

We deliberately chose distinct templates instead of template parameters, since
this should result in more readable compiler errors.

Type-erasure isn't a very practical idea for simplifying the type signatures.
There are two reasons:

• folly/coro/safe should be zero-cost so teams can adopt it confidently.
• We shouldn't type-erase the lifetime safety level, and at present 4
  different ones need to be distinguished.

Shrinking the capture type zoo from 8 to 4 doesn't seem worth the runtime &
complexity cost of type erasure.

Why do `capture`s quack like pointers? Copy Section

Morally, they are either values or references, and the "pointer-like" UX hurts
ergonomics.

Let's consider the "no wrapper" alternative. It would be possible for
bind::capture() args to async_closure to just pass a reference to the
underlying type into the inner coro. This comes with many downsides:

• Bug farm: The inner coro has to remember to write auto& / ActualType& --
  except when you have the no-cleanup closure optimization. Pass-by-value
  for non-cleanup captures will compile, making a copy, but the runtime
  behavior is wrong. This is fragile enough that I wold abandon the no-cleanup
  optimization in this scenario.
• Clarity: The inner coro signature doesn't distinguish between captures and
  plain arguments, even though they have important lifetime differences (only
  capture refs can be passed into async scope tasks, e.g.).
• Raw reference: no lifetime safety checks are possible.
• To prevent co_cleanup types from being used in unmanaged contexts, we'd
  have to use the "passkey constructor" pattern, which is less flexible than
  the capture_proxy design.

While C++20 lacks a good story for generic reference-like wrapper
types,
per above, the uglier dereferenceable wrapper style provides benefits that far
outweigh the syntactic boilerplate.

File: folly/coro/README.md Copy Chapter

Coro

Introduction Copy Chapter

folly::coro is a developer-friendly asynchronous C++ framework built on C++20 coroutines.

Basic example Copy Section

folly::coro::Task task42() {
  co_return 42;
}

folly::coro::Task taskSlow43() {
  co_await folly::futures::sleep(std::chrono::seconds{1});
  co_return co_await task42() + 1;
}

int main() {
  ...
  CHECK_EQ(43, folly::coro::blockingWait(co_withExecutor(
      folly::getGlobalCPUExecutor(), taskSlow43())));
  ...
}

The same logic implemented with folly::SemiFuture:

folly::SemiFuture task42() {
  return folly::makeSemiFuture().deferValue([](auto) {
    return 42;
  });
}

folly::SemiFuture taskSlow43() {
  return folly::futures::sleep(std::chrono::seconds{1})
      .semi()
      .deferValue([](auto) { return task42(); })
      .deferValue([](auto value) { return value + 1; });
}

int main() {
  ...
  CHECK_EQ(
      43,
      taskSlow43().via(folly::getCPUExecutor().get()).get());
  ...
}

Features Copy Section

• Better performance than folly::Future
• Full-compatibility with folly::Future and folly::SemiFuture
• Asynchronous synchronization primitives (e.g. coro::Baton, coro::Mutex, coro::SharedMutex)
• Compatible with other libraries based on C++20 coroutines

Overview Copy Chapter

Writing a coroutine Copy Section

Any function that returns a folly::coro::Task and has at least one use of co_await or co_return is a coroutine.

Use co_return instead of return in a coroutine.

folly::coro::Task task42() {
  co_return 42;
}

folly::coro::Task task43() {
  auto value = co_await task42();
  co_return value + 1;
}

Starting a coroutine Copy Section

Calling a folly::coro::Task-coroutine function captures the arguments, but doesn't start executing the coroutine immediately. Instead the coroutine is lazily started when you co_await the task.

Alternatively, you can start executing a coroutine from a normal function by attaching a folly::Executor via co_withExecutor() and either calling start() or using folly::coro::blockingWait().

folly::coro::Task<void> checkArg(int arg42) {
  CHECK_EQ(42, arg42);
  co_return;
}

void runCoroutine1() {
  int arg42 = 42;
  // Coroutine arguments are captured here, not when we start the coroutine.
  auto task = checkArg(arg42);
  arg42 = 43;
  folly::coro::blockingWait(co_withExecutor(
      folly::getCPUExecutor(), std::move(task)));
}

void runCoroutine2() {
  folly::SemiFuture<folly::Unit> f = co_withExecutor(
      folly::getCPUExecutor(), checkArg(42)).start();
}

Executor stickiness Copy Section

Every folly::coro::Task will always be running on the Executor on which it was launched, even if it co_awaited something that completed on a different Executor.

You can extract the Executor which the folly::coro::Task is running on by using folly::coro::co_current_executor.

folly::coro::Task task42Slow() {
  // This doesn't suspend the coroutine, just extracts the Executor*.
  folly::Executor* startExecutor = co_await folly::coro::co_current_executor;
  co_await folly::futures::sleep(std::chrono::seconds{1});
  folly::Executor* resumeExecutor = co_await folly::coro::co_current_executor;
  CHECK_EQ(startExecutor, resumeExecutor);
}

By default, when a folly::coro::Task is awaited within the context of another Task it inherits the executor from the awaiting coroutine. If you want to run a child coroutine on a different executor then you can call co_withExecutor() to explicitly specify an alternative executor.

folly::coro::Task<void> foo() {
  co_await folly::futures::sleep(std::chrono::seconds{1});
  std::cout << "Current executor is " << (co_await folly::coro::co_current_executor) << std::endl;
}

folly::coro::Task<void> bar(folly::CPUThreadPoolExecutor* otherExecutor) {
  // Executes foo() on whatever execution context bar() was launched on.
  co_await foo();

  // Launches foo() on 'otherExecutor' and when it's done resumes this
  // coroutine on whatever executor bar() was launched on.
  co_await co_withExecutor(otherExecutor, foo());
}

Awaitables Copy Section

You can co_await anything that follows the C++ awaitable protocol.
It can be folly::coro::Task, folly::Future, folly::SemiFuture etc.

Keep in mind that an Awaitable may result in an exception, so you'll have to use try-catch blocks to handle errors.

folly::coro::Task<void> throwCoro() {
  throw std::logic_error("Expected");
  co_return;
}

folly::coro::Task<void> coro() {
  auto future42 = folly::makeSemiFuture(42);
  EXPECT_EQ(42, co_await std::move(future42));

  try {
    co_await throwCoro();
    LOG(FATAL) << "Unreachable";
  } catch (const std::logic_error&) {
  } catch (...) {
    LOG(FATAL) << "Unreachable";
  }
}

Concurrently awaiting multiple Tasks Copy Section

When you invoke a coroutine that returns a folly::coro::Task, the coroutine
doesn't begin execution immediately. It only starts when you apply co_await
to the returned task. Applying co_await also suspends the coroutine that is
awaiting, until the awaited operation is complete.

This means that you cannot perform two operations concurrently by simply calling
the two coroutines and later awaiting them both.

SLOWER: The following will execute the two operations sequentially

folly::coro::Task task1();
folly::coro::Task task2();

folly::coro::Task example() {
  auto t1 = task1();
  auto t2 = task2();
  int result1 = co_await std::move(t1);
  int result2 = co_await std::move(t2);
  co_return result1 + result2;
}

If, instead, you want to perform these operations concurrently and wait until
both of the operations complete you can use folly::coro::collectAll().

FASTER: The following may execute the two operations concurrently

folly::coro::Task task1();
folly::coro::Task task2();

folly::coro::Task example() {
  auto [result1, result2] =
      co_await folly::coro::collectAll(task1(), task2());
  co_return result1 + result2;
}

Note that in the above example, when the co_await expression is evaluated
it first launches the task1() coroutine and it will execute in the current
thread until it reaches its first suspend-point, at which point it will then
launch task2(). Once both sub-tasks are complete then the example()
coroutine is resumed with a tuple of the individual results.

Note that if both task1() and task2() complete synchronously then they
will still be executed sequentially.

Handling partial failure Copy Section

When executing multiple sub-tasks concurrently it's possible that some of those
tasks will fail with an exception and some will succeed.

If you use the folly::coro::collectAll() function to concurrently wait for
multiple tasks to complete then any partial results are discarded if any of
the tasks complete with an exception. If multiple sub-tasks complete with an
exception then one of the exceptions is rethrown as the result and the others
are discarded.

If you need to be able determine which sub-operation failed or if you need
to be able to retrieve partial results then you can use folly::coro::collectAllTry()
instead. Instead of producing a tuple of the results it produces a tuple of
folly::Try<T> values, one for each input task.

folly::coro::Task task1();
folly::coro::Task task2();

folly::coro::Task example() {
  auto [try1, try2] = co_await folly::coro::collectAllTry(task1(), task2());
  int result = 0;

  if (try1.hasValue()) {
    result += try1.value();
  } else {
    LOG(ERROR) << "Error in task1(): " << try1.exception().what();
  }

  if (try2.hasValue()) {
    result += try2.value();
  } else {
    LOG(ERROR) << "Error in task2(): " << try2.exception().what();
  }

  co_return result;
}

folly::SemiFuture Copy Section

Any folly::coro::Task can be converted to a folly::SemiFuture by calling .semi(). Use this for interoperability with APIs that require folly::Future or folly::SemiFuture; otherwise, prefer coroutine-native primitives.

folly::coro::Task task1();
folly::coro::Task task2();

folly::coro::Task sumTask() {
  auto f1 = task1().semi();
  auto f2 = task2().semi();

  folly::Try r1, r2;
  std::tie(r1, r2) = co_await folly::collectAllSemiFuture(std::move(f1), std::move(f2));

  co_return *r1 + *r2;
}

Lambdas Copy Section

A lambda can be a coroutine, but its return type must be specified explicitly because the compiler cannot deduce it from the body.

IMPORTANT: You need to be very careful about the lifetimes of temporary lambda objects. Invoking a lambda coroutine returns a folly::coro::Task that captures a reference to the lambda and so if the returned Task is not immediately co_awaited then the task will be left with a dangling reference when the temporary lambda goes out of scope.

Use the folly::coro::co_invoke() helper when immediately invoking a lambda coroutine to keep the lambda alive as long as the Task.

BAD: The following code has undefined behavior.

folly::coro::Task<Reply> coro_send(const Request&);

folly::SemiFuture<Reply> semifuture_send(const Request& request) {
  auto task = [request]() -> folly::coro::Task<Reply> {
    auto reply = co_await coro_send(request);
    if (reply.isError()) {
      LOG(reply.error().message());
    }
    co_return reply;
  }(); // <-- Whoops, lambda is destroyed at semicolon.

  return std::move(task).semi();
}

GOOD: Use co_invoke to invoke the lambda to prevent the lambda from being destroyed.

folly::SemiFuture<Reply> semifuture_send(const Request& request) {
  auto task = folly::coro::co_invoke([request]() -> folly::coro::Task<Reply> {
    auto reply = co_await coro_send(request);
    if (reply.isError()) {
      LOG(reply.error().message());
    }
    co_return reply;
  });

  return std::move(task).semi();
}

Writing loops with coroutines Copy Section

Sequential retry loop

folly::coro::Task<void> pingServer();

folly::coro::Task<void> pingServerWithRetry(int retryCount) {
  for (int retry = 0; retry <= retryCount; ++retry) {
    try {
      co_await pingServer();
      co_return;
    } catch (...) {
      LOG(WARNING) << "Ping attempt " << retry << " failed";
      if (retry == retryCount) throw;
    }
    // Wait before trying again.
    co_await folly::futures::sleep(10ms);
  }
}

Concurrently execute many operations

Operations with side-effects:

folly::coro::Task<void> doWork(int i);

folly::coro::Task<void> example(int count) {
  std::vector<folly::coro::Task<void>> tasks;
  for (int i = 0; i < count; ++i) {
    tasks.push_back(doWork(i));
  }
  co_await folly::coro::collectAllRange(std::move(tasks));
}

Operations that return values:

folly::coro::Task<std::string> getString(int i);

folly::coro::Task<void> example(int count) {
  std::vector<folly::coro::Task<std::string>> tasks;
  for (int i = 0; i < count; ++i) {
    tasks.push_back(getString(i));
  }

  // Concurrently wait for all of these tasks.
  std::vector<std::string> strings =
      co_await folly::coro::collectAllRange(std::move(tasks));

  // ... use 'strings'
}

File: folly/debugging/exception_tracer/README.md Copy Chapter

Exception tracer library

This library allows you to inspect the exception stack at runtime.
The library can be used in three ways:

1. Link in the exception_tracer_base library. You get access to the functions
   in ExceptionTracer.h, but no stack traces. This has no runtime overhead,
   and is compliant with the C++ ABI.

2. Link in the (full) exception_tracer library. You get access to the
   functions in ExceptionTracer.h, the std::terminate and std::unexpected
   handlers are installed by default, and you get full stack traces with
   all exceptions. This has some runtime overhead (the stack trace must be
   captured and stored whenever an exception is thrown) added to throw
   and catch, but no runtime overhead otherwise. This is less portable
   (depends on internal details of GNU's libstdc++).

3. LD_PRELOAD libexceptiontracer.so. This is equivalent to #2 above, but
   requires no link-time changes. On the other hand, you need to ensure that
   libexceptiontracer.so is compiled with the same compiler and flags as
   your binary, and the usual caveats about LD_PRELOAD apply (it propagates
   to child processes, etc).

File: folly/detail/base64_detail/README.md Copy Chapter

This file contains explanation of how SIMD implementation of Base64 functions

Our solution is based on 0x80 blog: encoding, decoding.

This is a different version of the same explanation + we have some differences.

NOTE: We are using 1 digit for two bits when writing data

Understanding Base64 encoding.

If you find it easier, Wikipedia.

The goal of base64 is to encode arbitrary byte data as text that can be passed around.
It works as follows:

• we select a 64 character alphabet.
• we insert two 0 bits after each 6 bits. 2^6 is 64.
• because we now only need to encode 64 values, our alphabet is sufficient.

Encoding

So, we have 2 steps needed to do the conversion: 1. get indexes 0-64, 2. lookup the corresponding char.
There is also a little bit of tail handling, see the appropriate section.

If one letter represents two bits, it looks smth like this (remember - our machines are little endian):

`cddd`bbcc`aaab => 0ddd`0ccc`0bbb`0aaa

After this we just have to convert the bytes into the selected alphabet.

This means we have two steps to the algorithm: encodeToIndexes and lookupByIndex.

encodeToIndexes Copy Chapter

NOTE: assume 16 byte registers.

We will only be converting 12 bytes to output 16 bytes.
The last 4 loaded bytes are ignored.

1. We need to shuffle bytes in a way that each dword contains all the bits to construct output for that dword. Specifically:

PONM,LKJI,HGFE,DCBA => KLJK,GIGH,EFDE,BCAB

STEP BY STEP:

• We had bytes in memory ABCD.
• Loaded on a LE machine they become DCBA.
• The first output dword will only fit ABC,
  D goes into the second dword.

• We will also reshuffle CBA as BCAB because this will make
  further operations simpler.

After this we will mutate each dword (letter+digit indicate 2 bits):

shuffled b2b3c1c2'c3d1d2d3'a1a2a3b1'b2b3c1c2
expected 00d1d2d3'00c1c2c3'00b1b2b3'00a1a2a3

At the moment of writing this we only have an SSE4.2 version. We can do it fairly straightforwardly with shifts and blends. However the 0x80 blogs suggests that using a tricky multiplication scheme is superior, and that's what we do.

For neon there are by element shift instructions which would help.
On avx2 there are srlv family of instructions that can come in handy as well.
The 0x80 blog also talks about a BMI implementation (pdep/pext instructions). They had issues on AMD but apparently not on the AMDs in Meta's fleet, so in the future we can consider it as a possibility as well.

lookupByIndex Copy Chapter

The idea is to use table lookup/shuffle instructions (pshuvb on sse4.2). They allow you to shuffle a register by index (0..16).

We have values 0..64. However, we can utilize that the output values are not random. The are split into a few contiguous groups. We don't have to lookup the complete encoding, we just need to lookup the offset to add.

NOTE: the URL version of Base64 encoding uses -_ instead of +/.

Since we have 16 values to map to, we are not going to bother with consolidating 52-61 to a single base and instead will them up individually.

This is our final lookup table:

0: 'A' - 0
1: 'a' - 26
2: '0' - 52,
3: '1' - 53
...
11: '9' - 61
12: '+' - 62
13: '/' - 63
14: -
15: -

We even have two extra indexes 14 and 15 that are unused.

Tail handling Copy Chapter

What if we have less than register size to load?
What if we have less than 3 elements to encode?

Base64 for incomplete 3 bytes works as if there were
extra 0s at the end, except the garbage elements are replaced
with either a padding character or just removed.

Example:

After measuring different options, using scalar loop peeling
proved to be the fastest.

Decoding

Overall the decoding process is similar to inverse of the encoding: 1. from chars get numbers 0..63 2. pack them
into bytes.

However, unlike encoding, not all the sequences of bytes are valid.
We have to decide which ones to accept and how to handle errors.

NOTE: error detection is fairly expensive, if in the
future there is a need for a decode that can sometimes
swallow invalid values, it can be done faster.

Decisions:
base64Decode requires = padding and accepts only [+, /] as 62/63 character.
If there are extra bits on the end, those are not allowed: iZ== is not a valid input
because no input sequence will produce it.
base64URLDecode: allows everything encoded with plain base64 and base64URL.
It will successfully decode some combinations that are not either. The extra bits on
the end are currently allowed: iZ== will decode successfully (this decision is not
motivated by anything).

NOTE: details on baseURLDecode rules:

• Padding bytes follow regular base64: if they are present they are allowed to be only in positions that
  regular base64 allows them to be in: 4th or 3rd and 4th in the 4 byte chunk. "aa==", "aaa=" - OK, "aa=", "==" - not OK. This decision follows the previous most common implementation of base64 in the codebase.
• Both ['+', '/'] and ['-', '_'] are allowed in any combinations. "+-" is legal for example.

NOTE: this follows the previous design and not necessarily how other places define
base64URLDecode. The difference comes to decoding invalid sequence of padding characters.
Example: "ba=" we consider invalid while some other implementations might just strip '='. We
suspect it won't be an issue.

This behaviour matches what the previous implementation did.

We only have a SIMD version of this algorithm for base64Decode because the URL decode has
very little use (so far at least).

The SIMD algorithm has 2 steps:

• decodeCharToIndex: convert to numbers from 0..63
• packIndexesToBytes: packs 0..63 into the originally encoded bytes.

If we encounter an error, we are not going to stop processing data. We are just going to mark it and then check at the end.

decodeCharToIndex Copy Chapter

Conversions we want

Idea Copy Section

We have unique higher 4 bits (nibble) per consecutive group,
except for '+' and '/'.
We can find a unique offset with pshuvb by it.

Deal with '+' and '/' nibbles Copy Section

We need to move '+' and '/' into their own nibbles.
It's important that all previously invalid chars stay invalid.

The best way I see to do it is to subtract 0x0f from everything less than or equal to +.
The reason to use 0x0f is that it's a constant we will need anyways ot get 4 higher nibbles.

However on intel there is no unsigned comparison, so all the negative values will be considered as <= '+'. To deal with it, we can use a signed comparison but subtract with saturation.

• <= '+' gives -1 where '+'
• and 0x0f
• subs

Everything bigger than '+' will stay the same.
Everything smaller than '+' is invalid and will become even smaller.
It will saturate to -127 which is still invalid, so we are OK.

NOTE: I was also thinking if this is possible to do with just one subtraction and no mask. Unfortunately we also need to keep a separate nibble for '0' and '/' and '0' == '/' + 1, so that subtraction will guarantee put '/' and '0' on the same higher nibble.

NOTE: If we drop the requirement on invalid elements, again - this is much easier.

New conversion table:

Detect invalid values. Copy Section

The idea is that we have valid higher nibbles in range from 1..7.
We can convert higher nibbles into a bitmask 0000'0010 ... 1000'0000 (1 << nibble)
Due to a lack of proper shift instruction on x86, we will use a table lookup (pshuvb).
All other higher nibbles can become 0, indicating invalid input.

Now for all possible lower nibbles we have a set of valid higher nibbles.

So: by higher nibble lookup a bit that indicates that higher nibble
by lower nibble lookup a set of valid bits
and

This will give us a non-zero when it's OK.
And 0 when it's not.

Between iterations we can accumulate error with unsigned min.
0 - is the smallest value - so we will get 0 if there was one.

Offset to correct values. Copy Section

Similar idea to encode - we just lookup the proper offset and add it.
We'll need to lookup by higher nibble.

packIndexesToBytes Copy Chapter

NOTE: assume 16 byte registers.

From a register of 16 bytes we need to get 12 bytes.
I think the only way to do it is to convert each 4 bytes to
appropriate 3 bytes and then put them all together.
After we doing conversion 4 to 3 we'll remove the leftover byte
with one shuffle.

Goal (One letter - 2 bits):

• Input: 0ddd'0ccc'0bbb'0aaa
• Needed bytes: 'cddd'bbcc'aaab

We can obviously shift and or to get the desired result
(and maybe on ARM we should) but again, shifting story for x86 is poor.

The 0x80 blog suggests the following trick.

Multiply add (MADD) solution Copy Section

On SSE there are madd instructions for adjacent bytes (_mm_maddubs_epi16) and words (_mm_madd_epi16). Multiply is a strictly more powerful operation than shift, so this will work.

NOTE: all of our numbers are positive so the sign of the operations doesn't matter

Here is the scalar equivalent of the code we'll do.
(I omit indicating leading 0s and ignore casts).

std::uint16_t aaabbb = aaa << 6 + bbb;
std::uint16_t cccddd = ccc << 6 + ddd;
std::uint32_t aaabbbcccddd = aaabbb << 12 + cccddd;

Multiplication equivalent of << 6 is * 0x40 and of << 12 is * 0x1000.

Now that we have 0000'aaab'bbcc'cddd.
The correct order cddd'bccc'aaab which we can mix
into the final shuffle.

looping Copy Chapter

We can convert only in registers. There is a question: when can we write the whole
register to the output?
For example, for 16 bytes of input (no padding) we only have 12 bytes of output space.

A simple way to answer if we have enough space is to compute how much output space we'll need overall.
However, this operation is somewhat expensive and is likely already done for the allocation. So computing output size ideally should be avoided.

We can prove that as long as the Register is bigger than 16 bytes, 1.5 Register of input space is enough to guarantee at least one register of the output space.

Proof.

Out of 1.5 Register, 1 Register converts to 0.75 Register in the output. So we are left with proving that 0.5 Register will produce at least 0.25 Register of the output.

If there is no padding - 0.5 converts to 3/8, which is > 0.25.
If there is padding, the last dword of input might produce just 1 output byte.

So, we need to prove that:

convertedSize(RegisterSize / 2 - 4) >= RegisterSize / 4 - 1

For 16 bytes it works convertedSize(4) == 3.
For Register > 16 bytes, we can split:

convertedSize(RegisterSize / 4) +
convertedSize(RegisterSize / 4 - 4) >=
RegisterSize / 8 +
RegisterSize / 8 - 1

Since convertedSize(RegisterSize / 4) > RegisterSize / 8 we just reduced the problem to 16 bytes.

Proven.

Decoding SWAR Copy Chapter

SWAR stands for SIMD Within A Register i.e. using bit tricks to
process multiple bytes in a bigger integer register.
Previous version of Base64Decode was using some bit tricks and, as a result,
was beating our performance for tails.

On top of that, if the platform lacks the necessary SIMD capabilities, SWAR is
beneficial, so we decided to implement it.

How does it work?

The simple version of the decoding algorithm matches from the input char to
the index: let's say char a is matched to the number 26. So we would first match
chars to the corresponding indexes and then blend those indexes together.

Let's say (one letter still 2 bits):

0AAA'0BBB'0CCC'0DDD  // input chars
0aaa'0bbb'0ccc'0ddd  // corresponding bytes
cddd'bbcc'aaab'____  // after a bunch of bit manipulations
                     // (last byte is w/e)

However, what if we incorporated both position and character in the lookup table?

char:                 0AAA
corresponds to index: 0aaa

[0][0AAA] = 0000'0000'aaa0'0000
[1][0AAA] = 0000'aa00'000a'0000
[2][0AAA] = a000'00aa'0000'0000
[4][0AAA] = 0aaa'0000'0000'0000

This way we can just or results for all input chars.
Since we have one byte, which is always 0000, we can use that byte for marking errors.
So for a busted input we can just store 0xffffffff. We will or everything we output - and then check for 0xffffffff in the end.

This is the formula for each position (d - decoded index for char):

d << 2;                                   // 0: 0000'0000'0000'aaa0
d >> 4 | (d << 12 & 0xff00);              // 1: 0000'0000'bb00'000b
(d << 6 & 0xff00) | (d << 22 & 0xff0000); // 2: 0000'c000'00cc'0000
d << 16;                                  // 3: 0000'0ddd'0000'0000

This is a memory/speed trade off. For a simple table lookup decoding we store 256 bytes. For this decoding we store 256 * 4 * 4 = 4kb. On big enough data this is a win of about a third over naive code. As far as SIMD clean up code is concerned, this is more questionable but for now we decided to go with it given that it shows an
improvement in microbenchmarks.

File: folly/docs/AtomicHashMap.md Copy Chapter

`folly/AtomicHashmap.h` Copy Chapter

folly/AtomicHashmap.h introduces a synchronized UnorderedAssociativeContainer
implementation designed for extreme performance in heavily multithreaded
environments (about 2-5x faster than tbb::concurrent_hash_map) and good memory
usage properties. Find and iteration are wait-free, insert has key-level lock
granularity, there is minimal memory overhead, and permanent 32-bit ids can be
used to reference each element.

Limitations Copy Section

Although it can provide extreme performance, AtomicHashmap has some unique
limitations as well.

• The space for erased elements cannot be reclaimed (they are tombstoned
  forever) so it's generally not a good idea to use this if you're erasing things
  a lot.

• Only supports 32 or 64 bit keys - this is because they must be atomically
  compare-and-swap'ed.

• Growth beyond initialization reduces performance - if you don't know
  the approximate number of elements you'll be inserting into the map, you
  probably shouldn't use this class.

• Must manage synchronization externally in order to modify values in the map
  after insertion. Lock pools are a common way to do this, or you may
  consider using folly::PackedSyncPtr<T> as your ValueT.

• Must define special reserved key values for empty, erased, and locked
  elements.

For a complete list of limitations and departures from the
UnorderedAssociativeContainer concept, see folly/AtomicHashMap.h

Unique Features Copy Section

• value_type references remain valid as long as the map itself. Note this is
  not true for most other probing hash maps which will move elements when
  rehashing, which is necessary for them to grow. AtomicHashMap grows by chaining
  additional slabs, so elements never need to be moved.

• Unique 32-bit ids can be used to reference elements in the map via
  iterator::getIndex(). This can be helpful to save memory in the rest of the
  application by replacing 64-bit pointers or keys.

• Iterators are never invalidated. This means you can iterate through the map
  while simultaneously inserting and erasing. This is particularly useful for
  non-blocking map serialization.

Usage Copy Section

Usage is similar to most maps, although note the conspicuous lack of operator[]
which encourages non thread-safe access patterns.

Below is a synchronized key counter implementation that allows the counter
values to be incremented in parallel with serializing all the values to a
string.

class Counters {
    private:
     AtomicHashMap ahm;

    public:
     explicit Counters(size_t numCounters) : ahm(numCounters) {}

     void increment(int64_t obj_id) {
       auto ret = ahm.insert(make_pair(obj_id, 1));
       if (!ret.second) {
         // obj_id already exists, increment
         NoBarrier_AtomicIncrement(&ret.first->second, 1);
       }
     }

     int64_t getValue(int64_t obj_id) {
       auto ret = ahm.find(obj_id);
       return ret != ahm.end() ? ret->second : 0;
     }

     // Serialize the counters without blocking increments
     string toString() {
       string ret = "{\n";
       ret.reserve(ahm.size() * 32);
       for (const auto& e : ahm) {
         ret += folly::to<string>(
           "  [", e.first, ":", NoBarrier_Load(&e.second), "]\n");
       }
       ret += "}\n";
       return ret;
     }
   };

Implementation Copy Section

AtomicHashMap is a composition of AtomicHashArray submaps, which implement the
meat of the functionality. Only one AHA is created on initialization, and
additional submaps are appended if the first one gets full. If the AHM grows,
there will be multiple submaps that must be probed in series to find a given
key. The more growth, the more submaps will be chained, and the slower it will
get. If the initial size estimate is good, only one submap will ever be created
and performance will be optimal.

AtomicHashArray is a fixed-size probing hash map (also referred to as an open
addressed hash map) where hash collisions are resolved by checking subsequent
elements. This means that they can be allocated in slabs as arrays of
value_type elements, have excellent cache performance, and have no memory
overhead from storing pointers.

The algorithm is simple - when inserting, the key is hash-mod'ed to an offset,
and that element-key is atomically compare-and-swap'ed with the locked key
value. If successful, the value is written and the element-key is unlocked by
setting it to the input key value. If the compare fails, the next element is
tried until success or the map is full.

Finds are even simpler. The key is hash-mod'ed to an offset, and the
element-key is examined. If it is the same as the input key, the reference is
returned, if it's the empty key, failure is returned, otherwise the next key is
tried. This can be done wait-free without any atomic instructions because the
elements are always in a valid state.

Erase is done by finding the key, then compare-and-swap'ing the element-key with
the reserved erased key value. If the swap succeeds, return success, otherwise
return failure (the element was erased by a competing thread). If the key does
not exist, return failure.

File: folly/docs/Benchmark.md Copy Chapter

`folly/Benchmark.h` Copy Chapter

folly/Benchmark.h provides a simple framework for writing and
executing benchmarks. Currently the framework targets only
single-threaded testing (though you can internally use fork-join
parallelism and measure total run time).

Also read docs/BenchmarkAdaptive.md, which describes--bm_mode=adaptive, an
easier & quicker way to get reliable timings for your BENCHMARKs.

Overview Copy Section

Using folly/Benchmark.h is very simple. Here's an example:

#include <folly/Benchmark.h>
    #include <vector>
    using namespace std;
    using namespace folly;
    BENCHMARK(insertFrontVector) {
      // Let's insert 100 elements at the front of a vector
      vector v;
      for (unsigned int i = 0; i < 100; ++i) {
        v.insert(v.begin(), i);
      }
    }
    BENCHMARK(insertBackVector) {
      // Let's insert 100 elements at the back of a vector
      vector v;
      for (unsigned int i = 0; i < 100; ++i) {
        v.insert(v.end(), i);
      }
    }
    int main() {
      runBenchmarks();
    }

Compiling and running this code produces to the standard output:

===============================================================================
    test.cpp                                              relative ns/iter  iters/s
    ===============================================================================
    insertFrontVector                                                3.84K  260.38K
    insertBackVector                                                 1.61K  622.75K
    ===============================================================================

Let's worry about the empty column "relative" later. The table
contains, for each benchmark, the time spent per call and the converse
number of calls per second. Numbers are represented in metric notation
(K for thousands, M for millions etc). As expected, in this example
the second function is much faster (fewer ns/iter and more iters/s).

The macro BENCHMARK introduces a function and also adds it to an
internal array containing all benchmarks in the system. The defined
function takes no arguments and returns void.

The framework calls the function many times to collect statistics
about it. Sometimes the function itself would want to do that
iteration---for example how about inserting n elements instead of
100 elements? To do the iteration internally, use BENCHMARK with two
parameters. The second parameter is the number of iterations and is
passed by the framework down to the function. The type of the count is
implicitly unsigned. Consider a slightly reworked example:

#include <folly/Benchmark.h>
    #include <folly/container/Foreach.h>
    #include <vector>
    using namespace std;
    using namespace folly;
    BENCHMARK(insertFrontVector, n) {
      vector v;
      for (unsigned int i = 0; i < n; ++i) {
        v.insert(v.begin(), i);
      }
    }
    BENCHMARK(insertBackVector, n) {
      vector v;
      for (unsigned int i = 0; i < n; ++i) {
        v.insert(v.end(), i);
      }
    }
    int main() {
      runBenchmarks();
    }

The produced numbers are substantially different:

===============================================================================
    Benchmark                                             relative ns/iter  iters/s
    ===============================================================================
    insertFrontVector                                               39.92    25.05M
    insertBackVector                                                 3.46   288.89M
    ===============================================================================

Now the numbers indicate the speed of one single insertion because the
framework assumed the user-defined function used internal iteration
(which it does). So inserting at the back of a vector is more than 10
times faster than inserting at the front! Speaking of comparisons...

Baselines Copy Section

Choosing one or more good baselines is a crucial activity in any
measurement. Without a baseline there is little information to derive
from the sheer numbers. If, for example, you do experimentation with
algorithms, a good baseline is often an established approach (e.g. the
built-in std::sort for sorting). Essentially all experimental
numbers should be compared against some baseline.

To support baseline-driven measurements, folly/Benchmark.h defines
BENCHMARK_RELATIVE, which works much like BENCHMARK, except it
considers the most recent lexically-occurring BENCHMARK a baseline,
and fills the "relative" column. Say, for example, we want to use
front insertion for a vector as a baseline and see how back insertion
compares with it:

#include <folly/Benchmark.h>
    #include <folly/container/Foreach.h>
    #include <vector>
    using namespace std;
    using namespace folly;
    BENCHMARK(insertFrontVector, n) {
      vector v;
      for (unsigned int i = 0; i < n; ++i) {
        v.insert(v.begin(), i);
      }
    }
    BENCHMARK_RELATIVE(insertBackVector, n) {
      vector v;
      for (unsigned int i = 0; i < n; ++i) {
        v.insert(v.end(), i);
      }
    }
    int main() {
      runBenchmarks();
    }

This program prints something like:

===============================================================================
    Benchmark                                             relative ns/iter  iters/s
    ===============================================================================
    insertFrontVector                                               42.65    23.45M
    insertBackVector                                     1208.24%    3.53   283.30M
    ===============================================================================

showing the 1208.24% relative speed advantage of inserting at the back
compared to front. The scale is chosen in such a way that 100% means
identical speed, numbers smaller than 100% indicate the benchmark is
slower than the baseline, and numbers greater than 100% indicate the
benchmark is faster. For example, if you see 42% that means the speed
of the benchmark is 0.42 of the baseline speed. If you see 123%, it
means the benchmark is 23% or 1.23 times faster.

To close the current benchmark group and start another, simply use
BENCHMARK again.

Ars Gratia Artis Copy Section

If you want to draw a horizontal line of dashes (e.g. at the end of a
group or for whatever reason), use BENCHMARK_DRAW_LINE(). The line
fulfills a purely aesthetic role; it doesn't interact with
measurements in any way.

BENCHMARK(foo) {
      Foo foo;
      foo.doSomething();
    }

    BENCHMARK_DRAW_LINE();

    BENCHMARK(bar) {
      Bar bar;
      bar.doSomething();
    }

If you want to print arbitrary text (e.g. a comment or for whatever
reason), use BENCHMARK_DRAW_TEXT("your text here"). The output will
be the literal value so escape codes like \n or \t will not work.
To add multiple lines of output use multiple BENCHMARK_DRAW_TEXT
calls.

BENCHMARK(foo) {
      Foo foo;
      foo.doSomething();
    }

    BENCHMARK_DRAW_TEXT("Note: bar is expected to be 2x more expensive.");

    BENCHMARK(bar) {
      Bar bar;
      bar.doSomething();
    }

Suspending a benchmark Copy Section

Sometimes benchmarking code must do some preparation work that is
physically inside the benchmark function, but should not take part to
its time budget. To temporarily suspend the benchmark, use the
pseudo-statement BENCHMARK_SUSPEND as follows:

BENCHMARK(insertBackVector, n) {
      vector v;
      BENCHMARK_SUSPEND {
        v.reserve(n);
      }
      for (unsigned int i = 0; i < n; ++i) {
        v.insert(v.end(), i);
      }
    }

The preallocation effected with v.reserve(n) will not count toward
the total run time of the benchmark.

Only the main thread should call BENCHMARK_SUSPEND (and of course it
should not call it while other threads are doing actual work). This is
because the timer is application-global.

If the scope introduced by BENCHMARK_SUSPEND is not desired, you may
want to "manually" use the BenchmarkSuspender type. Constructing
such an object suspends time measurement, and destroying it resumes
the measurement. If you want to resume time measurement before the
destructor, call dismiss against the BenchmarkSuspender
object. The previous example could have been written like this:

BENCHMARK(insertBackVector, n) {
      BenchmarkSuspender braces;
      vector v;
      v.reserve(n);
      braces.dismiss();
      for (unsigned int i = 0; i < n; ++i) {
        v.insert(v.end(), i);
      }
    }

`doNotOptimizeAway` Copy Section

Finally, the small utility function doNotOptimizeAway prevents
compiler optimizations that may interfere with benchmarking . Call
doNotOptimizeAway(var) against variables that you use for
benchmarking but otherwise are useless. The compiler tends to do a
good job at eliminating unused variables, and this function fools it
into thinking a variable is in fact needed. Example:

BENCHMARK(fpOps, n) {
      double d = 1;
      FOR_EACH_RANGE (i, 1, n) {
        d += i;
        d -= i;
        d *= i;
        d /= i;
      }
      doNotOptimizeAway(d);
    }

A look under the hood Copy Section

folly/Benchmark.h has a simple, systematic approach to collecting
timings.

First, it organizes measurements in several large epochs, and takes
the minimum over all epochs. Taking the minimum gives the closest
result to the real runtime. Benchmark timings are not a regular random
variable that fluctuates around an average. Instead, the real time
we're looking for is one to which there's a variety of additive noise
(i.e. there is no noise that could actually shorten the benchmark time
below its real value). In theory, taking an infinite amount of samples
and keeping the minimum is the actual time that needs
measuring. That's why the accuracy of benchmarking increases with the
number of epochs.

Clearly, in real functioning there will also be noise and a variety of
effects caused by the running context. But the noise during the
benchmark (straight setup, simple looping) is a poor model for the
noise in the real application. So taking the minimum across several
epochs is the most informative result.

Inside each epoch, the function measured is iterated an increasing
number of times until the total runtime is large enough to make noise
negligible. At that point the time is collected, and the time per
iteration is computed. As mentioned, the minimum time per iteration
over all epochs is the final result.

The timer function used is clock_gettime with the CLOCK_REALTIME
clock id. Note that you must use a recent Linux kernel (2.6.38 or
newer), otherwise the resolution of CLOCK_REALTIME is inadequate.

File: folly/docs/Conv.md Copy Chapter

`folly/Conv.h` Copy Chapter

folly/Conv.h is a one-stop-shop for converting values across
types. Its main features are simplicity of the API (only the
names to and toAppend must be memorized), speed
(folly is significantly faster, sometimes by an order of magnitude,
than comparable APIs), and correctness.

Synopsis Copy Section

All examples below are assume to have included folly/Conv.h
and issued using namespace folly; You will need:

// To format as text and append to a string, use toAppend.
    fbstring str;
    toAppend(2.5, &str);
    CHECK_EQ(str, "2.5");

    // Multiple arguments are okay, too. Just put the pointer to string at the end.
    toAppend(" is ", 2, " point ", 5, &str);
    CHECK_EQ(str, "2.5 is 2 point 5");

    // You don't need to use fbstring (although it's much faster for conversions and in general).
    std::string stdStr;
    toAppend("Pi is about ", 22.0 / 7, &stdStr);
    // In general, just use to<TargetType>(sourceValue). It returns its result by value.
    stdStr = to<std::string>("Variadic ", "arguments also accepted.");

    // to<fbstring> is 2.5x faster than to<std::string> for typical workloads.
    str = to<fbstring>("Variadic ", "arguments also accepted.");

Integral-to-integral conversion Copy Section

Using to<Target>(value) to convert one integral type to another
will behave as follows:

• If the target type can accommodate all possible values of the
  source value, the value is implicitly converted. No further
  action is taken. Example:

short x;
        unsigned short y;
        ...
        auto a = to(x); // zero overhead conversion
        auto b = to(y); // zero overhead conversion

• Otherwise, to inserts bounds checks and throws
  std::range_error if the target type cannot accommodate the
  source value. Example:

short x;
    unsigned short y;
    long z;
    ...
    x = 123;
    auto a = to(x); // fine
    x = -1;
    a = to(x); // THROWS
    z = 2000000000;
    auto b = to(z); // fine
    z += 1000000000;
    b = to(z); // THROWS
    auto b = to(z); // fine

Anything-to-string conversion Copy Section

As mentioned, there are two primitives for converting anything to
string: to and toAppend. They support the same set of source
types, literally by definition (to is implemented in terms of
toAppend for all types). The call toAppend(value, &str)
formats and appends value to str whereas
to<StringType>(value) formats value as a StringType and
returns the result by value. Currently, the supported
StringTypes are std::string and fbstring

Both toAppend and to with a string type as a target support
variadic arguments. Each argument is converted in turn. For
toAppend the last argument in a variadic list must be the
address of a supported string type (no need to specify the string
type as a template argument).

Integral-to-string conversion

Nothing special here - integrals are converted to strings in
decimal format, with a '-' prefix for negative values. Example:

auto a = to<fbstring>(123);
    assert(a == "123");
    a = to<fbstring>(-456);
    assert(a == "-456");

The conversion implementation is aggressively optimized. It
converts two digits at a time assisted by fixed-size tables.
Converting a long to an fbstring is 3.6x faster than using
boost::lexical_cast and 2.5x faster than using sprintf even
though the latter is used in conjunction with a stack-allocated
constant-size buffer.

Note that converting integral types to fbstring has a
particular advantage compared to converting to std::string
No integral type (<= 64 bits) has more than 20 decimal digits
including sign. Since fbstring employs the small string
optimization for up to 23 characters, converting an integral
to fbstring is guaranteed to not allocate memory, resulting
in significant speed and memory locality gains. Benchmarks
reveal a 2x gain on a typical workload.

`char` to string conversion

Although char is technically an integral type, most of the time
you want the string representation of 'a' to be "a", not 96
That's why folly/Conv.h handles char as a special case that
does the expected thing. Note that signed char and unsigned char are still considered integral types.

Floating point to string conversion

folly/Conv.h uses V8's double conversion
routines. They are accurate and fast; on typical workloads,
to<fbstring>(doubleValue) is 1.9x faster than sprintf and
5.5x faster than boost::lexical_cast (It is also 1.3x faster
than to<std::string>(doubleValue)

`const char*` to string conversion

For completeness, folly/Conv.h supports const char* including
i.e. string literals. The "conversion" consists, of course, of
the string itself. Example:

auto s = to<fbstring>("Hello, world");
    assert(s == "Hello, world");

Anything from string conversion (i.e. parsing)

folly/Conv.h includes three kinds of parsing routines:

• to<Type>(const char* begin, const char* end) rigidly
  converts the range [begin, end) to Type These routines have
  drastic restrictions (e.g. allow no leading or trailing
  whitespace) and are intended as an efficient back-end for more
  tolerant routines.
• to<Type>(stringy) converts stringy to Type Value
  stringy may be of type const char*, StringPiece,
  std::string, or fbstring (Technically, the requirement is
  that stringy implicitly converts to a StringPiece
• to<Type>(&stringPiece) parses with progress information:
  given stringPiece of type StringPiece it parses as much
  as possible from it as type Type and alters stringPiece
  to remove the munched characters. This is easiest clarified
  by an example:

fbstring s = " 1234 angels on a pin";
    StringPiece pc(s);
    auto x = to(&pc);
    assert(x == 1234);
    assert(pc == " angels on a pin";

Note how the routine ate the leading space but not the trailing one.

Parsing integral types

Parsing integral types is unremarkable - decimal format is
expected, optional '+' or '-' sign for signed types, but no
optional '+' is allowed for unsigned types. The one remarkable
element is speed - parsing typical long values is 6x faster than
sscanf. folly/Conv.h uses aggressive loop unrolling and
table-assisted SIMD-style code arrangement that avoids integral
division (slow) and data dependencies across operations
(ILP-unfriendly). Example:

fbstring str = "  12345  ";
    assert(to(str) == 12345);
    str = "  12345six seven eight";
    StringPiece pc(str);
    assert(to(&pc) == 12345);
    assert(str == "six seven eight");

Parsing floating-point types

folly/Conv.h uses, again, V8's double-conversion
routines as back-end. The speed is 3x faster than sscanf and
1.7x faster than in-home routines such as parse<double> But
the more important detail is accuracy - even if you do code a
routine that works faster than to<double> chances are it is
incorrect and will fail in a variety of corner cases. Using
to<double> is strongly recommended.

Note that if the string "NaN" (with any capitalization) is passed to
to<double> then NaN is returned, which can be tested for as follows:

fbstring str = "nan"; // "NaN", "NAN", etc.
    double d = to<double>(str);
    if (std::isnan(d)) {
      // string was a valid representation of the double value NaN
    }

Note that passing "-NaN" (with any capitalization) to to<double> also returns
NaN.

Note that if the strings "inf" or "infinity" (with any capitalization) are
passed to to<double> then infinity is returned, which can be tested for
as follows:

fbstring str = "inf"; // "Inf", "INF", "infinity", "Infinity", etc.
    double d = to<double>(str);
    if (std::isinf(d)) {
      // string was a valid representation of one of the double values +Infinity
      // or -Infinity
    }

Note that passing "-inf" or "-infinity" (with any capitalization) to
to<double> returns -infinity rather than +infinity. The sign of the
infinity can be tested for as follows:

fbstring str = "-inf"; // or "inf", "-Infinity", "+Infinity", etc.
    double d = to<double>(str);
    if (d == std::numeric_limits<double>::infinity()) {
      // string was a valid representation of the double value +Infinity
    } else if (d == -std::numeric_limits<double>::infinity()) {
      // string was a valid representation of the double value -Infinity
    }

Note that if an unparseable string is passed to to<double> then an exception
is thrown, rather than NaN being returned. This can be tested for as follows:

fbstring str = "not-a-double"; // Or "1.1.1", "", "$500.00", etc.
    double d;
    try {
      d = to<double>(str);
    } catch (const std::range_error &) {
      // string could not be parsed
    }

Note that the empty string ("") is an unparseable value, and will cause
to<double> to throw an exception.

Non-throwing interfaces

tryTo<T> is the non-throwing variant of to<T>. It returns
an Expected<T, ConversionCode>. You can think of Expected
as like an Optional<T>, but if the conversion failed, Expected
stores an error code instead of a T.

tryTo<T> has similar performance as to<T> when the
conversion is successful. On the error path, you can expect
tryTo<T> to be roughly three orders of magnitude faster than
the throwing to<T> and to completely avoid any lock contention
arising from stack unwinding.

Here is how to use non-throwing conversions:

auto t1 = tryTo(str);
    if (t1.hasValue()) {
      use(t1.value());
    }

Expected has a composability feature to make the above pattern simpler.

tryTo(str).then([](int i) { use(i); });

File: folly/docs/Dynamic.md Copy Chapter

`folly/dynamic.h` Copy Chapter

folly/dynamic.h provides a runtime dynamically typed value for
C++, similar to the way languages with runtime type systems work
(e.g. Python). It can hold types from a predetermined set of types
(ints, bools, arrays of other dynamics, etc), similar to something like
std::variant, but the syntax is intended to be a little more like
using the native type directly.

Overview Copy Section

Here are some code samples to get started (assumes a using folly::dynamic; was used):

dynamic twelve = 12; // creates a dynamic that holds an integer
    dynamic str = "string"; // yep, this one is an fbstring

    // A few other types.
    dynamic nul = nullptr;
    dynamic boolean = false;

    // Arrays can be initialized with dynamic::array.
    dynamic array = dynamic::array("array ", "of ", 4, " elements");
    assert(array.size() == 4);
    dynamic emptyArray = dynamic::array;
    assert(emptyArray.empty());

    // Maps from dynamics to dynamics are called objects.  The
    // dynamic::object constant is how you make an empty map from dynamics
    // to dynamics.
    dynamic map = dynamic::object;
    map["something"] = 12;
    map["another_something"] = map["something"] * 2;

    // Dynamic objects may be initialized this way
    dynamic map2 = dynamic::object("something", 12)("another_something", 24);

Runtime Type Checking and Conversions Copy Section

Any operation on a dynamic requires checking at runtime that the
type is compatible with the operation. If it isn't, you'll get a
folly::TypeError. Other exceptions can also be thrown if
you try to do something impossible (e.g. if you put a very large
64-bit integer in and try to read it out as a double).

More examples should hopefully clarify this:

dynamic dint = 42;

    dynamic str = "foo";
    dynamic anotherStr = str + "something"; // fine
    dynamic thisThrows = str + dint; // TypeError is raised

Explicit type conversions can be requested for some of the basic types:

dynamic dint = 12345678;
    dynamic doub = dint.asDouble(); // doub will hold 12345678.0
    dynamic str = dint.asString(); // str == "12345678"

    dynamic hugeInt = std::numeric_limits::max();
    dynamic hugeDoub = hugeInt.asDouble();  // throws a folly/Conv.h error,
                                            // since it can't fit in a double

For more complicated conversions, see DynamicConverter.

Comparison Operators and Hashing Copy Section

Equality Operators

Equality operators (==, !=) are supported for all types.

For dynamics of the same type, the underlying equality operator shall apply.

For comparisons between different numeric types (double and int64), numeric
equality will apply - thus 2.0 == 2.

Values of any other different types will be deemed to not be equal.

Ordering operators

Ordering operators (<, <=, >, >=) are supported for all types, except
dynamic::object which will throw if it is involved in an ordering operator.

For dynamics of the same type, the underlying ordering operator shall apply.

For comparisons between different numeric types (double and int64), numeric
ordering will apply - thus 1.5 < 2.

Ordering of values between other different types will maintain total ordering
properties and be consistent within a given binary run, and thus safe for use in
e.g. std::set. The actual ordering is undefined and could change across
versions, thus a dependency should not be taken outside of the total ordering
property within a given binary.

Hashing

Hashing is supported by all types, and the hashes of two values will match if
they are equal per dynamic::operator==.

As a result, numerical types have the same numerical hashing regardless of int64
vs double - so e.g. std::hash<dynamic>()(2) will give the same value as
std::hash<dynamic>()(2.0).

Iteration and Lookup Copy Section

You can iterate over dynamic arrays as you would over any C++ sequence container.

dynamic array = dynamic::array(2, 3, "foo");

    for (auto& val : array) {
      doSomethingWith(val);
    }

You can iterate over dynamic maps by calling items(), keys(),
values(), which behave similarly to the homonymous methods of Python
dictionaries.

dynamic obj = dynamic::object(2, 3)("hello", "world")("x", 4);

    for (auto& pair : obj.items()) {
      // Key is pair.first, value is pair.second
      processKey(pair.first);
      processValue(pair.second);
    }

    for (auto& key : obj.keys()) {
      processKey(key);
    }

    for (auto& value : obj.values()) {
      processValue(value);
    }

You can find an element by key in a dynamic map using the find() method,
which returns an iterator compatible with items():

dynamic obj = dynamic::object(2, 3)("hello", "world")("x", 4);

    auto pos = obj.find("hello");
    // pos->first is "hello"
    // pos->second is "world"

    auto pos = obj.find("no_such_key");
    // pos == obj.items().end()

Erasure Copy Section

You can erase elements from dynamic arrays by calling member dynamic::erase,
which works like and has overloads like std::vector::erase, and from dynamic
objects by calling member dynamic::erase, which works like and has overloads
like std::unordered_map::erase. You can also find and erase elements from
dynamic arrays by calling free function erase, and from dynamic arrays or
objects by calling free function erase_if, which work and have overloads
like erase(std::vector), erase_if(std::vector), and
erase_if(std::unordered_map).

https://en.cppreference.com/w/cpp/container/vector/erase2
https://en.cppreference.com/w/cpp/container/unordered_map/erase_if.html

Use for JSON Copy Section

The original motivation for implementing this type was to try to
make dealing with json documents in C++ almost as easy as it is
in languages with dynamic type systems (php or javascript, etc).
The reader can judge whether we're anywhere near that goal, but
here's what it looks like:

// Parsing JSON strings and using them.
    std::string jsonDocument = R"({"key":12,"key2":[false, null, true, "yay"]})";
    dynamic parsed = folly::parseJson(jsonDocument);
    assert(parsed["key"] == 12);
    assert(parsed["key2"][0] == false);
    assert(parsed["key2"][1] == nullptr);

    // Building the same document programmatically.
    dynamic sonOfAJ = dynamic::object
      ("key", 12)
      ("key2", dynamic::array(false, nullptr, true, "yay"));

    // Printing.  (See also folly::toPrettyJson)
    auto str = folly::toJson(sonOfAJ);
    assert(jsonDocument.compare(str) == 0);

Performance Copy Section

Dynamic typing is more expensive than static typing, even when
you do it in C++. ;)

However, some effort has been made to keep folly::dynamic and
the json (de)serialization at least reasonably performant for
common cases. The heap is only used for arrays and objects, and
move construction is fully supported. String formatting
internally also uses the highly performant folly::to<> (see
folly/Conv.h).

A trade off to keep in mind though, is that
sizeof(folly::dynamic) is 64 bytes. You probably don't want to
use it if you need to allocate large numbers of them (prefer
static types, etc).

Some Design Rationale Copy Section

Q. Why doesn't a dynamic string support begin(), end(), and operator[]?

The value_type of a dynamic iterator is dynamic, and operator[]
(or the at() function) has to return a reference to a dynamic. If
we wanted this to work for strings, this would mean we'd have to
support dynamics with a character type, and moreover that the internal
representation of strings would be such that we can hand out
references to dynamic as accessors on individual characters. There
are a lot of potential efficiency drawbacks with this, and it seems
like a feature that is not needed too often in practice.

Q. Isn't this just a poor imitation of the C# language feature?

Pretty much.

File: folly/docs/DynamicConverter.md Copy Chapter

`folly/DynamicConverter.h` Copy Chapter

When dynamic objects contain data of a known type, it is sometimes
useful to have its well-typed representation. A broad set of
type-conversions are contained in DynamicConverter.h, and
facilitate the transformation of dynamic objects into their well-typed
format.

Usage Copy Section

Simply pass a dynamic into a templated convertTo:

dynamic d = { { 1, 2, 3 }, { 4, 5 } }; // a vector of vector of int
    auto vvi = convertTo<fbvector<fbvector>>(d);

Supported Types Copy Section

convertTo naturally supports conversions to

1. arithmetic types (such as int64_t, unsigned short, bool, and double)
2. fbstring, std::string
3. containers and map-containers

NOTE:

convertTo will assume that Type is a container if

• it has a Type::value_type, and
• it has a Type::iterator, and
• it has a constructor that accepts two InputIterators

Additionally, convertTo will assume that Type is a map if

• it has a Type::key_type, and
• it has a Type::mapped_type, and
• value_type is a pair of const key_type and mapped_type

If Type meets the container criteria, then it will be constructed
by calling its InputIterator constructor.

Customization Copy Section

If you want to use convertTo to convert dynamics into your own custom
class, then all you have to do is provide a template specialization
of DynamicConverter with the static method convert. Make sure you put it
in namespace folly.

Example:

struct Token {
      int kind_;
      fbstring lexeme_;
      
      explicit Token(int kind, const fbstring& lexeme)
        : kind_(kind), lexeme_(lexeme) {}
    };
    namespace folly {
    template <> struct DynamicConverter<Token> {
      static Token convert(const dynamic& d) {
        int k = convertTo(d["KIND"]);
        fbstring lex = convertTo<fbstring>(d["LEXEME"]);
        return Token(k, lex);
      }
    };
    }