Skip to content

Conversation

mpawlowski-eyeo
Copy link
Contributor

This addresses #8200.

The overall idea:

  • string-type keys are stored in flatbuffers as char* null-terminated arrays.
  • LookupByKey only works correctly with const char* null-terminated arguments because it ends up calling std::bsearch that compares T::key_member() with the argument via strcmp
  • Non-null terminated strings, like a string_view that is size()-terminated, could also be used by LookupByKey
  • I introduce an overload of KeyCompareWithValue that should work for any string-like type that can compare itself to a const char* via operator<

Here's an example when this could be useful:

// schema
table FilesystemPermissions {
  path: string (key);
  access_granted: bool;
}
// C++

bool HasPermission(const std::string& path) {
  std::string_view sub_path = path;
  while (!sub_path.empty()) {
    auto* perm = filesystem_permissions()->LookupByKey(sub_path);
    if (perm && perm->access_granted)
      return true;
    // maybe there's a permission for the parent folder?
    sub_path.remove_suffix(sub_path.size() - sub_path.rfind('/'));
  }
  return false;
}

if path is "/usr/local/bin/calculator"
and filesystem_permissions() contains:
"/usr" -> access_granted: true
I expect the LookupByKey(sub_path) to search for:
"/usr/local/bin/calculator"
"/usr/local/bin"
"/usr/local"
"/usr" -> Found!

Instead, LookupByKey(sub_path.c_str()) searches for "/usr/local/bin/calculator" 5 times,
because sub_path.remove_suffix() does not modify path, does not insert
a null terminator, only reduces the size() of sub_path.

@github-actions github-actions bot added c++ codegen Involving generating code from schema labels Jan 1, 2024
@mpawlowski-eyeo
Copy link
Contributor Author

Q: Does a change like this warrant incrementing FLATBUFFERS_VERSION?

Copy link
Collaborator

@dbaileychess dbaileychess left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks a lot, i think just moving to using a common function would be ideal.

@dbaileychess dbaileychess merged commit 0cfb7eb into google:master Mar 25, 2024
jochenparm pushed a commit to jochenparm/flatbuffers that referenced this pull request Oct 29, 2024
…8203)

* Reproduce the error in a unit test

Reproduces google#8200

* Overload KeyCompareWithValue to work for string-like objects

This fixes google#8200.

* Extra tests

---------

Co-authored-by: Derek Bailey <derekbailey@google.com>
jochenparm pushed a commit to jochenparm/flatbuffers that referenced this pull request Oct 29, 2024
…8203)

* Reproduce the error in a unit test

Reproduces google#8200

* Overload KeyCompareWithValue to work for string-like objects

This fixes google#8200.

* Extra tests

---------

Co-authored-by: Derek Bailey <derekbailey@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
c++ codegen Involving generating code from schema
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants