reorder-expression-0.1.0.0: Reorder expressions in a syntax tree according to operator fixities.
Copyright (c) 2021 comp MIT onecomputer00@gmail.com stable portable Safe-Inferred Haskell2010

Expression.Reorder

Description

Reorders expressions in a syntax tree so that prefix, postfix, and infix operator chains are correct according to their associativity and precedence.

Get started by creating a SyntaxTree instance for your syntax types.

Synopsis

# Syntax tree reordering

class SyntaxTree t e | t -> e where Source #

Typeclass for syntax trees t with ambiguity errors e.

The reason for the error type is because there may be different types of expressions, e.g. value expressions and pattern matching patterns, so there is no way to return the offending expression without combining the types first.

Methods

reorderChildren :: t -> Validation (NonEmpty e) t Source #

Applies reorder to all children of this node that may have expressions to reorder.

This is usually in the form of a traversal over the children, which will aggregate errors via Validation.

structureOf :: t -> Node t Source #

Gets the structure of a node.

makeError :: Ambiguity -> t -> e Source #

Builds an error for the ambiguous expression given.

reorder :: forall t e. SyntaxTree t e => t -> Validation (NonEmpty e) t Source #

Reorders a syntax tree to have correct precedence and associativity.

Returns either the reordered tree or a list of ambiguous expression errors.

data Node t Source #

The structure of a node in a syntax tree in regards to operations.

A non-leaf node is made up of:

• An operator (associativity and precedence for infix nodes, just precedence for unary nodes).
• The open children of the node i.e. the children that may have reordering happen.
• A rebuilding function, which replaces the children of node and rebuilds it e.g. updating source locations.

Note that the arity referred to is the number of open children, not the arity of the operation itself.

Constructors

 NodePrefix Precedence t (t -> t) A prefix operator, where only the right-hand side is open, e.g. -n or if p then x else y. NodePostfix Precedence t (t -> t) A postfix operator, where only the left-hand side is open, e.g. obj.field or xs[n]. NodeInfix Fixity t t (t -> t -> t) An infix operator, where both sides are open, e.g. x + y or p ? x : y. NodeLeaf A leaf node where expressions may be contained, but are not open, e.g. (x + y) or do { x }.

data Validation e a Source #

Validation applicative, similar to Either but aggregates errors.

Constructors

 Success a Failure e

#### Instances

Instances details
 Source # Instance detailsDefined in Expression.Reorder Methodsbimap :: (a -> b) -> (c -> d) -> Validation a c -> Validation b d #first :: (a -> b) -> Validation a c -> Validation b c #second :: (b -> c) -> Validation a b -> Validation a c # Source # Instance detailsDefined in Expression.Reorder Methodsfmap :: (a -> b) -> Validation e a -> Validation e b #(<$) :: a -> Validation e b -> Validation e a # Source # Instance detailsDefined in Expression.Reorder Methodspure :: a -> Validation e a #(<*>) :: Validation e (a -> b) -> Validation e a -> Validation e b #liftA2 :: (a -> b -> c) -> Validation e a -> Validation e b -> Validation e c #(*>) :: Validation e a -> Validation e b -> Validation e b #(<*) :: Validation e a -> Validation e b -> Validation e a # (Eq a, Eq e) => Eq (Validation e a) Source # Instance detailsDefined in Expression.Reorder Methods(==) :: Validation e a -> Validation e a -> Bool #(/=) :: Validation e a -> Validation e a -> Bool # (Show a, Show e) => Show (Validation e a) Source # Instance detailsDefined in Expression.Reorder MethodsshowsPrec :: Int -> Validation e a -> ShowS #show :: Validation e a -> String #showList :: [Validation e a] -> ShowS # Generic (Validation e a) Source # Instance detailsDefined in Expression.Reorder Associated Typestype Rep (Validation e a) :: Type -> Type # Methodsfrom :: Validation e a -> Rep (Validation e a) x #to :: Rep (Validation e a) x -> Validation e a # type Rep (Validation e a) Source # Instance detailsDefined in Expression.Reorder type Rep (Validation e a) = D1 ('MetaData "Validation" "Expression.Reorder" "reorder-expression-0.1.0.0-inplace" 'False) (C1 ('MetaCons "Success" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "Failure" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 e))) # Operator properties data Fixity Source # The fixity of an operator. Constructors  Fixity Fields #### Instances Instances details  Source # Instance detailsDefined in Expression.Reorder Methods(==) :: Fixity -> Fixity -> Bool #(/=) :: Fixity -> Fixity -> Bool # Source # Instance detailsDefined in Expression.Reorder MethodsshowsPrec :: Int -> Fixity -> ShowS #showList :: [Fixity] -> ShowS # Source # Instance detailsDefined in Expression.Reorder Associated Typestype Rep Fixity :: Type -> Type # Methodsfrom :: Fixity -> Rep Fixity x #to :: Rep Fixity x -> Fixity # type Rep Fixity Source # Instance detailsDefined in Expression.Reorder type Rep Fixity = D1 ('MetaData "Fixity" "Expression.Reorder" "reorder-expression-0.1.0.0-inplace" 'False) (C1 ('MetaCons "Fixity" 'PrefixI 'True) (S1 ('MetaSel ('Just "fixityAssoc") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Assoc) :*: S1 ('MetaSel ('Just "fixityPrec") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Precedence))) data Assoc Source # The associativity of an operator. Constructors  AssocLeft Associates to the left: (a * b) * c. AssocRight Associates to the right: a * (b * c). AssocNone Does not associate at all: a * b * c would be ambiguous. #### Instances Instances details  Source # Instance detailsDefined in Expression.Reorder Methods(==) :: Assoc -> Assoc -> Bool #(/=) :: Assoc -> Assoc -> Bool # Source # Instance detailsDefined in Expression.Reorder MethodsshowsPrec :: Int -> Assoc -> ShowS #show :: Assoc -> String #showList :: [Assoc] -> ShowS # Source # Instance detailsDefined in Expression.Reorder Associated Typestype Rep Assoc :: Type -> Type # Methodsfrom :: Assoc -> Rep Assoc x #to :: Rep Assoc x -> Assoc # type Rep Assoc Source # Instance detailsDefined in Expression.Reorder type Rep Assoc = D1 ('MetaData "Assoc" "Expression.Reorder" "reorder-expression-0.1.0.0-inplace" 'False) (C1 ('MetaCons "AssocLeft" 'PrefixI 'False) (U1 :: Type -> Type) :+: (C1 ('MetaCons "AssocRight" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "AssocNone" 'PrefixI 'False) (U1 :: Type -> Type))) The precedence of the operator. Higher precedence binds tighter. data Ambiguity Source # An ambiguity in the operator chain. Constructors  AmbiguityMismatchAssoc Multiple operators with same precedence but different associativities in a chain. AmbiguityAssocNone Multiple non-associative infix operators in a chain e.g. 1 == 2 == 3. #### Instances Instances details  Source # Instance detailsDefined in Expression.Reorder Methods Source # Instance detailsDefined in Expression.Reorder MethodsshowList :: [Ambiguity] -> ShowS # Source # Instance detailsDefined in Expression.Reorder Associated Typestype Rep Ambiguity :: Type -> Type # Methodsto :: Rep Ambiguity x -> Ambiguity # type Rep Ambiguity Source # Instance detailsDefined in Expression.Reorder type Rep Ambiguity = D1 ('MetaData "Ambiguity" "Expression.Reorder" "reorder-expression-0.1.0.0-inplace" 'False) (C1 ('MetaCons "AmbiguityMismatchAssoc" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "AmbiguityAssocNone" 'PrefixI 'False) (U1 :: Type -> Type)) # Example usage First, we implement the SyntaxTree class for our expression type: data Expr = ExprBinary BinOp Expr Expr | ExprPrefix PreOp Expr | ExprTuple [Expr] | ExprInt Int fixityOf :: BinOp -> Fixity precOf :: PreOp -> Precedence instance SyntaxTree Expr String where reorderChildren expr = case expr of ExprBinary op l r -> ExprBinary op <$> reorder l <*> reorder r
ExprPrefix op x -> ExprPrefix op <$> reorder x ExprTuple xs -> ExprTuple <$> traverse reorder xs
_ -> pure expr

structureOf expr = case expr of
ExprBinary binop l r -> NodeInfix (fixityOf binop) l r (ExprBinary binop)
ExprPrefix preop x -> NodePrefix (precOf preop) x (ExprPrefix preop)
_ -> NodeLeaf

makeError err _ = show err

Writing the traversals manually for reorderChildren can be tedious, but can easily be done with other libraries, such as types from generic-lens or gplate from optics.

Then, use reorder to apply the reordering to a tree:

>>> reorder $ExprBinary BinOpMul (ExprBinary BinOpAdd (ExprInt 1) (ExprInt 2)) (ExprInt 3) -- (1 + 2) * 3 ExprBinary BinOpAdd (ExprInt 1) (ExprBinary BinOpMul (ExprInt 2) (ExprInt 3)) -- 1 + (2 * 3)  If your syntax tree is annotated with e.g. source positions, you can rebuild those in the function of Node: (<~>) :: (HasSourcePos a, HasSourcePos b) => a -> b -> SourcePos structureOf (Located _ expr) = case expr of ExprBinary binop l r -> NodeInfix (fixityOf binop) l r (\l' r' -> Located (l' <~> r')$ ExprBinary binop l' r')
ExprPrefix preop x -> NodePrefix (precOf preop) x (\x' -> Located (preop <~> x') \$ ExprPrefix preop x')
_ -> NodeLeaf

Higher arity operations, where at most two child expressions are open, are supported; they can be treated as a prefix, postfix, or infix operator depending on how many open child expressions there are:

structureOf expr = case expr of
ExprTernary x y z -> NodeInfix ternaryFixity x z (\x' z' -> ExprTernary x' y z')   -- x ? y : z
ExprIfThenElse x y z -> NodePrefix ifThenElsePrec z (\z' -> ExprIfThenElse x y z') -- if x then y else z
ExprIndex x y -> NodePostfix indexPrec x (\x' -> ExprIndex x' y)                   -- x[y]
_ -> NodeLeaf