FilesExpand file tree

master

/

string-replace-stream.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

109 lines (102 loc) · 3.31 KB

master

/

string-replace-stream.js

Copy path

Top

File metadata and controls

• Code
• Blame

109 lines (102 loc) · 3.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

// Replace a string with another string in a node stream even when the search

// string spans multiple chunks

'use strict';

var through2 = require('through2');

var StringDecoder = require('string_decoder').StringDecoder;

// Build the Knuth-Morris-Pratt table

function buildTable(search) {

// Based on https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Description_of_pseudocode_for_the_table-building_algorithm

var table = Array(search.length), pos = 2, cnd = 0, searchLen = search.length;

table[0] = -1;

table[1] = 0;

while (pos < searchLen) {

if (search[pos-1] === search[cnd]) {

// the substring continues

cnd++;

table[pos] = cnd;

pos++;

} else if (cnd > 0) {

// it doesn't, but we can fall back

cnd = table[cnd];

} else {

// we have run part of candidates. Note cnd = 0

table[pos] = 0;

pos++;

}

}

return table;

}

// Create a transform stream that replaces one string with another

module.exports = function replaceStream(search, replace, opts) {

var encoding = (opts && opts.encoding) || 'utf8';

var decoder = new StringDecoder(encoding);

var matchStart = 0, matchPos = 0;

var table = buildTable(search);

var buffer = [], bufferLen = 0, bufferStart = 0,

outputBuffer = [], chunkLength = 0;

// Flush up to the current matchStart (match start is relative to the start

// of the current chunk so it's negative counting from the end of the

// buffer)

function flush(writeTo) {

var outputTo = bufferLen + matchStart - chunkLength;

while (outputTo > 0 && outputTo > bufferStart) {

if (outputTo > buffer[0].length-1) {

var part = buffer.shift();

outputBuffer.push(part.slice(bufferStart));

bufferStart = Math.max(0, bufferStart - part.length);

bufferLen -= part.length;

outputTo -= part.length;

} else {

outputBuffer.push(buffer[0].slice(bufferStart, outputTo));

bufferStart = outputTo;

break;

}

}

if (writeTo) {

// Output everything ready as one chunk

writeTo.push(outputBuffer.join(''));

outputBuffer.length = 0;

}

}

return through2(

function (chunk, enc, callback) {

chunk = decoder.write(chunk);

chunkLength = chunk.length;

buffer.push(chunk);

bufferLen += chunkLength;

while (matchStart + matchPos < chunkLength) {

if (search[matchPos] === chunk[matchStart+matchPos]) {

matchPos++;

if (matchPos === search.length) {

// FOUND IT

flush();

outputBuffer.push(replace);

bufferStart += matchPos;

matchStart = matchPos + matchStart;

matchPos = 0;

}

} else if (table[matchPos] === -1) {

// Failed on the first first char of search

matchPos = 0;

matchStart++;

} else {

matchPos = table[matchPos];

matchStart += matchPos - table[matchPos];

}

}

flush(this);

// Adjust the matchStart so it'll be relative to the start of the next

// chunk

matchStart = matchStart - chunkLength;

callback();

},

function (callback) {

matchStart = 0;

chunkLength = 0;

flush(this);

callback();

}

);

}

// Export for testing

module.exports._buildTable = buildTable;