Class: Idl::BinaryExpressionAst

Inherits:
AstNode
  • Object
show all
Includes:
Rvalue
Defined in:
lib/idlc/ast.rb,
lib/idlc/passes/prune.rb,
lib/idlc/passes/gen_adoc.rb

Constant Summary collapse

LOGICAL_OPS = 
["==", "!=", ">", "<", ">=", "<=", "&&", "||"].freeze
BIT_OPS = 
["&", "|", "^"].freeze
ARITH_OPS = 
["+", "-", "/", "*", "%", "<<", ">>", ">>>", "`+", "`-", "`*", "`<<"].freeze
OPS = 
(LOGICAL_OPS + ARITH_OPS + BIT_OPS).freeze

Constants inherited from AstNode

AstNode::Bits1Type, AstNode::Bits32Type, AstNode::Bits64Type, AstNode::BoolType, AstNode::ConstBoolType, AstNode::PossiblyUnknownBits1Type, AstNode::PossiblyUnknownBits32Type, AstNode::PossiblyUnknownBits64Type, AstNode::ReachableFunctionCacheType, AstNode::StringType, AstNode::VoidType

Instance Attribute Summary collapse

Attributes inherited from AstNode

#children, #input, #interval, #parent

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Rvalue

#truncate, #values

Methods inherited from AstNode

#always_terminates?, #declaration?, #executable?, extract_base_var_name, #find_ancestor, #find_dst_registers, #find_referenced_csrs, #find_src_registers, #freeze_tree, #gen_option_adoc, #input_file, input_from_source_yaml, #inspect, #internal_error, interval_from_source_yaml, #lineno, #lines_around, #nullify_assignments, #pass_find_return_values, #path, #print_ast, #reachable_exceptions, #reachable_functions, #set_input_file, #set_input_file_unless_already_set, #source_line_file_offsets, #source_starting_offset, #source_yaml, #starting_line, #text_value, #truncation_warn, #type_error, #unindent, value_else, #value_else, value_error, #value_error, value_try, #value_try, write_back_nested

Constructor Details

#initialize(input, interval, lhs, op, rhs) ⇒ BinaryExpressionAst

create a new, left-recursion-fixed, binary expression



4530
4531
4532
4533
4534
 
# File 'lib/idlc/ast.rb', line 4530

def initialize(input, interval, lhs, op, rhs)
  super(input, interval, [lhs, rhs])
  @op = op.to_s
  type_error "Bad op '#{@op}'" unless OPS.include?(@op)
end

Instance Attribute Details

#op ⇒ Object (readonly)

returns the operator as a string



5339
5340
5341
 
# File 'lib/idlc/ast.rb', line 5339

def op
  @op
end

Class Method Details

.from_h(yaml, source_mapper) ⇒ Object 



4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
 
# File 'lib/idlc/ast.rb', line 4582

def self.from_h(yaml, source_mapper)
  raise "Bad YAML" unless yaml.key?("kind") && yaml.fetch("kind") == "binary_operator_expr"

  input = input_from_source_yaml(yaml.fetch("source"), source_mapper)
  interval = interval_from_source_yaml(yaml.fetch("source"))
  BinaryExpressionAst.new(
    input, interval,
    T.cast(AstNode.from_h(yaml.fetch("lhs"), source_mapper), RvalueAst),
    yaml.fetch("op"),
    T.cast(AstNode.from_h(yaml.fetch("rhs"), source_mapper), RvalueAst)
  )
end

Instance Method Details

#bits_needed(value, signed) ⇒ Integer

Returns the number of bits needed to represent value in two’s complement.

Parameters:

  • value (Integer) —

    the value

  • signed (Boolean) —

    if true, return the number of bits needed if the value is a signed type

Returns:

  • (Integer) —

    the number of bits needed to represent value in two’s complement



4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
 
# File 'lib/idlc/ast.rb', line 4800

def bits_needed(value, signed)
  if signed
    case value
    when 0
      1
    when 1
      2
    else
      if value > 0
        # need bit_legnth plus a sign bit
        bits = value.bit_length + 1
      else
        # need bit_length plus a sign bit, unless value is a power of 2
        if (value.abs & (value.abs - 1)) == 0
          value.bit_length
        else
          value.bit_length + 1
        end
      end
    end
  else
    internal_error "unsigned value is negative" if value < 0

    value == 0 ? 1 : value.bit_length
  end
end

#const_eval?(symtab) ⇒ Boolean

Returns:

  • (Boolean) 


4520
4521
4522
4523
4524
 
# File 'lib/idlc/ast.rb', line 4520

def const_eval?(symtab)
  # can't check for short-circuit here unless we also evaluate values during the const_eval pass
  # thus, conservative assume there is no short-circuiting
  lhs.const_eval?(symtab) && rhs.const_eval?(symtab)
end

#gen_adoc(indent = 0, indent_spaces: 2) ⇒ Object 



240
241
242
 
# File 'lib/idlc/passes/gen_adoc.rb', line 240

def gen_adoc(indent = 0, indent_spaces: 2)
  "#{' ' * indent}#{lhs.gen_adoc(0, indent_spaces:)} #{op.sub("+", "pass:[+]").sub("`", "pass:[`]")} #{rhs.gen_adoc(0, indent_spaces:)}"
end

#invert(symtab) ⇒ BinaryExpressionAst

Returns this expression, but with an inverted condition.

Returns:



4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
 
# File 'lib/idlc/ast.rb', line 4537

def invert(symtab)
  unless symtab.nil?
    type_error "Not a boolean operator" unless type(symtab).kind == :boolean
  end

  inverted_op_map = {
    "==" => "!=",
    "!=" => "==",
    ">" => "<=",
    "<" => ">=",
    "<=" => ">",
    ">=" => "<"
  }

  if inverted_op_map.key?(op)
    BinaryExpressionAst.new(input, interval, lhs.dup, inverted_op_map[op], rhs.dup)
  else
    UnaryOperatorExpressionAst.new(input, interval, "!", self.dup)
  end
  # else
  #   # harder case of && / ||
  #   if op == "&&"
  #     inverted_text = "!#{lhs.to_idl} || !#{rhs.to_idl}"
  #     BinaryExpressionAst.new(inverted_text, 0..(inverted_text.size - 1), UnaryOperatorExpressionAst.new())
  #   elsif op == "||"
  #     inverted_text = "!#{lhs.to_idl} && !#{rhs.to_idl}"
  #   end
end

#lhs ⇒ Object 



4526
 
# File 'lib/idlc/ast.rb', line 4526

def lhs = @children[0]

#max_value(symtab) ⇒ Object 



4827
4828
4829
4830
4831
4832
4833
4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
 
# File 'lib/idlc/ast.rb', line 4827

def max_value(symtab)
  lhs_max_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    lhs_max_value = lhs.value(symtab)
  end
  value_else(value_result) do
    lhs_max_value = lhs.max_value(symtab)
  end

  lhs_min_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    lhs_min_value = lhs.value(symtab)
  end
  value_else(value_result) do
    lhs_min_value = lhs.min_value(symtab)
  end

  rhs_max_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    rhs_max_value = rhs.value(symtab)
  end
  value_else(value_result) do
    rhs_max_value = rhs.max_value(symtab)
  end
  rhs_min_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    rhs_min_value = rhs.value(symtab)
  end
  value_else(value_result) do
    rhs_min_value = rhs.min_value(symtab)
  end

  max_value =
    case @op
    when "+"
      return :unknown if [lhs_max_value, rhs_max_value].include?(:unknown)

      sum = T.cast(lhs_max_value, Integer) + T.cast(rhs_max_value, Integer)
      # convert to unsigned if needed
      sum = sum & ((1 << type(symtab).width) - 1) if sum < 0 && !type(symtab).signed?

      # check for truncation
      sum_bits_needed = bits_needed(sum, type(symtab).signed?)
      if type(symtab).width != :unknown
        return sum if sum_bits_needed <= type(symtab).width

        trunc_sum = truncate(sum, type(symtab).width, type(symtab).signed?)
        truncation_warn "result is truncated from #{sum} to #{trunc_sum}. Did you mean to use the widening additio
        n operator (`+)?"
        return trunc_sum
      else
        # sum width isn't known...we might still be able to know that it fits if the sum would fit
        # in lhs or rhs
        return sum if (lhs.type(symtab).width != :unknown) && (lhs.type(symtab).width >= sum_bits_needed)
        return sum if (rhs.type(symtab).width != :unknown) && (rhs.type(symtab).width >= sum_bits_needed)

        return :unknown # Cannot know if sum would be truncated
      end
    when "`+"
      return :unknown if [lhs_max_value, rhs_max_value].include?(:unknown)

      sum = T.cast(lhs_max_value, Integer) + T.cast(rhs_max_value, Integer)
      # convert to unsigned if needed
      sum = sum & ((1 << type(symtab).width) - 1) if sum < 0 && !type(symtab).signed?

      return sum
    when "-"
      return :unknown if [lhs_max_value, rhs_min_value].include?(:unknown)

      diff = T.cast(lhs_max_value, Integer) - T.cast(rhs_min_value, Integer)
      diff = diff & ((1 << type(symtab).width) - 1) if diff < 0 && !type(symtab).signed?
      diff_bits_needed = bits_needed(diff, type(symtab).signed?)

      if type(symtab).width != :unknown
        return diff if diff_bits_needed <= type(symtab).width

        trunc_diff = truncate(diff, type(symtab).width, type(symtab).signed?)
        truncation_warn "result is truncated from #{diff} to #{trunc_diff}. Did you mean to use the widening subtraction operator (`-)?"
        return trunc_diff
      else
        # diff width isn't known...we might still be able to know that it fits if the sum would fit
        # in lhs or rhs
        return diff if (lhs.type(symtab).width != :unknown) && (lhs.type(symtab).width >= diff_bits_needed)
        return diff if (rhs.type(symtab).width != :unknown) && (rhs.type(symtab).width >= diff_bits_needed)

        return :unknown # Cannot know if sum would be truncated
      end
    when "`-"
      return :unknown if [lhs_max_value, rhs_min_value].include?(:unknown)

      diff = T.cast(lhs_max_value, Integer) - T.cast(rhs_min_value, Integer)
      diff = diff & ((1 << type(symtab).width) - 1) if diff < 0 && !type(symtab).signed?

      return diff
    when "*"
      # max could be multiplying the mins if both are negative
      return :unknown if [lhs_max_value, rhs_max_value].include?(:unknown)

      if lhs.type(symtab).signed? && rhs.type(symtab).signed?
        return :unknown if [lhs_min_value, rhs_min_value].include?(:unknown)
      end

      prod = T.cast(lhs_max_value, Integer) * T.cast(rhs_max_value, Integer)
      if ![lhs_min_value, rhs_min_value].include?(:unknown) && ((T.cast(lhs_min_value, Integer) * T.cast(rhs_min_value, Integer)) > prod)
        prod = T.cast(lhs_min_value, Integer) * T.cast(rhs_min_value, Integer)
      end
      prod = prod & ((1 << type(symtab).width) - 1) if prod < 0 && !type(symtab).signed?

      # check for truncation
      prod_bits_needed = bits_needed(prod, type(symtab).signed?)
      if (type(symtab).width != :unknown)
        return prod if prod_bits_needed <= type(symtab).width

        trunc_prod = truncate(prod, type(symtab).width, type(symtab).signed?)
        truncation_warn "result is truncated from #{prod} to #{trunc_prod}. Did you mean to use the widening multiplication operator (`*)?"
        return trunc_prod
      else
        # prod width isn't known...we might still be able to know that it fits if the sum would fit
        # in lhs or rhs
        return prod if (lhs.type(symtab).width != :unknown) && (lhs.type(symtab).width >= prod_bits_needed)
        return prod if (rhs.type(symtab).width != :unknown) && (rhs.type(symtab).width >= prod_bits_needed)

        return :unknown # Cannot know if sum would be truncated
      end
    when "`*"
      # max could be multiplying the mins if both are negative
      return :unknown if [lhs_max_value, rhs_max_value].include?(:unknown)

      if lhs.type(symtab).signed? && rhs.type(symtab).signed?
        return :unknown if [lhs_min_value, rhs_min_value].include?(:unknown)
      end

      prod = T.cast(lhs_max_value, Integer) * T.cast(rhs_max_value, Integer)
      if ![lhs_min_value, rhs_min_value].include?(:unknown) && ((T.cast(lhs_min_value, Integer) * T.cast(rhs_min_value, Integer)) > prod)
        prod = T.cast(lhs_min_value, Integer) * T.cast(rhs_min_value, Integer)
      end

      prod
    end
  raise "TODO: #{op}" if max_value.nil?
  max_value
end

#min_value(symtab) ⇒ Object 



4970
4971
4972
4973
4974
4975
4976
4977
4978
4979
4980
4981
4982
4983
4984
4985
4986
4987
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997
4998
4999
5000
5001
5002
5003
5004
5005
5006
5007
5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
 
# File 'lib/idlc/ast.rb', line 4970

def min_value(symtab)
  lhs_max_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    lhs_max_value = lhs.value(symtab)
  end
  value_else(value_result) do
    lhs_max_value = lhs.max_value(symtab)
  end

  lhs_min_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    lhs_min_value = lhs.value(symtab)
  end
  value_else(value_result) do
    lhs_min_value = lhs.min_value(symtab)
  end

  rhs_max_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    rhs_max_value = rhs.value(symtab)
  end
  value_else(value_result) do
    rhs_max_value = rhs.max_value(symtab)
  end

  rhs_min_value = T.let(:unknown, T.any(Symbol, Integer))
  value_result = value_try do
    rhs_min_value = rhs.value(symtab)
  end
  value_else(value_result) do
    rhs_min_value = rhs.min_value(symtab)
  end

  case op
  when "+"
    return :unknown if [lhs_min_value, rhs_min_value].include?(:unknown)

    sum = T.cast(lhs_min_value, Integer) + T.cast(rhs_min_value, Integer)
    sum = sum & ((1 << type(symtab).width) - 1) if sum < 0 && !type(symtab).signed?

    # check for truncation
    sum_bits_needed = bits_needed(sum, type(symtab).signed?)
    if type(symtab).width != :unknown
      return sum if sum_bits_needed <= type(symtab).width

      trunc_sum = truncate(sum, type(symtab).width, type(symtab).signed?)
      truncation_warn "result is truncated from #{sum} to #{trunc_sum}. Did you mean to use the widening addition operator (`+)?"
      return trunc_sum
    else
      # sum width isn't known...we might still be able to know that it fits if the sum would fit
      # in lhs or rhs
      return sum if (lhs.type(symtab).width != :unknown) && (lhs.type(symtab).width >= sum_bits_needed)
      return sum if (rhs.type(symtab).width != :unknown) && (rhs.type(symtab).width >= sum_bits_needed)

      return :unknown # Cannot know if sum would be truncated
    end
  when "`+"
    return :unknown if [lhs_min_value, rhs_min_value].include?(:unknown)

    sum = T.cast(lhs_min_value, Integer) + T.cast(rhs_min_value, Integer)
    sum = sum & ((1 << type(symtab).width) - 1) if sum < 0 && !type(symtab).signed?

    return sum
  when "-"
    return :unknown if [lhs_min_value, rhs_max_value].include?(:unknown)

    diff = T.cast(lhs_min_value, Integer) - T.cast(rhs_max_value, Integer)
    diff = diff & ((1 << type(symtab).width) - 1) if diff < 0 && !type(symtab).signed?

    diff_bits_needed = bits_needed(diff, type(symtab).signed?)
    if type(symtab).width != :unknown
      return diff if diff_bits_needed <= type(symtab).width

      trunc_diff = truncate(diff, type(symtab).width, type(symtab).signed?)
      truncation_warn "result is truncated from #{diff} to #{trunc_diff}. Did you mean to use the widening subtraction operator (`-)?"
      return trunc_diff
    else
      # diff width isn't known...we might still be able to know that it fits if the sum would fit
      # in lhs or rhs
      return diff if (lhs.type(symtab).width != :unknown) && (lhs.type(symtab).width >= diff_bits_needed)
      return diff if (rhs.type(symtab).width != :unknown) && (rhs.type(symtab).width >= diff_bits_needed)

      return :unknown # Cannot know if sum would be truncated
    end
  when "`-"
    return :unknown if [lhs_min_value, rhs_max_value].include?(:unknown)

    diff = T.cast(lhs_min_value, Integer) - T.cast(rhs_max_value, Integer)
    diff = diff & ((1 << type(symtab).width) - 1) if diff < 0 && !type(symtab).signed?

    return diff
  when "*"
    # min could be any combination of mutliplying min/max if numbers are signed
    return :unknown if [lhs_min_value, rhs_min_value].include?(:unknown)

    if lhs.type(symtab).signed?
      return :unknown if rhs_max_value == :unknown
    end

    if rhs.type(symtab).signed?
      return :unknown if lhs_max_value == :unknown
    end

    prod = T.cast(lhs_min_value, Integer) * T.cast(rhs_min_value, Integer)
    prod = T.cast(lhs_min_value, Integer) * T.cast(rhs_max_value, Integer) if (rhs_max_value != :unknown) && ((T.cast(lhs_min_value, Integer) * T.cast(rhs_max_value, Integer)) < prod)
    prod = T.cast(lhs_max_value, Integer) * T.cast(rhs_min_value, Integer) if (lhs_max_value != :unknown) && ((T.cast(lhs_max_value, Integer) * T.cast(rhs_min_value, Integer)) < prod)
    prod = T.cast(lhs_max_value, Integer) * T.cast(rhs_max_value, Integer) if (![lhs_max_value, rhs_min_value].include?(:unknown)) && ((T.cast(lhs_max_value, Integer) * T.cast(rhs_max_value, Integer)) < prod)
    prod = prod & ((1 << type(symtab).width) - 1) if prod < 0 && !type(symtab).signed?

    # check for truncation
    prod_bits_needed = bits_needed(prod, type(symtab).signed?)
    if (type(symtab).width != :unknown)
      return prod if prod_bits_needed <= type(symtab).width

      trunc_prod = truncate(prod, type(symtab).width, type(symtab).signed?)
      truncation_warn "result is truncated from #{prod} to #{trunc_prod}. Did you mean to use the widening multiplication operator (`*)?"
      return trunc_prod
    else
      # sum width isn't known...we might still be able to know that it fits if the sum would fit
      # in lhs or rhs
      return prod if (lhs.type(symtab).width != :unknown) && (lhs.type(symtab).width >= prod_bits_needed)
      return prod if (rhs.type(symtab).width != :unknown) && (rhs.type(symtab).width >= prod_bits_needed)

      return :unknown # Cannot know if sum would be truncated
    end
  when "`*"
    # max could be multiplying the mins if both are negative
    return :unknown if [lhs_min_value, rhs_min_value].include?(:unknown)

    if lhs.type(symtab).signed?
      return :unknown if rhs_max_value == :unknown
    end

    if rhs.type(symtab).signed?
      return :unknown if lhs_max_value == :unknown
    end

    prod = T.cast(lhs_min_value, Integer) * T.cast(rhs_min_value, Integer)
    prod = T.cast(lhs_min_value, Integer) * T.cast(rhs_max_value, Integer) if (rhs_max_value != :unknown) && ((T.cast(lhs_min_value, Integer) * T.cast(rhs_max_value, Integer)) < prod)
    prod = T.cast(lhs_max_value, Integer) * T.cast(rhs_min_value, Integer) if (lhs_max_value != :unknown) && ((T.cast(lhs_max_value, Integer) * T.cast(rhs_min_value, Integer)) < prod)
    prod = T.cast(lhs_max_value, Integer) * T.cast(rhs_max_value, Integer) if (![lhs_max_value, rhs_min_value].include?(:unknown)) && ((T.cast(lhs_max_value, Integer) * T.cast(rhs_max_value, Integer)) < prod)
    prod = prod & ((1 << type(symtab).width) - 1) if prod < 0 && !type(symtab).signed?

    return prod
  else
    raise "TODO: op '#{op}'"
  end
end

#prune(symtab, forced_type: nil) ⇒ Object 



393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
 
# File 'lib/idlc/passes/prune.rb', line 393

def prune(symtab, forced_type: nil)
  value_try do
    val = value(symtab)
    if val.is_a?(Integer)
      # can only prune if the bit width of the integer is known
      if type(symtab).width == :unknown
        value_error "Unknown width"
      end
    end
    return PruneHelpers.create_literal(symtab, val, type(symtab), forced_type: forced_type || type(symtab))
  end
  # fall through

  lhs_value = nil
  rhs_value = nil

  value_try do
    lhs_value = lhs.value(symtab)
  end

  value_try do
    rhs_value = rhs.value(symtab)
  end

  if op == "&&"
    raise "pruning error" unless forced_type.nil? || forced_type.kind == :boolean
    if !lhs_value.nil? && !rhs_value.nil?
      PruneHelpers.create_bool_literal(lhs_value && rhs_value)
    elsif lhs_value == true
      rhs.prune(symtab)
    elsif rhs_value == true
      lhs.prune(symtab)
    elsif lhs_value == false || rhs_value == false
      PruneHelpers.create_bool_literal(false)
    else
      BinaryExpressionAst.new(input, interval, lhs.prune(symtab), @op, rhs.prune(symtab))
    end
  elsif op == "||"
    raise "pruning error" unless forced_type.nil? || forced_type.kind == :boolean
    if !lhs_value.nil? && !rhs_value.nil?
      PruneHelpers.create_bool_literal(lhs_value || rhs_value)
    elsif lhs_value == true || rhs_value == true
      PruneHelpers.create_bool_literal(true)
    elsif lhs_value == false
      rhs.prune(symtab)
    elsif rhs_value == false
      lhs.prune(symtab)
    else
      BinaryExpressionAst.new(input, interval, lhs.prune(symtab), @op, rhs.prune(symtab))
    end
  elsif op == "&"
    if lhs_value == 0 && type(symtab).width != :unknown
      PruneHelpers.create_literal(symtab, 0, forced_type: forced_type || type(symtab))
    elsif (rhs.type(symtab).width != :unknown) && lhs_value == ((1 << rhs.type(symtab).width) - 1) && type(symtab).width != :unknown
      # rhs idenntity
      rhs.prune(symtab, forced_type:)
    elsif rhs_value == 0 && type(symtab).width != :unknown
      # anything & 0 == 0
      PruneHelpers.create_literal(symtab, 0, forced_type: forced_type || type(symtab))
    elsif (lhs.type(symtab).width != :unknown) && rhs_value == ((1 << lhs.type(symtab).width) - 1) && type(symtab).width != :unknown
      # lhs identity
      lhs.prune(symtab, forced_type:)
    else
      # neither lhs nor rhs were prunable
      BinaryExpressionAst.new(input, interval, lhs.prune(symtab, forced_type:), @op, rhs.prune(symtab, forced_type:))
    end
  elsif op == "|"
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)

    if lhs_value == 0
      # rhs idenntity
      rhs.prune(symtab, forced_type:)
    elsif rhs_type.width != :unknown && lhs_value == ((1 << rhs.type(symtab).width) - 1) && type(symtab).width != :unknown
      # ~0 | anything == ~0
      PruneHelpers.create_literal(symtab, lhs_value, forced_type: forced_type || type(symtab))
    elsif rhs_value == 0 && type(symtab).width != :unknown
      # lhs identity
      lhs.prune(symtab, forced_type:)
    elsif lhs_type.width != :unknown && rhs_value == ((1 << lhs.type(symtab).width) - 1) && type(symtab).width != :unknown
      # anything | ~0 == ~0
      PruneHelpers.create_literal(symtab, rhs_value, forced_type: forced_type || type(symtab))
    else
      # neither lhs nor rhs were prunable
      BinaryExpressionAst.new(input, interval, lhs.prune(symtab, forced_type:), @op, rhs.prune(symtab, forced_type:))
    end
  elsif op == "=="
    if !lhs_value.nil? && !rhs_value.nil?
      PruneHelpers.create_bool_literal(lhs_value == rhs_value)
    else
      BinaryExpressionAst.new(input, interval, lhs.prune(symtab), @op, rhs.prune(symtab))
    end
  else
    BinaryExpressionAst.new(input, interval, lhs.prune(symtab), @op, rhs.prune(symtab))
  end
end

#rhs ⇒ Object 



4527
 
# File 'lib/idlc/ast.rb', line 4527

def rhs = @children[1]

#to_h ⇒ Object 



4573
4574
4575
4576
4577
4578
4579
 
# File 'lib/idlc/ast.rb', line 4573

def to_h = {
  "kind" => "binary_operator_expr",
  "op" => op,
  "lhs" => lhs.to_h,
  "rhs" => rhs.to_h,
  "source" => source_yaml
}

#to_idl ⇒ Object 



4568
4569
4570
 
# File 'lib/idlc/ast.rb', line 4568

def to_idl
  "(#{lhs.to_idl} #{op} #{rhs.to_idl})"
end

#type(symtab) ⇒ Type

Given a specific symbol table, return the type of this node.

Should not be called until #type_check is called with the same arguments

Parameters:

Returns:

  • (Type) —

    The type of the node

Raises:



4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
 
# File 'lib/idlc/ast.rb', line 4596

def type(symtab)

  if op == "||" || op == "&&"
    # see if we can short circuit
    lhs_value = T.let(nil, T.untyped)
    value_try do
      lhs_value = lhs.value(symtab)
    end
    rhs_value = T.let(nil, T.untyped)
    value_try do
      rhs_value = rhs.value(symtab)
    end

    if (lhs_value == true || lhs_value == false) && (rhs_value == true || rhs_value == false)
      # both are known and boolean. nothing more to check
      return ConstBoolType
    elsif lhs_value == false && op == "||"
      rhs_type = rhs.type(symtab)
      return rhs_type.const? ? ConstBoolType : BoolType
    elsif lhs_value == true && op == "||"
      return ConstBoolType
    elsif lhs_value == true && op == "&&"
      rhs_type = rhs.type(symtab)
      return rhs_type.const? ? ConstBoolType : BoolType
    elsif lhs_value == false && op == "&&"
      return ConstBoolType
    elsif rhs_value == false && op == "||"
      lhs_type = lhs.type(symtab)
      return lhs_type.const? ? ConstBoolType : BoolType
    elsif rhs_value == true && op == "||"
      return ConstBoolType
    elsif rhs_value == true && op == "&&"
      lhs_type = lhs.type(symtab)
      return lhs_type.const? ? ConstBoolType : BoolType
    elsif rhs_value == false && op == "&&"
      return ConstBoolType
    end
  end

  lhs_type = lhs.type(symtab)
  rhs_type = rhs.type(symtab)

  qualifiers = []
  qualifiers << :const if lhs_type.const? && rhs_type.const?

  if LOGICAL_OPS.include?(op)
    if qualifiers.include?(:const)
      ConstBoolType
    else
      BoolType
    end
  elsif ["<<", ">>", ">>>"].include?(op)
    # type of non-widening left/right shift is the type of the left hand side
    lhs_type
  elsif op == "`<<"
    qualifiers << :known if lhs_type.known? && rhs_type.known?
    value_result = value_try do
      # if shift amount is known, then the result width is increased by the shift
      # otherwise, the result is the width of the left hand side
      value_error "lhs width unknown" if lhs_type.width == :unknown
      return Type.new(:bits, width: lhs_type.width + rhs.value(symtab), qualifiers:)
    end
    value_else(value_result) do
      Type.new(:bits, width: lhs_type.width, qualifiers:)
    end
  elsif ["`+", "`-"].include?(op)
    qualifiers << :known # +/- raises exception if either lhs or rhs has undefined state
    # widening addition/subtraction: result is 1 more bit than the largest operand to
    # capture the carry
    value_result = value_try do
      value_error "lhs width is unknown" if lhs_type.width == :unknown
      value_error "rhs width is unknown" if rhs_type.width == :unknown
      return Type.new(:bits, width: [lhs_type.width, rhs_type.width].max + 1, qualifiers:)
    end
    value_else(value_result) do
      Type.new(:bits, width: :unknown, qualifiers:)
    end
  elsif op == "`*"
    qualifiers << :known if lhs_type.known? && rhs_type.known?
    # widening multiply: result sum of the widths of the operations
    value_result = value_try do
      value_error "lhs width is unknown" if lhs_type.width == :unknown
      value_error "rhs width is unknown" if rhs_type.width == :unknown
      return Type.new(:bits, width: (lhs_type.width + rhs_type.width), qualifiers:)
    end
    value_else(value_result) do
      Type.new(:bits, width: :unknown, qualifiers:)
    end
  else
    qualifiers << :signed if lhs_type.signed? && rhs_type.signed?
    qualifiers << :known if lhs_type.known? && rhs_type.known?
    if [lhs_type.width, rhs_type.width].include?(:unknown)
      Type.new(:bits, width: :unknown, qualifiers:)
    else
      Type.new(:bits, width: [lhs_type.width, rhs_type.width].max, qualifiers:)
    end
  end
end

#type_check(symtab, strict:) ⇒ void

This method returns an undefined value.

type check this node and all children

Calls to #type and/or #value may depend on type_check being called first with the same symtab. If not, those functions may raise an AstNode::InternalError

Parameters:

Raises:



4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
 
# File 'lib/idlc/ast.rb', line 4696

def type_check(symtab, strict:)
  internal_error "No type_check function #{lhs.inspect}" unless lhs.respond_to?(:type_check)

  lhs_short_circuit = T.let(false, T::Boolean)
  rhs_short_circuit = T.let(false, T::Boolean)
  if op == "||" || op == "&&"
    # see if we can short circuit
    lhs_value = T.let(nil, T.untyped)
    value_try do
      lhs_value = lhs.value(symtab)
    end
    rhs_value = T.let(nil, T.untyped)
    value_try do
      rhs_value = rhs.value(symtab)
    end

    if (lhs_value == true || lhs_value == false) && (rhs_value == true || rhs_value == false)
      # both are known and boolean. nothing more to check
      return
    elsif lhs_value == false && op == "||"
      rhs.type_check(symtab, strict:)
    elsif lhs_value == true && op == "||"
      rhs_short_circuit = true
    elsif lhs_value == true && op == "&&"
      rhs.type_check(symtab, strict:)
    elsif lhs_value == false && op == "&&"
      rhs_short_circuit = true
    elsif rhs_value == false && op == "||"
      lhs.type_check(symtab, strict:)
    elsif rhs_value == true && op == "||"
      lhs_short_circuit = true
    elsif rhs_value == true && op == "&&"
      lhs.type_check(symtab, strict:)
    elsif rhs_value == false && op == "&&"
      lhs_short_circuit = true
    end
  end


  if ["<=", ">=", "<", ">", "!=", "=="].include?(op)
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    internal_error text_value if rhs_type.nil?
    unless rhs_type.comparable_to?(lhs_type)
      type_error "#{lhs.text_value} (type = #{lhs_type}) and #{rhs.text_value} (type = #{rhs_type}) are not comparable"
    end

  elsif ["&&", "||"].include?(op)
    unless lhs_short_circuit
      lhs_type = lhs.type(symtab)
      unless lhs_type.convertable_to?(:boolean)
        type_error "left-hand side of #{op} needs to be boolean (is #{lhs_type}) (#{text_value})"
      end
    end

    unless rhs_short_circuit
      rhs_type = rhs.type(symtab)
      unless rhs_type.convertable_to?(:boolean)
        type_error "right-hand side of #{op} needs to be boolean (is #{rhs_type}) (#{text_value})"
      end
    end

  elsif op == "<<"
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    type_error "Unsupported type for left shift: #{lhs_type}" unless lhs_type.kind == :bits
    type_error "Unsupported shift for left shift: #{rhs_type}" unless rhs_type.kind == :bits
  elsif op == "`<<"
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    type_error "Unsupported type for left shift: #{lhs_type}" unless lhs_type.kind == :bits
    type_error "Unsupported shift for left shift: #{rhs_type}" unless rhs_type.kind == :bits
    type_error "Widening shift amount must be constant (if it's not, the width of the result is unknowable)." unless rhs_type.const?
  elsif [">>", ">>>"].include?(op)
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    type_error "Unsupported type for right shift: #{lhs_type}" unless lhs_type.kind == :bits
    type_error "Unsupported shift for right shift: #{rhs_type}" unless rhs_type.kind == :bits
  elsif ["*", "`*", "/", "%"].include?(op)
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    unless lhs_type.integral? && rhs_type.integral?
      type_error "Multiplication/division is only defined for integral types. Maybe you forgot a $bits cast?"
    end
  elsif ["+", "-", "`+", "`-"].include?(op)
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    unless lhs_type.integral? && rhs_type.integral?
      type_error "Addition/subtraction is only defined for integral types. Maybe you forgot a $bits cast?"
    end
  elsif ["&", "|", "^"].include?(op)
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    unless lhs_type.integral? && rhs_type.integral?
      type_error "Bitwise operation is only defined for integral types. Maybe you forgot a $bits cast?"
    end
  else
    internal_error "Unhandled op '#{op}'"
  end
end

#value(symtab) ⇒ Object

Return the compile-time-known value of the node



5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
5323
5324
5325
5326
5327
5328
5329
5330
5331
5332
5333
5334
5335
5336
 
# File 'lib/idlc/ast.rb', line 5120

def value(symtab)
  # cached_value = @value_cache[symtab]
  # return cached_value unless cached_value.nil?

  value =
    if op == ">>>"
      lhs_value = lhs.value(symtab)
      if (lhs_value & (1 << (lhs.type(symtab).width - 1))).zero?
        shamt = rhs.value(symtab)
        shamt.zero? ? lhs_value : (lhs_value >> shamt)
      else
        # need to shift in ones
        shift_amount = rhs.value(symtab)
        if shift_amount.zero?
          lhs_value
        else
          shifted_value = lhs_value >> shift_amount
          mask_len = [lhs.type(symtab).width, shift_amount].min
          mask = ((1 << mask_len) - 1) << [(lhs.type(symtab).width - shift_amount), 0].max

          shifted_value | mask
        end
      end
    elsif ["&&", "||"].include?(op)
      # these can short circuit, so we might only need to check the lhs
      lhs_value = lhs.value(symtab)
      if (op == "&&") && lhs_value == false
        false
      elsif (op == "||") && lhs_value == true
        true
      else
        if op == "&&"
          lhs_value && rhs.value(symtab)
        else
          lhs_value || rhs.value(symtab)
        end
      end
    elsif op == "=="
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        rhs_val = rhs.value(symtab)
        return lhs_val == rhs_val
      end
      value_else(value_result) do
        # even if we don't know the exact value of @lhs and @rhs, we can still
        # know that == is false if the possible values of each do not overlap
        if lhs.values(symtab).intersection(rhs.values(symtab)).empty?
          false
        else

          value_error "There is overlap in the lhs/rhs return values"
        end
      end
    elsif op == "!="
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        rhs_val = rhs.value(symtab)
        return lhs_val != rhs_val
      end
      value_else(value_result) do
        # even if we don't know the exact value of @lhs and @rhs, we can still
        # know that != is true if the possible values of each do not overlap
        if lhs.values(symtab).intersection(rhs.values(symtab)).empty?
          true
        else
          value_error "There is overlap in the lhs/rhs return values"
        end
      end
    elsif op == "<="
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        rhs_val = rhs.value(symtab)
        return lhs_val <= rhs_val
      end
      value_else(value_result) do
        # even if we don't know the exact value of @lhs and @rhs, we can still
        # know that != is true if the possible values of lhs are all <= the possible values of rhs
        rhs_values = rhs.values(symtab)
        if lhs.values(symtab).all? { |lhs_value| rhs_values.all? { |rhs_value| lhs_value <= rhs_value } }
          true
        else
          value_error "Some value of lhs is not <= some value of rhs"
        end
      end
    elsif op == ">="
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        rhs_val = rhs.value(symtab)
        return lhs_val >= rhs_val
      end
      value_else(value_result) do
        # even if we don't know the exact value of @lhs and @rhs, we can still
        # know that != is true if the possible values of lhs are all >= the possible values of rhs
        rhs_values = rhs.values(symtab)
        if lhs.values(symtab).all? { |lhs_value| rhs_values.all? { |rhs_value| lhs_value >= rhs_value } }
          true
        else
          value_error "Some value of lhs is not >= some value of rhs"
        end
      end
    elsif op == "<"
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        rhs_val = rhs.value(symtab)
        return lhs_val < rhs_val
      end
      value_else(value_result) do
        # even if we don't know the exact value of @lhs and @rhs, we can still
        # know that != is true if the possible values of lhs are all < the possible values of rhs
        rhs_values = rhs.values(symtab)
        if lhs.values(symtab).all? { |lhs_value| rhs_values.all? { |rhs_value| lhs_value < rhs_value } }
          true
        else
          value_error "Some value of lhs is not < some value of rhs"
        end
      end
    elsif op == ">"
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        rhs_val = rhs.value(symtab)
        return lhs_val > rhs_val
      end
      value_else(value_result) do
        # even if we don't know the exact value of @lhs and @rhs, we can still
        # know that != is true if the possible values of lhs are all > the possible values of rhs
        rhs_values = rhs.values(symtab)
        if lhs.values(symtab).all? { |lhs_value| rhs_values.all? { |rhs_value| lhs_value > rhs_value } }
          true
        else
          value_error "Some value of lhs is not > some value of rhs"
        end
      end
    elsif op == "&"
      # if one side is zero, we don't need to know the other side
      lhs_val = T.let(nil, T.nilable(Integer))
      value_result = value_try do
        lhs_val = lhs.value(symtab)
        return 0 if lhs_val.zero?
      end
      # ok, try rhs
      rhs_val = rhs.value(symtab)
      return 0 if rhs_val.zero?

      # If we got here, both sides must have values
      value_error "lhs value not known" if lhs_val.nil?
      lhs_val & rhs_val

    elsif op == "|"
      # if one side is all ones, we don't need to know the other side
      rhs_type = rhs.type(symtab)
      value_error("Unknown width") if rhs_type.width == :unknown
      lhs_type = lhs.type(symtab)
      value_error("unknown width") if lhs_type.width == :unknown

      rhs_val = T.let(nil, T.nilable(Integer))
      value_result = value_try do
        rhs_mask = ((1 << rhs_type.width) - 1)
        rhs_val = rhs.value(symtab)
        return rhs_mask if (rhs_val == rhs_mask) && (lhs_type.width <= rhs_type.width)
      end
      # ok, try lhs

      lhs_mask = ((1 << lhs_type.width) - 1)
      lhs_val = T.let(nil, T.nilable(Integer))
      value_try do
        lhs_val = lhs.value(symtab)
        return lhs_mask if (lhs_val == lhs_mask) && (rhs_type.width <= lhs_type.width)
      end

      # If we got here, we need both values
      value_error "lhs value not known" if lhs_val.nil?
      value_error "rhs value not known" if rhs_val.nil?
      lhs_val | rhs_val

    else
      v =
        case op
        when "+", "`+"
          lhs.value(symtab) + rhs.value(symtab)
        when "-", "`-"
          lhs.value(symtab) - rhs.value(symtab)
        when "*", "`*"
          lhs.value(symtab) * rhs.value(symtab)
        when "/"
          lhs.value(symtab) / rhs.value(symtab)
        when "%"
          lhs.value(symtab) % rhs.value(symtab)
        when "^"
          lhs.value(symtab) ^ rhs.value(symtab)
        when "|"
          lhs.value(symtab) | rhs.value(symtab)
        when "&"
          lhs.value(symtab) & rhs.value(symtab)
        when ">>"
          lhs.value(symtab) >> rhs.value(symtab)
        when "<<", "`<<"
          lhs.value(symtab) << rhs.value(symtab)
        else
          internal_error "Unhandled binary op #{op}"
        end

      expr_type = type(symtab).width
      value_error "Cannot know value of Bits with unknown width" if expr_type == :unknown

      v_trunc =
        if op.include?("`")
          v
        else
          truncate(v, type(symtab).width, type(symtab).signed?)
        end

      truncation_warn "The value of '#{text_value}' is truncated from #{v} to #{v_trunc} because the result is only #{type(symtab).width} bits" if v != v_trunc
      v_trunc
    end
  # @value_cache[symtab] = value
  value
end