1use std::collections::BTreeMap;
2use std::sync::{Arc, RwLock};
3use std::{fs, vec};
4
5use conjure_cp_core::Model;
6use conjure_cp_core::ast::DeclarationPtr;
7use conjure_cp_core::ast::assertions::debug_assert_model_well_formed;
8use conjure_cp_core::context::Context;
9#[allow(unused)]
10use uniplate::Uniplate;
11
12use super::ParseContext;
13use super::dominance::parse_dominance_relation;
14use super::find::{parse_find_statement, parse_given_statement};
15use super::letting::parse_letting_statement;
16use super::objective::parse_objective_statement;
17use super::util::{TypecheckingContext, get_tree};
18use crate::diagnostics::source_map::SourceMap;
19use crate::errors::{FatalParseError, ParseErrorCollection, RecoverableParseError};
20use crate::expression::parse_expression;
21use crate::syntax_errors::detect_syntactic_errors;
22use tree_sitter::Tree;
23
24pub fn parse_essence_file_native(
26 path: &str,
27 context: Arc<RwLock<Context<'static>>>,
28) -> Result<Model, Box<ParseErrorCollection>> {
29 let source_code = fs::read_to_string(path).map_err(|source| {
30 Box::new(ParseErrorCollection::fatal(FatalParseError::FileRead {
31 path: path.to_string(),
32 source,
33 }))
34 })?;
35
36 let mut errors = vec![];
37 let model = parse_essence_with_context(&source_code, context, &mut errors);
38
39 match model {
40 Ok(Some(m)) => {
41 debug_assert_model_well_formed(&m, "tree-sitter");
42 Ok(m)
43 }
44 Ok(None) => {
45 Err(Box::new(ParseErrorCollection::multiple(
47 errors,
48 Some(source_code),
49 Some(path.to_string()),
50 )))
51 }
52 Err(fatal) => {
53 Err(Box::new(ParseErrorCollection::fatal(fatal)))
55 }
56 }
57}
58
59pub fn parse_essence_with_context(
60 src: &str,
61 context: Arc<RwLock<Context<'static>>>,
62 errors: &mut Vec<RecoverableParseError>,
63) -> Result<Option<Model>, FatalParseError> {
64 match parse_essence_with_context_and_map(src, context, errors, None)? {
65 (Some(model), _source_map) => Ok(Some(model)),
66 (None, _source_map) => Ok(None),
67 }
68}
69
70pub fn parse_essence_with_context_and_map(
78 src: &str,
79 context: Arc<RwLock<Context<'static>>>,
80 errors: &mut Vec<RecoverableParseError>,
81 tree: Option<&Tree>,
82) -> Result<(Option<Model>, SourceMap), FatalParseError> {
83 let (tree, source_code) = if let Some(tree) = tree {
84 (tree.clone(), src.to_string())
85 } else {
86 match get_tree(src) {
87 Some(tree) => tree,
88 None => {
89 return Err(FatalParseError::TreeSitterError(
90 "Failed to parse source code".to_string(),
91 ));
92 }
93 }
94 };
95
96 let has_syntax_errors = tree.root_node().has_error();
97 if has_syntax_errors {
98 detect_syntactic_errors(src, &tree, errors);
99 }
100
101 let mut suppressed_semantic_errors = Vec::new();
103 let semantic_errors: &mut Vec<RecoverableParseError> = if has_syntax_errors {
104 &mut suppressed_semantic_errors
105 } else {
106 errors
107 };
108
109 let mut model = Model::new(context);
110 let mut source_map = SourceMap::default();
111 let mut declaration_spans = BTreeMap::new();
112 let root_node = tree.root_node();
113
114 let mut ctx = ParseContext::new(
116 &source_code,
117 &root_node,
118 Some(model.symbols_ptr_unchecked().clone()),
119 semantic_errors,
120 &mut source_map,
121 &mut declaration_spans,
122 );
123
124 let mut cursor = root_node.walk();
125 for statement in root_node.children(&mut cursor) {
126 if !statement.is_named() || statement.is_error() || statement.kind() == "ERROR" {
127 continue;
128 }
129
130 ctx.typechecking_context = TypecheckingContext::Unknown;
131 ctx.inner_typechecking_context = TypecheckingContext::Unknown;
132
133 match statement.kind() {
134 "single_line_comment" => {}
135 "language_declaration" => {}
136 "find_statement" => {
137 let parsed = parse_find_statement(&mut ctx, statement)?;
138 for (name, domain) in parsed.declarations {
139 let decl = if parsed.auxiliary {
140 DeclarationPtr::new_find_auxiliary(name, domain)
141 } else {
142 DeclarationPtr::new_find(name, domain)
143 };
144 model.symbols_mut().insert(decl);
145 }
146 }
147 "given_statement" => {
148 let var_hashmap = parse_given_statement(&mut ctx, statement)?;
149 for (name, domain) in var_hashmap {
150 model
151 .symbols_mut()
152 .insert(DeclarationPtr::new_given(name, domain));
153 }
154 }
155 "bool_expr" | "atom" | "comparison_expr" | "arithmetic_expr" => {
159 ctx.typechecking_context = TypecheckingContext::Boolean;
160 let Some(expr) = parse_expression(&mut ctx, statement)? else {
161 continue;
162 };
163 model.add_constraint(expr);
164 }
165 "where_statement" => {
166 ctx.typechecking_context = TypecheckingContext::Boolean;
167 let mut cursor = statement.walk();
168 for condition in statement.named_children(&mut cursor) {
169 let Some(expr) = parse_expression(&mut ctx, condition)? else {
170 continue;
171 };
172 model.add_instantiation_condition(expr);
173 }
174 }
175 "language_label" => {}
176 "letting_statement" => {
177 let Some(letting_vars) = parse_letting_statement(&mut ctx, statement)? else {
178 continue;
179 };
180 model.symbols_mut().extend(letting_vars);
181 }
182 "dominance_relation" => {
183 let Some(dominance) = parse_dominance_relation(&mut ctx, &statement)? else {
184 continue;
185 };
186 if model.dominance.is_some() {
187 ctx.record_error(RecoverableParseError::new(
188 "Duplicate dominance relation".to_string(),
189 None,
190 ));
191 continue;
192 }
193 model.dominance = Some(dominance);
194 }
195 "objective_statement" => {
196 let Some(objective) = parse_objective_statement(&mut ctx, &statement)? else {
197 continue;
198 };
199 if model.objective.is_some() {
200 ctx.record_error(RecoverableParseError::new(
201 "Duplicate objective statement".to_string(),
202 None,
203 ));
204 continue;
205 }
206 model.objective = Some(objective);
207 }
208 _ => {
209 ctx.record_error(RecoverableParseError::new(
210 format!("Unexpected top-level statement: {}", statement.kind()),
211 Some(statement.range()),
212 ));
213 continue;
214 }
215 }
216 }
217
218 if !errors.is_empty() {
220 return Ok((None, source_map));
221 }
222 Ok((Some(model), source_map))
224}
225
226pub fn parse_essence(src: &str) -> Result<(Model, SourceMap), Box<ParseErrorCollection>> {
227 let context = Arc::new(RwLock::new(Context::default()));
228 let mut errors = vec![];
229 match parse_essence_with_context_and_map(src, context, &mut errors, None) {
230 Ok((Some(model), source_map)) => {
231 debug_assert_model_well_formed(&model, "tree-sitter");
232 Ok((model, source_map))
233 }
234 Ok((None, _source_map)) => {
235 Err(Box::new(ParseErrorCollection::multiple(
237 errors,
238 Some(src.to_string()),
239 None,
240 )))
241 }
242 Err(fatal) => Err(Box::new(ParseErrorCollection::fatal(fatal))),
243 }
244}
245
246mod test {
247 #[allow(unused_imports)]
248 use crate::parse_essence;
249 #[allow(unused_imports)]
250 use conjure_cp_core::ast::{
251 Atom, DeclarationKind, Expression, Metadata, Moo, Name, ReturnType, Typeable,
252 };
253 #[allow(unused_imports)]
254 use conjure_cp_core::{domain_int, matrix_expr, range};
255 #[allow(unused_imports)]
256 use std::ops::Deref;
257
258 #[test]
259 pub fn test_parse_xyz() {
260 let src = "
261 find x, y, z : int(1..4)
262 such that x + y + z = 4
263 such that x >= y
264 ";
265
266 let (model, _source_map) = parse_essence(src).unwrap();
267
268 let st = model.symbols();
269 let x = st.lookup(&Name::user("x")).unwrap();
270 let y = st.lookup(&Name::user("y")).unwrap();
271 let z = st.lookup(&Name::user("z")).unwrap();
272 assert_eq!(x.domain(), Some(domain_int!(1..4)));
273 assert_eq!(y.domain(), Some(domain_int!(1..4)));
274 assert_eq!(z.domain(), Some(domain_int!(1..4)));
275
276 let constraints = model.constraints();
277 assert_eq!(constraints.len(), 2);
278
279 let c1 = constraints[0].clone();
280 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x));
281 let y_e = Expression::Atomic(Metadata::new(), Atom::new_ref(y));
282 let z_e = Expression::Atomic(Metadata::new(), Atom::new_ref(z));
283 assert_eq!(
284 c1,
285 Expression::Eq(
286 Metadata::new(),
287 Moo::new(Expression::Sum(
288 Metadata::new(),
289 Moo::new(matrix_expr!(
290 Expression::Sum(
291 Metadata::new(),
292 Moo::new(matrix_expr!(x_e.clone(), y_e.clone()))
293 ),
294 z_e
295 ))
296 )),
297 Moo::new(Expression::Atomic(Metadata::new(), 4.into()))
298 )
299 );
300
301 let c2 = constraints[1].clone();
302 assert_eq!(
303 c2,
304 Expression::Geq(Metadata::new(), Moo::new(x_e), Moo::new(y_e))
305 );
306 }
307
308 #[test]
309 pub fn test_parse_bare_int_domain_is_unbounded() {
310 let src = "given a : int";
311 let (model, _source_map) = parse_essence(src).unwrap();
312
313 let st = model.symbols();
314 let a = st.lookup(&Name::user("a")).unwrap();
315 assert_eq!(
316 a.domain(),
317 Some(conjure_cp_core::ast::Domain::int_ground(vec![
318 conjure_cp_core::ast::Range::Unbounded
319 ]))
320 );
321 }
322
323 #[test]
324 pub fn test_parse_empty_int_domain() {
325 let src = "find x : int()";
326 let (model, _source_map) = parse_essence(src).unwrap();
327
328 let st = model.symbols();
329 let x = st.lookup(&Name::user("x")).unwrap();
330 assert_eq!(x.domain(), Some(domain_int!()));
331 }
332
333 #[test]
334 pub fn test_pretty_int_domain_reference_bound_without_extra_parentheses() {
335 let src = "
336 given n : int
337 find x : int(1..n)
338 ";
339
340 let (model, _source_map) = parse_essence(src).unwrap();
341
342 assert!(model.to_string().contains("find x: int(1..n)\n"));
343 }
344
345 #[test]
346 pub fn test_parse_letting_index() {
347 let src = "
348 letting a be [ [ 1,2,3 ; int(1,2,4) ], [ 1,3,2 ; int(1,2,4) ], [ 3,2,1 ; int(1,2,4) ] ; int(-2..0) ]
349 find b: int(1..5)
350 such that
351 b < a[-2,2],
352 allDiff(a[-2,..])
353 ";
354
355 let (model, _source_map) = parse_essence(src).unwrap();
356 let st = model.symbols();
357 let a_decl = st.lookup(&Name::user("a")).unwrap();
358 let a = a_decl.as_value_letting().unwrap().deref().clone();
359 assert_eq!(
360 a,
361 matrix_expr!(
362 matrix_expr!(1.into(), 2.into(), 3.into() ; domain_int!(1, 2, 4)),
363 matrix_expr!(1.into(), 3.into(), 2.into() ; domain_int!(1, 2, 4)),
364 matrix_expr!(3.into(), 2.into(), 1.into() ; domain_int!(1, 2, 4));
365 domain_int!(-2..0)
366 )
367 )
368 }
369
370 #[test]
371 pub fn test_parse_chained_and_multi_index() {
372 let src = "
373 find x : (bool, (bool, int(1..4)))
374 such that
375 x[2][1] = true,
376 x[2,1] = true
377 ";
378
379 let (model, _source_map) = parse_essence(src).unwrap();
380 let constraints = model.constraints();
381 assert_eq!(constraints.len(), 2);
382 for constraint in constraints {
383 let Expression::Eq(_, lhs, _) = constraint else {
384 panic!("expected an equality constraint");
385 };
386 assert_eq!(lhs.return_type(), ReturnType::Bool);
387 }
388 }
389
390 #[test]
391 pub fn test_multi_dimensional_matrix_index_return_type() {
392 let src = "
393 find a : matrix indexed by [int(1..2), int(1..2)] of int(1..4)
394 such that a[1,1] = 1
395 ";
396
397 let (model, _source_map) = parse_essence(src).unwrap();
398 let constraints = model.constraints();
399 let Expression::Eq(_, lhs, _) = &constraints[0] else {
400 panic!("expected an equality constraint");
401 };
402 assert_eq!(lhs.return_type(), ReturnType::Int);
403 }
404
405 #[test]
406 pub fn value_letting_retains_symbolic_integer_domain() {
407 let src = "
408 given v: int(1..)
409 given b: int(1..)
410 given r: int(1..)
411 letting rv be r * v
412 letting ceilrv be rv / b + toInt(rv % b != 0)
413 ";
414
415 let (model, _source_map) = parse_essence(src).unwrap();
416 let symbols = model.symbols();
417
418 for name in ["rv", "ceilrv"] {
419 let declaration = symbols.lookup(&Name::user(name)).unwrap();
420 assert!(
421 declaration.domain().is_some(),
422 "{name} should have a domain"
423 );
424 assert!(matches!(
425 declaration.kind().deref(),
426 DeclarationKind::ValueLetting(_, Some(_))
427 ));
428 }
429 drop(symbols);
430
431 let (params, _source_map) = parse_essence(
432 "
433 letting v be 8
434 letting b be 28
435 letting r be 14
436 ",
437 )
438 .unwrap();
439 let model = conjure_cp_core::instantiate::instantiate_model(model, params).unwrap();
440 let symbols = model.symbols();
441 let rv = symbols.lookup(&Name::user("rv")).unwrap();
442 assert_eq!(
443 rv.domain().unwrap().resolve().unwrap().as_ref(),
444 domain_int!(112).resolve().unwrap().as_ref()
445 );
446 }
447
448 #[test]
449 pub fn test_parse_table_in_quantifier() {
450 let src = "
451 find x, y, z : int(1..3)
452 such that forAll i : int(1..1) . table([x,y,z], [[1,2,3]])
453 ";
454
455 let (model, _source_map) = parse_essence(src).unwrap();
456 let constraints = model.constraints();
457 assert_eq!(constraints.len(), 1);
458
459 let Expression::And(_, comprehension_expr) = &constraints[0] else {
460 panic!("expected forAll to parse as an And over a comprehension");
461 };
462 let Expression::Comprehension(_, comprehension) = comprehension_expr.as_ref() else {
463 panic!("expected forAll body to be a comprehension");
464 };
465
466 assert!(matches!(
467 comprehension.return_expression,
468 Expression::Table(_, _, _)
469 ));
470 }
471
472 #[test]
473 pub fn test_parse_objective_statement() {
474 let src = "
475 find cost : int(0..10)
476 minimising cost
477 such that cost = 5
478 ";
479
480 let (model, _source_map) = parse_essence(src).unwrap();
481 assert!(matches!(
482 model.objective.as_ref().unwrap().direction,
483 conjure_cp_core::ast::OptimiseDirection::Minimising
484 ));
485
486 let st = model.symbols();
487 let objective = model.objective.as_ref().unwrap();
488 let cost = st.lookup(&Name::user("cost")).unwrap();
489 assert_eq!(
490 objective.expression,
491 Expression::Atomic(Metadata::new(), Atom::new_ref(cost))
492 );
493 }
494
495 #[test]
496 pub fn test_parse_pareto_in_dominance_relation() {
497 let src = "
498 find x : int(0..3)
499
500 dominance relation
501 pareto(minimising x)
502 ";
503
504 let (model, _source_map) = parse_essence(src).unwrap();
505 let st = model.symbols();
506 let x = st.lookup(&Name::user("x")).unwrap();
507 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x.clone()));
508 let x_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(x)));
509
510 assert_eq!(
511 model.dominance,
512 Some(Expression::DominanceRelation(
513 Metadata::new(),
514 Moo::new(Expression::And(
515 Metadata::new(),
516 Moo::new(matrix_expr!(
517 Expression::Leq(
518 Metadata::new(),
519 Moo::new(x_e.clone()),
520 Moo::new(x_prev.clone())
521 ),
522 Expression::Lt(Metadata::new(), Moo::new(x_e), Moo::new(x_prev))
523 ))
524 ))
525 ))
526 );
527 }
528
529 #[test]
530 pub fn test_parse_pareto_with_mixed_directions() {
531 let src = "
532 find x : int(0..3)
533 find y : int(0..3)
534
535 dominance relation
536 pareto(minimising x, maximising y)
537 ";
538
539 let (model, _source_map) = parse_essence(src).unwrap();
540 let st = model.symbols();
541 let x = st.lookup(&Name::user("x")).unwrap();
542 let y = st.lookup(&Name::user("y")).unwrap();
543 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x.clone()));
544 let y_e = Expression::Atomic(Metadata::new(), Atom::new_ref(y.clone()));
545 let x_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(x)));
546 let y_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(y)));
547
548 assert_eq!(
549 model.dominance,
550 Some(Expression::DominanceRelation(
551 Metadata::new(),
552 Moo::new(Expression::And(
553 Metadata::new(),
554 Moo::new(matrix_expr!(
555 Expression::Leq(
556 Metadata::new(),
557 Moo::new(x_e.clone()),
558 Moo::new(x_prev.clone())
559 ),
560 Expression::Geq(
561 Metadata::new(),
562 Moo::new(y_e.clone()),
563 Moo::new(y_prev.clone())
564 ),
565 Expression::Or(
566 Metadata::new(),
567 Moo::new(matrix_expr!(
568 Expression::Lt(Metadata::new(), Moo::new(x_e), Moo::new(x_prev)),
569 Expression::Gt(Metadata::new(), Moo::new(y_e), Moo::new(y_prev))
570 ))
571 )
572 ))
573 ))
574 ))
575 );
576 }
577
578 #[test]
579 pub fn test_parse_pareto_over_expression_component() {
580 let src = "
581 find x : int(0..3)
582
583 dominance relation
584 pareto(minimising x + 1)
585 ";
586
587 let (model, _source_map) = parse_essence(src).unwrap();
588 let st = model.symbols();
589 let x = st.lookup(&Name::user("x")).unwrap();
590 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x.clone()));
591 let x_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(x)));
592 let one = Expression::Atomic(Metadata::new(), 1.into());
593 let current = Expression::Sum(
594 Metadata::new(),
595 Moo::new(matrix_expr!(x_e.clone(), one.clone())),
596 );
597 let previous = Expression::Sum(Metadata::new(), Moo::new(matrix_expr!(x_prev, one)));
598
599 assert_eq!(
600 model.dominance,
601 Some(Expression::DominanceRelation(
602 Metadata::new(),
603 Moo::new(Expression::And(
604 Metadata::new(),
605 Moo::new(matrix_expr!(
606 Expression::Leq(
607 Metadata::new(),
608 Moo::new(current.clone()),
609 Moo::new(previous.clone())
610 ),
611 Expression::Lt(Metadata::new(), Moo::new(current), Moo::new(previous))
612 ))
613 ))
614 ))
615 );
616 }
617
618 #[test]
619 pub fn test_parse_permutation_domain_literal_and_operators() {
620 let src = "
621 find p : permutation (numMoved 3) of int(1..5)
622 letting q be permutation((1,2,3),(4,5))
623 find x, y : int(1..5)
624 such that y = image(p, x)
625 such that inverse(p, q)
626 such that q = permInverse(p)
627 such that y = image(compose(p, q), x)
628 ";
629
630 let (model, _source_map) = parse_essence(src).unwrap();
631
632 let st = model.symbols();
633 let p = st.lookup(&Name::user("p")).unwrap();
634 let ground = p.domain().unwrap().resolve().unwrap();
635 let conjure_cp_core::ast::GroundDomain::Permutation(attrs, inner) = ground.as_ref() else {
636 panic!("expected a permutation domain, got {ground}");
637 };
638 assert_eq!(attrs.num_moved, range!(3));
639 assert_eq!(**inner, *domain_int!(1..5).resolve().unwrap());
640
641 let constraints = model.constraints();
642 assert_eq!(constraints.len(), 4);
643 assert!(matches!(constraints[0], Expression::Eq(_, _, _)));
644 assert!(matches!(constraints[1], Expression::Inverse(_, _, _)));
645 assert!(matches!(constraints[2], Expression::Eq(_, _, _)));
646 let Expression::Eq(_, _, rhs) = &constraints[2] else {
647 unreachable!()
648 };
649 assert!(matches!(rhs.as_ref(), Expression::PermInverse(_, _)));
650 assert!(matches!(constraints[3], Expression::Eq(_, _, _)));
651 let Expression::Eq(_, _, rhs) = &constraints[3] else {
652 unreachable!()
653 };
654 let Expression::Image(_, compose_expr, _) = rhs.as_ref() else {
655 unreachable!()
656 };
657 assert!(matches!(
658 compose_expr.as_ref(),
659 Expression::Compose(_, _, _)
660 ));
661 }
662
663 #[test]
664 pub fn test_parse_permutation_unattributed_domain_and_empty_literal() {
665 let src = "
671 find p : permutation of int(1..3)
672 letting q be permutation()
673 find x : int(1..3)
674 such that x = image(p, 1)
675 ";
676
677 let (model, _source_map) = parse_essence(src).unwrap();
678
679 let st = model.symbols();
680 let p = st.lookup(&Name::user("p")).unwrap();
681 let ground = p.domain().unwrap().resolve().unwrap();
682 let conjure_cp_core::ast::GroundDomain::Permutation(attrs, _) = ground.as_ref() else {
683 panic!("expected a permutation domain, got {ground}");
684 };
685 assert_eq!(attrs.num_moved, conjure_cp_core::ast::Range::Unbounded);
686
687 let q_decl = st.lookup(&Name::user("q")).unwrap();
688 let q = q_decl.as_value_letting().unwrap().deref().clone();
689 assert_eq!(
690 q,
691 Expression::AbstractLiteral(
692 Metadata::new(),
693 conjure_cp_core::ast::AbstractLiteral::Permutation(vec![])
694 )
695 );
696 }
697}