feat(language-core): support overlapping ranges #205
Conversation
| @@ -60,13 +60,13 @@ export class SourceMapWithDocuments { | |||
| } | |||
|
|
|||
| public * getSourcePositions(position: vscode.Position, filter: (data: CodeInformation) => boolean = () => true) { | |||
| for (const mapped of this.findPositions(position, filter, this.embeddedDocument, this.sourceDocument, 'generatedOffsets', 'sourceOffsets')) { | |||
| for (const mapped of this.findPositions(position, filter, this.embeddedDocument, this.sourceDocument, 'generatedOffsets')) { | |||
There was a problem hiding this comment.
I've cleaned up an API a little bit - 'sourceOffsets' is a duplciated information here
| ) { | ||
| for (const mapped of this.map.findMatching(fromDoc.offsetAt(position), from, to)) { | ||
| for (const mapped of this.map.findMatchingOffsets(fromDoc.offsetAt(position), from)) { |
There was a problem hiding this comment.
Refactored name for consistency with other methods on the map
| if (filter(mapping.data)) { | ||
| mappedStart = mapped; | ||
| break; | ||
| for (const [mappedStart, mappedEnd] of map.getGeneratedStartEnd(start, end, filter)) { |
There was a problem hiding this comment.
filter is added to map API, to optimize iterations and disregard mappings early on
| const isSorted = fromOffsets.every((value, index) => index === 0 || fromOffsets[index - 1] <= value); | ||
| if (!isSorted) { | ||
| throw new Error('fromOffsets must be sorted in ascending order'); | ||
| if (!areRangesSortedAndNonOverlapping(fromOffsets, fromLengths)) { |
There was a problem hiding this comment.
Added stricter check - ranges should not be overlapping with the mapping
| test('Angular template with overlapping ranges', () => { | ||
| const map = new SourceMap([ | ||
| { | ||
| sourceOffsets: [ |
There was a problem hiding this comment.
I think this is where our misunderstanding comes from. When generating the map, I am putting all of the mappings into a single offsets array. It seems that this is not the intended use of the API, but it's a more performative one - less memory consumption.
| } | ||
| } | ||
| if (!mapped) { |
There was a problem hiding this comment.
All of the logic goes to the map, which can fallback to map-anything-mode
| const memo = this.getMemoBasedOnRange(fromRange); | ||
| if (memo.offsets.length === 0) { | ||
| return; | ||
| * findMatchingStartEnd(start: number, end: number, fromRange: CodeRangeKey, filter?: (data: Data) => boolean): Generator<[start: number, end: number, Mapping<Data>]> { |
There was a problem hiding this comment.
Moving range matching logic to the source map ensures that we have consistency across the codebase
| if (mapped !== undefined) { | ||
| yield [mapped, mapping as Mapping<Data>] as const; | ||
| for (const endMatch of endMatches) { | ||
| if (endMatch[0] != mapping) { |
There was a problem hiding this comment.
Not sure about this part, maybe we can have a second loop as a fallback, where we try to match just anything
packages/source-map/lib/sourceMap.ts
Outdated
| } | ||
|
|
||
| private createStorage(key: CodeRangeKey): MapStorage<Data> { | ||
| if (this.mappings.every(mapping => areRangesSortedAndNonOverlapping(mapping[key], getLengths(mapping, key)))) { |
There was a problem hiding this comment.
Several thoughts here:
- We could also just throw an error if mappings are too large or contain overlapping ranges and not use
IntervalTreeStorageat all. - I wonder if there are any benefits to use
IntervalTreeStoragein terms of performance. - It seems that we small modification, your structure can be reused for overlapping ranges as well. Which structure would be more performant?
- The thing is, that if you have many mappings, storing their offsets and lengths in arrays takes much less memory as you don't need to create an object for each mapping - see the modified Angular template test how I use mappings.
| const fromLength = fromLengths[mid]; | ||
|
|
||
| if (offset >= fromOffset && offset <= fromOffset + fromLength) { | ||
| yield [mapping, mid] |
There was a problem hiding this comment.
The only difference in the algorithm here is that I return the index instead of ready-to-use offset, as I can than match ranges, so one would not need to do zero-length thingies.
piotrtomiak
force-pushed
the
overlapping-ranges
branch
from
2254992 to
c7b4c3d
Compare
|
I'll create a new one |
Closes #203