From 457cb1dc843511d6e987b0ffce0f985d4e97c968 Mon Sep 17 00:00:00 2001 From: Greg Hysen Date: Tue, 13 Nov 2018 15:55:07 -0800 Subject: optimizer works for basic case --- packages/order-utils/test/abi/calldata.ts | 98 +++++++++++++++++++++++-- packages/order-utils/test/abi/evm_data_types.ts | 4 +- packages/order-utils/test/abi_encoder_test.ts | 16 +++- 3 files changed, 109 insertions(+), 9 deletions(-) (limited to 'packages') diff --git a/packages/order-utils/test/abi/calldata.ts b/packages/order-utils/test/abi/calldata.ts index 1173f90cc..ab42b7d73 100644 --- a/packages/order-utils/test/abi/calldata.ts +++ b/packages/order-utils/test/abi/calldata.ts @@ -29,6 +29,10 @@ export abstract class CalldataBlock { this.bodySizeInBytes = bodySizeInBytes; } + protected setName(name: string) { + this.name = name; + } + public getName(): string { return this.name; } @@ -65,7 +69,14 @@ export abstract class CalldataBlock { this.offsetInBytes = offsetInBytes; } + public computeHash(): Buffer { + const rawData = this.getRawData(); + const hash = ethUtil.sha3(rawData); + return hash; + } + public abstract toBuffer(): Buffer; + public abstract getRawData(): Buffer; } export class PayloadCalldataBlock extends CalldataBlock { @@ -81,12 +92,19 @@ export class PayloadCalldataBlock extends CalldataBlock { public toBuffer(): Buffer { return this.payload; } + + public getRawData(): Buffer { + return this.payload; + } } export class DependentCalldataBlock extends CalldataBlock { public static DEPENDENT_PAYLOAD_SIZE_IN_BYTES = 32; + public static RAW_DATA_START = new Buffer('<'); + public static RAW_DATA_END = new Buffer('>'); private parent: CalldataBlock; private dependency: CalldataBlock; + private aliasFor: CalldataBlock | undefined; constructor(name: string, signature: string, parentName: string, relocatable: boolean, dependency: CalldataBlock, parent: CalldataBlock) { const headerSizeInBytes = 0; @@ -94,13 +112,14 @@ export class DependentCalldataBlock extends CalldataBlock { super(name, signature, parentName, headerSizeInBytes, bodySizeInBytes, relocatable); this.parent = parent; this.dependency = dependency; + this.aliasFor = undefined; } public toBuffer(): Buffer { - const dependencyOffset = this.dependency.getOffsetInBytes(); + const destinationOffset = (this.aliasFor !== undefined) ? this.aliasFor.getOffsetInBytes() : this.dependency.getOffsetInBytes(); const parentOffset = this.parent.getOffsetInBytes(); const parentHeaderSize = this.parent.getHeaderSizeInBytes(); - const pointer: number = dependencyOffset - (parentOffset + parentHeaderSize); + const pointer: number = destinationOffset - (parentOffset + parentHeaderSize); const pointerBuf = ethUtil.toBuffer(`0x${pointer.toString(16)}`); const evmWordWidthInBytes = 32; const pointerBufPadded = ethUtil.setLengthLeft(pointerBuf, evmWordWidthInBytes); @@ -110,6 +129,25 @@ export class DependentCalldataBlock extends CalldataBlock { public getDependency(): CalldataBlock { return this.dependency; } + + public setAlias(block: CalldataBlock) { + this.aliasFor = block; + this.setName(`${this.getName()} (alias for ${block.getName()})`); + } + + public getAlias(): CalldataBlock | undefined { + return this.aliasFor; + } + + public getRawData(): Buffer { + const dependencyRawData = this.dependency.getRawData(); + const rawDataComponents: Buffer[] = []; + rawDataComponents.push(DependentCalldataBlock.RAW_DATA_START); + rawDataComponents.push(dependencyRawData); + rawDataComponents.push(DependentCalldataBlock.RAW_DATA_END); + const rawData = Buffer.concat(rawDataComponents); + return rawData; + } } export class MemberCalldataBlock extends CalldataBlock { @@ -125,6 +163,20 @@ export class MemberCalldataBlock extends CalldataBlock { this.contiguous = contiguous; } + public getRawData(): Buffer { + const rawDataComponents: Buffer[] = []; + if (this.header !== undefined) { + rawDataComponents.push(this.header); + } + _.each(this.members, (member: CalldataBlock) => { + const memberBuffer = member.getRawData(); + rawDataComponents.push(memberBuffer); + }); + + const rawData = Buffer.concat(rawDataComponents); + return rawData; + } + public setMembers(members: CalldataBlock[]) { let bodySizeInBytes = 0; _.each(members, (member: CalldataBlock) => { @@ -201,8 +253,8 @@ export class Calldata { // Children _.each(memberBlock.getMembers(), (member: CalldataBlock) => { - if (member instanceof DependentCalldataBlock) { - const dependency = member.getDependency(); + if (member instanceof DependentCalldataBlock && member.getAlias() === undefined) { + let dependency = member.getDependency(); if (dependency instanceof MemberCalldataBlock) { blockQueue.merge(this.createQueue(dependency)); } else { @@ -321,6 +373,41 @@ export class Calldata { return hexValue; } + public optimize() { + if (this.root === undefined) { + throw new Error('expected root'); + } + + const subtreesByHash: { [key: string]: DependentCalldataBlock[] } = {}; + + // 1. Create a queue of subtrees by hash + // Note that they are ordered the same as + const subtreeQueue = this.createQueue(this.root); + let block: CalldataBlock | undefined; + while ((block = subtreeQueue.pop()) !== undefined) { + console.log(block.getName()); + + if (block instanceof DependentCalldataBlock === false) continue; + const blockHashBuf = block.computeHash(); + const blockHashHex = ethUtil.bufferToHex(blockHashBuf); + if (blockHashHex in subtreesByHash === false) { + subtreesByHash[blockHashHex] = [block as DependentCalldataBlock]; + } else { + subtreesByHash[blockHashHex].push(block as DependentCalldataBlock); + } + } + + // Iterate through trees that have the same hash and + _.each(subtreesByHash, (subtrees: DependentCalldataBlock[], hash: string) => { + if (subtrees.length === 1) return; // No optimization + // Optimize + const lastSubtree = subtrees[subtrees.length - 1]; + for (let i = 0; i < subtrees.length - 1; ++i) { + subtrees[i].setAlias(lastSubtree); + } + }); + } + public toHexString(optimize: boolean = false, annotate: boolean = false): string { if (this.root === undefined) { throw new Error('expected root'); @@ -334,8 +421,7 @@ export class Calldata { offset += block.getSizeInBytes(); } - - // if (optimize) this.optimize(valueQueue.getStore()); + if (optimize) this.optimize(); const hexValue = annotate ? this.generateAnnotatedHexString() : this.generateCondensedHexString(); return hexValue; diff --git a/packages/order-utils/test/abi/evm_data_types.ts b/packages/order-utils/test/abi/evm_data_types.ts index ea401247b..a24046664 100644 --- a/packages/order-utils/test/abi/evm_data_types.ts +++ b/packages/order-utils/test/abi/evm_data_types.ts @@ -489,10 +489,10 @@ export class Method extends MemberDataType { return selector; } - public encode(value: any[] | object, calldata = new Calldata(), annotate: boolean = false): string { + public encode(value: any[] | object, calldata = new Calldata(), annotate: boolean = false, optimize: boolean = false): string { calldata.setSelector(this.methodSelector); super.encode(value, calldata); - return calldata.toHexString(false, annotate); + return calldata.toHexString(optimize, annotate); } public decode(calldata: string, decodeStructsAsObjects: boolean = false): any[] | object { diff --git a/packages/order-utils/test/abi_encoder_test.ts b/packages/order-utils/test/abi_encoder_test.ts index 8b836f77f..5ef4203b7 100644 --- a/packages/order-utils/test/abi_encoder_test.ts +++ b/packages/order-utils/test/abi_encoder_test.ts @@ -27,7 +27,21 @@ const expect = chai.expect; describe.only('ABI Encoder', () => { describe.only('ABI Tests at Method Level', () => { - it.only('Crazy ABI', async () => { + it.only('Optimizer', async () => { + const method = new AbiEncoder.Method(AbiSamples.stringAbi); + const strings = [ + "Test String", + "Test String 2", + "Test String", + "Test String 2", + ]; + const args = [strings]; + + const optimizedCalldata = method.encode(args, new Calldata(), true, true); + console.log(optimizedCalldata); + }); + + it('Crazy ABI', async () => { const method = new AbiEncoder.Method(AbiSamples.crazyAbi); console.log(method.getSignature()); -- cgit v1.2.3