8000 RFC: Needle API (née Pattern API) by kennytm · Pull Request #2500 · rust-lang/rfcs · GitHub
[go: up one dir, main page]
Skip to content

RFC: Needle API (née Pattern API) #2500

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 10 commits into from
Nov 29, 2018
Merged

RFC: Needle API (née Pattern API) #2500

Changes from 1 commit
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
d53f3a1
Pattern API v3.0, first draft.
kennytm Jul 6, 2018
d0782c8
Add shallow cloning to unresolved questions.
kennytm Jul 18, 2018
e10b004
Merge Searcher and Consumer.
kennytm Jul 24, 2018
5f00210
Fix typos and addressed some review comments.
kennytm Aug 3, 2018
370bd60
Make Hay and Haystack unsafe.
kennytm Aug 4, 2018
eba46df
Split Searcher and Consumer again.
kennytm Aug 11, 2018
58741a8
s/Pattern/Needle/g
kennytm Aug 25, 2018
07308d4
Explain ReverseSearcher and DoubleEndedSearcher.
kennytm Nov 14, 2018
7b0f0c3
Fixed typo.
kennytm Nov 14, 2018
e69b245
RFC 2500
Centril Nov 29, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Fix typos and addressed some review comments.
  • Loading branch information
@kennytm
kennytm committed Aug 3, 2018
commit 5f00210403c959073da1344f7e55fe394288c09d
16 changes: 11 additions & 5 deletions text/0000-pattern-3.md
View file
Open in desktop
assert_eq!("EF".into_searcher().consume(span.clone()), None);
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,11 @@ A hay can *borrowed* from a haystack.
pub trait Haystack: Deref<Target: Hay> + Sized {
Copy link

Choose a reason for hiding this comment

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

I think that, due to its unsafe methods being called from safe code (e.g. in trim_start), Haystack needs to be an unsafe trait. Otherwise, without ever writing an unsafe block and therefore promising to uphold the invariants of safe code, an invalid implementation of Haystack could violate memory safety. The fact that split_around and split_unchecked are unsafe capture the fact that the caller, to preserve memory safety, must pass in valid indices, but it does nothing to prevent the callee from doing arbitrary bad behaviour even if the indices are valid.

Hay probably also needs to be an unsafe trait. It looks like in practice, Searchers are implemented for specific Hay types, indicating trust of just those implementations, and , so it may not be strictly necessary. Additionally, one of the requirements of a valid Haystack implementation could be the validity of the associated Hay type. However, with the proposed impl<'a, H: Hay> Haystack for &'a H, this is impossible to promise, and I think it would be necessary for Hay to be an unsafe trait.

Copy link
Contributor

Choose a reason for hiding this comment

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

I agree.

Copy link
Member Author

Choose a reason for hiding this comment

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

Fixed, both are now unsafe.

fn empty() -> Self;
unsafe fn split_around(self, range: Range<Self::Target::Index>) -> [Self; 3];
unsafe fn slice_unchecked(self, range: Range<Self::Target::Index>) -> Self;

unsafe fn slice_unchecked(self, range: Range<Self::Target::Index>) -> Self {
let [_, middle, _] = self.split_around(range);
middle
}

fn restore_range(
&self,
Expand Down Expand Up @@ -269,7 +273,7 @@ pub unsafe trait DoubleEndedSearcher<A: Hay + ?Sized>: ReverseSearcher<A> {}
with invalid ranges. Implementations of these methods often start with:

```rust
fn search(&mut self, span: SharedSpan<&A>) -> Option<Range<A::Index>> {
fn search(&mut self, span: Span<&A>) -> Option<Range<A::Index>> {
let (hay, range) = span.into_parts();
// search for pattern from `hay` restricted to `range`.
}
Expand All @@ -285,13 +289,13 @@ The `.consume()` method will is similar, but anchored to the start of the span.
let span = unsafe { Span::from_parts("CDEFG", 3..8) };
// we can find "CD" at the start of the span.
assert_eq!("CD".into_searcher().search(span.clone()), Some(3..5));
assert_eq!("CD".into_searcher().consume(span.clone()), Some(5));
assert_eq!("CD".into_consumer().consume(span.clone()), Some(5));
// we can only find "EF" in the middle of the span.
assert_eq!("EF".into_searcher().search(span.clone()), Some(5..7));
assert_eq!("EF".into_consumer().consume(span.clone()), None);
// we cannot find "GH" in the span.
assert_eq!("GH".into_searcher().search(span.clone()), None);
assert_eq!("GH".into_searcher().consume(span.clone()), None);
assert_eq!("GH".into_consumer().consume(span.clone()), None);
```

The trait also provides a `.trim_start()` method in case a faster specialization exists.
Expand Down Expand Up @@ -1629,6 +1633,8 @@ Unlike this RFC, the `Extract` class is much simpler.
the core type `&A` only, we could keep `SharedHaystack` unstable longer
(a separate track from the main Pattern API) until this question is resolved.

* With a benefit of type checking, we may still want to split `Consumer` from `Searcher`.

[RFC 528]: https://github.com/rust-lang/rfcs/pull/528
[RFC 1309]: https://github.com/rust-lang/rfcs/pull/1309
[RFC 1672]: https://github.com/rust-lang/rfcs/pull/1672
Expand Down
0