===========
Logical Not								[TOC]
===========

For supporting a logical not we have to change the grammar for a unary
expression. Again we steel shamelessly from C:

---- LATEX ---------------------------------------------------------------------
\begin{array}{rcl}
\text{unary-expr}
    & = &
    \text{primary-expr}\;
    |\;
    (\; \texttt{"+"}\; |\; \texttt{"-"}\; |\; \texttt{"!"}\; )\;
    \text{unary-expr}
    \\
\end{array}
--------------------------------------------------------------------------------

Parsing
=======

For unary expressions we have to patch the parser manually, and it will also
require another expression kind ('``EK_LOGICAL_NOT``'):

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
parseUnaryExpr(void)
{
    if (token.kind == PLUS || token.kind == MINUS || token.kind == NOT) {
        enum TokenKind op = token.kind;
        getToken();
        const struct Expr *expr = parsePrimaryExpr();
        if (!expr) {
            expectedError("non-empty expression");
        }
        if (op == PLUS) {
            return newUnaryExpr(EK_UNARY_PLUS, expr);
        } else if (op == MINUS) {
            return newUnaryExpr(EK_UNARY_MINUS, expr);
        } else if (op == NOT) {
            return newUnaryExpr(EK_LOGICAL_NOT, expr);
        } else {
            assert(0);
        }
    }
    return parsePrimaryExpr();
}
--------------------------------------------------------------------------------

Following the hacker's approach we just extend ``enum ExprKind`` for the
constant ``EK_LOGICAL_NOT``. Of course in the group for unary operators:

---- CODE (type=c) -------------------------------------------------------------
enum ExprKind
{
    /* .. as before ... */

    EK_UNARY = EK_BINARY_END,
    // unary expression
    EK_UNARY_MINUS = EK_UNARY,
    EK_UNARY_PLUS,
    EK_LOGICAL_NOT,
    EK_UNARY_END,

    /* .. as before ... */
};
--------------------------------------------------------------------------------

We now can test if the parser accepts expressions with a logical not. Of course
we are well aware that in the current state no correct code can be generated.
But if we did things right we should get an assertion failure (and not some
segmentation fault):

---- SHELL (path=session26/git/abc_step2,hide) ---------------------------------
make
--------------------------------------------------------------------------------

---- SHELL (path=session26/git/abc_step2) --------------------------------------
echo '!x;' | ./xtest_abc
--------------------------------------------------------------------------------

Code Generation
===============
For generating code only ``condJmpExpr()``, ``loadExpr()`` and
``constFoldUnary()`` need to be modified. Here the complete code of _expr.c_ in
advance

:import: session26/git/abc_step3/expr.c [fold]

Modifying ``condJmpExpr()``
---------------------------
In ``condJmpExpr()`` we have to handle the new case of an expression kind
``EK_LOGICAL_NOT``. This is actually simple. If the child not is _true_ the
value of the node is _false_, and vice versa. This can be realized with a
simple recursive call where ``condJmpExpr()`` receives the child not and the
labels are flipped:

---- CODE (type=c) -------------------------------------------------------------
void
condJmpExpr(const struct Expr *expr, GenReg dest, const char *trueLabel,
	    const char *falseLabel)
{
    /* ... as before ... */

    switch (expr->kind) {
	/* ... as before ... */
	case EK_LOGICAL_NOT:
	    condJmpExpr(expr->unary, dest, falseLabel, trueLabel);
	    return;
	/* ... as before ... */
    }
}
--------------------------------------------------------------------------------

Modifying ``loadExpr()``
------------------------
Here we actually can reuse the implementation for handling equality ('``==``'),
inequality ('``!=``') and relational ('``>``', '``>=``', '``<``', '``<=``')
expressions. However, it will be convenient to reorganize the structure of
``loadExpr()``. So far we use the pattern where we distinguish between binary,
unary and primary expression kinds. Hence, we have this structure

---- CODE (type=c) -------------------------------------------------------------
void
loadExpr(const struct Expr *expr, GenReg dest)
{
    /* ... */

    if (expr->kind >= EK_BINARY && expr->kind < EK_BINARY_END) {
	/* code for binary expression */
    } else if (expr->kind >= EK_UNARY && expr->kind < EK_UNARY_END) {
	/* code for unary expression */
    } else if (expr->kind == EK_IDENTIFIER) {
	/* code for identifiers */
    } else if (expr->kind == EK_UNSIGNED_LITERAL) {
	/* code for unsigned integer literals */
    }
}
--------------------------------------------------------------------------------

It will be more convenient to reorganize ``loadExpr()`` such that it has the
same structure as ``condJmpExpr()`` where we have a single switch statement
for handling all expression kinds:

---- CODE (type=c) -------------------------------------------------------------
void
loadExpr(const struct Expr *expr, GenReg dest)
{
    /* ... as before ... */

    switch (expr->kind) {
	case EK_ADD:
	case EK_SUB:
	case EK_MUL:
	case EK_DIV:
	case EK_MOD:
	    {
		const struct Expr *left = expr->binary.left;
		const struct Expr *right = expr->binary.right;

		/* code for left associative binary operators */
	    }
	    return;
	case EK_ASSIGN:
	    {
		const struct Expr *left = expr->binary.left;
		const struct Expr *right = expr->binary.right;

		/* code for assignment operator */
	    }
	    return;
	case EK_LOGICAL_NOT:
	case EK_GREATER:
	case EK_GREATER_EQUAL:
	case EK_LESS:
	case EK_LESS_EQUAL:
        case EK_EQUAL:
        case EK_NOT_EQUAL:
            {
		/* code for logical operators */
            }
            return;
	case EK_UNARY_MINUS:
		/* code for unary minus */
	    return;
	case EK_UNARY_PLUS:
		/* code for unary plus */
	    return;
	case EK_IDENTIFIER:
		/* code for identifier */
	    return;
	case EK_UNSIGNED_LITERAL:
		/* code for unsigned integers */
	    return;
	default:
	    ;
    }
    /* ... as before ... */
}

--------------------------------------------------------------------------------


Variant 1 (Jump if true)
~~~~~~~~~~~~~~~~~~~~~~~~
For the logical operators we used in the last session this code snippet (and we
can continue to do so):

---- CODE (type=c) -------------------------------------------------------------
{
    const char *elseLabel = genGetLabel();
    const char *endLabel = genGetLabel();

    condJmpExpr(expr, dest, elseLabel, 0);
    genLoadUInt(0, dest);
    genJmp(endLabel);
    genLabelDef(elseLabel);
    genLoadUInt(1, dest);
    genLabelDef(endLabel);
}
--------------------------------------------------------------------------------

The flowcharts below describes how ``condJmpExpr()`` handles here a logical not
by flipping the labels.

+ ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{flowchart.tex}
  \SetMargin{1}{4}{0}{5.1}
  \renewcommand\BoxWidth { 5 }

  \PutStatement{0}{code before}
  \PutJump{1}{$\lnot C$}
  \PutStatement{2}{load 0 into \%dest}
  \PutJump{3}{}
  \PutStatement{4}{load 1 into \%dest}
  \PutStatement{5}{code after}

  \AddPath{0}{1}
  \AddPath{1}{2}
  \AddCondJumpPath{1}{4}
  \AddPath{2}{3}
  \AddPath{4}{5}
  \AddJumpPathLeft{3}{5}
  \end{tikzpicture}
  ------------------------------------------------------------------------------

+ ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{flowchart.tex}
  \SetMargin{1}{4}{0}{5.1}
  \renewcommand\BoxWidth { 5 }

  \PutStatement{0}{code before}
  \PutJump{1}{$C$}
  \PutStatement{2}{load 0 into \%dest}
  \PutJump{3}{}
  \PutStatement{4}{load 1 into \%dest}
  \PutStatement{5}{code after}

  \AddPath{0}{1}
  \AddPath{1}{2}
  \AddCondJumpPathAlt{1}{4}
  \AddPath{2}{3}
  \AddPath{4}{5}
  \AddJumpPathLeft{3}{5}

  \end{tikzpicture}
  ------------------------------------------------------------------------------

Variant 2 (Jump if false)
~~~~~~~~~~~~~~~~~~~~~~~~~
As an alternative for the logical operators also this code block could be used

---- CODE (type=c) -------------------------------------------------------------
{
    const char *elseLabel = genGetLabel();
    const char *endLabel = genGetLabel();

    condJmpExpr(expr, dest, 0, elseLabel);
    genLoadUInt(1, dest);
    genJmp(endLabel);
    genLabelDef(elseLabel);
    genLoadUInt(0, dest);
    genLabelDef(endLabel);
}
--------------------------------------------------------------------------------

Again, the flowcharts below describes how ``condJmpExpr()`` handles here a
logical not by flipping the labels.


+ ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{flowchart.tex}
  \SetMargin{1}{4}{0}{5.1}
  \renewcommand\BoxWidth { 5 }

  \PutStatement{0}{code before}
  \PutJump{1}{$\lnot C$}
  \PutStatement{2}{load 1 into \%dest}
  \PutJump{3}{}
  \PutStatement{4}{load 0 into \%dest}
  \PutStatement{5}{code after}

  \AddPath{0}{1}
  \AddPath{1}{2}
  \AddCondJumpPathAlt{1}{4}
  \AddPath{2}{3}
  \AddPath{4}{5}
  \AddJumpPathLeft{3}{5}
  \end{tikzpicture}
  ------------------------------------------------------------------------------

+ ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{flowchart.tex}
  \SetMargin{1}{4}{0}{5.1}
  \renewcommand\BoxWidth { 5 }

  \PutStatement{0}{code before}
  \PutJump{1}{$C$}
  \PutStatement{2}{load 1 into \%dest}
  \PutJump{3}{}
  \PutStatement{4}{load 0 into \%dest}
  \PutStatement{5}{code after}

  \AddPath{0}{1}
  \AddPath{1}{2}
  \AddCondJumpPath{1}{4}
  \AddPath{2}{3}
  \AddPath{4}{5}
  \AddJumpPathLeft{3}{5}
  \end{tikzpicture}
  ------------------------------------------------------------------------------

Modifying ``constFoldUnary()``
------------------------------
We just have to add a new case in the switch statement:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
constFoldUnary(const struct Expr *expr)
{
    /* ... as before ... */
    switch (expr->kind) {
	/* ... as before ... */
	case EK_LOGICAL_NOT:
	    return newUnsignedLiteralExpr(!unary->primary.literal.uint);
	/* ... as before ... */
    }
}
--------------------------------------------------------------------------------

Adapting ``printExprNode()``
============================
For generating Latex code representing expression trees we have to handle the
new expression kind in ``printExprNode()``. Here the symbol $\lnot$ is used:

---- CODE (type=c) -------------------------------------------------------------
static void
printExprNode(const struct Expr *expr, size_t indent, FILE *out)
{
    /* ... as before ... */

    if (expr->kind >= EK_BINARY && expr->kind < EK_UNARY_END) {
	switch (expr->kind) {
	    /* ... as before ... */
	    case EK_LOGICAL_NOT:
		fprintf(out, "[ $\\lnot$ \n");
		return;
	    default:;
	}
    } else if (expr->kind == EK_UNSIGNED_LITERAL) {
	/* ... as before ... */
    } else if (expr->kind == EK_IDENTIFIER) {
	/* ... as before ... */
    }
    /* ... as before ... */
}
--------------------------------------------------------------------------------


Some Test
=========
Here a simple test program:

---- CODE (file=session26/git/abc_step3/examples/logical_not.abc) --------------
x = !5;
$< x;
x = !0;
$< x;
x = 5;
$< !x;
x = 0;
$< !x;
--------------------------------------------------------------------------------

---- SHELL (path=session26/git/abc_step3,hide) ---------------------------------
make
--------------------------------------------------------------------------------

---- SHELL (path=session26/git/abc_step3, hide) --------------------------------
./xtest_abc foo.s logical-not.tex < examples/logical_not.abc
lualatex logical-not.tex
cp logical-not.pdf /home/www/htdocs/numerik/hpc/ss22/hpc0/session26/
--------------------------------------------------------------------------------

Here the generated __logical-not.pdf__ for the expression trees in the
program.  And here a test run:

:links: logical-not.pdf -> https://www.mathematik.uni-ulm.de/numerik/hpc/ss22/hpc0/session26/logical-not.pdf


---- SHELL (path=session26/git/abc_step3/examples) -----------------------------
make logical_not
./logical_not
--------------------------------------------------------------------------------