Expression.Reorder

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.

Syntax tree reordering

class SyntaxTree t e | t -> e where

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

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

Gets the structure of a node.

makeError :: Ambiguity -> t -> e

Builds an error for the ambiguous expression given.

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

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

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

Validation applicative, similar to Either but aggregates errors.

Constructors

Success a

Failure e

Instances

Bifunctor Validation

Defined in Expression.Reorder

Methods

bimap :: (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

Functor (Validation e)

Defined in Expression.Reorder

Methods

fmap :: (a -> b) -> Validation e a -> Validation e b

(<$) :: a -> Validation e b -> Validation e a

Semigroup e => Applicative (Validation e)

Defined in Expression.Reorder

Methods

pure :: 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)

Defined 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)

Defined in Expression.Reorder

Methods

showsPrec :: Int -> Validation e a -> ShowS

show :: Validation e a -> String

showList :: [Validation e a] -> ShowS

Generic (Validation e a)

Defined in Expression.Reorder

Associated Types

type Rep (Validation e a) :: Type -> Type

Methods

from :: Validation e a -> Rep (Validation e a) x

to :: Rep (Validation e a) x -> Validation e a

type Rep (Validation e a)

Defined 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

The fixity of an operator.

Constructors

Fixity

Fields

• fixityAssoc :: Assoc
• fixityPrec :: Precedence

Instances

Eq Fixity

Defined in Expression.Reorder

Methods

(==) :: Fixity -> Fixity -> Bool

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

Show Fixity

Defined in Expression.Reorder

Methods

showsPrec :: Int -> Fixity -> ShowS

show :: Fixity -> String

showList :: [Fixity] -> ShowS

Generic Fixity

Defined in Expression.Reorder

Associated Types

type Rep Fixity :: Type -> Type

Methods

from :: Fixity -> Rep Fixity x

to :: Rep Fixity x -> Fixity

type Rep Fixity

Defined 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

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

Eq Assoc

Defined in Expression.Reorder

Methods

(==) :: Assoc -> Assoc -> Bool

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

Show Assoc

Defined in Expression.Reorder

Methods

showsPrec :: Int -> Assoc -> ShowS

show :: Assoc -> String

showList :: [Assoc] -> ShowS

Generic Assoc

Defined in Expression.Reorder

Associated Types

type Rep Assoc :: Type -> Type

Methods

from :: Assoc -> Rep Assoc x

to :: Rep Assoc x -> Assoc

type Rep Assoc

Defined 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)))

type Precedence = Double

The precedence of the operator.

Higher precedence binds tighter.

data Ambiguity

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

Eq Ambiguity

Defined in Expression.Reorder

Methods

(==) :: Ambiguity -> Ambiguity -> Bool

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

Show Ambiguity

Defined in Expression.Reorder

Methods

showsPrec :: Int -> Ambiguity -> ShowS

show :: Ambiguity -> String

showList :: [Ambiguity] -> ShowS

Generic Ambiguity

Defined in Expression.Reorder

Associated Types

type Rep Ambiguity :: Type -> Type

Methods

from :: Ambiguity -> Rep Ambiguity x

to :: Rep Ambiguity x -> Ambiguity

type Rep Ambiguity

Defined 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