///|
/// 布局：把调用树算成一组矩形坐标。
///
/// 采用 icicle 方向（根在顶部、逐层向下）。算法本身很简单，要点有三个：
///
///   1. **按值比例切分**：子项宽度 = 父宽度 × (子值 / 父值)。因此不需要任何
///      矩形打包算法，天然不重叠、不留缝；
///   2. **最后一个子项直接取父节点右边界**，而不是用累加值。否则浮点误差会
///      一点点累积，几千个矩形之后就会出现肉眼可见的缝或重叠；
///   3. **自身耗时作为合成子项参与切分**，这样「父宽 = 全部子项宽之和」严格成立，
///      图面上不会出现空洞。
///
/// 布局不做最小宽度过滤：它产出的是**精确**的几何数据，是否绘制小于若干像素的
/// 矩形属于渲染层的取舍。

///|
/// 一个待绘制的矩形。
pub struct Rect {
  x : Double
  /// 纵向位置。由 `layout` 在排布完成后统一确定：
  /// 火焰图方向下根在底部，因此 y 依赖整棵树的最大深度。
  mut y : Double
  width : Double
  height : Double
  name : String
  /// 累计权重；合成项（自身耗时）则为该帧的自身耗时
  value : Double
  depth : Int
  /// 差异模式下的变化量；普通模式下为 `None`
  delta : Double?
} derive(Eq)

///|
/// 显式声明 `Eq` 的方法可被当作常规方法调用。
///
/// 新版编译器不再自动完成这个提升，不声明会报 `implicit_impl_as_method`。
pub extend Rect with Eq::{not_equal, equal}

///|
/// 布局结果。渲染器拿到的布局自带完整几何信息，无需再传画布参数。
pub struct Layout {
  rects : Array[Rect]
  /// 画布宽度，与传入值一致
  width : Double
  /// 每行高度，与传入值一致
  row_height : Double
  /// 最深的深度下标（渲染高度为 `(max_depth + 1) * row_height`）
  max_depth : Int
  /// 全部权重之和，用于计算占比
  total : Double
  /// 差异模式下最大的变化量绝对值，用于颜色归一化；非差异模式为 0
  max_delta : Double
  /// 纵向方向：`false` 火焰图（根在底部），`true` 冰柱图（根在顶部）。
  /// 交互脚本判断「祖先在上还是在下」时需要它。
  inverted : Bool
} derive(Eq)

///|
/// 显式声明 `Eq` 的方法可被当作常规方法调用。
///
/// 新版编译器不再自动完成这个提升，不声明会报 `implicit_impl_as_method`。
pub extend Layout with Eq::{not_equal, equal}

///|
/// 「自身耗时」合成帧的名字。
pub fn self_placeholder() -> String {
  "(self)"
}

///|
/// 参与切分的一个子项：要么是真实子节点，要么是自身耗时的合成项。
priv struct Item {
  name : String
  value : Double
  node : Node?
}

///|
/// 排序规则：值降序；同值时按名字升序，保证确定性。
fn compare_items(a : Item, b : Item) -> Int {
  if a.value > b.value {
    -1
  } else if a.value < b.value {
    1
  } else {
    String::compare(a.name, b.name)
  }
}

///|
/// 布局一个节点的子树。`x0`/`x1` 是它占据的水平区间。
fn layout_node(
  node : Node,
  x0 : Double,
  x1 : Double,
  depth : Int,
  row_height : Double,
  rects : Array[Rect],
) -> Unit {
  let pending : Array[(Node?, String, Double, Double, Double, Int, Double?)] = [
    (Some(node), node.name, node.value, x0, x1, depth, node.delta),
  ]
  while pending.length() > 0 {
    let (source, name, value, left, right, d, delta) = pending[pending.length() -
      1]
    ignore(pending.pop())
    rects.push({
      x: left,
      y: d.to_double() * row_height,
      width: right - left,
      height: row_height,
      name,
      value,
      depth: d,
      delta,
    })
    guard source is Some(current) else { continue }
    if right <= left || current.value <= 0.0 {
      continue
    }
    let items : Array[Item] = []
    for child in current.children {
      if child.value > 0.0 {
        items.push({ name: child.name, value: child.value, node: Some(child), })
      }
    }
    let own = current.self_time()
    if own > 0.0 && items.length() > 0 {
      items.push({ name: self_placeholder(), value: own, node: None, })
    }
    items.sort_by(compare_items)
    let tasks : Array[(Node?, String, Double, Double, Double, Int, Double?)] = []
    let mut cursor = left
    for i = 0; i < items.length(); i = i + 1 {
      let item = items[i]
      let next = if i + 1 == items.length() {
        right
      } else {
        smaller(
          right,
          larger(cursor, cursor + (right - left) * (item.value / current.value)),
        )
      }
      let change = match item.node {
        Some(child) => child.delta
        None => current.self_delta
      }
      tasks.push(
        (item.node, item.name, item.value, cursor, next, d + 1, change),
      )
      cursor = next
    }
    for i = tasks.length() - 1; i >= 0; i = i - 1 {
      pending.push(tasks[i])
    }
  }
}

///|
/// 把调用树布局成矩形列表（前序遍历顺序：父节点先于子节点）。
///
/// 多个根节点时按各自权重水平切分画布。
///
/// `inverted` 选择纵向方向：
///
///   - **默认（false）火焰图**：根在**底部**，逐层向上生长。底部密、顶部疏，
///     高耗时路径表现为向上伸出的「火苗」——这是 Brendan Gregg 定义的经典形态。
///   - `inverted = true` 冰柱图（icicle）：根在顶部，逐层向下。
///
/// 两种方向都只影响 y 坐标，水平切分完全一致。
pub fn layout(
  tree : CallTree,
  width : Double,
  row_height : Double,
  inverted? : Bool,
) -> Layout raise ValidationError {
  validate_tree(tree)
  positive_geometry(width, "width")
  positive_geometry(row_height, "row_height")
  let flip = match inverted {
    Some(value) => value
    None => false
  }
  let rects : Array[Rect] = []
  if width > 0.0 &&
    row_height > 0.0 &&
    tree.total > 0.0 &&
    tree.roots.length() > 0 {
    let mut cursor = 0.0
    let mut index = 0
    for root in tree.roots {
      index = index + 1
      let next = if index == tree.roots.length() {
        width
      } else {
        smaller(
          width,
          larger(cursor, cursor + width * (root.value / tree.total)),
        )
      }
      layout_node(root, cursor, next, 0, row_height, rects)
      cursor = next
    }
  }
  let mut max_depth = 0
  for rect in rects {
    if rect.depth > max_depth {
      max_depth = rect.depth
    }
  }
  // 方向直到这里才能确定：火焰图的根在底部，y 取决于整棵树的最大深度
  if !flip {
    for rect in rects {
      rect.y = (max_depth - rect.depth).to_double() * row_height
    }
  }
  if !finite((max_depth.to_double() + 1.0) * row_height) {
    raise InvalidGeometry("height overflow")
  }
  // 差异配色需要一个统一的量级做归一化，否则一处剧变就会让其它差别看不出来
  let mut max_delta = 0.0
  for rect in rects {
    match rect.delta {
      Some(value) => {
        let magnitude = if value < 0.0 { -value } else { value }
        if magnitude > max_delta {
          max_delta = magnitude
        }
      }
      None => ()
    }
  }
  {
    rects,
    width,
    row_height,
    max_depth,
    total: tree.total,
    max_delta,
    inverted: flip,
  }
}

///|
/// 需要绘制的行数（= 最深深度 + 1）。
pub fn Layout::row_count(self : Layout) -> Int {
  if self.rects.length() == 0 {
    0
  } else {
    self.max_depth + 1
  }
}

///|
/// 画布所需高度。
pub fn Layout::height(self : Layout) -> Double {
  self.row_count().to_double() * self.row_height
}