Skip to content

Instantly share code, notes, and snippets.

@MrSmith33

MrSmith33/dmd_bug.d

Created October 10, 2018 08:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save MrSmith33/d8b2ecdbab7b16aa1f1238959e8b78a0 to your computer and use it in GitHub Desktop.
Save MrSmith33/d8b2ecdbab7b16aa1f1238959e8b78a0 to your computer and use it in GitHub Desktop.
Download ZIP
Error: CTFE internal error: ErrorExp
Raw
dmd_bug.d
import std.array : empty;
import std.string : format;
import std.typecons : Flag, Yes, No;
import std.stdio : writeln, write, writef, writefln, stdout;
import std.format : formattedWrite, FormatSpec;
import std.range : repeat;
import std.range : chain;
import std.bitmanip : bitfields;
import std.algorithm : min, max, sort, swap;
import std.stdio;
import std.string : format;
import std.traits : getUDAs, Parameters;
import std.bitmanip : bitfields;
import std.format : formattedWrite, FormatSpec;
/// Describes what IrIndex is pointing at
/// Is used as UDA on instructions
enum IrValueKind : ubyte
{
none, /// Used for undefined indicies
listItem, /// Indicates items of linked list in SmallVector
instruction,
basicBlock,
constant,
phi,
memoryAddress,
virtualRegister,
physicalRegister,
}
/// Represent index of any IR entity inside function's ir array
struct IrIndex
{
this(uint _storageUintIndex, IrValueKind _kind)
{
storageUintIndex = _storageUintIndex;
kind = _kind;
}
union
{
mixin(bitfields!(
uint, "storageUintIndex", 28, // is never 0 for defined index
IrValueKind, "kind", 4 // is never 0 for defined index
));
uint asUint; // is never 0 for defined index
}
static assert(IrValueKind.max <= 0b1111, "4 bits are reserved");
bool isDefined() { return asUint != 0; }
void toString(scope void delegate(const(char)[]) sink) const {
}
IrIndexPrinter printer(IrFunction* func) { return IrIndexPrinter(this, func); }
/// When this index represents index of 0's array item, produces
/// index of this array items. Calling with 0 returns itself.
IrIndex indexOf(T)(size_t offset)
{
static assert(T.alignof == 4, "Can only point to types aligned to 4 bytes");
IrIndex result = this;
result.storageUintIndex = cast(uint)(storageUintIndex + divCeil(T.sizeof, uint.sizeof) * offset);
return result;
}
}
struct IrIndexPrinter
{
IrIndex index;
IrFunction* ir;
void toString(scope void delegate(const(char)[]) sink) {
}
}
struct IrLabel
{
/// If numPredecessors == 0, is null
/// If numPredecessors == 1, points to first predecessor
/// If numPredecessors > 1, points to a new block
IrIndex blockIndex;
///
uint numPredecessors;
}
enum HasResult : bool { no, yes }
struct InstrInfo
{
IrValueKind kind;
uint numArgs;
HasResult hasResult;
}
enum getInstrInfo(T) = getUDAs!(T, InstrInfo)[0];
/// Stores numeric constant data
@InstrInfo(IrValueKind.constant)
struct IrConstant
{
this(long value) {
this.i64 = value;
}
ubyte numSignedBytes() {
if (cast(byte)(i64 & 0xFF) == i64)
return 1;
else if (cast(short)(i64 & 0xFFFF) == i64)
return 2;
else if (cast(int)(i64 & 0xFFFF_FFFF) == i64)
return 4;
else
return 8;
}
ubyte numUnsignedBytes() {
if (cast(ubyte)(i64 & 0xFF) == i64)
return 1;
else if (cast(ushort)(i64 & 0xFFFF) == i64)
return 2;
else if (cast(uint)(i64 & 0xFFFF_FFFF) == i64)
return 4;
else
return 8;
}
union {
bool i1;
byte i8;
short i16;
int i32;
long i64;
}
}
///
@InstrInfo(IrValueKind.phi)
struct IrPhiInstr
{
IrIndex blockIndex;
IrIndex result;
IrIndex nextPhi;
IrIndex prevPhi;
IrIndex firstArgListItem;
PhiArgIterator args(IrFunction* ir) { return PhiArgIterator(ir, firstArgListItem); }
}
struct PhiArgIterator
{
IrFunction* ir;
IrIndex firstArgListItem;
int opApply(scope int delegate(size_t, ref IrPhiArg) dg) {
IrIndex next = firstArgListItem;
size_t i = 0;
while (next.isDefined)
{
IrPhiArg* arg = &ir.get!IrPhiArg(next);
if (int res = dg(i, *arg))
return res;
++i;
next = arg.nextListItem;
}
return 0;
}
}
///
@InstrInfo(IrValueKind.listItem)
struct IrPhiArg
{
IrIndex value;
IrIndex basicBlock;
IrIndex nextListItem;
}
/// Per Basic Block info for unresolved Phi functions, when CFG is incomplete.
/// Finished IR contains no such values
@InstrInfo(IrValueKind.listItem)
struct IrIncompletePhi
{
IrVar var;
IrIndex phi;
IrIndex nextListItem;
}
enum IrOpcode : ubyte
{
parameter,
block_header,
block_exit_jump,
block_exit_unary_branch,
block_exit_binary_branch,
block_exit_return_void,
block_exit_return_value,
store,
load
}
@InstrInfo(IrValueKind.virtualRegister)
struct IrVirtualRegister
{
/// Index of instruction that defines this register
IrIndex definition;
/// List of instruction indicies that use this register
SmallVector users;
}
/// Must end with one of block_exit_... instructions
@InstrInfo(IrValueKind.basicBlock)
struct IrBasicBlockInstr
{
IrIndex firstInstr; // null or first instruction
IrIndex lastInstr; // null or last instruction
IrIndex prevBlock; // null only if this is entryBasicBlock
IrIndex nextBlock; // null only if this is exitBasicBlock
IrIndex firstPhi; // may be null
PhiIterator phis(IrFunction* ir) { return PhiIterator(ir, &this); }
InstrIterator instructions(IrFunction* ir) { return InstrIterator(ir, &this); }
SmallVector predecessors;
SmallVector successors;
uint seqIndex;
/// True if all predecessors was added
bool isSealed;
IrName name;
}
pragma(msg, "BB size: ", cast(int)IrBasicBlockInstr.sizeof, " bytes");
struct PhiIterator
{
IrFunction* ir;
IrBasicBlockInstr* block;
int opApply(scope int delegate(IrIndex, ref IrPhiInstr) dg) {
IrIndex next = block.firstPhi;
while (next.isDefined)
{
IrPhiInstr* phi = &ir.get!IrPhiInstr(next);
if (int res = dg(next, *phi))
return res;
next = phi.nextPhi;
}
return 0;
}
}
struct InstrIterator
{
IrFunction* ir;
IrBasicBlockInstr* block;
int opApply(scope int delegate(IrIndex, ref IrInstrHeader) dg) {
IrIndex next = block.firstInstr;
while (next.isDefined)
{
IrInstrHeader* header = &ir.get!IrInstrHeader(next);
if (int res = dg(next, *header))
return res;
next = header.nextInstr;
}
return 0;
}
}
/// Common prefix of all IR instruction structs
@InstrInfo(IrValueKind.instruction)
struct IrInstrHeader
{
ushort op;
ubyte numArgs;
union
{
mixin(bitfields!(
HasResult, "hasResult", 1,
IrBinaryCondition, "binaryCond", 3,
uint, "", 4
));
mixin(bitfields!(
uint, "", 1,
IrUnaryCondition, "unaryCond", 3,
uint, "", 4
));
}
static assert(IrBinaryCondition.max <= 0b111, "3 bits are reserved");
static assert(IrUnaryCondition.max <= 0b111, "3 bits are reserved");
//HasResult hasResult;
IrIndex prevInstr;
IrIndex nextInstr;
IrIndex[0] _payload;
ref IrIndex result() {
assert(hasResult);
return _payload.ptr[0];
}
IrIndex[] args() {
return _payload.ptr[cast(size_t)hasResult..cast(size_t)hasResult+numArgs];
}
}
template IrGenericInstr(uint numArgs, HasResult hasResult)
{
@InstrInfo(IrValueKind.instruction, numArgs, hasResult)
struct IrGenericInstr
{
IrInstrHeader header;
static if (hasResult) IrIndex result;
static if (numArgs > 0) IrIndex[numArgs] args;
}
}
alias IrReturnValueInstr = IrGenericInstr!(1, HasResult.no);
alias IrReturnVoidInstr = IrGenericInstr!(0, HasResult.no);
alias IrStoreInstr = IrGenericInstr!(1, HasResult.no);
alias IrLoadInstr = IrGenericInstr!(1, HasResult.yes);
enum IrBinaryCondition : ubyte {
eq,
ne,
l,
le,
g,
ge
}
string[] binaryCondStrings = cast(string[IrBinaryCondition.max+1])["==", "!=", "<", "<=", ">", ">="];
/// Uses header.binaryCond
@InstrInfo(IrValueKind.instruction, 2, HasResult.no)
struct IrInstrBinaryBranch
{
IrInstrHeader header;
IrIndex[2] args;
}
enum IrUnaryCondition : ubyte {
zero,
not_zero
}
/// Uses header.unaryCond
@InstrInfo(IrValueKind.instruction, 1, HasResult.no)
struct IrInstrUnaryBranch
{
IrInstrHeader header;
IrIndex arg;
}
@InstrInfo(IrValueKind.instruction, 0, HasResult.yes)
struct IrInstrParameter
{
IrInstrHeader header;
IrIndex result;
uint index;
}
struct IrVarId { uint id; alias id this; }
struct IrVar { Identifier name; IrVarId id; IrValueType type; }
enum IrValueType : ubyte
{
void_t,
i32,
i64,
//f32,
//f64,
ptr,
}
struct BlockVarPair
{
IrIndex blockId;
IrVarId varId;
}
struct IrModule
{
IrFunction*[] functions;
void dump(ref TextSink sink, CompilationContext* context)
{
foreach (func; functions) dumpFunction(func, sink);
}
}
struct IrFunction
{
FixedBuffer!uint* storage;
FixedBuffer!uint* temp;
uint numBasicBlocks;
/// Special block. Automatically created. Program start. Created first.
IrIndex entryBasicBlock;
/// Special block. Automatically created. All returns must jump to it.
IrIndex exitBasicBlock;
// The last created basic block
IrIndex lastBasicBlock;
///
IrValueType returnType;
BlockIterator blocks() { return BlockIterator(&this); }
alias getBlock = get!IrBasicBlockInstr;
ref T get(T)(IrIndex index)
{
assert(index.kind != IrValueKind.none, "null index");
assert(index.kind == getInstrInfo!T.kind, format("%s != %s", index.kind, getInstrInfo!T.kind));
return *cast(T*)(&storage.bufPtr[index.storageUintIndex]);
}
ref T getTemp(T)(IrIndex index)
{
assert(index.kind != IrValueKind.none, "null index");
assert(index.kind == getInstrInfo!T.kind, format("%s != %s", index.kind, getInstrInfo!T.kind));
return *cast(T*)(&temp.bufPtr[index.storageUintIndex]);
}
/// Returns index to allocated item
/// Allocates howMany items. By default allocates single item.
/// If howMany > 1 - returns index of first item, access other items via IrIndex.indexOf
/// T must have UDA of InstrInfo() value
IrIndex append(T)(uint howMany = 1)
{
static assert(T.alignof == 4 || is(T == IrConstant), "Can only store types aligned to 4 bytes");
IrIndex result;
result.storageUintIndex = storage.length;
result.kind = getInstrInfo!T.kind;
storage.voidPut(divCeil(T.sizeof, uint.sizeof)*howMany);
(&get!T(result))[0..howMany] = T.init;
return result;
}
/// ditto
IrIndex appendTemp(T)(uint howMany = 1)
{
static assert(T.alignof == 4 || is(T == IrConstant), "Can only store types aligned to 4 bytes");
IrIndex result;
result.storageUintIndex = temp.length;
result.kind = getInstrInfo!T.kind;
temp.voidPut(divCeil(T.sizeof, uint.sizeof)*howMany);
(&getTemp!T(result))[0..howMany] = T.init;
return result;
}
/// Adds control-flow edge pointing `fromBlock` -> `toBlock`.
void addBlockTarget(IrIndex fromBasicBlockIndex, IrIndex toBasicBlockIndex) {
getBlock(fromBasicBlockIndex).successors.append(&this, toBasicBlockIndex);
getBlock(toBasicBlockIndex).predecessors.append(&this, fromBasicBlockIndex);
}
/// Does not remove its instructions/phis
/*void removeBasicBlock(IrIndex basicBlockToRemove) {
--numBasicBlocks;
IrBasicBlockInstr* bb = &get!IrBasicBlockInstr(basicBlockToRemove);
if (bb.prevBlock.isDefined)
getBlock(bb.prevBlock).nextBlock = bb.nextBlock;
if (bb.nextBlock.isDefined)
getBlock(bb.nextBlock).prevBlock = bb.prevBlock;
}*/
void computeBlockOrder()
{
uint[] orderArray = temp.voidPut(numBasicBlocks);
scope(exit) temp.clear;
// todo
}
}
struct BlockIterator
{
IrFunction* ir;
int opApply(scope int delegate(IrIndex, ref IrBasicBlockInstr) dg) {
IrIndex next = ir.entryBasicBlock;
while (next.isDefined)
{
IrBasicBlockInstr* block = &ir.getBlock(next);
if (int res = dg(next, *block))
return res;
next = block.nextBlock;
}
return 0;
}
}
// papers:
// 1. Simple and Efficient Construction of Static Single Assignment Form
struct IrBuilder
{
IrFunction* ir;
IrIndex currentBB;
// Stores current definition of variable per block during SSA-form IR construction.
private IrIndex[BlockVarPair] blockVarDef;
private IrIndex[IrIndex] blockToIrIncompletePhi;
private IrVarId nextIrVarId;
IrVar returnVar;
/// Must be called before compilation of each function. Allows reusing temp buffers.
/// Sets up entry and exit basic blocks.
void begin(IrFunction* ir) {
this.ir = ir;
blockVarDef.clear();
// Add dummy item into storage, since 0 index represents null
if (ir.storage.length == 0)
ir.storage.put(0);
// Canonical function CFG has entry block, and single exit block.
ir.numBasicBlocks = 2;
ir.entryBasicBlock = ir.append!IrBasicBlockInstr;
ir.exitBasicBlock = ir.append!IrBasicBlockInstr;
ir.getBlock(ir.entryBasicBlock).nextBlock = ir.exitBasicBlock;
sealBlock(ir.entryBasicBlock);
ir.getBlock(ir.exitBasicBlock).prevBlock = ir.entryBasicBlock;
currentBB = ir.entryBasicBlock;
if (ir.returnType != IrValueType.void_t)
{
IrIndex retIndex = addInstruction!IrReturnValueInstr(ir.exitBasicBlock, IrOpcode.block_exit_return_value);
returnVar = IrVar(Identifier(0), newIrVarId());
IrIndex retValue = readVariable(ir.exitBasicBlock, returnVar);
ir.get!IrReturnValueInstr(retIndex).args[0] = retValue;
addUser(retIndex, retValue);
}
else
{
addInstruction!IrReturnVoidInstr(ir.exitBasicBlock, IrOpcode.block_exit_return_void);
}
}
/// Sets currentBB to this block
IrIndex addBasicBlock() {
assert(currentBB.isDefined);
++ir.numBasicBlocks;
IrIndex newBlock = ir.append!IrBasicBlockInstr;
ir.getBlock(newBlock).nextBlock = ir.getBlock(currentBB).nextBlock;
ir.getBlock(newBlock).prevBlock = currentBB;
ir.getBlock(ir.getBlock(currentBB).nextBlock).prevBlock = newBlock;
ir.getBlock(currentBB).nextBlock = newBlock;
currentBB = newBlock;
return currentBB;
}
// Algorithm 4: Handling incomplete CFGs
/// Basic block is sealed if no further predecessors will be added to the block.
/// Sealed block is not necessarily filled.
/// Ignores already sealed blocks.
void sealBlock(IrIndex basicBlockToSeal) {
IrBasicBlockInstr* bb = &ir.getBlock(basicBlockToSeal);
if (bb.isSealed) return;
IrIndex index = blockToIrIncompletePhi.get(basicBlockToSeal, IrIndex());
while (index.isDefined)
{
IrIncompletePhi ip = ir.getTemp!IrIncompletePhi(index);
addPhiOperands(basicBlockToSeal, ip.var, ip.phi);
index = ip.nextListItem;
}
blockToIrIncompletePhi.remove(basicBlockToSeal);
bb.isSealed = true;
}
/// Allocates new variable id for this function. It should be bound to a variable
/// and used with writeVariable, readVariable functions
IrVarId newIrVarId() {
return IrVarId(nextIrVarId++);
}
// Algorithm 1: Implementation of local value numbering
/// Redefines `variable` with `value`. Is used for assignment to variable
void writeVariable(IrIndex blockIndex, IrVar variable, IrIndex value) {
with(IrValueKind)
{
assert(
value.kind == constant ||
value.kind == virtualRegister ||
value.kind == physicalRegister, format("%s", value));
}
blockVarDef[BlockVarPair(blockIndex, variable.id)] = value;
}
/// Returns the value that currently defines `variable` within `blockIndex`
IrIndex readVariable(IrIndex blockIndex, IrVar variable) {
if (auto irRef = BlockVarPair(blockIndex, variable.id) in blockVarDef)
return *irRef;
return readVariableRecursive(blockIndex, variable);
}
/// Puts `user` into a list of users of `used` value
void addUser(IrIndex user, IrIndex used) {
assert(user.isDefined, "user is undefined");
assert(used.isDefined, "used is undefined");
final switch (used.kind) with(IrValueKind) {
case none: assert(false);
case listItem: assert(false);
case instruction: assert(false);
case basicBlock: assert(false);
case constant: break; // allowed, noop
case phi: assert(false); // must be virt reg instead
case memoryAddress: break; // allowed, noop
case virtualRegister:
ir.get!IrVirtualRegister(used).users.append(ir, user);
break;
case physicalRegister: break; // allowed, noop
}
}
IrIndex addInstruction(I)(IrIndex blockIndex, ushort op) {
IrBasicBlockInstr* block = &ir.getBlock(blockIndex);
IrIndex instr = ir.append!I;
IrInstrHeader* instrHeader = &ir.get!IrInstrHeader(instr);
instrHeader.op = op;
instrHeader.prevInstr = block.lastInstr; // points to prev instruction or to null
instrHeader.numArgs = getInstrInfo!I.numArgs;
instrHeader.hasResult = getInstrInfo!I.hasResult;
if (instrHeader.hasResult)
{
instrHeader.result = addVirtualRegister(instr);
}
if (!block.firstInstr.isDefined) {
block.firstInstr = instr;
block.lastInstr = instr;
} else {
ir.get!IrInstrHeader(block.lastInstr).nextInstr = instr;
}
// TODO add users
return instr;
}
IrIndex addBinBranch(IrIndex blockIndex, IrBinaryCondition cond, IrIndex arg0, IrIndex arg1)
{
auto branch = addInstruction!IrInstrBinaryBranch(blockIndex, IrOpcode.block_exit_binary_branch);
with(ir.get!IrInstrBinaryBranch(branch)) {
header.binaryCond = cond;
args = [arg0, arg1];
}
addUser(branch, arg0);
addUser(branch, arg1);
return branch;
}
void addReturn(IrIndex blockIndex, IrIndex returnValue)
{
assert(ir.returnType != IrValueType.void_t);
writeVariable(blockIndex, returnVar, returnValue);
addJump(blockIndex);
ir.addBlockTarget(blockIndex, ir.exitBasicBlock);
}
void addReturn(IrIndex blockIndex)
{
assert(ir.returnType == IrValueType.void_t);
addJump(blockIndex);
ir.addBlockTarget(blockIndex, ir.exitBasicBlock);
}
IrIndex addJump(IrIndex blockIndex)
{
return addInstruction!(IrGenericInstr!(0, HasResult.no))(blockIndex, IrOpcode.block_exit_jump);
}
void addJumpToLabel(IrIndex blockIndex, ref IrLabel label)
{
switch (label.numPredecessors)
{
case 0:
// label.blockIndex points to block that started the scope
// no block was created for label yet
label.numPredecessors = 1;
label.blockIndex = blockIndex;
break;
case 1:
// label.blockIndex points to the only predecessor of label block
// no block was created for label yet
label.numPredecessors = 1;
IrIndex firstPred = label.blockIndex;
label.blockIndex = addBasicBlock;
ir.addBlockTarget(firstPred, label.blockIndex);
addJump(firstPred);
goto default;
default:
// label.blockIndex points label block with multiple predecessors
++label.numPredecessors;
ir.addBlockTarget(blockIndex, label.blockIndex);
addJump(blockIndex);
break;
}
}
IrIndex addConstant(IrConstant con) {
IrIndex conIndex = ir.append!IrConstant;
ir.get!IrConstant(conIndex) = con;
return conIndex;
}
private void incBlockRefcount(IrIndex basicBlock) { assert(false); }
private void decBlockRefcount(IrIndex basicBlock) { assert(false); }
// Creates operand for result of phi/instruction that is defined by `definition`
private IrIndex addVirtualRegister(IrIndex definition) {
IrIndex virtRegIndex = ir.append!IrVirtualRegister;
IrVirtualRegister* virtReg = &ir.get!IrVirtualRegister(virtRegIndex);
virtReg.definition = definition;
return virtRegIndex;
}
// ignores null opdId
private void removeVirtualRegister(IrIndex vreg) {
// noop
// TODO: freelist?
}
// Adds phi function to specified block
private IrIndex addPhi(IrIndex blockIndex) {
IrIndex phiIndex = ir.append!IrPhiInstr;
IrIndex vreg = addVirtualRegister(phiIndex);
ir.get!IrPhiInstr(phiIndex) = IrPhiInstr(blockIndex, vreg);
IrBasicBlockInstr* block = &ir.getBlock(blockIndex);
if (block.firstPhi.isDefined) {
ir.get!IrPhiInstr(block.firstPhi).prevPhi = phiIndex;
ir.get!IrPhiInstr(phiIndex).nextPhi = block.firstPhi;
}
block.firstPhi = phiIndex;
return phiIndex;
}
private void removePhi(IrIndex phiIndex)
{
writefln("remove phi %s", phiIndex);
IrPhiInstr* phi = &ir.get!IrPhiInstr(phiIndex);
IrBasicBlockInstr* block = &ir.getBlock(phi.blockIndex);
foreach(IrIndex phiIndex, ref IrPhiInstr phi; block.phis(ir))
{
writefln(" %s = %s", phi.result, phiIndex);
}
// TODO: free list of phis
if (block.firstPhi == phiIndex) block.firstPhi = phi.nextPhi;
if (phi.nextPhi.isDefined) ir.get!IrPhiInstr(phi.nextPhi).prevPhi = phi.prevPhi;
if (phi.prevPhi.isDefined) ir.get!IrPhiInstr(phi.prevPhi).nextPhi = phi.nextPhi;
writefln("after remove phi %s", phiIndex);
IrBasicBlockInstr* block1 = &ir.getBlock(phi.blockIndex);
foreach(IrIndex phiIndex, ref IrPhiInstr phi; block1.phis(ir))
{
writefln(" %s = %s", phi.result, phiIndex);
}
}
// Algorithm 2: Implementation of global value numbering
/// Returns the last value of the variable in basic block
private IrIndex readVariableRecursive(IrIndex blockIndex, IrVar variable) {
IrIndex value;
if (!ir.getBlock(blockIndex).isSealed) {
// Incomplete CFG
IrIndex phiIndex = addPhi(blockIndex);
value = ir.get!IrPhiInstr(phiIndex).result;
blockToIrIncompletePhi.update(blockIndex,
{
IrIndex incompletePhi = ir.appendTemp!IrIncompletePhi;
ir.getTemp!IrIncompletePhi(incompletePhi) = IrIncompletePhi(variable, phiIndex);
return incompletePhi;
},
(ref IrIndex oldPhi)
{
IrIndex incompletePhi = ir.appendTemp!IrIncompletePhi;
ir.getTemp!IrIncompletePhi(incompletePhi) = IrIncompletePhi(variable, phiIndex, oldPhi);
return incompletePhi;
});
}
else
{
SmallVector preds = ir.getBlock(blockIndex).predecessors;
if (preds.length == 1) {
// Optimize the common case of one predecessor: No phi needed
value = readVariable(preds[0, ir], variable);
}
else
{
// Break potential cycles with operandless phi
IrIndex phiIndex = addPhi(blockIndex);
value = ir.get!IrPhiInstr(phiIndex).result;
writeVariable(blockIndex, variable, value);
value = addPhiOperands(blockIndex, variable, phiIndex);
}
}
with(IrValueKind)
{
assert(
value.kind == constant ||
value.kind == virtualRegister ||
value.kind == physicalRegister, format("%s", value));
}
writeVariable(blockIndex, variable, value);
return value;
}
// Adds all values of variable as arguments of phi. Values are gathered from block's predecessors.
// Returns either φ result virtual register or one of its arguments if φ is trivial
private IrIndex addPhiOperands(IrIndex blockIndex, IrVar variable, IrIndex phi) {
// Determine operands from predecessors
foreach (i, predIndex; ir.getBlock(blockIndex).predecessors.range(ir))
{
IrIndex value = readVariable(predIndex, variable);
writefln("phi operand %s", value);
// Phi should not be cached before loop, since readVariable can add phi to phis, reallocating the array
addPhiArg(phi, predIndex, value);
addUser(phi, value);
}
return tryRemoveTrivialPhi(phi);
}
private void addPhiArg(IrIndex phiIndex, IrIndex blockIndex, IrIndex value)
{
IrIndex phiArg = ir.append!IrPhiArg;
auto phi = &ir.get!IrPhiInstr(phiIndex);
ir.get!IrPhiArg(phiArg) = IrPhiArg(value, blockIndex, phi.firstArgListItem);
phi.firstArgListItem = phiArg;
}
// Algorithm 3: Detect and recursively remove a trivial φ function
// Returns either φ result virtual register or one of its arguments if φ is trivial
private IrIndex tryRemoveTrivialPhi(IrIndex phiIndex) {
IrPhiArg same;
foreach (size_t i, ref IrPhiArg phiArg; ir.get!IrPhiInstr(phiIndex).args(ir))
{
writefln("arg %s", phiArg.value);
if (phiArg.value == same.value || phiArg.value == phiIndex) {
writefln(" same");
continue; // Unique value or self−reference
}
if (same != IrPhiArg()) {
writefln(" non-trivial");
return ir.get!IrPhiInstr(phiIndex).result; // The phi merges at least two values: not trivial
}
writefln(" same = %s", phiArg.value);
same = phiArg;
}
writefln(" trivial");
assert(same.value.isDefined, "Phi function got no arguments");
// Remember all users except the phi itself
IrIndex phiResultIndex = ir.get!IrPhiInstr(phiIndex).result;
assert(phiResultIndex.kind == IrValueKind.virtualRegister, format("%s", phiResultIndex));
SmallVector users = ir.get!IrVirtualRegister(phiResultIndex).users;
// Reroute all uses of phi to same and remove phi
replaceBy(users, phiResultIndex, same);
removePhi(phiIndex);
// Try to recursively remove all phi users, which might have become trivial
foreach (i, index; users.range(ir))
if (index.kind == IrValueKind.phi && index != phiIndex)
tryRemoveTrivialPhi(index);
removeVirtualRegister(phiResultIndex);
return same.value;
}
IrIndex definitionOf(IrIndex someIndex)
{
final switch (someIndex.kind) with(IrValueKind) {
case none: assert(false);
case listItem: assert(false);
case instruction: return someIndex;
case basicBlock: assert(false);
case constant: assert(false);
case phi: return someIndex;
case memoryAddress: assert(false); // TODO
case virtualRegister: return ir.get!IrVirtualRegister(someIndex).definition;
case physicalRegister: assert(false);
}
}
// ditto
/// Rewrites all users of phi to point to `byWhat` instead of its result `what`.
/// `what` is the result of phi (vreg), `phiUsers` is users of `what`
private void replaceBy(SmallVector phiUsers, IrIndex what, IrPhiArg byWhat) {
foreach (size_t i, IrIndex userIndex; phiUsers.range(ir))
{
final switch (userIndex.kind) with(IrValueKind) {
case none: assert(false);
case listItem: assert(false);
case instruction:
foreach (ref IrIndex arg; ir.get!IrInstrHeader(userIndex).args)
if (arg == what)
{
arg = byWhat.value;
replaceUserWith(byWhat.value, definitionOf(what), userIndex);
}
break;
case basicBlock: assert(false);
case constant: assert(false);
case phi:
foreach (size_t i, ref IrPhiArg phiArg; ir.get!IrPhiInstr(userIndex).args(ir))
if (phiArg.value == what)
{
phiArg = byWhat;
replaceUserWith(byWhat.value, definitionOf(what), userIndex);
}
break;
case memoryAddress: assert(false); // TODO
case virtualRegister: assert(false);
case physicalRegister: assert(false);
}
}
}
private void replaceUserWith(IrIndex used, IrIndex what, IrIndex byWhat) {
final switch (used.kind) with(IrValueKind) {
case none, listItem, basicBlock, physicalRegister: assert(false);
case instruction: return ir.get!IrVirtualRegister(ir.get!IrInstrHeader(used).result).users.replaceAll(ir, what, byWhat);
case constant: return; // constants dont track users
case phi: return ir.get!IrVirtualRegister(ir.get!IrPhiInstr(used).result).users.replaceAll(ir, what, byWhat);
case memoryAddress: assert(false); // TODO, has single user
case virtualRegister: return ir.get!IrVirtualRegister(used).users.replaceAll(ir, what, byWhat);
}
}
}
/// Used for linked list
@InstrInfo(IrValueKind.listItem)
struct ListItem
{
IrIndex itemIndex;
IrIndex nextItem;
}
/// Allows storing 2 items inline, or linked list's info if more than 2 items are needed
struct SmallVector
{
union {
IrIndex[2] items; // .kind != IrValueKind.listItem
struct {
IrIndex firstListItem; // .kind == IrValueKind.listItem
uint listLength;
}
}
uint length()
{
if (items[0].kind == IrValueKind.listItem)
return listLength;
else if (items[1].isDefined)
return 2;
else if (items[0].isDefined)
return 1;
else
return 0;
}
bool isBig()
{
return items[0].kind == IrValueKind.listItem;
}
SmallVectorRange range(IrFunction* ir)
{
return SmallVectorRange(&this, ir);
}
void replaceAll(IrFunction* ir, IrIndex what, IrIndex byWhat)
{
foreach (ref IrIndex item; range(ir))
{
if (item == what) item = byWhat;
}
}
IrIndex opIndex(size_t index, IrFunction* ir)
{
size_t len = length;
assert(index < len);
if (len < 3) return items[index];
foreach(i, val; range(ir))
if (i == index)
return val;
assert(false);
}
void append(IrFunction* ir, IrIndex itemData)
{
assert(itemData.kind != IrValueKind.listItem, "listItem is not storable inside SmallVector");
assert(itemData.kind != IrValueKind.none, "IrValueKind.none is not storable inside SmallVector");
if (isBig)
{
IrIndex newListItemIndex = ir.append!ListItem;
ListItem* listItem = &ir.get!ListItem(newListItemIndex);
*listItem = ListItem(itemData, firstListItem);
firstListItem = newListItemIndex;
++listLength;
}
else
{
if (!items[0].isDefined)
{
items[0] = itemData;
}
else if (!items[1].isDefined)
{
items[1] = itemData;
}
else
{
IrIndex arrayIndex = ir.append!ListItem(3);
ListItem* itemArray = &ir.get!ListItem(arrayIndex);
itemArray[2] = ListItem(itemData);
itemArray[1] = ListItem(items[1], arrayIndex.indexOf!ListItem(2));
itemArray[0] = ListItem(items[0], arrayIndex.indexOf!ListItem(1));
firstListItem = arrayIndex;
listLength = 3;
}
}
}
void toString(scope void delegate(const(char)[]) sink)
{
if (isBig)
sink.formattedWrite("[%s items]", listLength);
else if (items[1].isDefined)
sink.formattedWrite("[%s, %s]", items[0], items[1]);
else if (items[0].isDefined)
sink.formattedWrite("[%s]", items[0]);
else sink("[]");
}
}
unittest
{
IrFunction ir;
ir.storage.setBuffer(new uint[1024]);
ir.temp.setBuffer(new uint[1024]);
SmallVector vec;
assert(vec.length == 0);
assert(!vec.isBig);
vec.append(&ir, IrIndex(1, IrValueKind.instruction));
assert(vec.length == 1);
assert(!vec.isBig);
vec.append(&ir, IrIndex(2, IrValueKind.instruction));
assert(vec.length == 2);
assert(!vec.isBig);
vec.append(&ir, IrIndex(3, IrValueKind.instruction));
assert(vec.length == 3);
assert(vec.isBig);
vec.append(&ir, IrIndex(4, IrValueKind.instruction));
assert(vec.length == 4);
assert(vec.isBig);
}
struct SmallVectorRange
{
SmallVector* vector;
IrFunction* ir;
int opApply(scope int delegate(size_t, ref IrIndex) dg)
{
return opApplyImpl!2(dg);
}
int opApply(scope int delegate(ref IrIndex) dg)
{
return opApplyImpl!1(dg);
}
int opApplyImpl(uint size, Del)(scope Del dg)
{
if (vector.isBig) // length > 2
{
IrIndex next = vector.firstListItem;
size_t seqIndex = 0;
while (next.isDefined)
{
ListItem* listItem = &ir.get!ListItem(next);
next = listItem.nextItem;
static if (size == 2) {
if (int res = dg(seqIndex, listItem.itemIndex))
return res;
++seqIndex;
} else {
if (int res = dg(listItem.itemIndex))
return res;
}
}
}
else // 0, 1, 2
{
if (vector.items[0].isDefined)
{
static if (size == 2) {
if (int res = dg(0, vector.items[0])) return res;
if (vector.items[1].isDefined)
{
if (int res = dg(1, vector.items[1])) return res;
}
} else {
if (int res = dg(vector.items[0])) return res;
if (vector.items[1].isDefined)
{
if (int res = dg(vector.items[1])) return res;
}
}
}
}
return 0;
}
}
import std.traits : isIntegral;
public import std.algorithm : min, max;
import std.stdio;
import std.string : format;
enum size_t PAGE_SIZE = 4096;
version(Posix)
{
ubyte[] allocate(size_t bytes, void* location, bool is_executable)
{
import core.sys.posix.sys.mman : mmap, MAP_ANON, PROT_READ,
PROT_WRITE, PROT_EXEC, MAP_PRIVATE, MAP_FAILED;
if (!bytes) return null;
int protection = PROT_READ | PROT_WRITE | (is_executable ? PROT_EXEC : 0);
auto p = mmap(location, bytes, protection, MAP_PRIVATE | MAP_ANON, -1, 0);
if (p is MAP_FAILED) return null;
return cast(ubyte[])p[0 .. bytes];
}
bool deallocate(ubyte[] b)
{
import core.sys.posix.sys.mman : munmap;
if (b.ptr) munmap(b.ptr, b.length) == 0 || assert(0);
return true;
}
}
else version(Windows)
{
import core.sys.windows.windows : GetLastError, VirtualAlloc, VirtualFree, VirtualProtect, MEM_COMMIT,
PAGE_READWRITE, MEM_RELEASE, PAGE_EXECUTE_READWRITE, MEM_RESERVE;
ubyte[] allocate(size_t bytes, void* location, MemType memoryType)
{
if (!bytes) return null;
int protection;
final switch(memoryType)
{
case MemType.RW: protection = PAGE_READWRITE; break;
case MemType.RWX: protection = PAGE_EXECUTE_READWRITE; break;
}
auto p = VirtualAlloc(location, bytes, MEM_COMMIT | MEM_RESERVE, protection);
if (p == null)
{
import std.stdio;
import std.windows.syserror;
int errCode = GetLastError();
writefln("allocate(%s:bytes, %s:location, %s:memoryType", bytes, location, memoryType);
writeln(sysErrorString(errCode));
assert(false, "VirtualAlloc alloc failed");
return null;
}
return cast(ubyte[])p[0 .. bytes];
}
bool deallocate(ubyte[] b)
{
return b.ptr is null || VirtualFree(b.ptr, 0, MEM_RELEASE) != 0;
}
void markAsRW(void* addr, size_t numPages)
{
uint val;
VirtualProtect(addr, numPages*PAGE_SIZE, PAGE_READWRITE, &val);
}
void testAdresses()
{
import std.stdio;
import std.windows.syserror;
import core.sys.windows.windows;
size_t successful;
size_t failed;
size_t bytes = PAGE_SIZE * 1024;
foreach(ulong loc; 0..16 * 16)
{
void* location = cast(void*)(loc*64*1024*1024);
auto p = VirtualAlloc(location, bytes, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
if (p == null)
{
int errCode = GetLastError();
writefln("Fail loc %s err '%s'", location, sysErrorString(errCode));
++failed;
}
else
{
++successful;
VirtualFree(p, 0, MEM_RELEASE);
writefln("Success loc %s ptr %s", location, p);
}
}
writefln("s %s", successful);
writefln("f %s", failed);
}
}
enum MemType
{
RW,
RWX
}
ubyte[] alloc_executable_memory(size_t bytes)
{
return allocate(bytes, cast(void*)0x4000_0000UL, MemType.RWX);
}
bool free_executable_memory(ubyte[] bytes)
{
return deallocate(bytes);
}
void printHex(ubyte[] buffer, size_t lineLength)
{
import std.stdio;
size_t index = 0;
if (lineLength) {
while (index + lineLength <= buffer.length) {
writefln("%(%02X %)", buffer[index..index+lineLength]);
index += lineLength;
}
}
if (index < buffer.length)
writefln("%(%02X %)", buffer[index..buffer.length]);
}
T divCeil(T)(T a, T b)
{
return a / b + (a % b > 0);
}
T nextPOT(T)(T x)
{
--x;
x |= x >> 1; // handle 2 bit numbers
x |= x >> 2; // handle 4 bit numbers
x |= x >> 4; // handle 8 bit numbers
static if (T.sizeof >= 2) x |= x >> 8; // handle 16 bit numbers
static if (T.sizeof >= 4) x |= x >> 16; // handle 32 bit numbers
static if (T.sizeof >= 8) x |= x >> 32; // handle 64 bit numbers
++x;
return x;
}
T alignValue(T)(T value, T alignment) pure
{
return cast(T)((value + (alignment-1)) & ~(alignment-1));
}
T paddingSize(T)(T address, T alignment)
{
return cast(T)(alignValue(address, alignment) - address);
}
public import core.time : MonoTime, Duration, usecs, dur;
MonoTime currTime() { return MonoTime.currTime(); }
struct ScaledNumberFmt(T)
{
T value;
void toString()(scope void delegate(const(char)[]) sink)
{
int scale = calcScale(value);
auto scaledValue = scaled(value, -scale);
int digits = numDigitsInNumber(scaledValue);
import std.format : formattedWrite;
sink.formattedWrite("%*.*f%s", digits, 3-digits, scaledValue, scaleSuffixes[scaleToScaleIndex(scale)]);
}
}
auto scaledNumberFmt(T)(T value)
{
return ScaledNumberFmt!T(value);
}
auto scaledNumberFmt(Duration value, double scale = 1)
{
double seconds = value.total!"hnsecs" / 10_000_000.0;
return ScaledNumberFmt!double(seconds * scale);
}
// -24 .. 24, with step of 3. Or -8 to 8 with step of 1
immutable string[] scaleSuffixes = ["y","z","a","f","p","n","u","m","","K","M","G","T","P","E","Z","Y"];
int numDigitsInNumber(Num)(const Num val)
{
import std.math: abs;
ulong absVal = cast(ulong)abs(val);
int numDigits = 1;
while (absVal >= 10)
{
absVal /= 10;
++numDigits;
}
return numDigits;
}
int calcScale(Num)(Num val)
{
import std.algorithm: clamp;
import std.math: abs, floor, ceil, log10;
static int signum(T)(const T x) nothrow
{
return (x > 0) - (x < 0);
}
auto lg = log10(abs(val));
int logSign = signum(lg);
double absLog = abs(lg);
int scale;
if (lg < 0)
scale = cast(int)(ceil(absLog/3.0))*3;
else
scale = cast(int)(floor(absLog/3.0))*3;
int clampedScale = clamp(scale * logSign, -24, 24);
return clampedScale;
}
int scaleToScaleIndex(int scale)
{
return scale / 3 + 8; // -24..24 -> -8..8 -> 0..16
}
double scaled(Num)(Num num, int scale)
{
import std.math: pow;
return num * pow(10.0, scale);
}
struct Buffer(T)
{
import std.experimental.allocator.gc_allocator;
alias allocator = GCAllocator.instance;
T* bufPtr;
uint capacity;
T[] buf() { return bufPtr[0..capacity]; }
// Must be kept private since it can be used to check for avaliable space
// when used as output range
uint length;
// postblit
this(this)
{
import core.memory;
void[] tmp = allocator.allocate(capacity*T.sizeof);
T* newBufPtr = cast(T*)tmp.ptr;
newBufPtr[0..length] = bufPtr[0..length];
bufPtr = newBufPtr;
GC.addRange(bufPtr, capacity * T.sizeof, typeid(T));
}
bool empty() { return length == 0; }
void put(T[] items ...)
{
reserve(items.length);
bufPtr[length..length+items.length] = items;
length += cast(uint)items.length;
}
void put(R)(R itemRange)
{
foreach(item; itemRange)
put(item);
}
void stealthPut(T item)
{
reserve(1);
bufPtr[length] = item;
}
/// Increases length and returns void-initialized slice to be filled by user
T[] voidPut(size_t howMany)
{
reserve(howMany);
length += howMany;
return buf[length-howMany..length];
}
ref T opIndex(size_t at)
{
return bufPtr[at];
}
ref T back() { return bufPtr[length-1]; }
inout(T[]) data() inout {
return bufPtr[0..length];
}
alias opSlice = data;
void clear() nothrow {
length = 0;
}
void reserve(size_t items)
{
if (capacity - length < items)
{
import core.memory;
GC.removeRange(bufPtr);
size_t newCapacity = nextPOT(capacity + items);
void[] tmp = buf;
allocator.reallocate(tmp, newCapacity*T.sizeof);
bufPtr = cast(T*)tmp.ptr;
capacity = cast(uint)(tmp.length / T.sizeof);
GC.addRange(bufPtr, capacity * T.sizeof, typeid(T));
}
}
void removeInPlace(size_t index)
{
if (index+1 != length)
{
bufPtr[index] = bufPtr[length-1];
}
--length;
}
void unput(size_t numItems)
{
length = cast(uint)(length - numItems);
}
}
struct IndentTextSink
{
import std.range : repeat;
TextSink sink;
int indentSize = 2;
private int indent;
void putIndent() { sink.putf("%s", ' '.repeat(indent)); }
void put(in char[] str) { putIndent; sink.put(str); }
void putf(Args...)(const(char)[] fmt, Args args) { putIndent; sink.putf(fmt, args); }
void putfln(Args...)(const(char)[] fmt, Args args) { putIndent; sink.putfln(fmt, args); }
void putln(const(char)[] str = null) { putIndent; sink.putln(str); }
void push() { indent += indentSize; }
void pop() { indent -= indentSize; }
}
struct TextSink
{
import std.format : formattedWrite;
import std.string : stripRight;
Buffer!char data;
void clear() { data.clear(); }
string text() { return stripRight(cast(string)data.data); }
void put(in char[] str)
{
if (str.length == 0) return;
data.put(str);
data.stealthPut('\0');
}
void putf(Args...)(const(char)[] fmt, Args args) { formattedWrite(&this, fmt, args); }
void putfln(Args...)(const(char)[] fmt, Args args) { formattedWrite(&this, fmt, args); put("\n"); }
void putln(const(char)[] str = null) { put(str); put("\n"); }
}
struct FixedBuffer(T)
{
T* bufPtr;
uint capacity;
void setBuffer(uint[] newBuffer) {
bufPtr = newBuffer.ptr;
assert(bufPtr);
assert(newBuffer.length <= uint.max, "capacity overflow");
capacity = cast(uint)newBuffer.length;
length = 0;
}
T[] buf() { return bufPtr[0..capacity]; }
uint length;
bool empty() { return length == 0; }
void put(T[] items ...)
{
reserve(items.length);
bufPtr[length..length+items.length] = items;
length += cast(uint)items.length;
}
void put(R)(R itemRange)
{
foreach(item; itemRange)
put(item);
}
void stealthPut(T item)
{
reserve(1);
bufPtr[length] = item;
}
/// Increases length and returns void-initialized slice to be filled by user
T[] voidPut(size_t howMany)
{
reserve(howMany);
length += howMany;
return buf[length-howMany..length];
}
ref T opIndex(size_t at)
{
return bufPtr[at];
}
ref T back() { return bufPtr[length-1]; }
inout(T[]) data() inout {
return bufPtr[0..length];
}
void clear() nothrow {
length = 0;
}
void reserve(size_t items)
{
if (capacity - length < items)
{
assert(false, format("out of memory: capacity %s, length %s, requested %s", capacity, length, items));
}
}
}
struct Win32Allocator
{
import core.sys.windows.windows;
enum PAGE_SIZE = 4096;
void* bufferPtr;
size_t reservedBytes;
size_t committedBytes;
size_t allocatedBytes;
bool reserve(size_t size)
{
reservedBytes = divCeil(size, PAGE_SIZE) * PAGE_SIZE; // round up to page size
bufferPtr = VirtualAlloc(null, reservedBytes, MEM_RESERVE, PAGE_NOACCESS);
version(print_allocator) writefln("reserve %s, ptr %X", size, bufferPtr);
return bufferPtr !is null;
}
void releaseMemory()
{
VirtualFree(bufferPtr, 0, MEM_RELEASE);
bufferPtr = null;
reservedBytes = 0;
committedBytes = 0;
allocatedBytes = 0;
}
void[] allocate(size_t numBytes)
{
version(print_allocator) writef("allocate %s, %s -> ", numBytes, this);
scope(exit) version(print_allocator) writeln(this);
if (numBytes == 0) return null;
size_t newAllocatedBytes = allocatedBytes + numBytes;
if (newAllocatedBytes > committedBytes) // commit more
{
size_t newCommittedBytes = alignValue(newAllocatedBytes, PAGE_SIZE);
size_t bytesToCommit = newCommittedBytes - committedBytes;
void* result = VirtualAlloc(bufferPtr + committedBytes, bytesToCommit, MEM_COMMIT, PAGE_READWRITE);
if (result is null) return null;
committedBytes = newCommittedBytes;
}
void* ptr = bufferPtr + allocatedBytes;
allocatedBytes = newAllocatedBytes;
return ptr[0..numBytes];
}
bool deallocate(void[] block)
{
version(print_allocator) writefln("deallocate %s", block.length);
if (block.ptr + block.length == bufferPtr + allocatedBytes)
{
// Shrink allocated part if block is at the end of allocated area
allocatedBytes -= block.length;
}
return true;
}
bool deallocateAll()
{
allocatedBytes = 0;
return true;
}
bool reallocate(ref void[] block, size_t newSize)
{
version(print_allocator) writefln("\nreallocate ptr %X size %s -> %s", block.ptr, block.length, newSize);
if (block.ptr + block.length == bufferPtr + allocatedBytes)
{
if (block.length >= newSize)
{
// Shrink if this is the last allocated block
allocatedBytes = allocatedBytes - (block.length - newSize);
block = block.ptr[0..newSize];
version(print_allocator) writeln(" shrink last block");
return true;
}
// Expand block that is the last allocated one
void[] extra = allocate(newSize - block.length);
if (extra.ptr !is null)
{
block = block.ptr[0..newSize];
version(print_allocator) writefln(" expand last block %X:%s", block.ptr, block.length);
return true;
}
return false;
}
if (block.length >= newSize)
{
// Dont reallocate if already satisfies
block = block.ptr[0..newSize];
version(print_allocator) writeln(" shrink block in place");
return true;
}
// attempt full reallocation / block is null
void[] newBlock = allocate(newSize);
version(print_allocator) writefln(" reallocate block %X:%s", newBlock.ptr, newBlock.length);
if (newBlock.ptr !is null)
{
newBlock[0..block.length] = block;
block = newBlock;
return true;
}
return false;
}
}
T[] removeInPlace(T)(T[] array, T what)
{
size_t i = 0;
size_t length = array.length;
while(i < length)
{
if (array[i] == what)
{
array[i] = array[length-1];
--length;
}
++i;
}
return assumeSafeAppend(array[0..length]);
}
unittest
{
assert(removeInPlace([], 1) == []);
assert(removeInPlace([1], 1) == []);
assert(removeInPlace([1], 2) == [1]);
assert(removeInPlace([1, 2], 2) == [1]);
assert(removeInPlace([2, 1], 2) == [1]);
}
// Grammar
/**
<module> = <declaration>* EOF
<declaration> = <func_decl> / <var_decl> / <struct_decl>
<func_decl> = <type> <identifier> "(" <param_list> ")" (<block_statement> / ';')
<param_list> = <parameter> "," <parameter_list> / <parameter>?
<parameter> = <type> <identifier>?
<var_decl> = <type> <identifier> ";"
<struct_decl> = "struct" <identifier> "{" <declaration>* "}"
<statement> = "if" <paren_expression> <statement> ("else" <statement>)?
"while" <paren_expression> <statement> /
"do" <statement> "while" <paren_expression> ";" /
"return" <expression>? ";" /
"continue" ";" /
"break" ";" /
<block_statement> /
<expression> ("=" <expression>)? ";" /
<declaration_statement>
<declaration_statement> = <declaration>
<block_statement> = "{" <statement>* "}"
<expression> = <test>
<test> = <sum> | <sum> ("=="|"!="|"<"|">"|"<="|">=") <sum>
<sum> = <term> / <sum> ("+"|"-") <term>
<term> = <identifier> "(" <expression_list> ")" / <identifier> "[" <expression> "]" / <identifier> / <int_literal> / <paren_expression>
<paren_expression> = "(" <expression> ")"
<expression_list> = (<expression> ",")*
<identifier> = [_a-zA-Z] [_a-zA-Z0-9]*
<type> = (<type_basic> / <type_user>) <type_specializer>*
<type_specializer> = '*' / '[' <expression> ']'
<type_basic> = ("i8" | "i16" | "i32" | "i64" | "isize" |
"u8" | "u16" | "u32" | "u64" | "usize" | "void" | "f32" | "f64")
<type_user> = <identifier>
<int_literal> = <literal_dec_int> / <literal_hex_int>
<literal_dec_int> = 0|[1-9][0-9_]*
<literal_hex_int> = ("0x"|"0X")[0-9A-Fa-f_]+
<literal_bin_int> = ("0b"|"0B")[01_]+
<literal_oct_int> = 0[01_]*
*/
struct ExternalSymbol
{
string name;
void* ptr;
}
enum IceBehavior : ubyte {
error,
breakpoint
}
struct CompilationContext
{
string input;
ubyte[] codeBuffer;
ExternalSymbol[Identifier] externalSymbols;
ModuleDeclNode* mod;
MachineInfo* machineInfo = &mach_info_x86_64;
ScopeStack scopeStack;
IdentifierMap idMap;
bool hasErrors;
TextSink sink;
IceBehavior iceBehavior = IceBehavior.error;
bool buildDebug = false;
//alias idString = idMap.get;
string idString(const Identifier id) { return idMap.get(id); }
static __gshared BasicTypeNode[] basicTypes = [
basicTypeNode(0, BasicType.t_error),
basicTypeNode(0, BasicType.t_void),
basicTypeNode(1, BasicType.t_bool , BasicTypeFlag.isBoolean),
basicTypeNode(1, BasicType.t_i8 , BasicTypeFlag.isInteger),
basicTypeNode(2, BasicType.t_i16 , BasicTypeFlag.isInteger),
basicTypeNode(4, BasicType.t_i32 , BasicTypeFlag.isInteger),
basicTypeNode(8, BasicType.t_i64 , BasicTypeFlag.isInteger),
//basicTypeNode(1, BasicType.t_isize, BasicTypeFlag.isInteger), // this is alias
basicTypeNode(1, BasicType.t_u8 , BasicTypeFlag.isInteger | BasicTypeFlag.isUnsigned),
basicTypeNode(2, BasicType.t_u16 , BasicTypeFlag.isInteger | BasicTypeFlag.isUnsigned),
basicTypeNode(4, BasicType.t_u32 , BasicTypeFlag.isInteger | BasicTypeFlag.isUnsigned),
basicTypeNode(8, BasicType.t_u64 , BasicTypeFlag.isInteger | BasicTypeFlag.isUnsigned),
//basicTypeNode(1, BasicType.t_usize, BasicTypeFlag.isInteger | BasicTypeFlag.isUnsigned), // this is alias
basicTypeNode(4, BasicType.t_f32 , BasicTypeFlag.isFloat),
basicTypeNode(8, BasicType.t_f64 , BasicTypeFlag.isFloat),
];
TypeNode* basicTypeNodes(BasicType basicType) { return cast(TypeNode*)&basicTypes[basicType]; }
void error(Args...)(SourceLocation loc, string format, Args args)
{
sink.putf("file(%s, %s): Error: ", loc.line+1, loc.col+1);
sink.putfln(format, args);
hasErrors = true;
}
void unrecoverable_error(Args...)(SourceLocation loc, string format, Args args)
{
sink.putf("file(%s, %s): Error: ", loc.line+1, loc.col+1);
sink.putfln(format, args);
hasErrors = true;
throw new CompilationException();
}
void assertf(Args...)(bool cond, string fmt, lazy Args args, string file = __MODULE__, int line = __LINE__)
{
if (cond) return;
sink.putf("%s(%s): ICE: Assertion failure: ", file, line);
sink.putfln(fmt, args);
hasErrors = true;
handleICE;
throw new CompilationException(true);
}
void assertf(Args...)(bool cond, SourceLocation loc, string fmt, lazy Args args, string file = __MODULE__, int line = __LINE__)
{
if (cond) return;
sink.putf("%s(%s): file(%s, %s): ICE: ", file, line, loc.line+1, loc.col+1);
sink.putfln(fmt, args);
hasErrors = true;
handleICE;
throw new CompilationException(true);
}
void unreachable(string file = __MODULE__, int line = __LINE__) {
internal_error_impl("Unreachable", file, line);
}
void internal_error(Args...)(SourceLocation loc, string format, Args args, string file = __MODULE__, int line = __LINE__)
{
sink.putf("source(%s, %s): ", loc.line+1, loc.col+1);
internal_error_impl(format, file, line, args);
}
void internal_error(Args...)(string format, Args args, string file = __MODULE__, int line = __LINE__)
{
internal_error_impl(format, file, line, args);
}
private void internal_error_impl(Args...)(string format, string file, int line, Args args)
{
sink.putf("ICE(%s:%s): ", file, line);
sink.putfln(format, args);
hasErrors = true;
handleICE;
throw new CompilationException(true);
}
private void handleICE() {
final switch(iceBehavior)
{
case IceBehavior.error: assert(false);
case IceBehavior.breakpoint:
writeln(sink.text);
stdout.flush;
version(DMD) asm { db 0xCC; } // breakpoint
version(LDC) assert(false); // LDC has no data in assembler
break;
}
}
void throwOnErrors() {
if (hasErrors) throw new CompilationException();
}
}
class CompilationException : Exception { this(bool isICE=false){ super(null); this.isICE = isICE; } bool isICE; }
// ####### ### # # ####### # #
// # # # # # # ## #
// # # # # # # # # #
// # # # ### ##### # # #
// # # # # # # # # #
// # # # # # # # ##
// # ### # # ####### # #
// -----------------------------------------------------------------------------
alias TT = TokenType;
enum TokenType : ubyte {
EOI,
AND, // &
AND_AND, // &&
AND_EQUAL, // &=
AT, // @
BACKSLASH, // \
COLON, // :
COMMA, // ,
DOLLAR, // $
DOT, // .
DOT_DOT, // ..
DOT_DOT_DOT, // ...
EQUAL, // =
EQUAL_EQUAL, // ==
GREATER, // >
GREATER_EQUAL, // >=
GREATER_GREATER, // >>
GREATER_GREATER_EQUAL, // >>=
GREATER_GREATER_GREATER, // >>>
GREATER_GREATER_GREATER_EQUAL, // >>>=
HASH, // #
LESS, // <
LESS_EQUAL, // <=
LESS_LESS, // <<
LESS_LESS_EQUAL, // <<=
MINUS, // -
MINUS_EQUAL, // -=
MINUS_MINUS, // --
NOT, // !
NOT_EQUAL, // !=
OR, // |
OR_EQUAL, // |=
OR_OR, // ||
PERCENT, // %
PERCENT_EQUAL, // %=
PLUS, // +
PLUS_EQUAL, // +=
PLUS_PLUS, // ++
QUESTION, // ?
SEMICOLON, // ;
SLASH, // /
SLASH_EQUAL, // /=
STAR, // *
STAR_EQUAL, // *=
TILDE, // ~
TILDE_EQUAL, // ~=
XOR, // ^
XOR_EQUAL, // ^=
LPAREN, // (
RPAREN, // )
LBRACKET, // [
RBRACKET, // ]
LCURLY, // {
RCURLY, // }
INVALID,
BREAK_SYM, // break
CONTINUE_SYM, // continue
DO_SYM, // do
ELSE_SYM, // else
IF_SYM, // if
RETURN_SYM, // return
STRUCT_SYM, // struct
WHILE_SYM, // while
IDENTIFIER, // [a-zA-Z_] [a-zA-Z_0-9]*
// ----------------------------------------
// list of basic types. The order is the same as in `enum BasicType`
TYPE_VOID, // void
TYPE_BOOL, // bool
TYPE_I8, // i8
TYPE_I16, // i16
TYPE_I32, // i32
TYPE_I64, // i64
TYPE_U8, // u8
TYPE_U16, // u16
TYPE_U32, // u32
TYPE_U64, // u64
TYPE_F32, // f32
TYPE_F64, // f64
// ----------------------------------------
TYPE_ISIZE, // isize
TYPE_USIZE, // usize
INT_LITERAL,
//DECIMAL_LITERAL, // 0|[1-9][0-9_]*
//BINARY_LITERAL, // ("0b"|"0B")[01_]+
//HEX_LITERAL, // ("0x"|"0X")[0-9A-Fa-f_]+
COMMENT, // // /*
}
enum TokenType TYPE_TOKEN_FIRST = TokenType.TYPE_VOID;
enum TokenType TYPE_TOKEN_LAST = TokenType.TYPE_F64;
struct Token {
TokenType type;
SourceLocation loc;
}
struct SourceLocation {
uint start;
uint line;
uint col;
uint size;
string getTokenString(string input) const { return input[start..start+size]; }
void toString(scope void delegate(const(char)[]) sink) const {
sink.formattedWrite("line %s col %s", line+1, col+1);
}
}
enum char EOI_CHAR = '\3';
// # ####### # #
// # # # #
// # # # #
// # ##### #
// # # # #
// # # # #
// ###### ####### # #
// -----------------------------------------------------------------------------
struct Lexer {
string input;
private dchar c; // current symbol
private uint position;
private uint line;
private uint column;
private uint startPos;
private uint startLine;
private uint startCol;
private long numberRep;
private void restartToken()
{
position = startPos;
line = startLine;
column = startCol;
if (position >= input.length) c = EOI_CHAR;
else c = input[position];
}
private void nextChar()
{
++position;
++column;
if (position >= input.length) c = EOI_CHAR;
else c = input[position];
}
private Token new_tok(TokenType type) pure
{
uint tokSize = position - startPos;
return Token(type, SourceLocation(startPos, startLine, startCol, tokSize));
}
string getTokenString(Token tok) pure { return input[tok.loc.start..tok.loc.start+tok.loc.size]; }
string getTokenString(SourceLocation loc) pure { return input[loc.start..loc.start+loc.size]; }
long getTokenNumber() { return numberRep; }
int opApply(scope int delegate(Token) dg)
{
Token tok;
while ((tok = nextToken()).type != TokenType.EOI)
if (int res = dg(tok))
return res;
return 0;
}
Token nextToken()
{
if (position >= input.length) c = EOI_CHAR;
else c = input[position];
while (true)
{
startPos = position;
startLine = line;
startCol = column;
switch(c)
{
case EOI_CHAR: return new_tok(TT.EOI);
case '\t': nextChar; continue;
case '\n': lex_EOLN(); continue;
case '\r': lex_EOLR(); continue;
case ' ' : nextChar; continue;
case '!' : nextChar; return lex_multi_equal2(TT.NOT, TT.NOT_EQUAL);
case '#' : nextChar; return new_tok(TT.HASH);
case '$' : nextChar; return new_tok(TT.DOLLAR);
case '%' : nextChar; return lex_multi_equal2(TT.PERCENT, TT.PERCENT_EQUAL);
case '&' : nextChar; return lex_multi_equal2_3('&', TT.AND, TT.AND_EQUAL, TT.AND_AND);
case '(' : nextChar; return new_tok(TT.LPAREN);
case ')' : nextChar; return new_tok(TT.RPAREN);
case '*' : nextChar; return lex_multi_equal2(TT.STAR, TT.STAR_EQUAL);
case '+' : nextChar; return lex_multi_equal2_3('+', TT.PLUS, TT.PLUS_EQUAL, TT.PLUS_PLUS);
case ',' : nextChar; return new_tok(TT.COMMA);
case '-' : nextChar; return lex_multi_equal2_3('-', TT.MINUS, TT.MINUS_EQUAL, TT.MINUS_MINUS);
case '.' : nextChar;
if (c == '.') { nextChar;
if (c == '.') { nextChar;
return new_tok(TT.DOT_DOT_DOT);
}
return new_tok(TT.DOT_DOT);
}
return new_tok(TT.DOT);
case '/' : return lex_SLASH();
case '0' : return lex_ZERO();
case '1' : ..case '9': return lex_DIGIT();
case ':' : nextChar; return new_tok(TT.COLON);
case ';' : nextChar; return new_tok(TT.SEMICOLON);
case '<' : nextChar;
if (c == '<') { nextChar;
if (c == '=') { nextChar;
return new_tok(TT.LESS_LESS_EQUAL);
}
return new_tok(TT.LESS_LESS);
}
if (c == '=') { nextChar;
return new_tok(TT.LESS_EQUAL);
}
return new_tok(TT.LESS);
case '=' : nextChar; return lex_multi_equal2(TT.EQUAL, TT.EQUAL_EQUAL);
case '>' : nextChar;
if (c == '=') { nextChar;
return new_tok(TT.GREATER_EQUAL);
}
if (c == '>') { nextChar;
if (c == '>') { nextChar;
if (c == '=') { nextChar;
return new_tok(TT.GREATER_GREATER_GREATER_EQUAL);
}
return new_tok(TT.GREATER_GREATER_GREATER);
}
if (c == '=') { nextChar;
return new_tok(TT.GREATER_GREATER_EQUAL);
}
return new_tok(TT.GREATER_GREATER);
}
return new_tok(TT.GREATER);
case '?' : nextChar; return new_tok(TT.QUESTION);
case '@' : nextChar; return new_tok(TT.AT);
case 'A' : ..case 'Z': return lex_LETTER();
case '[' : nextChar; return new_tok(TT.LBRACKET);
case '\\': nextChar; return new_tok(TT.BACKSLASH);
case ']' : nextChar; return new_tok(TT.RBRACKET);
case '^' : nextChar; return lex_multi_equal2(TT.XOR, TT.XOR_EQUAL);
case '_' : nextChar; return lex_LETTER();
case 'a' : ..case 'z': return lex_LETTER();
case '{' : nextChar; return new_tok(TT.LCURLY);
case '|' : nextChar; return lex_multi_equal2_3('|', TT.OR, TT.OR_EQUAL, TT.OR_OR);
case '}' : nextChar; return new_tok(TT.RCURLY);
case '~' : nextChar; return lex_multi_equal2(TT.TILDE, TT.TILDE_EQUAL);
default : nextChar; return new_tok(TT.INVALID);
}
}
}
private void lex_EOLR() // \r[\n]
{
nextChar;
if (c == '\n') nextChar;
++line;
column = 0;
}
private void lex_EOLN() // \n
{
nextChar;
++line;
column = 0;
}
// Lex X= tokens
private Token lex_multi_equal2(TokenType single_tok, TokenType eq_tok)
{
if (c == '=') {
nextChar;
return new_tok(eq_tok);
}
return new_tok(single_tok);
}
private Token lex_multi_equal2_3(dchar chr, TokenType single_tok, TokenType eq_tok, TokenType double_tok)
{
if (c == chr) { nextChar;
return new_tok(double_tok);
}
if (c == '=') { nextChar;
return new_tok(eq_tok);
}
return new_tok(single_tok);
}
private Token lex_SLASH() // /
{
nextChar;
if (c == '/')
{
consumeLine();
return new_tok(TT.COMMENT);
}
if (c == '*')
{
while (true)
{
switch(c)
{
case EOI_CHAR: return new_tok(TT.INVALID);
case '\n': lex_EOLN(); continue;
case '\r': lex_EOLR(); continue;
case '*':
nextChar;
if (c == '/') {
nextChar;
return new_tok(TT.COMMENT);
}
break;
default: break;
}
nextChar;
}
return new_tok(TT.COMMENT);
}
if (c == '=') { nextChar;
return new_tok(TT.SLASH_EQUAL);
}
return new_tok(TT.SLASH);
}
private Token lex_ZERO() // 0
{
numberRep = 0;
nextChar;
if (c == 'x' || c == 'X')
{
nextChar;
consumeHexadecimal();
return new_tok(TT.INT_LITERAL);
}
else if (c == 'b' || c == 'B')
{
nextChar;
consumeBinary();
return new_tok(TT.INT_LITERAL);
}
else
{
consumeDecimal();
return new_tok(TT.INT_LITERAL);
}
}
private Token lex_DIGIT() // 1-9
{
numberRep = c - '0';
nextChar;
consumeDecimal();
return new_tok(TT.INT_LITERAL);
}
private Token lex_LETTER() // a-zA-Z_
{
switch (c)
{
case 'b':
nextChar;
if (c == 'o' && match("ool")) return new_tok(TT.TYPE_BOOL);
else if (c == 'r' && match("reak")) return new_tok(TT.BREAK_SYM);
break;
case 'c': if (match("continue")) return new_tok(TT.CONTINUE_SYM); break;
case 'd': if (match("do")) return new_tok(TT.DO_SYM); break;
case 'e': if (match("else")) return new_tok(TT.ELSE_SYM); break;
case 'f':
nextChar;
if (c == '3' && match("32")) return new_tok(TT.TYPE_F32);
if (c == '6' && match("64")) return new_tok(TT.TYPE_F64);
break;
case 'i':
nextChar;
switch(c) {
case '1': if (match("16")) return new_tok(TT.TYPE_I16); break;
case '3': if (match("32")) return new_tok(TT.TYPE_I32); break;
case '6': if (match("64")) return new_tok(TT.TYPE_I64); break;
case '8': if (match("8")) return new_tok(TT.TYPE_I8); break;
case 's': if (match("size")) return new_tok(TT.TYPE_ISIZE); break;
case 'f': if (match("f")) return new_tok(TT.IF_SYM); break;
default: break;
}
break;
case 'r': if (match("return")) return new_tok(TT.RETURN_SYM); break;
case 's': if (match("struct")) return new_tok(TT.STRUCT_SYM); break;
case 'u':
nextChar;
switch(c) {
case '1': if (match("16")) return new_tok(TT.TYPE_U16); break;
case '3': if (match("32")) return new_tok(TT.TYPE_U32); break;
case '6': if (match("64")) return new_tok(TT.TYPE_U64); break;
case '8': if (match("8")) return new_tok(TT.TYPE_U8); break;
case 's': if (match("size")) return new_tok(TT.TYPE_USIZE); break;
default: break;
}
break;
case 'v': if (match("void")) return new_tok(TT.TYPE_VOID); break;
case 'w': if (match("while")) return new_tok(TT.WHILE_SYM); break;
default: break;
}
consumeId();
return new_tok(TT.IDENTIFIER);
}
private bool match(string identifier)
{
uint index = 0;
while (identifier[index] == c)
{
nextChar;
++index;
if (index == identifier.length)
{
// check that no valid symbol follow this id. ifff for if id.
if (isIdSecond(c)) return false;
return true;
}
}
return false;
}
private void consumeId()
{
while (isIdSecond(c)) nextChar;
}
private void consumeDecimal()
{
while (true)
{
if ('0' <= c && c <= '9') {
numberRep = numberRep * 10 + c - '0';
} else if (c != '_') return;
nextChar;
}
}
private void consumeHexadecimal()
{
while (true)
{
if ('0' <= c && c <= '9') {
numberRep = numberRep * 16 + c - '0';
} else if ('a' <= c && c <= 'f') {
numberRep = numberRep * 16 + c - 'a' + 10;
} else if ('A' <= c && c <= 'F') {
numberRep = numberRep * 16 + c - 'A' + 10;
} else if (c != '_') return;
nextChar;
}
}
private void consumeBinary()
{
while (true)
{
if (c == '0' || c == '1') {
numberRep = numberRep * 2 + c - '0';
} else if (c != '_') return;
nextChar;
}
}
private void consumeLine()
{
while (true)
{
switch(c)
{
case EOI_CHAR: return;
case '\n': lex_EOLN(); return;
case '\r': lex_EOLR(); return;
default: break;
}
nextChar;
}
}
}
private bool isIdSecond(dchar chr) pure nothrow {
return
'0' <= chr && chr <= '9' ||
'a' <= chr && chr <= 'z' ||
'A' <= chr && chr <= 'Z' ||
chr == '_';
}
unittest {
{
string[] keywords = ["bool","break","continue","do","else","f32","f64",
"i16","i32","i64","i8","if","isize","return","struct","u16","u32","u64",
"u8","usize","void","while"];
TokenType[] tokens = [TT.TYPE_BOOL,TT.BREAK_SYM,TT.CONTINUE_SYM,TT.DO_SYM,
TT.ELSE_SYM,TT.TYPE_F32,TT.TYPE_F64,TT.TYPE_I16,TT.TYPE_I32,TT.TYPE_I64,
TT.TYPE_I8,TT.IF_SYM,TT.TYPE_ISIZE,TT.RETURN_SYM,TT.STRUCT_SYM,
TT.TYPE_U16,TT.TYPE_U32,TT.TYPE_U64,TT.TYPE_U8,TT.TYPE_USIZE,
TT.TYPE_VOID,TT.WHILE_SYM];
Lexer lexer;
foreach(i, keyword; keywords)
{
lexer = Lexer(keyword);
Token token = lexer.nextToken;
assert(token.type == tokens[i],
format("For %s expected %s got %s", keyword, tokens[i], token.type));
lexer = Lexer(keyword~"A");
assert(lexer.nextToken.type == TT.IDENTIFIER);
}
}
{
string[] ops = ["&","&&","&=","@","\\",":",",","$",".","..","...",
"=","==",">",">=",">>",">>=",">>>",">>>=","#","<","<=","<<","<<=","-",
"-=","--","!","!=","|","|=","||","%","%=","+","+=","++","?",";","/",
"/=","*","*=","~","~=","^","^=","(",")","[","]","{","}",];
TokenType[] tokens_ops = [TT.AND,TT.AND_AND,TT.AND_EQUAL,TT.AT,TT.BACKSLASH,
TT.COLON,TT.COMMA,TT.DOLLAR,TT.DOT,TT.DOT_DOT,TT.DOT_DOT_DOT,TT.EQUAL,
TT.EQUAL_EQUAL,TT.GREATER,TT.GREATER_EQUAL,TT.GREATER_GREATER,
TT.GREATER_GREATER_EQUAL,TT.GREATER_GREATER_GREATER,
TT.GREATER_GREATER_GREATER_EQUAL,TT.HASH,
TT.LESS,TT.LESS_EQUAL,TT.LESS_LESS,TT.LESS_LESS_EQUAL,TT.MINUS,
TT.MINUS_EQUAL,TT.MINUS_MINUS,TT.NOT,TT.NOT_EQUAL,TT.OR,TT.OR_EQUAL,
TT.OR_OR,TT.PERCENT,TT.PERCENT_EQUAL,TT.PLUS,TT.PLUS_EQUAL,TT.PLUS_PLUS,
TT.QUESTION,TT.SEMICOLON,TT.SLASH,TT.SLASH_EQUAL,TT.STAR,TT.STAR_EQUAL,
TT.TILDE,TT.TILDE_EQUAL,TT.XOR,TT.XOR_EQUAL,TT.LPAREN,TT.RPAREN,
TT.LBRACKET,TT.RBRACKET, TT.LCURLY,TT.RCURLY,];
Lexer lexer;
foreach(i, op; ops)
{
lexer = Lexer(op);
Token token = lexer.nextToken;
assert(token.type == tokens_ops[i],
format("For %s expected %s got %s", op, tokens_ops[i], token.type));
}
}
void testNumeric(string input, TokenType tokType, long expectedValue)
{
Lexer lexer = Lexer(input);
assert(lexer.nextToken.type == tokType);
assert(lexer.numberRep == expectedValue);
}
assert(Lexer("_10").nextToken.type == TT.IDENTIFIER);
testNumeric("10", TT.INT_LITERAL, 10);
testNumeric("1_0", TT.INT_LITERAL, 1_0);
testNumeric("10_", TT.INT_LITERAL, 10_);
testNumeric("0xFF", TT.INT_LITERAL, 0xFF);
testNumeric("0XABCDEF0123456789", TT.INT_LITERAL, 0XABCDEF0123456789);
testNumeric("0x1_0", TT.INT_LITERAL, 0x1_0);
testNumeric("0b10", TT.INT_LITERAL, 0b10);
testNumeric("0B10", TT.INT_LITERAL, 0B10);
testNumeric("0b1_0", TT.INT_LITERAL, 0b1_0);
{
string source = "/*\n*/test";
Lexer lexer = Lexer(source);
Token tok = lexer.nextToken;
assert(tok.type == TT.COMMENT);
assert(tok.loc.getTokenString(source) == "/*\n*/");
tok = lexer.nextToken;
assert(tok.type == TT.IDENTIFIER);
assert(tok.loc.getTokenString(source) == "test");
}
{
string source = "//test\nhello";
Lexer lexer = Lexer(source);
Token tok = lexer.nextToken;
assert(tok.type == TT.COMMENT);
assert(tok.loc.getTokenString(source) == "//test\n");
tok = lexer.nextToken;
assert(tok.type == TT.IDENTIFIER);
assert(tok.loc.getTokenString(source) == "hello");
}
}
alias Identifier = uint;
struct IdentifierMap {
string[] strings;
uint[string] map;
Buffer!char tempBuf;
string get(Identifier id) {
return strings[id];
}
Identifier find(string str) {
return map.get(str, uint.max);
}
Identifier getOrRegWithSuffix(string str, size_t suffix) {
import std.format : formattedWrite;
tempBuf.clear;
tempBuf.put(str);
formattedWrite(tempBuf, "%s%s", str, suffix);
const(char)[] idString = tempBuf.data;
return getOrReg(idString);
}
Identifier getOrReg(const(char)[] str) {
uint id = map.get(cast(string)str, uint.max);
if (id == uint.max) {
string duppedKey = str.idup;
id = cast(uint)strings.length;
map[duppedKey] = id;
strings ~= duppedKey;
}
return id;
}
Identifier getOrRegNoDup(string str) {
uint id = map.get(str, uint.max);
if (id == uint.max) {
id = cast(uint)strings.length;
map[str] = id;
strings ~= str;
}
return id;
}
}
// The order is the same as in TokenType enum
enum BasicType : ubyte {
t_error,
t_void,
t_bool,
t_i8,
t_i16,
t_i32,
t_i64,
//t_isize,
t_u8,
t_u16,
t_u32,
t_u64,
//t_usize,
t_f32,
t_f64,
}
bool isTypeImplemented(BasicType t) {
final switch(t) {
case BasicType.t_error: return false;
case BasicType.t_void: return false;
case BasicType.t_bool: return false;
case BasicType.t_i8: return false;
case BasicType.t_i16: return false;
case BasicType.t_i32: return false;
case BasicType.t_i64: return false;
case BasicType.t_u8: return false;
case BasicType.t_u16: return false;
case BasicType.t_u32: return false;
case BasicType.t_u64: return false;
case BasicType.t_f32: return false;
case BasicType.t_f64: return false;
}
}
// usage isAutoConvertibleFromToBasic[from][to]
immutable bool[13][13] isAutoConvertibleFromToBasic = [
//err void bool i8 i16 i32 i64 u8 u16 u32 u64 f32 f64 // to
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // from error
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // from void
[ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], // from bool
[ 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1], // from i8
[ 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1], // from i16
[ 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1], // from i32
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1], // from i64
[ 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1], // from u8
[ 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1], // from u16
[ 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1], // from u32
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1], // from u64
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], // from f32
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], // from f64
];
immutable BasicType[13][13] commonBasicType = (){ with(BasicType){ return [
// error void bool i8 i16 i32 i64 u8 u16 u32 u64 f32 f64
[t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error], // error
[t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error], // void
[t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error, t_error], // bool
[t_error, t_error, t_error, t_i8, t_i16, t_i32, t_i64, t_i8, t_i16, t_i32, t_i64, t_f32, t_f64 ], // i8
[t_error, t_error, t_error, t_i16, t_i16, t_i32, t_i64, t_i16, t_i16, t_i32, t_i64, t_f32, t_f64 ], // i16
[t_error, t_error, t_error, t_i32, t_i32, t_i32, t_i64, t_i32, t_i32, t_i32, t_i64, t_f32, t_f64 ], // i32
[t_error, t_error, t_error, t_i64, t_i64, t_i64, t_i64, t_i64, t_i64, t_i64, t_i64, t_f32, t_f64 ], // i64
[t_error, t_error, t_error, t_i8, t_i16, t_i32, t_i64, t_u8, t_u16, t_u32, t_u64, t_f32, t_f64 ], // u8
[t_error, t_error, t_error, t_i16, t_i16, t_i32, t_i64, t_u16, t_u16, t_u32, t_u64, t_f32, t_f64 ], // u16
[t_error, t_error, t_error, t_i32, t_i32, t_i32, t_i64, t_u32, t_u32, t_u32, t_u64, t_f32, t_f64 ], // u32
[t_error, t_error, t_error, t_i64, t_i64, t_i64, t_i64, t_u64, t_u64, t_u64, t_u64, t_f32, t_f64 ], // u64
[t_error, t_error, t_error, t_f32, t_f32, t_f32, t_f32, t_f32, t_f32, t_f32, t_f32, t_f32, t_f64 ], // f32
[t_error, t_error, t_error, t_f64, t_f64, t_f64, t_f64, t_f64, t_f64, t_f64, t_f64, t_f64, t_f64 ], // f64
]; }
}();
string[13] basicTypeNames = ["error", "void", "bool", "i8", "i16", "i32",
"i64", "u8", "u16", "u32", "u64", "f32", "f64"];
bool isBasicTypeToken(TokenType tt) {
return tt >= TYPE_TOKEN_FIRST && tt <= TYPE_TOKEN_LAST;
}
BasicType tokenTypeToBasicType(TokenType tt) {
return cast(BasicType)(tt - TYPE_TOKEN_FIRST + BasicType.t_void);
}
// # ##### #######
// # # # #
// ### # #
// # # ##### #
// ##### # #
// # # # # #
// ## ## ##### #
// -----------------------------------------------------------------------------
enum AstType : ubyte {
error,
abstract_node,
decl_module,
decl_function,
decl_var,
decl_struct,
stmt_block,
stmt_if,
stmt_while,
stmt_do_while,
stmt_return,
stmt_break,
stmt_continue,
stmt_assign,
expr_var,
expr_literal,
expr_bin_op,
expr_call,
expr_index,
expr_type_conv,
type_basic,
type_ptr,
type_static_array,
type_user,
}
enum AstFlags {
isDeclaration = 1 << 0,
isScope = 1 << 1,
isExpression = 1 << 2,
isStatement = 1 << 3,
isType = 1 << 4,
isSymResolved = 1 << 5,
}
mixin template AstNodeData(AstType _astType = AstType.abstract_node, int default_flags = 0) {
this(Args...)(SourceLocation loc, Args args) {
this(loc);
enum len = this.tupleof.length - 3;
enum numDefault = len - args.length;
static assert(args.length <= len, "Too many args");
this.tupleof[3..$-numDefault] = args;
}
this(SourceLocation loc) {
this.loc = loc; this.astType = _astType; this.flags = cast(ushort)default_flags; }
/*this(SourceLocation loc, int flags) {
this.loc = loc; this.astType = _astType; this.flags = cast(ushort)(default_flags|flags); }
this(SourceLocation loc, AstType astType) {
this.loc = loc; this.astType = astType; this.flags = cast(ushort)default_flags; }
this(SourceLocation loc, AstType astType, int flags) {
this.loc = loc; this.astType = astType; this.flags = cast(ushort)(default_flags|flags); }*/
SourceLocation loc;
AstType astType = _astType;
ushort flags;
bool isDeclaration() { return cast(bool)(flags & AstFlags.isDeclaration); }
bool isScope() { return cast(bool)(flags & AstFlags.isScope); }
bool isExpression() { return cast(bool)(flags & AstFlags.isExpression); }
bool isStatement() { return cast(bool)(flags & AstFlags.isStatement); }
bool isType() { return cast(bool)(flags & AstFlags.isType); }
bool isSymResolved() { return cast(bool)(flags & AstFlags.isSymResolved); }
}
mixin template SymRefNodeData() {
SymbolRef symRef;
string strId(CompilationContext* context) { return context.idString(symRef.id(isSymResolved)); }
Identifier id() { return symRef.id(isSymResolved); }
void resolveSymbol(Symbol* symbol) {
symRef._symbol = symbol;
flags |= AstFlags.isSymResolved;
}
Symbol* getSym() { assert(isSymResolved, "Unresolved symbol"); return symRef._symbol; }
}
struct AstNode {
mixin AstNodeData;
}
// ----------------------------------- Types -----------------------------------
// -----------------------------------------------------------------------------
mixin template TypeNodeData(AstType _astType) {
mixin AstNodeData!(_astType, AstFlags.isType);
}
struct TypePrinter
{
TypeNode* node;
CompilationContext* ctx;
void toString(scope void delegate(const(char)[]) sink) {
node.toString(sink, ctx);
}
}
struct TypeNode {
mixin AstNodeData!(AstType.abstract_node, AstFlags.isType);
BasicTypeNode* basicTypeNode() { return cast(BasicTypeNode*)&this; }
PtrTypeNode* ptrTypeNode() { return cast(PtrTypeNode*)&this; }
StaticArrayTypeNode* staticArrayTypeNode() { return cast(StaticArrayTypeNode*)&this; }
UserTypeNode* userTypeNode() { return cast(UserTypeNode*)&this; }
ulong alignment()
{
switch(astType)
{
case AstType.type_basic: return basicTypeNode.alignment;
case AstType.type_ptr: return ptrTypeNode.alignment;
case AstType.type_static_array: return staticArrayTypeNode.alignment;
case AstType.type_user: return userTypeNode.alignment;
default: assert(false, format("got %s", astType));
}
}
ulong size()
{
switch(astType)
{
case AstType.type_basic: return basicTypeNode.size;
case AstType.type_ptr: return ptrTypeNode.size;
case AstType.type_static_array: return staticArrayTypeNode.size;
case AstType.type_user: return userTypeNode.size;
default: assert(false, format("got %s", astType));
}
}
string typeName(CompilationContext* context) {
if (&this == null) return null;
assert(isType);
switch(astType)
{
case AstType.type_basic:
return basicTypeNode.strId;
case AstType.type_ptr:
return "ptr";
case AstType.type_static_array: return "[num]";
case AstType.type_user:
return userTypeNode.strId(context);
default: assert(false, format("got %s", astType));
}
}
TypePrinter printer(CompilationContext* context) {
return TypePrinter(&this, context);
}
bool sameType(TypeNode* t2) {
assert(isType, format("this is %s, not type", astType));
assert(t2.isType, format("t2 is %s, not type", t2.astType));
if (astType != t2.astType) return false;
switch(astType)
{
case AstType.type_basic:
return basicTypeNode.basicType == t2.basicTypeNode.basicType;
case AstType.type_ptr:
return ptrTypeNode.base == t2.ptrTypeNode.base;
case AstType.type_static_array:
return staticArrayTypeNode.base == t2.staticArrayTypeNode.base &&
staticArrayTypeNode.length == t2.staticArrayTypeNode.length;
case AstType.type_user:
return cast(void*)(&this) == cast(void*)(t2);
default:
assert(false, format("got %s %s", astType, t2.astType));
}
}
bool isVoid() {
return astType == AstType.type_basic &&
basicTypeNode.basicType == BasicType.t_void;
}
bool isError() {
return astType == AstType.type_basic &&
basicTypeNode.basicType == BasicType.t_error;
}
void assertImplemented(SourceLocation loc, CompilationContext* context) {
if (!isImplemented)
context.error(loc, "Type is not implemented `%s`",
typeName(context));
}
bool isImplemented() {
switch (astType)
{
case AstType.type_basic:
switch (basicTypeNode.basicType)
{
case BasicType.t_bool: return true;
case BasicType.t_i32: return true;
case BasicType.t_i64: return true;
default: return false;
}
case AstType.type_ptr:
return ptrTypeNode.base.isImplemented;
default: return false;
}
}
TypeNode* getElementType(CompilationContext* context) {
switch(astType)
{
case AstType.type_ptr: return ptrTypeNode.base;
case AstType.type_static_array: return staticArrayTypeNode.base;
default: context.internal_error(loc, "%s is not indexable", astType); assert(false);
}
}
IrValueType irType(CompilationContext* context) {
switch (astType)
{
case AstType.type_basic:
switch(basicTypeNode.basicType)
{
case BasicType.t_void: return IrValueType.i32;
case BasicType.t_bool: return IrValueType.i32;
case BasicType.t_i32: return IrValueType.i32;
case BasicType.t_i64: return IrValueType.i64;
default: break;
}
break;
case AstType.type_ptr: return IrValueType.ptr;
default: break;
}
context.internal_error(loc, "Cannot convert `%s` to IrValueType", astType);
assert(false);
}
void toString(scope void delegate(const(char)[]) sink, CompilationContext* ctx) {
switch(astType)
{
case AstType.type_basic:
sink(basicTypeNames[basicTypeNode.basicType]);
break;
case AstType.type_ptr:
ptrTypeNode.base.toString(sink, ctx);
sink("*");
break;
case AstType.type_static_array:
staticArrayTypeNode.base.toString(sink, ctx);
formattedWrite(sink, "[%s]", staticArrayTypeNode.length);
break;
case AstType.type_user:
sink(userTypeNode.strId(ctx));
sink("*");
break;
default: assert(false, format("%s is not type", astType));
}
}
}
enum BasicTypeFlag : ubyte {
isFloat = 1 << 0,
isInteger = 1 << 1,
isUnsigned = 1 << 2,
isBoolean = 1 << 3,
}
enum POINTER_SIZE = 8;
BasicTypeNode basicTypeNode(ulong size, BasicType basicType, int typeFlags = 0)
{
return BasicTypeNode(SourceLocation(), size, basicType, cast(ubyte)typeFlags);
}
struct BasicTypeNode {
mixin TypeNodeData!(AstType.type_basic);
ulong size; // -1 arch dependent
ulong alignment() { return size; }
BasicType basicType;
ubyte typeFlags;
TypeNode* typeNode() { return cast(TypeNode*)&this; }
string strId() { return basicTypeNames[basicType]; }
bool isFloat() { return cast(bool)(typeFlags & BasicTypeFlag.isFloat); }
bool isInteger() { return cast(bool)(typeFlags & BasicTypeFlag.isInteger); }
bool isUnsigned() { return cast(bool)(typeFlags & BasicTypeFlag.isUnsigned); }
bool isBoolean() { return cast(bool)(typeFlags & BasicTypeFlag.isBoolean); }
}
struct PtrTypeNode {
mixin TypeNodeData!(AstType.type_ptr);
TypeNode* typeNode() { return cast(TypeNode*)&this; }
TypeNode* base;
ulong size() { return POINTER_SIZE; }
ulong alignment() { return POINTER_SIZE; }
}
struct StaticArrayTypeNode {
mixin TypeNodeData!(AstType.type_static_array);
TypeNode* typeNode() { return cast(TypeNode*)&this; }
TypeNode* base;
ulong length;
ulong size() { return base.size * length; }
ulong alignment() { return base.alignment; }
}
struct UserTypeNode {
mixin TypeNodeData!(AstType.type_user);
mixin SymRefNodeData;
TypeNode* typeNode() { return cast(TypeNode*)&this; }
ulong size = 1; // TODO, set in semantic
ulong alignment = 1; // TODO, set as max alignment of members
}
// ------------------------------- Declarations --------------------------------
// -----------------------------------------------------------------------------
mixin template ScopeDeclNodeData(AstType _astType, int default_flags = 0) {
mixin AstNodeData!(_astType, default_flags | AstFlags.isScope | AstFlags.isDeclaration);
/// Each node can be struct, function or variable
AstNode*[] declarations;
}
struct ModuleDeclNode {
mixin ScopeDeclNodeData!(AstType.decl_module);
Scope* _scope;
/// Linear list of all functions of a module (including nested and methods)
FunctionDeclNode*[] functions;
IrModule irModule;
void* newIrModule; // new_ir.IrModule
void addFunction(FunctionDeclNode* func) {
functions ~= func;
}
FunctionDeclNode* findFunction(string idStr, CompilationContext* ctx) {
Identifier id = ctx.idMap.find(idStr);
if (id == uint.max) return null;
return findFunction(id);
}
FunctionDeclNode* findFunction(Identifier id) {
Symbol* sym = _scope.symbols.get(id, null);
if (sym.symClass != SymbolClass.c_function) return null;
return sym.funcDecl;
}
}
struct StructDeclNode {
mixin ScopeDeclNodeData!(AstType.decl_struct);
mixin SymRefNodeData;
Scope* _scope;
}
struct FunctionDeclNode {
mixin AstNodeData!(AstType.decl_function, AstFlags.isDeclaration);
mixin SymRefNodeData;
TypeNode* returnType;
VariableDeclNode*[] parameters;
BlockStmtNode* block_stmt; // null if external
Scope* _scope;
IrFunction* irData;
void* newIrData; // new_ir.IrFunction
/// Position in buffer or in memory
void* funcPtr;
}
enum VariableFlags : ubyte {
isParameter = 1 << 1,
forceMemoryStorage = 1 << 0,
}
struct VariableDeclNode {
mixin AstNodeData!(AstType.decl_var, AstFlags.isDeclaration | AstFlags.isStatement);
mixin SymRefNodeData;
TypeNode* type;
ubyte varFlags;
ushort paramIndex; // 0 for non-params
IrIndex irRef;
IrVar irVar; // unique id of variable within a function
IrIndex stackSlotId;
bool isParameter() { return cast(bool)(varFlags & VariableFlags.isParameter); }
bool forceMemoryStorage() { return cast(bool)(varFlags & VariableFlags.forceMemoryStorage); }
}
// -------------------------------- Statements ---------------------------------
// -----------------------------------------------------------------------------
struct IfStmtNode {
mixin AstNodeData!(AstType.stmt_if, AstFlags.isStatement);
ExpressionNode* condition;
AstNode* thenStatement;
AstNode* elseStatement; // Nullable
Scope* then_scope;
Scope* else_scope;
}
struct WhileStmtNode {
mixin AstNodeData!(AstType.stmt_while, AstFlags.isStatement);
ExpressionNode* condition;
AstNode* statement;
Scope* _scope;
}
struct DoWhileStmtNode {
mixin AstNodeData!(AstType.stmt_do_while, AstFlags.isStatement);
ExpressionNode* condition;
AstNode* statement;
Scope* _scope;
}
struct ReturnStmtNode {
mixin AstNodeData!(AstType.stmt_return, AstFlags.isStatement);
ExpressionNode* expression; // Nullable
}
struct BreakStmtNode {
mixin AstNodeData!(AstType.stmt_break, AstFlags.isStatement);
}
struct ContinueStmtNode {
mixin AstNodeData!(AstType.stmt_continue, AstFlags.isStatement);
}
struct BlockStmtNode {
mixin AstNodeData!(AstType.stmt_block, AstFlags.isStatement);
/// Each node can be expression, declaration or expression
AstNode*[] statements;
Scope* _scope;
}
enum AssignOp : ubyte {
opAssign,
opIndexAssign
}
struct AssignStmtNode {
mixin AstNodeData!(AstType.stmt_assign, AstFlags.isStatement);
AssignOp op;
ExpressionNode* left;
ExpressionNode* right;
}
// ------------------------------- Expressions ---------------------------------
// -----------------------------------------------------------------------------
mixin template ExpressionNodeData(AstType _astType) {
mixin AstNodeData!(_astType, AstFlags.isExpression);
TypeNode* type;
IrIndex irRef;
}
enum SymbolFlags : ubyte {
isInOrderedScope = 1 << 0,
}
struct SymbolRef
{
this(Identifier identifier)
{
this._id = identifier;
}
union
{
Symbol* _symbol; // used when resolved, Symbol contains Identifier internally
Identifier _id; // used when not yet resolved
}
/// Resolved is stored in isSymResolved flag of AstNode
Identifier id(bool resolved) { return resolved ? _symbol.id : _id; }
}
struct Symbol {
Identifier id;
SourceLocation loc;
SymbolClass symClass;
ubyte flags;
AstNode* node;
/// Symbol in outer scope with the same id. Can be null
Symbol* outerSymbol;
bool isInOrderedScope() { return cast(bool)(flags & SymbolFlags.isInOrderedScope); }
VariableDeclNode* varDecl() {
assert(node.astType == AstType.decl_var, format("varDecl used on %s", node.astType));
return cast(VariableDeclNode*)node;
}
FunctionDeclNode* funcDecl() {
assert(node.astType == AstType.decl_function, format("funcDecl used on %s", node.astType));
return cast(FunctionDeclNode*)node;
}
TypeNode* getType() {
switch(node.astType) with(AstType)
{
case decl_function: return (cast(FunctionDeclNode*)node).returnType;
case decl_var: return (cast(VariableDeclNode*)node).type;
case expr_var, expr_literal, expr_bin_op, expr_call, expr_index, expr_type_conv:
return (cast(ExpressionNode*)node).type;
case type_basic: return cast(TypeNode*)node;
case type_user: return cast(TypeNode*)node;
default: assert(false, format("getType used on %s", node.astType));
}
}
}
struct Scope
{
Symbol*[Identifier] symbols;
Scope* parentScope;
string debugName;
bool isOrdered;
}
/// Used for semantic analysis
struct ScopeStack
{
CompilationContext* context;
// TODO: do not maintain all visible symbols for current scope
// We will only use a small portion of visible symbols in each scope,
// so maintaining this is most probably wasted effort, and
// it is faster to walk up the scope stack. Need to benchmark.
Symbol*[Identifier] symbols;
Scope* currentScope;
/// Used in 1 semantic pass
Scope* pushScope(string name, Flag!"ordered" isOrdered)
{
//print("push scope %s", name); // debug
//indent += indentSize;
Scope* newScope = new Scope;
newScope.isOrdered = isOrdered;
newScope.debugName = name;
if (currentScope)
newScope.parentScope = currentScope;
return currentScope = newScope;
}
/// Used in 2 semantic pass
void pushCompleteScope(Scope* newScope)
{
//print("push scope %s", newScope.debugName); // debug
//indent += indentSize;
currentScope = newScope;
foreach (id, sym; newScope.symbols)
{
if (auto outerSymbol = symbols.get(sym.id, null))
sym.outerSymbol = outerSymbol;
symbols[id] = sym;
}
}
/// Used in 1 semantic pass
void popScope1()
{
if (currentScope.parentScope) currentScope = currentScope.parentScope;
else currentScope = null;
}
/// Used in 2 semantic pass
void popScope2()
{
assert(currentScope);
//indent -= indentSize; // debug
//if (currentScope.debugName) print("pop scope %s", currentScope.debugName);
//else print("pop scope");
// Pop all symbols of the scope we are leaving from symbols
foreach(id, sym; currentScope.symbols)
{
if (sym.outerSymbol) // replace by symbol from outer scope
symbols[id] = sym.outerSymbol;
else // or simply remove it if no such symbol
symbols.remove(id);
}
if (currentScope.parentScope)
currentScope = currentScope.parentScope;
else
currentScope = null;
}
/// Used in 2 semantic pass
/// Look up symbol by Identifier. Searches the whole stack of scopes.
Symbol* lookup(const Identifier id, SourceLocation from)
{
auto sym = symbols.get(id, null);
while (sym)
{
// print("try lookup %s @ %s", context.idString(sym.id), sym.loc);
// forward reference allowed for unordered scope
if (!sym.isInOrderedScope) break;
// not a forward reference
else if (from.start > sym.loc.start) break;
sym = sym.outerSymbol;
}
if (sym) {
//print("lookup %s @ %s", context.idString(sym.id), sym.loc);
}
else
{
context.error(from, "undefined identifier `%s`", context.idString(id));
}
return sym;
}
/// Used in 1 semantic pass
/// Constructs and inserts symbol with id
Symbol* insert(Identifier id, SourceLocation loc, SymbolClass symClass, AstNode* node)
{
typeof(Symbol.flags) flags = currentScope.isOrdered ? SymbolFlags.isInOrderedScope : 0;
auto sym = new Symbol(id, loc, symClass, flags, node);
insert(sym);
return sym;
}
/// Used in 1 semantic pass
/// Inserts symbol `sym`
void insert(Symbol* sym)
{
//print("insert %s @ %s", context.idString(sym.id), sym.loc);
symbols[sym.id] = sym;
if (auto s = currentScope.symbols.get(sym.id, null))
{
context.error(sym.loc,
"declaration `%s` is already defined at %s", context.idString(sym.id), s.loc);
}
currentScope.symbols[sym.id] = sym;
}
int indentSize = 2;
int indent;
void print(Args...)(Args args) {
write(' '.repeat(indent));
writefln(args);
}
}
void pass_semantic_decl(ref CompilationContext ctx) {
ctx.scopeStack = ScopeStack(&ctx);
auto sem1 = SemanticDeclarations(&ctx, &ctx.scopeStack);
sem1.visit(ctx.mod);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment