5 ms·
Why write a glob engine at all when you already have a fast regex implementation that can match both exact paths and plausible subtrees? The bulk of the haskel
by oconnore 9y ago
Why write a glob engine at all when you already have a fast regex implementation that can match both exact paths and plausible subtrees?
The bulk of the haskell code to do this:
parseGlob :: Char -> Char -> String -> Parser Glob
parseGlob escC sepC forbid =
many1' (gpart <|> sep <|> glob <|> alt) >>= return . GGroup . V.fromList
where gpart = globPart escC (sepC : (forbid ++ "{*")) >>= return . GPart
sep = satisfy (== ch2word sepC) >> return GSeparator
alt = do
_ <- AttoC.char '{'
choices <- sepBy' (GEmpty `option` parseGlob escC sepC (",}" ++ forbid)) (char ',')
_ <- AttoC.char '}'
return $ GAlternate $ V.fromList choices
glob = do
res <- takeWhile1 (== ch2word '*')
if B.length res == 1 then
return GSingle
else
return GDouble
wrapParens s = T.concat ["(", s, ")"]
globRegex :: Char -> Glob -> T.Text
globRegex sep GSingle = T.concat ["([^", T.singleton sep, "]*|\\", T.singleton sep, ")"]
globRegex _ GDouble = ".*"
globRegex _ GEmpty = ""
globRegex sep GSeparator = T.singleton sep
globRegex sep (GRepeat a) = T.concat ["(", T.concat (V.toList $ fmap (globRegex sep) a), ")*"]
globRegex sep (GGroup a) = T.concat $ V.toList $ fmap (globRegex sep) a
globRegex _ (GPart p) = T.concatMap efun base
where base = TE.decodeUtf8 p
escChars = S.fromList ".[]()\\{}^$*+"
efun c = if S.member c escChars
then T.concat ["\\", T.singleton c]
else T.singleton c
globRegex sep (GAlternate a) =
if V.null alts
then ""
else T.concat [altsStr, if hasEmpty then "?" else ""]
where hasEmpty = isJust $ V.find (== GEmpty) a
alts = fmap (globRegex sep) $ V.filter (/= GEmpty) a
altsStr = wrapParens $ T.intercalate "|" $ V.toList alts
- f2f 9y agoWhy write a glob engine at all when you already have a fast regex you didn't read the article. there are glob implementations that do just that.
- oconnore 9y agoThe bulk of the article is about how the Go implementation avoids this behavior without just converting to regex.
- taeric 9y agoI took it more as the bulk of the article explaining the differences and problems in algorithms. Just knowing that you can use a non-backtracking regex engine is fine, of course. Knowing how folks got it wrong is pedagogical in its own right. As an easy additional point to the lesson, it might not be clear to everyone why you have to take care on which regex engine you move to.
- hkeide 9y agoNo, the Go standard library implementation is mentioned in a single paragraph. The Go code in the article is written simply as an illustration.
- jwilk 9y agoFrom the HN guidelines: Please don't insinuate that someone hasn't read an article. "Did you even read the article? It mentions that" can be shortened to "The article mentions that."
- thomasahle 9y agoDid you just write this now? Are you saying that the above parser is linear time worst case?
- oconnore 9y agoI wrote it a few months ago. The resulting regex is linear time worst case in thompson or dfa regex engines.