kokkos / kokkos/mdspan

Document where integer overflow - related preconditions get checked

Open
#160 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C++
Stars
507
Forks
87
Avg merge
15h 27m
Merged PRs (30d)
2

Description

A user recently asked what parts of mdspan impose preconditions relating to integer overflow. One can deduce this from the proposals, but it would make sense to restate the preconditions in a single place for tutorial material.

One source of confusion was just where one can find the final version of mdspan. This lives in the proposals to be voted on Monday 2022/07/25: P0009R18, P2599R2, P2604R0 and P2613R1. In particular, P0009R18 has all the official content of mdspan, except for the renamings in P2599 and P2604, and the addition of empty() in P2613.

Summary: Integer overflow preconditions mainly live in the layout mapping. Here is a more detailed list of preconditions.

  • extents only requires that each extent is representable as a value of type index_type. Their product doesn't have to be.
  • The layout mapping requirements impose preconditions. operator() must return something less than max index_type, and less than or equal to max size_t. required_size_type() must be less than or equal to max index_type (explaining the strict inequality for operator()).
  • The specific layout mapping constructors also impose preconditions: see e.g., mdspan.layoutleft.ctor 1 and mdspan.layoutleft.obs 3.
  • mdspan's constructors get their preconditions from the layout mapping (map_'s constructor's preconditions), and from "[0, map_.required_span_size()) is an accessible range."
  • mdspan::operator[] gets its preconditions from a combination of the layout mapping and index-cast. The static_cast to index_type in the "effects: equivalent to" doesn't affect the Precondition. (The Precondition applies pre-cast. The cast to index_type exists because the input to operator[] need not be integers. For example, users could wrap integers to make "strongly typed indices" (to avoid mixing up i and j in loops).)
  • mdspan::size() returns the product of extents, which is the number of elements. This could be greater than required_span_size(). For example, a "single value" mapping could map every multidimensional index to the offset zero. The size() would still be the product of extents, but the required_span_size() would be 1.

Here are some examples.

This code does not violate any preconditions, even though the product of the extents does not fit in index_type.

extents<uint32_t, dynamic_extent, dynamic_extent> e{std::numeric_limits<uint32_t>::max(), 2}; // OK

This code violates the extents constructor precondition that each extent is representable as a value of type index_type.

extents<uint32_t, dynamic_extent, dynamic_extent> e{static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1, 2}; // UB

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Compare the integer-overflow preconditions across P0009R18, P2599R2, P2604R0, and P2613R1, paying particular attention to the cited layout-mapping clauses such as mdspan.layoutleft.ctor and mdspan.layoutleft.obs. Consolidate the applicable preconditions and examples into the project's tutorial material, with the finished documentation clearly distinguishing extents, layout mappings, constructors, operator[], and size().

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
documentation
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.