tools/SwiftSyntax/SyntaxData.swift - third_party/swift - Git at Google

 //===-------------------- SyntaxData.swift - Syntax Data ------------------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//

 import Foundation

 /// A unique identifier for a node in the tree.
 /// Currently, this is an index path from the current node to the root of the
 /// tree. It's an implementation detail and shouldn't be
 /// exposed to clients.
 typealias NodeIdentifier = [Int]

 /// SyntaxData is the underlying storage for each Syntax node.
 /// It's modelled as an array that stores and caches a SyntaxData for each raw
 /// syntax node in its layout. It is up to the specific Syntax nodes to maintain
 /// the correct layout of their SyntaxData backing stores.
 ///
 /// SyntaxData is an implementation detail, and should not be exposed to clients
 /// of libSyntax.
 ///
 /// The following relationships are preserved:
 ///   parent.cachedChild(at: indexInParent) === self
 ///   raw.layout.count == childCaches.count
 ///   pathToRoot.first === indexInParent
 final class SyntaxData: Equatable {

   let raw: RawSyntax
   let indexInParent: Int
   weak var parent: SyntaxData?

   let childCaches: [AtomicCache<SyntaxData>]

   let positionCache: AtomicCache<AbsolutePosition>

   fileprivate func calculatePosition(_ initPos: AbsolutePosition) ->
       AbsolutePosition {
     guard let parent = parent else {
       assert(raw.isSourceFile, "cannot find SourceFileSyntax as root")
       // If this node is SourceFileSyntax, its location is the start of the file.
       return initPos
     }

     // If the node is the first child of its parent, the location is same with
     // the parent's location.
     guard indexInParent != 0 else { return parent.position }

     // Otherwise, the location is same with the previous sibling's location
     // adding the stride of the sibling.
     for idx in (0..<indexInParent).reversed() {
       if let sibling = parent.cachedChild(at: idx) {
         let pos = sibling.position.copy()
         sibling.raw.accumulateAbsolutePosition(pos)
         return pos
       }
     }
     return parent.position
   }

   var position: AbsolutePosition {
     return positionCache.value { return calculatePosition(UTF8Position()) }
   }

   var positionAfterSkippingLeadingTrivia: AbsolutePosition {
     let result = position.copy()
     _ = raw.accumulateLeadingTrivia(result)
     return result
   }

   fileprivate func getNextSiblingPos() -> AbsolutePosition {
     // If this node is root, the position of the next sibling is the end of
     // this node.
     guard let parent = parent else {
       assert(raw.isSourceFile, "cannot find SourceFileSyntax as root")
       let result = self.position.copy()
       raw.accumulateAbsolutePosition(result)
       return result
     }

     // Find the first valid sibling and return its position.
     for i in indexInParent+1..<parent.raw.layout.count {
       guard let sibling = parent.cachedChild(at: i) else { continue }
       return sibling.position
     }
     // Otherwise, use the parent's sibling instead.
     return parent.getNextSiblingPos()
   }

   var byteSize: Int {
     return getNextSiblingPos().byteOffset - self.position.byteOffset
   }

   /// Creates a SyntaxData with the provided raw syntax, pointing to the
   /// provided index, in the provided parent.
   /// - Parameters:
   ///   - raw: The raw syntax underlying this node.
   ///   - indexInParent: The index in the parent's layout where this node will
   ///                    reside.
   ///   - parent: The parent of this node, or `nil` if this node is the root.
   required init(raw: RawSyntax, indexInParent: Int = 0,
                 parent: SyntaxData? = nil) {
     self.raw = raw
     self.indexInParent = indexInParent
     self.parent = parent
     self.childCaches = raw.layout.map { _ in AtomicCache<SyntaxData>() }
     self.positionCache = AtomicCache<AbsolutePosition>()
   }

   /// The index path from this node to the root. This can be used to uniquely
   /// identify this node in the tree.
   lazy private(set) var pathToRoot: NodeIdentifier = {
     var path = [Int]()
     var node = self
     while let parent = node.parent {
       path.append(node.indexInParent)
       node = parent
     }
     return path
   }()

   /// Returns the child data at the provided index in this data's layout.
   /// This child is cached and will be used in subsequent accesses.
   /// - Note: This function traps if the index is out of the bounds of the
   ///         data's layout.
   ///
   /// - Parameter index: The index to create and cache.
   /// - Returns: The child's data at the provided index.
   func cachedChild(at index: Int) -> SyntaxData? {
     if raw.layout[index] == nil { return nil }
     return childCaches[index].value { realizeChild(index) }
   }

   /// Returns the child data at the provided cursor in this data's layout.
   /// This child is cached and will be used in subsequent accesses.
   /// - Note: This function traps if the cursor is out of the bounds of the
   ///         data's layout.
   ///
   /// - Parameter cursor: The cursor to create and cache.
   /// - Returns: The child's data at the provided cursor.
   func cachedChild<CursorType: RawRepresentable>(
     at cursor: CursorType) -> SyntaxData?
     where CursorType.RawValue == Int {
     return cachedChild(at: cursor.rawValue)
   }

   /// Walks up the provided node's parent tree looking for the receiver.
   /// - parameter data: The potential child data.
   /// - returns: `true` if the receiver exists in the parent chain of the
   ///            provided data.
   /// - seealso: isDescendent(of:)
   func isAncestor(of data: SyntaxData) -> Bool {
     return data.isDescendent(of: self)
   }

   /// Walks up the receiver's parent tree looking for the provided node.
   /// - parameter data: The potential ancestor data.
   /// - returns: `true` if the data exists in the parent chain of the receiver.
   /// - seealso: isAncestor(of:)
   func isDescendent(of data: SyntaxData) -> Bool {
     if data == self { return true }
     var node = self
     while let parent = node.parent {
       if parent == data { return true }
       node = parent
     }
     return false
   }

   /// Creates a copy of `self` and recursively creates `SyntaxData` nodes up to
   /// the root.
   /// - parameter newRaw: The new RawSyntax that will back the new `Data`
   /// - returns: A tuple of both the new root node and the new data with the raw
   ///            layout replaced.
   func replacingSelf(
     _ newRaw: RawSyntax) -> (root: SyntaxData, newValue: SyntaxData) {
     // If we have a parent already, then ask our current parent to copy itself
     // recursively up to the root.
     if let parent = parent {
       let (root, newParent) = parent.replacingChild(newRaw, at: indexInParent)
       let newMe = newParent.cachedChild(at: indexInParent)!
       return (root: root, newValue: newMe)
     } else {
       // Otherwise, we're already the root, so return the new data as both the
       // new root and the new data.
       let newMe = SyntaxData(raw: newRaw, indexInParent: indexInParent,
                              parent: nil)
       return (root: newMe, newValue: newMe)
     }
   }

   /// Creates a copy of `self` with the child at the provided index replaced
   /// with a new SyntaxData containing the raw syntax provided.
   ///
   /// - Parameters:
   ///   - child: The raw syntax for the new child to replace.
   ///   - index: The index pointing to where in the raw layout to place this
   ///            child.
   /// - Returns: The new root node created by this operation, and the new child
   ///            syntax data.
   /// - SeeAlso: replacingSelf(_:)
   func replacingChild(_ child: RawSyntax,
     at index: Int) -> (root: SyntaxData, newValue: SyntaxData) {
     let newRaw = raw.replacingChild(index, with: child)
     return replacingSelf(newRaw)
   }

   /// Creates a copy of `self` with the child at the provided cursor replaced
   /// with a new SyntaxData containing the raw syntax provided.
   ///
   /// - Parameters:
   ///   - child: The raw syntax for the new child to replace.
   ///   - cursor: A cursor that points to the index of the child you wish to
   ///             replace
   /// - Returns: The new root node created by this operation, and the new child
   ///            syntax data.
   /// - SeeAlso: replacingSelf(_:)
   func replacingChild<CursorType: RawRepresentable>(_ child: RawSyntax,
     at cursor: CursorType) -> (root: SyntaxData, newValue: SyntaxData)
     where CursorType.RawValue == Int {
     return replacingChild(child, at: cursor.rawValue)
   }

   /// Creates the child's syntax data for the provided cursor.
   ///
   /// - Parameter cursor: The cursor pointing into the raw syntax's layout for
   ///                     the child you're creating.
   /// - Returns: A new SyntaxData for the specific child you're
   ///            creating, whose parent is pointing to self.
   func realizeChild<CursorType: RawRepresentable>(
     _ cursor: CursorType) -> SyntaxData
       where CursorType.RawValue == Int {
     return realizeChild(cursor.rawValue)
   }

   /// Creates the child's syntax data for the provided index.
   ///
   /// - Parameter cursor: The cursor pointing into the raw syntax's layout for
   ///                     the child you're creating.
   /// - Returns: A new SyntaxData for the specific child you're
   ///            creating, whose parent is pointing to self.
   func realizeChild(_ index: Int) -> SyntaxData {
     return SyntaxData(raw: raw.layout[index]!,
                       indexInParent: index,
                       parent: self)
   }

   /// Tells whether two SyntaxData nodes have the same identity.
   /// This is not structural equality.
   /// - Returns: True if both datas are exactly the same.
   static func ==(lhs: SyntaxData, rhs: SyntaxData) -> Bool {
     return lhs === rhs
   }
 }

 /// An absolute position in a source file as text - the absolute byteOffset from
 /// the start, line, and column.
 public class AbsolutePosition {
   public fileprivate(set) var byteOffset: Int
   public fileprivate(set) var line: Int
   public fileprivate(set) var column: Int

   required public init(line: Int = 1, column: Int = 1, byteOffset: Int = 0) {
     self.line = line
     self.column = column
     self.byteOffset = byteOffset
   }

   internal func add(text: String) {
      preconditionFailure("this function must be overridden")
   }

   internal func copy() -> Self {
     return type(of: self).init(line: line, column: column, byteOffset: byteOffset)
   }
 }

 extension AbsolutePosition {

   /// Add some number of columns to the position.
   internal func add(columns: Int) {
     column += columns
     byteOffset += columns
   }

   /// Add some number of newlines to the position, resetting the column.
   /// Size is byte size of newline char.
   /// '\n' and '\r' are 1, '\r\n' is 2.
   internal func add(lines: Int, size: Int) {
     line += lines
     column = 1
     byteOffset += lines * size
   }

   /// Use some text as a reference for adding to the absolute position,
   /// taking note of newlines, etc.
   fileprivate func add<C: BidirectionalCollection>(text chars: C)
       where C.Element: UnsignedInteger  {
     let cr: C.Element = 13
     let nl: C.Element = 10
     var idx = chars.startIndex
     while idx != chars.endIndex {
       let c = chars[idx]
       idx = chars.index(after: idx)
       switch c {
       case cr:
         if chars[idx] == nl {
           add(lines: 1, size: 2)
           idx = chars.index(after: idx)
         } else {
           add(lines: 1, size: 1)
         }
       case nl:
         add(lines: 1, size: 1)
       default:
         add(columns: 1)
       }
     }
   }
 }

 class UTF8Position: AbsolutePosition {
   internal override func add(text: String) {
     add(text: text.utf8)
   }
 }

 class UTF16Position: AbsolutePosition {
   internal override func add(text: String) {
     add(text: text.utf16)
   }
 }
	//===-------------------- SyntaxData.swift - Syntax Data ------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	import Foundation

	/// A unique identifier for a node in the tree.
	/// Currently, this is an index path from the current node to the root of the
	/// tree. It's an implementation detail and shouldn't be
	/// exposed to clients.
	typealias NodeIdentifier = [Int]

	/// SyntaxData is the underlying storage for each Syntax node.
	/// It's modelled as an array that stores and caches a SyntaxData for each raw
	/// syntax node in its layout. It is up to the specific Syntax nodes to maintain
	/// the correct layout of their SyntaxData backing stores.
	///
	/// SyntaxData is an implementation detail, and should not be exposed to clients
	/// of libSyntax.
	///
	/// The following relationships are preserved:
	/// parent.cachedChild(at: indexInParent) === self
	/// raw.layout.count == childCaches.count
	/// pathToRoot.first === indexInParent
	final class SyntaxData: Equatable {

	let raw: RawSyntax
	let indexInParent: Int
	weak var parent: SyntaxData?

	let childCaches: [AtomicCache<SyntaxData>]

	let positionCache: AtomicCache<AbsolutePosition>

	fileprivate func calculatePosition(_ initPos: AbsolutePosition) ->
	AbsolutePosition {
	guard let parent = parent else {
	assert(raw.isSourceFile, "cannot find SourceFileSyntax as root")
	// If this node is SourceFileSyntax, its location is the start of the file.
	return initPos
	}

	// If the node is the first child of its parent, the location is same with
	// the parent's location.
	guard indexInParent != 0 else { return parent.position }

	// Otherwise, the location is same with the previous sibling's location
	// adding the stride of the sibling.
	for idx in (0..<indexInParent).reversed() {
	if let sibling = parent.cachedChild(at: idx) {
	let pos = sibling.position.copy()
	sibling.raw.accumulateAbsolutePosition(pos)
	return pos
	}
	}
	return parent.position
	}

	var position: AbsolutePosition {
	return positionCache.value { return calculatePosition(UTF8Position()) }
	}

	var positionAfterSkippingLeadingTrivia: AbsolutePosition {
	let result = position.copy()
	_ = raw.accumulateLeadingTrivia(result)
	return result
	}

	fileprivate func getNextSiblingPos() -> AbsolutePosition {
	// If this node is root, the position of the next sibling is the end of
	// this node.
	guard let parent = parent else {
	assert(raw.isSourceFile, "cannot find SourceFileSyntax as root")
	let result = self.position.copy()
	raw.accumulateAbsolutePosition(result)
	return result
	}

	// Find the first valid sibling and return its position.
	for i in indexInParent+1..<parent.raw.layout.count {
	guard let sibling = parent.cachedChild(at: i) else { continue }
	return sibling.position
	}
	// Otherwise, use the parent's sibling instead.
	return parent.getNextSiblingPos()
	}

	var byteSize: Int {
	return getNextSiblingPos().byteOffset - self.position.byteOffset
	}

	/// Creates a SyntaxData with the provided raw syntax, pointing to the
	/// provided index, in the provided parent.
	/// - Parameters:
	/// - raw: The raw syntax underlying this node.
	/// - indexInParent: The index in the parent's layout where this node will
	/// reside.
	/// - parent: The parent of this node, or `nil` if this node is the root.
	required init(raw: RawSyntax, indexInParent: Int = 0,
	parent: SyntaxData? = nil) {
	self.raw = raw
	self.indexInParent = indexInParent
	self.parent = parent
	self.childCaches = raw.layout.map { _ in AtomicCache<SyntaxData>() }
	self.positionCache = AtomicCache<AbsolutePosition>()
	}

	/// The index path from this node to the root. This can be used to uniquely
	/// identify this node in the tree.
	lazy private(set) var pathToRoot: NodeIdentifier = {
	var path = [Int]()
	var node = self
	while let parent = node.parent {
	path.append(node.indexInParent)
	node = parent
	}
	return path
	}()

	/// Returns the child data at the provided index in this data's layout.
	/// This child is cached and will be used in subsequent accesses.
	/// - Note: This function traps if the index is out of the bounds of the
	/// data's layout.
	///
	/// - Parameter index: The index to create and cache.
	/// - Returns: The child's data at the provided index.
	func cachedChild(at index: Int) -> SyntaxData? {
	if raw.layout[index] == nil { return nil }
	return childCaches[index].value { realizeChild(index) }
	}

	/// Returns the child data at the provided cursor in this data's layout.
	/// This child is cached and will be used in subsequent accesses.
	/// - Note: This function traps if the cursor is out of the bounds of the
	/// data's layout.
	///
	/// - Parameter cursor: The cursor to create and cache.
	/// - Returns: The child's data at the provided cursor.
	func cachedChild<CursorType: RawRepresentable>(
	at cursor: CursorType) -> SyntaxData?
	where CursorType.RawValue == Int {
	return cachedChild(at: cursor.rawValue)
	}

	/// Walks up the provided node's parent tree looking for the receiver.
	/// - parameter data: The potential child data.
	/// - returns: `true` if the receiver exists in the parent chain of the
	/// provided data.
	/// - seealso: isDescendent(of:)
	func isAncestor(of data: SyntaxData) -> Bool {
	return data.isDescendent(of: self)
	}

	/// Walks up the receiver's parent tree looking for the provided node.
	/// - parameter data: The potential ancestor data.
	/// - returns: `true` if the data exists in the parent chain of the receiver.
	/// - seealso: isAncestor(of:)
	func isDescendent(of data: SyntaxData) -> Bool {
	if data == self { return true }
	var node = self
	while let parent = node.parent {
	if parent == data { return true }
	node = parent
	}
	return false
	}

	/// Creates a copy of `self` and recursively creates `SyntaxData` nodes up to
	/// the root.
	/// - parameter newRaw: The new RawSyntax that will back the new `Data`
	/// - returns: A tuple of both the new root node and the new data with the raw
	/// layout replaced.
	func replacingSelf(
	_ newRaw: RawSyntax) -> (root: SyntaxData, newValue: SyntaxData) {
	// If we have a parent already, then ask our current parent to copy itself
	// recursively up to the root.
	if let parent = parent {
	let (root, newParent) = parent.replacingChild(newRaw, at: indexInParent)
	let newMe = newParent.cachedChild(at: indexInParent)!
	return (root: root, newValue: newMe)
	} else {
	// Otherwise, we're already the root, so return the new data as both the
	// new root and the new data.
	let newMe = SyntaxData(raw: newRaw, indexInParent: indexInParent,
	parent: nil)
	return (root: newMe, newValue: newMe)
	}
	}

	/// Creates a copy of `self` with the child at the provided index replaced
	/// with a new SyntaxData containing the raw syntax provided.
	///
	/// - Parameters:
	/// - child: The raw syntax for the new child to replace.
	/// - index: The index pointing to where in the raw layout to place this
	/// child.
	/// - Returns: The new root node created by this operation, and the new child
	/// syntax data.
	/// - SeeAlso: replacingSelf(_:)
	func replacingChild(_ child: RawSyntax,
	at index: Int) -> (root: SyntaxData, newValue: SyntaxData) {
	let newRaw = raw.replacingChild(index, with: child)
	return replacingSelf(newRaw)
	}

	/// Creates a copy of `self` with the child at the provided cursor replaced
	/// with a new SyntaxData containing the raw syntax provided.
	///
	/// - Parameters:
	/// - child: The raw syntax for the new child to replace.
	/// - cursor: A cursor that points to the index of the child you wish to
	/// replace
	/// - Returns: The new root node created by this operation, and the new child
	/// syntax data.
	/// - SeeAlso: replacingSelf(_:)
	func replacingChild<CursorType: RawRepresentable>(_ child: RawSyntax,
	at cursor: CursorType) -> (root: SyntaxData, newValue: SyntaxData)
	where CursorType.RawValue == Int {
	return replacingChild(child, at: cursor.rawValue)
	}

	/// Creates the child's syntax data for the provided cursor.
	///
	/// - Parameter cursor: The cursor pointing into the raw syntax's layout for
	/// the child you're creating.
	/// - Returns: A new SyntaxData for the specific child you're
	/// creating, whose parent is pointing to self.
	func realizeChild<CursorType: RawRepresentable>(
	_ cursor: CursorType) -> SyntaxData
	where CursorType.RawValue == Int {
	return realizeChild(cursor.rawValue)
	}

	/// Creates the child's syntax data for the provided index.
	///
	/// - Parameter cursor: The cursor pointing into the raw syntax's layout for
	/// the child you're creating.
	/// - Returns: A new SyntaxData for the specific child you're
	/// creating, whose parent is pointing to self.
	func realizeChild(_ index: Int) -> SyntaxData {
	return SyntaxData(raw: raw.layout[index]!,
	indexInParent: index,
	parent: self)
	}

	/// Tells whether two SyntaxData nodes have the same identity.
	/// This is not structural equality.
	/// - Returns: True if both datas are exactly the same.
	static func ==(lhs: SyntaxData, rhs: SyntaxData) -> Bool {
	return lhs === rhs
	}
	}

	/// An absolute position in a source file as text - the absolute byteOffset from
	/// the start, line, and column.
	public class AbsolutePosition {
	public fileprivate(set) var byteOffset: Int
	public fileprivate(set) var line: Int
	public fileprivate(set) var column: Int

	required public init(line: Int = 1, column: Int = 1, byteOffset: Int = 0) {
	self.line = line
	self.column = column
	self.byteOffset = byteOffset
	}

	internal func add(text: String) {
	preconditionFailure("this function must be overridden")
	}

	internal func copy() -> Self {
	return type(of: self).init(line: line, column: column, byteOffset: byteOffset)
	}
	}

	extension AbsolutePosition {

	/// Add some number of columns to the position.
	internal func add(columns: Int) {
	column += columns
	byteOffset += columns
	}

	/// Add some number of newlines to the position, resetting the column.
	/// Size is byte size of newline char.
	/// '\n' and '\r' are 1, '\r\n' is 2.
	internal func add(lines: Int, size: Int) {
	line += lines
	column = 1
	byteOffset += lines * size
	}

	/// Use some text as a reference for adding to the absolute position,
	/// taking note of newlines, etc.
	fileprivate func add<C: BidirectionalCollection>(text chars: C)
	where C.Element: UnsignedInteger {
	let cr: C.Element = 13
	let nl: C.Element = 10
	var idx = chars.startIndex
	while idx != chars.endIndex {
	let c = chars[idx]
	idx = chars.index(after: idx)
	switch c {
	case cr:
	if chars[idx] == nl {
	add(lines: 1, size: 2)
	idx = chars.index(after: idx)
	} else {
	add(lines: 1, size: 1)
	}
	case nl:
	add(lines: 1, size: 1)
	default:
	add(columns: 1)
	}
	}
	}
	}

	class UTF8Position: AbsolutePosition {
	internal override func add(text: String) {
	add(text: text.utf8)
	}
	}

	class UTF16Position: AbsolutePosition {
	internal override func add(text: String) {
	add(text: text.utf16)
	}
	}