130 std::ranges::sort(boundaries,
141 const int64_t prev_boundary_index,
142 const int64_t current_boundary_index,
145 const int64_t size = current_boundary_index - prev_boundary_index;
151 return *prev_segment;
153 if (current_boundary_index - prev_segment->
bounds.
start() < max_segment_size) {
158 return *prev_segment;
164 return result.segments.last();
169 const int64_t prev_boundary_index,
170 const int64_t current_boundary_index,
178 return *prev_segment;
184 return result.segments.last();
189 const int64_t prev_boundary_index,
190 const int64_t current_boundary_index,
197 prev_segment->
mask == ©_from_mask)
201 return *prev_segment;
207 return *prev_segment;
213 return result.segments.last();
225 int64_t prev_boundary_index = boundaries[0].index;
228 if (prev_boundary_index <
boundary.index) {
231 bool has_full =
false;
232 bool has_unknown =
false;
233 bool copy_from_single_mask =
true;
234 const IndexMask *copy_from_mask =
nullptr;
235 for (
const CoarseSegment *active_segment : active_segments) {
236 switch (active_segment->type) {
246 if (!
ELEM(copy_from_mask,
nullptr, active_segment->mask)) {
247 copy_from_single_mask =
false;
249 copy_from_mask = active_segment->mask;
259 else if (has_unknown || !copy_from_single_mask) {
263 else if (copy_from_mask !=
nullptr && copy_from_single_mask) {
265 prev_segment, prev_boundary_index,
boundary.index, *copy_from_mask,
result);
268 prev_boundary_index =
boundary.index;
292 int64_t prev_boundary_index = boundaries[0].index;
295 if (prev_boundary_index <
boundary.index) {
298 if (active_segments.
size() == terms_num) {
302 int unknown_count = 0;
304 bool copy_from_single_mask =
true;
305 const IndexMask *copy_from_mask =
nullptr;
306 for (
const CoarseSegment *active_segment : active_segments) {
307 switch (active_segment->type) {
318 if (!
ELEM(copy_from_mask,
nullptr, active_segment->mask)) {
319 copy_from_single_mask =
false;
321 copy_from_mask = active_segment->mask;
327 BLI_assert(full_count + unknown_count + copy_count == terms_num);
328 if (full_count == terms_num) {
332 else if (unknown_count > 0 || copy_count < terms_num || !copy_from_single_mask) {
336 else if (copy_count == terms_num && copy_from_single_mask) {
338 prev_segment, prev_boundary_index,
boundary.index, *copy_from_mask,
result);
342 prev_boundary_index =
boundary.index;
366 int64_t prev_boundary_index = boundaries[0].index;
369 if (prev_boundary_index <
boundary.index) {
372 if (active_main_segments.
size() == 1) {
373 const CoarseSegment &active_main_segment = *active_main_segments[0];
376 bool has_subtract_full =
false;
377 bool has_subtract_same_mask =
false;
378 for (
const CoarseSegment *active_subtract_segment : active_subtract_segments) {
379 switch (active_subtract_segment->type) {
384 has_subtract_full =
true;
389 if (active_main_segment.
mask == active_subtract_segment->mask) {
390 has_subtract_same_mask =
true;
398 if (has_subtract_full) {
402 switch (active_main_segment.
type) {
409 if (active_subtract_segments.is_empty()) {
420 if (active_subtract_segments.is_empty()) {
424 *active_main_segment.
mask,
427 else if (has_subtract_same_mask) {
440 prev_boundary_index =
boundary.index;
481 const std::optional<IndexRange> eval_bounds = std::nullopt)
488 for (
const Expr *expression : eval_order) {
489 CoarseResult &expr_result = expression_results[expression->index].emplace();
490 switch (expression->type) {
495 if (eval_bounds.has_value()) {
502 if (!
mask.is_empty()) {
504 if (
const std::optional<IndexRange> range =
mask.to_range()) {
519 boundaries.
append({segment.bounds.first(),
true, &segment});
520 boundaries.
append({segment.bounds.one_after_last(),
false, &segment});
533 boundaries.
append({segment.bounds.first(),
true, &segment});
534 boundaries.
append({segment.bounds.one_after_last(),
false, &segment});
544 const CoarseResult &main_term_result = *expression_results[expr.
terms[0]->index];
546 boundaries.
append({{segment.bounds.first(),
true, &segment},
true});
547 boundaries.
append({{segment.bounds.one_after_last(),
false, &segment},
true});
549 for (
const Expr *term : expr.
terms.as_span().drop_front(1)) {
550 const CoarseResult &term_result = *expression_results[term->index];
552 boundaries.
append({{segment.bounds.first(),
true, &segment},
false});
553 boundaries.
append({{segment.bounds.one_after_last(),
false, &segment},
false});
564 return std::move(final_result);
602 expr_array_size, ints_in_bounds * bits::BitsPerInt,
false);
604 for (
const Expr *expression : eval_order) {
606 switch (expression->type) {
610 mask.to_bits(expr_result, -bounds_min);
614 for (
const Expr *term : expression->
terms) {
615 expr_result |= expression_results[term->
index];
621 for (
const Expr *term : expression->
terms.as_span().drop_front(1)) {
622 expr_result &= expression_results[term->index];
628 for (
const Expr *term : expression->
terms.as_span().drop_front(1)) {
632 expression_results[term->index]);
651 if (segments.
size() == 1) {
654 if (segments.
size() == 2) {
657 const int64_t size = std::set_union(a.
begin(), a.
end(),
b.begin(),
b.end(), r_values) -
659 return {bounds_min, {r_values, size}};
666 return a.
size() <
b.size();
669 std::array<int16_t, max_segment_size> tmp_indices;
673 int16_t *buffer_b = tmp_indices.data();
675 if (sorted_segments.
size() % 2 == 1) {
677 std::swap(buffer_a, buffer_b);
686 count = std::set_union(a.
begin(), a.
end(),
b.begin(),
b.end(), dst) - dst;
696 count = std::set_union(a, a + count,
b.begin(),
b.end(), dst) - dst;
697 std::swap(buffer_a, buffer_b);
699 return {bounds_min, {r_values, count}};
710 if (segments.
size() == 1) {
713 if (segments.
size() == 2) {
716 const int64_t size = std::set_intersection(a.
begin(), a.
end(),
b.begin(),
b.end(), r_values) -
718 return {bounds_min, {r_values, size}};
725 return a.
size() <
b.size();
728 std::array<int16_t, max_segment_size> tmp_indices_1;
729 std::array<int16_t, max_segment_size> tmp_indices_2;
730 int16_t *buffer_a = tmp_indices_1.data();
731 int16_t *buffer_b = tmp_indices_2.data();
739 count = std::set_intersection(a.
begin(), a.
end(),
b.begin(),
b.end(), dst) - dst;
747 int16_t *dst = (segment_i == sorted_segments.
size() - 1) ? r_values : buffer_b;
748 count = std::set_intersection(a, a + count,
b.begin(),
b.end(), dst) - dst;
749 std::swap(buffer_a, buffer_b);
751 return {bounds_min, {r_values, count}};
770 if (subtract_segments.
size() == 1) {
772 const IndexMaskSegment subtract_segment = subtract_segments[0].shift(-bounds_min);
773 const int64_t size = std::set_difference(shifted_main_segment.
begin(),
774 shifted_main_segment.
end(),
775 subtract_segment.
begin(),
776 subtract_segment.
end(),
779 return {bounds_min, {r_values, size}};
784 subtract_count += segment.size();
786 if (subtract_count < main_segment.
size() / 2) {
789 std::array<int16_t, max_segment_size> union_indices;
794 const int64_t size = std::set_difference(shifted_main_segment.
begin(),
795 shifted_main_segment.
end(),
796 unioned_subtract_segment.
begin(),
797 unioned_subtract_segment.
end(),
800 return {bounds_min, {r_values, size}};
806 sorted_subtract_segments,
809 std::array<int16_t, max_segment_size> tmp_indices_1;
810 std::array<int16_t, max_segment_size> tmp_indices_2;
811 int16_t *buffer_a = tmp_indices_1.data();
812 int16_t *buffer_b = tmp_indices_2.data();
818 const IndexMaskSegment subtract_segment = sorted_subtract_segments[0].shift(-bounds_min);
820 count = std::set_difference(shifted_main_segment.
begin(),
821 shifted_main_segment.
end(),
822 subtract_segment.
begin(),
823 subtract_segment.
end(),
829 const IndexMaskSegment &subtract_segment = sorted_subtract_segments[segment_i].shift(
832 int16_t *dst = (segment_i == sorted_subtract_segments.
size() - 1) ? r_values : buffer_b;
833 count = std::set_difference(buffer_a,
835 subtract_segment.
begin(),
836 subtract_segment.
end(),
839 std::swap(buffer_a, buffer_b);
841 return {bounds_min, {r_values, count}};
858 for (
const Expr *expression : eval_order) {
859 switch (expression->type) {
865 if (
mask.segments_num() == 1) {
866 results[expression->index] =
mask.segment(0);
873 int64_t result_size_upper_bound = 0;
874 bool used_short_circuit =
false;
881 results[expression->index] = term_segment;
882 used_short_circuit =
true;
885 term_segments[term_i] = term_segment;
886 result_size_upper_bound += term_segment.
size();
888 if (used_short_circuit) {
891 result_size_upper_bound = std::min(result_size_upper_bound,
bounds.size());
894 term_segments, bounds_min, dst.
data());
896 result_segment.base_span().end());
897 results[expression->index] = result_segment;
904 bool used_short_circuit =
false;
910 results[expression->index] = {};
911 used_short_circuit =
true;
914 result_size_upper_bound = std::min(result_size_upper_bound, term_segment.
size());
915 term_segments[term_i] = term_segment;
917 if (used_short_circuit) {
922 term_segments, bounds_min, dst.
data());
924 result_segment.base_span().end());
925 results[expression->index] = result_segment;
934 results[expression->index] = {};
937 int64_t result_size_upper_bound = main_segment.
size();
938 bool used_short_circuit =
false;
940 for (
const int64_t term_i : expr.
terms.index_range().drop_front(1)) {
941 const Expr &subtract_term = *expr.
terms[term_i];
946 results[expression->index] = {};
947 used_short_circuit =
true;
950 result_size_upper_bound = std::min(result_size_upper_bound,
952 subtract_segments[term_i - 1] = term_segment;
954 if (used_short_circuit) {
959 main_segment, subtract_segments, bounds_min, dst.
data());
961 result_segment.base_span().end());
962 results[expression->index] = result_segment;
967 return results[root_expression.
index];
979 switch (evaluated_segment.type) {
986 evaluated_segment.bounds);
992 result_mask_segments.
append(evaluated_segment.indices);
997 return result_mask_segments;
1008 eval_order.
append(&root_expression);
1015 expr_stack.
push(&root_expression);
1018 const Expr &expression = *expr_stack.
peek();
1019 bool &is_evaluated = is_evaluated_states[expression.
index];
1024 bool all_terms_evaluated =
true;
1025 for (
const Expr *term : expression.
terms) {
1026 bool &term_evaluated = is_evaluated_states[term->
index];
1027 if (!term_evaluated) {
1030 term_evaluated =
true;
1033 expr_stack.
push(term);
1034 all_terms_evaluated =
false;
1038 if (all_terms_evaluated) {
1039 eval_order.
append(&expression);
1040 is_evaluated =
true;
1051 for (
const Expr *term : root_expression.
terms) {
1052 if (!term->
terms.is_empty()) {
1061 const Expr &root_expression,
1071 const int64_t coarse_segment_size_threshold = max_segment_size;
1076 auto handle_coarse_result = [&](
const CoarseResult &coarse_result) {
1077 for (
const CoarseSegment &segment : coarse_result.segments) {
1078 switch (segment.type) {
1080 if (segment.bounds.size() > coarse_segment_size_threshold) {
1081 long_unknown_segments.
push(segment.bounds);
1084 r_short_unknown_segments.
append(segment.bounds);
1090 r_evaluated_segments.
append(
1105 handle_coarse_result(initial_coarse_result);
1108 while (!long_unknown_segments.
is_empty()) {
1109 const IndexRange unknown_bounds = long_unknown_segments.
pop();
1110 const int64_t split_pos = unknown_bounds.
size() / 2;
1115 handle_coarse_result(left_result);
1116 handle_coarse_result(right_result);
1121 const Expr &root_expression,
1133 switch (exact_eval_mode) {
1136 root_expression, allocator,
bounds, eval_order);
1138 r_local_evaluated_segments.append(
1150 const Expr &expr = *eval_order[eval_order_i];
1157 if (segments_num <= 1) {
1167 split_indices.
append(segment[0]);
1170 std::ranges::sort(split_indices);
1173 split_indices[boundary_i + 1]);
1178 root_expression, allocator, sub_bounds, eval_order);
1180 r_local_evaluated_segments.append(
1191 const int64_t unknown_segment_eval_grain_size = 8;
1192 if (short_unknown_segments.
size() < unknown_segment_eval_grain_size) {
1194 evaluate_unknown_segment(
bounds, memory, r_evaluated_segments);
1207 unknown_segment_eval_grain_size,
1209 LocalData &data = data_by_thread.local();
1210 for (const IndexRange &bounds : short_unknown_segments.slice(range)) {
1211 evaluate_unknown_segment(bounds, data.allocator, data.evaluated_segments);
1214 for (LocalData &
data : data_by_thread) {
1215 if (!
data.evaluated_segments.is_empty()) {
1216 r_evaluated_segments.
extend(
data.evaluated_segments);
1226 if (evaluated_segments.
is_empty()) {
1229 if (evaluated_segments.
size() == 1) {
1231 switch (evaluated_segment.
type) {
1267 root_expression, eval_order, evaluated_segments, short_unknown_segments);
1271 short_unknown_segments,
1273 evaluated_segments);
1297 for (
const Term &term : terms) {
1298 term_expressions.
append(&this->term_to_expr(term));
1302 expr.
index = expr_count_++;
1303 expr.
terms = std::move(term_expressions);
1310 term_expressions.
append(&this->term_to_expr(main_term));
1311 for (
const Term &subtract_term : subtract_terms) {
1312 term_expressions.
append(&this->term_to_expr(subtract_term));
1316 expr.
index = expr_count_++;
1317 expr.
terms = std::move(term_expressions);
1324 for (
const Term &term : terms) {
1325 term_expressions.
append(&this->term_to_expr(term));
1329 expr.
index += expr_count_++;
1330 expr.
terms = std::move(term_expressions);
1334const Expr &ExprBuilder::term_to_expr(
const Term &term)
1336 if (
const Expr *
const *expr = std::get_if<const Expr *>(&term)) {
1339 AtomicExpr &expr = scope_.construct<AtomicExpr>();
1340 expr.
type = Expr::Type::Atomic;
1341 expr.index = expr_count_++;
1342 if (
const IndexRange *range = std::get_if<IndexRange>(&term)) {
1343 expr.mask = &scope_.construct<
IndexMask>(*range);
1346 expr.mask = std::get<const IndexMask *>(term);
constexpr int64_t one_after_last() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t size() const
constexpr bool is_empty() const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange with_new_end(const int64_t new_end) const
constexpr IndexRange()=default
static constexpr IndexRange from_begin_size(const int64_t begin, const int64_t size)
constexpr int64_t start() const
constexpr IndexRange take_front(int64_t n) const
constexpr IndexRange drop_front(int64_t n) const
MutableSpan< T > allocate_array(int64_t size)
void free_end_of_previous_allocation(const int64_t original_allocation_size, const void *free_after)
MutableSpan< T > construct_array_copy(Span< T > src)
void transfer_ownership_from(LinearAllocator<> &other)
constexpr int64_t size() const
constexpr bool is_empty() const
constexpr T * data() const
constexpr int64_t size_in_bytes() const
constexpr const T * data() const
constexpr int64_t size() const
constexpr IndexRange index_range() const
constexpr bool is_empty() const
void push(const T &value)
void append(const T &value)
void remove_first_occurrence_and_reorder(const T &value)
IndexRange index_range() const
void append_unchecked(const T &value)
void extend(Span< T > array)
std::variant< const Expr *, const IndexMask *, IndexRange > Term
const IntersectionExpr & intersect(const Span< Term > terms)
const UnionExpr & merge(const Span< Term > terms)
const DifferenceExpr & subtract(const Term &main_term, const Span< Term > subtract_terms)
IndexMaskSegment shift(const int64_t shift) const
IndexMaskSegment(const OffsetSpan< int64_t, int16_t > span)
static IndexMask from_segments(Span< IndexMaskSegment > segments, LinearAllocator<> &memory)
IndexMask slice_content(IndexRange range) const
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
void mix_into_first_expr(ExprFn &&expr, FirstBitSpanT &&first_arg, const BitSpanT &...args)
void copy_from_or(FirstBitSpanT &first_arg, const BitSpanT &...args)
void foreach_1_index(const BitSpanT &data, Fn &&fn)
static CoarseSegment & add_coarse_segment__full(CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult &result)
static IndexMaskSegment evaluate_exact_with_indices(const Expr &root_expression, LinearAllocator<> &allocator, const IndexRange bounds, const Span< const Expr * > eval_order)
static void evaluate_coarse_and_split_until_segments_are_short(const Expr &root_expression, const Span< const Expr * > eval_order, Vector< EvaluatedSegment, 16 > &r_evaluated_segments, Vector< IndexRange, 16 > &r_short_unknown_segments)
static IndexMaskSegment union_index_mask_segments(const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t *r_values)
static constexpr int64_t segment_size_threshold
IndexMask evaluate_expression(const Expr &expression, LinearAllocator<> &memory)
static IndexMask evaluate_expression_impl(const Expr &root_expression, LinearAllocator<> &memory, const ExactEvalMode exact_eval_mode)
static void sort_course_boundaries(MutableSpan< CourseBoundary > boundaries)
static ExactEvalMode determine_exact_eval_mode(const Expr &root_expression)
static CoarseResult evaluate_coarse(const Expr &root_expression, const Span< const Expr * > eval_order, const std::optional< IndexRange > eval_bounds=std::nullopt)
static IndexMaskSegment evaluate_exact_with_bits(const Expr &root_expression, LinearAllocator<> &allocator, const IndexRange bounds, const Span< const Expr * > eval_order)
static void evaluate_short_unknown_segments_exactly(const Expr &root_expression, const ExactEvalMode exact_eval_mode, const Span< const Expr * > eval_order, const Span< IndexRange > short_unknown_segments, LinearAllocator<> &memory, Vector< EvaluatedSegment, 16 > &r_evaluated_segments)
void index_range_to_mask_segments(const IndexRange range, Vector< IndexMaskSegment, N > &r_segments)
static Span< int16_t > bits_to_indices(const BoundedBitSpan bits, LinearAllocator<> &allocator)
static Vector< const Expr *, inline_expr_array_size > compute_eval_order(const Expr &root_expression)
static IndexMaskSegment intersect_index_mask_segments(const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t *r_values)
static CoarseSegment & add_coarse_segment__unknown(CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult &result)
static IndexMask evaluated_segments_to_index_mask(MutableSpan< EvaluatedSegment > evaluated_segments, LinearAllocator<> &memory)
static Vector< IndexMaskSegment > build_result_mask_segments(const Span< EvaluatedSegment > evaluated_segments)
static void evaluate_coarse_difference(const Span< DifferenceCourseBoundary > boundaries, CoarseResult &r_result)
static CoarseSegment & add_coarse_segment__copy(CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, const IndexMask ©_from_mask, CoarseResult &result)
static IndexMaskSegment difference_index_mask_segments(const IndexMaskSegment main_segment, const Span< IndexMaskSegment > subtract_segments, const int64_t bounds_min, int16_t *r_values)
static void evaluate_coarse_intersection(const Span< CourseBoundary > boundaries, const int64_t terms_num, CoarseResult &r_result)
static void evaluate_coarse_union(const Span< CourseBoundary > boundaries, CoarseResult &r_result)
constexpr int64_t inline_expr_array_size
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
BMesh const char void * data
constexpr IntT ceil_division(const IntT x, const IntT y)
Vector< CoarseSegment > segments
const CoarseSegment * segment
const IndexMask * copy_mask
const DifferenceExpr & as_difference() const
const IntersectionExpr & as_intersection() const
const AtomicExpr & as_atomic() const
int expression_array_size() const
const UnionExpr & as_union() const
Vector< const Expr * > terms