Summary:
This diff extends heterogeneous key handling (when the hasher and
key equality functor are transparent) to mutating operations.  If a key
of type K was previously eligible for heterogeneous find and key_type can
be constructed from the key, then that construction can be deferred until
after it is verified that the key is not previously in the table when
using any of the operations that may insert a new element.  If the key was
already present then this avoids the construction of key_type entirely.
Heterogeneous erase is also added in the obvious fashion.

Construction of key_type from K can be accomplished without key_type's
cooperation by the use of an explicit conversion operator, such as the
explicit operator std::string recently added to StringPiece.  That means
that a F14 map or set with std::string key and transparent StringPiece
hash and equality can now use StringPiece natively as a key.

Destructuring is applied whenever possible, so the heterogeneous key
type K may be found as the first element of a pair (for map insert or
emplace) or even inside the first tuple when using map emplace with
std::piecewise_construct.

This diff adds heterogeneous key support to

    Map::insert
    Map::insert_or_assign
    Map::emplace
    Map::try_emplace
    Map::operator[]
    Set::insert
    Set::emplace

Reviewed By: yfeldblum

Differential Revision: D8301887

fbshipit-source-id: 1a45e13739c550f094afe09123839a3c9cd892ff

Summary:
[Folly] In Futures Core, destroy context when destroying callback since they basically go together.

Also removes expectations in an Eden FS test case which affirm the old behavior, along with a TODO to remove the expectations once the affirmed behavior is fixed.

Reviewed By: marshallcline

Differential Revision: D8347040

fbshipit-source-id: ed9fec932ad1e0aa1e40675cf70081d19bbe4325

Summary:
[Folly] Use a simpler atomic state in Futures `Core` v.s. `FSM` which abstracts an atomic state plus a spin-lock.

The `FSM` abstraction can be useful in more complex cases, but is not needed in the current case. All that is needed is a single barrier state, which is `Done` - setting callback and result happen before state transitions to `Done`, while invoking callback with result happens after state transitions to `Done`.

Reviewed By: marshallcline

Differential Revision: D8083703

fbshipit-source-id: 42d96b41cbdac5e7c42f3f8a661d5db3113655db

Summary:
[Folly] Use `terminate_with` in Futures `Core` invalid transitions.

Both `Promise` and `Future` check state validity before calling the `Core` transition methods and throws in invalid state. So `Core` no longer needs to throw and may terminate instead.

Reviewed By: marshallcline

Differential Revision: D8346113

fbshipit-source-id: 9ff158673149096789b29544453262797b06d441

Summary: [Folly] `folly::terminate_with`, to terminate as if by forwarding to `folly::throw_exception` but in a `noexcept` context.

Reviewed By: marshallcline

Differential Revision: D8345962

fbshipit-source-id: bc5cf5d3a3e1f085dd2989c940a6ea753a520cbf

Summary:
[Folly] Let Future check before adding a continuation whether a continuation has already been added.

Requires making wait behave more like timed-wait; alternatively, it would be possible to add a reverse state transition, but there seems not to be a need.

Reviewed By: marshallcline

Differential Revision: D8344923

fbshipit-source-id: f077fb4b83b92c96af9a83e1b1479c4cb41b048a

Summary:
[Folly] `Range` explicit conversion to any target type, with overloads enabled only for target types which are explicitly constructible from two iterators.

Also changes `Range::to` to do similar, but permits additional arguments to be forwarded as trailing arguments to the target type constructor.

For example, this makes `std::string`, `folly::fbstring`, `std::vector<char>`, and all variants with default-constructible custom allocators, to be constructible from (but not convertible from) `folly::StringPiece`.

Reviewed By: nbronson

Differential Revision: D8386240

fbshipit-source-id: 2426191d1c8ac71cd5832f784e83bbe09b8716e7

Summary:
There were two TODOs that I knew of in fbcode about this, so I decided to file
a task so we can track it.

Reviewed By: simpkins

Differential Revision: D8176921

fbshipit-source-id: 0ca45620050639659ac038dbed43acf4634f7a1d

Summary:
Added `FutureBase::delayedImplementation`. Kept the existing semantics of
`Future::delayed` and `Future::delayedUnsafe`. `SemiFuture::delayed` uses
the inline executor which means we could execute our trivial lambda on
the `Timekeeper` thread. However we ultimately return a `SemiFuture`,
so we're not necessarily on the hook to execute an arbitrarily complex
continuation.

NOTE: This is still possible if the user explicitly specifies
`.via(inline_executor)`. Perhaps we should consider disallowing, or maybe linting for this.

Reviewed By: yfeldblum

Differential Revision: D8372515

fbshipit-source-id: e660dbf2a2bb084e11c5e57d1badacf09425f939

Summary:
To implement tdigest aggregation in scuba, we need to be able to deserialize and serialize the digests.
I added a getter for the centroids so that we can serialize the tdigest, and added a constructor to create one from the list of centroids.

Last diff was reverted because of a build error :(
We were seeing an error only in opt mode because it's an error in gcc but not in clang.

Differential Revision: D8381617

fbshipit-source-id: 768a12795aeb02737eb9b060f80d01608685c91d

Summary: title

Reviewed By: yfeldblum, andriigrynenko

Differential Revision: D8386575

fbshipit-source-id: c900c8692b10004f2d9fbd95fa8ca96b3b8517d2

Summary:
[Folly] Skip trivial-copyability `Expected` expectations under gcc49.

The focus is on gcc5+; all that is needed for now is to keep code compiling with gcc49, but not necessarily to ensure optimal trivial-copyability behavior.

Reviewed By: Orvid

Differential Revision: D8364392

fbshipit-source-id: b0062193c844509b6bf26ed632dd8e5d4bdf77d2

Summary: Assume, when UBSAN is used, it is always used on top of ASAN.

Reviewed By: luciang

Differential Revision: D8360231

fbshipit-source-id: 3106cfa53567b18f199e9303ea4c14a464ff03cc

Summary: Makes a spec for libsodium.

Reviewed By: knekritz

Differential Revision: D8228801

fbshipit-source-id: 18f623bce0bbc07f711129b15b78d56b6c852bf7

Summary: [Folly] A cache for `InlineExecutor` singleton, which can be inlined into callers with little extra code compared to calling the backing function directly.

Reviewed By: marshallcline

Differential Revision: D8339793

fbshipit-source-id: d2be0128e617cfefe66809eb44ce40e1a8ae2dfb

Summary: [Folly] Write `Promise::setException` in terms of `Promise::setTry`.

Reviewed By: marshallcline

Differential Revision: D8344928

fbshipit-source-id: 90e21219f054329eca7ae1a6c2ca731a16328b6f

Revert D8360404: [folly] Support constructing TDigest from centroids and getting centroids from TDigest

Differential Revision:
D8360404

Original commit changeset: b0f42e892f66

fbshipit-source-id: 985ba55bb443aafe7c324f15caeca0abb34d200a

Summary: Before this diff, since `ctx->memo_` starts out in the `OnlyResult` state, the first reduce (and therefore all subsequent reduces) are run immediately inside the lock.

Reviewed By: yfeldblum

Differential Revision: D8319067

fbshipit-source-id: 5ed08885beefb42c6efb61768fcbc36e0a08a46b

Summary:
To implement tdigest aggregation in scuba, we need to be able to deserialize and serialize the digests.
I added a getter for the centroids so that we can serialize the tdigest, and added a constructor to create one from the list of centroids.

Differential Revision: D8360404

fbshipit-source-id: b0f42e892f666e787e06198c7e8ff65dd8799dcc

Summary:
In folly::small_vector, we were (mistakenly) relying on a default constructor
for non-trivially constructible types.

The problem got worse on gcc 4.9, because for that compiler version, we set
folly::is_trivially_copyable to be std::is_trivial. This is mostly okay, as
std::is_trivial implies std::is_trivially_copyable. The problem is that
std::is_trivial also implies std::is_default_constructuble, which which was
breaking folly::small_vector

Reviewed By: yfeldblum

Differential Revision: D8346780

fbshipit-source-id: 9c8a9dab21ea2d4fd34f636458324915c30e10a2

Summary:
See https://gitlab.kitware.com/cmake/cmake/issues/16686

This patch was originally contributed to MacPorts by mohd-akram in https://github.com/macports/macports-ports/pull/1933.
Closes https://github.com/facebook/folly/pull/862

Reviewed By: Orvid

Differential Revision: D8346974

Pulled By: yfeldblum

fbshipit-source-id: 2673e1f414dd86bf91bb2183c2f6d9f7e72251f8

Summary:
[Folly] A shorter name for executor local variable in `Future` methods. Reads more nicely, with less awkward formatting.

When the scope of a local variable's use is just a few lines, long names are not quite so critical.

Reviewed By: marshallcline

Differential Revision: D8339451

fbshipit-source-id: 5d50cf0ce3473c1a79afeeddb9e1257cccf73e31

Summary: [Folly] No need for qualifying `InlineExecutor` in `Futures` - they are both in `namespace folly` already.

Reviewed By: marshallcline

Differential Revision: D8307058

fbshipit-source-id: 17a0ecde1e57f1c0c88cbac09bbd1bb3daf7a24e

Summary:
[Folly] Use `InlineExecutor` singleton in `Future` wait v.s. letting the executor be `nullptr`.

The effect is the same, but just more explicit.

Reviewed By: marshallcline

Differential Revision: D8306902

fbshipit-source-id: fc90704de670b1ca9956253383fadad3be297847

Summary:
Executor adaptor which allows joining only tasks scheduled through this VirtualExecutor instance without joining all other tasks in a wrapped Executor.
This is very similar to VirtualEventBase, but works for any Executor.

Reviewed By: yfeldblum, aary

Differential Revision: D8342064

fbshipit-source-id: 420b6390e2da88c4826e6d22bc8f3b3585525214

Summary: [Folly] Ensure sleep duration in logging `RateLimiter` test to make sure that there is no chance of waking up from the sleep too early.

Reviewed By: Orvid

Differential Revision: D8330018

fbshipit-source-id: f1222e1da50f8360267f9e1c5e0f24897b7b8f47

Reviewed By: shixiao

Differential Revision: D8333485

fbshipit-source-id: 02f74700272b663474c2f02535265ffb6f4bcd22

Summary:
method-level contracts

(Note: this ignores all push blocking failures!)

Reviewed By: yfeldblum

Differential Revision: D8132350

fbshipit-source-id: d79b1d88a38ea97de8d0e841e822805aff3959ae

Summary:
fbthrift needs to link against newer version of krb5 library to avoid linking
issue during OpenR build.

```
libsecurity.so: undefined reference to `error_message(long)'
```

Reviewed By: yfeldblum

Differential Revision: D8330387

fbshipit-source-id: 34f3f7361c99bb38adf558a52ef05e9d3156640d

Summary:
Make the interface consistent with the other queue algorithms.
push
try_push
try_push_for
try_push_until
pop
try_pop
try_pop_for
try_pop_until
peek
try_peek
try_peek_for
try_peek_until

Reviewed By: yfeldblum, djwatson

Differential Revision: D8262170

fbshipit-source-id: 0299e947a0069eacafd1315c920ec6e1b36675f3

Summary: Weak reference can be used if it's ok for some tasks to be dropped when Executor is destroyed.

Reviewed By: yfeldblum

Differential Revision: D8309958

fbshipit-source-id: 8ecc86a8be181a9eb695aa12305b2a30b6f4b60e

Summary:
Moved `Future::within` to `FutureBase::withinImplementation`, and changed it to return a `SemiFuture`.
`SemiFuture::within` uses it directly, and `Future::within` uses it then attaches the current executor or falls back to the inline executor to preserve existing behavior.

Reviewed By: yfeldblum

Differential Revision: D8269907

fbshipit-source-id: 76e235a2ecb2c648603961d0ac0ac17bf646d027

Summary:
[Folly] Support self-copy in `small_vector`.

And refactor move-assignment to look like the fixed copy-assignment for symmetry.

Reviewed By: Ahmed-Salama

Differential Revision: D8321122

fbshipit-source-id: 2c8b26ad6c4e538266082df29276b827cf4505fc

Summary: When vector intrinsics are not available, `visitAllocationClasses` fails to compile as it is a member function of a template class and it invokes a member function of a template base class without explicit `this->`.

Reviewed By: yfeldblum, nbronson

Differential Revision: D8300168

fbshipit-source-id: 1c1619bd1c864535648e531b218d2cf1ffef767b

Summary:
VLOG(1) shows up in Android logs, which is annoying as some of our
tools try to repeatedly connect.

Reviewed By: yfeldblum

Differential Revision: D8297987

fbshipit-source-id: 45cf4320d2e2fcf570117fee6aef133b2d9986e6

Summary:
There is no guarantee that the default branch in git is 'master'; so
    unless specified we checkout a tag along the 'dev' branch, which is not
    intended as it is the master branch that tracks releases for Zstd.

Reviewed By: jstrizich

Differential Revision: D8297843

fbshipit-source-id: 8497dc75c399ae7c86e27b28fdb73898ef4b1a4e

Summary: `s/Future/SemiFuture/` on `SemiFuture` ctor and fixed typo `s/Timeekeeper/Timekeeper/`.

Reviewed By: yfeldblum

Differential Revision: D8290658

fbshipit-source-id: 99ddbdecc0302e620bd2b4ebce74c6080cf81aec

Make Future<T>::delayed complete on correct executor 5/n: Add back Future::delayed with correct behaviour

Summary:
Overall plan to modify Future<T>::delayed to complete on the same
executor as the input future.

[folly::Futures] Make Future<T>::delayed complete on correct executor 5/n:
 * Add back future::delayed.
 * Have Future::delayed complete on input executor.
 * r-value qualify Future::delayed

Reviewed By: yfeldblum, marshallcline

Differential Revision: D8238220

fbshipit-source-id: 79afa8cc9a9fe588609ad186ad62f714ee322f7d

Summary: [Folly] Let `Sychronized` move-constructor not lock the source object, since it is an rvalue-reference and the move-constructor code may therefore be assumed to have the only live reference to the source. Same with the move-assignment operator.

Reviewed By: aary

Differential Revision: D8219883

fbshipit-source-id: f62ff87197ac4b9ceed290a73a05062ab8ed45c4

Summary:
Reusing a context can provide significant efficiency benefits.

Depends on D8172871.

Reviewed By: yfeldblum, terrelln

Differential Revision: D8287767

fbshipit-source-id: 2565e7a959b2ac0911f0a4d6e1596f9da6d12ee8