Re: Weak Graph

2015-11-06 Thread Steve Fink 

On 11/04/2015 08:09 AM, Jussi Kalliokoski wrote:
It provides the needed interface and the unused child revisions get 
cleaned up properly. However:


* This is a complete nightmare for GC performance because of cyclical 
weak references.


Not necessarily. Current Spidermonkey should handle it ok, using a 
linear-time algorithm for weakmap marking. (I think an inverted 
representation would also be good for this? I haven't thought it through.)



* Any reference to a child will maintain references to all its parents.

However this doesn't necessarily need to be the case because the 
stored ancestry is not observable to anything that creates a 
WeakGraph, except to the oldest ancestor that has a reference elsewhere.


I'm not sure if this use case alone warrants adding a new feature to 
the language, or if I'm just missing something and it can be 
implemented with existing constructs or if there should be some other 
lower level primitive that would allow building a WeakGraph on the 
user level.


The brute-force approach would be to give each node its own weakmap, and 
add an entry for *every* ancestor:


```JS
this.getLineage() = function (node, ancestor) {
  const lineage = [];
  while (node) {
lineage.push(node);
if (node == ancestor)
  return lineage;
node = node.parentForAncestor.get(ancestor);
  }
}

this.addNode = function (node, parent, ancestor) {
  node.parentForAncestor = new WeakMap();
  for (let key of this.getLineage(parent, ancestor))
node.parentForAncestor.set(key, parent);
};
```

...but notice that addNode now requires an ancestor to be specified, and 
it will only work as far back as that. And of course, this defeats the 
whole point of the exercise, in that it requires space quadratic in the 
number of live nodes. And insertion is linear in the distance from the 
node to the chosen ancestor. Which could still be a win in rare cases, I 
guess, but my point is only to show that the leak could be "fixed".


I should note that in your example, you have a WeakMap with basically 
infinite lifetime. That means that keys always hold values live, in 
which case you might as well store them directly as properties on the 
key (node.parent = parent).


I also pondered what language primitives would fix this case. The 
straightforward approach is to expose something tailored specifically to 
this use case -- call it a WeakList. You cannot look up elements by 
index. You can call WeakList.prototype.get(begin, end) and it will 
return an Array of elements from begin..end (where 'begin' and 'end' are 
actual elements of the list), or undefined if either begin or end is not 
present in the list. Internally, the implementation would allowed to 
discard all leading and trailing dead elements. It would be stored as a 
dag to share space with overlapping lists.


A totally different option is something I'm calling a VagueMap. I should 
mention here that I don't know of any prior art, nor have I looked for 
any, so my apologies if this is known by another name. A VagueMap is 
sort of the dual of a WeakMap, where the value keeps the entry (and key) 
alive rather than the key keeping the value alive. But to avoid exposing 
GC behavior, you cannot just look up values by key (since then if you 
wanted to know when something gets GC'ed, you'd just stick it in a 
VagueMap under a well-known key and look it up periodically.) Instead, 
get(key) returns a "vague value", which can only be used in two ways: 
for equality testing, and as a VagueMap key. VagueMap lookups would 
treat vague values and their equivalent non-vague values identically. 
VagueMap would also support has().


Note that VagueMap does not automatically keep its keys live (as in, 
only the ones with live values will be kept live.) So you still can't 
iterate over the keys.


This still doesn't fix the original example. The simple replacement of 
WeakMap with VagueMap will "work", but getLineage() will return an array 
of vague values, which aren't much use. So I'll need to add another 
funky feature to VagueMap: if you give it a (non-vague) value, it will 
hand you back the non-vague, guaranteed live, key. I'll call it 
VagueMap.prototype.getKey(vkey, value) where vkey is a possibly-vague 
key that maps to value.


We get back very close to the original code, with an added loop to reify 
the vague nodes (oh, and I include the ancestor in the lineage -- which 
means the do/while loop could now easily be a for loop, but I'll stick 
close to the original):


```JS
function WeakGraph () {
const parentByNode = new VagueMap();

this.getLineage = function (node, ancestor) {
const lineage = [];

let currentNode = node;
do {
lineage.push(currentNode);
if ( !parentByNode.has(currentNode) ) { throw new 
Error("node is not a descendant of ancestor"); }

currentNode = parentByNode.get(currentNode);
} while ( currentNode !== ancestor );

RE: RegExp free-spacing & comments

2015-11-06 Thread Gorkem Yakin 
I don’t know about other engines, but Chakra does cache the RegExp matcher when 
the RegExp object is created via the constructor.

Gorkem

From: es-discuss [mailto:es-discuss-boun...@mozilla.org] On Behalf Of Isiah 
Meadows
Sent: Friday, November 6, 2015 4:36 PM
To: C. Scott Ananian ; Brian Terlson 

Cc: es-discuss@mozilla.org
Subject: Re: RegExp free-spacing & comments


The problem with using the RegExp constructor is that it is never cached by the 
engine. As a literal, engines usually internalize them, speeding up matches 
very quickly.

On Fri, Nov 6, 2015, 14:24 C. Scott Ananian 
> wrote:
On Fri, Nov 6, 2015 at 1:20 PM, Brian Terlson
> wrote:
> RegExp.re or similar seems nice:
>
> ```
> let re = RegExp.re("x")`
> (\d{3}-)? # area code (optional)
> \d{3}-# prefix
> \d{4} # line number
> `;
> ```
>
> But it seems like previous proposals of this want escaping which doesn't seem 
> ideal for this purpose. Do we need both `RegExp.re` and `RegExp.escapedRe`?

Escaping happens if you use interpolation into the string template:
```
let re = RegExp.re`(?x:
(\d{3}-)?  # area code (optional)
${ /\d{3}/ }-  # prefix
\d{4}   # line number
( ${ "*" } \d+ )?  # extension
)`;
```
If the interpolated expression is a regexp, then things seem
relatively straightforward (although there are corner cases to
consider).  If the interpolated expression is a string, then it is
suggested that you use some sort of automatic escaping.
 --scott
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: RegExp free-spacing & comments

2015-11-06 Thread Isiah Meadows 
The problem with using the RegExp constructor is that it is never cached by
the engine. As a literal, engines usually internalize them, speeding up
matches very quickly.

On Fri, Nov 6, 2015, 14:24 C. Scott Ananian  wrote:

> On Fri, Nov 6, 2015 at 1:20 PM, Brian Terlson
>  wrote:
> > RegExp.re or similar seems nice:
> >
> > ```
> > let re = RegExp.re("x")`
> > (\d{3}-)? # area code (optional)
> > \d{3}-# prefix
> > \d{4} # line number
> > `;
> > ```
> >
> > But it seems like previous proposals of this want escaping which doesn't
> seem ideal for this purpose. Do we need both `RegExp.re` and
> `RegExp.escapedRe`?
>
> Escaping happens if you use interpolation into the string template:
> ```
> let re = RegExp.re`(?x:
> (\d{3}-)?  # area code (optional)
> ${ /\d{3}/ }-  # prefix
> \d{4}   # line number
> ( ${ "*" } \d+ )?  # extension
> )`;
> ```
> If the interpolated expression is a regexp, then things seem
> relatively straightforward (although there are corner cases to
> consider).  If the interpolated expression is a string, then it is
> suggested that you use some sort of automatic escaping.
>  --scott
> ___
> es-discuss mailing list
> es-discuss@mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: RegExp free-spacing & comments

2015-11-06 Thread Isiah Meadows 
Does it still read the string?

On Fri, Nov 6, 2015, 20:59 Gorkem Yakin  wrote:

> I don’t know about other engines, but Chakra does cache the RegExp matcher
> when the RegExp object is created via the constructor.
>
>
>
> Gorkem
>
>
>
> *From:* es-discuss [mailto:es-discuss-boun...@mozilla.org] *On Behalf Of 
> *Isiah
> Meadows
> *Sent:* Friday, November 6, 2015 4:36 PM
> *To:* C. Scott Ananian ; Brian Terlson <
> brian.terl...@microsoft.com>
> *Cc:* es-discuss@mozilla.org
> *Subject:* Re: RegExp free-spacing & comments
>
>
>
> The problem with using the RegExp constructor is that it is never cached
> by the engine. As a literal, engines usually internalize them, speeding up
> matches very quickly.
>
>
>
> On Fri, Nov 6, 2015, 14:24 C. Scott Ananian  wrote:
>
> On Fri, Nov 6, 2015 at 1:20 PM, Brian Terlson
>  wrote:
> > RegExp.re or similar seems nice:
> >
> > ```
> > let re = RegExp.re("x")`
> > (\d{3}-)? # area code (optional)
> > \d{3}-# prefix
> > \d{4} # line number
> > `;
> > ```
> >
> > But it seems like previous proposals of this want escaping which doesn't
> seem ideal for this purpose. Do we need both `RegExp.re` and
> `RegExp.escapedRe`?
>
> Escaping happens if you use interpolation into the string template:
> ```
> let re = RegExp.re`(?x:
> (\d{3}-)?  # area code (optional)
> ${ /\d{3}/ }-  # prefix
> \d{4}   # line number
> ( ${ "*" } \d+ )?  # extension
> )`;
> ```
> If the interpolated expression is a regexp, then things seem
> relatively straightforward (although there are corner cases to
> consider).  If the interpolated expression is a string, then it is
> suggested that you use some sort of automatic escaping.
>  --scott
> ___
> es-discuss mailing list
> es-discuss@mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
> 
>
>
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

RegExp free-spacing & comments

2015-11-06 Thread Brian Terlson 
While looking in to proposals for look-behinds and named capture groups for 
ECMAScript RegExps, I thought I'd also think about other oft-requested features 
we currently lack: free-spacing and comments. Comments allow a programmer to 
embed comments inside the regexp literal. Free-spacing tells the RegExp engine 
to ignore spaces, tabs, and line breaks. These two features go really nicely 
together to allow human readable regexps - different parts of a pattern can be 
split into separate lines with comments on each line describing what it 
matches. XRegExp supports both of these features as well as the RegExp engines 
in Perl, Java, C# and others.

One challenge with supporting free-spacing in ECMAScript is that we don't allow 
line breaks inside our regexp literal and constructing regexps from strings is 
somewhat annoying. The best we could have right now (I think) is something like:

```
let re = new RegExp(String.raw`
(\d{3}-)?# area code (optional)
\d{3}-# prefix
\d{4} # line number
`, "x");
```

I think this is still a win for long confusing patterns, but maybe I'm alone! 
Is free-spacing and comments still reasonable if we have to use string 
templates? Or is there a nice way to extend the grammar of regular expression 
literals to allow for line breaks? (Eg. maybe we only allow free-spacing with a 
mode specifier like (?x) inside the pattern?) Any other thoughts?
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: RegExp free-spacing & comments

2015-11-06 Thread C. Scott Ananian 
On Fri, Nov 6, 2015 at 1:20 PM, Brian Terlson
 wrote:
> RegExp.re or similar seems nice:
>
> ```
> let re = RegExp.re("x")`
> (\d{3}-)? # area code (optional)
> \d{3}-# prefix
> \d{4} # line number
> `;
> ```
>
> But it seems like previous proposals of this want escaping which doesn't seem 
> ideal for this purpose. Do we need both `RegExp.re` and `RegExp.escapedRe`?

Escaping happens if you use interpolation into the string template:
```
let re = RegExp.re`(?x:
(\d{3}-)?  # area code (optional)
${ /\d{3}/ }-  # prefix
\d{4}   # line number
( ${ "*" } \d+ )?  # extension
)`;
```
If the interpolated expression is a regexp, then things seem
relatively straightforward (although there are corner cases to
consider).  If the interpolated expression is a string, then it is
suggested that you use some sort of automatic escaping.
 --scott
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: Weak Graph

2015-11-06 Thread Jason Orendorff 
On Wed, Nov 4, 2015 at 10:09 AM, Jussi Kalliokoski
 wrote:
> I'm trying to come up with a solution to the problem of rendering lists [...]
> My idea for a solution is that the lists are immutable, contain a reference
> to their parent and a changeset / diff compared to their parent. [...]

Good problem, interesting idea.

> The biggest problem is that this will leak memory like crazy; every revision
> of the list will be preserved.

OK. Perhaps obviously, the only way around this is to mutate the list,
breaking the chain at a point where nobody cares about the rest of it
anymore.

The approach you've outlined is to have the GC tell you when to do the
mutation, but why is that a good idea? You can do it deterministically
in getLineage().

Maybe the concepts here would be clearer if we limited the graph to a
single linked list. Then it looks a lot like a stream, in the
functional reactive programming sense. Let the user (in this case, the
renderer) buffer the diffs as needed; it knows when to reset the list.
And no need for fancy data structures: it could just be an Array.

-j
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: RegExp free-spacing & comments

2015-11-06 Thread Caitlin Potter 
(Repost from IRC discussion)

Could do something like this:

```javascript

let re = /```
(\d{3}-)?# area code (opt)
\d{3}-# exchange
\d{4} # line number
```/;

```

It looks sort of heredoc-ish, which is nice, and it shouldn’t break existing  
parsing rules.

RegularExpressionLiteral: /``` LineTerminator 
RegularExpressionBody[SpacingAndComments] ```/ RegularExpressionFlags

This is a PrimaryExpression, and therefore should not be confused with 
TemplateLiterals, or MultiplicativeExpressions. And because of the required 
linefeed,
should not break any existing RegularExpressionLiterals.

Just throwing it out there as a possibility.

The 3 backticks is a cute idea, but it probably doesn’t matter how it’s 
represented. It just looks very heredoc-ish, and distinct from TemplateLiterals.

> On Nov 6, 2015, at 12:28 PM, Brian Terlson  
> wrote:
> 
> While looking in to proposals for look-behinds and named capture groups for 
> ECMAScript RegExps, I thought I’d also think about other oft-requested 
> features we currently lack: free-spacing and comments. Comments allow a 
> programmer to embed comments inside the regexp literal. Free-spacing tells 
> the RegExp engine to ignore spaces, tabs, and line breaks. These two features 
> go really nicely together to allow human readable regexps – different parts 
> of a pattern can be split into separate lines with comments on each line 
> describing what it matches. XRegExp supports both of these features as well 
> as the RegExp engines in Perl, Java, C# and others.
> 
> One challenge with supporting free-spacing in ECMAScript is that we don’t 
> allow line breaks inside our regexp literal and constructing regexps from 
> strings is somewhat annoying. The best we could have right now (I think) is 
> something like:
> 
> ```
> let re = new RegExp(String.raw`
> (\d{3}-)?# area code (optional)
> \d{3}-# prefix
> \d{4} # line number
> `, "x");
> ```
> 
> I think this is still a win for long confusing patterns, but maybe I’m alone! 
> Is free-spacing and comments still reasonable if we have to use string 
> templates? Or is there a nice way to extend the grammar of regular expression 
> literals to allow for line breaks? (Eg. maybe we only allow free-spacing with 
> a mode specifier like (?x) inside the pattern?) Any other thoughts?
> ___
> es-discuss mailing list
> es-discuss@mozilla.org 
> https://mail.mozilla.org/listinfo/es-discuss 
> 


signature.asc
Description: Message signed with OpenPGP using GPGMail
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: RegExp free-spacing & comments

2015-11-06 Thread C. Scott Ananian 
We have a template string mechanism, and it allows linefeeds.  Let's
use that, instead of inventing new heredoc syntax.
 --scott
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: RegExp free-spacing & comments

2015-11-06 Thread C. Scott Ananian 
If you're using string templates, why not do the full regex there,
instead of just passing the result to `new RegExp`?

See https://esdiscuss.org/topic/regexp-escape#content-22 and
https://esdiscuss.org/topic/regexp-escape#content-28 for some
examples, and 
https://github.com/benjamingr/RegExp.escape/issues/37#issuecomment-126785041
for a discussion of creating a new template string function called
`re`.
  --scott

On Fri, Nov 6, 2015 at 12:28 PM, Brian Terlson
 wrote:
> While looking in to proposals for look-behinds and named capture groups for
> ECMAScript RegExps, I thought I’d also think about other oft-requested
> features we currently lack: free-spacing and comments. Comments allow a
> programmer to embed comments inside the regexp literal. Free-spacing tells
> the RegExp engine to ignore spaces, tabs, and line breaks. These two
> features go really nicely together to allow human readable regexps –
> different parts of a pattern can be split into separate lines with comments
> on each line describing what it matches. XRegExp supports both of these
> features as well as the RegExp engines in Perl, Java, C# and others.
>
>
>
> One challenge with supporting free-spacing in ECMAScript is that we don’t
> allow line breaks inside our regexp literal and constructing regexps from
> strings is somewhat annoying. The best we could have right now (I think) is
> something like:
>
>
>
> ```
>
> let re = new RegExp(String.raw`
>
> (\d{3}-)?# area code (optional)
>
> \d{3}-# prefix
>
> \d{4} # line number
>
> `, "x");
>
> ```
>
>
>
> I think this is still a win for long confusing patterns, but maybe I’m
> alone! Is free-spacing and comments still reasonable if we have to use
> string templates? Or is there a nice way to extend the grammar of regular
> expression literals to allow for line breaks? (Eg. maybe we only allow
> free-spacing with a mode specifier like (?x) inside the pattern?) Any other
> thoughts?
>
>
> ___
> es-discuss mailing list
> es-discuss@mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

RE: RegExp free-spacing & comments

2015-11-06 Thread Brian Terlson 
RegExp.re or similar seems nice:

```
let re = RegExp.re("x")`
(\d{3}-)? # area code (optional)
\d{3}-# prefix
\d{4} # line number
`;
```

But it seems like previous proposals of this want escaping which doesn't seem 
ideal for this purpose. Do we need both `RegExp.re` and `RegExp.escapedRe`?
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss

Re: Status of Chrome Proxy in face of Object.observe removal

2015-11-06 Thread Andreas Rossberg 
On 6 November 2015 at 19:16, Simon Blackwell
 wrote:
> In the face of the announcment that the  Object.observe standard proposal is
> being revoked and commentary that seems to indicate that at a minimum either
> Proxy or Object.observe is needed, does anyone know the status of
> re-introduction of Proxy into Chrome and v8?

We currently have like half a dozen people working on bringing proxies
to V8. It's a lot of work that leaves almost no stone unturned. But we
hope to be able to ship them early next year. Removing O.o will
actually help.

/Andreas
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss