===========
Logical Or								[TOC]
===========

For supporting a logical Or we have to go through the same steps as for the
logical not:

- We have to update the grammar (and based on that the parser) and
- define an enum contant for a corresponding expression kind in ``expr.h``
- Support constant folding. In this case by adapting ``constFoldBinary()`` in
  ``expr.c``.
- Adapt functions ``loadExpr()`` and ``condJmpExpr()`` in ``expr.c``
- Adapt function ``printExprNode()`` in ``expr.c``

Compared to before only a few lines of code will be involved. Having
restructured now pays off.


Grammar and Parser Update
=========================
Like in C the logical Or will be a left associative binary operator. In grammar
the production rule for an assigment expression now reads as follows:

---- LATEX ---------------------------------------------------------------------
\begin{array}{rcl}
\text{assignment-expr}
    & = &
    \text{logical-or-expr}\;
    [\;
    \texttt{=}\;
    \text{assignment-expr}\;
    ]\;
    \\
\end{array}
--------------------------------------------------------------------------------

That means it is the first left associative binary operator that now occurs in
the sequence of production rules for left associative binary operators:

---- LATEX ---------------------------------------------------------------------
\begin{array}{rcl}
\text{logical-or-expr}
    & = &
    \text{equality-expr}\;
    \{\;
      \texttt{"||"}\;
      \text{equality-expr}
    \}
    \\
\text{equality-expr}
    & = &
    \text{relational-expr}\;
    \{\;
      (\;
      \texttt{"=="}\; |\; \texttt{"!="}\;
      )\;
      \text{relational-expr}
    \}
    \\
\text{relational-expr}
    & = &
    \text{additive-expr}\;
    \{\;
      (\;
      \texttt{">"}\; |\; \texttt{"<"}\; |\; \texttt{">="}\; |\; \texttt{"<="}\;
      )\;
      \text{additive-expr}
    \}
    \\
\text{additive-expr}
    & = &
    \text{multiplicative-expr}\;
    \{\;
      (\;
      \texttt{"+"}\; |\; \texttt{"-"}\;
      )\;
      \text{multiplicative-expr}
    \}
    \\
\text{multiplicative-expr}
    & = &
    \text{unary-expr}\;
    \{\;
      (\;
      \texttt{"*"}\; |\; \texttt{"/"}\; |\; \texttt{"%"}
      )\;
      \text{unary-expr}
    \}
    \\
\end{array}
--------------------------------------------------------------------------------

Hence, of all left associative binary operators it has the lowest precedence.
And like in C (See __Session 8, Page 4__) we give it the precedence level 4. So
this is the current state of our supported associative binary operators and
their precedence levels:

+---------------+---------------------------------------+---------------+
| Precedence	|	Operators			| Meaning	|
+---------------+---------------------------------------+---------------+
| 13		|	`*` (multiply)			|Multiplicative |
|		|					|		|
|		|	`/` (divide)			|		|
|		|					|		|
|		|	`%` (modulo)			|	        |
+---------------+---------------------------------------+---------------+
| 12		|	`+` (add)			|   Additive    |
|		|					|	        |
|		|	`-` (subtract)			|		|
+---------------+---------------------------------------+---------------+
| 10		|	`<`  (less)			|   Relation    |
|		|					|		|
|		|	`>`  (greater)	     		|		|
|		|					|		|
|		|	`<=` (less equal)		|		|
|		|					|		|
|		|	`>=` (greater equal)		|		|
+---------------+---------------------------------------+---------------+
| 9		|	`==`				| Equality	|
|		|					|		|
|  		|	`!=`				| Inequality	|
+---------------+---------------------------------------+---------------+
| 4		|	`||`				| Logical Or	|
+---------------+---------------------------------------+---------------+

:links: Session 8, Page 4 -> doc:session08/page04

Updating Expression Kinds
~~~~~~~~~~~~~~~~~~~~~~~~~
In ``expr.h`` we define the enum constant ``EK_LOGICAL_OR`` with the group of
binary operators:

---- CODE (type=c) -------------------------------------------------------------
enum ExprKind
{
    EK_BINARY,
    // binary expression
    // ...
    EK_LOGICAL_OR,
    // ...
    EK_BINARY_END,

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

Updating the Parser
~~~~~~~~~~~~~~~~~~~
In ``tokenkind.txt`` change the line with ``VBAR2`` to

---- CODE (type=c) -------------------------------------------------------------
VBAR2		||	4	EK_LOGICAL_OR
--------------------------------------------------------------------------------

That's it!


Constant Folding
================
In ``expr.c`` function ``constFoldBinary()`` now also has to handle the case
that both child node are constant:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
constFoldBinary(const struct Expr *expr)
{
    /* ... as before ...*/

    // handle cases where node can be completely folded
    // NOTE: here we exploit that in our case constants are always unsigned
    uint64_t leftVal = left->primary.literal.uint;
    uint64_t rightVal = right->primary.literal.uint;
    switch (expr->kind) {
	/* ... as before ...*/
	case EK_LOGICAL_OR:
	    return newUnsignedLiteralExpr(leftVal || rightVal);
	/* ... as before ...*/
    }
  
--------------------------------------------------------------------------------

That's it!

Adapting ``loadExpr()``
=======================
Expression nodes of kind ``EK_LOGICAL_OR`` can be handled like any other kind
of logical expression node (i.e. ``EK_LOGICAL_NOT``, ``EK_GREATER``, etc.).
Hence, the code block in the switch statement just gets another case:

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

    switch (expr->kind) {
	/* ... as before ... */

	case EK_LOGICAL_OR:
	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:
            {
		/* handle logical expression nodes */
            }
            return;

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

That's it!

Adapting ``condJmpExpr()``
==========================
This is actually the place were some careful thought is required. Like in C
the right expression in an Or conjunction should only be evaluated if the left
expression was _false_ (__Short-circuit evaluation__).  But it is actually kind
of simple. We just have to consider two examples and make sure it works for
them:

- One example where the jump should take place if the condition is _true_, and
- one example where the jump should take place if the condition is _false_.

From this examples we can derive an implementation by considering flow charts.

:links: Short-circuit evaluation -> https://en.wikipedia.org/wiki/Short-circuit_evaluation

Jump if Condition is True
~~~~~~~~~~~~~~~~~~~~~~~~~
In this case we have to generate for both child nodes a condition jump that
takes place if their condition is true. Both condition jumps for the child nodes
inherit the "true label" from the parent node:

+ Flow chart for the logical Or conjunction:

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

  \PutStatement{0}{code before}
  \PutJump{1}{$C_1 \lor C_2$}
  \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}
  ------------------------------------------------------------------------------

+ Flow chart with child nodes of the logical Or conjunction:

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

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

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

Jump if Condition is False
~~~~~~~~~~~~~~~~~~~~~~~~~~
Here we have to generate a new "true label". This "true label" marks the end of
the generated code block. If the left child evaluates to _true_ the Or
conjunction is false. Hence, for the left child node a conditional jump gets
generated that jumps in this case to the end of the generated code block, i.e.
it jumps to the generated "true label" if its condition is true. The right child
node inherits the "false label" and jumps if its condition is false:


+ Flow chart for the logical Or conjunction:

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


  \PutStatement{0}{code before}
  \PutJump{1}{$C_1 \lor C_2$}
  \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}
  ------------------------------------------------------------------------------

+ Flow chart with child nodes of the logical Or conjunction:

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

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

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

If the jump should take place when the condition is _true_ the "true label" is
used for the recursive call of ``condJmpExpr()`` for the child nodes. But if the
jump should happen if the condition is _false_ we need to generate a new label.
This label is used for the left child node as "true label":

---- 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_OR:
	    {
                const struct Expr *left = expr->binary.left;
                const struct Expr *right = expr->binary.right;
		if (trueLabel) {
		    condJmpExpr(left, dest, trueLabel, 0);
		    condJmpExpr(right, dest, trueLabel, 0);
		} else {
		    trueLabel = genGetLabel();
                    condJmpExpr(left, dest, trueLabel, 0);
                    condJmpExpr(right, dest, 0, falseLabel);
                    genLabelDef(trueLabel);
		}
	    }
	    return;
	/* ... as before ... */
    }
}
--------------------------------------------------------------------------------

But that's it! And a logical AND can be supported in the same fashion.

Adapting ``printExprNode()``
============================
Here we have to handle the new expression kind. The hardest part is two choose
a good name for nodes representing a logical Or. Here the symbol $\lor$ 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_OR:
		fprintf(out, "[ $\\lor$ \n");
		return;
	    default:;
	}
    } else if (expr->kind == EK_UNSIGNED_LITERAL) {
	/* ... as before ... */
    } else if (expr->kind == EK_IDENTIFIER) {
	/* ... as before ... */
    }
    /* ... as before ... */
}
--------------------------------------------------------------------------------

Tests
=====
In the test we should check whether the new expression kind can be used in
control statements (for testing ``condJmpExpr()`` directly) but also in
assignments (for testing if ``loadExpr()`` makes proper use of
``condJmpExpr()``). And we also should test constant folding. So a simple test
would be:

---- CODE (file=session26/git/abc_step4/examples/logical_or_simple.abc) --------
x = 0 || 1;
$< x;

x = 1 || 0;
$< x;

x = 0 || 0;
$< x;

$> x;
$> y;

z = x || y;
$< z;
z = !(x || y);
$< z;
if (x < y || x > y) {
    $< 42;
} else {
    $< 13;
}
--------------------------------------------------------------------------------

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

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

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

---- SHELL (path=session26/git/abc_step4/examples/) ----------------------------
make logical_or_simple
echo "0 5" | ./logical_or_simple
echo "5 5" | ./logical_or_simple
echo "5 0" | ./logical_or_simple
echo "0 0" | ./logical_or_simple
--------------------------------------------------------------------------------

Here another test with multiple logical Or conjunctions:

---- CODE (file=session26/git/abc_step4/examples/logical_or.abc) ---------------
$> a;
$> b;
$> c;
$> d;

x = a || b || c || d;
$< x;
x = !(a || b || c || d);
$< x;
x = !a || !b || !c || !d;
$< x;
--------------------------------------------------------------------------------

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

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

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


And here a test run:

---- SHELL (path=session26/git/abc_step4/examples/) ----------------------------
make logical_or
echo "1 2 3 4" | ./logical_or
echo "0 2 3 4" | ./logical_or
echo "0 0 3 4" | ./logical_or
echo "0 0 0 4" | ./logical_or
echo "0 0 0 0" | ./logical_or
--------------------------------------------------------------------------------

Here some test for short-circuit evaluation for the logical Or:

---- CODE (file=session26/git/abc_step4/examples/logical_or_sce.abc) ----------
$> a;

x = a || (a = a + 1);
$< x;
$< a;
--------------------------------------------------------------------------------

Only when ``a`` is zero it gets incremented:

---- SHELL (path=session26/git/abc_step4/examples/) ----------------------------
make logical_or_sce
echo "1" | ./logical_or_sce
echo "0" | ./logical_or_sce
--------------------------------------------------------------------------------

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

Here the generated __logical-or-sce.pdf__ for the expression trees in the
program.


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