1	# Digit sequences of a known length
2	# =================================
3	#
4	# Digits(n) is a sequence of exactly n hexadecimal digits: the length is part
5	# of the type, so a trace ID is a Digits(32n) and a flag byte a Digits(2n).
6	# NonZero<n> adds the proof that the digits are not all zero, which W3C 3.2.2.3
7	# and 3.2.2.4 require of trace and parent IDs. This module is internal to the
8	# package. proofs/digits.bend proves that n digits always format as n
9	# characters.
10	
11	import Base
12	import ./hex.bend as Hex
13	
14	# The length is part of the type. A Digits(32n) cannot contain 31 or 33 digits.
15	# This is the same type-family pattern that Base uses for Word(n).
16	#
17	# The empty sequence: the only value of Digits(0n).
18	type Digits.Nil is Data:
19	  DNil{}
20	
21	# A first digit followed by a sequence of p digits: a value of Digits(1n+p).
22	type Digits.Con<-p: Nat> is Data:
23	  DCon{head: Hex.Digit, tail: Digits(p)}
24	
25	# The type of sequences of exactly n digits, computed from n: Digits(0n) is
26	# Digits.Nil and Digits(1n+p) is Digits.Con<p>.
27	def Digits(n: Nat) -> Data:
28	  match n:
29	    case 0n:
30	      Digits.Nil
31	    case 1n+p:
32	      Digits.Con<p>
33	
34	# The n lowercase characters of the digits, in order.
35	def Digits.to_string(n: Nat, digits: Digits(n)) -> String:
36	  match n:
37	    case 0n:
38	      ""
39	    case 1n+p:
40	      match digits:
41	        case DCon{head, tail}:
42	          SCon{Hex.Digit.to_char(head), Digits.to_string(p, tail)}
43	
44	# Whether every digit is 0. The empty sequence counts as zero.
45	def Digits.is_zero(n: Nat, digits: Digits(n)) -> Bool:
46	  match n:
47	    case 0n:
48	      True{}
49	    case 1n+p:
50	      match digits:
51	        case DCon{head, tail}:
52	          Bool.and(Hex.Digit.is_zero(head), Digits.is_zero(p, tail))
53	
54	# The eight digits of a word, most significant first: the first digit holds
55	# bits 31 to 28 and the last digit bits 3 to 0.
56	def Digits.of_u32(word: U32) -> Digits(8n):
57	  match word:
58	    case U32{WCon{b0, WCon{b1, WCon{b2, WCon{b3, WCon{b4, WCon{b5, WCon{b6, WCon{b7, WCon{b8, WCon{b9, WCon{b10, WCon{b11, WCon{b12, WCon{b13, WCon{b14, WCon{b15, WCon{b16, WCon{b17, WCon{b18, WCon{b19, WCon{b20, WCon{b21, WCon{b22, WCon{b23, WCon{b24, WCon{b25, WCon{b26, WCon{b27, WCon{b28, WCon{b29, WCon{b30, WCon{b31, WNil{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}:
59	      DCon{Hex.Digit.from_bits(b28, b29, b30, b31), DCon{Hex.Digit.from_bits(b24, b25, b26, b27), DCon{Hex.Digit.from_bits(b20, b21, b22, b23), DCon{Hex.Digit.from_bits(b16, b17, b18, b19), DCon{Hex.Digit.from_bits(b12, b13, b14, b15), DCon{Hex.Digit.from_bits(b8, b9, b10, b11), DCon{Hex.Digit.from_bits(b4, b5, b6, b7), DCon{Hex.Digit.from_bits(b0, b1, b2, b3), DNil{}}}}}}}}}
60	
61	# The word whose eight digits these are, most significant first.
62	def Digits.to_u32(digits: Digits(8n)) -> U32:
63	  match digits:
64	    case DCon{+d7, DCon{+d6, DCon{+d5, DCon{+d4, DCon{+d3, DCon{+d2, DCon{+d1, DCon{+d0, DNil{}}}}}}}}}:
65	      U32{WCon{Hex.Digit.is_odd(d0), WCon{Hex.Digit.has_bit1(d0), WCon{Hex.Digit.has_bit2(d0), WCon{Hex.Digit.has_bit3(d0), WCon{Hex.Digit.is_odd(d1), WCon{Hex.Digit.has_bit1(d1), WCon{Hex.Digit.has_bit2(d1), WCon{Hex.Digit.has_bit3(d1), WCon{Hex.Digit.is_odd(d2), WCon{Hex.Digit.has_bit1(d2), WCon{Hex.Digit.has_bit2(d2), WCon{Hex.Digit.has_bit3(d2), WCon{Hex.Digit.is_odd(d3), WCon{Hex.Digit.has_bit1(d3), WCon{Hex.Digit.has_bit2(d3), WCon{Hex.Digit.has_bit3(d3), WCon{Hex.Digit.is_odd(d4), WCon{Hex.Digit.has_bit1(d4), WCon{Hex.Digit.has_bit2(d4), WCon{Hex.Digit.has_bit3(d4), WCon{Hex.Digit.is_odd(d5), WCon{Hex.Digit.has_bit1(d5), WCon{Hex.Digit.has_bit2(d5), WCon{Hex.Digit.has_bit3(d5), WCon{Hex.Digit.is_odd(d6), WCon{Hex.Digit.has_bit1(d6), WCon{Hex.Digit.has_bit2(d6), WCon{Hex.Digit.has_bit3(d6), WCon{Hex.Digit.is_odd(d7), WCon{Hex.Digit.has_bit1(d7), WCon{Hex.Digit.has_bit2(d7), WCon{Hex.Digit.has_bit3(d7), WNil{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
66	
67	# The digits of `left` followed by those of `right`: m + n digits. Identifiers
68	# are built from source words this way, eight digits per word.
69	def Digits.append(m: Nat, -n: Nat, left: Digits(m), right: Digits(n)) -> Digits(Nat.add(m, n)):
70	  match m:
71	    case 0n:
72	      match left:
73	        case DNil{}:
74	          right
75	    case 1n+p:
76	      match left:
77	        case DCon{head, tail}:
78	          DCon{head, Digits.append(p, n, tail, right)}
79	
80	# n digits that are not all zero. `evidence` is the proof. The equality is
81	# checked statically; compiled evidence is a null placeholder. Keeping its
82	# binder usable lets later proofs recover and reuse this guarantee. Even direct
83	# construction must supply a proof that these digits are not zero.
84	type NonZero<-n: Nat> is Data:
85	  NonZero{digits: Digits(n), evidence: {Digits.is_zero(n, digits) == False{} : Bool}}
86	
87	# Carry the equation into the branch: matching status refines its right side.
88	# The value is built only in the False case, where the equation is the proof.
89	def NonZero.new.checked(-n: Nat, digits: Digits(n), status: Bool,
90	  evidence: {Digits.is_zero(n, digits) == status : Bool}) -> Maybe<&2, NonZero<n>>:
91	  match status:
92	    case True{}:
93	      None{}
94	    case False{}:
95	      Some{NonZero{digits, evidence}}
96	
97	# Attach the proof that the digits are not all zero, or None when they are.
98	def NonZero.new(+n: Nat, +digits: Digits(n)) -> Maybe<&2, NonZero<n>>:
99	  NonZero.new.checked(n, digits, Digits.is_zero(n, digits), {==})
100	
101	# The digits, without their proof.
102	def NonZero.digits(-n: Nat, value: NonZero<n>) -> Digits(n):
103	  match value:
104	    case NonZero{digits, evidence}:
105	      digits
106	
107	# The n lowercase characters of the digits.
108	def NonZero.to_string(n: Nat, value: NonZero<n>) -> String:
109	  Digits.to_string(n, NonZero.digits(n, value))