stringutil.go 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. /*
  10. Package stringutil contains common function for string operations.
  11. */
  12. package stringutil
  13. import (
  14. "bytes"
  15. "crypto/md5"
  16. "encoding/json"
  17. "fmt"
  18. "regexp"
  19. "sort"
  20. "strconv"
  21. "strings"
  22. "unicode/utf8"
  23. )
  24. /*
  25. LongestCommonPrefix determines the longest common prefix of a given list of strings.
  26. */
  27. func LongestCommonPrefix(s []string) string {
  28. var res string
  29. commonPrefix := func(str1, str2 string) string {
  30. var buf bytes.Buffer
  31. rs2 := StringToRuneSlice(str2)
  32. rs2len := len(rs2)
  33. for i, c := range str1 {
  34. if i >= rs2len {
  35. break
  36. } else if c == rs2[i] {
  37. buf.WriteRune(c)
  38. }
  39. }
  40. return buf.String()
  41. }
  42. lens := len(s)
  43. if lens > 0 {
  44. res = s[0]
  45. for i := 1; i < lens; i++ {
  46. res = commonPrefix(res, s[i])
  47. }
  48. }
  49. return res
  50. }
  51. /*
  52. PrintStringTable prints a given list of strings as table with c columns.
  53. */
  54. func PrintStringTable(ss []string, c int) string {
  55. var ret bytes.Buffer
  56. if c < 1 {
  57. return ""
  58. }
  59. // Determine max widths of columns
  60. maxWidths := make(map[int]int)
  61. for i, s := range ss {
  62. col := i % c
  63. if l := utf8.RuneCountInString(s); l > maxWidths[col] {
  64. maxWidths[col] = l
  65. }
  66. }
  67. for i, s := range ss {
  68. col := i % c
  69. if i < len(ss)-1 {
  70. var formatString string
  71. if col != c-1 {
  72. formatString = fmt.Sprintf("%%-%vv ", maxWidths[col])
  73. } else {
  74. formatString = "%v"
  75. }
  76. ret.WriteString(fmt.Sprintf(formatString, s))
  77. } else {
  78. ret.WriteString(fmt.Sprintln(s))
  79. break
  80. }
  81. if col == c-1 {
  82. ret.WriteString(fmt.Sprintln())
  83. }
  84. }
  85. return ret.String()
  86. }
  87. /*
  88. GraphicStringTableSymbols defines how to draw a graphic table.
  89. */
  90. type GraphicStringTableSymbols struct {
  91. BoxHorizontal string
  92. BoxVertical string
  93. BoxMiddle string
  94. BoxCornerTopLeft string
  95. BoxCornerTopRight string
  96. BoxCornerBottomLeft string
  97. BoxCornerBottomRight string
  98. BoxTopMiddle string
  99. BoxLeftMiddle string
  100. BoxRightMiddle string
  101. BoxBottomMiddle string
  102. }
  103. /*
  104. Standard graphic table drawing definitions.
  105. */
  106. var (
  107. SingleLineTable = &GraphicStringTableSymbols{"─", "│", "┼", "┌", "┐", "└", "┘", "┬", "├", "┤", "┴"}
  108. DoubleLineTable = &GraphicStringTableSymbols{"═", "║", "╬", "╔", "╗", "╚", "╝", "╦", "╠", "╣", "╩"}
  109. SingleDoubleLineTable = &GraphicStringTableSymbols{"═", "│", "╪", "╒", "╕", "╘", "╛", "╤", "╞", "╡", "╧"}
  110. DoubleSingleLineTable = &GraphicStringTableSymbols{"─", "║", "╫", "╓", "╖", "╙", "╜", "╥", "╟", "╢", "╨"}
  111. MonoTable = &GraphicStringTableSymbols{"#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#"}
  112. )
  113. /*
  114. PrintGraphicStringTable prints a given list of strings in a graphic table
  115. with c columns - creates a header after n rows using syms as drawing symbols.
  116. */
  117. func PrintGraphicStringTable(ss []string, c int, n int, syms *GraphicStringTableSymbols) string {
  118. var topline, bottomline, middleline, ret bytes.Buffer
  119. if c < 1 {
  120. return ""
  121. }
  122. if syms == nil {
  123. syms = MonoTable
  124. }
  125. // Determine max widths of columns
  126. maxWidths := make(map[int]int)
  127. for i, s := range ss {
  128. col := i % c
  129. l := utf8.RuneCountInString(s)
  130. if l > maxWidths[col] {
  131. maxWidths[col] = l
  132. }
  133. }
  134. // Determine total width and create top, middle and bottom line
  135. totalWidth := 1
  136. topline.WriteString(syms.BoxCornerTopLeft)
  137. bottomline.WriteString(syms.BoxCornerBottomLeft)
  138. middleline.WriteString(syms.BoxLeftMiddle)
  139. for i := 0; i < len(maxWidths); i++ {
  140. totalWidth += maxWidths[i] + 2
  141. topline.WriteString(GenerateRollingString(syms.BoxHorizontal, maxWidths[i]+1))
  142. bottomline.WriteString(GenerateRollingString(syms.BoxHorizontal, maxWidths[i]+1))
  143. middleline.WriteString(GenerateRollingString(syms.BoxHorizontal, maxWidths[i]+1))
  144. if i < len(maxWidths)-1 {
  145. topline.WriteString(syms.BoxTopMiddle)
  146. bottomline.WriteString(syms.BoxBottomMiddle)
  147. middleline.WriteString(syms.BoxMiddle)
  148. }
  149. }
  150. topline.WriteString(syms.BoxCornerTopRight)
  151. bottomline.WriteString(syms.BoxCornerBottomRight)
  152. middleline.WriteString(syms.BoxRightMiddle)
  153. // Draw the table
  154. ret.WriteString(topline.String())
  155. ret.WriteString(fmt.Sprintln())
  156. row := 0
  157. for i, s := range ss {
  158. col := i % c
  159. ret.WriteString(syms.BoxVertical)
  160. if i < len(ss)-1 {
  161. formatString := fmt.Sprintf("%%-%vv ", maxWidths[col])
  162. ret.WriteString(fmt.Sprintf(formatString, s))
  163. } else {
  164. formatString := fmt.Sprintf("%%-%vv ", maxWidths[col])
  165. ret.WriteString(fmt.Sprintf(formatString, s))
  166. for col < c-1 && col < len(ss)-1 {
  167. col++
  168. ret.WriteString(syms.BoxVertical)
  169. ret.WriteString(GenerateRollingString(" ", maxWidths[col]))
  170. ret.WriteString(" ")
  171. }
  172. ret.WriteString(syms.BoxVertical)
  173. ret.WriteString(fmt.Sprintln())
  174. break
  175. }
  176. if col == c-1 {
  177. ret.WriteString(syms.BoxVertical)
  178. ret.WriteString(fmt.Sprintln())
  179. row++
  180. if row == n {
  181. ret.WriteString(middleline.String())
  182. ret.WriteString(fmt.Sprintln())
  183. }
  184. }
  185. }
  186. ret.WriteString(bottomline.String())
  187. ret.WriteString(fmt.Sprintln())
  188. return ret.String()
  189. }
  190. /*
  191. PrintCSVTable prints a given list of strings in a CSV table with c
  192. columns.
  193. */
  194. func PrintCSVTable(ss []string, c int) string {
  195. var ret bytes.Buffer
  196. var col int
  197. if c < 1 || len(ss) == 0 {
  198. return ""
  199. }
  200. // Write the table
  201. for i, s := range ss {
  202. col = i % c
  203. ret.WriteString(strings.TrimSpace(fmt.Sprint(s)))
  204. if col == c-1 {
  205. ret.WriteString(fmt.Sprintln())
  206. } else if i < len(ss)-1 {
  207. ret.WriteString(", ")
  208. }
  209. }
  210. if col != c-1 {
  211. ret.WriteString(fmt.Sprintln())
  212. }
  213. return ret.String()
  214. }
  215. /*
  216. RuneSliceToString converts a slice of runes into a string.
  217. */
  218. func RuneSliceToString(buf []rune) string {
  219. var sbuf bytes.Buffer
  220. for _, r := range buf {
  221. fmt.Fprintf(&sbuf, "%c", r)
  222. }
  223. return sbuf.String()
  224. }
  225. /*
  226. StringToRuneSlice converts a string into a slice of runes.
  227. */
  228. func StringToRuneSlice(s string) []rune {
  229. var buf []rune
  230. for _, r := range s {
  231. buf = append(buf, r)
  232. }
  233. return buf
  234. }
  235. /*
  236. Plural returns the string 's' if the parameter is greater than one or
  237. if the parameter is 0.
  238. */
  239. func Plural(l int) string {
  240. if l > 1 || l == 0 {
  241. return "s"
  242. }
  243. return ""
  244. }
  245. /*
  246. GlobParseError describes a failure to parse a glob expression
  247. and gives the offending expression.
  248. */
  249. type GlobParseError struct {
  250. Msg string
  251. Pos int
  252. Glob string
  253. }
  254. /*
  255. Error Returns a string representation of the error.
  256. */
  257. func (e *GlobParseError) Error() string {
  258. return fmt.Sprintf("%s at %d of %s", e.Msg, e.Pos, e.Glob)
  259. }
  260. /*
  261. GlobToRegex converts a given glob expression into a regular expression.
  262. */
  263. func GlobToRegex(glob string) (string, error) {
  264. buf := new(bytes.Buffer)
  265. brackets, braces := 0, 0
  266. n := len(glob)
  267. for i := 0; i < n; i++ {
  268. char := glob[i]
  269. switch char {
  270. case '\\':
  271. // Escapes
  272. i++
  273. if i >= n {
  274. return "", &GlobParseError{"Missing escaped character", i, glob}
  275. }
  276. buf.WriteByte(char)
  277. buf.WriteByte(glob[i])
  278. continue
  279. case '*':
  280. // Wildcard match multiple characters
  281. buf.WriteByte('.')
  282. case '?':
  283. // Wildcard match any single character
  284. buf.WriteByte('.')
  285. continue
  286. case '{':
  287. // Group (always non-capturing)
  288. buf.WriteString("(?:")
  289. braces++
  290. continue
  291. case '}':
  292. // End of group
  293. if braces > 0 {
  294. braces--
  295. buf.WriteByte(')')
  296. continue
  297. }
  298. case '[':
  299. // Character class
  300. if brackets > 0 {
  301. return "", &GlobParseError{"Unclosed character class", i, glob}
  302. }
  303. brackets++
  304. case ']':
  305. // End of character class
  306. brackets = 0
  307. case ',':
  308. // OR in groups
  309. if braces > 0 {
  310. buf.WriteByte('|')
  311. } else {
  312. buf.WriteByte(char)
  313. }
  314. continue
  315. case '^':
  316. // Beginning of line in character classes otherwise normal
  317. // escaped character
  318. if brackets == 0 {
  319. buf.WriteByte('\\')
  320. }
  321. case '!':
  322. // [! is the equivalent of [^ in glob
  323. if brackets > 0 && glob[i-1] == '[' {
  324. buf.WriteByte('^')
  325. } else {
  326. buf.WriteByte('!')
  327. }
  328. continue
  329. case '.', '$', '(', ')', '|', '+':
  330. // Escape all regex characters which are not glob characters
  331. buf.WriteByte('\\')
  332. }
  333. buf.WriteByte(char)
  334. }
  335. if brackets > 0 {
  336. return "", &GlobParseError{"Unclosed character class", n, glob}
  337. } else if braces > 0 {
  338. return "", &GlobParseError{"Unclosed group", n, glob}
  339. }
  340. return buf.String(), nil
  341. }
  342. /*
  343. GlobStartingLiterals gets the first literals of a glob string.
  344. */
  345. func GlobStartingLiterals(glob string) string {
  346. buf := new(bytes.Buffer)
  347. n := len(glob)
  348. for i := 0; i < n; i++ {
  349. char := glob[i]
  350. if char == '\\' || char == '*' || char == '?' ||
  351. char == '{' || char == '[' {
  352. break
  353. }
  354. buf.WriteByte(char)
  355. }
  356. return buf.String()
  357. }
  358. /*
  359. LevenshteinDistance computes the Levenshtein distance between two strings.
  360. */
  361. func LevenshteinDistance(str1, str2 string) int {
  362. if str1 == str2 {
  363. return 0
  364. }
  365. rslice1 := StringToRuneSlice(str1)
  366. rslice2 := StringToRuneSlice(str2)
  367. n, m := len(rslice1), len(rslice2)
  368. if n == 0 {
  369. return m
  370. } else if m == 0 {
  371. return n
  372. }
  373. v0 := make([]int, m+1, m+1)
  374. v1 := make([]int, m+1, m+1)
  375. for i := 0; i <= m; i++ {
  376. v0[i] = i
  377. }
  378. var cost int
  379. for i := 0; i < n; i++ {
  380. v1[0] = i + 1
  381. for j := 0; j < m; j++ {
  382. if rslice1[i] == rslice2[j] {
  383. cost = 0
  384. } else {
  385. cost = 1
  386. }
  387. v1[j+1] = min3(v1[j]+1, v0[j+1]+1, v0[j]+cost)
  388. }
  389. v0, v1 = v1, v0
  390. }
  391. return v0[m]
  392. }
  393. /*
  394. 3 way min for computing the Levenshtein distance.
  395. */
  396. func min3(a, b, c int) int {
  397. ret := a
  398. if b < ret {
  399. ret = b
  400. }
  401. if c < ret {
  402. ret = c
  403. }
  404. return ret
  405. }
  406. /*
  407. VersionStringCompare compares two version strings. Returns: 0 if the strings are
  408. equal; -1 if the first string is smaller; 1 if the first string is greater.
  409. */
  410. func VersionStringCompare(str1, str2 string) int {
  411. val1 := strings.Split(str1, ".")
  412. val2 := strings.Split(str2, ".")
  413. idx := 0
  414. for idx < len(val1) && idx < len(val2) && val1[idx] == val2[idx] {
  415. idx++
  416. }
  417. switch {
  418. case idx < len(val1) && idx < len(val2):
  419. return versionStringPartCompare(val1[idx], val2[idx])
  420. case len(val1) > len(val2):
  421. return 1
  422. case len(val1) < len(val2):
  423. return -1
  424. }
  425. return 0
  426. }
  427. /*
  428. versionStringPartCompare compares two version string parts. Returns: 0 if the
  429. strings are equal; -1 if the first string is smaller; 1 if the first string is
  430. greater.
  431. */
  432. func versionStringPartCompare(str1, str2 string) int {
  433. pat := regexp.MustCompile("^([0-9]+)([\\D].*)?")
  434. res1 := pat.FindStringSubmatch(str1)
  435. res2 := pat.FindStringSubmatch(str2)
  436. switch {
  437. case res1 == nil && res2 == nil:
  438. return strings.Compare(str1, str2)
  439. case res1 == nil && res2 != nil:
  440. return -1
  441. case res1 != nil && res2 == nil:
  442. return 1
  443. }
  444. v1, _ := strconv.Atoi(res1[1])
  445. v2, _ := strconv.Atoi(res2[1])
  446. res := 0
  447. switch {
  448. case v1 > v2:
  449. res = 1
  450. case v1 < v2:
  451. res = -1
  452. }
  453. if res == 0 {
  454. switch {
  455. case res1[2] != "" && res2[2] == "":
  456. return 1
  457. case res1[2] == "" && res2[2] != "":
  458. return -1
  459. case res1[2] != "" && res2[2] != "":
  460. return strings.Compare(res1[2], res2[2])
  461. }
  462. }
  463. return res
  464. }
  465. /*
  466. IsAlphaNumeric checks if a string contains only alpha numerical characters or "_".
  467. */
  468. func IsAlphaNumeric(str string) bool {
  469. ret, _ := regexp.MatchString("^[a-zA-Z0-9_]*$", str)
  470. return ret
  471. }
  472. /*
  473. IsTrueValue checks if a given string is a true value.
  474. */
  475. func IsTrueValue(str string) bool {
  476. str = strings.ToLower(str)
  477. return str == "true" || str == "yes" || str == "on" || str == "ok" ||
  478. str == "1" || str == "active" || str == "enabled"
  479. }
  480. /*
  481. IndexOf returns the index of str in slice or -1 if it does not exist.
  482. */
  483. func IndexOf(str string, slice []string) int {
  484. for i, s := range slice {
  485. if str == s {
  486. return i
  487. }
  488. }
  489. return -1
  490. }
  491. /*
  492. MapKeys returns the keys of a map as a sorted list.
  493. */
  494. func MapKeys(m map[string]interface{}) []string {
  495. ret := make([]string, 0, len(m))
  496. for k := range m {
  497. ret = append(ret, k)
  498. }
  499. sort.Strings(ret)
  500. return ret
  501. }
  502. /*
  503. GenerateRollingString creates a string by repeating a given string pattern.
  504. */
  505. func GenerateRollingString(seq string, size int) string {
  506. var buf bytes.Buffer
  507. rs := StringToRuneSlice(seq)
  508. l := len(rs)
  509. if l == 0 {
  510. return ""
  511. }
  512. for i := 0; i < size; i++ {
  513. buf.WriteRune(rs[i%l])
  514. }
  515. return buf.String()
  516. }
  517. /*
  518. ConvertToString tries to convert a given object into a stable string. This
  519. function can be used to display nested maps.
  520. */
  521. func ConvertToString(v interface{}) string {
  522. if vStringer, ok := v.(fmt.Stringer); ok {
  523. return vStringer.String()
  524. }
  525. if _, err := json.Marshal(v); err != nil {
  526. v = containerStringConvert(v)
  527. }
  528. if vString, ok := v.(string); ok {
  529. return vString
  530. } else if res, err := json.Marshal(v); err == nil {
  531. return string(res)
  532. }
  533. return fmt.Sprint(v)
  534. }
  535. /*
  536. ConvertToPrettyString tries to convert a given object into a stable human-readable
  537. string.
  538. */
  539. func ConvertToPrettyString(v interface{}) string {
  540. var res []byte
  541. var err error
  542. if res, err = json.MarshalIndent(v, "", " "); err != nil {
  543. if res, err = json.MarshalIndent(containerStringConvert(v), "", " "); err != nil {
  544. res = []byte(fmt.Sprint(v))
  545. }
  546. }
  547. return string(res)
  548. }
  549. /*
  550. containerStringConvert converts container contents into strings.
  551. */
  552. func containerStringConvert(v interface{}) interface{} {
  553. res := v
  554. if mapContainer, ok := v.(map[interface{}]interface{}); ok {
  555. newRes := make(map[string]interface{})
  556. for mk, mv := range mapContainer {
  557. newRes[ConvertToString(mk)] = containerStringConvert(mv)
  558. }
  559. res = newRes
  560. } else if mapList, ok := v.([]interface{}); ok {
  561. newRes := make([]interface{}, len(mapList))
  562. for i, lv := range mapList {
  563. newRes[i] = containerStringConvert(lv)
  564. }
  565. res = newRes
  566. }
  567. return res
  568. }
  569. /*
  570. MD5HexString calculates the MD5 sum of a string and returns it as hex string.
  571. */
  572. func MD5HexString(str string) string {
  573. return fmt.Sprintf("%x", md5.Sum([]byte(str)))
  574. }
  575. /*
  576. LengthConstantEquals compares two strings in length-constant time. This
  577. function is deliberately inefficient in that it does not stop at the earliest
  578. possible time. This is to prevent timing attacks when comparing password
  579. hashes.
  580. */
  581. func LengthConstantEquals(str1 []byte, str2 []byte) bool {
  582. diff := len(str1) ^ len(str2)
  583. for i := 0; i < len(str1) && i < len(str2); i++ {
  584. diff |= int(str1[i] ^ str2[i])
  585. }
  586. return diff == 0
  587. }