Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D107932 Diff 366656 libcxx/include/__ranges/non_propagating_cache.h

Changeset View

Standalone View

View Options

libcxx/include/__ranges/non_propagating_cache.h

// -*- C++ -*- // -*- C++ -*-
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H #ifndef _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H
#define _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H #define _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H
#include <__config> #include <__config>
#include <__iterator/concepts.h> // indirectly_readable #include <__iterator/concepts.h> // indirectly_readable
#include <__iterator/iterator_traits.h> // iter_reference_t #include <__iterator/iterator_traits.h> // iter_reference_t
#include <__memory/addressof.h> #include <__memory/addressof.h>
#include <__utility/forward.h>
#include <concepts> // constructible_from #include <concepts> // constructible_from
#include <optional> #include <optional>
#include <type_traits> #include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header #pragma GCC system_header
#endif #endif
_LIBCPP_PUSH_MACROS
#include <__undef_macros>
_LIBCPP_BEGIN_NAMESPACE_STD _LIBCPP_BEGIN_NAMESPACE_STD
// clang-format off
#if !defined(_LIBCPP_HAS_NO_RANGES) #if !defined(_LIBCPP_HAS_NO_RANGES)
namespace ranges { namespace ranges {
// __non_propagating_cache is a helper type that allows storing an optional value in it, // __non_propagating_cache is a helper type that allows storing an optional value in it,
// but which does not copy the source's value when it is copy constructed/assigned to, // but which does not copy the source's value when it is copy constructed/assigned to,
// and which resets the source's value when it is moved-from. // and which resets the source's value when it is moved-from.
// //
// This type is used as an implementation detail of some views that need to cache the // This type is used as an implementation detail of some views that need to cache the
// result of `begin()` in order to provide an amortized O(1) begin() method. Typically, // result of `begin()` in order to provide an amortized O(1) begin() method. Typically,
// we don't want to propagate the value of the cache upon copy because the cached iterator // we don't want to propagate the value of the cache upon copy because the cached iterator
// may refer to internal details of the source view. // may refer to internal details of the source view.
template<class _Tp> template<class _Tp>
requires is_object_v<_Tp> requires is_object_v<_Tp>
class _LIBCPP_TEMPLATE_VIS __non_propagating_cache { class _LIBCPP_TEMPLATE_VIS __non_propagating_cache {
optional<_Tp> __value_ = nullopt; struct __from_tag { };
struct __forward_tag { };
// This helper class is needed to perform copy and move elision when
// constructing the contained type from an iterator.
misccoUnsubmitted
Done
ReplyInline Actions

I would not go that route.

There are more places where you would want to reuse __non_propagating_cache, e.g. with views::split you want to cache the call to search(__view.begin(), __pattern). That would not be possible to achieve when hard coding the wrapper in __non_propagating_cache

It is much easier to pull that wrapper as an implementation detail into views::join and let __non_propagating_cache be a generic utility

See (https://github.com/microsoft/STL/blob/a9321cfe53ea31a7e197d5d8336167d6ca3de8b6/stl/inc/ranges#L2962-L2975)

miscco: I would not go that route. There are more places where you would want to reuse…
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

I see a non-propagating-cache in lazy_split_view
http://eel.is/c++draft/range.adaptors#range.lazy.split.outer-1
but it's initialized only with the result of ranges::find, which is an iterator, right? I don't see anywhere where we'd need to cache the result of ranges::search.
I don't see a non-propagating-cache actually specified for split_view, although the English wording does talk about "caches the result [of begin()]" in http://eel.is/c++draft/range.adaptors#range.split.view-4

However, if we anticipate needing to emplace more things than just *it, then it would be reasonable IMO to augment or replace this __emplace_deref(It) with a more general __emplace_from(F) that takes an arbitrary prvalue-producing lambda. (What I've called the "super constructing super elider.")

Quuxplusone: I see a //`non-propagating-cache`// in `lazy_split_view` http://eel.is/c++draft/range.
misccoUnsubmitted
Done
ReplyInline Actions

You are missing the new and shiny split_view In begin we call find-next `http://eel.is/c++draft/range.split.view#3 with the explicit remark that we need to cache it http://eel.is/c++draft/range.split.view#4

find-next returns a subrange<It>

miscco: You are missing the new and shiny `split_view` In begin we call `find-next` `http://eel.
ldionneAuthorUnsubmitted
Done
ReplyInline Actions

Hmm, I quite like Arthur's idea with a general __emplace_from. It will allow us to easily elide from arbitrary expressions.

ldionne: Hmm, I quite like Arthur's idea with a general `__emplace_from`. It will allow us to easily…
struct __wrapper {
template<class ..._Args>
constexpr explicit __wrapper(__forward_tag, _Args&& ...__args) : __t_(_VSTD::forward<_Args>(__args)...) { }
template<class _Fn>
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

This overload set has the distinct smell of "greedy perfect-forwarding overload eats things you wouldn't expect." You use it below like this:

constexpr _Tp& __emplace_deref(_Iter const& __iter) {
  return __value_.emplace(__deref_tag{}, __iter).__t_;
}

which I think is fine; but if you (or future-you) changes it to

constexpr _Tp& __emplace_deref(_Iter __iter) {
  return __value_.emplace(__deref_tag{}, __iter).__t_;
}

then suddenly it'll pick the wrong overload. Right?
I'm not 100% sure this is worth fixing, but if it is, then I think I'd fix it by adding a second tag type, say struct __no_deref_tag { }, and making the constructor on line 47 take __wrapper(__no_deref_tag, _Args&&...).

Quuxplusone: This overload set has the distinct smell of "greedy perfect-forwarding overload eats things you…
constexpr explicit __wrapper(__from_tag, _Fn const& __f) : __t_(__f()) { }
_Tp __t_;
};
optional<__wrapper> __value_ = nullopt;
public: public:
_LIBCPP_HIDE_FROM_ABI __non_propagating_cache() = default; _LIBCPP_HIDE_FROM_ABI __non_propagating_cache() = default;
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr __non_propagating_cache(__non_propagating_cache const&) noexcept constexpr __non_propagating_cache(__non_propagating_cache const&) noexcept
: __value_(nullopt) : __value_(nullopt)
{ } { }
Show All 15 Lines public:
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept { constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept {
__value_.reset(); __value_.reset();
__other.__value_.reset(); __other.__value_.reset();
return *this; return *this;
} }
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr _Tp& operator*() { return *__value_; } constexpr _Tp& operator*() { return __value_->__t_; }
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr _Tp const& operator*() const { return *__value_; } constexpr _Tp const& operator*() const { return __value_->__t_; }
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

Any appetite for making these named members (e.g. npc.__value())?
Besides my usual advice that operators can be harder to read and/or go-to-definition of, it also just occurred to me that operators are subject to ADL but member functions are not:
https://godbolt.org/z/EsasGzoad
(I don't think the Standard cares about ADL in this instance; but any time I see a chance to ADL-proof something... ;))

Quuxplusone: Any appetite for making these named members (e.g. `npc.__value()`)? Besides my usual advice…
ldionneAuthorUnsubmitted
Done
ReplyInline Actions

Any appetite for making these named members (e.g. npc.__value())?

Not really, I think operator* is pretty idiomatic and I see no strong enough reason to change.

ldionne: > Any appetite for making these named members (e.g. `npc.__value()`)? Not really, I think…
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr bool __has_value() const { return __value_.has_value(); } constexpr bool __has_value() const { return __value_.has_value(); }
template<class _Fn>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr void __set(_Tp const& __value) { __value_.emplace(__value); } constexpr _Tp& __emplace_from(_Fn const& __f) {
_LIBCPP_HIDE_FROM_ABI return __value_.emplace(__from_tag{}, __f).__t_;
constexpr void __set(_Tp&& __value) { __value_.emplace(_VSTD::move(__value)); } }
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

FYI: With a super-eliding __emplace_from, this would turn into

template<class _Fn>
_LIBCPP_HIDE_FROM_ABI
constexpr _Tp& __emplace_from(_Fn __iter) {
  return __value_.emplace(__from_tag{}, _Fn).__t_;
}

template<class _Iter>
_LIBCPP_HIDE_FROM_ABI
constexpr _Tp& __emplace_deref(_Iter const& __iter) {
  return __emplace_from([&]() -> decltype(auto) { return *__iter; });
}
Quuxplusone: FYI: With a super-eliding `__emplace_from`, this would turn into ``` template<class _Fn>…
template<class _Other> template<class ..._Args>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDE_FROM_ABI
constexpr _Tp& __emplace_deref(const _Other& __value) { constexpr _Tp& __emplace(_Args&& ...__args) {
__value_.reset(); return __value_.emplace(__forward_tag{}, _VSTD::forward<_Args>(__args)...).__t_;
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

FWIW, this could be

return __value_.emplace(__from_tag{}, [&]() { return _Tp(_VSTD::forward<_Args>(__args)...); }).__t_;

and then eliminate __forward_tag. No strong preference.

Quuxplusone: FWIW, this could be ``` return __value_.emplace(__from_tag{}, [&]() { return _Tp(_VSTD…
ldionneAuthorUnsubmitted
Done
ReplyInline Actions

Will keep as-is, I like to avoid creating a potentially large number of captures in the lambda here (even if those are by ref).

ldionne: Will keep as-is, I like to avoid creating a potentially large number of captures in the lambda…
__value_.emplace(*__value);
return *__value_;
} }
}; };
struct __empty_cache { }; struct __empty_cache { };
} // namespace ranges } // namespace ranges
#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES) #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES)
_LIBCPP_END_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD
_LIBCPP_POP_MACROS
#endif // _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H #endif // _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H