1// Copyright 2019 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package ssa
6
7import (
8	"cmd/internal/src"
9	"fmt"
10)
11
12type lineRange struct {
13	first, last uint32
14}
15
16// An xposmap is a map from fileindex and line of src.XPos to int32,
17// implemented sparsely to save space (column and statement status are ignored).
18// The sparse skeleton is constructed once, and then reused by ssa phases
19// that (re)move values with statements attached.
20type xposmap struct {
21	// A map from file index to maps from line range to integers (block numbers)
22	maps map[int32]*biasedSparseMap
23	// The next two fields provide a single-item cache for common case of repeated lines from same file.
24	lastIndex int32            // -1 means no entry in cache
25	lastMap   *biasedSparseMap // map found at maps[lastIndex]
26}
27
28// newXposmap constructs an xposmap valid for inputs which have a file index in the keys of x,
29// and line numbers in the range x[file index].
30// The resulting xposmap will panic if a caller attempts to set or add an XPos not in that range.
31func newXposmap(x map[int]lineRange) *xposmap {
32	maps := make(map[int32]*biasedSparseMap)
33	for i, p := range x {
34		maps[int32(i)] = newBiasedSparseMap(int(p.first), int(p.last))
35	}
36	return &xposmap{maps: maps, lastIndex: -1} // zero for the rest is okay
37}
38
39// clear removes data from the map but leaves the sparse skeleton.
40func (m *xposmap) clear() {
41	for _, l := range m.maps {
42		if l != nil {
43			l.clear()
44		}
45	}
46	m.lastIndex = -1
47	m.lastMap = nil
48}
49
50// mapFor returns the line range map for a given file index.
51func (m *xposmap) mapFor(index int32) *biasedSparseMap {
52	if index == m.lastIndex {
53		return m.lastMap
54	}
55	mf := m.maps[index]
56	m.lastIndex = index
57	m.lastMap = mf
58	return mf
59}
60
61// set inserts p->v into the map.
62// If p does not fall within the set of fileindex->lineRange used to construct m, this will panic.
63func (m *xposmap) set(p src.XPos, v int32) {
64	s := m.mapFor(p.FileIndex())
65	if s == nil {
66		panic(fmt.Sprintf("xposmap.set(%d), file index not found in map\n", p.FileIndex()))
67	}
68	s.set(p.Line(), v)
69}
70
71// get returns the int32 associated with the file index and line of p.
72func (m *xposmap) get(p src.XPos) int32 {
73	s := m.mapFor(p.FileIndex())
74	if s == nil {
75		return -1
76	}
77	return s.get(p.Line())
78}
79
80// add adds p to m, treating m as a set instead of as a map.
81// If p does not fall within the set of fileindex->lineRange used to construct m, this will panic.
82// Use clear() in between set/map interpretations of m.
83func (m *xposmap) add(p src.XPos) {
84	m.set(p, 0)
85}
86
87// contains returns whether the file index and line of p are in m,
88// treating m as a set instead of as a map.
89func (m *xposmap) contains(p src.XPos) bool {
90	s := m.mapFor(p.FileIndex())
91	if s == nil {
92		return false
93	}
94	return s.contains(p.Line())
95}
96
97// remove removes the file index and line for p from m,
98// whether m is currently treated as a map or set.
99func (m *xposmap) remove(p src.XPos) {
100	s := m.mapFor(p.FileIndex())
101	if s == nil {
102		return
103	}
104	s.remove(p.Line())
105}
106
107// foreachEntry applies f to each (fileindex, line, value) triple in m.
108func (m *xposmap) foreachEntry(f func(j int32, l uint, v int32)) {
109	for j, mm := range m.maps {
110		s := mm.size()
111		for i := 0; i < s; i++ {
112			l, v := mm.getEntry(i)
113			f(j, l, v)
114		}
115	}
116}
117