Retrie

This module provides the external interface for using Retrie as a library. All other modules should be considered internal, with APIs that are subject to change without notice.

Scripting

runScript :: (Options -> IO (Retrie ())) -> IO ()

Define a custom refactoring script. A script is an IO action that defines a Retrie computation. The IO action is run once, and the resulting Retrie computation is run once for each target file. Typically, rewrite parsing/construction is done in the IO action, so it is performed only once. Example:

module Main where

main :: IO ()
main = runScript $ \opts -> do
  rr <- parseRewrites opts ["forall f g xs. map f (map g xs) = map (f . g) xs"]
  return $ apply rr

To run the script, compile the program and execute it.

runScriptWithModifiedOptions :: (Options -> IO (Options, Retrie ())) -> IO ()

Define a custom refactoring script and run it with modified options. This is the same as runScript, but the returned Options will be used during rewriting.

Parsing Rewrites

Imports

parseImports :: [String] -> IO AnnotatedImports

Parse import statements. Each string must be a full import statement, including the keyword 'import'. Supports full import syntax.

Queries

parseQueries :: Options -> [(Quantifiers, QuerySpec, v)] -> IO [Query Universe v]

Create Querys from string specifications of expressionstypesstatements.

data QuerySpec

Specifies which parser to use in parseQueries.

Constructors

QExpr String

QType String

QStmt String

Rewrites

parseRewrites :: Options -> [RewriteSpec] -> IO [Rewrite Universe]

Create Rewrites from string specifications of rewrites.

data RewriteSpec

Possible ways to specify rewrites to parseRewrites.

Constructors

Adhoc String

Equation in RULES-format. (e.g. "forall x. succ (pred x) = x") Will be applied left-to-right.

Fold QualifiedName

Fold a function definition. The inverse of unfolding/inlining. Replaces instances of the function body with calls to the function.

RuleBackward QualifiedName

Apply a GHC RULE right-to-left.

RuleForward QualifiedName

Apply a GHC RULE left-to-right.

TypeBackward QualifiedName

Apply a type synonym right-to-left.

TypeForward QualifiedName

Apply a type synonym left-to-right.

Unfold QualifiedName

Unfold, or inline, a function definition.

type QualifiedName = String

A qualified name. (e.g. "Module.Name.functionName")

Retrie Computations

data Retrie a

The Retrie monad is essentially IO, plus state containing the module that is being transformed. It is run once per target file.

It is special because it also allows Retrie to extract a set of GroundTerms from the Retrie computation without evaluating it.

Retrie uses the ground terms to select which files to target. This is the key optimization that allows Retrie to handle large codebases.

Note: Due to technical limitations, we cannot extract ground terms if you use liftIO before calling one of apply, focus, or query at least once. This will cause Retrie to attempt to parse every module in the target directory. In this case, please add a call to focus before the call to liftIO.

Instances

Monad Retrie

Defined in Retrie.Monad

Methods

(>>=) :: Retrie a -> (a -> Retrie b) -> Retrie b

(>>) :: Retrie a -> Retrie b -> Retrie b

return :: a -> Retrie a

fail :: String -> Retrie a

Functor Retrie

Defined in Retrie.Monad

Methods

fmap :: (a -> b) -> Retrie a -> Retrie b

(<$) :: a -> Retrie b -> Retrie a

Applicative Retrie

Defined in Retrie.Monad

Methods

pure :: a -> Retrie a

(<*>) :: Retrie (a -> b) -> Retrie a -> Retrie b

liftA2 :: (a -> b -> c) -> Retrie a -> Retrie b -> Retrie c

(*>) :: Retrie a -> Retrie b -> Retrie b

(<*) :: Retrie a -> Retrie b -> Retrie a

MonadIO Retrie

Defined in Retrie.Monad

Methods

liftIO :: IO a -> Retrie a

Applying Rewrites

apply :: [Rewrite Universe] -> Retrie ()

Apply a set of rewrites. By default, rewrites are applied top-down, pruning the traversal at successfully changed AST nodes. See topDownPrune.

applyWithStrategy :: Strategy (TransformT (WriterT Change IO)) -> [Rewrite Universe] -> Retrie ()

Apply a set of rewrites with a custom traversal strategy.

applyWithUpdate :: ContextUpdater -> [Rewrite Universe] -> Retrie ()

Apply a set of rewrites with a custom context-update function.

applyWithUpdateAndStrategy :: ContextUpdater -> Strategy (TransformT (WriterT Change IO)) -> [Rewrite Universe] -> Retrie ()

Apply a set of rewrites with custom context-update and traversal strategy.

addImports :: AnnotatedImports -> Retrie ()

Add imports to the module.

Control Flow

ifChanged :: Retrie () -> Retrie () -> Retrie ()

If the first Retrie computation makes a change to the module, run the second Retrie computation.

iterateR :: Int -> Retrie () -> Retrie ()

Iterate given Retrie computation until it no longer makes changes, or N times, whichever happens first.

Focusing

focus :: Data k => [Query k v] -> Retrie ()

Use the given queries/rewrites to select files for rewriting. Does not actually perform matching. This is useful if the queries/rewrites which best determine which files to target are not the first ones you run, and when you need to liftIO before running any queries/rewrites.

Querying the AST

query :: [Query Universe v] -> Retrie [(Context, Substitution, v)]

Query the AST. Each match returns the context of the match, a substitution mapping quantifiers to matched subtrees, and the query's value.

queryWithUpdate :: ContextUpdater -> [Query Universe v] -> Retrie [(Context, Substitution, v)]

Query the AST with a custom context update function.

Traversal Strategies

bottomUp :: Strategy m

Perform a bottom-up traversal.

topDown :: Strategy m

Perform a top-down traversal.

topDownPrune :: Monad m => Strategy (TransformT (WriterT Change m))

Top-down traversal that does not descend into changed AST nodes. Default strategy used by apply.

Advanced Scripting

For advanced rewriting, Retrie provides the notion of a MatchResultTransformer. This is a callback function that is provided the result of matching the left-hand side of an equation. Whatever the callback returns is used to perform the actual rewrite.

The callback has access to the Context of the match, the generated Substitution, and IO. Helper libraries such as Annotated and subst make it possible to define complex transformers without too much tedium.

Transformers can check side conditions by examining the MatchResult and returning NoMatch when conditions do not hold.

type MatchResultTransformer = Context -> MatchResult Universe -> IO (MatchResult Universe)

A MatchResultTransformer allows the user to specify custom logic to modify the result of matching the left-hand side of a rewrite (the MatchResult). The MatchResult generated by this function is used to effect the resulting AST rewrite.

For example, this transformer looks at the matched expression to build the resulting expression:

fancyMigration :: MatchResultTransformer
fancyMigration ctxt matchResult
  | MatchResult sub t <- matchResult
  , HoleExpr e <- lookupSubst sub "x" = do
    e' <- ... some fancy IO computation using 'e' ...
    return $ MatchResult (extendSubst sub "x" (HoleExpr e')) t
  | otherwise = NoMatch

main :: IO ()
main = runScript $ \opts -> do
  rrs <- parseRewrites opts [Adhoc "forall x. ... = ..."]
  return $ apply
    [ setRewriteTransformer fancyMigration rr | rr <- rrs ]

Since the MatchResultTransformer can also modify the Template, you can construct an entirely novel right-hand side, add additional imports, or inject new dependent rewrites.

defaultTransformer :: MatchResultTransformer

The default transformer. Returns the MatchResult unchanged.

data MatchResult ast

The result of matching the left-hand side of a Rewrite.

Constructors

MatchResult Substitution (Template ast)

NoMatch

Instances

Functor MatchResult

Defined in Retrie.Types

Methods

fmap :: (a -> b) -> MatchResult a -> MatchResult b

(<$) :: a -> MatchResult b -> MatchResult a

Annotated ASTs

data Annotated ast

Annotated packages an AST fragment with the annotations necessary to exactPrint or transform that AST.

Instances

Functor Annotated

Defined in Retrie.ExactPrint.Annotated

Methods

fmap :: (a -> b) -> Annotated a -> Annotated b

(<$) :: a -> Annotated b -> Annotated a

Foldable Annotated

Defined in Retrie.ExactPrint.Annotated

Methods

fold :: Monoid m => Annotated m -> m

foldMap :: Monoid m => (a -> m) -> Annotated a -> m

foldr :: (a -> b -> b) -> b -> Annotated a -> b

foldr' :: (a -> b -> b) -> b -> Annotated a -> b

foldl :: (b -> a -> b) -> b -> Annotated a -> b

foldl' :: (b -> a -> b) -> b -> Annotated a -> b

foldr1 :: (a -> a -> a) -> Annotated a -> a

foldl1 :: (a -> a -> a) -> Annotated a -> a

toList :: Annotated a -> [a]

null :: Annotated a -> Bool

length :: Annotated a -> Int

elem :: Eq a => a -> Annotated a -> Bool

maximum :: Ord a => Annotated a -> a

minimum :: Ord a => Annotated a -> a

sum :: Num a => Annotated a -> a

product :: Num a => Annotated a -> a

Traversable Annotated

Defined in Retrie.ExactPrint.Annotated

Methods

traverse :: Applicative f => (a -> f b) -> Annotated a -> f (Annotated b)

sequenceA :: Applicative f => Annotated (f a) -> f (Annotated a)

mapM :: Monad m => (a -> m b) -> Annotated a -> m (Annotated b)

sequence :: Monad m => Annotated (m a) -> m (Annotated a)

(Data ast, Monoid ast) => Semigroup (Annotated ast)

Defined in Retrie.ExactPrint.Annotated

Methods

(<>) :: Annotated ast -> Annotated ast -> Annotated ast

sconcat :: NonEmpty (Annotated ast) -> Annotated ast

stimes :: Integral b => b -> Annotated ast -> Annotated ast

(Data ast, Monoid ast) => Monoid (Annotated ast)

Defined in Retrie.ExactPrint.Annotated

Methods

mempty :: Annotated ast

mappend :: Annotated ast -> Annotated ast -> Annotated ast

mconcat :: [Annotated ast] -> Annotated ast

Default ast => Default (Annotated ast)

Defined in Retrie.ExactPrint.Annotated

Methods

def :: Annotated ast

astA :: Annotated ast -> ast

Examine the actual AST.

Type Synonyms

type AnnotatedHsDecl = Annotated (LHsDecl GhcPs)

type AnnotatedHsExpr = Annotated (LHsExpr GhcPs)

type AnnotatedHsType = Annotated (LHsType GhcPs)

type AnnotatedImports = Annotated [LImportDecl GhcPs]

type AnnotatedModule = Annotated (Located (HsModule GhcPs))

type AnnotatedPat = Annotated (Located (Pat GhcPs))

type AnnotatedStmt = Annotated (LStmt GhcPs (LHsExpr GhcPs))

Parsing

Note: These parsers do not re-associate infix operators. To do so, use fix. For example:

do
  expr <- parseExpr "f <$> x <*> y"
  e <- transformA expr (fix (fixityEnv opts))

parseDecl :: String -> IO AnnotatedHsDecl

Parse a top-level HsDecl.

parseExpr :: String -> IO AnnotatedHsExpr

Parse a HsExpr.

parsePattern :: String -> IO AnnotatedPat

Parse a Pat.

parseStmt :: String -> IO AnnotatedStmt

Parse a Stmt.

parseType :: String -> IO AnnotatedHsType

Parse a HsType.

Operations

transformA :: Monad m => Annotated ast1 -> (ast1 -> TransformT m ast2) -> m (Annotated ast2)

Transform an Annotated thing.

graftA :: (Data ast, Monad m) => Annotated ast -> TransformT m ast

Graft an Annotated thing into the current transformation. The resulting AST will have proper annotations within the TransformT computation. For example:

mkDeclList :: IO (Annotated [LHsDecl GhcPs])
mkDeclList = do
  ad1 <- parseDecl "myId :: a -> a"
  ad2 <- parseDecl "myId x = x"
  transformA ad1 $ \ d1 -> do
    d2 <- graftA ad2
    return [d1, d2]

pruneA :: (Data ast, Monad m) => ast -> TransformT m (Annotated ast)

Encapsulate something in the current transformation into an Annotated thing. This is the inverse of graftT. For example:

splitHead :: Monad m => Annotated [a] -> m (Annotated a, Annotated [a])
splitHead l = fmap astA $ transformA l $ \(x:xs) -> do
  y <- pruneA x
  ys <- pruneA xs
  return (y, ys)

trimA :: Data ast => Annotated ast -> Annotated ast

Trim the annotation data to only include annotations for ast. (Usually, the annotation data is a superset of what is necessary.) Also freshens all source locations, so filename information in annotation keys is discarded.

Note: not commonly needed, but useful if you want to inspect the annotation data directly and don't want to wade through a mountain of output.

printA :: Annotate ast => Annotated (Located ast) -> String

Exactprint an Annotated thing.

Util

Collection of miscellaneous helpers for manipulating the GHC AST.

module Retrie.Expr

Types

Context

data Context

Context maintained by AST traversals.

Constructors

Context

Fields

• ctxtBinders :: [RdrName]

  Stack of bindings of which we are currently in the right-hand side. Used to avoid introducing self-recursion.

• ctxtDependents :: Rewriter

  The rewriter we apply to determine whether to add context-dependent rewrites to ctxtRewriter. We keep this separate because most of the time it is empty, and we don't want to match every rewrite twice.

• ctxtFixityEnv :: FixityEnv

  Current FixityEnv.

• ctxtInScope :: AlphaEnv

  In-scope local bindings. Used to detect shadowing.

• ctxtParentPrec :: ParentPrec

  Precedence of parent (app = HasPrec 10, infix op = HasPrec $ op precedence)

• ctxtRewriter :: Rewriter

  The rewriter we should use to mutate the code.

• ctxtSubst :: Maybe Substitution

  If present, update substitution with binder renamings. Used to implement capture-avoiding substitution.

type ContextUpdater = forall m. MonadIO m => GenericCU (TransformT m) Context

Type of context update functions for apply. When defining your own ContextUpdater, you probably want to extend updateContext using SYB combinators such as mkQ and extQ.

updateContext :: forall m. MonadIO m => GenericCU (TransformT m) Context

Default context update function.

Options

type Options = Options_ [Rewrite Universe] AnnotatedImports

Command-line options.

data Options_ rewrites imports

Constructors

Options

Fields

• additionalImports :: imports

  Imports specified by the command-line flag '--import'.

• colorise :: ColoriseFun

  Function used to colorize results of certain execution modes.

• executionMode :: ExecutionMode

  Controls behavior of apply. See ExecutionMode.

• extraIgnores :: [FilePath]

  Specific files that should be ignored. Paths should be relative to targetDir.

• fixityEnv :: FixityEnv

  Fixity information for operators used during parsing (of rewrites and target modules). Defaults to base fixities.

• iterateN :: Int

  Iterate the given rewrites or Retrie computation up to this many times. Iteration may stop before the limit if no changes are made during a given iteration.

• randomOrder :: Bool

  Whether to randomize the order of target modules before rewriting them.

• rewrites :: rewrites

  Rewrites specified by command-line flags such as '--adhoc'.

• roundtrips :: [RoundTrip]

  Paths that should be roundtripped through ghc-exactprint to debug. Specified by the '--roundtrip' command-line flag.

• singleThreaded :: Bool

  Whether to concurrently rewrite target modules. Mostly useful for viewing debugging output without interleaving it.

• targetDir :: FilePath

  Directory that contains the code being targeted for rewriting.

• targetFiles :: [FilePath]

  Instead of targeting all Haskell files in targetDir, only target specific files. Paths should be relative to targetDir.

• verbosity :: Verbosity

  How much should be output on stdout.

data Verbosity

Constructors

Silent

Normal

Loud

Instances

Eq Verbosity

Defined in Retrie.Util

Methods

(==) :: Verbosity -> Verbosity -> Bool

(/=) :: Verbosity -> Verbosity -> Bool

Ord Verbosity

Defined in Retrie.Util

Methods

compare :: Verbosity -> Verbosity -> Ordering

(<) :: Verbosity -> Verbosity -> Bool

(<=) :: Verbosity -> Verbosity -> Bool

(>) :: Verbosity -> Verbosity -> Bool

(>=) :: Verbosity -> Verbosity -> Bool

max :: Verbosity -> Verbosity -> Verbosity

min :: Verbosity -> Verbosity -> Verbosity

Show Verbosity

Defined in Retrie.Util

Methods

showsPrec :: Int -> Verbosity -> ShowS

show :: Verbosity -> String

showList :: [Verbosity] -> ShowS

Quantifiers

module Retrie.Quantifiers

Queries

data Query ast v

Query is the primitive way to specify a matchable pattern (quantifiers and expression). Whenever the pattern is matched, the associated result will be returned.

Constructors

Query

Fields

• qQuantifiers :: Quantifiers
• qPattern :: Annotated ast
• qResult :: v

Instances

Bifunctor Query

Defined in Retrie.Types

Methods

bimap :: (a -> b) -> (c -> d) -> Query a c -> Query b d

first :: (a -> b) -> Query a c -> Query b c

second :: (b -> c) -> Query a b -> Query a c

Functor (Query ast)

Defined in Retrie.Types

Methods

fmap :: (a -> b) -> Query ast a -> Query ast b

(<$) :: a -> Query ast b -> Query ast a

Rewrites

type Rewrite ast = Query ast (Template ast, MatchResultTransformer)

A Rewrite is a Query specialized to Template results, which have all the information necessary to replace one expression with another.

data Template ast

The right-hand side of a Rewrite.

Constructors

Template

Fields

• tTemplate :: Annotated ast

  The expression for the right-hand side.

• tImports :: AnnotatedImports

  Imports to add whenever a rewrite is successful.

• tDependents :: Maybe [Rewrite Universe]

  Dependent rewrites to introduce whenever a rewrite is successful. See Note [tDependents]

Instances

Functor Template

Defined in Retrie.Types

Methods

fmap :: (a -> b) -> Template a -> Template b

(<$) :: a -> Template b -> Template a

mkRewrite :: Quantifiers -> Annotated ast -> Annotated ast -> Rewrite ast

Make a Rewrite from given quantifiers and left- and right-hand sides.

ppRewrite :: Rewrite Universe -> String

Pretty-print a Rewrite for debugging.

addRewriteImports :: AnnotatedImports -> Rewrite ast -> Rewrite ast

Add imports to a Rewrite. Whenever the Rewrite successfully rewrites an expression, the imports are inserted into the enclosing module.

setRewriteTransformer :: MatchResultTransformer -> Rewrite ast -> Rewrite ast

Set the MatchResultTransformer for a Rewrite.

Substitution

subst :: (MonadIO m, Data ast) => Substitution -> Context -> ast -> TransformT m ast

Perform the given Substitution on an AST, avoiding variable capture by alpha-renaming binders as needed.

See Retrie.Substitution for the Substitution type.

module Retrie.Substitution

Universe

data Universe

A sum type to collect all possible top-level rewritable types.

Instances

Data Universe

Defined in Retrie.Universe

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Universe -> c Universe

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Universe

toConstr :: Universe -> Constr

dataTypeOf :: Universe -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Universe)

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Universe)

gmapT :: (forall b. Data b => b -> b) -> Universe -> Universe

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Universe -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Universe -> r

gmapQ :: (forall d. Data d => d -> u) -> Universe -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Universe -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Universe -> m Universe

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Universe -> m Universe

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Universe -> m Universe

Matchable Universe

Defined in Retrie.Universe

Methods

inject :: Universe -> Universe

project :: Universe -> Universe

getOrigin :: Universe -> SrcSpan

class Matchable ast where

Class of types which can be injected into the Universe type.

Methods

inject :: ast -> Universe

Inject an AST into Universe

project :: Universe -> ast

Project an AST from a Universe. Can fail if universe contains the wrong type.

getOrigin :: ast -> SrcSpan

Get the original location of the AST.

Instances

Matchable Universe

Defined in Retrie.Universe

Methods

inject :: Universe -> Universe

project :: Universe -> Universe

getOrigin :: Universe -> SrcSpan

Matchable (LHsType GhcPs)

Defined in Retrie.Universe

Methods

inject :: LHsType GhcPs -> Universe

project :: Universe -> LHsType GhcPs

getOrigin :: LHsType GhcPs -> SrcSpan

Matchable (LHsExpr GhcPs)

Defined in Retrie.Universe

Methods

inject :: LHsExpr GhcPs -> Universe

project :: Universe -> LHsExpr GhcPs

getOrigin :: LHsExpr GhcPs -> SrcSpan

Matchable (LStmt GhcPs (LHsExpr GhcPs))

Defined in Retrie.Universe

Methods

inject :: LStmt GhcPs (LHsExpr GhcPs) -> Universe

project :: Universe -> LStmt GhcPs (LHsExpr GhcPs)

getOrigin :: LStmt GhcPs (LHsExpr GhcPs) -> SrcSpan

toURewrite :: Matchable ast => Rewrite ast -> Rewrite Universe

Inject a type-specific rewrite into the universal type.

fromURewrite :: Matchable ast => Rewrite Universe -> Rewrite ast

Project a type-specific rewrite from the universal type.

GHC API

Retrie.GHC re-exports the GHC API, with some helpers for consistency across versions.

module Retrie.GHC