git.iko.soy/j
on master help sign in
j/src/shape.rs
462 lines 18 kB history raw
1//! Shape computation from typedecls (§4.12) and runtime contracts (§4.13).
3use crate::ast::TypeExpr;
4use crate::value::{PrimKind, ShapeKind, ShapeVal, Value};
5use std::collections::{BTreeSet, HashMap, HashSet};
7#[derive(Default, Clone)]
8pub struct Shapes {
9 /// name -> its declared type
10 pub decls: HashMap<String, TypeExpr>,
11 /// Memo for `shape_of`. A contract check against a record type asks for
12 /// the shape on every call, and computing it builds the field set afresh;
13 /// the declarations never change once the config is loaded.
14 memo: std::cell::RefCell<HashMap<String, Option<ShapeVal>>>,
17impl Shapes {
18 pub fn new() -> Shapes {
19 Shapes::default()
20 }
22 /// Compute the ShapeVal for a type name used as a value (§4.12).
23 /// Returns None if the name is undeclared, or its shape is a function,
24 /// a list, or otherwise not usable.
25 pub fn shape_of(&self, name: &str) -> Option<ShapeVal> {
26 if let Some(hit) = self.memo.borrow().get(name) {
27 return hit.clone();
28 }
29 let computed = self.shape_of_uncached(name);
30 self.memo
31 .borrow_mut()
32 .insert(name.to_string(), computed.clone());
33 computed
34 }
36 fn shape_of_uncached(&self, name: &str) -> Option<ShapeVal> {
37 match name {
38 "Int" => Some(ShapeVal {
39 name: name.into(),
40 kind: ShapeKind::Prim(PrimKind::Int),
41 }),
42 "Text" => Some(ShapeVal {
43 name: name.into(),
44 kind: ShapeKind::Prim(PrimKind::Text),
45 }),
46 "Bool" => Some(ShapeVal {
47 name: name.into(),
48 kind: ShapeKind::Prim(PrimKind::Bool),
49 }),
50 "Id" => Some(ShapeVal {
51 name: name.into(),
52 kind: ShapeKind::Prim(PrimKind::Id),
53 }),
54 "Blob" => Some(ShapeVal {
55 name: name.into(),
56 kind: ShapeKind::Prim(PrimKind::Blob),
57 }),
58 "Shape" => None, // Shape itself is primitive but extract Shape is odd; crash
59 _ => {
60 let ty = self.decls.get(name)?;
61 self.shape_of_type(ty).map(|kind| ShapeVal {
62 name: name.into(),
63 kind,
64 })
65 }
66 }
67 }
69 fn shape_of_type(&self, ty: &TypeExpr) -> Option<ShapeKind> {
70 // an alias takes its type's shape (§4.12); `unfold` is bounded, so a
71 // cycle of aliases (`Self = Self`) ends on a name like any other
72 match self.unfold(ty) {
73 TypeExpr::Con(n) if is_primitive(n) => self.shape_of(n).map(|s| s.kind),
74 // undeclared, a type variable, or an alias cycle: not a usable
75 // shape, and a crash when used (§4.12)
76 TypeExpr::Con(_) => None,
77 TypeExpr::Record(fields) => Some(ShapeKind::Record(
78 fields.iter().map(|(n, _)| n.clone()).collect(),
79 )),
80 TypeExpr::List(_) | TypeExpr::Fun(_, _) => None,
81 }
82 }
84 /// Unfold an alias chain by reference. Contracts are checked at every
85 /// call, so cloning the type each time — a `Vec` of `String`s for a record
86 /// type — was a per-application allocation.
87 pub fn unfold<'a>(&'a self, ty: &'a TypeExpr) -> &'a TypeExpr {
88 let mut cur = ty;
89 // a declaration cycle would otherwise spin here; the bound is far
90 // above any real alias chain
91 for _ in 0..64 {
92 match cur {
93 TypeExpr::Con(n) if !is_primitive(n) && !is_type_var(n) => {
94 match self.decls.get(n) {
95 Some(decl) => cur = decl,
96 None => return cur,
97 }
98 }
99 _ => return cur,
100 }
101 }
102 cur
103 }
106fn is_primitive(n: &str) -> bool {
107 matches!(n, "Int" | "Text" | "Bool" | "Id" | "Blob" | "Shape")
110fn is_type_var(n: &str) -> bool {
111 n.chars().next().map(|c| c.is_ascii_lowercase()).unwrap_or(false)
114/// A compiled signature: a chain of parameter types and a final result type.
115/// The types are shared, so handing one out is a refcount bump rather than a
116/// deep copy — contracts are consulted on every call.
117#[derive(Clone, Debug)]
118pub struct Contract {
119 pub params: Vec<Rc2<TypeExpr>>,
120 pub result: Rc2<TypeExpr>,
123pub fn compile_contract(shapes: &Shapes, ty: &TypeExpr) -> Contract {
124 let mut params = Vec::new();
125 let mut cur = ty;
126 // an alias met again on this walk refers to itself (`Stream = Int ->
127 // Stream`, or `A = B` with `B = A`) and would unfold forever; the walk
128 // stops there, and the result is checked as that alias
129 let mut unfolded: HashSet<&str> = HashSet::new();
130 loop {
131 match cur {
132 TypeExpr::Fun(a, b) => {
133 params.push(a.clone());
134 cur = b;
135 }
136 TypeExpr::Con(n) => {
137 // alias of a function type is unfolded (§4.13)
138 if !is_primitive(n) && !is_type_var(n) && unfolded.insert(n.as_str()) {
139 if let Some(decl) = shapes.decls.get(n) {
140 cur = decl;
141 continue;
142 }
143 }
144 break;
145 }
146 _ => break,
147 }
148 }
149 Contract {
150 params,
151 result: Rc2::new(cur.clone()),
152 }
155/// Check one level deep (§4.13). On failure, describe expected and got.
156pub fn check(shapes: &Shapes, ty: &TypeExpr, v: &Value) -> Result<(), String> {
157 let ty = shapes.unfold(ty);
158 match ty {
159 TypeExpr::Con(n) => {
160 if is_type_var(n) {
161 return Ok(());
162 }
163 match n.as_str() {
164 "Int" => kind_check(matches!(v, Value::Int(_)), "Int", v),
165 "Text" => kind_check(matches!(v, Value::Text(_)), "Text", v),
166 "Bool" => kind_check(matches!(v, Value::Bool(_)), "Bool", v),
167 "Id" => kind_check(matches!(v, Value::Id(_)), "Id", v),
168 "Blob" => kind_check(matches!(v, Value::Blob(_)), "Blob", v),
169 "Shape" => kind_check(matches!(v, Value::Shape(_)), "Shape", v),
170 _ => {
171 // shape name: exact field set (aliases resolved by shape_of)
172 match shapes.shape_of(n) {
173 Some(ShapeVal {
174 kind: ShapeKind::Record(fields),
175 ..
176 }) => record_check(&fields, n, v),
177 Some(ShapeVal {
178 kind: ShapeKind::Prim(p),
179 ..
180 }) => {
181 let ok = matches!(
182 (p, v),
183 (PrimKind::Int, Value::Int(_))
184 | (PrimKind::Text, Value::Text(_))
185 | (PrimKind::Bool, Value::Bool(_))
186 | (PrimKind::Id, Value::Id(_))
187 | (PrimKind::Blob, Value::Blob(_))
188 );
189 kind_check(ok, n, v)
190 }
191 _ => Ok(()),
192 }
193 }
194 }
195 }
196 TypeExpr::List(_) => kind_check(matches!(v, Value::List(_)), "a list", v),
197 TypeExpr::Record(fields) => {
198 let set: BTreeSet<String> = fields.iter().map(|(n, _)| n.clone()).collect();
199 record_check(&set, "record", v)
200 }
201 TypeExpr::Fun(_, _) => kind_check(matches!(v, Value::Fun(_)), "a function", v),
202 }
205fn kind_check(ok: bool, expected: &str, v: &Value) -> Result<(), String> {
206 if ok {
207 Ok(())
208 } else {
209 Err(format!("expected {}, got {}", expected, v.kind_name()))
210 }
213fn record_check(expected: &BTreeSet<String>, name: &str, v: &Value) -> Result<(), String> {
214 match v {
215 Value::Record(m) => {
216 let got: BTreeSet<String> = m.keys().cloned().collect();
217 if *expected == got {
218 Ok(())
219 } else {
220 Err(format!(
221 "expected {} {}, got {}",
222 if name == "record" { "" } else { name },
223 fmt_fields(expected),
224 fmt_fields(&got)
225 ))
226 }
227 }
228 _ => Err(format!("expected {}, got {}", name, v.kind_name())),
229 }
232pub fn fmt_fields(s: &BTreeSet<String>) -> String {
233 format!("{{ {} }}", s.iter().cloned().collect::<Vec<_>>().join(", "))
236/// A human-readable name for a type, used in contract messages.
237pub fn type_name(ty: &TypeExpr) -> String {
238 match ty {
239 TypeExpr::Con(n) => n.clone(),
240 TypeExpr::List(t) => format!("[{}]", type_name(t)),
241 TypeExpr::Record(fields) => {
242 let parts: Vec<String> = fields
243 .iter()
244 .map(|(n, t)| format!("{} : {}", n, type_name(t)))
245 .collect();
246 format!("{{ {} }}", parts.join(", "))
247 }
248 TypeExpr::Fun(a, b) => format!("{} -> {}", type_name(a), type_name(b)),
249 }
252// ----------------------------------------------------------------------
253// contract expressions: the type of a (possibly partially applied) function
254// ----------------------------------------------------------------------
256use std::rc::Rc as Rc2;
258#[derive(Clone, Debug)]
259pub enum ContractExpr {
260 /// no contract information; arg checks pass through
261 Unknown,
262 /// a signature with its first `at` parameters already supplied; advancing
263 /// it is an index bump, where rebuilding the shortened parameter list
264 /// copied every remaining type on every application
265 Known { contract: Rc2<Contract>, at: usize },
266 /// compose(f, g): (f . g); both contract expressions
267 Compose(Box<ContractExpr>, Box<ContractExpr>),
268 /// apply e to an argument that checked against e's first parameter
269 ApplyFirst(Box<ContractExpr>),
272impl ContractExpr {
273 /// The type of the next parameter this function expects, if known.
274 pub fn next_param(&self) -> Option<Rc2<TypeExpr>> {
275 match self {
276 ContractExpr::Unknown => None,
277 ContractExpr::Known { contract, at } => contract.params.get(*at).cloned(),
278 // (f . g) x = f (g x) (§4.9): the argument is g's, even when
279 // g's contract is unknown or used up, and f's own contract
280 // checks what g returns when it is applied to it
281 ContractExpr::Compose(_, g) => g.next_param(),
282 ContractExpr::ApplyFirst(e) => {
283 let advanced = ContractExpr::apply_first(e.clone());
284 advanced.next_param()
285 }
287 }
288 }
290 /// The result type once all parameters are supplied.
291 pub fn result_after(&self) -> Option<Rc2<TypeExpr>> {
292 match self {
293 ContractExpr::Unknown => None,
294 ContractExpr::Known { contract, at } => {
295 if *at >= contract.params.len() {
296 Some(contract.result.clone())
297 } else {
298 None
299 }
300 }
301 ContractExpr::Compose(f, g) => {
302 if g.is_exhausted() {
303 f.result_after()
304 } else {
305 None
306 }
307 }
308 ContractExpr::ApplyFirst(_) => None,
309 }
310 }
312 /// True when no parameters remain (value-level).
313 pub fn is_exhausted(&self) -> bool {
314 match self {
315 ContractExpr::Unknown => false,
316 ContractExpr::Known { contract, at } => *at >= contract.params.len(),
317 ContractExpr::Compose(_, g) => g.is_exhausted(),
318 ContractExpr::ApplyFirst(_) => false,
319 }
320 }
322 /// Advance after one argument has been supplied and checked.
323 pub fn apply_first_rc(self: Rc2<ContractExpr>) -> ContractExpr {
324 // the common case advances without allocating anything
325 match &*self {
326 ContractExpr::Unknown => ContractExpr::Unknown,
327 ContractExpr::Known { contract, at } => ContractExpr::Known {
328 contract: contract.clone(),
329 at: contract.params.len().min(at + 1),
330 },
331 _ => ContractExpr::apply_first(Box::new((*self).clone())),
332 }
333 }
335 /// Advance after one argument has been supplied and checked.
336 pub fn apply_first(self: Box<ContractExpr>) -> ContractExpr {
337 match *self {
338 ContractExpr::Unknown => ContractExpr::Unknown,
339 ContractExpr::Known { contract, at } => {
340 let at = contract.params.len().min(at + 1);
341 ContractExpr::Known { contract, at }
342 }
343 ContractExpr::Compose(f, g) => {
344 if !g.is_exhausted() {
345 ContractExpr::Compose(f, Box::new(ContractExpr::apply_first(g)))
346 } else {
347 // x flowed into f
348 ContractExpr::ApplyFirst(f)
349 }
350 }
351 ContractExpr::ApplyFirst(e) => ContractExpr::ApplyFirst(Box::new(ContractExpr::apply_first(e))),
352 }
353 }
355 /// Number of remaining parameters, if known and not nested.
356 pub fn params_len(&self) -> usize {
357 match self {
358 ContractExpr::Known { contract, at } => contract.params.len() - at,
359 _ => 99,
360 }
361 }
363 /// The 0-based position of the next argument among those the signature
364 /// lists, when known. Messages number arguments by the signature (§4.13:
365 /// "describe expected Text as argument 1"), not by what the function
366 /// value already holds: `tree`, which is `treeWith` applied to its
367 /// options, takes its argument 1, and so does `squash`, a composition.
368 pub fn position(&self) -> Option<usize> {
369 match self {
370 ContractExpr::Known { at, .. } => Some(*at),
371 ContractExpr::Compose(_, g) => g.position(),
372 _ => None,
373 }
374 }
376 /// True when both are the same signature at the same position, so that
377 /// checking against one after the other repeats every check: the same
378 /// definition's contract, advanced as far. Only a known signature is
379 /// compared; any other is never the same.
380 pub fn same_as(&self, other: &ContractExpr) -> bool {
381 match (self, other) {
382 (
383 ContractExpr::Known { contract: a, at: i },
384 ContractExpr::Known { contract: b, at: j },
385 ) => Rc2::ptr_eq(a, b) && i == j,
386 _ => false,
387 }
388 }
390 /// Check an argument to this function. The outer ApplyFirst layer (if
391 /// any) accounts for the argument currently being consumed.
392 pub fn check_arg(&self, shapes: &Shapes, fname: &str, v: &Value) -> Result<(), Crash2> {
393 self.check_arg_at(shapes, fname, 0, v)
394 }
396 /// like check_arg, with the 0-based position of the argument for messages
397 pub fn check_arg_at(
398 &self,
399 shapes: &Shapes,
400 fname: &str,
401 position: usize,
402 v: &Value,
403 ) -> Result<(), Crash2> {
404 let peeled = match self {
405 ContractExpr::ApplyFirst(e) => ContractExpr::apply_first(e.clone()),
406 other => other.clone(),
407 };
408 if let Some(param) = peeled.next_param() {
409 if let Err(msg) = check(shapes, &param, v) {
410 // `check` reports "expected T, got V". Show the argument
411 // position with the declared type, then the got-kind; when the
412 // declared type is a type variable or alias whose inner
413 // description adds information (e.g. "[a]" vs "a list"), the
414 // inner "expected" is more helpful, so prefer it (§4.13).
415 let (exp, got) = match msg.split_once(", got ") {
416 Some((e, g)) => (
417 e.strip_prefix("expected ").unwrap_or(e).to_string(),
418 g.to_string(),
419 ),
420 None => (type_name(&param), v.kind_name().to_string()),
421 };
422 let declared = type_name(&param);
423 let shown = if declared == exp { declared } else { format!("{} ({})", declared, exp) };
424 return Err(Crash2::new(format!(
425 "contract: {} expected {} as argument {}, got {}",
426 fname,
427 shown,
428 position + 1,
429 got
430 )));
431 }
432 }
433 Ok(())
434 }
436 /// Check a result. Only called when this expression is exhausted.
437 pub fn check_result(&self, shapes: &Shapes, fname: &str, v: &Value) -> Result<(), Crash2> {
438 if !self.is_exhausted() {
439 // more parameters remain: the result must be a function; further
440 // checking happens when it is applied
441 if !matches!(v, Value::Fun(_)) {
442 return Err(Crash2::new(format!(
443 "contract: {} expected a function, got {}",
444 fname,
445 v.kind_name()
446 )));
447 }
448 return Ok(());
449 }
450 if let Some(res) = self.result_after() {
451 if let Err(msg) = check(shapes, &res, v) {
452 return Err(Crash2::new(format!(
453 "contract: {}: result {}",
454 fname, msg
455 )));
456 }
457 }
458 Ok(())
459 }
462pub type Crash2 = crate::value::Crash;