Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: BurntSushi/aho-corasick
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 0.7.13
Choose a base ref
...
head repository: BurntSushi/aho-corasick
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 0.7.14
Choose a head ref
  • 3 commits
  • 6 files changed
  • 2 contributors

Commits on Jul 1, 2020

  1. doc: fix confusing typo

    PR #63
    Ten0 authored Jul 1, 2020
    Configuration menu
    Copy the full SHA
    39b029b View commit details
    Browse the repository at this point in the history

Commits on Oct 12, 2020

  1. prefilter: fix bug when doing a stream search

    This fixes yet another bug in the prefilter. Sigh. This only occurs when
    doing a stream search. The problem is that the stream handling code
    assumes that if no match is found at the end of the buffer, then the
    current state of the automaton is correctly updated and the buffer can
    be rolled.
    
    With most prefilters that look for a candidate *start* of a match, this
    is okay. If a prefilter can't find anything, then there's nothing to
    start and the current state remains in the starting state.
    
    But if the prefilter looks for a byte that may not be at the start of
    the match---like the rare byte prefilter---then we cannot assume that a
    match doesn't begin near the end of the buffer searched. And in this
    case, the internal implementation of search doesn't correctly hold up
    it's contract because the current state won't be updated. That is, there
    is an embedded assumption that if a prefilter fails then there is no
    match and thus there is no need to update the current state ID. But of
    course, this is just not true in a streaming context.
    
    The right way to fix this is unfortunately to rethink how we've
    implemented stream searching and make it aware of these kinds of
    prefilters. I think, anyway. The other option would be to fix the lower
    level search APIs to always make sure the current state ID is correct.
    That would fix everything, but that seems tricky and probably requires
    some delicate handling.
    
    So for now, we just disable a prefilter entirely if it's a rare byte
    prefilter and we're doing a stream search. We could build a backup
    prefilter and still use that, but it feels like a gross hack. At least
    now, we preserve correctness.
    
    Kudos to @ogoffart who did the initial investigation here and came up
    with a regression test, which is included in this commit. Note though,
    that some tests do fail when the buffer's size is set to its minimum. So
    there was a regression at some point because we aren't getting the best
    test coverage. We should just bite the buffer and make the buffer size
    configurable as an internal API so that tests can tweak it and provoke
    more edge cases.
    
    Fixes #64
    BurntSushi committed Oct 12, 2020
    Configuration menu
    Copy the full SHA
    e5ea128 View commit details
    Browse the repository at this point in the history
  2. 0.7.14

    BurntSushi committed Oct 12, 2020
    Configuration menu
    Copy the full SHA
    63f0b52 View commit details
    Browse the repository at this point in the history
Loading