[VM] analysis-pass variable lookup fails due to a cost check if the variable is not defined

[jcnelson]

If you have a contract that uses an undefined variable at the highest context in a function body, the analysis pass fails due to the analysis cost function for variable lookup (which is O(n log n)) receiving n = 0, which is undefined for log2. Example:

$ cat /tmp/invalid-var-0.clar 
(begin
    (print y)
)
$ clarity-cli check /tmp/invalid-var-0.clar | jq
INFO [1619200632.082919] [src/vm/functions/mod.rs:445] [main] "``... to be a completely separate network and separate block chain, yet share CPU power with Bitcoin`` - Satoshi Nakamoto"
{
  "error": {
    "analysis": {
      "level": "Error",
      "message": "contract cost computation failed: Error evaluating result of cost function SP000000000000000000002Q6VF78.costs.cost_analysis_lookup_variable_depth: Arithmetic(\"log2 must be passed a positive integer\")\n Stack Trace: \nSP000000000000000000002Q6VF78.costs:cost_analysis_lookup_variable_depth\nSP000000000000000000002Q6VF78.costs:nlogn\n_native_:native_log2\n",
      "spans": [
        {
          "end_column": 12,
          "end_line": 2,
          "start_column": 12,
          "start_line": 2
        }
      ],
      "suggestion": null
    }
  },
  "message": "Checks failed."
}

I think this is a (benign) bug in the analysis checker. The analysis pass should have reported that x is undefined, but the logic that does this (in TypeChecker<'_, '_> in src/vm/analysis/type_checker/mod.rs) executes the cost check before the variable existence check, and passes in the context depth as n (which is, somehow, 0 in this case). The offending code is here:

fn lookup_variable(&mut self, name: &str, context: &TypingContext) -> TypeResult {
    runtime_cost(ClarityCostFunction::AnalysisLookupVariableConst, self, 0)?;

    if let Some(type_result) = type_reserved_variable(name) {
        Ok(type_result)
    } else if let Some(type_result) = self.contract_context.get_variable_type(name) {
        Ok(type_result.clone())
    } else if let Some(type_result) = context.lookup_trait_reference_type(name) {
        Ok(TypeSignature::TraitReferenceType(type_result.clone()))
    } else {
        /***************************************************/
        // context.depth is 0 here, so this method fails.
        /***************************************************/
        runtime_cost(
            ClarityCostFunction::AnalysisLookupVariableDepth,
            self,
            context.depth,   // should this really be 0?  Or, should we have a check here?
        )?;

        if let Some(type_result) = context.lookup_variable_type(name) {
            Ok(type_result.clone())
        } else {
            Err(CheckErrors::UndefinedVariable(name.to_string()).into())
        }
    }
}

The error behavior I'd expect can be seen here:

$ cat /tmp/invalid-var.clar 
(begin
    (let (
        (x 3)
    )
        (print y)
    )
)
$ clarity-cli check /tmp/invalid-var.clar | jq
INFO [1619200706.282661] [src/vm/functions/mod.rs:445] [main] "``... to be a completely separate network and separate block chain, yet share CPU power with Bitcoin`` - Satoshi Nakamoto"
{
  "error": {
    "analysis": {
      "level": "Error",
      "message": "use of unresolved variable 'y'",
      "spans": [
        {
          "end_column": 16,
          "end_line": 5,
          "start_column": 16,
          "start_line": 5
        }
      ],
      "suggestion": null
    }
  },
  "message": "Checks failed."
}

I don't believe this is consensus-critical, because the VM should fail analysis either way (which would mean that a smart contract transaction would fail in the analysis step). But, the error itself is wrong, and I wouldn't want to try and fix this unless we're absolutely sure it's not a consensus bug. Please advise.

[kantai]

Yep -- I believe you're correct that this is a benign bug. The analysis will fail in any event, but I think this should be tested via integration testing to ensure that's the case.