} if (end > target_len) { end = target_len; } else if (end < 0) { end += target_len; if (end < 0) end = 0; } /* zero-length substrings always match at the first attempt */ if (pattern_len == 0) return (direction > 0) ? start : end; end -= pattern_len; if (direction < 0) { for (; end >= start; end--) if (Py_STRING_MATCH(target, end, pattern, pattern_len)) return end; } else { for (; start <= end; start++) if (Py_STRING_MATCH(target, start, pattern, pattern_len)) return start; } return -1;} Py_LOCAL_INLINE(Py_ssize_t)countstring(const char *target, Py_ssize_t target_len, const char *pattern, Py_ssize_t pattern_len, Py_ssize_t start, Py_ssize_t end, int direction, Py_ssize_t maxcount){ Py_ssize_t count=0; if (start < 0) { start += target_len; if (start < 0) start = 0; } if (end > target_len) { end = target_len; } else if (end < 0) { end += target_len; if (end < 0) end = 0; } /* zero-length substrings match everywhere */ if (pattern_len == 0 || maxcount == 0) { if (target_len+1 < maxcount) return target_len+1; return maxcount; } end -= pattern_len; if (direction < 0) { for (; (end >= start); end--) if (Py_STRING_MATCH(target, end, pattern, pattern_len)) { count++; if (--maxcount <= 0) break; end -= pattern_len-1; } } else { for (; (start <= end); start++) if (Py_STRING_MATCH(target, start, pattern, pattern_len)) { count++; if (--maxcount <= 0) break; start += pattern_len-1; } } return count;} /* Algorithms for different cases of string replacement */ /* len(self)>=1, from="", len(to)>=1, maxcount>=1 */Py_LOCAL(PyStringObject *)replace_interleave(PyStringObject *self, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount){ char *self_s, *result_s; Py_ssize_t self_len, result_len; Py_ssize_t count, i, product; PyStringObject *result; self_len = PyString_GET_SIZE(self); /* 1 at the end plus 1 after every character */ count = self_len+1; if (maxcount < count) count = maxcount; /* Check for overflow */ /* result_len = count * to_len + self_len; */ product = count * to_len; if (product / to_len != count) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } result_len = product + self_len; if (result_len < 0) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } if (! (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) ) return NULL; self_s = PyString_AS_STRING(self); result_s = PyString_AS_STRING(result); /* TODO: special case single character, which doesn't need memcpy */ /* Lay the first one down (guaranteed this will occur) */ Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; count -= 1; for (i=0; i<count; i++) { *result_s++ = *self_s++; Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; } /* Copy the rest of the original string */ Py_MEMCPY(result_s, self_s, self_len-i); return result;} /* Special case for deleting a single character *//* len(self)>=1, len(from)==1, to="", maxcount>=1 */Py_LOCAL(PyStringObject *)replace_delete_single_character(PyStringObject *self, char from_c, Py_ssize_t maxcount){ char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count; PyStringObject *result; self_len = PyString_GET_SIZE(self); self_s = PyString_AS_STRING(self); count = countchar(self_s, self_len, from_c, maxcount); if (count == 0) { return return_self(self); } result_len = self_len - count; /* from_len == 1 */ assert(result_len>=0); if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { next = findchar(start, end-start, from_c); if (next == NULL) break; Py_MEMCPY(result_s, start, next-start); result_s += (next-start); start = next+1; } Py_MEMCPY(result_s, start, end-start); return result;} /* len(self)>=1, len(from)>=2, to="", maxcount>=1 */ Py_LOCAL(PyStringObject *)replace_delete_substring(PyStringObject *self, const char *from_s, Py_ssize_t from_len, Py_ssize_t maxcount) { char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count, offset; PyStringObject *result; self_len = PyString_GET_SIZE(self); self_s = PyString_AS_STRING(self); count = countstring(self_s, self_len, from_s, from_len, 0, self_len, 1, maxcount); if (count == 0) { /* no matches */ return return_self(self); } result_len = self_len - (count * from_len); assert (result_len>=0); if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL ) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { offset = findstring(start, end-start, from_s, from_len, 0, end-start, FORWARD); if (offset == -1) break; next = start + offset; Py_MEMCPY(result_s, start, next-start); result_s += (next-start); start = next+from_len; } Py_MEMCPY(result_s, start, end-start); return result;} /* len(self)>=1, len(from)==len(to)==1, maxcount>=1 */Py_LOCAL(PyStringObject *)replace_single_character_in_place(PyStringObject *self, char from_c, char to_c, Py_ssize_t maxcount){ char *self_s, *result_s, *start, *end, *next; Py_ssize_t self_len; PyStringObject *result; /* The result string will be the same size */ self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); next = findchar(self_s, self_len, from_c); if (next == NULL) { /* No matches; return the original string */ return return_self(self); } /* Need to make a new string */ result = (PyStringObject *) PyString_FromStringAndSize(NULL, self_len); if (result == NULL) return NULL; result_s = PyString_AS_STRING(result); Py_MEMCPY(result_s, self_s, self_len); /* change everything in-place, starting with this one */ start = result_s + (next-self_s); *start = to_c; start++; end = result_s + self_len; while (--maxcount > 0) { next = findchar(start, end-start, from_c); if (next == NULL) break; *next = to_c; start = next+1; } return result;} /* len(self)>=1, len(from)==len(to)>=2, maxcount>=1 */Py_LOCAL(PyStringObject *)replace_substring_in_place(PyStringObject *self, const char *from_s, Py_ssize_t from_len, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount){ char *result_s, *start, *end; char *self_s; Py_ssize_t self_len, offset; PyStringObject *result; /* The result string will be the same size */ self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); offset = findstring(self_s, self_len, from_s, from_len, 0, self_len, FORWARD); if (offset == -1) { /* No matches; return the original string */ return return_self(self); } /* Need to make a new string */ result = (PyStringObject *) PyString_FromStringAndSize(NULL, self_len); if (result == NULL) return NULL; result_s = PyString_AS_STRING(result); Py_MEMCPY(result_s, self_s, self_len); /* change everything in-place, starting with this one */ start = result_s + offset; Py_MEMCPY(start, to_s, from_len); start += from_len; end = result_s + self_len; while ( --maxcount > 0) { offset = findstring(start, end-start, from_s, from_len, 0, end-start, FORWARD); if (offset==-1) break; Py_MEMCPY(start+offset, to_s, from_len); start += offset+from_len; } return result;} /* len(self)>=1, len(from)==1, len(to)>=2, maxcount>=1 */Py_LOCAL(PyStringObject *)replace_single_character(PyStringObject *self, char from_c, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount){ char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count, product; PyStringObject *result; self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); count = countchar(self_s, self_len, from_c, maxcount); if (count == 0) { /* no matches, return unchanged */ return return_self(self); } /* use the difference between current and new, hence the "-1" */ /* result_len = self_len + count * (to_len-1) */ product = count * (to_len-1); if (product / (to_len-1) != count) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } result_len = self_len + product; if (result_len < 0) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { next = findchar(start, end-start, from_c); if (next == NULL) break; if (next == start) { /* replace with the 'to' */ Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start += 1; } else { /* copy the unchanged old then the 'to' */ Py_MEMCPY(result_s, start, next-start); result_s += (next-start); Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start = next+1; } } /* Copy the remainder of the remaining string */ Py_MEMCPY(result_s, start, end-start); return result;} /* len(self)>=1, len(from)>=2, len(to)>=2, maxcount>=1 */Py_LOCAL(PyStringObject *)replace_substring(PyStringObject *self, const char *from_s, Py_ssize_t from_len, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount) { char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count, offset, product; PyStringObject *result; self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); count = countstring(self_s, self_len, from_s, from_len, 0, self_len, FORWARD, maxcount); if (count == 0) { /* no matches, return unchanged */ return return_self(self); } /* Check for overflow */ /* result_len = self_len + count * (to_len-from_len) */ product = count * (to_len-from_len); if (product / (to_len-from_len) != count) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } result_len = self_len + product; if (result_len < 0) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { offset = findstring(start, end-start, from_s, from_len, 0, end-start, FORWARD); if (offset == -1) break; next = start+offset; if (next == start) { /* replace with the 'to' */ Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start += from_len; } else { /* copy the unchanged old then the 'to' */ Py_MEMCPY(result_s, start, next-start); result_s += (next-start); Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start = next+from_len; } } /* Copy the remainder of the remaining string */ Py_MEMCPY(result_s, start, end-start); return result;} Py_LOCAL(PyStringObject *)replace(PyStringObject *self, const char *from_s, Py_ssize_t from_len, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount){ if (maxcount < 0) { maxcount = PY_SSIZE_T_MAX; } else if (maxcount == 0 || PyString_GET_SIZE(self) == 0) { /* nothing to do; return the original string */ return return_self(self); } if (maxcount == 0 || (from_len == 0 && to_len == 0)) { /* nothing to do; return the original string */ return return_self(self); } /* Handle zero-length special cases */ if (from_len == 0) { /* insert the 'to' string everywhere. */ /* >>> "Python".replace("", ".") */ /* '.P.y.t.h.o.n.' */ return replace_interleave(self, to_s, to_len, maxcount); } /* Except for "".replace("", "A") == "A" there is no way beyond this */ /* point for an empty self string to generate a non-empty string */ /* Special case so the remaining code always gets a non-empty string */ if (PyString_GET_SIZE(self) == 0) {Lines 2501–3000 of 5009. Previous lines Load more
} if (end > target_len) { end = target_len; } else if (end < 0) { end += target_len; if (end < 0) end = 0; } /* zero-length substrings always match at the first attempt */ if (pattern_len == 0) return (direction > 0) ? start : end; end -= pattern_len; if (direction < 0) { for (; end >= start; end--) if (Py_STRING_MATCH(target, end, pattern, pattern_len)) return end; } else { for (; start <= end; start++) if (Py_STRING_MATCH(target, start, pattern, pattern_len)) return start; } return -1; } Py_LOCAL_INLINE(Py_ssize_t) countstring(const char *target, Py_ssize_t target_len, const char *pattern, Py_ssize_t pattern_len, Py_ssize_t start, Py_ssize_t end, int direction, Py_ssize_t maxcount) { Py_ssize_t count=0; if (start < 0) { start += target_len; if (start < 0) start = 0; } if (end > target_len) { end = target_len; } else if (end < 0) { end += target_len; if (end < 0) end = 0; } /* zero-length substrings match everywhere */ if (pattern_len == 0 || maxcount == 0) { if (target_len+1 < maxcount) return target_len+1; return maxcount; } end -= pattern_len; if (direction < 0) { for (; (end >= start); end--) if (Py_STRING_MATCH(target, end, pattern, pattern_len)) { count++; if (--maxcount <= 0) break; end -= pattern_len-1; } } else { for (; (start <= end); start++) if (Py_STRING_MATCH(target, start, pattern, pattern_len)) { count++; if (--maxcount <= 0) break; start += pattern_len-1; } } return count; } /* Algorithms for different cases of string replacement */ /* len(self)>=1, from="", len(to)>=1, maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_interleave(PyStringObject *self, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount) { char *self_s, *result_s; Py_ssize_t self_len, result_len; Py_ssize_t count, i, product; PyStringObject *result; self_len = PyString_GET_SIZE(self); /* 1 at the end plus 1 after every character */ count = self_len+1; if (maxcount < count) count = maxcount; /* Check for overflow */ /* result_len = count * to_len + self_len; */ product = count * to_len; if (product / to_len != count) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } result_len = product + self_len; if (result_len < 0) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } if (! (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) ) return NULL; self_s = PyString_AS_STRING(self); result_s = PyString_AS_STRING(result); /* TODO: special case single character, which doesn't need memcpy */ /* Lay the first one down (guaranteed this will occur) */ Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; count -= 1; for (i=0; i<count; i++) { *result_s++ = *self_s++; Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; } /* Copy the rest of the original string */ Py_MEMCPY(result_s, self_s, self_len-i); return result; } /* Special case for deleting a single character */ /* len(self)>=1, len(from)==1, to="", maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_delete_single_character(PyStringObject *self, char from_c, Py_ssize_t maxcount) { char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count; PyStringObject *result; self_len = PyString_GET_SIZE(self); self_s = PyString_AS_STRING(self); count = countchar(self_s, self_len, from_c, maxcount); if (count == 0) { return return_self(self); } result_len = self_len - count; /* from_len == 1 */ assert(result_len>=0); if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { next = findchar(start, end-start, from_c); if (next == NULL) break; Py_MEMCPY(result_s, start, next-start); result_s += (next-start); start = next+1; } Py_MEMCPY(result_s, start, end-start); return result; } /* len(self)>=1, len(from)>=2, to="", maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_delete_substring(PyStringObject *self, const char *from_s, Py_ssize_t from_len, Py_ssize_t maxcount) { char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count, offset; PyStringObject *result; self_len = PyString_GET_SIZE(self); self_s = PyString_AS_STRING(self); count = countstring(self_s, self_len, from_s, from_len, 0, self_len, 1, maxcount); if (count == 0) { /* no matches */ return return_self(self); } result_len = self_len - (count * from_len); assert (result_len>=0); if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL ) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { offset = findstring(start, end-start, from_s, from_len, 0, end-start, FORWARD); if (offset == -1) break; next = start + offset; Py_MEMCPY(result_s, start, next-start); result_s += (next-start); start = next+from_len; } Py_MEMCPY(result_s, start, end-start); return result; } /* len(self)>=1, len(from)==len(to)==1, maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_single_character_in_place(PyStringObject *self, char from_c, char to_c, Py_ssize_t maxcount) { char *self_s, *result_s, *start, *end, *next; Py_ssize_t self_len; PyStringObject *result; /* The result string will be the same size */ self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); next = findchar(self_s, self_len, from_c); if (next == NULL) { /* No matches; return the original string */ return return_self(self); } /* Need to make a new string */ result = (PyStringObject *) PyString_FromStringAndSize(NULL, self_len); if (result == NULL) return NULL; result_s = PyString_AS_STRING(result); Py_MEMCPY(result_s, self_s, self_len); /* change everything in-place, starting with this one */ start = result_s + (next-self_s); *start = to_c; start++; end = result_s + self_len; while (--maxcount > 0) { next = findchar(start, end-start, from_c); if (next == NULL) break; *next = to_c; start = next+1; } return result; } /* len(self)>=1, len(from)==len(to)>=2, maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_substring_in_place(PyStringObject *self, const char *from_s, Py_ssize_t from_len, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount) { char *result_s, *start, *end; char *self_s; Py_ssize_t self_len, offset; PyStringObject *result; /* The result string will be the same size */ self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); offset = findstring(self_s, self_len, from_s, from_len, 0, self_len, FORWARD); if (offset == -1) { /* No matches; return the original string */ return return_self(self); } /* Need to make a new string */ result = (PyStringObject *) PyString_FromStringAndSize(NULL, self_len); if (result == NULL) return NULL; result_s = PyString_AS_STRING(result); Py_MEMCPY(result_s, self_s, self_len); /* change everything in-place, starting with this one */ start = result_s + offset; Py_MEMCPY(start, to_s, from_len); start += from_len; end = result_s + self_len; while ( --maxcount > 0) { offset = findstring(start, end-start, from_s, from_len, 0, end-start, FORWARD); if (offset==-1) break; Py_MEMCPY(start+offset, to_s, from_len); start += offset+from_len; } return result; } /* len(self)>=1, len(from)==1, len(to)>=2, maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_single_character(PyStringObject *self, char from_c, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount) { char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count, product; PyStringObject *result; self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); count = countchar(self_s, self_len, from_c, maxcount); if (count == 0) { /* no matches, return unchanged */ return return_self(self); } /* use the difference between current and new, hence the "-1" */ /* result_len = self_len + count * (to_len-1) */ product = count * (to_len-1); if (product / (to_len-1) != count) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } result_len = self_len + product; if (result_len < 0) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { next = findchar(start, end-start, from_c); if (next == NULL) break; if (next == start) { /* replace with the 'to' */ Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start += 1; } else { /* copy the unchanged old then the 'to' */ Py_MEMCPY(result_s, start, next-start); result_s += (next-start); Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start = next+1; } } /* Copy the remainder of the remaining string */ Py_MEMCPY(result_s, start, end-start); return result; } /* len(self)>=1, len(from)>=2, len(to)>=2, maxcount>=1 */ Py_LOCAL(PyStringObject *) replace_substring(PyStringObject *self, const char *from_s, Py_ssize_t from_len, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount) { char *self_s, *result_s; char *start, *next, *end; Py_ssize_t self_len, result_len; Py_ssize_t count, offset, product; PyStringObject *result; self_s = PyString_AS_STRING(self); self_len = PyString_GET_SIZE(self); count = countstring(self_s, self_len, from_s, from_len, 0, self_len, FORWARD, maxcount); if (count == 0) { /* no matches, return unchanged */ return return_self(self); } /* Check for overflow */ /* result_len = self_len + count * (to_len-from_len) */ product = count * (to_len-from_len); if (product / (to_len-from_len) != count) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } result_len = self_len + product; if (result_len < 0) { PyErr_SetString(PyExc_OverflowError, "replace string is too long"); return NULL; } if ( (result = (PyStringObject *) PyString_FromStringAndSize(NULL, result_len)) == NULL) return NULL; result_s = PyString_AS_STRING(result); start = self_s; end = self_s + self_len; while (count-- > 0) { offset = findstring(start, end-start, from_s, from_len, 0, end-start, FORWARD); if (offset == -1) break; next = start+offset; if (next == start) { /* replace with the 'to' */ Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start += from_len; } else { /* copy the unchanged old then the 'to' */ Py_MEMCPY(result_s, start, next-start); result_s += (next-start); Py_MEMCPY(result_s, to_s, to_len); result_s += to_len; start = next+from_len; } } /* Copy the remainder of the remaining string */ Py_MEMCPY(result_s, start, end-start); return result; } Py_LOCAL(PyStringObject *) replace(PyStringObject *self, const char *from_s, Py_ssize_t from_len, const char *to_s, Py_ssize_t to_len, Py_ssize_t maxcount) { if (maxcount < 0) { maxcount = PY_SSIZE_T_MAX; } else if (maxcount == 0 || PyString_GET_SIZE(self) == 0) { /* nothing to do; return the original string */ return return_self(self); } if (maxcount == 0 || (from_len == 0 && to_len == 0)) { /* nothing to do; return the original string */ return return_self(self); } /* Handle zero-length special cases */ if (from_len == 0) { /* insert the 'to' string everywhere. */ /* >>> "Python".replace("", ".") */ /* '.P.y.t.h.o.n.' */ return replace_interleave(self, to_s, to_len, maxcount); } /* Except for "".replace("", "A") == "A" there is no way beyond this */ /* point for an empty self string to generate a non-empty string */ /* Special case so the remaining code always gets a non-empty string */ if (PyString_GET_SIZE(self) == 0) {