Efficient immutable syntax representation with incremental change

US11372630B2 · kind B2 · utility

Assignee

• MICROSOFT TECHNOLOGY LICENSING, LLC · US

Inventors

• Matthew J. Warren · Redmond, US
• Mads Torgersen · Bellevue, US
• Renaud Paquay · Redmond, US
• Neal M. Gafter · Allen, US
• Jared Porter Parsons · Kirkland, US
• David N. Schach · Redmond, US
• Aleksey V. Tsingauz · Seattle, US
• Peter Golde · Bellevue, US
• Kevin Andrew Pilch · Snohomish, US
• Karen Liu · Bellevue, US

Key dates

• Filing date: Feb 17, 2020
• Grant date: Jun 28, 2022
• Expiry date: Sep 13, 2040

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F8/48
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Efficient immutable syntax representation with parent pointers under incremental change is enabled by creating a data structure comprising at least one tree structure that allows both upward and downward references in the tree and a tree structure that is immutable (read-only), and allows parts of itself to be re-used in other data structures. The data structure described enables tools to search and target particular sub trees. The fragment of the tree representing the targeted sub tree is produced as it is used. The rest of the tree is not produced. The read-only tree retains relative information, allowing it to be reassembled and shared.