| // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| library sourcemap.diff; |
| |
| import 'package:compiler/src/io/source_file.dart'; |
| |
| import 'html_parts.dart'; |
| import 'output_structure.dart'; |
| import 'sourcemap_helper.dart'; |
| |
| enum DiffKind { |
| UNMATCHED, |
| MATCHING, |
| IDENTICAL, |
| } |
| |
| /// A list of columns that should align in output. |
| class DiffBlock { |
| final DiffKind kind; |
| List<List<HtmlPart>> columns = <List<HtmlPart>>[]; |
| |
| DiffBlock(this.kind); |
| |
| void addColumn(int index, List<HtmlPart> lines) { |
| if (index >= columns.length) { |
| columns.length = index + 1; |
| } |
| columns[index] = lines; |
| } |
| |
| List<HtmlPart> getColumn(int index) { |
| List<HtmlPart> lines; |
| if (index < columns.length) { |
| lines = columns[index]; |
| } |
| return lines != null ? lines : const <HtmlPart>[]; |
| } |
| } |
| |
| |
| /// Align the content of [list1] and [list2]. |
| /// |
| /// If provided, [range1] and [range2] aligned the subranges of [list1] and |
| /// [list2], otherwise the whole lists are aligned. |
| /// |
| /// If provided, [match] determines the equality between members of [list1] and |
| /// [list2], otherwise `==` is used. |
| /// |
| /// [handleSkew] is called when a subrange of one list is not found in the |
| /// other. |
| /// |
| /// [handleMatched] is called when two indices match up. |
| /// |
| /// [handleUnmatched] is called when two indices don't match up (none are found |
| /// in the other list). |
| void align(List list1, |
| List list2, |
| {Interval range1, |
| Interval range2, |
| bool match(a, b), |
| void handleSkew(int listIndex, Interval range), |
| void handleMatched(List<int> indices), |
| void handleUnmatched(List<int> indices)}) { |
| if (match == null) { |
| match = (a, b) => a == b; |
| } |
| |
| if (range1 == null) { |
| range1 = new Interval(0, list1.length); |
| } |
| if (range2 == null) { |
| range2 = new Interval(0, list2.length); |
| } |
| |
| Interval findInOther( |
| List thisLines, Interval thisRange, |
| List otherLines, Interval otherRange) { |
| for (int index = otherRange.from; index < otherRange.to; index++) { |
| if (match(thisLines[thisRange.from], otherLines[index])) { |
| int offset = 1; |
| while (thisRange.from + offset < thisRange.to && |
| otherRange.from + offset < otherRange.to && |
| match(thisLines[thisRange.from + offset], |
| otherLines[otherRange.from + offset])) { |
| offset++; |
| } |
| return new Interval(index, index + offset); |
| } |
| } |
| return null; |
| } |
| |
| int start1 = range1.from; |
| int end1 = range1.to; |
| int start2 = range2.from; |
| int end2 = range2.to; |
| |
| const int ALIGN1 = -1; |
| const int UNMATCHED = 0; |
| const int ALIGN2 = 1; |
| |
| while (start1 < end1 && start2 < end2) { |
| if (match(list1[start1], list2[start2])) { |
| handleMatched([start1++, start2++]); |
| } else { |
| Interval subrange1 = new Interval(start1, end1); |
| Interval subrange2 = new Interval(start2, end2); |
| Interval element2inList1 = |
| findInOther(list1, subrange1, list2, subrange2); |
| Interval element1inList2 = |
| findInOther(list2, subrange2, list1, subrange1); |
| int choice = 0; |
| if (element2inList1 != null) { |
| if (element1inList2 != null) { |
| if (element1inList2.length > 1 && element2inList1.length > 1) { |
| choice = |
| element2inList1.from < element1inList2.from ? ALIGN2 : ALIGN1; |
| } else if (element2inList1.length > 1) { |
| choice = ALIGN2; |
| } else if (element1inList2.length > 1) { |
| choice = ALIGN1; |
| } else { |
| choice = |
| element2inList1.from < element1inList2.from ? ALIGN2 : ALIGN1; |
| } |
| } else { |
| choice = ALIGN2; |
| } |
| } else if (element1inList2 != null) { |
| choice = ALIGN1; |
| } |
| switch (choice) { |
| case ALIGN1: |
| handleSkew(0, new Interval(start1, element1inList2.from)); |
| start1 = element1inList2.from; |
| break; |
| case ALIGN2: |
| handleSkew(1, new Interval(start2, element2inList1.from)); |
| start2 = element2inList1.from; |
| break; |
| case UNMATCHED: |
| handleUnmatched([start1++, start2++]); |
| break; |
| } |
| } |
| } |
| if (start1 < end1) { |
| handleSkew(0, new Interval(start1, end1)); |
| } |
| if (start2 < end2) { |
| handleSkew(1, new Interval(start2, end2)); |
| } |
| } |
| |
| /// Create a list of blocks containing the diff of the two output [structures] |
| /// and the corresponding Dart code. |
| List<DiffBlock> createDiffBlocks( |
| List<OutputStructure> structures, |
| SourceFileManager sourceFileManager) { |
| return new DiffCreator(structures, sourceFileManager).computeBlocks(); |
| } |
| |
| class DiffCreator { |
| final List<OutputStructure> structures; |
| final SourceFileManager sourceFileManager; |
| |
| List<List<CodeLine>> inputLines; |
| |
| List<int> nextInputLine = [0, 0]; |
| |
| List<DiffBlock> blocks = <DiffBlock>[]; |
| |
| DiffCreator(List<OutputStructure> structures, this.sourceFileManager) |
| : this.structures = structures, |
| this.inputLines = structures.map((s) => s.lines).toList(); |
| |
| CodeSource codeSourceFromEntities(Iterable<OutputEntity> entities) { |
| for (OutputEntity entity in entities) { |
| if (entity.codeSource != null) { |
| return entity.codeSource; |
| } |
| } |
| return null; |
| } |
| |
| /// Checks that lines are added in sequence without gaps or duplicates. |
| void checkLineInvariant(int index, Interval range) { |
| int expectedLineNo = nextInputLine[index]; |
| if (range.from != expectedLineNo) { |
| print('Expected line no $expectedLineNo, found ${range.from}'); |
| if (range.from < expectedLineNo) { |
| print('Duplicate lines:'); |
| int i = range.from; |
| while (i <= expectedLineNo) { |
| print(inputLines[index][i++].code); |
| } |
| } else { |
| print('Missing lines:'); |
| int i = expectedLineNo; |
| while (i <= range.from) { |
| print(inputLines[index][i++].code); |
| } |
| } |
| } |
| nextInputLine[index] = range.to; |
| } |
| |
| /// Creates a block containing the code lines in [range] from input number |
| /// [index]. If [codeSource] is provided, the block will contain a |
| /// corresponding Dart code column. |
| void handleSkew(int index, Interval range, [CodeSource codeSource]) { |
| DiffBlock block = new DiffBlock(DiffKind.UNMATCHED); |
| checkLineInvariant(index, range); |
| block.addColumn(index, inputLines[index].sublist(range.from, range.to)); |
| if (codeSource != null) { |
| block.addColumn(2, |
| codeLinesFromCodeSource(sourceFileManager, codeSource)); |
| } |
| blocks.add(block); |
| } |
| |
| /// Create a block containing the code lines in [ranges] from the |
| /// corresponding JavaScript inputs. If [codeSource] is provided, the block |
| /// will contain a corresponding Dart code column. |
| void addLines(DiffKind kind, List<Interval> ranges, [CodeSource codeSource]) { |
| DiffBlock block = new DiffBlock(kind); |
| for (int i = 0; i < ranges.length; i++) { |
| checkLineInvariant(i, ranges[i]); |
| block.addColumn(i, inputLines[i].sublist(ranges[i].from, ranges[i].to)); |
| } |
| if (codeSource != null) { |
| block.addColumn(2, |
| codeLinesFromCodeSource(sourceFileManager, codeSource)); |
| } |
| blocks.add(block); |
| } |
| |
| /// Merge the code lines in [range1] and [range2] of the corresponding input. |
| void addRaw(Interval range1, Interval range2) { |
| match(a, b) => a.code == b.code; |
| |
| List<Interval> currentMatchedIntervals; |
| List<Interval> currentUnmatchedIntervals; |
| |
| void flushMatching() { |
| if (currentMatchedIntervals != null) { |
| addLines(DiffKind.IDENTICAL, currentMatchedIntervals); |
| } |
| currentMatchedIntervals = null; |
| } |
| |
| void flushUnmatched() { |
| if (currentUnmatchedIntervals != null) { |
| addLines(DiffKind.UNMATCHED, currentUnmatchedIntervals); |
| } |
| currentUnmatchedIntervals = null; |
| } |
| |
| List<Interval> updateIntervals(List<Interval> current, List<int> indices) { |
| if (current == null) { |
| return [ |
| new Interval(indices[0], indices[0] + 1), |
| new Interval(indices[1], indices[1] + 1)]; |
| } else { |
| current[0] = |
| new Interval(current[0].from, indices[0] + 1); |
| current[1] = |
| new Interval(current[1].from, indices[1] + 1); |
| return current; |
| } |
| } |
| |
| align( |
| inputLines[0], |
| inputLines[1], |
| range1: range1, |
| range2: range2, |
| match: match, |
| handleSkew: (int listIndex, Interval range) { |
| flushMatching(); |
| flushUnmatched(); |
| handleSkew(listIndex, range); |
| }, |
| handleMatched: (List<int> indices) { |
| flushUnmatched(); |
| currentMatchedIntervals = |
| updateIntervals(currentMatchedIntervals, indices); |
| }, |
| handleUnmatched: (List<int> indices) { |
| flushMatching(); |
| currentUnmatchedIntervals = |
| updateIntervals(currentUnmatchedIntervals, indices); |
| }); |
| |
| flushMatching(); |
| flushUnmatched(); |
| } |
| |
| /// Adds the top level blocks in [childRange] for structure [index]. |
| void addBlock(int index, Interval childRange) { |
| addSkewedChildren(index, structures[index], childRange); |
| } |
| |
| /// Adds the [entity] from structure [index]. If the [entity] supports child |
| /// entities, these are process individually. Otherwise the lines from |
| /// [entity] are added directly. |
| void addSkewedEntity(int index, OutputEntity entity) { |
| if (entity.canHaveChildren) { |
| handleSkew(index, entity.header); |
| addSkewedChildren( |
| index, entity, new Interval(0, entity.children.length)); |
| handleSkew(index, entity.footer); |
| } else { |
| handleSkew(index, entity.interval, codeSourceFromEntities([entity])); |
| } |
| } |
| |
| /// Adds the children of [parent] in [childRange] from structure [index]. |
| void addSkewedChildren(int index, OutputEntity parent, Interval childRange) { |
| for (int i = childRange.from; i < childRange.to; i++) { |
| addSkewedEntity(index, parent.getChild(i)); |
| } |
| } |
| |
| /// Adds the members of the [classes] aligned. |
| void addMatchingContainers(List<OutputEntity> classes) { |
| addLines(DiffKind.MATCHING, classes.map((c) => c.header).toList()); |
| align(classes[0].children, classes[1].children, |
| match: (a, b) => a.name == b.name, |
| handleSkew: (int listIndex, Interval childRange) { |
| addSkewedChildren(listIndex, classes[listIndex], childRange); |
| }, |
| handleMatched: (List<int> indices) { |
| List<BasicEntity> entities = [ |
| classes[0].getChild(indices[0]), |
| classes[1].getChild(indices[1])]; |
| if (entities.every((e) => e is Statics)) { |
| addMatchingContainers(entities); |
| } else { |
| addLines(DiffKind.MATCHING, |
| entities.map((e) => e.interval).toList(), |
| codeSourceFromEntities(entities)); |
| } |
| }, |
| handleUnmatched: (List<int> indices) { |
| List<Interval> intervals = [ |
| classes[0].getChild(indices[0]).interval, |
| classes[1].getChild(indices[1]).interval]; |
| addLines(DiffKind.UNMATCHED, intervals); |
| }); |
| addLines(DiffKind.MATCHING, classes.map((c) => c.footer).toList()); |
| } |
| |
| /// Adds the library blocks in [indices] from the corresponding |
| /// [OutputStructure]s, aligning their content. |
| void addMatchingBlocks(List<int> indices) { |
| List<LibraryBlock> blocks = [ |
| structures[0].getChild(indices[0]), |
| structures[1].getChild(indices[1])]; |
| |
| addLines(DiffKind.MATCHING, blocks.map((b) => b.header).toList()); |
| align(blocks[0].children, blocks[1].children, |
| match: (a, b) => a.name == b.name, |
| handleSkew: (int listIndex, Interval childRange) { |
| addSkewedChildren( |
| listIndex, blocks[listIndex], childRange); |
| }, |
| handleMatched: (List<int> indices) { |
| List<BasicEntity> entities = [ |
| blocks[0].getChild(indices[0]), |
| blocks[1].getChild(indices[1])]; |
| if (entities.every((e) => e is LibraryClass)) { |
| addMatchingContainers(entities); |
| } else { |
| addLines( |
| DiffKind.MATCHING, |
| entities.map((e) => e.interval).toList(), |
| codeSourceFromEntities(entities)); |
| } |
| }, |
| handleUnmatched: (List<int> indices) { |
| List<Interval> intervals = [ |
| blocks[0].getChild(indices[0]).interval, |
| blocks[1].getChild(indices[1]).interval]; |
| addLines(DiffKind.UNMATCHED, intervals); |
| }); |
| addLines(DiffKind.MATCHING, blocks.map((b) => b.footer).toList()); |
| } |
| |
| /// Adds the lines of the blocks in [indices] from the corresponding |
| /// [OutputStructure]s. |
| void addUnmatchedBlocks(List<int> indices) { |
| List<LibraryBlock> blocks = [ |
| structures[0].getChild(indices[0]), |
| structures[1].getChild(indices[1])]; |
| addLines(DiffKind.UNMATCHED, [blocks[0].interval, blocks[1].interval]); |
| } |
| |
| /// Computes the diff blocks for [OutputStructure]s. |
| List<DiffBlock> computeBlocks() { |
| addRaw(structures[0].header, structures[1].header); |
| |
| align(structures[0].children, |
| structures[1].children, |
| match: (a, b) => a.name == b.name, |
| handleSkew: addBlock, |
| handleMatched: addMatchingBlocks, |
| handleUnmatched: addUnmatchedBlocks); |
| |
| addRaw(structures[0].footer, structures[1].footer); |
| |
| return blocks; |
| } |
| } |
| |
| /// Creates html lines for code lines in [codeSource]. [sourceFileManager] is |
| /// used to read that text from the source URIs. |
| List<HtmlPart> codeLinesFromCodeSource( |
| SourceFileManager sourceFileManager, |
| CodeSource codeSource) { |
| List<HtmlPart> lines = <HtmlPart>[]; |
| SourceFile sourceFile = sourceFileManager.getSourceFile(codeSource.uri); |
| String elementName = codeSource.name; |
| HtmlLine line = new HtmlLine(); |
| line.htmlParts.add(new ConstHtmlPart('<span class="comment">')); |
| line.htmlParts.add(new HtmlText( |
| '${elementName}: ${sourceFile.filename}')); |
| line.htmlParts.add(new ConstHtmlPart('</span>')); |
| lines.add(line); |
| if (codeSource.begin != null) { |
| int startLine = sourceFile.getLine(codeSource.begin); |
| int endLine = sourceFile.getLine(codeSource.end); |
| for (int lineNo = startLine; lineNo <= endLine; lineNo++) { |
| String text = sourceFile.getLineText(lineNo); |
| CodeLine codeLine = new CodeLine(lineNo, sourceFile.getOffset(lineNo, 0)); |
| codeLine.codeBuffer.write(text); |
| codeLine.htmlParts.add(new HtmlText(text)); |
| lines.add(codeLine); |
| } |
| } |
| return lines; |
| } |