Repository: ast-grep/ast-grep (language: rust)

Issue:
[bug] ast-grep scan: special characters lead to different end columns
### Please read the FAQ for the bug you encountered.

- [X] I have read the existing FAQ

### ⏯ Playground Link

https://ast-grep.github.io/playground.html#eyJtb2RlIjoiQ29uZmlnIiwibGFuZyI6ImNwcCIsInF1ZXJ5IjoiY29uc29sZS5sb2coJE1BVENIKSIsInJld3JpdGUiOiJsb2dnZXIubG9nKCRNQVRDSCkiLCJzdHJpY3RuZXNzIjoic21hcnQiLCJzZWxlY3RvciI6IiIsImNvbmZpZyI6IiMgWUFNTCBSdWxlIGlzIG1vcmUgcG93ZXJmdWwhXG4jIGh0dHBzOi8vYXN0LWdyZXAuZ2l0aHViLmlvL2d1aWRlL3J1bGUtY29uZmlnLmh0bWwjcnVsZVxucnVsZTpcbiAga2luZDogY29tbWVudFxuICBwYXR0ZXJuOiAkQ09NTUVOVFxuICBhbGw6XG4gICAgLSByZWdleDogXCJUT0RPW146XXxGSVhNRVteOl1cIlxudHJhbnNmb3JtOlxuICBORVdfQ09NTUVOVDpcbiAgICByZXBsYWNlOlxuICAgICAgc291cmNlOiAkQ09NTUVOVFxuICAgICAgcmVwbGFjZTogKD88RklYPlRPRE98RklYTUUpXG4gICAgICBieTogXCIkRklYOlwiXG5maXg6ICRORVdfQ09NTUVOVCIsInNvdXJjZSI6IiAgLy8gIFRPRE8gdGVzdCBzdHVmZi4uLi4uXG4gIC8vICBUT0RPIHRlc3RlIMOcYmVyZ8OkbmdlIn0=

### 💻 Code

_No response_

### 🙁 Actual behavior

The playground example has two comments that are matched. In the playground, you can see that the end column is at 26 for both. When I run the rule with json output I get the following:
```
[
{
  "text": "//  TODO test stuff.....",
  "range": {
    "byteOffset": {
      "start": 2,
      "end": 26
    },
    "start": {
      "line": 0,
      "column": 2
    },
    "end": {
      "line": 0,
      "column": 26
    }
  },
  "file": "comment.cpp",
  "lines": "  //  TODO test stuff.....",
  "charCount": {
    "leading": 2,
    "trailing": 0
  },
  "replacement": "//  TODO: test stuff.....",
  "replacementOffsets": {
    "start": 2,
    "end": 26
  },
  "language": "Cpp",
  "metaVariables": {
    "single": {
      "COMMENT": {
        "text": "//  TODO test stuff.....",
        "range": {
          "byteOffset": {
            "start": 2,
            "end": 26
          },
          "start": {
            "line": 0,
            "column": 2
          },
          "end": {
            "line": 0,
            "column": 26
          }
        }
      }
    },
    "multi": {},
    "transformed": {
      "NEW_COMMENT": "//  TODO: test stuff....."
    }
  },
  "ruleId": "comment",
  "severity": "hint",
  "note": null,
  "message": ""
},
{
  "text": "//  TODO teste Übergänge",
  "range": {
    "byteOffset": {
      "start": 29,
      "end": 55
    },
    "start": {
      "line": 1,
      "column": 2
    },
    "end": {
      "line": 1,
      "column": 28
    }
  },
  "file": "comment.cpp",
  "lines": "  //  TODO teste Übergänge",
  "charCount": {
    "leading": 2,
    "trailing": 0
  },
  "replacement": "//  TODO: teste Übergänge",
  "replacementOffsets": {
    "start": 29,
    "end": 55
  },
  "language": "Cpp",
  "metaVariables": {
    "single": {
      "COMMENT": {
        "text": "//  TODO teste Übergänge",
        "range": {
          "byteOffset": {
            "start": 29,
            "end": 55
          },
          "start": {
            "line": 1,
            "column": 2
          },
          "end": {
            "line": 1,
            "column": 28
          }
        }
      }
    },
    "multi": {},
    "transformed": {
      "NEW_COMMENT": "//  TODO: teste Übergänge"
    }
  },
  "ruleId": "comment",
  "severity": "hint",
  "note": null,
  "message": ""
}
]
```

Although both comment matches have the end column 26, ast-grep scan reports end column 28 for the comment with special characters.

### 🙂 Expected behavior

Ast-grep scan should report the actual end column.

### Additional information about the issue

_No response_


Discussion / hints:
This is because `ts_node_start_point` returns zero-based byte offset column.

Using tree-sitter-json as an example, the test case

```json
"Übergänge"
```

returns the `string_content` ending at 12

<img width="502" alt="image" src="https://github.com/user-attachments/assets/fa2625e0-3b47-4eea-a2b9-0e43cea89299">


In contrast, the tree-sitter web returns ending column 10

<img width="434" alt="image" src="https://github.com/user-attachments/assets/e3ac1275-38e8-4efe-be5f-b190ba4407b4">


Also see 

https://github.com/tree-sitter/tree-sitter/issues/1727
https://github.com/tree-sitter/tree-sitter/pull/1581#issuecomment-1010512449
https://github.com/tree-sitter/tree-sitter/issues/2946
I don't think upstream tree-sitter will fix this in the core lib in the near future. See

https://github.com/tree-sitter/tree-sitter/pull/3610/files

Fix patch:
diff --git a/crates/core/src/node.rs b/crates/core/src/node.rs
index a0953e7bab..bd3737f6cd 100644
--- a/crates/core/src/node.rs
+++ b/crates/core/src/node.rs
@@ -19,21 +19,25 @@ pub struct Position {
   row: usize,
   /// zero-based BYTE offset instead of character offset
   byte_column: usize,
+  /// byte offset of this position
+  byte_offset: usize,
 }
 
 impl Position {
-  fn new(row: u32, byte_column: u32) -> Self {
+  fn new(row: u32, byte_column: u32, byte_offset: u32) -> Self {
     Self {
       row: row as usize,
       byte_column: byte_column as usize,
+      byte_offset: byte_offset as usize,
     }
   }
   pub fn row(&self) -> usize {
     self.row
   }
   /// TODO: return unicode character offset
-  pub fn column<D: Doc>(&self, _node: &Node<D>) -> usize {
-    self.byte_column
+  pub fn column<D: Doc>(&self, node: &Node<D>) -> usize {
+    let source = node.root.doc.get_source();
+    source.get_char_column(self.byte_column, self.byte_offset)
   }
   /// Convert to tree-sitter's Point
   pub fn ts_point(&self) -> tree_sitter::Point {
@@ -218,13 +222,15 @@ impl<'r, D: Doc> Node<'r, D> {
   /// Nodes' start position in terms of zero-based rows and columns.
   pub fn start_pos(&self) -> Position {
     let pos = self.inner.start_position();
-    Position::new(pos.row(), pos.column())
+    let byte = self.inner.start_byte();
+    Position::new(pos.row(), pos.column(), byte)
   }
 
   /// Nodes' end position in terms of rows and columns.
   pub fn end_pos(&self) -> Position {
     let pos = self.inner.end_position();
-    Position::new(pos.row(), pos.column())
+    let byte = self.inner.end_byte();
+    Position::new(pos.row(), pos.column(), byte)
   }
 
   pub fn text(&self) -> Cow<'r, str> {
@@ -742,7 +748,6 @@ if (a) {
   }
 
   #[test]
-  #[ignore = "TODO: fix column to be unicode character"]
   fn test_unicode_pos() {
     let root = Tsx.ast_grep("🦀");
     let root = root.root();
@@ -751,5 +756,12 @@ if (a) {
     assert_eq!(node.start_pos().column(&node), 0);
     assert_eq!(node.end_pos().row(), 0);
     assert_eq!(node.end_pos().column(&node), 1);
+    let root = Tsx.ast_grep("\n  🦀🦀");
+    let root = root.root();
+    let node = root.find("$A").expect("should exist");
+    assert_eq!(node.start_pos().row(), 1);
+    assert_eq!(node.start_pos().column(&node), 2);
+    assert_eq!(node.end_pos().row(), 1);
+    assert_eq!(node.end_pos().column(&node), 4);
   }
 }
diff --git a/crates/core/src/source.rs b/crates/core/src/source.rs
index 28fc6d2a55..e6b8dad6a7 100644
--- a/crates/core/src/source.rs
+++ b/crates/core/src/source.rs
@@ -146,6 +146,8 @@ pub trait Content: Sized {
   /// Used for string replacement. We need this for
   /// transformation.
   fn encode_bytes(bytes: &[Self::Underlying]) -> Cow<str>;
+  /// Get the character column at the given position
+  fn get_char_column(&self, column: usize, offset: usize) -> usize;
 }
 
 impl Content for String {
@@ -189,6 +191,25 @@ impl Content for String {
   fn encode_bytes(bytes: &[Self::Underlying]) -> Cow<str> {
     String::from_utf8_lossy(bytes)
   }
+
+  /// This is an O(n) operation. We assume the col will not be a
+  /// huge number in reality. This may be problematic for special
+  /// files like compressed js
+  fn get_char_column(&self, _col: usize, offset: usize) -> usize {
+    let src = self.as_bytes();
+    let mut col = 0;
+    // TODO: is it possible to use SIMD here???
+    for &b in src[..offset].iter().rev() {
+      if b == b'\n' {
+        break;
+      }
+      // https://en.wikipedia.org/wiki/UTF-8#Description
+      if b & 0b1100_0000 != 0b1000_0000 {
+        col += 1;
+      }
+    }
+    col
+  }
 }
 
 #[cfg(test)]
diff --git a/crates/napi/src/doc.rs b/crates/napi/src/doc.rs
index 99225d9210..eed952b813 100644
--- a/crates/napi/src/doc.rs
+++ b/crates/napi/src/doc.rs
@@ -107,6 +107,10 @@ impl Content for Wrapper {
     let s = String::from_utf16_lossy(bytes);
     Cow::Owned(s)
   }
+  fn get_char_column(&self, column: usize, _offset: usize) -> usize {
+    // utf-16 is 2 bytes per character, this is O(1) operation!
+    column / 2
+  }
 }
 
 fn pos_for_byte_offset(input: &[u16], byte_offset: usize) -> Point {
diff --git a/crates/napi/src/sg_node.rs b/crates/napi/src/sg_node.rs
index 59a9a89200..fb752621e6 100644
--- a/crates/napi/src/sg_node.rs
+++ b/crates/napi/src/sg_node.rs
@@ -43,8 +43,7 @@ impl SgNode {
   fn to_pos(&self, pos: Position, offset: usize) -> Pos {
     Pos {
       line: pos.row() as u32,
-      // TODO: remove the division by 2 hack
-      column: pos.column(&self.inner) as u32 / 2,
+      column: pos.column(&self.inner) as u32,
       index: offset as u32 / 2,
     }
   }


Test patch:
diff --git a/crates/pyo3/tests/test_range.py b/crates/pyo3/tests/test_range.py
index 9b72a9b3b4..037fb3517d 100644
--- a/crates/pyo3/tests/test_range.py
+++ b/crates/pyo3/tests/test_range.py
@@ -48,5 +48,4 @@ def test_unicode():
     assert node is not None
     assert node.range().start.index == 5
     assert node.range().start.line == 0
-    # TODO: Fix this, it should be 5 in character
-    # assert node.range().start.column == 5
\ No newline at end of file
+    assert node.range().start.column == 5
\ No newline at end of file