facebookincubator / retrie

Retrie is a powerful, easy-to-use codemodding tool for Haskell.
MIT License
502 stars 30 forks source link

Retrie is a powerful, easy-to-use codemodding tool for Haskell.

Install

cabal update
cabal install retrie

Example

Assume you have some code, including functions like foo:

module MyModule where

foo :: [Int] -> [Int]
foo ints = map bar (map baz ints)

Someone points out that traversing the list ints twice is slower than doing it once. You could fix the code by hand, or you could rewrite it with retrie:

retrie --adhoc "forall f g xs. map f (map g xs) = map (f . g) xs"

Retrie applies the equation as a rewrite to all the Haskell modules it finds in the current directory:

 module MyModule where

 foo :: [Int] -> [Int]
-foo ints = map bar (map baz ints)
+foo ints = map (bar . baz) ints

Of course, now you might find this code more difficult to understand. You also learn that GHC will do this sort of optimization automatically, so you decide to undo your rewrite:

retrie --adhoc "forall f g xs. map (f . g) xs = map f (map g xs)"

Now you have your original code back.

Other Sources Of Equations

To try some examples, put the following into MyModule2.hs:

module MyModule2 where

maybe :: b -> (a -> b) -> Maybe a -> b
maybe d f mb = case mb of
  Nothing -> d
  Just x -> f x

type MyMaybe = Maybe Int

{-# RULES "myRule" forall x. maybe Nothing Just x = x #-}

foo :: Maybe Int
foo = maybe Nothing Just (Just 5)

Then try the following rewrites and check the contents of the module after each step:

retrie --type-backward MyModule2.MyMaybe
 module MyModule2 where

 maybe :: b -> (a -> b) -> Maybe a -> b
 maybe d f mb = case mb of
   Nothing -> d
   Just x -> f x

 type MyMaybe = Maybe Int

 {-# RULES "myRule" forall x. maybe Nothing Just x = x #-}

-foo :: Maybe Int
+foo :: MyMaybe
 foo = maybe Nothing Just (Just 5)
retrie --unfold MyModule2.maybe
 module MyModule2 where

 maybe :: b -> (a -> b) -> Maybe a -> b
 maybe d f mb = case mb of
   Nothing -> d
   Just x -> f x

 type MyMaybe = Maybe Int

-{-# RULES "myRule" forall x. maybe Nothing Just x = x #-}
+{-# RULES "myRule" forall x. case x of
+            Nothing -> Nothing
+            Just x1 -> Just x1 = x #-}

 foo :: MyMaybe
-foo = maybe Nothing Just (Just 5)
+foo = case Just 5 of
+  Nothing -> Nothing
+  Just x -> Just x
retrie --fold MyModule2.maybe
 module MyModule2 where

 maybe :: b -> (a -> b) -> Maybe a -> b
 maybe d f mb = case mb of
   Nothing -> d
   Just x -> f x

 type MyMaybe = Maybe Int

-{-# RULES "myRule" forall x. case x of
-            Nothing -> Nothing
-            Just x1 -> Just x1 = x #-}
+{-# RULES "myRule" forall x. maybe Nothing Just x = x #-}

 foo :: MyMaybe
-foo = case Just 5 of
-  Nothing -> Nothing
-  Just x -> Just x
+foo = maybe Nothing Just (Just 5)
retrie --rule-forward MyModule2.myRule
 module MyModule2 where

 maybe :: b -> (a -> b) -> Maybe a -> b
 maybe d f mb = case mb of
   Nothing -> d
   Just x -> f x

 type MyMaybe = Maybe Int

 {-# RULES "myRule" forall x. maybe Nothing Just x = x #-}

 foo :: MyMaybe
-foo = maybe Nothing Just (Just 5)
+foo = Just 5
retrie --type-forward MyModule2.MyMaybe
 module MyModule2 where

 maybe :: b -> (a -> b) -> Maybe a -> b
 maybe d f mb = case mb of
   Nothing -> d
   Just x -> f x

 type MyMaybe = Maybe Int

 {-# RULES "myRule" forall x. maybe Nothing Just x = x #-}

-foo :: MyMaybe
+foo :: Maybe Int
 foo = Just 5

Motivation

Refactoring tools fall on a spectrum. At one end is simple string replacement (grep and sed). At the other is parsing an abstract-syntax tree (AST) and directly manipulating it. Broadly, the tradeoffs are:

Retrie finds a middle ground:

Features

See retrie --help for a complete list of options.

Scripting and Side Conditions

Retrie can be used as a library to tackle more complex rewrites.

Consider the task of changing the argument type of a function from String to an enumeration:

fooOld :: String -> IO ()

data FooArg = Foo | Bar

fooNew :: FooArg -> IO ()

Retrie provides a small monadic DSL for scripting the application of rewrites. It also allows you to intercept and manipulate the result of matching the left-hand side of an equation. Putting those two together, you could implement the following refactoring:

{-# LANGUAGE OverloadedStrings #-}
module Main where

import qualified GHC.Paths as GHC.Paths
import Retrie

main :: IO ()
main = runScript GHC.Paths.libdir $ \opts -> do
  [rewrite] <- parseRewrites GHC.Paths.libdir opts [Adhoc "forall arg. fooOld arg = fooNew arg"]
  return $ apply [setRewriteTransformer stringToFooArg rewrite]

argMapping :: [(FastString, String)]
argMapping = [("foo", "Foo"), ("bar", "Bar")]

stringToFooArg :: MatchResultTransformer
stringToFooArg _ctxt match
  | MatchResult substitution template <- match
  , Just (HoleExpr expr) <- lookupSubst "arg" substitution
  , L _ (HsLit _ (HsString _ str)) <- astA expr = do
    newExpr <- case lookup str argMapping of
      Nothing ->
        parseExpr GHC.Paths.libdir $ "error \"invalid argument: " ++ unpackFS str ++ "\""
      Just constructor -> parseExpr GHC.Paths.libdir constructor
    return $
      MatchResult (extendSubst substitution "arg" (HoleExpr newExpr)) template
  | otherwise = return NoMatch

Running this program would create the following diff:

 module MyModule3 where

 baz, bar, quux :: IO ()
-baz = fooOld "foo"
+baz = fooNew Foo

-bar = fooOld "bar"
+bar = fooNew Bar

-quux = fooOld "quux"
+quux = fooNew (error "invalid argument: quux")

Defining the stringToFooArg function requires knowledge of both the Retrie library and GHC's internal AST types. You'll find haddock/hoogle invaluable for both.

Reporting Bugs/Submitting Patches

To report a bug in the result of a rewrite, please create a test case (example) and submit it as an issue or merge request.

To report other bugs, please create a GitHub issue.

Build Status

License

Retrie is MIT licensed, as found in the LICENSE file.