//
// Copyright (c) 2019 Apple, Inc. All rights reserved.
//
// @APPLE_OSREFERENCE_LICENSE_HEADER_START@
//
// This file contains Original Code and/or Modifications of Original Code
// as defined in and that are subject to the Apple Public Source License
// Version 2.0 (the 'License'). You may not use this file except in
// compliance with the License. The rights granted to you under the License
// may not be used to create, or enable the creation or redistribution of,
// unlawful or unlicensed copies of an Apple operating system, or to
// circumvent, violate, or enable the circumvention or violation of, any
// terms of an Apple operating system software license agreement.
//
// Please obtain a copy of the License at
// http://www.opensource.apple.com/apsl/ and read it before using this file.
//
// The Original Code and all software distributed under the License are
// distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
// EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
// INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
// Please see the License for the specific language governing rights and
// limitations under the License.
//
// @APPLE_OSREFERENCE_LICENSE_HEADER_END@
//

#ifndef XNU_LIBKERN_LIBKERN_CXX_BOUNDED_ARRAY_REF_H
#define XNU_LIBKERN_LIBKERN_CXX_BOUNDED_ARRAY_REF_H

#if !TAPI

#if DRIVERKIT_FRAMEWORK_INCLUDE
#include <DriverKit/bounded_array.h>
#include <DriverKit/bounded_ptr.h>
#else
#include <libkern/c++/bounded_array.h>
#include <libkern/c++/bounded_ptr.h>
#endif /* DRIVERKIT_FRAMEWORK_INCLUDE */

#include <stddef.h>
#include <os/base.h>

namespace libkern {
namespace bar_detail {
using nullptr_t = decltype(nullptr);
}

// Represents a reference to a sequence of 0 or more elements consecutively in
// memory, i.e. a start pointer and a length.
//
// When elements of the sequence are accessed, `bounded_array_ref` ensures
// that those elements are in the bounds of the sequence (which are provided
// when the `bounded_array_ref` is constructed).
//
// This class does not own the underlying data. It is expected to be used in
// situations where the data resides in some other buffer, whose lifetime
// extends past that of the `bounded_array_ref`. For this reason, storing a
// `bounded_array_ref` adds the risk of a dangling pointer if the lifetime of
// the `bounded_array_ref` extends past that of the underlying data.
//
// `bounded_array_ref` is trivially copyable and it should be passed by value.
template <typename T, typename TrappingPolicy>
struct bounded_array_ref {
	// Creates an empty `bounded_array_ref`.
	//
	// An empty `bounded_array_ref` does not reference anything, so its
	// `data()` is null and its `size()` is 0.
	explicit constexpr bounded_array_ref() noexcept : data_(nullptr), size_(0)
	{
	}

	// Creates a `bounded_array_ref` from a bounded pointer and a size.
	//
	// The resulting `bounded_array_ref` starts at the location where the
	// pointer points, and has the given number of elements. All the elements
	// must be in the bounds of the `bounded_ptr`, otherwise this constructor
	// will trap.
	explicit constexpr bounded_array_ref(bounded_ptr<T, TrappingPolicy> data, size_t n)
		: data_(data.unsafe_discard_bounds()), size_(static_cast<uint32_t>(n))
	{
		if (n != 0) {
			data[n - 1]; // make sure the bounds are valid
			// TODO: find a better way to do that
		}
		if (__improbable(n > UINT32_MAX)) {
			TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX");
		}
	}

	// Creates a `bounded_array_ref` from a raw pointer and a size.
	//
	// The resulting `bounded_array_ref` starts at the location where the
	// pointer points, and has the given number of elements. This constructor
	// trusts that `n` elements are reachable from the given pointer.
	explicit constexpr bounded_array_ref(T* data, size_t n) : data_(data), size_(static_cast<uint32_t>(n))
	{
		if (__improbable(n > UINT32_MAX)) {
			TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX");
		}
	}

	// Creates a `bounded_array_ref` from a `[first, last)` half-open range.
	//
	// The resulting `bounded_array_ref` starts at the location pointed-to by
	// `first`, and contains `last - first` elements. The `[first, last)`
	// half-open range must be a valid range, i.e. it must be the case that
	// `first <= last`, otherwise the constructor traps.
	explicit constexpr bounded_array_ref(T* first, T* last) : data_(first), size_(static_cast<uint32_t>(last - first))
	{
		if (__improbable(first > last)) {
			TrappingPolicy::trap("bounded_array_ref: The [first, last) constructor requires a valid range.");
		}
		if (__improbable(last - first > UINT32_MAX)) {
			TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX");
		}
	}

	// Creates a `bounded_array_ref` from a `bounded_array`.
	//
	// The resulting `bounded_array_ref` starts at the first element of the
	// `bounded_array`, and has the number of elements in the `bounded_array`.
	template <size_t N>
	constexpr bounded_array_ref(bounded_array<T, N, TrappingPolicy>& data) : data_(data.data()), size_(static_cast<uint32_t>(data.size()))
	{
		if (__improbable(data.size() > UINT32_MAX)) {
			TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX");
		}
	}

	// Creates a `bounded_array_ref` from a C-style array.
	//
	// The resulting `bounded_array_ref` starts at the first element of the
	// C-style array, and has the number of elements in that array.
	template <size_t N>
	constexpr bounded_array_ref(T (&array)[N]) : data_(array), size_(static_cast<uint32_t>(N))
	{
		if (__improbable(N > UINT32_MAX)) {
			TrappingPolicy::trap("bounded_array_ref: Can't construct from a size greater than UINT32_MAX");
		}
	}

	constexpr
	bounded_array_ref(bounded_array_ref const&) = default;
	constexpr
	bounded_array_ref(bounded_array_ref&& other) noexcept = default;

	constexpr bounded_array_ref& operator=(bounded_array_ref const&) = default;
	constexpr bounded_array_ref& operator=(bounded_array_ref&& other) = default;
	~bounded_array_ref() = default;

	// Returns whether the `bounded_array_ref` points to a sequence or not.
	//
	// Note that pointing to a sequence at all is different from pointing to
	// a valid sequence, or having a size of 0. If a `bounded_array_ref`
	// points to a sequence (regardless of whether it is valid or whether
	// the size of that sequence is 0), this operator will return true.
	explicit
	operator bool() const noexcept
	{
		return data_ != nullptr;
	}

	using iterator = bounded_ptr<T, TrappingPolicy>;

	// The following methods allow obtaining iterators (i.e. cursors) to
	// objects inside a `bounded_array_ref`.
	//
	// The iterators of a `bounded_array_ref` are `bounded_ptr`s, which know
	// the bounds of the sequence and will trap when dereferenced outside
	// of those bounds.
	//
	// `begin()` returns an iterator to the first element in the range, and
	// `end()` returns an iterator to one-past-the-last element in the range.
	// The `end()` iterator can't be dereferenced, since it is out of bounds.
	//
	// If the `bounded_array_ref` is empty, these methods will return null
	// `bounded_ptr`s, which can be checked for equality but can't be
	// dereferenced.
	OS_ALWAYS_INLINE iterator
	begin() const noexcept
	{
		return iterator(data_, data_, data_ + size_);
	}
	iterator
	end() const noexcept
	{
		return iterator(data_ + size_, data_, data_ + size_);
	}

	// Returns the number of elements in the range referenced by the
	// `bounded_array_ref`.
	//
	// This method returns `0` if the `bounded_array_ref` is null, since
	// such an array ref behaves the same as an empty range.
	constexpr size_t
	size() const noexcept
	{
		return size_;
	}

	// This has the same behavior as size(), but is intended to avoid confusion
	// about whether it is returning an array count or size in bytes.
	constexpr size_t
	length() const noexcept
	{
		return size_;
	}

	// Returns a non-owning pointer to the underlying memory referenced by a
	// `bounded_array_ref`.
	//
	// This method can be called even if the `bounded_array_ref` is null, in
	// which case the returned pointer will be null.
	constexpr T*
	data() const noexcept
	{
		return data_;
	}

	// Access the n-th element of a `bounded_array_ref`.
	//
	// If `n` is out of the bounds of the sequence, this operation will
	// trap. If the array ref is null, this operation will trap too.
	//
	// Design note:
	// We voluntarily use a signed type to represent the index even though a
	// negative index will always cause a trap. If we used an unsigned type,
	// we could get an implicit conversion from signed to unsigned, which
	// could silently wrap around. We think trapping early is more likely
	// to be helpful in this situation.
	OS_ALWAYS_INLINE T&
	operator[](ptrdiff_t n) const
	{
		return begin()[n];
	}

	// Chop off the first `n` elements of the array, and keep `m` elements
	// in the array.
	//
	// The resulting range can be described by `[beg + n, beg + n + m)`, where
	// `beg` is the `begin()` of the range being sliced. This operation traps
	// if `n + m` is larger than the number of elements in the array.
	//
	// Since `bounded_array_ref` checks (or assumes) that the range it is
	// given on construction is within bounds and `slice()` checks that the
	// produced slice is within the original range, it is impossible to create
	// a `bounded_array_ref` that isn't a subset of a valid range using this
	// function.
	bounded_array_ref<T, TrappingPolicy>
	slice(size_t n, size_t m) const
	{
		uint32_t total;
		if (__improbable(os_add_overflow(n, m, &total))) {
			TrappingPolicy::trap("bounded_array_ref: n + m is larger than the size of any bounded_array_ref");
		}
		if (__improbable(total > size())) {
			TrappingPolicy::trap("bounded_array_ref: invalid slice provided, the indices are of bounds for the bounded_array_ref");
		}
		return bounded_array_ref(data_ + n, m);
	}

private:
	T* data_;
	uint32_t size_;
};

// The comparison functions against `nullptr` all return whether the
// `bounded_array_ref` references a sequence or not.
template <typename T, typename P>
bool
operator==(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t)
{
	return !static_cast<bool>(x);
}

template <typename T, typename P>
bool
operator!=(bounded_array_ref<T, P> const& x, bar_detail::nullptr_t)
{
	return !(x == nullptr);
}

template <typename T, typename P>
bool
operator==(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x)
{
	return x == nullptr;
}

template <typename T, typename P>
bool
operator!=(bar_detail::nullptr_t, bounded_array_ref<T, P> const& x)
{
	return x != nullptr;
}
} // end namespace libkern

#endif /* !TAPI */

#endif // !XNU_LIBKERN_LIBKERN_CXX_BOUNDED_ARRAY_REF_H