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, OXIDE_INT_MAX, OXIDE_INT_MIN,
252 ReturnType, Typeable,
253 };
254 #[allow(unused_imports)]
255 use conjure_cp_core::{domain_int, matrix_expr, range};
256 #[allow(unused_imports)]
257 use std::ops::Deref;
258
259 #[test]
260 pub fn test_parse_xyz() {
261 let src = "
262 find x, y, z : int(1..4)
263 such that x + y + z = 4
264 such that x >= y
265 ";
266
267 let (model, _source_map) = parse_essence(src).unwrap();
268
269 let st = model.symbols();
270 let x = st.lookup(&Name::user("x")).unwrap();
271 let y = st.lookup(&Name::user("y")).unwrap();
272 let z = st.lookup(&Name::user("z")).unwrap();
273 assert_eq!(x.domain(), Some(domain_int!(1..4)));
274 assert_eq!(y.domain(), Some(domain_int!(1..4)));
275 assert_eq!(z.domain(), Some(domain_int!(1..4)));
276
277 let constraints = model.constraints();
278 assert_eq!(constraints.len(), 2);
279
280 let c1 = constraints[0].clone();
281 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x));
282 let y_e = Expression::Atomic(Metadata::new(), Atom::new_ref(y));
283 let z_e = Expression::Atomic(Metadata::new(), Atom::new_ref(z));
284 assert_eq!(
285 c1,
286 Expression::Eq(
287 Metadata::new(),
288 Moo::new(Expression::Sum(
289 Metadata::new(),
290 Moo::new(matrix_expr!(
291 Expression::Sum(
292 Metadata::new(),
293 Moo::new(matrix_expr!(x_e.clone(), y_e.clone()))
294 ),
295 z_e
296 ))
297 )),
298 Moo::new(Expression::Atomic(Metadata::new(), 4.into()))
299 )
300 );
301
302 let c2 = constraints[1].clone();
303 assert_eq!(
304 c2,
305 Expression::Geq(Metadata::new(), Moo::new(x_e), Moo::new(y_e))
306 );
307 }
308
309 #[test]
310 pub fn test_parse_bare_int_domain_is_full() {
311 let src = "given a : int";
312 let (model, _source_map) = parse_essence(src).unwrap();
313
314 let st = model.symbols();
315 let a = st.lookup(&Name::user("a")).unwrap();
316 assert_eq!(a.domain(), Some(domain_int!(OXIDE_INT_MIN..OXIDE_INT_MAX)));
317 }
318
319 #[test]
320 pub fn test_parse_empty_int_domain() {
321 let src = "find x : int()";
322 let (model, _source_map) = parse_essence(src).unwrap();
323
324 let st = model.symbols();
325 let x = st.lookup(&Name::user("x")).unwrap();
326 assert_eq!(x.domain(), Some(domain_int!()));
327 }
328
329 #[test]
330 pub fn test_pretty_int_domain_reference_bound_without_extra_parentheses() {
331 let src = "
332 given n : int
333 find x : int(1..n)
334 ";
335
336 let (model, _source_map) = parse_essence(src).unwrap();
337
338 assert!(model.to_string().contains("find x: int(1..n)\n"));
339 }
340
341 #[test]
342 pub fn test_parse_letting_index() {
343 let src = "
344 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) ]
345 find b: int(1..5)
346 such that
347 b < a[-2,2],
348 allDiff(a[-2,..])
349 ";
350
351 let (model, _source_map) = parse_essence(src).unwrap();
352 let st = model.symbols();
353 let a_decl = st.lookup(&Name::user("a")).unwrap();
354 let a = a_decl.as_value_letting().unwrap().deref().clone();
355 assert_eq!(
356 a,
357 matrix_expr!(
358 matrix_expr!(1.into(), 2.into(), 3.into() ; domain_int!(1, 2, 4)),
359 matrix_expr!(1.into(), 3.into(), 2.into() ; domain_int!(1, 2, 4)),
360 matrix_expr!(3.into(), 2.into(), 1.into() ; domain_int!(1, 2, 4));
361 domain_int!(-2..0)
362 )
363 )
364 }
365
366 #[test]
367 pub fn test_parse_chained_and_multi_index() {
368 let src = "
369 find x : (bool, (bool, int(1..4)))
370 such that
371 x[2][1] = true,
372 x[2,1] = true
373 ";
374
375 let (model, _source_map) = parse_essence(src).unwrap();
376 let constraints = model.constraints();
377 assert_eq!(constraints.len(), 2);
378 for constraint in constraints {
379 let Expression::Eq(_, lhs, _) = constraint else {
380 panic!("expected an equality constraint");
381 };
382 assert_eq!(lhs.return_type(), ReturnType::Bool);
383 }
384 }
385
386 #[test]
387 pub fn test_multi_dimensional_matrix_index_return_type() {
388 let src = "
389 find a : matrix indexed by [int(1..2), int(1..2)] of int(1..4)
390 such that a[1,1] = 1
391 ";
392
393 let (model, _source_map) = parse_essence(src).unwrap();
394 let constraints = model.constraints();
395 let Expression::Eq(_, lhs, _) = &constraints[0] else {
396 panic!("expected an equality constraint");
397 };
398 assert_eq!(lhs.return_type(), ReturnType::Int);
399 }
400
401 #[test]
402 pub fn value_letting_retains_symbolic_integer_domain() {
403 let src = "
404 given v: int(1..)
405 given b: int(1..)
406 given r: int(1..)
407 letting rv be r * v
408 letting ceilrv be rv / b + toInt(rv % b != 0)
409 ";
410
411 let (model, _source_map) = parse_essence(src).unwrap();
412 let symbols = model.symbols();
413
414 for name in ["rv", "ceilrv"] {
415 let declaration = symbols.lookup(&Name::user(name)).unwrap();
416 assert!(
417 declaration.domain().is_some(),
418 "{name} should have a domain"
419 );
420 assert!(matches!(
421 declaration.kind().deref(),
422 DeclarationKind::ValueLetting(_, Some(_))
423 ));
424 }
425 drop(symbols);
426
427 let (params, _source_map) = parse_essence(
428 "
429 letting v be 8
430 letting b be 28
431 letting r be 14
432 ",
433 )
434 .unwrap();
435 let model = conjure_cp_core::instantiate::instantiate_model(model, params).unwrap();
436 let symbols = model.symbols();
437 let rv = symbols.lookup(&Name::user("rv")).unwrap();
438 assert_eq!(
439 rv.domain().unwrap().resolve().unwrap().as_ref(),
440 domain_int!(112).resolve().unwrap().as_ref()
441 );
442 }
443
444 #[test]
445 pub fn test_parse_table_in_quantifier() {
446 let src = "
447 find x, y, z : int(1..3)
448 such that forAll i : int(1..1) . table([x,y,z], [[1,2,3]])
449 ";
450
451 let (model, _source_map) = parse_essence(src).unwrap();
452 let constraints = model.constraints();
453 assert_eq!(constraints.len(), 1);
454
455 let Expression::And(_, comprehension_expr) = &constraints[0] else {
456 panic!("expected forAll to parse as an And over a comprehension");
457 };
458 let Expression::Comprehension(_, comprehension) = comprehension_expr.as_ref() else {
459 panic!("expected forAll body to be a comprehension");
460 };
461
462 assert!(matches!(
463 comprehension.return_expression,
464 Expression::Table(_, _, _)
465 ));
466 }
467
468 #[test]
469 pub fn test_parse_objective_statement() {
470 let src = "
471 find cost : int(0..10)
472 minimising cost
473 such that cost = 5
474 ";
475
476 let (model, _source_map) = parse_essence(src).unwrap();
477 assert!(matches!(
478 model.objective.as_ref().unwrap().direction,
479 conjure_cp_core::ast::OptimiseDirection::Minimising
480 ));
481
482 let st = model.symbols();
483 let objective = model.objective.as_ref().unwrap();
484 let cost = st.lookup(&Name::user("cost")).unwrap();
485 assert_eq!(
486 objective.expression,
487 Expression::Atomic(Metadata::new(), Atom::new_ref(cost))
488 );
489 }
490
491 #[test]
492 pub fn test_parse_pareto_in_dominance_relation() {
493 let src = "
494 find x : int(0..3)
495
496 dominance relation
497 pareto(minimising x)
498 ";
499
500 let (model, _source_map) = parse_essence(src).unwrap();
501 let st = model.symbols();
502 let x = st.lookup(&Name::user("x")).unwrap();
503 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x.clone()));
504 let x_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(x)));
505
506 assert_eq!(
507 model.dominance,
508 Some(Expression::DominanceRelation(
509 Metadata::new(),
510 Moo::new(Expression::And(
511 Metadata::new(),
512 Moo::new(matrix_expr!(
513 Expression::Leq(
514 Metadata::new(),
515 Moo::new(x_e.clone()),
516 Moo::new(x_prev.clone())
517 ),
518 Expression::Lt(Metadata::new(), Moo::new(x_e), Moo::new(x_prev))
519 ))
520 ))
521 ))
522 );
523 }
524
525 #[test]
526 pub fn test_parse_pareto_with_mixed_directions() {
527 let src = "
528 find x : int(0..3)
529 find y : int(0..3)
530
531 dominance relation
532 pareto(minimising x, maximising y)
533 ";
534
535 let (model, _source_map) = parse_essence(src).unwrap();
536 let st = model.symbols();
537 let x = st.lookup(&Name::user("x")).unwrap();
538 let y = st.lookup(&Name::user("y")).unwrap();
539 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x.clone()));
540 let y_e = Expression::Atomic(Metadata::new(), Atom::new_ref(y.clone()));
541 let x_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(x)));
542 let y_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(y)));
543
544 assert_eq!(
545 model.dominance,
546 Some(Expression::DominanceRelation(
547 Metadata::new(),
548 Moo::new(Expression::And(
549 Metadata::new(),
550 Moo::new(matrix_expr!(
551 Expression::Leq(
552 Metadata::new(),
553 Moo::new(x_e.clone()),
554 Moo::new(x_prev.clone())
555 ),
556 Expression::Geq(
557 Metadata::new(),
558 Moo::new(y_e.clone()),
559 Moo::new(y_prev.clone())
560 ),
561 Expression::Or(
562 Metadata::new(),
563 Moo::new(matrix_expr!(
564 Expression::Lt(Metadata::new(), Moo::new(x_e), Moo::new(x_prev)),
565 Expression::Gt(Metadata::new(), Moo::new(y_e), Moo::new(y_prev))
566 ))
567 )
568 ))
569 ))
570 ))
571 );
572 }
573
574 #[test]
575 pub fn test_parse_pareto_over_expression_component() {
576 let src = "
577 find x : int(0..3)
578
579 dominance relation
580 pareto(minimising x + 1)
581 ";
582
583 let (model, _source_map) = parse_essence(src).unwrap();
584 let st = model.symbols();
585 let x = st.lookup(&Name::user("x")).unwrap();
586 let x_e = Expression::Atomic(Metadata::new(), Atom::new_ref(x.clone()));
587 let x_prev = Expression::FromSolution(Metadata::new(), Moo::new(Atom::new_ref(x)));
588 let one = Expression::Atomic(Metadata::new(), 1.into());
589 let current = Expression::Sum(
590 Metadata::new(),
591 Moo::new(matrix_expr!(x_e.clone(), one.clone())),
592 );
593 let previous = Expression::Sum(Metadata::new(), Moo::new(matrix_expr!(x_prev, one)));
594
595 assert_eq!(
596 model.dominance,
597 Some(Expression::DominanceRelation(
598 Metadata::new(),
599 Moo::new(Expression::And(
600 Metadata::new(),
601 Moo::new(matrix_expr!(
602 Expression::Leq(
603 Metadata::new(),
604 Moo::new(current.clone()),
605 Moo::new(previous.clone())
606 ),
607 Expression::Lt(Metadata::new(), Moo::new(current), Moo::new(previous))
608 ))
609 ))
610 ))
611 );
612 }
613
614 #[test]
615 pub fn test_parse_permutation_domain_literal_and_operators() {
616 let src = "
617 find p : permutation (numMoved 3) of int(1..5)
618 letting q be permutation((1,2,3),(4,5))
619 find x, y : int(1..5)
620 such that y = image(p, x)
621 such that inverse(p, q)
622 such that q = permInverse(p)
623 such that y = image(compose(p, q), x)
624 ";
625
626 let (model, _source_map) = parse_essence(src).unwrap();
627
628 let st = model.symbols();
629 let p = st.lookup(&Name::user("p")).unwrap();
630 let ground = p.domain().unwrap().resolve().unwrap();
631 let conjure_cp_core::ast::GroundDomain::Permutation(attrs, inner) = ground.as_ref() else {
632 panic!("expected a permutation domain, got {ground}");
633 };
634 assert_eq!(attrs.num_moved, range!(3));
635 assert_eq!(**inner, *domain_int!(1..5).resolve().unwrap());
636
637 let constraints = model.constraints();
638 assert_eq!(constraints.len(), 4);
639 assert!(matches!(constraints[0], Expression::Eq(_, _, _)));
640 assert!(matches!(constraints[1], Expression::Inverse(_, _, _)));
641 assert!(matches!(constraints[2], Expression::Eq(_, _, _)));
642 let Expression::Eq(_, _, rhs) = &constraints[2] else {
643 unreachable!()
644 };
645 assert!(matches!(rhs.as_ref(), Expression::PermInverse(_, _)));
646 assert!(matches!(constraints[3], Expression::Eq(_, _, _)));
647 let Expression::Eq(_, _, rhs) = &constraints[3] else {
648 unreachable!()
649 };
650 let Expression::Image(_, compose_expr, _) = rhs.as_ref() else {
651 unreachable!()
652 };
653 assert!(matches!(
654 compose_expr.as_ref(),
655 Expression::Compose(_, _, _)
656 ));
657 }
658
659 #[test]
660 pub fn test_parse_permutation_unattributed_domain_and_empty_literal() {
661 let src = "
667 find p : permutation of int(1..3)
668 letting q be permutation()
669 find x : int(1..3)
670 such that x = image(p, 1)
671 ";
672
673 let (model, _source_map) = parse_essence(src).unwrap();
674
675 let st = model.symbols();
676 let p = st.lookup(&Name::user("p")).unwrap();
677 let ground = p.domain().unwrap().resolve().unwrap();
678 let conjure_cp_core::ast::GroundDomain::Permutation(attrs, _) = ground.as_ref() else {
679 panic!("expected a permutation domain, got {ground}");
680 };
681 assert_eq!(attrs.num_moved, conjure_cp_core::ast::Range::Unbounded);
682
683 let q_decl = st.lookup(&Name::user("q")).unwrap();
684 let q = q_decl.as_value_letting().unwrap().deref().clone();
685 assert_eq!(
686 q,
687 Expression::AbstractLiteral(
688 Metadata::new(),
689 conjure_cp_core::ast::AbstractLiteral::Permutation(vec![])
690 )
691 );
692 }
693}