Repository structure modernization

[sleeepyjack]

We'd like to discuss two friction points in the repo layout, both about the public include surface. Filing as a discussion because any change here would break the public API and warrant a major version bump; better to agree on the destination before anyone writes a patch.

Problem 1: Generic top-level header names collide across libraries

Public headers sit at shallow paths with generic filenames, installed flat under a single directory:

hll/include/hll.hpp
theta/include/theta_sketch.hpp
common/include/serde.hpp
common/include/optional.hpp
# ...installed via `DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches"`

Consumers write #include <hll.hpp>. Nothing in the path identifies the library, and names like hll.hpp, serde.hpp, optional.hpp, and tdigest.hpp are plausible choices for any number of unrelated projects. A consumer linking against datasketches alongside another library that also ships an hll.hpp ends up with two headers competing for the same include path, with no clean way to disambiguate.

The fix is to namespace the include path under the library name. Two shapes are worth considering.

Option A: Nested per-sketch directories, drop the filename prefix

include/datasketches/
  hll/
    sketch.hpp                 # was hll.hpp
    detail/...
  theta/
    sketch.hpp                 # was theta_sketch.hpp
    union.hpp                  # was theta_union.hpp
    intersection.hpp
    a_not_b.hpp
    jaccard_similarity.hpp
    detail/...
  cpc/
    sketch.hpp
    detail/...
  ...

Consumer: #include <datasketches/theta/union.hpp>

The directory does the namespacing work; the filename drops the now-redundant theta_ prefix. Matches Boost (<boost/graph/adjacency_list.hpp>).

Option B: Flat namespace, keep descriptive filenames

include/datasketches/
  hll_sketch.hpp                # was hll.hpp
  theta_sketch.hpp
  theta_union.hpp
  theta_intersection.hpp
  theta_a_not_b.hpp
  theta_jaccard_similarity.hpp
  cpc_sketch.hpp
  ...
  detail/
    hll/...
    theta/...

Consumer: #include <datasketches/theta_union.hpp>

The filename prefix carries the grouping, and the public surface stays on a single flat level. Matches Abseil (<absl/container/flat_hash_map.h>).

Either way, the install path becomes ${CMAKE_INSTALL_INCLUDEDIR}/datasketches/.

Problem 2: Public and internal headers live in the same directory

hll/include/ mixes the public hll.hpp with roughly 30 implementation headers (e.g. HllSketchImpl.hpp, AuxHashMap.hpp) plus another 15-odd *-internal.hpp files. All of them get installed by hll/CMakeLists.txt. From a consumer standpoint, this seems valid:

#include <DataSketches/HllSketchImpl.hpp>
#include <DataSketches/AuxHashMap-internal.hpp>

There is no clear API boundary between public and internal headers.

The fix is a per-sketch detail/ subdirectory, a convention Boost has used since the early 2000s and that Abseil mirrors with its internal/ directories. Implementation headers move there, and the contract for consumers is straightforward: anything inside detail/ is internal, and reaching in is at your own risk.

Low-priority items

• Header guards. Two styles coexist: hll/include/HllArray.hpp uses _HLLARRAY_HPP_ (leading underscore, reserved by the standard); theta/include/theta_sketch.hpp uses THETA_SKETCH_HPP_. Switching all headers to #pragma once removes the inconsistency, the reserved-identifier risk, and a class of copy-paste mistakes.
• No .clang-format. Style is enforced by convention only. Committing a single file would replace formatting back-and-forth in code review.
• Pick one casing convention. File names and code currently mix CamelCase and snake_case. Low-priority but easy on the eyes.
• Tests scattered per-sketch. Each <sketch>/test/CMakeLists.txt repeats the Catch2 wiring and test-discovery setup. Consolidating into a single test/ tree (with per-sketch subdirs) would declare the test framework once, give shared fixtures (random key generators, serde helpers) an obvious home. The current setup works; this is cleanup, not a fix.

[sleeepyjack]

CC += @leerho @PointKernel

[PointKernel]

+1 for the new structural layout, both fixes are overdue: generic names like optional.hpp are a real collision risk for downstream integrators, and a detail/ boundary keeps implementation headers from quietly becoming ABI contracts.

Worth noting this doesn't have to be a breaking change in one cut: move every header to its new location and leave the old paths as thin facade headers that just #include the new ones with a [[deprecated]] attribute (if available with c++14 or newer) and a @deprecated doxygen note for one or two releases, giving downstream consumers a deprecation window before the shims get removed in the major bump.

[PointKernel]

It looks like this is a duplicate of #419.

[sleeepyjack]

It looks like this is a duplicate of #419.

You're right, it's a near duplicate.
@tjstum @jmalkin lets consolidate the discussion. What are your thoughts on the proposed new layout?

[leerho]

I am all for restructuring the library for ease of use and understanding and make it more consistent in structure with other big libraries. Although this is somewhat of a duplicate of #419, There is additional information here as well.

However, your Option A above will not work. Users often are using several of our sketches in the same application. Absent any other clarifying information the user could end up with a unique counting "sketch.hpp" and a quantiles "sketch.hpp". Oops! This means the user would end up having to fully qualify which sketch is which every time it is used.

We had a similar situation in the DS-Java library and I ended up having to rename many of the classes and methods to include the sketch type in the call. You will now find HllSketch, CpcSketch, ThetaSketch, etc.

A lot of this is historical. Our library started with just one sketch and grew, and grew and added multiple languages as well.

Also, as @jmalkin points out in #419, our original thought was that users would just always install the whole library. And that might have been OK when the library was just one or two sketches. Nonetheless, breaking this up so that each sketch can be extracted on its own may be a lot more involved. There is some common code that is shared across some of the sketches that will have to be looked at.

It is time to modernize the C++ library structure. I will defer to others who are more familiar with C++ to comment on your other suggestions.

This will constitute a new major version. In that context, we may want to take the opportunity to examine whether we want to set the minimum C++ version to C++17. We also want to make sure we include some of the other bug fixes that have been trickling in :)

We also could use some help in this restructuring as the original authors no longer have the time to devote to this. I think they may be available to answer some questions, but that is about it.

I would like to invite a few other folks to weigh in on this :)
CC += @AlexanderSaydakov @jmalkin @will-lauer @tjstum

[sleeepyjack]

Agree the file/class shape needs to land somewhere that doesn't make multi-sketch usage awkward.

One nuance worth surfacing: in C++ the filename and the class name are independent, so even under Option A the classes themselves can keep distinguishing prefixes:

#include <datasketches/hll/sketch.hpp>
#include <datasketches/quantiles/sketch.hpp>

datasketches::hll_sketch h;
datasketches::quantiles_sketch q;

Use sites stay readable that way, even with two sketch.hpp files in different directories.

The filename-level overlap still has some ergonomic cost though: IDE fuzzy search returns multiple sketch.hpp hits, compiler errors read a bit worse, and there's some path-vs-class redundancy if hll appears in both the directory and the class name.

I lean B from this thread, but A still works if the per-sketch directory grouping turns out valuable as the library grows. Curious what the others think.