------------------------------------------------------------------------
-- Finite-depth terminal sequence
--
-- The finite-depth half of the terminal sequence of the indexed
-- edge-family functor.
--
-- 有限深度终序列
--
-- 索引边族函子终序列的有限深度一半。
------------------------------------------------------------------------

{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}

module Base.MCorr.TerminalSequence where

open import Agda.Primitive using (Level; _⊔_)
open import Agda.Builtin.Sigma using (Σ; _,_)
open import Data.Unit.Polymorphic.Base using (⊤; tt)
open import Data.Nat.Base using (ℕ; zero; suc)
open import Data.Product.Base using (_×_; proj₁; proj₂)

open import Base.MCorr using (M)
open import Base.MCorr.Setoid using
  (SysEq; EqOn; FiberAdjˢ; idAdjˢ; symAdjˢ; compAdjˢ; _≈Mˢ_)
open FiberAdjˢ

module _ {i a b ℓa ℓe : Level} (X : SysEq i a b ℓa ℓe) where

  open SysEq X

  private
    ℓtr  = i ⊔ a ⊔ b
    ℓeq = i ⊔ a ⊔ b ⊔ ℓa ⊔ ℓe

  ----------------------------------------------------------------------
  -- Finite-depth trees
  --
  -- F^n of the unit carrier. Depth 0 is the single unit leaf; a
  -- successor depth is a label and depth-n children along every edge.
  --
  -- 有限深度树
  --
  -- 单位载体的 F^n。深度 0 为单一单位叶;后继深度为一个标签与沿每条边
  -- 的深度 n 子树。

  Tr : ℕ → I → Set ℓtr
  Tr zero    x = ⊤ {ℓtr}
  Tr (suc n) x =
    Σ (A x) λ a → ((y : I) (e : E x a y) → Tr n y)

  head : ∀ {n : ℕ} {x : I} → Tr (suc n) x → A x
  head = proj₁

  kids : ∀ {n : ℕ} {x : I} (q : Tr (suc n) x)
         (y : I) (e : E x (head q) y) → Tr n y
  kids q y e = proj₂ q y e

  ----------------------------------------------------------------------
  -- Bonding map of the terminal sequence
  --
  -- Erase the deepest layer.
  --
  -- 终序列的结合映射
  --
  -- 抹去最深层。

  drop : ∀ {n : ℕ} {x : I} → Tr (suc n) x → Tr n x
  drop {n = zero}  _        = tt
  drop {n = suc m} (a , k)  =
    a , λ y e → drop (k y e)

  -- Truncation of an infinite tree to depth n.
  --
  -- 无穷树到深度 n 的截断。
  take : ∀ {n : ℕ} {x : I} → M A E x → Tr n x
  take {n = zero}  _ = tt
  take {n = suc m} t =
    M.here t , λ y e → take (M.below t y e)

  ----------------------------------------------------------------------
  -- Carried finite-depth setoid
  --
  -- The successor case is one bisimulation step — a label equivalence
  -- and, per target index, an edge adjunction with pointwise related
  -- children — recursive in the depth. It carries the edge adjunction
  -- as data, so no equality is matched and there is no subst.
  --
  -- 携带式有限深度 setoid
  --
  -- 后继情形即一步互模拟——标签等价,且对每个目标索引给一个边伴随与
  -- 逐点相关的子树——并对深度递归。边伴随作为数据携带,故不匹配等式、
  -- 无 subst。

  _≈Tr_ : ∀ {n : ℕ} {x : I} → Tr n x → Tr n x → Set ℓeq
  _≈Tr_ {n = zero}  _       _       = ⊤ {ℓeq}
  _≈Tr_ {n = suc m} {x = x} (a , k) (a' , k') =
      EqOn._≈_ (≈A x) a a'
    × ((y : I)
       → Σ (FiberAdjˢ (≈E x a' y) (≈E x a y)) λ adj
       →   (∀ (e : E x a y)
            → _≈Tr_ {n = m} (k y e) (k' y (to adj e)))
         × (∀ (e' : E x a' y)
            → _≈Tr_ {n = m} (k' y e') (k y (fro adj e'))))

  -- Each node already stores both directions, so symmetry only swaps
  -- the adjunction and exchanges the two components (no recursion into
  -- the children).
  --
  -- 每个节点已存放两个方向,故对称只需交换伴随、对调两个分量
  -- (无需递归进入子树)。
  ≈Tr-sym : ∀ {n : ℕ} {x : I} {q r : Tr n x}
          → q ≈Tr r → r ≈Tr q
  ≈Tr-sym {n = zero}  _           = tt
  ≈Tr-sym {n = suc m} (ha , body) =
      EqOn.sym (≈A _) ha
    , λ y → let adj , fwd , bwd = body y
            in symAdjˢ adj , ( bwd , fwd )

  ≈Tr-refl : ∀ {n : ℕ} {x : I} (q : Tr n x) → q ≈Tr q
  ≈Tr-refl {n = zero}  _       = tt
  ≈Tr-refl {n = suc m} (a , k) =
      EqOn.refl (≈A _)
    , λ y → idAdjˢ (≈E _ a y)
          , ( (λ e → ≈Tr-refl (k y e))
            , (λ e → ≈Tr-refl (k y e)) )

  ----------------------------------------------------------------------
  -- M is a cone over the terminal sequence
  --
  -- Truncating to n+1 and then erasing the deepest layer agrees, at
  -- depth n, with truncating to n. Induction on n; the successor step
  -- only rearranges carried pointwise children, so it never compares
  -- functions propositionally.
  --
  -- M 是终序列上的锥
  --
  -- 先截断到 n+1 再抹去最深层,在深度 n 处与直接截断到 n 一致。对 n
  -- 归纳;后继步只重排携带的逐点子树,故绝不命题式地比较函数。

  take-cone : ∀ {n : ℕ} {x : I} (t : M A E x)
            → take {n = n} t ≈Tr drop (take {n = suc n} t)
  take-cone {n = zero}  t = tt
  take-cone {n = suc m} t =
      EqOn.refl (≈A _)
    , λ y → idAdjˢ (≈E _ (M.here t) y)
          , ( (λ e → take-cone (M.below t y e))
            , (λ e → ≈Tr-sym (take-cone (M.below t y e))) )

  ----------------------------------------------------------------------
  -- Finite-depth necessity of bisimulation
  --
  -- Two bisimilar trees agree at every finite depth. The bisimulation's
  -- edge adjunction is reused at every depth; induction is on n and the
  -- recursive calls are the carried pointwise children.
  --
  -- 互模拟的有限深度必要性
  --
  -- 两棵互模拟的树在每个有限深度一致。互模拟的边伴随在每个深度复用;
  -- 对 n 归纳,递归调用即携带的逐点子树。

  bisim→finite : ∀ {x : I} {t s : M A E x}
               → _≈Mˢ_ ≈A ≈E t s
               → (n : ℕ) → take {n = n} t ≈Tr take {n = n} s
  bisim→finite _ zero = tt
  bisim→finite {x = x} p (suc m) =
      _≈Mˢ_.here-eq p
    , λ y →
        let adj , fwd , bwd = _≈Mˢ_.below-eq p y
        in adj
         , ( (λ e  → bisim→finite (fwd e) m)
           , (λ e' → bisim→finite (bwd e') m) )

  ----------------------------------------------------------------------
  -- Limit cone
  --
  -- A compatible family of finite-depth observations, with coherence at
  -- the carried setoid (not _≡_). M supplies a cone via truncation.
  --
  -- 极限锥
  --
  -- 有限深度观察的相容族,相干性在携带 setoid(非 _≡_)上。M 经截断
  -- 给出一个锥。

  record Cone (x : I) : Set ℓeq where
    field
      obs : (n : ℕ) → Tr n x
      coh : (n : ℕ) → obs n ≈Tr drop (obs (suc n))
  open Cone

  take-coneM : ∀ {x : I} → M A E x → Cone x
  take-coneM t .obs n = take {n = n} t
  take-coneM t .coh n = take-cone {n = n} t

  -- Label at depth m+1 of a cone.
  --
  -- 锥在深度 m+1 处的标签。
  cone-head : ∀ {x : I} → Cone x → ℕ → A x
  cone-head c m = head (obs c (suc m))

  -- Cumulative edge relabeling: Γ c m y is the adjunction from the
  -- depth-0 edge fibre to the depth-m edge fibre, built by composing
  -- the adjunctions stored in the cone's coherence. `to` sends a
  -- depth-0 edge to its depth-m representative.
  --
  -- 累积边重定域:Γ c m y 是从深度 0 边纤维到深度 m 边纤维的伴随,
  -- 由锥相干性中存放的伴随复合而成。`to` 把深度 0 的边映到其在深度 m
  -- 的代表。
  relabel : ∀ {x : I} (c : Cone x) (m : ℕ) (y : I)
          → FiberAdjˢ (≈E x (cone-head c m) y)
                       (≈E x (cone-head c 0) y)
  relabel {x = x} c zero    y = idAdjˢ (≈E x (cone-head c 0) y)
  relabel {x = x} c (suc m) y
    with coh c (suc m)
  ... | _ , body
    with body y
  ... | α , _ , _ =
    compAdjˢ (≈E x (cone-head c 0) y)
             (≈E x (cone-head c m) y)
             (≈E x (cone-head c (suc m)) y)
             (relabel c m y) α

  -- Tail cone at the target index y for a depth-0 edge e: its depth-m
  -- observation is the depth-(m+1) child of the cone, read along the
  -- relabelled edge. Coherence is exactly the forward component of the
  -- cone's coherence, using `to (Γ (suc m)) = to α ∘ to (Γ m)`.
  --
  -- 目标索引 y 处、对深度 0 边 e 的尾锥:其深度 m 观察是锥的深度 m+1
  -- 子节点,沿重定域后的边读取。相干性恰为锥相干性的前向分量,用到
  -- `to (Γ (suc m)) = to α ∘ to (Γ m)`。
  tail-obs : ∀ {x : I} (c : Cone x) (y : I)
             (e : E x (cone-head c 0) y) (m : ℕ) → Tr m y
  tail-obs c y e m =
    kids (obs c (suc m)) y (to (relabel c m y) e)

  tail-coh : ∀ {x : I} (c : Cone x) (y : I)
             (e : E x (cone-head c 0) y) (m : ℕ)
           → tail-obs c y e m ≈Tr drop (tail-obs c y e (suc m))
  tail-coh c y e m
    with coh c (suc m)
  ... | _ , body
    with body y
  ... | _ , fwd , _ = fwd (to (relabel c m y) e)

  tail-cone : ∀ {x : I} (c : Cone x) (y : I)
              (e : E x (cone-head c 0) y) → Cone y
  tail-cone c y e .obs = tail-obs c y e
  tail-cone c y e .coh = tail-coh c y e

  ----------------------------------------------------------------------
  -- Mediating map
  --
  -- Every compatible cone realizes an M-tree. The head is the depth-1
  -- label; each child mediates the corresponding tail cone. The only
  -- recursive call is directly under M.below, so the definition is
  -- guarded; all relabeling is carried, no subst.
  --
  -- 中介映射
  --
  -- 每个相容锥都实现为一棵 M-树。头部取深度 1 标签;每个子节点中介相应
  -- 的尾锥。唯一的递归调用直接位于 M.below 之下,故受守护;所有重定域
  -- 皆携带,无 subst。

  mediate : ∀ {x : I} → Cone x → M A E x
  mediate c .M.here        = cone-head c 0
  mediate c .M.below y e   = mediate (tail-cone c y e)

  ----------------------------------------------------------------------
  -- Path B machinery
  --
  -- Finite-depth setoid transitivity: the two edge adjunctions compose
  -- via compAdjˢ and the pointwise children close recursively.
  --
  -- 路径 B 机器
  --
  -- 有限深度 setoid 的传递性:两根边伴随经 compAdjˢ 复合,逐点子树
  -- 递归闭合。

  ≈Tr-trans : ∀ {n : ℕ} {x : I} {q r s : Tr n x}
            → q ≈Tr r → r ≈Tr s → q ≈Tr s
  ≈Tr-trans {n = zero}  _ _ = tt
  ≈Tr-trans {n = suc m} {x = x}
            {(a , k)} {(a' , k')} {(a'' , k'')} (ha₁ , b₁) (ha₂ , b₂) =
      EqOn.trans (≈A x) ha₁ ha₂
    , λ y →
        let adj₁ , f1 , b1c = b₁ y
            adj₂ , f2 , b2c = b₂ y
            adj = compAdjˢ (≈E x a y) (≈E x a' y) (≈E x a'' y)
                            adj₁ adj₂
        in adj
         , ( (λ e   → ≈Tr-trans (f1 e) (f2 (to adj₁ e)))
           , (λ e'' → ≈Tr-trans (b2c e'') (b1c (fro adj₂ e''))) )

  -- Cross-depth label coherence of a cone: the depth-0 label is
  -- related to the depth-m label by composing the label components of
  -- coh.
  --
  -- 锥的跨深度标签相干性:深度 0 标签经 coh 的标签分量复合而与深度 m
  -- 标签相关。
  cone-label-coh : ∀ {x : I} (c : Cone x) (m : ℕ)
                 → EqOn._≈_ (≈A x) (cone-head c 0) (cone-head c m)
  cone-label-coh c zero    = EqOn.refl (≈A _)
  cone-label-coh c (suc m)
    with coh c (suc m)
  ... | ha , _ = EqOn.trans (≈A _) (cone-label-coh c m) ha

  -- Edge-setoid congruence of a cone, carried at the cone and every
  -- tail cone. `here-cong` says equivalent edges at depth m index
  -- pointwise-related depth children; `tail-cong` lifts the same to
  -- each depth-0 tail cone.
  --
  -- 锥的边 setoid 同余,携带于锥及其每个尾锥。`here-cong` 表示深度 m
  -- 处等价的边索引出逐点相关的深度子树;`tail-cong` 将其提升到每个
  -- 深度 0 尾锥。
  record ConeCong {x : I} (c : Cone x) : Set ℓeq where
    coinductive
    field
      here-cong : (m : ℕ) (y : I)
                  (e e' : E x (cone-head c m) y)
                → EqOn._≈_ (≈E x (cone-head c m) y) e e'
                → _≈Tr_ {n = m} (kids (obs c (suc m)) y e)
                              (kids (obs c (suc m)) y e')
      tail-cong : (y : I) (e : E x (cone-head c 0) y)
                → ConeCong (tail-cone c y e)
  open ConeCong

  -- Conditional round trip (limit side): under ConeCong, truncating
  -- the mediating tree reproduces the cone's observation at every
  -- depth. The forward component is the induction hypothesis at the
  -- tail cone; the backward component closes with the adjunction
  -- counit, here-cong and finite-depth transitivity.
  --
  -- 条件性往返(极限侧):在 ConeCong 下,截断中介树逐深度复现锥的
  -- 观察。前向分量即尾锥处的归纳假设;反向分量由伴随余单位、here-cong
  -- 与有限深度传递性闭合。
  take-mediate : ∀ {x : I} {c : Cone x} (cc : ConeCong c) (n : ℕ)
               → take {n = n} (mediate c) ≈Tr obs c n
  take-mediate cc zero    = tt
  take-mediate {x = x} {c = c} cc (suc m) =
      cone-label-coh c m
    , λ y →
        let Γ  = relabel c m y
            cg = λ e → tail-cong cc y e
        in Γ
         , ( (λ e   → take-mediate (cg e) m)
           , (λ e'  →
               let ih = take-mediate (cg (fro Γ e')) m
                   hc = here-cong cc m y (to Γ (fro Γ e')) e' (ε Γ e')
               in ≈Tr-sym (≈Tr-trans ih hc)) )

  ----------------------------------------------------------------------
  -- Uniqueness and the finite-to-bisimulation boundary
  --
  -- `mediate c` is the anamorphism of the cone-induced observation
  -- coalgebra, so uniqueness of mediating trees up to _≈Mˢ_ is exactly
  -- the terminal-coalgebra uniqueness already proved in
  -- MCorrSetoidCoalg (terminalUpToBisim / !-unique). The limit→νF leg
  -- therefore holds unconditionally, with all cross-depth edge
  -- relabeling carried by FiberAdjˢ.
  --
  -- Pointwise finite agreement alone, (n : ℕ) → take n t ≈Tr take n s,
  -- does NOT yield _≈Mˢ_: each depth selects its own edge adjunction
  -- and the choices need not be coherent across depths. A cross-depth
  -- coherent adjunction is precisely the data carried by a _≈Mˢ_
  -- witness, so no weaker pointwise lemma exists without funExt or an
  -- edge-congruence hypothesis such as ConeCong. This is a structural
  -- boundary, not a missing construction. For a generic cone the
  -- cumulative adjunction is the identity only up to the edge EqOn
  -- (η/ε), and the backward leg compares children at η-related edges;
  -- closing it propositionally either carries the cumulative adjunction
  -- as cone data (identity for truncation cones) or assumes child maps
  -- are edge-setoid congruent — the hypothesis ConeCong.
  --
  -- 唯一性与有限→互模拟边界
  --
  -- `mediate c` 即锥诱导的观察余代数的 anamorphism,故中介树到 _≈Mˢ_
  -- 的唯一性正是 MCorrSetoidCoalg 已证的终余代数唯一性
  -- (terminalUpToBisim / !-unique)。因此极限→νF 一侧无条件成立,
  -- 跨深度边重定域全部由 FiberAdjˢ 携带。
  --
  -- 仅逐点有限一致 (n : ℕ) → take n t ≈Tr take n s 并不能得出 _≈Mˢ_:
  -- 每个深度各自选择边伴随,跨深度未必相干。跨深度一致的边伴随恰是
  -- _≈Mˢ_ 见证所携带的数据,故在没有 funExt 或 ConeCong 这类边同余
  -- 假设时,不存在更弱的逐点引理。这是结构性边界,而非遗漏的构造。
  -- 对一般锥,累积伴随只在边 EqOn(η/ε)意义下为恒等,反向腿要在 η
  -- 相关的边处比较子树;命题式地闭合它,要么把累积伴随作为锥的数据
  -- 携带(截断锥处即恒等),要么假设子树映射是边 setoid 同余——即
  -- ConeCong 假设。
  ----------------------------------------------------------------------