vyre_libs/
range_ordering.rs

1//! Domain-neutral byte-range ordering predicates.
2//!
3//! These helpers build IR for relations between tagged byte-range streams.
4//! They use the scanner output contract's `counts`, `offsets`, and `lengths`
5//! buffer names.
6
7use vyre_foundation::ir::{Expr, Node};
8
9/// Maximum number of cached positions per tagged range. Matches the
10/// source-query dialect scanner-side cap.
11pub const MAX_CACHED_POSITIONS: u32 = 256;
12
13/// Maximum logical "depth" used by the same scanner-side convention.
14pub const MAX_DEPTH: u32 = 12;
15
16/// Helper to read the element of a packed 2D array laid out as
17/// `buffer[id * MAX_CACHED_POSITIONS + index]`.
18fn packed_load(buffer: &str, id: Expr, index: Expr) -> Expr {
19    Expr::load(
20        buffer,
21        Expr::add(Expr::mul(id, Expr::u32(MAX_CACHED_POSITIONS)), index),
22    )
23}
24
25/// Generate a loop block deciding whether any range tagged `left_id`
26/// ends at or before some range tagged `right_id` begins.
27///
28/// Returns `(Vec<Node>, Expr)` where the expression is the boolean
29/// result bound to an internal `let` variable named `<res_name>_found`.
30///
31/// The emitted block assumes the enclosing IR provides three storage
32/// buffers: `counts[tag]` (how many ranges carry that tag), and
33/// `offsets[tag * MAX_CACHED_POSITIONS + i]` + `lengths[tag * MAX_CACHED_POSITIONS + i]`.
34///
35/// AUDIT: PHASE5_ASTWALK match_order quadratic  -  replaced nested O(N²)
36/// loops with a sweep-line O(N) pass.  The hit positions for each tag
37/// are guaranteed to be sorted by ascending offset by the host scanner
38/// (see `downstream analyzer::scan::collector::select_hits_for_dispatch`).  Because
39/// the inputs are sorted, the predicate `∃ a ∈ A, ∃ b ∈ B : a_end <=
40/// b_start` is equivalent to `min_a_end <= max_b_start`.  We compute
41/// `min_a_end` with a single linear scan over A and read `max_b_start`
42/// directly from the last element of B (the largest offset).  Inner
43/// work is O(N) with N ≤ MAX_CACHED_POSITIONS = 256, versus the prior
44/// 65 536 iterations per workgroup lane.
45#[must_use]
46pub fn match_order(left_id: Expr, right_id: Expr, res_name: &str) -> (Vec<Node>, Expr) {
47    let mut block = Vec::new();
48
49    let limit_a = Expr::load("counts", left_id.clone());
50    let clamped_limit_a = Expr::select(
51        Expr::gt(limit_a.clone(), Expr::u32(MAX_CACHED_POSITIONS)),
52        Expr::u32(MAX_CACHED_POSITIONS),
53        limit_a,
54    );
55
56    let limit_b = Expr::load("counts", right_id.clone());
57    let clamped_limit_b = Expr::select(
58        Expr::gt(limit_b.clone(), Expr::u32(MAX_CACHED_POSITIONS)),
59        Expr::u32(MAX_CACHED_POSITIONS),
60        limit_b,
61    );
62
63    block.push(Node::let_bind(format!("{res_name}_len_a"), clamped_limit_a));
64    block.push(Node::let_bind(format!("{res_name}_len_b"), clamped_limit_b));
65
66    // Compute min_a_end across all valid A positions.
67    block.push(Node::let_bind(
68        format!("{res_name}_min_a_end"),
69        Expr::u32(u32::MAX),
70    ));
71
72    let scan_a_loop = Node::loop_for(
73        "i",
74        Expr::u32(0),
75        Expr::var(format!("{res_name}_len_a").as_str()),
76        vec![
77            Node::let_bind(
78                "a_start",
79                packed_load("offsets", left_id.clone(), Expr::var("i")),
80            ),
81            Node::let_bind(
82                "a_len",
83                packed_load("lengths", left_id.clone(), Expr::var("i")),
84            ),
85            Node::let_bind("a_end", Expr::add(Expr::var("a_start"), Expr::var("a_len"))),
86            Node::assign(
87                format!("{res_name}_min_a_end"),
88                Expr::select(
89                    Expr::lt(
90                        Expr::var("a_end"),
91                        Expr::var(format!("{res_name}_min_a_end")),
92                    ),
93                    Expr::var("a_end"),
94                    Expr::var(format!("{res_name}_min_a_end")),
95                ),
96            ),
97        ],
98    );
99    block.push(scan_a_loop);
100
101    // B is sorted by offset, so max_b_start is the last valid element.
102    let max_b_start = Expr::select(
103        Expr::gt(
104            Expr::var(format!("{res_name}_len_b").as_str()),
105            Expr::u32(0),
106        ),
107        packed_load(
108            "offsets",
109            right_id.clone(),
110            Expr::sub(
111                Expr::var(format!("{res_name}_len_b").as_str()),
112                Expr::u32(1),
113            ),
114        ),
115        Expr::u32(0),
116    );
117    block.push(Node::let_bind(
118        format!("{res_name}_max_b_start"),
119        max_b_start,
120    ));
121
122    // Found iff both sides are non-empty and the earliest-ending A
123    // ends at or before the latest-starting B begins.
124    let both_non_empty = Expr::and(
125        Expr::gt(
126            Expr::var(format!("{res_name}_len_a").as_str()),
127            Expr::u32(0),
128        ),
129        Expr::gt(
130            Expr::var(format!("{res_name}_len_b").as_str()),
131            Expr::u32(0),
132        ),
133    );
134    block.push(Node::let_bind(
135        format!("{res_name}_found"),
136        Expr::select(
137            both_non_empty,
138            Expr::select(
139                Expr::le(
140                    Expr::var(format!("{res_name}_min_a_end").as_str()),
141                    Expr::var(format!("{res_name}_max_b_start").as_str()),
142                ),
143                Expr::u32(1),
144                Expr::u32(0),
145            ),
146            Expr::u32(0),
147        ),
148    ));
149
150    (block, Expr::var(format!("{res_name}_found")))
151}
vyre_libs/range_ordering.rs

vyre_libs/
range_ordering.rs
