;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
;; RUN: foreach %s %t wasm-opt -all --minimize-rec-groups -S -o - | filecheck %s

;; A module with no heap types at all should be ok.
(module
  ;; CHECK:      (global $g i32 (i32.const 0))
  (global $g i32 (i32.const 0))
)

;; A module with a single heap type should be ok.
(module
  ;; CHECK:      (type $t (struct))
  (type $t (struct))
  ;; CHECK:      (global $g (ref null $t) (ref.null none))
  (global $g (ref null $t) (ref.null none))
)

;; Split a rec group containing independent types
(module
  (rec
    ;; CHECK:      (type $a (struct (field i32)))
    (type $a (struct (field i32)))
    ;; CHECK:      (type $b (struct (field i64)))
    (type $b (struct (field i64)))
    ;; CHECK:      (type $c (struct (field f32)))
    (type $c (struct (field f32)))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
  ;; CHECK:      (global $c (ref null $c) (ref.null none))
  (global $c (ref null $c) (ref.null none))
)

;; Split a rec group containing types that depend on each other but belong to
;; different SCCs.
(module
  (rec
    ;; CHECK:      (type $a (struct))
    (type $a (struct))
    ;; CHECK:      (type $b (struct (field (ref $a))))
    (type $b (struct (field (ref $a))))
    ;; CHECK:      (type $c (struct (field (ref $b))))
    (type $c (struct (field (ref $b))))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
  ;; CHECK:      (global $c (ref null $c) (ref.null none))
  (global $c (ref null $c) (ref.null none))
)

;; Reverse the order of the previous case. The output should still be in a valid
;; order.
(module
  (rec
    ;; CHECK:      (type $a (struct))

    ;; CHECK:      (type $b (struct (field (ref $a))))

    ;; CHECK:      (type $c (struct (field (ref $b))))
    (type $c (struct (field (ref $b))))
    (type $b (struct (field (ref $a))))
    (type $a (struct))
  )

  ;; CHECK:      (global $c (ref null $c) (ref.null none))
  (global $c (ref null $c) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
)

;; Now all the types are in the same SCC.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $c (struct (field (ref $a))))

    ;; CHECK:       (type $b (struct (field (ref $c))))

    ;; CHECK:       (type $a (struct (field (ref $b))))
    (type $a (struct (field (ref $b))))
    (type $b (struct (field (ref $c))))
    (type $c (struct (field (ref $a))))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
)

;; Only two of the types are in the same SCC.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $b (struct (field (ref $a))))

    ;; CHECK:       (type $a (struct (field (ref $b))))
    (type $a (struct (field (ref $b))))
    (type $b (struct (field (ref $a))))
    ;; CHECK:      (type $c (struct (field (ref $a))))
    (type $c (struct (field (ref $a))))
  )

  ;; CHECK:      (global $c (ref null $c) (ref.null none))
  (global $c (ref null $c) (ref.null none))
)

;; Same, but change which two are in the SCC. The output order should still be
;; valid.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $c (struct (field (ref $b))))

    ;; CHECK:       (type $b (struct (field (ref $c))))

    ;; CHECK:      (type $a (struct (field (ref $b))))
    (type $a (struct (field (ref $b))))
    (type $b (struct (field (ref $c))))
    (type $c (struct (field (ref $b))))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
)

;; Two types that are in conflicting SCCs should be disambiguated. In this case
;; there are no different permutations, so we use a brand.
(module
  (rec
    ;; CHECK:      (type $a (func))
    (type $a (func))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $1 (struct))

    ;; CHECK:       (type $b (func))
    (type $b (func))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null nofunc))
  (global $a (ref null $a) (ref.null nofunc))
  ;; CHECK:      (global $b (ref null $b) (ref.null nofunc))
  (global $b (ref null $b) (ref.null nofunc))
)

;; Same as above, but now the types match the initial brand, so we have to skip
;; to the next one.
(module
  (rec
    ;; CHECK:      (type $a (struct))
    (type $a (struct))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $1 (array (mut i8)))

    ;; CHECK:       (type $b (struct))
    (type $b (struct))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
)

;; Now we have groups that match both the initial brand and the next one, so
;; adding the brand will cause a conflict. We will have to go to the next brand.
(module
  (rec
    ;; CHECK:      (type $a1 (struct))
    (type $a1 (struct))
    ;; CHECK:      (type $b1 (array (mut i8)))

    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $2 (array (mut i8)))

    ;; CHECK:       (type $a2 (struct))
    (type $a2 (struct))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a3 (struct))
    (type $a3 (struct))
    (type $b1 (array (mut i8)))
    ;; CHECK:       (type $5 (array (mut i8)))

    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $6 (array i8))

    ;; CHECK:       (type $b2 (array (mut i8)))
    (type $b2 (array (mut i8)))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
  (global $a2 (ref null $a2) (ref.null none))
  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
  (global $a3 (ref null $a3) (ref.null none))
  ;; CHECK:      (global $b1 (ref null $b1) (ref.null none))
  (global $b1 (ref null $b1) (ref.null none))
  ;; CHECK:      (global $b2 (ref null $b2) (ref.null none))
  (global $b2 (ref null $b2) (ref.null none))
)

;; Now the types have more fields, including one referring to a previous SCC.
(module
  (rec
    ;; CHECK:      (type $other (struct (field i32)))
    (type $other (struct (field i32)))
    ;; CHECK:      (type $a (struct (field anyref) (field i32) (field (ref $other))))
    (type $a (struct (field anyref i32 (ref $other))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $2 (struct))

    ;; CHECK:       (type $b (struct (field anyref) (field i32) (field (ref $other))))
    (type $b (struct (field anyref i32 (ref $other))))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
)

;; Now there is a third type and we can disambiguate it by using a different
;; permutation with the same brand.
(module
  (rec
    ;; CHECK:      (type $a (struct))
    (type $a (struct))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $1 (array (mut i8)))

    ;; CHECK:       (type $b (struct))
    (type $b (struct))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $c (struct))
    (type $c (struct))
  )

  ;; CHECK:       (type $4 (array (mut i8)))

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
  ;; CHECK:      (global $c (ref null $c) (ref.null none))
  (global $c (ref null $c) (ref.null none))
)

;; Adding a fourth type requires using yet another brand.
(module
  (rec
    ;; CHECK:      (type $a (struct))
    (type $a (struct))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $1 (array (mut i8)))

    ;; CHECK:       (type $b (struct))
    (type $b (struct))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $c (struct))
    (type $c (struct))
    ;; CHECK:       (type $4 (array (mut i8)))

    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $5 (array i8))

    ;; CHECK:       (type $d (struct))
    (type $d (struct))
  )

  ;; CHECK:      (global $a (ref null $a) (ref.null none))
  (global $a (ref null $a) (ref.null none))
  ;; CHECK:      (global $b (ref null $b) (ref.null none))
  (global $b (ref null $b) (ref.null none))
  ;; CHECK:      (global $c (ref null $c) (ref.null none))
  (global $c (ref null $c) (ref.null none))
  ;; CHECK:      (global $d (ref null $d) (ref.null none))
  (global $d (ref null $d) (ref.null none))
)

;; After $a1 and $a2 are dismabiguated with a brand, $b1 and $b2 require no
;; further disambiguation.
(module
  (rec
    ;; CHECK:      (type $a1 (struct))
    (type $a1 (struct))
    ;; CHECK:      (type $b1 (struct (field (ref $a1))))

    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $2 (array (mut i8)))

    ;; CHECK:       (type $a2 (struct))
    (type $a2 (struct))
    (type $b1 (struct (field (ref $a1))))
    ;; CHECK:      (type $b2 (struct (field (ref $a2))))
    (type $b2 (struct (field (ref $a2))))
  )

  ;; CHECK:      (global $b1 (ref null $b1) (ref.null none))
  (global $b1 (ref null $b1) (ref.null none))
  ;; CHECK:      (global $b2 (ref null $b2) (ref.null none))
  (global $b2 (ref null $b2) (ref.null none))
)

;; Now we can disambiguate by permuting without a brand.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))

    ;; CHECK:       (type $a1 (struct (field (ref $b1)) (field i32)))
    (type $a1 (struct (field (ref $b1) i32)))
    (type $b1 (struct (field (ref $a1))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a2 (struct (field (ref $b2)) (field i32)))
    (type $a2 (struct (field (ref $b2) i32)))
    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
    (type $b2 (struct (field (ref $a2))))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
  (global $a2 (ref null $a2) (ref.null none))
)

;; But when we run out of permutations, we need a brand again.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))

    ;; CHECK:       (type $a1 (struct (field (ref $b1)) (field i32)))
    (type $a1 (struct (field (ref $b1) i32)))
    (type $b1 (struct (field (ref $a1))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a2 (struct (field (ref $b2)) (field i32)))
    (type $a2 (struct (field (ref $b2) i32)))
    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
    (type $b2 (struct (field (ref $a2))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $4 (struct))

    ;; CHECK:       (type $b3 (struct (field (ref $a3))))

    ;; CHECK:       (type $a3 (struct (field (ref $b3)) (field i32)))
    (type $a3 (struct (field (ref $b3) i32)))
    (type $b3 (struct (field (ref $a3))))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
  (global $a2 (ref null $a2) (ref.null none))
  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
  (global $a3 (ref null $a3) (ref.null none))
)

;; Same as above, except the middle global now refers to $b2 instead of $a2,
;; changing the initial order of types in the middle SCC. We arrive at the same
;; result by a different path.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))

    ;; CHECK:       (type $a1 (struct (field (ref $b1)) (field i32)))
    (type $a1 (struct (field (ref $b1) i32)))
    (type $b1 (struct (field (ref $a1))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a2 (struct (field (ref $b2)) (field i32)))
    (type $a2 (struct (field (ref $b2) i32)))
    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
    (type $b2 (struct (field (ref $a2))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $4 (struct))

    ;; CHECK:       (type $b3 (struct (field (ref $a3))))

    ;; CHECK:       (type $a3 (struct (field (ref $b3)) (field i32)))
    (type $a3 (struct (field (ref $b3) i32)))
    (type $b3 (struct (field (ref $a3))))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $b2 (ref null $b2) (ref.null none))
  (global $b2 (ref null $b2) (ref.null none))
  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
  (global $a3 (ref null $a3) (ref.null none))
)

;; Now we can't differentiate by permutation because of automorphisms.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))

    ;; CHECK:       (type $a1 (struct (field (ref $b1))))
    (type $a1 (struct (field (ref $b1))))
    (type $b1 (struct (field (ref $a1))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $2 (struct))

    ;; CHECK:       (type $b2 (struct (field (ref $a2))))

    ;; CHECK:       (type $a2 (struct (field (ref $b2))))
    (type $a2 (struct (field (ref $b2))))
    (type $b2 (struct (field (ref $a2))))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
  (global $a2 (ref null $a2) (ref.null none))
)

;; Now we can't differentiate by permutation because the subtyping constraint
;; admits only one ordering.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a1 (sub (struct (field (ref $b1)))))
    (type $a1 (sub (struct (field (ref $b1)))))
    ;; CHECK:       (type $b1 (sub $a1 (struct (field (ref $b1)))))
    (type $b1 (sub $a1 (struct (field (ref $b1)))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $2 (struct))

    ;; CHECK:       (type $a2 (sub (struct (field (ref $b2)))))
    (type $a2 (sub (struct (field (ref $b2)))))
    ;; CHECK:       (type $b2 (sub $a2 (struct (field (ref $b2)))))
    (type $b2 (sub $a2 (struct (field (ref $b2)))))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
  (global $a2 (ref null $a2) (ref.null none))
)


;; Now there are only two possible orderings admitted by the subtyping
;; constraint.
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a1 (sub (struct (field (ref $b1)))))
    (type $a1 (sub (struct (field (ref $b1)))))
    ;; CHECK:       (type $c1 (sub $a1 (struct (field (ref $b1)))))

    ;; CHECK:       (type $b1 (sub $a1 (struct (field (ref $b1)) (field (ref $c1)))))
    (type $b1 (sub $a1 (struct (field (ref $b1)) (ref $c1))))
    (type $c1 (sub $a1 (struct (field (ref $b1)))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $a2 (sub (struct (field (ref $b2)))))
    (type $a2 (sub (struct (field (ref $b2)))))
    ;; CHECK:       (type $b2 (sub $a2 (struct (field (ref $b2)) (field (ref $c2)))))
    (type $b2 (sub $a2 (struct (field (ref $b2)) (ref $c2))))
    ;; CHECK:       (type $c2 (sub $a2 (struct (field (ref $b2)))))
    (type $c2 (sub $a2 (struct (field (ref $b2)))))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $6 (struct))

    ;; CHECK:       (type $a3 (sub (struct (field (ref $b3)))))
    (type $a3 (sub (struct (field (ref $b3)))))
    ;; CHECK:       (type $c3 (sub $a3 (struct (field (ref $b3)))))

    ;; CHECK:       (type $b3 (sub $a3 (struct (field (ref $b3)) (field (ref $c3)))))
    (type $b3 (sub $a3 (struct (field (ref $b3)) (ref $c3))))
    (type $c3 (sub $a3 (struct (field (ref $b3)))))
  )

  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
  (global $a1 (ref null $a1) (ref.null none))
  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
  (global $a2 (ref null $a2) (ref.null none))
  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
  (global $a3 (ref null $a3) (ref.null none))
)

;; We must avoid conflicts with public types.
(module
  ;; CHECK:      (type $public (struct))
  (type $public (struct))
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $1 (array (mut i8)))

    ;; CHECK:       (type $private (struct))
    (type $private (struct))
    (type $other (struct (field (ref null $private))))
  )

  ;; CHECK:      (global $public (ref null $public) (ref.null none))
  (global $public (export "g") (ref null $public) (ref.null none))

  ;; CHECK:      (global $private (ref null $private) (ref.null none))
  (global $private (ref null $private) (ref.null none))
)

;; Same as above, but now the public types are more complicated.
;; CHECK:      (export "g" (global $public))
(module
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $publicA (struct (field (ref null $publicB))))
    (type $publicA (struct (field (ref null $publicB))))
    ;; CHECK:       (type $publicB (struct (field (ref null $publicA))))
    (type $publicB (struct (field (ref null $publicA))))
  )
  (rec
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $2 (struct))

    ;; CHECK:       (type $privateB (struct (field (ref null $privateA))))

    ;; CHECK:       (type $privateA (struct (field (ref null $privateB))))
    (type $privateA (struct (field (ref null $privateB))))
    (type $privateB (struct (field (ref null $privateA))))
    (type $other (struct (field i32)))
  )

  ;; CHECK:      (global $public (ref null $publicA) (ref.null none))
  (global $public (export "g") (ref null $publicA) (ref.null none))
  ;; CHECK:      (global $private (ref null $privateA) (ref.null none))
  (global $private (ref null $privateA) (ref.null none))
)

;; Now the conflict with the public type does not arise until we try to resolve
;; a conflict between the private types.
;; CHECK:      (export "g" (global $public))
(module
  (rec
    ;; CHECK:      (type $privateA (struct (field i32) (field i64)))

    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $publicBrand (struct))
    (type $publicBrand (struct))
    ;; CHECK:       (type $public (struct (field i32) (field i64)))
    (type $public (struct (field i32 i64)))
  )
  (rec
    (type $privateA (struct (field i32 i64)))
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $privateB (struct (field i32) (field i64)))
    (type $privateB (struct (field i32 i64)))
  )

  ;; CHECK:       (type $4 (struct))

  ;; CHECK:      (global $public (ref null $public) (ref.null none))
  (global $public (export "g") (ref null $public) (ref.null none))

  ;; CHECK:      (global $privateA (ref null $privateA) (ref.null none))
  (global $privateA (ref null $privateA) (ref.null none))
  ;; CHECK:      (global $privateB (ref null $privateB) (ref.null none))
  (global $privateB (ref null $privateB) (ref.null none))
)
;; CHECK:      (export "g" (global $public))