Repository: kdr-aus/ogma (rust)

Issue:
[BUG] Infinite compilation loop
## Current Behaviour
This snippet causes compilation to not terminate (or at least take a **very** long time)
```
# Returns a table with the following headers:
# `P20,P50,P80,σ`
def sim-characteristics Table () {
    let {len} $len
    | let { fold 0 + { \ $row | get $col} | / $len } $mean
    | Table 'mean'
    | append-row $mean
}

# Construct the Saleable by year table.
open input-constrained.csv | grp-by {get:Str Period | take 4} | map value { grp Run 
    | map value fold 0 + $row.SaleableTonnesMprd | ren value Saleable }
| map value sim-characteristics
| save saleable-table.csv
```

Notice that `$col` in `sim-characteristics` is not defined. When it _is_ defined it compiles fine (or at least it errors where it should).

## Expected Behaviour
A compilation error should occur stating that `$col` does not exist.

## Reproduction Steps
1. 

### Additional information


Pull request:
Add more robustness checks for variables that do not exist
Fixes #137 

This was due to a cycle in the locals graph needing updating.
This PR fixes this by altering the way LG nodes are sealed.
It also addresses some robustness bugs with the inferencer that this change introduced.

Patch:
diff --git a/RELEASE.md b/RELEASE.md
index e169bfc..d2fa137 100644
--- a/RELEASE.md
+++ b/RELEASE.md
@@ -9,6 +9,7 @@
 - Detect trailing command in `let` and suggest a pipe (https://github.com/kdr-aus/ogma/pull/113)
 - Fix error where stronger type guarantees were present (https://github.com/kdr-aus/ogma/pull/117)
 - Fix def not inferring correct input in `last` (https://github.com/kdr-aus/ogma/pull/147)
+- Fix _locals graph needs updating_ bug (https://github.com/kdr-aus/ogma/pull/148)
 
 **✨ Other Updates**
 - `ogma` crate API documentation is now published at https://kdr-aus.github.io/ogma/ogma/ (https://github.com/kdr-aus/ogma/commit/cf5cc7979c399b609e2e0605ffe176e70e474ac2)
diff --git a/ogma/src/eng/arg.rs b/ogma/src/eng/arg.rs
index 4de9987..f0a289c 100644
--- a/ogma/src/eng/arg.rs
+++ b/ogma/src/eng/arg.rs
@@ -203,6 +203,7 @@ impl<'a> ArgBuilder<'a> {
             Flag(_) => unreachable!("an argument cannot be a Flag variant"),
             Intrinsic { .. } => unreachable!("an argument cannot be a Intrinsic variant"),
             Def { .. } => unreachable!("an argument cannot be a Def variant"),
+
             Ident(s) => Ok(Hold::Lit(Str::new(s.str()).into())),
             Num { val, tag: _ } => Ok(Hold::Lit((*val).into())),
             Pound {
@@ -220,7 +221,7 @@ impl<'a> ArgBuilder<'a> {
             Pound {
                 ty: Pt::Newline,
                 tag: _,
-            } => Ok(Hold::Lit(Value::Str(Str::from("\n")))),
+            } => Ok(Hold::Lit(Value::Str(Str::from('\n')))),
             Pound {
                 ty: Pt::Input,
                 tag: _,
diff --git a/ogma/src/eng/comp/infer.rs b/ogma/src/eng/comp/infer.rs
index 4dcc462..1640475 100644
--- a/ogma/src/eng/comp/infer.rs
+++ b/ogma/src/eng/comp/infer.rs
@@ -19,7 +19,7 @@ impl<'d> Compiler<'d> {
     }
 
     fn infer_inputs_tgt_ops(&mut self) -> Result<bool> {
-        // we get _lowest_ nodes that are:
+        // we get _deepest_ nodes that are:
         // 1. Op variants,
         // 2. are not compiled,
         // 3. have multiple inputs
@@ -144,7 +144,7 @@ enum Error {
 /// Tries to compile the `op` with each type in the inferred types set.
 /// Pushes `RemoveInput` if failed.
 fn trial_inferred_types(op: OpNode, compiler: &Compiler, chgs: Chgs) {
-    let _sink1 = &mut Default::default();
+    let sink1 = &mut Default::default();
 
     let set = compiler.tg[op.idx()]
         .input
@@ -157,14 +157,17 @@ fn trial_inferred_types(op: OpNode, compiler: &Compiler, chgs: Chgs) {
         .filter(|ty| {
             let infer_output = &mut false;
             let compiled = compiler
-                .compile_block(op, ty.clone(), _sink1, infer_output)
+                .compile_block(op, ty.clone(), sink1, infer_output)
                 .is_ok();
+
+            let lg_chg_req = sink1.drain(..).any(|chg| chg.is_lg_chg());
+
             // remove input if failed compilation, and
             // does not infer output
             // we keep in if infer_output is true, since we need more information about types
             // before we can compile this block, and removing input inferences will just reduce it
             // to an empty set.
-            !compiled && !*infer_output
+            !compiled && !*infer_output && !lg_chg_req
         })
         .map(|ty| RemoveInput(op.into(), ty))
         .map(Into::into);
diff --git a/ogma/src/eng/graphs/astgraph.rs b/ogma/src/eng/graphs/astgraph.rs
index 62626ad..871f208 100644
--- a/ogma/src/eng/graphs/astgraph.rs
+++ b/ogma/src/eng/graphs/astgraph.rs
@@ -467,40 +467,41 @@ impl AstGraph {
     /// the nodes which do not flow to another `Op` variant.
     ///
     /// This way, the sinks of a AST node variant can be found.
-    pub fn sinks<F>(&self, filter: F) -> HashSet<NodeIndex>
+    pub fn sinks<F>(&self, filter: F) -> Vec<NodeIndex>
     where
         F: Fn(NodeIndex) -> bool,
     {
-        fn find_last_match<'a, F>(
-            g: &'a AstGraph,
-            sink: NodeIndex,
-            filter: F,
-        ) -> impl Iterator<Item = NodeIndex> + 'a
-        where
-            F: 'a + Fn(NodeIndex) -> bool + Copy,
-        {
-            let srcs = g.externals(Incoming);
-
-            srcs.flat_map(move |src| {
-                petgraph::algo::all_simple_paths::<Vec<_>, _>(&g.0, src, sink, 0, None)
-                    .filter_map(move |v| v.into_iter().rev().find(|&n| filter(n)))
-            })
-        }
-
-        let sinks = self.externals(Outgoing);
+        let space = &mut Default::default();
+        let mut has_path =
+            |from, to| petgraph::algo::has_path_connecting(&self.0, from, to, Some(space));
 
-        let mut set = HashSet::default();
-
-        for sink in sinks {
-            if filter(sink) {
-                // a sink matched the predicate, no need to walk path
-                set.insert(sink);
-            } else {
-                set.extend(find_last_match(self, sink, &filter));
+        let mut ns = self
+            .node_indices()
+            .filter(|&n| filter(n))
+            .collect::<Vec<_>>();
+        ns.sort_unstable();
+        ns.reverse();
+
+        let mut i = 1;
+        while i < ns.len() {
+            let to = ns[i - 1];
+
+            let mut j = i;
+            while j < ns.len() {
+                let from = ns[j];
+                // observe that indices increase as graph goes deeper
+
+                if has_path(from, to) {
+                    ns.remove(j);
+                } else {
+                    j += 1;
+                }
             }
+
+            i += 1;
         }
 
-        set
+        ns
     }
 
     /// Matches a specific implementation of a command (op) with the given input type.
diff --git a/ogma/src/eng/graphs/locals_graph.rs b/ogma/src/eng/graphs/locals_graph.rs
index f974414..7fc2fee 100644
--- a/ogma/src/eng/graphs/locals_graph.rs
+++ b/ogma/src/eng/graphs/locals_graph.rs
@@ -320,27 +320,38 @@ impl LocalsGraph {
     /// Seal an op or expr node, flagging that there will not be any more variables introduced.
     /// An op's successful compilation would seal it.
     pub fn seal_node(&mut self, node: NodeIndex, ag: &AstGraph) {
-        self.graph[node].sealed = true; // seal itself
-        let mut wlkr = self.graph.neighbors(node).detach();
-        while let Some(n) = wlkr.next_node(&self.graph) {
+        if ag[node].expr().is_some() {
+            // if sealing an expression seal itself
+            // NOTE we do NOT seal op's as themselves
+            self.graph[node].sealed = true;
+        }
+
+        let mut stack = self.graph.neighbors(node).collect::<Vec<_>>();
+
+        while let Some(n) = stack.pop() {
+            // if already sealed, it would have already gone through this process, so do not keep
+            // walking down.
+            if self.graph[n].sealed {
+                continue;
+            }
+
             self.graph[n].sealed = true; // seal flow targets
 
             // if flow target is an expression, seal the expr's first op as well
             if let Some(e) = ag[n].expr().map(|_| ExprNode(n)) {
-                self.graph[e.first_op(ag).idx()].sealed = true;
+                stack.push(e.first_op(ag).idx());
             }
 
             // if the flow target is an Op (ie next block), seal the **argument** nodes
             // NOTE: this is done since an Op should not have variable definition power that would
             // influence the op's arguments...
             if ag[n].op().is_some() {
-                let mut wlkr = self.graph.neighbors(n).detach();
-                while let Some(n) = wlkr
-                    .next_node(&self.graph)
-                    .filter(|&n| ag[n].op().is_none())
-                {
-                    self.graph[n].sealed = true;
-                }
+                stack.extend(
+                    self.graph
+                        .neighbors(n)
+                        // do not filter the next op though
+                        .filter(|&n| ag[n].op().is_none()),
+                );
             }
         }
     }
diff --git a/ogma/src/eng/graphs/mod.rs b/ogma/src/eng/graphs/mod.rs
index 205c61d..d4a8277 100644
--- a/ogma/src/eng/graphs/mod.rs
+++ b/ogma/src/eng/graphs/mod.rs
@@ -67,6 +67,12 @@ impl From<locals_graph::Chg> for Chg {
     }
 }
 
+impl Chg {
+    pub fn is_lg_chg(&self) -> bool {
+        matches!(self, Chg::Lg(_))
+    }
+}
+
 #[cfg(debug_assertions)]
 fn debug_write_flowchart<N, E, W, F0, F1, F2>(
     g: &petgraph::stable_graph::StableGraph<N, E>,
@@ -779,8 +785,6 @@ mod tests {
     fn variable_detection() {
         let (ag, _tg) = init_graphs("\\ 3 | let $a | + { - 4 } | - $a { > 3 }");
 
-        dbg!(&ag);
-
         assert!(!ag.detect_var(OpNode(1.into()))); // \ 3
         assert!(ag.detect_var(OpNode(3.into()))); // let
         assert!(!ag.detect_var(OpNode(5.into()))); // +
@@ -792,4 +796,25 @@ mod tests {
         assert!(!ag.detect_var(OpNode(27.into()))); // Ord::Gt
         assert!(ag.detect_var(OpNode(36.into()))); // eq $rhs
     }
+
+    #[test]
+    fn sinks_test() {
+        let (ag, _tg) = init_graphs("\\ 3 | + { - 4 | + 3 }");
+
+        let s = |sl: &[_]| {
+            let mut x = sl.iter().copied().map(Into::into).collect::<Vec<_>>();
+            x.sort_unstable();
+            x.reverse();
+            x
+        };
+
+        let set = ag.sinks(|_| true);
+        assert_eq!(set, s(&[9, 10, 11, 12, 13, 14, 15, 16]));
+
+        let set = ag.sinks(|n| ag[n].var().is_some());
+        assert_eq!(set, s(&[]));
+
+        let set = ag.sinks(|n| ag[n].op().is_some());
+        assert_eq!(set, s(&[7, 5, 1]));
+    }
 }


Test patch:
diff --git a/ogma/tests/commands/definitions.rs b/ogma/tests/commands/definitions.rs
index 5307690..bddd03c 100644
--- a/ogma/tests/commands/definitions.rs
+++ b/ogma/tests/commands/definitions.rs
@@ -422,3 +422,70 @@ fn not_defined_err_msg() {
 "
     );
 }
+
+#[test]
+fn variable_not_defined_in_def() {
+    let defs = &mut Definitions::new();
+
+    process_definition(
+        "def foo Table () { append { get $col } }",
+        Location::Shell,
+        None,
+        defs,
+    )
+    .unwrap();
+
+    let x = process_w_table("foo", defs).unwrap_err().to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        "Semantics Error: variable `col` does not exist
+--> shell:33
+ | def foo Table () { append { get $col } }
+ |                                  ^^^ `col` not in scope
+--> shell:0
+ | foo
+ | ^^^ invoked here
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"
+    );
+
+    // from bug 137
+    process_definition(
+        r#"def sim-characteristics Table () {
+    let {len} $len
+    | let { fold 0 + { \ $row | get $col} | / $len } $mean
+    | Table 'mean'
+    | append-row $mean
+}"#,
+        Location::Shell,
+        None,
+        defs,
+    )
+    .unwrap();
+
+    let x = process_w_nil(
+        "open input-constrained.csv | grp-by {get:Str Period | take 4} | map value { grp Run 
+    | map value fold 0 + $row.SaleableTonnesMprd | ren value Saleable }
+| map value sim-characteristics
+| save saleable-table.csv",
+        defs,
+    )
+    .unwrap_err()
+    .to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        r#"Semantics Error: variable `col` does not exist
+--> shell:37
+ |     | let { fold 0 + { \ $row | get $col} | / $len } $mean
+ |                                      ^^^ `col` not in scope
+--> shell:12
+ | | map value sim-characteristics
+ |             ^^^^^^^^^^^^^^^^^^^ invoked here
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"#
+    );
+}
diff --git a/ogma/tests/commands/mod.rs b/ogma/tests/commands/mod.rs
index ee2da09..79a471c 100644
--- a/ogma/tests/commands/mod.rs
+++ b/ogma/tests/commands/mod.rs
@@ -460,6 +460,110 @@ fn no_cmd_defined() {
     );
 }
 
+#[test]
+fn variables_not_existing() {
+    let defs = &Definitions::new();
+
+    let x = process_w_table("\\ $t", defs).unwrap_err().to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        r#"Semantics Error: variable `t` does not exist
+--> shell:3
+ | \ $t
+ |    ^ `t` not in scope
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"#
+    );
+
+    let x = process_w_table("let $a | \\ $t", defs)
+        .unwrap_err()
+        .to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        r#"Semantics Error: variable `t` does not exist
+--> shell:12
+ | let $a | \ $t
+ |             ^ `t` not in scope
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"#
+    );
+
+    let x = process_w_nil("let $a | \\ $a", defs);
+    assert_eq!(x, Ok(Value::Nil));
+
+    let x = process_w_table("append { get $col }", defs)
+        .unwrap_err()
+        .to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        "Semantics Error: variable `col` does not exist
+--> shell:14
+ | append { get $col }
+ |               ^^^ `col` not in scope
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"
+    );
+
+    let x = process_w_table("append { let $a | get $col }", defs)
+        .unwrap_err()
+        .to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        "Semantics Error: variable `col` does not exist
+--> shell:23
+ | append { let $a | get $col }
+ |                        ^^^ `col` not in scope
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"
+    );
+
+    let x = process_w_table("append { let 'first' $a | get:Num $a } | \\ 3", defs);
+    assert_eq!(x, Ok(Value::Num(3.into())));
+
+    let x = process_w_table("let { nth 0 get $col } $c | \\ $c", defs)
+        .unwrap_err()
+        .to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        r#"Semantics Error: variable `col` does not exist
+--> shell:17
+ | let { nth 0 get $col } $c | \ $c
+ |                  ^^^ `col` not in scope
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"#
+    );
+}
+
+#[test]
+fn variables_not_existing_with_fold_call() {
+    let defs = &Definitions::new();
+
+    let x = process_w_table("fold {Table} { get $col }", defs)
+        .unwrap_err()
+        .to_string();
+    println!("{x}");
+    assert_eq!(
+        &x,
+        r#"Semantics Error: variable `col` does not exist
+--> shell:20
+ | fold {Table} { get $col }
+ |                     ^^^ `col` not in scope
+--> help: variables must be in scope
+          variables can be defined using the `let` command
+"#
+    );
+}
+
 // ------ General Bugs ---------------------------------------------------------
 #[test]
 fn gt_should_resolve_as_bool_return_type() {
diff --git a/ogma/tests/commands/pipeline.rs b/ogma/tests/commands/pipeline.rs
index 94b9de4..ccc9c97 100644
--- a/ogma/tests/commands/pipeline.rs
+++ b/ogma/tests/commands/pipeline.rs
@@ -482,7 +482,6 @@ fn last_testing_bug_116() {
         r#"ls | grp name | fold 0 { \$row | get value | last get:Num size }"#,
         defs,
     );
-    dbg!(&x);
     assert!(matches!(x, Ok(Value::Num(_))));
 }