Class: Idl::BinaryExpressionAst

Inherits:
AstNode
  • Object
show all
Includes:
Rvalue
Defined in:
lib/idl/ast.rb

Constant Summary collapse

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

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

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



2636
2637
2638
2639
2640
 
# File 'lib/idl/ast.rb', line 2636

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



3007
3008
3009
 
# File 'lib/idl/ast.rb', line 3007

def op
  @op
end

Instance Method Details

#invert(symtab) ⇒ BinaryExpressionAst

Returns this expression, but with an inverted condition.

Returns:



2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
 
# File 'lib/idl/ast.rb', line 2643

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 



2632
 
# File 'lib/idl/ast.rb', line 2632

def lhs = @children[0]

#rhs ⇒ Object 



2633
 
# File 'lib/idl/ast.rb', line 2633

def rhs = @children[1]

#to_idl ⇒ String

Return valid IDL representation of the node (and its subtree)

Returns:

  • (String) —

    IDL code for the node



2673
2674
2675
 
# File 'lib/idl/ast.rb', line 2673

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:



2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
 
# File 'lib/idl/ast.rb', line 2678

def type(symtab)
  lhs_type = lhs.type(symtab)
  short_circuit = false

  value_result = value_try do
    lhs_value = lhs.value(symtab)
    if (lhs_value == true && op == "||") || (lhs_value == false && op == "&&")
      short_circuit = true
    end
  end
  value_else(value_result) { short_circuit = false }

  rhs_type = rhs.type(symtab) unless short_circuit

  qualifiers = []
  qualifiers << :const if lhs_type.const? && (short_circuit || rhs_type.const?)

  if LOGICAL_OPS.include?(op)
    if qualifiers.include?(:const)
      ConstBoolType
    else
      BoolType
    end
  elsif op == "<<"
    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)
  elsif lhs_type.const? && rhs_type.const?
    # if both types are const and the operator results in a Bits type,
    # then the result type is the largest of:
    #
    #  * the minimum bit width needed to represent `lhs op rhs`
    #  * the largest width of either lhs or rhs
    result_width =
      case op
      when "*"
        if [lhs_type.width, rhs_type.width].include?(:unknown)
          :unknown
        else
          lhs_type.width + rhs_type.width
        end
      when "+", "-"
        if [lhs_type.width, rhs_type.width].include?(:unknown)
          :unknown
        else
          [lhs_type.width, rhs_type.width].max + 1
        end
      when "/", "%", ">>", ">>>"
        lhs_type.width
      when "&", "|", "^"
        if [lhs_type.width, rhs_type.width].include?(:unknown)
          :unknown
        else
          [lhs_type.width, rhs_type.width].max
        end
      end
    qualifiers << :signed if lhs_type.signed? && rhs_type.signed?
    Type.new(:bits, width: result_width, qualifiers:)
  else
    qualifiers << :signed if lhs_type.signed? && rhs_type.signed?
    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) ⇒ 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:



2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
 
# File 'lib/idl/ast.rb', line 2754

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

  lhs.type_check(symtab)
  short_circuit = false
  value_result = value_try do
    lhs_value = lhs.value(symtab)
    if (lhs_value == true && op == "||") || (lhs_value == false && op == "&&")
      short_circuit = true
    end
  end
  value_else(value_result) do
    short_circuit = false
  end
  rhs.type_check(symtab) unless short_circuit

  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)
    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

    unless 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 == ">>" || op == ">>>"
    rhs_type = rhs.type(symtab)
    lhs_type = lhs.type(symtab)
    type_error "Unsupported type for right shift: #{lhs_type(symtab)}" unless lhs_type.kind == :bits
    type_error "Unsupported shift for right shift: #{rhs_type(symtab)}" 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



2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
 
# File 'lib/idl/ast.rb', line 2825

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?
        lhs_value >> rhs.value(symtab)
      else
        # need to shift in ones
        shift_amount = rhs.value(symtab)
        shifted_value = lhs_value >> shift_amount
        mask_len = lhs.type(symtab).width - shift_amount
        mask = ((1 << mask_len) - 1) << shift_amount

        shifted_value | mask
      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
        return lhs.value(symtab) == rhs.value(symtab)
      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
        return lhs.value(symtab) != rhs.value(symtab)
      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
        return lhs.value(symtab) <= rhs.value(symtab)
      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
        return lhs.value(symtab) >= rhs.value(symtab)
      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
        return lhs.value(symtab) < rhs.value(symtab)
      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
        return lhs.value(symtab) > rhs.value(symtab)
      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
      value_result = value_try do
        return 0 if lhs.value(symtab).zero?
      end
      # ok, trye rhs

      return 0 if rhs.value(symtab).zero?

      lhs.value(symtab) & rhs.value(symtab)

    elsif op == "|"
      # if one side is all ones, we don't need to know the other side
      value_result = value_try do
        rhs_mask = ((1 << rhs.type(symtab).width) - 1)
        return rhs_mask if (rhs.value(symtab) == rhs_mask) && (lhs.type(symtab).width <= rhs.type(symtab).width)
      end
      # ok, trye rhs

      lhs_mask = ((1 << lhs.type(symtab).width) - 1)
      return lhs_mask if (lhs.value(symtab) == lhs_mask) && (rhs.type(symtab).width <= lhs.type(symtab).width)

      lhs.value(symtab) | rhs.value(symtab)

    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

      v_trunc =
        if !lhs.type(symtab).const? || !rhs.type(symtab).const?
          # when both sides are constant, the value is not truncated
          v & ((1 << type(symtab).width) - 1)
        else
          v
        end

      warn "WARNING: The value of '#{text_value}' (#{lhs.type(symtab).const?}, #{rhs.type(symtab).const?}) 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

#values(symtab) ⇒ Array<Integer>, ... Originally defined in module Rvalue

Return a complete list of possible compile-time-known values of the node, or raise a ValueError if the full list cannot be determined

For most AstNodes, this will just be a single-entry array

Parameters:

  • symtab (SymbolTable) —

    The context for the evaulation

Returns:

  • (Array<Integer>) —

    The complete list of compile-time-known values, when they are integral

  • (Array<Boolean>) —

    The complete list of compile-time-known values, when they are booleans

  • (AstNode::ValueError) —

    if the list of values is not knowable at compile time