formatter_bytecode.py

"""
Specification, compiler, disassembler, and interpreter
for LLDB dataformatter bytecode.

See https://lldb.llvm.org/resources/formatterbytecode.html for more details.
"""

from __future__ importannotations

# Types
type_String=1
type_Int=2
type_UInt=3
type_Object=4
type_Type=5

# Opcodes
opcode=dict()


defdefine_opcode(n, mnemonic, name):
globals()["op_"+name] =n
ifmnemonic:
opcode[mnemonic] =n
opcode[n] =mnemonic


define_opcode(1, "dup", "dup")
define_opcode(2, "drop", "drop")
define_opcode(3, "pick", "pick")
define_opcode(4, "over", "over")
define_opcode(5, "swap", "swap")
define_opcode(6, "rot", "rot")

define_opcode(0x10, "{", "begin")
define_opcode(0x11, "if", "if")
define_opcode(0x12, "ifelse", "ifelse")
define_opcode(0x13, "return", "return")

define_opcode(0x20, None, "lit_uint")
define_opcode(0x21, None, "lit_int")
define_opcode(0x22, None, "lit_string")
define_opcode(0x23, None, "lit_selector")

define_opcode(0x2A, "as_int", "as_int")
define_opcode(0x2B, "as_uint", "as_uint")
define_opcode(0x2C, "is_null", "is_null")

define_opcode(0x30, "+", "plus")
define_opcode(0x31, "-", "minus")
define_opcode(0x32, "*", "mul")
define_opcode(0x33, "/", "div")
define_opcode(0x34, "%", "mod")
define_opcode(0x35, "<<", "shl")
define_opcode(0x36, ">>", "shr")

define_opcode(0x40, "&", "and")
define_opcode(0x41, "|", "or")
define_opcode(0x42, "^", "xor")
define_opcode(0x43, "~", "not")

define_opcode(0x50, "=", "eq")
define_opcode(0x51, "!=", "neq")
define_opcode(0x52, "<", "lt")
define_opcode(0x53, ">", "gt")
define_opcode(0x54, "=<", "le")
define_opcode(0x55, ">=", "ge")

define_opcode(0x60, "call", "call")

# Function signatures
sig_summary=0
sig_init=1
sig_get_num_children=2
sig_get_child_index=3
sig_get_child_at_index=4

# Selectors
selector=dict()


defdefine_selector(n, name):
globals()["sel_"+name] =n
selector["@"+name] =n
selector[n] ="@"+name


define_selector(0, "summary")
define_selector(1, "type_summary")

define_selector(0x10, "get_num_children")
define_selector(0x11, "get_child_at_index")
define_selector(0x12, "get_child_with_name")
define_selector(0x13, "get_child_index")
define_selector(0x15, "get_type")
define_selector(0x16, "get_template_argument_type")
define_selector(0x17, "cast")
define_selector(0x20, "get_value")
define_selector(0x21, "get_value_as_unsigned")
define_selector(0x22, "get_value_as_signed")
define_selector(0x23, "get_value_as_address")

define_selector(0x40, "read_memory_byte")
define_selector(0x41, "read_memory_uint32")
define_selector(0x42, "read_memory_int32")
define_selector(0x43, "read_memory_unsigned")
define_selector(0x44, "read_memory_signed")
define_selector(0x45, "read_memory_address")
define_selector(0x46, "read_memory")

define_selector(0x50, "fmt")
define_selector(0x51, "sprintf")
define_selector(0x52, "strlen")


################################################################################
# Compiler.
################################################################################


defcompile(assembler: str) ->bytearray:
"""Compile assembler into bytecode"""
# This is a stack of all in-flight/unterminated blocks.
bytecode= [bytearray()]

defemit(byte):
bytecode[-1].append(byte)

tokens=list(assembler.split(" "))
tokens.reverse()
whiletokens:
tok=tokens.pop()
iftok=="":
pass
eliftok=="{":
bytecode.append(bytearray())
eliftok=="}":
block=bytecode.pop()
emit(op_begin)
emit(len(block)) # FIXME: uleb
bytecode[-1].extend(block)
eliftok[0].isdigit():
iftok[-1] =="u":
emit(op_lit_uint)
emit(int(tok[:-1])) # FIXME
else:
emit(op_lit_int)
emit(int(tok)) # FIXME
eliftok[0] =="@":
emit(op_lit_selector)
emit(selector[tok])
eliftok[0] =='"':
s=bytearray()
done=False
chrs=tok[1:]
whilenotdone:
quoted=False
forcinchrs:
ifquoted:
s.append(ord(c)) # FIXME
quoted=False
elifc=="\\":
quoted=True
elifc=='"':
done=True
break
# FIXME assert this is last in token
else:
s.append(ord(c))
ifnotdone:
s.append(ord(" "))
chrs=tokens.pop()

emit(op_lit_string)
emit(len(s))
bytecode[-1].extend(s)
else:
emit(opcode[tok])
assertlen(bytecode) ==1# unterminated {
returnbytecode[0]


################################################################################
# Disassembler.
################################################################################


defdisassemble(bytecode: bytearray) -> (str, int):
"""Disassemble bytecode into (assembler, token starts)"""
asm=""
all_bytes=list(bytecode)
all_bytes.reverse()
blocks= []
tokens= [0]

defnext_byte():
"""Fetch the next byte in the bytecode and keep track of all
 in-flight blocks"""
foriinrange(len(blocks)):
blocks[i] -=1
tokens.append(len(asm))
returnall_bytes.pop()

whileall_bytes:
b=next_byte()
ifb==op_begin:
asm+="{"
length=next_byte()
blocks.append(length)
elifb==op_lit_uint:
b=next_byte()
asm+=str(b) # FIXME uleb
asm+="u"
elifb==op_lit_int:
b=next_byte()
asm+=str(b)
elifb==op_lit_selector:
b=next_byte()
asm+=selector[b]
elifb==op_lit_string:
length=next_byte()
s="'"
whilelength:
s+=chr(next_byte())
length-=1
asm+='"'+repr(s)[2:]
else:
asm+=opcode[b]

whileblocksandblocks[-1] ==0:
asm+=" }"
blocks.pop()

ifall_bytes:
asm+=" "

ifblocks:
asm+="ERROR"
returnasm, tokens


################################################################################
# Interpreter.
################################################################################


defcount_fmt_params(fmt: str) ->int:
"""Count the number of parameters in a format string"""
fromstringimportFormatter

f=Formatter()
n=0
for_, name, _, _inf.parse(fmt):
ifname>n:
n=name
returnn


definterpret(bytecode: bytearray, control: list, data: list, tracing: bool=False):
"""Interpret bytecode"""
frame= []
frame.append((0, len(bytecode)))

deftrace():
"""print a trace of the execution for debugging purposes"""

deffmt(d):
ifisinstance(d, int):
returnstr(d)
ifisinstance(d, str):
returnd
returnrepr(type(d))

pc, end=frame[-1]
asm, tokens=disassemble(bytecode)
print(
"=== frame = {1}, data = {2}, opcode = {0}".format(
opcode[b], frame, [fmt(d) fordindata]
 )
 )
print(asm)
print(" "* (tokens[pc]) +"^")

defnext_byte():
"""Fetch the next byte and update the PC"""
pc, end=frame[-1]
assertpc<len(bytecode)
b=bytecode[pc]
frame[-1] =pc+1, end
# At the end of a block?
whilepc>=end:
frame.pop()
ifnotframe:
returnNone
pc, end=frame[-1]
ifpc>=end:
returnNone
b=bytecode[pc]
frame[-1] =pc+1, end
returnb

whileframe[-1][0] <len(bytecode):
b=next_byte()
ifb==None:
break
iftracing:
trace()
# Data stack manipulation.
ifb==op_dup:
data.append(data[-1])
elifb==op_drop:
data.pop()
elifb==op_pick:
data.append(data[data.pop()])
elifb==op_over:
data.append(data[-2])
elifb==op_swap:
x=data.pop()
y=data.pop()
data.append(x)
data.append(y)
elifb==op_rot:
z=data.pop()
y=data.pop()
x=data.pop()
data.append(z)
data.append(x)
data.append(y)

# Control stack manipulation.
elifb==op_begin:
length=next_byte()
pc, end=frame[-1]
control.append((pc, pc+length))
frame[-1] =pc+length, end
elifb==op_if:
ifdata.pop():
frame.append(control.pop())
elifb==op_ifelse:
ifdata.pop():
control.pop()
frame.append(control.pop())
else:
frame.append(control.pop())
control.pop()
elifb==op_return:
control.clear()
returndata[-1]

# Literals.
elifb==op_lit_uint:
b=next_byte() # FIXME uleb
data.append(int(b))
elifb==op_lit_int:
b=next_byte() # FIXME uleb
data.append(int(b))
elifb==op_lit_selector:
b=next_byte()
data.append(b)
elifb==op_lit_string:
length=next_byte()
s=""
whilelength:
s+=chr(next_byte())
length-=1
data.append(s)

elifb==op_as_uint:
pass
elifb==op_as_int:
pass
elifb==op_is_null:
data.append(1ifdata.pop() ==Noneelse0)

# Arithmetic, logic, etc.
elifb==op_plus:
data.append(data.pop() +data.pop())
elifb==op_minus:
data.append(-data.pop() +data.pop())
elifb==op_mul:
data.append(data.pop() *data.pop())
elifb==op_div:
y=data.pop()
data.append(data.pop() /y)
elifb==op_mod:
y=data.pop()
data.append(data.pop() %y)
elifb==op_shl:
y=data.pop()
data.append(data.pop() <<y)
elifb==op_shr:
y=data.pop()
data.append(data.pop() >>y)
elifb==op_and:
data.append(data.pop() &data.pop())
elifb==op_or:
data.append(data.pop() |data.pop())
elifb==op_xor:
data.append(data.pop() ^data.pop())
elifb==op_not:
data.append(notdata.pop())
elifb==op_eq:
data.append(data.pop() ==data.pop())
elifb==op_neq:
data.append(data.pop() !=data.pop())
elifb==op_lt:
data.append(data.pop() >data.pop())
elifb==op_gt:
data.append(data.pop() <data.pop())
elifb==op_le:
data.append(data.pop() >=data.pop())
elifb==op_ge:
data.append(data.pop() <=data.pop())

# Function calls.
elifb==op_call:
sel=data.pop()
ifsel==sel_summary:
data.append(data.pop().GetSummary())
elifsel==sel_get_num_children:
data.append(data.pop().GetNumChildren())
elifsel==sel_get_child_at_index:
index=data.pop()
valobj=data.pop()
data.append(valobj.GetChildAtIndex(index))
elifsel==sel_get_child_with_name:
name=data.pop()
valobj=data.pop()
data.append(valobj.GetChildMemberWithName(name))
elifsel==sel_get_child_index:
name=data.pop()
valobj=data.pop()
data.append(valobj.GetIndexOfChildWithName(name))
elifsel==sel_get_type:
data.append(data.pop().GetType())
elifsel==sel_get_template_argument_type:
n=data.pop()
valobj=data.pop()
data.append(valobj.GetTemplateArgumentType(n))
elifsel==sel_get_value:
data.append(data.pop().GetValue())
elifsel==sel_get_value_as_unsigned:
data.append(data.pop().GetValueAsUnsigned())
elifsel==sel_get_value_as_signed:
data.append(data.pop().GetValueAsSigned())
elifsel==sel_get_value_as_address:
data.append(data.pop().GetValueAsAddress())
elifsel==sel_cast:
sbtype=data.pop()
valobj=data.pop()
data.append(valobj.Cast(sbtype))
elifsel==sel_strlen:
s=data.pop()
data.append(len(s) ifselse0)
elifsel==sel_fmt:
fmt=data.pop()
n=count_fmt_params(fmt)
args= []
foriinrange(n):
args.append(data.pop())
data.append(fmt.format(*args))
else:
print("not implemented: "+selector[sel])
assertFalse
pass
returndata[-1]


if__name__=="__main__":
# Work around the fact that one of the local files is called
# types.py, which breaks some versions of python.
importos, sys

path=os.path.abspath(os.path.dirname(__file__))
sys.path.remove(path)
importargparse

parser=argparse.ArgumentParser(
description="""
 Compiler, disassembler, and interpreter for LLDB dataformatter bytecode.
 See https://lldb.llvm.org/resources/formatterbytecode.html for more details.
 """
 )
parser.add_argument(
"-c", "--compile", type=str, help="compile assembler into bytecode"
 )
parser.add_argument("-d", "--disassemble", type=str, help="disassemble bytecode")
parser.add_argument("-t", "--test", action="store_true", help="run unit tests")
args=parser.parse_args()
ifargs.compile:
print(compile(str(args.compile)).hex())

ifargs.disassemble:
print(disassemble(bytearray.fromhex(str(args.disassemble))))

############################################################################
# Tests.
############################################################################
ifargs.test:
importunittest

classTestCompiler(unittest.TestCase):
deftest(self):
self.assertEqual(compile("1u dup").hex(), "200101")
self.assertEqual(compile('"1u dup"').hex(), "2206317520647570")
self.assertEqual(compile("16 < { dup } if").hex(), "21105210010111")
self.assertEqual(compile('{ { " } " } }').hex(), "100710052203207d20")

defroundtrip(asm):
self.assertEqual(disassemble(compile(asm))[0], asm)

roundtrip("1u dup")
roundtrip('1u dup "1u dup"')
roundtrip("16 < { dup } if")
roundtrip('{ { " } " } }')

self.assertEqual(interpret(compile("1 1 +"), [], []), 2)
self.assertEqual(interpret(compile("2 1 1 + *"), [], []), 4)
self.assertEqual(
interpret(compile('2 1 > { "yes" } { "no" } ifelse'), [], []), "yes"
 )

importsys

sys.argv.pop()
path=os.path.dirname(__file__)
sys.path.remove
unittest.main()