xposmap.go

     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  
     5  package ssa
     6  
     7  import (
     8  	"cmd/internal/src"
     9  	"fmt"
    10  )
    11  
    12  type 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.
    20  type 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.
    31  func 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.
    40  func (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.
    51  func (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.
    63  func (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.
    72  func (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.
    83  func (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.
    89  func (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.
    99  func (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.
   108  func (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
View as plain text