Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

overwrite method can cause state corruption #115

Closed
alangpierce opened this issue Dec 5, 2016 · 1 comment · Fixed by #126
Closed

overwrite method can cause state corruption #115

alangpierce opened this issue Dec 5, 2016 · 1 comment · Fixed by #126

Comments

@alangpierce
Copy link
Collaborator

Follow-up from #113, where an optimization commit was causing the decaffeinate build to fail.

I tracked down the issue and found two problems with the code change:

  • In the first.next = last.next; line, it might end up causing first.next to point to null. In that case, this.lastChunk needs to be updated. In the test case below, this.lastChunk ends up pointing to an object that isn't actually the last chunk.
  • The byStart and byEnd maps are never updated to remove the old chunks, so later operations will find those unreferenced chunks and insert into them. This basically means that later insertions at certain points are just lost.

Here's a test case that worked before and fails now:

		it ( 'allows later insertions at the end', () => {
			const s = new MagicString( 'abcdefg' );

			s.appendLeft(4, '(');
			s.overwrite( 2, 7, '' );
			s.appendLeft(7, 'h');
			console.log(`s.toString is ${s.toString()}`);
			assert.equal( s.toString(), 'abh' );
		});

I was thinking of writing up a fix, but the code seems a bit delicate, so probably @Rich-Harris is better-qualified to come up with a confident fix that updates all relevant state. It might be best to just revert the optimization if the added complexity/risk isn't worth it.

@alangpierce
Copy link
Collaborator Author

Oh, another idea that might have prevented this is to have a method that checks all expected invariants (the linked list is well-formed, lastChunk actually points to the last chunk, byStart and byEnd exactly match the contents of the linked list), and somehow call it after each operation in test code.

alangpierce added a commit to alangpierce/magic-string that referenced this issue Jul 7, 2017
Fixes Rich-Harris#115

This commit adds a new `IntegrityCheckingMagicString` class that subclasses
`MagicString` and does an integrity check operation, which is used in test code.

This revealed 5 bugs, all of which are also fixed in this commit:
* Within `indent`, the code was calling `chunk.split`, then making an attempt at
  properly updating `byStart` and `byEnd`. But it wasn't properly updating
  `lastChunk`. Rather than calling `chunk.split`, we can just call
  `this._splitChunk`, which updates `byStart`, `byEnd`, and `lastChunk`
  correctly.
* `move` could sometimes assign `undefined` as a `next` pointer, which is
  inconsistent since all other cases use `null`. Not a really big deal, but nice
  to be consistent.
* `overwrite` was attempting to do a linked list removal in a way that wasn't
  properly updating all state ( Rich-Harris#115 ). I tried changing the code to remove the
  nodes properly, but the details seemed to get really subtle, especially
  accounting for moved fragments, and it didn't seem like the complexity was
  worth it, so I effectively just reverted Rich-Harris#113 to fix the issue. But now with
  the new integrity checking, it should be a lot easier to get the details right
  if that's desirable.
* `trimStart` and `trimEnd` were attempting to update `byStart` and `byEnd`, but
  they didn't properly set `byEnd` of the newly-created chunk created by
  `chunk.trimStart`/`chunk.trimEnd`. Setting the `byEnd` for that new chunk
  seems to fix things.
* `trimEnd` was setting `this.lastChunk = chunk.next`, which makes sense for the
  first iteration (when working with the very last chunk in the linked list),
  but doesn't make sense for later operations, since it meant that some chunks
  just get dropped. We now only run that line on the last chunk.
alangpierce added a commit to alangpierce/magic-string that referenced this issue Jul 7, 2017
Fixes Rich-Harris#115

This commit adds a new `IntegrityCheckingMagicString` class that subclasses
`MagicString` and does an integrity check operation, which is used in test code.

This revealed 5 bugs, all of which are also fixed in this commit:
* Within `indent`, the code was calling `chunk.split`, then making an attempt at
  properly updating `byStart` and `byEnd`. But it wasn't properly updating
  `lastChunk`. Rather than calling `chunk.split`, we can just call
  `this._splitChunk`, which updates `byStart`, `byEnd`, and `lastChunk`
  correctly.
* `move` could sometimes assign `undefined` as a `next` pointer, which is
  inconsistent since all other cases use `null`. Not a really big deal, but nice
  to be consistent.
* `overwrite` was attempting to do a linked list removal in a way that wasn't
  properly updating all state ( Rich-Harris#115 ). I tried changing the code to remove the
  nodes properly, but the details seemed to get really subtle, especially
  accounting for moved chunks, and it didn't seem like the complexity was worth
  it, so I effectively just reverted Rich-Harris#113 to fix the issue. But now with the
  new integrity checking, it should be a lot easier to get the details right if
  that's desirable.
* `trimStart` and `trimEnd` were attempting to update `byStart` and `byEnd`, but
  they didn't properly set `byEnd` of the newly-created chunk created by
  `chunk.trimStart`/`chunk.trimEnd`. Setting the `byEnd` for that new chunk
  seems to fix things.
* `trimEnd` was setting `this.lastChunk = chunk.next`, which makes sense for the
  first iteration (when working with the very last chunk in the linked list),
  but doesn't make sense for later iterations, since it meant that some chunks
  just get dropped. We now only run that line on the last chunk.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant