cpp_typecheck_conversions.cpp

Go to the documentation of this file.

/*******************************************************************\
 
Module: C++ Language Type Checking
 
Author:
 
\*******************************************************************/
 
 
#include "cpp_typecheck.h"
 
#include <util/arith_tools.h>
#include <util/c_types.h>
#include <util/config.h>
#include <util/expr_util.h>
#include <util/pointer_expr.h>
#include <util/simplify_expr.h>
#include <util/std_expr.h>
 
#include <ansi-c/c_qualifiers.h>
 
#include "cpp_util.h"
 
bool cpp_typecheckt::standard_conversion_lvalue_to_rvalue(
  const exprt &expr,
  exprt &new_expr) const
{
  PRECONDITION(expr.get_bool(ID_C_lvalue));
 
  if(expr.type().id() == ID_code)
    return false;
 
  if(
    expr.type().id() == ID_struct &&
    to_struct_type(expr.type()).is_incomplete())
    return false;
 
  if(expr.type().id() == ID_union && to_union_type(expr.type()).is_incomplete())
    return false;
 
  new_expr=expr;
  new_expr.remove(ID_C_lvalue);
 
  return true;
}
 
bool cpp_typecheckt::standard_conversion_array_to_pointer(
  const exprt &expr,
  exprt &new_expr) const
{
  PRECONDITION(expr.type().id() == ID_array);
 
  index_exprt index(expr, from_integer(0, c_index_type()));
 
  index.set(ID_C_lvalue, true);
 
  new_expr=address_of_exprt(index);
 
  return true;
}
 
bool cpp_typecheckt::standard_conversion_function_to_pointer(
  const exprt &expr, exprt &new_expr) const
{
  if(!expr.get_bool(ID_C_lvalue))
    return false;
 
  new_expr=address_of_exprt(expr);
 
  return true;
}
 
bool cpp_typecheckt::standard_conversion_qualification(
  const exprt &expr,
  const typet &type,
  exprt &new_expr) const
{
  if(expr.type().id()!=ID_pointer ||
     is_reference(expr.type()))
    return false;
 
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  if(expr.type()!=type)
    return false;
 
  typet sub_from = to_pointer_type(expr.type()).base_type();
  typet sub_to = to_pointer_type(type).base_type();
  bool const_to=true;
 
  while(sub_from.id()==ID_pointer)
  {
    c_qualifierst qual_from(sub_from);
    c_qualifierst qual_to(sub_to);
 
    if(!qual_to.is_constant)
      const_to=false;
 
    if(qual_from.is_constant && !qual_to.is_constant)
      return false;
 
    if(qual_from!=qual_to && !const_to)
      return false;
 
    typet tmp1 = to_pointer_type(sub_from).base_type();
    sub_from.swap(tmp1);
 
    typet tmp2 = sub_to.add_subtype();
    sub_to.swap(tmp2);
  }
 
  c_qualifierst qual_from(sub_from);
  c_qualifierst qual_to(sub_to);
 
  if(qual_from.is_subset_of(qual_to))
  {
    new_expr=expr;
    new_expr.type()=type;
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::standard_conversion_integral_promotion(
  const exprt &expr,
  exprt &new_expr) const
{
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  c_qualifierst qual_from;
  qual_from.read(expr.type());
 
  typet int_type=signed_int_type();
  qual_from.write(int_type);
 
  if(expr.type().id()==ID_signedbv)
  {
    std::size_t width=to_signedbv_type(expr.type()).get_width();
    if(width >= config.ansi_c.int_width)
      return false;
    new_expr = typecast_exprt(expr, int_type);
    return true;
  }
 
  if(expr.type().id()==ID_unsignedbv)
  {
    std::size_t width=to_unsignedbv_type(expr.type()).get_width();
    if(width >= config.ansi_c.int_width)
      return false;
    new_expr = typecast_exprt(expr, int_type);
    return true;
  }
 
  if(expr.is_boolean() || expr.type().id() == ID_c_bool)
  {
    new_expr = typecast_exprt(expr, int_type);
    return true;
  }
 
  if(expr.type().id()==ID_c_enum_tag)
  {
    new_expr = typecast_exprt(expr, int_type);
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::standard_conversion_floating_point_promotion(
  const exprt &expr,
  exprt &new_expr) const
{
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  // we only do that with 'float',
  // not with 'double' or 'long double'
  if(expr.type()!=float_type())
    return false;
 
  std::size_t width=to_floatbv_type(expr.type()).get_width();
 
  if(width!=config.ansi_c.single_width)
    return false;
 
  c_qualifierst qual_from;
  qual_from.read(expr.type());
 
  new_expr = typecast_exprt(expr, double_type());
  qual_from.write(new_expr.type());
 
  return true;
}
 
bool cpp_typecheckt::standard_conversion_integral_conversion(
  const exprt &expr,
  const typet &type,
  exprt &new_expr) const
{
  if(type.id()!=ID_signedbv &&
     type.id()!=ID_unsignedbv)
      return false;
 
  if(
    expr.type().id() != ID_signedbv && expr.type().id() != ID_unsignedbv &&
    expr.type().id() != ID_c_bool && !expr.is_boolean() &&
    expr.type().id() != ID_c_enum_tag)
  {
    return false;
  }
 
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  c_qualifierst qual_from;
  qual_from.read(expr.type());
  new_expr = typecast_exprt::conditional_cast(expr, type);
  qual_from.write(new_expr.type());
 
  return true;
}
 
bool cpp_typecheckt::standard_conversion_floating_integral_conversion(
  const exprt &expr,
  const typet &type,
  exprt &new_expr) const
{
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  if(expr.type().id()==ID_floatbv ||
     expr.type().id()==ID_fixedbv)
  {
    if(type.id()!=ID_signedbv &&
       type.id()!=ID_unsignedbv)
      return false;
  }
  else if(expr.type().id()==ID_signedbv ||
          expr.type().id()==ID_unsignedbv ||
          expr.type().id()==ID_c_enum_tag)
  {
    if(type.id()!=ID_fixedbv &&
       type.id()!=ID_floatbv)
      return false;
  }
  else
    return false;
 
  c_qualifierst qual_from;
  qual_from.read(expr.type());
  new_expr = typecast_exprt::conditional_cast(expr, type);
  qual_from.write(new_expr.type());
 
  return true;
}
 
 
bool cpp_typecheckt::standard_conversion_floating_point_conversion(
  const exprt &expr,
  const typet &type,
  exprt &new_expr) const
{
  if(expr.type().id()!=ID_floatbv &&
     expr.type().id()!=ID_fixedbv)
    return false;
 
  if(type.id()!=ID_floatbv &&
     type.id()!=ID_fixedbv)
      return false;
 
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  c_qualifierst qual_from;
 
  qual_from.read(expr.type());
  new_expr = typecast_exprt::conditional_cast(expr, type);
  qual_from.write(new_expr.type());
 
  return true;
}
 
bool cpp_typecheckt::standard_conversion_pointer(
  const exprt &expr,
  const typet &type,
  exprt &new_expr)
{
  if(type.id()!=ID_pointer ||
     is_reference(type))
    return false;
 
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  // integer 0 to NULL pointer conversion?
  if(simplify_expr(expr, *this).is_zero() &&
     expr.type().id()!=ID_pointer)
  {
    new_expr=expr;
    new_expr.set(ID_value, ID_NULL);
    new_expr.type()=type;
    return true;
  }
 
  if(type.find(ID_to_member).is_not_nil())
    return false;
 
  if(
    expr.type().id() != ID_pointer ||
    expr.type().find(ID_to_member).is_not_nil())
  {
    return false;
  }
 
  const pointer_typet &pointer_type = to_pointer_type(type);
  const typet &sub_from = to_pointer_type(expr.type()).base_type();
  const typet &sub_to = pointer_type.base_type();
 
  // std::nullptr_t to _any_ pointer type
  if(sub_from.id()==ID_nullptr)
    return true;
 
  // anything but function pointer to void *
  if(sub_from.id()!=ID_code && sub_to.id()==ID_empty)
  {
    c_qualifierst qual_from;
    qual_from.read(to_pointer_type(expr.type()).base_type());
    new_expr = typecast_exprt::conditional_cast(expr, type);
    qual_from.write(to_pointer_type(new_expr.type()).base_type());
    return true;
  }
 
  // struct * to struct *
  if(sub_from.id() == ID_struct_tag && sub_to.id() == ID_struct_tag)
  {
    const struct_typet &from_struct = follow_tag(to_struct_tag_type(sub_from));
    const struct_typet &to_struct = follow_tag(to_struct_tag_type(sub_to));
    if(subtype_typecast(from_struct, to_struct))
    {
      c_qualifierst qual_from;
      qual_from.read(to_pointer_type(expr.type()).base_type());
      new_expr=expr;
      make_ptr_typecast(new_expr, pointer_type);
      qual_from.write(to_pointer_type(new_expr.type()).base_type());
      return true;
    }
  }
 
  return false;
}
 
bool cpp_typecheckt::standard_conversion_pointer_to_member(
  const exprt &expr,
  const typet &type,
  exprt &new_expr)
{
  if(
    type.id() != ID_pointer || is_reference(type) ||
    type.find(ID_to_member).is_nil())
  {
    return false;
  }
 
  if(expr.type().id() != ID_pointer || expr.type().find(ID_to_member).is_nil())
    return false;
 
  if(
    to_pointer_type(type).base_type() !=
    to_pointer_type(expr.type()).base_type())
  {
    // base types are different
    if(
      to_pointer_type(type).base_type().id() == ID_code &&
      to_pointer_type(expr.type()).base_type().id() == ID_code)
    {
      code_typet code1 = to_code_type(to_pointer_type(expr.type()).base_type());
      DATA_INVARIANT(!code1.parameters().empty(), "must have parameters");
      code_typet::parametert this1=code1.parameters()[0];
      INVARIANT(this1.get_this(), "first parameter should be `this'");
      code1.parameters().erase(code1.parameters().begin());
 
      code_typet code2 = to_code_type(to_pointer_type(type).base_type());
      DATA_INVARIANT(!code2.parameters().empty(), "must have parameters");
      code_typet::parametert this2=code2.parameters()[0];
      INVARIANT(this2.get_this(), "first parameter should be `this'");
      code2.parameters().erase(code2.parameters().begin());
 
      if(
        to_pointer_type(this2.type()).base_type().get_bool(ID_C_constant) &&
        !to_pointer_type(this1.type()).base_type().get_bool(ID_C_constant))
        return false;
 
      // give a second chance ignoring `this'
      if(code1!=code2)
        return false;
    }
    else
      return false;
  }
 
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  if(expr.is_constant() && to_constant_expr(expr).is_null_pointer())
  {
    new_expr = typecast_exprt::conditional_cast(expr, type);
    return true;
  }
 
  const struct_typet &from_struct = follow_tag(to_struct_tag_type(
    static_cast<const typet &>(expr.type().find(ID_to_member))));
 
  const struct_typet &to_struct = follow_tag(
    to_struct_tag_type(static_cast<const typet &>(type.find(ID_to_member))));
 
  if(subtype_typecast(to_struct, from_struct))
  {
    new_expr = typecast_exprt::conditional_cast(expr, type);
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::standard_conversion_boolean(
  const exprt &expr, exprt &new_expr) const
{
  if(expr.get_bool(ID_C_lvalue))
    return false;
 
  if(
    expr.type().id() != ID_signedbv && expr.type().id() != ID_unsignedbv &&
    expr.type().id() != ID_pointer && !expr.is_boolean() &&
    expr.type().id() != ID_c_enum_tag)
  {
    return false;
  }
 
  c_qualifierst qual_from;
  qual_from.read(expr.type());
 
  typet Bool = c_bool_type();
  qual_from.write(Bool);
 
  new_expr = typecast_exprt::conditional_cast(expr, Bool);
  return true;
}
 
bool cpp_typecheckt::standard_conversion_sequence(
  const exprt &expr,
  const typet &type,
  exprt &new_expr,
  unsigned &rank)
{
  PRECONDITION(!is_reference(expr.type()) && !is_reference(type));
 
  exprt curr_expr=expr;
 
  // bit fields are converted like their underlying type
  if(type.id()==ID_c_bit_field)
    return standard_conversion_sequence(
      expr, to_c_bit_field_type(type).underlying_type(), new_expr, rank);
 
  // we turn bit fields into their underlying type
  if(curr_expr.type().id()==ID_c_bit_field)
    curr_expr = typecast_exprt(
      curr_expr, to_c_bit_field_type(curr_expr.type()).underlying_type());
 
  if(curr_expr.type().id()==ID_array)
  {
    if(type.id()==ID_pointer)
    {
      if(!standard_conversion_array_to_pointer(curr_expr, new_expr))
        return false;
    }
  }
  else if(curr_expr.type().id()==ID_code &&
          type.id()==ID_pointer)
  {
    if(!standard_conversion_function_to_pointer(curr_expr, new_expr))
      return false;
  }
  else if(curr_expr.get_bool(ID_C_lvalue))
  {
    if(!standard_conversion_lvalue_to_rvalue(curr_expr, new_expr))
      return false;
  }
  else
    new_expr=curr_expr;
 
  curr_expr.swap(new_expr);
 
  // two enums are the same if the tag is the same,
  // even if the width differs (enum bit-fields!)
  if(type.id() == ID_c_enum_tag && curr_expr.type().id() == ID_c_enum_tag)
  {
    if(
      to_tag_type(type).get_identifier() ==
      to_tag_type(curr_expr.type()).get_identifier())
    {
      return true;
    }
    else
    {
      // In contrast to C, we simply don't allow implicit conversions
      // between enums.
      return false;
    }
  }
 
  // need to consider #c_type
  if(
    curr_expr.type() != type ||
    curr_expr.type().get(ID_C_c_type) != type.get(ID_C_c_type))
  {
    if(
      type.id() == ID_signedbv || type.id() == ID_unsignedbv ||
      type.id() == ID_c_enum_tag)
    {
      if(!standard_conversion_integral_promotion(curr_expr, new_expr) ||
         new_expr.type() != type)
      {
        if(!standard_conversion_integral_conversion(curr_expr, type, new_expr))
        {
          if(!standard_conversion_floating_integral_conversion(
              curr_expr, type, new_expr))
            return false;
        }
 
        rank+=3;
      }
      else
        rank+=2;
    }
    else if(type.id()==ID_floatbv || type.id()==ID_fixedbv)
    {
      if(!standard_conversion_floating_point_promotion(curr_expr, new_expr) ||
         new_expr.type() != type)
      {
        if(!standard_conversion_floating_point_conversion(
            curr_expr, type, new_expr) &&
           !standard_conversion_floating_integral_conversion(
             curr_expr, type, new_expr))
          return false;
 
        rank += 3;
      }
      else
        rank += 2;
    }
    else if(type.id()==ID_pointer)
    {
      if(
        expr.type().id() == ID_pointer &&
        to_pointer_type(expr.type()).base_type().id() == ID_nullptr)
      {
        // std::nullptr_t to _any_ pointer type is ok
        new_expr = typecast_exprt::conditional_cast(new_expr, type);
      }
      else if(!standard_conversion_pointer(curr_expr, type, new_expr))
      {
        if(!standard_conversion_pointer_to_member(curr_expr, type, new_expr))
          return false;
      }
 
      rank += 3;
    }
    else if(type.id() == ID_c_bool)
    {
      if(!standard_conversion_boolean(curr_expr, new_expr))
        return false;
 
      rank += 3;
    }
    else if(type.id() == ID_bool)
    {
      new_expr = is_not_zero(curr_expr, *this);
 
      rank += 3;
    }
    else
      return false;
  }
  else
    new_expr=curr_expr;
 
  curr_expr.swap(new_expr);
 
  if(curr_expr.type().id()==ID_pointer)
  {
    typet sub_from=curr_expr.type();
    typet sub_to=type;
 
    do
    {
      typet tmp_from = to_pointer_type(sub_from).base_type();
      sub_from.swap(tmp_from);
      typet tmp_to = sub_to.add_subtype();
      sub_to.swap(tmp_to);
 
      c_qualifierst qual_from;
      qual_from.read(sub_from);
 
      c_qualifierst qual_to;
      qual_to.read(sub_to);
 
      if(qual_from!=qual_to)
      {
        rank+=1;
        break;
      }
    }
    while(sub_from.id()==ID_pointer);
 
    if(!standard_conversion_qualification(curr_expr, type, new_expr))
      return false;
  }
  else
  {
    new_expr=curr_expr;
    new_expr.type()=type;
  }
 
  return true;
}
 
bool cpp_typecheckt::user_defined_conversion_sequence(
  const exprt &expr,
  const typet &to,
  exprt &new_expr,
  unsigned &rank)
{
  PRECONDITION(!is_reference(expr.type()));
  PRECONDITION(!is_reference(to));
 
  const typet &from = expr.type();
 
  new_expr.make_nil();
 
  // special case:
  // A conversion from a type to the same type is given an exact
  // match rank even though a user-defined conversion is used
 
  if(from==to)
    rank+=0;
  else
    rank+=4; // higher than all the standard conversions
 
  if(to.id() == ID_struct_tag)
  {
    std::string err_msg;
 
    if(cpp_is_pod(to))
    {
      if(from.id() == ID_struct_tag)
      {
        const struct_typet &from_struct = follow_tag(to_struct_tag_type(from));
        const struct_typet &to_struct = follow_tag(to_struct_tag_type(to));
 
        // potentially requires
        // expr.get_bool(ID_C_lvalue) ??
 
        if(subtype_typecast(from_struct, to_struct))
        {
          exprt address=address_of_exprt(expr);
 
          // simplify address
          if(expr.id()==ID_dereference)
            address = to_dereference_expr(expr).pointer();
 
          pointer_typet ptr_sub = pointer_type(to);
          c_qualifierst qual_from;
          qual_from.read(expr.type());
          qual_from.write(ptr_sub.base_type());
          make_ptr_typecast(address, ptr_sub);
 
          const dereference_exprt deref(address);
 
          // create temporary object
          side_effect_exprt tmp_object_expr(
            ID_temporary_object, to, expr.source_location());
          tmp_object_expr.copy_to_operands(deref);
          tmp_object_expr.set(ID_C_lvalue, true);
          tmp_object_expr.set(ID_mode, ID_cpp);
 
          new_expr.swap(tmp_object_expr);
          return true;
        }
      }
    }
    else
    {
      bool found=false;
      const auto &struct_type_to = follow_tag(to_struct_tag_type(to));
 
      for(const auto &component : struct_type_to.components())
      {
        if(component.get_bool(ID_from_base))
          continue;
 
        if(component.get_bool(ID_is_explicit))
          continue;
 
        const typet &comp_type = component.type();
 
        if(comp_type.id() !=ID_code)
          continue;
 
        if(to_code_type(comp_type).return_type().id() != ID_constructor)
          continue;
 
        // TODO: ellipsis
 
        const auto &parameters = to_code_type(comp_type).parameters();
 
        if(parameters.size() != 2)
          continue;
 
        exprt curr_arg1 = parameters[1];
        typet arg1_type=curr_arg1.type();
 
        if(is_reference(arg1_type))
        {
          typet tmp = to_reference_type(arg1_type).base_type();
          arg1_type.swap(tmp);
        }
 
        unsigned tmp_rank=0;
        if(arg1_type.id() != ID_struct_tag)
        {
            exprt tmp_expr;
            if(standard_conversion_sequence(
                expr, arg1_type, tmp_expr, tmp_rank))
            {
              // check if it's ambiguous
              if(found)
                return false;
              found=true;
 
              if(expr.get_bool(ID_C_lvalue))
                tmp_expr.set(ID_C_lvalue, true);
 
              tmp_expr.add_source_location()=expr.source_location();
 
              exprt func_symb = cpp_symbol_expr(lookup(component.get_name()));
              func_symb.type()=comp_type;
              already_typechecked_exprt::make_already_typechecked(func_symb);
 
              // create temporary object
              side_effect_expr_function_callt ctor_expr(
                std::move(func_symb),
                {tmp_expr},
                uninitialized_typet{},
                expr.source_location());
              typecheck_side_effect_function_call(ctor_expr);
              CHECK_RETURN(ctor_expr.get(ID_statement) == ID_temporary_object);
 
              new_expr.swap(ctor_expr);
 
              if(struct_type_to.get_bool(ID_C_constant))
                new_expr.type().set(ID_C_constant, true);
 
              rank += tmp_rank;
            }
          }
          else if(from.id() == ID_struct_tag && arg1_type.id() == ID_struct_tag)
          {
            // try derived-to-base conversion
            address_of_exprt expr_pfrom(expr, pointer_type(expr.type()));
            pointer_typet pto=pointer_type(arg1_type);
 
            exprt expr_ptmp;
            tmp_rank=0;
            if(standard_conversion_sequence(
                expr_pfrom, pto, expr_ptmp, tmp_rank))
            {
              // check if it's ambiguous
              if(found)
                return false;
              found=true;
 
              rank+=tmp_rank;
 
              // create temporary object
              dereference_exprt expr_deref(expr_ptmp);
              expr_deref.set(ID_C_lvalue, true);
              expr_deref.add_source_location()=expr.source_location();
 
              exprt new_object(ID_new_object, to);
              new_object.set(ID_C_lvalue, true);
              new_object.type().set(ID_C_constant, false);
 
              exprt func_symb = cpp_symbol_expr(lookup(component.get_name()));
              func_symb.type()=comp_type;
              already_typechecked_exprt::make_already_typechecked(func_symb);
 
              side_effect_expr_function_callt ctor_expr(
                std::move(func_symb),
                {expr_deref},
                uninitialized_typet{},
                expr.source_location());
              typecheck_side_effect_function_call(ctor_expr);
 
              new_expr.swap(ctor_expr);
 
              INVARIANT(
                new_expr.get(ID_statement)==ID_temporary_object,
                "statement ID");
 
              if(struct_type_to.get_bool(ID_C_constant))
                new_expr.type().set(ID_C_constant, true);
            }
          }
        }
        if(found)
          return true;
      }
  }
 
  // conversion operators
  if(from.id() == ID_struct_tag)
  {
    bool found=false;
    for(const auto &component :
        follow_tag(to_struct_tag_type(from)).components())
    {
      if(component.get_bool(ID_from_base))
        continue;
 
      if(!component.get_bool(ID_is_cast_operator))
        continue;
 
      const code_typet &comp_type = to_code_type(component.type());
      DATA_INVARIANT(
        comp_type.parameters().size() == 1, "expected exactly one parameter");
 
      typet this_type = comp_type.parameters().front().type();
      this_type.set(ID_C_reference, true);
 
      exprt this_expr(expr);
      this_type.set(ID_C_this, true);
 
      unsigned tmp_rank=0;
      exprt tmp_expr;
 
      if(implicit_conversion_sequence(
        this_expr, this_type, tmp_expr, tmp_rank))
      {
        // To take care of the possible virtual case,
        // we build the function as a member expression.
        const cpp_namet cpp_func_name(component.get_base_name());
 
        exprt member_func(ID_member);
        member_func.add(ID_component_cpp_name)=cpp_func_name;
        member_func.copy_to_operands(already_typechecked_exprt{expr});
 
        side_effect_expr_function_callt func_expr(
          std::move(member_func),
          {},
          uninitialized_typet{},
          expr.source_location());
        typecheck_side_effect_function_call(func_expr);
 
        if(standard_conversion_sequence(func_expr, to, tmp_expr, tmp_rank))
        {
          // check if it's ambiguous
          if(found)
            return false;
          found=true;
 
          rank+=tmp_rank;
          new_expr.swap(tmp_expr);
        }
      }
    }
    if(found)
      return true;
  }
 
  return new_expr.is_not_nil();
}
 
bool cpp_typecheckt::reference_related(
  const exprt &expr,
  const reference_typet &reference_type) const
{
  PRECONDITION(!is_reference(expr.type()));
 
  const typet &from = expr.type();
  const typet &from_followed =
    from.id() == ID_struct_tag
      ? static_cast<const typet &>(follow_tag(to_struct_tag_type(from)))
    : from.id() == ID_union_tag
      ? static_cast<const typet &>(follow_tag(to_union_tag_type(from)))
      : from;
  const typet &to = reference_type.base_type();
  const typet &to_followed =
    to.id() == ID_struct_tag
      ? static_cast<const typet &>(follow_tag(to_struct_tag_type(to)))
    : to.id() == ID_union_tag
      ? static_cast<const typet &>(follow_tag(to_union_tag_type(to)))
      : to;
 
  // need to check #c_type
  if(from_followed.get(ID_C_c_type) != to_followed.get(ID_C_c_type))
    return false;
 
  if(from==to)
    return true;
 
  if(from.id() == ID_struct_tag && to.id() == ID_struct_tag)
  {
    return subtype_typecast(
      to_struct_type(from_followed), to_struct_type(to_followed));
  }
 
  if(
    from.id() == ID_struct_tag && reference_type.get_bool(ID_C_this) &&
    to.id() == ID_empty)
  {
    // virtual-call case
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::reference_compatible(
  const exprt &expr,
  const reference_typet &reference_type,
  unsigned &rank) const
{
  PRECONDITION(!is_reference(expr.type()));
 
  if(!reference_related(expr, reference_type))
    return false;
 
  if(expr.type() != reference_type.base_type())
    rank+=3;
 
  c_qualifierst qual_from;
    qual_from.read(expr.type());
 
  c_qualifierst qual_to;
  qual_to.read(reference_type.base_type());
 
  if(qual_from!=qual_to)
    rank+=1;
 
  if(qual_from.is_subset_of(qual_to))
    return true;
 
  return false;
}
 
bool cpp_typecheckt::reference_binding(
  exprt expr,
  const reference_typet &reference_type,
  exprt &new_expr,
  unsigned &rank)
{
  PRECONDITION(!is_reference(expr.type()));
 
  unsigned backup_rank=rank;
 
  if(reference_type.get_bool(ID_C_this) && !expr.get_bool(ID_C_lvalue))
  {
    // `this' has to be an lvalue
    if(expr.get(ID_statement)==ID_temporary_object)
      expr.set(ID_C_lvalue, true);
    else if(expr.get(ID_statement)==ID_function_call)
      expr.set(ID_C_lvalue, true);
    else if(expr.get_bool(ID_C_temporary_avoided))
    {
      expr.remove(ID_C_temporary_avoided);
      exprt temporary;
      new_temporary(expr.source_location(), expr.type(), expr, temporary);
      expr.swap(temporary);
      expr.set(ID_C_lvalue, true);
    }
    else
      return false;
  }
 
  if(
    expr.get_bool(ID_C_lvalue) ||
    reference_type.base_type().get_bool(ID_C_constant))
  {
    if(reference_compatible(expr, reference_type, rank))
    {
      if(!expr.get_bool(ID_C_lvalue))
      {
        // create temporary object
        side_effect_exprt tmp{
          ID_temporary_object,
          {std::move(expr)},
          reference_type.base_type(),
          expr.source_location()};
        tmp.set(ID_mode, ID_cpp);
        expr.swap(tmp);
      }
 
      {
        address_of_exprt tmp(expr, ::reference_type(expr.type()));
        tmp.add_source_location()=expr.source_location();
        new_expr.swap(tmp);
      }
 
      if(expr.type() != reference_type.base_type())
      {
        c_qualifierst qual_from;
        qual_from.read(expr.type());
        new_expr = typecast_exprt::conditional_cast(new_expr, reference_type);
        qual_from.write(to_reference_type(new_expr.type()).base_type());
      }
 
      return true;
    }
 
    rank=backup_rank;
  }
 
  // conversion operators
  if(expr.type().id() == ID_struct_tag)
  {
    for(const auto &component :
        follow_tag(to_struct_tag_type(expr.type())).components())
    {
      if(component.get_bool(ID_from_base))
        continue;
 
      if(!component.get_bool(ID_is_cast_operator))
        continue;
 
      const code_typet &component_type = to_code_type(component.type());
 
      // otherwise it cannot bind directly (not an lvalue)
      if(!is_reference(component_type.return_type()))
        continue;
 
      DATA_INVARIANT(
        component_type.parameters().size() == 1, "exactly one parameter");
 
      typet this_type =
        component_type.parameters().front().type();
      this_type.set(ID_C_reference, true);
 
      exprt this_expr(expr);
 
      this_type.set(ID_C_this, true);
 
      unsigned tmp_rank=0;
 
      exprt tmp_expr;
      if(implicit_conversion_sequence(
        this_expr, this_type, tmp_expr, tmp_rank))
      {
        // To take care of the possible virtual case,
        // we build the function as a member expression.
        const cpp_namet cpp_func_name(component.get_base_name());
 
        exprt member_func(ID_member);
        member_func.add(ID_component_cpp_name)=cpp_func_name;
        member_func.copy_to_operands(already_typechecked_exprt{expr});
 
        side_effect_expr_function_callt func_expr(
          std::move(member_func),
          {},
          uninitialized_typet{},
          expr.source_location());
        typecheck_side_effect_function_call(func_expr);
 
        // let's check if the returned value binds directly
        exprt returned_value=func_expr;
        add_implicit_dereference(returned_value);
 
        if(
          returned_value.get_bool(ID_C_lvalue) &&
          reference_compatible(returned_value, reference_type, rank))
        {
          // returned values are lvalues in case of references only
          DATA_INVARIANT(
            is_reference(to_dereference_expr(returned_value).op().type()),
            "the returned value must be pointer to reference");
 
          new_expr = to_multi_ary_expr(returned_value).op0();
 
          if(returned_value.type() != reference_type.base_type())
          {
            c_qualifierst qual_from;
            qual_from.read(returned_value.type());
            make_ptr_typecast(new_expr, reference_type);
            qual_from.write(to_reference_type(new_expr.type()).base_type());
          }
          rank+=4+tmp_rank;
          return true;
        }
      }
    }
  }
 
  // No temporary allowed for `this'
  if(reference_type.get_bool(ID_C_this))
    return false;
 
  if(
    !reference_type.base_type().get_bool(ID_C_constant) ||
    reference_type.base_type().get_bool(ID_C_volatile))
    return false;
 
  // TODO: handle the case for implicit parameters
  if(
    !reference_type.base_type().get_bool(ID_C_constant) &&
    !expr.get_bool(ID_C_lvalue))
    return false;
 
  exprt arg_expr=expr;
 
  if(arg_expr.type().id() == ID_struct_tag)
  {
    // required to initialize the temporary
    arg_expr.set(ID_C_lvalue, true);
  }
 
  if(user_defined_conversion_sequence(
       arg_expr, reference_type.base_type(), new_expr, rank))
  {
    address_of_exprt tmp(new_expr, ::reference_type(new_expr.type()));
    tmp.add_source_location()=new_expr.source_location();
    new_expr.swap(tmp);
    return true;
  }
 
  rank=backup_rank;
  if(standard_conversion_sequence(
       expr, reference_type.base_type(), new_expr, rank))
  {
    {
      // create temporary object
      side_effect_exprt tmp(
        ID_temporary_object,
        reference_type.base_type(),
        expr.source_location());
      tmp.set(ID_mode, ID_cpp);
      // tmp.set(ID_C_lvalue, true);
      tmp.add_to_operands(std::move(new_expr));
      new_expr.swap(tmp);
    }
 
    address_of_exprt tmp(new_expr, pointer_type(new_expr.type()));
    tmp.type().set(ID_C_reference, true);
    tmp.add_source_location()=new_expr.source_location();
 
    new_expr=tmp;
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::implicit_conversion_sequence(
  const exprt &expr,
  const typet &type,
  exprt &new_expr,
  unsigned &rank)
{
  unsigned backup_rank=rank;
 
  exprt e=expr;
  add_implicit_dereference(e);
 
  if(is_reference(type))
  {
    if(!reference_binding(e, to_reference_type(type), new_expr, rank))
      return false;
 
    #if 0
    simplify_exprt simplify(*this);
    simplify.simplify(new_expr);
    new_expr.type().set(ID_C_reference, true);
    #endif
  }
  else if(!standard_conversion_sequence(e, type, new_expr, rank))
  {
    rank=backup_rank;
    if(!user_defined_conversion_sequence(e, type, new_expr, rank))
    {
      if(
        type.id() == ID_integer &&
        (expr.type().id() == ID_signedbv || expr.type().id() == ID_unsignedbv))
      {
        // This is a nonstandard implicit conversion, from
        // bit-vectors to unbounded integers.
        rank = 0;
        new_expr = typecast_exprt(expr, type);
        return true;
      }
      else if(
        (type.id() == ID_signedbv || type.id() == ID_unsignedbv) &&
        expr.type().id() == ID_integer)
      {
        // This is a nonstandard implicit conversion, from
        // unbounded integers to bit-vectors.
        rank = 0;
        new_expr = typecast_exprt(expr, type);
        return true;
      }
 
      // no conversion
      return false;
    }
 
#if 0
    simplify_exprt simplify(*this);
    simplify.simplify(new_expr);
#endif
  }
 
  return true;
}
 
bool cpp_typecheckt::implicit_conversion_sequence(
  const exprt &expr,
  const typet &type,
  exprt &new_expr)
{
  unsigned rank=0;
  return implicit_conversion_sequence(expr, type, new_expr, rank);
}
 
bool cpp_typecheckt::implicit_conversion_sequence(
  const exprt &expr,
  const typet &type,
  unsigned &rank)
{
  exprt new_expr;
  return implicit_conversion_sequence(expr, type, new_expr, rank);
}
 
void cpp_typecheckt::implicit_typecast(exprt &expr, const typet &type)
{
  exprt e=expr;
 
  if(
    e.id() == ID_initializer_list && cpp_is_pod(type) &&
    e.operands().size() == 1)
  {
    e = to_unary_expr(expr).op();
  }
 
  if(!implicit_conversion_sequence(e, type, expr))
  {
    show_instantiation_stack(error());
    error().source_location=e.find_source_location();
    error() << "invalid implicit conversion from '" << to_string(e.type())
            << "' to '" << to_string(type) << "'" << eom;
#if 0
    str << "\n " << e.type().pretty() << '\n';
    str << "\n " << type.pretty() << '\n';
#endif
    throw 0;
  }
}
 
void cpp_typecheckt::reference_initializer(
  exprt &expr,
  const reference_typet &reference_type)
{
  add_implicit_dereference(expr);
 
  unsigned rank=0;
  exprt new_expr;
  if(reference_binding(expr, reference_type, new_expr, rank))
  {
    expr.swap(new_expr);
    return;
  }
 
  error().source_location=expr.find_source_location();
  error() << "bad reference initializer" << eom;
  throw 0;
}
 
bool cpp_typecheckt::cast_away_constness(
  const typet &t1,
  const typet &t2) const
{
  PRECONDITION(t1.id() == ID_pointer && t2.id() == ID_pointer);
  typet nt1=t1;
  typet nt2=t2;
 
  if(is_reference(nt1))
    nt1.remove(ID_C_reference);
  nt1.remove(ID_to_member);
 
  if(is_reference(nt2))
    nt2.remove(ID_C_reference);
  nt2.remove(ID_to_member);
 
  // substitute final subtypes
  std::vector<typet> snt1;
  snt1.push_back(nt1);
 
  while(snt1.back().has_subtype())
  {
    snt1.reserve(snt1.size()+1);
    snt1.push_back(to_type_with_subtype(snt1.back()).subtype());
  }
 
  c_qualifierst q1;
  q1.read(snt1.back());
 
  bool_typet newnt1;
  q1.write(newnt1);
  snt1.back()=newnt1;
 
  std::vector<typet> snt2;
  snt2.push_back(nt2);
  while(snt2.back().has_subtype())
  {
    snt2.reserve(snt2.size()+1);
    snt2.push_back(to_type_with_subtype(snt2.back()).subtype());
  }
 
  c_qualifierst q2;
  q2.read(snt2.back());
 
  bool_typet newnt2;
  q2.write(newnt2);
  snt2.back()=newnt2;
 
  const std::size_t k=snt1.size() < snt2.size() ? snt1.size() : snt2.size();
 
  for(std::size_t i=k; i > 1; i--)
  {
    to_type_with_subtype(snt1[snt1.size() - 2]).subtype() =
      snt1[snt1.size() - 1];
    snt1.pop_back();
 
    to_type_with_subtype(snt2[snt2.size() - 2]).subtype() =
      snt2[snt2.size() - 1];
    snt2.pop_back();
  }
 
  exprt e1("Dummy", snt1.back());
  exprt e2;
 
  return !standard_conversion_qualification(e1, snt2.back(), e2);
}
 
bool cpp_typecheckt::const_typecast(
  const exprt &expr,
  const typet &type,
  exprt &new_expr)
{
  PRECONDITION(!is_reference(expr.type()));
 
  exprt curr_expr=expr;
 
  if(curr_expr.type().id()==ID_array)
  {
    if(type.id()==ID_pointer)
    {
      if(!standard_conversion_array_to_pointer(curr_expr, new_expr))
        return false;
    }
  }
  else if(curr_expr.type().id()==ID_code &&
          type.id()==ID_pointer)
  {
    if(!standard_conversion_function_to_pointer(curr_expr, new_expr))
        return false;
  }
  else if(curr_expr.get_bool(ID_C_lvalue))
  {
    if(!standard_conversion_lvalue_to_rvalue(curr_expr, new_expr))
      return false;
  }
  else
    new_expr=curr_expr;
 
  if(is_reference(type))
  {
    if(!expr.get_bool(ID_C_lvalue))
      return false;
 
    if(new_expr.type() != to_reference_type(type).base_type())
      return false;
 
    address_of_exprt address_of(expr, to_pointer_type(type));
    add_implicit_dereference(address_of);
    new_expr=address_of;
    return true;
  }
  else if(type.id()==ID_pointer)
  {
    if(type!=new_expr.type())
      return false;
 
    // add proper typecast
    typecast_exprt typecast_expr(expr, type);
    new_expr.swap(typecast_expr);
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::dynamic_typecast(
  const exprt &expr,
  const typet &type,
  exprt &new_expr)
{
  exprt e(expr);
 
  if(type.id()==ID_pointer)
  {
    if(e.id()==ID_dereference && e.get_bool(ID_C_implicit))
      e = to_dereference_expr(expr).pointer();
 
    if(e.type().id()==ID_pointer &&
       cast_away_constness(e.type(), type))
      return false;
  }
 
  add_implicit_dereference(e);
 
  if(is_reference(type))
  {
    if(to_reference_type(type).base_type().id() != ID_struct_tag)
      return false;
  }
  else if(type.id()==ID_pointer)
  {
    if(type.find(ID_to_member).is_not_nil())
      return false;
 
    if(to_pointer_type(type).base_type().id() == ID_empty)
    {
      if(!e.get_bool(ID_C_lvalue))
        return false;
      UNREACHABLE; // currently not supported
    }
    else if(to_pointer_type(type).base_type().id() == ID_struct_tag)
    {
      if(e.get_bool(ID_C_lvalue))
      {
        exprt tmp(e);
 
        if(!standard_conversion_lvalue_to_rvalue(tmp, e))
          return false;
      }
    }
    else return false;
  }
  else return false;
 
  return static_typecast(e, type, new_expr);
}
 
bool cpp_typecheckt::reinterpret_typecast(
  const exprt &expr,
  const typet &type,
  exprt &new_expr,
  bool check_constantness)
{
  exprt e=expr;
 
  if(check_constantness && type.id()==ID_pointer)
  {
    if(e.id()==ID_dereference && e.get_bool(ID_C_implicit))
      e = to_dereference_expr(expr).pointer();
 
    if(e.type().id()==ID_pointer &&
       cast_away_constness(e.type(), type))
      return false;
  }
 
  add_implicit_dereference(e);
 
  if(!is_reference(type))
  {
    exprt tmp;
 
    if(e.id()==ID_code)
    {
      if(standard_conversion_function_to_pointer(e, tmp))
         e.swap(tmp);
      else
        return false;
    }
 
    if(e.type().id()==ID_array)
    {
      if(standard_conversion_array_to_pointer(e, tmp))
        e.swap(tmp);
      else
        return false;
    }
 
    if(e.get_bool(ID_C_lvalue))
    {
      if(standard_conversion_lvalue_to_rvalue(e, tmp))
        e.swap(tmp);
      else
        return false;
    }
  }
 
  if(e.type().id()==ID_pointer &&
     (type.id()==ID_unsignedbv || type.id()==ID_signedbv))
  {
    // pointer to integer, always ok
    new_expr = typecast_exprt::conditional_cast(e, type);
    return true;
  }
 
  if(
    (e.type().id() == ID_unsignedbv || e.type().id() == ID_signedbv ||
     e.type().id() == ID_c_bool || e.is_boolean()) &&
    type.id() == ID_pointer && !is_reference(type))
  {
    // integer to pointer
    if(simplify_expr(e, *this).is_zero())
    {
      // NULL
      new_expr=e;
      new_expr.set(ID_value, ID_NULL);
      new_expr.type()=type;
    }
    else
    {
      new_expr = typecast_exprt::conditional_cast(e, type);
    }
    return true;
  }
 
  if(e.type().id()==ID_pointer &&
     type.id()==ID_pointer &&
     !is_reference(type))
  {
    // pointer to pointer: we ok it all.
    // This is more generous than the standard.
    new_expr = typecast_exprt::conditional_cast(expr, type);
    return true;
  }
 
  if(is_reference(type) && e.get_bool(ID_C_lvalue))
  {
    new_expr = typecast_exprt::conditional_cast(address_of_exprt(e), type);
    return true;
  }
 
  return false;
}
 
bool cpp_typecheckt::static_typecast(
  const exprt &expr, // source expression
  const typet &type, // destination type
  exprt &new_expr,
  bool check_constantness)
{
  exprt e=expr;
 
  if(check_constantness && type.id()==ID_pointer)
  {
    if(e.id()==ID_dereference && e.get_bool(ID_C_implicit))
      e = to_dereference_expr(expr).pointer();
 
    if(e.type().id()==ID_pointer &&
       cast_away_constness(e.type(), type))
      return false;
  }
 
  add_implicit_dereference(e);
 
  if(type.get_bool(ID_C_reference))
  {
    const reference_typet &reference_type = to_reference_type(type);
    unsigned rank=0;
    if(reference_binding(e, reference_type, new_expr, rank))
      return true;
 
    typet subto = reference_type.base_type();
    typet from = e.type();
 
    if(subto.id() == ID_struct_tag && from.id() == ID_struct_tag)
    {
      if(!expr.get_bool(ID_C_lvalue))
        return false;
 
      c_qualifierst qual_from;
      qual_from.read(e.type());
 
      c_qualifierst qual_to;
      qual_to.read(subto);
 
      if(!qual_to.is_subset_of(qual_from))
        return false;
 
      const struct_typet &from_struct = follow_tag(to_struct_tag_type(from));
      const struct_typet &subto_struct = follow_tag(to_struct_tag_type(subto));
 
      if(subtype_typecast(subto_struct, from_struct))
      {
        if(e.id()==ID_dereference)
        {
          make_ptr_typecast(to_dereference_expr(e).pointer(), reference_type);
          new_expr.swap(to_dereference_expr(e).pointer());
          return true;
        }
 
        exprt address_of=address_of_exprt(e);
        make_ptr_typecast(address_of, reference_type);
        new_expr.swap(address_of);
        return true;
      }
    }
    return false;
  }
 
  if(type.id()==ID_empty)
  {
    new_expr = typecast_exprt::conditional_cast(e, type);
    return true;
  }
 
  // int/enum to enum
  if(type.id()==ID_c_enum_tag &&
     (e.type().id()==ID_signedbv ||
      e.type().id()==ID_unsignedbv ||
      e.type().id()==ID_c_enum_tag))
  {
    new_expr = typecast_exprt::conditional_cast(e, type);
    new_expr.remove(ID_C_lvalue);
    return true;
  }
 
  if(implicit_conversion_sequence(e, type, new_expr))
  {
    if(!cpp_is_pod(type))
    {
      exprt temporary;
      new_temporary(
        e.source_location(),
        type,
        already_typechecked_exprt{new_expr},
        temporary);
      new_expr.swap(temporary);
    }
    else
    {
      // try to avoid temporary
      new_expr.set(ID_C_temporary_avoided, true);
      if(new_expr.get_bool(ID_C_lvalue))
        new_expr.remove(ID_C_lvalue);
    }
 
    return true;
  }
 
  if(type.id()==ID_pointer && e.type().id()==ID_pointer)
  {
    const pointer_typet &pointer_type = to_pointer_type(type);
    if(type.find(ID_to_member).is_nil() && e.type().find(ID_to_member).is_nil())
    {
      typet to = pointer_type.base_type();
      typet from = to_pointer_type(e.type()).base_type();
 
      if(from.id()==ID_empty)
      {
        new_expr = typecast_exprt::conditional_cast(e, type);
        return true;
      }
 
      if(to.id() == ID_struct_tag && from.id() == ID_struct_tag)
      {
        if(e.get_bool(ID_C_lvalue))
        {
          exprt tmp(e);
          if(!standard_conversion_lvalue_to_rvalue(tmp, e))
            return false;
        }
 
        const struct_typet &from_struct = follow_tag(to_struct_tag_type(from));
        const struct_typet &to_struct = follow_tag(to_struct_tag_type(to));
        if(subtype_typecast(to_struct, from_struct))
        {
          make_ptr_typecast(e, pointer_type);
          new_expr.swap(e);
          return true;
        }
      }
 
      return false;
    }
    else if(
      type.find(ID_to_member).is_not_nil() &&
      e.type().find(ID_to_member).is_not_nil())
    {
      if(pointer_type.base_type() != to_pointer_type(e.type()).base_type())
        return false;
 
      const struct_typet &from_struct = follow_tag(to_struct_tag_type(
        static_cast<const typet &>(e.type().find(ID_to_member))));
 
      const struct_typet &to_struct = follow_tag(to_struct_tag_type(
        static_cast<const typet &>(type.find(ID_to_member))));
 
      if(subtype_typecast(from_struct, to_struct))
      {
        new_expr = typecast_exprt::conditional_cast(e, type);
        return true;
      }
    }
    else if(
      type.find(ID_to_member).is_nil() &&
      e.type().find(ID_to_member).is_not_nil())
    {
      if(pointer_type.base_type() != to_pointer_type(e.type()).base_type())
      {
        return false;
      }
 
      const struct_tag_typet &from_struct_tag = to_struct_tag_type(
        static_cast<const typet &>(e.type().find(ID_to_member)));
 
      new_expr = e;
      new_expr.type().add(ID_to_member) = from_struct_tag;
 
      return true;
    }
    else
      return false;
  }
 
  return false;
}