DevTools: introduce Trie data structure

DevTools: introduce Trie data structure

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman

Committed: https://crrev.com/d9cfae12769e0007cc132d25af708a7f8a802096
Cr-Commit-Position: refs/heads/master@{#422663}

[lushnikov, 2016-10-03 08:58:51]

Description was changed from

==========
DevTools: introduce trie implementation

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman
==========

to

==========
DevTools: introduce Trie data structure

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman
==========

[lushnikov, 2016-10-03 08:58:56]

The CQ bit was checked by lushnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-03 08:59:04]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[lushnikov, 2016-10-03 08:59:34]

please, take a look

[commit-bot: I haz the power, 2016-10-03 11:30:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-03 11:30:42]

Dry run: This issue passed the CQ dry run.

[lushnikov, 2016-10-03 19:32:37]

please, take another look. I've updated measurements for the new proposed
implementation

[lushnikov, 2016-10-03 19:32:43]

The CQ bit was checked by lushnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-03 19:33:21]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-03 19:36:46]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-03 19:36:47]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_compile_dbg_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  mac_chromium_compile_dbg_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_comp...)
  mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[lushnikov, 2016-10-03 20:14:40]

The CQ bit was checked by lushnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-03 20:15:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[dgozman, 2016-10-03 20:32:57]

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Layo...
File third_party/WebKit/LayoutTests/http/tests/inspector-unit/trie.html (right):

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Layo...
third_party/WebKit/LayoutTests/http/tests/inspector-unit/trie.html:10:
UnitTest.addResult("\nTest add:");
Useless one.

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/devtools/BUILD.gn (right):

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/BUILD.gn:174: "front_end/platform/Trie.js",
common

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/devtools/front_end/platform/Trie.js (right):

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/platform/Trie.js:48:
this._marks[node] = false;
Why not remove edges which do not lead to leafs?

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/platform/Trie.js:79: node = next;
Can avoid |next| variable similar to has() function.

[commit-bot: I haz the power, 2016-10-03 21:46:21]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-03 21:46:22]

Dry run: This issue passed the CQ dry run.

[lushnikov, 2016-10-03 22:56:22]

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Layo...
File third_party/WebKit/LayoutTests/http/tests/inspector-unit/trie.html (right):

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Layo...
third_party/WebKit/LayoutTests/http/tests/inspector-unit/trie.html:10:
UnitTest.addResult("\nTest add:");
On 2016/10/03 20:32:57, dgozman wrote:
> Useless one.

Done.

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/devtools/BUILD.gn (right):

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/BUILD.gn:174: "front_end/platform/Trie.js",
On 2016/10/03 20:32:57, dgozman wrote:
> common

Done.

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/devtools/front_end/platform/Trie.js (right):

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/platform/Trie.js:48:
this._marks[node] = false;
On 2016/10/03 20:32:57, dgozman wrote:
> Why not remove edges which do not lead to leafs?

Done.

https://codereview.chromium.org/2385093002/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/platform/Trie.js:79: node = next;
On 2016/10/03 20:32:57, dgozman wrote:
> Can avoid |next| variable similar to has() function.

Nice, thanks

[lushnikov, 2016-10-03 22:56:27]

The CQ bit was checked by lushnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-03 22:57:12]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[dgozman, 2016-10-03 23:08:34]

lgtm

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/devtools/front_end/common/Trie.js (right):

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:26: next =
this._freeNodes.pop();
Let's comment that we don't clear all the fields because they are properly
cleaned up in remove().

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:56:
this._freeNodes.push(next);
Let's exercise add->remove->add in the test.

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:137: this._marks =
[false];
_isWord or something like that?

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:139:
this._subtreeMarks = [0];
_wordsInSubtree

[lushnikov, 2016-10-04 00:17:59]

Thanks, all done!

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
File third_party/WebKit/Source/devtools/front_end/common/Trie.js (right):

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:26: next =
this._freeNodes.pop();
On 2016/10/03 23:08:34, dgozman wrote:
> Let's comment that we don't clear all the fields because they are properly
> cleaned up in remove().

Done.

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:56:
this._freeNodes.push(next);
On 2016/10/03 23:08:34, dgozman wrote:
> Let's exercise add->remove->add in the test. 

Done.

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:137: this._marks =
[false];
On 2016/10/03 23:08:34, dgozman wrote:
> _isWord or something like that?

Done.

https://codereview.chromium.org/2385093002/diff/60001/third_party/WebKit/Sour...
third_party/WebKit/Source/devtools/front_end/common/Trie.js:139:
this._subtreeMarks = [0];
On 2016/10/03 23:08:34, dgozman wrote:
> _wordsInSubtree

Done.

[lushnikov, 2016-10-04 00:18:05]

The CQ bit was checked by lushnikov@chromium.org

[lushnikov, 2016-10-04 00:18:05]

The patchset sent to the CQ was uploaded after l-g-t-m from dgozman@chromium.org
Link to the patchset: https://codereview.chromium.org/2385093002/#ps80001
(title: "address comments")

[commit-bot: I haz the power, 2016-10-04 00:19:05]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-04 01:55:32]

Description was changed from

==========
DevTools: introduce Trie data structure

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman
==========

to

==========
DevTools: introduce Trie data structure

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman
==========

[commit-bot: I haz the power, 2016-10-04 01:55:33]

Committed patchset #5 (id:80001)

[commit-bot: I haz the power, 2016-10-04 02:00:08]

Description was changed from

==========
DevTools: introduce Trie data structure

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman
==========

to

==========
DevTools: introduce Trie data structure

This patch introduces uncompressed Trie implementation. Trie comes handy
to quickly answer questions of type "give me all words with given prefix".

Text editor autocomplete benefits immediately from the trie index.
The automapping algorithm prototype also relies heavily on the trie to
quickly query file paths.

The performance and memory analysis of the implementation:
https://goo.gl/UdgS4H

BUG=none
R=dgozman, pfeldman

Committed: https://crrev.com/d9cfae12769e0007cc132d25af708a7f8a802096
Cr-Commit-Position: refs/heads/master@{#422663}
==========

[commit-bot: I haz the power, 2016-10-04 02:00:09]

Patchset 5 (id:??) landed as
https://crrev.com/d9cfae12769e0007cc132d25af708a7f8a802096
Cr-Commit-Position: refs/heads/master@{#422663}