use std::collections::{HashMap, HashSet, VecDeque};
#[cfg(feature = "cubecl")]
use std::sync::mpsc;
use std::sync::Arc;
#[cfg(feature = "cubecl")]
use std::sync::Mutex;
#[cfg(feature = "cubecl")]
use std::time::Instant;
use eframe::egui;
use eframe::egui::{pos2, vec2, Align2, Rect, Response, Sense, Stroke, TextStyle, Ui};
#[cfg(feature = "cubecl")]
use cubecl::prelude::*;
#[cfg(feature = "cubecl")]
use cubecl::server::Handle as CubeHandle;
#[cfg(feature = "cubecl")]
use cubecl::wgpu::{WgpuDevice, WgpuRuntime};
use triblespace::core::blob::schemas::longstring::LongString;
use triblespace::core::blob::schemas::wasmcode::WasmCode;
use triblespace::core::blob::BlobCache;
use triblespace::core::id::Id;
use triblespace::core::query::TriblePattern;
use triblespace::core::repo::BlobStoreGet;
use triblespace::core::value::schemas::hash::{Blake3, Handle};
use triblespace::core::value::schemas::UnknownValue;
use triblespace::core::value::Value;
use triblespace::core::value_formatter::{WasmLimits, WasmValueFormatter};
use triblespace::prelude::valueschemas::GenId;
use triblespace::prelude::{find, pattern, ConstId, TribleSet, TribleSetFingerprint, View};
use crate::themes;
fn hex_prefix(bytes: impl AsRef<[u8]>, prefix_len: usize) -> String {
let bytes = bytes.as_ref();
let prefix_len = prefix_len.min(bytes.len());
let mut out = String::with_capacity(prefix_len * 2);
for byte in bytes.iter().take(prefix_len) {
out.push_str(&format!("{byte:02X}"));
}
out
}
pub fn id_short(id: Id) -> String {
let bytes: &[u8] = id.as_ref();
hex_prefix(bytes, 4)
}
pub fn id_full(id: Id) -> String {
let bytes: &[u8] = id.as_ref();
hex_prefix(bytes, 16)
}
fn try_decode_genid(raw: &[u8; 32]) -> Option<Id> {
let v = triblespace::core::value::Value::<GenId>::new(*raw);
let parsed: Result<Id, _> = v.try_from_value();
parsed.ok()
}
fn paint_hatching(painter: &egui::Painter, rect: Rect, color: egui::Color32) {
let spacing = 8.0;
let stroke = Stroke::new(1.0, color);
let h = rect.height();
let mut x = rect.left() - h;
while x < rect.right() + h {
painter.line_segment([pos2(x, rect.top()), pos2(x + h, rect.bottom())], stroke);
x += spacing;
}
}
#[derive(Clone, Debug)]
struct EntityRow {
attr_id: Id,
attr: String,
value: String,
target: Option<Id>,
hatched: bool,
}
#[derive(Clone, Debug)]
struct EntityNode {
id: Id,
title: String,
rows: Vec<EntityRow>,
}
#[derive(Clone, Debug)]
struct EntityEdge {
from_entity: usize,
from_row: usize,
to_entity: usize,
attr_id: Id,
}
#[derive(Debug)]
struct EntityGraph {
nodes: Vec<EntityNode>,
edges: Vec<EntityEdge>,
id_to_index: HashMap<Id, usize>,
}
#[derive(Clone, Debug)]
struct AttrInfo {
label: String,
schema: Option<Id>,
formatter: Option<Value<Handle<Blake3, WasmCode>>>,
}
fn build_attr_info<B>(
metadata: &TribleSet,
name_cache: &BlobCache<B, Blake3, LongString, View<str>>,
) -> HashMap<Id, AttrInfo>
where
B: BlobStoreGet<Blake3>,
{
let mut labels = HashMap::<Id, String>::new();
for (attr, name_handle) in find!(
(attr: Id, name_handle: Value<Handle<Blake3, LongString>>),
pattern!(metadata, [{ ?attr @ triblespace::core::metadata::name: ?name_handle }])
) {
if let Ok(name) = name_cache.get(name_handle) {
labels.insert(attr, name.as_ref().to_string());
}
}
for (usage, attr, name_handle) in find!(
(usage: Id, attr: Id, name_handle: Value<Handle<Blake3, LongString>>),
pattern!(metadata, [
{ ?usage @ triblespace::core::metadata::attribute: ?attr },
{ ?usage @ triblespace::core::metadata::tag: triblespace::core::metadata::KIND_ATTRIBUTE_USAGE },
{ ?usage @ triblespace::core::metadata::name: ?name_handle },
])
) {
let _ = usage;
if labels.contains_key(&attr) {
continue;
}
if let Ok(name) = name_cache.get(name_handle) {
labels.insert(attr, name.as_ref().to_string());
}
}
let mut schema_by_attr = HashMap::<Id, Id>::new();
for (attr, schema) in find!(
(attr: Id, schema: Id),
pattern!(metadata, [{ ?attr @ triblespace::core::metadata::value_schema: ?schema }])
) {
schema_by_attr.insert(attr, schema);
}
let mut formatter_by_schema = HashMap::<Id, Value<Handle<Blake3, WasmCode>>>::new();
for (schema, formatter) in find!(
(schema: Id, formatter: Value<Handle<Blake3, WasmCode>>),
pattern!(metadata, [{ ?schema @ triblespace::core::metadata::value_formatter: ?formatter }])
) {
formatter_by_schema.insert(schema, formatter);
}
let mut out = HashMap::<Id, AttrInfo>::new();
for (attr, schema) in schema_by_attr {
let label = labels
.remove(&attr)
.unwrap_or_else(|| format!("attr:{}", id_short(attr)));
let formatter = formatter_by_schema.get(&schema).copied();
out.insert(
attr,
AttrInfo {
label,
schema: Some(schema),
formatter,
},
);
}
for (attr, label) in labels {
out.entry(attr).or_insert(AttrInfo {
label,
schema: None,
formatter: None,
});
}
out
}
fn build_entity_graph<B>(
data: &TribleSet,
metadata: &TribleSet,
name_cache: &BlobCache<B, Blake3, LongString, View<str>>,
formatter_cache: &BlobCache<B, Blake3, WasmCode, WasmValueFormatter>,
) -> EntityGraph
where
B: BlobStoreGet<Blake3>,
{
let attr_info = build_attr_info(metadata, name_cache);
let limits = WasmLimits::default();
let schema_genid = GenId::ID;
let mut entity_ids = HashSet::<Id>::new();
let mut tribles = Vec::<(Id, Id, [u8; 32])>::new();
for (e, a, v) in find!((e: Id, a: Id, v: Value<UnknownValue>), data.pattern(e, a, v)) {
entity_ids.insert(e);
if let Some(info) = attr_info.get(&a) {
if info.schema == Some(schema_genid) {
if let Some(target) = try_decode_genid(&v.raw) {
entity_ids.insert(target);
}
}
}
tribles.push((e, a, v.raw));
}
let mut entities: Vec<Id> = entity_ids.into_iter().collect();
entities.sort_by(|a, b| {
let a: &[u8] = a.as_ref();
let b: &[u8] = b.as_ref();
a.cmp(b)
});
let mut id_to_index = HashMap::with_capacity(entities.len());
for (idx, id) in entities.iter().copied().enumerate() {
id_to_index.insert(id, idx);
}
let mut raw_rows = vec![Vec::<EntityRow>::new(); entities.len()];
for (e, attr, raw) in tribles {
let Some(entity_index) = id_to_index.get(&e).copied() else {
continue;
};
let info = attr_info.get(&attr);
let attr_text = info
.map(|info| info.label.clone())
.unwrap_or_else(|| format!("attr:{}", id_short(attr)));
let (value_text, target, hatched) = match info {
Some(info) if info.schema == Some(schema_genid) => {
if let Some(target) = try_decode_genid(&raw) {
(format!("id:{}", id_short(target)), Some(target), false)
} else {
(format!("id:0x{}", hex_prefix(raw, 6)), None, false)
}
}
Some(info) => match info
.formatter
.and_then(|handle| formatter_cache.get(handle).ok())
{
Some(formatter) => match formatter.format_value_with_limits(&raw, limits) {
Ok(text) => (text, None, false),
Err(_) => (format!("0x{}", hex_prefix(raw, 6)), None, true),
},
None => (format!("0x{}", hex_prefix(raw, 6)), None, true),
},
None => (format!("0x{}", hex_prefix(raw, 6)), None, true),
};
raw_rows[entity_index].push(EntityRow {
attr_id: attr,
attr: attr_text,
value: value_text,
target,
hatched,
});
}
let mut titles = HashMap::<Id, String>::new();
for (entity_idx, entity_id) in entities.iter().copied().enumerate() {
for row in &raw_rows[entity_idx] {
if row.attr == "name" && !row.hatched {
titles.insert(entity_id, row.value.clone());
break;
}
}
}
let mut nodes = Vec::with_capacity(entities.len());
for (idx, id) in entities.iter().copied().enumerate() {
let title = titles
.get(&id)
.cloned()
.unwrap_or_else(|| format!("id:{}", id_short(id)));
let mut rows = raw_rows[idx].clone();
rows.sort_by(|a, b| {
a.attr
.cmp(&b.attr)
.then_with(|| a.hatched.cmp(&b.hatched))
.then_with(|| a.value.cmp(&b.value))
});
nodes.push(EntityNode { id, title, rows });
}
let mut edges = Vec::new();
for (from_entity, node) in nodes.iter().enumerate() {
for (from_row, row) in node.rows.iter().enumerate() {
let Some(target) = row.target else {
continue;
};
let Some(&to_entity) = id_to_index.get(&target) else {
continue;
};
edges.push(EntityEdge {
from_entity,
from_row,
to_entity,
attr_id: row.attr_id,
});
}
}
EntityGraph {
nodes,
edges,
id_to_index,
}
}
#[derive(Clone)]
struct EntityGraphCache {
data_fingerprint: TribleSetFingerprint,
metadata_fingerprint: TribleSetFingerprint,
graph: Option<Arc<EntityGraph>>,
}
impl Default for EntityGraphCache {
fn default() -> Self {
Self {
data_fingerprint: TribleSetFingerprint::EMPTY,
metadata_fingerprint: TribleSetFingerprint::EMPTY,
graph: None,
}
}
}
fn cached_entity_graph<B>(
ui: &mut Ui,
cache_id: egui::Id,
data: &TribleSet,
metadata: &TribleSet,
name_cache: &BlobCache<B, Blake3, LongString, View<str>>,
formatter_cache: &BlobCache<B, Blake3, WasmCode, WasmValueFormatter>,
) -> Arc<EntityGraph>
where
B: BlobStoreGet<Blake3>,
{
let data_fingerprint = data.fingerprint();
let metadata_fingerprint = metadata.fingerprint();
ui.data_mut(|memory| {
let cache = memory.get_temp_mut_or_default::<EntityGraphCache>(cache_id);
let needs_rebuild = cache.graph.is_none()
|| cache.data_fingerprint != data_fingerprint
|| cache.metadata_fingerprint != metadata_fingerprint;
if needs_rebuild {
cache.graph = Some(Arc::new(build_entity_graph(
data,
metadata,
name_cache,
formatter_cache,
)));
cache.data_fingerprint = data_fingerprint;
cache.metadata_fingerprint = metadata_fingerprint;
}
cache
.graph
.as_ref()
.expect("entity graph cache missing")
.clone()
})
}
#[derive(Clone, Debug)]
struct ComponentLayout {
column_free: Vec<Vec<(f32, f32)>>,
}
#[derive(Clone, Debug)]
struct GraphLayout {
canvas_size: egui::Vec2,
column_count: usize,
column_gap: f32,
tile_padding: f32,
header_height: f32,
text_row_height: f32,
tile_rects: Vec<Rect>,
components: Vec<ComponentLayout>,
node_component: Vec<usize>,
node_column: Vec<usize>,
}
fn build_adjacency(graph: &EntityGraph) -> Vec<Vec<usize>> {
let mut adj = vec![Vec::<usize>::new(); graph.nodes.len()];
for edge in &graph.edges {
adj[edge.from_entity].push(edge.to_entity);
adj[edge.to_entity].push(edge.from_entity);
}
adj
}
fn connected_components(adjacency: &[Vec<usize>]) -> Vec<Vec<usize>> {
let mut visited = vec![false; adjacency.len()];
let mut components = Vec::new();
for start in 0..adjacency.len() {
if visited[start] {
continue;
}
visited[start] = true;
let mut queue = VecDeque::new();
queue.push_back(start);
let mut component = vec![start];
while let Some(node) = queue.pop_front() {
for &next in &adjacency[node] {
if !visited[next] {
visited[next] = true;
queue.push_back(next);
component.push(next);
}
}
}
component.sort_unstable();
components.push(component);
}
components.sort_by_key(|component| component[0]);
components
}
fn compute_graph_layout(
ui: &Ui,
graph: &EntityGraph,
forced_columns: usize,
order: &[usize],
) -> GraphLayout {
let column_gap = 48.0;
let outer_x_pad = column_gap;
let min_tile_width = 160.0;
let desired_tile_width = 220.0;
let max_tile_width = 260.0;
let usable_width = (ui.available_width() - outer_x_pad * 2.0).max(min_tile_width);
let mut column_count = if forced_columns == 0 {
((usable_width + column_gap) / (desired_tile_width + column_gap)).floor() as usize
} else {
forced_columns
};
column_count = column_count.max(1).min(graph.nodes.len().max(1));
let tile_width = loop {
if column_count == 1 {
break ui.available_width().clamp(180.0, 520.0);
}
let raw = (usable_width - column_gap * ((column_count - 1) as f32)) / column_count as f32;
if raw >= min_tile_width {
break raw.clamp(min_tile_width, max_tile_width);
}
if forced_columns != 0 {
break raw.max(1.0);
}
column_count = column_count.saturating_sub(1).max(1);
};
let tile_padding = 8.0;
let title_font = TextStyle::Monospace.resolve(ui.style());
let row_font = TextStyle::Small.resolve(ui.style());
let header_height = ui.fonts_mut(|fonts| fonts.row_height(&title_font)).ceil() + 6.0;
let text_row_height = ui.fonts_mut(|fonts| fonts.row_height(&row_font)).ceil() + 4.0;
let mut tile_heights = vec![0.0f32; graph.nodes.len()];
for (idx, node) in graph.nodes.iter().enumerate() {
let rows = node.rows.len().max(1);
tile_heights[idx] = tile_padding * 2.0 + header_height + text_row_height * rows as f32;
}
let row_gap = 24.0;
let top_pad = row_gap;
let bottom_pad = row_gap;
let clearance = 4.0;
let node_count = graph.nodes.len();
let mut tile_rects = vec![Rect::NOTHING; node_count];
let node_component = vec![0usize; node_count];
let mut node_column = vec![usize::MAX; node_count];
let mut column_bottoms = vec![top_pad; column_count];
let mut column_nodes = vec![Vec::<usize>::new(); column_count];
for &node_idx in order {
let (col, y) = column_bottoms
.iter()
.copied()
.enumerate()
.min_by(|(a_idx, a_y), (b_idx, b_y)| {
a_y.partial_cmp(b_y)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| a_idx.cmp(b_idx))
})
.unwrap_or((0, top_pad));
let x = outer_x_pad + col as f32 * (tile_width + column_gap);
let rect = Rect::from_min_size(pos2(x, y), vec2(tile_width, tile_heights[node_idx]));
tile_rects[node_idx] = rect;
node_column[node_idx] = col;
column_nodes[col].push(node_idx);
column_bottoms[col] = y + tile_heights[node_idx] + row_gap;
}
for bottom in &mut column_bottoms {
if *bottom > top_pad {
*bottom -= row_gap;
}
}
let content_height = column_bottoms.into_iter().fold(top_pad, f32::max);
let canvas_height = (content_height + bottom_pad).max(top_pad + bottom_pad);
let canvas_width = outer_x_pad * 2.0
+ tile_width * column_count as f32
+ column_gap * (column_count.saturating_sub(1) as f32);
let mut column_free = Vec::with_capacity(column_count);
for nodes in &column_nodes {
let mut intervals = Vec::new();
let mut cursor = 0.0f32;
for &node_idx in nodes {
let rect = tile_rects[node_idx];
let top = (rect.top() - clearance).max(0.0);
if top > cursor {
intervals.push((cursor, top));
}
cursor = (rect.bottom() + clearance).max(cursor);
}
if cursor < canvas_height {
intervals.push((cursor, canvas_height));
}
if intervals.is_empty() {
intervals.push((0.0, canvas_height));
}
column_free.push(intervals);
}
let component_layout = ComponentLayout { column_free };
GraphLayout {
canvas_size: vec2(canvas_width, canvas_height),
column_count,
column_gap,
tile_padding,
header_height,
text_row_height,
tile_rects,
components: vec![component_layout],
node_component,
node_column,
}
}
#[derive(Clone, Debug, Default)]
pub struct EntityInspectorStats {
pub nodes: usize,
pub edges: usize,
pub connected_components: usize,
pub columns: usize,
pub canvas_width: f32,
pub canvas_height: f32,
pub tile_coverage: f32,
pub total_edge_len: f32,
pub avg_edge_len: f32,
pub max_edge_len: f32,
pub avg_turns: f32,
pub max_turns: usize,
pub avg_span_cols: f32,
pub max_span_cols: usize,
pub left_edges: usize,
pub fallback_tracks: usize,
pub linear_total: f32,
pub linear_avg: f32,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum EntityOrder {
Id,
#[cfg(feature = "cubecl")]
Anneal,
}
pub struct EntityInspectorResponse {
pub response: egui::Response,
pub stats: EntityInspectorStats,
pub selection_changed: bool,
}
#[must_use = "Use `EntityInspectorWidget::show(ui)` to render this widget."]
pub struct EntityInspectorWidget<'a, B>
where
B: BlobStoreGet<Blake3>,
{
data: &'a TribleSet,
metadata: &'a TribleSet,
name_cache: &'a BlobCache<B, Blake3, LongString, View<str>>,
formatter_cache: &'a BlobCache<B, Blake3, WasmCode, WasmValueFormatter>,
selection: &'a mut Id,
columns: usize,
order: EntityOrder,
cache_id: Option<egui::Id>,
}
impl<'a, B> EntityInspectorWidget<'a, B>
where
B: BlobStoreGet<Blake3>,
{
pub fn new(
data: &'a TribleSet,
metadata: &'a TribleSet,
name_cache: &'a BlobCache<B, Blake3, LongString, View<str>>,
formatter_cache: &'a BlobCache<B, Blake3, WasmCode, WasmValueFormatter>,
selection: &'a mut Id,
) -> Self {
#[cfg(feature = "cubecl")]
let order = EntityOrder::Anneal;
#[cfg(not(feature = "cubecl"))]
let order = EntityOrder::Id;
Self {
data,
metadata,
name_cache,
formatter_cache,
selection,
columns: 0,
order,
cache_id: None,
}
}
pub fn columns(mut self, columns: usize) -> Self {
self.columns = columns;
self
}
pub fn order(mut self, order: EntityOrder) -> Self {
self.order = order;
self
}
pub fn cache_id(mut self, cache_id: egui::Id) -> Self {
self.cache_id = Some(cache_id);
self
}
pub fn show(self, ui: &mut Ui) -> EntityInspectorResponse {
let data_fingerprint = self.data.fingerprint();
let metadata_fingerprint = self.metadata.fingerprint();
let cache_id = self.cache_id.unwrap_or_else(|| {
ui.id()
.with("entity_inspector_graph")
.with(data_fingerprint)
.with(metadata_fingerprint)
});
let graph = {
#[cfg(feature = "telemetry")]
let _graph_span = tracing::info_span!("entity_inspector_graph").entered();
cached_entity_graph(
ui,
cache_id,
self.data,
self.metadata,
self.name_cache,
self.formatter_cache,
)
};
let selection_before = *self.selection;
if let Some(first) = graph.nodes.first().map(|node| node.id) {
if !graph.id_to_index.contains_key(self.selection) {
*self.selection = first;
}
}
let (layout, routed_edges, stats) = {
#[cfg(feature = "telemetry")]
let _layout_span = tracing::info_span!("entity_inspector_layout").entered();
compute_inspector(ui, cache_id, graph.as_ref(), self.columns, self.order)
};
let response = {
#[cfg(feature = "telemetry")]
let _paint_span = tracing::info_span!("entity_inspector_paint").entered();
paint_entity_inspector(ui, graph.as_ref(), self.selection, &layout, &routed_edges)
};
let selection_changed = *self.selection != selection_before;
EntityInspectorResponse {
response,
stats,
selection_changed,
}
}
}
#[derive(Clone, Debug)]
struct RoutedEdge {
points: Vec<egui::Pos2>,
length: f32,
turns: usize,
span_cols: usize,
start_underline: Option<(egui::Pos2, egui::Pos2)>,
attr_id: Id,
from_entity: usize,
to_entity: usize,
go_left: bool,
used_fallback_track: bool,
}
#[derive(Clone, Debug)]
struct EdgeRender {
points: Vec<egui::Pos2>,
line_color: egui::Color32,
start_underline: Option<(egui::Pos2, egui::Pos2)>,
from_entity: usize,
to_entity: usize,
}
#[derive(Clone, Debug)]
struct EdgeDraft {
edge: EntityEdge,
source_rect: Rect,
go_left: bool,
start: egui::Pos2,
end: egui::Pos2,
min_col: usize,
max_col: usize,
start_boundary: i32,
end_boundary: i32,
start_gutter_center_x: f32,
end_gutter_center_x: f32,
component: usize,
}
type BundleKey = (Id, usize);
fn attribute_palette_index(attr: Id, palette_len: usize) -> usize {
if palette_len == 0 {
return 0;
}
let raw: [u8; 16] = *attr.as_ref();
let val = u128::from_le_bytes(raw);
let hash = (val ^ (val >> 64)) as u64;
(hash as usize) % palette_len
}
fn entity_order(
ui: &mut Ui,
cache_id: egui::Id,
graph: &EntityGraph,
order: EntityOrder,
) -> Vec<usize> {
#[cfg(not(feature = "cubecl"))]
let _ = (ui, cache_id);
match order {
EntityOrder::Id => (0..graph.nodes.len()).collect(),
#[cfg(feature = "cubecl")]
EntityOrder::Anneal => {
gpu_sa_order(ui, cache_id, graph).unwrap_or_else(|| (0..graph.nodes.len()).collect())
}
}
}
#[cfg(feature = "cubecl")]
#[derive(Clone)]
struct GpuSaProblem {
node_count: usize,
edges: Vec<(usize, usize)>,
edges_flat: Vec<u32>,
adj_offsets: Vec<u32>,
adj_list: Vec<u32>,
}
#[cfg(feature = "cubecl")]
impl GpuSaProblem {
fn from_graph(graph: &EntityGraph) -> Self {
let node_count = graph.nodes.len();
let edges: Vec<(usize, usize)> = graph
.edges
.iter()
.map(|edge| (edge.from_entity, edge.to_entity))
.collect();
let mut edges_flat = Vec::with_capacity(edges.len() * 2);
for (u, v) in &edges {
edges_flat.push(*u as u32);
edges_flat.push(*v as u32);
}
let mut degrees = vec![0usize; node_count];
for &(u, v) in &edges {
degrees[u] += 1;
degrees[v] += 1;
}
let mut adj_offsets = Vec::with_capacity(node_count + 1);
adj_offsets.push(0u32);
for i in 0..node_count {
adj_offsets.push(adj_offsets[i] + degrees[i] as u32);
}
let total_adj = *adj_offsets.last().unwrap_or(&0) as usize;
let mut adj_list = vec![0u32; total_adj];
let mut cursor: Vec<usize> = adj_offsets.iter().map(|&offset| offset as usize).collect();
for &(u, v) in &edges {
let idx = cursor[u];
adj_list[idx] = v as u32;
cursor[u] += 1;
let idx = cursor[v];
adj_list[idx] = u as u32;
cursor[v] += 1;
}
Self {
node_count,
edges,
edges_flat,
adj_offsets,
adj_list,
}
}
}
#[cfg(feature = "cubecl")]
#[derive(Clone, Default)]
struct GpuSaCache {
graph_ptr: usize,
order: Option<Vec<usize>>,
best_cost: Option<u32>,
receiver: Option<Arc<Mutex<mpsc::Receiver<GpuSaUpdate>>>>,
skipped: bool,
}
#[cfg(feature = "cubecl")]
#[derive(Clone, Debug)]
struct GpuSaUpdate {
order: Vec<usize>,
}
#[cfg(feature = "cubecl")]
const SA_DEFAULT_STEPS: u32 = 1000;
#[cfg(feature = "cubecl")]
const SA_MIN_STEPS: u32 = 1;
#[cfg(feature = "cubecl")]
const SA_MAX_STEPS: u32 = 20_000;
#[cfg(feature = "cubecl")]
const SA_TARGET_MS: u32 = 60;
#[cfg(feature = "cubecl")]
const SA_MAX_TOTAL_NODES: usize = 200_000;
#[cfg(feature = "cubecl")]
const SA_MAX_BATCH_SIZE: usize = 256;
#[cfg(feature = "cubecl")]
const SA_DEFAULT_TARGET_ACCEPTANCE: f32 = 0.3;
#[cfg(feature = "cubecl")]
const SA_DEFAULT_COOLING_ADJUST: f32 = 0.002;
#[cfg(feature = "cubecl")]
const SA_RESEED_PLATEAU_STEPS: u32 = 12_000;
#[cfg(feature = "cubecl")]
const SA_STOP_AFTER_PLATEAU_MS: u64 = 10_000;
#[cfg(feature = "cubecl")]
const SA_FLOOR_FRACTION: f32 = 0.25;
#[cfg(feature = "cubecl")]
const SEED_MIX: u32 = 0x9E37_79B9;
#[cfg(feature = "cubecl")]
const LCG_A: u32 = 1_664_525;
#[cfg(feature = "cubecl")]
const LCG_C: u32 = 1_013_904_223;
#[cfg(feature = "cubecl")]
const INV_U32_MAX_PLUS1: f32 = 1.0 / 4_294_967_296.0;
#[cfg(feature = "cubecl")]
const MIN_ANNEAL_TEMP: f32 = 0.001;
#[cfg(feature = "cubecl")]
#[derive(Clone, Copy, Debug)]
struct LcgRng {
state: u64,
}
#[cfg(feature = "cubecl")]
impl LcgRng {
fn new(seed: u64) -> Self {
Self { state: seed }
}
fn next_u32(&mut self) -> u32 {
self.state = self
.state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1);
(self.state >> 32) as u32
}
fn gen_range(&mut self, upper: usize) -> usize {
if upper == 0 {
return 0;
}
(self.next_u32() as usize) % upper
}
}
#[cfg(feature = "cubecl")]
fn seed_to_u32(seed: u64) -> u32 {
let low = seed as u32;
let high = (seed >> 32) as u32;
low ^ high.wrapping_mul(SEED_MIX)
}
#[cfg(feature = "cubecl")]
fn sa_batch_size(node_count: usize) -> usize {
let node_count = node_count.max(1);
let max_chains = SA_MAX_TOTAL_NODES / node_count;
max_chains.clamp(1, SA_MAX_BATCH_SIZE)
}
#[cfg(feature = "cubecl")]
fn adjust_steps_per_batch(current: u32, elapsed_ms: u128, target_ms: u32) -> u32 {
if elapsed_ms == 0 {
return current.saturating_mul(2).clamp(SA_MIN_STEPS, SA_MAX_STEPS);
}
let target = target_ms.max(1) as f64;
let elapsed = elapsed_ms as f64;
let ratio = target / elapsed;
if (0.9..=1.1).contains(&ratio) {
return current.clamp(SA_MIN_STEPS, SA_MAX_STEPS);
}
let factor = ratio.clamp(0.5, 2.0);
let next = (current as f64 * factor).round() as u32;
next.clamp(SA_MIN_STEPS, SA_MAX_STEPS)
}
#[cfg(feature = "cubecl")]
fn cost_cpu(order: &[usize], problem: &GpuSaProblem) -> u32 {
let mut positions = vec![0u32; problem.node_count.max(1)];
for (pos, &node) in order.iter().take(problem.node_count).enumerate() {
positions[node] = pos as u32;
}
let mut cost = 0u32;
for &(u, v) in &problem.edges {
let pu = positions[u];
let pv = positions[v];
cost += if pu > pv { pu - pv } else { pv - pu };
}
cost
}
#[cfg(feature = "cubecl")]
fn order_cost(graph: &EntityGraph, order: &[usize]) -> u32 {
let mut positions = vec![0u32; graph.nodes.len().max(1)];
for (pos, &node) in order.iter().take(graph.nodes.len()).enumerate() {
positions[node] = pos as u32;
}
let mut cost = 0u32;
for edge in &graph.edges {
let pu = positions[edge.from_entity];
let pv = positions[edge.to_entity];
cost += if pu > pv { pu - pv } else { pv - pu };
}
cost
}
#[cfg(feature = "cubecl")]
fn order_cost_checked(graph: &EntityGraph, order: &[usize]) -> Option<u32> {
let node_count = graph.nodes.len();
if order.len() != node_count {
return None;
}
let mut positions = vec![u32::MAX; node_count.max(1)];
for (pos, &node) in order.iter().enumerate() {
if node >= node_count {
return None;
}
if positions[node] != u32::MAX {
return None;
}
positions[node] = pos as u32;
}
let mut cost = 0u32;
for edge in &graph.edges {
let pu = positions[edge.from_entity];
let pv = positions[edge.to_entity];
cost += if pu > pv { pu - pv } else { pv - pu };
}
Some(cost)
}
#[cfg(feature = "cubecl")]
fn estimate_initial_temp(problem: &GpuSaProblem, seed: u64, target_acceptance: f32) -> f32 {
let node_count = problem.node_count.max(2);
let mut order: Vec<usize> = (0..node_count).collect();
let base_cost = cost_cpu(&order, problem);
let mut rng = LcgRng::new(seed ^ 0x9E37_79B9_7F4A_7C15);
let sample_count = node_count.min(64).max(8);
let mut sum_delta = 0u64;
let mut count = 0u32;
for _ in 0..sample_count {
let i = rng.gen_range(node_count);
let mut j = rng.gen_range(node_count - 1);
if j >= i {
j += 1;
}
order.swap(i, j);
let candidate_cost = cost_cpu(&order, problem);
order.swap(i, j);
if candidate_cost > base_cost {
sum_delta += (candidate_cost - base_cost) as u64;
count += 1;
}
}
let avg_delta = if count > 0 {
sum_delta as f32 / count as f32
} else {
1.0
};
let target = target_acceptance.clamp(0.05, 0.95);
let denom = -target.ln();
let temp = if denom > 0.0 {
avg_delta / denom
} else {
avg_delta
};
temp.clamp(0.1, 100_000.0)
}
#[cfg(feature = "cubecl")]
fn sa_seed(problem: &GpuSaProblem) -> u64 {
use std::hash::{Hash, Hasher};
let mut hasher = std::collections::hash_map::DefaultHasher::new();
problem.node_count.hash(&mut hasher);
problem.edges.len().hash(&mut hasher);
for edge in problem.edges.iter().take(1024) {
edge.hash(&mut hasher);
}
hasher.finish()
}
#[cfg(feature = "cubecl")]
struct GpuSaConfig {
seed: u64,
initial_temp: f32,
temp_floor: f32,
cooling_adjust: f32,
reseed_plateau_steps: u32,
}
#[cfg(feature = "cubecl")]
struct GpuSaBatch {
best_cost: u32,
best_index: usize,
elapsed_ms: u128,
}
#[cfg(feature = "cubecl")]
struct GpuSaRunnerState<R: Runtime> {
_device: R::Device,
client: ComputeClient<R>,
_edges_handle: CubeHandle,
adj_offsets_handle: CubeHandle,
adj_list_handle: CubeHandle,
adj_list_len: usize,
node_count: usize,
batch_size: usize,
best_cost: u32,
best_version: u32,
orders_handle: CubeHandle,
positions_handle: CubeHandle,
best_orders_handle: CubeHandle,
current_costs_handle: CubeHandle,
best_orders_costs_handle: CubeHandle,
temp_floor_handle: CubeHandle,
rng_states_handle: CubeHandle,
stagnant_steps_handle: CubeHandle,
reseeded_handle: CubeHandle,
seed_versions_handle: CubeHandle,
}
#[cfg(feature = "cubecl")]
impl<R: Runtime> GpuSaRunnerState<R> {
fn new(
device: R::Device,
problem: &GpuSaProblem,
batch_size: usize,
config: &GpuSaConfig,
) -> Result<Self, String> {
if batch_size == 0 {
return Err("batch size must be > 0".to_string());
}
if problem.node_count == 0 {
return Err("graph must have at least one node".to_string());
}
let client = R::client(&device);
let edges_handle = client.create_from_slice(u32::as_bytes(&problem.edges_flat));
let adj_offsets_handle = client.create_from_slice(u32::as_bytes(&problem.adj_offsets));
let adj_list_handle = client.create_from_slice(u32::as_bytes(&problem.adj_list));
let order_len = match batch_size.checked_mul(problem.node_count) {
Some(len) if len > 0 => len,
_ => return Err("batch too large for graph size".to_string()),
};
let bytes_u32 = std::mem::size_of::<u32>();
let bytes_f32 = std::mem::size_of::<f32>();
let order_bytes = match order_len.checked_mul(bytes_u32) {
Some(bytes) => bytes,
None => return Err("order buffer too large".to_string()),
};
let batch_bytes_u32 = match batch_size.checked_mul(bytes_u32) {
Some(bytes) => bytes,
None => return Err("batch buffer too large".to_string()),
};
let batch_bytes_f32 = match batch_size.checked_mul(bytes_f32) {
Some(bytes) => bytes,
None => return Err("batch buffer too large".to_string()),
};
let orders_handle = client.empty(order_bytes);
let positions_handle = client.empty(order_bytes);
let best_orders_handle = client.empty(order_bytes);
let current_costs_handle = client.empty(batch_bytes_u32);
let best_orders_costs_handle = client.empty(batch_bytes_u32);
let temp_floor_handle = client.empty(batch_bytes_f32);
let rng_states_handle = client.empty(batch_bytes_u32);
let stagnant_steps_handle = client.empty(batch_bytes_u32);
let reseeded_handle = client.empty(batch_bytes_u32);
let seed_versions_handle = client.empty(batch_bytes_u32);
let seed32 = seed_to_u32(config.seed);
let initial_temp = config.initial_temp.max(MIN_ANNEAL_TEMP);
let floor_temp = config.temp_floor.max(MIN_ANNEAL_TEMP).min(initial_temp);
unsafe {
minla_sa_init_kernel::launch::<R>(
&client,
CubeCount::new_1d(batch_size as u32),
CubeDim::new_1d(1),
ArrayArg::from_raw_parts::<u32>(&edges_handle, problem.edges_flat.len(), 1),
ScalarArg::new(problem.node_count as u32),
ScalarArg::new(problem.edges.len() as u32),
ScalarArg::new(seed32),
ScalarArg::new(initial_temp),
ScalarArg::new(floor_temp),
ArrayArg::from_raw_parts::<u32>(&orders_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&positions_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&best_orders_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(¤t_costs_handle, batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&best_orders_costs_handle, batch_size, 1),
ArrayArg::from_raw_parts::<f32>(&temp_floor_handle, batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&rng_states_handle, batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&stagnant_steps_handle, batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&seed_versions_handle, batch_size, 1),
)
.expect("minla SA init kernel launch");
}
Ok(Self {
_device: device,
client,
_edges_handle: edges_handle,
adj_offsets_handle,
adj_list_handle,
adj_list_len: problem.adj_list.len(),
node_count: problem.node_count,
batch_size,
best_cost: u32::MAX,
best_version: 0,
orders_handle,
positions_handle,
best_orders_handle,
current_costs_handle,
best_orders_costs_handle,
temp_floor_handle,
rng_states_handle,
stagnant_steps_handle,
reseeded_handle,
seed_versions_handle,
})
}
fn run_steps(&mut self, steps: u32, config: &GpuSaConfig) -> Result<GpuSaBatch, String> {
let start = Instant::now();
let reheat_steps = config.reseed_plateau_steps.max(1);
let order_len = self.batch_size * self.node_count;
unsafe {
minla_sa_kernel::launch::<R>(
&self.client,
CubeCount::new_1d(self.batch_size as u32),
CubeDim::new_1d(1),
ArrayArg::from_raw_parts::<u32>(&self.adj_offsets_handle, self.node_count + 1, 1),
ArrayArg::from_raw_parts::<u32>(&self.adj_list_handle, self.adj_list_len, 1),
ScalarArg::new(self.node_count as u32),
ScalarArg::new(steps),
ScalarArg::new(config.cooling_adjust),
ScalarArg::new(reheat_steps),
ArrayArg::from_raw_parts::<u32>(&self.orders_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&self.positions_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&self.best_orders_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&self.current_costs_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<f32>(&self.temp_floor_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.best_orders_costs_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.rng_states_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.stagnant_steps_handle, self.batch_size, 1),
)
.expect("minla SA kernel launch");
}
let costs_bytes = self.client.read_one(self.best_orders_costs_handle.clone());
let costs = u32::from_bytes(&costs_bytes);
let mut best_cost = u32::MAX;
let mut best_index = 0usize;
for (idx, cost) in costs.iter().enumerate() {
if *cost < best_cost {
best_cost = *cost;
best_index = idx;
}
}
if best_cost != u32::MAX && best_cost < self.best_cost {
self.best_cost = best_cost;
self.best_version = self.best_version.saturating_add(1);
}
let reset_cap = config.initial_temp.max(MIN_ANNEAL_TEMP);
let reset_floor = config.temp_floor.max(MIN_ANNEAL_TEMP).min(reset_cap);
let stale_steps = if self.batch_size > 1 && best_cost != u32::MAX && self.node_count > 0 {
reheat_steps
} else {
0
};
unsafe {
minla_sa_reseed_kernel::launch::<R>(
&self.client,
CubeCount::new_1d(self.batch_size as u32),
CubeDim::new_1d(1),
ScalarArg::new(self.node_count as u32),
ScalarArg::new(best_index as u32),
ScalarArg::new(best_cost),
ScalarArg::new(stale_steps),
ScalarArg::new(self.best_version),
ScalarArg::new(reset_floor),
ArrayArg::from_raw_parts::<u32>(&self.orders_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&self.positions_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&self.best_orders_handle, order_len, 1),
ArrayArg::from_raw_parts::<u32>(&self.current_costs_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.best_orders_costs_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<f32>(&self.temp_floor_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.stagnant_steps_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.reseeded_handle, self.batch_size, 1),
ArrayArg::from_raw_parts::<u32>(&self.seed_versions_handle, self.batch_size, 1),
)
.expect("minla SA reseed kernel launch");
}
Ok(GpuSaBatch {
best_cost,
best_index,
elapsed_ms: start.elapsed().as_millis(),
})
}
fn read_best_order(&self, chain_index: usize) -> Vec<usize> {
let order_stride = self.node_count * std::mem::size_of::<u32>();
let offset_start = (chain_index * order_stride) as u64;
let offset_end = (self.batch_size.saturating_sub(chain_index + 1) * order_stride) as u64;
let handle = self
.best_orders_handle
.clone()
.offset_start(offset_start)
.offset_end(offset_end);
let order_bytes = self.client.read_one(handle);
let order = u32::from_bytes(&order_bytes);
order
.iter()
.take(self.node_count)
.map(|&val| val as usize)
.collect()
}
}
#[cfg(feature = "cubecl")]
fn gpu_sa_order(ui: &mut Ui, cache_id: egui::Id, graph: &EntityGraph) -> Option<Vec<usize>> {
if graph.nodes.is_empty() {
return Some(Vec::new());
}
let graph_ptr = graph as *const _ as usize;
let mut order_out = None;
let mut repaint = false;
ui.data_mut(|memory| {
let cache_id = cache_id.with("gpu_sa_order");
let cache = memory.get_temp_mut_or_default::<GpuSaCache>(cache_id);
if cache.graph_ptr != graph_ptr {
cache.graph_ptr = graph_ptr;
cache.order = None;
cache.best_cost = None;
cache.receiver = None;
cache.skipped = false;
}
if let Some(receiver) = cache.receiver.take() {
let mut latest = None;
let mut disconnected = false;
match receiver.lock() {
Ok(guard) => loop {
match guard.try_recv() {
Ok(update) => latest = Some(update),
Err(mpsc::TryRecvError::Empty) => break,
Err(mpsc::TryRecvError::Disconnected) => {
disconnected = true;
break;
}
}
},
Err(_) => {
disconnected = true;
}
}
if let Some(update) = latest {
if let Some(candidate_cost) = order_cost_checked(graph, &update.order) {
let improved = cache
.best_cost
.map(|best| candidate_cost < best)
.unwrap_or(true);
if improved {
cache.best_cost = Some(candidate_cost);
cache.order = Some(update.order);
repaint = true;
}
}
}
if disconnected {
cache.receiver = None;
cache.skipped = cache.order.is_none();
} else {
cache.receiver = Some(receiver);
}
}
if cache.order.is_none() && cache.receiver.is_none() && !cache.skipped {
let baseline: Vec<usize> = (0..graph.nodes.len()).collect();
cache.best_cost = Some(order_cost(graph, &baseline));
cache.order = Some(baseline);
if !graph.edges.is_empty() {
let problem = GpuSaProblem::from_graph(graph);
let (tx, rx) = mpsc::channel();
std::thread::spawn(move || {
gpu_sa_loop(problem, tx);
});
cache.receiver = Some(Arc::new(Mutex::new(rx)));
}
}
order_out = cache.order.clone();
});
if repaint {
ui.ctx().request_repaint();
}
order_out
}
#[cfg(feature = "cubecl")]
fn gpu_sa_loop(problem: GpuSaProblem, sender: mpsc::Sender<GpuSaUpdate>) {
let batch_size = sa_batch_size(problem.node_count);
let seed = sa_seed(&problem);
let initial_temp = estimate_initial_temp(&problem, seed, SA_DEFAULT_TARGET_ACCEPTANCE);
let floor_temp = (initial_temp * SA_FLOOR_FRACTION).max(MIN_ANNEAL_TEMP);
let config = GpuSaConfig {
seed,
initial_temp,
temp_floor: floor_temp,
cooling_adjust: SA_DEFAULT_COOLING_ADJUST,
reseed_plateau_steps: SA_RESEED_PLATEAU_STEPS,
};
let device = WgpuDevice::default();
let mut runner =
match GpuSaRunnerState::<WgpuRuntime>::new(device, &problem, batch_size, &config) {
Ok(runner) => runner,
Err(err) => {
eprintln!("gpu-sa: init failed: {err}");
return;
}
};
let mut best_cost = u32::MAX;
let mut steps = SA_DEFAULT_STEPS;
let mut plateau_ms = 0u64;
loop {
let batch = match runner.run_steps(steps, &config) {
Ok(batch) => batch,
Err(err) => {
eprintln!("gpu-sa: batch failed: {err}");
break;
}
};
if batch.best_cost < best_cost {
let order = runner.read_best_order(batch.best_index);
best_cost = batch.best_cost;
plateau_ms = 0;
if sender.send(GpuSaUpdate { order }).is_err() {
break;
}
} else {
let elapsed_ms = batch.elapsed_ms.min(u128::from(u64::MAX)) as u64;
plateau_ms = plateau_ms.saturating_add(elapsed_ms);
if plateau_ms >= SA_STOP_AFTER_PLATEAU_MS {
break;
}
}
steps = adjust_steps_per_batch(steps, batch.elapsed_ms, SA_TARGET_MS);
}
}
#[cfg(feature = "cubecl")]
#[cube(launch)]
fn minla_sa_init_kernel(
edges: &Array<u32>,
node_count: u32,
edge_count: u32,
seed: u32,
initial_temp: f32,
floor_temp: f32,
orders: &mut Array<u32>,
positions: &mut Array<u32>,
best_orders: &mut Array<u32>,
current_costs: &mut Array<u32>,
best_orders_costs: &mut Array<u32>,
temp_floors: &mut Array<f32>,
rng_states: &mut Array<u32>,
stagnant_steps: &mut Array<u32>,
seed_versions: &mut Array<u32>,
) {
let candidate = ABSOLUTE_POS;
let node_count = node_count as usize;
let edge_count = edge_count as usize;
let temp = initial_temp.max(MIN_ANNEAL_TEMP);
let floor_temp = floor_temp.max(MIN_ANNEAL_TEMP).min(temp);
if node_count == 0 {
current_costs[candidate] = 0;
best_orders_costs[candidate] = 0;
temp_floors[candidate] = floor_temp;
rng_states[candidate] = seed;
stagnant_steps[candidate] = 0;
seed_versions[candidate] = 0;
} else {
let mut state = seed ^ candidate as u32;
state = state * SEED_MIX;
let base = candidate * node_count;
for index in 0..node_count {
orders[base + index] = index as u32;
}
if node_count > 1 {
for i in 0..node_count {
state = state * LCG_A + LCG_C;
let remaining = node_count - i;
let j = (state % remaining as u32) as usize + i;
let left = base + i;
let right = base + j;
let tmp = orders[left];
orders[left] = orders[right];
orders[right] = tmp;
}
}
for pos in 0..node_count {
let node = orders[base + pos] as usize;
positions[base + node] = pos as u32;
}
let mut cost = 0u32;
for edge in 0..edge_count {
let edge_index = edge * 2;
let u = edges[edge_index] as usize;
let v = edges[edge_index + 1] as usize;
let pu = positions[base + u];
let pv = positions[base + v];
let diff = if pu > pv { pu - pv } else { pv - pu };
cost += diff;
}
current_costs[candidate] = cost;
best_orders_costs[candidate] = cost;
temp_floors[candidate] = floor_temp;
rng_states[candidate] = state;
stagnant_steps[candidate] = 0;
seed_versions[candidate] = 0;
for idx in 0..node_count {
best_orders[base + idx] = orders[base + idx];
}
}
}
#[cfg(feature = "cubecl")]
#[cube(launch)]
fn minla_sa_kernel(
adj_offsets: &Array<u32>,
adj_list: &Array<u32>,
node_count: u32,
steps: u32,
cooling_adjust: f32,
reheat_steps: u32,
orders: &mut Array<u32>,
positions: &mut Array<u32>,
best_orders: &mut Array<u32>,
current_costs: &mut Array<u32>,
temp_floors: &mut Array<f32>,
best_orders_costs: &mut Array<u32>,
rng_states: &mut Array<u32>,
stagnant_steps: &mut Array<u32>,
) {
let candidate = ABSOLUTE_POS;
let node_count = node_count as usize;
let steps = steps as usize;
if node_count == 0 {
current_costs[candidate] = 0;
best_orders_costs[candidate] = 0;
} else {
let base = candidate * node_count;
let mut state = rng_states[candidate];
let mut current_cost = current_costs[candidate];
let mut temp_floor = temp_floors[candidate].max(MIN_ANNEAL_TEMP);
let cooling_adjust = cooling_adjust.max(0.0001).min(0.05);
let reheat_gain = (cooling_adjust * 4.0).max(0.001).min(0.05);
let floor_decay = (1.0 - cooling_adjust * 2.0).max(0.90).min(0.9999);
let mut stagnant = stagnant_steps[candidate];
let mut best_cost = best_orders_costs[candidate];
let reheat_steps = reheat_steps.max(1);
if node_count > 1 && steps > 0 {
for _ in 0..steps {
state = state * LCG_A + LCG_C;
let i = (state % node_count as u32) as usize;
state = state * LCG_A + LCG_C;
let mut j = (state % (node_count as u32 - 1)) as usize;
if j >= i {
j += 1;
}
let left = base + i;
let right = base + j;
let node_i = orders[left];
let node_j = orders[right];
orders[left] = node_j;
orders[right] = node_i;
positions[base + node_j as usize] = i as u32;
positions[base + node_i as usize] = j as u32;
let node_i_usize = node_i as usize;
let node_j_usize = node_j as usize;
let pos_i = i as u32;
let pos_j = j as u32;
let mut delta_cost: i32 = 0;
let start_i = adj_offsets[node_i_usize] as usize;
let end_i = adj_offsets[node_i_usize + 1] as usize;
for idx in start_i..end_i {
let neighbor = adj_list[idx] as usize;
if neighbor != node_j_usize {
let pos_n = positions[base + neighbor];
let old = if pos_i > pos_n {
pos_i - pos_n
} else {
pos_n - pos_i
};
let new = if pos_j > pos_n {
pos_j - pos_n
} else {
pos_n - pos_j
};
delta_cost += new as i32 - old as i32;
}
}
let start_j = adj_offsets[node_j_usize] as usize;
let end_j = adj_offsets[node_j_usize + 1] as usize;
for idx in start_j..end_j {
let neighbor = adj_list[idx] as usize;
if neighbor != node_i_usize {
let pos_n = positions[base + neighbor];
let old = if pos_j > pos_n {
pos_j - pos_n
} else {
pos_n - pos_j
};
let new = if pos_i > pos_n {
pos_i - pos_n
} else {
pos_n - pos_i
};
delta_cost += new as i32 - old as i32;
}
}
let candidate_cost = (current_cost as i32 + delta_cost).max(0) as u32;
let delta = candidate_cost as f32 - current_cost as f32;
let mut accept = delta <= 0.0;
if !accept && temp_floor > MIN_ANNEAL_TEMP {
let probability = (-delta / temp_floor).exp();
state = state * LCG_A + LCG_C;
let rand = state as f32 * INV_U32_MAX_PLUS1;
accept = rand < probability;
}
if accept {
current_cost = candidate_cost;
if candidate_cost < best_cost {
best_cost = candidate_cost;
stagnant = 0;
for idx in 0..node_count {
best_orders[base + idx] = orders[base + idx];
}
temp_floor = (temp_floor * floor_decay).max(MIN_ANNEAL_TEMP);
} else if stagnant < u32::MAX {
stagnant += 1;
}
} else {
let left = base + i;
let right = base + j;
orders[left] = node_i;
orders[right] = node_j;
positions[base + node_i as usize] = i as u32;
positions[base + node_j as usize] = j as u32;
if stagnant < u32::MAX {
stagnant += 1;
}
}
if stagnant > 0 {
let ratio = stagnant as f32 / reheat_steps as f32;
let gain = reheat_gain * (ratio / (1.0 + ratio));
temp_floor = temp_floor * (1.0 + gain);
}
}
}
current_costs[candidate] = current_cost;
temp_floors[candidate] = temp_floor;
best_orders_costs[candidate] = best_cost;
rng_states[candidate] = state;
stagnant_steps[candidate] = stagnant;
}
}
#[cfg(feature = "cubecl")]
#[cube(launch)]
fn minla_sa_reseed_kernel(
node_count: u32,
best_idx: u32,
best_cost: u32,
stale_steps: u32,
best_version: u32,
reset_floor: f32,
orders: &mut Array<u32>,
positions: &mut Array<u32>,
best_orders: &mut Array<u32>,
current_costs: &mut Array<u32>,
best_orders_costs: &mut Array<u32>,
temp_floors: &mut Array<f32>,
stagnant_steps: &mut Array<u32>,
reseeded_flags: &mut Array<u32>,
seed_versions: &mut Array<u32>,
) {
let candidate = ABSOLUTE_POS;
let node_count = node_count as usize;
let best_idx = best_idx as usize;
if candidate == best_idx {
seed_versions[candidate] = best_version;
}
let should_reseed = stale_steps > 0
&& candidate != best_idx
&& stagnant_steps[candidate] >= stale_steps
&& seed_versions[candidate] < best_version;
reseeded_flags[candidate] = 0;
if should_reseed {
reseeded_flags[candidate] = 1;
}
if should_reseed {
if node_count == 0 {
current_costs[candidate] = best_cost;
best_orders_costs[candidate] = best_cost;
} else {
let base = candidate * node_count;
let best_base = best_idx * node_count;
for idx in 0..node_count {
let node = best_orders[best_base + idx];
orders[base + idx] = node;
best_orders[base + idx] = node;
positions[base + node as usize] = idx as u32;
}
current_costs[candidate] = best_cost;
best_orders_costs[candidate] = best_cost;
}
temp_floors[candidate] = reset_floor;
stagnant_steps[candidate] = 0;
seed_versions[candidate] = best_version;
}
}
fn choose_track_y(gap_tracks: &[(f32, f32)], start_y: f32, end_y: f32) -> f32 {
let mut best = (gap_tracks[0].0 + gap_tracks[0].1) * 0.5;
let mut best_cost = f32::INFINITY;
for (top, bottom) in gap_tracks {
let y = (top + bottom) * 0.5;
let cost = (start_y - y).abs() + (end_y - y).abs();
if cost < best_cost {
best_cost = cost;
best = y;
}
}
best
}
fn choose_track_y_monotonic(corridors: &[(f32, f32)], current_y: f32, end_y: f32) -> (f32, bool) {
if corridors.is_empty() {
return (current_y, true);
}
let going_down = end_y >= current_y;
let mut best = None;
let mut best_delta = f32::INFINITY;
if going_down {
for (top, bottom) in corridors {
if *bottom < current_y || *top > end_y {
continue;
}
let y = current_y.max(*top).min(*bottom);
let delta = y - current_y;
if delta < best_delta {
best_delta = delta;
best = Some(y);
if delta <= f32::EPSILON {
break;
}
}
}
} else {
for (top, bottom) in corridors {
if *top > current_y || *bottom < end_y {
continue;
}
let y = current_y.min(*bottom).max(*top);
let delta = current_y - y;
if delta < best_delta {
best_delta = delta;
best = Some(y);
if delta <= f32::EPSILON {
break;
}
}
}
}
if let Some(y) = best {
return (y, false);
}
best = None;
best_delta = f32::INFINITY;
if going_down {
for (top, bottom) in corridors {
if *bottom < current_y {
continue;
}
let y = current_y.max(*top).min(*bottom);
let delta = (y - current_y).abs();
if delta < best_delta {
best_delta = delta;
best = Some(y);
}
}
} else {
for (top, bottom) in corridors {
if *top > current_y {
continue;
}
let y = current_y.min(*bottom).max(*top);
let delta = (current_y - y).abs();
if delta < best_delta {
best_delta = delta;
best = Some(y);
}
}
}
if let Some(y) = best {
return (y, true);
}
(choose_track_y(corridors, current_y, end_y), true)
}
fn intersect_intervals(a: &[(f32, f32)], b: &[(f32, f32)]) -> Vec<(f32, f32)> {
let mut out = Vec::new();
let mut i = 0usize;
let mut j = 0usize;
while i < a.len() && j < b.len() {
let start = a[i].0.max(b[j].0);
let end = a[i].1.min(b[j].1);
if end > start {
out.push((start, end));
}
if a[i].1 < b[j].1 {
i += 1;
} else {
j += 1;
}
}
out
}
fn closest_corner_on_side(target: Rect, from: egui::Pos2, left: bool) -> egui::Pos2 {
let top = if left {
target.left_top()
} else {
target.right_top()
};
let bottom = if left {
target.left_bottom()
} else {
target.right_bottom()
};
if from.distance_sq(top) <= from.distance_sq(bottom) {
top
} else {
bottom
}
}
fn choose_track_y_between_columns(
component: &ComponentLayout,
start_y: f32,
end_y: f32,
min_col: usize,
max_col: usize,
) -> (f32, bool) {
let Some(first) = component.column_free.get(min_col) else {
return ((start_y + end_y) * 0.5, true);
};
let mut corridors = first.clone();
for col in (min_col + 1)..=max_col {
let Some(next) = component.column_free.get(col) else {
break;
};
corridors = intersect_intervals(&corridors, next);
if corridors.is_empty() {
break;
}
}
if corridors.is_empty() {
return (choose_track_y(first, start_y, end_y), true);
}
let going_down = end_y >= start_y;
if going_down {
for (top, bottom) in &corridors {
if *bottom < start_y {
continue;
}
if *top > end_y {
break;
}
let y = start_y.max(*top).min(end_y);
return (y, false);
}
} else {
for (top, bottom) in corridors.iter().rev() {
if *top > start_y {
continue;
}
if *bottom < end_y {
break;
}
let y = start_y.min(*bottom).max(end_y);
return (y, false);
}
}
if going_down {
for (top, bottom) in &corridors {
if *bottom >= start_y {
return (start_y.max(*top), true);
}
}
} else {
for (top, bottom) in corridors.iter().rev() {
if *top <= start_y {
return (start_y.min(*bottom), true);
}
}
}
(choose_track_y(&corridors, start_y, end_y), true)
}
fn row_line_y(layout: &GraphLayout, tile: Rect, row: usize) -> f32 {
let row_top = tile.top()
+ layout.tile_padding
+ layout.header_height
+ row as f32 * layout.text_row_height;
let y = row_top + layout.text_row_height - 2.0 - 1.0;
y.max(row_top + 2.0)
}
fn row_anchor(layout: &GraphLayout, tile: Rect, row: usize, on_left: bool) -> egui::Pos2 {
let y = row_line_y(layout, tile, row);
let edge_inset = 0.0;
let x = if on_left {
tile.left() + edge_inset
} else {
tile.right() - edge_inset
};
pos2(x, y)
}
fn row_underline_segment(
layout: &GraphLayout,
tile: Rect,
row: usize,
go_left: bool,
) -> Option<(egui::Pos2, egui::Pos2)> {
let inner = tile.shrink(layout.tile_padding);
if !inner.is_positive() {
return None;
}
let y = row_line_y(layout, tile, row);
let key_w = (inner.width() * 0.42).clamp(56.0, 120.0);
let divider_x = (inner.left() + key_w).min(inner.right());
let inset = 4.0;
let min_len = 6.0;
let edge_inset = 0.0;
let (start_x, end_x) = if go_left {
let start_x = tile.left() + edge_inset;
let mut end_x = divider_x - inset;
if end_x < start_x + min_len {
end_x = (start_x + min_len).min(inner.right());
}
(start_x, end_x)
} else {
let end_x = tile.right() - edge_inset;
let mut start_x = divider_x + inset;
if start_x > end_x - min_len {
start_x = (end_x - min_len).max(inner.left());
}
(start_x, end_x)
};
if end_x - start_x <= 0.5 {
return None;
}
Some((pos2(start_x, y), pos2(end_x, y)))
}
fn build_attribute_bundle_offsets(
layout: &GraphLayout,
drafts: &[EdgeDraft],
) -> HashMap<(i32, BundleKey), f32> {
let max_offset = (layout.column_gap * 0.5 - 4.0).max(0.0);
let mut keys_by_boundary = HashMap::<i32, Vec<BundleKey>>::new();
for draft in drafts {
let key = (draft.edge.attr_id, draft.edge.to_entity);
let start_keys = keys_by_boundary.entry(draft.start_boundary).or_default();
if !start_keys.contains(&key) {
start_keys.push(key);
}
let end_keys = keys_by_boundary.entry(draft.end_boundary).or_default();
if !end_keys.contains(&key) {
end_keys.push(key);
}
}
let mut offsets = HashMap::new();
for (boundary, keys) in keys_by_boundary {
let count = keys.len();
if count == 0 {
continue;
}
if max_offset <= 0.01 || count == 1 {
offsets.insert((boundary, keys[0]), 0.0);
continue;
}
let step = (max_offset * 2.0) / (count - 1) as f32;
for (idx, key) in keys.iter().enumerate() {
let offset = -max_offset + step * idx as f32;
offsets.insert((boundary, *key), offset);
}
}
offsets
}
fn route_edges(layout: &GraphLayout, graph: &EntityGraph) -> Vec<RoutedEdge> {
let mut drafts = Vec::with_capacity(graph.edges.len());
for edge in graph.edges.iter().cloned() {
let component = layout
.node_component
.get(edge.from_entity)
.copied()
.unwrap_or(usize::MAX);
if component == usize::MAX {
continue;
}
if layout.node_component.get(edge.to_entity).copied() != Some(component) {
continue;
}
let source_rect = layout.tile_rects[edge.from_entity];
let target_rect = layout.tile_rects[edge.to_entity];
if !source_rect.is_positive() || !target_rect.is_positive() {
continue;
}
let from_col = layout
.node_column
.get(edge.from_entity)
.copied()
.unwrap_or(usize::MAX);
let to_col = layout
.node_column
.get(edge.to_entity)
.copied()
.unwrap_or(usize::MAX);
if from_col == usize::MAX || to_col == usize::MAX {
continue;
}
let (min_col, max_col) = if from_col <= to_col {
(from_col, to_col)
} else {
(to_col, from_col)
};
let last_col = layout.column_count.saturating_sub(1);
let same_col = from_col == to_col;
let go_left = if same_col {
if last_col == 0 {
let raw: [u8; 16] = *edge.attr_id.as_ref();
raw[0] & 1 == 0
} else if from_col == 0 {
true
} else if from_col == last_col {
false
} else {
let raw: [u8; 16] = *edge.attr_id.as_ref();
raw[0] & 1 == 0
}
} else {
to_col < from_col
};
let start = row_anchor(layout, source_rect, edge.from_row, go_left);
let end_on_left = if same_col { go_left } else { !go_left };
let end = closest_corner_on_side(target_rect, start, end_on_left);
let start_boundary = if go_left {
from_col as i32 - 1
} else {
from_col as i32
};
let start_gutter_center_x = if go_left {
source_rect.left() - layout.column_gap * 0.5
} else {
source_rect.right() + layout.column_gap * 0.5
};
let end_boundary = if end_on_left {
to_col as i32 - 1
} else {
to_col as i32
};
let end_gutter_center_x = if end_on_left {
target_rect.left() - layout.column_gap * 0.5
} else {
target_rect.right() + layout.column_gap * 0.5
};
drafts.push(EdgeDraft {
edge,
source_rect,
go_left,
start,
end,
min_col,
max_col,
start_boundary,
end_boundary,
start_gutter_center_x,
end_gutter_center_x,
component,
});
}
let bundle_offsets = build_attribute_bundle_offsets(layout, &drafts);
let mut routed = Vec::with_capacity(drafts.len());
for draft in drafts {
let Some(component_layout) = layout.components.get(draft.component) else {
continue;
};
let bundle_key = (draft.edge.attr_id, draft.edge.to_entity);
let start_offset = bundle_offsets
.get(&(draft.start_boundary, bundle_key))
.copied()
.unwrap_or(0.0);
let end_offset = bundle_offsets
.get(&(draft.end_boundary, bundle_key))
.copied()
.unwrap_or(start_offset);
let start_center_x = draft.start_gutter_center_x;
let end_center_x = draft.end_gutter_center_x;
let mut start_bundle_x = start_center_x + start_offset;
let mut end_bundle_x = end_center_x + end_offset;
let same_gutter = draft.start_boundary == draft.end_boundary;
let span_cols = draft.max_col.saturating_sub(draft.min_col);
if !same_gutter {
if start_center_x <= end_center_x {
start_bundle_x = start_bundle_x.clamp(start_center_x, end_center_x);
end_bundle_x = end_bundle_x.clamp(start_bundle_x, end_center_x);
} else {
start_bundle_x = start_bundle_x.clamp(end_center_x, start_center_x);
end_bundle_x = end_bundle_x.clamp(end_center_x, start_bundle_x);
}
}
let mut used_fallback_track = false;
let mut points = if same_gutter {
let gutter_x = start_bundle_x;
vec![
draft.start,
pos2(gutter_x, draft.start.y),
pos2(gutter_x, draft.end.y),
draft.end,
]
} else if span_cols > 1 {
let mut points = vec![draft.start, pos2(start_bundle_x, draft.start.y)];
let step = if draft.end_boundary > draft.start_boundary {
1
} else {
-1
};
let step_x = draft.source_rect.width() + layout.column_gap;
let mut boundary = draft.start_boundary;
let mut current_y = draft.start.y;
let mut current_x = start_bundle_x;
let end_y = draft.end.y;
while boundary != draft.end_boundary {
let next_boundary = boundary + step;
let column_idx = if step > 0 {
next_boundary as usize
} else {
boundary as usize
};
let next_center_x =
start_center_x + (next_boundary - draft.start_boundary) as f32 * step_x;
let (track_y, fallback) = component_layout
.column_free
.get(column_idx)
.map(|corridors| choose_track_y_monotonic(corridors, current_y, end_y))
.unwrap_or((current_y, true));
used_fallback_track |= fallback;
let next_offset = bundle_offsets
.get(&(next_boundary, bundle_key))
.copied()
.unwrap_or(0.0);
let mut next_x = next_center_x + next_offset;
if step > 0 && next_x < current_x {
next_x = current_x;
} else if step < 0 && next_x > current_x {
next_x = current_x;
}
points.push(pos2(current_x, track_y));
points.push(pos2(next_x, track_y));
boundary = next_boundary;
current_y = track_y;
current_x = next_x;
}
points.push(pos2(current_x, end_y));
points.push(draft.end);
points
} else {
let (track_y, used_fallback) = choose_track_y_between_columns(
component_layout,
draft.start.y,
draft.end.y,
draft.min_col,
draft.max_col,
);
used_fallback_track = used_fallback;
vec![
draft.start,
pos2(start_center_x, draft.start.y),
pos2(start_center_x, track_y),
pos2(start_bundle_x, track_y),
pos2(end_bundle_x, track_y),
pos2(end_center_x, track_y),
pos2(end_center_x, draft.end.y),
draft.end,
]
};
points.dedup_by(|a, b| a.distance_sq(*b) < 0.01);
let mut length = 0.0f32;
for seg in points.windows(2) {
let a = seg[0];
let b = seg[1];
length += (a.x - b.x).abs() + (a.y - b.y).abs();
}
let mut turns = 0usize;
let mut last_dir: Option<bool> = None;
for seg in points.windows(2) {
let a = seg[0];
let b = seg[1];
let is_horizontal = (a.y - b.y).abs() <= (a.x - b.x).abs();
if let Some(prev) = last_dir {
if prev != is_horizontal {
turns += 1;
}
}
last_dir = Some(is_horizontal);
}
routed.push(RoutedEdge {
points,
length,
turns,
span_cols: draft.max_col.saturating_sub(draft.min_col),
start_underline: row_underline_segment(
layout,
draft.source_rect,
draft.edge.from_row,
draft.go_left,
),
attr_id: draft.edge.attr_id,
from_entity: draft.edge.from_entity,
to_entity: draft.edge.to_entity,
go_left: draft.go_left,
used_fallback_track,
});
}
routed
}
fn paint_subway_edge(painter: &egui::Painter, points: &[egui::Pos2], line: Stroke) {
if points.len() < 2 {
return;
}
painter.add(egui::Shape::line(points.to_vec(), line));
}
fn distance_sq_to_segment(point: egui::Pos2, a: egui::Pos2, b: egui::Pos2) -> f32 {
let ab = b - a;
let denom = ab.length_sq();
if denom <= f32::EPSILON {
return point.distance_sq(a);
}
let t = ((point - a).dot(ab) / denom).clamp(0.0, 1.0);
point.distance_sq(a + ab * t)
}
fn distance_sq_to_polyline(point: egui::Pos2, points: &[egui::Pos2]) -> f32 {
if points.len() < 2 {
return f32::INFINITY;
}
let mut best = f32::INFINITY;
for seg in points.windows(2) {
let d2 = distance_sq_to_segment(point, seg[0], seg[1]);
if d2 < best {
best = d2;
}
}
best
}
fn round_polyline(points: &[egui::Pos2], radius: f32, segments: usize) -> Vec<egui::Pos2> {
if points.len() < 3 || radius <= 0.0 || segments == 0 {
return points.to_vec();
}
let mut out = Vec::with_capacity(points.len() + segments * 2);
out.push(points[0]);
for i in 1..points.len() - 1 {
let prev = points[i - 1];
let curr = points[i];
let next = points[i + 1];
let v_in = curr - prev;
let v_out = next - curr;
let len_in = v_in.length();
let len_out = v_out.length();
if len_in <= 0.01 || len_out <= 0.01 {
out.push(curr);
continue;
}
let dir_in = v_in / len_in;
let dir_out = v_out / len_out;
if dir_in.dot(dir_out).abs() > 0.999 {
out.push(curr);
continue;
}
let corner_radius = radius.min(len_in * 0.5).min(len_out * 0.5);
if corner_radius <= 0.01 {
out.push(curr);
continue;
}
let p1 = curr - dir_in * corner_radius;
let p2 = curr + dir_out * corner_radius;
if i == 1 {
if out.last().is_none_or(|last| last.distance_sq(p1) > 0.01) {
out.push(p1);
}
} else if let Some(last) = out.last_mut() {
*last = p1;
} else {
out.push(p1);
}
let center = curr + (dir_out - dir_in) * corner_radius;
let a1 = (p1 - center).angle();
let mut a2 = (p2 - center).angle();
let cross = dir_in.x * dir_out.y - dir_in.y * dir_out.x;
if cross > 0.0 {
if a2 <= a1 {
a2 += std::f32::consts::TAU;
}
} else if a2 >= a1 {
a2 -= std::f32::consts::TAU;
}
let step = (a2 - a1) / segments as f32;
for s in 1..=segments {
let angle = a1 + step * s as f32;
out.push(center + egui::Vec2::angled(angle) * corner_radius);
}
}
out.push(*points.last().unwrap());
out
}
struct TableInteraction {
select_target: Option<usize>,
scroll_target: Option<usize>,
}
fn paint_entity_table(
ui: &mut Ui,
rect: Rect,
node: &EntityNode,
node_idx: usize,
is_selected: bool,
layout: &GraphLayout,
graph: &EntityGraph,
) -> TableInteraction {
let id = ui.id().with(("entity_table", node.id));
let response = ui.interact(rect, id, Sense::click());
let table_clicked = response.clicked();
let visuals = ui.visuals();
let fill = visuals.window_fill;
let ink = visuals.widgets.noninteractive.fg_stroke.color;
let stroke = Stroke::new(1.0, ink);
let grid_stroke = Stroke::new(1.0, ink);
let hatch_color = visuals.widgets.noninteractive.bg_stroke.color;
let painter = ui.painter();
painter.rect_filled(rect, 0.0, fill);
if is_selected {
painter.rect_stroke(rect, 0.0, stroke, egui::StrokeKind::Inside);
let inner_rect = rect.shrink(2.0);
if inner_rect.is_positive() {
painter.rect_stroke(inner_rect, 0.0, stroke, egui::StrokeKind::Inside);
}
} else {
painter.rect_stroke(rect, 0.0, stroke, egui::StrokeKind::Inside);
}
let text_color = ink;
let title_font = TextStyle::Monospace.resolve(ui.style());
let row_font = TextStyle::Small.resolve(ui.style());
let inner = rect.shrink(layout.tile_padding);
let title_rect = Rect::from_min_max(
inner.left_top(),
pos2(inner.right(), inner.top() + layout.header_height),
);
painter.text(
title_rect.left_top(),
Align2::LEFT_TOP,
node.title.as_str(),
title_font,
text_color,
);
let row_top = title_rect.bottom();
let key_w = (inner.width() * 0.42).clamp(56.0, 120.0);
let key_x = inner.left();
let value_x = (inner.left() + key_w + 8.0).min(inner.right());
let row_area = Rect::from_min_max(pos2(inner.left(), row_top), inner.right_bottom());
let divider_x = (inner.left() + key_w).min(inner.right());
if row_area.is_positive() {
painter.vline(divider_x, row_area.y_range(), grid_stroke);
}
let mut scroll_target = None;
let mut select_target = None;
for (i, row) in node.rows.iter().enumerate() {
let y = row_top + i as f32 * layout.text_row_height;
let row_rect = Rect::from_min_max(
pos2(inner.left(), y),
pos2(
inner.right(),
(y + layout.text_row_height).min(inner.bottom()),
),
);
if i > 0 {
painter.hline(row_rect.x_range(), row_rect.top(), grid_stroke);
}
if let Some(target) = row.target {
if let Some(&target_idx) = graph.id_to_index.get(&target) {
let row_id = id.with(("row", i));
let row_response = ui
.interact(row_rect, row_id, Sense::click())
.on_hover_cursor(egui::CursorIcon::PointingHand);
if row_response.clicked() {
scroll_target = Some(target_idx);
select_target = Some(target_idx);
}
}
}
painter.text(
pos2(key_x, row_rect.top() + 1.0),
Align2::LEFT_TOP,
row.attr.as_str(),
row_font.clone(),
text_color,
);
if row.hatched {
let value_rect = Rect::from_min_max(
pos2(value_x, row_rect.top()),
pos2(inner.right(), row_rect.bottom()),
);
let hatch_rect = value_rect.shrink(1.0);
if hatch_rect.is_positive() {
paint_hatching(&painter.with_clip_rect(hatch_rect), hatch_rect, hatch_color);
}
} else {
painter.text(
pos2(value_x, row_rect.top() + 1.0),
Align2::LEFT_TOP,
row.value.as_str(),
row_font.clone(),
text_color,
);
}
}
if response.hovered() {
let full = id_full(node.id);
let _ = response.on_hover_text(full);
}
if select_target.is_none() && table_clicked {
select_target = Some(node_idx);
}
TableInteraction {
select_target,
scroll_target,
}
}
fn compute_inspector(
ui: &mut Ui,
cache_id: egui::Id,
graph: &EntityGraph,
forced_columns: usize,
order: EntityOrder,
) -> (GraphLayout, Vec<RoutedEdge>, EntityInspectorStats) {
let order = entity_order(ui, cache_id, graph, order);
let mut positions = vec![0usize; graph.nodes.len()];
for (pos, &idx) in order.iter().enumerate() {
positions[idx] = pos;
}
let mut linear_total = 0.0f32;
for edge in &graph.edges {
let from = positions[edge.from_entity] as i32;
let to = positions[edge.to_entity] as i32;
linear_total += (from - to).abs() as f32;
}
let linear_avg = if graph.edges.is_empty() {
0.0
} else {
linear_total / graph.edges.len() as f32
};
let layout = compute_graph_layout(ui, graph, forced_columns, &order);
let routed_edges = route_edges(&layout, graph);
let stats = compute_graph_stats(graph, &layout, &routed_edges, linear_total, linear_avg);
(layout, routed_edges, stats)
}
fn compute_graph_stats(
graph: &EntityGraph,
layout: &GraphLayout,
routed_edges: &[RoutedEdge],
linear_total: f32,
linear_avg: f32,
) -> EntityInspectorStats {
let connected_components = connected_components(&build_adjacency(graph)).len();
let edges = routed_edges.len();
let tile_area = layout
.tile_rects
.iter()
.filter_map(|rect| rect.is_positive().then(|| rect.area()))
.sum::<f32>();
let canvas_area = layout.canvas_size.x * layout.canvas_size.y;
let tile_coverage = if canvas_area <= 0.0 {
0.0
} else {
tile_area / canvas_area
};
let mut total_edge_len = 0.0f32;
let mut max_edge_len = 0.0f32;
let mut total_turns = 0usize;
let mut max_turns = 0usize;
let mut total_span_cols = 0usize;
let mut max_span_cols = 0usize;
let mut left_edges = 0usize;
let mut fallback_tracks = 0usize;
for edge in routed_edges {
total_edge_len += edge.length;
max_edge_len = max_edge_len.max(edge.length);
total_turns += edge.turns;
max_turns = max_turns.max(edge.turns);
total_span_cols += edge.span_cols;
max_span_cols = max_span_cols.max(edge.span_cols);
if edge.go_left {
left_edges += 1;
}
if edge.used_fallback_track {
fallback_tracks += 1;
}
}
EntityInspectorStats {
nodes: graph.nodes.len(),
edges,
connected_components,
columns: layout.column_count,
canvas_width: layout.canvas_size.x,
canvas_height: layout.canvas_size.y,
tile_coverage,
total_edge_len,
avg_edge_len: if edges == 0 {
0.0
} else {
total_edge_len / edges as f32
},
max_edge_len,
avg_turns: if edges == 0 {
0.0
} else {
total_turns as f32 / edges as f32
},
max_turns,
avg_span_cols: if edges == 0 {
0.0
} else {
total_span_cols as f32 / edges as f32
},
max_span_cols,
left_edges,
fallback_tracks,
linear_total,
linear_avg,
}
}
fn paint_entity_inspector(
ui: &mut Ui,
graph: &EntityGraph,
selected_id: &mut Id,
layout: &GraphLayout,
routed_edges: &[RoutedEdge],
) -> Response {
let selected_index = graph.id_to_index.get(selected_id).copied();
let desired_width = ui.available_width();
let (outer_rect, response) =
ui.allocate_exact_size(vec2(desired_width, layout.canvas_size.y), Sense::hover());
if !ui.is_rect_visible(outer_rect) {
return response;
}
let offset_x = ((desired_width - layout.canvas_size.x).max(0.0)) * 0.5;
let origin = pos2(outer_rect.left() + offset_x, outer_rect.top());
let origin_vec = origin.to_vec2();
let tile_rects_ui: Vec<Rect> = layout
.tile_rects
.iter()
.map(|rect| rect.translate(origin_vec))
.collect();
let pointer_pos = ui
.input(|input| input.pointer.hover_pos())
.filter(|pos| outer_rect.contains(*pos));
let hovered_node = pointer_pos.and_then(|pos| {
tile_rects_ui
.iter()
.enumerate()
.find(|(_, rect)| rect.is_positive() && rect.contains(pos))
.map(|(idx, _)| idx)
});
let painter = ui.painter().with_clip_rect(outer_rect);
let line_width: f32 = 2.5;
let line_palette = [
themes::ral(1003),
themes::ral(2010),
themes::ral(3001),
themes::ral(4008),
themes::ral(5005),
themes::ral(6032),
themes::ral(3014),
];
let end_dot_radius = line_width * 2.5;
let hover_threshold = end_dot_radius.max(line_width * 3.0);
let mut edge_renders = Vec::with_capacity(routed_edges.len());
for routed in routed_edges {
let raw = routed
.points
.iter()
.copied()
.map(|p| p + origin_vec)
.collect::<Vec<_>>();
let points = round_polyline(&raw, (layout.text_row_height * 0.25).clamp(3.0, 8.0), 4);
let palette_index = attribute_palette_index(routed.attr_id, line_palette.len());
let line_color = line_palette[palette_index];
edge_renders.push(EdgeRender {
points,
line_color,
start_underline: routed
.start_underline
.map(|(a, b)| (a + origin_vec, b + origin_vec)),
from_entity: routed.from_entity,
to_entity: routed.to_entity,
});
}
let hovered_edge = if hovered_node.is_some() {
None
} else {
pointer_pos.and_then(|pos| {
let mut best = hover_threshold * hover_threshold;
let mut hovered = None;
for (idx, render) in edge_renders.iter().enumerate() {
let mut dist = distance_sq_to_polyline(pos, &render.points);
if let Some((a, b)) = render.start_underline {
dist = dist.min(distance_sq_to_segment(pos, a, b));
}
if dist <= best {
best = dist;
hovered = Some(idx);
}
}
hovered
})
};
let mut end_dots = Vec::new();
let mut end_dots_hover = Vec::new();
let mut start_underlines = Vec::new();
let mut start_underlines_hover = Vec::new();
let fade_bg = ui.visuals().window_fill;
let mut active_mask = vec![false; edge_renders.len()];
if let Some(node_idx) = hovered_node {
for (idx, render) in edge_renders.iter().enumerate() {
if render.from_entity == node_idx {
active_mask[idx] = true;
}
}
} else if let Some(hovered) = hovered_edge {
active_mask[hovered] = true;
}
if hovered_node.is_some() || hovered_edge.is_some() {
for (idx, render) in edge_renders.iter().enumerate() {
let is_active = active_mask[idx];
let line_color = if is_active {
render.line_color
} else {
themes::blend(render.line_color, fade_bg, 0.5)
};
let line_stroke = Stroke::new(line_width, line_color);
paint_subway_edge(&painter, &render.points, line_stroke);
if let Some((a, b)) = render.start_underline {
if is_active {
start_underlines_hover.push((a, b, line_color));
} else {
start_underlines.push((a, b, line_color));
}
}
if let Some(end) = render.points.last().copied() {
if is_active {
end_dots_hover.push((end, line_color));
} else {
end_dots.push((end, line_color));
}
}
}
} else {
for render in &edge_renders {
let line_stroke = Stroke::new(line_width, render.line_color);
paint_subway_edge(&painter, &render.points, line_stroke);
if let Some((a, b)) = render.start_underline {
start_underlines.push((a, b, render.line_color));
}
if let Some(end) = render.points.last().copied() {
end_dots.push((end, render.line_color));
}
}
}
let mut scroll_target = None;
let mut select_target = None;
for (idx, node) in graph.nodes.iter().enumerate() {
let rect = tile_rects_ui[idx];
if !rect.is_positive() {
continue;
}
let is_selected = selected_index == Some(idx);
let table = paint_entity_table(ui, rect, node, idx, is_selected, &layout, graph);
if scroll_target.is_none() {
scroll_target = table.scroll_target;
}
if select_target.is_none() {
select_target = table.select_target;
}
}
if scroll_target.is_none()
&& ui.input(|input| input.pointer.primary_clicked())
&& hovered_edge.is_some()
{
let shift = ui.input(|input| input.modifiers.shift);
if let Some(edge_idx) = hovered_edge {
if let Some(render) = edge_renders.get(edge_idx) {
let target_idx = if shift {
render.from_entity
} else {
render.to_entity
};
scroll_target = Some(target_idx);
select_target = Some(target_idx);
}
}
}
if let Some(target_idx) = select_target {
if let Some(node) = graph.nodes.get(target_idx) {
*selected_id = node.id;
}
}
if let Some(target_idx) = scroll_target {
if let Some(rect) = tile_rects_ui.get(target_idx).copied() {
if rect.is_positive() {
ui.scroll_to_rect(rect, Some(egui::Align::Center));
}
}
}
if !start_underlines.is_empty()
|| !end_dots.is_empty()
|| !start_underlines_hover.is_empty()
|| !end_dots_hover.is_empty()
{
let dot_painter = ui.painter().with_clip_rect(outer_rect);
for (a, b, color) in start_underlines {
dot_painter.line_segment([a, b], Stroke::new(line_width, color));
}
for (a, b, color) in start_underlines_hover {
dot_painter.line_segment([a, b], Stroke::new(line_width, color));
}
if end_dot_radius > 0.0 {
for (center, color) in end_dots {
dot_painter.circle_filled(center, end_dot_radius, color);
}
for (center, color) in end_dots_hover {
dot_painter.circle_filled(center, end_dot_radius, color);
}
}
}
response
}