Closed Bug 1078871 Opened 10 years ago Closed 10 years ago

Contrary to recently added assertion, it's possible to create deep chains of dependent strings

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla35

People

(Reporter: jimb, Assigned: bhackett1024)

References

Details

Attachments

(1 file)

Bug 1066828 included this change:

 MOZ_ALWAYS_INLINE JSLinearString *
 JSDependentString::new_(js::ExclusiveContext *cx, JSLinearString *baseArg, size_t start,
                         size_t length)
 {
     /* Try to avoid long chains of dependent strings. */
-    while (baseArg->isDependent()) {
+    if (baseArg->isDependent()) {
         start += baseArg->asDependent().baseOffset();
         baseArg = baseArg->asDependent().base();
     }
+    MOZ_ASSERT(!baseArg->isDependent());
 
With this change, the assertion reads that we never create dependent strings of dependent strings, because a single indirection should always lead us to a non-dependent string.

However, we do. The following program hits this assertion after a few hundred iterations, after producing some oddly rhythmic babbling:

function tangle(n, m) {
  function rand(n) {
    return Math.floor(Math.random() * n);
  }

  var arr = [];
  for (var i = 0; i < n; i++)
    arr[i] = String.fromCharCode(65 + rand(26));
  for (var i = 0; i < m; i++) {
    var j = rand(n);
    switch (rand(2)) {
      case 0: {
        var s = arr[rand(n)];
        var b = rand(s.length);
        var e = b + rand(s.length - b);
        if (e - b > 1)
          arr[j] = s.substring(b, e);
      }
      break;
      case 1: {
        arr[j] = arr[rand(n)] + arr[rand(n)];
      }
    }
    print("Produced " + uneval(arr[j]));
  }

  return arr;
}

tangle(10, 40000);
Assuming no stray pointers, everything else that could produce dependent strings is in JSRope::flattenInternal. The comment at the top says:

     * N.B. This optimization can create chains of dependent strings.

It's a bit hard to read, so I didn't look into where or why.
Attached patch patchSplinter Review
I tried to remove this in bug 1066828 since it is both a complexity and an efficiency savings.  The rope flattening case doesn't look like it can be fixed, though (a base flat string gets transformed into a dependent string and to avoid chains we would need to know any other dependent strings attached to that flat one), but since (a) chains of dependent strings have no cost other than potentially keeping a few more GC strings alive, and (b) it's extraordinarily hard to create such chains (and before this bug we had no tests which did so), I don't think there's a good justification for having a loop here.
Assignee: nobody → bhackett1024
Attachment #8500779 - Flags: review?(jdemooij)
Oh, and thanks for the nice testcase!
Blocks: 1078194
To wit, these chains of dependent strings were the source of a terrible s-s bug in the original rope implementation whose fix required the addition of JSUndependedString.
(In reply to Brian Hackett (:bhackett) from comment #3)
> Oh, and thanks for the nice testcase!

I'm glad you found it helpful. I was actually a little embarrassed to post it: it should be reduced, and it ought to be deterministic. I looked into improving it, but reading flattenInternal looked like a huge time sink.
Yeah, deterministic testcases are nice.  The one in the patch replaces Math.random with a deterministic function, as is done by the octane benchmark.
Comment on attachment 8500779 [details] [diff] [review]
patch

Review of attachment 8500779 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/String-inl.h
@@ +167,1 @@
>      if (baseArg->isDependent()) {

Why not change this back to a 'while' loop, and retain the assertion? Do we get quadratic behavior?
(In reply to Jim Blandy :jimb from comment #7)
> Comment on attachment 8500779 [details] [diff] [review]
> patch
> 
> Review of attachment 8500779 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/vm/String-inl.h
> @@ +167,1 @@
> >      if (baseArg->isDependent()) {
> 
> Why not change this back to a 'while' loop, and retain the assertion? Do we
> get quadratic behavior?

We don't get quadratic behavior, but per comment 2 I just don't think there's a good justification for having this loop.  With bug 1066828 we can now create dependent strings in jitcode, and need to model the behavior of JSDependentString::new_.  So if there's a loop here there should be a loop there, and I just don't think the complexity and overhead of having the loop is justified.  It's not a hill I'm going to die on though.
Attachment #8500779 - Flags: review?(jdemooij) → review+
https://hg.mozilla.org/mozilla-central/rev/2a12b3e698c9
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla35
You need to log in before you can comment on or make changes to this bug.