[apple/javascriptcore.git] / offlineasm / ast.rb

# Copyright (C) 2011 Apple Inc. All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
# THE POSSIBILITY OF SUCH DAMAGE.

require "config"

#
# Base utility types for the AST.
#

# Valid methods for Node:
#
# node.children -> Returns an array of immediate children.
#
# node.descendents -> Returns an array of all strict descendants (children
#     and children of children, transitively).
#
# node.flatten -> Returns an array containing the strict descendants and
#     the node itself.
#
# node.filter(type) -> Returns an array containing those elements in
#     node.flatten that are of the given type (is_a? type returns true).
#
# node.mapChildren{|v| ...} -> Returns a new node with all children
#     replaced according to the given block.
#
# Examples:
#
# node.filter(Setting).uniq -> Returns all of the settings that the AST's
#     IfThenElse blocks depend on.
#
# node.filter(StructOffset).uniq -> Returns all of the structure offsets
#     that the AST depends on.

class Node
    attr_reader :codeOrigin
    
    def initialize(codeOrigin)
        @codeOrigin = codeOrigin
    end
    
    def codeOriginString
        @codeOrigin.to_s
    end
    
    def descendants
        children.collect{|v| v.flatten}.flatten
    end
    
    def flatten
        [self] + descendants
    end
    
    def filter(type)
        flatten.select{|v| v.is_a? type}
    end
end

class NoChildren < Node
    def initialize(codeOrigin)
        super(codeOrigin)
    end
    
    def children
        []
    end
    
    def mapChildren
        self
    end
end

class StructOffsetKey
    attr_reader :struct, :field
    
    def initialize(struct, field)
        @struct = struct
        @field = field
    end
    
    def hash
        @struct.hash + @field.hash * 3
    end
    
    def eql?(other)
        @struct == other.struct and @field == other.field
    end
end

#
# AST nodes.
#

class StructOffset < NoChildren
    attr_reader :struct, :field
    
    def initialize(codeOrigin, struct, field)
        super(codeOrigin)
        @struct = struct
        @field = field
    end
    
    @@mapping = {}
    
    def self.forField(codeOrigin, struct, field)
        key = StructOffsetKey.new(struct, field)
        
        unless @@mapping[key]
            @@mapping[key] = StructOffset.new(codeOrigin, struct, field)
        end
        @@mapping[key]
    end
    
    def dump
        "#{struct}::#{field}"
    end
    
    def <=>(other)
        if @struct != other.struct
            return @struct <=> other.struct
        end
        @field <=> other.field
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class Sizeof < NoChildren
    attr_reader :struct
    
    def initialize(codeOrigin, struct)
        super(codeOrigin)
        @struct = struct
    end
    
    @@mapping = {}
    
    def self.forName(codeOrigin, struct)
        unless @@mapping[struct]
            @@mapping[struct] = Sizeof.new(codeOrigin, struct)
        end
        @@mapping[struct]
    end
    
    def dump
        "sizeof #{@struct}"
    end
    
    def <=>(other)
        @struct <=> other.struct
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class Immediate < NoChildren
    attr_reader :value
    
    def initialize(codeOrigin, value)
        super(codeOrigin)
        @value = value
        raise "Bad immediate value #{value.inspect} at #{codeOriginString}" unless value.is_a? Integer
    end
    
    def dump
        "#{value}"
    end
    
    def ==(other)
        other.is_a? Immediate and other.value == @value
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class AddImmediates < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        AddImmediates.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} + #{right.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class SubImmediates < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        SubImmediates.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} - #{right.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class MulImmediates < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        MulImmediates.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} * #{right.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class NegImmediate < Node
    attr_reader :child
    
    def initialize(codeOrigin, child)
        super(codeOrigin)
        @child = child
    end
    
    def children
        [@child]
    end
    
    def mapChildren
        NegImmediate.new(codeOrigin, (yield @child))
    end
    
    def dump
        "(-#{@child.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class OrImmediates < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        OrImmediates.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} | #{right.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class AndImmediates < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        AndImmediates.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} & #{right.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class XorImmediates < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        XorImmediates.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} ^ #{right.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class BitnotImmediate < Node
    attr_reader :child
    
    def initialize(codeOrigin, child)
        super(codeOrigin)
        @child = child
    end
    
    def children
        [@child]
    end
    
    def mapChildren
        BitnotImmediate.new(codeOrigin, (yield @child))
    end
    
    def dump
        "(~#{@child.dump})"
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        true
    end
    
    def register?
        false
    end
end

class RegisterID < NoChildren
    attr_reader :name
    
    def initialize(codeOrigin, name)
        super(codeOrigin)
        @name = name
    end
    
    @@mapping = {}
    
    def self.forName(codeOrigin, name)
        unless @@mapping[name]
            @@mapping[name] = RegisterID.new(codeOrigin, name)
        end
        @@mapping[name]
    end
    
    def dump
        name
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        false
    end
    
    def register?
        true
    end
end

class FPRegisterID < NoChildren
    attr_reader :name
    
    def initialize(codeOrigin, name)
        super(codeOrigin)
        @name = name
    end
    
    @@mapping = {}
    
    def self.forName(codeOrigin, name)
        unless @@mapping[name]
            @@mapping[name] = FPRegisterID.new(codeOrigin, name)
        end
        @@mapping[name]
    end
    
    def dump
        name
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        false
    end
    
    def register?
        true
    end
end

class SpecialRegister < NoChildren
    def initialize(name)
        @name = name
    end
    
    def address?
        false
    end
    
    def label?
        false
    end
    
    def immediate?
        false
    end
    
    def register?
        true
    end
end

class Variable < NoChildren
    attr_reader :name
    
    def initialize(codeOrigin, name)
        super(codeOrigin)
        @name = name
    end
    
    @@mapping = {}
    
    def self.forName(codeOrigin, name)
        unless @@mapping[name]
            @@mapping[name] = Variable.new(codeOrigin, name)
        end
        @@mapping[name]
    end
    
    def dump
        name
    end
    
    def inspect
        "<variable #{name} at #{codeOriginString}>"
    end
end

class Address < Node
    attr_reader :base, :offset
    
    def initialize(codeOrigin, base, offset)
        super(codeOrigin)
        @base = base
        @offset = offset
        raise "Bad base for address #{base.inspect} at #{codeOriginString}" unless base.is_a? Variable or base.register?
        raise "Bad offset for address #{offset.inspect} at #{codeOriginString}" unless offset.is_a? Variable or offset.immediate?
    end
    
    def withOffset(extraOffset)
        Address.new(codeOrigin, @base, Immediate.new(codeOrigin, @offset.value + extraOffset))
    end
    
    def children
        [@base, @offset]
    end
    
    def mapChildren
        Address.new(codeOrigin, (yield @base), (yield @offset))
    end
    
    def dump
        "#{offset.dump}[#{base.dump}]"
    end
    
    def address?
        true
    end
    
    def label?
        false
    end
    
    def immediate?
        false
    end
    
    def register?
        false
    end
end

class BaseIndex < Node
    attr_reader :base, :index, :scale, :offset
    
    def initialize(codeOrigin, base, index, scale, offset)
        super(codeOrigin)
        @base = base
        @index = index
        @scale = scale
        raise unless [1, 2, 4, 8].member? @scale
        @offset = offset
    end
    
    def scaleShift
        case scale
        when 1
            0
        when 2
            1
        when 4
            2
        when 8
            3
        else
            raise "Bad scale at #{codeOriginString}"
        end
    end
    
    def withOffset(extraOffset)
        BaseIndex.new(codeOrigin, @base, @index, @scale, Immediate.new(codeOrigin, @offset.value + extraOffset))
    end
    
    def children
        [@base, @index, @offset]
    end
    
    def mapChildren
        BaseIndex.new(codeOrigin, (yield @base), (yield @index), @scale, (yield @offset))
    end
    
    def dump
        "#{offset.dump}[#{base.dump}, #{index.dump}, #{scale}]"
    end
    
    def address?
        true
    end
    
    def label?
        false
    end
    
    def immediate?
        false
    end
    
    def register?
        false
    end
end

class AbsoluteAddress < NoChildren
    attr_reader :address
    
    def initialize(codeOrigin, address)
        super(codeOrigin)
        @address = address
    end
    
    def withOffset(extraOffset)
        AbsoluteAddress.new(codeOrigin, Immediate.new(codeOrigin, @address.value + extraOffset))
    end
    
    def dump
        "#{address.dump}[]"
    end
    
    def address?
        true
    end
    
    def label?
        false
    end
    
    def immediate?
        false
    end
    
    def register?
        false
    end
end

class Instruction < Node
    attr_reader :opcode, :operands, :annotation
    
    def initialize(codeOrigin, opcode, operands, annotation=nil)
        super(codeOrigin)
        @opcode = opcode
        @operands = operands
        @annotation = annotation
    end
    
    def children
        operands
    end
    
    def mapChildren(&proc)
        Instruction.new(codeOrigin, @opcode, @operands.map(&proc), @annotation)
    end
    
    def dump
        "\t" + opcode.to_s + " " + operands.collect{|v| v.dump}.join(", ")
    end

    def lowerDefault
        case opcode
        when "localAnnotation"
            $asm.putLocalAnnotation
        when "globalAnnotation"
            $asm.putGlobalAnnotation
        else
            raise "Unhandled opcode #{opcode} at #{codeOriginString}"
        end
    end
end

class Error < NoChildren
    def initialize(codeOrigin)
        super(codeOrigin)
    end
    
    def dump
        "\terror"
    end
end

class ConstDecl < Node
    attr_reader :variable, :value
    
    def initialize(codeOrigin, variable, value)
        super(codeOrigin)
        @variable = variable
        @value = value
    end
    
    def children
        [@variable, @value]
    end
    
    def mapChildren
        ConstDecl.new(codeOrigin, (yield @variable), (yield @value))
    end
    
    def dump
        "const #{@variable.dump} = #{@value.dump}"
    end
end

$labelMapping = {}

class Label < NoChildren
    attr_reader :name
    
    def initialize(codeOrigin, name)
        super(codeOrigin)
        @name = name
    end
    
    def self.forName(codeOrigin, name)
        if $labelMapping[name]
            raise "Label name collision: #{name}" unless $labelMapping[name].is_a? Label
        else
            $labelMapping[name] = Label.new(codeOrigin, name)
        end
        $labelMapping[name]
    end
    
    def dump
        "#{name}:"
    end
end

class LocalLabel < NoChildren
    attr_reader :name
    
    def initialize(codeOrigin, name)
        super(codeOrigin)
        @name = name
    end

    @@uniqueNameCounter = 0
    
    def self.forName(codeOrigin, name)
        if $labelMapping[name]
            raise "Label name collision: #{name}" unless $labelMapping[name].is_a? LocalLabel
        else
            $labelMapping[name] = LocalLabel.new(codeOrigin, name)
        end
        $labelMapping[name]
    end
    
    def self.unique(comment)
        newName = "_#{comment}"
        if $labelMapping[newName]
            while $labelMapping[newName = "_#{@@uniqueNameCounter}_#{comment}"]
                @@uniqueNameCounter += 1
            end
        end
        forName(nil, newName)
    end
    
    def cleanName
        if name =~ /^\./
            "_" + name[1..-1]
        else
            name
        end
    end
    
    def dump
        "#{name}:"
    end
end

class LabelReference < Node
    attr_reader :label
    
    def initialize(codeOrigin, label)
        super(codeOrigin)
        @label = label
    end
    
    def children
        [@label]
    end
    
    def mapChildren
        LabelReference.new(codeOrigin, (yield @label))
    end
    
    def name
        label.name
    end
    
    def dump
        label.name
    end
    
    def address?
        false
    end
    
    def label?
        true
    end
    
    def immediate?
        false
    end
end

class LocalLabelReference < NoChildren
    attr_reader :label
    
    def initialize(codeOrigin, label)
        super(codeOrigin)
        @label = label
    end
    
    def children
        [@label]
    end
    
    def mapChildren
        LocalLabelReference.new(codeOrigin, (yield @label))
    end
    
    def name
        label.name
    end
    
    def dump
        label.name
    end
    
    def address?
        false
    end
    
    def label?
        true
    end
    
    def immediate?
        false
    end
end

class Sequence < Node
    attr_reader :list
    
    def initialize(codeOrigin, list)
        super(codeOrigin)
        @list = list
    end
    
    def children
        list
    end
    
    def mapChildren(&proc)
        Sequence.new(codeOrigin, @list.map(&proc))
    end
    
    def dump
        list.collect{|v| v.dump}.join("\n")
    end
end

class True < NoChildren
    def initialize
        super(nil)
    end
    
    @@instance = True.new
    
    def self.instance
        @@instance
    end
    
    def value
        true
    end
    
    def dump
        "true"
    end
end

class False < NoChildren
    def initialize
        super(nil)
    end
    
    @@instance = False.new
    
    def self.instance
        @@instance
    end
    
    def value
        false
    end
    
    def dump
        "false"
    end
end

class TrueClass
    def asNode
        True.instance
    end
end

class FalseClass
    def asNode
        False.instance
    end
end

class Setting < NoChildren
    attr_reader :name
    
    def initialize(codeOrigin, name)
        super(codeOrigin)
        @name = name
    end
    
    @@mapping = {}
    
    def self.forName(codeOrigin, name)
        unless @@mapping[name]
            @@mapping[name] = Setting.new(codeOrigin, name)
        end
        @@mapping[name]
    end
    
    def dump
        name
    end
end

class And < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        And.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} and #{right.dump})"
    end
end

class Or < Node
    attr_reader :left, :right
    
    def initialize(codeOrigin, left, right)
        super(codeOrigin)
        @left = left
        @right = right
    end
    
    def children
        [@left, @right]
    end
    
    def mapChildren
        Or.new(codeOrigin, (yield @left), (yield @right))
    end
    
    def dump
        "(#{left.dump} or #{right.dump})"
    end
end

class Not < Node
    attr_reader :child
    
    def initialize(codeOrigin, child)
        super(codeOrigin)
        @child = child
    end
    
    def children
        [@child]
    end
    
    def mapChildren
        Not.new(codeOrigin, (yield @child))
    end
    
    def dump
        "(not #{child.dump})"
    end
end

class Skip < NoChildren
    def initialize(codeOrigin)
        super(codeOrigin)
    end
    
    def dump
        "\tskip"
    end
end

class IfThenElse < Node
    attr_reader :predicate, :thenCase
    attr_accessor :elseCase
    
    def initialize(codeOrigin, predicate, thenCase)
        super(codeOrigin)
        @predicate = predicate
        @thenCase = thenCase
        @elseCase = Skip.new(codeOrigin)
    end
    
    def children
        if @elseCase
            [@predicate, @thenCase, @elseCase]
        else
            [@predicate, @thenCase]
        end
    end
    
    def mapChildren
        IfThenElse.new(codeOrigin, (yield @predicate), (yield @thenCase), (yield @elseCase))
    end
    
    def dump
        "if #{predicate.dump}\n" + thenCase.dump + "\nelse\n" + elseCase.dump + "\nend"
    end
end

class Macro < Node
    attr_reader :name, :variables, :body

    def initialize(codeOrigin, name, variables, body)
        super(codeOrigin)
        @name = name
        @variables = variables
        @body = body
    end
    
    def children
        @variables + [@body]
    end
    
    def mapChildren
        Macro.new(codeOrigin, @name, @variables.map{|v| yield v}, (yield @body))
    end
    
    def dump
        "macro #{name}(" + variables.collect{|v| v.dump}.join(", ") + ")\n" + body.dump + "\nend"
    end
end

class MacroCall < Node
    attr_reader :name, :operands, :annotation
    
    def initialize(codeOrigin, name, operands, annotation)
        super(codeOrigin)
        @name = name
        @operands = operands
        raise unless @operands
        @operands.each{|v| raise unless v}
        @annotation = annotation
    end
    
    def children
        @operands
    end
    
    def mapChildren(&proc)
        MacroCall.new(codeOrigin, @name, @operands.map(&proc), @annotation)
    end
    
    def dump
        "\t#{name}(" + operands.collect{|v| v.dump}.join(", ") + ")"
    end
end
Commit	Line	Data
6fe7ccc8 A	1	# Copyright (C) 2011 Apple Inc. All rights reserved.
	2	#
	3	# Redistribution and use in source and binary forms, with or without
	4	# modification, are permitted provided that the following conditions
	5	# are met:
	6	# 1. Redistributions of source code must retain the above copyright
	7	# notice, this list of conditions and the following disclaimer.
	8	# 2. Redistributions in binary form must reproduce the above copyright
	9	# notice, this list of conditions and the following disclaimer in the
	10	# documentation and/or other materials provided with the distribution.
	11	#
	12	# THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
	13	# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
	14	# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	15	# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
	16	# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	17	# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	18	# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	19	# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	20	# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	21	# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
	22	# THE POSSIBILITY OF SUCH DAMAGE.
	23
93a37866 A	24	require "config"
93a37866 A	25
6fe7ccc8 A	26	#
	27	# Base utility types for the AST.
	28	#
	29
	30	# Valid methods for Node:
	31	#
	32	# node.children -> Returns an array of immediate children.
	33	#
	34	# node.descendents -> Returns an array of all strict descendants (children
	35	# and children of children, transitively).
	36	#
	37	# node.flatten -> Returns an array containing the strict descendants and
	38	# the node itself.
	39	#
	40	# node.filter(type) -> Returns an array containing those elements in
	41	# node.flatten that are of the given type (is_a? type returns true).
	42	#
	43	# node.mapChildren{\|v\| ...} -> Returns a new node with all children
	44	# replaced according to the given block.
	45	#
	46	# Examples:
	47	#
	48	# node.filter(Setting).uniq -> Returns all of the settings that the AST's
	49	# IfThenElse blocks depend on.
	50	#
	51	# node.filter(StructOffset).uniq -> Returns all of the structure offsets
	52	# that the AST depends on.
	53
	54	class Node
	55	attr_reader :codeOrigin
	56
	57	def initialize(codeOrigin)
	58	@codeOrigin = codeOrigin
	59	end
	60
	61	def codeOriginString
	62	@codeOrigin.to_s
	63	end
	64
	65	def descendants
	66	children.collect{\|v\| v.flatten}.flatten
	67	end
	68
	69	def flatten
	70	[self] + descendants
	71	end
	72
	73	def filter(type)
	74	flatten.select{\|v\| v.is_a? type}
	75	end
	76	end
	77
	78	class NoChildren < Node
	79	def initialize(codeOrigin)
	80	super(codeOrigin)
	81	end
	82
	83	def children
	84	[]
	85	end
	86
	87	def mapChildren
	88	self
	89	end
90	end
91
92	class StructOffsetKey
93	attr_reader :struct, :field
94
95	def initialize(struct, field)
96	@struct = struct
97	@field = field
98	end
99
100	def hash
101	@struct.hash + @field.hash * 3
102	end
103
104	def eql?(other)
105	@struct == other.struct and @field == other.field
106	end
107	end
108
109	#
110	# AST nodes.
111	#
112
113	class StructOffset < NoChildren
114	attr_reader :struct, :field
115
116	def initialize(codeOrigin, struct, field)
117	super(codeOrigin)
118	@struct = struct
119	@field = field
120	end
121
122	@@mapping = {}
123
124	def self.forField(codeOrigin, struct, field)
125	key = StructOffsetKey.new(struct, field)
126
127	unless @@mapping[key]
128	@@mapping[key] = StructOffset.new(codeOrigin, struct, field)
129	end
130	@@mapping[key]
131	end
132
133	def dump
134	"#{struct}::#{field}"
135	end
136
137	def <=>(other)
138	if @struct != other.struct
139	return @struct <=> other.struct
140	end
141	@field <=> other.field
142	end
143
144	def address?
145	false
146	end
147
148	def label?
149	false
150	end
151
152	def immediate?
153	true
154	end
155
156	def register?
157	false
158	end
159	end
160
161	class Sizeof < NoChildren
162	attr_reader :struct
163
164	def initialize(codeOrigin, struct)
165	super(codeOrigin)
166	@struct = struct
167	end
168
169	@@mapping = {}
170
171	def self.forName(codeOrigin, struct)
172	unless @@mapping[struct]
173	@@mapping[struct] = Sizeof.new(codeOrigin, struct)
174	end
175	@@mapping[struct]
176	end
177
178	def dump
179	"sizeof #{@struct}"
180	end
181
182	def <=>(other)
183	@struct <=> other.struct
184	end
185
186	def address?
187	false
188	end
189
190	def label?
191	false
192	end
193
194	def immediate?
195	true
196	end
197
198	def register?
199	false
200	end
201	end
202
203	class Immediate < NoChildren
204	attr_reader :value
205
206	def initialize(codeOrigin, value)
207	super(codeOrigin)
208	@value = value
209	raise "Bad immediate value #{value.inspect} at #{codeOriginString}" unless value.is_a? Integer
210	end
211
212	def dump
213	"#{value}"
214	end
215
216	def ==(other)
217	other.is_a? Immediate and other.value == @value
218	end
219
220	def address?
221	false
222	end
223
224	def label?
225	false
226	end
227
228	def immediate?
229	true
230	end
231
232	def register?
233	false
234	end
235	end
236
237	class AddImmediates < Node
238	attr_reader :left, :right
239
240	def initialize(codeOrigin, left, right)
241	super(codeOrigin)
242	@left = left
243	@right = right
244	end
245
246	def children
247	[@left, @right]
248	end
249
250	def mapChildren
251	AddImmediates.new(codeOrigin, (yield @left), (yield @right))
252	end
253
254	def dump
255	"(#{left.dump} + #{right.dump})"
256	end
257
258	def address?
259	false
260	end
261
262	def label?
263	false
264	end
265
266	def immediate?
267	true
268	end
269
270	def register?
271	false
272	end
273	end
274
275	class SubImmediates < Node
276	attr_reader :left, :right
277
278	def initialize(codeOrigin, left, right)
279	super(codeOrigin)
280	@left = left
281	@right = right
282	end
283
284	def children
285	[@left, @right]
286	end
287
288	def mapChildren
289	SubImmediates.new(codeOrigin, (yield @left), (yield @right))
290	end
291
292	def dump
293	"(#{left.dump} - #{right.dump})"
294	end
295
296	def address?
297	false
298	end
299
300	def label?
301	false
302	end
303
304	def immediate?
305	true
306	end
307
308	def register?
309	false
310	end
311	end
312
313	class MulImmediates < Node
314	attr_reader :left, :right
315
316	def initialize(codeOrigin, left, right)
317	super(codeOrigin)
318	@left = left
319	@right = right
320	end
321
322	def children
323	[@left, @right]
324	end
325
326	def mapChildren
327	MulImmediates.new(codeOrigin, (yield @left), (yield @right))
328	end
329
330	def dump
331	"(#{left.dump} * #{right.dump})"
332	end
333
334	def address?
335	false
336	end
337
338	def label?
339	false
340	end
341
342	def immediate?
343	true
344	end
345
346	def register?
347	false
348	end
349	end
350
351	class NegImmediate < Node
352	attr_reader :child
353
354	def initialize(codeOrigin, child)
355	super(codeOrigin)
356	@child = child
357	end
358
359	def children
360	[@child]
361	end
362
363	def mapChildren
364	NegImmediate.new(codeOrigin, (yield @child))
365	end
366
367	def dump
368	"(-#{@child.dump})"
369	end
370
371	def address?
372	false
373	end
374
375	def label?
376	false
377	end
378
379	def immediate?
380	true
381	end
382
383	def register?
384	false
385	end
386	end
387
388	class OrImmediates < Node
389	attr_reader :left, :right
390
391	def initialize(codeOrigin, left, right)
392	super(codeOrigin)
393	@left = left
394	@right = right
395	end
396
397	def children
398	[@left, @right]
399	end
400
401	def mapChildren
402	OrImmediates.new(codeOrigin, (yield @left), (yield @right))
403	end
404
405	def dump
406	"(#{left.dump} \| #{right.dump})"
407	end
408
409	def address?
410	false
411	end
412
413	def label?
414	false
415	end
416
417	def immediate?
418	true
419	end
420
421	def register?
422	false
423	end
424	end
425
426	class AndImmediates < Node
427	attr_reader :left, :right
428
429	def initialize(codeOrigin, left, right)
430	super(codeOrigin)
431	@left = left
432	@right = right
433	end
434
435	def children
436	[@left, @right]
437	end
438
439	def mapChildren
440	AndImmediates.new(codeOrigin, (yield @left), (yield @right))
441	end
442
443	def dump
444	"(#{left.dump} & #{right.dump})"
445	end
446
447	def address?
448	false
449	end
450
451	def label?
452	false
453	end
454
455	def immediate?
456	true
457	end
458
459	def register?
460	false
461	end
462	end
463
464	class XorImmediates < Node
465	attr_reader :left, :right
466
467	def initialize(codeOrigin, left, right)
468	super(codeOrigin)
469	@left = left
470	@right = right
471	end
472
473	def children
474	[@left, @right]
475	end
476
477	def mapChildren
478	XorImmediates.new(codeOrigin, (yield @left), (yield @right))
479	end
480
481	def dump
482	"(#{left.dump} ^ #{right.dump})"
483	end
484
485	def address?
486	false
487	end
488
489	def label?
490	false
491	end
492
493	def immediate?
494	true
495	end
496
497	def register?
498	false
499	end
500	end
501
502	class BitnotImmediate < Node
503	attr_reader :child
504
505	def initialize(codeOrigin, child)
506	super(codeOrigin)
507	@child = child
508	end
509
510	def children
511	[@child]
512	end
513
514	def mapChildren
515	BitnotImmediate.new(codeOrigin, (yield @child))
516	end
517
518	def dump
519	"(~#{@child.dump})"
520	end
521
522	def address?
523	false
524	end
525
526	def label?
527	false
528	end
529
530	def immediate?
531	true
532	end
533
534	def register?
535	false
536	end
537	end
538
539	class RegisterID < NoChildren
540	attr_reader :name
541
542	def initialize(codeOrigin, name)
543	super(codeOrigin)
544	@name = name
545	end
546
547	@@mapping = {}
548
549	def self.forName(codeOrigin, name)
550	unless @@mapping[name]
551	@@mapping[name] = RegisterID.new(codeOrigin, name)
552	end
553	@@mapping[name]
554	end
555
556	def dump
557	name
558	end
559
560	def address?
561	false
562	end
563
564	def label?
565	false
566	end
567
568	def immediate?
569	false
570	end
571
572	def register?
573	true
574	end
575	end
576
577	class FPRegisterID < NoChildren
578	attr_reader :name
579
580	def initialize(codeOrigin, name)
581	super(codeOrigin)
582	@name = name
583	end
584
585	@@mapping = {}
586
587	def self.forName(codeOrigin, name)
588	unless @@mapping[name]
589	@@mapping[name] = FPRegisterID.new(codeOrigin, name)
590	end
591	@@mapping[name]
592	end
593
594	def dump
595	name
596	end
597
598	def address?
599	false
600	end
601
602	def label?
603	false
604	end
605
606	def immediate?
607	false
608	end
609
610	def register?
611	true
612	end
613	end
614
615	class SpecialRegister < NoChildren
616	def initialize(name)
617	@name = name
618	end
619
620	def address?
621	false
622	end
623
624	def label?
625	false
626	end
627
628	def immediate?
629	false
630	end
631
632	def register?
633	true
634	end
635	end
636
637	class Variable < NoChildren
638	attr_reader :name
639
640	def initialize(codeOrigin, name)
641	super(codeOrigin)
642	@name = name
643	end
644
645	@@mapping = {}
646
647	def self.forName(codeOrigin, name)
648	unless @@mapping[name]
649	@@mapping[name] = Variable.new(codeOrigin, name)
650	end
651	@@mapping[name]
652	end
653
654	def dump
655	name
656	end
657
658	def inspect
659	"<variable #{name} at #{codeOriginString}>"
660	end
661	end
662
663	class Address < Node
664	attr_reader :base, :offset
665
666	def initialize(codeOrigin, base, offset)
667	super(codeOrigin)
668	@base = base
669	@offset = offset
670	raise "Bad base for address #{base.inspect} at #{codeOriginString}" unless base.is_a? Variable or base.register?
671	raise "Bad offset for address #{offset.inspect} at #{codeOriginString}" unless offset.is_a? Variable or offset.immediate?
672	end
673
93a37866 A	674	def withOffset(extraOffset)
	675	Address.new(codeOrigin, @base, Immediate.new(codeOrigin, @offset.value + extraOffset))
	676	end
	677
6fe7ccc8 A	678	def children
	679	[@base, @offset]
	680	end
	681
	682	def mapChildren
	683	Address.new(codeOrigin, (yield @base), (yield @offset))
	684	end
	685
	686	def dump
	687	"#{offset.dump}[#{base.dump}]"
	688	end
	689
	690	def address?
	691	true
	692	end
	693
	694	def label?
	695	false
	696	end
	697
	698	def immediate?
	699	false
	700	end
	701
	702	def register?
	703	false
	704	end
	705	end
	706
	707	class BaseIndex < Node
	708	attr_reader :base, :index, :scale, :offset
	709
	710	def initialize(codeOrigin, base, index, scale, offset)
	711	super(codeOrigin)
	712	@base = base
	713	@index = index
	714	@scale = scale
	715	raise unless [1, 2, 4, 8].member? @scale
	716	@offset = offset
	717	end
	718
	719	def scaleShift
	720	case scale
	721	when 1
	722	0
	723	when 2
	724	1
	725	when 4
	726	2
	727	when 8
	728	3
	729	else
	730	raise "Bad scale at #{codeOriginString}"
	731	end
	732	end
	733
93a37866 A	734	def withOffset(extraOffset)
	735	BaseIndex.new(codeOrigin, @base, @index, @scale, Immediate.new(codeOrigin, @offset.value + extraOffset))
	736	end
	737
6fe7ccc8 A	738	def children
	739	[@base, @index, @offset]
	740	end
	741
	742	def mapChildren
	743	BaseIndex.new(codeOrigin, (yield @base), (yield @index), @scale, (yield @offset))
	744	end
	745
	746	def dump
	747	"#{offset.dump}[#{base.dump}, #{index.dump}, #{scale}]"
	748	end
	749
	750	def address?
	751	true
	752	end
	753
	754	def label?
	755	false
	756	end
	757
	758	def immediate?
	759	false
	760	end
	761
	762	def register?
	763	false
	764	end
	765	end
	766
	767	class AbsoluteAddress < NoChildren
	768	attr_reader :address
	769
	770	def initialize(codeOrigin, address)
	771	super(codeOrigin)
	772	@address = address
	773	end
	774
93a37866 A	775	def withOffset(extraOffset)
	776	AbsoluteAddress.new(codeOrigin, Immediate.new(codeOrigin, @address.value + extraOffset))
	777	end
	778
6fe7ccc8 A	779	def dump
	780	"#{address.dump}[]"
	781	end
	782
	783	def address?
	784	true
	785	end
	786
	787	def label?
	788	false
	789	end
	790
	791	def immediate?
	792	false
	793	end
	794
	795	def register?
	796	false
	797	end
	798	end
	799
	800	class Instruction < Node
93a37866	801	attr_reader :opcode, :operands, :annotation
6fe7ccc8	802
93a37866	803	def initialize(codeOrigin, opcode, operands, annotation=nil)
6fe7ccc8 A	804	super(codeOrigin)
	805	@opcode = opcode
	806	@operands = operands
93a37866	807	@annotation = annotation
6fe7ccc8 A	808	end
	809
	810	def children
	811	operands
	812	end
	813
	814	def mapChildren(&proc)
93a37866	815	Instruction.new(codeOrigin, @opcode, @operands.map(&proc), @annotation)
6fe7ccc8 A	816	end
	817
	818	def dump
	819	"\t" + opcode.to_s + " " + operands.collect{\|v\| v.dump}.join(", ")
	820	end
93a37866 A	821
	822	def lowerDefault
	823	case opcode
	824	when "localAnnotation"
	825	$asm.putLocalAnnotation
	826	when "globalAnnotation"
	827	$asm.putGlobalAnnotation
	828	else
	829	raise "Unhandled opcode #{opcode} at #{codeOriginString}"
	830	end
	831	end
6fe7ccc8 A	832	end
	833
	834	class Error < NoChildren
	835	def initialize(codeOrigin)
	836	super(codeOrigin)
	837	end
	838
	839	def dump
	840	"\terror"
	841	end
	842	end
	843
	844	class ConstDecl < Node
	845	attr_reader :variable, :value
	846
	847	def initialize(codeOrigin, variable, value)
	848	super(codeOrigin)
	849	@variable = variable
	850	@value = value
	851	end
	852
	853	def children
	854	[@variable, @value]
	855	end
	856
	857	def mapChildren
	858	ConstDecl.new(codeOrigin, (yield @variable), (yield @value))
	859	end
	860
	861	def dump
	862	"const #{@variable.dump} = #{@value.dump}"
	863	end
	864	end
	865
	866	$labelMapping = {}
	867
	868	class Label < NoChildren
	869	attr_reader :name
	870
	871	def initialize(codeOrigin, name)
	872	super(codeOrigin)
	873	@name = name
	874	end
	875
	876	def self.forName(codeOrigin, name)
	877	if $labelMapping[name]
	878	raise "Label name collision: #{name}" unless $labelMapping[name].is_a? Label
	879	else
	880	$labelMapping[name] = Label.new(codeOrigin, name)
	881	end
	882	$labelMapping[name]
	883	end
	884
	885	def dump
	886	"#{name}:"
	887	end
	888	end
	889
	890	class LocalLabel < NoChildren
	891	attr_reader :name
	892
	893	def initialize(codeOrigin, name)
	894	super(codeOrigin)
	895	@name = name
896	end
897
898	@@uniqueNameCounter = 0
899
900	def self.forName(codeOrigin, name)
901	if $labelMapping[name]
902	raise "Label name collision: #{name}" unless $labelMapping[name].is_a? LocalLabel
903	else
904	$labelMapping[name] = LocalLabel.new(codeOrigin, name)
905	end
906	$labelMapping[name]
907	end
908
909	def self.unique(comment)
910	newName = "_#{comment}"
911	if $labelMapping[newName]
912	while $labelMapping[newName = "_#{@@uniqueNameCounter}_#{comment}"]
913	@@uniqueNameCounter += 1
914	end
915	end
916	forName(nil, newName)
917	end
918
919	def cleanName
920	if name =~ /^\./
921	"_" + name[1..-1]
922	else
923	name
924	end
925	end
926
927	def dump
928	"#{name}:"
929	end
930	end
931
932	class LabelReference < Node
933	attr_reader :label
934
935	def initialize(codeOrigin, label)
936	super(codeOrigin)
937	@label = label
938	end
939
940	def children
941	[@label]
942	end
943
944	def mapChildren
945	LabelReference.new(codeOrigin, (yield @label))
946	end
947
948	def name
949	label.name
950	end
951
952	def dump
953	label.name
954	end
955
956	def address?
957	false
958	end
959
960	def label?
961	true
962	end
963
964	def immediate?
965	false
966	end
967	end
968
969	class LocalLabelReference < NoChildren
970	attr_reader :label
971
972	def initialize(codeOrigin, label)
973	super(codeOrigin)
974	@label = label
975	end
976
977	def children
978	[@label]
979	end
980
981	def mapChildren
982	LocalLabelReference.new(codeOrigin, (yield @label))
983	end
984
985	def name
986	label.name
987	end
988
989	def dump
990	label.name
991	end
992
993	def address?
994	false
995	end
996
997	def label?
998	true
999	end
1000
1001	def immediate?
1002	false
1003	end
1004	end
1005
1006	class Sequence < Node
1007	attr_reader :list
1008
1009	def initialize(codeOrigin, list)
1010	super(codeOrigin)
1011	@list = list
1012	end
1013
1014	def children
1015	list
1016	end
1017
1018	def mapChildren(&proc)
1019	Sequence.new(codeOrigin, @list.map(&proc))
1020	end
1021
1022	def dump
1023	list.collect{\|v\| v.dump}.join("\n")
1024	end
1025	end
1026
1027	class True < NoChildren
1028	def initialize
1029	super(nil)
1030	end
1031
1032	@@instance = True.new
1033
1034	def self.instance
1035	@@instance
1036	end
1037
1038	def value
1039	true
1040	end
1041
1042	def dump
1043	"true"
1044	end
1045	end
1046
1047	class False < NoChildren
1048	def initialize
1049	super(nil)
1050	end
1051
1052	@@instance = False.new
1053
1054	def self.instance
1055	@@instance
1056	end
1057
1058	def value
1059	false
1060	end
1061
1062	def dump
1063	"false"
1064	end
1065	end
1066
1067	class TrueClass
1068	def asNode
1069	True.instance
1070	end
1071	end
1072
1073	class FalseClass
1074	def asNode
1075	False.instance
1076	end
1077	end
1078
1079	class Setting < NoChildren
1080	attr_reader :name
1081
1082	def initialize(codeOrigin, name)
1083	super(codeOrigin)
1084	@name = name
1085	end
1086
1087	@@mapping = {}
1088
1089	def self.forName(codeOrigin, name)
1090	unless @@mapping[name]
1091	@@mapping[name] = Setting.new(codeOrigin, name)
1092	end
1093	@@mapping[name]
1094	end
1095
1096	def dump
1097	name
1098	end
1099	end
1100
1101	class And < Node
1102	attr_reader :left, :right
1103
1104	def initialize(codeOrigin, left, right)
1105	super(codeOrigin)
1106	@left = left
1107	@right = right
1108	end
1109
1110	def children
1111	[@left, @right]
1112	end
1113
1114	def mapChildren
1115	And.new(codeOrigin, (yield @left), (yield @right))
1116	end
1117
1118	def dump
1119	"(#{left.dump} and #{right.dump})"
1120	end
1121	end
1122
1123	class Or < Node
1124	attr_reader :left, :right
1125
1126	def initialize(codeOrigin, left, right)
1127	super(codeOrigin)
1128	@left = left
1129	@right = right
1130	end
1131
1132	def children
1133	[@left, @right]
1134	end
1135
1136	def mapChildren
1137	Or.new(codeOrigin, (yield @left), (yield @right))
1138	end
1139
1140	def dump
1141	"(#{left.dump} or #{right.dump})"
1142	end
1143	end
1144
1145	class Not < Node
1146	attr_reader :child
1147
1148	def initialize(codeOrigin, child)
1149	super(codeOrigin)
1150	@child = child
1151	end
1152
1153	def children
93a37866	1154	[@child]
6fe7ccc8 A	1155	end
	1156
	1157	def mapChildren
	1158	Not.new(codeOrigin, (yield @child))
	1159	end
	1160
	1161	def dump
	1162	"(not #{child.dump})"
	1163	end
	1164	end
	1165
	1166	class Skip < NoChildren
	1167	def initialize(codeOrigin)
	1168	super(codeOrigin)
	1169	end
	1170
	1171	def dump
	1172	"\tskip"
	1173	end
	1174	end
	1175
	1176	class IfThenElse < Node
	1177	attr_reader :predicate, :thenCase
	1178	attr_accessor :elseCase
	1179
	1180	def initialize(codeOrigin, predicate, thenCase)
	1181	super(codeOrigin)
	1182	@predicate = predicate
	1183	@thenCase = thenCase
	1184	@elseCase = Skip.new(codeOrigin)
	1185	end
	1186
	1187	def children
	1188	if @elseCase
	1189	[@predicate, @thenCase, @elseCase]
	1190	else
	1191	[@predicate, @thenCase]
	1192	end
	1193	end
	1194
	1195	def mapChildren
	1196	IfThenElse.new(codeOrigin, (yield @predicate), (yield @thenCase), (yield @elseCase))
	1197	end
	1198
	1199	def dump
	1200	"if #{predicate.dump}\n" + thenCase.dump + "\nelse\n" + elseCase.dump + "\nend"
	1201	end
	1202	end
	1203
	1204	class Macro < Node
	1205	attr_reader :name, :variables, :body
93a37866	1206
6fe7ccc8 A	1207	def initialize(codeOrigin, name, variables, body)
	1208	super(codeOrigin)
	1209	@name = name
	1210	@variables = variables
	1211	@body = body
	1212	end
	1213
	1214	def children
	1215	@variables + [@body]
	1216	end
	1217
	1218	def mapChildren
	1219	Macro.new(codeOrigin, @name, @variables.map{\|v\| yield v}, (yield @body))
	1220	end
	1221
	1222	def dump
	1223	"macro #{name}(" + variables.collect{\|v\| v.dump}.join(", ") + ")\n" + body.dump + "\nend"
	1224	end
	1225	end
	1226
	1227	class MacroCall < Node
93a37866	1228	attr_reader :name, :operands, :annotation
6fe7ccc8	1229
93a37866	1230	def initialize(codeOrigin, name, operands, annotation)
6fe7ccc8 A	1231	super(codeOrigin)
	1232	@name = name
	1233	@operands = operands
	1234	raise unless @operands
	1235	@operands.each{\|v\| raise unless v}
93a37866	1236	@annotation = annotation
6fe7ccc8 A	1237	end
	1238
	1239	def children
	1240	@operands
	1241	end
	1242
	1243	def mapChildren(&proc)
93a37866	1244	MacroCall.new(codeOrigin, @name, @operands.map(&proc), @annotation)
6fe7ccc8 A	1245	end
	1246
	1247	def dump
	1248	"\t#{name}(" + operands.collect{\|v\| v.dump}.join(", ") + ")"
	1249	end
	1250	end
	1251