path: root/ast_to_hir.cpp

/*
 * Copyright © 2010 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

/**
 * \file ast_to_hir.c
 * Convert abstract syntax to to high-level intermediate reprensentation (HIR).
 *
 * During the conversion to HIR, the majority of the symantic checking is
 * preformed on the program.  This includes:
 *
 *    * Symbol table management
 *    * Type checking
 *    * Function binding
 *
 * The majority of this work could be done during parsing, and the parser could
 * probably generate HIR directly.  However, this results in frequent changes
 * to the parser code.  Since we do not assume that every system this complier
 * is built on will have Flex and Bison installed, we have to store the code
 * generated by these tools in our version control system.  In other parts of
 * the system we've seen problems where a parser was changed but the generated
 * code was not committed, merge conflicts where created because two developers
 * had slightly different versions of Bison installed, etc.
 *
 * I have also noticed that running Bison generated parsers in GDB is very
 * irritating.  When you get a segfault on '$$ = $1->foo', you can't very
 * well 'print $1' in GDB.
 *
 * As a result, my preference is to put as little C code as possible in the
 * parser (and lexer) sources.
 */
#include <stdio.h>
#include "main/imports.h"
#include "glsl_symbol_table.h"
#include "glsl_parser_extras.h"
#include "ast.h"
#include "glsl_types.h"
#include "ir.h"

void
_mesa_ast_to_hir(exec_list *instructions, struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;

   _mesa_glsl_initialize_variables(instructions, state);
   _mesa_glsl_initialize_constructors(instructions, state);
   _mesa_glsl_initialize_functions(instructions, state);

   state->current_function = NULL;

   foreach (ptr, & state->translation_unit) {
      ((ast_node *)ptr)->hir(instructions, state);
   }
}


/**
 * If a conversion is available, convert one operand to a different type
 *
 * The \c from \c ir_rvalue is converted "in place".
 *
 * \param to     Type that the operand it to be converted to
 * \param from   Operand that is being converted
 * \param state  GLSL compiler state
 *
 * \return
 * If a conversion is possible (or unnecessary), \c true is returned.
 * Otherwise \c false is returned.
 */
static bool
apply_implicit_conversion(const glsl_type *to, ir_rvalue * &from,
			  struct _mesa_glsl_parse_state *state)
{
   if (to->base_type == from->type->base_type)
      return true;

   /* This conversion was added in GLSL 1.20.  If the compilation mode is
    * GLSL 1.10, the conversion is skipped.
    */
   if (state->language_version < 120)
      return false;

   /* From page 27 (page 33 of the PDF) of the GLSL 1.50 spec:
    *
    *    "There are no implicit array or structure conversions. For
    *    example, an array of int cannot be implicitly converted to an
    *    array of float. There are no implicit conversions between
    *    signed and unsigned integers."
    */
   /* FINISHME: The above comment is partially a lie.  There is int/uint
    * FINISHME: conversion for immediate constants.
    */
   if (!to->is_float() || !from->type->is_numeric())
      return false;

   switch (from->type->base_type) {
   case GLSL_TYPE_INT:
      from = new ir_expression(ir_unop_i2f, to, from, NULL);
      break;
   case GLSL_TYPE_UINT:
      from = new ir_expression(ir_unop_u2f, to, from, NULL);
      break;
   case GLSL_TYPE_BOOL:
      assert(!"FINISHME: Convert bool to float.");
   default:
      assert(0);
   }

   return true;
}


static const struct glsl_type *
arithmetic_result_type(ir_rvalue * &value_a, ir_rvalue * &value_b,
		       bool multiply,
		       struct _mesa_glsl_parse_state *state)
{
   const glsl_type *const type_a = value_a->type;
   const glsl_type *const type_b = value_b->type;

   /* From GLSL 1.50 spec, page 56:
    *
    *    "The arithmetic binary operators add (+), subtract (-),
    *    multiply (*), and divide (/) operate on integer and
    *    floating-point scalars, vectors, and matrices."
    */
   if (!type_a->is_numeric() || !type_b->is_numeric()) {
      return glsl_type::error_type;
   }


   /*    "If one operand is floating-point based and the other is
    *    not, then the conversions from Section 4.1.10 "Implicit
    *    Conversions" are applied to the non-floating-point-based operand."
    */
   if (!apply_implicit_conversion(type_a, value_b, state)
       && !apply_implicit_conversion(type_b, value_a, state)) {
      return glsl_type::error_type;
   }
      
   /*    "If the operands are integer types, they must both be signed or
    *    both be unsigned."
    *
    * From this rule and the preceeding conversion it can be inferred that
    * both types must be GLSL_TYPE_FLOAT, or GLSL_TYPE_UINT, or GLSL_TYPE_INT.
    * The is_numeric check above already filtered out the case where either
    * type is not one of these, so now the base types need only be tested for
    * equality.
    */
   if (type_a->base_type != type_b->base_type) {
      return glsl_type::error_type;
   }

   /*    "All arithmetic binary operators result in the same fundamental type
    *    (signed integer, unsigned integer, or floating-point) as the
    *    operands they operate on, after operand type conversion. After
    *    conversion, the following cases are valid
    *
    *    * The two operands are scalars. In this case the operation is
    *      applied, resulting in a scalar."
    */
   if (type_a->is_scalar() && type_b->is_scalar())
      return type_a;

   /*   "* One operand is a scalar, and the other is a vector or matrix.
    *      In this case, the scalar operation is applied independently to each
    *      component of the vector or matrix, resulting in the same size
    *      vector or matrix."
    */
   if (type_a->is_scalar()) {
      if (!type_b->is_scalar())
	 return type_b;
   } else if (type_b->is_scalar()) {
      return type_a;
   }

   /* All of the combinations of <scalar, scalar>, <vector, scalar>,
    * <scalar, vector>, <scalar, matrix>, and <matrix, scalar> have been
    * handled.
    */
   assert(!type_a->is_scalar());
   assert(!type_b->is_scalar());

   /*   "* The two operands are vectors of the same size. In this case, the
    *      operation is done component-wise resulting in the same size
    *      vector."
    */
   if (type_a->is_vector() && type_b->is_vector()) {
      return (type_a == type_b) ? type_a : glsl_type::error_type;
   }

   /* All of the combinations of <scalar, scalar>, <vector, scalar>,
    * <scalar, vector>, <scalar, matrix>, <matrix, scalar>, and
    * <vector, vector> have been handled.  At least one of the operands must
    * be matrix.  Further, since there are no integer matrix types, the base
    * type of both operands must be float.
    */
   assert(type_a->is_matrix() || type_b->is_matrix());
   assert(type_a->base_type == GLSL_TYPE_FLOAT);
   assert(type_b->base_type == GLSL_TYPE_FLOAT);

   /*   "* The operator is add (+), subtract (-), or divide (/), and the
    *      operands are matrices with the same number of rows and the same
    *      number of columns. In this case, the operation is done component-
    *      wise resulting in the same size matrix."
    *    * The operator is multiply (*), where both operands are matrices or
    *      one operand is a vector and the other a matrix. A right vector
    *      operand is treated as a column vector and a left vector operand as a
    *      row vector. In all these cases, it is required that the number of
    *      columns of the left operand is equal to the number of rows of the
    *      right operand. Then, the multiply (*) operation does a linear
    *      algebraic multiply, yielding an object that has the same number of
    *      rows as the left operand and the same number of columns as the right
    *      operand. Section 5.10 "Vector and Matrix Operations" explains in
    *      more detail how vectors and matrices are operated on."
    */
   if (! multiply) {
      return (type_a == type_b) ? type_a : glsl_type::error_type;
   } else {
      if (type_a->is_matrix() && type_b->is_matrix()) {
	 /* Matrix multiply.  The columns of A must match the rows of B.  Given
	  * the other previously tested constraints, this means the vector type
	  * of a row from A must be the same as the vector type of a column from
	  * B.
	  */
	 if (type_a->row_type() == type_b->column_type()) {
	    /* The resulting matrix has the number of columns of matrix B and
	     * the number of rows of matrix A.  We get the row count of A by
	     * looking at the size of a vector that makes up a column.  The
	     * transpose (size of a row) is done for B.
	     */
	    return
	       glsl_type::get_instance(type_a->base_type,
				       type_a->column_type()->vector_elements,
				       type_b->row_type()->vector_elements);
	 }
      } else if (type_a->is_matrix()) {
	 /* A is a matrix and B is a column vector.  Columns of A must match
	  * rows of B.  Given the other previously tested constraints, this
	  * means the vector type of a row from A must be the same as the
	  * vector the type of B.
	  */
	 if (type_a->row_type() == type_b)
	    return type_b;
      } else {
	 assert(type_b->is_matrix());

	 /* A is a row vector and B is a matrix.  Columns of A must match rows
	  * of B.  Given the other previously tested constraints, this means
	  * the type of A must be the same as the vector type of a column from
	  * B.
	  */
	 if (type_a == type_b->column_type())
	    return type_a;
      }
   }


   /*    "All other cases are illegal."
    */
   return glsl_type::error_type;
}


static const struct glsl_type *
unary_arithmetic_result_type(const struct glsl_type *type)
{
   /* From GLSL 1.50 spec, page 57:
    *
    *    "The arithmetic unary operators negate (-), post- and pre-increment
    *     and decrement (-- and ++) operate on integer or floating-point
    *     values (including vectors and matrices). All unary operators work
    *     component-wise on their operands. These result with the same type
    *     they operated on."
    */
   if (!type->is_numeric())
      return glsl_type::error_type;

   return type;
}


static const struct glsl_type *
modulus_result_type(const struct glsl_type *type_a,
		    const struct glsl_type *type_b)
{
   /* From GLSL 1.50 spec, page 56:
    *    "The operator modulus (%) operates on signed or unsigned integers or
    *    integer vectors. The operand types must both be signed or both be
    *    unsigned."
    */
   if (!type_a->is_integer() || !type_b->is_integer()
       || (type_a->base_type != type_b->base_type)) {
      return glsl_type::error_type;
   }

   /*    "The operands cannot be vectors of differing size. If one operand is
    *    a scalar and the other vector, then the scalar is applied component-
    *    wise to the vector, resulting in the same type as the vector. If both
    *    are vectors of the same size, the result is computed component-wise."
    */
   if (type_a->is_vector()) {
      if (!type_b->is_vector()
	  || (type_a->vector_elements == type_b->vector_elements))
	 return type_a;
   } else
      return type_b;

   /*    "The operator modulus (%) is not defined for any other data types
    *    (non-integer types)."
    */
   return glsl_type::error_type;
}


static const struct glsl_type *
relational_result_type(ir_rvalue * &value_a, ir_rvalue * &value_b,
		       struct _mesa_glsl_parse_state *state)
{
   const glsl_type *const type_a = value_a->type;
   const glsl_type *const type_b = value_b->type;

   /* From GLSL 1.50 spec, page 56:
    *    "The relational operators greater than (>), less than (<), greater
    *    than or equal (>=), and less than or equal (<=) operate only on
    *    scalar integer and scalar floating-point expressions."
    */
   if (!type_a->is_numeric()
       || !type_b->is_numeric()
       || !type_a->is_scalar()
       || !type_b->is_scalar())
      return glsl_type::error_type;

   /*    "Either the operands' types must match, or the conversions from
    *    Section 4.1.10 "Implicit Conversions" will be applied to the integer
    *    operand, after which the types must match."
    */
   if (!apply_implicit_conversion(type_a, value_b, state)
       && !apply_implicit_conversion(type_b, value_a, state)) {
      return glsl_type::error_type;
   }

   if (type_a->base_type != type_b->base_type)
      return glsl_type::error_type;

   /*    "The result is scalar Boolean."
    */
   return glsl_type::bool_type;
}


/**
 * Validates that a value can be assigned to a location with a specified type
 *
 * Validates that \c rhs can be assigned to some location.  If the types are
 * not an exact match but an automatic conversion is possible, \c rhs will be
 * converted.
 *
 * \return
 * \c NULL if \c rhs cannot be assigned to a location with type \c lhs_type.
 * Otherwise the actual RHS to be assigned will be returned.  This may be
 * \c rhs, or it may be \c rhs after some type conversion.
 *
 * \note
 * In addition to being used for assignments, this function is used to
 * type-check return values.
 */
ir_rvalue *
validate_assignment(const glsl_type *lhs_type, ir_rvalue *rhs)
{
   const glsl_type *const rhs_type = rhs->type;

   /* If there is already some error in the RHS, just return it.  Anything
    * else will lead to an avalanche of error message back to the user.
    */
   if (rhs_type->is_error())
      return rhs;

   /* FINISHME: For GLSL 1.10, check that the types are not arrays. */

   /* If the types are identical, the assignment can trivially proceed.
    */
   if (rhs_type == lhs_type)
      return rhs;

   /* FINISHME: Check for and apply automatic conversions. */
   return NULL;
}

ir_rvalue *
do_assignment(exec_list *instructions, struct _mesa_glsl_parse_state *state,
	      ir_rvalue *lhs, ir_rvalue *rhs,
	      YYLTYPE lhs_loc)
{
   bool error_emitted = (lhs->type->is_error() || rhs->type->is_error());

   if (!error_emitted) {
      /* FINISHME: This does not handle 'foo.bar.a.b.c[5].d = 5' */
      if (!lhs->is_lvalue()) {
	 _mesa_glsl_error(& lhs_loc, state, "non-lvalue in assignment");
	 error_emitted = true;
      }
   }

   ir_rvalue *new_rhs = validate_assignment(lhs->type, rhs);
   if (new_rhs == NULL) {
      _mesa_glsl_error(& lhs_loc, state, "type mismatch");
   } else {
      rhs = new_rhs;
   }

   ir_instruction *tmp = new ir_assignment(lhs, rhs, NULL);
   instructions->push_tail(tmp);

   return rhs;
}


/**
 * Generate a new temporary and add its declaration to the instruction stream
 */
static ir_variable *
generate_temporary(const glsl_type *type, exec_list *instructions,
		   struct _mesa_glsl_parse_state *state)
{
   char *name = (char *) malloc(sizeof(char) * 13);

   snprintf(name, 13, "tmp_%08X", state->temp_index);
   state->temp_index++;

   ir_variable *const var = new ir_variable(type, name);
   instructions->push_tail(var);

   return var;
}


static ir_rvalue *
get_lvalue_copy(exec_list *instructions, struct _mesa_glsl_parse_state *state,
		ir_rvalue *lvalue, YYLTYPE loc)
{
   ir_variable *var;
   ir_rvalue *var_deref;

   /* FINISHME: Give unique names to the temporaries. */
   var = new ir_variable(lvalue->type, "_internal_tmp");
   var->mode = ir_var_auto;

   var_deref = new ir_dereference(var);
   do_assignment(instructions, state, var_deref, lvalue, loc);

   /* Once we've created this temporary, mark it read only so it's no
    * longer considered an lvalue.
    */
   var->read_only = true;

   return var_deref;
}


ir_rvalue *
ast_node::hir(exec_list *instructions,
	      struct _mesa_glsl_parse_state *state)
{
   (void) instructions;
   (void) state;

   return NULL;
}


ir_rvalue *
ast_expression::hir(exec_list *instructions,
		    struct _mesa_glsl_parse_state *state)
{
   static const int operations[AST_NUM_OPERATORS] = {
      -1,               /* ast_assign doesn't convert to ir_expression. */
      -1,               /* ast_plus doesn't convert to ir_expression. */
      ir_unop_neg,
      ir_binop_add,
      ir_binop_sub,
      ir_binop_mul,
      ir_binop_div,
      ir_binop_mod,
      ir_binop_lshift,
      ir_binop_rshift,
      ir_binop_less,
      ir_binop_greater,
      ir_binop_lequal,
      ir_binop_gequal,
      ir_binop_equal,
      ir_binop_nequal,
      ir_binop_bit_and,
      ir_binop_bit_xor,
      ir_binop_bit_or,
      ir_unop_bit_not,
      ir_binop_logic_and,
      ir_binop_logic_xor,
      ir_binop_logic_or,
      ir_unop_logic_not,

      /* Note: The following block of expression types actually convert
       * to multiple IR instructions.
       */
      ir_binop_mul,     /* ast_mul_assign */
      ir_binop_div,     /* ast_div_assign */
      ir_binop_mod,     /* ast_mod_assign */
      ir_binop_add,     /* ast_add_assign */
      ir_binop_sub,     /* ast_sub_assign */
      ir_binop_lshift,  /* ast_ls_assign */
      ir_binop_rshift,  /* ast_rs_assign */
      ir_binop_bit_and, /* ast_and_assign */
      ir_binop_bit_xor, /* ast_xor_assign */
      ir_binop_bit_or,  /* ast_or_assign */

      -1,               /* ast_conditional doesn't convert to ir_expression. */
      ir_binop_add,     /* ast_pre_inc. */
      ir_binop_sub,     /* ast_pre_dec. */
      ir_binop_add,     /* ast_post_inc. */
      ir_binop_sub,     /* ast_post_dec. */
      -1,               /* ast_field_selection doesn't conv to ir_expression. */
      -1,               /* ast_array_index doesn't convert to ir_expression. */
      -1,               /* ast_function_call doesn't conv to ir_expression. */
      -1,               /* ast_identifier doesn't convert to ir_expression. */
      -1,               /* ast_int_constant doesn't convert to ir_expression. */
      -1,               /* ast_uint_constant doesn't conv to ir_expression. */
      -1,               /* ast_float_constant doesn't conv to ir_expression. */
      -1,               /* ast_bool_constant doesn't conv to ir_expression. */
      -1,               /* ast_sequence doesn't convert to ir_expression. */
   };
   ir_rvalue *result = NULL;
   ir_rvalue *op[2];
   struct simple_node op_list;
   const struct glsl_type *type = glsl_type::error_type;
   bool error_emitted = false;
   YYLTYPE loc;

   loc = this->get_location();
   make_empty_list(& op_list);

   switch (this->oper) {
   case ast_assign: {
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      result = do_assignment(instructions, state, op[0], op[1],
			     this->subexpressions[0]->get_location());
      error_emitted = result->type->is_error();
      type = result->type;
      break;
   }

   case ast_plus:
      op[0] = this->subexpressions[0]->hir(instructions, state);

      error_emitted = op[0]->type->is_error();
      if (type->is_error())
	 op[0]->type = type;

      result = op[0];
      break;

   case ast_neg:
      op[0] = this->subexpressions[0]->hir(instructions, state);

      type = unary_arithmetic_result_type(op[0]->type);

      error_emitted = op[0]->type->is_error();

      result = new ir_expression(operations[this->oper], type,
				 op[0], NULL);
      break;

   case ast_add:
   case ast_sub:
   case ast_mul:
   case ast_div:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      type = arithmetic_result_type(op[0], op[1],
				    (this->oper == ast_mul),
				    state);

      result = new ir_expression(operations[this->oper], type,
				 op[0], op[1]);
      break;

   case ast_mod:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = op[0]->type->is_error() || op[1]->type->is_error();

      type = modulus_result_type(op[0]->type, op[1]->type);

      assert(operations[this->oper] == ir_binop_mod);

      result = new ir_expression(operations[this->oper], type,
				 op[0], op[1]);
      break;

   case ast_lshift:
   case ast_rshift:
      /* FINISHME: Implement bit-shift operators. */
      break;

   case ast_less:
   case ast_greater:
   case ast_lequal:
   case ast_gequal:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = op[0]->type->is_error() || op[1]->type->is_error();

      type = relational_result_type(op[0], op[1], state);

      /* The relational operators must either generate an error or result
       * in a scalar boolean.  See page 57 of the GLSL 1.50 spec.
       */
      assert(type->is_error()
	     || ((type->base_type == GLSL_TYPE_BOOL)
		 && type->is_scalar()));

      result = new ir_expression(operations[this->oper], type,
				 op[0], op[1]);
      break;

   case ast_nequal:
   case ast_equal:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      /* From page 58 (page 64 of the PDF) of the GLSL 1.50 spec:
       *
       *    "The equality operators equal (==), and not equal (!=)
       *    operate on all types. They result in a scalar Boolean. If
       *    the operand types do not match, then there must be a
       *    conversion from Section 4.1.10 "Implicit Conversions"
       *    applied to one operand that can make them match, in which
       *    case this conversion is done."
       */
      if ((!apply_implicit_conversion(op[0]->type, op[1], state)
	   && !apply_implicit_conversion(op[1]->type, op[0], state))
	  || (op[0]->type != op[1]->type)) {
	 _mesa_glsl_error(& loc, state, "operands of `%s' must have the same "
			  "type", (this->oper == ast_equal) ? "==" : "!=");
	 error_emitted = true;
      }

      result = new ir_expression(operations[this->oper], glsl_type::bool_type,
				 op[0], op[1]);
      type = glsl_type::bool_type;

      assert(result->type == glsl_type::bool_type);
      break;

   case ast_bit_and:
   case ast_bit_xor:
   case ast_bit_or:
   case ast_bit_not:
      /* FINISHME: Implement bit-wise operators. */
      break;

   case ast_logic_and:
   case ast_logic_xor:
   case ast_logic_or:
   case ast_logic_not:
      /* FINISHME: Implement logical operators. */
      break;

   case ast_mul_assign:
   case ast_div_assign:
   case ast_add_assign:
   case ast_sub_assign: {
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      type = arithmetic_result_type(op[0], op[1],
				    (this->oper == ast_mul_assign),
				    state);

      ir_rvalue *temp_rhs = new ir_expression(operations[this->oper], type,
				              op[0], op[1]);

      result = do_assignment(instructions, state, op[0], temp_rhs,
			     this->subexpressions[0]->get_location());
      type = result->type;
      error_emitted = (op[0]->type->is_error());

      /* GLSL 1.10 does not allow array assignment.  However, we don't have to
       * explicitly test for this because none of the binary expression
       * operators allow array operands either.
       */

      break;
   }

   case ast_mod_assign: {
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = op[0]->type->is_error() || op[1]->type->is_error();

      type = modulus_result_type(op[0]->type, op[1]->type);

      assert(operations[this->oper] == ir_binop_mod);

      struct ir_rvalue *temp_rhs;
      temp_rhs = new ir_expression(operations[this->oper], type,
				   op[0], op[1]);

      result = do_assignment(instructions, state, op[0], temp_rhs,
			     this->subexpressions[0]->get_location());
      type = result->type;
      error_emitted = op[0]->type->is_error();
      break;
   }

   case ast_ls_assign:
   case ast_rs_assign:
      break;

   case ast_and_assign:
   case ast_xor_assign:
   case ast_or_assign:
      break;

   case ast_conditional: {
      op[0] = this->subexpressions[0]->hir(instructions, state);

      /* From page 59 (page 65 of the PDF) of the GLSL 1.50 spec:
       *
       *    "The ternary selection operator (?:). It operates on three
       *    expressions (exp1 ? exp2 : exp3). This operator evaluates the
       *    first expression, which must result in a scalar Boolean."
       */
      if (!op[0]->type->is_boolean() || !op[0]->type->is_scalar()) {
	 YYLTYPE loc = this->subexpressions[0]->get_location();

	 _mesa_glsl_error(& loc, state, "?: condition must be scalar boolean");
	 error_emitted = true;
      }

      /* The :? operator is implemented by generating an anonymous temporary
       * followed by an if-statement.  The last instruction in each branch of
       * the if-statement assigns a value to the anonymous temporary.  This
       * temporary is the r-value of the expression.
       */
      ir_variable *const tmp = generate_temporary(glsl_type::error_type,
						  instructions, state);

      ir_if *const stmt = new ir_if(op[0]);
      instructions->push_tail(stmt);

      op[1] = this->subexpressions[1]->hir(& stmt->then_instructions, state);
      ir_dereference *const then_deref = new ir_dereference(tmp);
      ir_assignment *const then_assign =
	 new ir_assignment(then_deref, op[1], NULL);
      stmt->then_instructions.push_tail(then_assign);

      op[2] = this->subexpressions[2]->hir(& stmt->else_instructions, state);
      ir_dereference *const else_deref = new ir_dereference(tmp);
      ir_assignment *const else_assign =
	 new ir_assignment(else_deref, op[2], NULL);
      stmt->else_instructions.push_tail(else_assign);

      /* From page 59 (page 65 of the PDF) of the GLSL 1.50 spec:
       *
       *     "The second and third expressions can be any type, as
       *     long their types match, or there is a conversion in
       *     Section 4.1.10 "Implicit Conversions" that can be applied
       *     to one of the expressions to make their types match. This
       *     resulting matching type is the type of the entire
       *     expression."
       */
      if ((!apply_implicit_conversion(op[1]->type, op[2], state)
	   && !apply_implicit_conversion(op[2]->type, op[1], state))
	  || (op[1]->type != op[2]->type)) {
	 YYLTYPE loc = this->subexpressions[1]->get_location();

	 _mesa_glsl_error(& loc, state, "Second and third operands of ?: "
			  "operator must have matching types.");
	 error_emitted = true;
      } else {
	 tmp->type = op[1]->type;
      }

      result = new ir_dereference(tmp);
      type = tmp->type;
      break;
   }

   case ast_pre_inc:
   case ast_pre_dec: {
      op[0] = this->subexpressions[0]->hir(instructions, state);
      if (op[0]->type->base_type == GLSL_TYPE_FLOAT)
	 op[1] = new ir_constant(1.0f);
      else
	 op[1] = new ir_constant(1);

      type = arithmetic_result_type(op[0], op[1], false, state);

      struct ir_rvalue *temp_rhs;
      temp_rhs = new ir_expression(operations[this->oper], type,
				   op[0], op[1]);

      result = do_assignment(instructions, state, op[0], temp_rhs,
			     this->subexpressions[0]->get_location());
      type = result->type;
      error_emitted = op[0]->type->is_error();
      break;
   }

   case ast_post_inc:
   case ast_post_dec: {
      op[0] = this->subexpressions[0]->hir(instructions, state);
      if (op[0]->type->base_type == GLSL_TYPE_FLOAT)
	 op[1] = new ir_constant(1.0f);
      else
	 op[1] = new ir_constant(1);

      error_emitted = op[0]->type->is_error() || op[1]->type->is_error();

      type = arithmetic_result_type(op[0], op[1], false, state);

      struct ir_rvalue *temp_rhs;
      temp_rhs = new ir_expression(operations[this->oper], type,
				   op[0], op[1]);

      /* Get a temporary of a copy of the lvalue before it's modified.
       * This may get thrown away later.
       */
      result = get_lvalue_copy(instructions, state, op[0],
			       this->subexpressions[0]->get_location());

      (void)do_assignment(instructions, state, op[0], temp_rhs,
			  this->subexpressions[0]->get_location());

      type = result->type;
      error_emitted = op[0]->type->is_error();
      break;
   }

   case ast_field_selection:
      result = _mesa_ast_field_selection_to_hir(this, instructions, state);
      type = result->type;
      break;

   case ast_array_index:
      break;

   case ast_function_call:
      /* Should *NEVER* get here.  ast_function_call should always be handled
       * by ast_function_expression::hir.
       */
      assert(0);
      break;

   case ast_identifier: {
      /* ast_identifier can appear several places in a full abstract syntax
       * tree.  This particular use must be at location specified in the grammar
       * as 'variable_identifier'.
       */
      ir_variable *var = 
	 state->symbols->get_variable(this->primary_expression.identifier);

      result = new ir_dereference(var);

      if (var != NULL) {
	 type = result->type;
      } else {
	 _mesa_glsl_error(& loc, state, "`%s' undeclared",
			  this->primary_expression.identifier);

	 error_emitted = true;
      }
      break;
   }

   case ast_int_constant:
      type = glsl_type::int_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_uint_constant:
      type = glsl_type::uint_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_float_constant:
      type = glsl_type::float_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_bool_constant:
      type = glsl_type::bool_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_sequence: {
      struct simple_node *ptr;

      /* It should not be possible to generate a sequence in the AST without
       * any expressions in it.
       */
      assert(!is_empty_list(&this->expressions));

      /* The r-value of a sequence is the last expression in the sequence.  If
       * the other expressions in the sequence do not have side-effects (and
       * therefore add instructions to the instruction list), they get dropped
       * on the floor.
       */
      foreach (ptr, &this->expressions)
	 result = ((ast_node *)ptr)->hir(instructions, state);

      type = result->type;

      /* Any errors should have already been emitted in the loop above.
       */
      error_emitted = true;
      break;
   }
   }

   if (type->is_error() && !error_emitted)
      _mesa_glsl_error(& loc, state, "type mismatch");

   return result;
}


ir_rvalue *
ast_expression_statement::hir(exec_list *instructions,
			      struct _mesa_glsl_parse_state *state)
{
   /* It is possible to have expression statements that don't have an
    * expression.  This is the solitary semicolon:
    *
    * for (i = 0; i < 5; i++)
    *     ;
    *
    * In this case the expression will be NULL.  Test for NULL and don't do
    * anything in that case.
    */
   if (expression != NULL)
      expression->hir(instructions, state);

   /* Statements do not have r-values.
    */
   return NULL;
}


ir_rvalue *
ast_compound_statement::hir(exec_list *instructions,
			    struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;


   if (new_scope)
      state->symbols->push_scope();

   foreach (ptr, &statements)
      ((ast_node *)ptr)->hir(instructions, state);

   if (new_scope)
      state->symbols->pop_scope();

   /* Compound statements do not have r-values.
    */
   return NULL;
}


static const struct glsl_type *
type_specifier_to_glsl_type(const struct ast_type_specifier *spec,
			    const char **name,
			    struct _mesa_glsl_parse_state *state)
{
   struct glsl_type *type;

   if (spec->type_specifier == ast_struct) {
      /* FINISHME: Handle annonymous structures. */
      type = NULL;
   } else {
      type = state->symbols->get_type(spec->type_name);
      *name = spec->type_name;

      /* FINISHME: Handle array declarations.  Note that this requires complete
       * FINISHME: handling of constant expressions.
       */
   }

   return type;
}


static void
apply_type_qualifier_to_variable(const struct ast_type_qualifier *qual,
				 struct ir_variable *var,
				 struct _mesa_glsl_parse_state *state,
				 YYLTYPE *loc)
{
   if (qual->invariant)
      var->invariant = 1;

   /* FINISHME: Mark 'in' variables at global scope as read-only. */
   if (qual->constant || qual->attribute || qual->uniform
       || (qual->varying && (state->target == fragment_shader)))
      var->read_only = 1;

   if (qual->centroid)
      var->centroid = 1;

   if (qual->attribute && state->target == fragment_shader) {
      var->type = glsl_type::error_type;
      _mesa_glsl_error(loc, state,
		       "`attribute' variables may not be declared in the "
		       "fragment shader");
   }

   if (qual->in && qual->out)
      var->mode = ir_var_inout;
   else if (qual->attribute || qual->in
	    || (qual->varying && (state->target == fragment_shader)))
      var->mode = ir_var_in;
   else if (qual->out || (qual->varying && (state->target == vertex_shader)))
      var->mode = ir_var_out;
   else if (qual->uniform)
      var->mode = ir_var_uniform;
   else
      var->mode = ir_var_auto;

   if (qual->flat)
      var->interpolation = ir_var_flat;
   else if (qual->noperspective)
      var->interpolation = ir_var_noperspective;
   else
      var->interpolation = ir_var_smooth;
}


ir_rvalue *
ast_declarator_list::hir(exec_list *instructions,
			 struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;
   const struct glsl_type *decl_type;
   const char *type_name = NULL;


   /* FINISHME: Handle vertex shader "invariant" declarations that do not
    * FINISHME: include a type.  These re-declare built-in variables to be
    * FINISHME: invariant.
    */

   decl_type = type_specifier_to_glsl_type(this->type->specifier,
					   & type_name, state);

   foreach (ptr, &this->declarations) {
      struct ast_declaration *const decl = (struct ast_declaration * )ptr;
      const struct glsl_type *var_type;
      struct ir_variable *var;
      YYLTYPE loc = this->get_location();

      /* FINISHME: Emit a warning if a variable declaration shadows a
       * FINISHME: declaration at a higher scope.
       */

      if ((decl_type == NULL) || decl_type->is_void()) {
	 if (type_name != NULL) {
	    _mesa_glsl_error(& loc, state,
			     "invalid type `%s' in declaration of `%s'",
			     type_name, decl->identifier);
	 } else {
	    _mesa_glsl_error(& loc, state,
			     "invalid type in declaration of `%s'",
			     decl->identifier);
	 }
	 continue;
      }

      if (decl->is_array) {
	 /* FINISHME: Handle array declarations.  Note that this requires
	  * FINISHME: complete handling of constant expressions.
	  */
	 var_type = glsl_type::error_type;

	 /* FINISHME: Reject delcarations of multidimensional arrays. */
      } else {
	 var_type = decl_type;
      }

      var = new ir_variable(var_type, decl->identifier);

      /* FINISHME: Variables that are attribute, uniform, varying, in, or
       * FINISHME: out varibles must be declared either at global scope or
       * FINISHME: in a parameter list (in and out only).
       */

      apply_type_qualifier_to_variable(& this->type->qualifier, var, state,
				       & loc);

      /* Attempt to add the variable to the symbol table.  If this fails, it
       * means the variable has already been declared at this scope.
       */
      if (state->symbols->name_declared_this_scope(decl->identifier)) {
	 YYLTYPE loc = this->get_location();

	 _mesa_glsl_error(& loc, state, "`%s' redeclared",
			  decl->identifier);
	 continue;
      }

      instructions->push_tail(var);

      if (decl->initializer != NULL) {
	 YYLTYPE initializer_loc = decl->initializer->get_location();

	 /* From page 24 (page 30 of the PDF) of the GLSL 1.10 spec:
	  *
	  *    "All uniform variables are read-only and are initialized either
	  *    directly by an application via API commands, or indirectly by
	  *    OpenGL."
	  */
	 if ((state->language_version <= 110)
	     && (var->mode == ir_var_uniform)) {
	    _mesa_glsl_error(& initializer_loc, state,
			     "cannot initialize uniforms in GLSL 1.10");
	 }

	 if (var->type->is_sampler()) {
	    _mesa_glsl_error(& initializer_loc, state,
			     "cannot initialize samplers");
	 }

	 if ((var->mode == ir_var_in) && (state->current_function == NULL)) {
	    _mesa_glsl_error(& initializer_loc, state,
			     "cannot initialize %s shader input / %s",
			     (state->target == vertex_shader)
			     ? "vertex" : "fragment",
			     (state->target == vertex_shader)
			     ? "attribute" : "varying");
	 }

	 ir_dereference *const lhs = new ir_dereference(var);
	 ir_rvalue *const rhs = decl->initializer->hir(instructions, state);

	 /* FINISHME: If the declaration is either 'const' or 'uniform', the
	  * FINISHME: initializer (rhs) must be a constant expression.
	  */

	 if (!rhs->type->is_error()) {
	    (void) do_assignment(instructions, state, lhs, rhs,
				 this->get_location());
	 }
      }

      /* Add the vairable to the symbol table after processing the initializer.
       * This differs from most C-like languages, but it follows the GLSL
       * specification.  From page 28 (page 34 of the PDF) of the GLSL 1.50
       * spec:
       *
       *     "Within a declaration, the scope of a name starts immediately
       *     after the initializer if present or immediately after the name
       *     being declared if not."
       */
      const bool added_variable =
	 state->symbols->add_variable(decl->identifier, var);
      assert(added_variable);
   }

   /* Variable declarations do not have r-values.
    */
   return NULL;
}


ir_rvalue *
ast_parameter_declarator::hir(exec_list *instructions,
			      struct _mesa_glsl_parse_state *state)
{
   const struct glsl_type *type;
   const char *name = NULL;
   YYLTYPE loc = this->get_location();

   type = type_specifier_to_glsl_type(this->type->specifier, & name, state);

   if (type == NULL) {
      if (name != NULL) {
	 _mesa_glsl_error(& loc, state,
			  "invalid type `%s' in declaration of `%s'",
			  name, this->identifier);
      } else {
	 _mesa_glsl_error(& loc, state,
			  "invalid type in declaration of `%s'",
			  this->identifier);
      }

      type = glsl_type::error_type;
   }

   ir_variable *var = new ir_variable(type, this->identifier);

   /* FINISHME: Handle array declarations.  Note that this requires
    * FINISHME: complete handling of constant expressions.
    */

   /* Apply any specified qualifiers to the parameter declaration.  Note that
    * for function parameters the default mode is 'in'.
    */
   apply_type_qualifier_to_variable(& this->type->qualifier, var, state, & loc);
   if (var->mode == ir_var_auto)
      var->mode = ir_var_in;

   instructions->push_tail(var);

   /* Parameter declarations do not have r-values.
    */
   return NULL;
}


static void
ast_function_parameters_to_hir(struct simple_node *ast_parameters,
			       exec_list *ir_parameters,
			       struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;

   foreach (ptr, ast_parameters) {
      ((ast_node *)ptr)->hir(ir_parameters, state);
   }
}


static bool
parameter_lists_match(exec_list *list_a, exec_list *list_b)
{
   exec_list_iterator iter_a = list_a->iterator();
   exec_list_iterator iter_b = list_b->iterator();

   while (iter_a.has_next()) {
      /* If all of the parameters from the other parameter list have been
       * exhausted, the lists have different length and, by definition,
       * do not match.
       */
      if (!iter_b.has_next())
	 return false;

      /* If the types of the parameters do not match, the parameters lists
       * are different.
       */
      /* FINISHME */


      iter_a.next();
      iter_b.next();
   }

   return true;
}


ir_rvalue *
ast_function_definition::hir(exec_list *instructions,
			     struct _mesa_glsl_parse_state *state)
{
   ir_label *label;
   ir_function_signature *signature = NULL;
   ir_function *f = NULL;
   exec_list parameters;


   /* Convert the list of function parameters to HIR now so that they can be
    * used below to compare this function's signature with previously seen
    * signatures for functions with the same name.
    */
   ast_function_parameters_to_hir(& this->prototype->parameters, & parameters,
				  state);

   const char *return_type_name;
   const glsl_type *return_type =
      type_specifier_to_glsl_type(this->prototype->return_type->specifier,
				  & return_type_name, state);

   assert(return_type != NULL);

   /* Verify that this function's signature either doesn't match a previously
    * seen signature for a function with the same name, or, if a match is found,
    * that the previously seen signature does not have an associated definition.
    */
   const char *const name = this->prototype->identifier;
   f = state->symbols->get_function(name);
   if (f != NULL) {
      foreach_iter(exec_list_iterator, iter, f->signatures) {
	 signature = (struct ir_function_signature *) iter.get();

	 /* Compare the parameter list of the function being defined to the
	  * existing function.  If the parameter lists match, then the return
	  * type must also match and the existing function must not have a
	  * definition.
	  */
	 if (parameter_lists_match(& parameters, & signature->parameters)) {
	    /* FINISHME: Compare return types. */

	    if (signature->definition != NULL) {
	       YYLTYPE loc = this->get_location();

	       _mesa_glsl_error(& loc, state, "function `%s' redefined", name);
	       signature = NULL;
	       break;
	    }
	 }

	 signature = NULL;
      }

   } else if (state->symbols->name_declared_this_scope(name)) {
      /* This function name shadows a non-function use of the same name.
       */
      YYLTYPE loc = this->get_location();

      _mesa_glsl_error(& loc, state, "function name `%s' conflicts with "
		       "non-function", name);
      signature = NULL;
   } else {
      f = new ir_function(name);
      state->symbols->add_function(f->name, f);
   }

   /* Verify the return type of main() */
   if (strcmp(name, "main") == 0) {
      if (return_type != glsl_type::get_instance(GLSL_TYPE_VOID, 0, 0)) {
	 YYLTYPE loc = this->get_location();

	 _mesa_glsl_error(& loc, state, "main() must return void");
      }
   }

   /* Finish storing the information about this new function in its signature.
    */
   if (signature == NULL) {
      signature = new ir_function_signature(return_type);
      f->signatures.push_tail(signature);
   } else {
      /* Destroy all of the previous parameter information.  The previous
       * parameter information comes from the function prototype, and it can
       * either include invalid parameter names or may not have names at all.
       */
      foreach_iter(exec_list_iterator, iter, signature->parameters) {
	 assert(((ir_instruction *) iter.get())->as_variable() != NULL);

	 iter.remove();
	 delete iter.get();
      }
   }


   assert(state->current_function == NULL);
   state->current_function = signature;

   ast_function_parameters_to_hir(& this->prototype->parameters,
				  & signature->parameters,
				  state);
   /* FINISHME: Set signature->return_type */

   label = new ir_label(name);
   if (signature->definition == NULL) {
      signature->definition = label;
   }
   instructions->push_tail(label);

   /* Add the function parameters to the symbol table.  During this step the
    * parameter declarations are also moved from the temporary "parameters" list
    * to the instruction list.  There are other more efficient ways to do this,
    * but they involve ugly linked-list gymnastics.
    */
   state->symbols->push_scope();
   foreach_iter(exec_list_iterator, iter, parameters) {
      ir_variable *const var = (ir_variable *) iter.get();

      assert(((ir_instruction *) var)->as_variable() != NULL);

      iter.remove();
      instructions->push_tail(var);

      /* The only way a parameter would "exist" is if two parameters have
       * the same name.
       */
      if (state->symbols->name_declared_this_scope(var->name)) {
	 YYLTYPE loc = this->get_location();

	 _mesa_glsl_error(& loc, state, "parameter `%s' redeclared", var->name);
      } else {
	 state->symbols->add_variable(var->name, var);
      }
   }

   /* Convert the body of the function to HIR, and append the resulting
    * instructions to the list that currently consists of the function label
    * and the function parameters.
    */
   this->body->hir(instructions, state);

   state->symbols->pop_scope();

   assert(state->current_function == signature);
   state->current_function = NULL;

   /* Function definitions do not have r-values.
    */
   return NULL;
}


ir_rvalue *
ast_jump_statement::hir(exec_list *instructions,
			struct _mesa_glsl_parse_state *state)
{

   if (mode == ast_return) {
      ir_return *inst;

      if (opt_return_value) {
	 /* FINISHME: Make sure the enclosing function has a non-void return
	  * FINISHME: type.
	  */

	 ir_expression *const ret = (ir_expression *)
	    opt_return_value->hir(instructions, state);
	 assert(ret != NULL);

	 /* FINISHME: Make sure the type of the return value matches the return
	  * FINISHME: type of the enclosing function.
	  */

	 inst = new ir_return(ret);
      } else {
	 /* FINISHME: Make sure the enclosing function has a void return type.
	  */
	 inst = new ir_return;
      }

      instructions->push_tail(inst);
   }

   /* Jump instructions do not have r-values.
    */
   return NULL;
}


ir_rvalue *
ast_selection_statement::hir(exec_list *instructions,
			     struct _mesa_glsl_parse_state *state)
{
   ir_rvalue *const condition = this->condition->hir(instructions, state);
   struct simple_node *ptr;

   /* From page 66 (page 72 of the PDF) of the GLSL 1.50 spec:
    *
    *    "Any expression whose type evaluates to a Boolean can be used as the
    *    conditional expression bool-expression. Vector types are not accepted
    *    as the expression to if."
    *
    * The checks are separated so that higher quality diagnostics can be
    * generated for cases where both rules are violated.
    */
   if (!condition->type->is_boolean() || !condition->type->is_scalar()) {
      YYLTYPE loc = this->condition->get_location();

      _mesa_glsl_error(& loc, state, "if-statement condition must be scalar "
		       "boolean");
   }

   ir_if *const stmt = new ir_if(condition);

   if (then_statement != NULL) {
      ast_node *node = (ast_node *) then_statement;
      do {
	 node->hir(& stmt->then_instructions, state);
	 node = (ast_node *) node->next;
      } while (node != then_statement);
   }

   if (else_statement != NULL) {
      ast_node *node = (ast_node *) else_statement;
      do {
	 node->hir(& stmt->else_instructions, state);
	 node = (ast_node *) node->next;
      } while (node != else_statement);
   }

   instructions->push_tail(stmt);

   /* if-statements do not have r-values.
    */
   return NULL;
}