Insertion of a key, A, that is a complete subset of another key, B, prevents A from being found #12
Comments
|
Just read a comment you made in another thread about full prefixes not being supported, and using terminating characters instead. I'll close as this is obviously intended behaviour. |
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 1, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 1, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 1, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 2, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 2, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 2, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 3, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 3, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
1 task
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Consider 2 key-value pairs:
"tester" => 1
"test" => 2
Inserting both of these in the radix tree, in either order, results in a tree that fails to match on lookups using key "test".
Leaf nodes are always nodes representing the right-most bytes of the key, and a leaf node is regarded as synonymous with a match. However, the node representing the superset key is not split to allow a node representing the end of the subset key (or a "string end" leaf node if the leaf == match semantics are to be preserved).
The text was updated successfully, but these errors were encountered: