4 ms·

I've been playing around with my own glob implementation. From what I've seen, the simplified algorithm mentioned in the article wouldn't be able to handle ques

by E6300 9y ago

I've been playing around with my own glob implementation. From what I've seen, the simplified algorithm mentioned in the article wouldn't be able to handle question marks. In particular, I don't think a non-backtracking algorithm can handle a pattern like "?a?a?a?a?b". I've been working to minimize the worst-case behavior, but it's tricky.

JdeBP 9y ago
Your semantics for question marks are wrong. Question marks matching zero or one characters are the semantics for IBM/Microsoft command interpreters, for reasons that go back all of the way to CP/M. (Strictly speaking the original semantics amounted to, because of the 8.3 field padding, question marks matching a character, the end of the string, or zero characters if immediately before the dot.) In POSIX, question marks match exactly one character, always. There's no need for backtracking. * http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_13_01 http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3...
- E6300 9y ago
  HN screwed up my comment. It's not supposed to be "question mark, a, question mark, a, ...". I meant to write "question mark, a, star, question mark, a, star, ...".
  - JdeBP 9y ago
    That would be backtracking caused by those stars, not by the question marks. Hacker News didn't screw up the part where you wrote "wouldn't be able to handle question marks".
    - E6300 9y ago
      A pattern like "star a star a star a star" can be handled by the algorithm described in the article: > Consider the pattern "a star bx star cy star d". If we end the first star at the first bx, we have the rest of the name to find the cy and then the d. Using any later bx can only remove choices for cy and d; it cannot lead to a successful match that using the first bx missed. So we should implement a star bx star cy star d without any second-guessing, as “find a leading a, then find the earliest bx after that, then find the earliest cy after that, then find a trailing d, or else give up.” This algorithm doesn't work if the pattern has question marks.
      - rsc 9y ago
        Yes it does.
    - E6300 9y ago
      I made a type in my previous response. I wrote "can be handled" instead of "can't be handled". The algorithm described can't handle that case.
rsc 9y ago
In addition to what JdeBP said about the semantics of question marks, there's always the option of using a proper automata translation (or translation to a regexp with a suitable underlying engine). Neither of those require backtracking.

by E6300 9y ago

JdeBP 9y ago

Your semantics for question marks are wrong. Question marks matching zero or one characters are the semantics for IBM/Microsoft command interpreters, for reasons that go back all of the way to CP/M. (Strictly speaking the original semantics amounted to, because of the 8.3 field padding, question marks matching a character, the end of the string, or zero characters if immediately before the dot.) In POSIX, question marks match exactly one character, always. There's no need for backtracking. * http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_13_01 http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3...

E6300 9y ago
HN screwed up my comment. It's not supposed to be "question mark, a, question mark, a, ...". I meant to write "question mark, a, star, question mark, a, star, ...".
- JdeBP 9y ago
  That would be backtracking caused by those stars, not by the question marks. Hacker News didn't screw up the part where you wrote "wouldn't be able to handle question marks".
  - E6300 9y ago
    A pattern like "star a star a star a star" can be handled by the algorithm described in the article: > Consider the pattern "a star bx star cy star d". If we end the first star at the first bx, we have the rest of the name to find the cy and then the d. Using any later bx can only remove choices for cy and d; it cannot lead to a successful match that using the first bx missed. So we should implement a star bx star cy star d without any second-guessing, as “find a leading a, then find the earliest bx after that, then find the earliest cy after that, then find a trailing d, or else give up.” This algorithm doesn't work if the pattern has question marks.
    - rsc 9y ago
      Yes it does.
  - E6300 9y ago
    I made a type in my previous response. I wrote "can be handled" instead of "can't be handled". The algorithm described can't handle that case.

rsc 9y ago

In addition to what JdeBP said about the semantics of question marks, there's always the option of using a proper automata translation (or translation to a regexp with a suitable underlying engine). Neither of those require backtracking.