`already borrowed: BorrowMutError`

[kurtlawrence]

I am getting a 'already borrowed' error when using @fold adjacent to other output fields.

This query would break:

{
    Spry(file: "dev.spry") {
        cases {
            name @output
            fullname @output
            equipment @fold {
                eqname: name @output
                eqname_full: fullname @output
            }
        }
    }
}

But without the adjacent fields, it returns as expected.

{
    Spry(file: "dev.spry") {
        cases {
            equipment @fold {
                eqname: name @output
                eqname_full: fullname @output
            }
        }
    }
}

Stack Trace

thread 'main' panicked at 'already borrowed: BorrowMutError', C:\Users\kurt\.cargo\registry\src\github.com-1ecc6299db9ec823\trustfall_core-0.2.0\src\interpreter\execution.rs:541:54
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483/library\std\src\panicking.rs:575
   1: core::panicking::panic_fmt
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483/library\core\src\panicking.rs:64
   2: core::result::unwrap_failed
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483/library\core\src\result.rs:1791
   3: enum2$<core::result::Result<core::cell::RefMut<qtest::adapters::BulkAdapter>,core::cell::BorrowMutError> >::expect<core::cell::RefMut<qtest::adapters::BulkAdapter>,core::cell::BorrowMutError>
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\result.rs:1070
   4: core::cell::RefCell<qtest::adapters::BulkAdapter>::borrow_mut<qtest::adapters::BulkAdapter>
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\cell.rs:958
   5: trustfall_core::interpreter::execution::compute_fold::closure$5<enum2$<qtest::adapters::Db>,qtest::adapters::BulkAdapter>
             at C:\Users\kurt\.cargo\registry\src\github.com-1ecc6299db9ec823\trustfall_core-0.2.0\src\interpreter\execution.rs:541
   6: core::ops::function::impls::impl$4::call_once<tuple$<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> > >,trustfall_core::interpreter::execution::compute_fold::closure_env$5<enum2$<qtest::adapters::Db>,qtest::adapters::BulkAdapter> >
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\ops\function.rs:629
   7: enum2$<core::option::Option<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> > > >::map<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,ref_m
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\option.rs:925
   8: core::iter::adapters::map::impl$2::next<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\iter\adapters\map.rs:103
   9: alloc::boxed::impl$39::next<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> > > > >,alloc::alloc::Global>
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\alloc\src\boxed.rs:1923
  10: core::iter::adapters::map::impl$2::next<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\iter\adapters\map.rs:103
  11: alloc::boxed::impl$39::next<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> > > > >,alloc::alloc::Global>
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\alloc\src\boxed.rs:1923
  12: core::iter::adapters::map::impl$2::next<tuple$<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,enum2$<trustfall_core::ir::value::FieldValue> >,alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core:
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\iter\adapters\map.rs:103
  13: alloc::vec::spec_from_iter_nested::impl$0::from_iter<tuple$<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,enum2$<trustfall_core::ir::value::FieldValue> >,core::iter::adapters::map::Map<alloc::boxed::Box<dyn$<core::iter::traits::it
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\alloc\src\vec\spec_from_iter_nested.rs:26
  14: alloc::vec::spec_from_iter::impl$0::from_iter<tuple$<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,enum2$<trustfall_core::ir::value::FieldValue> >,core::iter::adapters::map::Map<alloc::boxed::Box<dyn$<core::iter::traits::iterator:
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\alloc\src\vec\spec_from_iter.rs:33
  15: alloc::vec::impl$17::from_iter<tuple$<trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> >,enum2$<trustfall_core::ir::value::FieldValue> >,core::iter::adapters::map::Map<alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator<assoc
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\alloc\src\vec\mod.rs:2748
  16: core::iter::traits::iterator::Iterator::collect<core::iter::adapters::map::Map<alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> > > > >,alloc::alloc::Global>,qte
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\iter\traits\iterator.rs:1836
  17: qtest::adapters::impl$4::owned_box<core::iter::adapters::map::Map<alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator<assoc$<Item,trustfall_core::interpreter::DataContext<enum2$<qtest::adapters::Db> > > > >,alloc::alloc::Global>,qtest::adapters:
             at .\src\adapters\mod.rs:228
  18: qtest::adapters::resolve_property_with<enum2$<qtest::adapters::Db>,qtest::adapters::impl$3::resolve_property::closure_env$0>
             at .\src\adapters\mod.rs:199
  19: qtest::adapters::impl$3::resolve_property
             at .\src\adapters\mod.rs:129
  20: trustfall_core::interpreter::basic_adapter::impl$0::resolve_property<qtest::adapters::BulkAdapter>
             at C:\Users\kurt\.cargo\registry\src\github.com-1ecc6299db9ec823\trustfall_core-0.2.0\src\interpreter\basic_adapter.rs:239
  21: trustfall_core::interpreter::execution::construct_outputs<enum2$<qtest::adapters::Db>,qtest::adapters::BulkAdapter>
             at C:\Users\kurt\.cargo\registry\src\github.com-1ecc6299db9ec823\trustfall_core-0.2.0\src\interpreter\execution.rs:222
  22: trustfall_core::interpreter::execution::interpret_ir<enum2$<qtest::adapters::Db>,qtest::adapters::BulkAdapter>
             at C:\Users\kurt\.cargo\registry\src\github.com-1ecc6299db9ec823\trustfall_core-0.2.0\src\interpreter\execution.rs:60
  23: trustfall::execute_query<qtest::adapters::BulkAdapter,alloc::string::String,enum2$<trustfall_core::ir::value::FieldValue> >
             at C:\Users\kurt\.cargo\registry\src\github.com-1ecc6299db9ec823\trustfall-0.2.1\src\lib.rs:43
  24: qtest::eng::Engine::execute_query
             at .\src\eng.rs:28
  25: qtest::main
             at .\src\main.rs:19
  26: core::ops::function::FnOnce::call_once<enum2$<core::result::Result<tuple$<>,miette::eyreish::Report> > (*)(),tuple$<> >
             at /rustc/d5a82bbd26e1ad8b7401f6a718a9c57c96905483\library\core\src\ops\function.rs:507
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
error: process didn't exit successfully: `target\debug\qtest.exe` (exit code: 101)

[obi1kenobi]

Sorry for the bug, and thanks for narrowing it down and sending the stack trace — very helpful!

It's currently late in the evening over here, but I'll look into this first thing tomorrow. At first glance, it looks like it shouldn't be a difficult fix and I'll get you unblocked ASAP.

[kurtlawrence]

@obi1kenobi No rush, I am just prototyping at the moment, so it isn't a blocker.

[obi1kenobi]

Interestingly, I'm not able to reproduce this error using the test schemas and adapters in the test suite. I've tried a variety of queries This is probably at least a contributing factor if not the outright reason why fuzzing didn't find the problem either.

Depending on your preference, there are two things we can do:

• If you're able / comfortable with sharing your adapter code, I'd be happy to take a look and debug it directly that way. I'd be happy to give you my email address so you don't have to post your code publicly, and I'll keep your code confidential and delete it as soon as I'm done debugging.
• Otherwise, I can make a branch where the Trustfall interpreter records additional debug information showing when the RefCell is being borrowed, and you could try running the problematic query using that tweaked Trustfall copy and then review and share the resulting logs. This is going to be a bit slower and might require a few tries until we're able to narrow down on the problem.

Sorry for the inconvenience! Let me know your thoughts.

[obi1kenobi]

I also forgot to ask: did you write your adapter in Rust or are you using the Python or WASM bindings instead?

[kurtlawrence]

Thanks for looking into it @obi1kenobi

The adapter is in Rust.

I'm off on leave for a few weeks, when I get back I'll see if I can get a minimal reproducible example. It could be that I am misusing the adapter API.

[obi1kenobi]

Thanks! I'm pretty sure this is a bug on the library side — no matter how the adapter is (mis)used, it shouldn't ever trigger a double borrow error like this. I'd love to track it down, and I appreciate your help. No rush, whenever you're able to get back to it is fine. I'll set a reminder to check back in in a month if I haven't heard back yet.

[kurtlawrence]

Hi @obi1kenobi.

I have managed to create a minimal reproducible example which breaks on my machine.
The weird thing is that if I mimic the code but use a slightly different vertex name, it works as expected. Not entirely sure why that is.

I also tracked down the culprit, there is a borrow in compute_fold which invokes whilst iterating in construct_outputs. I have managed to work around the double borrow by collecting the output_iterator (iterating through the collection) before the adaptor borrow occurs.

Breaking Example

use std::cell::RefCell;
use std::{collections::BTreeMap, fs, iter::*, rc::Rc};
use trustfall::{provider::*, FieldValue, Schema};

fn main() {
  let query = QUERY;

  let schema = Schema::parse(SCHEMA).unwrap();
  let adptr = Rc::new(RefCell::new(BulkAdapter {}));

  let variables: BTreeMap<String, FieldValue> = Default::default();

  let xs = trustfall::execute_query(&schema, Rc::clone(&adptr), query, variables).unwrap();
}

pub struct BulkAdapter {}

#[derive(Debug, Clone, TrustfallEnumVertex)]
pub enum Db {
  Spry,
}

impl<'vertex> BasicAdapter<'vertex> for BulkAdapter {
  type Vertex = Db;

  fn resolve_starting_vertices(
      &mut self,
      edge_name: &str,
      parameters: &EdgeParameters,
  ) -> VertexIterator<'vertex, Self::Vertex> {
      Box::new(once(Db::Spry))
  }

  fn resolve_property(
      &mut self,
      contexts: ContextIterator<'vertex, Self::Vertex>,
      type_name: &str,
      property_name: &str,
  ) -> ContextOutcomeIterator<'vertex, Self::Vertex, trustfall::FieldValue> {
      let contexts = contexts.map(|x| dbg!(x)).collect::<Vec<_>>();
      todo!()
  }

  fn resolve_neighbors(
      &mut self,
      contexts: ContextIterator<'vertex, Self::Vertex>,
      type_name: &str,
      edge_name: &str,
      parameters: &EdgeParameters,
  ) -> ContextOutcomeIterator<'vertex, Self::Vertex, VertexIterator<'vertex, Self::Vertex>> {
      trustfall::provider::resolve_neighbors_with(contexts, |_| Box::new(once(Db::Spry)))
  }

  fn resolve_coercion(
      &mut self,
      contexts: ContextIterator<'vertex, Self::Vertex>,
      type_name: &str,
      coerce_to_type: &str,
  ) -> ContextOutcomeIterator<'vertex, Self::Vertex, bool> {
      todo!()
  }
}

const QUERY: &str = r#"
# import * from "src/schema.graphql"

{
  Spry(file: "dev.spry") {
      cases {
          # fullname @output
          name @output
          equipment @fold {
              eqname: fullname @output
          }
          # steps {
          #     index @output
          # }
      }
  }
}
"#;

const SCHEMA: &str = r#"
schema {
  query: RootSchemaQuery
}
directive @output(
  """What to designate the output field generated from this property field."""
  name: String
) on FIELD
directive @fold on FIELD

type RootSchemaQuery {
  Spry(file: String): SpryProject
}

type SpryProject {
  cases: [Case]
}

type Case {
  name: String
  fullname: String
  equipment: [Equipment]
  steps: [ScheduleStep]
}

type Equipment {
  name: String
  fullname: String
}

interface ScheduleStep {
  index: Int
}

type ProductiveScheduleStep implements ScheduleStep {
  index: Int
}
"#;

More Details of Borrow Stack

• The compute_fold is where the borrow occurs, it is called within the iterator of returned by compute_component.

trustfall/trustfall_core/src/interpreter/execution.rs

Lines 69 to 71 in db8abec

	iterator = compute_component(adapter.clone(), &mut carrier, component, iterator);
	Ok(construct_outputs(adapter.as_ref(), &mut carrier, iterator))

    // The `compute_fold` is _lazily_ being evaluated here
    iterator = compute_component(adapter.clone(), &mut carrier, component, iterator);

    // passed here
    Ok(construct_outputs(adapter.as_ref(), &mut carrier, iterator))

• Before the resolve_property call the adaptor is borrowed.
• But the iteration of the contexts invokes compute_fold which tries to borrow again!
• A solution is to collect the iterator before the adaptor borrow.

trustfall/trustfall_core/src/interpreter/execution.rs

Lines 238 to 253 in db8abec

	let moved_iterator = Box::new(output_iterator.map(move |context| {
	let new_vertex = context.vertices[&vertex_id].clone();
	context.move_to_vertex(new_vertex)
	}));
	let mut adapter_ref = adapter.borrow_mut();
	let resolve_info = ResolveInfo::new(query, vertex_id, true);
	let type_name = &root_component.vertices[&vertex_id].type_name;
	let field_data_iterator = adapter_ref.resolve_property(
	moved_iterator,
	type_name,
	&context_field.field_name,
	&resolve_info,
	);
	drop(adapter_ref);

        // This iterator is still lazy
        let moved_iterator = Box::new(output_iterator.map(move |context| {
            let new_vertex = context.vertices[&vertex_id].clone();
            context.move_to_vertex(new_vertex)
        }));
        // NOTE: if we append a `.collect::<Vec<_>>()` after the map this will
        // avoid the double borrow because the iteration will have evaluated.


        // borrow occurs here
        let mut adapter_ref = adapter.borrow_mut();
        let resolve_info = ResolveInfo::new(query, vertex_id, true);


        let type_name = &root_component.vertices[&vertex_id].type_name;
        // The moved iterator will invoke `compute_fold` when evaluating.
        let field_data_iterator = adapter_ref.resolve_property(
            moved_iterator,
            type_name,
            &context_field.field_name,
            &resolve_info,
        );
        drop(adapter_ref);

[obi1kenobi]

Thank you so much for all the work you've done on this! I'm making this issue my top priority for today.

[obi1kenobi]

Fascinating. Confirming this as a re-entrancy bug. If it wasn't for Rust's commitment to safety, this would have been ~impossible to get to the bottom of, since the symptoms would have started even more downstream from here.

Collecting the iterator early would solve it, but it is quite undesirable as a solution since it makes almost the entire execution eager instead of lazy. I'm going to spend some time looking for alternatives.

Another possible workaround for your particular adapter is to avoid the .collect() in the resolve_property() implementation. Proceeding element-wise avoids the problem, and is why the project's (already fairly extensive) test suite didn't catch this problem. In the meantime, I'm going to be extending the test suite some more based on this test case!

Again, apologies for the inconvenience and thanks for the help in getting to the bottom of it!

[obi1kenobi]

For the benefit of both the current implementation and future work like #83, I think the best way to fix this issue is with a breaking change to the Adapter API.

I'm planning to change the Adapter trait to take &self instead of &mut self. That will allow removing RefCell throughout and will avoid the problem. This is the best option, since adapters must be reentrancy-safe — or else we're forever locking out the functionality and performance improvements that work like #83 can bring.

Unfortunately, it also means that users that need mutability will need to use their own RefCell in the adapter and will need to take care to avoid reentrancy issues. But unlike the reentrancy in this bug, that reentrancy is possible to avoid: first pull from the input iterator, and then call .borrow_mut(). This change is regrettable, but bearable and necessary. I'll highlight it in the release notes for the next version.