1# SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
2"""Parse or generate representations of perf metrics."""
3import ast
4import decimal
5import json
6import re
7from typing import Dict, List, Optional, Set, Tuple, Union
8
9
10class Expression:
11  """Abstract base class of elements in a metric expression."""
12
13  def ToPerfJson(self) -> str:
14    """Returns a perf json file encoded representation."""
15    raise NotImplementedError()
16
17  def ToPython(self) -> str:
18    """Returns a python expr parseable representation."""
19    raise NotImplementedError()
20
21  def Simplify(self):
22    """Returns a simplified version of self."""
23    raise NotImplementedError()
24
25  def Equals(self, other) -> bool:
26    """Returns true when two expressions are the same."""
27    raise NotImplementedError()
28
29  def Substitute(self, name: str, expression: 'Expression') -> 'Expression':
30    raise NotImplementedError()
31
32  def __str__(self) -> str:
33    return self.ToPerfJson()
34
35  def __or__(self, other: Union[int, float, 'Expression']) -> 'Operator':
36    return Operator('|', self, other)
37
38  def __ror__(self, other: Union[int, float, 'Expression']) -> 'Operator':
39    return Operator('|', other, self)
40
41  def __xor__(self, other: Union[int, float, 'Expression']) -> 'Operator':
42    return Operator('^', self, other)
43
44  def __and__(self, other: Union[int, float, 'Expression']) -> 'Operator':
45    return Operator('&', self, other)
46
47  def __rand__(self, other: Union[int, float, 'Expression']) -> 'Operator':
48    return Operator('&', other, self)
49
50  def __lt__(self, other: Union[int, float, 'Expression']) -> 'Operator':
51    return Operator('<', self, other)
52
53  def __gt__(self, other: Union[int, float, 'Expression']) -> 'Operator':
54    return Operator('>', self, other)
55
56  def __add__(self, other: Union[int, float, 'Expression']) -> 'Operator':
57    return Operator('+', self, other)
58
59  def __radd__(self, other: Union[int, float, 'Expression']) -> 'Operator':
60    return Operator('+', other, self)
61
62  def __sub__(self, other: Union[int, float, 'Expression']) -> 'Operator':
63    return Operator('-', self, other)
64
65  def __rsub__(self, other: Union[int, float, 'Expression']) -> 'Operator':
66    return Operator('-', other, self)
67
68  def __mul__(self, other: Union[int, float, 'Expression']) -> 'Operator':
69    return Operator('*', self, other)
70
71  def __rmul__(self, other: Union[int, float, 'Expression']) -> 'Operator':
72    return Operator('*', other, self)
73
74  def __truediv__(self, other: Union[int, float, 'Expression']) -> 'Operator':
75    return Operator('/', self, other)
76
77  def __rtruediv__(self, other: Union[int, float, 'Expression']) -> 'Operator':
78    return Operator('/', other, self)
79
80  def __mod__(self, other: Union[int, float, 'Expression']) -> 'Operator':
81    return Operator('%', self, other)
82
83
84def _Constify(val: Union[bool, int, float, Expression]) -> Expression:
85  """Used to ensure that the nodes in the expression tree are all Expression."""
86  if isinstance(val, bool):
87    return Constant(1 if val else 0)
88  if isinstance(val, (int, float)):
89    return Constant(val)
90  return val
91
92
93# Simple lookup for operator precedence, used to avoid unnecessary
94# brackets. Precedence matches that of the simple expression parser
95# but differs from python where comparisons are lower precedence than
96# the bitwise &, ^, | but not the logical versions that the expression
97# parser doesn't have.
98_PRECEDENCE = {
99    '|': 0,
100    '^': 1,
101    '&': 2,
102    '<': 3,
103    '>': 3,
104    '+': 4,
105    '-': 4,
106    '*': 5,
107    '/': 5,
108    '%': 5,
109}
110
111
112class Operator(Expression):
113  """Represents a binary operator in the parse tree."""
114
115  def __init__(self, operator: str, lhs: Union[int, float, Expression],
116               rhs: Union[int, float, Expression]):
117    self.operator = operator
118    self.lhs = _Constify(lhs)
119    self.rhs = _Constify(rhs)
120
121  def Bracket(self,
122              other: Expression,
123              other_str: str,
124              rhs: bool = False) -> str:
125    """If necessary brackets the given other value.
126
127    If ``other`` is an operator then a bracket is necessary when
128    this/self operator has higher precedence. Consider: '(a + b) * c',
129    ``other_str`` will be 'a + b'. A bracket is necessary as without
130    the bracket 'a + b * c' will evaluate 'b * c' first. However, '(a
131    * b) + c' doesn't need a bracket as 'a * b' will always be
132    evaluated first. For 'a / (b * c)' (ie the same precedence level
133    operations) then we add the bracket to best match the original
134    input, but not for '(a / b) * c' where the bracket is unnecessary.
135
136    Args:
137      other (Expression): is a lhs or rhs operator
138      other_str (str): ``other`` in the appropriate string form
139      rhs (bool):  is ``other`` on the RHS
140
141    Returns:
142      str: possibly bracketed other_str
143    """
144    if isinstance(other, Operator):
145      if _PRECEDENCE.get(self.operator, -1) > _PRECEDENCE.get(
146          other.operator, -1):
147        return f'({other_str})'
148      if rhs and _PRECEDENCE.get(self.operator, -1) == _PRECEDENCE.get(
149          other.operator, -1):
150        return f'({other_str})'
151    return other_str
152
153  def ToPerfJson(self):
154    return (f'{self.Bracket(self.lhs, self.lhs.ToPerfJson())} {self.operator} '
155            f'{self.Bracket(self.rhs, self.rhs.ToPerfJson(), True)}')
156
157  def ToPython(self):
158    return (f'{self.Bracket(self.lhs, self.lhs.ToPython())} {self.operator} '
159            f'{self.Bracket(self.rhs, self.rhs.ToPython(), True)}')
160
161  def Simplify(self) -> Expression:
162    lhs = self.lhs.Simplify()
163    rhs = self.rhs.Simplify()
164    if isinstance(lhs, Constant) and isinstance(rhs, Constant):
165      return Constant(ast.literal_eval(lhs + self.operator + rhs))
166
167    if isinstance(self.lhs, Constant):
168      if self.operator in ('+', '|') and lhs.value == '0':
169        return rhs
170
171      # Simplify multiplication by 0 except for the slot event which
172      # is deliberately introduced using this pattern.
173      if self.operator == '*' and lhs.value == '0' and (
174          not isinstance(rhs, Event) or 'slots' not in rhs.name.lower()):
175        return Constant(0)
176
177      if self.operator == '*' and lhs.value == '1':
178        return rhs
179
180    if isinstance(rhs, Constant):
181      if self.operator in ('+', '|') and rhs.value == '0':
182        return lhs
183
184      if self.operator == '*' and rhs.value == '0':
185        return Constant(0)
186
187      if self.operator == '*' and self.rhs.value == '1':
188        return lhs
189
190    return Operator(self.operator, lhs, rhs)
191
192  def Equals(self, other: Expression) -> bool:
193    if isinstance(other, Operator):
194      return self.operator == other.operator and self.lhs.Equals(
195          other.lhs) and self.rhs.Equals(other.rhs)
196    return False
197
198  def Substitute(self, name: str, expression: Expression) -> Expression:
199    if self.Equals(expression):
200      return Event(name)
201    lhs = self.lhs.Substitute(name, expression)
202    rhs = None
203    if self.rhs:
204      rhs = self.rhs.Substitute(name, expression)
205    return Operator(self.operator, lhs, rhs)
206
207
208class Select(Expression):
209  """Represents a select ternary in the parse tree."""
210
211  def __init__(self, true_val: Union[int, float, Expression],
212               cond: Union[int, float, Expression],
213               false_val: Union[int, float, Expression]):
214    self.true_val = _Constify(true_val)
215    self.cond = _Constify(cond)
216    self.false_val = _Constify(false_val)
217
218  def ToPerfJson(self):
219    true_str = self.true_val.ToPerfJson()
220    cond_str = self.cond.ToPerfJson()
221    false_str = self.false_val.ToPerfJson()
222    return f'({true_str} if {cond_str} else {false_str})'
223
224  def ToPython(self):
225    return (f'Select({self.true_val.ToPython()}, {self.cond.ToPython()}, '
226            f'{self.false_val.ToPython()})')
227
228  def Simplify(self) -> Expression:
229    cond = self.cond.Simplify()
230    true_val = self.true_val.Simplify()
231    false_val = self.false_val.Simplify()
232    if isinstance(cond, Constant):
233      return false_val if cond.value == '0' else true_val
234
235    if true_val.Equals(false_val):
236      return true_val
237
238    return Select(true_val, cond, false_val)
239
240  def Equals(self, other: Expression) -> bool:
241    if isinstance(other, Select):
242      return self.cond.Equals(other.cond) and self.false_val.Equals(
243          other.false_val) and self.true_val.Equals(other.true_val)
244    return False
245
246  def Substitute(self, name: str, expression: Expression) -> Expression:
247    if self.Equals(expression):
248      return Event(name)
249    true_val = self.true_val.Substitute(name, expression)
250    cond = self.cond.Substitute(name, expression)
251    false_val = self.false_val.Substitute(name, expression)
252    return Select(true_val, cond, false_val)
253
254
255class Function(Expression):
256  """A function in an expression like min, max, d_ratio."""
257
258  def __init__(self,
259               fn: str,
260               lhs: Union[int, float, Expression],
261               rhs: Optional[Union[int, float, Expression]] = None):
262    self.fn = fn
263    self.lhs = _Constify(lhs)
264    self.rhs = _Constify(rhs)
265
266  def ToPerfJson(self):
267    if self.rhs:
268      return f'{self.fn}({self.lhs.ToPerfJson()}, {self.rhs.ToPerfJson()})'
269    return f'{self.fn}({self.lhs.ToPerfJson()})'
270
271  def ToPython(self):
272    if self.rhs:
273      return f'{self.fn}({self.lhs.ToPython()}, {self.rhs.ToPython()})'
274    return f'{self.fn}({self.lhs.ToPython()})'
275
276  def Simplify(self) -> Expression:
277    lhs = self.lhs.Simplify()
278    rhs = self.rhs.Simplify() if self.rhs else None
279    if isinstance(lhs, Constant) and isinstance(rhs, Constant):
280      if self.fn == 'd_ratio':
281        if rhs.value == '0':
282          return Constant(0)
283        Constant(ast.literal_eval(f'{lhs} / {rhs}'))
284      return Constant(ast.literal_eval(f'{self.fn}({lhs}, {rhs})'))
285
286    return Function(self.fn, lhs, rhs)
287
288  def Equals(self, other: Expression) -> bool:
289    if isinstance(other, Function):
290      result = self.fn == other.fn and self.lhs.Equals(other.lhs)
291      if self.rhs:
292        result = result and self.rhs.Equals(other.rhs)
293      return result
294    return False
295
296  def Substitute(self, name: str, expression: Expression) -> Expression:
297    if self.Equals(expression):
298      return Event(name)
299    lhs = self.lhs.Substitute(name, expression)
300    rhs = None
301    if self.rhs:
302      rhs = self.rhs.Substitute(name, expression)
303    return Function(self.fn, lhs, rhs)
304
305
306def _FixEscapes(s: str) -> str:
307  s = re.sub(r'([^\\]),', r'\1\\,', s)
308  return re.sub(r'([^\\])=', r'\1\\=', s)
309
310
311class Event(Expression):
312  """An event in an expression."""
313
314  def __init__(self, name: str, legacy_name: str = ''):
315    self.name = _FixEscapes(name)
316    self.legacy_name = _FixEscapes(legacy_name)
317
318  def ToPerfJson(self):
319    result = re.sub('/', '@', self.name)
320    return result
321
322  def ToPython(self):
323    return f'Event(r"{self.name}")'
324
325  def Simplify(self) -> Expression:
326    return self
327
328  def Equals(self, other: Expression) -> bool:
329    return isinstance(other, Event) and self.name == other.name
330
331  def Substitute(self, name: str, expression: Expression) -> Expression:
332    return self
333
334
335class Constant(Expression):
336  """A constant within the expression tree."""
337
338  def __init__(self, value: Union[float, str]):
339    ctx = decimal.Context()
340    ctx.prec = 20
341    dec = ctx.create_decimal(repr(value) if isinstance(value, float) else value)
342    self.value = dec.normalize().to_eng_string()
343    self.value = self.value.replace('+', '')
344    self.value = self.value.replace('E', 'e')
345
346  def ToPerfJson(self):
347    return self.value
348
349  def ToPython(self):
350    return f'Constant({self.value})'
351
352  def Simplify(self) -> Expression:
353    return self
354
355  def Equals(self, other: Expression) -> bool:
356    return isinstance(other, Constant) and self.value == other.value
357
358  def Substitute(self, name: str, expression: Expression) -> Expression:
359    return self
360
361
362class Literal(Expression):
363  """A runtime literal within the expression tree."""
364
365  def __init__(self, value: str):
366    self.value = value
367
368  def ToPerfJson(self):
369    return self.value
370
371  def ToPython(self):
372    return f'Literal({self.value})'
373
374  def Simplify(self) -> Expression:
375    return self
376
377  def Equals(self, other: Expression) -> bool:
378    return isinstance(other, Literal) and self.value == other.value
379
380  def Substitute(self, name: str, expression: Expression) -> Expression:
381    return self
382
383
384def min(lhs: Union[int, float, Expression], rhs: Union[int, float,
385                                                       Expression]) -> Function:
386  # pylint: disable=redefined-builtin
387  # pylint: disable=invalid-name
388  return Function('min', lhs, rhs)
389
390
391def max(lhs: Union[int, float, Expression], rhs: Union[int, float,
392                                                       Expression]) -> Function:
393  # pylint: disable=redefined-builtin
394  # pylint: disable=invalid-name
395  return Function('max', lhs, rhs)
396
397
398def d_ratio(lhs: Union[int, float, Expression],
399            rhs: Union[int, float, Expression]) -> Function:
400  # pylint: disable=redefined-builtin
401  # pylint: disable=invalid-name
402  return Function('d_ratio', lhs, rhs)
403
404
405def source_count(event: Event) -> Function:
406  # pylint: disable=redefined-builtin
407  # pylint: disable=invalid-name
408  return Function('source_count', event)
409
410
411def has_event(event: Event) -> Function:
412  # pylint: disable=redefined-builtin
413  # pylint: disable=invalid-name
414  return Function('has_event', event)
415
416def strcmp_cpuid_str(cpuid: Event) -> Function:
417  # pylint: disable=redefined-builtin
418  # pylint: disable=invalid-name
419  return Function('strcmp_cpuid_str', cpuid)
420
421class Metric:
422  """An individual metric that will specifiable on the perf command line."""
423  groups: Set[str]
424  expr: Expression
425  scale_unit: str
426  constraint: bool
427
428  def __init__(self,
429               name: str,
430               description: str,
431               expr: Expression,
432               scale_unit: str,
433               constraint: bool = False):
434    self.name = name
435    self.description = description
436    self.expr = expr.Simplify()
437    # Workraound valid_only_metric hiding certain metrics based on unit.
438    scale_unit = scale_unit.replace('/sec', ' per sec')
439    if scale_unit[0].isdigit():
440      self.scale_unit = scale_unit
441    else:
442      self.scale_unit = f'1{scale_unit}'
443    self.constraint = constraint
444    self.groups = set()
445
446  def __lt__(self, other):
447    """Sort order."""
448    return self.name < other.name
449
450  def AddToMetricGroup(self, group):
451    """Callback used when being added to a MetricGroup."""
452    self.groups.add(group.name)
453
454  def Flatten(self) -> Set['Metric']:
455    """Return a leaf metric."""
456    return set([self])
457
458  def ToPerfJson(self) -> Dict[str, str]:
459    """Return as dictionary for Json generation."""
460    result = {
461        'MetricName': self.name,
462        'MetricGroup': ';'.join(sorted(self.groups)),
463        'BriefDescription': self.description,
464        'MetricExpr': self.expr.ToPerfJson(),
465        'ScaleUnit': self.scale_unit
466    }
467    if self.constraint:
468      result['MetricConstraint'] = 'NO_NMI_WATCHDOG'
469
470    return result
471
472
473class _MetricJsonEncoder(json.JSONEncoder):
474  """Special handling for Metric objects."""
475
476  def default(self, o):
477    if isinstance(o, Metric):
478      return o.ToPerfJson()
479    return json.JSONEncoder.default(self, o)
480
481
482class MetricGroup:
483  """A group of metrics.
484
485  Metric groups may be specificd on the perf command line, but within
486  the json they aren't encoded. Metrics may be in multiple groups
487  which can facilitate arrangements similar to trees.
488  """
489
490  def __init__(self, name: str, metric_list: List[Union[Metric,
491                                                        'MetricGroup']]):
492    self.name = name
493    self.metric_list = metric_list
494    for metric in metric_list:
495      metric.AddToMetricGroup(self)
496
497  def AddToMetricGroup(self, group):
498    """Callback used when a MetricGroup is added into another."""
499    for metric in self.metric_list:
500      metric.AddToMetricGroup(group)
501
502  def Flatten(self) -> Set[Metric]:
503    """Returns a set of all leaf metrics."""
504    result = set()
505    for x in self.metric_list:
506      result = result.union(x.Flatten())
507
508    return result
509
510  def ToPerfJson(self) -> str:
511    return json.dumps(sorted(self.Flatten()), indent=2, cls=_MetricJsonEncoder)
512
513  def __str__(self) -> str:
514    return self.ToPerfJson()
515
516
517class _RewriteIfExpToSelect(ast.NodeTransformer):
518  """Transformer to convert if-else nodes to Select expressions."""
519
520  def visit_IfExp(self, node):
521    # pylint: disable=invalid-name
522    self.generic_visit(node)
523    call = ast.Call(
524        func=ast.Name(id='Select', ctx=ast.Load()),
525        args=[node.body, node.test, node.orelse],
526        keywords=[])
527    ast.copy_location(call, node.test)
528    return call
529
530
531def ParsePerfJson(orig: str) -> Expression:
532  """A simple json metric expression decoder.
533
534  Converts a json encoded metric expression by way of python's ast and
535  eval routine. First tokens are mapped to Event calls, then
536  accidentally converted keywords or literals are mapped to their
537  appropriate calls. Python's ast is used to match if-else that can't
538  be handled via operator overloading. Finally the ast is evaluated.
539
540  Args:
541    orig (str): String to parse.
542
543  Returns:
544    Expression: The parsed string.
545  """
546  # pylint: disable=eval-used
547  py = orig.strip()
548  # First try to convert everything that looks like a string (event name) into Event(r"EVENT_NAME").
549  # This isn't very selective so is followed up by converting some unwanted conversions back again
550  py = re.sub(r'([a-zA-Z][^-+/\* \\\(\),]*(?:\\.[^-+/\* \\\(\),]*)*)',
551              r'Event(r"\1")', py)
552  # If it started with a # it should have been a literal, rather than an event name
553  py = re.sub(r'#Event\(r"([^"]*)"\)', r'Literal("#\1")', py)
554  # Convert accidentally converted hex constants ("0Event(r"xDEADBEEF)"") back to a constant,
555  # but keep it wrapped in Event(), otherwise Python drops the 0x prefix and it gets interpreted as
556  # a double by the Bison parser
557  py = re.sub(r'0Event\(r"[xX]([0-9a-fA-F]*)"\)', r'Event("0x\1")', py)
558  # Convert accidentally converted scientific notation constants back
559  py = re.sub(r'([0-9]+)Event\(r"(e[0-9]+)"\)', r'\1\2', py)
560  # Convert all the known keywords back from events to just the keyword
561  keywords = ['if', 'else', 'min', 'max', 'd_ratio', 'source_count', 'has_event', 'strcmp_cpuid_str']
562  for kw in keywords:
563    py = re.sub(rf'Event\(r"{kw}"\)', kw, py)
564  try:
565    parsed = ast.parse(py, mode='eval')
566  except SyntaxError as e:
567    raise SyntaxError(f'Parsing expression:\n{orig}') from e
568  _RewriteIfExpToSelect().visit(parsed)
569  parsed = ast.fix_missing_locations(parsed)
570  return _Constify(eval(compile(parsed, orig, 'eval')))
571
572
573def RewriteMetricsInTermsOfOthers(metrics: List[Tuple[str, str, Expression]]
574                                  )-> Dict[Tuple[str, str], Expression]:
575  """Shorten metrics by rewriting in terms of others.
576
577  Args:
578    metrics (list): pmus, metric names and their expressions.
579  Returns:
580    Dict: mapping from a pmu, metric name pair to a shortened expression.
581  """
582  updates: Dict[Tuple[str, str], Expression] = dict()
583  for outer_pmu, outer_name, outer_expression in metrics:
584    if outer_pmu is None:
585      outer_pmu = 'cpu'
586    updated = outer_expression
587    while True:
588      for inner_pmu, inner_name, inner_expression in metrics:
589        if inner_pmu is None:
590          inner_pmu = 'cpu'
591        if inner_pmu.lower() != outer_pmu.lower():
592          continue
593        if inner_name.lower() == outer_name.lower():
594          continue
595        if (inner_pmu, inner_name) in updates:
596          inner_expression = updates[(inner_pmu, inner_name)]
597        updated = updated.Substitute(inner_name, inner_expression)
598      if updated.Equals(outer_expression):
599        break
600      if (outer_pmu, outer_name) in updates and updated.Equals(updates[(outer_pmu, outer_name)]):
601        break
602      updates[(outer_pmu, outer_name)] = updated
603  return updates
604