Fix circular_queue pop_front(count) debug assert and empty() (#141)

Summary: Two bugs in circular_queue:

pop_front(count) aborts in debug builds on valid input. The debug assumption FATAL_ASSUME_EQ(offset_ == 0, count == chunk) is wrong: offset_ wraps to zero exactly when the first chunk reaches the end of the backing buffer, which is unrelated to count == chunk. Reproduced: q.push_back(0..2); q.pop_front(1); aborts at circular_queue.h:262 because offset_ == 0 is false while count == chunk is true. Similarly a wrap-around pop with count > chunk aborts because offset_ == 0 is true while count == chunk is false. The only input that survived was count == buffer_size - offset_ exactly. The assertion now encodes the real safety precondition of the second loop: when more elements remain to be destroyed beyond the first chunk, the buffer must have wrapped around (so offset_ was reset to 0).
empty() reports the wrong value. It returned queue_.empty() (emptiness of the backing std::vector) instead of size_ == 0. After all elements are popped, size() is 0 but empty() stays false because the backing vector still holds storage. This breaks the canonical while (!q.empty()) { q.pop_front(); } idiom (it never terminates) and lets front()/back() read already-destroyed elements. It now returns size_ == 0.

Pull Request resolved: https://github.com/facebook/fatal/pull/141

Test Plan:

Added regression tests: pop_front_count, pop_front_count_wrap, empty_after_drain.
pop_front_count aborts against the old header (wrong assumption); empty_after_drain hangs forever against the old empty().
Full circular_queue suite passes with the fix (13/13), plus a randomized model test (5000 mixed push/pop ops, std::deque oracle) and a std::string wrap-around test.

Reviewed By: ilvokhin

Differential Revision: D118651261

Pulled By: yfeldblum

fbshipit-source-id: c49659b62c3dc0c2a082323500314feb00d84282

Facebook Template Library

Fatal (Facebook Template Library) is a library for fast prototyping software in modern C++.

It provides facilities heavily based on template meta-programming, while keeping most of the complexity under-the-hood, to enhance the expressive power of C++.

Fatal also provides lessons on how to write meta-programs, as well as on how to make the best use of the library, starting at beginner levels.

The goal is make its benefits available to a wider audience other than just hard-core library writers.

Documentation and Examples

A learn-by-example guide is available under the lesson/ directory.

Demo programs are also available under the demo/ directory.

Extensive documentation with examples can be found inline in the source header files.

Building Fatal

Fatal is a header only library, therefore no building is required.

Requirements

A compliant C++14 compiler. Currently tested under Clang {3.5, 3.6, 3.7, 3.8, 3.9, 5.0} and GCC {5, 6}.

There are no other external dependencies.

Links

Discussions group on Facebook

Try it online using Metashell.

Philosophy

Fatal moves fast, therefore it uses the latest and greatest in C++ standards. It aims to adopt new standard features as soon as they’re officially out, as long as they provide benefits like performance, productivity and usability improvements.

Stable versions are tagged and can be found under the list of releases. Look out for breaking changes whenever a new release is made (see below) - they should be listed on the release notes.

The master branch is considered the development version of the library and experiences frequent updates. If you want the bleeding edge, that’s the branch for you. Be advised, though, that it is under heavy development: breaking changes might be introduced without notice. They’ll be tagged with the string [break] in the first line of the commit message.

Installation

There’s no need to install Fatal, as long as you add its base directory to the include directories list.

For Clang and GCC, it suffices to either:

use the -I path/to/fatal flag
set the environment variable CPLUS_INCLUDE_PATH=path/to/fatal

Building Benchmarks and Unit Tests

$ clang++ -Wall -Werror -O2 -std=c++17 -I path/to/fatal \
  -o path/to/output/binary path/to/test/or/benchmark.cpp \

$ g++ -Wall -Werror -O2 -std=c++17 -I path/to/fatal \
  -o path/to/output/binary path/to/test/or/benchmark.cpp \

Join the Fatal community

Website: https://github.com/facebook/fatal/
Facebook Group: https://www.facebook.com/groups/libfatal/
Talk at CppCon 2014: https://www.youtube.com/watch?v=0A9pYr8wevk

See the CONTRIBUTING file for how to help out.

License

Fatal is BSD-licensed. We also provide an additional patent grant.